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

stat.ML cs.LG Zhenisbek Assylbekov, Rustem Takhanov · Oct 14, 2026

What it does

Why it matters

This paper demonstrates that Feldman's central conditioning identity fails because the counts of other points convey information about the sampling distribution, and it provides an exact three-point counterexample together with an...

Main concern

The paper rigorously disproves Lemma 2. 1 and Theorem 2.

Community signal

0 up · 0 down

AI Review AI reviewed

Plain-language introduction

Feldman (2021) gave an influential lower bound linking the cost of not fitting training labels to excess population risk via frequency-dependent coefficients $\tau_{n,\ell}$. This paper demonstrates that Feldman's central conditioning identity fails because the counts of other points convey information about the sampling distribution, and it provides an exact three-point counterexample together with an exponentially large multiplicative gap. The authors recover a valid bound within the same model by replacing the count-only coefficient with the exact full-sample posterior mean, which depends on both multiplicity and the complete frequency profile.

Critical review

Verdict

Bottom line

The paper rigorously disproves Lemma 2.1 and Theorem 2.3 of Feldman (2021). The exact three-point counterexample ($N=n=3$) with independent fair labels and a permutation-equivariant learner violates the claimed inequality, and Theorem 3 shows the ratio of the original penalty to actual excess risk can grow as $\frac{2}{15}(4/3)^n$, ruling out any universal positive constant-factor repair. The authors then recover a valid lower bound within the same normalized-weight model by replacing the count-only coefficient $\tau_{n,\ell}$ with the exact full-sample posterior mean $q_x(Z)$.

“Lemma 2.1, proved through Lemma A.1, identifies the full-sample posterior mass with the count-only coefficient. Our counterexample disproves that identity and both forms of Theorem 2.3.”

Assylbekov & Takhanov · Section 7

“Consequently, no constant c > 0, independent of the frequency list and sample size, makes R(A) - R^* >= c sum_l tau_{n,l} E[B_l(A,S)] valid for all such models and learners.”

Assylbekov & Takhanov · Theorem 3

What holds up

The counterexample in Section 3 is exceptionally clean and checkable by hand via exact arithmetic over eight raw-weight configurations. The corrected exact posterior decomposition (Theorem 4) is tight pointwise: for any observed point $x$, a learner can concentrate its entire excess risk on $x$, so the coefficient $q_x(Z)$ cannot be increased without violating universality.

“Equality in that lower bound is achieved by every learner that makes posterior-optimal predictions on unseen points.”

Assylbekov & Takhanov · Theorem 4

“For any chosen observed point x, a learner can make a deliberate error only at x and use optimal predictions everywhere else. Its excess risk is exactly q_x(Z).”

Assylbekov & Takhanov · Section 5

Main concerns

The exponential failure mode uses a sample-size-dependent prior $\pi^{(n)}$, which correctly rules out a universal constant multiplier but does not imply the bound fails for any fixed long-tailed distribution of practical interest. The corrected coefficients depend on the full frequency profile rather than just multiplicity, making them harder to compute and deploy in downstream analyses; the paper explicitly leaves open the recovery of Feldman's noisy-label, privacy, and subpopulation extensions. Moreover, the corrected bound is fundamentally a lower bound on excess risk for unrestricted learners, so its implications for specific algorithm classes remain indirect.

“The subpopulation extension, Theorem 3.2, also fails when subpopulations are point masses on distinct domain points... We do not analyze the coupling argument for nontrivial subpopulations.”

Assylbekov & Takhanov · Section 7

“The priors vary with sample size, the offending profiles become rare, and both quantities vanish. This is a worst-case multiplicative obstruction, not a fixed-prior asymptotic result or a nonvanishing additive gap.”

Assylbekov & Takhanov · Section 4

Evidence and comparison

The evidence directly supports the core claims. The exact-arithmetic certificate in Appendix A makes the three-point counterexample fully verifiable without code. The authors fairly situate their result within the literature, distinguishing their fixed-sample-size, learner-dependent criterion from classical Dirichlet characterizations (Johnson's sufficientness postulate) and noting that the original $\tau_{n,\ell}$ is an occupancy-weighted average of the corrected profile coefficients. They also responsibly identify which intermediate calculations in Feldman's work survive the correction.

“Thus the finite counterexample can be checked directly from Table 1, without external code.”

Assylbekov & Takhanov · Appendix A

“Corollary 9 instead fixes N, n, and the prior, and characterizes a risk bound valid for every learner using posterior means for positive counts only. Without conditions across sample sizes or for unseen categories, it implies neither a Dirichlet characterization nor uniqueness of the prior.”

Assylbekov & Takhanov · Section 6.3

Reproducibility

The paper provides enough detail for independent reproduction of the central results. The counterexample requires only evaluating eight normalized vectors with rational weights, supported by an exact-arithmetic certificate. For general priors, Proposition 10 reduces the corrected coefficients to one-dimensional integrals, and the authors report quadrature cross-checks with discrepancies below $10^{-15}$. However, no source code or data repository is referenced, and the exponentially large gap relies on careful asymptotic leading-term analysis whose finite-$n$ values (e.g., $n=32$ giving ratio $\approx 1234.9$) are given but not accompanied by runnable scripts.

“With absolute and relative quadrature tolerances 10^{-12}, the maximum observed discrepancy over all six feasible profile--multiplicity pairs was at most 1.2 x 10^{-16}.”

Assylbekov & Takhanov · Appendix C

“Taking the corresponding ratios yields (6) and (7). Thus the finite counterexample can be checked directly from Table 1, without external code.”

Assylbekov & Takhanov · Appendix A

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.

Challenge the Review

Pick a starting point or write your own. Challenges run in the background, so you can keep reading while the AI investigates.

Challenges are public to read, but only signed-in members can post them. Your challenge text is stored with your account for moderation, but usernames are not shown in the public thread.

No challenges yet. Disagree with the review? Ask the AI to revisit a specific claim.