# A Comprehensive Linear Speedup Analysis for Asynchronous Stochastic Parallel Optimization from Zeroth-Order to First-Order

arXiv: https://arxiv.org/abs/1606.00498 · HTML: https://mlsanity.com/paper/1606.00498/

## Key facts

- Cited by 44 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 1 Jun 2016.

## Built on by (most cited first, 30 of 44)

- [DeepZero: Scaling up Zeroth-Order Optimization for Deep Model Training](https://mlsanity.com/paper/2310.02025/) (2023)
- [Enhancing Zeroth-order Fine-tuning for Language Models with Low-rank Structures](https://mlsanity.com/paper/2410.07698/) (2024)
- [A Zeroth-Order Block Coordinate Descent Algorithm for Huge-Scale Black-Box Optimization](https://mlsanity.com/paper/2102.10707/) (2021)
- [Gradient-Free Methods for Deterministic and Stochastic Nonsmooth Nonconvex Optimization](https://mlsanity.com/paper/2209.05045/) (2022)
- [How to Robustify Black-Box ML Models? A Zeroth-Order Optimization Perspective](https://mlsanity.com/paper/2203.14195/) (2022)
- [DPZero: Private Fine-Tuning of Language Models without Backpropagation](https://mlsanity.com/paper/2310.09639/) (2023)
- [L2ight: Enabling On-Chip Learning for Optical Neural Networks via Efficient in-situ Subspace Optimization](https://mlsanity.com/paper/2110.14807/) (2021)
- [Distributed Learning Systems with First-order Methods](https://mlsanity.com/paper/2104.05245/) (2021)
- [Persia: An Open, Hybrid System Scaling Deep Learning-based Recommenders up to 100 Trillion Parameters](https://mlsanity.com/paper/2111.05897/) (2021)
- [Optimizing Large-Scale Hyperparameters via Automated Learning Algorithm](https://mlsanity.com/paper/2102.09026/) (2021)
- [ComPO: Preference Alignment via Comparison Oracles](https://mlsanity.com/paper/2505.05465/) (2025)
- [Tensor-Compressed Back-Propagation-Free Training for (Physics-Informed) Neural Networks](https://mlsanity.com/paper/2308.09858/) (2023)
- [Refining Adaptive Zeroth-Order Optimization at Ease](https://mlsanity.com/paper/2502.01014/) (2025)
- [Certified Zeroth-order Black-Box Defense with Robust UNet Denoiser](https://mlsanity.com/paper/2304.06430/) (2023)
- [ZooPFL: Exploring Black-box Foundation Models for Personalized Federated Learning](https://mlsanity.com/paper/2310.05143/) (2023)
- [ZeroFlow: Overcoming Catastrophic Forgetting is Easier than You Think](https://mlsanity.com/paper/2501.01045/) (2025)
- [Leveraging Coordinate Momentum in SignSGD and Muon: Memory-Optimized Zero-Order](https://mlsanity.com/paper/2506.04430/) (2025)
- [Zeroth-Order Optimization is Secretly Single-Step Policy Optimization](https://mlsanity.com/paper/2506.14460/) (2025)
- [Statistical Inference for Polyak-Ruppert Averaged Zeroth-order Stochastic Gradient Algorithm](https://mlsanity.com/paper/2102.05198/) (2021)
- [Zeroth-Order Optimization Finds Flat Minima](https://mlsanity.com/paper/2506.05454/) (2025)
- [STARNet: Sensor Trustworthiness and Anomaly Recognition via Approximated Likelihood Regret for Robust Edge Autonomy](https://mlsanity.com/paper/2309.11006/) (2023)
- [ElasticZO: A Memory-Efficient On-Device Learning with Combined Zeroth- and First-Order Optimization](https://mlsanity.com/paper/2501.04287/) (2025)
- [SGD with Coordinate Sampling: Theory and Practice](https://mlsanity.com/paper/2105.11818/) (2021)
- [The Multi-Query Paradox in Zeroth-Order Optimization](https://mlsanity.com/paper/2509.15552/) (2025)
- [Distributed stochastic optimization with large delays](https://mlsanity.com/paper/2107.02919/) (2021)
- [Zeroth-Order Hard-Thresholding: Gradient Error vs. Expansivity](https://mlsanity.com/paper/2210.05279/) (2022)
- [Scalable Back-Propagation-Free Training of Optical Physics-Informed Neural Networks](https://mlsanity.com/paper/2502.12384/) (2025)
- [ZOTTA: Test-Time Adaptation with Gradient-Free Zeroth-Order Optimization](https://mlsanity.com/paper/2603.14254/) (2026)
- [Convergence Analysis of Nonconvex Distributed Stochastic Zeroth-order Coordinate Method](https://mlsanity.com/paper/2103.12954/) (2021)
- [An Accelerated Variance-Reduced Conditional Gradient Sliding Algorithm for First-order and Zeroth-order Optimization](https://mlsanity.com/paper/2109.08858/) (2021)

## Abstract (arXiv)

Asynchronous parallel optimization received substantial successes and extensive attention recently. One of core theoretical questions is how much speedup (or benefit) the asynchronous parallelization can bring us. This paper provides a comprehensive and generic analysis to study the speedup property for a broad range of asynchronous parallel stochastic algorithms from the zeroth order to the first order methods. Our result recovers or improves existing analysis on special cases, provides more insights for understanding the asynchronous parallel behaviors, and suggests a novel asynchronous parallel zeroth order method for the first time. Our experiments provide novel applications including model blending problems using the proposed asynchronous parallel zeroth order method.