# Zeroth-Order Algorithms for Nonconvex Minimax Problems with Improved Complexities

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

## Key facts

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

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

- [Stochastic Gradient Descent-Ascent: Unified Theory and New Efficient Methods](https://mlsanity.com/paper/2202.07262/) (2022)
- [DPZero: Private Fine-Tuning of Language Models without Backpropagation](https://mlsanity.com/paper/2310.09639/) (2023)
- [Adversarial Machine Unlearning](https://mlsanity.com/paper/2406.07687/) (2024)
- [AdaGDA: Faster Adaptive Gradient Descent Ascent Methods for Minimax Optimization](https://mlsanity.com/paper/2106.16101/) (2021)
- [Communication-Efficient Federated Hypergradient Computation via Aggregated Iterative Differentiation](https://mlsanity.com/paper/2302.04969/) (2023)
- [Addax: Utilizing Zeroth-Order Gradients to Improve Memory Efficiency and Performance of SGD for Fine-Tuning Language Models](https://mlsanity.com/paper/2410.06441/) (2024)
- [Derivative-free Alternating Projection Algorithms for General Nonconvex-Concave Minimax Problems](https://mlsanity.com/paper/2108.00473/) (2021)
- [Zeroth-Order Optimization Finds Flat Minima](https://mlsanity.com/paper/2506.05454/) (2025)
- [Combinatorial Optimization with Automated Graph Neural Networks](https://mlsanity.com/paper/2406.02872/) (2024)
- [Bilevel ZOFO: Efficient LLM Fine-Tuning and Meta-Training](https://mlsanity.com/paper/2502.03604/) (2025)
- [Min-Max Optimisation for Nonconvex-Nonconcave Functions Using a Random Zeroth-Order Extragradient Algorithm](https://mlsanity.com/paper/2504.07388/) (2025)
- [A Fully Parameter-Free Second-Order Algorithm for Convex-Concave Minimax Problems](https://mlsanity.com/paper/2407.03571/) (2024)
- [Two trust region type algorithms for solving nonconvex-strongly concave minimax problems](https://mlsanity.com/paper/2402.09807/) (2024)
- [Solving the Offline and Online Min-Max Problem of Non-smooth Submodular-Concave Functions: A Zeroth-Order Approach](https://mlsanity.com/paper/2601.21243/) (2026)
- [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)
- [Gradient-Free Method for Heavily Constrained Nonconvex Optimization](https://mlsanity.com/paper/2409.00459/) (2024)
- [A Framework for Finding Local Saddle Points in Two-Player Zero-Sum Black-Box Games](https://mlsanity.com/paper/2503.18224/) (2025)
- [ConMeZO: Adaptive Descent-Direction Sampling for Gradient-Free Finetuning of Large Language Models](https://mlsanity.com/paper/2511.02757/) (2025)
- [Stochastic Trust-Region Methods for Over-parameterized Models](https://mlsanity.com/paper/2604.14017/) (2026)
- [EGGROLL, Unrolled: Understanding and Improving Low-Rank Evolution Strategies at Scale](https://mlsanity.com/paper/2609.10980/) (2026)

## Abstract (arXiv)

In this paper, we study zeroth-order algorithms for minimax optimization problems that are nonconvex in one variable and strongly-concave in the other variable. Such minimax optimization problems have attracted significant attention lately due to their applications in modern machine learning tasks. We first consider a deterministic version of the problem. We design and analyze the Zeroth-Order Gradient Descent Ascent (textttZO-GDA) algorithm, and provide improved results compared to existing works, in terms of oracle complexity. We also propose the Zeroth-Order Gradient Descent Multi-Step Ascent (textttZO-GDMSA) algorithm that significantly improves the oracle complexity of textttZO-GDA. We then consider stochastic versions of textttZO-GDA and textttZO-GDMSA, to handle stochastic nonconvex minimax problems. For this case, we provide oracle complexity results under two assumptions on the stochastic gradient: (i) the uniformly bounded variance assumption, which is common in traditional stochastic optimization, and (ii) the Strong Growth Condition (SGC), which has been known to be satisfied by modern over-parametrized machine learning models. We establish that under the SGC assumption, the complexities of the stochastic algorithms match that of deterministic algorithms. Numerical experiments are presented to support our theoretical results.