Minimax bounds for watermarked and masked recursive discrete distribution estimation
2026-08-31 • Information Theory
Information TheoryMachine Learning
AI summaryⓘ
The authors study how adding watermarks to synthetic data samples affects the ability to estimate distributions when real data is limited. They find that if very few real samples are available, adding watermarks doesn't help unless the method to detect them almost never misses watermark signals. They compare different estimation methods and show that simple estimators perform nearly as well as theoretical limits. They also introduce a randomization technique called masking to improve performance in some cases, and suggest there may be ways to better understand the remaining gaps in their results.
watermarkingsynthetic samplesdistribution estimationminimax lossfalse negative ratedeterministic estimatorsrandomizationmaskingJensen gaporacle-assisted estimation
Authors
Millen Kanabar, Michael Gastpar
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.