Stochastic subGradient Methods with Linear Convergence for Polyhedral Convex Optimization

Abstract

In this paper, we show that simple {Stochastic} subGradient Decent methods with multiple Restarting, named {\bf RSGD}, can achieve a \textit{linear convergence rate} for a class of non-smooth and non-strongly convex optimization problems where the epigraph of the objective function is a polyhedron, to which we refer as {\bf polyhedral convex optimization}. Its applications in machine learning include ${\ell }_1$ constrained or regularized piecewise linear loss minimization and submodular function minimization. To the best of our knowledge, this is the first result on the linear convergence rate of stochastic subgradient methods for non-smooth and non-strongly convex optimization problems.

This paper has been withdrawn by the author due to that it has been merged into arXiv manuscript arXiv:1512.03107

References in corpus (4)

• SAGA: A Fast Incremental Gradient Method With Support for Non-Strongly Convex Composite Objectives
• Stochastic Gradient Descent for Non-smooth Optimization: Convergence Results and Optimal Averaging Schemes
• Stochastic Dual Coordinate Ascent Methods for Regularized Loss Minimization
• A Framework for Applying Subgradient Methods to Conic Optimization Problems

Cited by in corpus (4)

• SGDR: Stochastic Gradient Descent with Warm Restarts
• Fast Stochastic Variance Reduced Gradient Method with Momentum Acceleration for Machine Learning
• Nonasymptotic convergence of stochastic proximal point algorithms for constrained convex optimization
• Randomized Smoothing SVRG for Large-scale Nonsmooth Convex Optimization