Stochastic subGradient Methods with Linear Convergence for Polyhedral Convex Optimization
This provides a theoretical advancement for machine learning practitioners dealing with sparse or structured optimization problems, though it is incremental as it extends known deterministic results to stochastic settings.
The paper tackles the problem of achieving linear convergence for non-smooth, non-strongly convex optimization with polyhedral epigraphs, such as in ℓ1-constrained machine learning tasks, by proposing a stochastic subgradient method with restarting (RSGD) that attains this rate, marking the first such result for stochastic methods in this class.
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.