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

Abstract

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.

arXiv commentNeurIPS 2020, 29 pages, 7 figures

References in corpus (20)

• Scikit-learn: Machine Learning in Python
• SAGA: A Fast Incremental Gradient Method With Support for Non-Strongly Convex Composite Objectives
• A Stochastic Gradient Method with an Exponential Convergence Rate for Finite Training Sets
• The rate of convergence of Nesterov's accelerated forward-backward method is actually faster than $1/k^2$
• A Universal Catalyst for First-Order Optimization
• Optimized first-order methods for smooth convex minimization
• A Lyapunov Analysis of Momentum Methods in Optimization
• Another look at the fast iterative shrinkage/thresholding algorithm (FISTA)
• Un-regularizing: approximate proximal point and faster stochastic algorithms for empirical risk minimization
• A Simple Stochastic Variance Reduced Algorithm with Fast Convergence Rates
• A Simple Practical Accelerated Method for Finite Sums
• Tight Complexity Bounds for Optimizing Composite Objectives
• Generalizing the optimized gradient method for smooth convex minimization
• A unified variance-reduced accelerated gradient method for convex optimization
• Direct Acceleration of SAGA using Sampled Negative Momentum
• A Proximal Stochastic Gradient Method with Progressive Variance Reduction
• Estimate Sequences for Variance-Reduced Stochastic Composite Optimization
• Dissipativity Theory for Nesterov's Accelerated Method
• On the Properties of Convex Functions over Open Sets
• Potential-based analyses of first-order methods for constrained and composite optimization