A unified variance-reduced accelerated gradient method for convex optimization

Abstract

We propose a novel randomized incremental gradient algorithm, namely, VAriance-Reduced Accelerated Gradient (Varag), for finite-sum optimization. Equipped with a unified step-size policy that adjusts itself to the value of the condition number, Varag exhibits the unified optimal rates of convergence for solving smooth convex finite-sum problems directly regardless of their strong convexity. Moreover, Varag is the first accelerated randomized incremental gradient method that benefits from the strong convexity of the data-fidelity term to achieve the optimal linear convergence. It also establishes an optimal linear rate of convergence for solving a wide class of problems only satisfying a certain error bound condition rather than strong convexity. Varag can also be extended to solve stochastic finite-sum problems.

33rd Conference on Neural Information Processing Systems (NeurIPS 2019)

References in corpus (4)

• A Universal Catalyst for First-Order Optimization
• Estimate Sequences for Stochastic Composite Optimization: Variance Reduction, Acceleration, and Robustness to Noise
• Exploiting Strong Convexity from Data with Primal-Dual First-Order Algorithms
• Rest-Katyusha: Exploiting the Solution's Structure via Scheduled Restart Schemes

Cited by in corpus (13)

• Acceleration for Compressed Gradient Descent in Distributed and Federated Optimization
• On the Adaptivity of Stochastic Gradient-Based Optimization
• PAGE: A Simple and Optimal Probabilistic Gradient Estimator for Nonconvex Optimization
• On Biased Stochastic Gradient Estimation
• ANITA: An Optimal Loopless Accelerated Variance-Reduced Gradient Method
• Stochastic Gradient Hamiltonian Monte Carlo with Variance Reduction for Bayesian Inference
• Accelerated Stochastic Algorithms for Nonconvex Finite-sum and Multi-block Optimization
• A Feasible Level Proximal Point Method for Nonconvex Sparse Constrained Optimization
• Practical Schemes for Finding Near-Stationary Points of Convex Finite-Sums
• A Fast Anderson-Chebyshev Acceleration for Nonlinear Optimization
• Accelerated gradient sliding and variance reduction
• Method with Batching for Stochastic Finite-Sum Variational Inequalities in Non-Euclidean Setting
• Boosting First-Order Methods by Shifting Objective: New Schemes with Faster Worst-Case Rates