Some Extensions of an Inequality of Vapnik and Chervonenkis

By Dmitry Panchenko. 2002

42 citations recorded by the source corpus.

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.

Subfields: Applied Mathematics, Numerical Analysis, Statistical and Nonlinear Physics

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Applied Mathematics

In Numerical Analysis

In Statistical and Nonlinear Physics

Citations in the corpus

Smoothness, Low Noise and Fast Rates (2010, methodology): “d-dimensional linear predictors), then in expectation over sample [22]:”
Contextual Decision Processes with low Bellman rank are PAC-Learnable (2016, methodology): “However, this may only be a technical issue, and a more reﬁned analysis may recover a linear dependence (e.g., using tools from Panchenko [2002]).”
Theory of classification : a survey of some recent advances (2005, methodology): “…[158] and Rio [183]), Talagrand's induction method [217], [213], [216] (see also McDiarmid [168], Luczak and McDiarmid [143], Panchenko [176] [177] [178]) and the so-called " entropy method " , based on logarithmic Sobolev inequalities, developed by Ledoux [132], [131], see also Bobkov and…”
Introduction to Statistical Learning Theory (2004, methodology): “The bounded differences inequality was formulated explicitly first by McDiarmid [17] who proved it by martingale methods (see the surveys [17], [50]), but closely related concentration results have been obtained in various ways including information-theoretic methods (see Alhswede, Gács, and Körner ”
Concentration Inequalities (2008, methodology): “Several methods have been known to prove such inequalities, including martingale methods (see Milman and Schechtman [1] and the surveys of McDiarmid [2] [3]), information-theoretic methods (see Alhswede, Gács, and Körner [4], Marton [5] [6] [7], Dembo [8], Massart [9] and Rio [10]), Talagrand's indu”