Randomized Smoothing for Stochastic Optimization

John C. Duchi; Peter L. Bartlett; Martin J. Wainwright

Source-linked AI summary

Randomized Smoothing for Stochastic Optimization

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

arXiv:1103.4296v2Mar 22, 2011math.OCstat.ML

TL;DR

Non-smooth stochastic optimization lacks convergence rates that improve with reduced gradient-estimator variance. The paper combines randomized smoothing with accelerated gradient methods and obtains optimal variance dependence in expectation and with high probability, while demonstrating applications to statistical estimation and distributed optimization.

Problem
Non-smooth stochastic optimization procedures lacked variance-based convergence rates, despite multiple oracle samples reducing gradient-estimator variance.
Method
The paper smooths the non-smooth objective through random perturbations and applies accelerated gradient methods to stochastic gradients of the smoothed function.
Results
O(RL0/Tm) convergence is achieved in expectation and with high probability, and the paper reports optimal dependence on gradient-estimator variance.
Takeaways & Limitations
The methods provide provably optimal stochastic-oracle complexity and applications to statistical estimation and distributed optimization.
Takeaways & Limitations
Whether randomized smoothing is necessary for optimal convergence rates remains unresolved, with experiments suggesting that smoothing improves over repeated sampling alone.

Abstract

from arXiv · show

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.

1 Introduction

The paper develops randomized smoothing procedures for non-smooth stochastic convex optimization, using stochastic gradients of a smoothed objective. It establishes variance-sensitive convergence rates in expectation and with high probability, with applications to statistical and distributed optimization.

Problem formulation: The paper extends the framework to stochastic problems with a convex, possibly non-differentiable regularizer, including the ℓ1-norm and related regularizers.The regularizer is assumed closed and convex, while the objective remains convex on its domain.
Motivation: The paper studies stochastic optimization when the convex objective may be non-smooth and cannot be directly evaluated, leaving access only to stochastic function and subgradient realizations.These difficulties arise because the defining expectation may be computationally intractable or the distribution over instances may be unknown.
Method: Randomized smoothing convolves the objective with a density-induced perturbation, producing a differentiable function while preserving convexity.The smoothed objective is formed by taking an expectation over randomly perturbed points.
Method: The algorithm combines stochastic gradients of the smoothed objective with accelerated gradient methods to address the lack of variance dependence in standard non-smooth rates.Accelerated methods require Lipschitz-continuous gradients, motivating the smoothing step.
Results: m stochastic-oracle queries per iteration achieve convergence rate O(RL0/Tm) in expectation and with high probability.Here L0 is the Lipschitz constant of f and R is the ℓ2-radius of the domain; the rate is optimal up to constant factors.
Applications: The results support applications in statistical estimation and distributed optimization, including an order-optimal distributed stochastic optimization algorithm.The distributed connection combines the proposed algorithm with recent decentralized optimization work.

2 Main results and some consequences

The paper combines randomized smoothing with accelerated dual averaging to obtain variance-sensitive convergence guarantees for non-smooth stochastic optimization. The resulting expected and high-probability rates are supported by optimality arguments and several geometry- and application-dependent consequences.

2.2 Description of algorithm: The accelerated procedure uses varying smoothness parameters Lt and a damping term ηt/θt to control stochastic fluctuations without requiring the iteration horizon T in advance.The algorithm evolves three sequences, and varying Lt makes the smoothing scheme oblivious to the number of iterations.
2.1 Some background: Randomized smoothing makes the non-smooth objective sufficiently smooth for accelerated gradient methods while preserving a controlled approximation to the original objective.The smoothing distributions include Gaussian and uniform distributions on norm balls, under assumptions ensuring smoothness and uniform closeness.
2.3 Convergence rates: Theorem 1 gives an expected convergence rate that explicitly depends on the gradient-estimation variance, while Theorem 2 gives a corresponding high-probability guarantee under an additional tail condition.The expected theorem does not require prior knowledge of T; the high-probability theorem assumes compactness and Assumption B.
2.3 Convergence rates: The method achieves an O(RL0/√(Tm)) convergence rate in expectation and with high probability when m stochastic subgradients are queried at each iteration.The rate is stated as optimal up to constant factors, and the high-probability bound contains the same leading terms as the expected rate.
2.4 Some consequences: Uniform and Gaussian smoothing yield concrete geometry-dependent corollaries, while ℓ∞ smoothing offers easier sampling in high-dimensional or sparse settings at somewhat looser rates.Gaussian smoothing avoids normalization but imposes more stringent requirements on f; ℓ∞ smoothing is especially convenient for sparse data scenarios such as NLP.

3 Applications and experimental results

The applications and experiments show how randomized smoothing supports parallel, distributed, and computationally expensive stochastic optimization, while experiments validate its predicted scaling and practical benefits. Across regression, metric learning, and nonsmooth comparisons, increasing the sample count helps most in the low-sample regime, and smoothing becomes especially advantageous as m grows.

3.1 Some applications: Parallel oracle queries preserve the benefit of variance reduction while allowing optimization error O(1/(mε^2)) in the distributed adaptation.The distributed implementation can process m queries concurrently, with tree aggregation requiring O(log m) steps.
3.1 Some applications: For metric learning, randomized smoothing achieves optimization error O(1/(Tm)) after Tmd^2 + Td^3 computation, versus Tmd^3 for standard stochastic gradient.When m ≈ d, the randomized method uses a factor O(d) less computation.
3.2.1 Iteration Complexity of Reduced Variance Estimators: The predicted two-regime scaling gives T(ε,m) = O(L0^2R^2/(mε^2)) for small m and T(ε,m) = O(L0Rd^1/4/ε) for large m.The first regime is variance-dominated, whereas the second is governed by the dimension-dependent term.
3.2.3 Necessity of randomized smoothing: In the nonsmooth comparison, smoothing and simple mirror descent are essentially indistinguishable at m = 1, but smoothing has much better iteration complexity as m grows.The nonsmoothed method improves moderately with more samples, while the smoothed strategy benefits substantially.

4 Proofs

The proofs establish convergence by combining smoothness and approximation properties of randomized convolutions with variance control from averaged stochastic gradients. They handle both changing and fixed smoothing parameters, yielding expected and high-probability guarantees under the stated assumptions.

Proof strategy: The proof framework first shows that randomized smoothing produces smooth functions uniformly close to the original nonsmooth objective, then applies accelerated convergence theorems.The smoothed objectives form a decreasing sequence when the smoothing scale decreases.
Proof strategy: Averaging m stochastic gradient samples reduces the estimator variance at approximately rate 1/m, which is incorporated through suitable step sizes.The corollary proofs combine variance bounds with smoothness estimates for the chosen smoothing distributions.
Corollaries: For uniform ℓ2-ball smoothing, the proofs use a gradient Lipschitz constant proportional to L0d/u and select u = Rd^1/4.These choices connect the smoothing bias and stochastic-estimation variance to the resulting convergence bounds.
Theorem 3: The fixed-smoothing analysis sets ut ≡ u and Lt ≡ L1/u, while choosing u proportional to 1/T gives rates identical to the decreasing-smoothing theorem up to constants.Theorem 3 provides an alternative parameter setting when the iteration horizon is known in advance.
High-probability bounds: High-probability convergence is obtained by controlling the squared error sequence and applying concentration under Assumption B.The proof introduces auxiliary lemmas for the relevant error terms before deriving the probability bound.

5 Discussion

The paper develops smoothing strategies for stochastic non-smooth optimization and reports optimal stochastic-oracle complexity, applications, and experiments. It identifies open questions about the necessity and dimension dependence of randomized smoothing.

The methods are provably optimal in the stochastic oracle model of optimization complexity.
The paper presents, to the authors’ knowledge, the first variance reduction techniques for non-smooth stochastic optimization.
Applications show provable improvement from smoothing over standard methods, while experiments qualitatively agree with the theoretical predictions.
Open questions concern whether randomized smoothing is necessary for optimal convergence rates and whether dimension-independent smoothing is possible.The paper states that its chosen smoothing distributions have tight dimension dependence.

A Proof of Lemma 1

The proof combines concentration results for sub-Gaussian and sub-exponential random variables with variance control for averaged stochastic estimates. Jensen’s inequality and parameter substitution complete the argument.

The proof collects auxiliary results on sub-Gaussian and sub-exponential random variables in Appendix F.
Conditioned on F_t−1, the variables X_i are independent, enabling application of an appendix concentration lemma after setting L = 2L_0.
Averaging m estimates yields a sub-Gaussian parameter at most 4L^2/m for the relevant quantity.
The proof weakens the sub-Gaussian parameter using a maximum involving an expectation term, then applies Jensen’s inequality.
Replacing L with 2L_0 completes the proof.

B Proof of Lemma 2

The proof establishes an upper bound for the accelerated smoothed objective by combining linearization, smoothness, convexity, strong convexity, and Fenchel–Young arguments. It then incorporates the stochastic gradient error into the recursion.

The proof defines the linearized cumulative objective and introduces φ_t(x) = f_μt(x) + ϕ(x).
The indicator function of X initializes ℓ_−1, while z_t+1 is constructed as a minimizer of a regularized objective.
Smoothness, convexity, and strong convexity provide the inequalities used to derive the upper bound on φ_t(x_t+1).
The proof rewrites the bound using the gradient error e_t = ∇f_μt(y_t) − g_t and retains its inner-product contribution.
Adding ℓ_t(z_t+1), substituting x = z_t+1, and combining inequalities yields the lemma’s conclusion through successive applications and Fenchel–Young inequality.

C Proof of Lemma 4

The proof treats the accumulated stochastic error as a martingale difference sequence and controls it using bounded domain radius, conditional sub-Gaussianity, and Azuma–Hoeffding concentration.

Conditionally unbiased gradient error makes θ_t⟨e_t, z_t − x*⟩ a martingale difference sequence.
Compactness of X and the bound ∥z_t − x*∥ ≤ R control the error inner product by ∥e_t∥*R.
Setting c_t = Rσ/θ_t yields conditional sub-Gaussian control for the scaled error term.
Azuma–Hoeffding concentration bounds the accumulated martingale error.
The proof uses θ_T−1 ≤ θ_t for t < T and selects δ = exp(−3Tε^2...) to obtain the stated claim.

D Proof of Lemma 5

The proof establishes concentration bounds for quantities built from stochastic gradient errors by combining sub-exponential tail control with parameter inversion across deviation regimes.

The proof first establishes an intermediate bound for λ ≤ η_t/2σ^2 before applying it to control ∥e_t∥^2.
The resulting variables X_t inherit sub-exponential parameters Λ_t = η_t/2σ^2, with the smallest parameter attained at t = 0.
The first claim in Lemma 5 follows from applying a standard concentration theorem to these sub-exponential variables.
The second claim is obtained by inverting the exponential bounds separately in different ε regimes and taking the largest resulting bound.
The centered squared error X^2 − E[X^2] is sub-exponential with parameters Λ ≥ σ^2 and τ^2 ≤ 32eσ^4.

E.1 Statements of smoothing lemmas

The smoothing lemmas show that randomized convolution makes the expected objective differentiable, approximates the original function, and yields Lipschitz gradients under several sampling distributions and norm assumptions.

Uniform ℓ∞ smoothing: For uniform smoothing on an ℓ∞-ball, f ≤ f_μ ≤ f + L_0u and f_μ is L_0-Lipschitz.
Uniform ℓ∞ smoothing: Under uniform ℓ∞ smoothing, f_μ is continuously differentiable and its gradient is Lipschitz, while stochastic gradients are unbiased for ∇f_μ.
Sharpness: The ℓ∞ smoothing bounds, including the gradient-variance estimate, are simultaneously tight up to constant factors.
Gaussian smoothing: For Gaussian smoothing of ℓ2-Lipschitz functions, the gradient is Lipschitz with dimension-dependent scaling, and the stated bounds are likewise unimprovable up to constants.
Sharpness: The paper states that the approximation-versus-gradient-smoothness tradeoff for uniform and Gaussian smoothing cannot be improved beyond constant factors.

E.2 Proof of smoothing lemmas

This section introduces a technical lemma that bounds changes in expected subgradients under smoothing and identifies conditions under which the bound is tight.

Lemma 11 applies to convex L_0-Lipschitz functions smoothed by an arbitrary distribution over the relevant domain.
For rotationally symmetric, radially non-increasing smoothing in the ℓ2 norm, the bound is attained by a specific function.

E.2.1 Proof of Lemma 6

The proofs derive the smoothing lemmas using convexity, Jensen’s inequality, measure comparisons, and explicit examples that establish tightness of the resulting bounds.

Jensen’s inequality gives the lower bound f(x) ≤ f_μ(x), while Lipschitz continuity supplies the corresponding uniform approximation upper bound.
For uniform ℓ∞ smoothing, f_μ is shown to be L_0-Lipschitz, with tightness demonstrated using the separable shifted-Huber representation of ∥x∥_1.
Differentiability follows from averaging almost-everywhere gradients, and Lipschitz continuity of ∇f_μ is established through geometric control of symmetric differences between shifted supports.
Tightness examples include f(x)=∥x∥_1, f(x)=L_0|x|, and linear functions, showing that the Lipschitz and variance estimates cannot generally be improved.
The smoothed stochastic gradient is unbiased, and its variance bound follows from the triangle inequality and the underlying assumptions.
For Gaussian smoothing, rotational invariance reduces the relevant projection to a one-dimensional normal variable, enabling the dimension-dependent gradient bound.
The sharpness construction combines difficult convex functions and uses subgradient choices aligned with regions where the smoothing densities differ.

F.1 Sub-Gaussian variables

This section defines sub-Gaussian variables through a moment-generating-function bound and develops concentration tools for bounded sums and martingales. It also introduces sub-exponential variables and records related characterizations and implications.

A zero-mean variable is sub-Gaussian with parameter σ2 when E exp(λX) ≤ exp(σ2λ2/2) for every real λ.
Independent sub-Gaussian variables retain sub-Gaussian concentration under averaging, while bounded zero-mean variables have parameter at most C2.
Sub-Gaussian coordinates yield logarithmic growth of the expected maximum with dimension, using union bounds and Chernoff’s inequality.
The section uses Azuma-Hoeffding and related martingale techniques to control deviations of sums with conditionally sub-Gaussian increments.
For independent random vectors bounded by L, a Doob martingale controls ∥Sn∥−E∥Sn∥, producing a sub-Gaussian parameter at most 4nL2.The proof bounds each martingale difference by 2L and applies conditional sub-Gaussianity.