Importance of the work

Indeed, our work falls into the latter category that the reviewer points out: we address an established open problem from the work of Gopi et al. (COLT 2020), on achieving improved algorithms for non-interactive LDP hypothesis selection. This paper has received 41 citations (a reasonable number for theory works in this space), including from works that directly try to understand the role of interactivity in LDP hypothesis selection (Pour et al., COLT 2024), giving further evidence towards the importance of the problem. Breaking the $O(k^2)$ sample barrier (and making it "half way" to $\tilde O(k)$) is a significant step forward, since as far as we are aware, all prior methods for hypothesis selection which bypass $O(k^2)$ comparisons (in both the private and non-private settings) require substantial interactivity.

Experimental evaluation

While experimental evaluation would indeed be interesting, we choose to fit our work with existing work in this field, by studying theoretical properties of algorithms. This is established as the first-order goal in the area of hypothesis selection, given the precedent not only in the work of Gopi et al. (COLT 2020), but also several recent papers on this problem published in NeurIPS in particular, including Bun et al. (NeurIPS 2019), Aliakbarpour et al. (NeurIPS 2023), Aliakbarpour et al. (NeurIPS 2024), none of which consider experimental evaluation. Such investigation would be interesting, but is outside the scope of our present work.

The statements of Theorems 1 and 13 claim $\tilde{O}(k^{5/2})$ preprocessing time, but then in footnote 3 on page 7 it's admitted this assumes certain comparisons between distributions can be done in constant time. This feels to me like a lie even if it's close to the truth. It would be good to be more upfront in telling the reader this extra factor is missing.

Thanks for this comment. Indeed, the running time of preprocessing could vary based on the precise access to the hypotheses. While we consider our assumption to be fairly mild, we will increase clarity by being explicit about the exact operations one can perform on the hypotheses and their respective cost.

The local differential privacy scenario isn't described explicitl until line 160 ("each user holds an independent datapoint $x \sim p$") as far as I can tell. Not a serious problem, since it's the obvious scenario to study (instead of, I don't know, maybe each individual holds one of the distributions ?). Still, I think it would be good to say it explicitly earlier.

Thanks for pointing this out. We will update the discussion in Section 1 (before summary of existing results) to highlight that the LDP setting we consider is where each user holds an independent sample from the distribution $p$.

Lines 30-32: what notion of adjacent databases were those papers assuming when they showed $O(\log{k})$ samples suffice? (Or, almost equivalently: what does one user contribute to the database?) Worth mentioning in my opinion, unless you are really having trouble with the page limit.

The results which achieve $O(\log k)$ hold under essentially any neighboring relation (e.g., add/remove or substitution of a single point), which is rather similar to our work. However, the key difference with our work (resulting in the exponential difference in the dependence on $k$) is the semantics on privacy. Specifically, the $O(\log k)$ works assume a trusted curator (i.e., the central DP model), who is allowed to see all the (sensitive) data in the clear. In contrast, our work makes much weaker assumptions, in that no trusted party exists (i.e., no trusted curator, the local DP model), which necessarily incurs a $\mathrm{poly}(k)$ cost.

Theorem 1: $\alpha$ is missing a logical quantifier. For example one way to resolve this would be to add "for every $\alpha>0$" at the end of line 61, and then perhaps on line 62 replace $n>n_0$ with $n \geq n_0(\alpha)$ . Maybe there's a better way to write it. (Now that I write this, maybe it's better the way it's written now, even if it's a bit imprecise.)

Thanks for raising this point. We have implicitly required $n_0$ to depend on the values of $\alpha$ and $\beta$ and also that the guarantees hold for any $\alpha$ and $\beta$. We agree that it could be more precise if we include that the guarantee holds for any $\alpha$ and $\beta$.

Line 157: "...with small probability": the probability is only small if the LDP parameter is large. I personally wouldn't write "small" here since I think the best LDP setting would be something like so user privacy is well-protected.

Great point, we will adjust this wording.

Line 167: "Let ...": is not defined at this point. (The next sentence makes it clear $S$ is the sample.)

Thank you, we will make this clearer.

Some notes about the proof of Theorem 17

Thank you for your very careful reading and the helpful suggestions to improve clarity. We will make all the suggested changes.

Line 281: What does $\alpha$-separated mean?

In this case we mean that the distributions are at most $\alpha$-far in $\ell_1$-distance. However, there is a factor of $2$ missing from the conjecture as stated by Gopi et al. and it is missing from our counterexample as well. We will correct this and make a note of it.

Line 284: the arXiv version of [GKK+20] says "with high probability" here. Not sure how much that matters.

We think this use of "high probability" by Gopi et al. is a small typo (in particular, it is not clear what the probability is over) and thus we have removed it in our statement.

I didn't really understand the discussion on lines 286-291...

Our goal is not to estimate $\Vert q_i - q_j \Vert_1$ as that is already known at preprocessing time. Rather, our goal is to somehow check which of $q_i$ and $q_j$ is closer to the unknown distribution $p$ given (locally privatized) sample access to $p$. The reviewer is right that the connection between Conjecture 18 and sample-efficient LDP hypothesis selection is rather non-trivial. Unfortunately, this non-triviality makes it unclear whether we can make it self-contained without essentially reproducing the proof of Lemma 4.1 of Gopi et al. Instead, we we highlight the fact that this connection is not obvious and direct the interested reader to the proof of Lemma 4.1 of Gopi et al.

Line 307: "Since $\phi f_1 = \mathbf{1}/m...$": I don't think that's necessarily the case.

The reviewer is correct, and we have made that change, thank you.

Scheffé vs. Scheffe

Good eye! We thought about this and made the explicit choice to have the non-accented version in the title. This is because accented characters may be more difficult for scrapers and indexers to capture. It also is a bit more cumbersome to typeset in bibtex. To avoid all these issues, we went with the simpler non-accented version. There is precedence for such a decision, see, e.g., "Hyperparameter Tuning with Renyi Differential Privacy" in ICLR 2022.

Lack of empirical validation. The absence of experimental comparisons with existing algorithms limits the paper’s contributions to theoretical aspects.

Indeed, our work focuses on theoretical aspects of this problem. This is established as the first-order goal in the area of hypothesis selection, given the precedent not only in the work of Gopi et al. (COLT 2020), but also several recent papers on this problem published in NeurIPS in particular, including Bun et al. (NeurIPS 2019), Aliakbarpour et al. (NeurIPS 2023), Aliakbarpour et al. (NeurIPS 2024), none of which consider experimental evaluation. Such investigation would be interesting, but is outside the scope of our present work.

Potential of the Scheffé graph

As the reviewer correctly identifies, we use the triangle substructure to prove a domination number bound of $\tilde O(k^{3/2})$. We further show that the triangle substructure alone will not allow one to do better than $\tilde \Omega(k^{3/2})$. This raises the question of whether additional graph structure would help go beyond, towards reaching the optimal bound of $\tilde O(k)$.

Though we did not include them in the paper, to guide our theoretical investigations, we did run some simulation results for small values of $k$ (i.e., $k < 20$). We found that the Scheffé graph tends to be much denser than the bare triangular substructure would suggest and that the correct bound may in fact be $\tilde O(k)$ as a result. Unfortunately, there are a few computational challenges that preclude evaluation on larger $k$. Primarily, since the Dominating Set problem is known to be NP-complete, such simulations amount to brute force computation. Secondarily, the number of nodes in the Scheffé graph grows quadratically, increasing the computational burden. Nonetheless, we view our simulation results as some evidence towards an $\tilde O(k)$ domination number, and will include discussion to this effect.

Explain footnote 1: why the stated approximation factor includes the problem when $p$ is one of the $q_i$?

In the main text, we only mention the special case where $p$ is one of the $q_i$'s, in which case the reviewer is correct and the approximation factor is irrelevant: since $OPT = \min_{q \in Q} \|q - p\| = 0$, then multiplying by an arbitrary approximation factor will still be $0$. However, Gopi et al. (COLT 2020) actually prove a more general result: they show an agnostic-style guarantee (i.e., where $OPT \neq 0$), albeit with a substantially weaker approximation guarantee than what we're aiming for. We tried to capture this in the footnote; to further address weakness 2 of the reviewer (requesting a more precise comparison with prior work), we are revising it to the following:

The footnote: We simplify for the sake of presentation: they actually show a slightly stronger result. Let $OPT = \min_{q \in Q} \|q - p\|$. Roughly speaking, their Lemma 4.1 provides a non-interactive $\varepsilon$-LDP algorithm such that, given $n = \tilde O(k/\alpha^4\varepsilon^2)$ samples, it outputs a distribution $\hat q$ such that $\|\hat q - p\| \leq O(\sqrt{\log k}) \cdot \sqrt{OPT} + O(\alpha)$. Note that, compared to our desired $O(1) \cdot OPT$ guarantees, their result degrades quadratically in the value of OPT, and weakens as the number of hypotheses $k$ becomes large.

Differential privacy not explained when reviewing previous work (and definition is late, on page 3, after the theorem).

We feel that differential privacy's technical definition is not necessary to understand the background for our work, and many readers will already have an informal familiarity with the notion. Hence, we placed it slightly later in order to not interrupt the narrative. We will provide a forward pointer to the definition in order to assist unfamiliar readers.

Definition 3 about differential privacy is unclear. In particular, each individual i must be an algorithm satisfying Definition 2? If so, what is a multi-dimensional space for individual I (how many dimensions does it have, what are they, etc.)?

Clarify Definition 3 in the context of the considered problem, and explain, preferably in the context of Lemmas 9 and 10, why the algorithm satisfies LPD.

Thanks for the comments -- it would be helpful if the reviewer can clarify what parts of the definition are unclear. The input space $\mathcal{X}$ for each individual is an arbitrary set. The space $\mathcal{Y}$ containing the messages is arbitrary as well. We've added the sets $\mathcal{X}$ and $\mathcal{Y}$ to the definition so it is a little easier for the reader to infer the arbitrary nature of the input/message space. We will replace Definition 3 with the following, which is hopefully clearer.

Definition 3: Suppose there are $n$ individuals, where the $i$-th individual has datapoint $X_i$. A protocol is non-interactive and $\varepsilon$-local differentially private if, for every $i \in [n]$, individual $i$ computes and outputs a (randomized) message $m_i(X_i)$ (where $m_i : \mathcal{X} \rightarrow \mathcal{Y}$ is a randomized function, depending only on the datapoint $X_i$ and potentially the index $i$), and $m_i$ is $\varepsilon$-differentially private. That is, for all $i \in [n]$, any $X_i, X_i' \in \mathcal{X}$, and any event $E \subseteq \mathcal{Y}$, we have that

$

\Pr[m_i(X_i) \in E] \leq e^\varepsilon \Pr[m_i(X_i') \in E].

$

To clarify the relation with Lemmas 9 and 10: it is not hard to show that Randomized Response (as described by Lemma 9) is $\varepsilon$-LDP since the ratio of the two output probabilities is between $e^{-\varepsilon}$ and $e^\varepsilon$, as required by Definition 3. The proof is omitted since it is an established result, but we will provide a reference and include the above informal discussion. As for Lemma 10, privacy in this case is inherited from privacy of Lemma 9, since each individual applies Randomized Response exactly once to their data. We will add a sentence making this clear as well.

Some results (e.g., Lemma 9) are not clearly referenced (are they new or otherwise should state reference to the original work producing them)

Thanks for pointing this out: Randomized Response (Lemma 9) is an established mechanism in this space, and we will provide the appropriate citations (Warner '65, Evfimievski et al. '03, Kasiviswanathan et al. '08).

Line 118: explain acronyms PMF and PDF

Corrected (probability mass and density function, respectively), thank you.

Line 119: $\Delta(\cal{X})$ not defined

Fixed (the probability simplex over $\cal{X}$), thank you.

Line 163: what is “workload of queries”?

Thanks for bringing this to our attention. We will remove the unclear phrase from the statement of the lemma and will explain the workload in the exposition.

Where is Lemma 9 used?

Why is LPD guaranteed by Lemma 10?

As mentioned in a previous response, Lemma 9 is implicitly used in the proof of Lemma 10 (in terms of both its formulation and privacy guarantees), which we will edit for greater clarity. Essentially, we will re-write $y(x)$ as $RR(x)$ and include a remark that the mechanism satisfies the same LDP guarantee by the postprocessing property of DP (which we will also reference).

The current analysis is tied to binary‐valued, signed Scheffé functions. In practice, many model-selection tasks rely on real-valued or multi-ary statistics (e.g., log-likelihood ratios). Can the authors explain how to extend the tests beyond signed tests? Could one swap in the Laplace or Gaussian mechanism to privatize a bounded real-valued score and still retain the dominating-set advantage—at the cost of only a constant-factor blow-up in the sample complexity?

Unfortunately, standard log-likelihood ratio tests cannot, in general, solve our problem of hypothesis selection due to the required "agnostic" guarantees (i.e., outputting a hypothesis which is constant-factor competitive with the closest one in the set of hypotheses), even in the non-private setting. Section 6.4 of Devroye and Lugosi's book "Combinatorial Methods in Density Estimation" has a more detailed discussion of this issue. Note that the prior work of Gopi et al. (COLT 2020) employs a type of log-likelihood ratio test to privately perform an easier variant of hypothesis selection, achieving much weaker agnostic guarantees than we require. Unfortunately, in Section 6.2 we show that their core "flattening" technique cannot be improved to achieve the full desired agnostic guarantees. It is not clear whether any type of log-likelihood ratio test can achieve constant factor agnostic guarantees for hypothesis selection (with or without privacy) and it remains an interesting direction for further study.

The proofs track the variance introduced by randomized response, but there is also the usual sampling noise because each user contributes just one i.i.d. draw from p. Where exactly do you bound the deviation that includes both sources?

Lemma 10, which is the key component in our probabilistic analysis, takes into account both sources of randomness. In Line 170, for any functional $T$, the curator takes an average over all $\ell$ noisy data points $y(x),x\in S_{\pi(T)}$ that are sent to the the curator. In Line 172, it is proven that for each $x\in S_{\pi(T)}$, the expected value of the random variable $\frac{e^{\varepsilon}+1}{e^{\varepsilon }-1} y(x)$ is equal to $\langle p,T\rangle$. This expectation is with respect to both sources of randomness; the randomness incurred by the randomized response, and by $x\sim p$. In each expectation here, the sources of randomness are indicated in the subscript. The Hoeffding's inequality in Line 174 is bounding the probability with respect to both of these sources that the empirical estimate $\hat{p}_T$ calculated using the random variables $y(x)$ is close to their expectation, i.e., $\langle p,T\rangle$. Finally, the union bound guarantees this bounded deviation with respect to the randomized response and i.i.d. draws from the distribution for all the functionals in $\mathcal{T}$. We're happy to make this clearer in the final version of the paper.