Minimax bounds for watermarked and masked recursive discrete distribution estimation

1

Minimax bounds for watermarked and masked recursive discrete distribution estimation Millen Kanabar and Michael Gastpar School of Computer and Communication Sciences, EPFL, Switzerland

arXiv:2608.31091v1 [cs.IT] 31 Aug 2026

Abstract Watermarking has been proposed as a way to identify synthetic samples in estimation settings where no metadata is available to distinguish them from real samples, but its precise effects remain unexplored. In the absence of a distinguishing mechanism, it has been shown that adding synthetic samples significantly reduces the marginal efficacy of new real samples. In this work, we study the minimax loss of such recursive discrete distribution estimation in the presence of watermarks in contrast to the unassisted and oracle-assisted losses. When the fraction of real samples vanishes asymptotically, we provide a lower bound that shows that it is impossible to improve performance by adding watermarks unless the false negative rate of detection also vanishes. Additionally, we show that in most regimes, the worst-case losses of a sequence of simple deterministic estimators match the corresponding lower bounds up to constants. Finally, we propose masking, a randomization procedure that narrows the gap in the remaining regimes to a Jensen gap. We conjecture that a tighter lower bound argument can close this gap.

I. I NTRODUCTION In the generative machine learning literature, model collapse refers to the phenomenon where the underlying distributions of models trained only on their previous generation’s outputs degrade with each iteration. This stands to reason, since finitely many samples disproportionately represent higher-probability outcomes. This leads to increasingly noisy estimates for lowerprobability outcomes, until the output distribution eventually gets corrupted into a point mass by this sampling noise. Accumulating each batch of samples used for training and including fresh real samples in each batch can lead to eventual convergence to the ground truth, so long as real samples do not get ‘lost’ in a sea of synthetic ones. Even so, if synthetic samples are not distinguished from real samples, the reinforcement of higher probability symbols in the empirical distribution of the corpus acts as noise and affects performance. In a previous work, we quantify the effect of this noise in the discrete distribution estimation setting [1] via upper and lower minimax bounds. These bounds show that even in the regime where the expected number of real samples asymptotically grows to infinity, if synthetic sampling outpaces real sampling, the marginal utility of new real samples is greatly reduced. In the literature and in practice, watermarks have been proposed as a mechanism to identify synthetic samples and detect their provenances. When reliable, they can offer a useful way to identify and discard synthetic samples from the corpus. In this work, we use reductions from the watermarking-assisted setting to the unassisted setting studied in our previous work to find conditions where watermarking makes a difference. The problem setting in our work is depicted in Figure 1. New samples added at stage t are assumed to be drawn from the ground truth distribution p with probability αt and from the previous estimate Ppt´1 otherwise. We assume that the mixing factors αt are known to the estimator beforehand. We also assume that samples do not change appreciably with the application of watermarks, and therefore ignore any distortion in the distribution of synthetic samples due to watermarking. This assumption mirrors watermarking in image models, where a small amount of structured noise is added as a watermark. The estimator is equipped with a watermark detector. Since watermarking is not a perfect procedure to identify sample provenance (see e.g. [3], [4]), we model the outcome of the detector as a random variable correlated with the provenance of the sample with known output distributions given whether it is real or synthetic. This subsumes both detectors that provide a ‘confidence rating’ instead of a binary outcome and training methods that might use additional metadata collected with each sample as soft watermarks. Through our lower bound, we observe that watermarking can improve performance significantly only if the false negative rate of the watermark detector shrinks with the fraction of real samples, matching the oracle-assisted setting (equivalently, perfect watermarking) up to constant factors whenever this rate is linear or faster. We also observe that a matching upper bound (up to constant factors) is achieved by simple deterministic estimators in most regimes. However, when synthetic sampling outpaces real sampling extremely rapidly, the performance of these estimators falls short of the lower bound. A similar effect was also observed in the unassisted setting in our previous work. With this in mind, we propose a randomization procedure (which we refer to as masking) that narrows it to a Jensen gap. We conjecture that a tighter lower bound might close this gap. The work in this paper was supported by SNSF Grant 10004381 Email: millen.kanabar@epfl.ch, michael.gastpar@epfl.ch

2

New real samples„ p

¨¨¨

Corpus at stage t ´ 1

Detect watermarks

Retain

Add watermarks

ü

Corpus at stage t

Ť

Ř Detect watermarks

ü

Estimate

Estimate

Estimate Ppt´1

¨¨¨

Sample

New synthetic samples„ Ppt´1

Estimate Ppt

¨¨¨

Fig. 1. Stage t in the accumulation workflow with watermarking

A. Notation Deterministic quantities and functions are represented by lowercase Greek and Roman alphabets; random variables are represented by uppercase Roman alphabets. The probability simplex corresponding to the alphabet of size k is denoted as ∆k . We use ra : bs to denote tx P N : a ď x ď bu. The unit vector in with component j equal to 1 is denoted as ej . The j th component of a random or deterministic vector P or p is indexed by square brackets as P rjs and prjs respectively, and the probability of an event A under distribution Q is denoted as QtAu. The n-fold product of a distribution Q is denoted as Qn . For t ě 0 and functions f, g, we write gptq “ opf ptqq if limtÒ8 gptq{f ptq “ 0; gptq “ Opf ptqq if there exists a constant a ě 0 such that gptq ď af ptq @t ě 0 and gptq “ Θpf ptqq if gptq “ Opf ptqq and f ptq “ Opgptqq. B. Related work Model collapse has been widely observed empirically e.g. in [5]–[8] and analyzed theoretically for discrete distributions [5], [9], [10], parametric models [11]–[14], regression and kernel density estimation [15]–[21], and diffusion models [15], [22]. Various mechanisms to mitigate model collapse have also been proposed, such as accumulating data [9], [12], [17], [23], [24], watermarking [5], [25]–[27], and data curation [18], [28], [29]. Our masking procedure is inspired, in part, by recent work [30] that reduces recursive learning to the PU learning setting [31]. Additionally, in our setting, we only consider samples from the ground truth distribution and known estimates; similar bounds for settings such as [32] that use samples from unknown distributions close to the ground truth remain open. II. P ROBLEM S ETUP Let p P ∆k be the distribution being estimated, and pnt , αt qtě0 be a sequence over N ˆ r0, 1s. The estimators might also be equipped with additional randomness Ut ; the randomized estimates are available to the estimator at each subsequent stage of estimation. Sampling and estimation then follows the following procedure: A. Sampling procedure a) Initial samples and estimates: At stage 0, the estimator receives n0 samples X0n0 sampled i.i.d. from p. The estimator releases the estimate Pp0 “ pppX0n0 , U0 q and retains it for subsequent stages of estimation. n b) Recursive estimation: At every subsequent stage t ě 1, random variables Ytnt „ pBerpαt qq t are drawn. These nt will determine the provenances of the samples. Subsequently, samples Xt are drawn conditionally independently from PspX|Ppt´1 , Y q given as # prxs Y “1 PspX “ x|Ppt´1 , Y q “ (1) p Pt´1 rxs Y “ 0. ` ˘ The estimate Ppt :“ ppt pXini , Ui qtPr0:ts is released and retained for future estimation. For ease of notation, we define Y0n0 as s t,p . the all-ones vector. We will refer to the joint distribution of the whole sequence pUi , Xini qiPr0:ts as P

3

c) Watermarking: Additionally, when a watermarking mechanism is present, we model the output of the watermarking detector as random variables Wtnt P W nt , with |W| “ kW . Given Yt , these are drawn conditionally independently from # Q0,t rws y “ 0 PsWt |Yt pw|yq “ (2) Q1,t rws y “ 1. Once again, for ease of notation, we define W0n0 as the all-ones vector. For conciseness, we will drop the dependence on t and only write Q0 and Q 1 , however, the proofs ˘ do not depend on these staying constant. In this setting, the watermark-aided pwq pwq ` estimates Ppt :“ ppt pXini , Wini , Ui qiPr0:ts are released and retained for subsequent stages. We also add a superscript to s pwq to indicate the watermarking setting. The marginal distribution of the joint distribution of all the information available P t,p sα . the watermark αt Q1 ` p1 ´ αt qQ0 is denoted as Q t For the rest of the paper, we use the term ‘watermark’ to refer to the output of the detector. d) Oracle-assisted baseline: We consider estimators to be ‘oracle-assisted’ when the sample provenances pYini q are also available to the estimator via an oracle; this information is lost otherwise. In this setting, oracle-assisted estimates, denoted as ˘ poq poq ` Ppt :“ ppt pXini , Yini , Ui qiPr0:ts , are released and retained in memory. As with watermarking, we also add the superscript s poq to indicate the oracle-assisted setting. P t,p We use the unassisted and oracle-assisted performance of estimators as lower and upper baselines in this work: good watermarks and will get the loss as close to the oracle-assisted performance as possible, whereas a loss close to the unassisted performance will signal ineffective watermarks. B. Measuring performance We use the minimax expected ℓ22 loss as the figure of merit. Definition 1 (Minimax expected loss): The minimax expected loss rt,k of the sequence ppt is given as ” ´ ¯ı 2 p , p . rt,k :“ inf sup EP s t,p ℓ2 P t

(3)

ppt pP∆k

poq

pwq

The oracle-assisted and watermark-assisted minimax losses rt,k and rt,k are defined similarly. When estimating a discrete distribution p P ∆k from n i.i.d. samples, the minimax ℓ22 loss is Θp1{nq. Along similar lines, in the recursive estimation settings in this work, we informally refer to the multiplicative inverse of the expected ℓ22 losses (suitably normalized by constants) as the ‘effective sample size’. For example, using [1, Theorems 1 & 2], under most regimes in the unassisted setting, we find that the minimax loss is upper and lower bounded as c1 c2 ď rt,k ď t t ř ř ni αi2 ni αi2 i“0

i“0

for some positive constants c1 and c2 independent of the sequences nt , αt . Consequently, we refer to the denominator as the effective sample size, and the individual terms ni αi2 as the effective sample size at stage i.

t ř i“0

ni αi2

III. M AIN RESULTS To help state the results, we first define the memory term that encapsulates the effect estimates have on lower bounds for future stages. pwq Definition 2 (Memory terms for the lower bound): The memory term gt pρq (and, similarly, gt pρq) is defined as ˇ !ˇ ) s t,p ˇˇPpt´1 rxs ´ prxsˇˇ ě ρ . gt pρq “ sup P (4) pP∆k xPX

pwq

The term ht pρq (and similarly ht pρq) is defined as ht pρq “

t ÿ

ni αi gi pρq.

(5)

i“1

Notice that the memory terms depend on the deviation probabilities of the previous estimators. We comment on the necessity of these in our bounds in Section IV-B where we discuss the masking estimator.

4

A. Minimax bounds with watermarking Theorem 1 (Lower bound with watermarks): Consider the watermark-aided recursive distribution estimation problem with s pwq . There exists a constant m independent of t such that tuples pUi , Xini , Wini qiPr0:ts distributed according to P t,p m pwq rt,k ě řt (6) ` › ˘˘ ` pwq 2 2 Q ›Q sα ` ht p1{4kq 1 i i“0 ni αi 1 ` χ ` ` › ˘˘ řt pwq pwq sα ` ht p1{4kq ě k{4, with ht p1{4kq defined in Definition 2. whenever i“0 ni αi2 1 ` χ2 Q1 ›Q i We also show that the lower bound at each stage t is achievable by a sequence of deterministic estimators in most regimes under mild parametric assumptions. Theorem 2 (Upper bound with watermarks): For the problem setup given above, there exists a sequence of deterministic estimators for which the worst-case loss is bounded above as 3 pwq sup Erℓ22 pPpt , pqs ď řt (7) ` › ˘ 2 p1 ` χ2 Q ›Q sα q p n α 1 i i“0 i i whenever, for every t ě 1, ` ` ` › ˘˘˘ t sα 8 log kW 1 ` χ2 Q1 ›Q 1 ÿ t ď n ď ni αi2 . t s α rws α minw Q t t i“0

(8)

We note that the hypothesis conditions (8) can be dispensed with in favor of more complicated results and proofs: the first inequality allows us to match a loose lower bound via concentration of the denominator, and the second is necessary only to ensure that the corresponding estimates lie in ∆k with probability 1 (as opposed lying outside ∆k with only exponentially small probability). From the above bounds, we ` ` see that ˘˘ when the memory term is small, the effective sample size for batch i sα . in the watermarking setting is ni αi2 1 ` χ2 Q1 }Q i B. Performance of the masked estimator The above upper and lower bounds do not match when the memory term is not small. Making progress towards closing this gap, we show that probabilistically masking the output estimate reduces this to a Jensen gap. 1) The masking process: Let Bt be a (not necessarily i.i.d.) process such that Bt „ Ber pbt q for some sequence bt . Let ppreq ppreq p Pt be an unbiased pre-release estimate of p. Sample St „ Ppt . The released estimate is given as # ppreq Ppt rxs Bt “ 0 Ppt rxs “ . 1tSt “ xu Bt “ 1 We refer to this as masking to refer to the probabilistic replacement of the pre-release estimate with the k deterministic distributions ex , x P X . When the estimate is indeed masked at time t, each synthetic sample in batch t ` 1 is equal to St . 2) Performance: For conciseness of expression and proof, we state the upper bound in the unassisted setting, applying the masking process to a sequence of simple linear estimators. An equivalent expression with the corresponding χ2 divergence terms for each stage i can be shown by masking the sequence of estimators proposed in Theorem 2 instead. Theorem 3: There exists a sequence of estimators ppt such that, for each t ě 0, ” ´ ¯ı 2 p sup EP ď 2σt2 ¨ p1 ` cq, (9) s t,p ℓ2 P t, p p fi » — σt2 :“ E — –

1 ´ 1{k n0 `

t ř i“1

ni αi2 p1 ´ Bi´1 q ` ni αi Bi´1

ffi ffi fl

(10)

for any process pBi qiě0 with marginal distributions Bt „ Ber pbt q, as long as bi ď cσi2 for some constant c ą 0 for every i. The proofs of these theorems can be found in Appendix A IV. D ISCUSSION To get a sense of the impact(s) of watermarking and masking, we compare our results to the previously known unassisted and oracle-assisted minimax bounds. Via [1, Theorems 1 and 2 and Lemma 1], the effective sample sizes at stage t are nt αt2 ` nt αt gt p1{4kq for the lower bound and nt αt2 for the upper bound in the unassisted setting, and nt αt in both`senses › for ˘ sα . the oracle-assisted setting. Watermarking therefore improves the effective samples size of stage t by a factor of 1`χ2 Q1 ›Q t

5

A. Watermarking in recursive settings Since perfect watermarking is exactly equivalent to the availability of oracle information pYini qiPr0:ts , we can compare effective sample sizes to find how fragile the benefit of watermarking is; a ‘good’ watermark would lead to an increase in effective sample size by a factor of Ωp1{αi q at each stage i. Given the statistics of the watermark, we have the following Proposition bounding the magnitude of this increment. ` › ˘ s α is bounded from above as Proposition 1: For any α P r0, 1s, Let ϵ “ minw Q0 rws{Q1 rws Then χ2 Q1 ›Q ` › ˘ 1 1 sα ď 1 ` χ2 Q1 ›Q ď (11) α ` ϵ ´ αϵ maxtα, ϵu Proof: The proof is direct. We have ÿ ` › ˘ sα “ Q1 rws 1 ` χ2 Q1 ›Q wPW

ÿ “

Q1 rws αQ1 rws ` p1 ´ αqQ0 rws 1

Q1 rws

Q0 rws α ` p1 ´ αq Q 1 rws ÿ 1 Q1 rws. ď ¨ α ` p1 ´ αqϵ wPW wPW

This bound provides a concise condition on Q0 and Q1 for watermarking to be useful: ϵt should decay at least as quickly as αt . Since Q1 rws ď 1, this implies that the watermarking detector should ‘misidentify’ synthetic samples as real samples (via at least one high confidence ‘real’ signal w˚ ) with smaller and smaller probabilities as real samples become rarer and the estimates get closer to the ground truth distribution. We present the exact performance in two well-known cases, where the watermarking detection statistics describe the output of the sample provenances Y when passed through two well-known channels: the BEC and the BSC. Claim 1 (BEC): Let the conditional distributions Q0 and Q1 denote the output distributions of a binary erasure channel s α q is then given as 1 ´ ϵ{α. (BEC) with error probability ϵ given inputs 0 and 1 respectively. χ2 pQ1 }Q This is exactly the behavior we expect, since the detection outputs for synthetic samples are either 0 or ‘error’. This might be difficult to implement in practice: watermarks still have relatively high false negative rates (see [2]–[4]). A more realistic watermarking scheme is described by a BSC: Claim 2 (BSC): For Q0 and Q1 describing the conditional output distributions of a binary symmetric channel (BSC) with s α q is given as crossover probability ϵ ă 1{2, the corresponding χ2 pQ1 }Q ˜ ¸ 1 1 1 p1 ´ 2ϵq ¨ . ď α ϵ ´ α 1´ϵ maxtα, ϵu 1´α ` 1´ϵ 1´α ` ϵ Thus, whenever the probability of misidentification is not very small (here, when ϵ is not close to α), watermarking only increases the effective sample size very marginally. B. Masking estimators pwq

In a large selection of regimes, the term ht p1{4kq (and similarly, ht p1{4kq) is dominated by the other term in the denominator [1, Propositions 1 and 2]. However, we see that there is a gap between the upper and lower bounds whenever the memory term ht p1{4kq dominates the effective sample size. 2 1) The linear estimation gap: Using Chebyshev’s inequality, we can upper bound the memory term gi pρq ď 16k 2 σi´1 and řt 2 2 consequently, upper bound the total effective sample size by n0 ` i“1 16k ni αi σi´1 . pwq Now, any sequence of linear estimators of p will lead to subgaussian estimates Ppi (since the empirical distributions of each pwq batch are subgaussian). Additionally, the bias of any such estimate has to be OpvarpPpi qq, which is op1q, i.e. the mean of these estimates is at an op1q distance from p. Consequently, the corresponding memory term gi —the probability of deviating from p by a constant distance 1{4k—will be exponentially small due to the concentration of these subgaussians around their mean. 2 If α (asymptotically) decreases quicker than σi´1 , using linear estimators cannot lead to an effective sample size larger than řt i řt 2 2 i“0 ni αi , while our Chebyshev upper bound is of the order n0 ` i“1 ni αi σi´1 . We show that the non-linearity introduced by the masking procedure narrows this to a Jensen gap.

6

2) Partially bridging the gap via masking: Notice that when bi is indeed equal to σi2 (or equivalently within constant factors), the expected value of the denominator in the RHS of (10) is ff « t t t ÿ ÿ ÿ 2 ni αi2 ` ni αi σi2 . (12) E n0 ` ni αi p1 ´ Bi´1 q ` ni αi Bi´1 “ i“0

i“1

i“1

While on the wrong side of Jensen’s inequality, the loss of the sequence of masking estimators converges to the corresponding lower bound in [1, Theorem 1] in the regimes where this denominator concentrates around its expected value, thereby closing the gap. We conjecture that a more careful analysis which accounts for sample path averages over each of the events in the memory term can further close this gap by raising the lower bound for the regimes in which concentration does not occur. 3) Masking with distributions of support larger than 1: For some alphabet x, let the released estimate Ppi´1 rxs “ 0. Conditioned on x getting masked in this way, the marginal probability of drawing x at stage i is given as αi prxs. The ‘corrected’ empirical estimate α1i ppemp rxs has variance exactly prxsp1 ´ αi prxsq 1 ¨ ni ¨ αi prxsp1 ´ αi prxsq “ , n2i αi2 ni αi

(13)

which directly raises the effective sample size for the estimate of prxs from ni αi2 to ni αi . Therefore, masking each estimate with distributions that have support size 1 ă k ă k would also lead to a similar upper bound, provided that masking is done often enough for each alphabet. We persist with masking using distributions of support size 1 for simplicity of proof. 4) Masking as a watermark: Similar to implementations in text generation, masking itself acts as a watermark: given Ppt´1 rxs “ 0, all samples in stage t with value x can be directly classified as real with probability 1. It does, however, distort the synthetic distribution, and therefore offers a more limited advantage compared to ‘invisible’ watermarks. Practicality is further limited by the fact that our modeling assumption that only samples from Ppt´1 are mixed in at stage t might no longer be valid in realistic settings. R EFERENCES [1] M. Kanabar and M. Gastpar, “Model Non-Collapse: Minimax Bounds for Recursive Discrete Distribution Estimation,” IEEE Transactions on Information Theory, vol. 72, pp. 1817–1830, Mar. 2026. [2] Q. Pang, S. Hu, W. Zheng, and V. Smith, “No Free Lunch in LLM Watermarking: Trade-offs in Watermarking Design Choices,” Advances in Neural Information Processing Systems, vol. 37, pp. 138756–138788, Dec. 2024. [3] H. Zhang, B. L. Edelman, D. Francati, D. Venturi, G. Ateniese, and B. Barak, “Watermarks in the Sand: Impossibility of Strong Watermarking for Generative Models,” Apr. 2024. [4] S. Gowal, R. Bunel, F. Stimberg, D. Stutz, G. Ortiz-Jimenez, C. Kouridi, M. Vecerik, J. Hayes, S.-A. Rebuffi, P. Bernard, C. Gamble, M. Z. Horváth, F. Kaczmarczyck, A. Kaskasoli, A. Petrov, I. Shumailov, M. Thotakuri, O. Wiles, J. Yung, Z. Ahmed, V. Martin, S. Rosen, C. Savčak, A. Senoner, N. Vyas, and P. Kohli, “SynthID-Image: Image watermarking at internet scale,” Oct. 2025. arXiv:2510.09263. [5] I. Shumailov, Z. Shumaylov, Y. Zhao, N. Papernot, R. Anderson, and Y. Gal, “AI models collapse when trained on recursively generated data,” Nature, vol. 631, July 2024. arXiv:2305.17493. [6] S. Alemohammad, J. Casco-Rodriguez, L. Luzi, A. I. Humayun, H. Babaei, D. LeJeune, A. Siahkoohi, and R. Baraniuk, “Self-consuming generative models go MAD,” in The Twelfth International Conference on Learning Representations, 2024. arXiv:2307.01850. [7] J. Kazdan, R. Schaeffer, A. Dey, M. Gerstgrasser, R. Rafailov, D. L. Donoho, and S. Koyejo, “Collapse or Thrive? Perils and Promises of Synthetic Data in a Self-Generating World,” Feb. 2025. arXiv:2410.16713. [8] L. Shi, M. Wu, H. Zhang, Z. Zhang, M. Tao, and Q. Qu, “A Closer Look at Model Collapse: From a Generalization-to-Memorization Perspective,” Advances in Neural Information Processing Systems, vol. 38, pp. 40658–40691, Apr. 2026. [9] M. E. A. Seddik, S.-W. Chen, S. Hayou, P. Youssef, and M. A. Debbah, “How bad is training on synthetic data? a statistical analysis of language model collapse,” in First Conference on Language Modeling, 2024. arxiv:2404.05090. [10] A. T. Suresh, A. Thangaraj, and A. N. K. Khandavally, “Rate of model collapse in recursive training,” in The 28th International Conference on Artificial Intelligence and Statistics, 2025. arXiv:2412.17646. [11] Q. Bertrand, J. Bose, A. Duplessis, M. Jiralerspong, and G. Gidel, “On the stability of iterative retraining of generative models on their own data,” in The Twelfth International Conference on Learning Representations, 2024. arXiv:2310.00429. [12] M. Marchi, S. Soatto, P. Chaudhari, and P. Tabuada, “Heat Death of Generative Models in Closed-Loop Learning,” Aug. 2024. arXiv:2404.02325. [13] S. Xu, H. He, and G. Cheng, “A Probabilistic Perspective on Model Collapse,” May 2025. arXiv:2505.13947. [14] D. Barzilai and O. Shamir, “When Models Don’t Collapse: On the Consistency of Iterative MLE,” Advances in Neural Information Processing Systems, vol. 38, pp. 76813–76854, Apr. 2026. [15] S. Fu, S. Zhang, Y. Wang, X. Tian, and D. Tao, “Towards theoretical understandings of self-consuming generative models,” in Forty-first International Conference on Machine Learning, 2024. arXiv:2402.11778. [16] E. Dohmatob, Y. Feng, and J. Kempe, “Model collapse demystified: The case of regression,” in The Thirty-eighth Annual Conference on Neural Information Processing Systems, 2024. arXiv:2402.07712. [17] M. Gerstgrasser, R. Schaeffer, A. Dey, R. Rafailov, T. Korbak, H. Sleight, R. Agrawal, J. Hughes, D. B. Pai, A. Gromov, D. Roberts, D. Yang, D. L. Donoho, and S. Koyejo, “Is model collapse inevitable? breaking the curse of recursion by accumulating real and synthetic data,” in First Conference on Language Modeling, 2024. arXiv:2404.01413. [18] Y. Feng, E. Dohmatob, P. Yang, F. Charton, and J. Kempe, “Beyond model collapse: Scaling up with synthesized data requires reinforcement,” in ICML 2024 Workshop on Theoretical Foundations of Foundation Models, 2024. arXiv:2406.07515. [19] E. Dohmatob, Y. Feng, A. Subramonian, and J. Kempe, “Strong model collapse,” in The Thirteenth International Conference on Learning Representations, 2025. arXiv:2410.04840. [20] H. A. Vu, G. Reeves, and E. Wenger, “What happens when generative AI models train recursively on each others’ outputs?,” Oct. 2025. arXiv:2505.21677. [21] A. Garg, S. Bhattacharya, and P. Sur, “Preventing Model Collapse Under Overparametrization: Optimal Mixing Ratios for Interpolation Learning and Ridge Regression,” Feb. 2026. arXiv:2509.22341. [22] N. B. Khelifa, R. E. Turner, and R. Venkataramanan, “Error Propagation and Model Collapse in Diffusion Models: A Theoretical Study,” Feb. 2026. arXiv:2602.16601.

7

[23] S. Fu, Y. Wang, Y. Chen, X. Tian, and D. Tao, “A Theoretical Perspective: How to Prevent Model Collapse in Self-consuming Training Loops,” Feb. 2025. arXiv:2502.18865. [24] J. Kazdan, R. Schaeffer, A. Dey, M. Gerstgrasser, R. Rafailov, D. L. Donoho, and S. Koyejo, “Collapse or thrive? perils and promises of synthetic data in a self-generating world,” 2025. arXiv:2410.16713. [25] H. He, S. Xu, and G. Cheng, “Golden Ratio Weighting Prevents Model Collapse,” Mar. 2025. arXiv:2502.18049. [26] W. Ji, W. Yuan, E. Getzen, K. Cho, M. I. Jordan, S. Mei, J. Weston, W. J. Su, J. Xu, and L. Zhang, “An Overview of Large Language Models for Statisticians,” The American Statistician, vol. 0, pp. 1–106, Apr. 2026. eprint: https://doi.org/10.1080/00031305.2026.2657480. [27] G. Racca, M. Valko, and A. Sanyal, “Language Generation with Replay: A Learning-Theoretic View of Model Collapse,” Mar. 2026. arXiv:2603.11784. [28] E. Dohmatob, M. Pezeshki, and R. Askari-Hemmat, “Why Less is More (Sometimes): A Theory of Data Curation,” Nov. 2025. arXiv:2511.03492. [29] K. Amin, S. Babakniya, A. Bie, W. Kong, U. Syed, and S. Vassilvitskii, “Escaping collapse: The strength of weak data for large language model training,” in The Thirty-ninth Annual Conference on Neural Information Processing Systems, 2025. arXiv.2502.08924. [30] K. Amin, A. Bie, W. Kong, U. Syed, and S. Vassilvitskii, “Learning from synthetic data: Limitations of ERM,” in 37th International Conference on Algorithmic Learning Theory, 2026. [31] F. Mansouri and S. Ben-David, “Learning from positive and unlabeled examples -Finite size sample bounds,” Oct. 2025. [32] A. Jain, A. Montanari, and E. Sasoglu, “Scaling laws for learning with real and surrogate data,” Advances in Neural Information Processing Systems, vol. 37, Dec. 2024. [33] L. Paninski, “A Coincidence-Based Test for Uniformity Given Very Sparsely Sampled Discrete Data,” IEEE Transactions on Information Theory, vol. 54, Oct. 2008. [34] B. Yu, “Assouad, Fano, and Le Cam,” in Festschrift for Lucien Le Cam: Research Papers in Probability and Statistics (D. Pollard, E. Torgersen, and G. L. Yang, eds.), New York, NY: Springer, 1997.

A PPENDIX A P ROOF OF THE L OWER B OUND A. The lower bound for watermarking As in [1], we use the Paninski construction [33] along with Assouad’s method (see e.g. [34]) to find lower bounds in the various settings. s t,p . Consider the set of vectors V “ t`1, ´1uk{2 . With each vector Lemma 4 (Restated Lemma 7 from [1]): Let Z „ P v P V, associate the distribution „ ȷ δ v (14) pv :“ pu ` k ´v where pu is the uniform distribution. Let Pk :“ tpv : v P Vu. The ℓ22 minimax estimation risk of an estimator Ppt “ ppt pZq as described in Definition 1 is lower bounded as ¨ g ˛ f f k{2 › ´ ¯ 2 δ ˚ f2 ÿ ‹ s t,p ››P s t,p rt,k ě max D P (15) ˝1´e ‚ v v´2ej 4k k j“1 vPV: vj “1

We are now ready to prove the lower bound. › ¯ ´ s pwq s pwq ››P Proof of Theorem 1: The proof proceeds by showing an upper bound on D P t,pv´2ej , with pv as defined in t,pv (14). Define the conditional distributions (with some abuse of notation) ˇ ! ´ ¯ ) ni s pwq pXt , Wt qnt “ pxt , wt qnt ˇˇpXi , Wi qni r pwq pxt , wt qnt |pxi , wi qni :“ P “ px , w q P i i iPr0:t´1s , t,p t,p iPr0:t´1s iPr0:t´1s ˇ ´ ¯ ! ) pwq ni i s pwq pXt rjs, Wt rjsq “ pxt , wt qˇˇpXi , Wi qni Prt,p xt , wt |pxi , wi qniPr0:t´1s :“P j P r1 : nt s, t,p iPr0:t´1s “ pxi , wi qiPr0:t´1s ˇ ´ ˇ ¯ ! ) ˇ ˇ pwq pwq i i i s and Prt,p,wt xt ˇpxi , wi qniPr0:t´1s :“P Xt rjs “ xt ˇpXi , Wi qniPr0:t´1s “ pxi , wi qniPr0:t´1s , Wt rjs “ wt j P r1 : nt s. t,p Then t › › ˇ ´ ¯ paq ÿ ´ ¯ ˇ s pwq s pwq ››P s pwq r pwq ››P r pwq D P “ D P t,pv t,pv´2e i,pv i,pv´2e ˇPi´1,pv j

j

i“0 t ÿ

“ i“0 t ÿ

“ pbq

i“0 t ÿ

“

i“0

ni EP s pwq

› ” ´ ¯ı pwq › pwq D Pri,pv ›Pri,pv´2e

ni EP s pwq

› ” ” ´ ¯ıı › pwq pwq EW „Qs αt D Pri,pv ,W ›Pri,pv´2e ,W

i´1,pv

i´1,pv

j

j

” EW „Qs αt ni EP s pwq

i´1,pv

› ” ´ ¯ıı › pwq pwq D Pri,pv ,W ›Pri,pv´2e ,W j

(16)

where paq follows from the chain rule of KL Divergences and pbq follows because of the independence of the distribution of the watermark and the samples themselves. Observe that pwq pwq ri,w p ` p1 ´ α ri,w qPpt´1 Prt,p,w “ α

(17)

8

where αi Q1 rws pwq ri,w :“ s α Qαi rws

i P r0 : ts.

(18)

Thus, conditioned on each watermark detection output Wt rjs “ wt , the distributions of the samples Xt rjs are equal to the pwq ri,wt . We can therefore directly use results marginal distributions of unwatermarked samples with equivalent mixing factors α from the unwatermarked setting to bound (16). From [1, Equation 17], for each W “ w, ˆ ´ ˙ › ¯ı ” ´ ¯2 8δ 2 › rpwq pwq pwq pwq r 1 ˘ ni α ri,w ` ni α ri,w gi p {4kq . ď `9 ni E P D Pi,pv ,W ›Pi,pv´2e ,W (19) s pwq j i´1,pv k 16 ´ δ 2 Consequently, ´ D

›

s pwq ››P s pwq P t,pv t,pv´2ej

¯

8δ 2 ˘E ď `9 s k 16 ´ δ 2 W „Qαt

«

t ÿ

´

pwq ri,W ni α

¯2

ff pwq ri,W gi p1{4kq ` ni α

.

i“0

Since ˙2 ff ` › ˘˘ ` Q1 rws sα “ αi2 1 ` χ2 Q1 ›Q EW „Qs αt “EW „Qs αt i s Qαt rxs „ ȷ ” ı Q1 rws pwq ri,W “EW „Qs αt αt s and EW „Qs αt α “ αi , Qαt rxs „´

pwq ri,W α

«

¯2 ȷ

ˆ

αt2

(20) (21)

choosing δ2 “

64

k ˘˘ ˘ ` ` › 2 1 ` χ2 Q ›Q sα ` ni αi gi p1{4kq n α i i 1 i i“0

řt

`

(22)

gives us › ¯ 1 ´ s pwq s pwq ››P ď D P t,pv´2ej t,pv 4 whenever

řt

2 i“0 ni αi

`

` › ˘˘ pwq sα 1 ` χ2 Q1 ›Q ` ht p1{4kq ě k{4. Invoking Lemma 4 then leads to a lower bound of i 1

pwq

rt,k ě

512

řt

2 i“0 ni αi

`

1 ` χ2

`

› , ˘˘ sα ` ht p1{4kq Q1 ›Q i

(23)

completing the proof. A PPENDIX B P ROOFS OF THE U PPER B OUNDS A. Useful Lemmas We also have the following Lemma showing the performance of a linear estimator in the presence of recursive sampling. Lemma 5 (Restated Lemma 9 from [1]): Let Pp0 be an unbiased estimate of p with a variance η 2 rxs ¨ prxsp1 ´ prxsq for each component x P X . Let samples Z n „ pαp ` p1 ´ αqPp0 qn . Denote the empirical distribution of samples X n as ppemp pX n q. Then the intermediate estimate ¯ 1´ ppemp pX1n1 q ´ p1 ´ αqPp0 Pp1,int “ pp1,int pX1n1 q :“ (24) α has expectation p and is component-wise uncorrelated with Pp0 . Additionally, each component x P X has variance „´ ¯2 ȷ prxsp1´prxsq ` ˘ p E P1,int rxs´prxs “ 1´p1´αq2 η 2 rxs . (25) n1 α 2 Finally, we state the following elementary lemma that will be useful in combining estimates when upper bounds on their variances are known. Lemma 6: Let θp1 and θp2 be two unbiased and uncorrelated estimates of a parameter θ P Θ, and let their variances be bounded above by σ12 and σ22 .ˆWe can ˙then construct a linear combination θs of θp1 and θp2 that is unbiased and with variance s2 bounded above as σ σ s2 ď 1{ σ12 ` σ12 . 1

2

9

B. Proof of the watermarking upper bound Proof of Theorem 2: The proof proceeds inductively. Assume that at stage t ´ 1, each component of Ppt´1 is unbiased and has variance upper bounded as ´ ¯ 3 ¨ prxsp1 ´ prxsq pwq 2 var Ppt´1 rxs ď σ st´1 rxs “ řt ` › ˘ . 2 2 Q ›Q sα q 1 i i“0 ni αi p1 ` χ It is easy to verify that the empirical estimator satisfies these conditions for t “ 0. N rws Let the number of samples in batch t watermarked as w be Nt rws, and let the corresponding samples be Xt,wt . Recall from pwq N rws pwq pwq pwq rt,w p ` p1 ´ α rt,w qPpt´1 . (17) that given Ppt´1 and Wt “ w, Xt,wt is a conditionally i.i.d. vector with marginal distributions α th Therefore, invoking ´ Lemma ¯ 5, for each x P X , the conditional variance of the x component of intermediate estimates Nt rws pwq p Pt,w,int :“ ppt,int Xt,w given Wtnt and Ppt´1 is bounded above by ˇ ¯ ´ prxsp1 ´ prxsq ˇ pwq var Ppt,w,int rxsˇWtnt , Ppt´1 ď ´ ¯2 . pwq ri,w Nt rws α pwq For each x P X , all estimates Ppt,w,int rxs, w P W are also ´unbiased and conditionally independent given Wtnt and Ppt´1 . The ¯2 pwq r i,w Nt rws α ř pt,w,int therefore has a conditional variance bounded ´ ¯ ¨P combined intermediate estimate Ppt,int “ wPW ř pwq 2 1 w1 PW Nt rw s

α r i,w1

above as ˇ ´ ¯ prxsp1 ´ prxsq ˇ pwq var Ppt,int rxsˇWtnt , Ppt´1 ď ř ´ ¯2 , pwq α r N rws t i,w wPW › ˘˘ ` ` s α . Now, (via Lemma 6) where the denominator has an expected value nt αt2 1 ` χ2 Q1 ›Q t # + # + ´ ¯2 ÿ ď " s α rws * paq pwq › ` ` ˘˘ 1 n Q t pwq pwq t s s sα ri,w ď nt αt2 1 ` χ2 Q1 ›Q P Nt rws α ďP Nt rws ď t,p t,p t 2 2 wPW wPW * " s pbq ÿ s pwq Nt rws ď nt Qαt rws ď P t,p 2 wPW " s α rws * nt Q pwq t s ďkW max Pt,p Nt rws ď wPW 2 ˆ s α rws ˙ pcq minz Q t ď kW exp ´nt 8 pdq 1 ď 2 sα q , 1 ` χ pQ1 }Q t

(26)

(27)

pwq s α and α s α rws, pbq follows from the union bound, pcq follows from ri,w “ Q1 rws{Q where paq follows from Wt ris „ Q t t Hoeffding’s inequality, and pdq follows from the lower bound assumption on nt in (8). Define the pre-release estimate as $ ´ ¯2 ` ` › ˘˘ ř &p pwq sα ri,w ą 12 nt αt2 1 ` χ2 Q1 ›Q Pt,int if wPW Nt rws α t p Pt,pre :“ %pp pX nt q otherwise. t,int t

Consequently, from (26), Lemma 5, and (27), ˇ ” ´ ¯ı 2 ¨ prxsp1 ´ prxsq ˇ pwq ` ` › ˘˘ E var Ppt,pre rxsˇWtnt , Ppt´1 ď sα nt αt2 1 ` χ2 Q1 ›Q t # + ´ ¯2 › ` ` ˘˘ 1 prxsp1 ´ prxsq s pwq ÿ pwq sα ri,w ď nt αt2 1 ` χ2 Q1 ›Q ` ¨ Pt,p Nt rws α t nt αt2 2 wPW 3 ¨ prxsp1 ´ prxsq ` › ˘ . 2 2 Q ›Q sα q 1 i i“0 ni αi p1 ` χ

ď řt

pwq Ppt,pre is unbiased and component-wise uncorrelated with Ppt´1 (since ppt,int pXtnt q and Ppt,int are also unbiased and componentpwq wise uncorrelated). Using Lemma 6 again to combine Ppt,pre and Ppt´1 completes the induction step.

10

C. Proof for the masking estimator upper bound ppreq Recall that the masking procedure takes an unbiased pre-release estimate Ppt and masking decision Bt P t0, 1u as inputs and releases the estimate # ppreq Ppt rxs Bt “ 0 Ppt rxs “ 1tSt “ xu Bt “ 1 ppreq where St „ Ppt . Proof of Theorem 3: Fix Bi “ui Pt0,1u for each iPr0:ts. Mirroring the notation in Lemma 5, define ηi2 rxs as the scalar such that ˇ ¯ ´ ˇ var Ppi rxsˇpBi qiPr1:ts “ pui qiPr1:ts “ ηi2 rxs ¨ prxsp1 ´ prxsq. ppreq If Ppt is unbiased, Er1tSt “ xus “ p and therefore Ppt is also unbiased. Using the empirical estimator pp0,int “ ppemp in stage 0, and subsequently ppi,int from Lemma 5 in stage i ě 1, we have ˇ ¯ prxsp1 ´ prxsq ´ ˇ var Pp0,int ˇpBi qiPr0:ts “ pui qiPr0:ts ď i“0 n0 ˇ ¯ prxsp1 ´ prxsq ´ ˇ 2 ¨ p1 ´ p1 ´ αi q2 ηi´1 rxsq iě1 var Ppi,int rxsˇpBj qjPr0:ts “ puj qjPr0:ts ď ni αi2

These are all unbiased and uncorrelated with the previous estimate. Therefore, using Lemma 6, we can find the pre-release ppreq estimate Ppt with a variance upper bound of ˇ ´ ¯ prxsp1 ´ prxsq ppreq ˇ var Ppt ˇpBi qiPr0:ts “ pui qiPr0:ts ď t ř ni α2i n0 ` 1´p1´α2 qη 2 rxs i“1

i

i´1

We now consider two cases: 1) The variance of Ppi rxs given Bi “ 1 is ” ı ppreq ppreq E p1 ´ prxsq2 Ppi rxs ` prxs2 p1 ´ Ppi q “ p1 ´ prxsq2 prxs ` prxs2 p1 ´ prxsq “ prxsp1 ´ prxsq. 2 Thus, if ui´1 “ 1, then ηi´1 rxs “ 1 for all x P X , and consequently 2 1´p1´αi q2 ηi´1 rxs“2αi . 2 2) If Bi “ 0, we simply use the trivial upper bound of 1 for 1 ´ p1 ´ αi q2 ηi´1 rxs. Consequently, given pBi qiPr0:ts “ pui qiPr0:ts , we have ˇ ´ ¯ prxsp1 ´ prxsq ppreq ˇ var Ppt st2 :“ ˇpBi qiPr0:ts “ pui qiPr0:ts ď σ t ř ni α i 2 n0 ` 2 ui `ni αi p1´ui q i“1

Taking the sum over x and expectation over the joint distribution of Bi and noticing that masking can only increase the loss by bt , and therefore only a factor of c when bt ď cs σt2 concludes the proof.

Related documents

• Minimax bounds for watermarked and masked recursive discrete distribution estimation#819115
• Minimax bounds for watermarked and masked recursive discrete distribution estimation#809123
• Information-Theoretic Foundations of the AaroNet Multi-Scale Detector#237194
• Tight Sample Bounds for Renyi and Min-Entropy Estimation#625535
• Tight Sample Bounds for Renyi and Min-Entropy Estimation#623262