# On the Design of Black-box Adversarial Examples by Leveraging Gradient-free Optimization and Operator Splitting Method

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

## Key facts

- Cited by 21 papers in the map (data through 7 Oct 2026).
- First posted on arXiv 26 Jul 2019.

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

- [Advances in adversarial attacks and defenses in computer vision: A survey](https://mlsanity.com/paper/2108.00401/) (2021)
- [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)
- [Mind the box: l1-APGD for sparse adversarial attacks on image classifiers](https://mlsanity.com/paper/2103.01208/) (2021)
- [Enhancing Zeroth-order Fine-tuning for Language Models with Low-rank Structures](https://mlsanity.com/paper/2410.07698/) (2024)
- [Adversarial Robustness against Multiple and Single lp-Threat Models via Quick Fine-Tuning of Robust Classifiers](https://mlsanity.com/paper/2105.12508/) (2021)
- [Back in Black: A Comparative Evaluation of Recent State-Of-The-Art Black-Box Attacks](https://mlsanity.com/paper/2109.15031/) (2021)
- [Versatile Weight Attack via Flipping Limited Bits](https://mlsanity.com/paper/2207.12405/) (2022)
- [Holistic Adversarial Robustness of Deep Learning Models](https://mlsanity.com/paper/2202.07201/) (2022)
- [Powering Up Zeroth-Order Training via Subspace Gradient Orthogonalization](https://mlsanity.com/paper/2602.17155/) (2026)
- [Efficient Black-box Adversarial Attacks via Bayesian Optimization Guided by a Function Prior](https://mlsanity.com/paper/2405.19098/) (2024)
- [BruSLeAttack: A Query-Efficient Score-Based Black-Box Sparse Adversarial Attack](https://mlsanity.com/paper/2404.05311/) (2024)
- [Statistical Inference for Polyak-Ruppert Averaged Zeroth-order Stochastic Gradient Algorithm](https://mlsanity.com/paper/2102.05198/) (2021)
- [SoK: Pitfalls in Evaluating Black-Box Attacks](https://mlsanity.com/paper/2310.17534/) (2023)
- [Adversarial Attacks on Graph Classification via Bayesian Optimisation](https://mlsanity.com/paper/2111.02842/) (2021)
- [Trust Regions for Explanations via Black-Box Probabilistic Certification](https://mlsanity.com/paper/2402.11168/) (2024)
- [ZOQO: Zero-Order Quantized Optimization](https://mlsanity.com/paper/2501.06736/) (2025)
- [LSDAT: Low-Rank and Sparse Decomposition for Decision-based Adversarial Attack](https://mlsanity.com/paper/2103.10787/) (2021)
- [SemiAdv: Query-Efficient Black-Box Adversarial Attack with Unlabeled Images](https://mlsanity.com/paper/2407.11073/) (2024)
- [ZO-SAM: Zero-Order Sharpness-Aware Minimization for Efficient Sparse Training](https://mlsanity.com/paper/2603.13115/) (2026)
- [Curvature-Aware Zeroth-Order Optimization for Memory-Efficient Test-Time Adaptation](https://mlsanity.com/paper/2608.12279/) (2026)

## Abstract (arXiv)

Robust machine learning is currently one of the most prominent topics which could potentially help shaping a future of advanced AI platforms that not only perform well in average cases but also in worst cases or adverse situations. Despite the long-term vision, however, existing studies on black-box adversarial attacks are still restricted to very specific settings of threat models (e.g., single distortion metric and restrictive assumption on target model's feedback to queries) and/or suffer from prohibitively high query complexity. To push for further advances in this field, we introduce a general framework based on an operator splitting method, the alternating direction method of multipliers (ADMM) to devise efficient, robust black-box attacks that work with various distortion metrics and feedback settings without incurring high query complexity. Due to the black-box nature of the threat model, the proposed ADMM solution framework is integrated with zeroth-order (ZO) optimization and Bayesian optimization (BO), and thus is applicable to the gradient-free regime. This results in two new black-box adversarial attack generation methods, ZO-ADMM and BO-ADMM. Our empirical evaluations on image classification datasets show that our proposed approaches have much lower function query complexities compared to state-of-the-art attack methods, but achieve very competitive attack success rates.