On McDiarmid's concentration inequality

Emmanuel Rio (Université de Versailles)

Abstract


In this paper we improve the rate function in the McDiarmid concentration inequality for separately Lipschitz functions of independent random variables. In particular the rate function tends to infinity at the boundary. We also prove that in some cases the usual normalization factor is not adequate and may be improved.



Full Text: Download PDF | View PDF online (requires PDF plugin)

Pages: 1-11

Publication Date: June 8, 2013

DOI: 10.1214/ECP.v18-2659

References

  • Bentkus, V. A remark on the inequalities of Bernstein, Prokhorov, Bennett, Hoeffding, and Talagrand. (Russian) Liet. Mat. Rink. 42 (2002), no. 3, 332--342; translation in Lithuanian Math. J. 42 (2002), no. 3, 262--269 MR1947624
  • Bentkus, Vidmantas. On Hoeffding's inequalities. Ann. Probab. 32 (2004), no. 2, 1650--1673. MR2060313
  • Bentkus, Vidmantas. On measure concentration for separately Lipschitz functions in product spaces. Israel J. Math. 158 (2007), 1--17. MR2342455
  • Devroye, Luc; Lugosi, Gábor. Combinatorial methods in density estimation. Springer Series in Statistics. Springer-Verlag, New York, 2001. xii+208 pp. ISBN: 0-387-95117-2 MR1843146
  • Gilardoni, Gustavo L. An improvement on Vajda's inequality. In and out of equilibrium. 2, 299--304, Progr. Probab., 60, Birkhäuser, Basel, 2008. MR2477387
  • Hoeffding, Wassily. Probability inequalities for sums of bounded random variables. J. Amer. Statist. Assoc. 58 1963 13--30. MR0144363
  • Kearns, M. J. and Saul, L. K. Large deviation methods for approximate probabilistic inference. In UAI, 1998.
  • Krafft, O. A note on exponential bounds for binomial probabilities. Annals of the Institute of Statistical Mathematics 21, (1969), 219-220. Zbl 0176.49106
  • McDiarmid, Colin. On the method of bounded differences. Surveys in combinatorics, 1989 (Norwich, 1989), 148--188, London Math. Soc. Lecture Note Ser., 141, Cambridge Univ. Press, Cambridge, 1989. MR1036755
  • McDiarmid, Colin. Concentration. Probabilistic methods for algorithmic discrete mathematics, 195--248, Algorithms Combin., 16, Springer, Berlin, 1998. MR1678578
  • Owhadi, H., Sullivan, T. J., McKerns, M., Ortiz, M. and Scovel, C. Optimal Uncertainty Quantification. arXiv: 1009.0679v3. Math. PR. 2012.
  • Pinelis, Iosif. On normal domination of (super)martingales. Electron. J. Probab. 11 (2006), no. 39, 1049--1070. MR2268536
  • Pinelis, Iosif. Binomial upper bounds on generalized moments and tail probabilities of (super)martingales with differences bounded from above. High dimensional probability, 33--52, IMS Lecture Notes Monogr. Ser., 51, Inst. Math. Statist., Beachwood, OH, 2006. MR2387759
  • Sion, Maurice. On general minimax theorems. Pacific J. Math. 8 1958 171--176. MR0097026
  • Topsøe, Flemming. Bounds for entropy and divergence for distributions over a two-element set. JIPAM. J. Inequal. Pure Appl. Math. 2 (2001), no. 2, Article 25, 13 pp. (electronic). MR1873865
  • Vajda, Igor. Note on discrimination information and variation. IEEE Trans. Information Theory IT-16 1970 771--773. MR0275575
Bookmark and Share


Creative Commons License
This work is licensed under a Creative Commons Attribution 3.0 License.