Randomized Smoothing for Non-Smooth Optimization

47 concepts40 papers

The Challenge of Jagged Landscapes

Imagine trying to find the lowest point in a mountain range, but the terrain is fractured by sharp cliffs, sudden drops, and jagged ridges. Standard gradient descent relies on the terrain being smooth; it looks at the slope directly beneath its feet and takes a step in the steepest downward direction.

However, modern machine learning and optimization landscapes are frequently non-smooth. They are filled with "kinks" introduced by ReLU activations ($max(0, x)$), absolute values from $L_1$ regularization, or sharp boundaries from hinge losses. At these points, the gradient is discontinuous or entirely undefined.

The problem intensifies in black-box (zeroth-order) optimization, where we can only query a function's value but have no direct access to its derivatives. On a jagged landscape, a tiny step forward might hit a sudden spike, rendering local finite-difference approximations highly unstable or misleading.

The Core Mechanism: Blurring the Terrain

To navigate a jagged landscape, we can mathematically "blur" it. Instead of evaluating the non-smooth objective function $f(x)$ at an exact coordinate, we evaluate its average behavior over a local neighborhood. This technique is known as randomized smoothing.

Mathematically, we define a smooth surrogate function $f_\delta(x)$ by taking the expectation of $f$ over a random perturbation:

$$f_\delta(x) = \mathbb{E}_{u \sim \mathcal{D}}[f(x + \delta u)]$$

Here, $u$ is a random noise vector drawn from a continuous probability distribution $\mathcal{D}$ (such as a standard Gaussian or a uniform distribution over a unit ball), and $\delta$ is a smoothing parameter that dictates the radius of the neighborhood.

As John C. Duchi et al. demonstrated, convolving a non-smooth function with a continuous probability density function acts as a low-pass filter. It shaves off the sharp peaks and fills in the jagged valleys, transforming a problematic landscape into a well-behaved, differentiable surface. Crucially, the gradient of this surrogate function exists everywhere—even if the underlying function $f(x)$ has discontinuities.

Why It Works: Turning Noise into Gradients

The elegance of randomized smoothing lies in a fundamental property of calculus: the derivative of an expectation can often be transferred directly to the underlying probability density function. This means we can compute or estimate the gradient of the smooth surrogate $f_\delta(x)$ using only evaluations of the original, non-smooth function.

For example, when using a uniform distribution over a local neighborhood, the gradient of the surrogate function corresponds to an average of the function's values across that local space. Tianyi Lin et al. leverage this property to construct gradient-free optimization methods for non-smooth, non-convex functions. By averaging function values over a local unit ball, their approach creates a smooth landscape that rigorously maps back to the original function's properties via Goldstein subdifferentials. Similarly, Francesco Rinaldi utilizes Gaussian perturbations to optimize stochastic weakly convex functions, proving that derivative-free methods can achieve convergence rates comparable to traditional gradient-based algorithms by navigating this smoothed surrogate.

When optimization occurs within a restricted domain, global perturbations might push the parameters outside the feasible region. To resolve this, Angelia Nedic et al. introduced localized uniform randomized smoothing. By confining the uniform noise to a tight, bounded neighborhood, the authors ensure that the surrogate remains valid and computable within strict domain constraints.

Applications Across the Optimization Landscape

Because randomized smoothing provides a reliable bridge between non-smooth landscapes and gradient-based algorithms, it has become a foundational tool across several distinct domains:

Differential Privacy

In private optimization, injecting noise is mandatory to prevent individual data points from leaking. Randomized smoothing offers a powerful synergy here. As Qinzi Zhang et al. and Giorgio Micali et al. demonstrate, the exact same random perturbations used to smooth out jagged objectives can simultaneously serve as the privacy-preserving noise mechanism required for Differential Privacy (DP). This dual-purpose noise allows practitioners to deploy sophisticated first-order optimization techniques on complex, private objectives without paying a double penalty for smoothing and privacy separately.

Discrete and Structured Prediction

Discrete operations, such as an argmax step or a 0/1 loss function, are notoriously difficult to optimize because their gradients are zero almost everywhere and infinite at transition boundaries. Andrew Cotter et al. show that adding uniform noise to a classification rule converts a discrete 0/1 loss into a smooth, convex surrogate. For complex structured predictors, Hedda Cohen Indelman et al. apply random perturbations directly to the underlying scoring functions. This guarantees the existence of a unique maximizer almost surely, transforming rigid, non-smooth discrete operations into continuous, differentiable surfaces that can be trained directly via backpropagation.

Automatic Differentiation

When standard automatic differentiation (AD) libraries encounter non-smooth operations like ReLUs or absolute values, they often make arbitrary local choices at the "kinks," which can lead to mathematically incorrect subgradients. Jason D. Lee et al. resolve this by introducing a randomized direction vector during the differentiation process. This controlled randomization forces the AD system to consistently select a single execution branch, ensuring that the resulting derivative is almost surely a valid element of the Clarke subdifferential.

Physical Dynamics

Non-smoothness is not unique to loss functions; it also appears in physical simulations. In robotics, contact dynamics (such as a foot striking the ground or a gripper grabbing an object) create severe discontinuities in the physics landscape. Tao Pang applies randomized dynamics smoothing to average a system's behavior over a local neighborhood. This smooths out the hard boundaries of physical impact, allowing standard gradient-based trajectory optimizers to successfully guide robots through complex manipulation tasks.

Key Foundational Work

On Stochastic Gradient and Subgradient Methods with Adaptive Steplength Sequences (2011) — contributed 2 concept elements to this direction.
Randomized Smoothing for Stochastic Optimization (2012) — contributed 1 concept elements to this direction.
History & citationVersion 1 · 2026-10-04

Current · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_randomized_smoothing_differentiable_surr_7cd5ea55,
  title = {randomized smoothing (differentiable surrogate approximation)},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/randomized-smoothing-differentiable-surrogate-approximation/rdr_7cd5ea5556034147bc5c606d8593a001},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-20},
}

This exact version (version 1, frozen text):

@misc{lacuna_randomized_smoothing_differentiable_surr_7cd5ea55_v1,
  title = {randomized smoothing (differentiable surrogate approximation)},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/randomized-smoothing-differentiable-surrogate-approximation/rdr_7cd5ea5556034147bc5c606d8593a001/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-20},
}

See something wrong? Report a mistake