Timezone: »

 
Poster
Efficient Projection-free Algorithms for Saddle Point Problems
Cheng Chen · Luo Luo · Weinan Zhang · Yong Yu

Wed Dec 09 09:00 PM -- 11:00 PM (PST) @ Poster Session 4 #1182
in Poster Session 5 »
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 show that it only requires $\tilde{\cO}(1/\sqrt{\epsilon})$ gradient evaluations and $\tilde{\cO}(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.

Author Information

Cheng Chen (Shanghai Jiao Tong University)
Luo Luo (The Hong Kong University of Science and Technology)
Weinan Zhang (Shanghai Jiao Tong University)
Yong Yu (Shanghai Jiao Tong Unviersity)

More from the Same Authors