Minimax bounds for watermarked and masked recursive discrete distribution estimation

• URL: http://arxiv.org/abs/2608.31091v1
• Date: Mon, 31 Aug 2026 17:00:09 GMT
• Title: Minimax bounds for watermarked and masked recursive discrete distribution estimation
• Abstract summary: In the absence of a distinguishing mechanism, it has been shown that adding synthetic samples significantly reduces the marginal efficacy of new real samples.<n>We show that it is impossible to improve performance by adding watermarks unless the false negative rate of detection also vanishes.<n>We propose masking, a randomization procedure that narrows the gap in the remaining regimes to a Jensen gap.
• Score: 15.724207170366846
• License: http://creativecommons.org/licenses/by/4.0/
• 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 papers

• Tightening the Score Matching Gap for Diffusion Models [33.16787042554974]
  We develop tighter bounds for three metrics: KL divergence, reverse KL divergence, and Wasserstein distance.<n>Our results suggest that the quality of the score approximation has more impact on closing the score matching gap for low noise scales.
  arXiv  Detail & Related papers  (2026-07-05T18:00:32Z)
• Sample Complexities of Estimating Gumbel--Max Watermark Proportions with and without Reduction to Pivotal Statistics [4.346179456029564]
  Watermarking promises statistical traceability of large language model (LLM) uses, but real documents rarely arrive as purely human-written or purely LLM-generated.<n>We study this watermark proportion estimation problem under the Gumbel--max watermarking mechanism.<n>We develop a Laguerre-polynomial estimator and establish a matching information-theoretic lower bound for the sample complexity.
  arXiv  Detail & Related papers  (2026-06-30T22:04:35Z)
• Corrected Samplers for Discrete Flow Models [36.348940136801296]
  A line of recent work has studied samplers for discrete diffusion models, such as tau-leaping and Euler solver.<n>We establish non-asymptotic discretization error bounds for those samplers without any restriction on transition rates and source distributions.<n>We rigorously show that the location-corrected sampler has a lower complexity than existing parallel samplers.
  arXiv  Detail & Related papers  (2026-01-30T03:53:22Z)
• Combating Noisy Labels through Fostering Self- and Neighbor-Consistency [120.4394402099635]
  Label noise is pervasive in various real-world scenarios, posing challenges in supervised deep learning.<n>We propose a noise-robust method named Jo-SNC (textbfJoint sample selection and model regularization based on textbfSelf- and textbfNeighbor-textbfConsistency)<n>We design a self-adaptive, data-driven thresholding scheme to adjust per-class selection thresholds.
  arXiv  Detail & Related papers  (2026-01-19T07:55:29Z)
• Self-Guided Generation of Minority Samples Using Diffusion Models [57.319845580050924]
  We present a novel approach for generating minority samples that live on low-density regions of a data manifold. Our framework is built upon diffusion models, leveraging the principle of guided sampling. Experiments on benchmark real datasets demonstrate that our approach can greatly improve the capability of creating realistic low-likelihood minority instances.
  arXiv  Detail & Related papers  (2024-07-16T10:03:29Z)
• A Huber Loss Minimization Approach to Mean Estimation under User-level Differential Privacy [32.38935276997549]
  Privacy protection of users' entire contribution of samples is important in distributed systems. We propose a Huber loss minimization approach to mean estimation under user-level differential privacy. We provide a theoretical analysis of our approach, which gives the noise strength needed for privacy protection, as well as the bound of mean squared error.
  arXiv  Detail & Related papers  (2024-05-22T08:46:45Z)
• Risk-Sensitive Diffusion: Robustly Optimizing Diffusion Models with Noisy Samples [58.68233326265417]
  Non-image data are prevalent in real applications and tend to be noisy. Risk-sensitive SDE is a type of differential equation (SDE) parameterized by the risk vector. We conduct systematic studies for both Gaussian and non-Gaussian noise distributions.
  arXiv  Detail & Related papers  (2024-02-03T08:41:51Z)
• Saliency Grafting: Innocuous Attribution-Guided Mixup with Calibrated Label Mixing [104.630875328668]
  Mixup scheme suggests mixing a pair of samples to create an augmented training sample. We present a novel, yet simple Mixup-variant that captures the best of both worlds.
  arXiv  Detail & Related papers  (2021-12-16T11:27:48Z)
• Exploiting Sample Uncertainty for Domain Adaptive Person Re-Identification [137.9939571408506]
  We estimate and exploit the credibility of the assigned pseudo-label of each sample to alleviate the influence of noisy labels. Our uncertainty-guided optimization brings significant improvement and achieves the state-of-the-art performance on benchmark datasets.
  arXiv  Detail & Related papers  (2020-12-16T04:09:04Z)
• The Hidden Uncertainty in a Neural Networks Activations [105.4223982696279]
  The distribution of a neural network's latent representations has been successfully used to detect out-of-distribution (OOD) data. This work investigates whether this distribution correlates with a model's epistemic uncertainty, thus indicating its ability to generalise to novel inputs.
  arXiv  Detail & Related papers  (2020-12-05T17:30:35Z)
• Log-Likelihood Ratio Minimizing Flows: Towards Robust and Quantifiable Neural Distribution Alignment [52.02794488304448]
  We propose a new distribution alignment method based on a log-likelihood ratio statistic and normalizing flows. We experimentally verify that minimizing the resulting objective results in domain alignment that preserves the local structure of input domains.
  arXiv  Detail & Related papers  (2020-03-26T22:10:04Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.