Fast rates in structured prediction
arXiv:2102.00760
Abstract
Discrete supervised learning problems such as classification are often tackled by introducing a continuous surrogate problem akin to regression. Bounding the original error, between estimate and solution, by the surrogate error endows discrete problems with convergence rates already shown for continuous instances. Yet, current approaches do not leverage the fact that discrete problems are essentially predicting a discrete output when continuous problems are predicting a continuous value. In this paper, we tackle this issue for general structured prediction problems, opening the way to "super fast" rates, that is, convergence rates for the excess risk faster than , where is the number of observations, with even exponential rates with the strongest assumptions. We first illustrate it for predictors based on nearest neighbors, generalizing rates known for binary classification to any discrete problem within the framework of structured prediction. We then consider kernel ridge regression where we improve known rates in to arbitrarily fast rates, depending on a parameter characterizing the hardness of the problem, thus allowing, under smoothness assumptions, to bypass the curse of dimensionality.
arXiv comment14 main pages, 3 main figures, 43 pages, 4 figures (with appendix)
References in corpus (9)
- Fast learning rates for plug-in classifiers
- Risk bounds for statistical learning
- Rates of Convergence for Nearest Neighbor Classification
- Optimal Rates for Spectral Algorithms with Least-Squares Regression over Hilbert Spaces
- Statistical Optimality of Stochastic Gradient Descent on Hard Learning Problems through Multiple Passes
- A Consistent Regularization Approach for Structured Prediction
- A General Theory for Structured Prediction with Smooth Convex Surrogates
- Sharp Analysis of Learning with Discrete Losses
- Beyond Least-Squares: Fast Rates for Regularized Empirical Risk Minimization through Self-Concordance