Probability inequalities for sum of bounded random variables

By W. Hoeffding. 1963

Subfields: Statistics and Probability, Probabilistic & Bayesian Methods

How researchers see this paper

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

In Statistics and Probability

In Probabilistic & Bayesian Methods

Citations in the corpus

All Models are Wrong, but Many are Useful: Learning a Variable’s Importance by Studying an Entire Class of Prediction Models Simultaneously (2018, background): “Thus, under fairly minor conditions, these estimators are unbiased, asymptotically normal, and have finite-sample probabilistic bounds (Hoeffding, 1948, 1963; Serfling, 1980; see also DeLong et al., 1988 for an early use of U-statistics in machine learning, as well as caveats in Demler et al.,…”
Local Linear Forests (2018, methodology): “The proof of Lemma 2 uses concentration bounds for U -statistics given by Hoeffding [1963]. Lemma 2.”
Counterfactual Estimation and Optimization of Click Metrics for Search Engines (2014, background): “Concentration inequalities like Hoeffding’s [15] can be used to estimate whether the gap between the two quantities is statistically significant or not.”
A low variance consistent test of relative dependency (2014, methodology): “The derivation of our test utilizes classical results of U -statistics (Hoeffding, 1963; Serfling, 1981; Arcones & Gine, 1993).”
A Kernel Method for the Two-Sample-Problem (2006, background): “2, uses a Hoeffding (1963) bound for the unbiased statistic.”
Curriculum learning of multiple tasks (2014, methodology): “j );y n j ) : (11) Since the data points in S nare i.i.d., all terms in this product are independent and take values between (er n(h ) 1) nm n and er n(h n) nm n . Therefore, by Hoeffding’s lemma [15], we obtain that the last term of (10) is bounded by a constant: E h n˘Q n 1 E S n exp n (er n(h ”
Excess risk bounds for multitask learning with trace norm regularization (2012, positive): “Using Hoeffding’s inequality [16] it can be bounded with probability at least 1 − δ by √ ln (1/δ) / (2n̄T ).”
Characterizing the sample complexity of private learners (2013, background): “The first two inequalities are known as the multiplicative Chernoff bounds [8], and the last inequality is known as the Hoeffding bound [15].”
Finding Structure with Randomness: Probabilistic Algorithms for Constructing Approximate Matrix Decompositions (2009, background): “ifi1, where fij are the components of the DFT matrix F. This random sum clearly has zero mean. Since the entries of the DFT have magnitude n−1/2, the variance of the sum is n−1. Hoeﬀding’s inequality [71] shows that the magnitude of the ﬁrst component of x∗DF is on the order of n−1/2 with extremely ”
High-dimensional Ising model selection using ℓ1-regularized logistic regression (2010, methodology): “2,...,n, the variables Z(i) u :=x (i) \r {x (i) r −Pθ∗[xr =1|x (i) \r ]+Pθ∗[xr =−1|x (i) \r ]} are zero-mean under Pθ∗, i.i.d. and bounded (|Z (i) u | ≤2). Therefore, by the Azuma-Hoeﬀding inequality [15], we have, for any δ > 0, P[|Wn u | > δ] ≤ 2exp(−nδ2 8 ). Setting δ = αλn 4(2−α), we obtai”
A Survey of Preference-Based Online Learning with Bandit Algorithms (2014, methodology): “A high probability confidence interval for qi,j can be obtained based on the Hoeffding bound [27], which is commonly used in the bandit literature.”
Random Graphs and Complex Networks (2016, background): “Further similar bounds under the same conditions and, even more generally, for independent random variables Xi such that 0 ≤ Xi ≤ 1, are given, for example, in [30, 133] and [14, Appendix A].”
Mean Estimation and Regression Under Heavy-Tailed Distributions: A Survey (2019, unknown): “Applying Hoeffding’s inequality ([32]), we see that (3.”
Extensions to McDiarmid's inequality when dierences are bounded with high probability (2002, background): “There have been a number of generalizations of Chernoff’s inequality, such as the HoeffdingAzuma inequality [9, 1, 7] for martingale difference sequences.”
Tight finite-key analysis for quantum cryptography (2011, background): “According to [39], the probability that Λ exceeds Q+ η cannot exceed12”