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
-
2022 Poster: Learning Enhanced Representation for Tabular Data via Neighborhood Propagation »
Kounianhua Du · Weinan Zhang · Ruiwen Zhou · Yangkun Wang · Xilong Zhao · Jiarui Jin · Quan Gan · Zheng Zhang · David P Wipf -
2022 : Visual Imitation Learning with Patch Rewards »
Minghuan Liu · Tairan He · Weinan Zhang · Shuicheng Yan · Zhongwen Xu -
2022 : Planning Immediate Landmarks of Targets for Model-Free Skill Transfer across Agents »
Minghuan Liu · Zhengbang Zhu · Menghui Zhu · Yuzheng Zhuang · Weinan Zhang · Jianye Hao -
2022 Poster: Honor of Kings Arena: an Environment for Generalization in Competitive Reinforcement Learning »
Hua Wei · Jingxiao Chen · Xiyang Ji · Hongyang Qin · Minwen Deng · Siqin Li · Liang Wang · Weinan Zhang · Yong Yu · Liu Linc · Lanxiao Huang · Deheng Ye · Qiang Fu · Wei Yang -
2022 Poster: Reinforcement Learning with Automated Auxiliary Loss Search »
Tairan He · Yuge Zhang · Kan Ren · Minghuan Liu · Che Wang · Weinan Zhang · Yuqing Yang · Dongsheng Li -
2022 Poster: Bootstrapped Transformer for Offline Reinforcement Learning »
Kerong Wang · Hanye Zhao · Xufang Luo · Kan Ren · Weinan Zhang · Dongsheng Li -
2022 Poster: PerfectDou: Dominating DouDizhu with Perfect Information Distillation »
Guan Yang · Minghuan Liu · Weijun Hong · Weinan Zhang · Fei Fang · Guangjun Zeng · Yue Lin -
2022 Poster: NeoRL: A Near Real-World Benchmark for Offline Reinforcement Learning »
Rong-Jun Qin · Xingyuan Zhang · Songyi Gao · Xiong-Hui Chen · Zewen Li · Weinan Zhang · Yang Yu -
2022 Poster: Multi-Agent Reinforcement Learning is a Sequence Modeling Problem »
Muning Wen · Jakub Kuba · Runji Lin · Weinan Zhang · Ying Wen · Jun Wang · Yaodong Yang -
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