Uniform mean estimation via generic chaining
Daniel Bartl, Shahar Mendelson · 2025
Read Uniform mean estimation via generic chaining by Daniel Bartl, Shahar Mendelson (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2502-15116.txt.
Introduction
Daniel Bartl and Shahar Mendelson introduce an optimal estimator for means taken uniformly over a whole class of functions, in a 2025 math paper. Estimating one mean from samples is standard, but doing so evenly well for many functions at once is far harder. Their estimator is a single empirical functional built for that job.
Under minimal assumptions, its error across the whole class is bounded with very high probability by a term involving a Gaussian process measure of the class. The construction joins Talagrand's generic chaining method with optimal single-variable mean estimators. The authors say the surprising bound solves several open problems in high-dimensional probability and statistics.
Catalog record
| CREATOR | Daniel Bartl, Shahar Mendelson |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 55 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2502-15116
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Uniform mean estimation via generic chaining Daniel Bartl, Shahar Mendelson Abstract . We introduce an empirical functional Ψ \Psi that is an optimal uniform mean estimator: Let F ⊂ L 2 ( μ ) F\subset L_{2}(\mu) be a class of mean zero functions, u u is a real valued function, and X 1 , … , X N X_{1},\dots,X_{N} are independent, distributed according to μ \mu . We show that under minimal assumptions, with μ ⊗ N \mu^{\otimes N} exponentially high probability, sup f ∈ F | Ψ ( X 1 , … , X N , f ) − 𝔼 u ( f ( X ) ) | ≤ c R ( F ) 𝔼 sup f ∈ F | G f | N , \sup_{f\in F}|\Psi(X_{1},\dots,X_{N},f)-\mathbb{E}u(f(X))|\leq cR(F)\frac{\mathbb{E}\sup_{f\in F}|G_{f}|}{\sqrt{N}}, where ( G f ) f ∈ F (G_{f})_{f\in F} is the Gaussian processes indexed by F F and R ( F ) R(F) is an appropriate notion of ‘diameter’ of the class { u ( f ( X ) ) : f ∈ F } \{u(f(X)):f\in F\} . The fact that such a bound is possible is surprising, and it leads to the solution of various key problems in high dimensional probability and high dimensional statistics. The construction is based on combining Talagrand’s generic chaining mechanism with optimal mean estimation procedures for a single real-valued random variable. 1. Introduction Empirical processes theory was developed as an attempt to obtain uniform versions of the fundamental limit laws of probability theory — leading to the uniform law of large numbers; the uniform central limit theorem; and the uniform law of the iterated logarithm (see the books [ 11 , 12 , 13 , 29 , 33 ] for detailed surveys on these topics). However, over the last 25 years the focus of the theory has shifted — because it has become apparent that quantitative estimates and not the limit behaviour of empirical processes are of central importance in Data Science. As a result, most of the effort in the recent study of empirical processes theory has been devoted to the following question: Question 1.1 . Let (\Omega,\mu) be a probability space and consider F\subset L_{2}(\mu) , consisting of mean-zero functions. Set u:\mathbb{R}\to\mathbb{R} that satisfies u(0)=0 and let u(F)=\left\{u\circ f:f\in F\right\}. Let X,X_{1},...,X_{N} be independent, distributed according to \mu . Find sharp (high probability and in expectation) bounds on (1.1) \sup_{f\in F}\left|\frac{1}{N}\sum_{i=1}^{N}u\left(f(X_{i})\right)-\mathbb{E}u(f(X))\right|\equiv\|\mathbb{P}_{N}-\mathbb{P}\|_{u(F)}. Specifically, the main interest in an estimate on ( 1.1 ) is on the way the supremum \|\mathbb{P}_{N}-\mathbb{P}\|_{u(F)} depends on the geometric structure of F —rather than on that of the class u(F) —, and on N . The case that received the most attention (other than the obvious choice of u(t)=t which corresponds to the empirical process indexed by the class F itself), is u(t)=t^{2} . The quadratic empirical process appears naturally in central questions in Probability, Asymptotic Geometric Analysis and Statistics. In some of those applications the empirical mean \frac{1}{N}\sum_{i=1}^{N}u\left(f(X_{i})\right) is the object of interest—for example, when X is an isotropic random vector in \mathbb{R}^{d} (i.e., X is centred and {\rm Cov}(X)={\rm Id} ), and F=\{\left\langle\cdot,z\right\rangle:z\in S^{d-1}\} ; in that case, \|\mathbb{P}_{N}-\mathbb{P}\|_{u(F)}=\sup_{z\in S^{d-1}}\left|\frac{1}{N}\sum_{i=1}^{N}\left\langle X_{i},z\right\rangle^{2}-1\right| captures the behaviour of the extremal singular values of the random matrix whose rows are X_{i}/\sqrt{N} . Although using the empirical mean \mathbb{P}_{N}u(f) as an ‘educated guess’ of the mean \mathbb{E}u(f) is an obvious choice of a functional, by now it is well understood that it is a poor one. At the same time, there is a variety of applications where the goal is not the study of the empirical mean, but rather to obtain a uniform estimates on the means \{\mathbb{E}u(f(X)):f\in F\} ; in Sections 4 and 5 we present examples of that flavour that have been studied extensively in recent years. Over the years, several attempts have been made to construct uniform mean estimators for arbitrary classes of functions that outperform the empirical mean (notable constructions can be found in [ 1 , 8 , 20 , 22 ] ). And while these estimators do outperform the empirical mean, they either rely on strong structural assumptions on F and exploit those heavily, or attempt to handle general classes F but at the expense of suboptimal performance. To be more accurate, a mean estimation procedure is a real-valued functional \Psi that receives as input an N -tuple X_{1},\dots,X_{N}\in\Omega , a function f and a parameter \delta . The idea is that if X_{1},\dots,X_{N} are selected according to \mu^{\otimes N} , then with probability at least 1-\delta , \left|\Psi_{\delta}(X_{1},\dots,X_{N},f)-\mathbb{E}u(f)\right| is ‘small’; specifically, there is an event of \mu^{\otimes N} -probability at least 1-\delta on which one has sufficient control on \sup_{f\in F}\left|\Psi_{\delta}(X_{1},\dots,X_{N},f)-\mathbb{E}u(f)\right|. The main goal of this note is to construct an optimal uniform mean estimator for an arbitrary class F and a general u under minimal assumptions. As a result, our focus is on the following alternative to Question 1.1 . Question 1.2 . Let X_{1},...,X_{N} be independent, distributed according to \mu . Given \varepsilon>0 and 0<\delta<1 , is there a functional \Psi that receives as data the points X_{1},...,X_{N} and the wanted confidence parameter \delta , and on an event with probability at least 1-\delta with respect to \mu^{\otimes N} , returns \Psi_{\delta}(X_{1},...,X_{N},f) for which (1.2) \displaystyle\sup_{f\in F}\left|\Psi_{\delta}(X_{1},...,X_{N},f)-\mathbb{E}u(f)\right|\leq\varepsilon? Setting our aim high, one may consider a wildly optimistic conjecture regarding a possible answer to Question 1.2 : that the error in ( 1.2 ) should scale as (1.3) \sim{\rm diam}(u(F))\frac{\mathbb{E}\sup_{f\in F}G_{f}}{\sqrt{N}}, where \{G_{f}:f\in F\} is the centred Gaussian process indexed by F\subset L_{2}(\mu) whose covariance is endowed by L_{2}(\mu) 1 1 1 That is, {\rm Cov}(G_{f},G_{h})=\|f-h\|_{L_{2}} for every f,h\in F . , and {\rm diam}(u(F)) is some natural notion of the diameter of the class u(F) . The estimate ( 1.3 ) is, in fact, true when u(t)=t^{2} and the class consists of mean zero functions and satisfies a subgaussian condition: namely, that for every f,h\in F\cup\{0\} and every q\geq 2 , (1.4) \|f-h\|_{L_{q}}\leq L\sqrt{q}\|f-h\|_{L_{2}}. Setting d_{F}=\sup_{f\in F}\|f\|_{L_{2}} , one can show that for a subgaussian, centrally symmetric 2 2 2 That is, if f\in F then -f\in F . class F , if N\geq c_{0}(\frac{\mathbb{E}\sup_{f\in F}G_{f}}{d_{F}})^{2} , then (1.5) \mathbb{E}\sup_{f\in F}\left|\frac{1}{N}\sum_{i=1}^{N}f^{2}(X_{i})-\mathbb{E}f^{2}\right|\leq c_{1}(L)d_{F}\frac{\mathbb{E}\sup_{f\in F}G_{f}}{\sqrt{N}}, and that ( 1.5 ) is the best estimate one can hope for. The proof of ( 1.5 ) and other results on empirical processes involving subgaussian classes can be found in [ 23 ] . Unfortunately, even for u(t)=|t|^{p} , this phenomenon—that the empirical mean \mathbb{P}_{N}u(f) has the error ( 1.3 )—, does not go beyond the case p=2 in the sense that if u(t)=|t|^{p} for some p>2 (even very close to 2), then \sup_{f\in F}|\frac{1}{N}\sum_{i=1}^{N}u(f(X_{i}))-\mathbb{E}u(f)| can be much bigger than ( 1.3 ). Indeed, let X=(g_{1},...,g_{d}) be the standard Gaussian random vector in \mathbb{R}^{d} , put F=\{\left\langle\cdot,z\right\rangle:z\in S^{d-1}\} , and denote the Euclidean norm by \|\cdot\|_{2} . Note that \{G_{f}:f\in F\}=\{\left\langle X,z\right\rangle:z\in S^{d-1}\} , that \sup_{z\in S^{d-1}}\left\langle X,z\right\rangle=\|X\|_{2} , and that \mathbb{E}\sup_{f\in F}G_{f}=\mathbb{E}\|X\|_{2}\sim\sqrt{d} . In fact, it is standard to verify that \|X\|_{2} concentrates sharply around \sqrt{d} (for our purposes it is enough that c_{1}\sqrt{d}\leq\|X\|_{2}\leq c_{2}\sqrt{d} holds with probability at least 1-2\exp(-c_{3}d) ). Moreover,