Timezone: »
Poster
Efficient Projection-free Algorithms for Saddle Point Problems
Cheng Chen · Luo Luo · Weinan Zhang · Yong Yu
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
-
2021 Poster: Curriculum Offline Imitating Learning »
Minghuan Liu · Hanye Zhao · Zhengyu Yang · Jian Shen · Weinan Zhang · Li Zhao · Tie-Yan Liu -
2021 Poster: On Effective Scheduling of Model-based Reinforcement Learning »
Hang Lai · Jian Shen · Weinan Zhang · Yimin Huang · Xing Zhang · Ruiming Tang · Yong Yu · Zhenguo Li -
2020 Poster: Stochastic Recursive Gradient Descent Ascent for Stochastic Nonconvex-Strongly-Concave Minimax Problems »
Luo Luo · Haishan Ye · Zhichao Huang · Tong Zhang -
2020 Poster: Decentralized Accelerated Proximal Gradient Descent »
Haishan Ye · Ziang Zhou · Luo Luo · Tong Zhang -
2020 Poster: Model-based Policy Optimization with Unsupervised Model Adaptation »
Jian Shen · Han Zhao · Weinan Zhang · Yong Yu -
2020 Spotlight: Model-based Policy Optimization with Unsupervised Model Adaptation »
Jian Shen · Han Zhao · Weinan Zhang · Yong Yu -
2017 Demonstration: MAgent: A Many-Agent Reinforcement Learning Research Platform for Artificial Collective Intelligence »
Lianmin Zheng · Jiacheng Yang · Han Cai · Weinan Zhang · Jun Wang · Yong Yu -
2008 Poster: Translated Learning »
Wenyuan Dai · Yuqiang Chen · Gui-Rong Xue · Qiang Yang · Yong Yu -
2008 Spotlight: Translated Learning »
Wenyuan Dai · Yuqiang Chen · Gui-Rong Xue · Qiang Yang · Yong Yu