A Proximal Stochastic Gradient Method with Progressive Variance Reduction

Abstract

We consider the problem of minimizing the sum of two convex functions: one is the average of a large number of smooth component functions, and the other is a general convex function that admits a simple proximal mapping. We assume the whole objective function is strongly convex. Such problems often arise in machine learning, known as regularized empirical risk minimization. We propose and analyze a new proximal stochastic gradient method, which uses a multi-stage scheme to progressively reduce the variance of the stochastic gradient. While each iteration of this algorithm has similar cost as the classical stochastic gradient method (or incremental gradient method), we show that the expected objective value converges to the optimum at a geometric rate. The overall complexity of this method is much lower than both the proximal full gradient method and the standard proximal stochastic gradient method.

References in corpus (3)

• A Stochastic Gradient Method with an Exponential Convergence Rate for Finite Training Sets
• Tail bounds for stochastic approximation
• ASTEP South: a first photometric analysis

Cited by in corpus (17)

• SAGA: A Fast Incremental Gradient Method With Support for Non-Strongly Convex Composite Objectives
• Stochastic Primal-Dual Coordinate Method for Regularized Empirical Risk Minimization
• Stochastic Optimization with Importance Sampling
• Randomized Dual Coordinate Ascent with Arbitrary Sampling
• An Accelerated Proximal Coordinate Gradient Method and its Application to Regularized Empirical Risk Minimization
• Coordinate Descent with Arbitrary Sampling I: Algorithms and Complexity
• SPRING: A fast stochastic proximal alternating method for non-smooth non-convex optimization
• Sketch and Project: Randomized Iterative Methods for Linear Systems and Inverting Matrices
• Coordinate Descent Face-Off: Primal or Dual?
• Side Information Fusion for Recommender Systems over Heterogeneous Information Network
• Accelerated Stochastic Gradient Descent for Minimizing Finite Sums
• Improving Self-supervised Pre-training via a Fully-Explored Masked Language Model
• On Data Preconditioning for Regularized Loss Minimization
• Online and Stochastic Universal Gradient Methods for Minimizing Regularized Hölder Continuous Finite Sums
• Empirical study of PROXTONE and PROXTONE${}^{+}$ for Fast Learning of Large Scale Sparse Models
• Proximal Stochastic Newton-type Gradient Descent Methods for Minimizing Regularized Finite Sums
• Boosting First-Order Methods by Shifting Objective: New Schemes with Faster Worst-Case Rates