# Fast Objective & Duality Gap Convergence for Non-Convex Strongly-Concave Min-Max Problems with PL Condition

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

## Key facts

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

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

- [AUC Maximization in the Era of Big Data and AI: A Survey](https://mlsanity.com/paper/2203.15046/) (2022)
- [Faster Single-loop Algorithms for Minimax Optimization without Strong Concavity](https://mlsanity.com/paper/2112.05604/) (2021)
- [Stochastic Optimization of Areas Under Precision-Recall Curves with Provable Convergence](https://mlsanity.com/paper/2104.08736/) (2021)
- [Federated Deep AUC Maximization for Heterogeneous Data with a Constant Communication Complexity](https://mlsanity.com/paper/2102.04635/) (2021)
- [Finding Second-Order Stationary Points in Nonconvex-Strongly-Concave Minimax Optimization](https://mlsanity.com/paper/2110.04814/) (2021)
- [Algorithmic Foundations of Empirical X-risk Minimization](https://mlsanity.com/paper/2206.00439/) (2022)
- [SGDA with shuffling: faster convergence for nonconvex-PL minimax optimization](https://mlsanity.com/paper/2210.05995/) (2022)
- [A first-order augmented Lagrangian method for constrained minimax optimization](https://mlsanity.com/paper/2301.02060/) (2023)
- [Tight Analysis of Extra-gradient and Optimistic Gradient Methods For Nonconvex Minimax Problems](https://mlsanity.com/paper/2210.09382/) (2022)
- [Deep AUC Maximization for Medical Image Classification: Challenges and Opportunities](https://mlsanity.com/paper/2111.02400/) (2021)
- [An Efficient Stochastic Algorithm for Decentralized Nonconvex-Strongly-Concave Minimax Optimization](https://mlsanity.com/paper/2212.02387/) (2022)
- [Causality-Driven One-Shot Learning for Prostate Cancer Grading from MRI](https://mlsanity.com/paper/2309.10725/) (2023)
- [Faster Stochastic Algorithms for Minimax Optimization under Polyak--Lojasiewicz Conditions](https://mlsanity.com/paper/2307.15868/) (2023)
- [Exploiting Causality Signals in Medical Images: A Pilot Study with Empirical Results](https://mlsanity.com/paper/2309.10399/) (2023)
- [Category-wise Fine-Tuning: Resisting Incorrect Pseudo-Labels in Multi-Label Image Classification with Partial Labels](https://mlsanity.com/paper/2401.16991/) (2024)
- [Boosting Few-Shot Learning with Disentangled Self-Supervised Learning and Meta-Learning for Medical Image Classification](https://mlsanity.com/paper/2403.17530/) (2024)
- [AUC Optimization from Multiple Unlabeled Datasets](https://mlsanity.com/paper/2305.15776/) (2023)
- [A first-order method for nonconvex-strongly-concave constrained minimax optimization](https://mlsanity.com/paper/2512.22909/) (2025)
- [Communication-Efficient Federated AUC Maximization with Cyclic Client Participation](https://mlsanity.com/paper/2601.01649/) (2026)

## Abstract (arXiv)

This paper focuses on stochastic methods for solving smooth non-convex strongly-concave min-max problems, which have received increasing attention due to their potential applications in deep learning (e.g., deep AUC maximization, distributionally robust optimization). However, most of the existing algorithms are slow in practice, and their analysis revolves around the convergence to a nearly stationary point.We consider leveraging the Polyak-Lojasiewicz (PL) condition to design faster stochastic algorithms with stronger convergence guarantee. Although PL condition has been utilized for designing many stochastic minimization algorithms, their applications for non-convex min-max optimization remain rare. In this paper, we propose and analyze a generic framework of proximal stage-based method with many well-known stochastic updates embeddable. Fast convergence is established in terms of both the primal objective gap and the duality gap. Compared with existing studies, (i) our analysis is based on a novel Lyapunov function consisting of the primal objective gap and the duality gap of a regularized function, and (ii) the results are more comprehensive with improved rates that have better dependence on the condition number under different assumptions. We also conduct deep and non-deep learning experiments to verify the effectiveness of our methods.