Near-optimal algorithms for private estimation and sequential testing of collision probability

This paper studies the problem of estimating, given samples from a discrete distributions, the collision probability of the distribution to within an additive (constant) factor. The collision probability is the probability that a pair of samples from the distribution collides (equals the same value), and is essentially equivalent to the well-studied second moment of the distribution. For a distribution with support size  $k$ and probabilities $p_1, \ldots, p_k$, the collision probability is $\sum_{i=1}^{k} p_i^2$. The goal is to estimate this quantity to within an additive error of $\pm \epsilon$.

As mentioned, estimating the second moment of a distribution is a classical problem in statistics and data analysis. However, most of the literature (for example, all of the streaming literature) focuses on multiplicative  $(1+\epsilon)$-approximation of these quantities, rather than additive approximation. In many interesting cases, an $\epsilon$-additive approximation is much more crude (and consequently, much easier to compute) than a  $(1+\epsilon)$-multiplicative one. Indeed, it is not hard to see for example that the collision probability is smaller than  $\max \{p_1, \ldots, p_k\}$, so for any distribution that doesn't have an heavy hitter with probability more than $\epsilon$, returning the value $0$ or $\epsilon$ would trivially satisfy the approximation requirements.

The main two contributions of the authors are as follows:

1. A differentially private estimator for the collision probability in the local DP model. The sample complexity for local $(\alpha, \beta)$-DP estimation to within additive error $\epsilon$ is $O(\log (1/\beta) / \alpha^2 \epsilon^2)$, an improvement by a factor of $1/\epsilon^2$ over previous work [Bravo-Hermsdorff et al., NeurIPS 2022]. Notably the results in Bravo-Hermsdorff et al. are in the pure DP local model, whereas here the results are in the approximate setting.
2. An estimator, not differentially private, for the sequential setting where we do not know $\epsilon$ in advance and need to test whether the collision probability is equal to some value $c_0$ (null hypotheses) or $\epsilon$-far from it in additive terms. The sample complexity, for constant success probability, is $O(\log \log (1 / \epsilon) / \epsilon^2)$, and it is standard and easy to see that this is optimal up to the lower order term.

Given samples from a probability distribution $p$ on a universe of size $k$, the collision probability is defined as $\sum_{i=1}^k (p_i)^2$. This paper studies the problems of privately estimating and sequentially testing the collision probability. This paper first gives a locally differentially private algorithm for estimating the collision probability up to additive error $\varepsilon$, provided the number of samples is roughly $O\left(\frac{1}{\varepsilon^2}\right)$. The paper then gives a tester for collision probability that distinguishes whether the input distribution has some collision probability $c$ or is $\varepsilon$-far from $c$, using roughly $O\left(\frac{1}{\varepsilon^2}\log\log\frac{1}{\varepsilon}\right)$ samples.

The LDP mechanism chooses a salt uniformly at random and sends a one-bit hash by applying a hash function to the dot product of the salt and user's sample. The server then partitions the users into a number of groups, compares the collision frequency within each group, corrects the bias, and outputs the median across the groups.

The tester similarly computes the number of pairwise collisions, corrects the bias, and rejects if the resulting estimated collision probability is too large from $c$.

This work considers the problem of estimating or testing collision probabilities given samples from an unknown distribution in two interesting settings: local privacy and sequential testing. For the former problem, the goal is to develop a sample- and communication-efficient mechanism that achieves $(\alpha,\beta)$-privacy in the usual DP sense, with the local constraint ensuring that privacy is maintained even with an untrusted server. When $\alpha,\beta>0$, this work extends prior work of Bravo-Hesdorff, et al. [Neurips'22] by providing a distributed hashing-based approach that achieves sample complexity $O(\log(1/\beta)/\alpha^2\varepsilon^2)$ to attain $\varepsilon$ additive accuracy with constant probability. This is complemented with a lower bound for the case $\beta=0$, where it is shown that the denominator is necessary. The sequential testing problem is as follows: given a value $c_0\in [0,1]$ and error probability $\delta$, query samples from the distribution and either (i) never reject with probability at least $1-\delta$ if the true collision probability is $c_0$, or (ii) if the true collision probability is at least $\varepsilon$-far from $c_0$, reject after $N(\varepsilon,\delta)$ samples with probability $1-\delta$ with minimal $N(\varepsilon,\delta)$. In this case, this work shows that $N(\varepsilon,\delta)\leq O(\log(\log(1/\varepsilon)/\delta)/\varepsilon^2)$ is sufficient, while $\Omega(\log(1/\delta)/\varepsilon^2)$ is necessary. The upper bound is attained by leveraging powerful martingale inequalities to analyze the deviations of an appropriate estimator.

This paper studies the problem of estimating the collision probability(CP) of a discrete distribution, where CP is the L2 norm of the probability vector. CP estimation is well motivated and has applications to a number of areas in statistics. This work considers the problem in the distributed privacy setting where there are a number of users that have a single sample drawn from a distribution. The aim is to design a mechanism that lets the users communicate their information to a central server, such that the server can determine the CP without learning too much about the sample held by any particular user.

The solution presented in the paper improves upon the state of the art in terms of the minimum number of samples required to ensure the privacy guarantees are met. The proposal is nearly optimal in the sample complexity, as shown by lower bound is also provided in the paper. The authors implement their algorithm and test it on a dataset, to find that the algorithm performs better in practice as well.

The authors also consider the problem of sequential testing in the standard non-private setting, where one has sample access. Here the task is to test whether the CP is some value c_0 or if it additively epsilon far from c_0. The sequential testing problem also requires that the test be adaptive in terms of epsilon, when the epsilon is unknown. Here they provide an algorithm nearly optimal in epsilon.

The authors propose some creative techniques (involving salts and hashes) to estimate the collision probability of a discrete distribution in a locally private manner, and a sequential test for collision probability. These two contributions appear to have little to do with each other (the second being non-private and using different techniques).

While the paper was on the borderline after reading the reviews and responses, after reading the paper and proofs myself, I recommend a rejection. Apart from several missing discussions to related work mentioned by reviewers, I found a bug in the proof of the sequential test, specifically Lemma 5. While the final result might be correct in spirit, the current proof is irreparably and fundamentally incorrect. Below, I propose a fix that the authors can implement in a revision (which may also significantly simplify the proof).

The major bug in the proof of Lemma 5: the invocation of the time-uniform martingale bound of Howard et al. in (12) is incorrect. While it is true that Y_i(p) is bounded, its bound depends on i and increases with i. The stated bound \phi(i,\delta) applies only in the 1-subGaussian case: otherwise there is a price to pay for the subGaussian constant, which in this case even changes with time. So that bound cannot be directly plugged in.

The proof also has several minor typos: Theorem 8.1.1 is attributed several times to Tsybakov, and once to de La Pena and Gine, while only the latter reference is correct. Near the bottom of Pg 21, |Y_k| <= 4m, but perhaps it should be 4k (here is where the bound depends on the index k). After (12), there is a missing bracket for Y_i(p), and it is mentioned that each term is subGaussian, but the subGaussian constant is not mentioned, while here it is particularly important because it increases with time. The definition of \bar U_m might also be missing a normalization by m(m-1).

In my view the above proof technique is not salvageable, though the authors may manage to do this with some effort. A different approach is to directly use the confidence sequences for (possibly degenerate) U-statistics and V-statistics provided in Section 4.2 of "Martingale Methods for Sequential Estimation of Convex Functionals and Divergences, T. Manole and A. Ramdas, IEEE Transactions on Information Theory (2023)". I believe that the lower and upper confidence sequences (for bounded kernels) will be of the same order as the one used from Howard et al, but it might significantly shorten and simplify the proof, since it bypasses the decoupling techniques employed here.

Apart from this, following reviewer suggestions, I recommend that the authors seriously discuss the related work in terms of papers on locally private heavy hitters, and on multiplicative approximation of collision probability, and the possibility of applying these techniques to other related problems (especially since some other cited papers handle several problems at once, not just collision probability).

Reject