# Posterior Frequencies and the Cost of Not Fitting: A Correction to a Memorization Lower Bound

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 2 of its 4 references that are in the map.
- First posted on arXiv 14 Oct 2026.

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

- [Does Learning Require Memorization? A Short Tale about a Long Tail](https://mlsanity.com/paper/1906.05271/) (2019)
- [Defining Predictive Probability Functions for Species Sampling Models](https://mlsanity.com/paper/1306.2503/) (2013)

## Abstract (arXiv)

Feldman's memorization lower bound assigns a frequency coefficient based on how often a point appears in the training sample. We give an exact three-point counterexample to its conditional and averaged forms, using independent fair labels and a permutation-equivariant learner. A sequence of sampling priors makes the ratio of the proposed penalty to actual excess risk grow exponentially, ruling out a universal positive constant-factor repair. The priors vary with sample size, the offending profiles become rare, and both quantities vanish. Retaining the original model, we obtain an exact replacement using full-sample posterior probabilities. Under exchangeability, these depend on multiplicity and the complete frequency profile. We characterize the largest multiplicity-only coefficients valid for unrestricted learners. The original coefficient has the posterior-mean form of Good's exact frequency formula and is an occupancy-weighted average of the corrected coefficients.