Optimal Algorithms for Augmented Testing of Discrete Distributions

presentation

Thank you for your feedback. The algorithm is given on page 8 of the main body. We give technical overview in Section 2 before the algorithm to give a high level picture about how our upper bounds and lower bounds (in the appendix) fit together to give a complete characterization of the augmented distribution testing problems we study.

Intuition behind our algorithm

For the closeness testing problem, we use the hint distribution to $\hat{p}$ to reduce the $\ell_2$ norm of $p$, the unknown distribution. Intuitively, we can do this by looking at the ‘heavy hitters’ of $\hat{p}$: the domain elements that $\hat{p}$ assigns a high probability mass to. Then we split the mass of all heavy elements equally among many synthetically created domain elements. If we see such an element $i$ from our sample from $p$, we perform a thought experiment where we instead sample uniformly from the synthetically created domain elements corresponding to $i$. This does not change any of the TV distances, but significantly reduces the $\ell_2$ norm of $p$ (formalized in Lemma 3.1). A smaller $\ell_2$ norm makes the testing problem significantly easier, as done in prior works. Please see Section 2 for intuition about our other results. For further details, please see Section 2 and Section 3 in the main body.

Comparisons to the previous work

[29] is an example of studying distribution testing when both samples and a prediction distribution $\hat{p} = p$ are available. However, their algorithm does not receive $p$ directly and can only query $p$. Since they do not see the whole $p$, they would require samples from it as well. They consider two types of queries: querying the probability of a certain domain element $p(i)$, or querying the probability of the first $i$ elements for a given $i$. In comparison to our model, their assumption on the accuracy of the prediction is very strong as they assume $p = \hat{p}$. They also consider an alternative model with multiplicative noise, which is still a stronger assumption compared to ours. However, their model is weaker in another sense, as they do not have access to $\hat{p}$ for free. The total cost of their algorithm involves the number of queries they make to $\hat{p}$ and the number of samples (which they describe it as queries to the sampling oracle). For testing uniformity and identity, they have shown that $\Theta(1/\epsilon)$ queries are necessary and sufficient. Given their upper bounds and our lower bounds, it can be concluded that solving the problem in our model is more difficult, meaning it would require many more samples. Please see Section 1.3 for more detailed comparison to prior related works.

Sample complexity

For $s_f$, we have two possibilities, either it is equal to $n^{2/3} \alpha^{1/3} / \epsilon^{4/3}$ or it is equal to $n$. For the first case, it is not too hard to see that the equation will be $O(s_f) = O(n^{2/3} \alpha^{1/3} / \epsilon^{4/3})$. Now, assume $s_f$ is $n$. This case, implies that: $n \leq n^{2/3} \alpha^{1/3} / \epsilon^{4/3} \leq n^{2/3}/\epsilon^{4/3}.$ Hence, there is an interdependence between the parameters: $n \leq 1/\epsilon^4$. Therefore, one can conclude $n \leq \sqrt{n}/\epsilon^2$. Therefore, both expressions in the sample complexity equate to $O(\sqrt{n}/\epsilon^2)$. Maybe it is helpful to note that in this case: $\sqrt{n}/\epsilon^2 \geq n^{2/3}/\epsilon^{4/3} \geq n^{2/3} \alpha^{1/3}/\epsilon^{4/3}$. Hence, our lower bound is not violated. [In case we did not answer this question adequately, please leave us a comment, and we will try to clarify further.]

Suitability for the conference

We would like to point out that many related works on distribution testing have appeared in recent ML conferences such as NeruIPS/ICML/ICLR. These works are relevant to the learning-theory, privacy, algorithmic statistics, and sublinear algorithms community within ML. Please see below for a small sample of such related works that appeared in recent NeurIPS conferences that we cite in our work. Our references in our submission list additional related works in other top ML venues. [4] J. Acharya, Z. Sun, and H. Zhang. Differentially private testing of identity and closeness of discrete distributions. NeurIPS 2018

[5] Jayadev Acharya, Constantinos Daskalakis, and Gautam Kamath. Optimal testing for properties of distributions. NeurIPS 2015

[8] Maryam Aliakbarpour, Mark Bun, and Adam Smith. Hypothesis selection with memory constraints. NeurIPS 2023 [9] Maryam Aliakbarpour, Ilias Diakonikolas, Daniel Kane, and Ronitt Rubinfeld. Private testing of distributions via sample permutations. NeurIPS 2019

[24] Clement L. Canonne, Ilias Diakonikolas, Daniel Kane, and Sihan Liu. Nearly-tight bounds for testing histogram distributions. NeurIPS 2022

[27] Clement L Canonne, Gautam Kamath, Audra McMillan, Jonathan Ullman, and Lydia Zakynthinou. Private identity testing for high-dimensional distributions. NeurIPS 2020

[45] Ilias Diakonikolas, Daniel M. Kane, and Alistair Stewart. Sharp bounds for generalized uniformity testing. NeurIPS 2018

Weaker assumptions about prediction

Thank you for suggesting an interesting open direction! It is not clear to us if our predictor assumption can be relaxed while retaining similar guarantees. We believe our model is quite natural, but there could certainly be other weaker assumptions which are powerful enough to give improved sample complexity. However, we note that our algorithms are robust, so even if the predictor assumptions do not hold, we never lose asymptotically on the sample complexity compared to classical algorithms without predictions.

Experiments on identity testing and uniformity testing

We focused on closeness testing since it is the hardest statistical task out of the three distribution testing problems we studied: it generalizes identity and uniformity testing, and a larger sample complexity is required, both in the classical and augmented settings. We suspect that one can see similar qualitative gains from using our augmented algorithms, provided that appropriate predictions are available.

Clarification on evolving distributions

For our results, the algorithm requires access to a prediction distribution $\hat{p}$, which is intended to be close to the unknown distribution $p$ (in addition to samples from $p$). Our algorithms are applicable in settings where the extra information available about $p$ can be translated into a distribution $\hat{p}$. In our introduction, we strive to depict various scenarios where such predictions can be available, including slowly evolving distributions such as network traffic data or search engine queries. Mathematically, we consider a series of slowly changing unknown distributions: $p_1, p_2, \ldots, p_t$. In this setting, the empirical distribution of the samples from $p_1, p_2, \ldots, p_{t-1}$ can serve as a prediction for $p_t$. For example, the distributions of search queries change slightly every hour or so. However, the overall empirical distribution of search queries from the past year could be a good prediction for the distribution at a particular hour. We will clarify this in our introduction. Continual testing while the distributions undergo small perturbations at every step is a very interesting open question. Although our results do not directly address this problem, we believe that some techniques from augmented flattening could potentially be helpful in solving this problem as well.

Studying two predictions

Thank you for suggesting an interesting open direction. We did not consider this case in our paper. First, we would like to mention that our upper bound still holds when two predictions are provided. It is not too difficult to adapt our augmented flattening to incorporate both $\hat{p}$ and $\hat{q}$. The sample complexity in this setting is proportional to the minimum of $\alpha_p^{1/3}$ and $\alpha_q^{1/3}$. However, the lower bounds do not hold. As you pointed out, one can hope to achieve better sample complexity if the distance between the two predictions is more than $\alpha_p + \alpha_q + \epsilon$. In particular, estimating the probability of the Scheffé set gives us either a 'reject' or 'inaccurate information' result for one of the distributions. On the other hand, when $\hat{p}$ and $\hat{q}$ are identical, our lower bound indicates that one cannot hope for better sample complexity. It remains an open question to study the case where the distance between the two predictions is smaller than $\alpha_p + \alpha_q + \epsilon$, but larger than zero.

Connection to testable learning

Yes, in both cases, the algorithm is given an option of forgoing to solve the problem when the underlying assumption does not hold. Although there is no notion of ``augmentation’’ in that line of work.