The Curse of Dimensionality in Randomized Smoothing

136 concepts58 papers1 proposal

Randomized smoothing has emerged as a cornerstone of certified adversarial robustness. By taking a base classifier, injecting random noise (such as Gaussian noise) into an input, and taking a majority vote, researchers can construct a "smoothed" classifier with provable safety guarantees. As shown by Jeremy Cohen et al. in Certified Adversarial Robustness via Randomized Smoothing., this technique provides a mathematically rigorous way to ensure that a model's predictions remain stable within a certain Euclidean ($\ell_2$) radius.

However, when we attempt to scale these guarantees from low-resolution toy examples to high-dimensional, real-world data—such as high-resolution imagery or complex 3D point clouds—we run into a fundamental mathematical wall. This wall is the curse of dimensionality. As the number of input features ($d$) grows, the certified safety margins provided by standard smoothing techniques rapidly degrade, often vanishing entirely.

The Geometry of Decay: Why Certified Radii Vanish

To understand why randomized smoothing struggles in high dimensions, we must look at how the certified radius scales relative to the dimension $d$. For $\ell_p$ threat models where $p > 2$—most notably the maximum-absolute-difference norm ($\ell_\infty$), which represents independent coordinate-wise perturbations—the maximum certifiable radius shrinks at a rate of $\mathcal{O}(1/\sqrt{d})$.

As proven by Aounon Kumar et al. in Curse of Dimensionality on Randomized Smoothing for Certifiable Robustness, this decay means that for high-resolution images, the guaranteed safe perturbation per pixel becomes practically negligible. This is not a flaw of a specific noise distribution; Yihan Wu et al. demonstrated in Completing the Picture: Randomized Smoothing Suffers from the Curse of Dimensionality for a Large Family of Distributions that this vanishing radius applies to almost all continuous, symmetric smoothing distributions. Similarly, Jamie Hayes in Extensions and limitations of randomized smoothing for robustness guarantees established that as the order of the norm approaches infinity, the certified safety radius drops to zero, rendering standard smoothing ill-suited for minimax adversarial settings.

The Thin Shell Effect and Orthogonality

High-dimensional spaces exhibit counterintuitive geometric properties due to the concentration of measure. This phenomenon manifests in two devastating ways for randomized smoothing:

  1. The Thin Shell Effect: In high dimensions, the probability mass of a standard isotropic Gaussian distribution does not cluster near the center (the clean input). Instead, it concentrates almost entirely on a narrow hyperspherical "thin shell" far away from the original data point. As noted by Dinghuai Zhang et al. in Black-Box Certification with Randomized Smoothing: A Functional Optimization Based Framework, this leaves the immediate neighborhood of the input poorly covered, creating a severe trade-off between maintaining high clean accuracy and achieving meaningful robustness.
  2. Rapid Orthogonality: To combat the rigidity of fixed noise, one might consider input-dependent smoothing, where the noise variance adapts to the input. However, the authors of Intriguing Properties of Input-dependent Randomized Smoothing revealed that high-dimensional Gaussians with different variances become orthogonal to each other incredibly quickly. To maintain a valid mathematical certificate, the noise level between an input and its potential adversary must vary extremely slowly—a constraint that becomes tighter and more restrictive as dimensionality increases.

The Collapse of Bounded Support Distributions

A natural question is whether we can avoid these issues by switching from infinite-support noise (like Gaussian or Laplace) to bounded-support noise (like uniform noise). Intuitively, uniform noise might seem cleaner because it strictly limits how far a perturbed sample can stray.

In reality, bounded distributions suffer from an even harsher curse of dimensionality. In Certified Adversarial Robustness Under the Bounded Support Set, Yiwen Kou et al. showed that the geometric overlap (intersection) between an original bounded noise distribution and its shifted counterpart shrinks at a polynomial or exponential rate as dimensions increase. While infinite-support distributions maintain a persistent, albeit small, overlap across the entire space, bounded distributions see their overlap collapse to zero instantly when shifted in high dimensions. This makes uniform noise highly impractical for certifying high-resolution data.

The Information Bottleneck

Beyond geometry, traditional randomized smoothing suffers from an informational limitation. Most standard frameworks only utilize the final label probabilities or the probability of the top-predicted class to calculate the certified radius.

As analyzed by Greg Yang et al. in Randomized Smoothing of All Shapes and Sizes, this creates a strict information bottleneck. By throwing away the full output distribution of the base classifier and relying solely on hard class probabilities, it becomes mathematically impossible to derive non-trivial robustness guarantees against high-dimensional $\ell_\infty$ attacks, regardless of what noise distribution is engineered.

Bypassing the Dimensionality Barrier

To overcome these fundamental limits, recent frameworks look beyond standard data-independent smoothing:

  • Exploiting Model Confidence: Linyi Li et al. introduced Double Sampling Randomized Smoothing, which leverages the concentration of model confidence near clean inputs. By combining information from two distinct noise distributions, they derive certified radii that scale with the square root of the input dimension, effectively counteracting the vanishing radius problem.
  • Low-Rank Projections: Real-world high-dimensional data often lies on a lower-dimensional manifold. In Adversarial robustness via robust low rank representations, Pranjal Awasthi et al. proposed projecting inputs into a low-rank subspace (such as the Discrete Cosine Transform basis) before smoothing. This maps high-dimensional $\ell_\infty$ perturbations into lower-dimensional spaces with small operator norms, bypassing the dimensionality-dependent scaling limits entirely.
History & citationVersion 2 · 2026-10-04

Current · Permanent link

  1. Version 2 (latest) · 2026-10-04 · 70 papers
  2. Version 1 · 2026-10-04 · 72 papers
Cite this direction

Latest version (a living page):

@misc{lacuna_curse_of_dimensionality_in_randomized_sm_ba307b8b,
  title = {curse of dimensionality in randomized smoothing},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/curse-of-dimensionality-in-randomized-smoothing/rdr_ba307b8b7d524a66aa0f50c316d82ce7},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-21},
}

This exact version (version 2, frozen text):

@misc{lacuna_curse_of_dimensionality_in_randomized_sm_ba307b8b_v2,
  title = {curse of dimensionality in randomized smoothing},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/curse-of-dimensionality-in-randomized-smoothing/rdr_ba307b8b7d524a66aa0f50c316d82ce7/v/2},
  note = {Version 2, frozen 2026-10-04. Accessed 2026-11-21},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake