A Universal Catalyst for First-Order Optimization

Abstract

We introduce a generic scheme for accelerating first-order optimization methods in the sense of Nesterov, which builds upon a new analysis of the accelerated proximal point algorithm. Our approach consists of minimizing a convex objective by approximately solving a sequence of well-chosen auxiliary problems, leading to faster convergence. This strategy applies to a large class of algorithms, including gradient descent, block coordinate descent, SAG, SAGA, SDCA, SVRG, Finito/MISO, and their proximal variants. For all of these methods, we provide acceleration and explicit support for non-strongly convex objectives. In addition to theoretical speed-up, we also show that acceleration is useful in practice, especially for ill-conditioned problems where we measure significant improvements.

to appear in Advances in Neural Information Processing Systems (NIPS)

References in corpus (5)

• SAGA: A Fast Incremental Gradient Method With Support for Non-Strongly Convex Composite Objectives
• Proximal Stochastic Dual Coordinate Ascent
• Finito: A Faster, Permutable Incremental Gradient Method for Big Data Problems
• Un-regularizing: approximate proximal point and faster stochastic algorithms for empirical risk minimization
• An optimal randomized incremental gradient method

Cited by in corpus (89)

• On the Global Linear Convergence of Frank-Wolfe Optimization Variants
• Optimization for deep learning: theory and algorithms
• Communication-Efficient Distributed Deep Learning: A Comprehensive Survey
• Why gradient clipping accelerates training: A theoretical justification for adaptivity
• The Approximate Duality Gap Technique: A Unified Theory of First-Order Methods
• Fast and Simple PCA via Convex Optimization
• A Generalized Accelerated Composite Gradient Method: Uniting Nesterov's Fast Gradient Method and FISTA
• Tight Complexity Bounds for Optimizing Composite Objectives
• Adaptive restart of accelerated gradient methods under local quadratic growth condition
• Stochastic L-BFGS: Improved Convergence Rates and Practical Acceleration Strategies
• The Practicality of Stochastic Optimization in Imaging Inverse Problems
• SDCA without Duality, Regularization, and Individual Convexity
• A unified variance-reduced accelerated gradient method for convex optimization
• On the Adaptivity of Stochastic Gradient-Based Optimization
• Recent theoretical advances in decentralized distributed convex optimization
• Estimate Sequences for Stochastic Composite Optimization: Variance Reduction, Acceleration, and Robustness to Noise
• Convergence of Distributed Stochastic Variance Reduced Methods without Sampling Extra Data
• Contracting Proximal Methods for Smooth Convex Optimization
• Painless Stochastic Gradient: Interpolation, Line-Search, and Convergence Rates
• Fast and Faster Convergence of SGD for Over-Parameterized Models and an Accelerated Perceptron
• Solving Empirical Risk Minimization in the Current Matrix Multiplication Time
• PAGE: A Simple and Optimal Probabilistic Gradient Estimator for Nonconvex Optimization
• Universal gradient descent
• Asynchronous Accelerated Proximal Stochastic Gradient for Strongly Convex Distributed Finite Sums
• Catalyst Acceleration for Gradient-Based Non-Convex Optimization
• Accelerating Smooth Games by Manipulating Spectral Shapes
• On the Iteration Complexity of Oblivious First-Order Optimization Algorithms
• Less than a Single Pass: Stochastically Controlled Stochastic Gradient Method
• Stochastic Newton and Cubic Newton Methods with Simple Local Linear-Quadratic Rates
• Statistically Preconditioned Accelerated Gradient Method for Distributed Optimization
• A Generic Acceleration Framework for Stochastic Composite Optimization
• Smooth Monotone Stochastic Variational Inequalities and Saddle Point Problems: A Survey
• The Proximal Robbins-Monro Method
• Stochastic Canonical Correlation Analysis
• Solving smooth min-min and min-max problems by mixed oracle algorithms
• On the Ineffectiveness of Variance Reduced Optimization for Deep Learning
• Stochastic Nonconvex Optimization with Large Minibatches
• The Complexity of Nonconvex-Strongly-Concave Minimax Optimization
• On Communication Compression for Distributed Optimization on Heterogeneous Data
• Mini-Batch Stochastic ADMMs for Nonconvex Nonsmooth Optimization
• Acceleration in Distributed Optimization under Similarity
• GENO -- GENeric Optimization for Classical Machine Learning
• A Hybrid Stochastic Optimization Framework for Stochastic Composite Nonconvex Optimization
• A Stochastic Proximal Point Algorithm for Saddle-Point Problems
• Efficient Algorithms for Large-scale Generalized Eigenvector Computation and Canonical Correlation Analysis
• Stochastic Subspace Descent
• ANITA: An Optimal Loopless Accelerated Variance-Reduced Gradient Method
• From low probability to high confidence in stochastic convex optimization
• Mini-batch stochastic subgradient for functional constrained optimization
• Potential Function-based Framework for Making the Gradients Small in Convex and Min-Max Optimization
• MISO is Making a Comeback With Better Proofs and Rates
• A Stochastic Extra-Step Quasi-Newton Method for Nonsmooth Nonconvex Optimization
• Dual-Free Stochastic Decentralized Optimization with Variance Reduction
• CANITA: Faster Rates for Distributed Convex Optimization with Communication Compression
• Inexact Tensor Methods with Dynamic Accuracies
• Near-Optimal Methods for Minimizing Star-Convex Functions and Beyond
• On the Complexity Analysis of the Primal Solutions for the Accelerated Randomized Dual Coordinate Ascent
• Katyusha Acceleration for Convex Finite-Sum Compositional Optimization
• Globally Convergent Newton Methods for Ill-conditioned Generalized Self-concordant Losses
• An Inexact Variable Metric Proximal Point Algorithm for Generic Quasi-Newton Acceleration
• A Linearly Convergent Algorithm for Decentralized Optimization: Sending Less Bits for Free!
• Katalyst: Boosting Convex Katayusha for Non-Convex Problems with a Large Condition Number
• How Does Momentum Help Frank Wolfe?
• Locally Accelerated Conditional Gradients
• A stochastic subspace approach to gradient-free optimization in high dimensions
• Structured Logconcave Sampling with a Restricted Gaussian Oracle
• Output Perturbation for Differentially Private Convex Optimization: Faster and More General
• Delayed Projection Techniques for Linearly Constrained Problems: Convergence Rates, Acceleration, and Applications
• Numerical methods in large-scale optimization: inexact oracle and primal-dual analysis
• On the Complexity of Minimizing Convex Finite Sums Without Using the Indices of the Individual Functions
• Reducing Runtime by Recycling Samples
• Variance Reduced Coordinate Descent with Acceleration: New Method With a Surprising Application to Finite-Sum Problems
• A Smoother Way to Train Structured Prediction Models
• A Unifying Framework for Variance Reduction Algorithms for Finding Zeroes of Monotone Operators
• Efficient Globally Convergent Stochastic Optimization for Canonical Correlation Analysis
• Accelerated gradient sliding and variance reduction
• Asynchronous Distributed Optimization with Stochastic Delays
• Boosting First-Order Methods by Shifting Objective: New Schemes with Faster Worst-Case Rates
• Optimization for Supervised Machine Learning: Randomized Algorithms for Data and Parameters
• Accelerated Randomized Mirror Descent Algorithms For Composite Non-strongly Convex Optimization
• Acceleration of SVRG and Katyusha X by Inexact Preconditioning
• Curvature-Exploiting Acceleration of Elastic Net Computations
• Convex optimization
• Convergence and Stability of the Stochastic Proximal Point Algorithm with Momentum
• Accelerated Stochastic ExtraGradient: Mixing Hessian and Gradient Similarity to Reduce Communication in Distributed and Federated Learning
• Stochastic Bias-Reduced Gradient Methods
• Tight Lower Complexity Bounds for Strongly Convex Finite-Sum Optimization
• Accelerated Proximal Envelopes: Application to the Coordinate Descent Method
• Optimization Methods for Fully Composite Problems