Randomized Smoothing for Stochastic Optimization

Randomized Smoothing for Stochastic Optimization

John C. Duchi, Peter L. Bartlett, and Martin J. Wainwright

SIAM Journal on Optimization (SIOPT), Volume 22, No. 2, 2012, pages 674-701. Posted on arXiv, March 2011.

We analyze convergence rates of stochastic optimization procedures for non-smooth convex optimization problems. By combining randomized smoothing techniques with accelerated gradient methods, we obtain optimal variance-based convergence rates of stochastic optimization procedures, both in expectation and with high probability, To the best of our knowledge, these are the first variance-based rates for non-smooth optimization. We give several applications of our results to statistical estimation problems, and provide experimental results that demonstrate the effectiveness of the proposed algorithms. We also describe how a combination of our algorithm with recent work on decentralized optimization yields a distributed stochastic optimization algorithm that is order-optimal.