Posterior Frequencies and the Cost of Not Fitting: A Correction to a Memorization Lower Bound
Abstract
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.
Related
- Cross-Fitting for Neural Posterior Estimation
- Model-Based Posterior Correction for Isolating Structurally Indistinguishable Faults
- Small graphs without power-of-two cycles: a lower bound of 24, a correction to a construction of Exoo, and explicit bounds for f(k)
- Valid Early Detection of Memorization in Diffusion Models
- Memorization Capacity of Invariant Convolutional Neural Nets
BibTeX
@misc{assylbekov2026posterior,
title = {{Posterior Frequencies and the Cost of Not Fitting: A Correction to a Memorization Lower Bound}},
author = {Zhenisbek Assylbekov and Rustem Takhanov},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.20402},
eprint = {2610.20402},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.20402},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Posterior Frequencies and the Cost of Not Fitting: A Correction to a Memorization Lower Bound
AU - Zhenisbek Assylbekov
AU - Rustem Takhanov
PY - 2026
DA - 2026/10/14
PB - arXiv
DO - 10.48550/arxiv.2610.20402
UR - https://arxiv.org/abs/2610.20402
AB - 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.
ER -