# Boosting First-Order Methods by Shifting Objective: New Schemes with Faster Worst-Case Rates

arXiv: https://arxiv.org/abs/2005.12061 · HTML: https://mlsanity.com/paper/2005.12061/

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 25 May 2020.

## Built on by (most cited first, 4 of 4)

- [Practical Schemes for Finding Near-Stationary Points of Convex Finite-Sums](https://mlsanity.com/paper/2105.12062/) (2021)
- [Efficient algorithms for implementing incremental proximal-point methods](https://mlsanity.com/paper/2205.01457/) (2022)
- [Accelerating Perturbed Stochastic Iterates in Asynchronous Lock-Free Optimization](https://mlsanity.com/paper/2109.15292/) (2021)
- [An Adaptive Incremental Gradient Method With Support for Non-Euclidean Norms](https://mlsanity.com/paper/2205.02273/) (2022)

## Abstract (arXiv)

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.