Introduction
Min-max optimization problems are foundational to modern machine learning, serving as the mathematical backbone for Generative Adversarial Networks (GANs), Robust Optimization, and adversarial training. Despite their importance, standard first-order methods like Gradient Descent Ascent (GDA) suffer from a significant theoretical and practical limitation: they are "initialization-oblivious." In standard minimization, starting an algorithm near the optimal solution typically yields faster convergence. In the convex-concave min-max regime, however, traditional convergence rates depend explicitly on the total diameter of the domain ($D$) rather than the distance to the optimal point ($dist(x_0, x^*)$). This implies that even with a high-quality initial guess, the algorithm's theoretical speed limit remains unchanged.
This paper addresses this gap by introducing a framework for parameter-free algorithms that naturally adapt to their starting points. By leveraging strict-convexity-strict-concavity, the authors demonstrate that it is possible to achieve "initialization-dependent" rates without the need for manual hyper-parameter tuning.
The Problem: Breaking the Domain-Size Barrier
In standard convex-concave optimization, the best-known convergence rates for first-order methods are often tied to the maximum possible distance between any two points in the domain. This is counter-intuitive; one would expect that a better initialization should lead to a faster result. The authors identify two primary objectives:
- Identifying the structural conditions under which initialization-dependent rates are achievable.
- Designing algorithms that exploit these conditions automatically, removing the burden of tuning learning rates ($\eta$) from the user.
Methodology: Coin-Betting and Parameter-Free OCO
The proposed solution shifts away from standard GDA toward a framework based on Parameter-Free Online Convex Optimization (OCO), specifically utilizing "Coin-Betting" (CB) algorithms.
CB-Min-Max (Algorithm 2)
Instead of a unified gradient step, the authors decouple the primal and dual problems. They apply a parameter-free OCO subroutine to each. These algorithms do not require a pre-defined learning rate; instead, they adaptively "bet" on gradient directions. This allows the algorithm to effectively "search" for the distance to the optimum on the fly, making the convergence rate a function of the initial distance rather than the domain diameter.
Strict-Convexity-Strict-Concavity
The authors identify strict-convexity-strict-concavity as the critical structural property required to break the initialization-oblivious barrier. Unlike the more restrictive "strong" convexity, strict convexity does not require a specific quadratic growth rate. However, it is sufficient to ensure a unique optimal solution, which the authors prove allows the "residual" terms—those usually dependent on domain size—to eventually vanish during execution.
Restart-CB-Min-Max (Algorithm 3)
To further accelerate convergence, the authors introduce a restarting scheme. For functions satisfying specific growth conditions and Hölder continuous solution mappings, the Restart-CB-Min-Max algorithm periodically resets the parameter-free subroutines. This allows the method to exploit the local geometry of the loss landscape, achieving novel, fast non-asymptotic convergence rates that surpass the standard $1/\sqrt{T}$ limit.
Empirical Validation
The authors validated their approach through both synthetic benchmarks and high-dimensional real-world applications.
- Synthetic Testing: On a custom 1D non-smooth min-max problem, the CB-Min-Max and Restart-CB-Min-Max algorithms significantly outperformed GDA, even when GDA was equipped with theoretically optimal learning rates. Remarkably, the parameter-free methods were competitive with GDA versions where the learning rate was manually optimized via exhaustive grid search.
- Distributionally Robust Optimization (DRO): The algorithms were tested on eight classic machine learning datasets from the LIBSVM library (including mnist, dna, gisette, and protein). In these DRO tasks, the proposed parameter-free algorithm consistently outperformed the standard primal-dual gradient method in both training and test loss, demonstrating its robustness and practical utility.
Key Insights and Results
The theoretical contribution of this work is highlighted by the proof that the proposed algorithm achieves an asymptotic rate of $\tilde{O}(\frac{dist(x_0, x^*)}{\sqrt{T}})$. This result confirms that the convergence speed scales directly with the quality of the initialization. Furthermore, the work demonstrates that strict convexity is a powerful enough tool to improve algorithmic performance, suggesting that the "heavy hammer" of strong convexity is not always necessary for optimization gains.
Limitations and Future Work
While the results are promising, a complexity gap remains for the specific subclass of strongly-convex-strongly-concave problems. The authors' restart algorithm achieves a complexity of $O(1/\epsilon^{4/3})$, which is slightly slower than the state-of-the-art $O(1/\epsilon)$. Future research will focus on investigating theoretical lower bounds for parameter-free algorithms in min-max settings and extending these insights to non-convex-non-concave landscapes, such as those found in deep generative models.
Summary updated