# A Zeroth-Order Block Coordinate Descent Algorithm for Huge-Scale Black-Box Optimization

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

## Key facts

- Cited by 46 papers in the map (data through 14 Oct 2026).
- Builds on 24 of its 57 references that are in the map.
- First posted on arXiv 21 Feb 2021.

## Builds on (most cited first, 24 of 24)

- [Rethinking the Inception Architecture for Computer Vision](https://mlsanity.com/paper/1512.00567/) (2015)
- [Speech Commands: A Dataset for Limited-Vocabulary Speech Recognition](https://mlsanity.com/paper/1804.03209/) (2018)
- [Stochastic First- and Zeroth-order Methods for Nonconvex Stochastic Programming](https://mlsanity.com/paper/1309.5549/) (2013)
- [ZOO: Zeroth Order Optimization based Black-box Attacks to Deep Neural Networks without Training Substitute Models](https://mlsanity.com/paper/1708.03999/) (2017)
- [Evolution Strategies as a Scalable Alternative to Reinforcement Learning](https://mlsanity.com/paper/1703.03864/) (2017)
- [Black-box Adversarial Attacks with Limited Queries and Information](https://mlsanity.com/paper/1804.08598/) (2018)
- [Deep Speech: Scaling up end-to-end speech recognition](https://mlsanity.com/paper/1412.5567/) (2014)
- [Audio Adversarial Examples: Targeted Attacks on Speech-to-Text](https://mlsanity.com/paper/1801.01944/) (2018)
- [SparseFool: a few pixels make a big difference](https://mlsanity.com/paper/1811.02248/) (2018)
- [GenAttack: Practical Black-box Attacks with Gradient-Free Optimization](https://mlsanity.com/paper/1805.11090/) (2018)
- [ZO-AdaMM: Zeroth-Order Adaptive Momentum Method for Black-Box Optimization](https://mlsanity.com/paper/1910.06513/) (2019)
- [A Theoretical and Empirical Comparison of Gradient Approximations in Derivative-Free Optimization](https://mlsanity.com/paper/1905.01332/) (2019)
- [Stochastic Zeroth-order Optimization in High Dimensions](https://mlsanity.com/paper/1710.10551/) (2017)
- [Did you hear that? Adversarial Examples Against Automatic Speech Recognition](https://mlsanity.com/paper/1801.00554/) (2018)
- [Zeroth-Order Regularized Optimization (ZORO): Approximately Sparse Gradients and Adaptive Sampling](https://mlsanity.com/paper/2003.13001/) (2020)
- [A Comprehensive Linear Speedup Analysis for Asynchronous Stochastic Parallel Optimization from Zeroth-Order to First-Order](https://mlsanity.com/paper/1606.00498/) (2016)
- [Gradientless Descent: High-Dimensional Zeroth-Order Optimization](https://mlsanity.com/paper/1911.06317/) (2019)
- [Targeted Adversarial Examples for Black Box Audio Systems](https://mlsanity.com/paper/1805.07820/) (2018)
- [Zeroth-order Nonconvex Stochastic Optimization: Handling Constraints, High-Dimensionality and Saddle-Points](https://mlsanity.com/paper/1809.06474/) (2018)
- [Enabling Fast and Universal Audio Adversarial Attack Using Generative Model](https://mlsanity.com/paper/2004.12261/) (2020)
- [A One-bit, Comparison-Based Gradient Estimator](https://mlsanity.com/paper/2010.02479/) (2020)
- [Inexact Coordinate Descent: Complexity and Preconditioning](https://mlsanity.com/paper/1304.5530/) (2013)
- [Universal adversarial examples in speech command classification](https://mlsanity.com/paper/1911.10182/) (2019)
- [WaveTransform: Crafting Adversarial Examples via Input Decomposition](https://mlsanity.com/paper/2010.15773/) (2020)

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

- [Fine-Tuning Language Models with Just Forward Passes](https://mlsanity.com/paper/2305.17333/) (2023)
- [Revisiting Zeroth-Order Optimization for Memory-Efficient LLM Fine-Tuning: A Benchmark](https://mlsanity.com/paper/2402.11592/) (2024)
- [DeepZero: Scaling up Zeroth-Order Optimization for Deep Model Training](https://mlsanity.com/paper/2310.02025/) (2023)
- [Sparse MeZO: Less Parameters for Better Performance in Zeroth-Order LLM Fine-Tuning](https://mlsanity.com/paper/2402.15751/) (2024)
- [Second-Order Fine-Tuning without Pain for LLMs:A Hessian Informed Zeroth-Order Optimizer](https://mlsanity.com/paper/2402.15173/) (2024)
- [How to Robustify Black-Box ML Models? A Zeroth-Order Optimization Perspective](https://mlsanity.com/paper/2203.14195/) (2022)
- [A Fast Optimization View: Reformulating Single Layer Attention in LLM Based on Tensor and SVM Trick, and Solving It in Matrix Multiplication Time](https://mlsanity.com/paper/2309.07418/) (2023)
- [Why Softmax Attention Outperforms Linear Attention](https://mlsanity.com/paper/2310.11685/) (2023)
- [FZOO: Fast Zeroth-Order Optimizer for Fine-Tuning Large Language Models towards Adam-Scale Speed](https://mlsanity.com/paper/2506.09034/) (2025)
- [Achieving Dimension-Free Communication in Federated Learning via Zeroth-Order Optimization](https://mlsanity.com/paper/2405.15861/) (2024)
- [Tensor-Compressed Back-Propagation-Free Training for (Physics-Informed) Neural Networks](https://mlsanity.com/paper/2308.09858/) (2023)
- [Unmasking Transformers: A Theoretical Approach to Data Recovery via Attention Weights](https://mlsanity.com/paper/2310.12462/) (2023)
- [Gradient Compressed Sensing: A Query-Efficient Gradient Estimator for High-Dimensional Zeroth-Order Optimization](https://mlsanity.com/paper/2405.16805/) (2024)
- [Zeroth-Order Policy Gradient for Reinforcement Learning from Human Feedback without Reward Inference](https://mlsanity.com/paper/2409.17401/) (2024)
- [Certified Zeroth-order Black-Box Defense with Robust UNet Denoiser](https://mlsanity.com/paper/2304.06430/) (2023)
- [Revisiting Zeroth-Order Optimization: Minimum-Variance Two-Point Estimators and Directionally Aligned Perturbations](https://mlsanity.com/paper/2510.19975/) (2025)
- [Leveraging Coordinate Momentum in SignSGD and Muon: Memory-Optimized Zero-Order](https://mlsanity.com/paper/2506.04430/) (2025)
- [Stochastic Zeroth order Descent with Structured Directions](https://mlsanity.com/paper/2206.05124/) (2022)
- [Curvature-Aware Derivative-Free Optimization](https://mlsanity.com/paper/2109.13391/) (2021)
- [The Expressibility of Polynomial based Attention Scheme](https://mlsanity.com/paper/2310.20051/) (2023)
- [Towards Straggler-Resilient Split Federated Learning: An Unbalanced Update Approach](https://mlsanity.com/paper/2510.21155/) (2025)
- [Convergence of Two-Layer Regression with Nonlinear Units](https://mlsanity.com/paper/2308.08358/) (2023)
- [ZO2: Scalable Zeroth-Order Fine-Tuning for Extremely Large Language Models with Limited GPU Memory](https://mlsanity.com/paper/2503.12668/) (2025)
- [An Optimal Transport Approach for Computing Adversarial Training Lower Bounds in Multiclass Classification](https://mlsanity.com/paper/2401.09191/) (2024)
- [Poor Man's Training on MCUs: A Memory-Efficient Quantized Back-Propagation-Free Approach](https://mlsanity.com/paper/2411.05873/) (2024)
- [LORENZA: Enhancing Generalization in Low-Rank Gradient LLM Training via Efficient Zeroth-Order Adaptive SAM](https://mlsanity.com/paper/2502.19571/) (2025)
- [Asynchronous Distributed Reinforcement Learning for LQR Control via Zeroth-Order Block Coordinate Descent](https://mlsanity.com/paper/2107.12416/) (2021)
- [ZOQO: Zero-Order Quantized Optimization](https://mlsanity.com/paper/2501.06736/) (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)

## Abstract (arXiv)

We consider the zeroth-order optimization problem in the huge-scale setting, where the dimension of the problem is so large that performing even basic vector operations on the decision variables is infeasible. In this paper, we propose a novel algorithm, coined ZO-BCD, that exhibits favorable overall query complexity and has a much smaller per-iteration computational complexity. In addition, we discuss how the memory footprint of ZO-BCD can be reduced even further by the clever use of circulant measurement matrices. As an application of our new method, we propose the idea of crafting adversarial attacks on neural network based classifiers in a wavelet domain, which can result in problem dimensions of over 1.7 million. In particular, we show that crafting adversarial examples to audio classifiers in a wavelet domain can achieve the state-of-the-art attack success rate of 97.9%.