Concentration Inequalities for Sub-Additive Functions Using the Entropy Method

By Olivier Bousquet. 2003

136 citations recorded by the source corpus.

Subfields: Numerical Analysis, Statistical and Nonlinear Physics, Statistics and Probability

How researchers see this paper

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

In Numerical Analysis

1. Richard Nickl
2. Evarist Gin'e
3. Gábor Lugosi
4. Stéphane Boucheron
5. John C. Duchi
6. Karim Lounici
7. Pascal Massart
8. Shahar Mendelson

In Statistical and Nonlinear Physics

1. Gábor Lugosi
2. Stéphane Boucheron
3. Richard Nickl
4. Pascal Massart
5. Evarist Gin'e
6. Holger Rauhut
7. John C. Duchi
8. Hongseok Namkoong

In Statistics and Probability

1. Richard Nickl
2. Gábor Lugosi
3. John C. Duchi
4. Evarist Gin'e
5. Vladimir Koltchinskii
6. Shahar Mendelson
7. Stéphane Boucheron
8. Hongseok Namkoong

Citations in the corpus

• Variance-based Regularization with Convex Objectives (2016, methodology): “ Rsup n (F) 2 log3 nM+ M2 n (t+loglogn) with probability at least 1−e−t. Next, we give an upper bound for (EPb n (f−E[f]))2. We use the following version of Talagrand’s inequality due to Bousquet [12, 14]. (See also Bartlett et al. [3, Thm 2.1].) Lemma B.2. Let r>0 and F be a class of functions”
• Local Rademacher complexities (2005, methodology): “ for the sake of completeness. 34 P. L. BARTLETT, O. BOUSQUET AND S. MENDELSON Recall the following improvement of Rio’s [29] version of Talagrand’s concentration inequality, which is due to Bousquet [7, 8]. Theorem A.1. Let c>0, let Xi be independent random variables distributed according to Pan”
• High‐dimensional quantile regression: Convolution smoothing and concave regularization (2021, background): “3 in Bousquet (2003) (a refined Talagrand’s inequality) to conclude that, for any t > 0,”
• A high-dimensional Wilks phenomenon (2011, methodology): “…E h Pn−1bhn−1i ≥ E hPnbhni . ut Remark 1 Note that we refrained from using the immediate upper-bounds Pnbh2n ≤ sup h∈H Pnh 2 or Pbh2n ≤ sup h∈H Ph2 as is usually done in the proof of the above-stated upper-bounds on the variance of suprema of general empirical processes (Rio 2001; Bousquet 2003).”
• Concentration around the mean for maxima of empirical processes (2005, unknown): “Theorem 3 in Bobkov (1996) applied toZ yields VarZ ≤ 2V , where V = E ( sup t∈T n∑ k=1 ( ζk(t)Xk )2) is Talagrand’s variance factor.”
• An exponential inequality for the distribution function of the kernel density estimator, with applications to adaptive estimation (2009, methodology): “Then, Bousquet’s [3] version of Talagrand’s inequality ([32]), with constants, is as follows (see Theorem 7.3 in [3]): For every x ≥ 0 Pr ⎧ ⎨ ⎩ ‖ n∑ j=1 f (X j )‖F ≥ E‖ n∑ j=1 f (X j )‖F + √ 2V x + U x/3 ⎫ ⎬ ⎭ ≤ 2e−x .”
• Theory of classification : a survey of some recent advances (2005, background): “Variations on the theme and detailed proofs appeared in [48].”
• Adaptive estimation of a distribution function and its density in sup-norm loss by wavelet and spline projections (2008, methodology): “Then, noting that supf ∈F ∪(−F ) ∑n i=1 f (Xi) = supF | ∑n i=1 f (Xi)|, Bousquet’s [3] version of Talagrand’s inequality is as follows: for every t > 0, Pr {∥∥∥∥∥ n∑ i=1 ( f (Xi) − Pf )∥∥∥∥∥ F ≥ E ∥∥∥∥∥ n∑ i=1 ( f (Xi) − Pf )∥∥∥∥∥ F + t } ≤ exp ( − t 2 2V + (2/3)t ) .”
• GLOBAL UNIFORM RISK BOUNDS FOR WAVELET DECONVOLUTION ESTIMATORS (2011, background): “and one likewise proves, using the upper-deviation version of Talagrand’s inequality [6],”
• Concentration Inequalities (2008, methodology): “In this section we focus on so-called “entropy method”, based on logarithmic Sobolev inequalities developed by Ledoux [20, 21], see also Bobkov and Ledoux [22], Massart [23], Rio [10], Boucheron, Lugosi, and Massart [25], [26], and Bousquet [27, 28].”
• Adaptation on the space of finite signed measures (2008, unknown): “β(μ, ν) = sup f∈FBL ∣∣∣∣∫ R fd(μ− ν) ∣∣∣∣ = ‖μ− ν‖FBL , (2)”
• Concentration inequalities for sampling without replacement (2013, background): “A natural tool for this would be a dedicated tensorization inequality for the entropy in the case of sampling without replacement (Boucheron, Lugosi and Massart [4], Maurer [11], Bousquet [5]).”
• Local Rademacher Complexity-based Learning Guarantees for Multi-Task Learning (2016, background): “Furthermore, the graph-regularized MTL [51, 24, 46] can be specialized by taking Ω( W ) = D 1 / 2 W 2 F , wherein . k k k F is a Frobenius norm, and D = L + η I with L being a graph-Laplacian, and η being a regularization constant.”
• Compressive Sensing with structured random matrices (2012, background): “We refer the interested reader to [14].”