PaperlayerView exact revision on arXiv

Source-linked AI summary

Minimax bounds for watermarked and masked recursive discrete distribution estimation

Millen Kanabar, Michael Gastpar

arXiv:2608.31091v1cs.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.

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.Source: §I · p. 1
  • 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.Source: §I · p. 1
  • 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.Source: §I · p. 1
  • 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.Source: §I · p. 1
  • 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.Source: §I · p. 1
  • 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.Source: §I · p. 1

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.Source: B. Measuring performance · p. 3
  • For n i.i.d. samples, discrete distribution estimation has minimax ℓ2^2 loss Θ(1/n).Source: B. Measuring performance · p. 3
  • 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.Source: B. Measuring performance · p. 3
  • 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.Source: B. Measuring performance · p. 3

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.Source: §III · p. 3

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.Source: A. Minimax bounds with watermarking · p. 4

Upper bound with watermarks

  • A sequence of deterministic estimators achieves the watermarking lower bound up to constants in most regimes under mild parametric assumptions.Source: A. Minimax bounds with watermarking · p. 4
  • 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.Source: A. Minimax bounds with watermarking · p. 4

Effective sample size

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.

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.Source: 1) The masking process · p. 4

Performance

  • The masked-estimator analysis states an upper bound in the unassisted setting for a sequence of simple linear estimators.Source: 2) Performance · p. 4
  • 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.Source: 2) Performance · p. 4

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.Source: §IV · p. 4
  • Although perfect watermarking is equivalent to oracle information, realistic watermarking may have relatively high false negative rates.Source: A. Watermarking in recursive settings · p. 5
  • The detector should misidentify synthetic samples as real with probabilities that decay at least as quickly as α_t as real samples become rarer.Source: A. Watermarking in recursive settings · p. 5

Channel examples

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.Source: B. Masking estimators · p. 5
  • 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}.Source: 1) The linear estimation gap · p. 5
  • 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.Source: 1) The linear estimation gap · p. 5
  • 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.Source: 2) Partially bridging the gap via… · p. 6
  • 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.Source: 3) Masking with distributions of… · p. 6
  • 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.Source: 4) Masking as a watermark · p. 6

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.Source: A. The lower bound for watermarking · p. 7
  • 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.Source: A. The lower bound for watermarking · p. 7
  • 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.Source: A. The lower bound for watermarking · p. 7
  • 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.Source: A. The lower bound for watermarking · p. 8
  • 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.Source: A. The lower bound for watermarking · p. 8

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.Source: A. Useful Lemmas · p. 8
  • 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.Source: A. Useful Lemmas · p. 8
  • 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.Source: A. Useful Lemmas · p. 8

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.Source: B. Proof of the watermarking upper bound · p. 9
  • 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.Source: B. Proof of the watermarking upper bound · p. 9
  • 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.Source: B. Proof of the watermarking upper bound · p. 9
  • 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.Source: B. Proof of the watermarking upper bound · p. 9

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.

Related papers

Loading 2608.31091v1…