Chervonenkis: On the uniform convergence of relative frequencies of events to their probabilities

By Vladimir Naumovich Vapnik. 1971

How researchers see this paper

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

In Statistical Learning Theory

Citations in the corpus

mixup: Beyond Empirical Risk Minimization (2017, background): “Strikingly, a classical result in learning theory (Vapnik & Chervonenkis, 1971) tells us that the convergence of ERM is guaranteed as long as the size of the learning machine (e.g., the neural network) does not increase with the number of training data.”
The Surprising Simplicity of the Early-Time Learning Dynamics of Neural Networks (2020, methodology): “, 2017b], VC dimension [Vapnik and Chervonenkis, 1971], and parameter norms [Bartlett et al.”
Optimization Methods for Large-Scale Machine Learning (2016, background): “is optimizing. For this reason, one often turns to uniform laws of large numbers and the concept of the VapnikChervonenkis (VC) dimension of H, a measure of the capacity of such a family of functions [158]. For the intuition behind this concept, consider, e.g., a binary classication scheme in R2 whe”
Interpretable Machine Learning: Fundamental Principles and 10 Grand Challenges (2021, background): “…for instance, Srebro et al., 2010; Kakade et al., 2009; Zhou, 2002; Schapire et al., 1998; Koltchinskii et al., 2002; Bousquet and Elisseeff, 2002; Vapnik and Chervonenkis, 1971); the size of the Rashomon set differs from all of these quantities in fundamental ways, and it is important in its own…”
A Meta-Transfer Objective for Learning to Disentangle Causal Mechanisms (2019, background): “Since sample complexity - the number of training examples necessary to learn a model - grows approximately linearly (Ehrenfeucht et al., 1989) with VC-dimension (Vapnik and Chervonenkis, 1971), and since VC-dimension grows approximately linearly in the number of parameters in linear models and neura”
Counterfactual reasoning and learning systems: the example of computational advertising (2012, background): “Thanks to a famous combinatorial lemma (Vapnik and Chervonenkis, 1968, 1971; Sauer, 1972), for many usual parametric families F , the growth function N (n, ε,F) increases at most polynomially14 with both n and 1/ε. 14.”
Balanced Policy Evaluation and Learning (2017, methodology): “In some cases it is easier to deal with VC (Vapnik-Chervonenkis) dimension [37] rather than Rademacher complexity.”
Variance-based Regularization with Convex Objectives (2016, background): “M⇢R(✓) n + C M⇢ n , a type of result well-known and achieved by empirical risk minimization for bounded nonnegative losses [6, 26, 25].”
Rademacher and Gaussian Complexities: Risk Bounds and Structural Results (2003, background): “For example, in pattern classification , the following theorem is an improvement of a classical result of Vapnik and Chervonenkis (Vapnik and Chervonenkis, 1971).”
Learning in the presence of malicious errors (1988, methodology): “The Vapnik-Chervonenkis was originally introduced in the paper of Vapnik and Chervonenkis [25] and was rst studied in the context of the distribution-free model by Blumer et al.”
Kernel methods in machine learning (2007, neutral): “Properties of such functions can be captured by the VC-dimension (Vapnik and Chervonenkis [142]), that is, the maximum number of observations which can be labeled in an arbitrary fashion by functions of the class.”
Local Rademacher complexities (2005, background): “The above result is similar to results obtained by Vapnik and Chervonenkis [37] and by Lugosi and Wegkamp (Theorem 3.”
Fantastic Generalization Measures and Where to Find Them (2019, background): “We observe that, with both types, VC-dimension as well as the number of parameters are negatively correlated with generalization gap which conﬁrms the widely known empirical observation that overparametrization improves generalization in deep learning .”
Uniform Convergence of Random Forests via Adaptive Concentration (2015, neutral): “Earlier results with a somewhat similar ﬂavor use arguments in the style of Vapnik and Chervonenkis [41] and study the complexity of the class of ﬁxed-depth decision trees to provide global generalization bounds [2, 10].”