TL;DR
This paper introduces the first efficient, purely projection-free algorithms for solving convex-strongly-concave saddle point (min-max) problems. By replacing expensive projection steps with simpler linear optimizations, the authors achieve state-of-the-art convergence rates in both batch and stochastic settings. This makes complex constraints, such as nuclear norm balls, computationally feasible for robust machine learning applications.
The Bottleneck of Projections in Min-Max Problems
Many machine learning tasks—including training Generative Adversarial Networks (GANs), robust optimization, and game theory—are formulated as saddle point problems. In these scenarios, one variable is minimized while another is maximized ($\min_x \max_y f(x, y)$).
Standard algorithms for these problems rely on "projections" to keep variables within a feasible set (the constraints). However, for many important constraints like the nuclear norm ball (frequently used in matrix completion or multiclass classification), the projection step requires a full Singular Value Decomposition (SVD). This operation is computationally brutal for high-dimensional data.
While "projection-free" algorithms like Frank-Wolfe exist for standard minimization, adapting them to the min-max setting has historically required restrictive assumptions—such as assuming the solution lies in the interior of the constraint set. This paper bridges that gap by proposing methods that avoid these limitations.
Proposed Methods: MPCGS and MPSCGS
The authors propose two primary algorithms to tackle these challenges:
- Mirror-Prox Conditional Gradient Sliding (MPCGS): Designed for the batch setting, this algorithm combines the Mirror-Prox method (which uses proximal point iterations to stabilize min-max dynamics) with Conditional Gradient Sliding (CGS). CGS is a technique that "skips" unnecessary gradient evaluations by focusing on the linear optimization (LO) oracle.
- Mirror-Prox Stochastic Conditional Gradient Sliding (MPSCGS): An extension for the stochastic setting, where only noisy samples of the gradient are available. To make this work, the authors developed a new variant of a variance-reduction algorithm called iSTORC (Inexact Stochastic Variance Reduced Conditional Gradient Sliding), which handles inexact gradients more robustly than previous versions.
The core advantage of these methods is their reliance on a Linear Optimization (LO) Oracle. Instead of finding the closest point in a set (projection), the algorithm only needs to find the point in the set that is furthest in a specific direction. For a nuclear norm ball, this only requires finding the top singular vector—a significantly faster operation than a full SVD.
Key Insights
- Decoupling Complexity: The algorithms achieve a "best of both worlds" complexity. In the batch setting, they only require $\tilde{O}(1/\sqrt{\epsilon})$ gradient evaluations (matching the best projection-based methods) while using $\tilde{O}(1/\epsilon^2)$ linear optimizations.
- The First of Its Kind: MPSCGS is the first stochastic projection-free algorithm for convex-strongly-concave saddle point problems that does not require the solution to be in the interior of the feasible set.
- Efficiency through Inexactness: A key theoretical contribution is proving that the inner loops of these algorithms don't need to be solved perfectly. By allowing for "inexact" proximal steps, the authors significantly reduce the total number of iterations required.
Empirical Results
The algorithms were evaluated on a robust multiclass classification problem using a nuclear norm ball constraint to test their ability to handle complex, high-dimensional geometry. The tests utilized three real-world datasets from the LIBSVM repository: rcv1, sector, and news20.
- Speedup: In empirical tests, the proposed methods (MPCGS and MPSCGS) significantly outperformed baselines like SPFW (Saddle Point Frank-Wolfe) and SVRE (Stochastic Variance Reduced Extragradient).
- Computational Cost: The projection-based baseline (SVRE) could only complete a few iterations in the time it took the proposed algorithms to converge, primarily due to the heavy cost of SVD-based projections.
- Stochastic Advantage: MPSCGS (the stochastic version) converged faster than the batch version (MPCGS) on large datasets, demonstrating that stochastic sampling is highly effective even in projection-free min-max optimization.
Limitations and Future Work
- Strong Concavity Requirement: The current theoretical guarantees require the function to be strongly concave in one of the variables. While common in robust optimization, many GAN formulations are only convex-concave, which represents a harder class of problems.
- LO Oracle Complexity: While LO is faster than projection, the authors note there is still room to improve the complexity of the LO oracles themselves.
- Generalization: Future work will aim to extend this framework to general convex-concave problems and explore "strongly-convex-strongly-concave" cases to achieve even faster (linear) convergence rates.
Summary updated