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:
- Non-convex Landscapes: Tianyi Lin and Michael Jordan established a link between uniform smoothing and "Goldstein subdifferentials," proving that smoothing allows algorithms to find stationary points even in non-smooth, non-convex environments like ReLU neural networks (Gradient-Free Methods for Deterministic and Stochastic Nonsmooth Nonconvex Optimization).
- Structured Directions: Marco Rando and Lorenzo Rosasco introduced O-ZD (Orthogonal Zeroth-order Descent), which uses sets of perpendicular random directions to estimate these smoothed gradients more efficiently than simple random sampling (An Optimal Structured Zeroth-order Algorithm for Non-smooth Optimization).
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.