Home | Contents | Submissions, editors, etc. | Login | Search | ECP
 Electronic Journal of Probability > Vol. 14 (2009) > Paper 64 open journal systems 


On concentration of self-bounding functions

Stephane Boucheron, Université Paris-Diderot
Gabor Lugosi, Pompeu Fabra University
Pascal Massart, Université Paris-Sud


Abstract
We prove some new concentration inequalities for self-bounding functions using the entropy method. As an application, we recover Talagrand's convex distance inequality. The new Bernstein-like inequalities for self-bounding functions are derived thanks to a careful analysis of the so-called Herbst argument. The latter involves comparison results between solutions of differential inequalities that may be interesting in their own right.


Full text: PDF

Pages: 1884-1899

Published on: September 9, 2009
Bibliography
  1. Boucheron, Stéphane; Bousquet, Olivier; Lugosi, Gábor; Massart, Pascal. Moment inequalities for functions of independent random variables. Ann. Probab. 33 (2005), no. 2, 514--560. MR2123200 (2006a:60024)
  2. Boucheron, Stéphane; Lugosi, Gábor; Massart, Pascal. A sharp concentration inequality with applications. Random Structures Algorithms 16 (2000), no. 3, 277--292. MR1749290 (2001m:26072)
  3. Boucheron, Stéphane; Lugosi, Gábor; Massart, Pascal. Concentration inequalities using the entropy method. Ann. Probab. 31 (2003), no. 3, 1583--1614. MR1989444 (2004i:60023)
  4. Bousquet, Olivier. A Bennett concentration inequality and its application to suprema of empirical processes. C. R. Math. Acad. Sci. Paris 334 (2002), no. 6, 495--500. MR1890640 (2003f:60039)
  5. Devroye, Luc. Laws of large numbers and tail inequalities for random tries and PATRICIA trees. Probabilistic methods in combinatorics and combinatorial optimization. J. Comput. Appl. Math. 142 (2002), no. 1, 27--37. MR1910516 (2003b:60036)
  6. Klein, Thierry. Une inégalité de concentration à gauche pour les processus empiriques. (French) [A left concentration inequality for empirical processes] C. R. Math. Acad. Sci. Paris 334 (2002), no. 6, 501--504. MR1890641 (2003g:60032)
  7. Klein, T.; Rio, E. Concentration around the mean for maxima of empirical processes. Ann. Probab. 33 (2005), no. 3, 1060--1077. MR2135312 (2006c:60022)
  8. Ledoux, Michel. On Talagrand's deviation inequalities for product measures. ESAIM Probab. Statist. 1 (1995/97), 63--87 (electronic). MR1399224 (97j:60005)
  9. Ledoux, Michel. The concentration of measure phenomenon. Mathematical Surveys and Monographs, 89. American Mathematical Society, Providence, RI, 2001. x+181 pp. ISBN: 0-8218-2864-9 MR1849347 (2003k:28019)
  10. McDiarmid, Colin. Concentration. Probabilistic methods for algorithmic discrete mathematics, 195--248, Algorithms Combin., 16, Springer, Berlin, 1998. MR1678578 (2000d:60032)
  11. McDiarmid, Colin; Reed, Bruce. Concentration for self-bounding functions and an inequality of Talagrand. Random Structures Algorithms 29 (2006), no. 4, 549--557. MR2268235 (2007k:60058)
  12. Molloy, Michael; Reed, Bruce. Graph colouring and the probabilistic method. Algorithms and Combinatorics, 23. Springer-Verlag, Berlin, 2002. xiv+326 pp. ISBN: 3-540-42139-4 MR1869439 (2003c:05001)
  13. Pollard, David. A note on Talagrand's convex hull concentration inequality. Asymptotics: particles, processes and inverse problems, 196--203, IMS Lecture Notes Monogr. Ser., 55, Inst. Math. Statist., Beachwood, OH, 2007. MR2459940
  14. Rio, Emmanuel. Inégalités de concentration pour les processus empiriques de classes de parties. (French) [Concentration inequalities for set-indexed empirical processes] Probab. Theory Related Fields 119 (2001), no. 2, 163--175. MR1818244 (2001m:60042)
  15. Rio, Emmanuel. Inégalités de concentration pour les processus empiriques de classes de parties. (French) [Concentration inequalities for set-indexed empirical processes] Probab. Theory Related Fields 119 (2001), no. 2, 163--175. MR1818244 (2001m:60042)
  16. Steele, J. Michael. Probability theory and combinatorial optimization. CBMS-NSF Regional Conference Series in Applied Mathematics, 69. Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, 1997. viii+159 pp. ISBN: 0-89871-380-3 MR1422018 (99d:60002)
  17. Talagrand, Michel. Concentration of measure and isoperimetric inequalities in product spaces. Inst. Hautes Études Sci. Publ. Math. No. 81 (1995), 73--205. MR1361756 (97h:60016)
  18. Talagrand, Michel. New concentration inequalities in product spaces. Invent. Math. 126 (1996), no. 3, 505--563. MR1419006 (99b:60030)
  19. Talagrand, Michel. A new look at independence. Ann. Probab. 24 (1996), no. 1, 1--34. MR1387624 (97d:60028)
















Research
Support Tool
Capture Cite
View Metadata
Printer Friendly
Context
Author Address
Action
Email Author
Email Others


Home | Contents | Submissions, editors, etc. | Login | Search | ECP

Electronic Journal of Probability. ISSN: 1083-6489