Randomized Smoothing for Stochastic Optimization

By John C. Duchi, Peter L. Bartlett, Martin J. Wainwright. 2011

323 citations recorded by the source corpus.

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 convergence rates of stochastic optimization procedures, both in expectation and with high probability, that have optimal dependence on the variance of the gradient estimates. 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.

Subfields: Artificial Intelligence, Computational Mechanics, Statistics and Probability

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computational Mechanics

In Statistics and Probability

Citations in the corpus

Privacy Amplification by Iteration (2018, methodology): “While smoothing a non-smooth objective is a standard technique in optimization (e.g., see [Nes05, DBW12]) we are not aware of bounds that are stated in the form we need.”
Certified Adversarial Robustness via Randomized Smoothing (2019, methodology): “If the base classifier f is likely to return x’s correct class when fed noisy corruptions of x, then the smoothed classifier (1)We adopt this term because it has been used to describe a similar technique in a different context (Duchi et al., 2012).”
Optimal Algorithms for Non-Smooth Distributed Optimization in Networks (2018, methodology): “Under the more challenging global regularity assumption, we show in Section 3 that distributing the simple smoothing approach introduced in [10] yields fast convergence rates with respect to communication.”
Taming the Wild: A Unified Analysis of Hogwild!-Style Algorithms (2015, background): “have been proposed [5, 11, 12, 21, 22, 23]; only a fraction of these algorithms have been analyzed in the asynchronous case.”
An asynchronous mini-batch algorithm for regularized stochastic optimization (2015, neutral): “This assumption is commonly used in the analysis for stochastic optimization algorithms, for example, [5]–[10], [19], [27]–[29], [41]–[43].”
Training Recurrent Neural Networks by Diffusion (2016, background): “For example, smoothing a nonsmooth convex objective function by convolution can improve the convergence rate of stochastic optimization algorithms [Duchi et al., 2012].”
A Comprehensive Linear Speedup Analysis for Asynchronous Stochastic Parallel Optimization from Zeroth-Order to First-Order (2016, critical): “[9] proved a O(N/K + 1/ √ K) rate for zeroth order SGD on convex objectives but with some very different assumptions compared to our paper.”
The Complexity of Large-scale Convex Programming under a Linear Optimization Oracle (2013, methodology): “…of D X , D Y and the target accuracy ǫ given in advance. c) If f is a general nonsmooth function satisfying (1.4), we show that the CndG method can achieve a nearly optimal complexity bound in terms of its dependence on ǫ after properly incorporating the randomized smoothing technique (e.g., [16]).”
Minimax Bounds on Stochastic Batched Convex Optimization (2018, background): “…has had wide-ranging influences, most saliently for us in the context of optimization, where a number of researchers, including Dekel et al. (2012), Duchi et al. (2012), and Niu et al. (2011), show how leveraging parallelism to compute many stochastic (sub)gradients of convex functions…”
Artificial Neural Variability for Deep Learning: On Overfitting, Noise Memorization, and Catastrophic Forgetting (2020, background): “Another related line of research is Randomized Smoothing (Duchi et al., 2012; Nesterov and Spokoiny, 2017).”
Mini-batch stochastic approximation methods for nonconvex stochastic composite optimization (2013, background): “, [9,11,27,29]) to explore the zeroth-order information of f .”
A Dual Approach for Optimal Algorithms in Distributed Optimization over Networks (2018, background): “Recently in [76], the authors extended the optimality lower bounds from [75] to the non-smooth case using the randomized regularization approach [21].”
Implicit Bias of Gradient Descent for Wide Two-layer Neural Networks Trained with the Logistic Loss (2020, unknown): “, Duchi et al. (2012)).”
Communication-efficient algorithms for statistical optimization (2012, unknown): “…papers Nedić and Ozdaglar (2009); Ram et al. (2010); Johansson et al. (2009); Duchi et al. (2012a); Dekel et al. (2012); Agarwal and Duchi (2011); Recht et al. (2011); Duchi et al. (2012b) and references therein contain a sample of relevant work—we touch on a few important themes here.”
Optimal Convergence Rates for Convex Distributed Optimization in Networks (2019, unknown): “We now show that the simple smoothing approach introduced by Duchi et al. (2012b) can lead to fast rates for error due to communication time.”
On stochastic proximal gradient algorithms (2014, background): “(12) As mentioned above, contrary to Duchi et al. (2012), the sampling distribution πθ depends on θ.”
On Perturbed Proximal Gradient Algorithms (2014, methodology): “ and a measurable function H: X ! , (;x) 7!H(;x), satisfying R ˇ (dx)kH(;x)k<1. When r‘() takes this integral form the optimization problem shares some similarities with the one considered in Duchi et al. (2012), In our setting however the distribution ˇ depends upon the parameter 2. This introd”