Home | Contents | Submissions, editors, etc. | Login | Search | EJP
 Electronic Communications in Probability > Vol. 7 (2002) > Paper 6 open journal systems 


Some Extensions of an Inequality of Vapnik and Chervonenkis

Dmitriy Panchenko, University of New Mexico


Abstract
The inequality of Vapnik and Chervonenkis controls the expectation of the function  by its sample
average uniformly over a VC-major class of functions taking into account the size of the expectation.
Using Talagrand's kernel method we prove a similar result for the classes of functions for which Dudley's
uniform entropy integral or bracketing entropy integral is finite.


Full text: PDF

Pages: 55-65

Published on: January 17, 2002
Bibliography
  1. Boucheron, S., Lugosi, G., Massart, P. (2000), A sharp concentration inequality with applications, Random Structures Algorithms, 16, 277 - 292. Math. Review 2001m:26072
  2. Dembo, A. (1997), Information inequalities and concentration of measure, Ann. Probab., 25, 527 - 539. Math. Review 98e:60027
  3. Dudley, R.M. (1999), Uniform Central Limit Theorems, Cambridge University Press. Math. Review 2000k:60050
  4. Haussler, D. (1995), Sphere packing numbers for subsets of the boolean n-cube with bounded Vapnik-Chervonenkis dimension, J. Combin. Theory Ser. A,  69, 217 - 232. Math. Review 96f:52027
  5. Kohler, M. (2000), Inequalities for uniform deviations of averages from expectations with applications to nonparametric regression, J. Statist. Plann. Inference, 89, no. 1-2, 1 - 23. Math. Review 2001k:62065
  6. Ledoux, M. (1996), On Talagrand's deviation inequalities for product measures,
        ESAIM: Probab. Statist., 1, 63 - 87. Math. Review 97j:60005
  7. Li, Y., Long, P.M., Srinivasan,A. (2001), Improved bounds on the sample complexity of learning, Journal of Computer and System Sciences, 62, 516 - 527. Math. Review  1 824 457
  8. Massart, P. (2000), About the constants in Talagrand's concentration inequalities for empirical processes, Ann. Probab., 28, 863 - 885. Math. Review 2001m:60038
  9. Panchenko, D. (2001), A note on Talagrand's concentration inequality, Elect. Comm. in Probab., 6 , 55 - 65. Math. Review 1 831 801
  10. Panchenko, D. (2001), New zero-error bounds for voting algorithms, preprint.
  11. Rio E. (2000), Inegalites exponentielles pour les processus empiriques, C.R. Acad. Sci. Paris, t.330, Serie I, 597 - 600. Math. Review 2000m:60020
  12. Rio E. (2001), Inegalites de concentration pour les processus empiriques de classes de parties, Probab. Theory Relat. Fields, 119, 163 -175. Math. Review 2001m:60042
  13. Talagrand, M. (1995), Concentration of measure and isoperimetric inequalities in product spaces, Publications Mathematiques de l'I.H.E.S. 81, 73 - 205. Math. Review 97h:60016
  14. Talagrand, M. (1996), New concentration inequalities in product spaces, Invent. Math., 126, 505 - 563. Math. Review 99b:60030
  15. van der Vaart, A., Wellner, J. (1996), Weak Convergence and Empirical Processes: With Applications to Statistics, John Wiley & Sons, New York. Math. Review 97g:60035
  16. Vapnik, V.N., Chervonenkis, A.Ya. (1968), On the uniform convergence of relative frequencies of event to their probabilities, Soviet Math. Dokl., 9, 915 - 918.
  17. Vapnik, V., Chervonenkis, A. (1974), Theory of Pattern Recognition: Statistical problems of learning, Nauka, Moscow. Math. Review 57:14274
  18. Vapnik, V.N. (1998), Statistical Learning Theory, Wiley, New York. Math. Review 99h:62052
















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


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

Electronic Communications in Probability. ISSN: 1083-589X