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.
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).
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:
- 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.
- 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.
- 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