Linear Convergence of Variance-Reduced Stochastic Gradient without Strong Convexity

Abstract

Stochastic gradient algorithms estimate the gradient based on only one or a few samples and enjoy low computational cost per iteration. They have been widely used in large-scale optimization problems. However, stochastic gradient algorithms are usually slow to converge and achieve sub-linear convergence rates, due to the inherent variance in the gradient computation. To accelerate the convergence, some variance-reduced stochastic gradient algorithms, e.g., proximal stochastic variance-reduced gradient (Prox-SVRG) algorithm, have recently been proposed to solve strongly convex problems. Under the strongly convex condition, these variance-reduced stochastic gradient algorithms achieve a linear convergence rate. However, many machine learning problems are convex but not strongly convex. In this paper, we introduce Prox-SVRG and its projected variant called Variance-Reduced Projected Stochastic Gradient (VRPSG) to solve a class of non-strongly convex optimization problems widely used in machine learning. As the main technical contribution of this paper, we show that both VRPSG and Prox-SVRG achieve a linear convergence rate without strong convexity. A key ingredient in our proof is a Semi-Strongly Convex (SSC) inequality which is the first to be rigorously proved for a class of non-strongly convex problems in both constrained and regularized settings. Moreover, the SSC inequality is independent of algorithms and may be applied to analyze other stochastic gradient algorithms besides VRPSG and Prox-SVRG, which may be of independent interest. To the best of our knowledge, this is the first work that establishes the linear convergence rate for the variance-reduced stochastic gradient algorithms on solving both constrained and regularized problems without strong convexity.

18 pages

References in corpus (3)

• A Stochastic Gradient Method with an Exponential Convergence Rate for Finite Training Sets
• Stochastic Gradient Descent for Non-smooth Optimization: Convergence Results and Optimal Averaging Schemes
• Proximal Stochastic Dual Coordinate Ascent

Cited by in corpus (17)

• Why gradient clipping accelerates training: A theoretical justification for adaptivity
• Riemannian SVRG: Fast Stochastic Optimization on Riemannian Manifolds
• Improved Dynamic Regret for Non-degenerate Functions
• R-SPIDER: A Fast Riemannian Stochastic Optimization Algorithm with Curvature Independent Rate
• Unbiased Simulation for Optimizing Stochastic Function Compositions
• New Analysis of Linear Convergence of Gradient-type Methods via Unifying Error Bound Conditions
• The Physical Systems Behind Optimization Algorithms
• Local Convergence Properties of SAGA/Prox-SVRG and Acceleration
• Accelerate Stochastic Subgradient Method by Leveraging Local Growth Condition
• Linear convergence of SDCA in statistical estimation
• The restricted strong convexity revisited: Analysis of equivalence to error bound and quadratic growth
• A variable metric mini-batch proximal stochastic recursive gradient algorithm with diagonal Barzilai-Borwein stepsize
• A Study of Condition Numbers for First-Order Optimization
• Nearly Optimal Robust Method for Convex Compositional Problems with Heavy-Tailed Noise
• Linear convergence of random dual coordinate incremental aggregated gradient methods
• Randomized Smoothing SVRG for Large-scale Nonsmooth Convex Optimization
• Projected Semi-Stochastic Gradient Descent Method with Mini-Batch Scheme under Weak Strong Convexity Assumption