Efficient Projection-Free Algorithms for Saddle Point Problems
This work addresses optimization challenges in machine learning for constrained saddle point problems, offering incremental improvements in efficiency for researchers and practitioners.
The paper tackles saddle point problems with complex constraints by developing projection-free algorithms, achieving Õ(1/√ε) gradient evaluations and Õ(1/ε²) linear optimizations in batch settings, with extensions to stochastic settings and experimental validation.
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ε)$ gradient evaluations and $\tilde{O}(1/ε^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.