Empirical margin distributions and bounding the generalization error of combined classifiers

By Vladimir Koltchinskii, D. Panchenko. 2002

596 citations recorded by the source corpus.

We prove new probabilistic upper bounds on generalization error of complex classifiers that are combinations of simple classifiers. Such combinations could be implemented by neural networks or by voting methods of combining the classifiers, such as boosting and bagging. The bounds are in terms of the empirical distribution of the margin of the combined classifier. They are based on the methods of the theory of Gaussian and empirical processes (comparison inequalities, symmetrization method, concentration inequalities) and they improve previous results of Bartlett (1998) on bounding the generalization error of neural networks in terms of 1 -norms of the weights of neurons and of Schapire, Freund, Bartlett and Lee (1998) on bounding the generalization error of boosting. We also obtain rates of convergence in Levy distance of empirical margin distribution to the true margin distribution uniformly over the classes of classifiers and prove the optimality of these rates.

Subfields: Artificial Intelligence, Control and Systems Engineering, Statistical and Nonlinear Physics, Statistical Learning Theory

How researchers see this paper

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

In Artificial Intelligence

In Control and Systems Engineering

In Statistical and Nonlinear Physics

In Statistical Learning Theory

Citations in the corpus

Interpretable Machine Learning: Fundamental Principles and 10 Grand Challenges (2021, background): “Ways that complexity of function classes, algorithms, or learning problems are typically measured in statistical learning theory include the VC dimension, covering numbers, algorithmic stability, Rademacher complexity, or flat minima (see, for instance, Srebro et al., 2010; Kakade et al., 2009; Zhou”
Agnostic Federated Learning (2019, background): “Proof The proof is an extension of the standard proofs for Rademacher complexity generalization bounds (Koltchinskii and Panchenko, 2002; Mohri et al., 2018).”
Smoothness, Low Noise and Fast Rates (2010, methodology): “Koltchinskii and Panchenko [13] provides margin bounds for a generic class H based on the Rademacher complexity of the class. loss This is done by using a non-smooth Lipschitz “ramp” that upper bounds the zero-one loss and is upper-bounded by the margin zero-one loss.”
Rademacher and Gaussian Complexities: Risk Bounds and Structural Results (2003, background): “Koltchinskii and Panchenko (2000a) proved an analogous error bound in terms of margins .”
Robustness and Regularization of Support Vector Machines (2008, background): “This phenomenon is often interpreted from a statistical learning theory view: the regularization term restricts the complexity of the classifier, hence the deviation of the testing error and the training error is controlled [5, 6, 7].”
Generalization in Deep Learning (2017, methodology): “Recall the following fact: using the result by Koltchinskii and Panchenko (2002), we have that for any δ > 0 , with probability at least 1 − δ , the following holds for all f ∈ F : where R ′ m σ ( F ) is Rademacher complexity defined as Here, ξ i is the Rademacher variable, and the supremum is…”
Sparse coding for multitask and transfer learning (2012, background): “The utility of these concepts for learning theory comes from the following key-result (see (Bartlett & Mendelson, 2002; Koltchinskii & Panchenko, 2002)), stated here in two portions for convenience in the sequel.”
Size-Independent Sample Complexity of Neural Networks (2017, methodology): “We refer to the proof of the margin bound of Koltchinskii and Panchenko [2002, Theorem 2] for an example of this technique.”
Norm-Based Capacity Control in Neural Networks (2015, background): “Per-unit ℓ 1 -regularization was studied by Bartlett (1998); Koltchinskii and Panchenko (2002); Bartlett and Mendelson (2003) who showed generalization guarantees.”
Theory of classification : a survey of some recent advances (2005, methodology): “The analysis based on the observation that AdaBoost and related methods tend to produce large-margin classifiers appears in Schapire, Freund, Bartlett, and Lee [191], and Koltchinskii and Panchenko [127].”
Concentration inequalities using the entropy method (2003, background): “In this section we simply present the main result, the reader can consult the background in the recent work of Koltchinskii Panchenko [15], Massart [25], and Bartlett, Boucheron, and Lugosi [2].”
Functional Gradient Boosting based on Residual Network Perception (2018, methodology): “Generally, we can derive a bound on the empirical margin distribution (Koltchinskii & Panchenko, 2002) by using the functional gradient norm in a similar way, and can obtain a generalization bound using it, as shown later.”