The Dimensionality Penalty in Randomized Smoothing

18 concepts14 papers1 proposal

Optimization algorithms thrive on smoothness. When an objective function is smooth—meaning its gradients change continuously without sudden jumps—algorithms can reliably follow the gradient downhill to find a minimum. However, many real-world machine learning objectives are non-smooth, featuring sharp kinks, crevices, or high-frequency noise.

To tackle these rugged landscapes, a common strategy is randomized smoothing. The core idea is simple: instead of optimizing the jagged function $f(x)$ directly, we optimize a blurred version of it, $\hat{f}(x) = \mathbb{E}_{u}[f(x + u)]$, where $u$ is random noise drawn from a simple distribution like a Gaussian or a uniform ball. By averaging out the local bumps, we get a well-behaved, differentiable surrogate.

But this elegant trick hits a mathematical wall when applied to modern, high-dimensional problems. As the number of dimensions $d$ grows, the geometric properties of the smoothing distribution change drastically, forcing a severe trade-off: either the smoothed function loses too much detail, or its smoothness properties degrade rapidly. This phenomenon is known as the dimension-dependent scaling bottleneck of randomized smoothing.


The Geometry of the Penalty: Why $\sqrt{d}$ Emerges

To understand why smoothing fails in high dimensions, we must look at the geometry of high-dimensional space.

Imagine smoothing a function using uniform noise inside a sphere of radius $\sigma$. In a 1-dimensional space, a step of size $\sigma$ moves you a distance of exactly $\sigma$. But in a $d$-dimensional space, if you perturb each coordinate independently by a small amount, the total Euclidean distance from the center scales as $\sigma \sqrt{d}$.

When we compute the gradient of a smoothed function, we are mathematically evaluating how the average value of $f(x)$ shifts as we move the smoothing window. By applying integration by parts, the gradient of the smoothed function can be expressed as an expectation over the boundary of the smoothing distribution:

$$\nabla \hat{f}(x) = \mathbb{E} [f(x+u) \cdot \delta(u)]$$

where $\delta(u)$ depends on the geometry and derivative of the noise density. In high dimensions, because the volume of a sphere or Gaussian concentrates heavily along its outer shell at a distance proportional to $\sqrt{d}$, the sensitivity of this expectation to small shifts in $x$ scales up by a factor of $\sqrt{d}$.

Consequently, if the original function is $L$-Lipschitz, the Lipschitz constant of the gradient of the smoothed function (which dictates how fast the gradient changes) necessarily scales as:

$$L_{\text{smooth}} \approx \frac{L \sqrt{d}}{\sigma}$$

Early foundational work by Nedic et al. and Duchi et al. identified this exact $\sqrt{d}$ penalty. It creates a fundamental conflict: to make the function highly smooth (small $L_{\text{smooth}}$), you must choose a large noise radius $\sigma$. But a large $\sigma$ means you are averaging over a massive volume, which introduces a huge approximation error between your smoothed surrogate $\hat{f}(x)$ and the true objective $f(x)$.


An Inescapable Mathematical Reality

For a long time, researchers wondered if this $\sqrt{d}$ degradation was simply a limitation of using naive noise distributions like Gaussians or uniform hypercubes. Could a more sophisticated, dimension-independent smoothing distribution exist?

Kornowski et al. answered this definitively by proving that the dimension-dependent penalty is an inescapable property of any computationally efficient local smoothing technique. They demonstrated that any polynomial-time algorithm approximating a non-smooth function faces a fundamental trade-off where the smoothness parameter must degrade with $\sqrt{d}$. This implies that standard randomized smoothing is nearly optimal; the penalty is baked into the nature of high-dimensional space itself.

This fundamental limit ripples across several domains:

  • Optimization Lower Bounds: When proving the absolute "speed limits" of optimization algorithms, researchers construct worst-case functions. Bai et al. showed that the smoothing techniques required to build these functions inevitably inject unwanted dimension-dependent artifacts, complicating the derivation of pure, dimension-free oracle complexities.
  • Parallel Optimization: In parallel and distributed settings, algorithms often rely on $L_2$ norm bounds for smoothing to distribute work. As Chakrabarty et al. noted, these $L_2$ bounds cause the approximation error to explode in high dimensions, forcing parallel algorithms to take a high number of sequential iterations to maintain accuracy, defeating the purpose of parallelization.
  • Inexact Oracles: When algorithms only have access to noisy or inexact gradients, applying randomized smoothing to stabilize the algorithm introduces error terms that scale with $\sqrt{d}$, limiting practical efficiency on massive datasets as shown by Kerger et al..

How the Penalty Sabotages Convergence

In practical optimization, the degradation of the smoothness parameter directly translates to slower convergence. Most gradient-based optimizers dictate that the maximum stable step size (learning rate) is inversely proportional to the smoothness constant ($1/L_{\text{smooth}}$). Because $L_{\text{smooth}}$ inflates by $\sqrt{d}$, the algorithm is forced to take tiny steps, dragging down convergence rates.

This issue becomes even more pronounced in zero-order (gradient-free) and stochastic settings. As Kornowski et al. argued, standard analyses often let this $\sqrt{d}$ factor propagate carelessly through optimization bounds, leading to highly pessimistic and suboptimal complexity results (such as $O(d^{3/2})$ instead of the true optimal $O(d)$).

Beyond step sizes, the penalty causes a structural failure in multimodal optimization. If an objective function has many local minima, we want a large smoothing radius $\sigma$ to "skip" over the high-frequency ripples and capture the global trend. However, as Tran et al. explained, keeping the approximation error under control in high dimensions forces $\sigma$ to be tiny. This traps the optimizer in local minima, rendering isotropic Gaussian smoothing ineffective for high-dimensional, multimodal landscapes.

Isotropic Smoothing (Fails):
High Dimensions -> Must shrink radius σ to keep error low -> Trapped in local minima

Directional Smoothing (Succeeds):
High Dimensions -> Smooth along 1D orthogonal lines -> Keeps large σ exploration without dimensional error explosion

Designing Around the Curse

To bypass these dimensional bottlenecks, researchers have developed algorithms that alter how the smoothing is performed, or exploit the geometry of specific problems.

1. Directional and Non-Isotropic Smoothing

Instead of smoothing isotropically across all $d$ dimensions simultaneously—which causes the volume and error to explode—one can smooth along lower-dimensional subspaces. Tran et al. proposed Directional Gaussian Smoothing (DGS), which replaces full-dimensional convolving with long-range 1D explorations along orthogonal directions. This allows the algorithm to maintain a large exploration radius $\sigma$ to skip local minima without suffering from the multi-dimensional volume explosion.

2. Advanced Smoothing Operators

Other approaches replace standard Gaussian or uniform noise with more sophisticated mathematical envelopes. Scaman et al. introduced Bend, Mix and Release (BMR), a method that bridges the gap between computationally cheap randomized smoothing and the theoretically ideal Moreau Envelope. BMR achieves a $\sqrt{d}$ multiplicative improvement in approximation error over standard randomized smoothing, allowing optimizers to navigate sharp cracks in non-convex landscapes much more efficiently.

3. Turning the Curse into a Blessing

Intriguingly, the aggressive smoothing required in high dimensions is not always a disadvantage. In score-based generative modeling (SGMs), deep networks are trained to estimate the gradient of a smoothed data distribution. Fu et al. demonstrated a counter-intuitive phenomenon: because higher dimensions require more aggressive smoothing to maintain theoretical stability, the resulting target distribution becomes significantly simpler and flatter. As a result, the neural network width required to learn this distribution can actually decrease as the ambient dimension increases, turning a notorious optimization bottleneck into a representation advantage.

Key Foundational Work

On Stochastic Gradient and Subgradient Methods with Adaptive Steplength Sequences (2011) — contributed 1 concept elements to this direction.
Some Approximation Properties of Projection Pursuit Learning Networks (1991) — 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_dimension_dependent_smoothing_126c38f7,
  title = {dimension-dependent smoothing},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/dimension-dependent-smoothing/rdr_126c38f776e5463c8815731beccdefaf},
  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_dimension_dependent_smoothing_126c38f7_v1,
  title = {dimension-dependent smoothing},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/dimension-dependent-smoothing/rdr_126c38f776e5463c8815731beccdefaf/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-20},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake