# Sequential prediction under log-loss and misspecification

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 6 of its 33 references that are in the map.
- First posted on arXiv 29 Jan 2021.

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

- [Fast Rates for General Unbounded Loss Functions: from ERM to Generalized Bayes](https://mlsanity.com/paper/1605.00252/) (2016)
- [Online Nonparametric Regression with General Loss Functions](https://mlsanity.com/paper/1501.06598/) (2015)
- [Sequential Probability Assignment with Binary Alphabets and Large Classes of Experts](https://mlsanity.com/paper/1501.07340/) (2015)
- [Learning, compression, and leakage: Minimising classification error via meta-universal compression principles](https://mlsanity.com/paper/2010.07382/) (2020)
- [Universal Supervised Learning for Individual Data](https://mlsanity.com/paper/1812.09520/) (2018)
- [Horizon-Independent Optimal Prediction with Log-Loss in Exponential Families](https://mlsanity.com/paper/1305.4324/) (2013)

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

- [Universal Batch Learning Under The Misspecification Setting](https://mlsanity.com/paper/2405.07252/) (2024)
- [How Wrong Can a Good Predictor Be? Diverging Updates with Vanishing Predictive KL](https://mlsanity.com/paper/2609.11132/) (2026)

## Abstract (arXiv)

We consider the question of sequential prediction under the log-loss in terms of cumulative regret. Namely, given a hypothesis class of distributions, learner sequentially predicts the (distribution of the) next letter in sequence and its performance is compared to the baseline of the best constant predictor from the hypothesis class. The well-specified case corresponds to an additional assumption that the data-generating distribution belongs to the hypothesis class as well. Here we present results in the more general misspecified case. Due to special properties of the log-loss, the same problem arises in the context of competitive-optimality in density estimation, and model selection. For the d-dimensional Gaussian location hypothesis class, we show that cumulative regrets in the well-specified and misspecified cases asymptotically coincide. In other words, we provide an o(1) characterization of the distribution-free (or PAC) regret in this case -- the first such result as far as we know. We recall that the worst-case (or individual-sequence) regret in this case is larger by an additive constant dover 2 + o(1). Surprisingly, neither the traditional Bayesian estimators, nor the Shtarkov's normalized maximum likelihood achieve the PAC regret and our estimator requires special "robustification" against heavy-tailed data. In addition, we show two general results for misspecified regret: the existence and uniqueness of the optimal estimator, and the bound sandwiching the misspecified regret between well-specified regrets with (asymptotically) close hypotheses classes.