From Gauss to Kolmogorov: localized measures of complexity for ellipses

DOI10.1214/20-EJS1739MaRDI QIDQ2199701zbMATHOpenAlexFDO

Authors Yuting Wei, Billy Fang, Martin J. Wainwright

Publication date 14 September 2020

Published in Electronic Journal of Statistics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1803.07763

zbMATH Keywords

least squaresadaptive estimationKolmogorov widthcomplexity measurelocal metric entropyellipse constraint

Mathematics Subject Classification ID

Statistical aspects of information-theoretic topics (62B10) Algorithmic information theory (Kolmogorov complexity, etc.) (68Q30) Probabilistic measure theory (60A10) Information geometry (statistical aspects) (62B11)

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 $alpha$, we exhibit rates that vary from $(sigm{a}^2{)}^{frac2alpha2alpha+1}$, corresponding to the classical global rate, to the faster rate $(sigm{a}^2{)}^{frac4alpha4alpha+1}$. We also show how the local Kolmogorov width can be related to local metric entropy.

Recommendations

• Kolmogorov complexity and the geometry of Brownian motion
• Relative Kolmogorov complexity and geometry
• scientific article; zbMATH DE number 17560
• Ellipticity and circularity measuring via Kullback-Leibler divergence
• The Local Geometry of Testing in Ellipses: Tight Control via Localized Kolmogorov Widths
• Kolmogorov Complexity, Lovász Local Lemma and Critical Exponents
• Kolmogorov complexity and Hausdorff dimension
• scientific article; zbMATH DE number 2089354
• Sharp asymptotics of the metric entropy for ellipsoids
• A geometric approach to complexity

Cites work

• scientific article; zbMATH DE number 3877692 (Why is no real title available?)
• scientific article; zbMATH DE number 5654889 (Why is no real title available?)
• scientific article; zbMATH DE number 3980111 (Why is no real title available?)
• scientific article; zbMATH DE number 45848 (Why is no real title available?)
• scientific article; zbMATH DE number 49190 (Why is no real title available?)
• A new perspective on least squares under convex constraint
• Adapting to Unknown Smoothness via Wavelet Shrinkage
• An automatic inequality prover and instance optimal identity testing
• Chaining, interpolation and convexity II: the contraction principle
• Chaining, interpolation, and convexity
• Compressed sensing
• Concentration inequalities. A nonasymptotic theory of independence
• High-dimensional statistics. A non-asymptotic viewpoint
• Hypothesis testing for densities and high-dimensional multinomials: sharp local minimax rates
• Ideal spatial adaptation by wavelet shrinkage
• Introduction to nonparametric estimation
• Local Rademacher complexities
• Local Rademacher complexities and oracle inequalities in risk minimization. (2004 IMS Medallion Lecture). (With discussions and rejoinder)
• Majorizing measures: The generic chaining
• Minimax risk over hyperrectangles, and implications
• Near-optimality of linear recovery in Gaussian observation scheme under \(\| \cdot \|_{2}^{2}\)-loss
• On density estimation in the view of Kolmogorov's ideas in approximation theory
• On risk bounds in isotonic and other shape restricted regression problems
• On the degrees of freedom in shape-restricted regression.
• Optimal filtering of square-integrable signals in Gaussian noise
• Rademacher penalties and structural risk minimization
• Randomized sketches for kernels: fast and optimal nonparametric regression
• Risk bounds in isotonic regression
• Smoothing spline ANOVA models
• Some results on Tchebycheffian spline functions and stochastic processes
• The Local Geometry of Testing in Ellipses: Tight Control via Localized Kolmogorov Widths
• The geometry of hypothesis testing over convex cones: generalized likelihood ratio tests and minimax radii
• The sizes of compact subsets of Hilbert space and continuity of Gaussian processes
• Theory of Reproducing Kernels
• Upper and lower bounds for stochastic processes. Modern methods and classical problems
• Weak convergence and empirical processes. With applications to statistics

Cited in

(2)

• Noisy linear inverse problems under convex constraints: exact risk asymptotics in high dimensions
• Localized Gaussian width of \(M\)-convex hulls with applications to Lasso and convex aggregation

Describes a project that uses

Uses Software

• gss

This page was built for publication: From Gauss to Kolmogorov: localized measures of complexity for ellipses

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2199701)