Randomized Smoothing for Non-Smooth Optimization

This direction is split into other directions: randomized smoothing (differentiable surrogate approximation). Its last version stays readable and citable here.

Version 1 of 191 papers106 conceptsfrozen 2026-10-04

In traditional optimization, we rely on the gradient—the "slope" of a function—to tell us which way to move to reach a minimum. However, modern machine learning often encounters functions where gradients are either unavailable (black-box systems) or fundamentally broken (non-smooth functions with sharp "kinks" like ReLU activations or physical collisions).

Randomized smoothing provides a way to "blur" these jagged landscapes into smooth, differentiable surfaces. By evaluating the average behavior of a function in a small neighborhood, researchers can derive meaningful directions for optimization even when the original function is non-differentiable or entirely unknown.

The Intuition: Blurring the Kinks

Imagine trying to find the bottom of a jagged mountain range while wearing a blindfold. If you stand on a sharp peak, the "slope" at your exact position is undefined or misleading. However, if you could sense the average elevation of the ground within a few meters of you, you would gain a clear sense of which general direction leads downhill.

This is the core mechanism of randomized smoothing. As Alexander Gasnikov and colleagues explain in The power of first-order smooth optimization for black-box non-smooth problems, the technique replaces a non-smooth function $f(x)$ with a smoothed surrogate $f_\delta(x)$, defined as the expectation of the function over a small perturbation:

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

where $u$ is noise (often Gaussian or uniform) and $\delta$ is the smoothing parameter. This convolution "blurs" discontinuities and sharp corners, creating a differentiable landscape where standard gradient-based tools can operate.

Bridging the Zeroth-Order Gap

Randomized smoothing is particularly transformative for zeroth-order (gradient-free) optimization, where we can only query function values, not derivatives.

In Optimal rates for zero-order optimization: the power of two function evaluations, John Duchi and Michael I. Jordan demonstrate that by evaluating the function at two nearby perturbed points, one can estimate the gradient of the smoothed surrogate. This "two-point feedback" allows derivative-free methods to achieve convergence rates nearly as fast as those that have full access to gradients.

This approach has been extended to increasingly complex settings:

Smoothing in Physical and Distributed Systems

The utility of randomized smoothing extends beyond abstract mathematics into high-stakes engineering and privacy.

Robotics and Differentiable Physics

In robotics, physical interactions like friction and contact are inherently non-smooth—a robot is either touching a wall or it isn't. Louis Montaut and Antoine Bambade applied randomized smoothing to collision detection, allowing optimizers to "see" the curvature of sharp-edged objects (Differentiable Collision Detection: a Randomized Smoothing Approach). Similarly, Quentin Le Lidec developed Randomized Differential Dynamic Programming (RDDP) to enable gradient-based control through the "jagged" physics of contact and impact (Leveraging randomized smoothing for optimal control of nonsmooth dynamical systems).

Federated Learning and Privacy

In distributed environments, calculating exact gradients can be communication-heavy or violate privacy. Farzad Yousefian and Uday Shanbhag have pioneered zeroth-order federated learning frameworks. By using randomized smoothing, they allow decentralized agents to optimize non-smooth models (like those with ReLU activations) using only local function evaluations, maintaining both convergence and communication efficiency (Zeroth-Order Methods for Nondifferentiable, Nonconvex, and Hierarchical Federated Optimization).

Furthermore, smoothing acts as a natural partner to Differential Privacy. Andrew Lowy and Hilal Asi show that convolving loss functions with noise not only smooths the landscape but also helps satisfy privacy guarantees by ensuring that no single data point can radically alter the optimization trajectory (Faster Algorithms for User-Level Private Stochastic Convex Optimization).

Why It Works: The Statistical Advantage

The power of randomized smoothing lies in its ability to convert a local, potentially singular property (the gradient at a point) into a global, statistical property (the average change over a region).

As Yaron Singer demonstrates in the context of submodular optimization, smoothing prevents an optimizer from being misled by "adversarial noise" or local discontinuities by leveraging the statistical stability of the neighborhood (Submodular Optimization under Noise). Whether the challenge is a non-differentiable ReLU, a noisy black-box simulation, or a discrete combinatorial set, randomized smoothing provides the differentiable "bridge" necessary to apply the full power of modern optimization.

Papers in this version

Showing 60 of 91 papers.

History & citationVersion 1 · 2026-10-04

Split into other directions · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_randomized_smoothing_for_non_smooth_opti_6e281d67,
  title = {Randomized Smoothing for Non-Smooth Optimization},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/randomized-smoothing-for-non-smooth-optimization/rdr_6e281d67c68e435faa1bac1492777b13},
  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_for_non_smooth_opti_6e281d67_v1,
  title = {Randomized Smoothing for Non-Smooth Optimization},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/randomized-smoothing-for-non-smooth-optimization/rdr_6e281d67c68e435faa1bac1492777b13/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-20},
}