# Non-convex Min-Max Optimization: Applications, Challenges, and Recent Theoretical Advances

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

## Key facts

- Cited by 38 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 15 Jun 2020.

## Built on by (most cited first, 30 of 38)

- [Recent Advances in Adversarial Training for Adversarial Robustness](https://mlsanity.com/paper/2102.01356/) (2021)
- [Revisiting and Advancing Fast Adversarial Training Through The Lens of Bi-Level Optimization](https://mlsanity.com/paper/2112.12376/) (2021)
- [An Introduction to Bi-level Optimization: Foundations and Applications in Signal Processing and Machine Learning](https://mlsanity.com/paper/2308.00788/) (2023)
- [Policy Gradient in Robust MDPs with Global Convergence Guarantee](https://mlsanity.com/paper/2212.10439/) (2022)
- [What is the Solution for State-Adversarial Multi-Agent Reinforcement Learning?](https://mlsanity.com/paper/2212.02705/) (2022)
- [Adversarial Examples can be Effective Data Augmentation for Unsupervised Machine Learning](https://mlsanity.com/paper/2103.01895/) (2021)
- [MagicTailor: Component-Controllable Personalization in Text-to-Image Diffusion Models](https://mlsanity.com/paper/2410.13370/) (2024)
- [Learning to Continuously Optimize Wireless Resource in a Dynamic Environment: A Bilevel Optimization Perspective](https://mlsanity.com/paper/2105.01696/) (2021)
- [Nonsmooth Nonconvex-Nonconcave Minimax Optimization: Primal-Dual Balancing and Iteration Complexity Analysis](https://mlsanity.com/paper/2209.10825/) (2022)
- [Solving a class of non-convex min-max games using adaptive momentum methods](https://mlsanity.com/paper/2104.12676/) (2021)
- [Nonconvex-Nonconcave Min-Max Optimization with a Small Maximization Domain](https://mlsanity.com/paper/2110.03950/) (2021)
- [Regularized DeepIV with Model Selection](https://mlsanity.com/paper/2403.04236/) (2024)
- [Optimization and Optimizers for Adversarial Robustness](https://mlsanity.com/paper/2303.13401/) (2023)
- [Exploration is Harder than Prediction: Cryptographically Separating Reinforcement Learning from Supervised Learning](https://mlsanity.com/paper/2404.03774/) (2024)
- [Asymptotically Unbiased Instance-wise Regularized Partial AUC Optimization: Theory and Algorithm](https://mlsanity.com/paper/2210.03967/) (2022)
- [Exploring and Learning in Sparse Linear MDPs without Computationally Intractable Oracles](https://mlsanity.com/paper/2309.09457/) (2023)
- [Low-rank Matrix Recovery With Unknown Correspondence](https://mlsanity.com/paper/2110.07959/) (2021)
- [f-FERM: A Scalable Framework for Robust Fair Empirical Risk Minimization](https://mlsanity.com/paper/2312.03259/) (2023)
- [A Single-Loop Robust Policy Gradient Method for Robust Markov Decision Processes](https://mlsanity.com/paper/2406.00274/) (2024)
- [Generative Minimization Networks: Training GANs Without Competition](https://mlsanity.com/paper/2103.12685/) (2021)
- [A Fully First-Order Layer for Differentiable Optimization](https://mlsanity.com/paper/2512.02494/) (2025)
- [Stability and Generalization of Differentially Private Minimax Problems](https://mlsanity.com/paper/2204.04858/) (2022)
- [Mind the (optimality) Gap: A Gap-Aware Learning Rate Scheduler for Adversarial Nets](https://mlsanity.com/paper/2302.00089/) (2023)
- [Diffusion Stochastic Optimization for Min-Max Problems](https://mlsanity.com/paper/2401.14585/) (2024)
- [Rethinking Data Mixture for Large Language Models: A Comprehensive Survey and New Perspectives](https://mlsanity.com/paper/2505.21598/) (2025)
- [Dr. FERMI: A Stochastic Distributionally Robust Fair Empirical Risk Minimization Framework](https://mlsanity.com/paper/2309.11682/) (2023)
- [Kolmogorov n-Widths for Multitask Physics-Informed Machine Learning (PIML) Methods: Towards Robust Metrics](https://mlsanity.com/paper/2402.11126/) (2024)
- [Local convergence of simultaneous min-max algorithms to differential equilibrium on Riemannian manifold](https://mlsanity.com/paper/2405.13392/) (2024)
- [EXOTIC: An Exact, Optimistic, Tree-Based Algorithm for Min-Max Optimization](https://mlsanity.com/paper/2508.12479/) (2025)
- [Min-Max Optimization Requires Exponentially Many Queries](https://mlsanity.com/paper/2605.13806/) (2026)

## Abstract (arXiv)

The min-max optimization problem, also known as the saddle point problem, is a classical optimization problem which is also studied in the context of zero-sum games. Given a class of objective functions, the goal is to find a value for the argument which leads to a small objective value even for the worst case function in the given class. Min-max optimization problems have recently become very popular in a wide range of signal and data processing applications such as fair beamforming, training generative adversarial networks (GANs), and robust machine learning, to just name a few. The overarching goal of this article is to provide a survey of recent advances for an important subclass of min-max problem, where the minimization and maximization problems can be non-convex and/or non-concave. In particular, we will first present a number of applications to showcase the importance of such min-max problems; then we discuss key theoretical challenges, and provide a selective review of some exciting recent theoretical and algorithmic advances in tackling non-convex min-max problems. Finally, we will point out open questions and future research directions.