On Concentration-of-Measure Inequalities

By Gábor Lugosi. 1998

How researchers see this paper

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

Citations in the corpus

RUDDER: Return Decomposition for Delayed Rewards (2018, methodology): “Following Grünewälder and Obermayer [34], Bernstein’s inequality can be used to describe the deviation of the arithmetic mean (unbiased estimator of μ) from the expectation μ (see Theorem 6 of Gábor Lugosi’s lecture notes [67]):”
Graph Sparsiﬁcation by Effective Resistances (unknown): “We now apply Bennett’s inequality for sums of i.i.d. variables (see, e.g., [20]), which says Theorem 9.”
Stochastic Approximation of Smooth and Strongly Convex Functions: Beyond the O(1/T) Convergence Rate (2019, background): “Although we can get a high-probability bound by introducing concentration inequalities (Lugosi, 2009), an O(1/T ) confidence term will appear in the upper bound, making it impossible to be faster than O(1/T ).”
Strong Data Processing Inequalities and $\Phi $ -Sobolev Inequalities for Discrete Channels (2014, background): “…κ > 0 and for all f in a suitable subset of F ( X ) is called the Herbst argument [31], [57], [58], and can be summarized as follows (see, e.g., [58, Ch. 3]): We start with a pair ( A , (cid:28)) , where: We then say that μ satisﬁes a modiﬁed log-Sobolev inequality with constant c > 0 on Here…”
Concentration inequalities for sampling without replacement (2013, unknown): “A standard result from the proof of Bennett’s inequality (see (Lugosi, 2009, page 11) or (Boucheron, Lugosi and Massart, 2013, proof of Theorem 2.9)) applied to the random variable XN−k+1 − µ, with conditional mean µ ,N−k+1 and conditional variance σ 2 ,N−k+1, yields E [ exp ( λ′ XN−k+1−µ+Yk−1 N −…”
Regression on manifolds: Estimation of the exterior derivative (2011, background): “Using the Bernstein inequality [36] and the union bound, P (”
On the concentration of the missing mass (2012, unknown): “32 48 v1 [ m at h. PR ] 1 1 O ct 2”
Bayesian Gaussian process models : PAC-Bayesian generalisation error bounds and sparse approximations (2003, background): “We also neglect to cite results properly, see [106] for the original references.”