Boosting First-Order Methods by Shifting Objective: New Schemes with Faster Worst-Case Rates
This work addresses optimization efficiency for machine learning practitioners, offering incremental improvements in convergence rates for specific problem classes.
The authors tackled the problem of designing faster first-order methods for strongly convex optimization by introducing a shifted objective function that encodes smoothness and strong convexity, resulting in new accelerated schemes with improved worst-case convergence rates compared to existing methods.
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.