  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.
