Research map / Optimization / Nonconvex and smooth optimization
Faster Adaptive Decentralized Learning Algorithms
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.
Proposes AdaMDOS and AdaMDOF, adaptive momentum-based decentralized algorithms with gradient tracking for nonconvex stochastic and finite-sum optimization, claiming near-optimal sample complexities of Õ(ε^-3) and O(√n ε^-2).
Problem
Decentralized nonconvex stochastic and finite-sum optimization with adaptive learning rates, where prior adaptive decentralized methods suffer high sample and communication complexity (O(ε^-4)).
Approach
Combines STORM-style (AdaMDOS) or ZeroSARAH-style (AdaMDOF) variance-reduced momentum with gradient tracking and a unified adaptive matrix (Adam-like or Barzilai-Borwein-like) applied in a decentralized setting.
Key results
- AdaMDOS achieves Õ(ε^-3) sample complexity for stochastic nonconvex optimization, versus O(ε^-4) for DADAM, DAMSGrad and DAdaGrad.
- AdaMDOF achieves O(√n ε^-2) sample complexity for nonconvex finite-sum optimization and is claimed as the first adaptive decentralized method for this setting.
- In experiments, AdaMDOS outperforms adaptive decentralized baselines on logistic regression and CNN training; AdaMDOF is described as comparable to existing adaptive methods due to its large batch-size requirement.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use AdaMDOS instead of existing adaptive decentralized stochastic algorithms | Adaptive decentralized stochastic optimization · Nonconvex stochastic optimization | sample complexity: O(\epsilon^{-4}) -> \tilde{O}(\epsilon^{-3}) | Helped |
| Use AdaMDOS instead of existing adaptive decentralized stochastic algorithms | Adaptive decentralized stochastic optimization · Nonconvex stochastic optimization | communication complexity: O(\epsilon^{-4}) -> O(\epsilon^{-3}) | Helped |
| Use AdaMDOS rather than the compared adaptive methods | Adaptive decentralized optimization · w8a and covertype; ring and 3-regular networks | stationary gap | Helped |
| Use AdaMDOF rather than the compared adaptive methods | Adaptive decentralized optimization · w8a and covertype; ring and 3-regular networks | stationary gap | No clear effect |
| Use AdaMDOS rather than the compared adaptive methods | Adaptive decentralized CNN training · MNIST; ring and 3-regular networks | training loss | Helped |
| Use AdaMDOF rather than the compared adaptive methods | Adaptive decentralized CNN training · MNIST; ring and 3-regular networks | training loss | No clear effect |
| Use AdaMDOS rather than DADAM and D² | Decentralized ResNet-18 training · Tiny-ImageNet; ring and 3-regular networks | test accuracy | Mixed |
Surprising findings
- On ResNet-18 Tiny-ImageNet, DADAM and D^2 outperform AdaMDOS early in training before AdaMDOS overtakes them.
Limitations
- Convergence analysis excludes sparse stochastic gradients and specific adaptive cases, relying on a unified adaptive matrix with bounded eigenvalues (A ⪰ ρI).
- AdaMDOF requires large minibatch size b=√n, so it is comparable rather than superior to baselines in experiments.
- Experiments are limited to small-scale tasks with 5 clients and simple models (logistic regression, small CNN, ResNet-18).
Experimental setup
Datasets: w8a covertype MNIST Tiny-ImageNet
Benchmarks: w8a covertype MNIST Tiny-ImageNet
Metrics: stationary gap training loss training accuracy test accuracy
Baselines: DADAM DAMSGrad DAdaGrad D-PSGD D^2
Builds on: STORM ZeroSARAH gradient tracking Adam D-PSGD
Closest papers by meaning
- An Online Optimization Perspective on First-Order and Zero-Order Decentralized Nonsmooth Nonconvex Stochastic Optimization (ICML 2024 · similarity 0.88)
- Decentralized Sum-of-Nonconvex Optimization (AAAI 2024 · similarity 0.88)
- Enhancing Parallelism in Decentralized Stochastic Convex Optimization (ICML 2025 · similarity 0.87)
- Hybrid Decentralized Optimization: Leveraging Both First- and Zeroth-Order Optimizers for Faster Convergence (AAAI 2025 · similarity 0.87)
- Decentralized Convex Finite-Sum Optimization with Better Dependence on Condition Numbers (ICML 2024 · similarity 0.87)
- Convergence of Distributed Adaptive Optimization with Local Updates (ICLR 2025 · 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.