📊 statistics

Gaussian Width of Convex Sets via Integral Decompositions, Projections, and the Distribution of Intrinsic Volumes

This paper establishes new decompositions for the Gaussian width of a convex set by linking metric projections and fixed points to intrinsic volumes, ultimately demonstrating that the width is controlled by a single "peak index" of these volumes while recovering classical bounds in the worst case.

Original authors: Reese Pathak, Nikita Zhivotovskiy

Published 2026-03-04

📖 5 min read🧠 Deep dive

CC0 1.0

Original authors: Reese Pathak, Nikita Zhivotovskiy

Original paper dedicated to the public domain under CC0 1.0 (http://creativecommons.org/publicdomain/zero/1.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are trying to measure the "size" of a complex, multi-dimensional shape (like a weirdly shaped cloud of points in space). In mathematics and statistics, this shape is called a convex set. But here's the twist: we aren't just measuring its volume or surface area. We are trying to measure how much this shape "jiggles" when you shake it with a specific kind of random noise (called a Gaussian process).

This measurement is called the Gaussian Width. It's a crucial number used in machine learning to predict how well an algorithm will learn, how fast a signal can be compressed, or how hard a statistical problem is to solve.

For decades, the standard way to calculate this width was like trying to map a mountain range by walking every single possible path up the mountain, step by tiny step. This method is called Generic Chaining. It's incredibly precise, but it's also a nightmare to compute. It's like trying to find the perfect route up a mountain by checking every single blade of grass.

The Big Idea of This Paper
The authors, Reese Pathak and Nikita Zhivotovskiy, say: "Stop walking every path! Let's look at the mountain from a different angle."

They propose two new, simpler ways to estimate this "jiggle" (the Gaussian width) by borrowing tools from statistics and geometry. Instead of walking the path, they look at how a ball rolls down the mountain or how the mountain's "layers" are stacked.

Here are the three main metaphors they use to explain their new methods:

1. The "Rolling Ball" Analogy (Metric Projections)

Imagine you have a bouncy ball (representing random noise) and you drop it onto a complex, bumpy hill (your shape). The ball will roll down and get stuck in a valley. This is called a metric projection.

The Old Way: You try to calculate the average height of the ball by simulating millions of drops and measuring every single wobble.
The New Way: The authors realized that if you drop the ball from different heights (changing the "noise level"), the average distance the ball travels before getting stuck tells you everything you need to know about the shape's size.
The Insight: They broke the problem down into a sum of these "rolling distances" at different noise levels. It's like saying, "Instead of measuring the whole mountain at once, let's measure how far a ball rolls when dropped from 1 foot up, then 2 feet up, then 3 feet up, and add them all together." This turns a hard, complex problem into a simple integral (a sum of smooth curves).

2. The "Onion Layers" Analogy (Intrinsic Volumes)

Imagine your shape is an onion. It has many layers.

The outermost layer is the surface area.
The next layer is the volume.
The innermost layer is a single point.

In math, these layers are called Intrinsic Volumes. Usually, to understand the shape, you have to look at all the layers.

The New Way: The authors discovered that for most shapes, there is one specific "peak layer" (the thickest part of the onion) that dominates the behavior.
The Insight: They showed that the "jiggle" of the shape is mostly determined by this single peak layer. Instead of calculating the complexity of the whole onion, you just need to find the "peak" and measure that. It's like saying, "To know how heavy this onion is, you don't need to weigh every single layer; just find the thickest slice, and that tells you the story."

3. The "Statistical Detective" Analogy (The Reverse Direction)

Usually, statisticians use the shape of a problem to predict how hard it is to solve.

The Old Way: "This shape is complex, so the problem will be hard."
The New Way: The authors flipped the script. They said, "Let's look at how hard the problem actually is to solve (using statistical rates), and use that to figure out the shape's properties."
The Insight: They treated the shape as a "target" for a statistical estimator. By analyzing how well a statistical algorithm performs when trying to hit this target, they could reverse-engineer the shape's Gaussian width. It's like a detective figuring out the size of a hidden room by watching how fast a person can run around inside it, rather than trying to measure the walls directly.

Why Does This Matter?

It's Faster: You don't need to build the complex "admissible partitions" (the step-by-step paths) anymore. You can use simpler formulas involving the shape's geometry.
It's Sharper: For some tricky shapes (like a "cross-polytope," which looks like a star in high dimensions), the old methods gave answers that were way too big (overestimating the difficulty). The new methods give the exact right answer.
It Connects Fields: It bridges the gap between pure geometry (shapes) and statistics (data analysis), showing that tools from one field can solve problems in the other.

The Bottom Line

Think of the Gaussian Width as the "difficulty score" of a shape.

Before: To get the score, you had to climb every single step of a giant, confusing staircase.
Now: The authors gave us an elevator. We just look at the "rolling ball" behavior or the "thickest onion layer," and the elevator takes us straight to the correct score.

This paper is a toolkit for mathematicians and data scientists to stop overcomplicating their calculations and start using the natural geometry of their data to get quick, accurate answers.

1. Problem Statement

The paper addresses the fundamental problem of bounding the Gaussian width of a convex set $T \subset \mathbb{R}^d$ , defined as:
$w(T) = \mathbb{E} \left[ \sup_{x \in T} \langle x, g \rangle \right]$
where $g \sim \mathcal{N}(0, I_d)$ is a standard Gaussian vector.

While Talagrand's Majorizing Measure Theorem provides a complete characterization of the Gaussian width via the $\gamma_2$ functional (based on admissible partitions and generic chaining), constructing optimal partitions for general convex sets is often computationally intractable or requires complex geometric arguments. The authors aim to develop alternative characterizations that:

Avoid explicit generic chaining constructions.
Leverage tools from statistical estimation (specifically the Gaussian sequence model) and convex geometry.
Provide sharp bounds for specific geometric structures (like crosspolytopes and ellipsoids) where classical entropy integrals (Dudley's bound) are known to be loose.

2. Methodology

The authors' approach bridges the gap between the geometry of convex sets and the statistical performance of the Least Squares Estimator (LSE) in a Gaussian sequence model.

A. Statistical Framework

They consider the observation model $Y = \theta^* + \sigma g$ , where $\theta^* \in T$ . The LSE is the metric projection $\Pi_T(Y)$ . The paper exploits the relationship between the Gaussian width and:

The variance of the LSE: $\mathbb{E} \|\Pi_T(\sigma g)\|^2$ .
The minimax estimation rate: $\varepsilon^*(\sigma)$ .
Fixed points of localized Gaussian widths.

B. Two Integral Decompositions

The core of the methodology involves deriving two exact integral decompositions for the Gaussian width $w(T)$ , parameterized by a noise level $\sigma > 0$ :

Decomposition via Fixed Points (Variational Approach):
$w(T) = \left( w(T \cap r(\sigma)B_2^d) - \frac{r(\sigma)^2}{2\sigma} \right) + \frac{1}{2} \int_{\sigma}^{\infty} \frac{r(\nu)^2}{\nu^2} d\nu$
Here, $r(\sigma)$ is the unique maximizer of a variational problem involving the local width of $T$ . This term relates to the "head" of the generic chaining sum.
Decomposition via Metric Projections:
$w(T) = \mathbb{E} \left[ \sup_{t \in T} \left( \langle t, g \rangle - \frac{\|t\|^2}{2\sigma} \right) \right] + \frac{1}{2} \int_{\sigma}^{\infty} \mathbb{E} \|\Pi_{T/\nu}(g)\|^2 d\nu$
This relates the width to the expected squared norm of the projection of a Gaussian vector onto rescaled copies of $T$ .

C. Connection to Intrinsic Volumes and Wills Functional

The authors connect the first terms of these decompositions to the Wills functional $W(T) = \sum_{i=0}^d V_i(T)$ , where $V_i(T)$ are the intrinsic volumes of $T$ .

They utilize recent results by Mourtada (2025) showing that $\log W(T)$ is controlled by a single "peak" intrinsic volume index.
This allows them to bound the Gaussian width using the profile of intrinsic volumes, specifically the index $i^*_\sigma$ where the intrinsic volume of the rescaled set $T/\sigma$ is maximized.

3. Key Contributions and Results

A. Exact Decompositions without Generic Chaining

The paper establishes that the Gaussian width can be exactly decomposed into a "local" term (related to the risk of the LSE at a specific noise level) and an "integrated" term (related to the variance of the LSE across all noise levels).

Result: These decompositions are exact identities (Theorems 2.1 and 2.2), not just upper bounds.
Significance: They bypass the need to construct admissible partitions, replacing them with statistical quantities (fixed points and projection variances) that are often easier to analyze.

B. Characterization via Intrinsic Volumes

The authors prove that the Gaussian width is controlled by the peak intrinsic volume index $i^*$ :
$w(T) \asymp i^* \cdot \text{diam}(T)$
where $i^*$ is the index $i$ maximizing $V_i(T/\text{diam}(T))$ .

Result: This provides a purely geometric characterization of the width. For example, for a crosspolytope, the width is determined by the index where the intrinsic volume profile peaks, which scales as $\sqrt{\log d}$ .
Significance: This explains why the Gaussian width of certain sets (like the crosspolytope) is much smaller than what the dimension $d$ or the diameter alone would suggest.

C. Equivalence of Local and Global Parameters

A significant theoretical contribution is the proof that local and global entropy parameters are equivalent up to universal constants for Dudley-type upper bounds and Sudakov-type lower bounds.

Result: $\text{Local Dudley Integral} \asymp \text{Global Dudley Integral}$ .
Significance: This resolves a subtle issue in statistical learning theory where local and global complexities often differ. It implies that for bounding Gaussian widths, one can use local packing numbers without losing order-of-magnitude accuracy.

D. Information-Theoretic Proofs of Sudakov Inequalities

The paper provides new, information-theoretic proofs for both the classical and dual Sudakov minoration inequalities.

Method: Instead of using Gaussian comparison inequalities (like Sudakov-Fernique), the authors use Fano's inequality combined with properties of the Wills functional and Anderson's lemma.
Significance: This suggests a pathway to extending minoration results to non-Gaussian settings where Gaussian comparison tools fail.

E. Sharp Bounds for Specific Geometries

The authors demonstrate the utility of their framework on the crosspolytope ( $B_1^d$ ) and ellipsoids:

Crosspolytope: The classical Dudley integral yields a bound of order $\log^{3/2}(d)$ , which is loose. The authors' method (using intrinsic volumes or metric projections) recovers the sharp bound of order $\sqrt{\log d}$ .
Ellipsoids: They use a variational approach (Donsker-Varadhan identity) with localized priors to derive sharp bounds for the first term in their decomposition, recovering the correct width for ellipsoids where standard chaining fails.

4. Significance and Impact

Bridging Statistics and Geometry: The paper successfully translates problems in convex geometry (Gaussian width) into problems in statistical estimation (LSE risk, minimax rates). This "reverse direction" (using statistical rates to bound geometric quantities) is a novel and powerful perspective.
Alternative to Generic Chaining: It offers a viable alternative to Talagrand's generic chaining for convex sets. While generic chaining is optimal in the worst case, it is often difficult to apply. The proposed integral decompositions and intrinsic volume profiles offer more tractable tools for specific convex bodies.
Understanding "Loose" Bounds: The paper provides a statistical explanation for why the Dudley entropy integral can be loose: the gap corresponds to the discrepancy between the performance of the LSE at the origin versus the worst-case minimax rate.
New Tools for High-Dimensional Probability: The introduction of the "peak intrinsic index" as a governing parameter for Gaussian width provides a new lens for analyzing high-dimensional convex bodies, potentially impacting fields like compressed sensing, high-dimensional statistics, and machine learning theory.

In summary, Pathak and Zhivotovskiy provide a rigorous framework that decomposes the Gaussian width into statistically interpretable components, linking it to the distribution of intrinsic volumes and the behavior of metric projections, thereby offering sharper and more intuitive bounds for a wide class of convex sets.