  We analyze stochastic algorithms for optimizing nonconvex, nonsmooth
finite-sum problems, where the nonconvex part is smooth and the nonsmooth part
is convex. Surprisingly, unlike the smooth case, our knowledge of this
fundamental problem is very limited. For example, it is not known whether the
proximal stochastic gradient method with constant minibatch converges to a
stationary point. To tackle this issue, we develop fast stochastic algorithms
that provably converge to a stationary point for constant minibatches.
Furthermore, using a variant of these algorithms, we show provably faster
convergence than batch proximal gradient descent. Finally, we prove global
linear convergence rate for an interesting subclass of nonsmooth nonconvex
functions, that subsumes several recent works. This paper builds upon our
recent series of papers on fast stochastic methods for smooth nonconvex
optimization [22, 23], with a novel analysis for nonconvex and nonsmooth
functions.
