Probability Inequalities for Sums of Bounded Random Variables

By Nicholas I. Fisher, Pranab Kumar Sen. 1994

Subfields: Statistics and Probability, Statistical Learning Theory

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 Statistical Learning Theory

Citations in the corpus

Can a Suit of Armor Conduct Electricity? A New Dataset for Open Book Question Answering (2018, neutral): “8 An application of Hoeffding’s Inequality (Hoeffding, 1963) shows that ˜ H ( Q ) − 3% with probability over 98.8% and at least ˜ H ( Q ) − 2 .”
Certified Robustness to Adversarial Examples with Differential Privacy (2018, methodology): “It is possible to use Hoeffding’s inequality [23] to bound the number of draws necessary to distinguish the highest probability with probability at least η, given the difference between the top two probabilities pmax − p2.”
Turbo-Aggregate: Breaking the Quadratic Aggregation Barrier in Secure Federated Learning (2020, background): “Then, Xl follows a hypergeometric distribution with parameters (N,T, logN) and its tail probability is bounded as P[Xl ≥ logN 2 ] ≤ exp (−2( 12 − T N )(2) logN) = exp (−2 2 logN) [42].”
Nothing Else Matters: Model-Agnostic Explanations By Identifying Prediction Invariance (2016, methodology): “We use Hoeffding bounds [6] for the differences in precision to decide when a constraint dominates all the other constraints with high probability.”
Generalized random forests (2016, positive): “…that δ is a U -statistic and using (47) to bound the variance of a single tree, we can use the Bernstein bound for U -statistics established by Hoeffding (1963) to verify that, for any η > 0, P [∥∥δ ((θ, ν) , (θ′, ν ′))∥∥∞ > η] ≤ 2k exp ( −bn/scη2 / ( 2L ∥∥∥∥(θ − θ′ν − ν ′ )∥∥∥∥ 2 + 4G 3…”
Counterfactual Estimation and Optimization of Click Metrics for Search Engines (2014, background): “Concentration inequalities like Hoeﬀding’s [15] can be used to estimate whether the gap between the two quantities is statistically signiﬁcant or not.”
Learning from Logged Implicit Exploration Data (2010, positive): “First, given a dataset ( x t , a t , r t,a t ), t = 1 , . . . , T , generated by the process described in Section 2, note that it is straight-forward to apply Hoeﬀd-ing’s bound (Hoeﬀding, 1963) to the random variables q holds with probability at least 1 − δ , for a ﬁxed policy h .”
Sharp analysis of low-rank kernel matrix approximations (2012, positive): “This result extends to the matrix case the classical result of Hoeffding (1963).”
A PAC-Bayesian bound for Lifelong Learning (2013, methodology): “In the proof we will make use of Hoeffding’s Lemma : Lemma 3 (Hoeffding, 1963) Let X be a real-valued random variable such that Pr ( X ∈ .”
Optimal and Adaptive Off-policy Evaluation in Contextual Bandits (2016, neutral): “Lemma 3 (Hoeffding, 1963, Theorem 2) .”
An Alternative View: When Does SGD Escape Local Minima? (2018, neutral): “Lemma 6 (Hoeﬀding bound [12]) .”
Empirical Bernstein Bounds and Sample-Variance Penalization (2009, background): “It appears in a stronger, more general form in Hoeffding’s 1963 milestone paper [4].”
Uniform Convergence of Random Forests via Adaptive Concentration (2015, background): “This bound is an adaptation of a result due to Chernoff [12] and Hoeffding [22], stated below for convenience.”
Action Elimination and Stopping Conditions for the Multi-Armed Bandit and Reinforcement Learning Problems (2006, background): “Lemma 4 (Hoeﬀding, 1963) Let X be a set, D be a probability distribution on X , and f 1 , ..., f m be real-valued functions deﬁned on X with , where a i and b i are real numbers satisfying a i b i .”