Minimax bounds for watermarked and masked recursive discrete distribution estimation
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.
Related
- Maximum principle for discrete-time stochastic recursive games driven by fractional noises
- Nonparametric hazard rate estimation with associated kernels and minimax bandwidth choice
- Discrete Diffusion Models are Minimax Optimal Under Sparsity
- Minimax rates for pointwise CATE estimation: the role of design smoothness
- On the bias distribution of pseudo-linear regression algorithms for recursive identification
BibTeX
@misc{kanabar2026minimax,
title = {{Minimax bounds for watermarked and masked recursive discrete distribution estimation}},
author = {Millen Kanabar and Michael Gastpar},
howpublished = {arXiv},
year = {2026},
month = aug,
doi = {10.48550/arxiv.2608.31091},
eprint = {2608.31091},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2608.31091},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Minimax bounds for watermarked and masked recursive discrete distribution estimation
AU - Millen Kanabar
AU - Michael Gastpar
PY - 2026
DA - 2026/08/31
PB - arXiv
DO - 10.48550/arxiv.2608.31091
UR - https://arxiv.org/abs/2608.31091
AB - 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.
ER -