Concentration inequalities under sub-Gaussian and sub-exponential conditions
Authors: Andreas Maurer
Massimiliano Pontil
Venue: NeurIPS 2021 Poster (2021)
Keywords: Statistical Learning Theory
Concentration Inequalities

Abstract: We prove analogues of the popular bounded difference inequality (also called McDiarmid's inequality) for functions of independent random variables under sub-gaussian and sub-exponential conditions. Applied to vector-valued concentration and the method of Rademacher complexities these inequalities allow an easy extension of uniform convergence results for PCA and linear regression to the case potentially unbounded input- and output variables.

Concentration inequalities under sub-Gaussian and sub-exponential conditions
Andreas Maurer Istituto Italiano di Tecnologia amCandreas -aarrrr. eu
Massimiliano Pontil
Istituto Italiano di Tecnologia & University College London massimi liano. pon.ipliit..iii
Abstract
We prove analogues of the popular bounded difference inequality (also called McDiarmid's inequality) for functions of independent random variables under sub- Gaussian and sub-exponential conditions. Applied to rector-valued concentration and the method of Rademacher complexities these inequalities allow an easy extension of uniform convergence results for PCA and linear regression the case of potentially unbounded input- and output variables.
Introduction
The popular bounded difference inequality [ has become a standard tool in the analysis of algorithms. It bounds the deviation probability of function of independent random variables from its mean in terms of the sum of conditional ranges, and may not be applied when these ranges are infinite. This hampers the utility of the inequality in certain situations. It may happen that the conditional ranges are infinite, but that the conditional versions, the random variables obtained by fixing all but one of the arguments of the function, have light tails with exponential decay. In this still expect exponential concentration, but the bounded difference inequality is of no help.
might
Vershynin's book [14] gives general Hoeffding and Bemstein-type incqualities for sums of indepen- dent uub-Gaussian or sub-exponential random variables. In situations where the bounded difference inequality is used, one would like to have analogous bounds for general functions. In this work use the entropy method (8) 1. 22 3) to extend these inequalities from sums to general functions of in- dependent variables, for which the centered conditional versions sub-Gaussian sub-exponential, respectively. These concentration inequalities, Theorem 3 and [5] are stated in Section 3 below. Theorems [5 which apply to the heavier tailed sub-exponential distributions, are our principal contributions. Theorem for the sub-Gaussian case has less novelty, but is included to complete the picture, and because its proof provides good demonstration of the entropy method.
For the purpose of illustration we apply these results to some standard problems in learning theory, vector valued concentration, the generalization of PCA and the method of Rademacher complexities. Over the last twenty years the latter method (M. (5]) has been successfully used to prove gener- alization bounds in variety of situations. The Rademacher complexity itself does not necessitate boundedness, but, when losses and distribbiiis are unbounded, the use of the bounded differ- ence inequality only be circumvented with considerable effort. Using our bounds the extension is immediate. We also show how an inequality of Kontorovich [6]. which describes concentration on products of sub-Gaussian metric probability spaces and has applications algorithmic stability, can be extended to the sub-exponential case.
Related work Several works contain results very similar Theorem which refers to the sub- Gaussian case. The closest to it is Theorem in [12], which gives essentially the same learning bounds for sub-Gaussian distributions. Theorem 1 in 6 is also somewhat similar, but specializes to metric probability spaces. Somewhat akin is the work in
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

To address the sub-exponential case, we have not found results comparable to Theorems and S in the literature.
There has been a lot of work to establish generalization in unbounded situations 12
) or
the astounding results in [3]. but we unaware of an equally simple extension of the method of Rademacher complexities to sub-exponential distributions, as the one given below.
2
Preliminaries
2.1 Notation and conventions
We use upper-case letters for random variables and vectors of random variables and lower case letters for scalars and vectors of scalars. In the sequel X (X)..... X,) is vector of independent random variables with values in a space X' the vector X' (Xi..... X² is iid to X and f is function f: A + R. We are interested in concentration of the random variable f (X) about its expectation, and require some special notation to describe the fluctuations of f in its k-th variable X5., when the other variables (I; + k) are given.
Definition If xm R, (I1, In) X and (X,,..., a random vector with independent components in X", then the k-th centered conditional version of f is the random variable f (x) f 2k X Tk+1 T.)) - If (01 ........ Ik X
Fn)]
Then fo (X) is a random- random-variable-vee variaabe--bblleeed function fx (X) : I E X + fa (X) (z), which does not depend on the k-th coordinate of x. If II-Ila is any given Il (X)Il, 1g (z) := Iffe (X) (z))l,, defines a non-negative real-valued function Ilfe (X)Ila on X"" Thus II (X)ll. (X) is also random variable, of which [I]] (X)llalloo is the essential supremum. If X" is iid to X then fl (X)ll, is the same function as f (X') la and Il (X)lla (X') is iid to
random variables, then
I| (X)lla (X). Note that
fx (X) - ([) .... XR X
Also, if (x)) = Σ. Fi, then fu (x) = X E [Xx] is independent of x.
If H is a Hilbert space, then the Hilbert space of Hilbert-Schmidt operators HS (H) is the of bounded operators T on H satisfying [T]) v E.₁ (Te,, ez) < oo with inner product (T. 5) HS Eis (Te,, ex) (Se,, ez) where (ex) is an orthonormal basis. For E H the operator Q₂ HS (H) is defined by Q.y = (y,x) x, and one verifies that || Hs ||-11
2.2 Sub-Gaussian and sub-exponential norms
It follows from Propositions 2.7.1 and 2.5.2 in [14] that we can equivalently redefine the usual sub-Gaussian and sub-exponential norms ||-11 and ||-1|y,, for any real random variable 7 as
||1|, and || = sup
|z
|
122 = sup p21
(1)
vP
p21
|| = (E (1ZP)) //2 It also follows from the above mentioned
where the norms defined propositions that for every centered sub- Gaussian random variable Z we have, for all 8 R.
E [c < 12331121122
2
Sub-exponential variables 2| d/ the exponential, chi-squared and Poisson distributions. Products and squares of sub-Gaussian variables are sub-exponential, in partieular
co) have heavier tails than sub-Gaussian variables and include
2 11
| 12p / 2p
||
2 |7
sup p21
suu p21
P

---

|| if the norms were defined as in [44.. All sub- Gaussann and bounded variables are sub-exponential. For bounded variables we have || v S 1 S 2 but for concentrated variables the sub-Gaussian and sub-exponential norms can be much smaller. The arithmetic mean of N iid bounded variables has uniform norm O (1), sub-Gaussian norm O 1/2). and the square the mean has sub-exponential norm O (N-1) (see (4] The inequalities the next section can therefore be applied successfully to n such variables, even when the bounded difference inequality gives only trivial results, for example when n < In (1/8), where 6 is the confidence parameter. For strongly concentrated variables we have the following lemma (with proof in the supplement).
(we would have | vi
Lemma Suppose the random variable satisfies E [ = 0, |X| S 1 a.s and Pr (|X] for some > 0. Then Vp 2 |,, S 2/ and || I (e (1/e))
> c Se
In nearly deterministic situation, with c = e- we have || S (1/dd, and simple union bound of the sub-exponential inequalities allows uniform estimation of ed such variables with sample size O (n) S 0 (d).
In several applications will require sub-Gaussing sub-exponential bound on the norm of a random vector. This may seem quite restrictive. If X = Σ Z; then in general we can only say XII| Illa> S El so X = Rd with basis (e:) then our most general estimate IIlle, $ >E= () X) which has poor dimension dependence. But in many situations in machine learning one can assume that is a sum, X = Zeignal + Znoises where || is bounded and the perturbing component || /noisell || is of small sub-exponential norm, albeit potentially unbounded.
3 Results
Our first result assumes aub-Gaussian versions f& (X). ). It an unbounded analogue of the popular bounded difference inequality, which is sometimes also called McDiarmid's inequality (B), 111)
Theorem Let f X" R and X (X,....,X,) be vector of independent random variables with values in a space X. Then for any 1 >> O we have
(x)
exp
32e
Σn ll. (X) (x)1
variables this reduces to the general Hoeffding inequality, Theorem 2.6.2 in [14]. On the other hand, if the fu (X) are a.s. bounded, I[ (X) (2) S ти (x), then also Ilf (X)l (x) S (x) and we recover the bounded difference inequality (Theorem 6.5 in (3) up to constant factor. A similar result to Theorem 3 is given with better constants in (6), although
If is a sum of
in specialized and slightly weaker forms, where the essential supremum inside sum in denominator of the exponent.
The next two results are our principal contributions and apply to functions with sub-exponential conditional versions.
Theorem With f and as in Theorem for any t
Pr (f [f (X') t}
t2
< exp
462
Σx fife (x)11
+ 2e max;
I1 (X) (x)]l
The bound exhibits Sab-Gaussian tail governed by the variance-proxy
Σx 1l.f (x1
for
small deviations, and sub-exponential tail governed by the scale-proxy max; large deviations. If is sum recover the inequality in [14, Theorem 2.8.1.
[1lff (X) for
3

---

In Theorem 4 both the variance proxy and the scale proxy depend on the sub- caab-eexoneniall norms Ill, A well known two-tailed bound for sums bounded variables, Bernstein's 's inequality [T]] has the variance proxy depending on Il-Il2 and the scale-proxy on Il- When 11-I12 < |I this leads to tighter bounds, whenever the inequality is operating in the sub-Gaussian regime, which often happens for large sample-sizes. The next result allows a similar use, whenever 11-1 < q Il for conjugate exponents p and q.
Theorem 5 With f and X as above let p. (1, satisfy p- + + 1. Then for any > 0
-12
(x) - Ef (X')] > 5 exp
2 E
/xE I15e (x)
+ 2eq max
I1.a (X)
We cannot let + to recover the behaviour Bernstein's 's inequality in the sub-Gaussian regime, because this would drive the scale-proxy to infinity. But already p = 9 can give substantial improvements over Theorem 4 if the distributions of the fa (X) are very concentrated. This inequality appears to be new even if applied to sums. A proof is given in the supplement, where also show, that the y in the scale-proxy can be replaced by vq. the sub-exponential norm replaced by the sub-Gaussian norm.
We conclude this section with centering lemma, which will be useful in applications. The proof given in the supplement.
Lemma 6 Let X, X' be iid with values in X, db X X R measurable, [1,2). Then
(i) || [ (X, [X]] v. I 11 (X,X'))
(ii) X = IR then || - E [X]l s.. S 2 11.
One consequence of this lemma is, that could equally well work with uncentered conditional versions, if we adjust the constants by an additional factor of 2.
Applications
To illustrate the use of these inequalities we give applications to vector valued concentration and different methods to prove generalization bounds. We concentrate mainly on applications of the more novel Theorems and Applications of the the sub-Gaussian inequality can often be substituted by the reader following the same pattern.
4.1 Vector valued concentration
We begin with concentration of vectors in a normed space (X,,
Proposition 7 Suppose the X; are independent random variables with values in normed space (X, II-II) such that |+I|
S oa and that 8 > O. (i) With probability at least 1
Σx x.
E Σ
X,
< 4e
V
Σ
|1I In (1/5) + 4e max |II| X In (1/5).
The inequality is two-sided, that the two terms on the beft-hand-side may be interchanged.
(ii) If X is a Hilbert space, the X; are tid, n 2 In (1/6) 2 2 then with probability at least 1 -
In (1/8)
Σ EX,-E(X E[X]] s 8e |
(3)
(ii) If X is a Hilbert space, the X; are iid 0 5 1/2 and p.q (1, oc) are conjugale exponents then with probability at least 1 8
In (1/8)
In (1/8)
Σ X; 71
22 -
[XiIll] 2p n
4eg |

---

The purpose of the simple inequality (3) is to give compact expression, when it is possible to restrict the sub-Gaussian regime with the assumption 2 In (1/6). This is often possible applications. Part (iii) gives better estimation bounds when the lower order moments |1-112p ar small.
Proof. (i) We look at the function f (a)
E
zyll- Then
Iife (x) =
Σ ig
J/ + X
E
Σ i
X
S XXII
Observe that the bound on fx (X) (x) (not fa (X) (x) itself) is independent of x. Using Lemma we get
I|x (x) (1)) < ||| Xll, 2 x
and the first conclusion follows from Theorem by equating the probability to á and solving for t. The proofs of (ii) and (ii) follow similar pattern and are given the supplement.
4.2 A uniform bound for PCA
With the results of the previous section is very easy to obtain a uniform bound for principal subspace selection (often called PCA for principal component analysis) with sub- Gabssiann data. In PCA look for a projection onto a d-dimensional subspace which most faithfully represents the data. Let H be Hilbert-space, X; iid with values in H and Pa the set of d-dimensional orthogonal projection operators in H.. For æ E Il and Pa the reconstruction error is (P,x) := Pax [1 We give a bound on the estimation difference between the expected and the empirical reconstruction error, uniform for projections Pa-
Theorem 8 With X = (X,,.., X,)) iid and 2 In (1/8) 2 In 2 we have with probability at least 6
-EM(PXX)) s 16e (Vd+1) I V
2 2l (2/8)
sup PEPa n
Proof. It convenient to work the space of Hilbert-Schmidt operators HS (H), where we can write (P,x) ||QzIH (P. (.)22H HS. Then
1
sup PEP, n
1 Σ (1x. - 11xx,))
+ [ HS - 1 Σ IIQxIIlss
sup PePs
HS
Since for P E Pa we have ||Pllss = /d, we can use Cauchy- Sehuhy-Schwwrz and Proposition 7 (ii) to bound the first term above with probability at least 1 ô
In (1/8)
Vd n
-
(Qx,))
Sevvd |11 Illl
n
HS
The remaining term is bounded by applying the same result the random vectors ||Qx, ll ss in the Hilbert space IR (note that this just involves a sum of sub-exponential variables and could already be handled with Theorem 2 in [14). The result follows from combining both bounds in union bound and noting that ||||@x, ssl,, = X1
<
|||
v1
4.3 Generalization with Rademacher complexities
Suppose that H is class of functions h X + R. We seek high-probability bound on the supremum deviation, which is the random variable
n
f ((X) sup
(X.) E (X)I).
n1 m
i=1
5

---

=x)) - -
The now classical method of Rademacher complexities (α). (5] writes f (X) as the sum
- (
and bounds the two terms separately. The first term is bounded using concentration inequality. the second term [f (X) is bounded by symmetrization. If the G are independent Rademacher variables, uniformly distributed on { {-1,1] 1). then
E [
<
L E
sup WEA
Σ cahe (X.)
= (HL
Further bounds on this quantity depend on the class in question. but they do not necessarily require the h (.X;) to be bounded random variables, Lipschitz properties being more relevant. For the first term fX) E [f (x)], however, the classical approach uses the bounded difference inequality, which requires boundedness. We now show that boundedness can be replaced by sub-exponential distributions for uniformly Lipschitz function classes.
Theorem Let X = (X1, X be iid random variables with values in Banach space (X, II-II) and let H. be a class of functions h X - R such that h (x) - (v) S L L| yll for all h E H and T, y X. 1f 2 In (1/8) then with probability at least 1
In (1/8)
Σ - -((()) & E (H, + 16eL ( NEH
sup
Proof. The vector space
B = 9 H - IR: sup 1g (h)l < 00
heh
|ااو| = supдeh 1g (h)l For each X; define X, E B by X, (h) = (1/n) (h (X:) - E [A (X)I). Then the X, are zero mean random variables in B and
becomes a normed space with norm
(X) E x. Also with Lemma and the iid-assumption
sup (E h (X.) h (Xx)) (X) 1
4ha
n
h
L
2L
E [| X/II | v0. S n ||||X ||lll
n
and from Proposition (ii) get with probability at least 1 8
In (1/6)
f ( - E [f (x') s 16eL |||xa,lle,
n
The result follows from
Remarks. 1. A possible candidate for H would be a ball of radius T. in the dual space X composed with Lipschitz functions, like the hinge-loss.
If, instead using Proposition 7 one directly considers the centered conditional versions of f (X), the constants above can be improved at the expense of slightly more complicated proof.
corresponding Lub-Gaussian result can supplied along the same lines by using Theorem 3 instead of Theorem 4 Such result has been given in [12). Theorem 3, using a sub-Gaussian
condition which involves the supremum over the function class. The sub-exponential bound above
new as far as we know, and in the relevant regime n > In (1/5) it improves over the sub-Gaussian case, since ||ll,, < x Illas
As a concrete case consider linear regression with potentially unbounded data. Let X (H, R). where H is Hilbert-space with inner product (...) and norm II-1I I and let X1 and Z, be each sub-exponential random variables in and respectively. The pair (X,, Z1) represents the joint occurrence of input-vectors X1 and real outputs Z1. On X' we consider the class H of functions H {(x, =) - (ar, 2) ((w,, æ)) - =) ||w|| S T.). where is 1-Lipschitz loss function, like the absolute error or the Huber loss.

---

Corollary 10 Let X' and H. be as above and (X, 2) = of random variables X. Then for 5 and n 2 (1/0) with probability at least
..... (X,, Zn)) be an iid sample
1 (x, - - (X, 2.)) Vn (IIIIXI + -11121111l.)) (1 20 (n
8
sup NEH
The proof of this corollary given the supplement.
4.4 Unbounded metric spaces and algorithmic stability
We use Theorem 2 to extend a method of Kontorovich [6] from sub-Gaussian to sub-exponential distributions. (x, d. (1) is metric probability space and X, X' ~ y are iid random variables with values in X' Kontorovich defines the sub- Gaussian diameter of (X, d) as the optimal uub-Gaussian parameter of the random variable ed (X, where c a Rademacher variable. The Rademacher variable is needed in [6] to work with centered random variables, which gives better constants, In our case we work with norms and we can more simply define the sub-Gaussian and sub-exponential diameters respectively as
A. (X, d. p) = Id X'Ile, for a E (1,2) and independent X', X ~ μ.
Then Theorem 4 implies the following result, the easy proof of which is given in the supplement.
Theorem 11 For < S n let X; be independent random variables distributed as p in X, X = (X1,.., X,). X' iid to X, and let x - >R have Lipschitz constant L with respect to the metric on X defined by p (x,y) = Σ, d. (x y:). Then for O
12
-x( 1 < exp
4eI2 Σ, A1 (.). + 2e max; A (X, d.)tt)
This is the sub-exponential counterpart Theorem 1 of ( version of which could have been derived using Theorem in place of Our result can be equally substituted to establish generalization using the notion of total Lipschitz stability, just as in []. We also note that Theorem 4 of the latter work also gives bounds for different Orlicz norms I1-1l,,- but it requires > 1, and the bounds deteriorate as p + 1.
Proofs of Theorems and
first collect some necessary tools. Central to the entropy method the entropy S (Y) of a real valued random variable Y defined as
S S = Ey Y
where the tilted expectation By is defined as Ey |7| E Ze /IR [ey] Using Theorem I in [10 the logarithm of the moment generating function can be expressed in terms of the entropy as
In 00 [XXX-EMM]]] 3 //" S (
(5)
72
If x - R and and the fa are as in the introduction then the conditional entropy is function Sy,a X0 + R defined by Sy.x (x) = S (J& (X) (x:) for E X", At the heart of the method is the sub-additivity entropy (Theorem [T0] or Theorem 4.22 in 3
Σ S. (x)
S (X)) < 5())
(6)
1=11
The following lemma gives a bound on the entropy of a sub-Gaussian random variable.
Lemma For any centered random variable we have (i) (Y) < In [e2r].
(i) If is
sub- Gabssia and 3 is real then S (3YY 16eB2 |

---

Proof.
ex
)
e E [(er]
S(Y) = Ey
In
= In By
In E [ear] - -2 1E [e7]
E B s Iu [e2y]
The first inequality follows from Jensen's is inequality by concavity of the logarithm, the second by convexity of the exponential function. This gives (i). For (ii) replace Y by BY and use 2 to get
S (BY) S In [e29y]
I 16 ||
Proof of Theorem For any E X and y E IR part (ii) of the previous lemma gives Syf.A (2) =
S (yfa (X) (x)) 16en² Il (X) (z))l By subadditivity of entropy (6) this gives
S (ff (X)) 16e7 2 ((x)
Σ Ell (x)
S 16e72
Σ k
llfe (X)1
Using Markov's inequality and (5) this gives
S (ff dy
Pr -f t S exp
B
Bt
7/
exp
16eB32
Σ
1I5 (X)1
dy - Bt
Minimization in 3 concludes the proof.
Lemma 12 (i) and the preceeding proof provide a general template to convert many exponential tail-bounds for sums into analogous bounds for general functions. For sums Σ X; one typically has bound on In E [e@X:]. Lemmaa 12 then provides an analogous bound on the entropy of the conditional versions of general function, and subadditivity of entropy and (5) complete the conversion, albeit
with deterioration of constants. Using part (v) of Proposition 2. 2.7.1 1.1 in [14] this method would lead
an easy proof of Theorem 4 form exactly like Theorem 2.8.1 14] Here we will use slightly
different method which gives better constants and will also provide the proof of Theorem 5
For the proof of Theorem we the following fluctuation representation of entropy (Theorem 3 in (00
s (.. E.y [ E,y [M]]] ds dt
We use this to bound the entropy of centered sub-exponential random variable.
Lemma 13 If Y < <// and EE [Y] = 0 then
e² 1
S
(1 ||
Proof. Let s [0, 1]
E 12 xY YY
Eyy (Y-Exs E,y [M]]]]
E.y [Y²]
E [
The first inequality follows from the variational property of variance, the second from Jensen's inequality since E [Yx] O. Expanding the exponential get
SE
m2+
m
m!!
m!
m==
m=0
8

---

The interchange of expectation and summation will be justified by absolute convergence of the sum as follows.
E
[ym+2]
11 (m 2)
m!
IYR m==
Σ
(m + 2) (m +1 ssc [|e| "
The first inequality follows from definition of | and the second from Stirling's approximation (m + m I (m + 2). Absolute convergence is insured since se le <
Using
[. J. d ds di m
1
the fluctuation representation 7 and the above inequalities give
L (.. E,y (Y Ey [M])²] ds dl
S(Y)
00
6² 11
e IYR
(m + 1) (e (< (e11 m Σ
(1-ellxe --ell\lll,) 2"
We also need the following lemma (Lemma 12 in 9
Lemma 14 Let C and b denote two positive real numbers, > 0. Then
(-Bt+ 1- $ 2 (2C bt)
C,32
-t2
inf 8EjU,1/b)
(8)
Proof of Theorem 4. We abbreviate M == max 1If (X) || and let 0 < S < (eM)
Then for any E 2 and k E (1....,m} we have Ih (1))l,,) by the definition of M. We can therefore apply the previous lemma to 7fx (X) (z). It gives for almost all æ
<
lIfa (X) (x)]l / (eM) I 1/e
6² IYff (X) (2)
230 11f (X) (x) (1 (1-7eM)²
Syf
S
(1 l1-e (x) (x))l
Subadditivity of entropy (6) then yields the total entropy bound
2²22E
Σx fl (X'),,, (X) (1-reMY)
(x)(()) < (x)(x) Σ SREM (X)
(9)
2262 EE II (X)1
(1 (e-7eM
Together with 5 this gives
fee
Σx fl.f (X)11
f 1 S (T)
In E [e[ 3
72
1 BEM
and the concentration inequality then follows from Markov's inequality and Lemma 14
6 Conclusion
In this paper, we presented an extension of Hoeffding- and Bernstein-tyre inequalities for sums of sub-Gaussian and sub-exponential independent random variables to general functions, and illustrated these inequalities with applications to statistical learning theory.
We hope that future work will reveal other interesting applications of these inequalities.

---

References
[1] Bartlett and S. Mendelson. Rademacher and gaussian complexities: Risk bounds and structural results. Journal of Machine Learning Research, 3:463-4822 2002.
[2] S. Boucheron, G. Lugosi, P. Massart, et al. Concentration inequalities using the entropy method. The Annals of Probability, 3133)1183311114 2003.
[3] S. Boucheron, G. Lugosi, and P. Massart. Concentration Inequalities. Oxford University Press, 2013.
[4] C. Cortes, Greenberg, and M. Mohri. Relative deviation learning bounds and generalization with unbounded loss functions. arXiv preprint arXiv:1310.577 1310.5796, 2013.
[5] V. Koltchinskii and D. Panchenko. Rademacher processes and bounding the risk of function learning. In W. E. Gine, D. Mason, editor, High Dimensional Probability II, pages 443-459. 2000.
[6] A. Kontorovich. Concentration in unbounded metric spaces and algorithmic stability. In International Conference on Machine Learning, pages 28-36. PMLR, 2014.
[7] S. Kutin. Extensions to mediarmid's inequality when differences are bounded with high probability. Dept. Comput. Sci., Univ. Chicago, Chicago, IL, USA, Tech. Rep. TR-2002-04, 2002.
[8] M. Ledoux. The concentration of measure phenomenon. Number 89, American Mathematical Soc., 2001.
[9] A. Maurer. Concentration inequalities for functions of independent variables. Random Structures & Algorithms, 29(2): 2006.
[10] A. Maurer. Thermodynamics and concentration. Bernoulli, 18(2):434 454, 2012.
[11] C. McDiarmid. Concentration. In Probabilistic Methods of Algorithmic Discrete Mathematics, pages 195-248, Berlin, 1998. Springer.
[12] R. Meir and T. Zhang, Generalization error bounds for bayesian mixture algorithms. Journal of Machine Learning Research, 4:839-860, 2003.
[13] S. Mendelson. Learning without concentration. In Conference on Learning Theory, pages 25-39. PMLR, 2014.
[14] R. Vershynin. High-dimensional probability: An introduction with applications in data science, volume 47. Cambridge university press, 2018.
10


Reviews:
[{"review_id": "W_44S5qd-D0", "reviewer": "Reviewer_hVqo", "summary": "This paper shows generalizations of the method of bounded differences to a broad class of functions with sub-Gaussian and sub-exponential behavior.\nImportant applications include Rademacher averages, and bounding the generalization error of PCA. The paper is quite technical, but the machinery developed therein is highly general, and seems to this reviewer to be of great interest in a broad variety of machine learning settings.\n", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Overall, this is a very nice paper, with strong results that are less restrictive than prior work.\nThis is a well-trodden area, but this paper makes significant contributions driving bounds that are both more straightforward to use, and, in many cases, sharper.  Having read many of the cited works, coming away with little concept of how to apply them to adapt standard learning methodology to unbounded functional families, several of the results here were quite refreshing, and did seem directly applicable to important learning settings. That being said, there are some connections to work in uniform convergence, that are now quite classic, that are missing.  There is also, of course, some work left to do here, which could be more clearly outlined in this paper.  This reviewer holds that the contribution already is sufficient for a strong NeurIPS publication.\n\nThe comment on line 178 about the classical approach is quite misleading; While Bartlett (2002) gives this approach, Talagrand’s inequality for the supremum of empirical processes was well known by the time the Rademacher average entered the popular machine learning dialogue, and Bousquet’s inequality was proved around this same time (See [1], chapter 12).\nThese bounds depend on ranges substantially less than the corresponding McDiarmid bounds. What would be the advantage of applying your method theorem 8 over the Bousquet bound, with a correction for random variables escaping a bounded set with negligible probability?  Alternatively, could your results be used to derive an analogue of the Bousquet inequality relaxing the boundedness assumption?\n\n\nOne nitpick: the title is rather strange to me. What is a Hoeffding-type bound, if not one that shows sub-Gaussian guarantees under a bounded range assumption? If we take away the bounded range assumption, as this paper so valiantly accomplishes, I would hardly call the result Hoeffding-type.\n\n\nSpecific Points:\n\nThe explanation on line 52 about the function being function valued was very confusing; I understood it, but there must be a better way to express this.\nShould there be an X’ involved in the expectation in the display math after line 57?\n\nline 60: the order of the norms does not match their order in expression 1. \n\nline 61: are the usual LP norms the pth-root of the p-moments? I suspect these definitions are quite familiar to readers of Vershynin, but an explanation in terms of moments would be beneficial for some audiences.  Furthermore section 4.1 would be much more helpful if the information were presented here.\n\nLine 75: “A similar results to” -> “A similar result to”\n\nLine 75: The Kontorovich work uses a symmetric notion of sub-Gaussian diameter; I believe this result is significantly more general, so it reads to me like you're under-selling your work here.\n \n76: The statement about essential supremum reads poorly, I would prefer to see this in algebraic notation.\n\nLines 81 to 83 (and in general much in the paper): I believe this can be expressed in the modern parlance as sub-gamma random variables; in particular this is helpful, as you draw a large parallel to the (sub-gamma) Bernstein inequality. It also raises the question of whether similar bounds can be shown for sub-Poisson random variables, as has often been the case historically, e.g., Bernstein to Bennett, and Talagrand to Bousquet inequalities.\n\nSome dressings on lemma 5 would be appreciated.  Clearly Hoeffding’s lemma handles the sub-Gaussian case, and it appears you bound moments and the sub-exponential constants under similar assumptions?\n\nline 135: Concentration of norms sounds like the expectation of the norm, whereas you bound the norm of the expectation.\nFurthermore, defining the norm of the X as simply ||.|| is rather confusing, as there are a lot of different norms and vertical double bars already. Perhaps writing as ||.||_X would be easier on the reader?\n\nTheorem 7: Is it possible to get an absolute value inside of the supremum with a symmetry argument (at no additional cost)? Furthermore, is it possible to remove the union bound by working directly with the MGFs before applying Markov’s inequality? The result is nice, but it does not seem necessary to have $log(2 / \\delta)$ on this 1-tail bound.\n\n\nIt may be helpful to remind readers that the random variable defined on 170 is generally termed the supremum deviation.\n\n176: I would like to see an example of this. I guess I can see how, e.g., the Massart and Khintchine inequalities can bound empirical Rademacher averages in terms of only empirical (raw) variances, but how does one translate this into a bound on expected Rademacher averages? Even knowing the maximum raw variance (wimpy) seems insufficient; it seems one would need to know the weak variance, but the relationship between weak and wimpy variance relies on boundedness in the contraction inequality application.\n\n\nThe quantity described as the entropy on line 228 is, of course the entropy functional used in e.g., Ledoux's entropy method, however I would read “entropy of a real valued random variable” as “Shannon differential entropy” if it were not further qualified.\nReferences seem to be to Maurer 2012, whereas perhaps citing Ledoux would be more appropriate.\n\nMust the definition of tilted expectation be written in this manner, or must it be defined at all, if only used once?  Many authors use subscripts on expectations to denote the random variable that the expectation is being taken with respect to.\n\n\n\n[1] “Concentration inequalities: A nonasymptotic theory of independence,” Stéphane Boucheron, Gábor Lugosi, et Pascal Massart\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes.  societal impact: largely N/A", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "12"}, "extra_text": {}}, {"review_id": "SmCQAsc0xWq", "reviewer": "Reviewer_tbKF", "summary": "McDiarmid's inequality is one of the workhorses of modern machine learning. In its simplest form, however, it requires the function under consideration to verify a bounded differences property. This work (as others before it) investigates extensions of this idea beyond this stringent requirement.  Using the entropy method [Boucheron et al., 2013, Section 6],  the authors prove concentration inequalities for functions of independent random variables for which the *conditional versions* (random function that keeps all arguments but one fixed) enjoy sub-Gaussianity/sub-exponentiality (instead of being bounded as for *vanilla McDiarmid*).  They further put the new tools in application for vector valued concentration, principal subspace analysis and generalization through Rademacher complexity and algorithmic stability.", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "To the best of this reviewer's knowledge, Theorem 2 and 3 are novel.\nThese newly developed tools would be of value to the machine learning community, as exemplified by the authors.\nThis reviewer recommends acceptance, modulo a few clarifications and fixes (detailed below).\n\n* It is not clear to this reviewer why the authors decided to redefine the sub-Gaussian and sub-exponential  norms  in  a  way  that  they  say  is  different  from  Vershynin  [2018].   For  previously  defined norms, centering properties in Lemma 4 are well-known [Vershynin, 2018, Lemma 2.6.8, Exercise 2.7.10].  If this alternative definition has been given before,  please add a reference.  If it is new,  please provide some motivation.\n\n* Minor detail:\n    * p.1  The current title is uninformative. This reviewer encourages the authors to revisit it.\n    * p.2 Recall briefly definitions of norms on random variables (usual $L_p$ norms in terms of expectations).\n    * L.58  ”does not dependent”\n    * L.237 $\\phi_2 \\to \\psi_2$\n\n**References**\n\n* S. Boucheron,  G. Lugosi,  and P. Massart. Concentration inequalities: A non asymptotic theory of independence. Oxford university press, 2013.\n\n* R. Vershynin. High-dimensional probability: An introduction with applications in data science, volume 47.  Cambridge university press, 2018.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Adequately addressed.", "review_text": "", "extra_scores": {"ethical_concerns": "None.", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3"}, "extra_text": {}}, {"review_id": "FxUGGkEKOTO", "reviewer": "Reviewer_SxeE", "summary": "This paper derives concentration inequalities for functions of independent random variables that are sub-Gaussian or sub-exponential. Applications to vector-valued concentration, PCA, and Rademacher generalization bounds are provided.", "questions": "", "limitations": "", "rating": 9, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The main contributions are the sub-exponential bounds, and their applications are compelling. I think the results are highly relevant. My main suggestions are in the presentation of the material.\n\nI would suggest the following reorganization. You could include the notation as a small piece of the introduction section. Since there are quite a few preliminaries, you could insert a “Preliminaries” section between the results and applications, in which you give the facts that are currently in the notation section along with the material from what is now Section 4.1. \n\nWriting is generally polished, though I found some grammar/style issues.\n- “circumnavigated”→ circumvented\n- PCA is more standard than PSA (in any case be consistent with the abstract)\n- Something wrong with third sentence of the introduction\n- f_k(X)(x) is heavy notation. Please avoid double parentheses.\n- line 16: In situations, where → no comma\n- line 232: missing theorem environment\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "N/A", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "1"}, "extra_text": {}}, {"review_id": "7XHoQMfGi1h", "reviewer": "Reviewer_CLFV", "summary": "The paper provides sub-Gaussian and sub-exponential concentration bounds for functions of independent variables and applies these bounds to Principal Components Analysis (PCA) and linear regression.", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The paper studies random variables of the form $f(X)$,  where $f$ is a function of $n$ variables and $X$ is  a vector of $n$ independent random variables. The paper defines the $k$-centered conditional version $f_k$ of $f(X)$, for $1\\le k\\le n$,  and proves concentration bounds on $f(X)$ in terms of sub-Gaussian and sub-exponential norms associated with the $f_k$'s. These bounds are interesting. For instance, Theorem 1 generalizes existing concentration bounds on the sum of independent random variables.  On the negative side, I think that the machine-learning applications of these techniques are not sufficiently developped to attract the audience of NIPS. Also, the statement of Lemma 11 is erronous: the inequality in Lemma 11 (i) does not holds if $Y$ is a negative constant. Here are other comments:\n\n--The statement in lines 124--126 should be clarified.\n\n--Corollary 9. Something is missing, because the inequality does not hold with probability 1\n\n--Equation after line 217: typo in independet.\n\n--Last equation in Theorem 10. I think $\\sum_k$ should be replaced by $\\sum_i$\n\n--Lemma 11: variables -> variable.\n\n--After feedback, I have increased my score.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The authors discussed a limitation of their work in the conclusion", "review_text": "", "extra_scores": {"ethical_concerns": "I am not aware of ethical concerns regarding this paper", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "8"}, "extra_text": {}}]

Author rebuttal:

Meta-review: The referees are in agreement that this submission provides novel concentration-of-measure inequalities. It is very much within the conference scope and of sufficient interest and novelty. All of the referee objections have been addressed during the discussion phase.
Decision: Accept (Poster)