Min-Max Optimization

Ask about this topic

Overview

Min-max optimization models adversarial learning, zero-sum games, distributionally robust learning, and bilevel problems in which one objective is optimized against another. Methods include gradient descent-ascent, extragradient and optimistic updates, proximal and smoothing techniques, and stochastic variance-reduction methods; their guarantees depend strongly on whether the objective is convex-concave, strongly concave in the maximizing variable, or fully nonconvex. Current work seeks faster last-iterate convergence and single-loop algorithms, with applications evaluated in settings such as GAN training, robust regression, and Markov games. A central tension is that stronger guarantees often require restrictive assumptions, while lower bounds and hardness results show that general nonconvex-nonconcave problems can demand very high oracle complexity or resist efficient solution.

Latest papers

CardsList

38 papers6 papers in the last four weeks, down 14% on the four weeks before. 0.0% of all new papers.

  1. Generalization Analysis of Biased Stochastic Gradient Methods for Minimax Problems

    Oct 14, 2026Shuang Zeng, Yunwen Lei, Yiming YingMin-Max OptimizationGeneralization Bounds

    Department of Mathematics, The University of Hong Kong, Hong Kong, China · School of Mathematics and Statistics, The University of Sydney, Sydney, Australia

  2. Controlled-Minimax: Stabilizing Adversarial Optimization via Control Theory

    Oct 9, 2026Tianjiao Luo, Jianfei Chen, Jun ZhuMin-Max OptimizationOptimization Convergence Analysis

    Department of Computer Science and Technology, Tsinghua University, Beijing, China.

  3. Stochastic Gradient Descent Ascent is Suboptimal for Nonconvex-PŁ Min-Max Games

    Oct 6, 2026Junsoo HaOptimization Convergence AnalysisMin-Max Optimization

  4. Neural Algorithmic Reasoning for Graph Saddle Point Problems

    Oct 5, 2026Samantha Chen, Jesse He, Coleman Clougherty +2Primal-Dual OptimizationGraph Neural Networks

    Oberlin College · Department of Computer Science, Oberlin College · University of California, San Diego +2

  5. Near-Optimal Complexity of Finite-Sum Nonconvex-Strongly-Concave Minimax Optimization

    Oct 4, 2026Qihao ZhouMin-Max OptimizationOracle Complexity

    Independent Researcher

  6. Lower Bounds for Stochastic First-Order Algorithms with Variance Reduction in Nonconvex--Concave Minimax Optimization

    Oct 1, 2026Jiayi Song, Zi XuMin-Max Optimization

    Department of Mathematics, College of Sciences, Shanghai University, Shanghai 200444, China

  7. Tight Stochastic Condition-Number Dependence in Nonconvex-Strongly-Concave Minimax Optimization

    Sep 25, 2026Qihao ZhouOracle ComplexityMin-Max Optimization

    Independent Researcher

  8. Single-Loop Stochastic Projected Damped Extragradient Methods for Nonconvex--(Strongly) Concave Minimax Optimization

    Sep 18, 2026Huiling Zhang, Minhao Zhang, Zi Xu +1Min-Max OptimizationStochastic Optimization

    LSEC, ICMSEC, Academy of Mathematics and Systems Science, Chinese Academy of Sciences, Beijing 100190, China · Department of Mathematics, College of Sciences, Shanghai University, Shanghai 200444, China

  9. Near-Optimal Single-Loop Predictor--Corrector Extragradient Method for Strongly Convex--Strongly Concave Minimax Optimization

    Sep 17, 2026Minhao Zhang, Zi XuLast-Iterate ConvergenceMin-Max Optimization

    Department of Mathematics, Shanghai University, Shanghai 200444, People’s Republic of China

  10. Matching Multi-Loop Complexities with a Single Loop: Optimal Optimization Stationarity and Best-Known Game Stationarity in Nonconvex--Concave Minimax Optimization

    Sep 16, 2026Minghao Zhang, Zi XuMin-Max OptimizationExtragradient Methods

    Department of Mathematics, College of Sciences, Shanghai University, Shanghai, 200444, P.R.China.

  11. Riemannian ascent--descent for nonconvex nonconcave minimax landscapes: convergence to basin saddle points and applications to distributionally robust optimization

    Sep 12, 2026Rishabh Dixit, Pranav Upadrashta, Alex CloningerMin-Max OptimizationWasserstein Distributionally Robust Optimization

    Department of Mathematics, UC San Diego · Department of Mathematics and Halıcıoglu Data Science Institute, UC San Diego

  12. How to Make the Gradient Mapping Small for Constrained Stochastic Min-Max Problems and Beyond

    Sep 8, 2026Ahmet AlacaogluStochastic OptimizationMin-Max Optimization

    Department of Mathematics, University of British Columbia

  13. The Role of Gradient Modification in Heavy-Tailed Nonconvex Stochastic Min-Max Optimization

    Sep 5, 2026Tianxi Zhu, Yi Xu, Xiangyang JiMin-Max OptimizationStochastic Optimization Convergence

    School of Control Science and Engineering, Dalian University of Technology · Department of Automation, Tsinghua University

  14. Deciding When to Switch: E-Processes for Adaptive Minimax Training for Generative Adversarial Nets

    Aug 10, 2026Hyunjoo Kim, Sicheng Wu, Agastya Venkatraman +2Min-Max OptimizationSequential Hypothesis Testing

    Department of Statistics, Ewha Womans University · Department of Mathematics, Purdue University · Department of Computer Science, Purdue University

  15. Accelerated and Stable Convergence with Anchored Optimistic Method

    Jun 19, 2026Motahareh Sohrabi, Jianxin You, Simon Lacoste-Julien +2Last-Iterate ConvergenceGradient Descent

    Universit´e de Montr´eal · Mila - Quebec AI Institute · CIFAR AI Chair +1

  16. The Complexity of Min-Max Optimization for Quadratic Polynomials

    Jun 15, 2026Martino Bernasconi, Matteo Castiglioni, Andrea Celli +1Min-Max OptimizationNonconvex Optimization

    Bocconi University · Politecnico di Milano · University of Oxford

  17. Last-Iterate Convergence of Optimistic Multiplicative Weight Update

    Jun 10, 2026Francesco OrabonaLast-Iterate ConvergenceOptimization Convergence Analysis

    King Abdullah University of Science and Technology (KAUST) Thuwal, 23955-6900, Kingdom of Saudi Arabia

  18. Literature-Guided Minimax Optimization of Virtual Epilepsy Neurostimulation

    Jun 3, 2026Cathy LiuMin-Max Optimization

    Cathy Liu

  19. Accelerating Min-Max Optimization via Power-Law Stepsizes

    Jun 1, 2026Yue Wu, Weiqiang Zheng, Yang Cai +1Learning Rate SchedulingLast-Iterate Convergence

    University of Southern California · Yale University

  20. Bilevel Optimization over Saddle Points of Zero-Sum Markov Games

    May 26, 2026Zihao Zheng, Irwin King, Songtao LuGame TheoryZero-Sum Games

    Department of Computer Science and Engineering, The Chinese University of Hong Kong · Shun Hing Institute of Advanced Engineering, The Chinese University of Hong Kong

  21. Adversarial Water-Filling: Theory, Algorithms, and a Domain-Specific Wireless Foundation Model

    May 24, 2026Xindi Tong, Chee Wei Tan, H. Vincent PoorWireless Foundation ModelsMin-Max Optimization

    College of Computing and Data Science (CCDS), Nanyang Technological University, Singapore · Princeton University, United States

  22. Understanding Dynamics of Adam in Zero-Sum Games: An ODE Approach

    May 19, 2026Yi Feng, Weiming Ou, Xiao WangZero-Sum GamesMin-Max Optimization

    Aarhus University, Aarhus, Denmark · Shanghai University of Finance and Economics, Shanghai, China · MoE Key Laboratory of Interdisciplinary Research of Computation and Economics, Shanghai University of Finance and Economics, Shanghai, China

  23. Min-Max Optimization Requires Exponentially Many Queries

    May 13, 2026Martino Bernasconi, Matteo Castiglioni, Andrea Celli +1Query ComplexityOracle Complexity

    Bocconi University · Politecnico di Milano · University of Oxford

  24. Penalty-Based First-Order Methods for Bilevel Optimization with Minimax and Constrained Lower-Level Problems

    May 8, 2026Yiyang Shen, Yutian He, Weiran Wang +1Min-Max OptimizationBilevel Optimization

    University of Iowa

  25. MEMOA: Massive Mixtures of Online Agents via Mean-Field Decentralized Nash Equilibria

    May 6, 2026Xuwei Yang, David B. Emerson, Fatemeh Tavakoli +1Nash EquilibriumFederated RL

    Department of Mathematics and Statistics McMaster University Ontario, Canada · Vector Institute Ontario, Canada

  26. On the Stability and Generalization of First-order Bilevel Minimax Optimization

    Apr 22, 2026Xuelin Zhang, Peipei YuanMin-Max OptimizationBilevel Optimization

    College of Informatics, Huazhong Agricultural University, Wuhan, 430070, China · School of Artificial Intelligence, Jianghan University, Wuhan, 430056, China

  27. Negative Momentum for Convex-Concave Optimization

    Apr 18, 2026Henry Shugart, Shuyi Wang, Jason M. AltschulerMomentum MethodsMin-Max Optimization

    UPenn · Yale

  28. Optimal last-iterate convergence in matrix games with bandit feedback using the log-barrier

    Apr 16, 2026Come Fiegel, Pierre Menard, Tadashi Kozuno +2Last-Iterate ConvergenceImperfect-Information Games

    ENSAE Paris – CREST, France · ENS Lyon, France · Isara Labs +2

  29. An Improved Last-Iterate Convergence Rate for Anchored Gradient Descent Ascent

    Apr 4, 2026Anja Surina, Arun Suggala, George Tsoukalas +5Last-Iterate ConvergenceMin-Max Optimization

    Google DeepMind

  30. Minimax Generalized Cross-Entropy

    Mar 20, 2026Kartheek Bondugula, Santiago Mazuelas, Aritz Pérez +1Robust Loss FunctionsMin-Max Optimization

    Basque Center for Applied Mathematics, Bilbao, Spain · Ikerbasque, Basque Foundation for Science · Johns Hopkins University, Baltimore, USA