Track papers across labs, topics, and trends.
Search papers, labs, and topics across Lattice.
We provide a three-point counterexample to Feldman's memorization lower bound using a permutation-equivariant learner and independent fair labels, demonstrating that its conditional and averaged forms can be arbitrarily inaccurate. By introducing sampling priors that vary with sample size, we show that the ratio of the proposed penalty to actual excess risk can grow exponentially, invalidating a universal constant-factor repair. An exact replacement is derived using full-sample posterior probabilities, which depend on multiplicity and the complete frequency profile under exchangeability, and we characterize the largest multiplicity-only coefficients for unrestricted learners.
Feldman's memorization lower bound can be arbitrarily inaccurate, but a corrected version using full-sample posterior probabilities offers an exact replacement.
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.