From Gauss to Kolmogorov: Localized Measures of Complexity for Ellipses

Yuting Wei, Yuting Wei 0001, Billy Fang, Martin J. WainwrightarXiv 2018 · arXiv

Abstract

Traditional statistical learning theory often relies on minimax risk to characterize the performance of estimators, providing a "worst-case" global average. However, this approach fails to capture the instance-specific difficulty of estimation tasks where the true parameter resides in a geometrically favorable region. This paper establishes a formal bridge between Gaussian width and Kolmogorov width, localized to specific points on an ellipse. By defining a "critical dimension" based on local curvature, the authors derive instance-specific error rates for least-squares estimation, demonstrating that parameters in "narrower" regions of the parameter space can be estimated significantly more efficiently than those in the "fat" interior.

Introduction: Beyond Global Minimaxity

In high-dimensional statistics, the standard tool for measuring the complexity of a parameter set is the Gaussian width. While powerful, Gaussian width is notoriously difficult to calculate for general sets, particularly when one wishes to "localize" the measure to a small neighborhood around a specific parameter $\theta^*$. This localization is crucial because the difficulty of an estimation task is rarely uniform across the entire parameter space.

Consider a parameter set defined by an ellipse. A true parameter $\theta^*$ located at the sharp tip of a highly eccentric ellipse should, intuitively, be easier to estimate than one located in the center, as the set of plausible alternatives is much more constrained in the former case. Standard minimax rates ignore this local geometry, providing a pessimistic bound that applies to the entire class. This paper addresses the challenge of providing tractable, instance-specific error bounds by connecting the probabilistic measure of Gaussian width to the more geometric concept of Kolmogorov width.

Local Geometry and Estimation Hardness

The core motivation of this work is that the "hardness" of a statistical problem is a function of local curvature rather than just global set size. By studying the intersection of an ellipse $\mathcal{E}$ with a Euclidean ball $\mathbb{B}(\delta)$ centered at the true parameter $\theta^*$, the authors can analyze the local complexity.

Varying hardness over an ellipse: Parameters at the "tips" (Easier problem) have smaller local neighborhoods than those in the center (Harder problem).

As illustrated in the figure above, the local neighborhood of $\theta_E^*$ is significantly more constrained than that of $\theta_H^*$. The authors prove that for ellipses, the localized Gaussian width is bounded by a quantity derived from the localized Kolmogorov $k$-width—a measure of how well the set can be approximated by a $k$-dimensional linear subspace. This "Gauss-to-Kolmogorov" bridge allows researchers to use the more tractable geometric properties of Kolmogorov widths to derive statistical convergence rates.

Methods: The Critical Dimension and the Sandwich Relation

The authors introduce a "critical dimension" $k^*$, which acts as the effective dimension of the set near $\theta^*$. Under a specific "regularity" condition for ellipses (generalizing previous work on function class smoothness), they establish a "sandwich relation." This relation shows that the localized Gaussian width is equivalent to $\delta \sqrt{k^*}$ up to universal constants, where $\delta$ is the scale of the localization.

To validate this theory, the authors focus on ellipses defined by the decay of their eigenvalues, which correspond to various kernel classes in Reproducing Kernel Hilbert Spaces (RKHS).

The shape of different kernels (a) and the corresponding decay of their eigenvalues (b), which define the geometry of the resulting ellipses.

For example, Sobolev ellipses represent classes of smooth functions where eigenvalues decay polynomially ($j^{-2\alpha}$), while Gaussian kernels lead to exponential decay. The faster the decay, the "thinner" the ellipse becomes in higher dimensions, leading to different local complexities.

Key Results and Statistical Implications

The theoretical framework yields several significant insights:

  1. Instance-Specific Convergence: The Least Squares Estimator (LSE) is shown to adapt to the local geometry. For a Sobolev ellipse with smoothness $\alpha$, the global minimax error rate is $(\sigma^2)^{\frac{2\alpha}{2\alpha+1}}$. However, at extremal (narrow) points, the rate improves to $(\sigma^2)^{\frac{4\alpha}{4\alpha+1}}$. For highly smooth functions, this represents a massive increase in estimation efficiency.
  2. Minimax Optimality: Despite its ability to adapt to "easy" points, the LSE remains minimax optimal across the entire ellipse, ensuring that local adaptation does not come at the cost of global robustness.
  3. Numerical Verification: Simulations on 500-dimensional ellipses confirm these theoretical predictions. For $\alpha=1$, the error for a "spiked" vector (an easy point) decays with a slope of -4/5 on a log-log plot, matching the theory, whereas the zero vector (a harder point) follows the standard -2/3 slope.

Conclusion

By bridging the gap between Gaussian and Kolmogorov widths, this paper provides a powerful new toolkit for understanding high-dimensional estimation. While currently focused on ellipses and RKHS structures, the transition from probabilistic to geometric complexity measures offers a promising path for studying local geometry in more general convex sets and diverse statistical problems beyond least squares.

Summary updated

Abstract

The Gaussian width is a fundamental quantity in probability, statistics and geometry, known to underlie the intrinsic difficulty of estimation and hypothesis testing. In this work, we show how the Gaussian width, when localized to any given point of an ellipse, can be controlled by the Kolmogorov width of a set similarly localized. This connection leads to an explicit characterization of the estimation error of least-squares regression as a function of the true regression vector within the ellipse. The rate of error decay varies substantially as a function of location: as a concrete example, in Sobolev ellipses of smoothness $α$, we exhibit rates that vary from $(σ^2)^{\frac{2 α}{2 α+ 1}}$, corresponding to the classical global rate, to the faster rate $(σ^2)^{\frac{4 α}{4 α+ 1}}$. We also show how the local Kolmogorov width can be related to local metric entropy.
BibTeX
@misc{wei2018from,
  author = {Yuting Wei and Yuting Wei and Billy Fang and Martin J. Wainwright},
  title = {{From Gauss to Kolmogorov: Localized Measures of Complexity for Ellipses}},
  year = {2018},
  eprint = {1803.07763},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1803.07763},
}
Figure