# Zeroth-Order Online Alternating Direction Method of Multipliers: Convergence Analysis and Applications

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

## Key facts

- Cited by 22 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 21 Oct 2017.

## Built on by (most cited first, 22 of 22)

- [DeepZero: Scaling up Zeroth-Order Optimization for Deep Model Training](https://mlsanity.com/paper/2310.02025/) (2023)
- [Communication-Efficient Stochastic Zeroth-Order Optimization for Federated Learning](https://mlsanity.com/paper/2201.09531/) (2022)
- [FORMS: Fine-grained Polarized ReRAM-based In-situ Computation for Mixed-signal DNN Accelerator](https://mlsanity.com/paper/2106.09144/) (2021)
- [Zeroth-Order Policy Gradient for Reinforcement Learning from Human Feedback without Reward Inference](https://mlsanity.com/paper/2409.17401/) (2024)
- [Powering Up Zeroth-Order Training via Subspace Gradient Orthogonalization](https://mlsanity.com/paper/2602.17155/) (2026)
- [GRIM: A General, Real-Time Deep Learning Inference Framework for Mobile Devices based on Fine-Grained Structured Weight Sparsity](https://mlsanity.com/paper/2108.11033/) (2021)
- [Statistical Inference for Polyak-Ruppert Averaged Zeroth-order Stochastic Gradient Algorithm](https://mlsanity.com/paper/2102.05198/) (2021)
- [Poor Man's Training on MCUs: A Memory-Efficient Quantized Back-Propagation-Free Approach](https://mlsanity.com/paper/2411.05873/) (2024)
- [ElasticZO: A Memory-Efficient On-Device Learning with Combined Zeroth- and First-Order Optimization](https://mlsanity.com/paper/2501.04287/) (2025)
- [Min-Max Optimisation for Nonconvex-Nonconcave Functions Using a Random Zeroth-Order Extragradient Algorithm](https://mlsanity.com/paper/2504.07388/) (2025)
- [Sign-SZPO: Provable Preference-based Reinforcement Learning with an Unknown Link Function](https://mlsanity.com/paper/2506.03066/) (2025)
- [Zeroth-Order Hard-Thresholding: Gradient Error vs. Expansivity](https://mlsanity.com/paper/2210.05279/) (2022)
- [Universally Empowering Zeroth-Order Optimization via Adaptive Layer-wise Sampling](https://mlsanity.com/paper/2604.18264/) (2026)
- [Adaptive Zeroth-Order Optimisation of Nonconvex Composite Objectives](https://mlsanity.com/paper/2208.04579/) (2022)
- [SODA: Robust Training of Test-Time Data Adaptors](https://mlsanity.com/paper/2310.11093/) (2023)
- [End-to-End Mesh Optimization of a Hybrid Deep Learning Black-Box PDE Solver](https://mlsanity.com/paper/2404.11766/) (2024)
- [Gradient-Free Method for Heavily Constrained Nonconvex Optimization](https://mlsanity.com/paper/2409.00459/) (2024)
- [ZO-Act: Efficient Zeroth-Order Fine-Tuning via One-Shot Activation-Informed Low-Rank Subspaces](https://mlsanity.com/paper/2607.01125/) (2026)
- [TerMeZO: Ternary Sparse Zeroth-Order Optimization for Fine-tuning BitNet Models at the Edge](https://mlsanity.com/paper/2609.33548/) (2026)
- [Hard-label Manifolds: Unexpected Advantages of Query Efficiency for Finding On-manifold Adversarial Examples](https://mlsanity.com/paper/2103.03325/) (2021)
- [Adaptive Stochastic Optimisation of Nonconvex Composite Objectives](https://mlsanity.com/paper/2211.11710/) (2022)
- [Warming Up for Zeroth-Order Federated Pre-Training with Low Resource Clients](https://mlsanity.com/paper/2509.03503/) (2025)

## Abstract (arXiv)

In this paper, we design and analyze a new zeroth-order online algorithm, namely, the zeroth-order online alternating direction method of multipliers (ZOO-ADMM), which enjoys dual advantages of being gradient-free operation and employing the ADMM to accommodate complex structured regularizers. Compared to the first-order gradient-based online algorithm, we show that ZOO-ADMM requires √m times more iterations, leading to a convergence rate of O(√m/√T), where m is the number of optimization variables, and T is the number of iterations. To accelerate ZOO-ADMM, we propose two minibatch strategies: gradient sample averaging and observation averaging, resulting in an improved convergence rate of O(√1+q-1m/√T), where q is the minibatch size. In addition to convergence analysis, we also demonstrate ZOO-ADMM to applications in signal processing, statistics, and machine learning.