Source-linked AI summary
First Analysis of Local GD on Heterogeneous Data
Ahmed Khaled, Konstantin Mishchenko, Peter Richtárik
TL;DR
The paper addresses how to analyze local gradient descent for smooth, convex objectives built from arbitrarily heterogeneous private device data, a setting important for federated learning. It develops a convergence analysis without bounded-dissimilarity assumptions and shows that, at low accuracy, local gradient descent has the same communication complexity as gradient descent.
Problem
Existing convergence analyses for local methods often rely on bounded gradient dissimilarity or bounded gradients, despite federated learning involving arbitrarily heterogeneous private device data.
Method
The paper analyzes local gradient descent for averaged L-smooth convex functions using average iterates, iterate variance, and average gradients.
Results
In a low-accuracy regime, local gradient descent requires the same number of iterations, and hence communications, as gradient descent.
Takeaways & Limitations
The resulting convergence analysis depends on the expected noise at the optimum, σ^2, a measure of how dissimilar the local functions are there.
Takeaways & Limitations
The analysis assumes each local function is convex and L-smooth and that the averaged objective has a minimizer.
Abstract
from arXiv · showhide
We provide the first convergence analysis of local gradient descent for minimizing the average of smooth and convex but otherwise arbitrary functions. Problems of this form and local gradient descent as a solution method are of importance in federated learning, where each function is based on private data stored by a user on a mobile device, and the data of different users can be arbitrarily heterogeneous. We show that in a low accuracy regime, the method has the same communication complexity as gradient descent.
1 Introduction
The paper studies local gradient descent for smooth, convex objectives assembled from arbitrarily heterogeneous device-local data. It motivates the method as a communication-efficient alternative for federated learning while challenging prior analyses that rely on restrictive bounded-gradient or bounded-dissimilarity assumptions.
- Problem setting: The analysis targets smooth, convex local functions whose data distributions may be arbitrarily heterogeneous across devices.Each local function is assumed L-smooth and convex, with a minimizer for the averaged objective.
- Method: Local Gradient Descent averages models across devices, then performs multiple local gradient steps independently without communication within each epoch.The method is designed to reduce communication while retaining first-order optimization scalability.
- Motivation: Federated Averaging is a stochastic local-gradient method used in federated learning, where non-i.i.d. device data can make local gradients point in different directions.Its empirical success has outpaced theoretical understanding, and too many local steps have been observed to cause divergence.
- Limitations of prior work: Prior local-method analyses commonly assume bounded gradient dissimilarity or bounded local gradients, assumptions the paper argues can be pathological or yield vacuous bounds.Bounded gradients cannot hold in unconstrained strongly convex minimization and may obscure meaningful dependence on inter-function variation.
- Limitations of prior work: Earlier work also gives a pessimistic O(H^2/T) rate, making the number of local steps H effectively O(1) if the rate is to match gradient descent.The paper contrasts this with a more meaningful variance-based analysis.
2 Convergence of Local GD
Under convex, smooth local objectives and bounded synchronization intervals, the analysis derives local GD convergence through iterate variance and Bregman-divergence recursions. In the low-accuracy regime, appropriately parameterized local GD requires the same number of communications as gradient descent, while higher accuracy incurs additional communication complexity.
- Assumptions: The analysis assumes a nonempty minimizer set, convex L-smooth local functions, and a bounded synchronization interval.These conditions define the setting under which the convergence results are established.
- Analysis: A single-step recursion controls the next iterate variance using the current variance and decreases the Bregman divergence to the optimum.For γ ≤ 1/(4L), the bound becomes ∥r_t+1∥^2 ≤ ∥r_t∥^2 + (3/2)γLV_t − γD_f(ẋ_t,x˚).
- Analysis: Theorem 1 combines variance and optimality-gap bounds to establish convergence for constant stepsize γ ≤ 1/(4LH).The resulting analysis is built from epoch-level control of the local iterate variance.
- Local GD vs GD: For target accuracy ϵ ≥ 3σ^2/L, local GD can use parameters achieving the same communication count as gradient descent.The comparison identifies a low-accuracy regime in which local computation does not increase communication complexity.
- Local GD vs SGD: For ϵ < 3σ^2/L, local GD has a different communication-complexity expression, while its convergence analogy with minibatch SGD is a 1/T rate to a σ^2-dependent neighborhood.The quantity σ^2 measures local-function dissimilarity at the optimum.
- Computation–communication trade-off: Choosing longer synchronization intervals creates a computation–communication trade-off that can alter the attainable convergence rate.The analysis discusses choices of H for rates such as 1/√T and 1/T.
3 Experiments
Experiments evaluate local gradient descent on regularized logistic regression with heterogeneous, non-i.i.d. data, comparing communication and computation trade-offs. Results closely match the theory, with local methods helping most when communication is expensive and only imprecise convergence is needed.
- Experimental setup: Experiments use regularized logistic regression on LIBSVM datasets with MPI-based communication across a 24-core machine.The experiments use full local gradients and a constant stepsize, with data partitioned non-i.i.d. by original dataset index.
- Trade-offs: When communication is significantly more expensive than gradient computation, local methods are much faster for imprecise convergence.With the reported architecture, the overall advantage is limited because full-gradient computation takes substantial time.
- Theory and experiment: The numerical results closely match the theoretical predictions.
- Convergence comparison: 1 local step is fully synchronized gradient descent and is the only method that converges precisely to the optimum.The comparison varies the number of local steps on the a5a dataset.
- Convergence comparison: Local methods show a clear communication-round advantage when only limited accuracy is required.The reported advantage concerns communication rounds rather than necessarily elapsed wall-clock time.
4 Proofs
The proofs establish convergence through technical lemmas that control averaged iterates, local-update variation, and Bregman-divergence terms under smoothness and convexity assumptions. These bounds are combined over synchronization intervals to prove the main result.
- Technical lemmas: The proof introduces technical lemmas relating averaged iterates, local quantities, and gradients at the optimum.The lemmas are stated as independent of the algorithm and are used as building blocks for the convergence argument.
- Technical lemmas: A key inequality bounds the relevant inner product by negative Bregman divergence plus a term proportional to local-update variation.The displayed bound has the form -2D_f(x̂_t,x*) + LV_t.
- Parameter conditions: A stepsize restriction γ ≤ 1/(4L) ensures favorable signs and constants in the recurrence bounds.The proof uses this condition to obtain 1 − 2γL ≥ 1/2 and 1 + 2γL ≤ 3/2.
- Main theorem: The main theorem follows by summing inequalities across synchronization intervals and applying double counting, Jensen’s inequality, and convexity.The interval-wise terms are bounded using the preceding lemmas before the final convergence claim is obtained.