We study statistical watermarking by formulating it as a hypothesis testing
problem, a general framework which subsumes all previous statistical
watermarking methods. Key to our formulation is a coupling of the output tokens
and the rejection region, realized by pseudo-random generators in practice,
that allows non-trivial trade-off between the Type I error and Type II error.
We characterize the Uniformly Most Powerful (UMP) watermark in this context. In
the most common scenario where the output is a sequence of $n$ tokens, we
establish matching upper and lower bounds on the number of i.i.d. tokens
required to guarantee small Type I and Type II errors. Our rate scales as
$\Theta(h^{-1} \log (1/h))$ with respect to the average entropy per token $h$
and thus greatly improves the $O(h^{-2})$ rate in the previous works. For
scenarios where the detector lacks knowledge of the model's distribution, we
introduce the concept of model-agnostic watermarking and establish the minimax
bounds for the resultant increase in Type II error. Moreover, we formulate the
robust watermarking problem where user is allowed to perform a class of
perturbation on the generated texts, and characterize the optimal type II error
of robust UMP tests via a linear programming problem. To the best of our
knowledge, this is the first systematic statistical treatment on the
watermarking problem with near-optimal rates in the i.i.d. setting, and might
be of interest for future works.

通过将统计水印技术作为一种假设检验问题进行研究，我们建立了一个通用框架，涵盖了所有以前的统计水印方法，并通过在实际中使用伪随机生成器将输出符号和拒绝域进行耦合，实现了类型 I 错误和类型 II 错误之间的非平凡权衡。我们描述了在这种情境中的均匀最有力（UMP）水印。对于输出为 $n$ 个符号序列的最常见情况，我们对所需的 i.i.d. 符号数量的上下界进行了匹配，以保证较小的类型 I 错误和类型 II 错误。我们的比率与每个符号的平均熵 $h$ 相关，因此大幅改进了先前作品中的 $O (h^{-2})$ 比率。对于检测器缺乏模型分布知识的情况，我们引入了模型无关水印技术，并为类型 II 错误增加的最小值界限建立了最小化界限。此外，我们还制定了鲁棒水印问题，允许用户对生成的文本进行一类扰动，并通过线性规划问题表征了鲁棒 UMP 检验的最佳类型 II 错误。据我们所知，这是第一个在 i.i.d. 设置中具有近乎最优速率的水印问题的系统统计处理，对于未来的研究可能具有兴趣。

走向最佳的统计水印技术

Towards Optimal Statistical Watermarking

An important aspect of multiple hypothesis testing is controlling the
significance level, or the level of Type I error. When the test statistics are
not independent it can be particularly challenging to deal with this problem,
without resorting to very conservative procedures. In this paper we show that,
in the context of contemporary multiple testing problems, where the number of
tests is often very large, the difficulties caused by dependence are less
serious than in classical cases. This is particularly true when the null
distributions of test statistics are relatively light-tailed, for example, when
they can be based on Normal or Student's $t$ approximations. There, if the test
statistics can fairly be viewed as being generated by a linear process, an
analysis founded on the incorrect assumption of independence is asymptotically
correct as the number of hypotheses diverges. In particular, the point process
representing the null distribution of the indices at which statistically
significant test results occur is approximately Poisson, just as in the case of
independence. The Poisson process also has the same mean as in the independence
case, and of course exhibits no clustering of false discoveries. However, this
result can fail if the null distributions are particularly heavy-tailed. There
clusters of statistically significant results can occur, even when the null
hypothesis is correct. We give an intuitive explanation for these disparate
properties in light- and heavy-tailed cases, and provide rigorous theory
underpinning the intuition.

本文主要介绍如何在多重假设检验中通过对空假设的控制以及对数据是否独立等因素的考虑，来有效地控制显著水平，同时探讨在不同的分布下，统计假设结果的线性相关性会带来的影响并提出解决方案。