Scaling of model approximation errors and expected entropy distances

Guido F. Montúfar, Johannes RauhKybernetika 2014 · OpenReview

Abstract: We compute the expected value of the Kullback-Leibler divergence to various fundamental statistical models with respect to canonical priors on the probability simplex. We obtain closed formulas for the expected model approximation errors, depending on the dimension of the models and the cardinalities of their sample spaces. For the uniform prior, the expected divergence from any model containing the uniform distribution is bounded by a constant $1-\gamma$, and for the models that we consider, this bound is approached if the state space is very large and the models' dimension does not grow too fast. For Dirichlet priors the expected divergence is bounded in a similar way, if the concentration parameters take reasonable values. These results serve as reference values for more complicated statistical models.

Introduction: Beyond Worst-Case Analysis

In statistical modeling, we often use structures like neural networks or graphical models to approximate complex probability distributions. A central question is how "wrong" these models are. Traditionally, this is measured via the Kullback-Leibler (KL) divergence. Most theoretical work focuses on worst-case analysis, which often suggests that error grows indefinitely as the number of possible outcomes ($N$) increases.

However, this paper demonstrates that worst-case scenarios are often unrepresentative. By calculating the expected error—the average divergence when the "true" distribution is chosen randomly—the authors find that for many fundamental models, the error remains remarkably small and stable, even as the state space scales to infinity.

Methods and Model Classes

The researchers derived closed-form expressions for expected distances using Dirichlet priors to define the distribution of "true" models on the probability simplex. They analyzed several key model classes:

  • Independence Models: Variables are assumed to be independent.
  • Partition Models: Outcomes are grouped into discrete blocks.
  • Decomposable Hierarchical Models: These models can be represented as a "junction tree" of smaller, overlapping components.
A decomposable graph (left) and its corresponding junction tree representation (right), illustrating how complex models are broken down for analysis.

By leveraging the aggregation properties of Dirichlet distributions, the authors were able to solve complex integrals to find exact formulas for the expected KL divergence from these models to the true distribution.

Key Insights: The Stability of Error

The most significant finding is the existence of a "magic constant." For a uniform prior, the expected divergence from any model containing the uniform distribution is bounded by $1 - \gamma \approx 0.4228$, where $\gamma$ is the Euler-Mascheroni constant.

This result implies scale invariance: as long as a model's dimension remains relatively small, its average approximation error does not explode as the state space grows. While the worst-case error might grow logarithmically ($\log N$), the average case stays flat. This suggests that the "bad" distributions that are difficult for these models to approximate are statistically rare.

Results and Numerical Verification

The paper provides exact theorems for expected entropy and divergence. For symmetric Dirichlet priors with parameter $a$, the error is approximately $h(a) - \log(a) - \gamma$. For independence and decomposable models, the paper proves that as the number of elementary events $N \to \infty$, the expected divergence converges exactly to $1 - \gamma$.

Numerical simulations involving tens of thousands of sampled distributions confirmed these theoretical limits, showing that different model architectures and prior parameters converge to predictable horizontal asymptotes as system size increases.

Limitations and Future Directions

While these results offer a more optimistic view of model performance, they rely on the choice of a Dirichlet prior. Real-world data often possesses more complex structures—such as sparsity or clustering—that a uniform or symmetric Dirichlet prior may not fully capture. Furthermore, while the authors conjecture these bounds apply to more complex architectures like Restricted Boltzmann Machines (RBMs), formal proofs for deep, non-linear models remain a subject for future research.

Summary updated

Abstract

We compute the expected value of the Kullback-Leibler divergence of various fundamental statistical models with respect to Dirichlet priors. For the uniform prior, the expected divergence of any model containing the uniform distribution is bounded by a constant $1-\gamma$. For the models that we consider this bound is approached as the cardinality of the sample space tends to infinity, if the model dimension remains relatively small. For Dirichlet priors with reasonable concentration parameters the expected values of the divergence behave in a similar way. These results serve as a reference to rank the approximation capabilities of other statistical models.
BibTeX
@inproceedings{montufar2014scaling,
  author = {Guido F. Montúfar and Johannes Rauh},
  title = {{Scaling of model approximation errors and expected entropy distances}},
  booktitle = {Kybernetika},
  year = {2014},
  url = {https://openreview.net/forum?id=DykTDS5HfF6},
}
Figure