mlsanityData to 7 Oct 2026

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

arXiv 2102.10707 ↗First posted 21 Feb 2021math.OC cs.AI cs.LGcited by 46

Not on the map. Why?

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%.

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

Builds on

24 of 57 references.

References · 24

  1. 2015Rethinking the Inception Architecture for Computer Visioncited by 5,451
  2. 2018Speech Commands: A Dataset for Limited-Vocabulary Speech Recognitioncited by 741
  3. 2013Stochastic First- and Zeroth-order Methods for Nonconvex Stochastic Programmingcited by 716
  4. 2017ZOO: Zeroth Order Optimization based Black-box Attacks to Deep Neural Networks without Training Substitute Modelscited by 656
  5. 2017Evolution Strategies as a Scalable Alternative to Reinforcement Learningcited by 555
  6. 2018Black-box Adversarial Attacks with Limited Queries and Informationcited by 499
  7. 2014Deep Speech: Scaling up end-to-end speech recognitioncited by 354
  8. 2018Audio Adversarial Examples: Targeted Attacks on Speech-to-Textcited by 268
  9. 2018SparseFool: a few pixels make a big differencecited by 94
  10. 2018GenAttack: Practical Black-box Attacks with Gradient-Free Optimizationcited by 82
  11. 2019ZO-AdaMM: Zeroth-Order Adaptive Momentum Method for Black-Box Optimizationcited by 75
  12. 2019A Theoretical and Empirical Comparison of Gradient Approximations in Derivative-Free Optimizationcited by 66
12 more
  1. 2017Stochastic Zeroth-order Optimization in High Dimensionscited by 62
  2. 2018Did you hear that? Adversarial Examples Against Automatic Speech Recognitioncited by 48
  3. 2020Zeroth-Order Regularized Optimization (ZORO): Approximately Sparse Gradients and Adaptive Samplingcited by 45
  4. 2016A Comprehensive Linear Speedup Analysis for Asynchronous Stochastic Parallel Optimization from Zeroth-Order to First-Ordercited by 43
  5. 2019Gradientless Descent: High-Dimensional Zeroth-Order Optimizationcited by 42
  6. 2018Targeted Adversarial Examples for Black Box Audio Systemscited by 41
  7. 2018Zeroth-order Nonconvex Stochastic Optimization: Handling Constraints, High-Dimensionality and Saddle-Pointscited by 36
  8. 2020Enabling Fast and Universal Audio Adversarial Attack Using Generative Modelcited by 31
  9. 2020A One-bit, Comparison-Based Gradient Estimatorcited by 15
  10. 2013Inexact Coordinate Descent: Complexity and Preconditioningcited by 8
  11. 2019Universal adversarial examples in speech command classificationcited by 4
  12. 2020WaveTransform: Crafting Adversarial Examples via Input Decompositioncited by 4

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 2; 2022: 4; 2023: 10; 2024: 11; 2025: 16; 2026: 3.

46 papers.

Sort:

By area:

  1. 2023Fine-Tuning Language Models with Just Forward Passescited by 337
  2. 2024Revisiting Zeroth-Order Optimization for Memory-Efficient LLM Fine-Tuning: A Benchmarkcited by 113
  3. 2023DeepZero: Scaling up Zeroth-Order Optimization for Deep Model Trainingcited by 76
  4. 2024Sparse MeZO: Less Parameters for Better Performance in Zeroth-Order LLM Fine-Tuningcited by 53
  5. 2024Second-Order Fine-Tuning without Pain for LLMs:A Hessian Informed Zeroth-Order Optimizercited by 51
  6. 2022How to Robustify Black-Box ML Models? A Zeroth-Order Optimization Perspectivecited by 39
  7. 2023A Fast Optimization View: Reformulating Single Layer Attention in LLM Based on Tensor and SVM Trick, and Solving It in Matrix Multiplication Timecited by 30
  8. 2023Why Softmax Attention Outperforms Linear Attentioncited by 15
  9. 2023Tensor-Compressed Back-Propagation-Free Training for (Physics-Informed) Neural Networkscited by 12
  10. 2024Achieving Dimension-Free Communication in Federated Learning via Zeroth-Order Optimizationcited by 12
  11. 2024Gradient Compressed Sensing: A Query-Efficient Gradient Estimator for High-Dimensional Zeroth-Order Optimizationcited by 12
  12. 2024Zeroth-Order Policy Gradient for Reinforcement Learning from Human Feedback without Reward Inferencecited by 12
34 more
  1. 2023Certified Zeroth-order Black-Box Defense with Robust UNet Denoisercited by 11
  2. 2023Unmasking Transformers: A Theoretical Approach to Data Recovery via Attention Weightscited by 11
  3. 2025FZOO: Fast Zeroth-Order Optimizer for Fine-Tuning Large Language Models towards Adam-Scale Speedcited by 11
  4. 2025Leveraging Coordinate Momentum in SignSGD and Muon: Memory-Optimized Zero-Ordercited by 9
  5. 2025Revisiting Zeroth-Order Optimization: Minimum-Variance Two-Point Estimators and Directionally Aligned Perturbationscited by 9
  6. 2022Stochastic Zeroth order Descent with Structured Directionscited by 8
  7. 2021Curvature-Aware Derivative-Free Optimizationcited by 7
  8. 2023The Expressibility of Polynomial based Attention Schemecited by 7
  9. 2025Towards Straggler-Resilient Split Federated Learning: An Unbalanced Update Approachcited by 7
  10. 2023Convergence of Two-Layer Regression with Nonlinear Unitscited by 6
  11. 2024An Optimal Transport Approach for Computing Adversarial Training Lower Bounds in Multiclass Classificationcited by 5
  12. 2024Poor Man's Training on MCUs: A Memory-Efficient Quantized Back-Propagation-Free Approachcited by 5
  13. 2025ZO2: Scalable Zeroth-Order Fine-Tuning for Extremely Large Language Models with Limited GPU Memorycited by 5
  14. 2021Asynchronous Distributed Reinforcement Learning for LQR Control via Zeroth-Order Block Coordinate Descentcited by 4
  15. 2025ZOQO: Zero-Order Quantized Optimizationcited by 4
  16. 2025Sign-SZPO: Provable Preference-based Reinforcement Learning with an Unknown Link Functioncited by 4
  17. 2022Zeroth-Order Hard-Thresholding: Gradient Error vs. Expansivitycited by 3
  18. 2023It begins with a boundary: A geometric view on probabilistically robust learningcited by 3
  19. 2025LORENZA: Enhancing Generalization in Low-Rank Gradient LLM Training via Efficient Zeroth-Order Adaptive SAMcited by 3
  20. 2025Learning a Zeroth-Order Optimizer for Fine-Tuning LLMscited by 3
  21. 2025Elucidating Subspace Perturbation in Zeroth-Order Optimization: Theory and Practice at Scalecited by 2
  22. 2025Scalable Back-Propagation-Free Training of Optical Physics-Informed Neural Networkscited by 2
  23. 2025On the Optimal Construction of Unbiased Gradient Estimators for Zeroth-Order Optimizationcited by 2
  24. 2024Binary Hypothesis Testing for Softmax Models and Leverage Score Modelscited by 1
  25. 2024A New Formulation for Zeroth-Order Optimization of Adversarial EXEmples in Malware Detectioncited by 1
  26. 2025DistZO2: High-Throughput and Memory-Efficient Zeroth-Order Fine-tuning LLMs with Distributed Parallel Computingcited by 1
  27. 2022Convergence of Batch Updating Methods with Approximate Gradients and/or Noisy Measurements: Theory and Computational Resultscited by 0
  28. 2024How to Boost Any Loss Functioncited by 0
  29. 2025Explainable Adversarial Attacks on Coarse-to-Fine Classifierscited by 0
  30. 2025Efficient Zeroth-Order Federated Finetuning of Language Models on Resource-Constrained Devicescited by 0
  31. 2025A Structured Tour of Optimization with Finite Differencescited by 0
  32. 2026Steering the Noise: Turning Random Perturbations into Effective Descent for Memory-Efficient LLM Fine-Tuningcited by 0
  33. 2026Memory Efficient Full-gradient Attacks (MEFA) Framework for Adversarial Defense Evaluationscited by 0
  34. 2026TACO: Ternary Absolute-max Column-wise One-sparse Optimizer for LLM Fine-Tuningcited by 0