# Nonsmooth Nonconvex-Nonconcave Minimax Optimization: Primal-Dual Balancing and Iteration Complexity Analysis

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

## Key facts

- Cited by 12 papers in the map (data through 14 Oct 2026).
- Builds on 38 of its 77 references that are in the map.
- First posted on arXiv 22 Sep 2022.

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

- [Towards Deep Learning Models Resistant to Adversarial Attacks](https://mlsanity.com/paper/1706.06083/) (2017)
- [Generative Adversarial Networks](https://mlsanity.com/paper/2203.00667/) (2022)
- [Convex Optimization: Algorithms and Complexity](https://mlsanity.com/paper/1405.4980/) (2014)
- [Agnostic Federated Learning](https://mlsanity.com/paper/1902.00146/) (2019)
- [Certifying Some Distributional Robustness with Principled Adversarial Training](https://mlsanity.com/paper/1710.10571/) (2017)
- [On Gradient Descent Ascent for Nonconvex-Concave Minimax Problems](https://mlsanity.com/paper/1906.00331/) (2019)
- [Large-Scale Methods for Distributionally Robust Optimization](https://mlsanity.com/paper/2010.05893/) (2020)
- [Stochastic model-based minimization of weakly convex functions](https://mlsanity.com/paper/1803.06523/) (2018)
- [Solving a Class of Non-Convex Min-Max Games Using Iterative First Order Methods](https://mlsanity.com/paper/1902.08297/) (2019)
- [Lower Bounds for Finding Stationary Points I](https://mlsanity.com/paper/1710.11606/) (2017)
- [Near-Optimal Algorithms for Minimax Optimization](https://mlsanity.com/paper/2002.02417/) (2020)
- [The Complexity of Constrained Min-Max Optimization](https://mlsanity.com/paper/2009.09623/) (2020)
- [Regularization via Mass Transportation](https://mlsanity.com/paper/1710.10016/) (2017)
- [Efficient Algorithms for Smooth Minimax Optimization](https://mlsanity.com/paper/1907.01543/) (2019)
- [Distributionally Robust Optimization: A Review](https://mlsanity.com/paper/1908.05659/) (2019)
- [Weakly-Convex Concave Min-Max Optimization: Provable Algorithms and Applications in Machine Learning](https://mlsanity.com/paper/1810.02060/) (2018)
- [Error bounds, quadratic growth, and linear convergence of proximal methods](https://mlsanity.com/paper/1602.06661/) (2016)
- [Efficiency of minimizing compositions of convex functions and smooth maps](https://mlsanity.com/paper/1605.00125/) (2016)
- [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)
- [Faster Single-loop Algorithms for Minimax Optimization without Strong Concavity](https://mlsanity.com/paper/2112.05604/) (2021)
- [The Complexity of Nonconvex-Strongly-Concave Minimax Optimization](https://mlsanity.com/paper/2103.15888/) (2021)
- [From error bounds to the complexity of first-order descent methods for convex functions](https://mlsanity.com/paper/1510.08234/) (2015)
- [Efficient Search of First-Order Nash Equilibria in Nonconvex-Concave Smooth Min-Max Problems](https://mlsanity.com/paper/2002.07919/) (2020)
- [Non-convex Min-Max Optimization: Applications, Challenges, and Recent Theoretical Advances](https://mlsanity.com/paper/2006.08141/) (2020)
- [Complexity Lower Bounds for Nonconvex-Strongly-Concave Min-Max Optimization](https://mlsanity.com/paper/2104.08708/) (2021)
- [Calculus of the exponent of Kurdyka-Lojasiewicz inequality and its applications to linear convergence of first-order methods](https://mlsanity.com/paper/1602.02915/) (2016)
- [Minimizing the Maximal Loss: How and Why?](https://mlsanity.com/paper/1602.01690/) (2016)
- [Splitting methods with variable metric for KL functions](https://mlsanity.com/paper/1405.1357/) (2014)

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

- [Universal Gradient Descent Ascent Method for Nonconvex-Nonconcave Minimax Optimization](https://mlsanity.com/paper/2212.12978/) (2022)
- [Worst-case generation via minimax optimization in Wasserstein space](https://mlsanity.com/paper/2512.08176/) (2025)
- [Solving Stochastic Variational Inequalities without the Bounded Variance Assumption](https://mlsanity.com/paper/2602.05531/) (2026)
- [f-FERM: A Scalable Framework for Robust Fair Empirical Risk Minimization](https://mlsanity.com/paper/2312.03259/) (2023)
- [Variance-reduced accelerated methods for decentralized stochastic double-regularized nonconvex strongly-concave minimax problems](https://mlsanity.com/paper/2307.07113/) (2023)
- [A first-order method for nonconvex-nonconcave minimax problems under a local Kurdyka-Lojasiewicz condition](https://mlsanity.com/paper/2507.01932/) (2025)
- [Primal-Dual Methods for Nonsmooth Nonconvex Optimization with Orthogonality Constraints](https://mlsanity.com/paper/2604.04130/) (2026)
- [Nonconvex Composite Functional Constraints via First-Order Augmented Lagrangian Methods under Local Regularity](https://mlsanity.com/paper/2607.08954/) (2026)
- [ℓ1-norm rank-one symmetric matrix factorization has no spurious second-order stationary points](https://mlsanity.com/paper/2410.05025/) (2024)
- [A first-order method for constrained nonconvex-nonconcave minimax optimization](https://mlsanity.com/paper/2510.01168/) (2025)
- [Robust Learning of a Group DRO Neuron](https://mlsanity.com/paper/2601.18115/) (2026)
- [Generative Predictive Distributions for Time Series](https://mlsanity.com/paper/2606.16773/) (2026)

## Abstract (arXiv)

Nonconvex-nonconcave minimax optimization has gained widespread interest over the last decade. However, most existing works focus on variants of gradient descent-ascent (GDA) algorithms, which are only applicable to smooth nonconvex-concave settings. To address this limitation, we propose a novel algorithm named smoothed proximal linear descent-ascent (smoothed PLDA), which can effectively handle a broad range of structured nonsmooth nonconvex-nonconcave minimax problems. Specifically, we consider the setting where the primal function has a nonsmooth composite structure and the dual function possesses the Kurdyka-Lojasiewicz (KL) property with exponent θ ∈ [0,1). We introduce a novel convergence analysis framework for smoothed PLDA, the key components of which are our newly developed nonsmooth primal error bound and dual error bound. Using this framework, we show that smoothed PLDA can find both ε-game-stationary points and ε-optimization-stationary points of the problems of interest in O(ε^-2max2θ,1) iterations. Furthermore, when θ ∈ [0,frac12], smoothed PLDA achieves the optimal iteration complexity of O(ε-2). To further demonstrate the effectiveness and wide applicability of our analysis framework, we show that certain max-structured problem possesses the KL property with exponent θ=0 under mild assumptions. As a by-product, we establish algorithm-independent quantitative relationships among various stationarity concepts, which may be of independent interest.