Risk bounds for statistical learning
arXiv:math/0702683 · doi:10.1214/009053606000000786
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.
arXiv commentPublished 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 (95)
- 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: -estimation
- Simultaneous adaptation to the margin and to complexity in classification
- Rates of convergence in active learning
- Fast learning rates for plug-in classifiers under the margin condition
- 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
- Efficient active learning of sparse halfspaces with arbitrary bounded noise
- A Survey on Cost Types, Interaction Schemes, and Annotator Performance Models in Selection Algorithms for Active Learning in Classification
- 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
- Empirical risk minimization is optimal for the convex aggregation problem
- PAC-Bayesian aggregation and multi-armed bandits
- Calibrated Surrogate Losses for Adversarially Robust Classification
- General nonexact oracle inequalities for classes with a subexponential envelope
- Sharper lower bounds on the performance of the empirical risk minimization algorithm
- 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
- Lecture Notes: Selected topics on robust statistical learning theory
- Classification algorithms using adaptive partitioning
- Robustness of shape-restricted regression estimators: an envelope perspective
- Exponential Savings in Agnostic Active Learning through Abstention
- Learning Halfspaces with Massart Noise Under Structured Distributions
- Learn to Expect the Unexpected: Probably Approximately Correct Domain Generalization
- Kernel Truncated Randomized Ridge Regression: Optimal Rates and Low Noise Acceleration
- Margin-adaptive model selection in statistical learning
- Fast Rates for Contextual Linear Optimization
- Fast Rates for Online Prediction with Abstention
- Risk Bounds for CART Classifiers under a Margin Condition
- Convergence rates of least squares regression estimators with heavy-tailed errors
- The Power of Comparisons for Actively Learning Linear Classifiers
- Beyond Perturbations: Learning Guarantees with Arbitrary Adversarial Test Examples
- Risk Bounds and Calibration for a Smart Predict-then-Optimize Method
- Variable selection through CART
- Towards Optimal Problem Dependent Generalization Error Bounds in Statistical Learning Theory
- Efficient Learning of Linear Separators under Bounded Noise
- Learnability with Indirect Supervision Signals
- DeepNNK: Explaining deep models and their generalization using polytope interpolation
- Structure-aware error bounds for linear classification with the zero-one loss
- Agnostic Learning of Halfspaces with Gradient Descent via Soft Margins
- A Compression Technique for Analyzing Disagreement-Based Active Learning
- Attribute-Efficient Learning of Halfspaces with Malicious Noise: Near-Optimal Label Complexity and Noise Tolerance
- From Stochastic Mixability to Fast Rates
- Model Selection in Utility-Maximizing Binary Prediction
- Noise-tolerant, Reliable Active Classification with Comparison Queries
- Refined Error Bounds for Several Learning Algorithms
- Fast rates in structured prediction
- A Multiclass Classification Approach to Label Ranking
- Optimal oracle inequalities for solving projected fixed-point equations
- Boosting in the Presence of Massart Noise
- Bandwidth selection in kernel empirical risk minimization via the gradient
- Convergence of Uncertainty Sampling for Active Learning
- Non-asymptotic Excess Risk Bounds for Classification with Deep Convolutional Neural Networks
- Statistical optimality conditions for compressive ensembles
- On the Power of Localized Perceptron for Label-Optimal Learning of Halfspaces with Adversarial Noise
- Estimating the Fundamental Limits is Easier than Achieving the Fundamental Limits
- Forster Decomposition and Learning Halfspaces with Noise
- Self-Training of Halfspaces with Generalization Guarantees under Massart Mislabeling Noise Model
- K-NN active learning under local smoothness assumption
- Exact upper and lower bounds on the misclassification probability
- ReLU Regression with Massart Noise
- Finding the Optimal Dynamic Treatment Regime Using Smooth Fisher Consistent Surrogate Loss
- Minimax bounds for structured prediction
- Regularized ERM on random subspaces
- Noisy classification with boundary assumptions
- Statistical learning with indirect observations
- Fast rate of convergence in high dimensional linear discriminant analysis
- Improving Generalization Bounds for VC Classes Using the Hypergeometric Tail Inversion
- Provable Generalization of SGD-trained Neural Networks of Any Width in the Presence of Adversarial Label Noise
- Optimal rates for F-score binary classification
- On the ERM Principle with Networked Data
- A local maximal inequality under uniform entropy
- Fundamentals for Binary Classification Under Label Noise
- Robust testing of low-dimensional functions
- Robust Learning under Strong Noise via SQs
- K-nn active learning under local smoothness condition
- Near-Optimal Statistical Query Hardness of Learning Halfspaces with Massart Noise
- A MOM-based ensemble method for robustness, subsampling and hyperparameter tuning
- Improved Algorithms for Efficient Active Learning Halfspaces with Massart and Tsybakov noise
- Sample-Optimal PAC Learning of Halfspaces with Malicious Noise