Asymptotic Log-Loss of Prequential Maximum Likelihood Codes

Peter Grünwald, Steven de RooijCOLT 2005 · DOI

TL;DR

This paper analyzes the "redundancy" of prequential maximum likelihood (ML) codes, a popular method for online prediction and model selection. They discover that unlike other common universal codes, prequential ML codes can exhibit significantly different redundancy rates when the true data distribution doesn't perfectly match the model, potentially leading to worse performance in practical applications.

What Problem Does This Paper Address?

In machine learning and statistics, we often want to model data using a set of candidate models, say $M$. A key challenge is how to quantify how well a model from $M$ can predict new data, especially when the true underlying data-generating distribution, $P$, might not be perfectly represented by any model in $M$ (this is called "misspecification").

One way to measure this is through "redundancy," which essentially quantifies how many extra bits are needed to encode data using a universal code (designed to work well for any model in $M$) compared to the ideal code for the true distribution $P$. Prequential ML codes are a popular choice for this, as they adaptively update their predictions based on past data. While it's known that for many universal codes, the redundancy grows like $\frac{k}{2} \ln n$ (where $k$ is the model dimension and $n$ is the data size) when $P$ is in $M$, this paper investigates what happens when $P$ is not in $M$. They aim to understand the asymptotic behavior of the redundancy in this misspecification scenario.

Methods

The core of the paper is a theoretical analysis of the asymptotic redundancy of prequential ML codes. They derive a precise formula for the redundancy in the case of a single-parameter exponential family model. The key technical tools involve:

  • Taylor expansions: Used to approximate the Kullback-Leibler (KL) divergence between the true distribution and the model's predictions.
  • Asymptotic analysis: Examining the behavior of the redundancy as the number of data points ($n$) goes to infinity.
  • Properties of exponential families: Leveraging the well-understood mathematical structure of exponential families, particularly their sufficient statistics and Fisher information.
  • Careful handling of estimators: The paper addresses the "startup problem" of ML estimators by introducing a "fake initial outcome," which allows for a more robust theoretical analysis and connects the ML estimator to Bayesian MAP and mean estimators.

Datasets

Not discussed in the paper. The paper is a theoretical analysis and does not involve empirical evaluation on specific datasets.

Key Insights and Ideas

  • Misspecification matters: The paper's main finding is that when the true data distribution $P$ is not in the model $M$, the prequential ML code's redundancy can deviate significantly from the standard $\frac{1}{2} \ln n$ rate.
  • Variance is key: The redundancy rate is shown to be proportional to $\frac{\text{var}_P X}{\text{var}_{M_{\mu^*}} X} \ln n$, where $\text{var}_P X$ is the variance of the sufficient statistic under the true distribution $P$, and $\text{var}_{M_{\mu^*}} X$ is the variance under the model distribution $M_{\mu^*}$ that is closest to $P$ in KL divergence. This means the redundancy can be larger or smaller than $\frac{1}{2} \ln n$, depending on the relative variances.
  • Undesirable behavior for model selection: This variable redundancy rate is problematic for MDL (Minimum Description Length) model selection. If one model's redundancy is artificially low due to matching variances, it might be unfairly favored over another model, even if it's not the "true" model.
  • Connection to KL Risk: The results can be re-interpreted as bounds on the asymptotic Kullback-Leibler risk of density estimation. The paper highlights that in-model estimators (like ML) behave fundamentally differently from out-of-model estimators (like Bayesian predictive distributions) under misspecification.

Key Results

The main result (Theorem 1) states that for a single-parameter exponential family $M$ and a data distribution $P$, the relative redundancy $R_U(n)$ of the prequential ML code $U$ is given by:

$R_U(n) = \frac{\text{var}_P X}{2 \text{var}_{M_{\mu^*}} X} \ln n + O(1)$

where $X$ is the sufficient statistic, and $M_{\mu^*}$ is the model in $M$ closest to $P$ in KL divergence.

Theorem 2 shows that the difference between redundancy and expected regret for finite sample spaces converges to $\frac{1}{2} \frac{\text{var}_P X}{\text{var}_{M_{\mu^*}} X}$. This implies that for finite sample spaces, redundancy and regret behave similarly.

Limitations and Future Work

  • Focus on 1-parameter families: The main result is derived for single-parameter exponential families. The authors conjecture that similar behavior holds for general $k$-parameter families but do not prove it.
  • Condition 1: The theorem relies on a technical "Condition 1" related to the derivatives of the KL divergence. While this condition holds for many practical exponential families (e.g., Poisson, Gaussian, Bernoulli) when the fourth moment of $P$ exists, it's a formal requirement.
  • Future Work: The authors express interest in extending the results to general $1$-parameter exponential families with arbitrary sample spaces. They also suggest further investigation into the implications for model selection and the theoretical differences between in-model and out-of-model estimators under misspecification.

Summary updated

BibTeX
@inproceedings{grunwald2005asymptotic,
  author = {Peter Grünwald and Steven de Rooij},
  title = {{Asymptotic Log-Loss of Prequential Maximum Likelihood Codes}},
  booktitle = {Conference on Learning Theory},
  year = {2005},
  doi = {10.1007/11503415\_44},
}
Figure