Theory of classification : a survey of some recent advances

By Stéphane Boucheron, Olivier Bousquet, Gábor Lugosi. 2005

619 citations recorded by the source corpus.

Subfields: Artificial Intelligence, Computer Vision and Pattern Recognition, 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 Computer Vision and Pattern Recognition

In Statistical Learning Theory

Citations in the corpus

On the Equivalence between Herding and Conditional Gradient Algorithms (2012, methodology): “…µ − ˆ µ is enough to control the error in computing the expectation for all f ∈ F with ﬁnite norm. sample Note that a random i.i.d. from p ( x ) would lead to an expected worst-case error which is less than 4 R √ n —a classical result based on Rademacher averages (see, e.g. Boucheron et al., 2005).”
Certifying Some Distributional Robustness with Principled Adversarial Training (2017, background): “Next, we show that EP̂n [φγ(θ;Z)] concentrates around its population counterpart at the usual rate (Boucheron et al., 2005).”
Fair Regression: Quantitative Definitions and Reduction-based Algorithms (2019, background): “By Theorem 3.2 of Boucheron et al. (2005), we then have with probability at least 1 − δ , for all g , We will next bound R n (Φ) in terms of R n ( G ) .”
Variance-based Regularization with Convex Objectives (2016, background): “3 Fast Rates In cases in which the risk R has curvature, empirical risk minimization often enjoys faster rates of convergence [6, 21].”
A Kernel Method for the Two-Sample-Problem (2006, background): “Bousquet et al. (2005) for a detailed discussion of recent uniform convergence bounding methods.”
A Reductions Approach to Fair Classification (2018, background): “By Theorem 3.2 of Boucheron et al. (2005), we then have with probability at least 1 − δ , for all h , We will next bound R n ( F ) in terms of R n ( H ) .”
Spectrally-normalized margin bounds for neural networks (2017, methodology): “This tool has been used to study the behavior of 2-layer networks, boosting methods, SVMs, and many others (Bartlett, 1996; Schapire et al., 1997; Boucheron et al., 2005); in boosting, for instance, there is a similar growth in complexity over time (each training iteration adds a weak learner),…”
Regret Analysis of Stochastic and Nonstochastic Multi-armed Bandit Problems (2012, neutral): “In the rest of this section we focus on the case of K = 2 arms and parametrize classes F of policies f : X → {1, 2} by their VC-dimension d—see Boucheron et al. [2005] for a modern introduction to VC theory.”
Access to Unlabeled Data can Speed up Prediction Time (2011, background): “, Boucheron et al. (2005)).”
Stochastic Gradient Methods for Distributionally Robust Optimization with f-divergences (2016, background): “Classical techniques in machine learning and statistics, including regularization, stability, concentration inequalities, and generalization guarantees [6, 25] provide such guarantees, though often a more ﬁne-tuned certiﬁcate—one with calibrated conﬁdence—is desirable.”
Relative deviation learning bounds and generalization with unbounded loss functions (2013, background): “3A version of this lemma is stated in [11], but no proof is given.”
Model Selection (2018, background): “…also a considerable body of literature on model selection and related methods in the areas of machine learning and empirical risk minimization, mainly focusing on classification and pattern recognition problems; see, e.g., Boucheron, Bousquet, and Lugosi (2005), and Cesa-Bianchi and Lugosi (2006).”
Group Invariance, Stability to Deformations, and Complexity of Deep Convolutional Representations (2017, neutral): “Additionally, the RKHS norm provides a way to control model complexity, and can lead to generalization bounds, e.g. , through Rademacher complexity and margin bounds (Boucheron et al., 2005; Shalev-Shwartz and Ben-David, 2014).”