# Min-Max Optimization without Gradients: Convergence and Applications to Adversarial ML

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

## Key facts

- Cited by 9 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 30 Sep 2019.

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

- [How to Robustify Black-Box ML Models? A Zeroth-Order Optimization Perspective](https://mlsanity.com/paper/2203.14195/) (2022)
- [Zeroth-Order Methods for Convex-Concave Minmax Problems: Applications to Decision-Dependent Risk Minimization](https://mlsanity.com/paper/2106.09082/) (2021)
- [Certified Zeroth-order Black-Box Defense with Robust UNet Denoiser](https://mlsanity.com/paper/2304.06430/) (2023)
- [Direct-Search for a Class of Stochastic Min-Max Problems](https://mlsanity.com/paper/2102.11386/) (2021)
- [Attack Anything: Blind DNNs via Universal Background Adversarial Attack](https://mlsanity.com/paper/2409.00029/) (2024)
- [An accelerated first-order regularized momentum descent ascent algorithm for stochastic nonconvex-concave minimax problems](https://mlsanity.com/paper/2310.15448/) (2023)
- [Data augmentation with automated machine learning: approaches and performance comparison with classical data augmentation methods](https://mlsanity.com/paper/2403.08352/) (2024)
- [A Mean-Field Analysis of Neural Stochastic Gradient Descent-Ascent for Functional Minimax Optimization](https://mlsanity.com/paper/2404.12312/) (2024)
- [Zeroth-Order Stochastic Mirror Descent Algorithms for Minimax Excess Risk Optimization](https://mlsanity.com/paper/2408.12209/) (2024)

## Abstract (arXiv)

In this paper, we study the problem of constrained robust (min-max) optimization ina black-box setting, where the desired optimizer cannot access the gradients of the objective function but may query its values. We present a principled optimization framework, integrating a zeroth-order (ZO) gradient estimator with an alternating projected stochastic gradient descent-ascent method, where the former only requires a small number of function queries and the later needs just one-step descent/ascent update. We show that the proposed framework, referred to as ZO-Min-Max, has a sub-linear convergence rate under mild conditions and scales gracefully with problem size. From an application side, we explore a promising connection between black-box min-max optimization and black-box evasion and poisoning attacks in adversarial machine learning (ML). Our empirical evaluations on these use cases demonstrate the effectiveness of our approach and its scalability to dimensions that prohibit using recent black-box solvers.