Results 201 - 210 of 23737

Communication between agents often constitutes a major computational bottleneck in distributed learning. One of the most common mitigation strategies is to compress the information exchanged, thereby reducing communication overhead. To counteract the degradation in convergence associated with compressed communication, error feedback schemes -- most notably EF and EF21-- were introduced. In a series of works, we provide tight analysis of both of these methods. Specifically, we find the Lyapunov function that yields the best possible convergence rate for each method -- with matching lower bounds. This principled approach yields sharp performance guarantees and enables a rigorous, apples-to-apples comparison between EF, EF21, and compressed gradient descent. Our analysis is carried out in a variety of representative setting, which allows for clean theoretical insights and fair comparison of the underlying mechanisms.

Federated and collaborative learning methods proliferate, yet our understanding of when and why they work lags behind empirical results. A central challenge is heterogeneity: how do we characterize it, measure it, and design algorithms that handle it? Drawing on recent work in distribution shift, I argue that the field's treatment of "heterogeneity" as monolithic obscures critical distinctions between interpolation, adaptation, and generalization scenarios—each requiring different theoretical and algorithmic approaches.

I will present a taxonomy of data and algorithmic interventions for distribution shifts, and translate its implications for federated settings: When does model averaging perform safe interpolation vs. risky extrapolation across clients? What is the fundamental tradeoff between personalization and generalization, and are we optimizing for the wrong objective? Do current benchmarks measure worst-case heterogeneity, or just benign shifts? I will close with open problems at the intersection of measurement science and federated learning: how do we design benchmarks with construct validity and adapt evaluation frameworks to match real-world collaborative learning scenarios?

Please RSVP here: https://docs.google.com/forms/d/e/1FAIpQLSdykNQoztvAZvoCTfkno1FCQvE1EQsHZ-d32-pqpO5bZjPx8w/viewform

Do you know how many computers were connected to the Internet on January 1, 1989? Or how many YouTube videos have more than 1 billion views? What about the bandwidth beneath the Atlantic Ocean?

If you want to solve problems like these, join us at our upcoming Estimathon — a team-based contest that combines trivia, game theory, and mathematical thinking. Participants will be placed in teams and will be tasked with solving 13 estimation problems in just 30 minutes.

After the Estimathon concludes, stick around for food and casual conversation with one of our Streeters to learn more about the firm’s work and opportunities.

Machine learning models must balance accuracy and fairness, but these goals often conflict, particularly when data come from multiple demographic groups. A useful tool for understanding this trade-off is the fairness-accuracy (FA) frontier, which characterizes the set of models that cannot be simultaneously improved in both fairness and accuracy. Prior analyses of the FA frontier provide a full characterization under the assumption of complete knowledge of population distributions, an unrealistic ideal. We study the FA frontier in the finite-sample regime, showing how it deviates from its population counterpart and quantifying the worst-case gap between them. In particular, we derive minimax-optimal estimators that depend on the designer's knowledge of the covariate distribution. For each estimator, we characterize how finite-sample effects asymmetrically impact each group's risk, and identify optimal sample allocation strategies. Our results transform the FA frontier from a theoretical construct into a practical tool for policymakers and practitioners who must often design algorithms with limited data.
 

Multi-agent learning faces a fundamental tension: leveraging distributed collaboration without sacrificing the personalization needed for diverse agents. This tension intensifies when aiming for full personalization while adapting to unknown heterogeneity levels—gaining collaborative speedup when agents are similar, without performance degradation when they are different. Embracing the challenge, we propose personalized collaborative learning (PCL), a novel framework for heterogeneous agents to collaboratively learn personalized solutions with seamless adaptivity. Through carefully designed bias correction and importance correction mechanisms, our method AffPCL robustly handles both environment and objective heterogeneity. We prove that AffPCL reduces sample complexity over independent learning by a factor of $\max\{n^{-1}, \delta\}$, where $n$ is the number of agents and $\delta\in[0,1]$ measures their heterogeneity. This *affinity-based* acceleration automatically interpolates between the linear speedup of federated learning in homogeneous settings and the baseline of independent learning, without requiring prior knowledge of the system. Our analysis further reveals that an agent may obtain linear speedup even by collaborating with arbitrarily dissimilar agents, unveiling new insights into personalization and collaboration in the high heterogeneity regime.