Query-Efficient Locally Private Hypothesis Selection via the Scheffe Graph
Authors: Gautam Kamath
Alireza F. Pour
Matthew Regehr
David Woodruff
Venue: NeurIPS 2025 poster ()
Keywords: differential privacy
hypothesis selection
Primary area: social_and_economic_aspects_of_machine_learning

Abstract: We propose an algorithm with improved query-complexity for the problem of hypothesis selection under local differential privacy constraints. Given a set of $k$ probability distributions $Q$, we describe an algorithm that satisfies local differential privacy, performs $\tilde{O}(k^{3/2})$ non-adaptive queries to individuals who each have samples from a probability distribution $p$, and outputs a probability distribution from the set $Q$ which is nearly the closest to $p$. Previous algorithms required either $\Omega(k^2)$ queries or many rounds of interactive queries.
    Technically, we introduce a new object we dub the Scheff\'e graph, which captures structure of the differences between distributions in $Q$, and may be of more broad interest for hypothesis selection tasks.

Query-Efficient Locally Private Hypothesis Selection via the Scheffe Graph *
Gautam Kamath
Alireza F. Pour University of Waterloo alireza alireza.atthol hataaaaattttolhhpouuuaaaatooooo
University of Waterloo and Vector Institute g0esail.. mit.
Matthew Regehr
David P. Woodruff Carnegie Mellon University dwoodruf@cs cmu. edu
University of Waterloo matt. rett.rreeerruuuatrloo..oo
Abstract
We propose an algorithm with improved query-complexity for the problem hypothesis selection under local differential privacy constraints. Given set of k probability distributions Q, we describe an algorithm that satisfies local differential privacy, performs (1:3/2) non-adaptive queries individuals who each have samples from probability distribution and outputs probability distribution from the Q which is nearly the closest to p. Previous algorithms required either ((A²)) queries many rounds of interactive queries. Technically, we introduce a new object we dub the Scheffé graph, which captures structure the differences between distributions in Q, and may be of more broad interest for hypothesis selection tasks.
1 Introduction
Hypothesis selection refers to the following statistical question: given n samples from a distribution and descriptions of l: distributions Q, output distribution which is as close to p as possible. More precisely, for an a > 0, the goal is to output a distribution & such that
1 p|l O(1) min ||q p|l a. qEQ
In other words, the & disttneee between p and the output distribution ğ most constant factor larger than that of the closest distribution q" Q. up to some additional additive eтror a. How many samples are needed for this task, and what algorithms do we use do it? This fundamental primitive serves as an important building block for many other statistical estimation tasks. Furthermore, it generalizes one of the most classic problems in statistics, simple hypothesis testing, wherein the distribution is promised to be exactly equal to one of the distributions Q.
Many classical works (e.g.. Yat85 DL96, DL97 DLÖI) address and resolve these questions, showing that n = O k) samples suffice. That is, we require only logarithmicclly-many samples in order identify the (near-)best distribution. Subsequently, many other works have studied hypothesis selection subject to other constraints and desiderata, including computational efficiency, robustness, weaker access hypotheses, and more (see. e.g., [MS08 DDS12 DK14 SOAJ14]
AJOSI4 DKK 16 AFJ 18 BKM19 BKSWI9 GKK 20))
We focus the constraint of differential privacy (DP) (DMN066, rigorous notion of data privacy that guarantees that a procedure will not leak too much information about individual points in the
Authors are listed in alphabetical order.
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

dataset. DP has been adopted in practice by numerous organizations, including Google [XZA 23]. Apple [Di and the US Census Bureau [AACM -M 22]. Under the central notion of DP, wherein there exists trusted curator who may observe the sensitive dataset directly, Bun, Kamath, Steinke, and Wu showed that Ollog k) samples still suffice to perform hypothesis selection [BKSW 19 BKSW21
However, central DP requires a trusted curator, a strong assumption when operating on sensitive data. Instead, one can consider local DP (LDP) [War65] EGS03 KLN+ in this setting, every dataholder makes their own outputs DP before sharing them with anyone else. This offers much stronger privacy semantics than central DP, but also requires more data for most tasks.
Work by Gopi, Kamath, Kulkarni. Nikolov, Wu, and Zhang [GKK* 20] initiated the study of hy- pothesis section under local DP [GKK 20). In this case, each user holds independent sample from the unknown distribution p. Unfortunately, lower bounds of Duchi and Rogers for sparse mean estimation imply that (2))) samples are necessary for this problem [DR19] exponentially more than the Olog k) samples which suffice for the central DP setting.
With this barrier in mind, |KKK 20) proved two main results. First, they provided an ((k)) sample algorithm for locally private hypothesis selection. This matches the lower bound of Duchi and Rogers up to logarithmic factors, and subsequent work by Pour, Ashtiami, and Asoodeh improves the upper bound to O(k) [PAA24), matching the lower bound up to constant factors. The major caveat of both these algorithms is that they require interactivity. This is because the specific queries asked to each dataholder depend on the outputs provided by earlier dataholders (i.e., the queries are selected adaptively). This style of interactivity can non-starter for real-world deployments of local DP. If one desires non-interactive algorithm, straightforward privatization of the celebrated Scheffé tournament requires O(k²) samples.
[GKK 20 improve upon this with their second main result, a non-interactive ssk)-slmple algorithm, but for the simpler problem of k-wise simple hypothesis testing, where the distribution p is promised to be equal to one of the distributions E Q
To summarize, we highlight three existing results under LDP:
An interactive O(k)-sample algorithm for hypothesis selection;
A non-interactive O(k*) -sample algorithm for hypothesis selection; and
A ion-interactive Ö(k) sample algorithm for simple hypothesis testing.
1.1
Results and Techniques
Our main result improves upon all of these, providing a non-interactive --samle algorithm for LDP hypothesis selection, where Ō(f) f polylog(f). Definitions are given in Section 2 Theorem 1. Given set of l distributtinns Q and 0(k5/2) expected preprocessing timq there exists a non-inteructive e-locally differentially private algorithm with the following guarantees. For any a, B >> 0, there is
1//2 Vog log(k/3)
no S
a?E2
such that given n. 2 no samples from a distribution p. then with probability at least 1 B the algorithm outputs a distribution q E Q satisfying
| - p|l S 13
min 1q p/1 ax. QEQ
In fact, by applying our algorithm recursively in GKKK 20), also get multi-roum procedure with improved sample complexity.
We simplify for the sake of presentation: they actually show slightly stronger result. Let OPT minge I|q p.l. Roughly speaking, their Lemma 4.1 provides non-interactive e-LDP algorithm such that, given O(k/a"e" samples. outputs distribution such that || pll O(yTog VOPT + O(a). Note that, compared to our desired ((1) OPT guarantees, their result degrades quadratically in the value of OPT, and weakens as the number of hypotheses k: becomes large.
PPreprocessing involves computing many probabilities 9( (E) E Q. which we treat constant-time. 'See Algorithm in [GKK 20) Subsection 5.4. Corollary follows immediately by applying their technique with their I-round subroutine replaced by ours and using slightly modified subdivision rate тe := 2/(3' 1) well as larger random set [H] O 2-1-1 - ((8--1) in the final round account for improved base rate.

---

Corollary 2. Given set of l distributions Q and ( expected preprocessing time, there exists
t-round E-locally differentially private protocol with the following guarantees. For any a, 3 there is
Vlo k log(k/3)
no S
a²
such that given no samples from distribution p. then with probability at least 1 - B the algorithm outputs a distribution q E & satisfying
4 pll S 39 min pll a.
PEQ
To prove Theorem [ we first introduce in Section 3 generalization of the classical minimum distance estimator that accepts any collection of queries that is rich enough to facilitate comparisons between any pair of distributions. Next, we show in Section 4 how standard tools from differential privacy can be used non-interactively estimate the queries under local privacy. Our final and most crucial step is to introduce in Section 3 new combinatorial object, the Scheffé graph. This is a directed graph whose vertices correspond to possible queries that locally private hypothesis selection algorithm may ask and whose directed edges indicate when one query gives sufficient information to answer another query.
queries that yield sufficient information to answer all queries and we show that there indeed exists such small such set of queries. Theorem
natural to ask for a minimal
then follows immediately by combining Theorem 12 in Section with Theorem 14 in Section below.
The natural question is whether our bound be strengthened achieve an Ö(k) sample complexity for non-interactive locally private hypothesis selection. A core part of our analysis involves showing an ((13/2) bound on the domination number of any Scheffé graph if this could be improved to Ökk), then it would produce the desired result. However, in Section 6.1 we provide a nearly-matching lower bound on the domination number, showing that additional structure must be employed to go beyond this barrier.
Another approach to designing an Ō(k) sample algorithm is based on a suggestion [GKK + 20 A key technical component of their work is so-called flattening lemmaa they point out that specific strengthening would lead to an (kk sample algorithm. In Section 6.2 provide concrete counterexample to such strengthening, showing that it is not achievable.
1.2 Related Work
Hypothesis selection is classical statistical task. This style of approach was introduced by Yatra- cos (Yt85), and further developed in subsequent work by Devroye and Lugosi [DL9 DL97 [LO1. The most relevant line of work to ours studies hypothesis selection under differential privacy constraints [BKSW19 AAK21 GLW2I GKK 23, PAA24] However, all of these works ei- ther study weaker notion of privacy, require interactivity, require more data, apply to weaker problem than our work. Another line of work focuses on algorithms for (non-private) hypothesis selection that minimize the number of comparisons or the amount of computa- tion [MS08] DDS12 DK14 SOAJ14 AJOS14 AFI 18 ABS24]. While many of these algorithm require only near-linear number of comparisons between hypotheses, they unsuitable for purposes as they perform adaptive queries, which would result in an interactive protocol in our setting. There are a number of other works on hypothesis selection, focusing on desiderata including robust- ness [DKK 16 BBKLL23) approximation factor [BКM19 BBK #22 memory constraints [B33)). and more [QCR20 AAC+23
24] There has also been significant work into hypothesis test- ing under local DP DJWI3 DJW17 GRI8 Shel8 ACFT19 ACTI9 JMNRI9] AZ24 PAJL24 PJL24]. though this often focuses on the non-agnostic case (i.e.. when the distribution is exactly equal to one of the given distributions) and A = 2. For more coverage of private statistics, see [KU20].
2 Preliminaries
We recall the classic definitions of differential privacy (DP) and sequentially interactive local differ- ential privacy (LDP):
3

---

Definition 3 (DMMS006). An algorithm M 2 + y is e-differentially private if. for all X' N that differ exactly one entry and S _ y, we have that
(x) E S] - e Pr(M(X') S).
Definition 4 ([ar65 EGS03
11N+ A t-round sequentially interactive protocol is defined by the following interaction between users and central server. Suppose there are n. users, where user i {l....,TL has datapoint X; E X. During round
{l,....,]] of communication, the central server transmits arbitrary messages new subset Uj S (I....,n) U - Up of users in parallel. These users transmit randomized messages back to the server in parallel. The messages sent by the server may depend on messages it received during any of the previous rounds of communication and the messages sent by a user may depend on her datapoint X, well the message she received from the server. We say that the protocol is s-locally differentially private (LDP) if the record of all messages in all rounds of communication transmitted from the users to the server is e-DP with respect to the datapoints (X1,..., Xn). If 1, we say that the protocol is non-interactive.
We also recall the notion of dominating set in directed graph.
Definition 5. Let G = (V, E") be a digraph. A dominating set for G is a subset D S V of vertices such that that, for every vertex w E V, either w D, or there is E D such that (u, w) E. i.e. there is an edge v + w. We call the size of a minimal dominating set the domination number of G, which we write as dom
We will sometimes say a vertex v dominates a set of vertices W, which means that for each w E W, either U or there is edge + w. In the same vein, say that of vertices U dominates set W if each w E W is dominated by some v E U.
Finally, recall the classical Scheffé test. Note that we frequently conflate distribution q with its mass function (density in the continuous setting) to make expressions such as q(x) and (q. T`) legible.
Definition 6. For a pair of distributions q. s' E A(X) over a domain X, we denote by 8(x) ((x) o' (x) the difference functional from to o' and we denote by
[+1 if((x) 2 (((x) S(x) = sgg]=(()(())) = [-1 if((x) < (())
the signed Scheffé set from q to to.
In some sense, "querying" the signed Scheffé set S is the best possible measure of the & distance between q and q', formalized in the following lemma.
Lemma 7. For any distributions and g' with signed Scheffé set S,
sup 1l ,T). llq o (8, () TE(-1,13*
The classical Scheffé test between q and q' involves sampling data from some unknown distribution calculating an estimate ds of (p, S), then returning if (g. S) is closer to Ps than (g', and returning q' otherwise. This estimator can be shown (DLOT to obtain eerrro at most
3 min f [|q
pll,, Il' - p } + (p, S) - psl-
The Relaxed Minimum Distance Estimator
In this section, we develop estimator for k distributions with similar guarantee to that of the classical Scheffé test. We assume that we are given access to some estimates Pr of (p. T) where p is unknown distribution and where T belongs to family of queries T. Moreover, under the LDP constraints, each query frr requires fresh data, so we would like some estimator that only makes small number of distinct queries to p.
Definition 8 (Relaxed Minimum Distance Estimator (RMDE)). Let Q C (XX) be a funite set of distributions and suppose we have collection T of functionals T [_1,1] as well as a sequence of query results PT = (fr)TeT. The relaxed minimum distance estimate given the query results is
q(pT)
arg min sup (g, T) p-
gEQ TET

---

The following theorem provides theoretical guarantees for the RMDE similar to the Scheffé test, it can be decomposed into the error from the optimal hypothesis plus approximation error over the set of functionals 'T
Theorem 9. Let Q be a finite set of distributions over X and let T S {-11,1} be set of functionals with the property that, for each q: q E Q, there is some E T satisfying
- -/, <1yg 9''l--
Then, for any distribution p and query results PT = (fr)
l(((Ā)) - p|l1 s (1+ 21+ pll1 20-1
sup (p prl TET
where q" == arg min yeq l1q - pll denotes the closest distribution to p.
One could take the query set T to be all (*) signed Scheffé sets between pairs q. E Q. This recovers the classical minimum distance estimator [LOM], and would satisfy the theorem condition with o I. Our goal will be obtain a smaller query set T (which will translate into fewer queries and samples), at the cost of a smaller value of Φb
Proof. Write q = ((²)) for short. Clearly, 1l4 pll I 11g" pll + ll q" 2ll .. so we will just focus on bounding |1 q² ||
Now, by + there must be some 7 'I for which
وا - 9 s 6 Kr- q² T'
$ Φ
sup K4 q², T
TET
< 16-
sup (g. T) - Prl + sup (q",T) - (2r)
TET
TET
20-1 sup [g"", ,T) -prl
TET
26
sup
K'4" - -p,7% sup Kp, T7 pT)
TET
TET Kp, T) prl
S 26- "11""
p|l + 2
sup TET
where the last inequality follows from Lemma
4 Non-Interactive Locally Differentially Private RMDE
In this section, we explain how to get accurate estimates of fr of (p, T3 under e-LDP. Consequently, we will achieve non-interactive LDP hypothesis selection by calculating all of these estimates in parallel and then supplying them to the relaxed minimum distance estimator.
We first recall randomized response, which is classical mechanism that ensures local privacy by flipping the response bit with small probability. This introduces a (correctable) bias.
Lemma 10 ([War65) EGS03 IL)+ Randomized response is the randomized function RR, that receives x E 1- and outputs x with probability ट①4 and -x with probability ह Randomized response satisfies E-LDP.
Assuming each user holds an independent datapoint z p. we can estimate our workload of queries (p, T') under LDP by applying randomized response to T(x) for each user, averaging, and correcting the bias introduced by RR..
Proposition 11. Let T be a collection of functionals T {-1,1]². Then there is an s-LDP mechanism which requires m O [T] log (IT)/B) samples and computes estimates pT (or)
a²
such that with probability at least - 3, we have (p,T)) prl S for all T e T.
5

---

Proof. Assume we have sample S from distributed locally among users. The curator divides the sample into [T] disjoint subsets S1, SIT) each of size = | = 0 log (1T)/)) Fix an enumeration on the functionals in T. For each T T, every user in Sa(T) with sample sends m(x)= == RR₂ (T())) the curator, who computes pr
(
a²
e--1 EEES...r m(x)) This protocol
e1+1
satisfies s-LDP by Lemma 10 Now, we claim that ++ mx) is an unbiased estimate of (p, T). Indeed, E
m(z)
<'+1 e-11
- -4 Ex((x)l)
[T(]]] {p, T). ef+1 e'+l -
Moreover, -- m(x) for Sa(r) l i.i.d. random variables with values in
We
can therefore apply Hoeffding's inequality to conclude that
P PlPT - (p, T>) 2 aj P
E +1
Σ m(x))
-p, 2
-
E
(EES.CT)
la
I exp
S B//T//
2
of
where the last line follows from the fact that for E E (0. 1), we have (== ((1/=²). The union bound yields lpr (p. T)1 S a for all T E T with probability at least |3, as desired.
Combining Theorem 9 and Proposition I have the following.
Theorem 12. Let be of k distributions over X and let T be set functionals T 1-1,1) with the property that, for each q' E Q, there is some T E T satisfying
Vlq - ,T,T)) 01 4'111.
Then, RMDE is an e-LDP algorithm that requires =0 ( [ (1T)/9) samples with the following
property. For any distribution it outputs distribution 9 such that with probability at least 1 - 3
1 - p11 S 20=+1=1"'14"--- + a,
where q" arg min |1q p|1 denotes the closest distribution to p.
Our remaining task to prove Theorem ! iis to find small set T of queries that satisfies the property with Φ (1)..
The Scheffé Graph
In order outfit RMDE with an appropriate them down by exploiting their shared information structure.
T, we will begin with the Scheffé sets and pare
Definition 13. Given distributions .I...., 9k E ((X), the induced o-Scheffé graph the digraph with vertice (()) ((i,)') 1 < < < k) and edge (i,i') - {i.j'} whenever
Ko Sw)) 61|ō
where kg 0; 4z' and Sw is the signed Scheffé set set from qi to qu-
Now recall that a dominating set in a digraph is a subset D its vertices V such that every vertex V either belongs to D
Now (D), namely v is an out-neigh of some vertex in D.
Since (6,, Sy |6,و | by Lemma 7 then clearly for any dominating set D the é-Scheffé graph, T (Spr (i.j' } D} will satisfy condition (x) of Theorem 9 so our main goal in this section is to demonstrate the existence of a small dominating set. particular, we show that the
1/6-Scheffé graph for any set distributions has domination number (133/2).
MMore generally, write (*) {A C X
A
t} for shorthand.

---

Theorem 14. For Φ 1/6 and any distributions 91..... 9e the induced é-Scheffé graph has domi- nation number at most 4/3/2 Vlg k. Moreover, there exists a randomized preprocessing algorithm that finds a dominating set of this size in 0 Vlgg k) expected time.
Note that this bound may be loose. We ran simulations for randomly selected Q and observed weak empirical evidence that the domination number behaves as (k)). This is because, for small values of (namely 20), the Scheffé graph appears to much denser than the following analysis suggests.
In any case, the first step to proving the bound is to examine the structure of a fixed triangle {"i,"", (i'.."") [i,"") We will argue that, if there small fillngtth (relative to the other vertices), then each vertex sends an edge to at least one other vertex in the triangle. On the other hand, if vertex has very small & fi-length, then can show that the remaining two vertices must share a bidirectional edge.
vertices whose corresponding has
Proposition 15 (Triangular Substructure). For Φ 1/6, the induced Φ-Scheffé graph on any distributions .u.....9 9 has the following triangular structure. For every {5.5', E (.)). the graph has least one of the following edge structures:
(i) (i.j") + 83'
(i) (i.')
(mi) (i,'' -..'""''''""
The argument relies on the following geometric property of triangle in metric space.
Lemma 16. For any three points x, y, in a metric space with metric d, let a == d(x, v), b = d(r, 2). and c d(y, 2) denote the lengths of each leg of the triangle zyz. Then either
1 - and a S 2 or a S
1 a =bb and a
1
3 Gc If > 1b, then
To prove the lemma, assume the first condition fails, namely a certainly a > b and, by the triangle inequality,
y or a > J..
1 (c-a) a)
3
1
2 2
3
The case } analogous.
Proof of Proposition 15 For simplicity, let j 1, j' 2, and j" 3. With an eye toward the
geometric lemma, assume first that 612 is "short", i.c.
|812|| 1リ2 11daal11 = ||ا2ا||
In this case, since 623 = 613 812, the triangle inequality yields
[1021111 (823, S2a)l < 16 S2a)1 + (201,) (613, S2a) [|
so
1 2 (1|ō1111 || |11) 2 - =1ó1s|1a
1613, S23)1 2
||ő2s||: || 2 2 ||625|1=
and thus we have an edge 32,3) (1. By symmetry we also have edge {1,3) (2,3).
On the other hand, by Lemma [6 the remaining case to consider is that
111211
|613 11 1d2zl11.
3
Then, since 812 813 823, we have
||612|| = 1612. Steil S (613. S12)1 + 1622, S12)1-
By averaging, either (813, T12) 2 11112111 > 3 111111112 so we have an edge (1,2) + {1,3), or
(822, S12) 2 112l1 > 1622 1I. in which case get edge {1,2] (2,3).
0

---

The consequence of this triangular substructure is that the graph must have relatively dense edges and thus only relatively few vertices can be supported by small number of other signed Scheffé sets.
Proposition 17. For any r 2 1, the 1/6-Scheffé graph on any k distributions has at most 3kr vertices with degree less than
Proof. Suppose not. By averaging over the following covering of the vertex set
= U.....U
where = fo V: j v), there must be some j for which Vj contains at least 3r vertices with
:=
in-degree less than r. Call these vertices Bj. Now, for any pair of vertices {j,j'} + {j. in Bj, either [j. ++ {i.j",, {J', "") fi.j", {j', J") {i.j") by Proposition 15 That is, for each pair of vertices V + e in Bj. there at least one corresponding edge that lands in B,. so
[B
1 B,((BB) 1).
Σ dm)(v) 2 BEB,
By averaging again, there must be some v E By for which
dm(u)) 2 2 (|B - 1) 2 2
(3r nr,
which is a contradiction.
We proceed by dominating vertices with small in-degree separately from vertices with large in-regeee.
Proof of Theorem 14
To that end, set r := vk loggh and let B be those vertices with in- less than r. By the previous proposition, |B] S 3/-8/2 Vlogk. k.
Now, draw uniformly at random subset R of size l t= k3/2 Vogg/oog/ K from the whole vertex set V. For fixed v e V B.
F(v Nowr (R)) (IVI (IVI-du(tt)
[V| di((t) )
(
( ( din(v)
(I
don(v) - 11+1 V1-
(V))
V
V -1
V di((v)
< 22-da(0)//M
< 2-2
V
By the union bound, P(V B & (R)) S Evevi P(u & Now Vou(R))) S VV/ S 1/2, so, by the probabilistic method, there must some E (1) that dominates V B, in which case D = B U R is dominating set of size at most [B] + S 4/3 Vlg K.
As for finding such a dominating set algorithmically, pick R E (AS/AVIOEN uniformly at random. {a, b) R, add and its triangular out-neighbours by checking {a, i} and {b, i} for each i E [k] \ v. By the preceding calculation, R together with all uncovered vertices in the hashtable is a dominating set of size at most 4//322 /log k with probability greater than 1/2, repeating until this is the case achieves the desired expected runtime.
Iterate
hashtable in O(k) time
6 Barriers to a Near-Linear Algorithm
The ideal algorithm for non-interactive locally private hypothesis selection would require only Ō(k) samples, matching known lower bounds for the problem [RR9 GKK +20. In this section, we rule out two different approaches one could employ to design such an algorithm.
'We treat the time to check whether 1g q Swr'l 2 وbgg; qr as single unit of computation. In practice, this requires computing integral and depends on how the distributions are stored in memory.

---

6.1 An ( Lower Bound under Triangular Substructure Assumption
One could conceive of a strengthening of Theorem 14 which argues that the domination number of any Scheffé graph is Ōkk). Unfortunately, we argue that the triangular substructure described in Proposition 15 is insufficient to yield better bound than ((k3/2). Therefore, to go beyond this bound, one must employ additional structure of the Scheffé graph.
Theorem 18. For all sufficiently large k, there is a digraph Gg on vertices (()) satisfyyng the triangular substructure condition of Proposition 13 for which
k3/2
dom (Gx)
8y klog (2(13312).
Proof. Draw uniformly at random a set R of size f == 1 1/3/2 Vlog h from the vertex set V = =(h) For a fixed vertex u = {a, b} V, consider the set of indices
- = {i E [M] : {a, i), {b,1} E R}
that form a triangle with v in which both vertices other than v land in R. We aim to show that this set is small with high probability. Indeed, setting 2 2oog k the union bound yields
(V1-2
- 2)
P 2 2
Σ JE((ANV
P((fa, ((U
2-26
e(k -(k--2 2)
i 21
(e(k 2)
1/2 log k 1 1)²
k(k: 2)
2log k
8
(h 1)2
$1/2
S1
< 2 2 log 1/k2
By another union bound, we can show that all such sets are likely to be small simultaneouslyy i.c. P(3v E V. 1 2 t) < IV/Rk² < 1/2, so there must be some R C V of size { = 1//3/22 /log K for which all 1.7 have size less than t 2 log k.
We can now form the bad digraph G5 on the vertex set V by adding edges as follows. For every {a, b) E V and every E [k] \ v.
E E (b. & R =
{a, b} + ib,
{a, R. (b, e R
{a, b} + {a,
otherwise = {a, + {a, or (a, b} - (b,i) arbitrarily.
Clearly, every triangle of G& satisfies either condition (ii) (iii) of Proposition 15] Moreover, for a vertex v = {a, . it can only dominate an element {a, i} or (b. i) of R if both a. i} and (b, i) most
belong R, namely i E 7... Therefore, including itself, v dominates
7. 2 log
elements of R, so any dominating set must have size at least 21og 8ylog
[R]
13/2
6.2 A Counterexample to Flattening
Another possible technique for non-interactive LDP hypothesis selection is that of flattening, which discussed 20),+ The following conjecture (Question 4.4 in that work), states that any collection of distributions over a finite domain can be mapped to distributions close to uniform while still preserving their pairwise É -ddisttaccs.. Note that the original conjecture contained minor mistakes as it was written writeen-including including missing factor of wo--wich we have corrected.
Conjecture 19 (Flattening). Let 41....,4k E A(ni)) be distributions that are separated in é1- distance by at most 2a. Then there exists a randomized map & : [m] -> [m] satisfying
1. For all 1 S j < k and y E [m], 1-a m I (v) < I+a and

---

2. For all " k. lóg;
Qqg ll2 E @(llg; - -1rll1)
where bq means the distribution of ((xx) x q-
the conjecture is true, then one can in effect compare any two distributions 9j and q3z by applying the mapping & to each and then comparing them separately the uniform distribution 24( ([mm).. In this case, only k comparisons to the intermediary uniform distribution are required to gain information about all (2) pairwise comparisons. These comparisons can be carried out in parallel with a small number of samples each, leading to non-interactive L.PP hypothesis selection. For more details see the proof of Lemma 4.1 in [GKK 20 Unfortunately, we show that this conjecture is false.
Counterexample Flattening Conjecture. For simplicity, we identify distribution with its mass function as a column vector in Rn or R and a sequence of distributions (q),-...()) .Ix) with the matrix Q whose columns f1:-... 9g- Similarly, matrix (LSM) in T so that (óq1...., Φqx) is just matrix multiplication p(.1......
identify a stochastic map e with left stochastic
Consider the n X n identity matrix E := In- We construct additional distributions that, for the purposes of flattening, will conflict with the columns of E. To that end, let H denote the n x n Hadamard matrix, i.e., Hij == -))()) mod 2 where and j are viewed as binary strings of length log Key properties of this matrix are that H/ / is orthonormal, every pair of columns differs in exactly n/2 entries, and every column sums to O, except for the first column which is all ones. Now, let F be n x n matrix whose first column fi is the uniform distribution 1/n and whose jth column fg is the jth column of И with -1 replaced by 0 and +1 replaced by 2/n. In this case, Q = -E, F' E Rank (A: = 2n) consists of distributions separated & -diitanec by at most 2.
Now, assume we have LSM & E R satisfying the first condition dQ E [0, 2/m] mmn,, In particular, all entries of Φ = & must fall in [0,2/m). On the other hand, by construction we have H = J2 .i,..., fa fi), so, since 1 H is orthonormal, we have
/n
l1o(f1, f2 f.. f /00/ / = 10 I mm(2/m)2//n 4/m.
By averaging, there must be some (fi f2 f1...., fn - }i} for which
|ø & ml ml|ooo13 & m (6f
fn -n f1 4/n.
Provided that > 4, this is impossible for fi because || = 1, so there must be 1 < <is isn such that | - hf || S 2/ = o(1) = o(Ilsi - -ill)).
Conclusion
In this work we introduce two new techniques for hypothesis selection.
The first is a relaxation of the classical minimum distance estimator in which the Scheffé sets replaced by any collection of queries that is diverse enough for E f1-comparisons between any pair of candidate distributions.
The second is a new object called the Scheffé graph that contains structural information about the relationship between queries hypothesis selection algorithm might ask. Our analysis of the Scheffé graph reveals a dense triangular substructure that can be exploited to yield a non-trivial reduction in query complexity. We show that analysis of query complexity arising from the triangular substructure is nearly tight, so any further reduction in query complexity via the Scheffé graph will require the discovery of additional graph substructure.
Combining these two techniques yields an algorithm for non-interactive hypothesis selection under LDP constraints with state-of-the-arr sample complexity, though we stress that our techniques are relevant to hypothesis selection problems more broadly.
Acknowledgments
GK is supported by Canada CIFAR AI Chair, an NSERC Discovery Grant, and an Ontario Early Researcher Award. MR supported by an NSERC CGS-D scholarship. DW supported by Simons Investigator Award and Office of Naval Research award number 126477.
10

---

References
[AAC*23] Anders Aamand, Alexandr Andoni, Justin Y. Chen, Piotr Indyk, Shyam Narayanan, and Sandeep Silwal. Data structures for density estimation. In Proceedings of the 40th International Conference on Machine Learning. ICML '23, pages 1-18. JMLR, Inc., 2023.
[AAC*24] Anders Aamand, Alexandr Andoni, Justin Y. Chen, Piotr Indyk, Shyam Narayanan, Sandeep Silwal, and Haike Xu. conisstial-cmmpuaatiinnaal trade-offs for density estima- tion. In Advances in Neural Information Processing Systems 37, NeurIPS '24, pages 97907-97921 Curran Associates, Inc., 2024.
[AACM*22] 22] John Abowd, Robert Ashmead, Ryan Humings-Menool Simson Garfinkel, Micah Hei- neck, Christine Heiss, Robert Johns, Daniel Kifer, Philip Leclere, Ashwin Machanava- jjhala, Brett Moran, William Sexton, Matthew Spence, and Pavel Zhuravlev. The 2020 census disclosure avoidance system topdown algorithm. Harvard Data Science Review, Special Issue 2, 2022.
[AAK21] Ishaq Aden-Ali, Hassan Ashtiani, and Gautam Kamath. On the sample complexity of privately learning unbounded bigh-dimensional gaussians. Proceedings of the 32nd International Conference on Algorithmic Learning Theory, ALT '21, pages 185-216. JMLR, Inc., 2021.
[ABS23] Maryam Aliakbarpour, Mark Bun, and Adam Smith. Hypothesis selection with memory constraints. In Advances in Neural Information Processing Systems 36, NeurlPS '23, pages 50453-50481. Curran Associates, Inc., 2023.
[ABS24] Maryam Aliakbarpour, Mark Bun, and Adam Smith. Optimal hypothesis selection in (almost) linear time. In Advances in Neural Information Processing Systems 37, NeurIPS '24, pages 141490-141522 Curran Associates, Inc., 2024.
[ACFT19] Jayadev Acharya, Clément L. Canonne, Cody Freitag, and Himanshu Tyagi. Test without trust: Optimal locally private distribution testing. In Proceedings of the 22nd International Conference on Artificial Intelligence and Statistics, AISTATS '19, pages 2067-2076. JMLR, Inc., 2019.
[ACT19] Jayadev Acharya, Clément L. Canonne, and Himanshu Tyagi. Inference under infor- mation constraints: Lower bounds from chi-square contraction. In Proceedings of the 32nd Annual Conference Learning Theory, COLT '19, pages 1-15, 2019.
[AF]* 18] Jayadev Acharya, Moein Falahatgar, Ashkan Jafarpour, Alon Orlitsky, and Ananda Theertha Suresh. Maximum selection and sorting with adversarial com- parators. Journal of Machine Learning Research, 19(1):2477-2477, 2018.
[AJOS14] Jayadev Acharya, Ashkan Jafarpour, Alon Orlitsky, and Ananda Theertha Suresh. Sort- ing with adversarial comparators and application density estimation. In Proceedings of the 2014 IEEE International Symposium on Information Theory, ISIT '14, pages 1682-1686. IEEE Computer Society, 2014.
[AZ24] Shahab Asoodeh and Huanyu Zhang. Contraction of locally differentially private mechanisms. IEEE Journal on Selected Areas Information Theory, 5:385-395, 2024.
[BBK 22] Olivier Bousquet, Mark Braverman, Gillat Kol, Klim Efremenko, and Shay Moran. Statistically near-optimal hypothesis selection. In Proceedings of the 62nd Annual IEEE Symposium on Foundations of Computer Science, FOCS '21, pages 909-919, IEEE Computer Society, 2022.
[BKKL23] Shai Ben-David, Alex Bie, Gautam Kamath, and Tosca Lechner. Distribution learn- ability and robustness. In Advances in Neural Information Processing Systems 36, NeurIPS '23, pages 52732-52758, Curran Associates, Inc., 2023.
11

---

[BKM19]
Olivier Bousquet, Daniel M. Kane, and Shay Moran. The optimal approximation factor in density estimation. In Proceedings of the 32nd Annual Conference on Learning Theory, COLT '19, pages 318-341, 2019.
[BKSW19] Mark Bun, Gautam Kamath, Thomas Steinke, and Zhiwei Steven Wu. Private hypoth- esis selection. In Advances in Neural Information Processing Systems 32, NeurIPS '19, pages 156-167. Curran Associates, Inc., 2019.
[BKSW21] Mark Bun, Gautam Kamath, Thomas Steinke, and Zhiwei Steven Wu. Private hy- pothesis selection. IEEE Transactions on Information Theory, 6703):181-2000, 2021.
[DDS12] Constantinos Daskalakis, Ilias Diakonikolas, and Rocco A. Servedio. Learning Poisson binomial distributions. In Proceedings of the 44th Annual ACM Symposium on the Theory of Computing, STOC 12, pages 709-728. ACM, 2012.
[Dif17] Differential Privacy Team, Apple. Learning with privacy scale. https: /machinnelearning.appepep apple. wwwm///cc/o//o/io//nnaaaaa with sech--pvvayy-a-t--ee scale aapleadlterreriilllrraayyyyyyaae pdf December 2017.
[DJW13] John C. Duchi, Michael I. Jordan, and Martin J. Wainwright. Local privacy and statistical minimax rates. In Proceedings of the 54th Anmual IEEE Symposium on Foundations of Computer Science, FOCS 13, pages 429 429-438. IEEE Computer Society, 2013.
[DWW17] John C. Duchi, Michael I. Jordan, and Martin J. Wainwright. Minimax optimal proce- dures for locally private estimation. Journal of the American Statistical Association, 2017.
[KK14] Constantinos Daskalakis and Gautam Kamath. Faster and sample near-optimal algo- rithms for proper learning mixtures of Gaussians. In Proceedings of the 27th Annual Conference on Learning Theory, COLT 14, pages 1183-1213, 2014.
[DKK 16] Ilias Diakonikolas, Gautam Kamath, Daniel M. Kane, Jerry Li, Ankur Moitra, and Alistair Stewart. Robust estimators in high dimensions without the computational intractability. In Proceedings of the 57th Annual IEEE Symposium on Foundations of Computer Science, FOCS 11,, pages 655-664. IEEE Computer Society, 2016.
[DL96] Luc Devroye and Gábor Lugosi. universally acceptable smoothing factor for kernel density estimation. The Annals of Statistics, 249992299-- 1996.
[DL97] Luc Devroye and Gábor Lugosi. Nonasymptotic universal smoothing factors, kernel complexity and Yatracos classes. The Annals of Statistics, 2566):2666-2677, 1997.
[DL01] Luc Devroye and Gábor Lugosi. Combinatorial methods in density estimation. Springer, 2001.
[DMN066] Cynthia Dwork, Frank McSherry, Kobbi Nissim, and Adam Smith. Calibrating noise sensitivity in private data analysis. In Proceedings of the 3rd Conference on Theory of Cryptography, TCC '06, pages 265- 285,, Berlin, Heidelberg, 2006. Springer.
[DR19] John Duchi and Ryan Rogers. Lower bounds for locally private estimation via com- munication complexity. In Proceedings of the 32nd Annual Conference on Learning Theory, COLT 19, pages 1161-1191, 2019.
[EGS03] Alexandre Evfimievski, Johannes Gehrke, and Ramakrishnan Srikant. Limiting privacy breaches in privacy preserving data mining. In Proceedings of the 22nd ACM SIGMOD- SIGACT-SIGART Symposium on Principles of Database Systems, PODS '03, pages 211-222. ACM, 2003.
(GKK+20) Sivakanth Gopi, Gautam Kamath, Janardhan Kulkarni, Aleksandar Nikolov, Zhi- wei Steven Wu, and Huanyu Zhang. Locally private hypothesis selection. In Proceed- ings of the 33d Annual Conference on Learning Theory, COLT '20, pages 1785-1816, 2020.
12

---

[GKK 23] Badih Ghazi, Pritish Kamath, Ravi Kumar, Pasin Manurangsi, Raghu Meka, and Chiyuan Zhang. User-level differential privacy with few examples per user. In Advances in Neural Information Processing Systems 36, NeurlPS '23, pages 19263- 19290. Curran Associates, Inc., 2023.
[GLW21] Sivakanth Gopi, Yin Tat Lee, and Lukas Wutschitz. Numerical composition of differ- ential privacy. In Advances in Neural Information Processing Systems 34, NeurlPS 221, pages 11631-1 1642. Curran Associates, Inc., 2021.
[GR18] Marco Gaboardi and Ryan Rogers. Local private hypothesis testing: Chi-square tests. In Proceedings of the 35th International Conference Machine Learning, ICML '18, pages 1626-1635. JMLR, Inc., 2018.
[JNNR19] Matthew Joseph, Jieming Mao, Seth Neel, and Aaron Roth. The role of interactivity in local differential privacy. In Proceedings of the 60th Annual IEEE Symposium Foundations of Computer Science FOCS 19, pages 94-105. IEEE Computer Society, 2019.
[KLN+11] Shiva Prasad Kasiviswanathan, Homin K. Lee, Kobbi Nissim, Sofya Raskhodnikova, and Adam Smith. What can we learn privately? SIAM Journal on Computing. 40(3):793 826, 2011.
[KU20] Gautam Kamath and Jonathan Ullman. A primer on private statistics. arXiv preprint arXiv:2005.000/00 2020.
[MS08] Satyaki Mahalanabis and Daniel Stefankovic. Density estimation in linear time. In Proceedings of the 21 Annual Conference on Learning Theory, COLT '08, pages 503-512, 2008
[PAA24] Alireza F Pour, Hassan Ashtiani, and Shahab Asoodeh. Sample-optimal locally private hypothesis selection and the provable benefits of interactivity. In Proceedings of the 37th Annual Conference on Learning Theory, COLT '24, pages 4240-4275, 2024.
[PAJL24] Ankit Pensia, Amir Reza Asadi, Varun Jog, and Po-Ling Loh. Simple binary hypoth- esis testing under local differential privacy and communication constraints. IEEE Transactions on Information Theory, 7 71(1):592-617, 2024.
[PJL.24] Ankit Pensia, Varun Jog, and Po-Ling Loh. In Proceedings of the 37th Annual Conference on Learning Theory, COLT '24, pages 4205-4206, 2024.
[QCR20] Yihui Quek, Clément L. Canonne, and Patrick Rebentrost. Robust quantum minimum finding with an application to hypothesis selection. arXiv preprint 2rXiv: 11777 2020.
[She18] Or Sheffet. Locally private hypothesis testing. In Proceedings of the 35th International Conference on Machine Learning, ICML '8, pages
JMLR, Inc., 2018.
[SOAJ14] Ananda Theertha Suresh, Alon Orlitsky, Jayadev Acharya, and Ashkan Jafarpour. Near- optimal-sample estimators for spherical Gaussian mixtures. In Advances in Neural Information Processing Systems 27, NIPS '4, pages 1395-1403. Curran Associates, Inc., 2014.
[War65] Stanley L. Warner. Randomized response: A survey technique for eliminating evasive answer bias. Journal of the American Statistical Association, 60(309):63 69, 1965.
[ZZ [ZZ]+23]220 Zheng Xu, Yanxiang Zhang, Galen Andrew, Christopher A Choquette-Chone Choo, Peter Kairouz, H Brendan McMahan, Jesse Rosenstock, and Yuanbo Zhang. Federated learning of Gboard language models with differential privacy. In Proceedings of the 61 Annual Meeting of the Association for Computational Linguistics (Volume Industry Track), ACL. '23, pages 629666996666 639. Association for Computational Linguistics. 2023.
[Yat85) Yannis G. Yatracos. Rates of convergence of minimum distance estimators and Kolmogorov's entropy. The Annals of Statistics, 13(2):768-774, 1985.
13

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: The title and abstract skip our negative results but include our more important positive results.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made the paper and important assumptions and limitations. A No or NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
It is fine to include aspirational goals as motivation as long as is clear that these goals attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations the work performed by the authors?
Answer: [Yes]
Justification: Our improved query complexity bound is v larger than the known lower bound for the problem. We give a hard construction that shows our bound to be tight for our technique and suggests how the bound could be improved by taking technique further.
Guidelines:
The answer NA means that the paper has limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create separate "I "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect the scope of the claims made, e.g., if the approach was only tested on a few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low or images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory assumptions and prool's
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
14

---

Answer: [Yes]
Justification: Only one lemma (Lemmaa 6) has no proof but it is standard easy result for the area.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but they appear in the supplemental material, the authors are encouraged provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental result reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that affects the main claims and/or conclusions of the paper (regardless whether the code and data are provided or not)?
Answer: [NA]
Justification: [NA]
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, descríbing the architecture fully might suffice, or if the contribution is specific model and empirical evaluation, it may be necessary to either make possible for others to replicate the model with the same dataset, provide access to the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g.. g., in the case of a large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) the contribution is primarily a new algorithm, the paper should make clear how reproduce that algorithm. (b) If the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) the contribution is new model (e-g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should possible for other researchers to have some path to reproducing verifying the results.
5. Open access to data and code
15

---

Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, as described in supplemental material?
Question:
Answer: [NA]
Justification: [NA]
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nips... cc/
for more details.
While we encourage the release of code and data, we understand that this might not be possible, "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for a new open-source benchmark).
The instructions should contain the exact command and environment needed to run reproduce the results. See the NeurIPS code and data submission guidelines (https
/ "pipsscc/puullc//uuu hotp:///ggiddeeeeCouuuuubbbbbi ssionPolicy) for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones omitted from the script and why.
At submission time, preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental setting/details
Question: Does the paper specify all the training and test details (c.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [NA]
Justification: [NA]
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can provided either with the code, in appendix, or as supplemental material.
7. Experiment statistical significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [NA]
Justification: [NA]
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
16

---

The assumptions made should be given (e.g.. Normally distributed errors).
It should be clear whether the error bar is the standard deviation the standard error of the mean.
It is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out of range (e.g. negative emrr rates).
error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed reproduce the experiments?
Question:
Answer: [NA]
Justification: [NA]
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make into the paper).
9. Code ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics
Answer: [Yes]
Justification:
Our paper conforms to the code of ethics.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g.. if there is a special consid- eration due to laws or regulations their jurisdiction).
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: Our paper a theoretical work with indirect societal impact.
Guidelines:
The answer NA means that there no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
17

---

The conference expects that many papers will be foundational research and not tied particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology being used intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms monitor how system learns from feedback over time, improving the efficiency and accessibility of MI..
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification: [NA]
Guidelines:
The answer NA means that the paper poses such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Lieenses for existing assets
Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper. properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [NA]
Justification: [NA]
Guidelines:
The answer NA means that the paper does existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (c.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (c.g., website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswi thcode. com com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
18

---

If this information is not available online, the authors are encouraged to reach out to the asset's creators.
13. New assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification: [NA]
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/mmoel as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsoureing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification: [NA]
Guidelines:
The answer NA means that the paper does not involve crowdsoureing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included the main paper.
According the NeurIPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals or equivalent for research with human subjects
Question:
Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: [NA]
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Depending the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and expect authors to adhere to the NeurlPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such the institution conducting the review.
16. Declaration of LLM usage
19

---

Question: Does the paper describe the usage of LLMs if it is important, original, or non-standard component of the core methods this research? Note that if the LLM used only for writing, editing, or formatting purposes and does not impact the core methodology, scientific rigorousness, or originality of the research, declaration is not required.
Answer: [NA]
Justification: [NA]
Guidelines:
The answer NA means that the core method development in this research does not involve LLMs any important, original, non-standard components.
Please refer to our LLM policy for what should or should not be described.
20


Reviews:
[{"review_id": "z3or79RCHC", "reviewer": "Reviewer_UrSm", "summary": "The paper studies hypothesis selection under LDP in the non-interactive setting. The classical baseline asks all (k choose 2) pairwise signed Scheffé tests and therefore needs O(k^2) samples. The authors introduce the Scheffé graph: This is a directed graph\nwhose vertices correspond to possible queries that a locally private hypothesis selection algorithm may ask and whose directed edges indicate when one query gives sufficient information to answer another query. The graph is highly connected because of triangle inequalities between probabilities. They show it has a dominating set of size O(k^(3/2) log k). so it suffices to query only those \nthis many tests with randomized response, and the results for all other pairs can be inferred using the graph structure. \n\nThe privacy comes from the Randomized response of the signed Scheffé test. For each vertex, we will use the debiased RR to estimate the  mean, and the overall estimation error is analyzed through Hoeffding’s inequality and union bound over all tests. \n\nThe authors argue that if one relies solely on the triangle-style relations among tests, a dominating set of size O(k^(3/2)) is necessary—so the result is essentially tight within this framework.", "questions": "see the weaknesses above", "limitations": "yes.", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 4, "originality": 4, "strengths_and_weaknesses": "Strengths\n\nPrior work either requires O(k^2) sample complexity or required interactivity; the jump to O(k^3/2) is significant. The paper also introduced an elegant graph-theoretic idea: it turns Scheffé tests into a domination problem, any this may inspire further reductions. \n\nThe paper also has clear presentation and proofs are sound.\n\nWeaknesses \n\n1. 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?\n\n2. 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?", "was_revised": true, "final_justification": "The authors clarified my concerns regarding these weaknesses.", "rebuttal": "> 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?\n\nUnfortunately, 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.\nNote 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.\nUnfortunately, in Section 6.2 we show that their core \"flattening\" technique cannot be improved to achieve the full desired agnostic guarantees. \nIt 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.\n\n> 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?\n\nLemma 10, which is the key component in our probabilistic analysis, takes into account both sources of randomness. \nIn 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$. \nIn 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}$.\nWe're happy to make this clearer in the final version of the paper."}, {"review_id": "cVfsRU0XOy", "reviewer": "Reviewer_kHsp", "summary": "The paper constructs and analyzes an efficient (constant approximation, roughly $k^{3/2}$ number of samples, where $k$ is the number of given distributions) and locally private algorithm for the problem of hypothesis selection. It also discusses theoretical limitations of the new technique.", "questions": "1.\tClarify 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.\n2.\tAddress unclear points stated in detail comments above.", "limitations": "yes", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 2, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Pros:\n\n-\tThe problem is among fundament ML problems\n\n-\tThere is a substantial (polynomial) improvement over previous work, and novel techniques (particularly, in Section 5)\n\nCons:\n\n-\tSimilarly as in the previous work (Gopi et al COLT 2020), the concept of Local Differential Privacy is unclear, and the analysis does not refer to the definition.\n\n-\tDetail comparison with the previous work would be useful, especially since there are nearly linear algorithms with logarithmic approximation\n\n-\tSome results (e.g., Lemma 9) are not clearly referenced (are they new or otherwise should state reference to the original work producing them)\n\nDetail comments:\n\nExplain footnote 1: why the stated approximation factor includes the problem when p is one of the q_i ?\n\nDifferential privacy not explained when reviewing previous work (and definition is late, on page 3, after the theorem).\n\nDefinition 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.)?\n\nLine 118: explain acronyms PMF and PDF\n\nLine 119: \\Delta(\\cal{X}) not defined\n\nLine 163: what is “workload of queries”?\n\nWhere is Lemma 9 used?\n\nWhy is LPD guaranteed by Lemma 10?", "was_revised": true, "final_justification": "This is a paper addressing important problem, with interesting technical idea and improvement over previous papers. Still, the presentation is not ideal, and in the discussion, it was raised that the COLT 2020 paper has more results and techniques, which makes the actual improvement in this paper a bit less substantial than I thought in the beginning. Nevertheless, I keep my weak accept recommendation.", "rebuttal": "> Explain footnote 1: why the stated approximation factor includes the problem when $p$ is one of the $q_i$?\n\nIn 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$. \nHowever, 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. \nWe 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:\n\nThe 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.\n\n> Differential privacy not explained when reviewing previous work (and definition is late, on page 3, after the theorem).\n\nWe 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.\n\n> 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.)?\n\n> 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.\n\nThanks for the comments -- it would be helpful if the reviewer can clarify what parts of the definition are unclear. \nThe 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.\nWe will replace Definition 3 with the following, which is hopefully clearer.\n\nDefinition 3: Suppose there are $n$ individuals, where the $i$-th individual has datapoint $X_i$.\nA 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\n\\[\n\t\\Pr[m_i(X_i) \\in E] \\leq e^\\varepsilon \\Pr[m_i(X_i') \\in E].\n\\]\n\nTo 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. \nThe proof is omitted since it is an established result, but we will provide a reference and include the above informal discussion. \nAs 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.\n\n> Some results (e.g., Lemma 9) are not clearly referenced (are they new or otherwise should state reference to the original work producing them)\n\nThanks 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).\n\n> Line 118: explain acronyms PMF and PDF\n\nCorrected (probability mass and density function, respectively), thank you.\n\n> Line 119: $\\Delta(\\cal{X})$ not defined\n\nFixed (the probability simplex over $\\cal{X}$), thank you.\n\n> Line 163: what is “workload of queries”?\n\nThanks 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.\n\n> Where is Lemma 9 used?\n\n> Why is LPD guaranteed by Lemma 10?\n\nAs 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)."}, {"review_id": "FD6HVs457E", "reviewer": "Reviewer_KcG9", "summary": "The authors propose a new non-interactive locally differentially private (LDP) algorithm for hypothesis selection. The algorithm is built upon a novel concept called the Scheffé graph and is supported by a theoretical sample complexity guarantee of $\\widetilde{O}(k^{3/2})$, which significantly improves upon the existing bound of $\\widetilde{O}(k^{2})$.", "questions": "Do the authors have any simulation results regarding the size of the dominating set of the Scheffé graph?", "limitations": "yes", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strength. 1. Theoretical analysis is rigorous and sound. 2. The sample complexity bound of LDP hypothesis selection is significantly improved. 3. The paper is clearly organized and easy to follow.\n\nWeakenss. 1. Lack of empirical validation. The absence of experimental comparisons with existing algorithms limits the paper’s contributions to theoretical aspects. 2. Unclear potential of the Scheffé graph: The lower bound provided suggests that the $\\widetilde{O}(k^{3/2})$ barrier may be inherent to Scheffé graph-based methods. However, the bound is proven for a broader class of triangular substructures, making it unclear whether Scheffé graphs can ever reach the theoretically optimal $O(k)$ complexity. It would be helpful if the authors included empirical simulations analyzing the size of the dominating set in Scheffé graphs to provide insight into its practical behavior and possible limits.", "was_revised": true, "final_justification": "The new private hypothesis selection method based on Scheffe graph did improved the existing method in sample complexity, however did not reached the optimal rate. This question the potential of the Scheffe graph whether the method can be optimal. The authors provided simulation that implies the Scheffe graph may be more optimal than their theoretical result. Therefore, I believe their method will have high impact in private hypothesis selection problem.", "rebuttal": "> Lack of empirical validation. The absence of experimental comparisons with existing algorithms limits the paper’s contributions to theoretical aspects.\n\nIndeed, our work focuses on theoretical aspects of this problem. \nThis 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. \nSuch investigation would be interesting, but is outside the scope of our present work.\n\n> Potential of the Scheffé graph\n\nAs the reviewer correctly identifies, we use the triangle substructure to prove a domination number bound of $\\tilde O(k^{3/2})$.\nWe further show that the triangle substructure alone will not allow one to do better than $\\tilde \\Omega(k^{3/2})$. \nThis raises the question of whether additional graph structure would help go beyond, towards reaching the optimal bound of $\\tilde O(k)$. \n\nThough 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.\nUnfortunately, there are a few computational challenges that preclude evaluation on larger $k$.\nPrimarily, since the Dominating Set problem is known to be NP-complete, such simulations amount to brute force computation.\nSecondarily, the number of nodes in the Scheffé graph grows quadratically, increasing the computational burden.\nNonetheless, we view our simulation results as some evidence towards an $\\tilde O(k)$ domination number, and will include discussion to this effect."}, {"review_id": "MArAlH7Nq8", "reviewer": "Reviewer_6GnU", "summary": "This paper presents a new local differential privacy (LDP) mechanism for the hypothesis selection problem.\n\nWe are given $ k $ probability distributions $ q\\_1, \\\\ldots, q\\_k $.\nThere is an unknown distribution $ p $ from which $ n $ individuals each receive an independent sample.\nThe task is to design a mechanism which guarantees $ \\\\varepsilon $-LDP for each individual, and allows approximately determining which $ q\\_i $ is closest to $ p $ in $ \\\\ell\\_1 $ distance.\n\nHere, \"approximately\" means the algorithm selects a distribution $ q\\_i $ such that\n$$ \\\\Vert q_i - p \\\\Vert_1 \\\\le 13 \\min\\_j \\\\Vert q\\_j  - p \\Vert_1 + \\\\alpha $$\nwhere $ \\\\alpha > 0 $ is a tunable parameter which affects the number of samples required.\n\nThe LDP mechanism is non-interactive, and solves the *agnostic* version of the problem, meaning $ p $ may be different from every $ q\\_i $.\n\nFor a fixed $ \\\\varepsilon $ and $ \\\\alpha $, the algorithm requires $ \\\\tilde{O}( k^{ 3/2 } ) $ samples, compared to a previous best of $ O( n^2 ) $ for this variant of the problem.\n\n(Filling in some detail: if $ \\\\varepsilon $ and $ \\\\alpha $ are allowed to vary, and the algorithm is allowed to fail with probability $ \\\\beta $, the number of samples required is $ \\\\tilde{O}( k^{ 3/2 } \\\\log( 1/ \\\\beta ) / ( \\\\alpha^2 \\\\varepsilon^2 ) $.)\n\nThe paper also describes two barriers to improving this $ \\tilde{O}( k^{3/2} ) $: first, an obstacle to the particular technique they use to reduce the number of comparisons; and second, a refutation of a conjecture that would have led to another approach.", "questions": "I've grouped my questions and comments by importance.\nPlease look at the \"High importance\" section and at least skim \"Medium importance\"; the \"Low importance\" section is just little things I noticed as I was reading.\n\n# High importance\n\nThe 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.\nThis feels to me like a lie even if it's close to the truth.\nIt would be good to be more upfront in telling the reader this extra factor is missing.\n\n# Medium importance\n\n- 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 $ q\\_i $?). Still, I think it would be good to say it explicitly earlier.\n\n- 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.\n\n- 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 \\\\ge n\\_0 $ with $ n \\\\ge 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.)\n\n- Line 157: \"...with small probability\": the probability is only small if the LDP parameter $ \\\\varepsilon $ is large. I personally wouldn't write \"small\" here since I think the best LDP setting would be something like $ \\\\varepsilon = 1 $ so user privacy is well-protected.\n\n- Line 167: \"Let $ \\\\ell = |S| / | \\\\mathcal T | $ ...\": $S$ is not defined at this point. (The next sentence makes it clear $S$ is the sample.)\n\n- Some notes about the proof of Theorem 17:\n\n\t- It talks about a set $S$. I think you mean $R$, unless I've missed something. (At least: the equation between lines 264-265, then line 265 itself, then line 274 in $ I\\_v^S $.\n\n\t- Consider ensuring $ t $ is an integer; $ 2 \\\\log k $ might not be. But maybe this is not worth the notational clutter. (Similarly, you could clarify the base of the logarithm is 2, but again, that's more clutter.)\n\n\t- In the display math line after line 266, I think $ \\\\binom{ k-2 }{ t } $ should be $ \\\\binom{ k-1 }{ t } $, and that change would propagate through the math that follows.\n\n\t- I found the inequality $ \\\\binom{ k-2 }{ t } \\\\cdot \\\\frac{ \\\\binom{ |V|-2t }{ \\\\ell-2t } }{ \\\\binom{ |V| }{ \\\\ell } } \\\\le \\\\left( \\\\frac{ e (k-2) }{ t } \\\\right)^t \\\\left( \\\\frac{ \\\\ell }{ |V| } \\\\right)^{ 2t } $ tricky to verify. It might be worth elaborating. Maybe state the approximation to the factorial function you're using somewhere.\n\n\t- Line 273: \"both of them\" is ambiguous; could refer to $ \\\\{ a,i \\\\} $ and $ \\\\{ b,i \\\\} $, or to $ v $ and whichever of those two is being dominated. Only one interpretation makes sense, but I got stuck on this sentence for a bit and the ambiguity didn't help. (The reason I got stuck is that my eyes skipped over the words \"of $R$\" the first few times I read the sentence, but that's my fault.)\n\n\t- Line 274: \"$v$ dominates at most $|I\\_v^S|+1$ (I'm assuming $S$ means $R$): I think a factor of 2 is missing, since each $ i \\\\in I\\_v^R $ corresponds to two vertices $ \\\\{a,i\\\\}, \\\\{b,i\\\\} $.\n\n- Line 281: What does $ \\\\alpha $-separated mean? I infer it means that every pair of distributions is *at least* distance $ \\\\alpha $ apart, but when I was first trying to understand the conjecture I entertained the idea it might be *at most*.\n\n- Line 264: the arXiv version of [GKK+20] says \"with high probability\" here. Not sure how much that matters.\n\n- I didn't really understand the discussion on lines 286-291. Suppose we have compared each of the $k$ distributions to the uniform distribution. Then how does that help us estimate $ \\\\Vert q\\_i - q\\_j \\\\Vert_1 $?\nWe know $ \\\\Vert q\\_i - u \\\\Vert_1 $ and $ \\\\Vert q\\_j - u \\\\Vert_1 $ but that only lets us upper-bound $ \\\\Vert q\\_i - q\\_j \\\\Vert_1 $. Probably if I spent some time reading [GKK+20] the situation would become more clear, but it would be nice if this were more self-contained.\n\n- Line 307: \"Since $ \\\\phi f\\_1 = \\\\mathbf{1} / m $...\": I don't think that's necessarily the case. However we have $ \\\\Vert \\\\phi f_1 \\Vert_1 = 1 $ which is enough.\n\n\n# Low importance\n\n- Scheffé vs. Scheffe: the latter appears in the title but the former appears elsewhere. I'm not sure why é got changed to e.", "limitations": "yes", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 4, "clarity": 4, "significance": 3, "originality": 4, "strengths_and_weaknesses": "# Strength: improved non-interactive locally differentially private hypothesis selection\n\nThe method described in this paper has a significantly better sample complexity than previously known in the non-interactive agnostic setting.\n\n# Strength: simplicity\n\nThe method sounds fairly easy to implement.\n\n# Strength: clear presentation; careful analysis including barriers\n\nI really enjoyed reading this paper.\nIt was quite clearly presented.\nFor example, I liked the way the proof of Theorem 1 is divided into Theorems 11 and 13, and Theorem 11 is in turn proved by Theorem 8 and Lemma 10, and I liked the proof sketch on lines 201-205.\n\nThe mathematical analysis was carefully done and includes barriers that would need to be overcome to improve the method.\n\n# Weakness: practical applicability / evaluation?\n\nThe practical importance or usefulness of the result is not completely clear.\n\nIf there is a concrete real-world situation where someone will benefit from this (for example, if someone is already attempting to do hypothesis selection but is limited by the available methods) then that would be worth mentioning.\nOr, similarly, if this variant of the problem has been a longstanding open problem getting a lot of attention, then this would also be worth mentioning.\n(Even without this, the problem is generic enough that it's bound to be useful to someone, so this doesn't seem like a fatal flaw. It just doesn't feel like a paper with \"groundbreaking impact\".)\n\nSimilarly, it wouldn't hurt to have an experimental evaluation, even on artificial data.\nFailing that, maybe just walk the reader through an example scenario with a particular $ \\\\varepsilon $ and set of distributions $ q\\_i $ and what Theorem 1 implies about how accuracy and number of samples trade off.\nThis is not especially important and the paper feels complete to me even without it.\n\n# Minor weaknesses: errors, some unclear points\n\nThere were some minor errors and a few things that were unclear or poorly stated.\n\nOne that stands out to me: the preprocessing is said to take $ \\\\tilde{O}( k^{ 5/2 } ) $ time, but (admitted only in footnote 3 on page 7) this doesn't account for the time to compare a pair of distributions.\nThe authors should be upfront about the actual runtime. (In the statements of Theorems 1 and 13.)\n(Maybe in the typical setting this time is neglibile compared to $ k $? If so, that could be mentioned explicitly.)\n\nOn the whole this paper ranks well in terms of clarity and technical accuracy: this is not a weakness relative to most other papers.", "was_revised": true, "final_justification": "I was tempted to rate this paper as 6 instead of 5, but I am not really familiar enough with the area to be confident that the k^2 -> k^2/3 improvement is a groundbreaking result; it just seems interesting to me as someone who doesn't do a lot of work on local DP. (Also the description of the 6 rating includes \"exceptionally strong evaluation\"; I'm not sure if exceptionally strong theorems count!)\n\nThe authors addressed my concerns, except that a small empirical part would have been nice, though I think their positioning this paper as a theory paper is a reasonable response to that.\n\nI'm maintaining my positive rating of 5 (accept).", "rebuttal": "> Importance of the work\n\nIndeed, 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.\nThis 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.\nBreaking 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.\n\n> Experimental evaluation\n\nWhile experimental evaluation would indeed be interesting, we choose to fit our work with existing work in this field, by studying theoretical properties of algorithms.\nThis 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. \nSuch investigation would be interesting, but is outside the scope of our present work.\n\n> 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.\n\nThanks for this comment. \nIndeed, the running time of preprocessing could vary based on the precise access to the hypotheses.\nWhile 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.\n\n> 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.\n\nThanks 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$.\n\n> 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.\n\nThe 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.\nHowever, the key difference with our work (resulting in the exponential difference in the dependence on $k$) is the semantics on privacy.\nSpecifically, 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.\nIn 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.\n\n> 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.)\n\nThanks 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$.\n\n> 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.\n\nGreat point, we will adjust this wording.\n\n> Line 167: \"Let  ...\":  is not defined at this point. (The next sentence makes it clear $S$ is the sample.)\n\nThank you, we will make this clearer. \n\n> Some notes about the proof of Theorem 17\n\nThank you for your very careful reading and the helpful suggestions to improve clarity. \nWe will make all the suggested changes.\n\n> Line 281: What does $\\alpha$-separated mean?\n\nIn 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.\n\n> Line 284: the arXiv version of [GKK+20] says \"with high probability\" here. Not sure how much that matters.\n\nWe 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.\n\n> I didn't really understand the discussion on lines 286-291...\n\nOur 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$.\nThe reviewer is right that the connection between Conjecture 18 and sample-efficient LDP hypothesis selection is rather non-trivial.\nUnfortunately, 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.\nInstead, 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.\n\n> Line 307: \"Since $\\phi f_1 = \\mathbf{1}/m...$\": I don't think that's necessarily the case.\n\nThe reviewer is correct, and we have made that change, thank you.\n\n> Scheffé vs. Scheffe\n\nGood eye! We thought about this and made the explicit choice to have the non-accented version in the title. \nThis is because accented characters may be more difficult for scrapers and indexers to capture. \nIt also is a bit more cumbersome to typeset in bibtex. \nTo avoid all these issues, we went with the simpler non-accented version.\nThere is precedence for such a decision, see, e.g., \"Hyperparameter Tuning with Renyi Differential Privacy\" in ICLR 2022."}]

Author rebuttal:

Meta-review: The manuscript aims to reduce the number of queries under local differential privacy to select the best fit amongst a set of hypothesised probability distributions. The theoretical results reducing sample complexity were perceived as clearly substantial [UrSm, kHsp, KcG9, 6GnU] and while an empirical evaluation was desired [KcG9, 6Gnu], the clear presentation [UrSm, 6Gnu] with sound proofs [UrSm, KcG9] and seemingly easy-to-implement method [6Gnu] makes this work also interesting as a purely theoretical exploration where empirical results could be left to future work.
Decision: Accept (poster)