Convergence of Stochastic Proximal Gradient Algorithm

2014/03/20 by Lorenzo Rosasco, Silvia Villa, Rosasco, Lorenzo +3 · 3 citations
Mathematics · #62G08 #65K10 #90C15 #90C25 #FOS: Mathematics #Optimization and Control (math.OC) #math.OC #msc:62G08 #msc:65K10 #msc:90C15 #msc:90C25

paper · pdf · doi:10.48550/arxiv.1403.5074

24 pages

arxiv created 2014/09/16 · arxiv updated 2016/08/10

Abstract

We prove novel convergence results for a stochastic proximal gradient algorithm suitable for solving a large class of convex optimization problems, where a convex objective function is given by the sum of a smooth and a possibly non-smooth component. We consider the iterates convergence and derive O(1/n) non asymptotic bounds in expectation in the strongly convex case, as well as almost sure convergence results under weaker assumptions. Our approach allows to avoid averaging and weaken boundedness assumptions which are often considered in theoretical studies and might not be satisfied in practice.

Cited by

• S-D-RSM: Stochastic Distributed Regularized Splitting Method for Large-Scale Convex Optimization Problems
• On Tackling High-Dimensional Nonconvex Stochastic Optimization via Stochastic First-Order Methods with Non-smooth Proximal Terms and Variance Reduction
• Computer-aided analyses of stochastic first-order methods, via interpolation conditions for stochastic optimization

Related

• Stochastic Proximal Methods for Non-Smooth Non-Convex Constrained Sparse Optimization
• Nonasymptotic convergence of stochastic proximal point algorithms for constrained convex optimization
• A Simple Proximal Stochastic Gradient Method for Nonsmooth Nonconvex Optimization
• New nonasymptotic convergence rates of stochastic proximal pointalgorithm for convex optimization problems
• On the Convergence and Complexity of Proximal Gradient and Accelerated Proximal Gradient Methods under Adaptive Gradient Estimation