# Derivative-free Alternating Projection Algorithms for General Nonconvex-Concave Minimax Problems

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

## Key facts

- Cited by 7 papers in the map (data through 14 Oct 2026).
- Builds on 36 of its 63 references that are in the map.
- First posted on arXiv 1 Aug 2021.

## Builds on (most cited first, 30 of 36)

- [Generative Adversarial Imitation Learning](https://mlsanity.com/paper/1606.03476/) (2016)
- [ZOO: Zeroth Order Optimization based Black-box Attacks to Deep Neural Networks without Training Substitute Models](https://mlsanity.com/paper/1708.03999/) (2017)
- [On Gradient Descent Ascent for Nonconvex-Concave Minimax Problems](https://mlsanity.com/paper/1906.00331/) (2019)
- [Manipulating Machine Learning: Poisoning Attacks and Countermeasures for Regression Learning](https://mlsanity.com/paper/1804.00308/) (2018)
- [Training GANs with Optimism](https://mlsanity.com/paper/1711.00141/) (2017)
- [A Primer on Zeroth-Order Optimization in Signal Processing and Machine Learning](https://mlsanity.com/paper/2006.06224/) (2020)
- [Solving a Class of Non-Convex Min-Max Games Using Iterative First Order Methods](https://mlsanity.com/paper/1902.08297/) (2019)
- [A Variational Inequality Perspective on Generative Adversarial Networks](https://mlsanity.com/paper/1802.10551/) (2018)
- [A Unified Analysis of Extra-gradient and Optimistic Gradient Methods for Saddle Point Problems: Proximal Point Approach](https://mlsanity.com/paper/1901.08511/) (2019)
- [Near-Optimal Algorithms for Minimax Optimization](https://mlsanity.com/paper/2002.02417/) (2020)
- [The Limit Points of (Optimistic) Gradient Descent in Min-Max Optimization](https://mlsanity.com/paper/1807.03907/) (2018)
- [Stochastic Recursive Gradient Descent Ascent for Stochastic Nonconvex-Strongly-Concave Minimax Problems](https://mlsanity.com/paper/2001.03724/) (2020)
- [Lower complexity bounds of first-order methods for convex-concave bilinear saddle-point problems](https://mlsanity.com/paper/1808.02901/) (2018)
- [Efficient Algorithms for Smooth Minimax Optimization](https://mlsanity.com/paper/1907.01543/) (2019)
- [A Theoretical and Empirical Comparison of Gradient Approximations in Derivative-Free Optimization](https://mlsanity.com/paper/1905.01332/) (2019)
- [Weakly-Convex Concave Min-Max Optimization: Provable Algorithms and Applications in Machine Learning](https://mlsanity.com/paper/1810.02060/) (2018)
- [A Single-Loop Smoothed Gradient Descent-Ascent Algorithm for Nonconvex-Concave Min-Max Problems](https://mlsanity.com/paper/2010.15768/) (2020)
- [A Unified Single-loop Alternating Gradient Projection Algorithm for Nonconvex-Concave and Convex-Nonconcave Minimax Problems](https://mlsanity.com/paper/2006.02032/) (2020)
- [Hybrid Block Successive Approximation for One-Sided Non-Convex Min-Max Problems: Algorithms and Applications](https://mlsanity.com/paper/1902.08294/) (2019)
- [Scaleable input gradient regularization for adversarial robustness](https://mlsanity.com/paper/1905.11468/) (2019)
- [The Complexity of Nonconvex-Strongly-Concave Minimax Optimization](https://mlsanity.com/paper/2103.15888/) (2021)
- [Differentiable Game Mechanics](https://mlsanity.com/paper/1905.04926/) (2019)
- [Accelerated Zeroth-Order and First-Order Momentum Methods from Mini to Minimax Optimization](https://mlsanity.com/paper/2008.08170/) (2020)
- [Efficient Search of First-Order Nash Equilibria in Nonconvex-Concave Smooth Min-Max Problems](https://mlsanity.com/paper/2002.07919/) (2020)
- [Robust Optimization over Multiple Domains](https://mlsanity.com/paper/1805.07588/) (2018)
- [Accelerated Schemes For A Class of Variational Inequalities](https://mlsanity.com/paper/1403.4164/) (2014)
- [An accelerated inexact proximal point method for solving nonconvex-concave min-max problems](https://mlsanity.com/paper/1905.13433/) (2019)
- [Zeroth-Order Algorithms for Nonconvex Minimax Problems with Improved Complexities](https://mlsanity.com/paper/2001.07819/) (2020)
- [Optimal Primal-Dual Methods for a Class of Saddle Point Problems](https://mlsanity.com/paper/1309.5548/) (2013)
- [Zeroth-Order Methods for Convex-Concave Minmax Problems: Applications to Decision-Dependent Risk Minimization](https://mlsanity.com/paper/2106.09082/) (2021)

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

- [Zeroth-Order Alternating Gradient Descent Ascent Algorithms for a Class of Nonconvex-Nonconcave Minimax Problems](https://mlsanity.com/paper/2211.13668/) (2022)
- [Federated Distributionally Robust Optimization with Non-Convex Objectives: Algorithm and Analysis](https://mlsanity.com/paper/2307.14364/) (2023)
- [A Fully Parameter-Free Second-Order Algorithm for Convex-Concave Minimax Problems](https://mlsanity.com/paper/2407.03571/) (2024)
- [An accelerated first-order regularized momentum descent ascent algorithm for stochastic nonconvex-concave minimax problems](https://mlsanity.com/paper/2310.15448/) (2023)
- [Zeroth-Order Stochastic Mirror Descent Algorithms for Minimax Excess Risk Optimization](https://mlsanity.com/paper/2408.12209/) (2024)
- [Iterative Minimax Games with Coupled Linear Constraints](https://mlsanity.com/paper/2212.04672/) (2022)
- [Gradient Norm Regularization Second-Order Algorithms for Solving Nonconvex-Strongly Concave Minimax Problems](https://mlsanity.com/paper/2411.15769/) (2024)

## Abstract (arXiv)

In this paper, we study zeroth-order algorithms for nonconvex-concave minimax problems, which have attracted widely attention in machine learning, signal processing and many other fields in recent years. We propose a zeroth-order alternating randomized gradient projection (ZO-AGP) algorithm for smooth nonconvex-concave minimax problems, and its iteration complexity to obtain an varepsilon-stationary point is bounded by O(varepsilon-4), and the number of function value estimation is bounded by O(dx+dy) per iteration. Moreover, we propose a zeroth-order block alternating randomized proximal gradient algorithm (ZO-BAPG) for solving block-wise nonsmooth nonconvex-concave minimax optimization problems, and the iteration complexity to obtain an varepsilon-stationary point is bounded by O(varepsilon-4) and the number of function value estimation per iteration is bounded by O(K dx+dy). To the best of our knowledge, this is the first time that zeroth-order algorithms with iteration complexity gurantee are developed for solving both general smooth and block-wise nonsmooth nonconvex-concave minimax problems. Numerical results on data poisoning attack problem and distributed nonconvex sparse principal component analysis problem validate the efficiency of the proposed algorithms.