A Result of Vapnik with Applications

By Martin H. Anthony, John Shawe-Taylor. 1993

How researchers see this paper

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

Citations in the corpus

Variance-based Regularization with Convex Objectives (2016, background): “ssume additionally that the model is well-speciﬁed, and that y= h⋆(x) + ξfor some random variable ξwith E[ξ| X] = 0, E[ξ2] ≤ σ2, and h⋆ ∈ BH. Let the function class {ℓ◦H}≤r := (x,y) → cℓ(h(x),y) | c∈ [0,1],c2E[ℓ(h(X),Y)2] ≤ r . 15 Based on inequality (20), we consider the localized complexity Rn({ℓ◦”
Private Learning and Sanitization: Pure vs. Approximate Differential Privacy (2013, neutral): “14 (VC-Dimension Agnostic Generalization Bound [2, 1]).”
Simultaneous Private Learning of Multiple Concepts (2015, background): “ This generalization argument extends to the setting of agnostic learning, where a hypothesis with small empirical error might not exist. Theorem 2.8 (VC-Dimension Agnostic Generalization Bound, e.g. [1,2]). Let Hbe a concept class over a domain X, and let Pbe a distribution over Xf 0;1g. For a samp”
Learning Bounds for Importance Weighting (2010, methodology): “We will use the following relative deviation bound for classiﬁcation of [1, 27].”
Theory of classification : a survey of some recent advances (2005, background): “We learnt the simple symmetrization trick shown above from Giné and Zinn [99] but different forms of symmetrization have been at the core of obtaining related results of similar flavor, see also Anthony and Shawe-Taylor [11], Cannon, Ettinger, Hush, Scovel [55], Herbrich and Williamson [108], Mendel”
Relative deviation learning bounds and generalization with unbounded loss functions (2013, methodology): “ion holds nevertheless in most common applications of machine learning. We start with the proof of a symmetrization lemma originally presented by Vapnik (1998), later improved by a constant factor by Anthony and Shawe-Taylor (1993). These publications and several others have all relied on a lower bo”
Pattern recognition and neural networks (1996, background): “(One difficult y is that the references, like Anthony & Shawe-Taylor, 1993, omit the proofs of these inequalities, which I find far subtler than the ideas which are proved.”
New approaches to statistical learning theory (2003, background): “where the constants above were actually achieved by Anthony and Shawe-Taylor (1993). Combining this inequality with Lemma B.”
Conformal Risk Control (2022, methodology): “See Appendix B for a detailed discussion and comparison of these algorithms, including experiments.”
The Sample Complexity of Pattern Classification with Neural Networks: The Size of the Weights is More Important than the Size of the Network (1998, methodology): “The following result can be proved using the techniques from the proof of Lemma 4, together with the proof of the corresponding result in [40] (or the simpler proof in [3]).”
Bayesian Gaussian process models : PAC-Bayesian generalisation error bounds and sparse approximations (2003, background): “In classical VC bounds which deal with zero-one loss, this problem is elegantly circumvented by bounding relative deviations such as (p − p̂)/√p (see [198, 5]).”
NEW APPROACHES TO STATISTICAL LEARNING THEORY (2006, background): “Vapnik and Chervonenkis also obtained the following result for classes of {0, 1}- valued functions Pf - Pnf ] (4.2) IP sup > t L J ~ ~ - _ 41E[N2 (9 ~, n-1/2)]e -nt2/4 ' where the constants above were actually achieved by Anthony and Shawe-Taylor (1993).”
Detecting Change in Data Streams (2004, result): “We start with the following consequence of a result of Anthony and Shawe-Taylor [2].”
Structural Risk Minimization Over Data-Dependent Hierarchies (1998, methodology): “We will make use of the following result of Vapnik in a slightly improved ver sion due to Anthony and Shawe-Taylor [4].”