# Fast rates in structured prediction

arXiv: https://arxiv.org/abs/2102.00760 · HTML: https://mlsanity.com/paper/2102.00760/

## Key facts

- Cited by 11 papers in the map (data through 14 Oct 2026).
- Builds on 12 of its 51 references that are in the map.
- First posted on arXiv 1 Feb 2021.

## Builds on (most cited first, 12 of 12)

- [Learning with Fenchel-Young Losses](https://mlsanity.com/paper/1901.02324/) (2019)
- [Sobolev Norm Learning Rates for Regularized Least-Squares Algorithm](https://mlsanity.com/paper/1702.07254/) (2017)
- [Statistical Optimality of Stochastic Gradient Descent on Hard Learning Problems through Multiple Passes](https://mlsanity.com/paper/1805.10074/) (2018)
- [Optimal Rates for Spectral Algorithms with Least-Squares Regression over Hilbert Spaces](https://mlsanity.com/paper/1801.06720/) (2018)
- [Fast rates in statistical and online learning](https://mlsanity.com/paper/1507.02592/) (2015)
- [Rates of Convergence for Nearest Neighbor Classification](https://mlsanity.com/paper/1407.0067/) (2014)
- [A General Framework for Consistent Structured Prediction with Implicit Loss Embeddings](https://mlsanity.com/paper/2002.05424/) (2020)
- [Structured Prediction with Partial Labelling through the Infimum Loss](https://mlsanity.com/paper/2003.00920/) (2020)
- [A Consistent Regularization Approach for Structured Prediction](https://mlsanity.com/paper/1605.07588/) (2016)
- [Beyond Least-Squares: Fast Rates for Regularized Empirical Risk Minimization through Self-Concordance](https://mlsanity.com/paper/1902.03046/) (2019)
- [A General Theory for Structured Prediction with Smooth Convex Surrogates](https://mlsanity.com/paper/1902.01958/) (2019)
- [Sharp Analysis of Learning with Discrete Losses](https://mlsanity.com/paper/1810.06839/) (2018)

## Built on by (most cited first, 11 of 11)

- [The SSL Interplay: Augmentations, Inductive Bias, and Generalization](https://mlsanity.com/paper/2302.02774/) (2023)
- [Online Structured Prediction with Fenchel--Young Losses and Improved Surrogate Regret for Online Multiclass Classification with Logistic Loss](https://mlsanity.com/paper/2402.08180/) (2024)
- [Multiclass learning with margin: exponential rates with no bias-variance trade-off](https://mlsanity.com/paper/2202.01773/) (2022)
- [Sketch In, Sketch Out: Accelerating both Learning and Inference for Structured Prediction with Kernels](https://mlsanity.com/paper/2302.10128/) (2023)
- [Disambiguation of weak supervision with exponential convergence rates](https://mlsanity.com/paper/2102.02789/) (2021)
- [A Case of Exponential Convergence Rates for SVM](https://mlsanity.com/paper/2205.10055/) (2022)
- [Active Labeling: Streaming Stochastic Gradients](https://mlsanity.com/paper/2205.13255/) (2022)
- [Deep Sketched Output Kernel Regression for Structured Prediction](https://mlsanity.com/paper/2406.09253/) (2024)
- [How many samples are needed to leverage smoothness?](https://mlsanity.com/paper/2305.16014/) (2023)
- [Robust Linear Predictions: Analyses of Uniform Concentration, Fast Rates and Model Misspecification](https://mlsanity.com/paper/2201.01973/) (2022)
- [From Weakly Supervised Learning to Active Learning](https://mlsanity.com/paper/2209.11629/) (2022)

## Abstract (arXiv)

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 n-1, where n 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 n-1/4 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.