# Solving Non-Convex Non-Differentiable Min-Max Games using Proximal Gradient Method

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

## Key facts

- Cited by 10 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 18 Mar 2020.

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

- [A Max-Min Entropy Framework for Reinforcement Learning](https://mlsanity.com/paper/2106.10517/) (2021)
- [Two-Timescale Gradient Descent Ascent Algorithms for Nonconvex Minimax Optimization](https://mlsanity.com/paper/2408.11974/) (2024)
- [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)
- [A Decentralized Adaptive Momentum Method for Solving a Class of Min-Max Optimization Problems](https://mlsanity.com/paper/2106.06075/) (2021)
- [Nonconvex-Nonconcave Min-Max Optimization with a Small Maximization Domain](https://mlsanity.com/paper/2110.03950/) (2021)
- [Low-rank Matrix Recovery With Unknown Correspondence](https://mlsanity.com/paper/2110.07959/) (2021)
- [Efficient Algorithms for Estimating the Parameters of Mixed Linear Regression Models](https://mlsanity.com/paper/2105.05953/) (2021)
- [RIFLE: Imputation and Robust Inference from Low Order Marginals](https://mlsanity.com/paper/2109.00644/) (2021)
- [Semi-Implicit Hybrid Gradient Methods with Application to Adversarial Robustness](https://mlsanity.com/paper/2202.10523/) (2022)

## Abstract (arXiv)

Min-max saddle point games appear in a wide range of applications in machine leaning and signal processing. Despite their wide applicability, theoretical studies are mostly limited to the special convex-concave structure. While some recent works generalized these results to special smooth non-convex cases, our understanding of non-smooth scenarios is still limited. In this work, we study special form of non-smooth min-max games when the objective function is (strongly) convex with respect to one of the player's decision variable. We show that a simple multi-step proximal gradient descent-ascent algorithm converges to ε-first-order Nash equilibrium of the min-max game with the number of gradient evaluations being polynomial in 1/ε. We will also show that our notion of stationarity is stronger than existing ones in the literature. Finally, we evaluate the performance of the proposed algorithm through adversarial attack on a LASSO estimator.