Nearly-Linear Time Private Hypothesis Selection with the Optimal Approximation Factor
Authors: Maryam Aliakbarpour
Zhan Shi
Ria Stevens
Vincent X. Wang
Venue: NeurIPS 2025 poster ()
Keywords: differential privacy
hypothesis selection
computational constraints
density estimation
distribution learning
private hypothesis selection
Primary area: theory
TL;DR: We provide a near-linear time algorithm for differentially private hypothesis selection that has polylogarithmic sample complexity and achieves the optimal approximation factor.

Abstract: Estimating the density of a distribution from its samples is a fundamental problem in statistics. \emph{Hypothesis selection} addresses the setting where, in addition to a sample set, we are given $n$ candidate distributions---referred to as \emph{hypotheses}---and the goal is to determine which one best describes the underlying data distribution. This problem is known to be solvable very efficiently, requiring roughly $O(\log n)$ samples and running in $\tilde{O}(n)$ time. The quality of the output is measured via the total variation distance to the unknown distribution, and the approximation factor of the algorithm determines how large this distance is compared to the optimal distance achieved by the best candidate hypothesis. It is known that $\alpha = 3$ is the optimal approximation factor for this problem.
We study hypothesis selection under the constraint of \emph{differential privacy}. We propose a differentially private algorithm in the central model that runs in nearly linear time with respect to the number of hypotheses, achieves the optimal approximation factor, and incurs only a modest increase in sample complexity, which remains polylogarithmic in $n$. This resolves an open question posed by [Bun, Kamath, Steinke, Wu, NeurIPS 2019]. Prior to our work, existing upper bounds required quadratic time.

Nearly-Linear Time Private Hypothesis Selection with the Optimal Approximation Factor
Maryam Aliakbarpour Zhan Shi', Ria Stevens', Vincent X. Wang' Rice University, Department of Computer Science Ken Kennedy Institute (maryama, zs50, ria. stevens, /w12]@rico edu
Abstract
Estimating the density of distribution from its samples is fundamental problem in statistics. Hypothesis selection addresses the setting where, addition to a sample set, we are given candidate distributions-referee to as hypotheses- the goal is to determine which one best describes the underlying data distribution. This problem is known be solvable very efficiently, requiring roughly O n) samples and running in (n)) time. The quality of the output is measured via the total variation distance to the unknown distribution, and the approximation factor the optimal
of the algorithm determines how large this distance is compared distance achieved by the best candidate hypothesis. It is known that = 3 is the optimal approximation factor for this problem. We study hypothesis selection under the constraint of differential privacy. We propose differentially private algorithm in the central model that runs in nearly-linear time with respect to the number of hypotheses, achieves the optimal approximation factor, and incurs only a modest increase sample complexity, which remains polylogarithmic n. This resolves an open question posed by [Bun, Kamath, Steinke, Wu, NeurIPS 2019]. Prior to our work, existing upper bounds required quadratic time.
Introduction
The task of accurately estimating the underlying probability distribution that generates a dataset is a fundamental theoretical problem in statistical inference with broad applicability in practical data anal- ysis. growing concern in modern data analysis preserving the privacy of the individuals whose data informs these estimations, specifically when dealing with sensitive information. Differential pri- vacy (DP) has emerged as widely adopted standard in crivacy-preservin data analysis [DMNS06a] and is currently employed by major entities, such as Google [EPK14] Apple [Dif17], and the U.S. Census Bureau [Abo18], See Section for more examples.
In this paper, we study a specific instance of distribution estimation under the constraint of differential privacy, referred to Hypothesis Selection. In this problem, we are given finite collection of candidate distributions 7/ == [H,, H2,.. .... H ), known as hypotheses, and dataset of i.i.d. samples drawn from an unknown distribution P. The goal is to select hypothesis in H. that well-approximates the true data distribution.
A long line of research has studied hypothesis selection in the non-private setting Yat85,, DL96, DI.97, DLO1, MS08, DK14, SOAJ14, AJOS14, AFJ+18 18, BBK+21, ABS23, AAC 23, AAC+ 24, ABS24). These algorithms' performances evaluated across three key aspects: sample complexity, ii) time complexity, and iii) approximation factor. Early work has shown that hypothesis selection admits highly sample-efficient algorithms, requiring only O(log n) samples, logarithmic dependence on the number of hypotheses, and no dependence on the domain size of distributions [Yat85, DL96, DL97, DLO1]. The sample efficiency is achieved by only needing estimate probabilities of (nn²) special sets, called Scheffé sets, according to P (see Equation (1) for a definition). Moreover, several
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

works [DK14, AFJ 18, ABS23, ABS24] have shown that one can find valid hypothesis in roughly linear time in n. Recently, [AAC* 24] characterized the statistical statistical-comuutaie computational trade-off of the problem when the distributions have finite domain.
Another key aspect is the accuracy of the selected hypothesis, measured by the total variation distance to the true distribution. The approximation factor (denoted by a) measures this distance relative to the minimum distance between P and a hypothesis in H. notable lower bound established in [BKMI9] shows that achieving a < 3 is impossible unless the number of samples is polynomial in the domain size of P. In an interesting development, Aliakbarpour et al. [ABS24] recently proposed an algorithm that simultaneously achieves logarithmic sample complexity, the optimal approximation factor a 3. representing a compelling performance in all three critical aspects of this problem.
time complexity. and
Despite this desirable performance in the non-private setting, the state of the art in the private setting falls short of optimal performance. A naive privatization of Scheffé estimates via Laplace noise leads an (n²) sample complexity [BKSW 19.. More advanced techniques, including the work of Bun et al. [BKSW19] offer better sample complexity (logarithmic) but suffer from quadratic time and suboptimal approximation. While Aden-Ali al. [AAAK2I] makes progress on accuracy and proof simplicity, their algorithm remains computationally expensive with a quadratic time complexity.
These limitations naturally lead us to address open question, first raised in part by Bun et al. [BKSW19]; Does there exist an ideal private hypothesis selection algorithm that offers logarithmic sample complexity, nearly-linear time complexity, and the optimal approximation factor? We present a significant step forward towards this ideal: our algorithm achieves nearly-linea time complexity and the optimal approximation factor with polylogarithmic sample complexity (which, while not logarithmic, is still considered a modest dependence on the number of hypotheses). A formal description of our results can be found in Section 1.2.
Applications:
Estimating data distributions is central component of many scientific tasks, such as estimating species abundance in ecology or analyzing survey results in the social sciences. Hypothesis selection describes broadly applicable scenario where can form finite set of interpretable, noise- free, or otherwise manageable distributions as our candidate hypotheses, and we aim to approximate the potentially noisy and complex unknown distribution with one of the so-called "nicer" candidates (e.g., modeling customer arrival time with Poisson processes).
One notable theoretical application of hypothesis selection is agnostic learning of parametric class of distributions (e.g., mixtures of Gaussians [SOAJ14, DK 14, ABM18, ABH+20), and junta distributions [ABR 16]) via the cover method. The approach is to first select representative set of parametric distributions, and hypothesis selection then identifies the closest approximation in this set. For survey, see Diakonikolas [Dial6].
1.1 Problem setup
Let P denote an unknown distribution over a domain X. and let H. := (H1, Hz.... ".2....,,,,, .n } be a set of n public and known distributions over X. We define OPT to be the total variation distance of P and the closest hypothesis in H.
We seek to design semi-agnostic proper learner such that for every H and P, the algorithm outputs hypothesis H H such that the total variation distance between A and P is within a-times OPT plus an additive error parameter a, which can be made arbitrarily small with sufficiently many samples.
We assume the standard access model of [DL01], where an algorithm accesses distributions by making queries of the following types:
1. The algorithm can draw i.i.d. samples from the unknown distribution P.
2. The algorithm can compare the PDFs of any two known distributions H,, H, given point x E X. Specifically, it can ask if (x) < Hz) This is equivalent to determining if x is in the Scheffé set of H, and H, (defined in Equation 1).
3. The algorithm can query the probability mass of the Scheffé set of any two known distribu- tions. Precisely, it can ask for (S,,,,) for all H,, H, H.
2

---

More formally, we have:
Definition 1.1 (Proper learner for private hypothesis selection). Let > O, and let A be an algorithm with input parameters c. 6.B.a E (0. 1), sample access an unknown distribution P. and query access to a finite class of n hypotheses above). We say A is (at, 6, 6, (2, (), -proppe learner for the private hypothesis selection problem if:
= {H1 HH...., Ha} (according to the access model described
1. A is e-differentially private in the central model (defined in Definition 1.2) with respect to the samples drawn from P.
2. A outputs H E H such that with probability at least 1 - 8,
H - Pllvv I a OPT +
We call a the approximation factor, the privacy parameter, B the confidence parameter, and the error parameter.
Remark 1. As mentioned in [DK14, ABS24], the third type of query in the standard access model can be relaxed. Our algorithms only need estimates. rather than exact values, of the probability masses of the Scheffé sets. Assuming all estimates of H,,), are accurate to an additive ervor of (aa) with high probability, the analysis of our algorithms remain essentially unchanged. These estimates could be obtained by sampling from each H; or numerically integrating density functions when analytic forms are available.
1.2 Our result
We present an algorithm for private hypothesis selection with the following guarantee:
Theorem 2 (Informal version of Theorem 3). For every B,B,o E (0.1), Algorithm 1 is an (a = 3, 3, o) -pproper learner for the private hypothesis selection problem that uses s = (log"(n/3) (B) samples and runs in time Ö(n / (B*
Our result is the first algorithm for private hypothesis selection that runs in nearly-linear time, resolving an open question first posed by [BKSW19] about the existence such an algorithm. In addition, we also maintain the optimal approximation factor = 3. However, our algorithm introduces an additional factor of Ollog" 2 n n/ a)) in the sample complexity compared to existing work on private hypothesis selection. We summarize this tradeoff and compare with existing private algorithms in Table 1.
The overhead in the sample complexity stems from our privatization strategy that is informed by the structure of our algorithm. Similar to most time efficient algorithms in previous works, our algorithm consists of multiple interdependent components, where each component directs us to focus only on a small set of Scheffé estimates, opposed to computing all of them. While these interdependencies allow us to achieve a highly time-efficient algorithm, they make direct privatization of the final output analytically very challenging. Rather than attempting to analyze the privacy loss of the full computation, we enforce differential privacy at each component of the algorithm, resulting in the sub-optimality of our sample complexity. Despite this added overhead, our algorithm still maintains sample complexity polylogarithmic in number of hypotheses with no dependence on the domain size.
Our algorithm also has a polynomial dependence on 1/3, contrasting with the typical log(1/3) dependence on the confidence parameter that arises in many learning theory problems when am- plifying result (e.g., by taking an "average" of the results of running log(1/8) many runs of an algorithm). However, hypothesis selection, this amplification process is unlikely to succeed without a significant increase in because it would require running hypothesis selection twice, which would push the total approximation factor to at least a = 9. Achieving a polylogarithmic dependence on 3 is difficult task, even in the absence of privacy constraints; both [ABS23, ABS24] present nearly-linear time algorithms with a but suffer from similar polynomial dependencies on 1/3.
Open directions:
This leaves two open directions for further work: i) Does there exist nearly- linear time algorithm that uses O log 0
+
loga de
samples in terms of its dependence on a, iii Can
the dependence on the confidence parameter be improved to O(log(1/3)) while maintaining -inray runtime?
3

---

Table 1: Summary of past hypothesis selection results under central DP
Result
Sample complexity (s)
Time complexity
Private Scheffé tournament [BKSW19] (Thm 3.6) [BKSW 19] (Thm 3.5)
log
n² log dc
O(n
> 54
Ô
log
Ó(n².
o²
Minimum distance estimate [AAAK21] (Thm 2.24)
0
log
log
O(n².s)
ac
This work
0
loy" n
(n ((n-8/) (/n-//o)
Significance of the approximation factor: One may argue that it is possible to improve the accuracy by decreasing OPT by selecting more candidate hypotheses in H. as opposed to decreasing the approximation factor However, mentioned in [ABS24], this is not feasible in many spaces, especially multivariate distributions, without substantially increasing the size of H. For instance, in the cover method, require H. to cover the space of parametric class of distributions with y-cover, where each distribution in the class is at most 7 away from an element in H. enforcing OPT < 7. As example, the mixture of k-Gaussians in [SOAJ14] requires 0 -3) distributions to create a 7-cover, making algorithms with high approximation factor more time-consuming.
1.3 Related work
Most of the previous work on hypothesis selection falls under two approaches: i) tournament-based algorithms that compare pairs of hypotheses based on their Scheffé estimates, and then perform a series of comparisons to find final winner ti) the minimum distance estimate (MDE) algorithms that compute an approximate distance based on the Scheffé estimates for each hypothesis, and then select the hypothesis with the minimum approximate distance.
The Scheffé tournament algorithm, first proposed by Devroye and Lugosi [DL01], runs O( s) time and achieves an approximation factor of 9. Other works in this line include [DK] 14, AJOS14, AFJ+ 18, AAC+23, ABS23]. Algorithms that follow the tournament structure typically exhibit a high approximation factor. Moreover, privatizing such algorithms raises extra challenges because changing a single data entry might affect the result of every comparison, thus greatly increasing sensitivity.
The other approach [DL01, MS08, ABS24] for non-private hypothesis selection is based on the minimam distance estimate (MDE) method introduced in [DL01], which has been the only type of al- gorithm that achieves the optimal approximation factor a = 3. Mahalanabis and Stefankovic [MS08] later improved the initial O(n 8) runtime of [DL01] to O(n² s), as well as proposed a nearly- linear time algorithm that requires exponential pre-pree pre-processing. Aliakbarpour et al. [ABS24] recently demonstrated that the optimal approximation factor
could be achieved with nearly-linear
time algorithm.
For an extended version of the related work, see Appendix A.
1.4 Background: differential privacy
We adopt the central model of DP [DMNS06b), where sensitive dataset is given to a trusted data curator who performs the algorithm and publicly publishes the outcome. Differential privacy protects each entry in the dataset from an adversary who observes the outcome.
Differential privacy:
dataset D [T]] E x is a collection of i.i.d. samples from an unknown distribution P. The Hamming distance between two datasets D and D' is defined as the number of differing entries and denoted as Ham(D, D'). We consider an algorithm to be private with respect to the samples drawn from P if it satisfies the following definition:
Definition 1.2 (Pure differential privacy). Let > O. An algorithm A is e-differentially private if for all measurable subsets S S Range(A) A) and D, D' E 0000 such that Ham (D, D') =1:
Pr(A(D) S] 1 < <PPAA(DD) S].

---

Standard methods for calibrating noise in DP rely on the concept of sensitivity:
Definition 1.3 (Sensitivity). h Let f x + Ii be function. Then, (f)) denotes the sensitivity of and is defined by: ( = sup [f(D) f(D')-
D,D' Ham(D,D')=1
Exponential mechanism: A widely used algorithm in DP is the exponential mechanism. This mechanism relies on a real-valued utility function u that maps a dataset D E X and candidate output H5 E H. to real-valued score, quantifying the "quality" of Hj with respect to D. Outputs with higher utility are more likely to selected.
Definition 1.4 (Exponential mechanism [MT07, DR+14)) 14]). Given utility function X x + R with sensitivity (u)), the exponential mechanism selects an element Hj E H. with probability proportional to exp
(x(,) (a
Fact 1.5 ([MT07J). The exponential mechanism e-differentially private.
We also have the following utility guarantee of the exponential mechanism:
Fact 1.6 (Corollary 3.12 of (DR+14]]. Let u X x H -> be utility function with sensitivity A (u)). Fix a dataset D) E X Let H E HH denote the output of the exponential mechanism with parameter e and utility function u. Then, for any 3 E (),
2A(u)
Pr ()
max H(D,H,) HGEH
log(n/3) Se -log(111/)) =3.
e
Sparse vector technique [DNR+ 09, DR 14, LSL16]: Given numerical statistic X' R. threshold query counts the number entries x E D such that g(x) is above or below a fixed cutoff. We will employ the sparse vector technique (SVT) [DNR 09]. which enables processing large number of threshold queries while incurring a privacy cost only for the small subset of queries whose values exceed specified threshold. Dwork et al. [DNR 09] presents simple e-differentially private algorithm
that takes in a stream of queries and identifies the first meaningful query above predefined threshold while privately ignoring queries that fall below the threshold.
Two properties make DP particularly well-suited for mod- ular algorithm design. Composition bounds the cumulative privacy loss after performing multiple differentially private subroutines, and procepsngss ensures that no further transformation of the output of differentially private algorithm can further degrade the privacy guarantees. We state the following theorems:
Composition and post-processing:
Fact 1.7 (Composition. Theorem 3.14 of [DR 14]). Let Ai...., As be algorithms that access the same dataset D E 8 and suppose each A; is c-diiferrntiilll private. Let A be the composed algorithu of A....., Ag. Then, A is Σ e-differentially private.
Fact 1.8 (Post-processing, Proposition 2.1 of [DR* 14]). Let A be e-differentially private algo- rithm. Let g be a (possibly random) mapping. Then, g A is e-differentially private.
Preliminaries
We begin by introducing notation and a list of key definitions in Section 2.1. These concepts expanded upon in later sections. Section 2.2 presents the framework of minimum distance estimate algorithms, and Section 2.3 describes the nearly-linear time optimization proposed by [ABS24].
2.1 Notation and basic concepts
Notation and basic definitions: For n. E Z+, we use [n] to denote the set [I....,,] For an arbitrary probability distribution P over X' let P(x) be the PDF of P at E X. For a measurable subset S C X, let P(S) be the probability mass the set according to P. We use X P to denote random variable X that is drawn from the distribution P. Let PP Pallrv == supscx (P) P2()) be the total variation distance between two distributions P1 and Ps. For sample space ?
5

---

and an event E S Ω2 the indicator function g evaluates to 1 when E' occurs and 0 otherwise. We use the standard O, Ω2 θ notation for asymptotic functions, as well as (zz), {xx), (xx) to indicate additional (a) factors. A dataset D = (Z1,..., Uss E 2 is collection of i.i.d. samples from an unknown distribution P.
Optimal hypothesis: We use H;- to indicate hypothesis in a finite hypothesis class H. that achieves the smallest total variation distance to P. which is called OPT. If there are ties, then we pick one such hypothesis H.- arbitrarily. Therefore, OPT == mingen | Pl[iv | Pl[rv.
Scheffé sets: For every pair of hypotheses H,, H, E H. we define the Scheffé set of H; and H, as:
S.J [ { H+)))) Hx)x)) ifi Sp
if
is not difficult to show that the difference of probability masses of two distributions on the Scheffé set of H; and Hy is precisely the total variation distance between H; and Hy:
H: HyllTv= = sup (H((S) H, (H. Hy(St,))l
SCX
Semi-distances: We adopt the definitions of semi-distances from [ABS24], building on earlier work
in MSO8). For every pair of hypotheses H;, H2 E H. the semi-distance w. (H,) is the distance between H, and P measured on the Scheffé set of H; and H;; that we (H₂) == (H) P(S.)))
The maximum semi-distance of Hj is defined as W WH3)) == ma HH)).
Empirical semi-distances: Given measurable set S C X, we define the empirical distribution P of a dataset D [..] P(S) = Ex- Dayes. The empirical semi-distance (i;(H;) -
is similarly defined as w; (H)) ;= ( P(S,,),, where P is based on the observed samples drawn from P. Observe that wy (H1) is an estimation of w; (Hd)). For a given hypothesis H3 H and a set of hypotheses A S H. the proxy distance W (H,,) is defined as Wa(H;) := maxH, W; (Hy). Here, A is set of hypotheses that is updated throughout the algorithm to improve (HH))) as an approximation for W (H2).
Refined access model: As in prior work [DL01, MS08, ABS24), our algorithms will have query access to wy (H2), which follows from the standard access model. In the lemma below, we show that (H,) is within some o' of ui (H2) )) with sufficiently large samples, where o' can be taken to be ((o). The time complexity of our algorithms is measured in number of queries to ūū (H,), and each query takes (s)) compute.
Lemma 2.1. Let B, o' E (0,1) 1). If the number of samples 2 26 log(2n/3). then with probability at least 1 - B, the empirical semi semi-distances are accurate to an additive error of o':
1 (H₂) ws w;(HH)] So',
for all i,j E [m].
Proof. The estimates úū (11,) (S, P(S.,)) can be computed via sampling from / and counting the fraction of samples in the Scheffé set of H; and Hy. which is P(S.,). By a reverse triangle inequality:
(H,) w., (H₂) = |1 - P(S.,) - (H, P(S.,)) (P()))) -
P(S.)))
Therefore, by a standard application of the Hoeffding and union bounds, we can estimate each we (H,) using T0 log(2n/3) samples.
Lifting: Let H3, H, E H. We define the lift value Hę induces H, by w; (H,)H) WH())) In other words, the lift value quantifies the improvement of the proxy distance W WH(H)) H; is added to the set of hypotheses A used to compute W WA (HH maxH, (H.H.). For some o' E (0, 1), we say that HI, -lifts H1 if the lift value is at least o', or equivalently that H, lifts H, by least o'.

---

we say hypothesis H, E is (o', prompping with respect to Q if H, -'-lifts a random hypothesis H, sampled from Q with probability at least 1j. In other words, we have:
Prompting: Let Q be a distribution over H. For two parameters ,,, E (0,
Pr (,(HH))) WA 20 2
(2)
We now consider empirical analog for list of hypotheses K. that is sampled from Q. Let K = [Hj....,, "ii....,,,,,,, 5.] be a list of t hypotheses in H. For two parameters o'. 17 E (0, we say hypothesis H, H is (o', rempirical-prompeeee 7-firaction of the hypotheses in K. In other words, we have:
with respect to K. if H₃ o'-lifts at least an
(o.(H,)) 2 9
2.2 Background: minimum distance estimate
In this section, we sketch the key ideas behind previous approaches that use a minimum distance estimate [DL01, MS08). For a more detailed treatment, see Section 1.1 of [ABS24].
Our algorithms rely on computations of vi;{ (Hz) that approximate the true semi-distances w:; H For clarity, we will assume in this section that the approximations w; (Ht) are exact by Lemma 2.1. Observe that wi (H2) provides lower bound for HH, PlItv: specifically, w.(Ht,
(St.) P(S.,)l S. supscx (S) P(S) = [| Pl[tv. Thus, we can view w; (H1z) as an attempt to lower bound || - Pl[tv. In particular, we discover that wy (H₂)
( is large, then this suggests that true: when w; (Hz) is small, this does not imply that
H2 is far from P. However, the inverse H, is close to P.
Fortunately, when the particular semi-distance w. (H2) is small, can upper bound || TV The semi-distance w. (H2) has the following property: if w. (Hz) < OPT, then H, satisfies ||H, Plitv < 3 OPT, making H, a valid hypothesis to output. This follows from repeated applications of the triangle inequality:
OPT H - Pl 1 || - H4- + HH - Plltv = (S, (S) OPT (H: P(S ,)) - (H. - P(S--.)) OPT
S w.- (H2) + (H.) + OPT S w. (H,) + OPT.
(3)
An issue with using this metric (w.. (11,) < OPT) is that we know neither the optimal hypothesis H4:- nor ОPT. This is remedied by minimizing a maximum semi-distance W (H₂) == maxH. W; (H,). Let / be the hypothesis that minimizes (H;) over all hypotheses in H. Then, we claim that H
satisfies the desired property w;- (Ht OPT, implying that || - Pliv s 3 -PP as in the above discussion. This follows from:
Wi- (it) S ((A) S (H)+) = OPT.
The first inequality follows from W W(f) being maximum over all semi-distances of H. The second inequality follows from minimality of (ff) over all other hypotheses. The last inequality follows from the fact that every semi-distance measured against the optimal hypothesis itself bounded by OPT. Therefore, we reduce the problem of hypothesis selection to finding a H that minimizes (ff).
2.3 Background: approximating the maximum semi-distance
The MDE framework sample-optimal and achieves an optimal error parameter of a However, computing all (H,))ss )'s exactly requires Ó(n²) time, which is expensive for large hypotheses classes. Instead, [ABS24] computes a proxy distance (Hz)) = max wy (H2) for each H,. which serves as an updateable approximation that lower bounds W (H;)). All W. (Hz)'s are initially set to 0. The proxy distances are updated throughout the algorithm via an iterative process. At every iteration, selectively chosen hypothesis, called prompting hypothesis, is added to A. Carefully selecting A
7

---

ensures that for all H,, WH(H,) is a good approximation of W W(H)) without exhaustively computing all pairwise distances... At the end of this process, hypothesis with low proxy distance is selected as the output. Because only O[IA| -n) semi-distances are queried, this strategy enables a nearly-linear time algorithm in (() that still maintains the a = 3 guarantee.
To identify prompting hypotheses, [ABS24] keeps track of "buckets" of candidate hypotheses. Each hypothesis H, is assigned bucket according to its proxy distance W (H2). Because the algorithm seeks a hypothesis with approximately the smallest maximum semi-distance, it only focuses on the "lowest" bucket with the smallest proxy distances. Because large proxy distance implies that the hypothesis is far from P. the algorithm can disregard hypotheses with a large proxy distance. Hence, only the hypothesis in the lowest bucket are required to have accurate proxy distances.
The set of prompting hypotheses A will ensure that the lowest bucket has hypotheses with proxy distances close to the maximum semi-distances.
Recall that if a hypothesis H satisfies wy- (ff) < OPT, then it is a valid output. Conversely, we would like to avoid outputting a hypothesis for which we have wpp (ff) > OPT. The algorithm of [ABS24] filters out such hypotheses in the lowest bucket by updating their proxy distance and effectively sending them to "higher" buckets. Specifically, a key observation is that H will always significantly lift the proxy distances of hypotheses that are poor choices. Therefore, in every iteration of the algorithm, the goal is to find a prompting hypothesis H; that substantially improves a large portion of the proxy distances and empties out the candidate hypotheses in the lowest bucket.
It can be shown after roughly ((logn) n) iterations either the lowest bucket is fully emptied out, and move forward the next bucket. Or, there no more prompting hypotheses that can be identified. This condition implies that H₁- is not prompting. That is, H₁- could not lift most hypotheses in the lowest bucket. For those hypotheses, we must have that their wi- (Hz) S OPT. Hence, a random hypothesis in the lowest bucket under this condition is a valid output.
the algorithm
3 Private Hypothesis Selection Algorithm
3.1 Overview of our algorithm
In this section, we present an overview of Algorithm 1, our main algorithm for solving the hypoth- esis selection problem in the central model of DP that obtains an a 3 guarantee. Building on the previous work described in Section 2.2, our goal is to find hypothesis H that approximately minimizes W (ff). For each hypothesis H, E H. our algorithm keeps track of the proxy distances (HH)) Ea ty (H2). The set A will store a small set of prompting hypotheses accumu- lated so far. In every round & of our algorithm, we privately identify a prompting hypothesis Hi, that improves substantial portion of current proxy distances W*(H,) and update each W., a (H3) to max (Wa(H)) uis, (H2)) This effectively adds the privately selected Hi, to the set A.
The primary challenge of privatizing the process of identifying a prompting hypothesis in [ABS24] arises due to the bucketing scheme. This membership to bucket is highly sensitive due to its discrete nature. In particular, changing one sample of the dataset could potentially shift the membership of every single hypothesis in H by changing every W (H₃).
Therefore, to privately select hypotheses with low proxy distances without relying on buckets, we use the exponential mechanism. We maintain distribution of hypotheses Q that assigns each hypothesis
H, a probability that favors hypotheses with low proxy distance W WHG)).. Based on this change, we modify the notion of prompting from [ABS24]: we say that a hypothesis is prompting with respect to the distribution Q over H. rather than with respect the hypotheses in bucket. We also introduce the notion of (a', (o',n))-prra prrompting to quantify the "prompting-
of a hypothesis in Equation 2, where 1) the probability mass of hypotheses in Q that can be a' -lliited. Recall that a hypothesis H; -'Iiitts a hypothesis H, if w; (H,)- W. A (H2) 2 a'. After sufficiently many rounds, when no more prompting hypotheses can be found, we sample an output hypothesis fi from distribution Q.
Identifying prompting hypotheses: To privately identify prompting hypothesis H;, we test whether H, significantly lifts large probability mass of hypotheses in Q. A straightforward approach
8

---

is to first create a list IC of hypotheses that are sampled from Q. Then, we may choose prompting hypothesis using a threshold query for hypotheses in K. that are lifted significantly. Unfortunately, such a threshold query would have a very high sensitivity with respect to the dataset D, as a single change the dataset can shift every lift value from below the threshold to being above the threshold.
To solve the issue of the high sensitivity, we replace the exact count of hypotheses lifted with a new type of query called ,,, (.))). This query instead returns a quantile of the lift values of each hypothesis, which is a much more stable type of query with lower sensitivity.
More specifically, score,, D (H) is computed by Algorithm 2 as follows: first calculate the lift value H, induces on each element in IC. Then, we sort these values in non-increasee -occeascgg order and return the [n/2- |K]]]tb largest lift value. This significantly reduces the sensitivity of score,, (H,), as shown in section 1. Even if every single value in H, shifts by some amount due to a change in the dataset, the quantile that we return should not shift significantly. In Section E.2, we show that score,, (H.) can be used to identify whether or not H; is prompting.
Applying the SVT: We now wish to determine exactly which hypotheses have high score,, (H:)'s to find hypotheses that are significantly prompting. For every round of our algorithm, we attempt to find a prompting hypothesis. This task is equivalent to answering threshold queries. In general, this is very costly from the perspective of privacy. However, because we are only interested one hypothesis that passes the threshold, we use the sparse vector technique (SVT) [DNR 09] to find this hypothesis with minimal privacy cost.
Algorithm 3 describes an algorithm using the SVT, which privately outputs either the index i of the hypothesis that was detected to have a high score,,x.D(H.), or 1. if no hypotheses have sufficiently high scores. This algorithm has guarantees on finding a prompting hypothesis formalized in Theorem 6. First, whenever the SVT returns a hypothesis, we guarantee that is at least somewhat prompting, so we make progress at every round by updating the proxy distances. Second, whenever the SVT fails to find any prompting hypotheses, all hypotheses have small (H) )'s and are therefore unlikely to be prompting.
As in [ABS24]. H2- is typically prompting for hypotheses far from P. When the SVT is unable to find any prompting hypotheses, it implies that H;- is not prompting with respect to Q. Consequently, a large probability mass of hypotheses in Q 2-namely, those with minimal proxy distances-mun have proxy distances that cannot be lifted by H:-. Recall that all the poor hypotheses can be lifted by H₁-, so in this case, outputting any random hypothesis in Q will be valid with high probability.
Number of rounds: Because we do not allow hypothesis to be added to the prompting set more than once, our algorithm will certainly halt after most n rounds. However, this leads a quadratic bound on the time complexity. We show that the algorithm will halt after O(log n) rounds, yielding a nearly-linear time complexity.
Arguing about this round complexity is a key hurdle that arises in the private setting. The non-private algorithm in [ABS24] iteratively eliminates hypotheses from buckets. At every round, upon finding prompting hypothesis, a significant (say constant) fraction of hypotheses within the bucket have their proxy distances updated, leading their removal from the bucket. This ensures that even with an initial bucket of all n hypotheses, the algorithm concentrates on this bucket for only Ollog n) iterations. After this, the bucket is either empty or the algorithm halts due the lack of prompting hypothesis. However, adapting the notion of prompting to the case where we update only a set of hypotheses with constant probability mass according to Q fundamentally changes the analysis. Determining the actual fraction of updated hypotheses becomes much more complex. For example, we might update only one hypothesis, since it may hold a constant probability mass under Q.
To resolve this issue, we provide a refined analysis of the progress of the exponential mechanism. This analysis relies on the fact that the normalization term in the exponential mechanism's ''s probabilities must decrease with each prompting hypothesis added to the set A, as some proxy distances will increase but none can decrease. As a result, hypotheses whose proxy distances do not increase significantly will see their probabilities rise. As these probabilities cannot exceed one, changes to the proxy distances must be able keep up with the decrease in the normalization term. However, they can only keep up for so long, as each proxy distance is itself upper bounded by one. As a result, we can bound the number of rounds of our algorithm by Oloo n).

---

Enforcing privacy: Throughout every round of the algorithm, we incur two types of privacy costs: one from drawing [X] hypotheses from the exponential mechanism and another from identifying prompting hypothesis through the sparse vector technique. As we have discussed above, the types of queries our algorithm makes have low sensitivities with respect to the dataset. In Lemma B.I, we give complete proof of privacy by using basic additive composition.
3.2 Algorithm
In Algorithm 1, we begin by sampling samples from the unknown distribution make up a dataset D. We initialize A. the set of prompting hypotheses to be empty, and the proxy distance of each hypothesis to O. We then iteratively search, over most T rounds, for prompting hypotheses add to A. In each round, we re-calculate the probabilities of the exponential mechanism in Line 9 and draw list of hypotheses from this mechanism Line 10. We call the procedure of Algorithm 3 to identify hypothesis which is empirically prompting over K. using the sparse vector technique. In Section F, we thoroughly describe this procedure. Section E. we describe the COMPUTE-SCORE procedure used assign score to each hypothesis throughout PROMPTING-HYPOTTI
FIND- PROMPTING-HVPOOTIIISSS
returns a hypothesis, we add that hypothesis to A in Line 13 and update the proxy estimates of all hypotheses in Line 14. If HIND-PROMPTING- HAANNGGESYPTSIISS returns 1, indicating that it could not find a prompting hypothesis, break from the "for" loop, draw hypothesis using the exponential mechanism, and output that final hypothesis.
Algorithm A private algorithm for hypothesis selection
1: procedure SELECT- HYC.CTESHOOOTHHSHH........ c, a, (8)
Foge log" (n/B)) T + min (Ø (1t log (n/3)) n). + e log (n/3))
2:
3:
61 - 2 62
2T
4:
5:
D samples drawn from
we will use these samples compute semi-distances
6:
A B
7:
(A(H;) +- 0 for every Hj E
8:
for / = -,..., T do
(H₂)) x exp (HH)
9:
for every H₃ E H
2A(WA)
IC k hypotheses drawn from Q
sample using exponential mechanism
11:
He +- FIND-PROMPIING-YYYOOHHES (2,
2 o' 8 H A,K, K.K,D) P) > Allgorithm 3
T
12:
if H₁ # 1 then
13:
A (H)
add Hi prompting set
14:
W (H₂) max (Wa(H)),e,(HH)))
de (H:)) for every H, E H
15:
else
16:
break
failed find prompting hypothesis
return A Q and halt
Theorem 3. Let c,8,0 E (0, 1). Algorithm 1 is an (a= 3, (.,,,va-r learner for hy- (8ot log (n/3) samples and has time complexity
pothesis selection that uses
min 330 n mologg (n/B), Bl n² log (n/
Proof sketch: In Section B, prove that Algorithm is e-differentially private. In Section C, we prove the correctness of Algorithm 1. Specifically, in Section C.1, we show that each hypothesis added A will be prompting with high probability. In Section C.2, show that, if this is the case, then the algorithm will halt after at most (log n) rounds. Section C.3, we show that, if the algorithm halts early, then it will output valid hypothesis with high probability. In Section C.5, give exact settings for T, and such that our proof of correctness holds. Finally, in Section D, we prove the time complexity of Algorithm
10

---

4
Acknowledgments
R.S. acknowledges partial support from the Ken Kennedy Institute Research Cluster Fund and the Ken Kennedy Institute Computational Science and Engineering Recruiting Fellowship, funded by the Energy HPC Conference and the Rice University Department of Computer Science.
References
[AAAK21] Ishaq Aden-Ali, Hassan Ashtiani, and Gautam Kamath. On the sample complexity of privately learning unbounded high-dimensional gaussians. In Proceedings of the 32nd International Conference on Algorithmic Learning Theory, ALT, Proceedings of Machine Learning Research. PMLR, 2021.
[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. PMLR, 2023.
[AAC*24] 24] Anders Aamand, Alexandr Andoni, Justin Chen, Piotr Indyk, Shyam Narayanan, Sandeep Silwal, and Haike Xu. cediitical-compuaatiinn tradc-offs for density estima- tion. Advances in Neural Information Processing Systems, 37:97907-979277 2024.
[ABH* *ABH+20] 20] Hassan Ashtiani, Shai Ben-David, Nicholas J. A. Harvey, Christopher Liaw, Abbas Mehrabian, and Yaniv Plan. Near-optimal sample complexity bounds for robust learning of gaussian mixtures via compression schemes. J. ACM, 67(6):32:1332:44 2020.
[ABM18] Hassan Ashtiani, Shai Ben-David, and Abbas Mehrabian. Sample-efficient learning of mixtures. In Sheila A. Mcllraith and Kilian Q. Weinberger, editors, Proceedings of the Shiony- AAAI Conference on Artificial Intelligence, pages 2679-2688 AAAI Press, 2018
[Abo18] John M. Abowd. The census bureau adopts differential privacy. In Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, page 2867, 2018.
[ABR16] Maryam Aliakbarpour, Eric Blais, and Ronitt Rubinfeld. Learning and testing junta distributions. In Proceedings of the 29th Conference Learning Theory, COLT 2016, New York, USA, June 23-26, 2016, pages 19-46, 2016.
[ABS23] Maryam Aliakbarpour, Mark Bun, and Adam Smith. Hypothesis selection with memory constraints. In A. Oh, T. Naumann, A. Globerson, K. Saenko, M. Hardt, and S. Levine, editors, Advances in Neural Information Processing Systems, volume 36, pages 50453- 50481. Curran Associates, Inc., 2023.
[ABS24] Maryam Aliakbarpour, Mark Bun, and Adam Smith. Optimal hypothesis selection (almost) linear time. In A. Globerson, L. Mackey, D. Belgrave, A. Fan, U. Paquet, J. Tomczak, and C. Zhang, editors, Advances in Neural Information Processing Systems, volume 37, pages 141490-141527. Curran Associates, Inc., 2024.
[ACFT19] J. Acharya, C. Canonne, C. Freitag, and H. Tyagi. Test without trust: Optimal locally private distribution testing. In Proceedings of Machine Learning Research, volume 89 of Proceedings of Machine Learning Reseurch, pages 2067-2076. PMLR, 2019.
[ADH*24] 24] Hilal Asi, John C Duchi, Saminul Haque, Zewei Li, and Feng Ruan. Universally instance-optimal mechanisms for private statistical estimation. In The Thirty Seventh Annual Conference on Learning Theory, pages 221-259. PMLR, 2024.
[ADKR19] Maryam Aliakbarpour, Ilias Diakonikolas, Daniel Kane, and Ronitt Rubinfeld. Private testing of distributions via sample permutations. In Advances in Neural Information Processing Systems 32: Annual Conference on Neural Information Processing Systems 2019, NeurIPS 2019, 8- 14 December 2019, Vancouver, BC, Canada, pages 10877- 10888, 2019.
11

---

[ADR18] Maryam Aliakbarpour, Ilias Diakonikolas, and Ronitt Rubinfeld. Differentially private identity and equivalence testing of discrete distributions. In Proceedings the 35th International Conference on Machine Learning (ICML., volume 80, pages 169-178, 2018.
[AF] 18] Jayadev Acharya, Moein Falahatgar, Ashkan Jafarpour, Alon Orlitsky, and Ananda Theertha Suresh. Maximum selection and sorting with adversarial comparators. The Journal of Machine Learning Research, 19:59:1-5::31, 2018.
[AGJ+22] Kareem Amin, Jennifer Gillenwater, Matthew Joseph, Alex Kulesza, and Sergei Vassil- vitskii. Plume: Differential privacy scale. CoRR, abs/2201. 1603, 2022.
[AJM20] Kareem Amin, Matthew Joseph, and Jieming Mao. Pan-private uniformity testing. In Jacob D. Abernethy and Shivani Agarwal, editors, Conference on Learning Theory, COLT 2020, 9-12 July 2020, Virtual Event [Graz, Austria]. volume 125 of Proceedings of Machine Learning Research, pages 183-218. PMLR, 2020.
[AJOS14] Jayadev Acharya, Ashkan Jafarpour, Alon Orlitsky, and Ananda Theertha Suresh. Sorting with adversarial comparators and application to density estimation. In 2014 IEEE International Symposium on Information Theory, pages 1682-1686, 2014.
[ASZ18] Jayadev Acharya, Ziteng Sun, and Huanyu Zhang. Differentially private testing of identity and closeness of discrete distributions. In S. Bengio, H. Wallach, H. Larochelle, K. Grauman, N. Cesa-Bianchi, and Garnett, editors, Advances in Neural Information Processing Systems, volume 31. Curran Associates, Inc., 2018.
[BB20] Thomas Berrett and Cristina Butucea. Locally private non-au non-as asymmtommiiic testing of discrete distributions is faster using interactive mechanisms. In Hugo Larochelle, Mare' Aurelio Ranzato, Raia Hadsell, Neural Information Processing Systems 33: Annual Conference Neural Information Processing Systems 2020, NeurlPS 2020, December 6- 12, 2020, virtual, 2020.
Balcan, and Hsuan- Tien Lin, editors, Advances in
[BBK*21] 21] Olivier Bousquet, Mark Braverman, Gillat Kol, Klim Efremenko, and Shay Moran. Statistically near-optimal hypothesis selection. In 62nd IEEE Annual Symposium on Foundations of Computer Science, FOCS 2021, Denver, CO, USA, February 7-10, 2022, pages 909-919. IEEE, 2021.
[BКМ19] Olivier Bousquet, Daniel Kane, and Shay Moran. The optimal approximation factor in density estimation. In Alina Beygelzimer and Daniel Hsu, editors, Proceedings of the Thirty-Second Conference on Learning Theory, volume 99 of Proceedings of Machine Learning Research, pages 318-341, PMLR, 25-28 Jun 2019.
[BKSW19] Mark Bun, Gautam Kamath, Thomas Steinke, and Zhiwei Steven Wu. Private hypothe- sis selection. In Hanna M. Wallach, Hugo Larochelle, Alina Beygelzimer, Florence d' A'Ach--Buu Bucc Emily B. Fox, and Roman Garettt, editors, Advances in Neural Infor- mation Processing Systems 32: Annual Conference on Neural Information Processing Systems 2019, NeurlPS 2019, December 8- 14, 2019, Vancouver, BC, Canada, pages 156-167,40 2019.
[CDKI7] B. Cai, C. Daskalakis, and G. Kamath. Priv'it: Private and sample efficient identity testing. In International Conference on Machine Learning, ICML, pages 635-644, 2017.
[CKM* 19] Clément L. Canonne, Gautam Kamath, Audra McMillan, Adam D. Smith, and Jonathan R. Ullman. The structure of optimal private tests for simple hypotheses. In Moses Charikar and Edith Cohen, editors, Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, STOC 2019, Phoenix, AZ, USA, June 23-26, 2019, pages 310-321. ACM, 2019.
[CKM*20 20] Clément L Canonne, Gautam Kamath, Audra McMillan, Jonathan Ullman, and Ly- dia Zakynthinou. Private identity testing for high-dimensional distributions. In H. Larochelle, M. Ranzato, R. Hadsell, M.F. Balcan, and H. Lin, editors, Advances Neural Information Processing Systems, volume 33, pages 10099-10111. Curran Associates, Inc., 2020.
12

---

[Dia16] Ilias Diakonikolas. Learning structured distributions. In CRC Handbook of Big Data, pages 267-283. 2016.
[Dif17] Differential scale. wwwtt-tiiiacc-atteeeee
Privacy
Team,
Learning with privacy https: wttpe///macaaaaaaaiiiieie apple. com/research/
Apple.
learning-wiid
2017. Accessed: 2024-05-22.
[DK14] Constantinos Daskalakis and Gautam Kamath. Faster and sample near-optimal algo- rithms for proper learning mixtures of gaussians. In Conference on Learning Theory, pages 1183-1213, PMLR, 2014.
[DL96] Luc Devroye and Gábor Lugosi. A universally acceptable smoothing factor for kernel density estimates. The Annals of Statistics, 24(6):2499 - 2512, 1996.
[DL97] Luc Devroye and Gábor Lugosi. Nonasymptotic universal smoothing factors, kernel complexity and Yatracos classes. The Annals of Statistics, 25(6):2626 2637, 1997.
[DL01] Luc Devroye and Gábor Lugosi. Combinatorial methods in density estimation. Springer, 2001.
[DMNS06a] Cynthia Dwork, Frank McSherry, Kobbi Nissim, and Adam Smith. Calibrating noise to sensitivity in private data analysis. In Shai Halevi and Tal Rabin, editors, Theory of Cryptography, pages 265-284, Berlin, Heidelbberg 2006. Springer Berlin Heidelberg.
[DMNS066] Cynthia Dwork, Frank McSherry, Kobbi Nissim, and Adam Smith. Calibrating noise to sensitivity in private data analysis. In Theory of Cryptography: Third Theory Cryp- tography Conference, TCC 2006, New York, NY, USA, March 4-7, 2006. Proceedings 3, pages 265-284, Springer, 2006.
[DNR+009] Cynthia Dwork, Moni Naor, Omer Reingold, Guy N. Rothblum, and Salil Vadhan. On the complexity of differentially private data release: efficient algorithms and hardness results. Proceedings of the Forty-First Annual ACM Symposium on Theory of Computing, STOC '09, pages 381-390, New York, NY, USA, 2009. Association for Computing Machinery.
[DR + 14] Cynthia Dwork, Aaron Roth, et al. The algorithmic foundations of differential privacy. Foundations and Trends@ in Theoretical Computer Science, 9(344)2211-007 2014.
[DVG20] Damien Desfontaines, James Voss, and Bryant Gipson. Differentially private partition selection. CoRR, abs/2006.03688 2020.
[EPK14] Úlfar Erlingsson, Vasyl Pihur, and Aleksandra Korolova. Rappor: Randomized aggre- gatable privacy-rresering ordinal response. In Proceedings of the 2014 ACM SIGSAC Conference on Computer and Communications Security, pages 1054-1067. 2014.
[GKK 20] Sivakanth Gopi, Gautam Kamath, Janardhan Kulkarni, Aleksandar Nikolov, Zhi- wei Steven Wu, and Huanyu Zhang. Locally private hypothesis selection. In Jacob D. Abernethy and Shivani Agarwal, editors, Conference on Learning Theory, COLT 2020, 9- 92 July 2020, Virtual Event [Groz, Austria), volume 125 of Proceedings of Machine Learning Research, pages 1785-1816. PMLR, 2020.
[GR18] M. Gaboardi and R. Rogers. Local private hypothesis testing: Chi-square tests. In Proceedings of the 35th International Conference on Machine Learning, ICMI 2018, pages 1612-1621, 2018.
KKLN 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.
[KT18] Krishnaram Kenthapadi and Thanh T. L. Tran. Pripearl: A framework for privacy- preserving analytics and reporting at linkedin. In Alfredo Cuzzocrea, James Allan, Norman W. Paton, Divesh Srivastava, Rakesh Agrawal, Andrei Z. Broder, Mohammed J. Zaki, K. Selçuk Candan, Alexandros Labrinidis, Assaf Schuster, and Haixun Wang.
13

---

editors, Proceedings of the 27th ACM International Conference on Information and Knowledge Management, CIKM 2018, Torino, Italy, October 22-26, 2018, pages 2183-2191. ACM, 2018.
[LSL16] Min Lyu, Dong Su, and Ninghui Li. Understanding the sparse vector technique for differential privacy. arXiv preprint arXiv: 2016.
[9SV+19] Mathias Lécuyer, Riley Spahn, Kiran Vodrahalli, Roxana Geambasu, and Daniel Hsu. Privacy accounting and quality control in the sage differentially private ML platform. CoRR, abs/1909.01 2019.
[MS08] Satyaki Mahalanabis and Daniel Stefankovic. Density estimation in linear time. In 21st Annual Conference on Learning Theory- COLT, pages 503-512, 2008.
[MT07] Frank McSherry and Kunal Talwar. Mechanism design via differential privacy. In 48th Annual IEEE Symposium on Foundations of Computer Science ( (FOCS'07, pages 94-103, 2007.
[NH12] Arjun Narayan and Andreas Haeberlen. Djoin: Differentially private join queries over distributed databases. In Chandu Thekkath and Amin Vahdat, editors, 10th USENIX Symposium on Operating Systems Design and Implementation, OSDI 2012, Hollywood, CA, USA, October 8-10, 2012, pages 149-166 169.162. USENIX Association, 2012.
[PAA24] Alireza Fathollah Pour, Hassan Ashtiani, and Shahab Asoodeh. Sample-optimal locally private hypothesis selection and the provable benefits of interactivity. In The Thirty Seventh Annual Conference on Learning Theory, COLT, Proceedings of Machine Learning Research. PMLR, 2024.
[PAJL25] Ankit Pensia, Amir R. Asadi, Varun Jog, and Po-Ling Loh. Simple binary hypothesis testing under local differential privacy and communication constraints. IFFE Trans. Inf. Theor, 71(1):592-66) 613922267,4444 January 2025.
[PJL24] Ankit Pensia, Varun S. Jog, and Po- Loh. The sample complexity of simple binary hypothesis testing. In Shipra Agrawal and Aaron Roth, editors, The Thirty Seventh Annual Conference Learning Theory, June 30 July 3, 2023, Edmonton. Canada, volume 247 Proceedings of Machine Learning Research, pages 4205-4206 PMLR, 2024.
[SOAJ14] Ananda Theertha Suresh, Alon Orlitsky, Jayadev Acharya, and Ashkan Jafarpour. Near-optimal- -sappe estimators for spherical gaussian mixtures. In Z. Ghahramani, M. Welling, Cortes. N. Lawrence, and K.Q. Weinberger, editors, Advances in Neural Information Processing Systems, volume 27, 2014.
[Ver18] Roman Vershynin. Hlihh-Dieensional Probability: An Introduction with Applications Data Science. Cambridge University Press, 2018
[Ya185] Yannis G. Yatracos. Rates convergence of minimum distance estimators and kol- mogorov's entropy. The Annals of Statistics, 13(2):768- 774, 1985.
14

---

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: Our abstract and introduction adhere to Theorem 3, which states the main contribution of the paper.
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 long is clear that these goals are not attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification: Please refer to the paragraph after Theorem 2 in the Introduction regarding extra factors in our sample complexity.
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 a separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (c.g.. independence assumptions, noiseless settings, model sell-speciiiitiinn 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 on the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on 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-tex, system might not be used reliably to provide closed captions for online lectures because it fails handle technical jargon.
The authors should discuss the computational efficiency of 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 faimesss.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a 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 an 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 proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
15

---

Answer: [Yes]
Justification: Our problem setup is described in Section 1.1. All the proofs are included in the appendices.
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 to 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:
This paper is thcoretical and does not contain experiments.
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
4.1 If the contribution is primarily a new algorithm, the paper should make it clear how reproduce that algorithm.
4.2 If the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
4.3 If the contribution is a new model (e-g., a large language model), then there should either be way to access this model for reproducing the results way to reproduce the model (c.g., with an open-source dataset or instructions for how to construct the dataset).
4.4 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
16

---

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:
This paper is theoretical and does not contain experiments.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nips.c cc/
Sublic//uiieesCodeSStte sosioddesssmmssssooooooorrr 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 to reproduce the results. See the NeurlPS code and data submission guidelines (https:
wtsps.cc/ppblic//eeeccc leaiic/gguiessee /CodeSubmi ssi ssionPoiccy 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: This paper is theoretical and does not contain experiments.
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 be 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: This paper is theoretical and does not contain experiments.
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.)
17

---

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 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 error rates).
If 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 to reproduce the experiments?
Question:
Answer: [NA]
Justification: This paper is theoretical and does not contain experiments.
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, cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental rums as well as 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 of ethics
Question: Does the research conducted the paper conform, in every respect, with the NeurlPS Code of Ethics https htt//enuripp../ ctp http/p/iic/tthicstuieeeeeeeeeeee
Answer: [Yes]
Justification:
There are no violations of the NeurIPS Code of Ethics in this paper.
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: While algorithms using hypothesis selection can have practical impacts, this paper describes the theoretical underpinning of the problem, making it difficult to meaningfully comment on its social impact. We believe its main impact will be improving scientific understanding of private hypothesis selection.
Guidelines:
The answer NA means that there is 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.
18

---

Examples of negative societal impacts include potential malicious unintended uses (e.g., disinformation, generating fake profiles, surveillance), faireess considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to 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 is being used as intended but gives incorrect results, and harms following from (intentional unintentional) misuse of the technology.
If there are 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 to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML).
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:
This paper poses such risks.
Guidelines:
The answer NA means that the paper poses no 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 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. Licenses for existing assets
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?
Question:
Answer: [NA]
Justification: This paper uses real asset other than publicly available papers have cited.
Guidelines:
The answer NA means that the paper does use 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 (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided.
19

---

If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswi thcode. com conddatasets 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.
this information is not available online, the authors are encouraged to reach out to the asset's s creators.
13. New assets
Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Question:
Answer: [NA]
Justification: This paper does not release new assets.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/cooeemmodll as part their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset used.
At submission time, remember to anonymize your assets (if applicable). You can either create anonymized URL or include an anonymized zip file.
14. Crowdsourcing 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: This paper theoretical and does not contain any crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing 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 in 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 (TRB) 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 equivalent approval/teview based the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: This paper is theoretical and does not contain any crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsoureing nor research with human subjects.
20

---

Depending on 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 we expect authors to adhere to the NeurIPS 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
Does the paper describe the usage of LLMs if it is an important, original, or non-standard component of the core methods this research? Note that if the L.LM is used only for writing, editing, or formatting purposes and does not impact the core methodology, scientific rigorousness, or originality the research, declaration is not required.
Question:
Answer: [NA]
Justification: This paper does not use LLMs for any important, original, or non-standard components.
Guidelines:
The answer NA means that the method development in this research does not involve I.LMs as any important, original, or non-standard components.
Please refer to LLM policy (https: http:///nnnu./eeeeeeeeeee wwweurips.ccoooffeeeeeeeeeeeeeee cccoooooeeecccce222055555 for what should or should not be described.
A Other Related Works
Hypothesis selection has also been studied in the local model of DP [KLN+ where the data curator is not trusted and thus only has access to the privatized version of users' data. Gopi et al. [GKK*20] showed that the sample complexity in the local model is linear in n, exponentially
larger than the central DP setting. Specifically, they proved lower bound of Ω (o²2). They also
proved two upper bounds of O nlog n 0422
for non inteertaeetive algorithms and O x lolog n log log n
(with a = 27) for sequentially interactive algorithms with Ollog log n) rounds. A recent algorithm by Pour al. [PAA24] closed the gap between upper and lower bounds by designing sequentially interactive algorithm using O
log" 1/3 samples, with = 9 and Ollog log n) rounds.
of g²min(e²,11
Another related problem in statisties is simple hypothesis testing. Given distributions / and Q. and a dataset D sampled from one of them, the goal is to determine whether D was drawn from P or Q. This setting resembles hypothesis selection where have only two candidate distributions. Cannone et al. [CKM* 19] developed private algorithm for simple hypothesis testing that achieves optimal sample complexity. Further developments on sample complexity on private simple hypothesis selection include [PJL24, PAJL25] under the local model of DP. Other examples within the broader topic of private hypothesis testing include [CDK17, GR18, ADR 18, ASZ18, ADKR19, ACFT19, AJM200, CKM+20, BB20].
Asi al. [ADH+24] give an instance-optimal algorithm for hypothesis selection when the hypothesis class H contains the true distribution P (i.e. OPT = 0). Their algorithm has logarithmic sample complexity and time complexity O(n²s).
A.1 Industrial applications of DP
We highlight several lines of research in differentially private data analysis motivated by real- world challenges. One example is the partition selection problem, where users aim to compute aggregate statistics over data grouped according to user-specified criteria. To ensure privacy, designers must bound the sensitivity of the statistics, decide which data partition to release, and maintain computational efficiency. Relevant works include Desfontaines al. [DVG20) and Google's Plune system 22].
21

---

Another direction concerns private analytics of user actions, where the goal is to prevent attack- ers from learning user's past behavior by repeated observation public analyties. Linkedln's PriPeARI. [KT18] provides such protection, even towards persistent attackers who observe the analyties overtime.
Privacy leakages also emerge from releasing models trained on sensitive data. To mitigate this problem, Lécuyer al. [LSV 19] developed Sage, machine learning platform that distributes training across data blocks, monitors privacy loss per blocks, and retires blocks once their privacy budget is depleted.
Lastly, the problem of answering queries across multiple private databases has also been studied. A representative system is DJoin by Narayan et al. [NH12].
B Proof of Privacy of Algorithm 1
Lemma B.1. Algorithm is c-differentially private.
Proof. In each iteration, Algorithm 1 samples K,, hypothesis list of size k. where each hypothesis H, is drawn with probability proportional to its proxy distance, Wa(H)). In Lemma E.3, we show that each proxy distance has sensitivity 1/s. We privatize this sampling of hypotheses using the exponential mechanism (Definition 1.4).
After drawing K., the algorithm calculates score,, (Hz, for each hypothesis Hj, and searches for a hypothesis with high s, D (H2). For each Hy, recall that ,,o (H2) is an empirical quantile of the promptingness of H, on K. K. is treated as publicly available when computing each score. This fact, along with the choice to use quantiles to calculate each score, leads to low sensitivity of the score function. Specifically, in Lemma E.4, we prove that the score function has sensitivity 2/s. We privately select hypothesis with sufficiently high score using the sparse vector technique (Algorithm 3), allowing us to incur loss of privacy independent of the number of hypotheses.
All remaining steps in the round either post-process K. and the chosen prompting hypothesis Hip or reveal no further information about the dataset. Therefore, in each round, we only consider the privacy loss of drawing hypotheses and finding a prompting hypothesis. By basic composition (Fact 1.7), sampling & hypotheses from Q and calling FIND-PROMPTING -YYTHINSSS once gives the following privacy loss in each round:
E- k
+ k 2T
2(kT +
Algorithm takes at most iterations. The composition of T rounds of the above procedure results privacy loss of:
T. (
E-
e KT
27 2(KT +1)
-
2(K7 +1)
Finally, Algorithm samples from Q to obtain output distribution in the last round. Hence, Algorithm 1 has total privacy loss of:
KT
C.
2 +1) +q=
+
2
2(KT
2(T +1)
C Proof of Correctness of Algorithm 1
The correctness proof of Algorithm 1 proceeds by first showing that, with high probability, three key events occur: i) the empirical semi-distances are accurate, ii) in each round, the score of every hypothesis accurately reflects its ability to lift many hypotheses, and iii in each round, FIND- SROMPTING--YPOTERE
either outputs a high-scoring hypothesis or correctly identifies that no such hypothesis remains. We then show that if these events hold, the algorithm will eventually fail to find a prompting hypothesis and will halt after less than T rounds. Finally, we prove that the key events hold and the algorithm halts early, the output is, with high probability, less than (30PT + σ) -far from P.
22

---

C.1 Key events occur
Let 01 = 0/4 and 02 = a/4. The correctness of Algorithm relies the following key events:
With the samples that we draw from P, we calculate the empirical semi-distances between all pairs of hypotheses to within aaddiiive error.
2. In each round of the algorithm, if the score of a hypothesis is least d2/2, then that hypothesis is (dz/2, //4 prompping with respect to Q. If the score of hypothesis is less than d2 then that hypothesis is not (Ø2, promptingg with respect to Q.
3. In each round of the algorithm, if FIND-PROMPTING-HYYE HYPOTIISSSS outputs hypothesis, then the score of that hypothesis is least 02/2. it does output a hypothesis, then no hypothesis had score greater than d2.
Each of these events fails occur with low probability, provided s, the number of samples, and k, the number of hypotheses sampled at each round, are sufficiently large. We recall the specific assumptions on s and & that guarantee each event as follows:
Empirical semi-distances are 01 accurata: Lemma 2.1 ensures that, with probability at least 1 - 3/6, the empirical cemi-distances are accurate up to additive factor of 01 if
log 12n/B)
20
Scores reflect prompting ability: In Lemma E.5, we show that, in each round, with high probability, the score of each hypothesis reflects whether that hypothesis is prompting with respect to the hypotheses in Q. Specifically, the lemma ensures that, with probability at least 1 - (6),,,, if
12 12lo(6nT//
(5)
7
then, in round for all H, if the score of H, at least 02/2, H, is 1/)p2./n//)-pmmmmpphi with respect to Q, and, if the score of H, is less than d2, H; is not (Øz, -prompting with respect to Q.
FIND- PROMPTING-HYOOTHIIIIIII probability, the FIND-PROMEN HROMPTING-HYPOTHESS procedure succeeds either finding prompting hypothesis identifying that there such hypotheses. Specifically, the theorem ensures that, with probability at least 3/((T)) if
succeeds: In Theorem 6, show that, in each round, with high
02C2
A <
(6)
32 log(12nT/B)
then, in round I, SOO.--PROMPINNGHHPPPPEEEE (<2, A = 2/s, 02, n. H A,A.) outputs H;,, the score of H₃, is at least /2, and, if the procedure outputs 1. each H,, has score less than d2. Note that this bound on implics the following bound on s, as A 2/s:
64
8 >
log( 12nT/8),
0262
For now, assume that 8, 7 and satisfy these requirements. Section C.5, we will give precise choice of parameters that satisfies these, along with other constraints. Then, the probability that at
23

---

least one of the three key events does not occur is: Pr[ at least one key event fails] v Pr[ Prssemi-distance estimation fails]
+
Pr(at at least one score is inaccurate in round t]
+
PPEEND-PROMPTAN-HHOOOHSS fails in round t]
t=1
T
B
T
B
<
67
6T
1=1
t=1
B
2
C.2 Algorithm halts early
outputs hypothesis with score at least 02/2, then that hypothesis must be able to 02/2-lif 2-lift at least an /// 2-fractooon of K. If its scores are an accurate representation of its ability lift Q, then H; is (a2/2, (1/44)poompping over Q. In this section, we show that, if each hypothesis added to the prompting set is truly (02/2 22, n/ 4)romm)ptii is, if the second and third events described in the previous section hold-, then the algorithm will reach Line 16 and halt before executing ' rounds.
TIIN-PROMPTING PROMPTING-HPPOTEESS HYPOTHESIS
Theorem 4. Let o' = 02/2, n/ 4. Assume exp hypothesis added the prompting set is (a', ,n/ pprompiiiin with respect Q in the round it is added.
CIO'
< 3. Further, assume that each
22(WA)
Then Algorithm 1 terminates after at most min
(log (n) + 2A(Wa) OPT) rounds.
log (o
Proof Sketch Initially, Q is the uniform distribution over (H,,..., H.,. as each proxy distance w/ (H₂) initialized to O. After each round of the algorithm, new hypothesis Hi, is added the prompting set and the proxy distance of each hypothesis either increases or remains constant. If each H, is truly prompting over Q. the normalization term of the exponential mechanism decreases each round, amplifying the probabilities of the hypotheses with proxy distances that are relatively unchanged by the addition of H,. By characterizing these changes, we give an upper bound T on the number of rounds our algorithm will execute before returning a hypothesis. Note that this upper bound must be less than n, as every hypothesis is added to the prompting set at most once. If we choose T to be greater than T, the algorithm will halt before executing T rounds.
To formally prove Theorem 4, we introduce the following notation, exactly describing the probability distribution induced by the exponential mechanism in each round.
Definition C.1 (Exponential mechanism at round t). Recall that, at round t, the hypothesis sampling distribution, Q(!,, is defined as follows:
Q(1)
(H2)
exp
2A(WA)
6
Z(1)
where
z Σ exp
-WH(H,)
(8)
2A(WA)
1=1
and (H) is the proxy distance of H at round t.
(H)
We also require the following lemma, which demonstrates that 7 decreases with each round, and bounds the amount of this decrease.
Lemma C.2. Let E .I, Let d' E =0, Assume exp (-
cid' 22(WW))
< Define (
and ((++)) in Definition 8. Assume the hypothesis Hi, added to the prompting set in round & is (o' nn (o'.n"")promppiiii >-prompting with respect to ((1), Then, have:
24

---

z(++1) Z -
1 2
(9)
Before proving Lemma C.2, we introduce, for each hypothesis H,, value u (H,) describing the increase in Hj's 's proxy distance between rounds aandd ( + 1:
u (H,)
(((+1) W (H₃) (H,) 1 (0) (H2).
(10)
Recall that we define (e+1)) ( (Hz) to be the maximum empirical semi-distance between H3 and the hypotheses in the prompting set A. Thus, when we add Hi, to the prompting set round e (((++) (H₂) is the maximum of (H,))) and W0 (Hz):
w A
(H₃) = max Wi (Hz) A ( (H,)
The difference between V (e+1) (Hz) and (H2) is thus lower bounded by the difference between w((++1) (H2) and wi (H2): (e+ (Hz)) = W (H) (H, 2 0ú (H1) W (H1).
If Hy is (a', -prompinn,, the definition of prompting allows us to lower bound the probability that this difference greater than a':
Q Tú (H,) W (2) H1 1H)2 2 r/ Pr (w ( (H₂) 2 2d 2
2/ n/. (11)
To prove Lemma C.2, we relate the ratio in question to the expected value of a function of these differences. If the hypothesis added the prompting set at round is prompting, Equation 11 gives tail bound on each of these differences. Combining this expected value and tail bound with careful consideration yields the desired bound.
Proof of Lemma C.2. Considering the ratio in question, we expand 7(++1) as follows:
1(++)
(i((+1) (H))
Z
(
exp
2A(WA)
(12)
Rewriting (L+1) A
(Hz) in terms of ul (H(+))(HI,) and w-(() (Hz) for every j. we have:
((++))
1 a
61
(W:) + ((H4))HH))
exp
2(0)
7
2A(WA)
j=1
C1
61
Z
2A(WA)
eexp
22(WW))
1=1
a
Σ j=1
((0) (H₂)
C1 2A(WA)
a ((+))(H)))
exp
The second equality follows from the definition of Q(9) (H,). Then, notice that the final line above forms an expectation over (0) We can rewrite it as such:
(H,) ].
-HH
exp
G
(1+1) (HH))HH)))
(13)
AA(WA)
25

---

Assuming the hypothesis added to the prompting set at round é is prompting, Equation I applies. We will use that bound on the probability to bound the expectation Equation 13. To do so, as the argument of the expectation is non-negative, we begin by applying the integral identity [Ver18]:
61
-u (
exp
2A(WA)
exp
61
u (H()
> dt.
2A(WA)
Rearranging to isolate u (Hz)) within the probability gives:
Pr u < (WA))
(H,)
log dl.
C
We apply a change of variables, letting === 23(Wa) log ::
Prin~Que (e+1) ( <w]
VEI
2A(WA)
eex
2A (W
du
Pri u ((e+)) <
61
ve1
eep
du.
2A(WA)
2A(WA)
Because (f+1) (H,) is nen-negative, the integrand when v < 0, and we need only evaluate the integral from = 0 to oc:
Prof~qio u (((+))(H)))) <v] (2A(WA))
VET
exp
dv.
2A(WA)
By Equation 11, we know that, for any S 0'. Pr (e(n(e1) (H,) 20 2 n/. This implies that, for any [0, o'), we can upper bound Pr [ ( (H,) < v) by 1 1-1 At the same time, for v > a', we can upper bound Pr [u (H,))) < v] by 1. Applying these bounds, the resulting integral is:
S0 (1
n'). (1-
.exp
061
dv
2A (AAWA)
2A (WA)
DC1
1
exp
du
2A(WA) A)
2A(WA) A)
000
1
E1
.exp
UE1
du
n/.
exp
-
E1
du
0
2A(WA)
2A(WA)
2A(WA)
2A 2A(WA)
lim
exp
T/ exp
- 2A(WA) 1
2A(WA)
lim exp
exp
2A(WA)
24(WA)
+ n
exp
exp
-0 2A(WA)
2A(WA)
-1
=1 T/ exp
-o'- 2A(Wa)
-1
26

---

Under the assumption exp
s,o' (- 22)(W2))
1 the following holds:
1 1- n/
(-exp/
(- Eio'
)) (~2A(WA))
7/ S -
2
Lemma C.2 implies that when hypothesis H2, added to the prompting set, the probability of sampling hypothesis H, which is not significantly lifted by H,, increases. As continue to add prompting hypotheses which do not significantly lift H Q(H,) continues to increase. As this probability approaches 1 and H, is repeatedly sampled by the exponential mechanism, either will find a hypothesis which lifts Hj. in which case its probability will decrease, or we will halt, as we could not find such hypothesis. At any given round, we know that the probability of sampling any hypothesis cannot grow until exceeds We use this fact to upper bound the number of rounds of Algorithm 1, thus proving Theorem 4.
Proof of Theorem 4. Note that the algorithm cannot add more than hypotheses the A, will only check for prompting hypothesis among the hypotheses in H \ A. As result, the algorithm does not run for more than rounds.
Fix t 2 O. Consider the probability that Hj is selected by the exponential mechanism at round t + 1, Q((+1) (H₃):
Q(++1) (11,) Z(+1)
1
exp
61
WA
(((+
2A(WA)
1
61 2A(WA)
(wiP (((t))
z(+1)
exp
z(0)
W WH)(H)
E1 2A(Wa)
-u(t))(HH)
7(++1)
7(0)
exp
2A(WA)
.cxp
z
Z0+1)
Q(4)
(H2)
exp
2A(WA)
u (H+)
Unfolding this expression over all rounds prior to t, obtain:
(HH) = II
(((-1)
(0) (H2) exp
61
(14)
Z
2A(WA) A)
Recall that (()) follows uniform distribution, implying ((9) (H₃) v/ Further, as W/ (H₃) = 0 and (0(0) A (H2) w (Hz + Et= (00 we have ((( (H2) = E/= (H;). As a result,
can simplify Equation 14 to:
()--))
Q(0) (H,) =
II
exp
E1 2A(WA)
(15)
Z
By Lemma C.2, we know ((++1)
d' for all l. Consequently, 20-1
2 3
21
Additionally, w (H3) upper bounded by W (H₂). Combining these two bounds and Equation 15, we have:
17')
G 22(WW))
W(HH)
2 1+
exp
(16)
2
27

---

The above expression of Q (Hy) holds for all H, including H... If we focus specifically on H..,
we know (H;,) I OPT, leading to the bound:
@ (1+) 2 + o
61
exp
OPT
(17)
2A(WA)
Because Q (H₂-) represents a probability, it is upper bounded by 1. The lower bound given in Equation is thus also upper bounded by I. We use these bounds to establish an upper bound on t:
1 2 1+ 1/) )
7/
2) 12
exp
(2A(W))
OPT
exp
2A(WA)
.PPT
1+
1+ 7//
log (n)
OPT 2 tlog
2A(WA)
log (n) + 2A(WA)
OPT
2t.
log + o
log(n)+ za(W,)) OPT log (1+ 4
Therefore, algorithm will terminate after at most
rounds.
C.3 Algorithm outputs valid hypothesis
Theorem 5. Assume o 2 8A(Wx) log (4n/3). Assume the key events hold and Algorithm / reaches Line 16 and outputs Å. Then, with probability at most B/2,, || Pllrv > 3 OPT a
Proof. If Algorithm breaks in round t, it must be that WWAND-ROMPTING---E HYMNHHESSS was unable to find a prompting hypothesis and returned L. Under the assumption that FIND-PROMPTING HYPOTHESIS succeeds, this implies that, at round f, all hypotheses had scores less than 02, implying that they were unable 02-lift more than n fraction of K. We' ve additionally assumed that the score each hypothesis reflects its promptingness. That is, the score of a hypothesis is less than 02. it is not (a2, 7) prompting. Therefore, under our assumptions, no H, E H. is (az, -rromppp..n.. Specifically, Hę- is not (02. prommppinng This guarantees that:
Pra-o wo (ft) WA (H) 2 02 <n.
(18)
We also know, by the utility guarantee of the exponential mechanism given in Lemma 1.6, that, with probability least 1 8/4, for H Q:
2A(WA)
(f(f)= S min WHH,)) + i6(n)
log (n/4,)
(19)
c1
We bound minse(") (HH,) as follows:
min W ((H+) WA(l))) max (z(li:) max ū (H+-).
(20)
xE[n]
jEin
Recall that we have assumed that the empirical semi-distance estimates are accurate up an additive factor of d1. This implies:
min W (H,) & max w (H++) < max (H,H;;)) + S H, Pllty + a = OPT + (21)
jE m
jEln]
28

---

Combining Equation 19, and Equation 21, we have, with probability at least 1 3/4, the following bound on, a (H), the proxy distance of our outputted hypothesis:
2A(WA) W S OPT + +0
log (4n/3)
(22)
E1
Because H is drawn from Q, we know, from Equation 18, that, with probability at least can bound the empirical semi-distance W; (H) as:
17, we
d;.- (ff) < WA(H) 02
(23)
Combining Equation 22 and Equation 23, we have, with probability at least 1 - (3/4 + 1)) the following bound on w.. (H):
- (f) OPT 02 2A(Wa) A)
log (4 +o.
(24)
"
By Equation 3, we have
|/ Pllrv < 20PT + w.. (H). Together with Equation 24, this yields:
H Pl[Tv & 20PT + wr- (ff
s 20PT + di. (f) + 01
2A(WA) A)
30PT + 02 +
log (4n/3) + 201
30PT + 0 + 2
30PT to.
The second-to-last inequality holds because we set 02 = 0/4,01 = o/4, and we assume > 8A(WA) log (4n/3). Recall that our algorithm sets r = 3/4. Ultimately, we have shown:
Pra
f Pllv > 3 OPT + algorithm breaks and key events occur S 7 = 3/2.
C.4 Overall correctness
We have shown, under certain constraints on s, T and k, that the probability that key events do not all hold is at most 3/2, and that, if the key events do hold and the algorithm halts before T rounds, then the probability that the algorithm outputs far hypothesis A is most 3/2.
Hence, if s, 7 and satisfy the required constraints, we can bound the probability that the algorithm outputs hypothesis f greater than (3OPT + ofaffar as:
Pr [ Plltv > OPT
Pr || PV >3 OPT + key events occur Pr key events occur]
Pr || - P| > OPT + not key events occur Pr not key events occur]
< 3/2 1+ 1-3/2
= 3.
C.5 Sample complexity
In this section, we give exact settings of s, T, and that satisfy the constraints given throughout proof of correctness.
Recall that, throughout our proof of conrectness, make the following assumptions:
29

---

1. To accurately estimate semi-distamme distances:
2 log 12m/3)
(25)
2
2. To accurately approximate prompting-ness:
h: 12 1ogg(6n7//)
(26)
7
3. For TIND-PROPTING-HHPPTHHSS to succeed:
64
(27)
2262
4. To ensure the final output has a low proxy distance:
8
o 2
E log (n)(4/33)
(28)
A(WA)
5. To bound the number of rounds the algorithm will execute:
610'
exp
(29)
2A(WA)
6. To ensure the algorithm does not halt prematurely:
T
log (1 + /2) logn n
E1
OPT)
(30)
2A(WA)
Throughout the algorithm and analysis, we also have the following parameter settings:
01 1' 02 17
8
σ'
A(W =
2
Combining these settings with our above assumptions and constraints, we have the following set of requirements for 8, T and k:
$ 2 max ( log (12n/8).
5127 log (12nT/B),
16log(2) +1) 16(KT +1)
log (4n/
02
oe
aee
aee
T 2
logn +
es 4(KT 1)
OPT
and
log
1
8 32
48
k:
log (BnT/8).
3
We claim that the following settings of 8, T. and i will satisfy these requirements:
32 96 33- 16
8
f200e
log (6n/3),
(31)
(33 16
T' = min
log (6m /3) n
(32)
96
k
log (6n/3) 3)
(33)
B
30

---

satisfies constraints As both T and & are logarithmic in the fourth argument in the constraint on will dominate. For completeness, we show that each argument of this constraint less than our choice of s.
Beginning with the first argument, have:
32 1--6--3- 16
8 2 o²
8 x²
1o2e log' (6n/B)
(log (6m/3) + log 2)
log (12n /))
For the second argument, we have:
32.96
33
16
log" (6n/3)
8200E
32
96
33 16
log (6n/3)- log (6n/3) ()
log (6n/3)
0c
B
Bo
32 967
log (6n/ (3) log (6n/3)
32 48T
(log (6n/3) + log 2) log (6n/3)
Boe
32 48T
log (12m/3) log (6n/3)
(34)
Boe
Then, because 2 T, we have the following sequence of inequalities, continued from Equation 34:
32. 24T
log (12n//3)²) log (6n/8)
8 2
Boc
347
log (12n² /3) log (6n/3) ()
Bac
32.24T
log (12nT log (6n/3)
Bac
512T
IV
log (12n1/33)
are
Note that third argument is entirely subsumed by the fourth. Therefore, for both the third and fourth argument, we have:
32
33
8
Po2e
log (6n/8)
32
96
33 16
log (6n/ B)
log (6n/3).
log (6n/3)
σe
B
Bo
32KT
log (6n/3)
σE
16(KT + 1) log( (gg(4n/3) 3))
a6 16 16log(2) +1) +1)
T. satisfies constraints We now show that our choice of T' exceeds the bound established in Theorem 4. First, observe that we can lower bound T by:
33- log(6n/B)
33
8 log n +
2
log(6n/33)
(35)
3o
3
σ
31

---

We can then expand the second term of this equation and rewrite it in terms of s, T and k. yielding:
2
33
logn n
c
96--6-3
16
log" (6n/3)
B
So
B
4
96 log (6m/3)
33 16 log (6/
33
6 +
log n
8
B
4
T
33
(log +
4kT
2
33
log 4(KT +
68
B
Applying the fact that 3 < 1 and the inequality log(1 + +x) 2 Itr
for all > -1, we can then show:
32
T 2
1
log
3
32
4(kT + 1)
32
B
1+
log
3
32
4(KT +
1 + 3/32
log
65
B/32
4(KT
+ 3/32
log
B/32
4(KT +1)
1
log n.
log (1 + B/32))
4(K7 + 1)
Finally, because OPT < 1, we know T must be greater than the number of rounds required for the algorithm to terminate.
68 OPT
T log (1 + 8/32) logn +
4(KT +
satisfies constraints Recall that T must less than n, as we do not allow any hypothesis to be added to the prompting set more than once. Then, choice of l satisfies the constraint as follows:
96
48 B
48
48
A: 3
log (6n/3)=
log ((6n/3)²)
log(6n2 /B) 2 log(6nT/3).
B
B
D Proof of Time Complexity of Algorithm 1
In this section, we prove the time complexity of Algorithm 1. Lemma D.1. Algorithm takes è (min (B n (n/B), 80 n² logllon(n//// (ng((n/))) time.
1
Proof. We walk through each step in Algorithm Recall that each semi-distance query dē (H,) takes (ss) to compute.
First, we draw samples from P. As we go through the algorithm, we estimate the semi-distances (H)) needed using these samples. We begin by setting each Wa(Hi) to be 0. The process of drawing samples and initializing proxy estimates takes (s + n) time.
The algorithm runs in at most T rounds. During single round, it performs the following actions:
1. Creates Q and draws l samples from the exponential mechanism. Computing the probability of every H; according to Q takes à (n s) time. Obtaining & samples from Q can be done in (n + k log k) time via computing the CDF and inverse sampling.
2. Invokes
(Algorithm 3). For each hypothesis H, E H. we compute its (, Computing the score involves computing the lift value of every hypothesis in K. and then sorting, which takes O(k k log k) time. No- tice that our choice of in Equation 31 dominates over our choice of log k. Therefore, FIND-PROMPTING HEW.HIINGG-HPOTHESS.S takes O(k s) time.
32

---

instead calculate 3. Updates all proxy distances (unless this is the last round). This takes O s) time.
Therefore, each round takes O(k s).
Finally, when the algorithm halts, it samples distribution from Q as output. Given there are at most T iterations, the total time spent is ( k s). Substituting the values of 8, T, and (Equations 31, 32, 33) yields the desired result.
E
Computing the Prompting Scores
The wrapper algorithm iteratively seeks a hypothesis H; E H. that can lift a significant portion of other hypotheses in H. Concretely, want characterize the following cases, when Hj is drawn from Q:
P iy (H,) - WA(H)) 2 o 2 1 vs. PT u. (H,HH) W (H(H)) 2 of < 4 (36)
Computing the exact probabilities in Equation 36 is costly, Specifically, we draw a list of hypotheses KC = j ... Hz from Q. where k is the number of samples. We compute the empirical fraction of hypotheses in K. that H; lifts significantly. If is sufficiently large, then the empirical estimate closely approximates the probability.
estimate them by sampling.
However, if we naively count the number of hypotheses in K. who have lift values above threshold o', then the result is highly sensitive: a single change in the dataset could shift every lift value from below o' to above o', thus shifting the count from 0 to To reduce sensitivity, an empirical quantile the lift values. Specifically, we use the n/2-quantile all lift values that H; induces for sampled hypotheses in K.. We call this value score, K.D (..((H)) (He,, which is approximation of the probabilities in Equation 36 and it allows us to distinguish between the two cases. In particular, if score,, K' ( H,)) is n// 4-close to the true probability, then guarantee:
If H4 can -lliftt Hy with probability at least r,, then ,., is least o'.
If H, can a' //2 -lift Hj with probability less than n/4, then score,,x,p(H.. is less than d1/2.
In Section E. we prove in Lemma E.4 that the output of Algorithm has low sensitivity with respect to changes in the imput dataset D. In Section E.2, prove that if the number of hypotheses sampled large enough, then the value of score, K, accurately approximates how often H, could lift hypotheses in H by o'.
Algorithm Compute score,,x.D(HI)
1: procedure COMPUTE-SCORE K, D)
2: T =
initialize a list to store lift values induced by H; for each H,, E K.
3:
for Hj, do
4: Append wi (H,,) w (H,,) assume query access to ih (H;)), access to W WH)))
5: Sort T in non non--nnneeeee non-increasing order
6: return T[nn/2 [X]]]]
return [n/2 [A[]]-th largest lift value
E.1 Sensitivity of the score
In the following lemmas, we compute sensitivities to support the privacy analysis of our scoring mechanism. Throughout, consider sensitivity with respect the private dataset D) all other inputs to each function are assumed to be public and fixed. Lemma E. shows that any quantile of a sorted list can change by at most the size of the individual perturbations of elements in that list. Lemma E.2 shows the sensitivity of the empirical semi-distance w; (H)) by 1/s, and Lemma E.3 shows that the sensitivity of W (H, is also 1/s. Finally, Lemma E.4 combines these results prove that the overall score function score, (H,) has sensitivity 2/s.
Lemma F. Let x [r1... In) be sorted non-incceasiie list. For all i E [n), let x/. == x; 8, where |ō < A. Sort the set (r into a non-increasing list y = [y1,..., yul. Then, for all i [m].
ly. < A.
33

---

Proof. Fix E [n]. We claim S + A. Suppose for a contradiction that > + A. Define the of indices
s [j [n] 2 > 2 }}.
Because y is ordered, there are values in y, namely V1..... yi. that must be greater than 3; + A. Therefore, there must be at least i values of such that z'3 Ia + A, so |S| 2 i. However, notice that if & 2 i, then o & S because
2 S + A S +.
Therefore, only indices < can be contained in S, which is a contradiction since there are only i such indices. The other direction yi 2 24 A is proved similarly. To verify that this bound tight, consider 8; A for all i E [n].
Lemma E.2. Let H,, H2 be two hypotheses in H. With respect to the dataset D, the sensitivity of (i(H)) is 1/8.
Proof. Notice that H, (St,) has no dependence on D. However, P(S..) can vary by at most 1/s depending on if the differing data point is in Sij. Therefore, (wú; (H2)) 1/s.
Lemma F.3. Let Hj E H and A C H. With respect to the dataset D, the sensitivity of of (H,) =
Ea (H,) is 1/s.
Proof. Notice that Wa(H,) is maximum taken over set of empirical semi-distances. Since the maximum is particular quantile, by Lemma E. and Lemma E.2, the sensitivity of (H(,,) is 1/8.
D
Lemma E.4. Fix H, E H. Let K. public list that consists of hypotheses in H. other words, consider K. to be given and fixed. With respect to the dataset D, the sensitivity of score, (H, is 2/8. Precisely,
(IsCore,,,.DHH)))
sup e Ham(D.D'==1
(soore,,x,nHH.)) score, (Hi) 2/8.
Proof. Consider the sensitivity of the lift value H; induces Hj. defined as w; (H₂) W. (H))) By Lemma E.2 and Lemma E.3, the sensitivity of each term is /,s so the sensitivity 0; -H is 2/s. s. Since Algorithm returns fixed quantile of the lift values, and each lift value has sensitivity at most 2/s, Lemma E.1 implies that score,, K. (H:) also has sensitivity 2/8.
E.2 Accuracy of the score
In the following lemma, discuss the accuracy of the score, In fact, we show that the score helps us to distinguish the two cases defined in Equation 36.
Lemma E.5. Let K. = [.i..... H be a list of hypotheses, where each Hje E K. represents an i.i.d. sample from Q k is at least
12 12gg(n/3sco)
"
then with probability at least -Bsco (taken over the randomness of H the following holds for every H; E H:
1. If H, (d', ....nnppoon proomppii with respect Q, then ,, is least o'. with respect to Q, then sc,,e,,,,n(H.) is less than
2. If H; is not (o' d2/2
Proof. Fix candidate hypothesis H; E H. For each H₁. K., indicator variable del (b(HH))) (H,, where l. E [0, 1), to determine whether H; can lift H, by at least or not.
34

---

Notice the expectation of this indicator variable evaluates to the probability that H; lifts Hj by at least t, _
P (. WA (H) 2
We set o' in case 1 and o' //2 in case 2. We estimate the probability above using the following empirical estimators, 2 and z defined as:
2
de ( W Wa(
t=1
and
2 WH, 12012
1. If H3 (d', prompting with respect to Q, then
P ih (Hz) - Wa(H,) 2 2 2n
Using Chernoff bound, we obtain
Pru;
! < Pru
27 1 (1- Eii,, - -
2
s exp (- -KEH,, ~ [,,(1Hp)
W. - (H 18)
Asco
S (-kp-kn/8) -
Therefore, with probability 2 Bsco /n. at least 11/ fraction of the hypotheses in I. can be lifted by H, by at least a'. This implies H4 is (a', // eeepeeericaalpoomppiee respect to K. This further implies that there are at least [kn/2] entries among the lift values in T that are at least o'. Therefore, the [kn/21 2] -th largest lift values must be at least o'. Thus, ,C, is at least o' as desired in the statement of the lemma.
with
2. If H; is not (a'/2, n/4 prompting with respect to Q, then
Præ w (H,) W Wa(H, 2 o' d'/2] < n/4.
Take X as a binomial random variable with parameter (k:, 1/4). Clearly, X/k: is stochasti- cally larger than ze¹/2 /2 meaning for any fix threshold r (0, 1), the probability of X/k > x is larger than the probability of 2 /2 æ. Setting x o' / attains
Prh, [
> n/2 < Prx Prxx
X > 1
X
X k
PrxxBln(kww/))
> (1 + 1)
k
kn
3sco
I cxp
12
Thus, with probability 2 Bsco fewer than / fraction of lift values exceed a'. This implies that H; is not (a', -mpppi/i-l promppiin with respect to K.. This further implies that there are less than [kn/2] entries of lift values least o'. Thus, sCore,, is less than o'.
Using union bound, we can show the above holds for all the hypotheses in H. Hence, the proof is complete.
35

---

F Finding a Prompting Hypothesis
To privately find prompting hypothesis given the scores computed in Algorithm vector technique [DR+14, LSL16). We feed a stream of scores into Algorithm 3, which privately outputs either the index of the hypothesis which was detected to have a score above So' 4 or L,, if no hypotheses have sufficiently high scores. With high probability, we can guarantee that, if the mechanism outputs i, then (c.re,,...(HI,, > z and, if the mechanism sees a hypothesis H; with score,,x.D(H.) > o', will not output 1.
the sparse
Algorithm& 3 An algorithm for privately finding prompting hypothesis
1: procedure FIND-RRMPTINN-YVOOOIISSS A, H, K. D)
2: 61
3: f2
61
4: -
Lap
5:
T 4
6:
ft p
7:
for H4 E H. do
8:
14 Lap
24
9:
score ,, H + COMPUTE-SCORE(HI K,K, D)
> Algorithm
xc. (H,, H,) + v then
11:
return H; and halt
12:
return and halt
Theorem 6 (Theorems 3.23 and 3.24 of [DR* Suppose we are given parameters c, A and o', m 1]. Assume are given two lists of hypotheses H and K. such that score,, Procedure in Algorithm 3 receives e, A, a', T,, H. K., and D its input and outputs H; 1. with e-privucy such that, with probubility least Bgvr:
has sensitivity at most A I 32 3ogr(//36r) Then the
d'eq
PROMPIING-HYPOTHERRE
1. If WOND-PROPPIING-- HYYPTHIN-HYPOTHESISS outputs H4 E H. then score, score,,,,D(H.) > E.
2. If there exists H; such that score,, > o', then HIND-PROMPTINN-HHPPOOSSS does not oulput I..
Proof overview: Theorem 6 follows from Theorems 3.23 and 3.24 in [DR+14] The privacy guarantee and the first statement of the theorem's accuracy guarantee are stated directly in [DR 14], while the second accuracy statement is the contrapositive the second statement [DR 14], Theorem 3.24.
Proof. FIND- PROMPTING---PPP HYPOTHHESS is an instance of the sparse vector technique [DR+ 14]. When A is upper bound the sensitivity of the outputs of COMPUTE-SCORE, the privacy of the algorithm holds by Theorem 3.23 in [DR* 14].
The proof of accuracy of FIND- PROMPTINGG CEEMMMIIGG-HYOOOTIO HYPOTHESIS is simple modification of Theorem 3.24 query with a score close to being above the threshold.
in [DR+144] 14], removing the requirement that the last query (or, in this case, hypothesis) is the only
Let T 3d' be the threshold of the mechanism. We want to find conditions on o' such that if 4
Algorithm outputs H;, then sc - - S. and, if Algorithm 3 outputs then for all i, score, (H, T _ a'. We will then use these conditions to establish bounds on A. Note that the second statement here the contrapositive of the second statement our theorem statement.
Observe that is sufficient to find conditions on o' such that, with probability most :SVT:
max m + lpl < 4
(37)
(E(M)
36

---

Recall that we don't 't halt at if:
score,, (H:) +1 < +P
,,
<T p 1/2
Σ + |p| + v/l
$ r + o'
by Equation 37.
Further, we do halt then:
score, H.) + + T
,,. 2 T -
p- 1/2
2 (lpl + (m/l)
2 o'
by Equation 37.
Thus, to find o' satisfying Equation 37, equivalently find conditions on a' such that:
o' 8
o'
Pr
ppl
and
Pr
max EE
2
S
8
By the properties of the Laplace distribution and the union bound, we find This results in a bound on A of:
84
log
d'c
A S 32 log (2n/ Bsvi)
37


Reviews:
[{"review_id": "ACQus5VULH", "reviewer": "Reviewer_MJur", "summary": "This paper looks at the hypothesis selection problem under the constraint of differential privacy. Hypothesis selection is a very fundamental problem in statistics which is also at the core of many distribution learning algorithms. The goal is as follows. Given a finite set of M distributions and samples from an unknown distribution, return a hypothesis which is within O(1) of the best hypothesis.\n\nSuch a problem has been studied a lot both in the private and non-private setting. It was only recently that there was a fast (i.e. near-linear time) algorithm known for the non-private setting with the optimal constant. The main result of this paper is to extend this result to the private setting. However, note that in doing so, this paper actually requires increasing the sample complexity by polylogarithmic factors. Nonetheless, this makes substantial progress in a very important problem in differentially private statistics.\n\nThe algorithm and its analysis appear to be quite nice but sophisticated. The building block is the standard Scheffe-style argument. In the Scheffe argument, one essentially tries to obtain witnesses to prove that a hypothesis is not that great (i.e. a witness to prove large TV distance). My understanding of the paper is that they start with poor witnesses. Then they try to “prompt” (the term the authors use) to find a hypothesis that increases the witness of other hypotheses. Exactly determining the hypothesis would likely violate privacy so the authors have to do this approximately. For this, they make use of the sparse vector technique which will privately find such a hypothesis. They show that the algorithm terminates when SVT fails and then one can then use the exponential mechanism using scores based on the TV distances to return a good candidate.\n\nThe analysis of the running time seems nice as well. They argue that it’s not hard to argue that it terminates in O(n) rounds but this would result in poor running time. Instead, they show that it can terminate in O(log n) rounds to get O(n log n) running time.", "questions": "No questions", "limitations": "Yes", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 4, "clarity": 4, "significance": 4, "originality": 4, "strengths_and_weaknesses": "**Strengths**\n- Fundamental problem in differentially private statistics.\n- Makes significant contribution to the literature but showing that there exists a nearly linear time algorithm for the problem with optimal constant albeit with slightly worse sample complexity than optimal.\n- Paper is written very well. It was easy to grasp the main ideas of the algorithm. The authors did an excellent job bringing me up to speed with some of the literature.\n- The techniques seem very nice. I would personally love to learn more about the paper and to talk to the authors at a poster.\n\n**Weaknesses**\n- Two minor technical downsides. First is that the sample complexity is a bit off as it incurs an additional O(log^2 n) term. Second is that the time complexity has a dependence on $\\sigma$ which does not seem ideal.\n- I do find one piece of notation a bit confusing / annoying. When they define $W(H_j) = \\max_{H_k \\in A} w_k(H_j)$, I think it would be clearer if they had $A$ in the notation of $W$ somehow. Because, as I understand, the set $A$ is built over time but the notation does not contain this. In addition (very minor), maybe make $A$ a set of indices instead so that one can write $\\max_{k \\in A} w_k(H_j)$.", "was_revised": true, "final_justification": "Overall good paper. While a lot of the paper is still based on ABS, making the algorithm private seems to still be non-trivial.\n\nI listed some minor technical downsides but these are more for potential follow up work.", "rebuttal": "Thank you for your thoughtful review and feedback. \n\nWe address your comments below.\n\n---\n\n### **Polylogarithmic Sample Complexity (Weakness 1)**\n\n> Two minor technical downsides. First is that the sample complexity is a bit off as it incurs an additional $O(\\log^2 n)$ term.\n\nWe agree that the gap between our $\\operatorname{polylog}(n)$ sample complexity and the non-private $\\log(n)$ is an important point.\n\nOur primary contribution is introducing a new stable, private minimum distance estimator that avoids direct comparisons (as in prior tournament-style algorithms) while obtaining a near-linear time private algorithm. To obtain the desired time complexity, our algorithm must *not* make very many wasteful queries, and it must adaptively choose the next hypothesis to query depending on previous outcomes.\n\nUnfortunately, this adaptivity is challenging to privatize because, in principle, the decision of which hypothesis to choose makes the algorithm very sensitive. Thus, we have to make every step private. The additional $\\log^2(n)$ factors are a natural byproduct of reconciling the inherent adaptivity of the algorithm with the need for privacy.\n\nWhether these $\\operatorname{polylog}$ factors are a necessary price to pay to achieve near-linear time complexity is an interesting open direction. We hope our result paves the way for more progress on this topic.\n\n\n> Second is that the time complexity has a dependence on $1/\\sigma$ which does not seem ideal\n\nWith respect to $\\sigma$, our bound matches those of the $\\alpha=3$ non-private algorithm in [ABS24]. While improving these dependencies is a valuable direction for future work (even in the non-private case), our result does not exacerbate these known challenges.\n\n### **Notation (Weakness 2)**\n\n> I do find one piece of notation a bit confusing / annoying. When they define $W(H_j) = \\max_{H_k \\in A}w_k(H_j)$, I think it would be clearer if they had $A$\n in the notation of $W$ somehow. Because, as I understand, the set $A$ is built over time but the notation does not contain this. In addition (very minor), maybe make $A$ a set of indices instead so that one can write $\\max_{k \\in A}w_k(H_j)$.\n \nThank you for suggesting a better notation for semi-distances. The notations in our papers were intended to follow the same patterns in previous works like [ABS24] to maintain consistency. However, we will adopt a more clear notation in the final draft.\n\n---\n\n### **References**\n\n[ABS24] Maryam Aliakbarpour, Mark Bun, and Adam Smith. Optimal hypothesis selection in (almost) linear time. NeurIPS, 2024."}, {"review_id": "KpMaMv4M4R", "reviewer": "Reviewer_TVoF", "summary": "This paper studies the problem of hypothesis selection under differential privacy: Given a set of \"hypotheses\" (distributions) $\\\\mathcal{H} = \\\\{H\\_1, H\\_2, \\\\ldots, H\\_n\\\\}$, and sample access to a distribution $P$, the goal is to return a hypothesis $H \\\\in \\\\mathcal{H}$ that minimizes the total variation distance to $P$, namely $\\\\|H - P\\\\|\\_{\\\\mathrm{TV}}$. Moreover it is required that the algorithm satisfies $\\\\varepsilon$-differential privacy with respect to the samples from $P$.\n\nThere are three parameters of interest:\n* Approximation ratio $\\\\alpha$: The return $H$ should satisfy $\\\\|H - P\\\\|\\_{\\\\mathrm{TV}} \\\\le \\\\alpha \\cdot \\\\|H^* - P\\\\|\\_{\\\\mathrm{TV}} + \\\\sigma$, where $\\\\sigma$ is an additive error. Even without DP requirement, it is known that $\\\\alpha = 3$ is the best possible approximation ratio.\n* Running time of the algorithm: Recent work has obtained a linear time (in $n$, the number of hypotheses).\n* Sample complexity of the algorithm.\n\nPreviously, $O(\\\\log n)$ sample complexity has been obtained with DP constraint and for approximation ratio $\\\\alpha = 3$ (which is the best possible). However, the running time of that algorithm is quadratic in $n$.\n\nThe main result of the paper is to provide an algorithm that achieves nearly linear running time in $n$, approximation ratio $\\\\alpha = 3$, although with slightly larger $O(\\\\log^3 n)$ sample complexity.", "questions": "### Comments\n\n* (Page 4: Table 1) It wasn't clear until much later what $s$ means in Table 1. (I understood later that it is the number of samples, which is basically the same as the last column. This could perhaps be made clear by having the last column header as \"_Sample Complexity ($s$)_\".\n* (Page 5): It might be better to write $w\\_i(H\\_j)$ as $w\\_i(H\\_j; P)$ to emphasize that it is a notion of distance from $P$. Similarly, $\\\\tilde{W}(H\\_j)$ could be $\\\\tilde{W}\\_A(H\\_j; P)$. I found it very confusing to keep track of what depends on what... (I understand that in Algorithm 1 $\\\\tilde{W}(H\\_j)$ is used to denote a \"variable\", but perhaps some other notation could be used for that?)\n* (Page 5): In the definition of _lift value_, I suppose it should be required that $i \\\\notin A$, but this is not specified.", "limitations": "The paper sufficiently discusses limitations and outlines open directions for future work.\n\nI don't have any concerns about potential negative societal impacts of this work.", "rating": 5, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "### Strengths\nThe paper makes important progress on the problem of private hypothesis selection, providing a linear time algorithm, while also obtaining the optimal approximation ratio of $\\\\alpha = 3$ and polylogarithmic sample complexity.\n\n### Weaknesses\nThe contributions _might_ be incremental over the work of [[ABS24](https://proceedings.neurips.cc/paper_files/paper/2024/file/ffee3090eac0aae698b2d77ac5642c2c-Paper-Conference.pdf)]. The algorithm seems to follow a similar outline with key steps replaced with privatized versions of the same, although with clever use of the exponential mechanism and the sparse vector technique (so I am not certain about my \"incremental\" claim).\n\nI felt that notations are a bit cumbersome and oversimplified, making it hard to follow (see comments under \"Questions\" below).\nThis also made the paper quite dense to follow (after Page 7 onwards) and relies on a fair bit of context that is only present in the Appendix.\n\nThe proofs in the paper look correct to me (the privacy proof is immediate from basic composition of exponential mechanism and sparse vector technique). But since I found the paper to be very dense and I was familiar with the prior work, I haven't been able to follow everything in detail.", "was_revised": true, "final_justification": "I had a good opinion of the paper to being with and was supportive of acceptance. My only concern was that there might be too many similarities with [ABS24], however after author's response, I feel there is sufficient novelty in the paper. So I will maintain my rating and support acceptance.", "rebuttal": "Thank you for the comments and detailed suggestions for improving the paper's notation. We will incorporate them into the final version. \n\n---\n\n### **Major Differences Compared to [ABS24]**\n\n> The contributions *might* be incremental over the work of [ABS24]. The algorithm seems to follow a similar outline with key steps replaced with privatized versions of the same, although with clever use of the exponential mechanism and the sparse vector technique (so I am not certain about my \"incremental\" claim)\n\nWe appreciate the reviewer's observation and acknowledge that the structure of our algorithm is indeed closely aligned to that of [ABS24]. However, we note that other nearly-linear algorithms for hypothesis selection (e.g., [AJOS14, AFJ+18]) are tournament-based and require many pairwise comparisons. Such comparisons are highly sensitive and therefore difficult to privatize. We chose to design a private algorithm based on the structure of [ABS24] to avoid these direct comparisons. \n\nNevertheless, despite not following a tournament-based structure, many components of [ABS24]’s algorithm are highly sensitive—particularly its bucketing scheme. In our private algorithm, we replace this bucketing scheme with an exponential mechanism, $Q$, that skews towards sampling hypotheses with low proxy distances. Instead of choosing a prompting hypothesis based on its ability to lift many hypotheses in a bucket, we choose a prompting hypothesis based on its ability to lift hypotheses with a large probability mass under the exponential mechanism. As a result, we can only guarantee that, for each selected prompting hypothesis, only the proxy distances of a few (or even one) hypothesis will increase. Both our algorithm and [ABS24] require $O(n)$ time to identify each prompting hypothesis. While [ABS24] prove that their algorithm terminates in near-linear time by showing that only $O(\\log n)$ prompting hypotheses can be identified at each bucket, we need a clever way of monitoring the progress of the algorithm to ensure that our algorithm similarly ends after finding $O(\\log n)$ prompting hypotheses. This is the most significant challenge that we overcome, in Section D.2.\n\n\n\n### **Notation**\n\n> (Page 4: Table 1) It wasn't clear until much later what $s$ means in Table 1. (I understood later that it is the number of samples, which is basically the same as the last column. This could perhaps be made clear by having the last column header as \"Sample Complexity ($s$)\".\n\nThank you for pointing this out. We will fix this issue in the final draft.\n\n> (Page 5): It might be better to write $w_i(H_j)$ as $w_i(H_j; P)$ to emphasize that it is a notion of distance from $P$. Similarly, $\\tilde{W}(H_j)$ could be $\\tilde{W}_{A}(H_j; P)$. I found it very confusing to keep track of what depends on what... (I understand that in Algorithm 1 $\\tilde{W}(H_j)$ is used to denote a \"variable\", but perhaps some other notation could be used for that?)\n\nThank you for suggesting a better notation for semi-distances and proxy distances. In terms of notations: $w_i(H_j)$ refers to the value of true semi-distances and $\\hat{w_i}(H_j)$ refers to the estimated semi-distances. $\\tilde{W}(H_j)$ refers to proxy distances, defined as $\\max_{H_i \\in A}\\hat{w}_i(H_j)$, where $A$ is an ever-growing set of hypotheses during execution of algorithm 1. These notations were intended to follow the same patterns in previous works like [ABS24] to maintain consistency. However, we will adopt a more clear notation in the final draft.\n\n> (Page 5): In the definition of lift value, I suppose it should be required that $i \\not \\in A$, but this is not specified.\n\nAs you stated, for hypotheses $H_i$ and $H_j$, where $H_i$ is already in $A$, we have that $\\tilde{W}(H_j) := \\max_{H_i \\in A}\\hat{w}_i(H_j)$ is greater than or equal to $\\hat{w}_i(H_j)$. Hence, the hypotheses that are already in $A$ are not going to lift any hypotheses. Therefore, we exclude these hypotheses when we are searching for a prompting hypothesis as stated in line 13 of Algorithm 1. We will consider explicitly stating this requirement on page 5 to improve clarity. \n\n---\n\n### **References**\n\n[ABS24] Maryam Aliakbarpour, Mark Bun, and Adam Smith. Optimal hypothesis selection in (almost) linear time. NeurIPS, 2024.\n\n[AFJ+18] Jayadev Acharya, Moein Falahatgar, Ashkan Jafarpour, Alon Orlitsky, and Ananda Theertha Suresh. Maximum selection and sorting with adversarial comparators. The Journal of Machine Learning Research, 2018.\n\n[AJOS14] Jayadev Acharya, Ashkan Jafarpour, Alon Orlitsky, and Ananda Theertha Suresh. Sorting with adversarial comparators and application to density estimation. IEEE International Symposium on Information Theory, 2014."}, {"review_id": "DcFHCUp0DC", "reviewer": "Reviewer_5ALS", "summary": "This work investigates the hypothesis selection problem under differential privacy. Given a list of $n$ hypotheses (candidate distributions), the objective is to select one that approximates the unknown underlying distribution while preserving data privacy. In this paper, the authors propose an algorithm that achieves an optimal (even without privacy) approximation factor $\\alpha = 3$ with nearly-linear runtime $\\tilde{O}(n)$. This improves existing algorithms in prior work, which typically run in at least quadratic time. Notably, the sample complexity of the proposed method scales poly-logarithmically in $n$, which is only a mild increase compared to the non-private results.", "questions": "1. The time complexity of the proposed algorithm includes a $1/\\sigma$ factor while previous methods do not. Is it possible to eliminate this dependence via allowing a larger approximation factor $\\alpha$ like in [ABS24]?\n2. I find the notations $W(H_j)$ and $\\tilde{W}(H_j)$ somewhat confusing. They seem to be defined w.r.t. the actual distribution $P$, whereas in many places they should represent the distance w.r.t. the empirical distribution $\\hat{P}$ (e.g., in Algorithm 1 and its analysis, particularly in Theorem 4). Could you clarify their precise definitions?\n3. The authors apply the SVT in Algorithm 3 to privately identify a prompting hypothesis with a high score. I wonder why not directly invoke a report-noisy-max mechanism, which yields a much simpler analysis.\n4. In Lemma F.3, should $w_k(H_i)$ be $\\hat{w}_k(H_i)$?\n5. Should the $\\sigma'$ in the second statement in Lemma F.5 be replaced by $\\sigma' / 2$ (for consistency with Line 640 and 641)? Additionally, the $H_j$ in the proof should be $H_{j_\\ell}$ and $t$ should be $k = \\lvert\\mathcal{K}\\rvert$.", "limitations": "yes", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 4, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths:\n\n1. This work introduces a nearly-linear time algorithm for private hypothesis selection, significantly improving the runtime compared to prior methods. \n2. The proposed algorithm achieves an approximation ratio of $\\alpha = 3$, which is known to be optimal even without privacy. Moreover, it results in a sample complexity of only $\\mathrm{polylog}(n)$.\n3. The article is well-organized and the writing is clear and concise.\n\nWeakness:\n\n1. While the algorithm incurs a sample complexity of only $\\mathrm{polylog}(n)$, non-private algorithms require only $O(\\log n)$ samples, indicating a notable drawback.\n2. The dependence on the confidence $\\beta$ and additive error $\\sigma$ in the sample complexity and time complexity bounds is greater than other algorithms (with worse $\\alpha$ or runtime). This may become a serious issue if one aims for a high success probability or a small additive error.\n3. It seems the algorithm is a simple extension of [ABS24]'s with standard techniques from differential privacy. The only thing I find interesting is analyzing the evolution of the exponential mechanism (Lemma D.2).", "was_revised": true, "final_justification": "While I'm uncertain about the significance of the main technical contribution, the paper does propose an algorithm for the private hypothesis selection problem with an optimal approximation ratio. Also, the utility bounds match the state-of-the-art non-private algorithm.", "rebuttal": "We thank the reviewer for their detailed feedback and constructive comments. We address the concerns and questions below.\n\n---\n\n### **Polylogarithmic Sample Complexity (Weakness 1)**\n\n> While the algorithm incurs a sample complexity of only $\\operatorname{polylog}(n)$, non-private algorithms require only samples $\\log(n)$, indicating a notable drawback.\n\nWe agree that the gap between our $\\operatorname{polylog}(n)$ sample complexity and the non-private $\\log(n)$ is an important point.\n\nOur primary contribution is introducing a new stable, private minimum distance estimator that avoids direct comparisons (as in prior tournament-style algorithms) while obtaining a near-linear time private algorithm. To obtain the desired time complexity, our algorithm must *not* make very many wasteful queries, and it must adaptively choose the next hypothesis to query depending on previous outcomes.\n\nUnfortunately, this adaptivity is challenging to privatize because, in principle, the decision of which hypothesis to choose makes the algorithm very sensitive. Thus, we have to make every step private. The additional $\\log^2(n)$ factors are a natural byproduct of reconciling the inherent adaptivity of the algorithm with the need for privacy.\n\nWhether these $\\operatorname{polylog}$ factors are a necessary price to pay to achieve near-linear time complexity is an interesting open direction. We hope our result paves the way for more progress on this topic.\n\n### **Dependence on** $\\beta$ **and** $\\sigma$ **(Weakness 2)**\n\n> The dependence on the confidence and additive error in the sample complexity and time complexity bounds is greater than other algorithms (with worse or runtime). This may become a serious issue if one aims for a high success probability or a small additive error.\n\nWe acknowledge that an ideal algorithm should have a sample complexity and time complexity with respect to $\\beta$ of $O(\\log(1/β))$, which our current algorithm does not achieve. Specifically, our algorithm has an additional $1/\\beta^2$ in the sample complexity as well as a $1/\\beta^4$ in the time complexity.\n\nEven in the non-private case, this $\\beta$ dependence is difficult to control with algorithms that obtain $\\alpha < 9$, largely because there is no known \"amplification process\" for hypothesis selection that preserves the approximation factor $\\alpha$, as opposed to many learning theory problems. See Lines 123-130 for more details.\n\nFor example, the first algorithm of [ABS24] ($\\alpha = 3$) obtains a time complexity of $1/\\beta^3$. The random ladder tournament in [ABS23] incurs a factor of $1/\\beta$ in the sample complexity while obtaining $\\alpha = 5$. Despite this dependence on $\\beta$, we believe our result is an important step forward as the first nearly-linear time algorithm for private hypothesis selection that obtains the optimal $\\alpha$.\n\nIt is important to note that if we relax the requirement for $\\alpha$ and allowing for a worse approximation factor, this dependence on $\\beta$ may be improved. The second algorithm of [ABS24] ($\\alpha = 4$) obtains a time complexity without polynomial dependence on $1/\\beta$, and it is the only near-linear time algorithm with $\\alpha < 9$. We did not focus on this algorithm due to the sub-optimality of its approximation factor. It remains an open question whether privatizing this algorithm would lead to a better dependence on $\\beta$ (and $\\sigma$, as the reviewer suggests in question 1).\n\nWith respect to $\\sigma$, our bound matches those of the $\\alpha=3$ non-private algorithm in [ABS24]. While improving these dependencies is a valuable direction for future work (even in the non-private case), our result does not exacerbate these known challenges.\n\n### **Major Differences Compared to [ABS24] (Weakness 3)**\n> It seems the algorithm is a simple extension of [ABS24]'s with standard techniques from differential privacy. The only thing I find interesting is analyzing the evolution of the exponential mechanism (Lemma D.2).\n\nWe appreciate the reviewer's observation and acknowledge that the structure of our algorithm is indeed closely aligned to that of [ABS24]. However, we note that other nearly-linear algorithms for hypothesis selection (e.g., [AJOS14, AFJ+18]) are tournament-based and require many pairwise comparisons. Such comparisons are highly sensitive and therefore difficult to privatize. We chose to design a private algorithm based on the structure of [ABS24] to avoid these direct comparisons. \n\nNevertheless, despite not following a tournament-based structure, many components of [ABS24]’s algorithm are highly sensitive—particularly its bucketing scheme. In our private algorithm, we replace this bucketing scheme with an exponential mechanism, $Q$, that skews towards sampling hypotheses with low proxy distances. Instead of choosing a prompting hypothesis based on its ability to lift many hypotheses in a bucket, we choose a prompting hypothesis based on its ability to lift hypotheses with a large probability mass under the exponential mechanism. As a result, we can only guarantee that, for each selected prompting hypothesis, only the proxy distances of a few (or even one) hypothesis will increase. Both our algorithm and [ABS24] require $O(n)$ time to identify each prompting hypothesis. While [ABS24] prove that their algorithm terminates in near-linear time by showing that only $O(\\log n)$ prompting hypotheses can be identified at each bucket, we need a clever way of monitoring the progress of the algorithm to ensure that our algorithm similarly ends after finding $O(\\log n)$ prompting hypotheses. This is the most significant challenge that we overcome, in Section D.2.\n\n### **Factor of $1/\\sigma$ (Question 1)**\n\n> The time complexity of the proposed algorithm includes a $1/\\sigma$ factor while previous methods do not. Is it possible to eliminate this dependence via allowing a larger approximation factor like in [ABS24]?\n\nThis is a great question for future work. We believe it is feasible to privatize the second algorithm in [ABS24] with $\\alpha = 4$. However, we did not focus on this algorithm because of its sub-optimal approximation factor. \n\n### **Notation (Question 2)**\n\n> I find the notations $W(H_j)$ and $\\tilde{W}(H_j)$ somewhat confusing. They seem to be defined w.r.t. the actual distribution $P$, whereas in many places they should represent the distance w.r.t. the empirical distribution (e.g., in Algorithm 1 and its analysis, particularly in Theorem 4). Could you clarify their precise definitions?\n\nThank you for pointing this out. Both the semi-distance $w_i(H_j)$ and the maximum semi-distance $W(H_j) := \\max_{H_i \\in \\mathcal{H}}w_i(H_j)$ are defined with respect to the actual distribution $P$. On Line 189, $\\tilde{W}(H_j)$ is erroneously defined as $\\max_{H_i \\in A} w_i(H_j)$. This will be corrected to $\\max_{H_i \\in A} \\hat{w}_i(H_j)$ in the revision. Throughout the rest of our paper, each $\\hat{w}_i(H_j)$ is an \"empirical approximation\" of ${w}_i(H_j)$ and is computed empirically from samples of $P$, as in Algorithm 1 and Theorem 4. \n\n### **Using Report-Noisy-Max (Question 3)**\n> The authors apply the SVT in Algorithm 3 to privately identify a prompting hypothesis with a high score. I wonder why not directly invoke a report-noisy-max mechanism, which yields a much simpler analysis\n\nThank you for your suggestion. In our analysis, we need each call to Find-Prompting-Hypothesis to satisfy two criteria in order for the algorithm to succeed: first, if we return a hypothesis, that hypothesis must have a sufficiently high score; and second, if we don't return any hypothesis, then all hypotheses must have sufficiently low scores. We apply SVT as a off-the-shelf procedure that gives these guarantees, as proven with only a very simple modification to existing results [DR+14]. If report-noisy-max also satisfies Theorem 6—which we believe it would, provided that we take care of the case where the maximum score is below our threshold—you are correct to assert that it could take the place of SVT in our algorithm. With this additional case, this would also be a simple modification of the existing result in the literature.\n\n### **Typos (Questions 4 and 5)**\n\n> In Lemma F.3, should $w_k(H_i)$ be $\\hat{w}_k(H_i)$?\n\n> Should the $\\sigma'$ in the second statement in Lemma F.5 be replaced by $\\frac{\\sigma'}{2}$ (for consistency with Line 640 and 641)? Additionally, the $H_j$ in the proof should be $H_{j_{l}}$ and $t$ should be $k = |K|$\n\nThank you for pointing out these typos—we appreciate your close attention to details. We will revise the notation in Lemmas F.3 and F.5 accordingly.\n\n---\n\n### **References**\n\n[ABS23] Maryam Aliakbarpour, Mark Bun, and Adam Smith. Hypothesis selection with memory constraints, NeurIPS, 2023.\n\n[ABS24] Maryam Aliakbarpour, Mark Bun, and Adam Smith. Optimal hypothesis selection in (almost) linear time. NeurIPS, 2024.\n\n[AFJ+18] Jayadev Acharya, Moein Falahatgar, Ashkan Jafarpour, Alon Orlitsky, and Ananda Theertha Suresh. Maximum selection and sorting with adversarial comparators. The Journal of Machine Learning Research, 2018.\n\n[AJOS14] Jayadev Acharya, Ashkan Jafarpour, Alon Orlitsky, and Ananda Theertha Suresh. Sorting with adversarial comparators and application to density estimation. IEEE International Symposium on Information Theory, 2014.\n\n[DR+14] Cynthia Dwork, and Aaron Roth. The algorithmic foundations of differential privacy. Foundations and Trends in Theoretical Computer Science, 2014."}]

Author rebuttal:

Meta-review: This paper studies a basic task in statistics, known as hypothesis selection, in the differentially private setting. This task has been extensively studied in the standard (non-private setting), where it is almost fully understood---both in terms of sample complexity and computational complexity. The main result of this work is an algorithm that solves this problem in the presence of privacy, with qualitatively near-optimal guarantees. The reviewers agreed that the contribution merits acceptance.
Decision: Accept (poster)