Stochastic subGradient Methods with Linear Convergence for Polyhedral Convex Optimization

Understand

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.