Imagine trying to find the lowest point in a rugged mountain range during a heavy fog. You cannot see the slope of the terrain (the gradient), and the ground is full of jagged rocks, sudden drops, and random bumps (non-smoothness and noise). All you can do is stand at a position, measure your current altitude, and poke around with a walking stick.
This is the core challenge of zeroth-order (derivative-free) optimization. In many real-world applications—such as hyperparameter tuning, reinforcement learning, and black-box adversarial attacks—we only have access to point evaluations $f(x)$ of an objective function, while explicit gradients $\nabla f(x)$ are either unavailable, too costly to compute, or completely undefined due to non-smoothness.
To navigate such landscapes, optimization algorithms must look past local irregularities to discern the underlying global trend. The foundational mechanism for achieving this is Gaussian smoothing: transforming a jagged, noisy, or non-differentiable function into a smooth, well-behaved surrogate by averaging its values over a local neighborhood.
The Core Intuition: Shifting the Derivative
Mathematically, the Gaussian-smoothed surrogate $f_\mu(x)$ is defined as the convolution of the original function $f(x)$ with a Gaussian probability density function $p_\mu(u) = \mathcal{N}(0, \mu^2 I)$:
$$f_\mu(x) = \mathbb{E}_{u \sim \mathcal{N}(0, I)} [f(x + \mu u)]$$
Here, $\mu$ represents the smoothing radius. If $\mu$ is small, $f_\mu$ closely tracks the original function; if $\mu$ is large, it filters out high-frequency noise and local irregularities.
The remarkable property of Gaussian smoothing is that the gradient of the smoothed function can be computed exactly using only evaluations of the original function. By changing variables, we can shift the derivative operator away from the unknown, potentially non-differentiable function $f$ and directly onto the well-behaved Gaussian density function. This yields the fundamental identity:
$$\nabla f_\mu(x) = \frac{1}{\mu} \mathbb{E}_{u \sim \mathcal{N}(0, I)} [f(x + \mu u) u]$$
This identity provides the core mechanism for zeroth-order gradient estimation. By perturbing the current point $x$ with random Gaussian noise $u$, evaluating the black-box function at this new point, and scaling the result by the direction of the perturbation, we obtain an unbiased estimate of the gradient of the smoothed surrogate.
As emphasized by Wang et al. and Bai et al., this simple randomized sampling allows algorithms to mimic standard gradient descent on black-box functions without ever computing an analytical derivative.
Taming Non-Smoothness and Weak Convexity
Why optimize the smoothed surrogate $f_\mu$ instead of the original function $f$? Because convolution with a Gaussian kernel acts as a mathematical iron, smoothing out sharp corners and discontinuities. Even if $f$ is non-differentiable, $f_\mu$ becomes infinitely differentiable.
This property bridges the gap between derivative-free optimization and classical gradient-based theory across several challenging domains:
- Weak Convexity: Pougkakiotis et al. utilize Gaussian smoothing to approximate non-smooth, weakly convex functions with smooth surrogates, enabling the application of proximal stochastic gradient methods to black-box problems.
- Noisy Landscapes: Shibaev et al. show that local neighborhood averaging allows derivative-free methods to optimize noisy Hölder-gradient functions, forcing jagged objectives to behave like smooth ones during optimization.
- Complex Boundaries: Lei et al. extend this paradigm to subdifferentially polynomially bounded functions, proving that adaptive stepsizes can minimize non-Lipschitz and non-smooth functions common in deep neural networks.
- Adversarial Min-Max Problems: In game-theoretic and robust optimization settings, Farzin et al. employ a two-point Gaussian smoothing estimator to solve non-smooth submodular-concave min-max problems, showing that classical smoothing can provide robust convergence guarantees where deep learning methods struggle.
Beyond First-Order: Hessians and Hierarchies
The utility of Gaussian smoothing extends beyond estimating first-order gradients. By applying generalized versions of Stein's identity, researchers can extract second-order (Hessian) geometric information from point evaluations alone.
In Bandit Convex Optimization (BCO), where an agent only observes a single noisy loss value at each step, understanding the local curvature is essential for fast convergence. Lattimore et al. and Fokkema et al. leverage Gaussian perturbations to approximate both gradient and Hessian information, successfully extending second-order methods like the Online Newton Step to the bandit framework.
[Point Evaluations f(x)] ──> [Gaussian Perturbations] ──> [Stein's Identity] ──> [Estimated Gradients & Hessians]
This capability is particularly valuable for hierarchical and multi-objective optimization problems:
- Bilevel Optimization: In bilevel problems, an outer "hyperobjective" depends on the optimal solution of an inner optimization problem. Computing gradients through this nested structure is notoriously difficult and frequently non-smooth. Aghasi et al. introduce a fully zeroth-order bilevel programming framework by convolving the objectives with a Gaussian distribution, transforming noisy function evaluations into unbiased first- and second-order derivative estimates. Similarly, van Leeuwen applies derivative-free stochastic bilevel optimization to inverse problems, automatically learning regularization parameters without explicit hypergradients.
- Multi-Objective Learning: Ye et al. transform black-box multi-objective functions into smooth, differentiable surrogates, enabling adaptive gradient aggregation across conflicting goals. In a similar vein, the authors of The Max-Min Formulation of Multi-Objective Reinforcement Learning: From Theory to a Model-Free Algorithm employ Gaussian smoothing to estimate objective weight gradients when a closed-form gradient is unavailable.
Mitigating the Curse of Dimensionality
Despite its elegance, standard $d$-dimensional Gaussian smoothing faces a significant challenge: as the dimensionality $d$ increases, the variance of the gradient estimator scales poorly. This occurs because random perturbation vectors in high-dimensional spaces tend to become mutually orthogonal, making isotropic sampling inefficient.
To address this limitation, researchers have developed several specialized variations:
- Directional Gaussian Smoothing (DGS): Instead of sampling across the entire $d$-dimensional space simultaneously, Zhang et al. propose computing a DGS gradient by performing 1D Gaussian smoothing along a set of orthogonal directions. This approach is computationally cheaper and significantly more robust to high-frequency noise.
- Implicit Regularization: Balasubramanian et al. demonstrate that standard zeroth-order gradient descent via Gaussian smoothing can automatically adapt to high-dimensional sparse problems, exploiting an implicit regularization effect that allows the algorithm to perform well when the underlying true structure is low-dimensional.
- Parallel Acceleration: Jambulapati et al. leverage a stability property of Gaussian convolutions to transform non-smooth convex functions into twice-differentiable forms, closing the theoretical gap between computational depth and query depth in parallel stochastic optimization.
Alternative Statistical Perspectives
While explicit convolution via random perturbation is the dominant approach, the broader concept of Gaussian smoothing can also be framed through a purely statistical lens.
Instead of actively perturbing a function to estimate its local behavior, one can use data points to fit a probabilistic model of the landscape. Calderhead et al. demonstrate this by using Gaussian Processes (GPs) to estimate state variables and their derivatives simultaneously. This statistical approach provides an alternative framework for managing noise and uncertainty in gradient estimates, offering robustness against multimodal likelihood surfaces.
Finally, when dealing with highly non-convex landscapes containing severe noise, local smoothing can be paired with global exploration. Mangoubi et al. combine Gaussian kernel smoothing with Simulated Annealing and Stochastic Gradient Langevin Dynamics (SGLD), demonstrating that smoothing allows algorithms to find global minima even when the background noise scales proportionally with the function's value.
Key Foundational Work
Convex Optimization with Unbounded Nonconvex Oracles using Simulated Annealing (2018) — contributed 1 concept elements to this direction.
Zeroth-order (Non)-Convex Stochastic Optimization via Conditional Gradient and Gradient Updates (2018) — contributed 1 concept elements to this direction.
Accelerating Bayesian Inference over Nonlinear Differential Equations with Gaussian Processes (2008) — contributed 1 concept elements to this direction.