Timezone: »

 
Poster
Boosting First-Order Methods by Shifting Objective: New Schemes with Faster Worst-Case Rates
Kaiwen Zhou · Anthony Man-Cho So · James Cheng

Wed Dec 09 09:00 AM -- 11:00 AM (PST) @ Poster Session 3 #814
in Poster Session 4 »

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.

[ Paper ]

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