# On the Initialization for Convex-Concave Min-max Problems

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

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- Builds on 30 of its 60 references that are in the map.
- First posted on arXiv 27 Feb 2021.

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

- [Towards Deep Learning Models Resistant to Adversarial Attacks](https://mlsanity.com/paper/1706.06083/) (2017)
- [Online Learning: A Modern Introduction Using Convex Optimization](https://mlsanity.com/paper/1912.13213/) (2019)
- [Approximation Methods for Bilevel Programming](https://mlsanity.com/paper/1802.02246/) (2018)
- [Training GANs with Optimism](https://mlsanity.com/paper/1711.00141/) (2017)
- [A Unified Analysis of Extra-gradient and Optimistic Gradient Methods for Saddle Point Problems: Proximal Point Approach](https://mlsanity.com/paper/1901.08511/) (2019)
- [Coin Betting and Parameter-Free Online Learning](https://mlsanity.com/paper/1602.04128/) (2016)
- [Black-Box Reductions for Parameter-free Online Learning in Banach Spaces](https://mlsanity.com/paper/1802.06293/) (2018)
- [Near-Optimal Algorithms for Minimax Optimization](https://mlsanity.com/paper/2002.02417/) (2020)
- [Last-Iterate Convergence: Zero-Sum Games and Constrained Min-Max Optimization](https://mlsanity.com/paper/1807.04252/) (2018)
- [Lower complexity bounds of first-order methods for convex-concave bilinear saddle-point problems](https://mlsanity.com/paper/1808.02901/) (2018)
- [Interaction Matters: A Note on Non-asymptotic Local Convergence of Generative Adversarial Networks](https://mlsanity.com/paper/1802.06132/) (2018)
- [Halpern Iteration for Near-Optimal and Parameter-Free Monotone Inclusion and Strong Solutions to Variational Inequalities](https://mlsanity.com/paper/2002.08872/) (2020)
- [Negative Momentum for Improved Game Dynamics](https://mlsanity.com/paper/1807.04740/) (2018)
- [Last Iterate is Slower than Averaged Iterate in Smooth Convex-Concave Saddle Point Problems](https://mlsanity.com/paper/2002.00057/) (2020)
- [Explore Aggressively, Update Conservatively: Stochastic Extragradient Methods with Variable Stepsize Scaling](https://mlsanity.com/paper/2003.10162/) (2020)
- [Unconstrained Online Linear Learning in Hilbert Spaces: Minimax Algorithms and Normal Approximations](https://mlsanity.com/paper/1403.0628/) (2014)
- [Online Learning Without Prior Information](https://mlsanity.com/paper/1703.02629/) (2017)
- [Accelerated Schemes For A Class of Variational Inequalities](https://mlsanity.com/paper/1403.4164/) (2014)
- [Finite Regret and Cycles with Fixed Step-Size via Alternating Gradient Descent-Ascent](https://mlsanity.com/paper/1907.04392/) (2019)
- [Simultaneous Model Selection and Optimization through Parameter-free Stochastic Learning](https://mlsanity.com/paper/1406.3816/) (2014)
- [A Universal Algorithm for Variational Inequalities Adaptive to Smoothness and Noise](https://mlsanity.com/paper/1902.01637/) (2019)
- [Last-iterate convergence rates for min-max optimization](https://mlsanity.com/paper/1906.02027/) (2019)
- [Faster Rates for Convex-Concave Games](https://mlsanity.com/paper/1805.06792/) (2018)
- [Optimal Primal-Dual Methods for a Class of Saddle Point Problems](https://mlsanity.com/paper/1309.5548/) (2013)
- [Adaptive scale-invariant online algorithms for learning linear models](https://mlsanity.com/paper/1902.07528/) (2019)
- [Accelerating Smooth Games by Manipulating Spectral Shapes](https://mlsanity.com/paper/2001.00602/) (2020)
- [RSG: Beating Subgradient Method without Smoothness and Strong Convexity](https://mlsanity.com/paper/1512.03107/) (2015)
- [Online Convex Optimization with Unconstrained Domains and Losses](https://mlsanity.com/paper/1703.02622/) (2017)
- [Scale-invariant unconstrained online learning](https://mlsanity.com/paper/1708.07042/) (2017)
- [Matrix-Free Preconditioning in Online Learning](https://mlsanity.com/paper/1905.12721/) (2019)

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

- [Unconstrained Online Learning with Unbounded Losses](https://mlsanity.com/paper/2306.04923/) (2023)
- [Near-Optimal Algorithms for Making the Gradient Small in Stochastic Minimax Optimization](https://mlsanity.com/paper/2208.05925/) (2022)
- [Dealing with unbounded gradients in stochastic saddle-point optimization](https://mlsanity.com/paper/2402.13903/) (2024)
- [Optimal Exploration is no harder than Thompson Sampling](https://mlsanity.com/paper/2310.06069/) (2023)

## Abstract (arXiv)

Convex-concave min-max problems are ubiquitous in machine learning, and people usually utilize first-order methods (e.g., gradient descent ascent) to find the optimal solution. One feature which separates convex-concave min-max problems from convex minimization problems is that the best known convergence rates for min-max problems have an explicit dependence on the size of the domain, rather than on the distance between initial point and the optimal solution. This means that the convergence speed does not have any improvement even if the algorithm starts from the optimal solution, and hence, is oblivious to the initialization. Here, we show that strict-convexity-strict-concavity is sufficient to get the convergence rate to depend on the initialization. We also show how different algorithms can asymptotically achieve initialization-dependent convergence rates on this class of functions. Furthermore, we show that the so-called "parameter-free" algorithms allow to achieve improved initialization-dependent asymptotic rates without any learning rate to tune. In addition, we utilize this particular parameter-free algorithm as a subroutine to design a new algorithm, which achieves a novel non-asymptotic fast rate for strictly-convex-strictly-concave min-max problems with a growth condition and H"older continuous solution mapping. Experiments are conducted to verify our theoretical findings and demonstrate the effectiveness of the proposed algorithms.