# Fast Rates for General Unbounded Loss Functions: from ERM to Generalized Bayes

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

## Key facts

- Cited by 27 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 1 May 2016.

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

- [User-friendly introduction to PAC-Bayes bounds](https://mlsanity.com/paper/2110.11216/) (2021)
- [PAC-Bayes, MAC-Bayes and Conditional Mutual Information: Fast rate bounds that handle general VC classes](https://mlsanity.com/paper/2106.09683/) (2021)
- [A Unified Confidence Sequence for Generalized Linear Models, with Applications to Bandits](https://mlsanity.com/paper/2407.13977/) (2024)
- [On PAC-Bayesian reconstruction guarantees for VAEs](https://mlsanity.com/paper/2202.11455/) (2022)
- [On Empirical Risk Minimization with Dependent and Heavy-Tailed Data](https://mlsanity.com/paper/2109.02224/) (2021)
- [The no-free-lunch theorems of supervised learning](https://mlsanity.com/paper/2202.04513/) (2022)
- [Information Complexity and Generalization Bounds](https://mlsanity.com/paper/2105.01747/) (2021)
- [On the Generalization for Transfer Learning: An Information-Theoretic Analysis](https://mlsanity.com/paper/2207.05377/) (2022)
- [Minimax Optimal Quantile and Semi-Adversarial Regret via Root-Logarithmic Regularizers](https://mlsanity.com/paper/2110.14804/) (2021)
- [Bayes meets Bernstein at the Meta Level: an Analysis of Fast Rates in Meta-Learning with PAC-Bayes](https://mlsanity.com/paper/2302.11709/) (2023)
- [PAC-Bayes Bounds for Bandit Problems: A Survey and Experimental Comparison](https://mlsanity.com/paper/2211.16110/) (2022)
- [Fast Rate Generalization Error Bounds: Variations on a Theme](https://mlsanity.com/paper/2205.03131/) (2022)
- [Fast Rate Information-theoretic Bounds on Generalization Errors](https://mlsanity.com/paper/2303.14658/) (2023)
- [Semiparametric inference using fractional posteriors](https://mlsanity.com/paper/2301.08158/) (2023)
- [Contextual Multinomial Logit Bandits with General Value Functions](https://mlsanity.com/paper/2402.08126/) (2024)
- [Sequential prediction under log-loss and misspecification](https://mlsanity.com/paper/2102.00050/) (2021)
- [Partial-Label Learning with Conformal Candidate Cleaning](https://mlsanity.com/paper/2502.07661/) (2025)
- [Demystify Optimization and Generalization of Over-parameterized PAC-Bayesian Learning](https://mlsanity.com/paper/2202.01958/) (2022)
- [Mixed moving average field guided learning for spatio-temporal data](https://mlsanity.com/paper/2301.00736/) (2023)
- [Valid Inference for Machine Learning Model Parameters](https://mlsanity.com/paper/2302.10840/) (2023)
- [Convergence of Statistical Estimators via Mutual Information Bounds](https://mlsanity.com/paper/2412.18539/) (2024)
- [Optimal Learning from Label Proportions with General Loss Functions](https://mlsanity.com/paper/2509.15145/) (2025)
- [Rectifying Regression in Reinforcement Learning](https://mlsanity.com/paper/2510.00885/) (2025)
- [Robust Linear Predictions: Analyses of Uniform Concentration, Fast Rates and Model Misspecification](https://mlsanity.com/paper/2201.01973/) (2022)
- [Robust Online Classification: From Estimation to Denoising](https://mlsanity.com/paper/2309.01698/) (2023)
- [Addressing the Inconsistency in Bayesian Deep Learning via Generalized Laplace Approximation](https://mlsanity.com/paper/2405.13535/) (2024)
- [General Bayesian Policy Learning](https://mlsanity.com/paper/2602.23672/) (2026)

## Abstract (arXiv)

We present new excess risk bounds for general unbounded loss functions including log loss and squared loss, where the distribution of the losses may be heavy-tailed. The bounds hold for general estimators, but they are optimized when applied to η-generalized Bayesian, MDL, and empirical risk minimization estimators. In the case of log loss, the bounds imply convergence rates for generalized Bayesian inference under misspecification in terms of a generalization of the Hellinger metric as long as the learning rate η is set correctly. For general loss functions, our bounds rely on two separate conditions: the v-GRIP (generalized reversed information projection) conditions, which control the lower tail of the excess loss; and the newly introduced witness condition, which controls the upper tail. The parameter v in the v-GRIP conditions determines the achievable rate and is akin to the exponent in the Tsybakov margin condition and the Bernstein condition for bounded losses, which the v-GRIP conditions generalize; favorable v in combination with small model complexity leads to tildeO(1/n) rates. The witness condition allows us to connect the excess risk to an "annealed" version thereof, by which we generalize several previous results connecting Hellinger and R'enyi divergence to KL divergence.