Timezone: »
We propose a new methodology to design first-order methods for unconstrained strongly convex problems. Specifically, instead of tackling the original objective directly, we construct a shifted objective function that has the same minimizer as the original objective and encodes both the smoothness and strong convexity of the original objective in an interpolation condition. We then propose an algorithmic template for tackling the shifted objective, which can exploit such a condition. Following this template, we derive several new accelerated schemes for problems that are equipped with various first-order oracles and show that the interpolation condition allows us to vastly simplify and tighten the analysis of the derived methods. In particular, all the derived methods have faster worst-case convergence rates than their existing counterparts. Experiments on machine learning tasks are conducted to evaluate the new methods.
Author Information
Kaiwen Zhou (The Chinese University of Hong Kong)
Anthony Man-Cho So (CUHK)
James Cheng (The Chinese University of Hong Kong)
More from the Same Authors
-
2022 Poster: Learning Causally Invariant Representations for Out-of-Distribution Generalization on Graphs »
Yongqiang Chen · Yonggang Zhang · Yatao Bian · Han Yang · MA Kaili · Binghui Xie · Tongliang Liu · Bo Han · James Cheng -
2022 : Nonsmooth Composite Nonconvex-Concave Minimax Optimization »
Jiajin Li · Linglingzhi Zhu · Anthony Man-Cho So -
2022 : Accelerating Perturbed Stochastic Iterates in Asynchronous Lock-Free Optimization »
Kaiwen Zhou · Anthony Man-Cho So · James Cheng -
2022 Spotlight: Lightning Talks 5B-3 »
Yanze Wu · Jie Xiao · Nianzu Yang · Jieyi Bi · Jian Yao · Yiting Chen · Qizhou Wang · Yangru Huang · Yongqiang Chen · Peixi Peng · Yuxin Hong · Xintao Wang · Feng Liu · Yining Ma · Qibing Ren · Xueyang Fu · Yonggang Zhang · Kaipeng Zeng · Jiahai Wang · GEN LI · Yonggang Zhang · Qitian Wu · Yifan Zhao · Chiyu Wang · Junchi Yan · Feng Wu · Yatao Bian · Xiaosong Jia · Ying Shan · Zhiguang Cao · Zheng-Jun Zha · Guangyao Chen · Tianjun Xiao · Han Yang · Jing Zhang · Jinbiao Chen · MA Kaili · Yonghong Tian · Junchi Yan · Chen Gong · Tong He · Binghui Xie · Yuan Sun · Francesco Locatello · Tongliang Liu · Yeow Meng Chee · David P Wipf · Tongliang Liu · Bo Han · Bo Han · Yanwei Fu · James Cheng · Zheng Zhang -
2022 Spotlight: Learning Causally Invariant Representations for Out-of-Distribution Generalization on Graphs »
Yongqiang Chen · Yonggang Zhang · Yatao Bian · Han Yang · MA Kaili · Binghui Xie · Tongliang Liu · Bo Han · James Cheng -
2022 Spotlight: Lightning Talks 4A-2 »
Barakeel Fanseu Kamhoua · Hualin Zhang · Taiki Miyagawa · Tomoya Murata · Xin Lyu · Yan Dai · Elena Grigorescu · Zhipeng Tu · Lijun Zhang · Taiji Suzuki · Wei Jiang · Haipeng Luo · Lin Zhang · Xi Wang · Young-San Lin · Huan Xiong · Liyu Chen · Bin Gu · Jinfeng Yi · Yongqiang Chen · Sandeep Silwal · Yiguang Hong · Maoyuan Song · Lei Wang · Tianbao Yang · Han Yang · MA Kaili · Samson Zhou · Deming Yuan · Bo Han · Guodong Shi · Bo Li · James Cheng -
2022 Spotlight: Exact Shape Correspondence via 2D graph convolution »
Barakeel Fanseu Kamhoua · Lin Zhang · Yongqiang Chen · Han Yang · MA Kaili · Bo Han · Bo Li · James Cheng -
2022 Poster: Exact Shape Correspondence via 2D graph convolution »
Barakeel Fanseu Kamhoua · Lin Zhang · Yongqiang Chen · Han Yang · MA Kaili · Bo Han · Bo Li · James Cheng -
2020 Poster: Fast Epigraphical Projection-based Incremental Algorithms for Wasserstein Distributionally Robust Support Vector Machine »
Jiajin Li · Caihua Chen · Anthony Man-Cho So -
2019 Poster: A First-Order Algorithmic Framework for Wasserstein Distributionally Robust Logistic Regression »
Jiajin Li · SEN HUANG · Anthony Man-Cho So -
2018 Poster: Norm-Ranging LSH for Maximum Inner Product Search »
Xiao Yan · Jinfeng Li · Xinyan Dai · Hongzhi Chen · James Cheng -
2017 Poster: Accelerated First-order Methods for Geodesically Convex Optimization on Riemannian Manifolds »
Yuanyuan Liu · Fanhua Shang · James Cheng · Hong Cheng · Licheng Jiao -
2014 Poster: Generalized Higher-Order Orthogonal Iteration for Tensor Decomposition and Completion »
Yuanyuan Liu · Fanhua Shang · Wei Fan · James Cheng · Hong Cheng -
2013 Poster: On the Linear Convergence of the Proximal Gradient Method for Trace Norm Regularization »
Ke Hou · Zirui Zhou · Anthony Man-Cho So · Zhi-Quan Luo -
2012 Poster: Learning with Partially Absorbing Random Walks »
Xiao-Ming Wu · Zhenguo Li · Shih-Fu Chang · John Wright · Anthony Man-Cho So -
2009 Poster: Fast Graph Laplacian Regularized Kernel Learning via Semidefinite–Quadratic–Linear Programming »
Xiao-Ming Wu · Anthony Man-Cho So · Zhenguo Li · Shuo-Yen Robert Li -
2009 Spotlight: Fast Graph Laplacian Regularized Kernel Learning via Semidefinite–Quadratic–Linear Programming »
Xiao-Ming Wu · Anthony Man-Cho So · Zhenguo Li · Shuo-Yen Robert Li