Risk bounds for statistical learning

Abstract

We propose a general theorem providing upper bounds for the risk of an empirical risk minimizer (ERM).We essentially focus on the binary classification framework. We extend Tsybakov's analysis of the risk of an ERM under margin type conditions by using concentration inequalities for conveniently weighted empirical processes. This allows us to deal with ways of measuring the ``size'' of a class of classifiers other than entropy with bracketing as in Tsybakov's work. In particular, we derive new risk bounds for the ERM when the classification rules belong to some VC-class under margin conditions and discuss the optimality of these bounds in a minimax sense.

Published at http://dx.doi.org/10.1214/009053606000000786 in the Annals of Statistics (http://www.imstat.org/aos/) by the Institute of Mathematical Statistics (http://www.imstat.org)

Cited by in corpus (92)

• Fast learning rates for plug-in classifiers
• Statistical performance of support vector machines
• Concentration inequalities and asymptotic results for ratio type empirical processes
• Decision-Focused Learning: Foundations, State of the Art, Benchmark and Future Opportunities
• Ranking the best instances
• Robust empirical mean Estimators
• A Contextual Bandit Bake-off
• Activized Learning: Transforming Passive to Active with Improved Label Complexity
• Distribution-Independent PAC Learning of Halfspaces with Massart Noise
• A new method for estimation and model selection: $\rho$-estimation
• Rates of convergence in active learning
• Discussion of ``2004 IMS Medallion Lecture: Local Rademacher complexities and oracle inequalities in risk minimization'' by V. Koltchinskii
• Minimal penalties and the slope heuristics: a survey
• Learning with Bounded Instance- and Label-dependent Label Noise
• Two Simple Ways to Learn Individual Fairness Metrics from Data
• Gibbs posterior concentration rates under sub-exponential type losses
• Sample Complexity of Sample Average Approximation for Conditional Stochastic Optimization
• Finite-sample Analysis of Interpolating Linear Classifiers in the Overparameterized Regime
• A Survey on Cost Types, Interaction Schemes, and Annotator Performance Models in Selection Algorithms for Active Learning in Classification
• Efficient active learning of sparse halfspaces with arbitrary bounded noise
• Minimax fast rates for discriminant analysis with errors in variables
• Nonasymptotic bounds for vector quantization in Hilbert spaces
• Optimal rates of aggregation in classification under low noise assumption
• PAC-Bayesian aggregation and multi-armed bandits
• Empirical risk minimization is optimal for the convex aggregation problem
• Calibrated Surrogate Losses for Adversarially Robust Classification
• Sharper lower bounds on the performance of the empirical risk minimization algorithm
• General nonexact oracle inequalities for classes with a subexponential envelope
• Classification Under Misspecification: Halfspaces, Generalized Linear Models, and Connections to Evolvability
• A Polynomial Time Algorithm for Learning Halfspaces with Tsybakov Noise
• Knowledge Distillation in Wide Neural Networks: Risk Bound, Data Efficiency and Imperfect Teacher
• Classification algorithms using adaptive partitioning
• Lecture Notes: Selected topics on robust statistical learning theory
• Robustness of shape-restricted regression estimators: an envelope perspective
• Learning Halfspaces with Massart Noise Under Structured Distributions
• Exponential Savings in Agnostic Active Learning through Abstention
• Margin-adaptive model selection in statistical learning
• Kernel Truncated Randomized Ridge Regression: Optimal Rates and Low Noise Acceleration
• Fast Rates for Contextual Linear Optimization
• Learn to Expect the Unexpected: Probably Approximately Correct Domain Generalization
• Fast Rates for Online Prediction with Abstention
• Convergence rates of least squares regression estimators with heavy-tailed errors
• The Power of Comparisons for Actively Learning Linear Classifiers
• Risk Bounds for CART Classifiers under a Margin Condition
• Variable selection through CART
• Risk Bounds and Calibration for a Smart Predict-then-Optimize Method
• Beyond Perturbations: Learning Guarantees with Arbitrary Adversarial Test Examples
• Towards Optimal Problem Dependent Generalization Error Bounds in Statistical Learning Theory
• Efficient Learning of Linear Separators under Bounded Noise
• DeepNNK: Explaining deep models and their generalization using polytope interpolation
• Learnability with Indirect Supervision Signals
• Model Selection in Utility-Maximizing Binary Prediction
• From Stochastic Mixability to Fast Rates
• A Compression Technique for Analyzing Disagreement-Based Active Learning
• Structure-aware error bounds for linear classification with the zero-one loss
• Noise-tolerant, Reliable Active Classification with Comparison Queries
• Agnostic Learning of Halfspaces with Gradient Descent via Soft Margins
• Attribute-Efficient Learning of Halfspaces with Malicious Noise: Near-Optimal Label Complexity and Noise Tolerance
• Refined Error Bounds for Several Learning Algorithms
• A Multiclass Classification Approach to Label Ranking
• Optimal oracle inequalities for solving projected fixed-point equations
• Fast rates in structured prediction
• Bandwidth selection in kernel empirical risk minimization via the gradient
• Boosting in the Presence of Massart Noise
• Estimating the Fundamental Limits is Easier than Achieving the Fundamental Limits
• Non-asymptotic Excess Risk Bounds for Classification with Deep Convolutional Neural Networks
• Convergence of Uncertainty Sampling for Active Learning
• On the Power of Localized Perceptron for Label-Optimal Learning of Halfspaces with Adversarial Noise
• Self-Training of Halfspaces with Generalization Guarantees under Massart Mislabeling Noise Model
• Statistical optimality conditions for compressive ensembles
• K-NN active learning under local smoothness assumption
• Forster Decomposition and Learning Halfspaces with Noise
• Improving Generalization Bounds for VC Classes Using the Hypergeometric Tail Inversion
• Noisy classification with boundary assumptions
• Statistical learning with indirect observations
• Provable Generalization of SGD-trained Neural Networks of Any Width in the Presence of Adversarial Label Noise
• Fast rate of convergence in high dimensional linear discriminant analysis
• Optimal rates for F-score binary classification
• On the ERM Principle with Networked Data
• Robust Learning under Strong Noise via SQs
• Robust testing of low-dimensional functions
• Near-Optimal Statistical Query Hardness of Learning Halfspaces with Massart Noise
• Improved Algorithms for Efficient Active Learning Halfspaces with Massart and Tsybakov noise
• Sample-Optimal PAC Learning of Halfspaces with Malicious Noise
• Minimax bounds for structured prediction
• ReLU Regression with Massart Noise
• K-nn active learning under local smoothness condition
• Finding the Optimal Dynamic Treatment Regime Using Smooth Fisher Consistent Surrogate Loss
• A MOM-based ensemble method for robustness, subsampling and hyperparameter tuning
• Regularized ERM on random subspaces
• Exact upper and lower bounds on the misclassification probability
• A local maximal inequality under uniform entropy