Randomized Smoothing for Zeroth Order Optimization

This direction is merged into another direction: black-box optimization. Its last version stays readable and citable here.

Version 1 of 131 papers33 conceptsfrozen 2026-10-04

In modern machine learning, we often treat systems as "black boxes." Whether we are tuning the hyperparameters of a complex pipeline, attacking a neural network where we don't have access to the weights, or performing reinforcement learning in a simulator, we frequently encounter a fundamental problem: we can see the output of a function, but we cannot calculate its gradient.

This is the domain of Zeroth-Order (ZO) Optimization. While traditional optimization relies on the "slope" (gradient) to find the minimum, ZO methods must navigate the landscape using only point evaluations. The most powerful tool for making this possible is Randomized Smoothing.

The Intuition: Blurring the Landscape

Imagine trying to find the lowest point in a dark, jagged mountain range using only a GPS that tells you your current altitude. If the terrain is "non-smooth"—full of sharp cliffs and tiny cracks—a single step in any direction might give you a misleading idea of where the valley lies. You might get stuck in a tiny pothole, thinking it's the global minimum.

Randomized smoothing solves this by "blurring" the map. Instead of looking at the altitude at exactly one point, you look at the average altitude in a small neighborhood around you. As Ming Lei, Ting Kei Pong, and Shuqin Sun describe in Subdifferentially polynomially bounded functions and Gaussian smoothing-based zeroth-order optimization, this process (mathematically a convolution with a Gaussian kernel) transforms a jagged, non-differentiable function into a smooth, differentiable surrogate.

By optimizing this "blurred" version of the function, you can ignore high-frequency noise and local irregularities, allowing gradient-based logic to operate even on surfaces that technically have no derivatives.

How to Estimate a Gradient Without Derivatives

The core mechanism of these algorithms is the Randomized Gradient Estimator. To estimate which way is "down" without a formula for the gradient, you sample the function at points perturbed by random noise.

The most common approach is the two-point estimator. As explained by Aleksandr Lobanov and Alexander Gasnikov in Gradient-Free Federated Learning Methods with $l_1$ and $l_2$-Randomization for Non-Smooth Convex Stochastic Optimization Problems, you pick a random direction $u$ (often from a Gaussian or spherical distribution) and a small step size $\mu$. You then evaluate the function at $x + \mu u$ and $x - \mu u$.

The difference between these two values, multiplied by the direction vector $u$, provides an unbiased estimate of the gradient of the smoothed function. This allows you to use standard tools like Stochastic Gradient Descent (SGD) or Mirror Descent in a completely derivative-free setting.

Taming the Triple Threat: Non-smooth, Non-convex, and Noisy

The real power of randomized smoothing appears when dealing with what Luke Marrinan, Uday Shanbhag, and Farzad Yousefian call the "triple threat": functions that are simultaneously non-smooth, non-convex, and stochastic.

  1. Non-smoothness: In Zeroth-Order Methods for Constrained Nonconvex Nonsmooth Stochastic Optimization, Zhuanghua Liu and Bryan Kian Hsiang Low show that smoothing allows us to define "approximate stationarity" for functions where a traditional gradient doesn't even exist (like ReLU networks).
  2. Non-convexity: One of the biggest fears in optimization is getting stuck at a saddle point. Qinbo Bai and Vaneet Aggarwal demonstrate in Escaping Saddle Points for Zeroth-order Nonconvex Optimization using Estimated Gradient Descent that the random perturbations used for smoothing actually help the algorithm "shake" itself out of saddle points, reaching second-order stationary points that first-order methods might miss.
  3. Noise: When function evaluations are corrupted by noise, the variance of the gradient estimate can explode. Researchers like Liu Liu and Cho-Jui Hsieh have integrated Variance Reduction techniques (like SVRG) into the zeroth-order framework to break the "curse of dimensionality" and ensure stable convergence even in high-dimensional spaces Stochastic Zeroth-order Optimization via Variance Reduction method.

Applications Across the Spectrum

Because it requires so little information about the underlying system, this approach is remarkably versatile:

By embracing the randomness of the neighborhood, these methods turn the "blindness" of black-box optimization into a structured, provable search for the optimum.

Papers in this version

History & citationVersion 1 · 2026-10-04

Merged into another direction · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_randomized_smoothing_for_zeroth_order_op_b1be7ee2,
  title = {Randomized Smoothing for Zeroth Order Optimization},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/randomized-smoothing-for-zeroth-order-optimization/rdr_b1be7ee2fc914ac2a499e368608fd8f2},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-19},
}

This exact version (version 1, frozen text):

@misc{lacuna_randomized_smoothing_for_zeroth_order_op_b1be7ee2_v1,
  title = {Randomized Smoothing for Zeroth Order Optimization},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/randomized-smoothing-for-zeroth-order-optimization/rdr_b1be7ee2fc914ac2a499e368608fd8f2/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-19},
}