Concentration inequalities and asymptotic results for ratio type empirical processes

By Evarist Gin'e, Vladimir Koltchinskii. 2006

159 citations recorded by the source corpus.

Let ℱ be a class of measurable functions on a measurable space $(S,\mathcal{S})$ with values in [0,1] and let Pn=n−1∑i=1nδXi be the empirical measure based on an i.i.d. sample (X1,…,Xn) from a probability distribution P on $(S,\mathcal{S})$. We study the behavior of suprema of the following type: \[\sup_{r_{n}\textless\sigma_{P}f\leq \delta_{n}}\frac{|P_{n}f-Pf|}{\phi(\sigma_{P}f)},\] where σPf≥Var1/2Pf and ϕ is a continuous, strictly increasing function with ϕ(0)=0. Using Talagrand’s concentration inequality for empirical processes, we establish concentration inequalities for such suprema and use them to derive several results about their asymptotic behavior, expressing the conditions in terms of expectations of localized suprema of empirical processes. We also prove new bounds for expected values of sup-norms of empirical processes in terms of the largest σPf and the L2(P) norm of the envelope of the function class, which are especially suited for estimating localized suprema. With this technique, we extend to function classes most of the known results on ratio type suprema of empirical processes, including some of Alexander’s results for VC classes of sets. We also consider applications of these results to several important problems in nonparametric statistics and in learning theory (including general excess risk bounds in empirical risk minimization and their versions for L2-regression and classification and ratio type bounds for margin distributions in classification).

Subfields: Applied Mathematics, Numerical Analysis, Statistics and Probability

View Paper: https://www.semanticscholar.org/paper/ae059aee7e0976d01ee5188508259d01267de363

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Applied Mathematics

In Numerical Analysis

In Statistics and Probability

Citations in the corpus

Convergence rates of least squares regression estimators with heavy-tailed errors (2017, background): “The following definition is from [21], page 1167.”
Oracle inequalities in empirical risk minimization and sparse recovery problems (2011, methodology): “Again, we follow the paper by Giné and Koltchinskii [64].”
On the uniform convergence of empirical norms and inner products, with application to causal inference (2013, background): “See also Giné and Koltchinskii [2006]. Recall the definition (2) of J0.”
Rejoinder: Local Rademacher complexities and oracle inequalities in risk minimization (2006, background): “4) is due to Giné and Koltchinskii [19]).”
On local U-statistic processes and the estimation of densities of functions of several sample variables (2007, methodology): “First we consider the case of [/-processes indexed by VC classes of functions and obtain a moment inequal ity that generalizes the scope of that of Einmahl and Mason [13] and Gine and Koltchinskii [17] for empirical processes.”
A high-dimensional Wilks phenomenon (2011, background): “…by general classes of sets goes back to the work of Alexander (1987) (see also van de Geer 2000, for applications to M -estimation), and the impact of recently obtained concentration inequalities on this topic is thoroughly investigated by Giné et al. (2003) and Giné and Koltchinskii (2006).”
Moving Beyond Sub-Gaussianity in High-Dimensional Statistics: Applications in Covariance Estimation and Linear Regression (2018, background): “More general function dependent scalings in empirical processes are considered in Giné and Koltchinskii (2006).”
Efficient Policy Learning (2017, methodology): “This “slicing” idea is common in the literature, and has been used in different contexts by, e.g., Bartlett et al. (2005) and Giné and Koltchinskii (2006).”
Spectral-Pruning: Compressing deep neural network via spectral analysis (2018, background): “By Theorem 3.1 in [16] or Lemma 2.3 of [37] with the covering number bound given by Suzuki [46] and Suzuki [45], there exists a universal constant C (cid:48) such that .”
Some new asymptotic theory for least squares series: Pointwise and uniform results (2012, background): “Theorem 6.1 (Giné and Koltchinskii (2006)).”
Active and passive learning of linear separators under log-concave distributions (2012, methodology): “…and Koltchinskii, 2006) and the closely related disagreement coefﬁcient notion (Hanneke, 2007), which have been widely used to characterize the sample complexity of various (active and passive) algorithms (Hanneke, 2007; Koltchinskii, 2010; Gin´e and Koltchinskii, 2006; Beygelzimer et al., 2010).”
An exponential inequality for the distribution function of the kernel density estimator, with applications to adaptive estimation (2009, methodology): “This was extended to VC classes of functions by several authors ([11,13,15], among others).”
Offline Multi-Action Policy Learning: Generalization and Optimization (2018, background): “As remarked in Gine and Koltchinskii (2006), by a further argument that uses randomization and contraction, Talagrand’s inequality yields the following bound (which will also be useful later): Lemma 9.”
Nonparametric regression using deep neural networks with ReLU activation function (2017, background): “Several oracle inequalities for the least-squares estimator are known; cf. [12, 15, 16, 27, 32].”
Adaptive confidence sets in $$L^2$$ (2011, background): “1 in [11] in case a) of Definition 2, and the second bracketing entropy moment inequality in Theorem 2.”
The Partial Linear Model in High Dimensions (2013, background): “The next lemma is along the lines of theorem 3.1 in Giné & Koltchinskii (2006).”
A compression technique for analyzing disagreement-based active learning (2014, background): “Similar quantities have also been studied in the passive learning literature, rooted in the work of Alexander (see e.g., Alexander, 1987; Gin´e and Koltchinskii, 2006).”
Theory of Disagreement-Based Active Learning (2014, result): “Specifically, the following result is implicit in the work of Giné and Koltchinskii [2006]; an explicit proof of a related result, from the details of which this lemma easily follows, is included in the work of Hanneke and Yang [2012], derived from a wonderfully elegant general result of van der Vaa”