From Gauss to Kolmogorov: localized measures of complexity for ellipses

DOI10.1214/20-EJS1739zbMATH Open1448.62023arXiv1803.07763OpenAlexW3049028083MaRDI QIDQ2199701FDOQ2199701

Billy Fang, Yuting Wei, Martin J. Wainwright

Publication date: 14 September 2020

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

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.

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

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
• Sharp asymptotics of the metric entropy for ellipsoids
• A geometric approach to complexity

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)

Cites Work

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

Cited In (1)

• Noisy linear inverse problems under convex constraints: exact risk asymptotics in high dimensions

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)