Local updates speed federated optimization but can cause bias
Faster to the Wrong Answer: The Price of Local Updates in Federated Optimization
Machine Learning
Summary
Federated optimization means training models using data held on many different devices without sharing the data itself. Doing more work locally on each device can make training updates better conditioned and faster, but it can also cause the final combined model to be biased, meaning it may not find the true best solution. The authors analyze how big this bias can get in the worst case, offering precise formulas and examples. They also show when local algorithms reach this minimum bias and extend their results beyond simple quadratic cases.
What this means in practice
- •For machine learning engineers: Design federated learning systems knowing the trade-off between faster local updates and bias in global models to balance accuracy and efficiency.
- •For distributed system architects: Build distributed optimization frameworks that account for worst-case bias introduced by local computations to improve convergence guarantees.
A theory result. No direct application yet.
Authors
Molly Wang
Abstract
Local computation can improve the conditioning of federated updates but may also introduce bias, causing their fixed point to differ from the global minimizer. We characterize the minimum worst-case bias achievable under a prescribed conditioning bound. We consider strongly convex quadratic client objectives with Hessian eigenvalues in $[μ,L]$ and local updates represented by a shared positive spectral filter. Client heterogeneity is measured by the root-mean-square gradient at the global minimizer. For a uniform surrogate condition number bounded by $χ\in[1,L/μ]$, we establish the exact worst-case bias per unit heterogeneity, $(L-μχ)/(2μL\sqrtχ)$, and show that local gradient descent with sufficiently small step sizes and proximal updates attain this bound. Our analysis reduces populations of arbitrary dimension, including noncommuting Hessians, to distributions over scalar curvatures. This reduction provides optimality certificates and worst-case constructions involving at most three scalar clients. We further extend the sharp proximal bias bound to smooth strongly convex objectives beyond quadratics and quantify the error introduced by inexact local solves.