Stochastic Smoothing for Nonsmooth Minimizations: Accelerating SGD by Exploiting Structure

Abstract

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.

Full length version of ICML'12 with all proofs. In this version, a bug in proving Theorem 6 is fixed. We'd like to thank Dr. Francesco Orabona for pointing it out

Cited by in corpus (5)

• Smoothed Variable Sample-size Accelerated Proximal Methods for Nonsmooth Stochastic Convex Programs
• Random minibatch subgradient algorithms for convex problems with functional constraints
• Almost surely constrained convex optimization
• Staggered Time Average Algorithm for Stochastic Non-smooth Optimization with O(1/T) Convergence
• Fast Nonsmooth Regularized Risk Minimization with Continuation