×

zbMATH — the first resource for mathematics

A sharp concentration inequality with applications. (English) Zbl 0954.60008
Summary: We derive a new general concentration-of-measure inequality. The concentration inequality applies, among others, to configuration functions as defined by Talagrand and also to combinatorial entropies such as the logarithm of the number of increasing subsequences in a random permutation and to Vapnik-Chervonenkis (VC) entropies. The results find direct applications in statistical learning theory, substantiating the possibility to use the empirical VC entropy in penalization techniques.

MSC:
60E15 Inequalities; stochastic orderings
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Ahlswede, Z Wahrscheinlichkeitstheor Verwand Geb 34 pp 157– (1976) · Zbl 0349.94038 · doi:10.1007/BF00535682
[2] Random graphs, Academic Press, Orlando, 1985.
[3] and Elements of information theory, John Wiley, New York, 1991. · doi:10.1002/0471200611
[4] Dembo, Ann Probab 25 pp 929– (1997)
[5] Deuschel, Combin Probab Comput 8 pp 247– (1999) · Zbl 0949.60019 · doi:10.1017/S0963548399003776
[6] and A probabilistic theory of pattern recognition, Springer-Verlag, New York, 1996. · doi:10.1007/978-1-4612-0711-5
[7] Frieze, Discrete Math 81 pp 171– (1990) · Zbl 0712.05052 · doi:10.1016/0012-365X(90)90149-C
[8] Frieze, Ann Appl Probab 1 pp 301– (1991) · Zbl 0738.05002 · doi:10.1214/aoap/1177005939
[9] Han, Inform and Control 36 pp 133– (1978) · Zbl 0367.94041 · doi:10.1016/S0019-9958(78)90275-9
[10] Haussler, Inform and Comput 115 pp 248– (1994) · Zbl 0938.68785 · doi:10.1006/inco.1994.1097
[11] A catalog of complexity classes, in Handbook of Theoretical Computer Science, A, MIT Press, Boston, 1990, pp. 67-162.
[12] ? Isoperimetry and gaussian analysis,?; Lectureson probability theory and statistics, Ecole d’Et? de Probabilit?s deSt-Flour XXIV-1994, (Editor), LNM 1648, Springer-Verlag, Berlin, 1996, pp. 165-294. · doi:10.1007/BFb0095676
[13] Ledoux, ESAIM: Probab Statist 1 pp 63– (1996) · Zbl 0869.60013 · doi:10.1051/ps:1997103
[14] Loomis, Bull Amer Math Soc 55 pp 961– (1949) · Zbl 0035.38302 · doi:10.1090/S0002-9904-1949-09320-5
[15] Lugosi, Ann. Stat 27 (1999) · Zbl 0961.62081 · doi:10.1214/aos/1017939242
[16] Marton, IEEE Trans Inform Theory 32 pp 445– (1986) · Zbl 0594.94003 · doi:10.1109/TIT.1986.1057176
[17] Marton, Ann Probab 24 pp 857– (1996) · Zbl 0865.60017 · doi:10.1214/aop/1039639365
[18] Marton, Geo Funct Anal 6 pp 556– (1996) · Zbl 0856.60072 · doi:10.1007/BF02249263
[19] About the constants in Talagrand’s concentration inequalities for empirical processes. Ann Probab, to appear ( 2000). · Zbl 1140.60310
[20] Optimal constants for Hoeffding type inequalities, Technical report, Math?matiques, Universit? de Paris-Sud, Report 98.86, 1998.
[21] Some applications of concentration inequalities to statistics, Technical report, Math?matiques, Universit? Paris-Sud, Report, 2000. · Zbl 0986.62002
[22] ? On the method of bounded differences,? Surveys in combinatorics 1989, Cambridge University Press, Cambridge, 1989, pp. 148-188.
[23] ? Concentration,? Probabilistic methods for algorithmic discrete mathematics, and (Editors), Springer, New York, 1997, pp. 195-248.
[24] Shawe-Taylor, IEEE Trans Inform Theory 44 pp 1926– (1998) · Zbl 0935.68090 · doi:10.1109/18.705570
[25] Talagrand, Publ Math del’IHES 81 pp 73– (1995) · Zbl 0864.60013 · doi:10.1007/BF02699376
[26] Talagrand, Invent Math 126 pp 505– (1996) · Zbl 0893.60001 · doi:10.1007/s002220050108
[27] Talagrand, Ann Probab 24 pp 1– (1996) · Zbl 0867.60017 · doi:10.1214/aop/1065725175
[28] The nature of statistical learning theory, Springer-Verlag, New York, 1995. · Zbl 0833.62008 · doi:10.1007/978-1-4757-2440-0
[29] Every NP-complete problem has a hard version, Eighth IEEE Structure in Complexity Theory Conf, 1993, pp 305-312.
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.