# Learning, compression, and leakage: Minimising classification error via meta-universal compression principles

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

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 14 Oct 2020.

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

- [Single Layer Predictive Normalized Maximum Likelihood for Out-of-Distribution Detection](https://mlsanity.com/paper/2110.09246/) (2021)
- [Batch Universal Prediction](https://mlsanity.com/paper/2402.03901/) (2024)
- [Sequential prediction under log-loss and misspecification](https://mlsanity.com/paper/2102.00050/) (2021)
- [Distribution Free Uncertainty for the Minimum Norm Solution of Over-parameterized Linear Regression](https://mlsanity.com/paper/2102.07181/) (2021)
- [The Conditional Regret-Capacity Theorem for Batch Universal Prediction](https://mlsanity.com/paper/2508.10282/) (2025)

## Abstract (arXiv)

Learning and compression are driven by the common aim of identifying and exploiting statistical regularities in data, which opens the door for fertile collaboration between these areas. A promising group of compression techniques for learning scenarios is normalised maximum likelihood (NML) coding, which provides strong guarantees for compression of small datasets - in contrast with more popular estimators whose guarantees hold only in the asymptotic limit. Here we consider a NML-based decision strategy for supervised classification problems, and show that it attains heuristic PAC learning when applied to a wide variety of models. Furthermore, we show that the misclassification rate of our method is upper bounded by the maximal leakage, a recently proposed metric to quantify the potential of data leakage in privacy-sensitive scenarios.