Abstract
The Frank-Wolfe algorithm is a classic method for constrained optimization problems. It has recently been popular in many machine learning applications because its projection-free property leads to more efficient iterations. In this paper, we study projection-free algorithms for convex-strongly-concave saddle point problems with complicated constraints. Our method combines Conditional Gradient Sliding with Mirror-Prox and shows that it only requires $\tilde{O}(1/\sqrt{\epsilon})$ gradient evaluations and $\tilde{O}(1/\epsilon^2)$ linear optimizations in the batch setting. We also extend our method to the stochastic setting and propose first stochastic projection-free algorithms for saddle point problems. Experimental results demonstrate the effectiveness of our algorithms and verify our theoretical guarantees.
Introduction
Saddle point (minimax) problems, formulated as $\min_x \max_y f(x, y)$, are foundational to robust machine learning, including training Generative Adversarial Networks (GANs), robust optimization, and matrix completion. However, these problems become computationally prohibitive when the feasible sets for $x$ and $y$ are complex.
Standard optimization solvers typically rely on projection steps to ensure solutions remain within feasible constraints. For certain constraints, such as nuclear norm balls common in matrix-related tasks, each projection requires a full Singular Value Decomposition (SVD). For high-dimensional data, this SVD step becomes a massive computational bottleneck. While "projection-free" methods like the Frank-Wolfe algorithm have gained traction for standard minimization, their application to minimax settings has remained limited. This work bridges that gap by introducing efficient projection-free algorithms that replace expensive projections with much cheaper Linear Optimization (LO) oracles.
Proposed Methodology
The authors propose two primary algorithms that integrate Mirror-Prox (a classic minimax solver) with Conditional Gradient Sliding (CGS):
- MPCGS (Mirror-Prox Conditional Gradient Sliding): Designed for batch settings, this algorithm utilizes a "Prox-step" procedure to iteratively find approximate maximizers. By leveraging CGS, it decouples gradient evaluations from linear optimizations, achieving optimal rates for both.
- MPSCGS (Mirror-Prox Stochastic Conditional Gradient Sliding): This stochastic variant is tailored for large-scale datasets where computing full gradients is infeasible.
- iSTORC (Inexact Stochastic Variance Reduced CGS): To support the stochastic framework, the authors developed iSTORC as a sub-routine. It employs variance reduction to approximate exact gradients efficiently, representing a significant theoretical contribution.
A key theoretical insight is the demonstration that the internal Prox-step acts as a contraction mapping. This property ensures rapid convergence to a fixed point, maintaining a low overall iteration count.
Experimental Setup
The algorithms were evaluated on a Robust Multiclass Classification task using three standard datasets from the LIBSVM repository: rcv1 ($n=15,564$), sector ($n=6,412$), and news20 ($n=15,935$). The researchers applied a nuclear norm ball constraint to the model parameters, ensuring that the projection step (SVD) would be the primary computational hurdle for baseline methods.
Key Results and Discussion
The core advantage of the proposed methods lies in the trade-off between iteration complexity and per-iteration cost. While projection-based methods like SVRE may require fewer total iterations, the cost of an SVD in every iteration makes them significantly slower in terms of wall-clock time.
As shown in the figure above, MPCGS and MPSCGS consistently outperform the baselines across all datasets. Specifically:
- Wall-clock Speedup: The proposed algorithms reach lower Frank-Wolfe gaps much faster than SVRE and SPFW.
- Stochastic Efficiency: MPSCGS demonstrates a clear advantage over the batch MPCGS on larger datasets, validating the effectiveness of the variance-reduction technique in handling stochastic noise.
- Theoretical Alignment: The empirical convergence rates closely match the predicted $\tilde{O}(1/\sqrt{\epsilon})$ gradient complexity, confirming the practical utility of the theoretical bounds.
Conclusion
This work introduces the first efficient stochastic projection-free algorithms for convex-strongly-concave saddle point problems. By decoupling gradient and linear optimization complexities, MPCGS and MPSCGS offer a scalable solution for problems with complex constraints. Future research will focus on extending this framework to general convex-concave problems, non-smooth objectives, and further optimizing the efficiency of Linear Optimization oracles.
Summary updated