SIAM Journal on Optimization (SIOPT), Volume 22, No. 2, 2012, pages 674-701. Posted on arXiv, March 2011.
Randomized Smoothing for (Parallel) Stochastic Optimization, conference version, which includes strongly convex case. Presented at International Conference on Machine Learning (ICML) 2012.
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.