Search papers, labs, and topics across Lattice.
This paper investigates the minimax loss associated with recursive discrete distribution estimation when incorporating watermarks, revealing that adding watermarks does not enhance performance unless the false negative detection rate decreases. The authors establish a lower bound demonstrating that the marginal efficacy of real samples diminishes as synthetic samples increase, particularly when the fraction of real samples approaches zero. Additionally, they introduce a masking technique that mitigates the performance gap in certain scenarios, suggesting potential for further refinement of lower bounds.
Adding watermarks to synthetic samples can actually degrade performance unless detection accuracy improves, challenging common assumptions in distribution estimation.
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.
