Minimax bounds for watermarked and masked recursive discrete distribution estimation

Millen Kanabar; Michael Gastpar

Source-linked AI summary

Minimax bounds for watermarked and masked recursive discrete distribution estimation

Millen Kanabar, Michael Gastpar

arXiv:2608.31091v1Aug 31, 2026cs.ITcs.LGmath.ST

TL;DR

Recursive estimation can lose the benefit of new real samples when synthetic samples are not distinguishable, motivating analysis of imperfect watermarking. The paper derives minimax bounds for watermark-assisted estimation and proposes masking, finding that watermarking helps substantially only when false negatives vanish appropriately, while masking narrows remaining gaps to a Jensen gap.

Problem
The paper addresses how recursive discrete distribution estimation behaves when synthetic samples are mixed with real samples and provenance is unavailable or imperfectly detected.
Method
The paper uses reductions, minimax lower and upper bounds, deterministic estimators, and a randomized masking procedure to analyze watermark-assisted recursive estimation.
Results
Watermarking improves performance significantly only when the detector’s false negative rate shrinks with the fraction of real samples; masking narrows the remaining gap to a Jensen gap.
Takeaways & Limitations
Useful watermarking requires increasingly reliable rejection of synthetic samples as real samples become rarer, while masking partially bridges regimes where deterministic estimators fall short.
Takeaways & Limitations
The paper conjectures that a tighter lower-bound argument is needed to close the remaining Jensen gap.

Abstract

from arXiv · show

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. INTRODUCTION

The paper studies recursive discrete distribution estimation when samples are mixed from the ground truth and prior estimates, with imperfect watermark detection providing provenance information. It compares watermark-assisted estimation with unassisted and oracle-assisted settings, and introduces masking to address remaining gaps.

Model collapse occurs when repeated training on previous-generation outputs progressively degrades the underlying distribution.Finite samples overrepresent high-probability outcomes, increasing noise in low-probability outcomes until the distribution can collapse to a point mass.
Without provenance information, synthetic samples reinforce high-probability symbols and greatly reduce the marginal utility of new real samples when synthetic sampling outpaces real sampling.Accumulating fresh real samples can converge to the ground truth only if real samples are not lost among synthetic ones.
The paper reduces watermark-assisted estimation to the unassisted setting to identify when watermarking changes recursive estimation performance.Masking is proposed as a randomized procedure for narrowing gaps that remain under ordinary watermarking.
The paper models stage-t samples as coming from the ground truth with probability αt and from the previous estimate otherwise, with known mixing factors.Watermark distortion of synthetic samples is ignored, reflecting the assumption that watermarking adds only a small amount of structured noise.
Watermark detectors are modeled as random outputs correlated with sample provenance through known conditional distributions for real and synthetic samples.The model includes binary detectors, confidence ratings, and soft watermarks based on additional metadata.
Watermarking improves performance significantly only when the detector’s false negative rate shrinks with the fraction of real samples.When the rate is linear or faster, watermarking matches perfect, oracle-assisted watermarking up to constant factors.

B. Measuring performance

Performance is measured by minimax expected ℓ2^2 loss, with effective sample size defined as its suitably normalized inverse. Unassisted and oracle-assisted losses provide lower and upper baselines for evaluating watermarking.

The minimax expected loss r_t,k measures worst-case expected ℓ2^2 error for the estimator sequence at stage t.
For n i.i.d. samples, discrete distribution estimation has minimax ℓ2^2 loss Θ(1/n).
Effective sample size is the multiplicative inverse of expected ℓ2^2 loss after suitable normalization by constants.In recursive estimation, the denominator in the corresponding loss bounds is referred to as the effective sample size.
Unassisted and oracle-assisted performance serve as lower and upper baselines for judging watermark effectiveness.Performance close to the oracle-assisted setting indicates useful watermarks, whereas performance close to the unassisted setting indicates ineffective watermarks.

III. MAIN RESULTS

The main results establish watermarking lower and upper bounds through memory terms that capture how earlier estimation errors affect later stages. Deterministic estimators match the lower bounds in most regimes, while masking narrows the remaining gap but does not fully close it.

Memory terms: Memory terms capture the effect of previous estimates on lower bounds for future recursive estimation stages.They depend on the deviation probabilities of previous estimators.
Lower bound with watermarks: A watermarking lower bound holds for recursive distribution estimation and includes a stage-dependent memory term.The theorem states the bound with a constant independent of stage t.
Upper bound with watermarks: A sequence of deterministic estimators achieves the watermarking lower bound up to constants in most regimes under mild parametric assumptions.
Upper bound with watermarks: Theorem 2 provides a worst-case upper bound for a sequence of deterministic watermark-assisted estimators under stated hypothesis conditions.The first condition supports denominator concentration, while the second ensures estimates remain in the probability simplex with probability 1.
Effective sample size: When the memory term is small, the effective sample size in the watermarking setting scales as n_i α_i^2.

B. Performance of the masked estimator

When ordinary upper and lower bounds fail to match because the memory term is large, probabilistic masking narrows the discrepancy to a Jensen gap. The paper analyzes masked sequences of estimators and provides an upper-bound theorem under a mild condition on the masking process.

Masking reduces the mismatch between upper and lower bounds to a Jensen gap when the memory term is not small.
The masking process: Masking probabilistically replaces the pre-release estimate with one of k deterministic distributions, causing the next synthetic batch to equal the selected distribution.
Performance: The masked-estimator analysis states an upper bound in the unassisted setting for a sequence of simple linear estimators.
Performance: Theorem 3 asserts the existence of estimators satisfying the stated bound for every stage under a Bernoulli masking process whose parameters obey b_i ≤ cσ^2_i.

IV. DISCUSSION

The discussion compares watermarking with unassisted and oracle-assisted estimation through effective sample sizes and examines binary erasure and symmetric channels. Watermarking is useful only when synthetic-sample misidentification decreases sufficiently quickly as real samples become rarer.

At stage t, unassisted estimation has effective sample size n_tα_t^2, whereas oracle-assisted estimation has n_tα_t.
Although perfect watermarking is equivalent to oracle information, realistic watermarking may have relatively high false negative rates.
The detector should misidentify synthetic samples as real with probabilities that decay at least as quickly as α_t as real samples become rarer.
Channel examples: For a binary erasure channel, the relevant χ2 expression is 1 − ϵ/α.
Channel examples: For a binary symmetric channel, the χ2 expression is bounded by 1/max{α,ϵ}.
When the misidentification probability is not very small, watermarking increases effective sample size only marginally.

B. Masking estimators

The section analyzes when linear estimators leave a gap between upper and lower bounds and shows how masking narrows or closes that gap in several regimes.

B. Masking estimators: When the memory term dominates effective sample size, the upper and lower bounds do not match.The memory term is identified as the source of the remaining gap.
B. Masking estimators: For linear estimators, rapidly decreasing real-sample fractions limit the effective sample size, while the Chebyshev bound can be larger.This occurs when α_i decreases faster than σ^2_{i−1}.
B. Masking estimators: Masking introduces nonlinearity that narrows the discrepancy between the upper and lower bounds to a Jensen gap.The masking construction is presented as a way to improve beyond the linear-estimation limitation.
B. Masking estimators: The masking estimators converge to the corresponding lower bound when the denominator concentrates around its expected value.The authors conjecture that a more careful sample-path analysis could close the remaining gap when concentration fails.
B. Masking estimators: Masking increases the effective sample size for estimating p[x] from n_i α_i^2 to n_i α_i under the stated support condition.The construction uses distributions with support size 1 for simplicity of proof.
B. Masking estimators: Masking can classify samples as real with probability 1 when the previous released estimate assigns zero probability to their value.This benefit comes with distortion of the synthetic distribution and reduced practicality under more realistic recursive mixtures.

APPENDIX A PROOF OF THE LOWER BOUND

The appendix proves the watermarking lower bound by relating conditioned watermark observations to an unwatermarked recursive estimation problem and applying existing lower-bound tools.

APPENDIX A PROOF OF THE LOWER BOUND: The proof uses the Paninski construction together with Assouad’s method to derive lower bounds across the considered settings.These are the same lower-bound tools used in the cited prior work.
APPENDIX A PROOF OF THE LOWER BOUND: Lemma 4 lower-bounds the minimax ℓ2 estimation risk for an estimator based on observations from the recursive sampling model.The lemma constructs a family of distributions indexed by sign vectors around the uniform distribution.
APPENDIX A PROOF OF THE LOWER BOUND: The proof bounds the divergence between joint sample-and-watermark distributions before invoking the lower-bound lemma.The appendix explicitly frames the proof of Theorem 1 around an upper bound on this divergence.
APPENDIX A PROOF OF THE LOWER BOUND: Conditioned on watermark detection outputs, the sample distributions equal marginal unwatermarked distributions with corresponding effective mixing factors.This reduction enables direct reuse of results from the unwatermarked setting.
APPENDIX A PROOF OF THE LOWER BOUND: The argument obtains the theorem’s lower bound after establishing a constant lower bound on the relevant deviation probability.The displayed proof fragment states a threshold of k/4 for that probability.

A. Useful Lemmas

The section supplies lemmas for analyzing recursive intermediate estimates and combining unbiased, uncorrelated estimates with controlled variance.

A. Useful Lemmas: The recursive intermediate estimate has expectation p and is component-wise uncorrelated with the previous estimate.This follows for samples drawn from the mixture αp + (1 − α)p̂_0 under the lemma’s assumptions.
A. Useful Lemmas: Lemma 5 gives a component-wise variance expression for the empirical distribution of recursively sampled observations.The variance depends on the mixture parameter, the underlying component probability, and the initial-estimate variance parameter.
A. Useful Lemmas: Lemma 6 combines two unbiased, uncorrelated estimates into another unbiased estimate with an upper-bounded variance.The resulting variance bound is determined by the two component variance bounds.

B. Proof of the watermarking upper bound

The proof establishes the watermarking upper bound inductively by constructing conditionally independent intermediate estimates and combining them through variance bounds.

B. Proof of the watermarking upper bound: The induction assumes each component of the previous estimate is unbiased with a controlled variance bound.The empirical estimator satisfies the base-case conditions at stage t = 0.
B. Proof of the watermarking upper bound: Conditioned on watermark outputs, samples assigned to each watermark class are conditionally independent with effective mixing distributions.This permits application of the recursive-estimation variance lemma to each class.
B. Proof of the watermarking upper bound: The proof combines class-specific intermediate estimates into a single intermediate estimate using conditional variance bounds.The combination is justified by conditional independence and the variance-combination lemma.
B. Proof of the watermarking upper bound: The pre-release estimate is combined with the watermark-conditioned estimate to complete the induction step.Both component estimates are treated as unbiased and component-wise uncorrelated before the final combination.

C. Proof for the masking estimator upper bound

The proof analyzes the masking estimator by conditioning on masking decisions, establishing unbiasedness and bounding variance before controlling the masking-induced loss increase.

The masking procedure uses a pre-release estimate together with a binary masking decision to release an estimate.
Conditioned on fixed masking decisions, the constructed estimator is unbiased, and its components are unbiased and uncorrelated with the previous estimate.
The variance analysis separates the cases where the masking decision is one and zero, using prxsp1 − prxsq in the first case and a trivial upper bound of 1 in the second.
The proof sums over symbols and averages over masking decisions, concluding that masking increases the loss by bt and only by a factor of c when bt ≤ csσ2.