Fast learning rates for plug-in classifiers

Abstract

It has been recently shown that, under the margin (or low noise) assumption, there exist classifiers attaining fast rates of convergence of the excess Bayes risk, that is, rates faster than $n^{-1/2}$. The work on this subject has suggested the following two conjectures: (i) the best achievable fast rate is of the order $n^{-1}$, and (ii) the plug-in classifiers generally converge more slowly than the classifiers based on empirical risk minimization. We show that both conjectures are not correct. In particular, we construct plug-in classifiers that can achieve not only fast, but also super-fast rates, that is, rates faster than $n^{-1}$. We establish minimax lower bounds showing that the obtained rates cannot be improved.

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

References in corpus (7)

• 2004 IMS Medallion Lecture: Local Rademacher complexities and oracle inequalities in risk minimization
• Fast learning rates for plug-in classifiers
• Fast rates for support vector machines using Gaussian kernels
• Risk bounds for statistical learning
• Statistical performance of support vector machines
• Square Root Penalty: Adaptation to the Margin in Classification and in Edge Estimation
• Fast learning rates for plug-in classifiers under the margin condition

Cited by in corpus (90)

• Fast learning rates for plug-in classifiers
• Choice of neighbor order in nearest-neighbor classification
• Optimal weighted nearest neighbour classifiers
• Statistical inference for the mean outcome under a possibly non-unique optimal treatment strategy
• Least Ambiguous Set-Valued Classifiers with Bounded Error Levels
• The multi-armed bandit problem with covariates
• Generalization error bounds in semi-supervised classification under the cluster assumption
• Optimal rates for plug-in estimators of density level sets
• Fast learning rates in statistical inference through aggregation
• Generalized density clustering
• Rates of Convergence for Nearest Neighbor Classification
• Exponential Regret Bounds for Gaussian Process Bandits with Deterministic Observations
• Quantum learning: optimal classification of qubit states
• Selection of variables and dimension reduction in high-dimensional non-parametric regression
• Sensitivity analysis via the proportion of unmeasured confounding
• Simultaneous adaptation to the margin and to complexity in classification
• Instance-Dependent Complexity of Contextual Bandits and Reinforcement Learning: A Disagreement-Based Perspective
• Asymptotic distribution and sparsistency for l1-penalized parametric M-estimators with applications to linear SVM and logistic regression
• Surrogate Losses in Passive and Active Learning
• Minimax fast rates for discriminant analysis with errors in variables
• Statistical Inference for Online Decision Making via Stochastic Gradient Descent
• Statistical Inference of the Value Function for Reinforcement Learning in Infinite Horizon Settings
• Optimal rates of aggregation in classification under low noise assumption
• Transfer Learning for Nonparametric Classification: Minimax Rate and Adaptive Classifier
• PAC-Bayesian aggregation and multi-armed bandits
• Class-Weighted Classification: Trade-offs and Robust Approaches
• Optimal classification and nonparametric regression for functional data
• An adaptive nearest neighbor rule for classification
• Classification under local differential privacy
• Feature Selection For High-Dimensional Clustering
• PAC-Bayesian High Dimensional Bipartite Ranking
• Fairness-aware Model-agnostic Positive and Unlabeled Learning
• Efficient First-Order Contextual Bandits: Prediction, Allocation, and Triangular Discrimination
• Classification algorithms using adaptive partitioning
• Minimax Rate Optimal Adaptive Nearest Neighbor Classification and Regression
• Principled analytic classifier for positive-unlabeled learning via weighted integral probability metric
• Universal consistency and rates of convergence of multiclass prototype algorithms in metric spaces
• A General Theory for Structured Prediction with Smooth Convex Surrogates
• Under-bagging Nearest Neighbors for Imbalanced Classification
• Smooth Contextual Bandits: Bridging the Parametric and Non-differentiable Regret Regimes
• Active Learning for Binary Classification with Abstention
• Fast Rates for Contextual Linear Optimization
• Nearest Neighbor and Kernel Survival Analysis: Nonasymptotic Error Bounds and Strong Consistency Rates
• Margin-adaptive model selection in statistical learning
• Classification with abstention but without disparities
• Binary Classification with Bounded Abstention Rate
• Neyman-Pearson Multi-class Classification via Cost-sensitive Learning
• Error Scaling Laws for Kernel Classification under Source and Capacity Conditions
• Fast Rates for the Regret of Offline Reinforcement Learning
• Classification with the nearest neighbor rule in general finite dimensional spaces: necessary and sufficient conditions
• Disambiguation of weak supervision with exponential convergence rates
• Minimax-Optimal Bounds for Detectors Based on Estimated Prior Probabilities
• Local High-order Regularization on Data Manifolds
• Classification with unknown class-conditional label noise on non-compact feature spaces
• Nearest neighbor density functional estimation from inverse Laplace transform
• A Generalized Neyman-Pearson Criterion for Optimal Domain Adaptation
• On Convergence of Nearest Neighbor Classifiers over Feature Transformations
• Improved Classification Rates for Localized SVMs
• Deep k-NN for Noisy Labels
• Discussion of ``2004 IMS Medallion Lecture: Local Rademacher complexities and oracle inequalities in risk minimization'' by V. Koltchinskii
• Functional Sequential Treatment Allocation with Covariates
• Fast rates in structured prediction
• A Computationally Efficient Classification Algorithm in Posterior Drift Model: Phase Transition and Minimax Adaptivity
• Self-Tuning Bandits over Unknown Covariate-Shifts
• Classification in postural style
• An adaptive multiclass nearest neighbor classifier
• Semiparametric Gaussian copula classification
• Minimax optimal high-dimensional classification using deep neural networks
• Classification of sparse binary vectors
• Predictive Power of Nearest Neighbors Algorithm under Random Perturbation
• Jump Interval-Learning for Individualized Decision Making
• Multiclass Classification via Class-Weighted Nearest Neighbors
• Non-asymptotic Excess Risk Bounds for Classification with Deep Convolutional Neural Networks
• K-NN active learning under local smoothness assumption
• Nonparametric adaptive active learning under local smoothness condition
• Exponential Convergence Rates of Classification Errors on Learning with SGD and Random Features
• Neural Neighborhood Encoding for Classification
• Finding the Optimal Dynamic Treatment Regime Using Smooth Fisher Consistent Surrogate Loss
• Posterior concentration and fast convergence rates for generalized Bayesian learning
• Individually Fair Gradient Boosting
• Statistical Guarantees for Fairness Aware Plug-In Algorithms
• DTR Bandit: Learning to Make Response-Adaptive Decisions With Low Regret
• VC dimension of partially quantized neural networks in the overparametrized regime
• Stochastic Gradient Descent with Exponential Convergence Rates of Expected Classification Errors
• Regularized ERM on random subspaces
• Distributed Adaptive Nearest Neighbor Classifier: Algorithm and Theory
• Harmless interpolation in regression and classification with structured features
• Nonparametric Confidence Regions for Level Sets: Statistical Properties and Geometry
• Noisy classification with boundary assumptions
• Optimal rates for F-score binary classification