arXiv preprint ·
Uniform convergence at optimal rate and scale
- Published
- Source
- arXiv preprint, posted before peer review
- Original
- Read it at arXiv
- Topics
Abstract
Uniform convergence asks how many random samples suffice for empirical averages to approximate expectations simultaneously over an entire class of functions. It is a central concept in probability and a foundation of statistical learning. For binary-valued classes, the Vapnik--Chervonenkis theorem characterizes uniform convergence by finiteness of the VC dimension. For dimension $d$, the sharp worst-case sample complexity for additive error $\varepsilon$ is of order $d/\varepsilon^2$. For real-valued functions, the analogous combinatorial parameter is the fat-shattering dimension, which depends on an approximation scale $γ$. The challenge is to achieve error $γ+\varepsilon$ with order $d/\varepsilon^2$ samples, matching the sample bound for binary classes, where $d$ is now the fat-shattering dimension at scale $γ$. Previous results achieved either the optimal scale or the optimal sample complexity, but not both. Our main result closes this gap, establishing the sharp sample complexity at the optimal scale. Along the way, we use several tools that may be of independent interest. The first concerns $\varepsilon$-nets with margin. A classical $\varepsilon$-net intersects every set of mass at least $\varepsilon$ in a prescribed family; we allow the net to intersect a slightly enlarged version of each such set. Remarkably, this relaxation permits bounds independent of the ambient dimension in natural geometric settings. Second, we derive improved covering bounds in both discrete and real-valued settings: we extend Haussler's covering lemma to partial concept classes and use this extension to obtain $\ell_2$ covers at the optimal scale for real-valued function classes. Third, we obtain a chaining bound at the optimal scale by aligning the covers so that successive approximations become increasingly close to one another.
The authors’ abstract, as arXiv lists it. arXiv’s listings, abstracts included, are free for anyone to reuse.
Read it on ReadSearch
Each opens after you create an account, and brings you back to this paper.
More in Machine Learning
Robust Direct Preference Optimization under Preference Label-Flip Attacks
The Certification Exponent: Instance-Optimal Sequential Certification of Policy Improvement from History Dependent Logs
Dimension-free comparison inequalities between $f$-divergences for Gaussian location mixtures
Private Evaluation of High-Dimensional Functions
Decision-Target Reversal under Informative Label Missingness
Get the few papers worth your time in Machine Learning every morning.
ReadSearch reads the new papers in your field each day and brings you the few worth reading, each with its key finding in a sentence.