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
-
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