Papers for

federated learning system builders

Papers whose findings have a practical use for this group, as judged from the abstract. Open a paper to read what it means in practice.

Distributed algorithms stay stable despite heavy delays in updates

Distributed Stochastic Approximation Algorithms and Heavy-Tailed Age of Information

Abstract: Algorithms in multi-agent systems such as federated learning, mobile robotic swarming, and consensus control can be designed and analyzed as distributed stochastic approximation algorithms. Such algorithms involve information exchanges between agents for various computations. The freshness of the information can be quantified using the Age of Information (AoI) metric. Consider robotic teams operating in highly obstructed geographical settings, such as subterranean or dense urban environments. Because of spatial disconnections, AoI has empirically been observed to be heavy-tailed with unbounded moments. However, most analyses assume AoI with bounded moments, creating a gap between theory and practice. To the best of our knowledge, ours is the first analysis under general heavy-tailed AoI with potentially infinite mean. We study the stability (almost sure boundedness of the distributed iterates) and convergence of multi-agent systems that are strictly dissipative in the scaling limit (system at ``infinity''). Examples include most gradient-based and consensus algorithms under the Robbins-Monro step-size regime.

Wed 23 SeptDistributed, Parallel, and Cluster ComputingMultiagent SystemsNetworking and Internet Architecture
The gist
Many systems where multiple agents or robots work together need fresh information to make decisions. When communication is slowed down or interrupted, the delay in receiving updates can be very unpredictable and sometimes extremely long. The authors studied what happens when these delays have heavy tails, meaning delays can sometimes be huge and unbounded, unlike previous studies that assumed delays are always manageable. They found that even under such challenging conditions, certain distributed algorithms can still stay stable and eventually work correctly.
Open → 2609.27499v1

Batched updates improve stochastic gradient descent with high confidence

High-Probability Convergence of SGD via Batched Updates

Abstract: Stochastic gradient descent (SGD) is the primary workhorse for large-scale optimization. While the average behavior of its iterates, typically characterized by mean-squared error bounds, is well-understood, obtaining high-probability guarantees for the last iterate remains challenging. Prior approaches to this problem have either imposed restrictive assumptions (such as bounded domains or gradients) or relied on complex proofs involving auxiliary sequences. In this work, we propose Batched SGD, a simple variant that partitions online samples into epochs and performs a single update per epoch using a refined, low-variance gradient estimate. Our main contribution demonstrates that this batching mechanism enables a surprisingly simple high-probability analysis that avoids both restrictive assumptions and auxiliary sequences. Under standard smoothness and norm-sub-Gaussian noise assumptions, we establish near-optimal rates for both strongly convex and non-convex objectives. Furthermore, we show that our batching idea extends naturally to federated learning (FL). We provide the first high-probability guarantees for FL, achieving logarithmic communication complexity, linear speedup in the number of agents, and resilience to data heterogeneity.

Fri 11 SeptMachine Learning
The gist
Stochastic gradient descent (SGD) is a key method used to train machine learning models, but it’s hard to guarantee its performance with strong confidence just from the last update. The authors introduce a simple change called Batched SGD, which groups data samples into chunks and updates the model once per chunk using more precise estimates. This approach helps prove that the method works well with high probability, without needing strict assumptions about the problem. They also show that this idea can improve federated learning, where many devices cooperate to train models efficiently and reliably.
Open → 2609.12765v1