On the Bernstein-Hoeffding method

Christos Pelekis, Jan Ramon, Yuyi WangarXiv 2015 · DOI · arXiv

Abstract

The Bernstein-Hoeffding method is a cornerstone of probability theory, providing tail bounds for sums of independent random variables. This paper demonstrates that the method can be extended to a significantly larger class of generalized moments beyond the standard exponential case. By leveraging convex ordering and Bernstein polynomials, we derive sharper inequalities that incorporate higher-order moments and conditional distribution data. We further identify "missing factors" in Hoeffding’s original bound and establish the conditions under which the method remains optimal or reduces to simpler inequalities like Markov’s.

Introduction

In statistical learning and probability theory, tail bounds—estimates of the probability that a sum of random variables deviates from its mean—are essential for establishing convergence rates and confidence intervals. Wassily Hoeffding’s 1963 work provided a foundational tool for bounded variables. However, Hoeffding’s bound is often conservative because it ignores specific distributional characteristics like variance or higher moments.

This research generalizes the Bernstein-Hoeffding method to a broader class of functions, providing a framework to "plug in" additional information about the underlying variables to achieve tighter, more precise bounds.

The Generalized Framework

The traditional Bernstein-Hoeffding approach applies Markov’s inequality to the exponential moment $E[e^{hX}]$. This paper expands this approach to the class $\mathcal{F}_{sic}$: functions that are sub-multiplicative, increasing, and convex.

Convex Ordering and Extremal Distributions

A key innovation is the use of convex ordering to identify "extremal" distributions. The authors show that certain distributions, such as the Binomial distribution, serve as worst-case scenarios within these function classes. By proving that a sum of variables is dominated in convex order by a specific "Bernstein random variable," the researchers can derive bounds that are inherently tighter than those relying solely on the range of the variables.

Key Contributions and Refinements

1. The "Missing Factor"

One of the most significant theoretical results is the insertion of a "missing factor" into Hoeffding’s inequality. While Michel Talagrand previously identified the existence of such factors in an asymptotic sense, this paper provides explicit numerical constants. Theorem 1.7 introduces a factor of approximately $(1+h)/e^h$, which strictly improves upon the 1963 original. This bridges the gap between Hoeffding’s bound and the behavior suggested by the Central Limit Theorem.

2. Higher-Order Moments via Bernstein Polynomials

When researchers possess knowledge of the first $m$ moments (e.g., mean, variance, skewness), the paper utilizes Bernstein polynomials to construct a dominating random variable. This leads to Theorems 1.9 and 4.3, which provide a systematic way to refine tail bounds as more information becomes available. Numerical simulations demonstrate that these new bounds often outperform Bennett’s bound, particularly in high-variance scenarios.

3. Conditional Distributions and Mixtures

The method also accommodates information about conditional distributions. For instance, if the mean of a variable is known within specific sub-intervals, the authors use mixtures of random variables to incorporate this granularity. This demonstrates a clear hierarchy: the more information provided to the model, the tighter the resulting bound.

Theoretical Limits and Optimality

The paper also explores the boundaries of the Bernstein-Hoeffding method.

  • Optimality: The authors prove that for integer thresholds and sub-multiplicative functions, Hoeffding’s original bound is optimal. The potential for improvement arises specifically when considering non-integer thresholds or broader function classes.
  • Unbounded Variables: A critical finding is that for non-negative, unbounded random variables, the Bernstein-Hoeffding method collapses into Markov’s inequality. This confirms that the method’s unique power is fundamentally derived from the bounded nature of the variables.

Conclusion

By generalizing the Bernstein-Hoeffding method, this work provides a more flexible and powerful toolkit for probability theory. The ability to incorporate higher moments and conditional data allows for the creation of "sharper" bounds that are more reflective of the actual data distribution than traditional, more conservative estimates. While these new bounds may require slightly more computational effort to optimize, the gain in precision offers significant value for rigorous statistical analysis.

Summary updated

Abstract

We show that the Bernstein-Hoeffding method can be employed to a larger class of generalized moments. This class includes the exponential moments whose properties play a key role in the proof of a well-known inequality of Wassily Hoeffding, for sums of independent and bounded random variables whose mean is assumed to be known. As a result we can generalise and improve upon this inequality. We show that Hoeffding's bound is optimal in a broader sense. Our approach allows to obtain "missing" factors in Hoeffding's inequality whose existence is motivated by the central limit theorem. The later result is a rather weaker version of a theorem that is due to Michel Talagrand. Using ideas from the theory of Bernstein polynomials, we show that the Bernstein-Hoeffding method can be adapted to case in which one has information on higher moments of the random variables. Moreover, we consider the performance of the method under additional information on the conditional distribution of the random variables and, finally, we show that the method reduces to Markov's inequality when employed to non-negative and unbounded random variables.
BibTeX
@misc{pelekis2015bernstein,
  author = {Christos Pelekis and Jan Ramon and Yuyi Wang},
  title = {{On the Bernstein-Hoeffding method}},
  year = {2015},
  eprint = {1503.02284},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1503.02284},
}

Loading related content...

Figure