Sharp Bounds for Federated Averaging (Local SGD) and Continuous Perspective

2021-11-05 · Margalit Glasgow, Honglin Yuan, Tengyu Ma

Federated Averaging (FedAvg), also known as Local SGD, is one of the most popular algorithms in Federated Learning (FL). Despite its simplicity and popularity, the convergence rate of FedAvg has thus far been undetermined. Even under the simplest assumptions (convex, smooth, homogeneous, and bounded covariance), the best-known upper and lower bounds do not match, and it is not clear whether the existing analysis captures the capacity of the algorithm. In this work, we first resolve this question by providing a lower bound for FedAvg that matches the existing upper bound, which shows the existing FedAvg upper bound analysis is not improvable. Additionally, we establish a lower bound in a heterogeneous setting that nearly matches the existing upper bound. While our lower bounds show the limitations of FedAvg, under an additional assumption of third-order smoothness, we prove more optimistic state-of-the-art convergence results in both convex and non-convex settings. Our analysis stems from a notion we call iterate bias, which is defined by the deviation of the expectation of the SGD trajectory from the noiseless gradient descent trajectory with the same initialization. We prove novel sharp bounds on this quantity, and show intuitively how to analyze this quantity from a Stochastic Differential Equation (SDE) perspective.

📄 PDF Abstract BibTeX arXiv:2111.03741

Code (1)

hongliny/sharp-bounds-for-fedavg-and-continuous-perspective 공식 구현

Tasks

Federated Learning

Methods 이 논문이 사용한 방법론

Local SGD Local SGD is a distributed training technique that runs SGD independently in parallel on different workers and averages the sequences…

SGD Stochastic Gradient Descent is an iterative optimization technique that uses minibatches of data to form an expectation of the gradient, rather than the full gradient using…

On Principled Local Optimization Methods for Federated Learning

2024-01-24 · Honglin Yuan

Federated Learning (FL), a distributed learning paradigm that scales on-device learning collaboratively, has emerged as a promising approach for decentralized AI applications. Local optimization methods such as Federated…

Federated Learning

Distributed Dual Averaging In Networks

2010-12-01 · NeurIPS 2010 12 · Alekh Agarwal, Martin J. Wainwright, John C. Duchi

The goal of decentralized optimization over a network is to optimize a global objective formed by a sum of local (possibly nonsmooth) convex functions using only local computation and communication. We develop and analyz…

What's in a Smoothness Constant? Tighter Rates for Local SGD with Bounded Second-order Heterogeneity

2026-07-16 · Kumar Kshitij Patel, Rustem Islamov, Sebastian U Stich, Aurelien Lucchi 외 arxiv

Local SGD, also known as Federated Averaging, is a widely used distributed optimization algorithm. Although Local SGD often outperforms alternatives such as Mini-batch SGD in practice, theory still only partially explain…

Distributed Optimization

Federated Averaging Langevin Dynamics: Toward a unified theory and new algorithms

2022-10-31 · Vincent Plassier, Alain Durmus, Eric Moulines

This paper focuses on Bayesian inference in a federated learning context (FL). While several distributed MCMC algorithms have been proposed, few consider the specific limitations of FL such as communication bottlenecks a…

Bayesian Inference Federated Learning

Dual Averaging for Distributed Optimization: Convergence Analysis and Network Scaling

2010-05-12 · John Duchi, Alekh Agarwal, Martin Wainwright

Distributed Optimization Stochastic Optimization