Research map / Optimization / Distributed and compressed
Convergence of Distributed Adaptive Optimization with Local Updates
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proves convergence of Local SGD with momentum (convex) and Local Adam (weakly convex) under generalized smoothness, heavy-tailed noise, and clipping, showing local updates can beat minibatch counterparts in certain regimes.
Problem
Whether distributed adaptive methods (SGDM and Adam) with local updates (intermittent communication) provably reduce communication complexity relative to minibatch versions, under generalized smoothness and heavy-tailed noise.
Approach
Introduces an auxiliary sequence z conditionally independent of the latest stochastic gradient to build martingales, enabling a contraction proof during local iterations for momentum and adaptive (Adam) preconditioned updates with coordinate-wise clipping, yielding high-probability bounds showing local updates help.
Key results
- Local SGDM convex high-probability rate includes LD_0^2/(KR) + sigma D_0/sqrt(MKR), which can beat minibatch SGDM's LD_0^2/R when K is large.
- Local Adam in weakly convex setting achieves rate with terms tau*Delta/R + L*Delta/(KR) + sqrt(L Delta sigma^2/(MKR)), outperforming Minibatch Adam when K >~ sigma^2 R/(L Delta) and M large, tau small.
- Local SGDM proof improves the strongly convex rate over prior SGDM analysis, removing L sigma^2/(mu^2 MKR) term to sigma^2/(mu MKR).
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use local updates instead of minibatch updates | SGDM · Strongly convex setting | function suboptimality bound | Helped |
| Use local updates instead of minibatch updates | SGDM · Convex setting | function suboptimality bound | Helped |
| Use local updates instead of minibatch updates | Adam · Weakly convex setting | weighted squared gradient norm | Helped |
| Use local updates instead of minibatch updates | Adam · Noise-dominated regime | weighted squared gradient norm | No clear effect |
Surprising findings
- Local Adam's advantage over minibatch Adam is shown only in the weakly convex, small-tau regime; no convex-case Adam guarantee is given since prior convex Adam proof was flawed.
Limitations
- Results hold only for convex/weakly convex settings; non-convex advantages not established.
- Convex Adam analysis is absent; Adam result only for weakly convex functions.
- Requires bias from clipping to be negligible via K large conditions and assumes smoothness only on a bounded subset.
Experimental setup
Metrics: optimality gap f(x)-f_* communication rounds needed
Baselines: Minibatch SGDM Minibatch Adam Local SGD Local SGD with clipping
Builds on: Local SGD Adam (L0,L1)-smoothness Moreau envelope analysis of weakly convex functions
Closest papers by meaning
- Local SGD with Periodic Averaging: Tighter Analysis and Adaptive Synchronization (NeurIPS 2019 · similarity 0.89)
- Accelerated Dual Method for Distributed Optimization: An Inexact-Gradient View of Local Updates (ICML 2026 · similarity 0.89)
- Minibatch vs Local SGD for Heterogeneous Distributed Learning (NeurIPS 2020 · similarity 0.88)
- SLowcalSGD : Slow Query Points Improve Local-SGD for Stochastic Convex Optimization (NeurIPS 2024 · similarity 0.88)
- Trading Redundancy for Communication: Speeding up Distributed SGD for Non-convex Optimization (ICML 2019 · similarity 0.88)
- Faster Adaptive Decentralized Learning Algorithms (ICML 2024 · similarity 0.87)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.