Research map / Optimization / Distributed and compressed
Hybrid Decentralized Optimization: Leveraging Both First- and Zeroth-Order Optimizers for Faster Convergence
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.
Analyzes decentralized pairwise-averaging SGD in which some nodes use only zeroth-order (forward-only, possibly biased) gradient estimators and others use first-order gradients, proving convergence for convex and non-convex objectives and showing hybrid populations can converge faster.
Problem
Decentralized optimization where some computationally bounded nodes can only obtain zeroth-order (function-value-based) gradient estimates, which are noisy and often biased, so existing first-order decentralized analyses do not apply.
Approach
Treat hybrid first- and zeroth-order nodes uniformly in a random pairwise-averaging protocol (each interaction: local gradient step then model averaging), and prove convergence bounds with a potential on model variance that handles biased zeroth-order estimators, showing the zeroth-order bias term decays with the learning rate and that large or hybrid populations can speed up convergence.
Key results
- On ResNet-18 fine-tuned on CIFAR-10, a hybrid population of 1 FO and 5 ZO nodes was reported to beat mono-type populations, with the 256-ZO and hybrid 24-FO+256-ZO groups overtaking the 24-FO group after about step 200 in the logistic MNIST experiment.
- Theory: for the non-convex case HDO attains a speedup of order sqrt(n) and for strongly convex a near-linear speedup of order n/log(n) in per-node oracle queries under stated conditions.
- Higher random-vector counts and unbiased forward-mode zeroth-order estimators gave better accuracy-versus-steps than biased ones on MNIST CNN training.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Increase the number of random vectors used by the biased ZO estimator (ablation) | ZO estimator on CNN · MNIST | accuracy | Helped |
| Use the unbiased forward-only ZO estimator instead of the biased ZO estimator (ablation) | ZO estimator on CNN · MNIST | accuracy | Helped |
| Increase random-vector count from 8 or 16 to 32 or 64 (ablation) | HDO with ZO estimators · MNIST | validation loss | Helped |
| Use a larger learning rate, such as 0.5, instead of smaller rates such as 0.005 or 0.01 (ablation) | HDO with 90 ZO and 3 FO nodes · MNIST regression | validation loss | Hurt |
| Increase the number of FO nodes in the 16-node population (ablation) | HDO · MNIST CNN | validation loss | Helped |
| Use more ZO nodes in the 16-node population (ablation) | HDO · MNIST CNN | validation loss | Mixed |
| Add 256 ZO nodes to a population of 24 FO nodes (ablation) | HDO · MNIST logistic model | validation loss | Helped |
| Add 5 ZO nodes to 1 FO node (ablation) | HDO · CIFAR-10 ResNet-18 | validation accuracy | Helped |
| Add 16 ZO nodes to 4 FO nodes (ablation) | HDO · Brackets Transformer | validation loss | Helped |
Surprising findings
- Larger populations of zeroth-order nodes can outperform smaller first-order populations, and hybrid populations outperform uniform ZO populations.
- Zeroth-order nodes can improve convergence over first-order-only populations after a sufficiently large number of steps, despite higher gradient variance and bias.
Limitations
- Experiments are simulated sequentially on a small number of models and datasets rather than a real large-scale decentralized deployment.
- Hyperparameter search was incomplete and learning rates were tuned separately per node type; theory relies on many constant-factor assumptions and a bounded-variance, data-split assumption.
- Analysis is limited to random pairwise interactions with a complete-mixing assumption; general graph topologies are left as future work.
Experimental setup
Datasets: MNIST CIFAR-10 ImageNet-1K Brackets
Benchmarks: MNIST CIFAR-10 Brackets
Metrics: validation loss validation accuracy loss standard deviation across nodes
Baselines: first-order-only decentralized SGD biased zeroth-order estimator unbiased forward-gradient estimator
Builds on: decentralized SGD Nesterov-Spokoiny gaussian smoothing zeroth-order estimator forward-mode gradient estimation (forward gradient) error feedback
Closest papers by meaning
- A Linearly Convergent Proximal Gradient Algorithm for Decentralized Optimization (NeurIPS 2019 · similarity 0.90)
- Decentralised Learning with Random Features and Distributed Gradient Descent (ICML 2020 · similarity 0.90)
- Stability and Generalization of Zeroth-Order Decentralized Stochastic Gradient Descent with Changing Topology (AAAI 2025 · similarity 0.89)
- Towards Stability and Generalization Bounds in Decentralized Minibatch Stochastic Gradient Descent (AAAI 2024 · similarity 0.89)
- Decentralized Convex Finite-Sum Optimization with Better Dependence on Condition Numbers (ICML 2024 · similarity 0.88)
- Achieving Linear Convergence with Parameter-Free Algorithms in Decentralized Optimization (NeurIPS 2024 · similarity 0.88)
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.