Memorization Lower Bound Overturned: Posterior Frequencies Yield Exact Correction

In machine learning theory, there is a widely cited conclusion: the more frequently a sample appears in the training set, the smaller the "memorization penalty" for the model remembering it. Feldman's memorization lower bound is built on this intuition, using a frequency coefficient to characterize this relationship. However, a recent corrective study provides an exact three-point counterexample, proving that this coefficient fails in both its conditional and average forms.

The Three-Point Counterexample: When the Frequency Coefficient Fails

The core construction of the study is remarkably simple: it uses independent fair labels (each sampled label is positive or negative with equal probability) and a permutation-equivariant learner. Under this setting, the authors provide a counterexample consisting of only three points, which is sufficient to simultaneously break both the conditional and average forms of Feldman's lower bound.

Permutation equivariance means that the learner's output does not depend on the ordering of the training samples, which rules out the possibility of "remembering the order" to cheat. Independent fair labels guarantee that the sample labels contain no learnable signal. In this cleanest symmetric scenario, a systematic discrepancy emerges between the penalty estimate given by the original frequency coefficient and the actual excess risk.

The significance of this counterexample is not that it identifies an edge case, but that it shows the coefficient is not a universally valid quantity.

Memorization in machine learning theory refers to a learner's "remembering" behavior toward a particular sample in the training set—that is, once the sample is included in training, it can still be correctly predicted or influence the model's output at test time. Feldman's memorization lower bound attempts to quantify the cost of this memorization: the more frequently a sample appears in the training set, the smaller the additional generalization risk the model must bear for "remembering it." Permutation equivariance means that the learner's output is insensitive to the ordering of the training samples—regardless of the order in which the samples are fed in, the output is the same. This property is often used to rule out the possibility that a learner gains an advantage by remembering the order of samples rather than their content. Independent fair labels means that each sample's label is independently sampled from an equal-probability distribution, ensuring that there is no exploitable regularity in the data. Together, these three elements constitute the simplest symmetric scenario for the counterexample.

Exponential Gap: Why No Constant-Factor Fix Exists

Going further, the authors construct a family of sampling priors such that the ratio between the "proposed penalty" and the "actual excess risk" grows exponentially with sample size. This directly rules out the possibility of patching the original formula with some universal positive constant factor—no fixed constant multiplier can simultaneously approximate the true risk under all priors.

As sample size increases, these priors make the "problematic frequency profiles" increasingly rare, so both the penalty and the actual risk tend toward zero. But the key point is that their ratio does not relax: one quantity approaching zero divided by another quantity approaching zero can diverge exponentially. This is precisely the mechanism by which the original coefficient fails in the asymptotic sense.

In other words, the problem is not that the coefficient is miscalculated at a few points, but that its structure cannot adapt to the distribution of frequency profiles as sample size changes.

Sampling prior here refers to an assumption or weight distribution about the data-generating distribution, which determines the probability of different frequency profiles (i.e., the distributional shape of how many times different points appear in the sample). Frequency profile describes how many times each distinct sample point appears in the training set—for example, "one point appears 3 times, another appears 1 time." Excess risk is the difference between the model's risk on the test set and the optimal Bayes risk, measuring the additional generalization loss the model incurs due to memorization. Constant-factor fix means multiplying the penalty term in the original formula by a fixed positive number so that it is closer to the true risk in all cases. The exponential gap shows that no such constant multiplier can maintain approximation simultaneously under all priors, because the required ratio itself diverges as sample size grows.

Exact Replacement: Rebuilding the Formula with Full-Sample Posterior Probabilities

The authors do not overturn Feldman's overall model framework. Instead, while retaining the original model, they provide an exact replacement quantity: using full-sample posterior probabilities to compute the penalty.

Under the exchangeability assumption, these posterior probabilities depend only on the sample's multiplicity and the complete frequency profile. Exchangeability is a natural assumption—it requires the joint distribution to be insensitive to the ordering of samples, echoing the permutation-equivariant learner mentioned earlier.

Under this framework, the penalty term is no longer a linear function of a single frequency, but a function of the entire frequency profile. This explains why looking only at how many times a certain point appears is insufficient: whether a point is remembered depends on the occurrence pattern of all points in the entire sample.

Exchangeability is a core concept in probability theory, requiring that the joint distribution of a set of random variables be invariant under any permutation—that is, the joint distribution of the samples depends only on their multiset, not their order. Multiplicity refers to the number of times a particular sample point appears in the training set. Under the full-sample posterior probability framework, the penalty depends not only on a single frequency but must integrate the occurrence patterns of all sample points. The Good exact frequency formula originates from Good's (1953) work on probability smoothing; it gives an exact estimate of the probability of a new event given that certain events have been observed, in a form involving the posterior expectation of the number of unobserved species. This article proves that Feldman's coefficient is precisely the posterior mean form of this formula, thereby placing the original lower bound within a more precise statistical estimation framework.

Upper Bound on Multiplicity Coefficients: The Limit of Unrestricted Learners

The study further characterizes the maximum range over which coefficients depending only on multiplicity remain valid for unrestricted learners. This is a conclusion with practical guidance: if you want the coefficient to depend only on how many times a certain point appears, then the class of learners it can cover has a clear boundary.

Beyond this boundary, complete frequency profile information must be introduced; otherwise, the coefficient cannot be guaranteed to be valid. This provides a clear trade-off criterion for designing memorization measures in practice—either accept the applicability limits of multiplicity coefficients, or pay additional computational and statistical costs for more general learners.

The True Identity of the Original Coefficient: The Posterior Mean of Good's Formula

The most elegant part is the authors' reinterpretation of the original frequency coefficient. They prove that the coefficient used by Feldman is actually the posterior mean form of the Good exact frequency formula, and can be written as an occupancy-weighted average of the corrected coefficient.

This explains why the original coefficient behaves as if it were correct in many scenarios: it is a weighted average of the correct quantity, and it approximates well when the frequency profile distribution is concentrated. When the distribution becomes dispersed and rare profiles begin to dominate, this average deviates from the true value; the counterexample and exponential gap are precisely the result of this deviation being amplified.

From a theoretical perspective, this correction does not negate Feldman's work, but places it within a more precise framework: the original coefficient is an approximation of the corrected coefficient under a specific weighting, and its validity depends on the shape of the frequency profile distribution.

Posterior mean refers to taking the expectation of an unknown parameter under the Bayesian framework given observed data. The posterior mean form of Good's formula means that the original frequency coefficient can be understood as the result of averaging the corrected coefficient under some posterior distribution, conditional on the frequency profile. Occupancy-weighted average means that the weight depends on the frequency with which each frequency value appears in the sample—frequency values that occur more often receive greater weight in the average. When the frequency profile distribution is concentrated (i.e., most sample points appear a similar number of times), this weighted average approximates well; when the distribution is dispersed and a few rare profiles dominate, the average deviates from the true corrected coefficient, causing the original lower bound to fail. This interpretation provides a new theoretical positioning for Feldman's original work.

One-line Summary

A recent study uses a three-point counterexample to prove that the frequency coefficient in Feldman's memorization lower bound fails in both conditional and average forms, and provides an exact replacement based on full-sample posterior probabilities.

Paragraph Summary

This article introduces a corrective study of Feldman's memorization lower bound. The original lower bound assumes that the more frequently a sample appears, the smaller the memorization penalty, and introduces a frequency coefficient to characterize this relationship. Using independent fair labels and a permutation-equivariant learner, the authors construct a counterexample with only three points, proving that the coefficient fails in both conditional and average forms. Furthermore, they construct a family of sampling priors such that the ratio of penalty to actual excess risk grows exponentially with sample size, thereby ruling out any universal constant-factor fix. While retaining the original model framework, the authors propose computing the penalty using full-sample posterior probabilities; under the exchangeability assumption, this quantity depends on the complete frequency profile rather than a single frequency. The study also characterizes the maximum range over which multiplicity-only coefficients remain valid for unrestricted learners, and proves that the original coefficient is actually the posterior mean form of the Good exact frequency formula, i.e., an occupancy-weighted average of the corrected coefficient.