Stochastic Smoothing for Nonsmooth Minimizations: Accelerating SGD by Exploiting Structure

Understand

In this work we consider the stochastic minimization of nonsmooth convex loss functions, a central problem in machine learning.

• We propose a novel algorithm called Accelerated Nonsmooth Stochastic Gradient Descent (ANSGD), which exploits the structure of common nonsmooth loss functions to achieve optimal convergence rates for a class of problems including SVMs.
• It is the first stochastic algorithm that can achieve the optimal O(1/t) rate for minimizing nonsmooth loss functions (with strong convexity).
• The fast rates are confirmed by empirical comparisons, in which ANSGD significantly outperforms previous subgradient descent algorithms including SGD.