On the Bernstein-Hoeffding method

Christos Pelekis 1 Jan Ramon 2 Yuyi Wang 3
2 MAGNET - Machine Learning in Information Networks
Inria Lille - Nord Europe, CRIStAL - Centre de Recherche en Informatique, Signal et Automatique de Lille (CRIStAL) - UMR 9189
Abstract : We consider extensions of Hoeffding's " exponential method " approach for obtaining upper estimates on the probability that a sum of independent and bounded random variables is significantly larger than its mean. We show that the exponential function in Hoeffding's approach can be replaced with any function which is non-negative, increasing and convex. As a result we generalize and improve upon Hoeffding's inequality. Our approach allows to obtain " missing factors " in Hoeffding's inequality. The later result is a rather weaker version of a theorem that is due to Michel Talagrand. Moreover, we characterize the class of functions with respect to which our method yields optimal concentration bounds. Finally, using ideas from the theory of Bernstein polynomials, we show that similar ideas apply under information on higher moments of the random variables.
Complete list of metadatas

Cited literature [26 references]  Display  Hide  Download

https://hal.inria.fr/hal-01814651
Contributor : Jan Ramon <>
Submitted on : Wednesday, June 13, 2018 - 1:32:57 PM
Last modification on : Friday, March 22, 2019 - 1:36:34 AM
Long-term archiving on : Friday, September 14, 2018 - 3:11:54 PM

File

62-31-43.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-01814651, version 1

Citation

Christos Pelekis, Jan Ramon, Yuyi Wang. On the Bernstein-Hoeffding method. Bulletin of the Hellenic Mathematical Society, Hellenic Mathematical Society, 2018, 62, pp.31-43. ⟨http://bulletin.math.uoc.gr/⟩. ⟨hal-01814651⟩

Share

Metrics

Record views

249

Files downloads

96