Optimal Hypothesis Selection in (Almost) Linear Time
Authors: Maryam Aliakbarpour
Mark Bun
Adam Smith
Venue: NeurIPS 2024 poster (2024)
Keywords: hypothesis selection
distribution learning
density estimation
time efficient algorithms
computational constraints
Primary area: learning_theory
TL;DR: We introduce the first near-linear-time algorithm for hypothesis selection that achieves optimal accuracy, significantly advancing previous methods.

Abstract: Hypothesis selection, also known as density estimation, is a fundamental problem in statistics and learning theory. Suppose we are given a sample set from an unknown distribution $P$ and a finite class of candidate distributions (called hypotheses) $\mathcal{H} \coloneqq \{H_1, H_2, \ldots, H_n\}$. The aim is to design an algorithm that selects a distribution $\hat H$ in  $\mathcal{H}$ that best fits the data. The algorithm's accuracy is measured based on the distance between $\hat{H}$ and $P$ compared to the distance of the closest distribution in $\mathcal{H}$ to $P$ (denoted by $OPT$). Concretely, we aim for $\|\hat{H} - P\|_{TV}$ to be at most $ \alpha \cdot OPT + \epsilon$ for some small $\epsilon$ and $\alpha$. 
While it is possible to decrease the value of $\epsilon$ as the number of samples increases, $\alpha$ is an inherent characteristic of the algorithm. In fact, one cannot hope to achieve $\alpha < 3$ even when there are only two candidate hypotheses, unless the number of samples is proportional to the domain size of $P$ [Bousquet, Kane, Moran '19]. Finding the best $\alpha$ has been one of the main focuses of studies of the problem since early work of [Devroye, Lugosi '01]. Prior to our work, no algorithm was known that achieves $\alpha = 3$ in near-linear time. We provide the first algorithm that operates in almost linear time ($\tilde{O}(n/\epsilon^3)$ time) and achieves $\alpha = 3$.  This result improves upon a long list of results in hypothesis selection. Previously known algorithms either had worse time complexity, a larger factor  $\alpha$, or extra assumptions about the problem setting.
In addition to this algorithm, we provide another (almost) linear-time algorithm with better dependency on the additive accuracy parameter $\epsilon$, albeit with a slightly worse accuracy parameter, $\alpha = 4$.

Optimal Hypothesis Selection in (Almost) Linear Time
Maryam Aliakbarpour Department of Computer Science Rice University Houston, TX 77005
Mark Bun Department Computer Science Boston University Boston, MA 02215 mbun@bu. edu
maryamaerice.cm edu
Adam Smith
Department of Computer Science
Boston University Boston, MA 02215
ads22@bu. edu
Abstract
Hypothesis selection, also known as density estimation, is fundamental problem in statistics and learning theory. Given a sample set from an unknown distribution P and finite class of candidate distributions (hypotheses) H. : H1, H2, ..... Hn the goal is to design an algorithm that selects distribution H from H that best describes P. The accuracy of the algorithm is measured by the distance between H and P. compared to the distance between the closest distribution in H. and P (denoted by OPT). Specifically, we aim for || P [TV to be at most a OPT + for some small and a.
While the value of can be reduced with an increasing number of samples, is an inherent characteristic of the algorithm. Achieving a < 3 is impossible, even with only two candidate hypotheses, unless the number of samples is proportional to the domain size of P [Bousquet, Kane, Moran "19]. Finding computationally efficient algorithm that achieves the optimal a has been a primary focus of research since the early work of [Devroye, Lugosi 'O1]. Before achieving a required time Q(n²). We present the first algorithm that operates in almost linear time (Ö(n/c²) and achieves a 3. This result improves upon long line of hypothesis selection research. Previously known algorithms had either worse time complexity. a larger factor, or additional assumptions about the problem setting. Additionally, we provide another (almost) linear-time algorithm with better dependency on the additive accuracy parameter e, albeit with a slightly worse accuracy parameter of 4.
work, the algorithms
Introduction
Hypothesis selection, also known density estimation, is fundamental problem in statistics and learning theory. This problem involves identifying a density function that accurately represents the distribution of given dataset. Suppose unknown distribution P and finite class of known distributions, representing different hypotheses: H = (Hi, H2,.................. .., H. The goal select distribution H that close to in total variation (TV) distance.
given dataset of samples drawn from an
Typically, learning distribution domain X' with an error in TV distance requires 2 (((x'l/e)) samples, which presents a substantial lower bound in sample complexity for distributions over large
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

domains. Surprisingly, the findings of Yatracos. Devroye, and Lugosi revealed that for hypothesis selection, this sample complexity can be independent of the domain size and only logarithmic in the number of hypotheses [Yat85, DI.96, DI.97. With just 8 == (llog nn/e²) samples from P. it possible to learn P within error a OPT + 6, where OPT denotes the distance of the nearest distribution in H to P. Specifically, Devroye and Lugosi introduced two algorithms for this problem: the Scheffé tournament, which operates On s) time' and achieves a = 9; and the minimum distance estimate, which runs in O(n" s) time and achieves a 3 [DL01, Chapter 6]. In these results, although e can be decreased as the number of samples increases, a remains an inherent parameter of the algorithm.
Significant effort has been directed towards finding computationally efficient algorithms for this problem while maintaining sample efficiency. The trade-off between the accuracy parameter a and computational efficiency has been a focal point. Mahalanabis and Stefankovie in [MS08] enhanced the minimum distance estimate, improving the time complexity to ( They also introduced a nearly linear-time algorithm that achieves a = 3, but requires exponential time in n for preprocessing the class H. Other nearly linear-time algorithms were developed achieving in [AJOS14, AFJ+ 18, AAC+ and a in [ABS23]. Furthermore, linear-time algorithms have been presented under the assumption that the algorithm receives the value of OPT (or its upper bound) as input [DK14, ABS23]. However, achieving a < 3 is not possible unless the number of samples becomes poly( as indicated in [BKM19]]
9
Despite the Long-standing history of this problem, the following question remained open:
Is there an algorithm for hypothesis selection with the optimal number of samples & (log(n)/e²) and optimal accuracy parameter
that runs in On 8) time?
We present the first almost linear-time time algorithm that uses the optimal number of samples and achieves the optimal accuracy parameter a = 3. Our algorithm runs in Ö(n 8 time (see Theorem 2). Additionally, we introduce another algorithm with improved dependency on e, running in Ö(n s) time while obtaining a slightly higher accuracy parameter, represent a significant step forward, as they are the first in decades to achieve time complexity linear in n for any a 5. See Table 1.
(see Theorem 3). Our results
Applications of Hypothesis Selection The primary application of hypothesis selection is to identify the best distribution from a set of known models that represent potential underlying data distributions we can effectively manage. For example, this set might include Poisson, gamma, and binomial distributions with various parameters used to model the number of arrivals per time unit. This makes hypothesis selection applicable to tasks like interpretable distribution selection and strategy optimization, where the objective is choose the most suitable model from available options.
Another key strength of hypothesis selection is its agnostic nature, allowing to adapt even when the true distribution lies outside the considered class. This robustness makes it effective in noisy data settings, with applications in denoising and anomaly detection. From a theoretical standpoint, hypothesis selection is fundamental in learning structured distributions, particularly when combined with the cover method, as seen in learning mixtures of Gaussians [DK14, SOAJ14]. For additional references, see Section 1.3.
Importance of improving a by a constant factor In most learning algorithms, the error guarantee decreases polynomially as the number of samples increases, so constant factors may not be as crucial. However, this is not the case in hypothesis selection. The output hypothesis is guaranteed to be (a OPT + c)-close to P in total variation distance. While increasing the number of samples can reduce to negligible levels, does not improve the term a OPT. Hence, a is an inherent property of the algorithm and directly impacts the best achievable error guarantee. Therefore, even constant improvement a is significant.
One might argue that, alternatively, OPT could be reduced by carefully curating the class H. However, beyond the practical challenges of finding a better H. it is unclear whether this can be achieved
'This time bound assumes constant-time comparisons of the H, 's density functions. See Section 1.1. 'Theorem 4.1 in [AAC 23] states the result for a = 27. However, according to personal correspondence with the authors, it is possible to modify their algorithu in conjunction with the minimum distance estimate and improve 9.

---

without significantly increasing the size of the hypothesis class H. For example, in the cover method, when aiming learn a distribution within class C, we set H. to be a y-nnt that serves as cover for C, ensuring that OPT < 7 While using finer 7-net can reduce OPT, it may also drastically increase the size of H. thereby increasing the algorithm's 's running time, since the size of the net can grow super-po super-polynomially with respect to For instance, in the case of mixtures of & Gaussians, the size of the net depends on y as roughly O(> (see [SOAJ14]). Thus, reducing y by a factor of three could exponentially increase the size of H. in terms of k. thereby increasing both the running time and sample complexity, ultimately resulting in an inefficient algorithm.
Table 1: Summary of Past Results in Hypothesis Selection. All algorithms use s (loogn/e samples.
Result
α
Time Complexity
Additional requirement
Min distance estimate [DL01]
3
O(
Scheffé tournament [DL01]
9
O(n²
Min distance estimate [MS08]
3
O .)
[AJOS14, AFJ+18] 18]
9
Ö(n .s)
[ABS23]
5
Ö(n ss)
[AAC*23]
9
O s/ logn)
[MS08]
3
O(n
Exponential time preprocessing
[DK14, ABS23]
Ö(n s)
Assume knowledge of OPT
Lower bound [BKM19]
Achieving < 3 requires poly([X')) samples
This work:Algorrthm
3
Ö(n.s) (/c)
This work: Algorithm 4
4
Ô (n
1.1 Problem Setup
Suppose have an unknown distribution P over domain X' and a of known distributions H = H1. Hz..... Hn}. Let OPT denote the distance between P and the closest distribution to it in H 9 OPT(H, P) == min || Plltv. We use the standard access model for this problem as introduced in [DL01]. The algorithm accesses the distributions through the following types of queries:
1. The algorithm can request a sample from the unknown distribution P.
2. The algorithm can compare the PDF two known distributions: For every domain element x E X and every pair of indices and j. it can ask if Hz Hz(()). This is equivalent to asking if x is in the Scheffé set of H; and H₃ (defined in Equation (2)).
3. The algorithm can query the probability mass of the Scheffé sets according to all the known distributions.
Remark 1. The last requirement of our model can be relaxed. Only estimates of the probability masses of the Scheffé sets are needed for our algorithms. Thus, one can alternatively assume sample access to H₃ ss, and estimate these values via samples.
Definition 1.1 (Proper learner for hypothesis selection). Suppose algorithm A is given parameters 8 E (0, 1), a E Ry0 and has access to an unknown distribution P and a class of n known distributions H. (as described above). We say A is an 6)8-properr learner for the hypothesis
selection problem if for every P and H. A ouiputs H H. for which, with probability at least 1 8,
| - Pl[rv S a OPT(H, P) +e.
(1)
We omit the arguments (H, P) when they clear from the context.
3

---

We refer to a as the accuracy parameter, e as the error (or proximity) parameter, and as the confidence parameter of the algorithm.
1.2 Main theorems
Below, we provide informal versions of our theorems.
Theorem 2. For every e, ô E (0, 1), Algorithm is an (a = 3, d)-rope learner for hypothesis samples and time Ö(n (6) = (6n)(5'=)),
selection that uses + = (log(n/6))
Theorem 3. For every e, 6 E (0, 1), Algorithm 4 is an (a= ( 4, 6) proper learner for hypothesis selection that uses s = (1 (/) samples and time Önn-s s (2/g) = OOn-(((n)))) (1)5)/²1)
For formal statements, see Theorem (Appendix A) and Corollary B.1 (Appendix B).
Our results are the first to achieve time complexity linear in n for any a < 5. To achieve this, we introduce novel algorithmic techniques that will hopefully be broadly useful-see Section 3 for overview. Both algorithms use the optimal number of samples. The first algorithm obtains optimal accuracy parameter o = 3 with a time complexity of ((n/(0² e). s), which is off by an O(1/(5$ )) factor. Our second algorithm achieves the optimal time complexity up logarithmic factors while achieving slightly higher a = 4. Our results leave a fascinating open question: Can one combine the best aspects of both algorithms, maintaining a achieving O(n s) time (or even lower), and sample complexity = ([[loo((//)/e"))
Remark 4. Readers may be surprised by the polynomial dependence on 166 in Theorem 2. In many settings, the success probability of a learning algorithm can be amplified from constant, say 2/3, to at least 1- at a cost of at most log(1/8) in running time and sample complexity. However, in hypothesis selection, there is no (known) general technique for boosting the confidence parameter while keeping a the same. The issue is that choosing the best oulput from several runs of given algorithm requires executing second hypothesis selection algorithm, which introduces another factor of a in the approximation leadin to total factor of at least 9. As a result, these kinds of two-phase algorithms are not sufficient in the low a regime. Some previous results, such as [ABS23]. also suffer from a polynomial dependency on 8.
1.3 Other related work
Hypothesis selection has been studied in various settings including improper setting. In [BKM19], the authors consider the improper version of the problem where the output hypothesis H may not necessarily be in H. They presented an improper learner with accuracy guarantee sample complexity of their algorithm was improved by [BBK who gave an algorithm with nearly optimal sample complexity and the same accuracy parameter our algorithms are proper learners and solve this problem with a slightly better sample complexity. In addition, like other proper learners, our algorithms select their output from a predefined set, which can facilitate choosing a distribution with specific structural property (c.g., mixture of Gaussians). In certain applications, this selection ensures consistency with the problem's 's underlying assumptions, which enhances interpretability and robustness.
2. The
2. It is worth noting that
The problem of hypothesis selection in sublinear time was studied for distributions on discrete domains [AAC+23]. Among other results, the authors developed data structure that upon receiving samples from a unknown distribution returns a hypothesis H in o(n) time. While their algorithm runs in sublinear time, their sample complexity depends on the domain size of the distribution, and their setting allows pre- pre-processing of the class H. in polynomial time. Another interesting variation for hypothesis selection is designing differentially private learners for the problem which has received attention over the past few years [BKSWIL 19, CKM 19, GKK+201
An important application of hypothesis selection arises when there is structural assumption on the underlying distributions. One approach for learning these classes to selectively choose cover for the class. One can then use the learners for the standard hypothesis selection problem (which we study in the paper) and use the cover as the class H. Examples of such structural assumptions include Poisson binomial distributions [DDS12], mixtures of Gaussians [KMV12, DK S0AJ14, 20), distributions with piecewise polynomial PDFs [ADLS17]. and histograms [Pea95, CDSS 14, CDKL22J. See Diakonikolas [Dia16] for survey of results.
DKS17, KSS18, ABM18, ABH+20),

---

2 Preliminaries
Notation: We use the following notation throughout this article. We use [n| to indicate the set .1.2....,12) For a distribution Q over X, ((x) denotes the PDF of Q at the domain element æ E X' For any measurable subset of the domain S S X. Q(S) indicates the probability mass of the set S according to Q. We use IQQ Q21lTv = supscx (Q)) Q2(5) to denote the total variation distance between Q1 and Q2. We say Q1 is e-close to Q2 if I Q2llTv is at most Conversely, we say Q1 is e-far from Q2 ||Q1 Q21lTV is greater than e. We use the standard O, Ω2 θ notation for asymptotic functions. Additionally, we use O, f2, and θ to hide polylog factors.
Scheffé sets: For every pair of hypotheses H; and Hj in H. we define the Scheffé set of H; and H, follows:
St. = { fo L H < Hy(r)} S3
(2)
ifi
It is known that the Scheffé set maximizes the probability discrepancy between H, and Hz. thus fully characterizing the total variation distance between the two distributions:
H - H2 = sup (H,(S) - H2(5)) = H (S.,) H2 (St,))
(3)
SCX
The optimal hypothesis: Recall that we assume the algorithm given samples drawn from an unknown distribution P. Let H,- denote the closest hypothesis in H to P. That is, H;- is the hypothesis for which |H,- - Pl = OPT. When there more than one hypothesis with this property, pick one arbitrarily as H..
Semi-distances: For every pair i,j in [n]. we define wy (H,H)) to be
In words, (y(H)) is the distance of H; to P observed on the Scheffé set of H; and Hy For every pair i E [n], we use (H.)) to denote an estimate of (H.H.) based on the observed sample. For the sake of consistency, we define wi w:(H:) to be zero. In addition, we define the score function W(H,) max wy( (H.). Similarly, W (H,) is defined to be maxje[m] (H,).
Refined access model: Similar to previous work [DL01, MS08], we use estimates of the semi- distances. One can easily estimate these quantities, denoted by w (H,), via the access model we have described earlier by letting ر (H,) be the empirical ratio of the samples that are in S,jj. Throughout this paper, we assume that there are universal parameters 8' (()) and e' O(c), for which with probability every (oy(H) is within e' of (H::)):
Vi E [n] |10 - (, SE.
A simple application of the Hoeffding bound and the union bound shows that one can compute all of the estimates via ((log(n/8')/e" samples, and each estimate can be computed in O(s) time.
Our algorithms access the distributions in U (P) only via querying w (H.). This fact brings the sample complexity of our algorithms to (llog(n/8)//e" samples. The time complexity of our algorithms determined by the number of queries they make the u (H,)'s multiplied by time that we spend on each query, O(s). Moreover, in the proofs of our theorems, we assume without loss of generality that all the أ (H,)" are accurate. Conditioning on the accuracy will not decrease the probability of correctness of any of our algorithms by more than 8' due to Fact C.I.
3 Overview of our techniques
In this section, we provide a high-level discussion of our algorithm. The important notations and definitions used here are provided in Section 2. For the high-level discussions in this section, we assume we have access to the exact values of the semi-distances wy (H,). the formal proofs presented in subsequent sections, will substitute each wy (H:) with estimated value w (H.).
5

---

If the error of these estimates is below e' = (c)) it can be shown that the overall impact of this substitution on our final distance guarantee (Equation 1) is most (c)). See the "Refined access model" in Section 2 for further details.
3.1 Background: Semi-distances and the minimum distance estimate
To solve the hypothesis selection problem, we seek a certificate that ensures we output a hypothesis H such that | TV is at most OPT. Similar to previous work, our algorithms operate based on the probability masses of the Scheffé sets (Equation (2)) of pairs of hypotheses in H. The semi-distance wyy(); (H)),, defined as H, (S(,) P (St,)], captures the "distance" between H; and P as measured on this particular S..j. One suggestion for readers internalize the semi-distances is to view them as distance between H; and P that is measured from the perspective of H,. By definition, wy (H;) is always a lower bound for |H Pl[tv:
Wy (H,H.) H. (8.,) (S sup (H,(S) P(S) H, Pl[Tv- SCX
However, it is possible for (H:) to be much lower, making it difficult for an algorithm to estimate the TV distance between H, and P just using semi-distances.
Nevertheless, for each hypothesis H,, a specific hypothesis H;-, determines its quality. As shown in the following proof, if w;-- (H,) S OPT, then H, is 3, OPT-close to P. with the total variation distance between H, and bounded by wi- (H,) and OPT via the triangle inequality:
w;- (H.), associated with the optimal
||4 - Pllvv |H, - H4- l|Tv + 111,- Pl[TV = ||, (8.,) H1 (8:))) OPT (By Eq. 3) S w.- (H.) w, + OPT S w,- (H,)) + 2OPT.
This observation implies that if assert that wi- (H,) is bounded by OPT, final solution to the problem and be done. The challenge is that we neither know i" nor OPT.
output H, as
This issue is addressed by the minimum distance estimate presented in [DL01, MS08] using a score function W W(H,) (H.). ). as defined earlier: W WH.) = max Wy(H), (.,). The minimum distance estimate outputs hypothesis f that minimizes W (H;). We can assert that, for the output of this algorithm, H. Wp (H) is at most OPT. This approach simultancously bypasses the issues of not knowing i* and OPT.
Note that W(H)) serves as a proxy for the quality of H; since W WHH) is an upper bound for wi- (H;). Using W (H,), we can address the issue of not knowing it. On the other hand, although OPT not known, we have good lower bound for OPT, which is W (H;-). Putting these observations together, we obtain:
( I Plltv S w;-(fi) 2OPT < w(I) + 2OPT < (()-)++ 30PT.
These inequalities are derived using the triangle inequality and the fact that H was chosen to be the arg minig(m] (Ht.). See Figure for an illustration the above inequality.
The primary hurdle with the minimum distance estimate is that it is costly to compute. Computing each W(H, takes Onn s) time, bringing the total time complexity of the algorithm to O(n² s). One might naturally conjecture that sampling may help compute an estimate of W WH,).. Instead of using ((H:) maxje[n] Wy (H.),, we can use W (H,) == maxjeR R wy (Hi: where R is set of
random indices in [n). The issue with this approach is that there is guarantee of i being selected
in R, making W(H, too low while H; may be far from P. Hence sampling, if used in trivial manner, is not beneficial.
3.2 The algorithm with a =3
In this section, we present an overview of Algorithm that attains 3. The details of this algorithm and related theorems are provided in Section A. At a high level, similar to the minimum distance estimate, we work towards finding hypothesis that minimizes W WHH)). To increase efficiency,

---

((H))
S OPT
Probability of St according to different distributions:
wy (H.)
ui (1I++
H. (S.))
((S.))
Hi. (S.,)
H.
||
Hy
l|Tv
0
TV distance absolute difference of prohabilities on Scheffé set
I|
Plire
P
OPT
Figure 1: A description of bounding |H, - Pllty via W(H)) and OPT
work with estimates of W(H,)'s denoted by W(H)). The general structure of our algorithm is as follows: Initially, all WH+) are set to zero. At every step. we come up with several pairs of hypotheses H; and H3 and update our estimates by setting W W(H) to max(W(HH)) w ()))). Our approach ensures that at every step, (H,) equal to maXjen (H,H)) for a small, carefully chosen set R. Eventually, we output hypothesis with roughly the smallest WH.)).
Focusing on small W: Our first idea is to focus on updating the W for hypotheses whose W(H) values are around the current minimum W. The rationale for this action comes from a simple fact: W (H;) always underestimates the value of W WHH)). Hence, if we observe that W (H;) is substantially larger than the current minimum, then W(H,) also substantially larger than the current minimum. This implies that H; is not suitable candidate for the minimum at this stage of the algorithm, and it can be ignored for now.
Bucketing hypotheses based on W: To implement this idea, we partition the hypotheses into = O(1/c') buckets = [B1, B2...., B based on (H,). The bucket & contains all the hypotheses H, such that WH+) E 1)c',
At every step, we focus on the smallest non- empty bucket B3 (the smallest & for which [Be] * 0). B, contains all the hypotheses whose (H₂) is around the minimum W. We pick pairs of hypotheses, H, E H and H, E Be, and update W (H₂). Note that our updates may increase W (H2), and may remove H, from B₁ and put it into larger bucket (a bucket with a larger index (). Also, observe that we never move a hypothesis into a smaller bucket since WH,) never decreases. We continue our updates to reach one of the following outcomes:
By becomes empty. That is, our updates made all (H;) fall out of the range of these buckets [0, E'). Thus, every W(H,) (and consequently every W W(H))) is at least E-c'. Every time that we empty out a bucket, we have increased our threshold for minimum (H.) by e'. Hence, we are getting closer to a bucket with the true minimum, which we hope reach in O(1/e) steps.
B3 is not empty, but we can confidently confirm most of the hypotheses in By are an acceptable output for the algorithm. Although we cannot ensure that H,, is indeed in Bi, we can find an acceptable final answer by selecting a random hypothesis in Be.
Which pairs to update? Next, we outline our update scheme to implement the above ideas in linear time. To enhance time efficiency, our aim to optimize the updating process ensure both quality and quantity in the chosen updates. Quality, in this context, relates to the extent of change in W (H,) following an update: We consider H, to have made a substantial update to Hi if W WHH) é' < u. (H.)) Such updates cause significant shift, increasing the value of W (H₂) by
7

---

more than c' and subsequently moving H, to different bucket with a higher index f. We refer to this event as H; removing H, from its bucket. The quantity, on the other hand, relates to the number of H instances that given H; can remove from Bg. An ideal H3 eliminates a substantial portion of hypotheses from By (say a constant fraction). We call such an H; a prompting hypothesis. Now, for (log Bel) rounds we find a prompting hypothesis and update all the W WH))) for H2 E Be, we will empty out the bucket Bj, and we can move forward.
Finding a prompting hypothesis: To find a prompting hypothesis quickly, we iterate over all H, in H. sample a few Hj, and check if H4 substantially updates W (H)). If Hi substantially improves a large fraction of the sampled hypotheses. then we declare that H; is a prompting hypothesis. See Section 1.1.1 for further details. In addition to that, we provide a more advanced version of this procedure in Section 1.2 that allows us shave off Olog n) factor.
Getting stuck? Here is your way out: What happens when Bg is not empty, and we cannot find prompting hypothesis? We show that if we do not find prompting hypothesis, then random hypothesis in B₁ is an acceptable answer.
The surprising part about this statement is that it holds regardless of the size of the bucket By due to hypothesis sampling procedure we have to find a prompting hypothesis. In search for a prompting hypothesis, iterate over all H, and sample roughly Olog n/o) many hypotheses Hj 's in By. We check, if H, can remove them from the bucket. Note that if H; was not found to be prompting, it implies that H₁- cannot substantially update most of the hypotheses in By. Thus, We have that with high probability for 1 - 5 fraction of the hypotheses in B,, w. (H,)) S c.
The clever hack here is an observation about H₃., Earlier, we discussed that we are looking for hypothesis H. with w;- (H,) S OPT. We claim that a random hypothesis in the last Bg (almost) has this property. On one hand. given that Hi was not found to be prompting hypothesis, for 1 - d fraction of H, in Be, wi- (H:) must be at most e'''. On the other hand, the fact that all the previous buckets. B1. .1...... BB-1, are empty indicates H,- has shown a semi-distance of at least (e 1) Hence, OPT, which is at least as large as all Hi- semi cemi-distances, is at least (E - 1) e'. Therefore, wi- (H,) < é' + OPT. Therefore, for 1 8 fraction of the hypotheses in Be, they are 3PPT + ((e) close to P. For a formal argument, see Lemma A.I.
Now, assume the search for the prompting hypothesis fails. Recall that during the search, we have checked every single hypothesis in H. During the search, at some point, we must have stumbled upon Hi- and did not declare it as a prompting hypothesis. In this case, either our sampling for substantial updates failed (which happens with small probability), or we can infer that there are not too many far hypotheses in B,. Either way, we can output a random hypothesis from B, as the final sample without increasing the error probability by too much.
Dependency 8: It is worth noting that this last step results in a polynomial dependency on 5 (as opposed to a more desirable dependency of log(1/5). This is mainly due to the fact that to ensure that random hypothesis in B, is not too far, with probability of 1 - 5 in a single round, we have to try O(log(n)5) /5) hypotheses in B, and check if H:- is prompting them. Hence, relying on this structural property of H-- makes polynomial dependency on 8 inevitable. Improving the dependency on 5 for this algorithm would require new algorithmic ideas.
3.3 The algorithm with a = 4
We introduce another (almost) linear-time algorithm for the hypothesis selection problem, where the time complexity shows improved dependency on e. However, this algorithm has a slightly worse accuracy parameter compared to our previous algorithm: a 4. This algorithm and the subsequent theorems are provided in Section B.
Algorithm with a guessed upper bound of OPT: As mentioned earlier, unlike previous work, our algorithm does not receive any prior information about the value of OPT. It might be speculated that there exists an easy reduction between our problem and another version of hypothesis selection, where an auxiliary parameter a is provided to the algorithm such that OPT < a. A learner without the knowledge of a can make guess about a and run one of the existing algorithms that works with the knowledge of an upper bound of OPT (c.g.. [ABS23]) and check if it finds good hypothesis or
8

---

not. With this procedure in mind, we can run a binary search to find the smallest a for which we find a hypothesis." + However, a challenge with this approach is that the algorithm might yield hypothesis even when < OPT, making it difficult for us to refute the hypothesis that is found. Even if the output Hl satisfies W ((i)= >
it does not necessarily invalidate our guessed value o.
To overcome this challenge, we design an algorithm, namely A. with enhanced accuracy guarantees for the output hypothesis. We provide A with the value σ. We treat a as a "guess" for which we hope that OPT S o. We require the algorithm to either refute our guess and declare OPT > o, or output a hypothesis A with a reasonable distance to P. irrespective of the relationship between OPT and a. More precisely, the distance of the output hypothesis should be bounded by: || - P S max max r) + With these revised guarantees, it is permissible to run binary search over different values of a in (e. [1/e] e) e). and output the hypothesis that A returns on the smallest For the rest of this discussion, focus designing A and a provided parameter
Seeds and finding an acceptable hypothesis via seeds: In this algorithm, we introduce new concept called a seed for hypotheses. A seed provides us with structural property that enables us to identify an acceptable hypothesis, regardless of the relationship between Hyg and the seed. More formally, for a hypothesis H,, we define Ma,b H,;) as the set of hypotheses H, such that (H,H)) is between a and b:
Ma,((H:) = (H, E < (.)((H.)) b).
We may omit the subscript of M when it is clear from the context. We say a hypothesis H, is a seed if almost all of its (H,) are low and its W (H,) is not too large. The quality of seed is determined by three parameters: a, b, and m.
Definition 3.1 (Seed), Given parameters a, E Rg0. and non-negative integer m. say hypothesis is an (a, b, m)-seed if the following hold: 1) W (H..) S b, and [Ma. S m.
A seed with a small-sized set M and a small b exhibits an interesting property: Suppose we have a seed H; with a constant-sized set M. In this case, in O(n) time, we can compute W W(;)) of every hypothesis H, in M. Now, let He E M be one of the hypotheses that minimize W (H,): He = arg H, EM (H2). We claim either H, or Hy is acceptable output in this case.
When H;- is in H.) \. M, we can infer that w;- (H:) is at most (or, more precisely. b b+6 é'), From our earlier discussion, if is sufficiently small (compared σ), we can show that H; is close to P. In cases where H₁- is in M, although we do not have strong guarantees for H, itself, we have a very good answer already: Hş is essentially a minimum distance estimate for the set M which includes Hy.. Thus, we can conclude: First, H₃ is an acceptable output because it is 3 -CToso,,, second, W (HH) is a lower bound for OPT.
Now, as we described, we have two acceptable outputs for two cases of the problem. For H;,- E H.M, H, is acceptable answer. For H,- E M, He is acceptable answer. The only problem is that do not know which case we are in. Our strategy is to pick hypothesis that is still reasonably close to P even if we are in the other case. Let us fix a threshold value T. We compare W W(H)) with To: 1) If W WH+)) < T a, as we have discussed earlier, H, is (T a + (0PT)-close to P. This bound holds regardless of where H.- is. 2) Next, if W W(H)
T a, we cannot say H, is a good choice for us. However, we can conclude that H; is a close hypothesis to P even when H₁- happens to be in M. In this case, we know that OPT 2 W (He)= > T c. We take advantage of this knowledge and obtain the following bound:
1| PlITv = bo + 2OPT & ( b +2 OPT.
Thus, regardless of where H,- is, H, is (maxx(a.bT)) + max (a, OPT). Now, the algorithm is fairly straightforward. If W (H+) is small, output H5; otherwise, output H,, We summarize these four cases in the following table. Depending on a and b, we set T to minimize the maximum distance we
'This idea works to some extent, but it causes a to be increased by 2, which is not useful in our setting. See [ABS23] for more details.

---

endure in these cases. It is worth noting that in this argument, we did not rely on any prior knowledge concerning the relationship between or and OPT.
H₂. EM
H₂- EM M
W(H)) > T W(H) > T
|H; Pl[tv 3 a a + 2PT
|H, Pl[Tv S (b/T + 2)OPT
He Plivv I T a 2OPT
[He 1V - T a + 2OPT
Table 2: Four cases when we process good seed.
How to find the first seed? Here, we provide an overview of our approach for identifying an initial seed. For a detailed explanation of the algorithm and its performance, refer to Section B.1.
To start, fix two parameters, a = a and b = 3a. To identify a seed hypothesis, we iterate over all hypotheses H1, - Hn, checking whether each hypothesis H; is strong seed (i.e., a seed with small MM) by sampling several Hj's and verifying if Wy (H,) is at most a. Roughly speaking, for an integer m E [n]. if we sample approximately ((n/m) H2 's and find that no wH,H,) > a, we can, with high probability, confirm that the size of M does not exceed m. This approach requires O(n²/mi /m) time.
There are, however, few caveats with this method. First, if seed is identified using the above approach, it may have a large W (H,) > b. In this case, we can infer that H; is likely far from P. Given the time invested in identifying H4, we aim to leverage this information. Broadly, observing that w, (H,) S. implies that many hypotheses are close to H; (assuming that w;(Hl) values are also small). Knowing that H, is far from P. we can mark all hypotheses close H, as also far, allowing us to proceed with the search. While this may seem counterproductive, marking a significant number of hypotheses as "far" constitutes progress for our algorithm. Specifically. if, at some point, all hypotheses are marked, we can declare that a < OPT.
The second caveat is more challenging. Ideally, seek seed with constant m. but finding such seed would require Ö(n? /m) Ó(n²) time. Consequently, for a linear-time algorithm, we can only afford to find seeds where m = (n)). In other words, the quality of the seed we can initially identify much lower than the quality required for producing solution. This leads our next idea: boosting a seed, which is an approach to incrementally improve the seed's quality in roughly Ollog n) steps.
In this process, reduced value of .MI. For a formal argument, see Section B.2. Assume a rate parameter 17 E (0, 1). As discussed earlier, by spending On//r) time, can identify seed with m & n7.n. n. Initially, m- = M might be O(n). Hence, rather than calculating W WH,)) exactly for all H2 E M,, we compute an approximate maximum semi-distame W (H₂) by sampling hypotheses. Specifically, for each H, E M, we set (H,)) == maxH, wy (Hz), where H 's are sample hypotheses. Using these approximate values W. we process the seed as follows. Let Hz denote the hypothesis minimizing WH,),, with the following possible outcomes:
Boosting Seed:
an initial seed to iteratively find stronger seed with
1. High (Her: If (Hte) is high, all WHzr (and thus W(H;)) values are likely large, making H, an acceptable final solution.
2. Low W (He): While this does not guarantee a low W it suggests that most wi (He) values are small. Based on the value of W (Ht), consider two cases:
2.1 (He)) > (He): He is likely far from P but has many close hypotheses, allowing us to mark these nearby hypotheses as far.
2.2 Moderate W (Hz): In this case, He can serve as our new seed, as it yields a smaller set ((H)) than Hj,
Note that when we select Hg as our new seed, M(H:) is roughly (nn/t). However, we compute WH,)'s for only [M(H))) P5 17 n many hypotheses. Hence, with an increased sample size t= =0(1/))) this approach yields a smaller [M(H+)) R 1/2 n. The step of the process requires O(IM) 1) = m//1" O(n/n), paralleling the initial search. By repeating, we progressively reduce m = M. and for a constant 77, m decreases by a fixed factor until reaching a constant m seed, as desired.
10

---

Acknowledgments
M.A. was supported by NSF awards CNS-21 CNS-2120603, CCF-1934840, and BU's Hariri Institute for Computing. This work initiated while M.A. was affiliated with Boston University and Northeastern University and was done in part while M.A. was a research fellow at the Simons Institute for the Theory of Computing. M.B. was supported in part by NSF award CNS-2046425 and a Sloan Research Fellowship. A.S. was supported in part by NSF awards CCF- and CN6-2120667 well as Faculty Awards from Google and Apple.
References
[AAC*23] Anders Aamand, Alexandr Andoni, Justin Y. Chen, Piotr Indyk, Shyam Narayanan, and Sandeep Silwal. Data structures for density estimation. In Proceedings of the 40th International Conference Machine Learning. PMLR, 2023.
[ABH+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:1-32:42) 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 Thirty-Second AAAI Conference Artificial Intelligence, pages 2679-2686. AAAI Press, 2018.
[ABS23] Maryam Aliakbarpour, Mark Bun, and Adam Smith. Hypothesis selection with memory constraints. To appear in NeurlPS 2023, 2023.
[ADLS17] Jayadev Acharya, Ilias Diakonikolas, Jerry Li, and Ludwig Schmidt. Sample-optimal density estimation in nearly-linead time. In Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium Discrete Algorithms, SODA, pages 1278-1289) SIAM, 2017.
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-59:33 2018.
[AJOS14] Jayadev Acharya, Ashkan Jafarpour, Alon Orlitsky, and Ananda Theertha Suresh. Sort- ing with adversarial comparators and application to density estimation. In 2014 IEEE International Symposium Information Theory, pages 1682-1686. 2014.
[BBK+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.
[BKM19] 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 hypothesis selection. In Hanna M. Wallach, Hugo Larochelle, Alina Beygelzimer, Florence d' Alché- Buc, Emily B. Fox, and Roman Garnett, editors, Advances in Neural Information Processing Systems 32: Annual Conference on Neural Information Processing Systems 2019, NeurIPS 2019, December 841 2019, Vancouver, BC, Canada, pages 156-167, 2019.
[CDKL122] Clément L. Canonne, Ilias Diakonikolas, Daniel Kane, and Sihan Liu. Nearly-tight bounds for testing histogram distributions. In Advances Neural Information Processing Systems 35 (NeurIPS), 2022. To appear.

---

[CDSS14] Siu-on Chan, Ilias Diakonikolas, Rocco A. Servedio, and Xiaorui Sun. Near-optimal density estimation in near-linear time using wirtt histograms. In Advances in Neural Information Processing Systems 27: Annual Conference on Neural Information Processing Systems 2014, December 8-13 2014, Montreal, Quebec, Canada, pages 1844-1855 2014.
[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.
[DDS12] Constantinos Daskalakis, Ilaas Diakonikolas, and Rocco A. Servedio. Learning poisson binomial distributions. Howard J. Karloff and Toniann Pitassi, editors, Proceedings of the 44th Symposium on Theory of Computing Conference, STOC 2012, New York, NY, USA, May 19 22, 2012, pages 709-728. ACM, 2012.
[Dia16] Ilias Diakonikolas. Learning structured distributions. In CRC Handbook of Big Data, pages 267-283 2016.
[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 1 1183-1213. PMLR, 2014.
[DKS17] Ilias Diakonikolas, Daniel M. Kane, and Alistair Stewart. Statistical query lower bounds for robust estimation of -igensimesion gaussians and gaussian mixtures. In Chris Umans, editor, 58th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2017, Berkeley, CA, USA, October 15-17, 2017, pages 73-84, IEEE Computer Society, 2017.
[DL96] Lue 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.
[GKK+20] Sivakanth Gopi, Gautam Kamath, Janardhan Kulkarni, Aleksandar Nikolov, Zhi- wei Steven Wu, and Huanyu Zhang. Locally private hypothesis selection. In Jacob D. Abemettyy and Shivani Agarwal, editors, Conference Learning Theory, COLT 2020, 9-12 July 2020, Virtual Event /Graz, Austria], volume 125 of Proceedings of Machine Learning Research, pages 1785-1816. PMLR, 2020.
[KMV12] Adam Tauman Kalai, Ankur Moitra, and Gregory Valiant. Disentangling gaussians. Commun. ACM, 55(2):113- 2012.
[KSS18] Pravesh K. Kothari, Jacob Steinhardt, and David Steurer. Robust moment estimation and improved clustering via sum of squares. In Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing. STOC 2018, Los Angeles, CA, USA, June 25-29, 2018, pages 1035-1046. ACM, 2018.
[MS08] Satyaki Mahalanabis and Daniel Stefankovic. Density estimation in linear time. In 21st Annual Conference on Learning Theory- COLT, pages 503-512, 2008
[Pea95] Karl Pearson. Mathematical contributions to the theory of evolution. ii skew variation in homogeneous material. [abstract]. Proceedings of the Royal Society of London, 57:257-260, 1895.
[SOAJ14] Ananda Theertha Suresh, Alon Orlitsky, Jayadev Acharya, and Ashkan Jafarpour. Near-optimal-sapphe estimators for spherical gaussian mixtures. In Z. Ghahramani, M. Welling, C. Cortes, N. Lawrence, and K.Q. Weinberger, editors, Advances Neural Information Processing Systems, volume 27, 2014.
12

---

[Yt885] Yannis G. Yatracos. Rates of convergence of minimum distance estimators and kol-
mogorov's 's entropy. The Annals of Statistics, 13(2):668 777, 1985.
13

---

Algorithm An algorithm for hypothesis selection with a =
procedure SELECT-HYPOTHISSSSEE e, ò, and query access w (11))s)
2:
W(H) < for every i [m]
3:
k [1/e'] +
4:
B1 1 H
5:
B +
6:
c/3
7:
8/3
8:
+
9:
fn + 8'/k
10:
ofp t 7. 7././/4/44///// k log(n))
11:
for 8 = 1,..., do
lterating over buckets
12:
for i ==
do
D. Iterating over hypotheses to find a prompting one
[Bg then
14:
Break the "for" loop and move on to the next bucket.
15:
if Is 1S-PROMPTI f, Hi, 7, e', 8') then
Checks if H; is prompting. Ce f 0 b A counter for the number of hypotheses that H, removes from B for H2 E B2 do -Update all hypotheses in Be via the prompting hypothesis if (i, > W(H)) + then
16:
17:
(HH,) max (W(H)), (b,(HH))
20:
Move H2 to B BIW
Cei - Ct +1
22:
Cra < 7/2 then
indicates H4 was not prompting.
Ci++BB
23:
Output 1 and halt.
24:
i 2--00 0
Restarts the "for" loop.
25:
if [B|] * 0 then
26:
H + a random hypothesis in Be
Output H and halt.
A
Almost linear time algorithm with a =
In this section, we focus on our first result, the algorithm with a 3. The pseudocode of our approach is presented in Algorithm 1. We prove the performance of this algorithm in Theorem 5, An overview of our approach is described Section 3.2.
At high level, our algorithm begins with all W (H.) set to zero, and all hypotheses placed in Bi We then iterate over all buckets. In round f, we check if there is prompting hypothesis H; H that can move a significant fraction of hypotheses from B, Specifically, we look for an H, that moves y-ffaction of hypotheses from Be by updating them, where y (()). If we find such hypothesis H,, we update all the hypotheses in B, and move many as possible this process, we count the number of hypotheses that H; removes from B₁, which is tracked by Cz: the algorithm. If the actual fraction of hypotheses removed from B& is less than 7/2, we infer that Is- IS-PROMPTING falsely declared H, as prompting hypothesis (false positive). Thus, the algorithm returns J. Otherwise, we restart the search by setting prompting hypothesis. We continue this process until no prompting hypothesis is found or the bucket emptied. we completely empty a bucket, we move on to the next one. not, we select a random hypothesis in B, as the final output and halt.
of Br. During
and iterate over all H, to find the next
Theorem 5. Suppose H. is class of known hypotheses and P is unknown hypothesis. Assume the algorithm has access to accurate estimates of úo (H+) that have an ervor of at most é'. Let e and 5 be parameters in (0, 1). If S e, then Algorithm I is (a 3, e, 5y-proerr learner for P in H. The running time our algorithm is (((n((5te) TT), where T2 the time obtain each (H.).
Proof. Our proof consists of three parts:
14

---

1. If the algorithm returns H, with high probability, H is not too far from P.
2. While the algorithm may not produce hypothesis all the time, the overall failure probability of the algorithm low.
3. The running time the algorithm meets the desired bounds in the theorem.
The output H is close with high probability. Suppose output H By at step l. Our goal is to show that H (3 OPT e)-close P with probability 8'. We define events & and & for each 8 E [k] based on the fraction of far hypotheses in B3 in Line 25:
& = the event that a non-empty B3 in Line 25 contains at least [ [Bel
hypotheses that are (3 OPT e)-far from P.
the event that non-empty B3 in Line 25 contains fewer than [ [Bel] hypotheses that are (3 OPT + e)- from P.
Conditioning on the event ε fewer than a y fraction of the hypotheses Bg are far. Since A is randomly selected hypothesis Be, the probability of H being far is less than 7
Pr [ Dr[li
PllTv > 3PPT + & <9
Next, we focus on the case where & holds: least a y fraction of the hypotheses in B, are (3 OPT + e)-far from P. In the following lemma, we show that Hi- is a prompting hypothesis for such Bg. The proof of this lemma is available in Section A.2.
Lemma A.1. Suppose Bt C H is the smallest non-empty bucket for which at least a fraction of its hypotheses are (3 OPT + e)-far from P. Then Hi is prompting hypothesis that can remove a Y fraction of the hypotheses in By.
If we output hypothesis in Be, clearly, the prompting hypotheses had failed empty out the bucket. Therefore, the last time the algorithm was iterating over all i's in [nt] the IS-PROMPTING procedure returned false for every single H,, and no "restart" happened. However, during those iterations, at some point, reached i" implying that the Is-PROMPTING procedure did not catch that H;- is prompting hypothesis. This event happens with probability at most 85n-
Pr[Ee] v Pr[Is Pr[Is- PROMPTING returns false for H₃- and H is prompting hypothesis]
< Pr[Is- PROMPIPRNGG returns false for H.- H;- is prompting hypothesis] S ögn
Given Equation (4) and Equation (5), we bound the probability of outputting a far it as follows:
Pr Outputting A and j - Plliv > 30PT + c]
Pr A - Pllrv 30PT + c ccE, Pr[[E]]
8=1
Pr ||A- Pl|tv > 30PT +e E
Pr El
Pr
k
< Σ Pr[E:] + Σ Pr
2=1
(=1
< k 8Fm + 7 28'
'It is worth noting that using the E₁ notation somewhat non-rigorously here. This notation does represent complementary event E,. Instead, it denotes the complementary event of E conditioning on outputting of H from the bucket Be.
15

---

The last line is due to the fact that we set 8Gn = 8//k and = 8'.
Bounding the overall error probability: We have shown that if we output H, it is acceptable answer with high probability. Now, we need to show that the overall error probability of the algorithm too high as well.
Our first claim is that the algorithm always ends, meaning that we do not restart the "for" loop infinitely many times in Line 24. Note that the restart happens only after check that at least 7/2 of the hypotheses are removed from B₃ in Line 22. Therefore, the total number of restarts for any (I + I 4log(n)/7 times.
given bucket is at most (001/(11//00
In addition, we claim the algorithm does not end without outputting A or T. Every H; belongs to some bucket at every step of the algorithm. This is due the assumption that üū (H;) is in [0. 1]. Thus, W H.) is always between W (H.) S ke' Thus, not possible to reach [g] = for all & E [k] in Line 25. For the bucket that cannot be emptied out, the algorithm outputs either 1. or A.
Next, we show that the probability outputting 1 is at most 8'. Note that the algorithm outputs 1 when H, was not able to remove at least 7/2 of the hypotheses in Bg. As we have established earlier, the restart happens only 4 log(n)/7 times for every bucket. Therefore, the IS-PROMPTING procedure is invoked at most 4kn log(n)/> / times overall. Each time we have chance of 6jp of declaring hypothesis prompting crroneously. The algorithm in Line 22 checks if the error has happened, and outputs 1 when it does. Hence, we have:
4kn log(n)
Pr[Outputting 1]
5sp S S
(6)
The final inequality follows from setting 6fp = 7 8//(4 kn log(n)). Thus, we can bound the overall error probability as follows:
Pr[ Wrong answer] Pr[Outputting 1]
Pr Outputting A s.t. 1| Pl[ny 3 3PPT +c] <38 s 5.
The last inequality holds since 8' 5/33.
The initialization takes O( k) time. The algorithm runs over & buckets. For each bucket, we may restart the "for" loop Ollog(n)/2) times. Within each "for" loop before restarting, we invoke the Is PROMPTING procedure (n)) times where, with the exception of one of them, all return false. Let T((i) indicate the time that the procedure spends on H; the false case. Also, set this quantity be Terue if the procedure returns true (which happens at most once before restarting). we find prompting hypothesis, we query the ri (H,)'s O(n) times, and spend O(n Tg) for this step. Hence, the total time complexity is:
Running time:
Total time complexity = =0 00(, log(n).
Σ T + Teruo + nn -Tg))) )
Advanced version of IS-PROMPTING: We described the guarantees of the advanced version of the Is PROOPPPPNN procedure in Lemma A.3. In that lemma, we have shown that the running time of the false case is proportionate to the number of hypotheses we remove from By during the procedure of Is P--PRMMPINGG. We denote this quantity in the r-th search for the prompting hypothesis H, in bucket by via nf ((,5) Since the total number of hypotheses that we can remove is at most O(n). we have:
16

---

T false
Σ 0 ((1og ( + log log
(0%)) -Tal? + + Tol?)
=0 n (log 074 + loglog
(57p)
Ta/l + n. -n.Tgg/ Tggl)
= n (log (Tm + log log
Ta//?))
Using the setting of our parameters, 0/p = y- 7 log(n)) = Onn log n// (ōe) and 6fn / = O
Tu(i)
0
n
log
1
+ log log [oe)
To
false
82
8e
n
log
+ log log (m)
82
8e
Moreover, for the that prompting hypothesis is found:
Tirue = 0
log
fp
(log
1
+ log log (0T²) -Ig/12)
n
1
11
log
log
+ log log
Tq
82
de
de
.0e
0
1
log
n 5e
log
1
+ log log (n)
- -Tg
82
de
Hence, the total time complexity is:
Total time complexity = 0 h: log(n).
(())) Faice + Terue + n Tn.T.)
log(n)
1 n log log + n --ogg
(10g
) Ty
2)
0
83
J3c Ta)
n1
Simple version of Is- IS-PROMPTING: In this version, we only have one possible confidence parameter, which min(ōfns 8fp). Hence, using Lemma A.2, we have:
(1) faise Terue O (log ((min(6 (/)))(())m:0/)))1))) -Tg/?²))
Total time complexity = 0 k. log(n)
Σ
(i)
falme + Teruo + n....T..
?
0
log(n)
83
(log
(5e)
12
-Tg)
Ô
Ta
03
Thus, the proof is complete.
17

---

A.1 Identifying prompting hypothesis
In this section, we provide two algorithms for identifying a prompting hypothesis. The simple algorithm, presented in Section A.I.1, involves sampling the hypotheses in bucket to estimate the fraction of the hypotheses that H, can move, using standard application of the Hoeffding bound. The advanced algorithm, presented in Section A.1.2, is based on the fact that we require different confidence parameters for false negative and false positive errors, given our analysis for Algorithm We also show that the time complexity of this algorithm, in the case it returns false, is proportional the number of hypotheses we can remove from the bucket during this procedure, which later helps us to use an amortized argument for the overall time spent false returns.
A.1.1 Simple version of Is- IS-PROMPTING
Algorithm An algorithm to identify a prompting hypothesis (simple version).
1:
procedure Is- IS-PROMPTING-SIMPLL E, Hi, 7/ é', 8, and query access to ú; (H;)'s)
2:
t [8 log(2/6)/72
3: Ur +
uy counts # sampled hypotheses that H, updates
4:
repeat times
5:
Hj + a random hypothesis in Br
6:
if th, (HH (H₃) + then
7:
Up + +,
8:
9:
if
Mr
3% then return false
11: else
12:
return true
Lemma A.2. Suppose we are given two parameters ,,e' E (0, 1), and three positive integers n. k, and [k). Assume we are given class of hypotheses H. its partition into buckets B = BB, B2,..,, Bx}, and hypothesis Hi H. The SS-PROMPTING-SIMPUL procedure in Algorithum 2 receives H. B, E, Hi, ofp 8fns and e' as its input and returns true or false with the following guarantees:
If H4 substantially updates at least a -ffrcction of the hypotheses in Br, then IS-PROMPTING- SIMPLE returns true with probability least 8.
If H; substantially updates less than 7 /22ffraction of the hypotheses in Bi, then Is- PROMPTING-S returns false with probability at least
We have the following guarantees for the algorithm::
Number of queries to uh dd(HH))s: O (1og(6-1)/72)
Running time: O (Log(6 -T//"?)
where T, is the time to obtain each (H;(
Proof. This is simple application of the Hoeffding bound:
Pr
E
[
2 2] s 2exp (-217²) 88.
A.1.2 Advanced version of IS-PROMPTING
We present an overview of the algorithm for the advanced version of Is IS-PROMPTING, Suppose we are given a parameter 7, and our goal is to design an algorithm that does the following with high probability: it returns true when H, can substantially update a 7-fraction of the hypotheses in Br, and it returns false when H; can substantially update less than 7/2 fraction of the hypotheses in Br.
18

---

For this new procedure, we take advantage of an asymmetry that exists between returning false and true. This asymmetry arises mainly from the analysis of Algorithm 1. Roughly speaking, for every bucket f, to find a single prompting hypothesis, we check ((n) (potentially von-prompting) hypotheses. On the other hand, we only need 1og1/- (Bz) prompting hypotheses to empty out the whole bucket. Hence, we expect that the procedure returns mostly false rather than true.
Another difference here is the cost we pay for mistakenly declaring true or false. When we declare hypothesis prompting. we iterate over all hypotheses in B₃ and check if we can remove them from the bucket. If the hypothesis was not actually prompting, we have paid a substantial cost (in time) without making progress. Thus, cannot have too many hypotheses that the algorithm declares prompting while they are not (false positives). However, the probability of mistakenly missing a prompting hypothesis does not have to be this small (false negatives).
Below is a more precise definition of these errors:
0 Pr[ Pettuunnng true H, substantially updates less than 7/2 fraction]
6 fm Pr[ Prettunning false H; substantially updates at least y fraction]
Given the analysis of our algorithm, we can show that the probability of false positives must be around ((1/ [Bl)) Ö(//)). On the other hand, our analysis is robust as long as the probability of false negatives is roughly (δ)), where 5 is the overall confidence of our algorithm. (The reason for this choice of parameter may not be obvious from this high-level discussion; however, it is direct artifact of our analysis.) This gap is particularly large when ō is a small constant, is common in the literature.
The Is- S--PROPPTING procedure (Algorithm 3) is designed in way that has different time complexities depending on its output being true or false. The procedure uses more than Olog n) (more like O(log n log(1 (1/ /²) time if it returns true. However, the main advantage is that it uses much less time when the output is false. In fact, instead of paying (log n), we only spend (llo((18)) time plus amortized cost of (117)) for the OB;) calls to the procedure.
The algorithm runs roughly (logn) rounds. each round, draws a few random hypotheses from By (roughly 0(log(1/0)/7)) In each round, we check if the fraction of hypotheses H; can substantially update is close to y. At any round, if we see that the fraction is not close to 7, we return false. The hope is that for prommpptt hypothesis, hypothesis passes too many rounds without us noticing that is not prompting. Therefore, we must have seen an inflated number of substantial updates in these rounds. Before returning false, we perform those substantial updates among the sampled hypotheses that we have observed to remove those movable hypotheses from By.
either stop very quickly the
We can capitalize on this fact in our cost analysis. In fact, we can show that in the false case, if the procedure takes roughly O(L/7) time, it must have removed / hypotheses from the bucket. Thus, one can show that the amortized cost of these elongated rounds is only O(1/7).6
Lemma A.3. Suppose we are given three parameters tp. 8yn, E (0, 1), and three positive integers k. and & E [k). Assume B 3 B2...., ......BB B&} and a hypothesis H; E H. The Is- IS-PRRMPTING procedure in Algorithm 3 receives H. B,e, Hi, ofp: oeay and e' as its input and returns true or false with the following guarantees:
given classes of hypotheses H. its partition into k buckets
If Hi substantially updates at least Toretyyrrra fraction of the hypotheses in Br, then IS-PROMPTING returns true with probability at least 1 8fn
If H; substantially updates less than 7/2 fraction of the hypotheses in Br, then Is- PROMPTING returns false with probability at least 1 8sg
'The parameters in this high-level discussion lack precision. For a rigorous analysis, refer to our proof of Lemma A.3.
19

---

Algorithm 3 An algorithm to identify a prompting hypothesis.
procedure (S-PROMPTING(B, & H4, Ts e', Öfns öfp, and query access úh (14)'s)
2: R
logs/2
3:
So +- 0
S'is is set of hypotheses that H; can update substantially.
4: for r 1,.... do
5:
if
18, -1 2 then
Br
6:
return true
7:
S, S1
8:
Ur +
Up indicates # hypotheses H; updates
18 log(2
9:
repeat
times
/ a random hypothesis in B3
v;; ((()) > W (cf") + then u, U, +1 S. S, u (
11:
12:
14:
15:
|, S
< 2- then
8
16:
for H E S, do
WHH,) max (H)
17:
18:
Move H, to B ([W(H)))
return false
20:
32 if de < T then
21:
for Hy E S, do
W(H)) c max (W(H)),
23:
Move H, B W[W,))
24:
return false return true
25:
the algorithm returns true, we have the following guarantees for the algorithm:
Number of queries to w; (H,H))ss:: O (log (07p) (log (DTTh) log log (0T2) /72))
Running time: O (1og ( (log (57))) + log log (5T²) -Ty/?2)
Suppose the algorithm returns false. Assume my (E.6) indicates the number of hypotheses that the algorithm removes from Be. Then, we have the following guarantees for the algorithm:
Number of queries to ús (H2)':: ((1g (5Tm1) -log log (5m)) /1² n((.0)
Running time: O ((10g (5Tm) + log log (077)) ) Tg/?² n (1.0) Tnl?) .S
In above bounds, where Tg denotes the time complexity obtain each (,y(H.)
Proof. The probabilities in this proof are taken over the random choices of Girl's Note that contains at the hypotheses for which we can change.
Probability false positive: First, we show that probability of outputting true, while H, can substantially update less 7/2 fraction of hypotheses in Br, is at most ösp- The algorithm return true in two places. First, the beginning of each round, we check whether 5,-1 contains least //2-fraction of hypotheses. This answer is always correct with probability
Since the algorithm
20

---

has an evidence that H, can certainly update at least 7/2 of hypotheses in Be. Thus, this case does affect our false positive rate fpp
Second, the algorithm returns true after all rounds end. This case only happens when ", ft is at least 3 in every round in Line 20. It is not hard to that uy is binomial random variable with t trials. The success probability of each trial is the ratio of the hypotheses in Be that H; can update substantially. Thus, in the case where II, substantially updates less than y fraction hypotheses, by Markov's s inequality, we have:
Pr[ Returning true H, substantially updates less than n/2-fraction]
n 1) s (2/3) S 66p t
Pr Vr [R]
Ur t
37
Pr
Ur
37 $1
Probability of false negative: Suppose that H, substantially updates at least --frcction of the hypotheses in Bg. That is, H; can update each G(()) with probability at least y. Fix round r. We bound the probability of returning false in Line 19 and Line 24.
In Line 19, return false when |S,] - | 3=²
That is, the number of new hypotheses we added to S, is not too large. Consider the random hypotheses we draw at round r. Our claim is that most of these random hypotheses
not in S, The probability that one G/7) be selected from - is | [Be] However, this expectation less than 7/2, Otherwise, the algorithm would
have returned true earlier in Line 5. With this information in mind, we can use the Hoeffding bound and get:
Pr number of G. E S,-1
5
Pr
number of G.T) E ES
5 ?
11
1)
8
t
8
2
number of G. E S
1
Pr
+
t
|B
85n
I exp (-2t (1/4))) -
2
In Line 24, we return false if u,/t less than 3 7/44. 4. By Chernoff bound, we have:
Ur < (1 (1- + Pr
ty 3 .
= 8fn 2 R
exp
t
Taking the union bound over all rounds, we obtain:
Pr Pr[Retuming false H, substantially updates least --frcction] S 8jn.
Running time: In the case the algorithm return true, the algorithm makes O(R (R-t) -) queries to w ( 's. And, it runs in the O(R t TTg). algorithm returns false in round r, similarly
makes Orr t) queries to wi c 's. And, it runs in the O(r (T)) Note that with the exception of the last round every round E [r - 1]. At least - t)/8 new hypotheses are added to S,,. Therefore, the size of S, is at least (7 t. (r - 1))/8. We remove all of these hypotheses before we output false which cause the size of B, to drop by (444)) = |S.]. In this case, the algorithm
makes ( nf (f,6) /n) queries w; (((7) 's. And, runs in the O ((1 no (2.1) /7) TTg) Thus,
the proof is complete by setting = Iogga/2 (1) and L == log /n/
21

---

A.2 Proof of Lemma A.1
Lemma A.I. Suppose B3 S H is the smallest non-empty bucket for which least a fraction its hypotheses are (3OPT e)-far P. Then Hi- is prompting hypothesis that can remove a fraction of the hypotheses in Be.
Proof. We show that H₃- can substantially update W of any far hypothesis in B₁. Let Hy denote a (3OPT + c)-far hypothesis. First, observe that vig- (Hy) must be large compared to OPT:
Wi- (H₂) 2 we (Hy) é' = , ( P x)) - z 5 (- )- - H,- (5 ) H (5 )- - P -S
z | H₁ IIv |H,- Pllrv -
(By Fact C.2)
|H P - 2 PllTv -
30PT + - 2OPT - < OPT + 2
addition, OPT cannot be much smaller than ée'. The main reason that the buckets before Bg are empty. Hence, H-- belongs bucket By where E is at least l. By our definition of bucketing:
W (H,-) must be at least (e 1) Hence have:
11- & W (H+)) S WH,-) (H+)) S OPT
Note that assume , belongs B₁, yy is less than le'. Putting all these observation together, we achieve:
W, + <le é S OPT 2 u.. (H₁).
Therefore, if we update Wr via ú.-- (Hy). then H,- can significantly improve W,. This fact implies that H;- can removes the bad hypothesis from B, which concludes the proof of the lemma.
B Linear time algorithm with a =
In this section, we present our second algorithm whose sample complexity has a better dependency on the accuracy parameter An overview of approach is presented in Section 3.3. The pseudocode of our approach is presented in Algorithm 4. We prove the performance of this algorithm in Theorem
Apart from improving the accuracy parameters, also provide modifications to algorithm that can achieve low rounds adaptivity (roughly speaking, it means the number of times the algorithm needs to look at the sample set). More formally, in our access model, define one round of adaptivity
as follows: The algorithm selects a set of t = O(n²) pairs of indices (ie, }e))e()) and query all Wi (H,)) at once. The number adaptivity rounds represents the total count times the algorithm needs to repeat this process in order to produce its final output. This is particularly interesting when considering federated learning setting in which the rounds interactivity are important. The modification of our algorithm runs in time O(n runs in ((1/A) rounds of adaptivity.
Theorem 6. Suppose Algorithu 4 receives these parameters as input: a E [0, E 1). Also, assume the algorithm has access a class of hypotheses H. and a set of unmarked hypotheses in Q C H where initially Q 3=H. H. Suppose the algorithm can query ú (H,)'s with error at most S <//6. The algorithm has one of the two possible outcomes: either it declares that < OPT; or it outputs a hypothesis H; such that: with probability at least we have:
(0, 1/4). e,
A -Pllvv S 4 max (o, OPT) +E.
The algorithm runs in O(n/n: /n Tg) time and O (105)))(n)) rounds of adaptivity. Here T is the time required to obtain each 0y (H.).
22

---

Algorithm 4 finds hypothesis that is 4 max (a, OPT) + close to P.
1: procedure SELECT-HYPOTHESISCA Q, a, e, 8, 17. and query access to wH (H,)ss
2: if Q = 0 then
3:
return "a < OPT".
4: if Q 1 then
5:
H₁ f- the only unmarked hypothesis left.
6:
if (H,) > a + then
7:
return "a OPT".
8:
else
9:
return Hi,
d' - c/6
8" 6/ (100- (1081/(2n(())) (10g)((00))
12:
m Ln
13:
Run FIND-SEED(H, 2, 0, c,, 8" 11
14:
if FIND-SEED declares "0 < OPT" then
15:
return "a < OPT".
else if FIND-SEED returns "start over" then
17:
return SELECT-HYPOTIEESS////
2, σ, e, 6, 1))
18:
H. < the seed that FIND-SEED found.
19:
while m > 1 do
20:
Run BOOST-SEED(H,, Q. H,, a, x= A' = e', n)
if BOOST-SERD finds the final answer. then return H, found by BOOST-SEED.
22:
else BOOST-SEED finds a new seed then
24:
H; the seed that BOOST-SEED returns m f [n-mm]
25:
26:
else if BOOST-SEED returns "start over" then return BELECC-HYPOTHESIISAA Q, 8, a, e, 8)
27:
28:
He < arg M.M WH;))
b M denotes 4otse
29:
if (He) 20 + then
30:
Output He.
31:
else
32:
Output H4:
Proof. For the sake of argument, assume each of the sub-routines in the algorithm works as guaranteed with prohability (as oppose to the where they work expected with probability 1 8"). Later on, we discuss the overall confidence of the algorithm to remove this assumption.
Accuracy of seeds: the procedure to find the initial seeds provides us with (a + (', 3.30 3e', m)- seed with high probability. Using Fact C.4, this seed is also t2 40 m). In boosting seeds, start with (2 e', 4 5e', m) and get (2 + e', 4 + -e',,,,,, .mm) where m [n-m]] This statement is justified by Theorem 9, setting K n' = 2, and using the same values for a = 2, o + and 4. + 5e' for our seeds. is worth noting that the only parameter that changes while boost is m.
Accuracy of the output Consider the case where we produce output when [Q] zero. That implies that our algorithm marked all the hypotheses. Throughout the course of algorithms, we never mark a hypothesis H, unless we have found an evidence that H, Plliv > a. This was established by observing ui (H;) > + e', which implies HH; Pl must be greater than σ: Or, showing close-by hypotheses to H; far from P and apply triangle inequality. See our argument for Case 3.2 in the proof of Theorem 9 for example. Thus, if all hypotheses are marked, it must be the case that for every H. || H, Pl[Tv is greater than a. Hence, when the size of zero we can truly assert. that "a < OPT".
23

---

For the case that [Q] 1, the algorithm focuses on H, the only unmarked hypothesis left. If we found (H.) is greater than +e', can simply conclude that for every H,, H, TV is greater than o, and < OPT". Otherwise, using Fact C.3, the H; is a valid answer:
H Pl 2 (H.)) + 2OPT S (HH) + 2OPT max (o, OPT) 2c'.
In addition, the accuracy of the H; that is returned in Line 22 is guaranteed by the Theorem 9, and setting 6 = k' = 2. Next, lets focus on the hypotheses we output after the "if" condition in Line 29. When W (He) small, we have:
HHryP & ((H))+0PT ((H))+ & 20+22' < max (o, OPT)
When W (He) is large, the analysis is very similar to Case 1 in the proof of Theorem 9. Again, by setting x' = 2, and using the facts that W(H)) - 2 n'a and W S (N + 2) 5e', obtain:
11 PlITv s 4 max (a, OPT) + 6é'.
Number of recursions: Given Theorem 8 and Theorem 9, we only see "start over" when (1 - 2n) fraction of unmarked hypotheses in Q have been marked. Since we have hypotheses, do not start over more than O(log1// (n)) times.
Running time: In the while loop, m decreases with factor of 17 every time we find new seed. Hence, the total number of iterations is bounded by (logg (n)). Using Theorem 8 and Theorem 9, invoking the procedures for finding seed and boosting seed each takes ((nlog(n/8" / TT) time. Thus, the total time complexity is:
Th (" (1-(log(n/0)) + log logi (n)) logi/, (ig)TT)) = -m))
o
1og(1/6) Tg (o- -00
Overall contidence parameter: The total number of subroutines we call here is at most Ologi)/,(m) (n)). Thus, by setting 8" to O logi;,,(1) (n)) and using the union bound, we show the overall error probability is bounded by 8.
Rounds of adaptivity: Using Theorem and Theorem invoking the procedures for finding a seed and boosting seed each takes O(1) rounds of adaptivity. Hence, the overall rounds of adaptivity is O [oggi/,()) rounds.
Remark 7. One could argue that we have demonstrated the algorithum operates in (n//n Ty) time with a probability of 8. However, this fact does not inherently guarantee that the algorithm consistently maintains the desired time complexity. Fortunately, a straightforward solution exists to address this concern.
Our algorithm may fail for two primary reasons: either too few hypotheses were marked, or the identified seed had a larger m value than anticipated. In either scenario, the algorithm can verify the occurrence of this undesirable. but improbable event. In these situations, we output 1 to indicate the algorithm's 's failure to produce a valid answer. With this adjustment, the time complexity remains low desired.
Corollary B.1. Suppose H a class of known hypotheses and P is an unknown hypothesis. Let and 8 be two parameters in (0. 1). Assume the algorithm has access to accurate estimates of ú (H,) that have error at most é'. 3f S. e, then for every 1 E (1/n, 1/4) there exists an (a = 4, 6)- proper learner for P in H. The rumning time of our algorithm is ((nn/r) log(116) log(1/e) Tg).
and it can implemented O (log)),(1) log(1/e)
rounds of adaptivity.
24

---

Proof. This is direct corollary of Theorem 6 combined with binary search over values of a {c', where e' e/ c/100. Note that for every OPT, the algorithm has to produce a hypothesis. since it cannot declare OPT < with high probability. Outputting the hypothesis associated with the smallest would give us the desired guaranteed.
B.1 Finding initial seed
In this section, we describe an algorithm that receives parameter o as input and finds (or é', 30 2d', in seeed in roughly O(nnn TT) time with high probability or declares "a < OPT".
Algorithm 5 finds (ar + c', 30 + 3c', mee-
1: procedure SEED(,, 2, a, e', ò, and query access to ú (H,)'s
2: f Ln.n1] n
3: for ,,...,72 do
4:
repeat n log (2n/5)/a /m] times
5:
H, < a uniformly random sample drawn from H.
6:
if r0 H4;) > Mark H, in Q.
then
7:
8:
H3 + a uniformly random sample drawn from Q
9:
if (w,((1)) > + then
10:
Mark H, in Q.
11:
if [ S for every H2 E Q do if (H,) > a + then
then
13:
15:
Mark H; in Q. if H; is unmarked. then Compute (H.). if (H,) + 3 then return H, as seed.
16:
17:
18:
20:
else
for H, E H do if w; (H₂) a + or () S + then Mark H, i
22:
23:
24:
return "Start over."
return "o < OPT".
Theorem 8. Suppose that we are given a class of hypotheses, H. a rate parameter yj E (0, 1/4), two parameters or, & (0, 1). and have access to (H.) with error most è' for every i, [m]. Algorithum queries O (n log(n (n/g(n//))))))))))))) /m)) many w. (H,)) and runs in O ((n (og(n/5)/n) i)) TTy) time. Also, it can be implemented in O(1) rounds of adaptivity. This algorithm returns hypothesis He, declares a < OPT, or returns "start over" for which the following guarantees hold with probability
1 6:
Iʃa 2 OPT, then the algorithm does not declare that is less than OPT.
If the algorithm returns a hypotheses H& then Hę is a (a e', 30 + 3e', m)-seed where
m = [n
If the algorithm returns "start over." with probability 8, it marks (1 - 2n) fraction of the hypotheses in Q
Proof. Our first claim is that if is at least OPT, then we do not declare otherwise. This is due to the fact that the discrepancy between H,- and on any subset of the domain, including the Scheffé sets, will not exceed OPT. Hence, (H,-) is at most OPT + +e' < a e', and we will not mark H;- in Line 7, Line 10, nor Line 15. That is, for at least one hypothesis, i.e., H,,, the "if" statement in Line 16 holds. And, we return seed or "start over." (And, will never reach Line 25.)
25

---

Next, we show that if the algorithm outputs H,, then it is a (a + 30 + 3c', m)-seed with high probability. First, observe that W (H)) must be at most 3 + 3'' due to the "if" condition in Line 18, satisfying one of the two conditions we need for our desired seed in Definition 3.1.
Now, we show the next required condition for H; to be a good seed holds as well: 3o (H.)) I m. This condition requires that the number of H2 's in H for which (H.) is in (o +é, 30 + 3e') is bounded by m. We have already established that tēş (H.)) for every j E [n] is bounded by 30 + 3' since (H,)) is most o + 3c.. Hence, only need to show that there are at most m hypotheses Hj such that w,(H, (H)) is larger than o +e'.
Now, if there are more than hypothesis Hj in H such that (H,HH.) > a + E'. Now, if we sample t = [8 n log (2n/5) /m] hypotheses, we should observe at least one H, for which uy (H,, is larger than a + e', with probability least 1 - 62n). However, we know that such hypothesis was never observed because we did not mark H; earlier. By the union bound, with a probability of at least 1 1-8/2, such H; exists. Hence, with probability at least 1 - 8/2, H, is an (a+t', voee,34t2 + m -eeds as promised in the statement of the lemma.
Next, assume we output "start over." after finding an unmarked hypothesis H;. In this case, we know that H; is not marked and (H.) > 2a + 3e'. Note that we have sampled l edges of H,, and we never see wy (H,) > σ + e'. Using a very similar argument as we have above: one can show there cannot be more than m' = In |Q] for which wy (H2)
+ e' with probability 1 /22 (for every H.). That means, we will mark [ m' many hypothesis in Q. If ||] > 2 1/n, this implics that (1 2n) fraction of the hypothesis in Q are removed. If Q S t, then we know all the hypothesis in Q have (H.)H.) S a + é' and all of them will be marked.
Furthermore, we show that we did not wrongfully mark a hypothesis that was a-close to P. Observe that the condition in Line 22 holds in two cases:
Case 1: (H:(H)) > a e'. is straightforward to show that Hj is not a-close to P since we have:
||, P 2 wx,H)) 2 w; (H₂) - >0.
Case 2: w; (H₂H So+é and (H,) <o Even though uy (H,) is small in this case, we can indirectly deduce that H2 is not a-close to P. By the definition of vy (H.) and (H₂)) we have:
[H, H1lliv (S.,) - Hy (S.,)) < H (8.,) - P - (S H2 (8
(H;) + u. (H:) S w; (H₂) + (H.) + 2e' 20 + 2e'.
On the other hand, by the triangle inequality, we have:
IP - Hylliv 2 P H 1|Tv - H - H2lliv 2 W(H)) - 11 H 11
> (H.) - - || Hy l|v > 30 36' -é' -22 + 26') a
Therefore, in both of the cases above, we do not mark an o-close distribution to P.
By the union bound over all the steps, our guarantees hold with probability 1 1- 8. In addition, it is not hard to see that the running time of the algorithm is O ((n t + n) -Tg) = O( (log(n/5) -T/n)) time.
Rounds of adaptivity: It is straight forward to show that this algorithm can be implemented with constant round of adaptivity. Let Qo denote the initial state of unmarked hypotheses at the algorithm's 's outset. Since hypotheses are marked in sequence, in round i, the set of unmarked hypotheses is Q == 2o n H,, H Hn, As a result, we can agree on the set of random H2 in Q and 71 and request ú (H,) within single round. If the size of IQil is at most t, then we include all úū (H,) for every E n and H2 E Q. Next, upon discovering an unmarked H;, we initiate another round of adaptivity request all (H.:) and w (H.) for all j E [m]. This enables the implementation of the rest of the algorithm.
26

---

B.2 Boosting a seed
In this section, we provide an algorithm that receives (Ko [K + 2) +5', -e)-sedd and aims to find (x' o + c', (N<' + 2) 5c', m') -eed with smaller m'. That means, the size of M for this new seed is smaller which brings us closer have enough time to fully investigate the set M for future seed. Our algorithm runs in Ó(n Tg/ ni) time where 1) mí/m is our rate parameter. This running time adaptive to our budget. we are aiming for (n) algorithm, we find a seed such that m' is only smaller than by constant factor (constant 7)) Alternatively, if we have more time, can decrease m' with a faster rate (smaller 17).
While our main goal is to find better seed, our algorithm may not always be able to do so; However, makes progress towards the end goal of the algorithm one way or the other. There are three possible outcomes for our algorithm:
1. The algorithm finds an accurate enough H as the final output of the algorithm.
2. The algorithm finds better seed aimed for.
3. The algorithm marks (1 - 21) fraction of the unmarked hypotheses; And after that, we start over the procedure.
Although we may have regressed in last case above, it does not happen too often. Since we have only unmarked hypotheses to begin with, and we marked a large fraction of them every time, we do not start more than ( (n)) times over the course of the algorithm. Our approach is presented in Algorithm 6, and we prove its performance in Theorem
Algorithm 6 aims to find better seed.
1: procedure BOOST-,EED(H, 2, Hi, o, H. K', e', ö, 17 and query access to (H:)ss)
2: m' <- [y ml
3: + 8 log (2n/6) /mm1
4: for H2 M do
We denote Micatte (c+2))+55 (H,) by M.
5:
WH;) + COMPUTE-W(HH, Q, H,,
6:
He + arg min WH,,)
7:
if (He) K σ + e' then
8:
Return H; as the final answer.
9:
else
10:
Compute (H²). if (He) S (k'' +2) + 5 then
12:
Return H, as a seed.
else
14:
for H, E H do if (y (H;) > a + or w (Ha) S n' then Mark H2 in Q.
16:
return "Start over."
Theorem 9. Suppose Algorithm 6 receives these parameters input: E R20 R R'' 1, (0, 1/4), e', 8 E (0, and two non-negative integers n, m. Also, assume the algorithu has access a class of n hypotheses H. and set of unmarked hypotheses in Q C H. It also receives hypothesis H; E H. The algorithm has one of the three possible outcomes listed below. Now. for any setting of such imput parameters, H; is (R + + guarantees hold for the outcome of Algorithm 6 with a probability of at least 8:
c', (N 2) 5e'', m)) seed, then the following
1. If the algorithu outputs hypothesis il as the final answer, then we have for every 2 6e':
x
| - -Pllv S max K +
rd +2) max (a, OPT) +
2. If the algorithm outputs hypothesis Hg as a new seed, then H3 is (K' o + 6,, (K' + 2)a
5e', é m mn')-seed where m' == [mm]..
27

---

Algorithm 7 computes W (H.).
1: procedure COMPUTE- WHL Q, H;, i, and query access to di (H,)'s
2:
W t 0
3: repeat times
4:
Hj + uniformly random sample drawn from H
5:
W max W, úi (H.)H.)
6:
Hj + a uniformly random sample drawn from Q
W f max (W, (H,)
7:
8:
9:
if Q < then
10:
for all H2 Q do
11:
W + max (W, úh (H,)
12:
Return W.
3. If the algorithm requires us to start over, then we have marked at least (1 - 2n) of the unmarked hypotheses.
The algorithm runs in O(n (log(n/6)) Tg/n) time and can be implemented in O(1) rounds of adaptivity.
Proof. Let M denote the set ( (x+2))+5 (H:). We consider the three possible outcomes of the algorithm, and prove the algorithm satisfied the desired guarantee in each of the three cases.
Case 1: WHe) > N' In this case, the algorithm will return H, the final answer. We show that the total variation distance between H; and P is as desired. There are two possibilities depending on whether Hip is in M or not.
Case 1.1: HІ- E M. Using that Hę has the minimum WHe) among all the hypotheses in M, can bound OPT as follows:
K'o. We prove that H, not too far from P. Note that since H, was an (x + é', (x 2) 5 m))-eed, we are guaranteed that W (H;) is bounded by (N + 2) o + 3e'. Using the above bound for OPT and Fact C.3, we get:
OPT 2 W(H+) 2 -
W
H, PVITV I (H,)) + +2PT S W(H)) + 20PT S (K + 2) a + 6 + 2OPT
+2 OPT +66 ( +2 max(o OPT) +c.
<
Case 1.2: H₃. & M. Since H, is (RT + c, (n 2) 5 m)--eed, ú; (H,) is bounded by W(H) S 22) + 5e'. Now that H,- is not in M, it must be the case that w;-- (H,) is bounded by K + 6'. In this case, we have the following bound for the total variation distance between H, and via Fact C.3:
||, PliTv I wi- (H.) + OPT < wx. (Hi) +e' 20PT SKO 22-+22+20P I (R + 2) max OPT) +e.
Case 2: (H+) Sk'Ot' and (He) S (N' + 2) +5'. In this case, we output H, as new seed. Given the assumptions of this case, we show that Hi, is a (K' a e', (k' + 2)a + 5 5e'mm') seed. First, W(+) is at most (w' + a 5e' implying the first desired property for being an (K' + é' (w' + 2)ar + 5,'', "ee.m'))sse m')-seed holds for Hg. Next, we show the second desired property for Hg the size of My ote' (#+2))+5e (He) is bounded by m'. At high level, we expect the size of
28

---

this set to be small; Otherwise, we would have observed one of these large dh (H,H)) when we have sampled hypotheses to compute W (Hte).
Suppose He has more than m' edges with (HtH) > rt' a + c' Now, we sample = [8 n log (2n/6) /m'] hypotheses, we should observe at least one H, for which wy (Hz) is larger than n o + c', with probability at least 6/(2n). However, we know that such a hypothesis was never observed because W (He). which the maximum of úū (Hy)"s ss is bounded from above by k' + , By the union bound, with probability of at least - 6/2, no such He exists. Hence, with probability at least 1 - 6/2, He is an (K' a + +e' (K' + 2) a + 5e', m' m')--eed as promised in the statement of the lemma.
Case 3: (He) S o + e' and WH)) > (w' + + In this case the algorithm marks any unmarked hypothesis H2 for which wy (I,) > o + or (H( S K' a + e', and we start over. First, we show that we did not wrongfully mark hypothesis that was a-close to P. Observe that the condition Line 15 holds in two cases:
Case 3.1: (bz > + é'. It is straightforward to show that H3 is not a-close to P since have:
H Pl wx)() 2 (x(H))) - >0.
Case 3.2: (H,) So and e S o Even though we (H,)) is small this case, we indirectly deduce that Hj is not c-llose to P. By the definition of tūy(H)) and (b,(H,), we have:
- He H, (He H, (8L,)) S HH (St,) P - we(Hl + w, - we (H1, + (H)())) 2 Sko
H, (St.))
On the other hand, by the triangle inequality, have:
[P - Hyllry 2 ||P Helltv - |He Hylliv 2 W(H)) - HellTv
2 (H,) - ||H HşllTV (K' + 2) - ((k' 1) - 16') =
Therefore, in both of the cases above, we do not mark an a-close distribution to P.
Second, claim that mark at least (1 1)) fraction of the unmarked hypotheses in Q. Recall that when we compute W (H)) we also sample hypotheses from the of unmarked hypotheses, and we did not observe any edge w. ( H2) that is larger than K' a +e With a very similar argument we had 8/mmn), we do not have more than m" == [ [2] m/nl < [Tp IQ1 hypotheses in Q such that (H2) > k' a + e'. Otherwise, we would have seen one of these edges, and (H+) would have been larger. By the union bound, this fact holds for every Hy. Hence, the "if" condition Line 15 holds for over [ - [Ty. 1Q]] of the unmarked hypotheses in Q, and the algorithm mark them. If [ 2 1/17. it is easy to show that Q [1] |Q is at least (1 2 2n) . 12). Thus, we mark at least (1 - n) fraction
above, with probability
the hypotheses in Q as we have claimed. Now, QQ < 1/n, it is easy to show that IQ] t. Hence, the algorithm involves all the H, 's in Q to compute W (He). Therefore, every single w (Hę) at most N' + c' and we mark all the hypotheses in Q.
By the union bound over all the steps, our guarantees hold with probability 1 1- 8. In addition, it not hard to see that the running time the algorithm is O ((m L ++n, n) TT) = O(n (0log((8))) TT/1) time.
Rounds of adaptivity: Our algorithm can be implemented in constant rounds of adaptivity. To compute W's, we can preselect the random H, ss If Q contains fewer than +++1 hypotheses, we include every (H,) (H,) for each H, E Q and E [n]. Upon discovering H;, another round of adaptivity allows us to query every wy H2)) and ue HH)) to calculate (He) and mark the hypotheses in Q.
29

---

C Preliminary facts and lemmas
Fact C.I. For all distribution P and for all probability event & defined under P. we have:
| Pellay = -1-1
where Pe denotes the probability distribution P when conditioned on the event E.
Fact C.2. For every pair of distributions H; and H. we have:
||4 -1fl-l |1 (Sig) H1 (St)))
The following fact is adapted from [DL01, MS08, ABS23].
Fact C.3. Suppose H;- is the closest hypothesis P H(i.e., |H - Pl) For every pair of hypotheses H; and H. the following holds:
1. H; Pllrv S wyHH) ) H Pllzv,
2. |H Plitv S wi- (H.,) (H,)+ 20PT,
3. |H; Pllvv (H)) 2OPT.
Proof. The proof is based on triangle inequality, and the definitions of wy (H,)'s and OPT. For every H, in H. we have:
[H Pl[tv < || H1Il-V
Pl HH (81,) H3 (8t,)) + || Pl[tv
- [1,
P(..)) (1 (H.) + (H,(H) ||, Pl|Tv
H1 (8ta)) + |H - P|[TV
S (H.). + -
Hence, Item is proved. Now, if we set Hj to His then |H,-- Plltv equal OPT implying Item 2. Item 3 is concluded from Item 2 and the fact that wi- (H;) is upper bounded by (HH.)). O
Fact C.4. Suppose we are given six parameters u, b, a' V E R20, and m, m'' E Zzo Ifa S a',
b < b', and m I m', every (a, b, m) -eed is also (a', b', m m')-seed.
Fact C.5. Suppose we have a set of hypotheses H. and a predicate, R(H) 7 {0, 13, that maps the hypotheses in H to zero or one. Assume H contains more than hypotheses with R(H)= for an arbitrary integer parameter S m < n. If we draw s 2 8n log( (a(00-1//m hypotheses from H uniformly random, we will observe least one hypothesis with R(H)- with probability at least 1-6 8.
Proof. Let p denote the fraction of such hypothesis H with R(H) 1. Observe that p since there are at least m + 1 such hypothesis in H. Then, using the Chernoff bound, we have:
Pr(r = 0] < Pr
sp
= Pr
r
<
1
1
2
2
8p)
8m
S exp
< exp
S
8n
D Data structure for marked and unmarked hypotheses
Here, we describe simple data structure that allows us efficiently keep track of marked and unmarked hypotheses. Our data structure consists of two integers, and t, and two arrays of size n: index and list []. Here, n represents the number hypotheses that the data structure supports. The list array is an arbitrary ordering of integers from to n. Throughout the operations of this data structure, we preserve the following guarantee: the value of index [i] indicates where to find element i in the list. In other words, list [index [i]] is always i. The integer t serves threshold quantity. The first numbers the list correspond unmarked hypotheses, while the remaining numbers represent marked hypotheses. Initially, list is list of integers from to in
30

---

ascending order. And, for every hypothesis H,, index [i] is set to i. This data structure supports the following operations:
Initialization ds (size): To initialize the data structure, we set n and to size. Next, we set 1ist to be a list of integers from to n in ascending order. To ensure consistency with the list, each index [i] is set i.
mark (i): To mark hypothesis H, swap the element index i with the element index t in the list array, and then decrement t by 1.
1..aaredd (i): Given our definition, if index [i] less than or equal to t, then H4 unmarked; otherwise, it is marked.
is_all_marked (): If t is equal to zero, then it means all the hypotheses are marked.
random_ uandom_ummarked (): To select random unmarked hypothesis, we generate a random integer r between and t, and output the hypothesis at list [r].
random_marker marked (): To select a random marked hypothesis, we follow the same process as for an unmarked hypothesis, except that r is generated between t+1 and n.
is easy to see that the initialization takes O(n) time, and the rest of the operations only take O(1) time.
31

---

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 results are theoretical contribution to the field of learning theory. The paper, including the appendix, contains all the algorithms, theorem statements, and their proofs.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in 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 be expected to generalize other settings.
is fine 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 see the discussion in Section regarding potential improvements and future directions.
Guidelines:
The answer NA means that the paper has limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect the scope of the claims made, e.g., if the approach was only tested on a few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low or images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full of assumptions and complete (and correct) proof?
32

---

Answer: [Yes]
Justification: We have clearly stated our model and our assumptions. All the proofs are included in the appendix.
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:
We do not have any experimental results.
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
33

---

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:
We do have any experimental results.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nips. cc/
Miblii//uuddes/CdeSuubbae sosoodeessmmssssoooooooor 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/ppblicc/eeeccc ceaiiic/guiesss /CodeSubmi ssi egionPolicy) 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:
We do have any experimental results.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can provided either with the code, in appendix, or as supplemental material.
7. Experiment Statistical Significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [NA]
Justification:
We do not have any experimental results.
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.)
34

---

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:
We do not have any experimental results.
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 NeurlPS Code of Ethics https h/r//erurip.../ httppplic//tiiscciiddeeeee
Answer: [Yes]
Justification: Our results are theoretical formulation of fundamental problem in statisties and learning theory. They can be viewed as computationally efficient version of cxisting results. Given the thcoretical nature of our findings, do not anticipate any harm society.
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).
Broader Impacts
Question: Does the paper discuss both potential positive socictal impacts and negative socictal impacts of the work performed?
Answer: [NA]
Justification: Given the theoretical nature of our findings, we do anticipate broader societal impact for this paper.
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.
35

---

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:
We do not have any experimental results.
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: We did not use any existing assets, other than the publicly available articles that we have cited.
Guidelines:
The answer NA means that the paper does not 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.
36

---

If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswi thcode. www.coo//aaooooo datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if has changed) should be provided.
If this information not available online, the authors are encouraged to reach out to the asset's s creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification: The contributions of this paper theoretical. As is standard in the field, will make our results publicly accessible and do not anticipate generating revenue from them.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/model as part of 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 is used.
At submission time, remember anonymize your assets (if applicable). You can either create an 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 as details about compensation (if any)?
Answer: [NA]
Justification:
We do have any crowdsourcing experiments nor human subjects.
Guidelines:
The answer NA means that the paper does involve crowdsourcing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included 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 (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: We do not have any experiments involving crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsoureing nor research with human subjects.
37

---

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 as the institution conducting the review.
38


Reviews:
[{"review_id": "UgGoWSUhZI", "reviewer": "Reviewer_fMmw", "summary": "This paper looks at proper distribution learning: given samples from\nsome distribution p, and a set of n candidate distributions H_i,\noutput one H_i that is close in TV; in particular, alpha * OPT + eps.\nSurprisingly, this is possible with a sample complexity independent of\nthe domain size (as would be needed to actually estimate the TV).\nThere's been a long line of work aiming to improve the approximation\nfactor alpha.  alpha = 2 is possible for *improper* learners, but\nproper learners can only hope for alpha = 3.  Getting alpha=3 in n^2 s\ntime is known; this paper gets that down to O~(ns) time (although an\nextra eps factor in time, which they can avoid for alpha=4, and worse\ndelta dependence).", "questions": "Are there applications of hypothesis selection where the constant alpha matters?", "limitations": "Fine.", "rating": 6, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "It gives much better running time for a natural problem.\n\nThe approach is fairly clean.", "weaknesses": "The algorithm overview is a bit vague, and could be written more\nclearly.\n\nThe failure probability dependence isn't good.\n\nThe alpha=3 approach is a fairly simple extension of prior work, and\nalpha=4 isn't so exciting.\n\nI'm not sure that the constant here matters for the applications of\nhypothesis selection.  Like, in the application where we choose a\ncover for the class, presumably we can just make a finer cover?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**Presentation**\n\nThank you for your feedback regarding the presentation of our paper. Our overview was intended to provide a high-level description of our algorithm to avoid obscuring the main technical ideas with detailed specifics. We will certainly focus on enhancing the clarity and quality of our write-up in future versions.\n\n**Novelty of our techniques**\n\nThe essence of our first algorithm indeed stems from the minimum distance estimate [DL01]. However, the primary challenge we faced was implementing this approach in linear time. Specifically, it is not feasible to compute the maximum semi-distances, $W(H_i)$, for all hypotheses in linear time. To address this, we developed an efficient and advanced method to estimate these values by taking the maximum over a small subset of semi-distances, while ensuring the algorithm's correctness. This approach allows us to achieve an algorithm that runs in (almost) linear time in $n$.\n\nOur second algorithm is completely novel to the best of our knowledge. It achieves the desired time complexity (up to logarithmic factors) with $\\alpha = 4$, an accuracy parameter that surpasses all previously known results. Our work introduces a novel algorithmic approach to this problem, marking a significant departure from existing techniques. We hope these new ideas will inspire future research.\n\n**Dependency on $\\epsilon$ and $\\delta$** \n\nPlease see our global rebuttal. \n\n\n**Applications of hypothesis selection**\n\nDensity estimation is a fundamental problem in statistics, with hypothesis selection being an important special case. It involves choosing the best distribution from a set of known models that represent potential underlying data distributions. For example, this set might include Poisson and gamma distributions with various parameters to model the number of arrivals per time unit. This technique is applicable in areas such as denoising, anomaly detection, selecting interpretable data distributions, strategy selection, and more.\n\nThat said, we view our results as a fundamental theoretical tool. Hypothesis selection has been instrumental in learning structured distributions (e.g., learning mixture of Gaussians [DK14, SOAJ14]). For additional references, see Section 1.3. Another significant aspect of hypothesis selection is its agnostic nature, allowing for learning even when the unknown distribution is not within the considered class. Hence, hypothesis selection is applicable even when data is noisy.\n\n\n**Addressing the importance of improving $\\alpha$ by a constant factor**\n\nIn most learning algorithms, the error guarantee decreases polynomially as the number of samples increases, so constant factors may not be as crucial. However, this is not the case in hypothesis selection. The output hypothesis is guaranteed to be $(\\alpha \\cdot OPT + \\epsilon)$-close to $P$ in total variation distance. While increasing the number of samples can reduce $\\epsilon$ to negligible levels, it does not improve the term $\\alpha \\cdot OPT$. $\\alpha$ is an inherent property of the algorithm and directly impacts the best achievable error guarantee. Therefore, even a constant improvement in $\\alpha$ is significant.\n\nSome may argue that focusing on improving $OPT$ is more beneficial than refining $\\alpha$. For instance, in the cover method (as you mentioned), using a finer $\\gamma$-net can ensure that $OPT < \\gamma$. However, this approach can drastically increase the algorithm's running time, as the size of the net can grow super-polynomially with $\\gamma$. For example, in the case of mixtures of $k$ Gaussians, the dependence of the net size on $\\gamma$ is roughly $O(\\gamma^{-3\\cdot k})$ (see [SOAJ14]). Thus, reducing $\\gamma$ by a factor of three could increase the size of $\\mathcal{H}$ by an exponential factor in $k$, and consequently, the running time, leading to an inefficient algorithm.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "SM2DuqXL6i", "reviewer": "Reviewer_Zrpk", "summary": "This paper introduces proper approximation algorithms for optimal hypothesis selection in the context of distribution learning.\nThe first algorithm achieves an optimal approximation factor of $\\alpha=3$ in time approximately linear in the number of hypotheses. The second achieves the slightly looser $\\alpha = 4$ approximation factor in exchange for significant reduced dependence \non $\\epsilon$ and $\\delta$, the standard learning parameters governing the error and confidence of the learning algorithms. The paper focuses on explanation of the algorithmic techniques involved.", "questions": "-Table 1: Is the dependence on $1/\\delta$ in $s$ just the standard $\\log(1/\\delta)$?  \n\n-line 180: The order of logical quanitifiers can be reversed to get a slightly stronger and more illustrative statement here, correct?  \n \n-line 240: It seems that to do this random sampling to decide if you have a prompting hypothesis, you need to check a number of hypotheses which is proportional to $1/\\delta^2$. I guess there is a naiver version of this algorithm which just checks all of the hypotheses at this step, incurring some quadratic dependence in $n$. Am I wrong in feeling like any sort of search for something like a promping hypotheses will always incur some sort of undesirable multiplicative interaction with $n$?", "limitations": "Yes", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 1, "contribution": 3, "strengths": "The paper introduces a novel learning algorithm for optimal approximation (Algorithm 1) which achieves a significantly reduced dependence (quadratic to near-linear) on the number of hypotheses in the hypothesis class in the computational complexity. This is notable given that the problem has been studied for a while, and practical, given that distribution learning over a discrete space requires a number of samples at least proportional to the cardinality of the domain on which the hypotheses are supported.", "weaknesses": "I found the writing to be unpolished, and not publication-ready. Much of the body attempts to furnish intuition to the algorithmic techniques introduced, but some portions seem underdeveloped, and occasionally read like direct translations from math to spoken language (e.g. line 358). For example, an extremely important concept in this paper (introduced in important prior works) is that of ``semi-distances'' $w_i(H_j)$. Seemingly the best intuition the reader is provided with regarding this concept comes at line 176: \"One suggestion for readers to internalize the semi-distances is to view them as a distance between $H_i$ and $P$ that is measured from the perspective of $H_j$\". I think this deserves more illuminating wording, and personally got a much better understanding by staring longer at the definition. Overall, I think the lack of attention to writing is somewhat a shame, as there seems to be a lot of nice algorithmic thought here which deserves a better exposition in my opinion.\n\nOn a more technical level, the dependence in the computational complexity of Algorithm 1 on the learning parameters $\\epsilon$ and $\\delta$ is heavy -- these enter as $1/\\delta^3\\epsilon^3$. One would really hope for something like $\\log(1/\\delta)polylog(1/\\epsilon)/\\epsilon^2$.  It seems there will be many regimes in which the guarantees of Algorithm 1 -- despite the linear dependence on the number of hypotheses -- will be looser than the quadratic algorithm of MS08.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**Presentation:**\nThank you for your feedback regarding the presentation of our paper. Our overview was intended to provide a high-level description of our algorithm to avoid obscuring the main technical ideas with detailed specifics. We will certainly focus on enhancing the clarity and quality of our write-up in future versions.\n\n**Dependency on $\\epsilon$ and $\\delta$:** Please see our global rebuttal. \n\nBelow is our answer to your questions:\n\n- In Table 1, for [ABS23] the dependence on $\\delta$ is $1/\\delta$, while for the rest it is $O(\\log(1/\\delta))$ (or unspecified by the authors).\n\n- Correct. There exists an $i^*$ such that for every $H_i$, $w_{i^*}(H_i)$ determines the quality of $H_i$.\n\n- Correct. To ensure that a random hypothesis in a bucket is not too far, with a probability of $1-\\delta$ in a single round, we have to sample $O(\\log(n)/\\delta)$ hypotheses and check if $H_{i^}$ is prompting them. Or, we can try all hypotheses in the bucket. Hence, relying on this structural property of $H_{i^*}$ makes a polynomial dependency on $\\delta$ inevitable. We speculate that improving the dependency on $\\delta$ for this algorithm would require new algorithmic ideas. The main difficulty here is that there is no (known) general technique for boosting the confidence parameter while keeping $\\alpha$ the same. In many settings, the success probability of a learning algorithm can be amplified from a constant, say 2/3, to at least $1-\\delta$ at a cost of at most $\\log(1/\\delta)$ in running time and sample complexity. However, in hypothesis selection, choosing the best output from several runs of a given algorithm requires executing a second hypothesis selection algorithm, which introduces another factor of $\\alpha$ in the approximation—leading to a total factor of at least $9$. As a result, these kinds of two-phase algorithms are not sufficient in the low $\\alpha$ regime. Some previous results, such as [ABS23], also suffer from a polynomial dependency on $\\delta$. Our second algorithm circumvents this polynomial dependence at the cost of a slightly worse accuracy parameter $(\\alpha = 4)$.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "dyHzTW9SsU", "reviewer": "Reviewer_URPo", "summary": "This paper studies the hypothesis selection problem, where given a set of candidate distributions $\\mathcal{H}=\\{H_1,\\dots,H_n\\}$ and samples from a distribution $P$, the learner wants to approximately select a distribution $H_i \\in \\mathcal{H}$ such that $||H_i-P||_{TV} \\le \\alpha opt+\\epsilon$ for some constant $\\alpha$, where $opt$ is the TV distance of the closest distribution in $\\mathcal{H}$ to $P$. Information theoretically, $\\alpha=3$ is the optimal constant one could achieve with optimal sample complexity $s=\\log n/\\epsilon^2$. Previous efficient algorithms either have a running time that has a bad dependence on $n$ or run in nearly linear time but achieve a suboptimal approximate factor $\\alpha \\ge 5$. In this paper, the authors design an algorithm that achieves the optimal approximate factor $\\alpha=3$, with running time $\\tilde{O}(ns/\\epsilon)$. This is the first algorithm that achieves the optimal approximate factor with a running time nearly linearly dependent on $n$. This paper also presents another algorithm that achieves an approximate factor $\\alpha = 4$ but has a better running time $\\tilde{O}(ns)$", "questions": "I only have one question about the model. It seems that the algorithms in the paper crucially rely on estimating the semi-distance defined based on the Scheffé set. But I believe in many applications it would be very hard to check whether an example falls into the Scheffé set of two hypothesises. For example, many learning algorithms might first improperly learn a list of candidate hypothesises and use hypothesis selection to select a good one. Computing pdf of these candidate hypothesises may not be realistic in general. Would it be possible to relax the dependence on the knowledge of the pdf of the candidate hypothesises in the model?", "limitations": "N/A", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "This paper makes progress on a fundamental problem, hypothesis selection. The two algorithms designed by the authors are highly non-trivial and involve many novel techniques. The paper is in general written well and gives a good intuition of why the algorithms work. Due to the time limit, I was not able to check the proofs in the appendix but given the discussions in the main body, I believe the results given by the paper are correct.", "weaknesses": "I want to give some minor suggestions. \n\n1. It would be nice to give some more applications or motivations at the beginning of the introduction. In the current version of the paper, the problem sounds mathematically interesting but lacks motivation.\n\n2. Since there is a long line of works that design nearly linear time algorithms for the problem. It would be helpful to give a brief review of the techniques used in prior works in the introduction.\n\n3. In line 327, I believe there is a typo in the equation $||H_{i^*}||_{TV}=...$", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your feedback. We will include the motivations and applications of hypothesis selection, as well as an overview of previous algorithms, in our paper. In this rebuttal, some applications of hypothesis selection are discussed in our response to Reviewer fMmw, for your reference.\n\nRegarding your question about relaxing the model, the short answer is yes; our algorithms remain effective with some minimal adjustments as long as approximations of Scheffe sets are provided.\n\nCurrently, in our paper, we compare the PDF of the known distributions, $H_i(x) > H_j(x)$, to determine whether $x$ belongs to $S_{ij}$, the Scheffe set of $H_i$ and $H_j$. However, this assumption can be relaxed if we can identify an alternative set $S'\\_{ij}$ that captures most of the discrepancy between $H_i$ and $H_j$. In particular, it is sufficient to have:\n$$\\|H\\_i - H\\_j \\|\\_{TV} \\leq (1+ \\Theta( \\epsilon)) \\cdot |H_i(S'\\_{ij}) - H_j(S'\\_{ij}) | \\,.$$\nEven with these imperfect sets, $w_{i^*}(H_i)$ is a good proxy for the quality of hypothesis $H_i$ (up to additive error $\\epsilon$). See the equations after Line 180 in the paper.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "X4fH9fr0yV", "reviewer": "Reviewer_reSf", "summary": "This paper studies the hypothesis selection problem: Given $n$ distributions $H_1, H_2, \\ldots, H_n$ and samples from an unknown distribution $P$, the goal is to output $\\hat H$ such that $\\mathrm{TV}(P, \\hat H) \\le \\alpha \\cdot \\mathsf{OPT} + \\epsilon$, where $\\mathsf{OPT} = \\min_{i \\in [n]}\\mathrm{TV}(P, H_i)$ is the TV-distance of the best hypothesis.\n\nIt is known that achieving a guarantee with $\\alpha < 3$ is impossible, if we want the sample complexity to be bounded by a function of $n$ and $\\epsilon$ (and not the domain size). Prior work gave various algorithms that achieve $\\alpha = O(1)$ (including some with $\\alpha = 3$), but none of them achieves $\\alpha = 3$ in near-linear time without making additional assumptions.\n\nThis work gives two improved algorithms. The first algorithm (Algorithm 1) achieves $\\alpha = 3$ in $\\tilde O(n\\cdot s / \\epsilon)$ time, where $s = \\Theta((\\log n) / \\epsilon^2)$ is the sample complexity. The second algorithm (Algorithm 4) achieves $\\alpha = 4$ in $\\tilde O(n\\cdot s)$ time.\n\nHere is an overview of Algorithm 1, outlined by the authors in Section 3:\n- Let $S_{i j}$ denote the subset of the domain that witnesses $\\mathrm{TV}(H_i, H_j)$. A simple argument shows that finding $i \\in [n]$ that minimizes the quantity $W(H_i) \\coloneqq \\max_{j \\in [n]}|H(S_{i j}) - P(S_{i j})|$ gives the $\\alpha = 3$ guarantee. However, the straightforward implementation takes $\\Omega(n^2)$ time to compute $W(H_i)$ for all $i \\in [n]$.\n- The actual algorithm maintains estimates on $W(H_i)$s (that always underestimate). These are grouped into $\\approx 1/\\epsilon$ \"buckets\", where bucket $l$ contains indices with estimated $W(H_i) \\approx l\\cdot\\epsilon$.\n- In each iteration, we find the lowest non-empty bucket $l$, and tries to update the estimates. Concretely, we loop over all $j \\in [n]$ and only sample a few indices $i$ from bucket $l$. For each $(i, j)$ pair, we try to update the estimate of $W(H_i)$ using $w_j(H_i)$. This might bump some $i$ into larger buckets.\n- If there is a single $j \\in [n]$ that bumps a substantial fraction of the sampled $i$s, we call such $j$ a \"prompting hypothesis\", and we use such $j$ to update all estimates in the current bucket. Note that if we keep finding prompting hypotheses, we will empty a bucket in $O(\\log n)$ repetitions, and the whole process must end in $O((\\log n)/\\epsilon)$ iterations. Moreover, each iteration is almost linear-time.\n- The harder part is to argue that, whenever we cannot find a prompting hypothesis, we are done. At a high level, this boils down to showing that the optimal hypothesis $i^*$ must be prompting, unless the majority of hypothesis in the lowest bucket are already good enough.", "questions": "Is there a reason why the \"right\" runtime should be $n \\cdot s = \\tilde O(n/\\epsilon^2)$? For example, given that the algorithm needs $\\Omega(n + s) = \\tilde\\Omega(n + 1/\\epsilon^2)$ time to read the inputs---can we hope to get an $\\tilde O(n + 1/\\epsilon^2)$ runtime?", "limitations": "Limitations are adequately addressed in Section 1.2.", "rating": 8, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- This work makes progress on improving the runtime for a fundamental problem in statistics / machine learning.\n- The new algorithms are based on clever ideas and several new concepts, which might find applications in future work.\n- The writing is very clear and I found the main paper relatively easy to follow. I especially liked that the authors spent most of the main paper on the proof overview, which is enjoyable to read and should be able to convince the readers why the proposed methods work.\n\nOverall, this paper contains fairly significant results that are very well presented and should be of interest to most learning theorists. I vote for acceptance.", "weaknesses": "The main weakness is that this work is unlikely to have said the last words on the problem---it remains open whether one can get $\\alpha = 3$ in $\\tilde O(n/\\epsilon^2)$ time.\n\nMinor writing suggestions:\n- Equation (2): Missing extra space in $S_{ij}$ on the left-hand side? (The notational convention in the rest of the paper seems to be $S_{i j}$, though personally writing $S_{i,j}$ might be clearer.)\n- Line 90: \"a $O(\\cdots)$ factor\" --> \"an $O(\\cdots)$ factor\"\n- Line 270: \"dependency\" not capitalized.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your feedback. \n\nIn response to your question, there is no explicit lower bound for the time complexity of this problem. As you mentioned, it is possible  that an algorithm could exist with a time complexity of just $\\Theta(n + s)$. However, for algorithms that operate by querying the probabilities of various sets according to an unknown distribution $P$—such as querying semi-distances or similar concepts, as many previous algorithms have done—we speculate that $\\Theta(n)$ queries to the semi-distances are both necessary and sufficient. \nThis would result in an overall time complexity of $\\Omega(n \\cdot s)$. We will clarify this in the future versions of our paper. \n\nEvidence suggesting that $O(n)$ queries might be sufficient comes from the upper bound of [MS08]. They demonstrated that there exist $O(n)$ sets to query, whose responses are sufficient to solve the problem. In their work, these sets and the order in which to query them are determined through an exponential time preprocessing step over the class $\\mathcal{H}$. It would be valuable to explore whether this problem can be solved with $\\Theta(n)$ queries without relying on the preprocessing step.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:
Thank you for taking the time to review our paper and for your feedback. 

**Presentation:**
Thank you for your comments regarding the presentation of our paper. We will incorporate all your editorial suggestions regarding the presentation of the paper. We will certainly focus on enhancing the clarity and quality of our write-up in future versions. 

**Dependency on $\epsilon$ and $\delta$:**
We acknowledge that, ideally, an algorithm should achieve a running time of $O(n \log(1/\delta)/\epsilon^2)$. Our first algorithm, with $\alpha = 3$, does not meet this ideal due to suboptimal dependencies on $\delta$ and $\epsilon$. However, it marks a significant step forward as it is the first in two decades to achieve a time complexity linear in $n$ for any $\alpha < 5$. To address the shortcomings, our second algorithm achieves the desired dependencies on $\epsilon$ and $\delta$, up to polylogarithmic factors, with a slight increase in the accuracy parameter ($\alpha = 4$). Given the significant departure from previous algorithmic approaches required by our work, we hope that our techniques will inspire further progress in this area.

Meta-review: This paper presents a new algorithm for a natural distribution learning problem that has been well-studied in the theory ML literature. It obtains the first linear time algorithm (linear in the number of choice distributions) that achieves a constant factor approximation (in fact, the best known approximation for a proper learner). All of the reviewers agreed that this was an interesting result, even if the paper falls slightly short of fully resolving the problem (it has a sub-optimal dependence on the statistical error, epsilon). There was also concern that the paper is no sufficiently polished, but we believe the author discussion period will help the authors improve their draft of the paper, so are recommending acceptance.
Decision: Accept (poster)