Min-Max Optimization

Follow this topic Ask about this topic

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

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

ADV-0: Closed-Loop Min-Max Adversarial Training for Long-Tail Robustness in Autonomous Driving
Mar 16, 2026Tong Nie, Yihong Tang, Junlin He +5Long-Tail Autonomous Driving Adversarial Training
The Hong Kong Polytechnic University, Hong Kong SAR, China · Tongji University, Shanghai, China · McGill University, Montreal, QC, Canada
Revisiting Sharpness-Aware Minimization: A More Faithful and Effective Implementation
Mar 9, 2026Jianlong Chen, Zhiming ZhouSharpness-Aware Minimization Deep Learning Optimization
Key Laboratory of Interdisciplinary Research of Computation and Economics Shanghai University of Finance and Economics
On the Stability Connection Between Discrete-Time Algorithms and Their Resolution ODEs: Applications to Min-Max Optimisation
Mar 2, 2026Amir Ali Farzin, Yuen-Man Pun, Philipp Braun +1Optimization Convergence Analysis Min-Max Optimization
School of Engineering, Australian National University · Department of Electrical and Electronic Engineering, University of Melbourne
Differentially Private Non-convex Distributionally Robust Optimization
Feb 18, 2026Difei Xu, Meng Ding, Zebin Ma +4Distributionally Robust Optimization Differential Privacy
Provable Responsible AI and Data Analytics (PRADA) Lab · King Abdullah University of Science and Technology · State University of New York at Buffalo +1
Solving the Offline and Online Min-Max Problem of Non-smooth Submodular-Concave Functions: A Zeroth-Order Approach
Jan 29, 2026Amir Ali Farzin, Yuen-Man Pun, Philipp Braun +2Min-Max Optimization Submodular Optimization
School of Engineering, Australian National University, Canberra, Australia · Department of Mechanical Engineering, University of Texas at Dallas, Richardson, Texas, USA · Department of Electrical and Electronic Engineering, The University of Melbourne, Parkville, Australia
Negative Stepsizes Make Gradient-Descent-Ascent Converge
May 2, 2025Henry Shugart, Jason M. AltschulerLearning Rate Scheduling Optimization Convergence Analysis
UPenn
A stochastic smoothing framework for nonconvex-nonconcave minEmax problems with applications to Wasserstein distributionally robust optimization
Feb 24, 2025Wei Liu, Muhammad Khan, Gabriel Mancino-Ball +1Randomized Smoothing Nonconvex Stochastic Optimization
Department of Applied Mathematics, Hong Kong Polytechnic University, Hong Kong, China · Institute for Math & AI, Wuhan (IMAI), Wuhan university, China · Department of Mathematical Sciences Rensselaer Polytechnic Institute, Troy, NY, USA
Accelerated Stochastic Min-Max Optimization Based on Bias-corrected Momentum
Jun 18, 2024Haoyuan Cai, Sulaiman A. Alghunaim, Ali H. SayedMomentum Methods Nonconvex Stochastic Optimization
Ecole Polytechnique Fédérale de Lausanne, Switzerland · Kuwait University, Kuwait

Mar 16, 2026J/K move · Enter open · S save

ADV-0: Closed-Loop Min-Max Adversarial Training for Long-Tail Robustness in Autonomous Driving

Tong Nie, Yihong Tang, Junlin He, Yuewen Mei+4

The Hong Kong Polytechnic University, Hong Kong SAR, China · Tongji University, Shanghai, China · McGill University, Montreal, QC, Canada

Long-Tail Autonomous Driving Adversarial Training Autonomous Driving Adversarial Scenario Generation Min-Max Optimization Autonomous Driving Planning

Open paper AskPDF arXiv

Deploying autonomous driving systems requires robustness against long-tail scenarios that are rare but safety-critical. While adversarial training offers a promising solution, existing methods typically decouple scenario generation from policy optimization and rely on heuristic surrogates. This leads to objective misalignment and fails to capture the shifting failure modes of evolving policies. This paper presents ADV-0, a closed-loop min-max optimization framework that treats the interaction between driving policy (defender) and adversarial agent (attacker) as a zero-sum Markov game. By aligning the attacker's utility directly with the defender's objective, we reveal the optimal adversary distribution. To make this tractable, we cast dynamic adversary evolution as iterative preference learning, efficiently approximating this optimum and offering an algorithm-agnostic solution to the game. Theoretically, ADV-0 converges to a Nash Equilibrium and maximizes a certified lower bound on real-world performance. Experiments indicate that it effectively exposes diverse safety-critical failures and greatly enhances the generalizability of both learned policies and motion planners against unseen long-tail risks.