Optimal Hypothesis Selection in (Almost) Linear Time

Introduction

Hypothesis selection, also known as density estimation, is a fundamental problem in statistics and learning theory. This problem involves identifying a density function that accurately represents the distribution of a given dataset. Suppose we are given a dataset of samples drawn from an unknown distribution P and a finite class of known distributions, representing different hypotheses: H := {H 1 , H 2 , . . . , H n }. The goal is to select a distribution in H that is close to P in total variation (TV) distance.

Typically, learning a distribution over a domain X with an ε error in TV distance requires !(|X |/εfoot_2 ) samples, which presents a substantial lower bound in sample complexity for distributions over large 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,DL96,DL97]. With just s := "(log n/ε 2 ) samples from P , it is possible to learn P within error ω • OPT + ε, 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 in O(n 2

• s) timefoot_1 and achieves ω = 9; and the minimum distance estimate, which runs in O(n 3

• s) time and achieves ω = 3 [DL01, Chapter 6]. In these results, although ε can be decreased as the number of samples increases, ω 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 ω and computational efficiency has been a focal point. Mahalanabis and Stefankovic in [MS08] enhanced the minimum distance estimate, improving the time complexity to O(n 2

• s). They also introduced a nearly linear-time algorithm that achieves ω = 3, but requires exponential time in n for preprocessing the class H. Other nearly linear-time algorithms were developed achieving ω = 9 in [AJOS14, AFJ + 18, AAC + 23] 2 and ω = 5 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 ω < 3 is not possible unless the number of samples becomes poly(|X |), as indicated in [BKM19].

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 s = O(log(n)/ε 2 ) and optimal accuracy parameter ω = 3 that runs in O(n • s) time?

We present the first almost linear-time algorithm that uses the optimal number of samples and achieves the optimal accuracy parameter ω = 3. Our algorithm runs in Õ(n • s / ε) time (see Theorem 2). Additionally, we introduce another algorithm with improved dependency on ε, running in Õ(n • s) time while obtaining a slightly higher accuracy parameter, ω = 4 (see Theorem 3). Our results represent a significant step forward, as they are the first in decades to achieve time complexity linear in n for any ω < 5. See Table 1.

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 to choose the most suitable model from available options.

Another key strength of hypothesis selection is its agnostic nature, allowing it 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 ω ω ω 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 (ω • OPT + ε)-close to P in total variation distance. While increasing the number of samples can reduce ε to negligible levels, it does not improve the term ω • OPT. Hence, ω is an inherent property of the algorithm and directly impacts the best achievable error guarantee. Therefore, even a constant improvement in ω 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 without significantly increasing the size of the hypothesis class H. For example, in the cover method, when aiming to learn a distribution within a class C, we set H to be a ϑ-net that serves as a cover for C, ensuring that OPT < ϑ. While using a finer ϑ-net can reduce OPT, it may also drastically increase the size of H, thereby increasing the algorithm's running time, since the size of the net can grow super-polynomially with respect to ϑ. For instance, in the case of mixtures of k Gaussians, the size of the net depends on ϑ as roughly O(ϑ →3•k ) (see [SOAJ14]). Thus, reducing ϑ 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 = "(log n/ε 2 ) samples.

Main theorems

Below, we provide informal versions of our theorems. Theorem 2. For every ε, ϖ ↔ (0, 1), Algorithm 1 is an (ω = 3, ε, ϖ)-proper learner for hypothesis selection that uses s = O(log(n/ϖ)/ε 2 ) samples and time Õ(n • s / (ϖ 3 ε)) = Õ(n/(ϖ 3 ε 3 )). Theorem 3. For every ε, ϖ ↔ (0, 1), Algorithm 4 is an (ω = 4, ε, ϖ)-proper learner for hypothesis selection that uses s = O(log(n/ϖ)/ε 2 ) samples and time

For formal statements, see Theorem 5 (Appendix A) and Corollary B.1 (Appendix B).

Our results are the first to achieve time complexity linear in n for any ω < 5. To achieve this, we introduce novel algorithmic techniques that will hopefully be broadly useful-see Section 3 for an overview. Both algorithms use the optimal number of samples. The first algorithm obtains optimal accuracy parameter ω = 3 with a time complexity of Õ(n/(ϖ 3 ε) • s), which is off by an O(1/(ϖ 3 ε)) factor. Our second algorithm achieves the optimal time complexity up to logarithmic factors while achieving a slightly higher ω = 4. Our results leave a fascinating open question: Can one combine the best aspects of both algorithms, maintaining ω = 3, achieving O(n • s) time (or even lower), and sample complexity s = O(log(n/ϖ)/ε 2 )? Remark 4. Readers may be surprised by the polynomial dependence on 1/ϖ in Theorem 2. In many settings, the success probability of a learning algorithm can be amplified from a constant, say 2/3, to at least 1 ↑ ϖ at a cost of at most log(1/ϖ) in running time and sample complexity. However, in hypothesis selection, there is no (known) general technique for boosting the confidence parameter while keeping ω the same. The issue is that choosing the best output from several runs of a given algorithm requires executing a second hypothesis selection algorithm, which introduces another factor of ω 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 ω regime. Some previous results, such as [ABS23], also suffer from a polynomial dependency on ϖ.

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 Ĥ may not necessarily be in H. They presented an improper learner with accuracy guarantee ω = 2. The sample complexity of their algorithm was improved by [BBK + 21], who gave an algorithm with nearly optimal sample complexity and the same accuracy parameter ω = 2. It is worth noting that 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 (e.g., mixture of Gaussians). In certain applications, this selection ensures consistency with the problem's underlying assumptions, which enhances interpretability and robustness.

The problem of hypothesis selection in sublinear time was studied for distributions on discrete domains [AAC + 23]. Among other results, the authors developed a data structure that upon receiving samples from a unknown distribution P returns a hypothesis Ĥ 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-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 [BKSW19, CKM + 19, GKK + 20].

An important application of hypothesis selection arises when there is a structural assumption on the underlying distributions. One approach for learning these classes is to selectively choose a 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, DK14, SOAJ14, DKS17, KSS18, ABM18, ABH + 20], distributions with piecewise polynomial PDFs [ADLS17], and histograms [Pea95, CDSS14, CDKL22]. See Diakonikolas [Dia16] for a survey of results.

Preliminaries

Notation: We use the following notation throughout this article. We use [n] to indicate the set {1, 2, . . . , n}. For a distribution Q over X , Q(x) denotes the PDF of Q at the domain element x ↔ X . For any measurable subset of the domain S ↘ X , Q(S) indicates the probability mass of the set S according to Q. We use

is greater than ε. We use the standard O, !, " notation for asymptotic functions. Additionally, we use Õ, !, and " to hide polylog factors.

Scheffé sets: For every pair of hypotheses H i and H j in H, we define the Scheffé set of H i and H j as follows:

It is known that the Scheffé set maximizes the probability discrepancy between H i and H j , thus fully characterizing the total variation distance between the two distributions:

The optimal hypothesis: Recall that we assume the algorithm is given samples drawn from an unknown distribution P . Let H i → denote the closest hypothesis in H to P . That is, H i → is the hypothesis for which →H i → ↑ P → TV = OPT. When there is more than one hypothesis with this property, we pick one arbitrarily as

Semi-distances: For every pair i, j in [n], we define w j (H i ) to be |H i (S i,j ) ↑ P (S i,j )|. In words, w j (H i ) is the distance of H i to P observed on the Scheffé set of H i and H j . For every pair i, j ↔ [n], we use ŵj (H i ) to denote an estimate of w j (H i ) based on the observed sample. For the sake of consistency, we define w i (H i ) to be zero. In addition, we define the score function

Refined access model: Similar to previous work [DL01,MS08], we use estimates of the semidistances. One can easily estimate these quantities, denoted by ŵj (H i ), via the access model we have described earlier by letting ŵj (H i ) be the empirical ratio of the samples that are in S i,j . Throughout this paper, we assume that there are two universal parameters ϖ ↔ = "(ϖ) and ε ↔ = "(ε), for which with probability

A simple application of the Hoeffding bound and the union bound shows that one can compute all of the estimates via s = O(log(n/ϖ ↔ )/ε ↔ 2 ) samples, and each estimate can be computed in O(s) time.

Our algorithms access the distributions in H ⇐ {P } only via querying ŵj (H i ). This fact brings the sample complexity of our algorithms to s = O(log(n/ϖ ↔ )/ε ↔ 2 ) samples. The time complexity of our algorithms is determined by the number of queries they make to the ŵj (H i )'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 ŵj (H i )'s are accurate. Conditioning on the accuracy will not decrease the probability of correctness of any of our algorithms by more than ϖ ↔ due to Fact C.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 Ĥ such that → Ĥ ↑P → TV is at most 3 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 w j (H i ), defined as |H i (S i,j ) ↑ P (S i,j )|, captures the "distance" between H i and P as measured on this particular set S i,j . 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 . By definition, w j (H i ) is always a lower bound for →H i ↑ P → TV :

However, it is possible for w j (H i ) to be much lower, making it difficult for an algorithm to estimate the TV distance between H i and P just using semi-distances.

Nevertheless, for each hypothesis H i , a specific semi-distance w i → (H i ), associated with the optimal hypothesis H i → , determines its quality. As shown in the following proof, if w i → (H i ) ↗ OPT, then H i is 3, OPT-close to P , with the total variation distance between H i and P bounded by w i → (H i ) and OPT via the triangle inequality:

This observation implies that if we assert that w i → (H i ) is bounded by OPT, we can output H i as our final solution to the problem and be done. The challenge is that we neither know i ↗ nor OPT.

This issue is addressed by the minimum distance estimate presented in [DL01, MS08] using a score function W (H i ), as defined earlier: W (H i ) := max j↑[n] w j (H i ). The minimum distance estimate outputs a hypothesis Ĥ that minimizes W (H i ). We can assert that, for the output of this algorithm, Ĥ, w i → ( Ĥ) is at most OPT. This approach simultaneously bypasses the issues of not knowing i ↗ and OPT.

Note that W (H i ) serves as a proxy for the quality of H i since W (H i ) is an upper bound for w i → (H i ).

Using W (H i ), we can address the issue of not knowing i ↗ . On the other hand, although OPT is not known, we have a good lower bound for OPT, which is W (H i → ). Putting these observations together, we obtain:

These inequalities are derived using the triangle inequality and the fact that Ĥ was chosen to be the arg min i↑[n] W (H i ). See Figure 1 for an illustration of the above inequality. The primary hurdle with the minimum distance estimate is that it is costly to compute. Computing each W (H i ) takes O(n • s) time, bringing the total time complexity of the algorithm to O(n 2

• s). One might naturally conjecture that sampling may help to compute an estimate of W (H i ). Instead of using W (H i ) := max j↑[n] w j (H i ), we can use W (H i ) := max j↑R w j (H i ) where R is a set of random indices in [n]. The issue with this approach is that there is no guarantee of i ↗ being selected in R, making W (H i ) too low while H i may be far from P . Hence sampling, if used in a trivial manner, is not beneficial.

The algorithm with ω = 3

In this section, we present an overview of Algorithm 1 that attains ω = 3. The details of this algorithm and its related theorems are provided in Section A. At a high level, similar to the minimum distance estimate, we work towards finding a hypothesis that minimizes W (H i ). To increase efficiency, we

P (Si,j) Hi→ (Si,j) Hi (Si,j) → OPT wi→ (Hi) → W (Hi) wi(Hi→ ) ↑Hi ↓ Hi→ ↑TV H i O P T H i→ P ↑ H i ↓ P ↑ T V TV distance = absolute difference of probabilities on Scheffé set Probability of S i,j according to different distributions: Figure 1: A description of bounding →H i ↑ P → TV via W (H i ) and OPT work with estimates of W (H i )'s, denoted by W (H i ). The general structure of our algorithm is as follows: Initially, all W (H i ) are set to zero. At every step, we come up with several pairs of hypotheses H i and H j and update our estimates by setting W (H j ) to max( W (H j ), w i (H j )). Our approach ensures that at every step, W (H i ) is equal to max j↑R w j (H i ) for a small, carefully chosen set R. Eventually, we output a hypothesis with roughly the smallest W (H i ).

Focusing on small W W W : Our first idea is to focus on updating the W for hypotheses whose W (H i ) values are around the current minimum W . The rationale for this action comes from a simple fact: W (H j ) always underestimates the value of W (H j ). Hence, if we observe that W (H i ) is substantially larger than the current minimum, then W (H i ) is also substantially larger than the current minimum. This implies that H i is not a suitable candidate for the minimum at this stage of the algorithm, and it can be ignored for now.

Bucketing hypotheses based on W W W : To implement this idea, we partition the hypotheses into k = "(1/ε ↔ ) buckets B := {B 1 , B 2 , . . . , B k } based on W (H i ). The bucket ϱ contains all the hypotheses H i such that W (H i ) ↔ [(ϱ ↑ 1)ε ↔ , ϱ ε ↔ ). At every step, we focus on the smallest nonempty bucket B ω (the smallest ϱ for which |B ω | ⇒ = 0). B ω contains all the hypotheses whose W (H j ) is around the minimum W . We pick pairs of hypotheses, H i ↔ H and H j ↔ B ω , and update W (H j ). Note that our updates may increase W (H j ), and we may remove H j from B ω and put it into a larger bucket (a bucket with a larger index ϱ). Also, observe that we never move a hypothesis into a smaller bucket since W (H j ) never decreases. We continue our updates to reach one of the following outcomes:

• B ω becomes empty. That is, our updates made all W (H i ) fall out of the range of these buckets [0, ϱ ε ↔ ). Thus, every W (H i ) (and consequently every

Every time that we empty out a bucket, we have increased our threshold for minimum W (H i ) by ε ↔ . Hence, we are getting closer to a bucket with the true minimum, which we hope to reach in O(1/ε ↔ ) steps. • B ω is not empty, but we can confidently confirm most of the hypotheses in B ω are an acceptable output for the algorithm. Although we cannot ensure that H i → is indeed in B ω , we can find an acceptable final answer by selecting a random hypothesis in B ω . Which pairs to update? Next, we outline our update scheme to implement the above ideas in linear time. To enhance time efficiency, our aim is to optimize the updating process to ensure both quality and quantity in the chosen updates. Quality, in this context, relates to the extent of change in W (H j ) following an update: We consider H i to have made a substantial update to H j if W (H j ) + ε ↔ < ŵj (H i ). Such updates cause a significant shift, increasing the value of W (H j ) by more than ε ↔ and subsequently moving H j to a different bucket with a higher index ϱ. We refer to this event as H i removing H j from its bucket. The quantity, on the other hand, relates to the number of H j instances that a given H i can remove from B ω . An ideal H i eliminates a substantial portion of hypotheses from B ω (say a constant fraction). We call such an H i a prompting hypothesis. Now, if for O(log |B ω |) rounds we find a prompting hypothesis and update all the W (H j ) for H j ↔ B ω , we will empty out the bucket B ω , and we can move forward. Finding a prompting hypothesis: To find a prompting hypothesis quickly, we iterate over all H i in H, sample a few H j , and check if H i substantially updates W (H j ). If H i substantially improves a large fraction of the sampled hypotheses, then we declare that H i is a prompting hypothesis. See Section A.1.1 for further details. In addition to that, we provide a more advanced version of this procedure in Section A.1.2 that allows us to shave off an O(log n) factor. Getting stuck? Here is your way out: What happens when B ω is not empty, and we cannot find a prompting hypothesis? We show that if we do not find a prompting hypothesis, then a 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 B ω due to hypothesis sampling procedure we have to find a prompting hypothesis. In search for a prompting hypothesis, we iterate over all H i and sample roughly O(log n/ϖ) many hypotheses H j 's in B ω . We check, if H i can remove them from the bucket. Note that if H i was not found to be prompting, it implies that H i → cannot substantially update most of the hypotheses in B ω . Thus, We have that with high probability for 1 ↑ ϖ fraction of the hypotheses in B ω ,

The clever hack here is an observation about H i → . Earlier, we discussed that we are looking for a hypothesis H i with w i → (H i ) ↗ OPT. We claim that a random hypothesis in the last B ω (almost) has this property. On one hand, given that H i → was not found to be a prompting hypothesis, for 1 ↑ ϖ fraction of H i in B ω , w i → (H i ) must be at most ϱ • ε ↔ . On the other hand, the fact that all the previous buckets, B 1 , . . . , B ω→1 , are empty indicates H i → has shown a semi-distance of at least (ϱ ↑ 1) ε ↔ . Hence, OPT, which is at least as large as all

Therefore, for 1 ↑ ϖ fraction of the hypotheses in B ω , they are 3 OPT + "(ε) close to P . For a formal argument, see Lemma A.1. 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 H i → 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 on ϖ: It is worth noting that this last step results in a polynomial dependency on ϖ (as opposed to a more desirable dependency of log(1/ϖ)). This is mainly due to the fact that to ensure that a random hypothesis in B ω is not too far, with a probability of 1 ↑ ϖ in a single round, we have to try O(log(n)/ϖ) hypotheses in B ω and check if H i → is prompting them. Hence, relying on this structural property of H i → makes a polynomial dependency on ϖ inevitable. Improving the dependency on ϖ for this algorithm would require new algorithmic ideas.

The algorithm with ω = 4

We introduce another (almost) linear-time algorithm for the hypothesis selection problem, where the time complexity shows improved dependency on ε. However, this algorithm has a slightly worse accuracy parameter compared to our previous algorithm: ω = 4. This algorithm and the subsequent theorems are provided in Section B.

Algorithm with a guessed upper bound of OPT OPT 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 ς is provided to the algorithm such that OPT ↗ ς. A learner without the knowledge of ς can make a guess about ς and run one of the existing algorithms that works with the knowledge of an upper bound of OPT (e.g., [ABS23]) and check if it finds a good hypothesis or not. With this procedure in mind, we can run a binary search to find the smallest ς for which we find a hypothesis. 4 However, a challenge with this approach is that the algorithm might yield a hypothesis even when ς < OPT, making it difficult for us to refute the hypothesis that is found. Even if the output Ĥ satisfies W ( Ĥ) > ς, it does not necessarily invalidate our guessed value ς.

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 ς as a "guess" for which we hope that OPT ↗ ς. We require the algorithm to either refute our guess and declare OPT > ς, or output a hypothesis Ĥ with a reasonable distance to P , irrespective of the relationship between OPT and ς. More precisely, the distance of the output hypothesis should be bounded by: → Ĥ ↑ P → TV ↗ ω • max(OPT, ς) + ε. With these revised guarantees, it is permissible to run a binary search over different values of ς in {ε, 2 ε, . . . , ⇑1/ε⇓ ε}, and output the hypothesis that A returns on the smallest ς. For the rest of this discussion, we focus on designing A and a provided parameter ς.

Seeds and finding an acceptable hypothesis via seeds: In this algorithm, we introduce a new concept called a seed for hypotheses. A seed provides us with a structural property that enables us to identify an acceptable hypothesis, regardless of the relationship between H i → and the seed. More formally, for a hypothesis H i , we define M a,b (H i ) as the set of hypotheses H j such that w j (H i ) is between a and b:

We may omit the subscript of M when it is clear from the context. We say a hypothesis H i is a seed if almost all of its ŵj (H i ) are low and its W (H i ) is not too large. The quality of a seed is determined by three parameters: a, b, and m. Definition 3.1 (Seed). Given parameters a, b ↔ R ↘0 , and a non-negative integer m, we say a hypothesis is an (a, b, m)-seed if the following hold: 1)

A seed with a small-sized set M and a small b exhibits an interesting property: Suppose we have a seed H i with a constant-sized set M. In this case, in O(n) time, we can compute W (H j ) of every hypothesis H j in M. Now, let H ω ↔ M be one of the hypotheses that minimize W (H j ): H ω := arg min Hj ↑M W (H j ). We claim either H i or H ω is acceptable output in this case. When H i → is in H \ M, we can infer that w i → (H i ) is at most b (or, more precisely, b + ε ↔ ). From our earlier discussion, if b is sufficiently small (compared to ς), we can show that H i is close to P . In cases where H i → is in M, although we do not have strong guarantees for H i itself, we have a very good answer already: H ω is essentially a minimum distance estimate for the set M which includes H i → . Thus, we can conclude: First, H ω is an acceptable output because it is 3 OPT-close; second, W (H ω ) is a lower bound for OPT. Now, as we described, we have two acceptable outputs for two cases of the problem. For H i → ↔ H\M, H i is an acceptable answer. For H i → ↔ M, H ω is an acceptable answer. The only problem is that we do not know which case we are in. Our strategy is to pick a 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 (H ω ) with T ς:

say H ω is a good choice for us. However, we can conclude that H i is a close hypothesis to P even when H i → happens to be in M. In this case, we know that OPT ↓ W (H ω ) > T • ς. We take advantage of this knowledge and obtain the following bound:

Thus, regardless of where

We summarize these four cases in the following table. Depending on a and b, we set T to minimize the maximum distance we endure in these cases. It is worth noting that in this argument, we did not rely on any prior knowledge concerning the relationship between ς and OPT.

Table 2: Four cases when we process a 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 = ς and b = 3ς. To identify a seed hypothesis, we iterate over all hypotheses H 1 , . . . , H n , checking whether each hypothesis H i is a strong seed (i.e., a seed with a small |M|) by sampling several H j 's and verifying if w j (H i ) is at most a. Roughly speaking, for an integer m ↔ [n], if we sample approximately Õ(n/m) H j 's and find that no w j (H i ) > a, we can, with high probability, confirm that the size of M does not exceed m. This approach requires O(n 2 /m) time.

There are, however, a few caveats with this method. First, if a seed is identified using the above approach, it may have a large W (H i ) > b. In this case, we can infer that H i is likely far from P . Given the time invested in identifying H i , we aim to leverage this information. Broadly, observing that w j (H i ) ↗ a implies that many hypotheses are close to H i (assuming that w i (H j ) values are also small). Knowing that H i is far from P , we can mark all hypotheses close to H i 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 ς < OPT.

The second caveat is more challenging. Ideally, we seek a seed with a constant m, but finding such a seed would require Õ(n 2 /m) = Õ(n 2 ) 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 is much lower than the quality required for a producing solution. This leads to our next idea: boosting a seed, which is an approach to incrementally improve the seed's quality in roughly O(log n) steps.

Boosting a Seed: In this process, we use an initial seed to iteratively find a stronger seed with a reduced value of |M|.

For a formal argument, see Section B.2. Assume a rate parameter φ ↔ (0, 1). As discussed earlier, by spending O(n/φ) time, we can identify a seed with m ⇔ φ • n. Initially, m = |M| might be O(n). Hence, rather than calculating W (H j ) exactly for all H j ↔ M, we compute an approximate maximum semi-distance W (H j ) by sampling t hypotheses. Specifically, for each H j ↔ M, we set W (H j ) := max H k ŵk (H j ), where H k 's are sample hypotheses. Using these approximate values W , we process the seed as follows. Let H ω denote the hypothesis minimizing W (H j ), with the following possible outcomes: 1. High W (H ω ): If W (H ω ) is high, all W (H j ) (and thus W (H j )) values are likely large, making H i an acceptable final solution. 2. Low W (H ω ): While this does not guarantee a low W (H ω ), it suggests that most w i (H ω ) values are small. Based on the value of W (H ω ), we consider two cases: 2.1 W (H ω ) ↖ W (H ω ): H ω is likely far from P but has many close hypotheses, allowing us to mark these nearby hypotheses as far. 2.2 Moderate W (H ω ): In this case, H ω can serve as our new seed, as it yields a smaller set M(H ω ) than H i . Note that when we select H ω as our new seed, M(H ω ) is roughly O(n/t). However, we compute W (H j )'s for only |M(H i )| ⇔ φ • n many hypotheses. Hence, with an increased sample size t = O(1/φ 2 ), this approach yields a smaller |M(H ω )| ⇔ φ 2

• n. The step of the process requires O(|M| • t) = m/φ 2 = O(n/φ), paralleling the initial search. By repeating, we progressively reduce m = |M|, and for a constant φ, m decreases by a fixed factor until reaching a constant m seed, as desired.

Algorithm 1 An algorithm for hypothesis selection with ω = 3.

1: procedure SELECT-HYPOTHESIS(H, ε, ϖ, and query access to ŵj (H i )'s)

ϖ fn ↙ ϖ ↔ /k 10:

11:

for ϱ = 1, . . . , k do ↼ Iterating over buckets 12:

for i = 1, . . . , n do ↼ Iterating over hypotheses to find a prompting one 13:

Break the "for" loop and move on to the next bucket.

15:

16:

for the number of hypotheses that H i removes from B ω 17: for H j ↔ B ω do ↼ Update all hypotheses in B ω via the prompting hypothesis 18:

Output ∈ and halt.

24:

i ↙ 0 ↼ Restarts the "for" loop.

25:

Ĥ ↙ a random hypothesis in B ω 27:

Output Ĥ and halt.

A Almost linear time algorithm with ω = 3 ω = 3 ω = 3

In this section, we focus on our first result, the algorithm with ω = 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 in Section 3.2.

At a high level, our algorithm begins with all W (H i ) set to zero, and all hypotheses placed in B 1 .

We then iterate over all buckets. In round ϱ, we check if there is a prompting hypothesis H i ↔ H that can move a significant fraction of hypotheses from B ω . Specifically, we look for an H i that moves a ϑ-fraction of hypotheses from B ω by updating them, where ϑ = "(ϖ). If we find such a hypothesis H i , we update all the hypotheses in B ω and move as many as possible out of B ω . During this process, we count the number of hypotheses that H i removes from B ω , which is tracked by C ω i in the algorithm. If the actual fraction of hypotheses removed from B ω is less than ϑ/2, we infer that IS-PROMPTING falsely declared H i as a prompting hypothesis (false positive). Thus, the algorithm returns ∈. Otherwise, we restart the search by setting i = 1 and iterate over all H i to find the next prompting hypothesis. We continue this process until no prompting hypothesis is found or the bucket is emptied. If we completely empty a bucket, we move on to the next one. If not, we select a random hypothesis in B ω as the final output and halt.

Theorem 5. Suppose H is a class of n known hypotheses and P is an unknown hypothesis. Assume the algorithm has access to accurate estimates of ŵj (H i )'s that have an error of at most ε ↔ . Let ε and ϖ be two parameters in (0, 1). If 3 ε ↔ ↗ ε, then Algorithm 1 is an (ω = 3, ε, ϖ)-proper learner for P in H. The running time of our algorithm is Õ((n/(ϖ 3 ε)) • T q ), where T q is the time to obtain each ŵj (H i ).

Proof. Our proof consists of three parts:

1. If the algorithm returns Ĥ, with high probability, Ĥ is not too far from P .

2. While the algorithm may not produce a hypothesis all the time, the overall failure probability of the algorithm is low.

3. The running time of the algorithm meets the desired bounds in the theorem.

The output Ĥ Ĥ Ĥ is close with high probability. Suppose we output Ĥ ↔ B ω at step ϱ. Our goal is to show that Ĥ is (3 OPT + ε)-close to P with probability 1 ↑ ϖ ↔ . We define two events E ω and E ω for each ϱ ↔ Conditioning on the event E ω , fewer than a ϑ fraction of the hypotheses in B ω are far. Since Ĥ is a randomly selected hypothesis in B ω , the probability of Ĥ being far is less than ϑ:

Next, we focus on the case where E ω holds: at least a ϑ fraction of the hypotheses in B ω are (3 OPT + ε)-far from P . In the following lemma, we show that H i → is a prompting hypothesis for such a B ω . The proof of this lemma is available in Section A.2.

Lemma A.1. Suppose B ω ↘ H is the smallest non-empty bucket for which at least a ϑ fraction of its hypotheses are (3 OPT + ε)-far from P . Then H i → is a prompting hypothesis that can remove a ϑ fraction of the hypotheses in B ω .

If we output a hypothesis in B ω , clearly, the prompting hypotheses had failed to empty out the bucket. Therefore, the last time the algorithm was iterating over all i's in [n], the IS-PROMPTING procedure returned false for every single H i , and no "restart" happened. However, during those iterations, at some point, i reached i ↗ , implying that the IS-PROMPTING procedure did not catch that H i → is a prompting hypothesis. This event happens with probability at most ϖ fn .

Given Equation (4) and Equation (5), we bound the probability of outputting a far Ĥ as follows:

The last line is due to the fact that we set ϖ fn = ϖ ↔ /k and ϑ = ϖ ↔ .

Bounding the overall error probability: We have shown that if we output Ĥ, it is an acceptable answer with high probability. Now, we need to show that the overall error probability of the algorithm is not 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 we check that at least ϑ/2 of the hypotheses are removed from B ω in Line 22. Therefore, the total number of restarts for any given bucket is at most

In addition, we claim the algorithm does not end without outputting Ĥ or ∈. Every H i belongs to some bucket at every step of the algorithm. This is due to the assumption that ŵj (

For the bucket that cannot be emptied out, the algorithm outputs either ∈ or Ĥ.

Next, we show that the probability of outputting ∈ is at most ϖ ↔ . Note that the algorithm outputs ∈ when H i was not able to remove at least ϑ/2 of the hypotheses in B ω . As we have established earlier, the restart happens only 4 log(n)/ϑ times for every bucket. Therefore, the IS-PROMPTING procedure is invoked at most 4kn log(n)/ϑ times overall. Each time we have a chance of ϖ fp of declaring a hypothesis prompting erroneously. The algorithm in Line 22 checks if the error has happened, and it outputs ∈ when it does. Hence, we have:

The final inequality follows from setting ϖ fp = ϑ • ϖ ↔ /(4 k n log(n)). Thus, we can bound the overall error probability as follows:

The last inequality holds since ϖ ↔ = ϖ/3.

A.1 Identifying prompting hypothesis

In this section, we provide two algorithms for identifying a prompting hypothesis. The simple algorithm, presented in Section A.1.1, involves sampling the hypotheses in a bucket to estimate the fraction of the hypotheses that H i can move, using a 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 1. We also show that the time complexity of this algorithm, in the case it returns false, is proportional to 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 on false returns.

A.1.1 Simple version of IS-PROMPTING Algorithm 2 An algorithm to identify a prompting hypothesis (simple version). 1: procedure IS-PROMPTING-SIMPLE(B, ϱ, H i , ϑ, ε ↔ , ϖ, and query access to ŵj (H i )'s) 2: t ↙ 8 log(2/ϖ)/ϑ 2  3: u r ↙ 0 ↼ u r counts # sampled hypotheses that H i updates 4: repeat t times 5: H j ↙ a random hypothesis in B ω 6: if ŵi (H j ) > W (H j ) + ε ↔ then 7: u r ↙ u r + 1 8: 9: if ur t < 3 ϑ 4 then 10: return false 11: else 12:

return true Lemma A.2. Suppose we are given two parameters ϖ, ε ↔ ↔ (0, 1), and three positive integers n, k, and ϱ ↔ [k]. Assume we are given a class of hypotheses H, its partition into k buckets B = {B 1 , B 2 , . . . , B k }, and a hypothesis H i ↔ H. The IS-PROMPTING-SIMPLE procedure in Algorithm 2 receives H, B, ϱ, H i , ϖ fp , ϖ fn , and ε ↔ as its input and returns true or false with the following guarantees:

• If H i substantially updates at least a ϑ-fraction of the hypotheses in B ω , then IS-PROMPTING-SIMPLE returns true with probability at least 1 ↑ ϖ.

• If H i substantially updates less than a ϑ/2-fraction of the hypotheses in B ω , then IS-PROMPTING-SIMPLE returns false with probability at least 1 ↑ ϖ.

• We have the following guarantees for the algorithm:

where T q is the time to obtain each ŵj (H i ).

Proof. This is a simple application of the Hoeffding bound:

A.1.2 Advanced version of IS-PROMPTING

We present an overview of the algorithm for the advanced version of IS-PROMPTING. Suppose we are given a parameter ϑ, and our goal is to design an algorithm that does the following with high probability: it returns true when H i can substantially update a ϑ-fraction of the hypotheses in B ω , and it returns false when H i can substantially update less than a ϑ/2 fraction of the hypotheses in B ω .

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 ϱ, to find a single prompting hypothesis, we check O(n) (potentially non-prompting) hypotheses. On the other hand, we only need log 1/ϑ (B ω ) 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 a 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, we 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:

Given the analysis of our algorithm, we can show that the probability of false positives must be around

On the other hand, our analysis is robust as long as the probability of false negatives is roughly O(ϖ), where ϖ 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 a direct artifact of our analysis.) This gap is particularly large when ϖ is a small constant, as is common in the literature.

The IS-PROMPTING procedure (Algorithm 3) is designed in a way that has different time complexities depending on its output being true or false. The procedure uses more than O(log n) (more like O(log n • log(1/ϖ)/ϑ 2 )) 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 O(log n), we only spend O(log(1/ϖ)) time plus an amortized cost of O(1/ϑ) for the O(B ω ) calls to the procedure.

The algorithm runs in roughly O(log n) rounds. In each round, it draws a few random hypotheses from B ω (roughly O(log(1/ϖ)/ϑ 2 )). In each round, we check if the fraction of hypotheses H i can substantially update is close to ϑ. At any round, if we see that the fraction is not close to ϑ, we return false. The hope is that for a non-prompting hypothesis, we either stop very quickly or the hypothesis passes too many rounds without us noticing that it 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 B ω .

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(t/ϑ) time, it must have removed t hypotheses from the bucket. Thus, one can show that the amortized cost of these elongated rounds is only O(1/ϑ).foot_6

Lemma A.3. Suppose we are given three parameters ϖ fp , ϖ fn , ε ↔ ↔ (0, 1), and three positive integers n, k, and ϱ ↔ [k]. Assume we are given a classes of hypotheses H, its partition into k buckets B = {B 1 , B 2 , . . . , B k } and a hypothesis H i ↔ H. The IS-PROMPTING procedure in Algorithm 3 receives H, B, ϱ, H i , ϖ fp , ϖ fn , and ε ↔ as its input and returns true or false with the following guarantees:

• If H i substantially updates at least ϑ fraction of the hypotheses in B ω , then IS-PROMPTING returns true with probability at least 1 ↑ ϖ fn .

• If H i substantially updates less than ϑ/2 fraction of the hypotheses in B ω , then IS-PROMPTING returns false with probability at least 1 ↑ ϖ fp .

Algorithm 3 An algorithm to identify a prompting hypothesis. 1: procedure IS-PROMPTING(B, ϱ, H i , ϑ, ε ↔ , ϖ fn , ϖ fp , and query access to ŵj (H i )'s)

is a set of hypotheses that H i can update substantially. 4: for r = 1, . . . , R do 5: if |Sr↓1| B ω ↓ ϑ 2 then 6: return true 7: S r ↙ S r→1 8: u r ↙ 0 ↼ u r indicates # hypotheses H i updates 9: repeat t :=  48 log(2R/ϖ fn ) ϑ 2  times 10: G (r) j ↙ a random hypothesis in B ω 11:

for H j ↔ S r do 17:

W (H j ) ↙ max W (H j ), ŵi (H j )

18:

Move

return false 20:

for H j ↔ S r do 22:

W (H j ) ↙ max W (H j ), ŵi (H j )

23:

Move

return false 25:

return true

• If the algorithm returns true, we have the following guarantees for the algorithm:

• Suppose the algorithm returns false. Assume n

indicates the number of hypotheses that the algorithm removes from B ω . Then, we have the following guarantees for the algorithm:

In above bounds, where T q denotes the time complexity to obtain each ŵj (H i ).

Proof. The probabilities in this proof are taken over the random choices of G (r) j 's. Note that S contains at the hypotheses for which we can change.

Probability of false positive: First, we show that probability of outputting true, while H i can substantially update less ϑ/2 fraction of hypotheses in B ω , is at most ϖ fp . The algorithm return true in two places. First, at the beginning of each round, we check whether S r→1 contains at least ϑ/2-fraction of hypotheses. This answer is always correct with probability one. Since the algorithm has an evidence that H i can certainly update at least ϑ/2 of hypotheses in B ω . Thus, this case does not affect our false positive rate ϖ fp . Second, the algorithm returns true after all rounds end. This case only happens when u r /t is at least 3ϑ/4 in every round in Line 20. It is not hard to see that u r is a binomial random variable with t trials. The success probability of each trial is the ratio of the hypotheses in B ω that H i can update substantially. Thus, in the case where H i substantially updates less than ϑ fraction of hypotheses, by Markov's inequality, we have:

Probability of false negative: Suppose that H i substantially updates at least ϑ-fraction of the hypotheses in B ω . That is, H i can update each G (r)

j with probability at least ϑ. Fix a round r. We bound the probability of returning false in Line 19 and Line 24.

In Line 19, we return false when

That is, the number of new hypotheses we added to S r is not too large. Consider the random hypotheses we draw at round r. Our claim is that most of these random hypotheses are not in S r→1 . The probability that one G (r)

However, this expectation is less than ϑ/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:

In Line 24, we return false if u r /t is less than 3 ϑ/4. By Chernoff bound, we have:

Taking the union bound over all rounds, we obtain:

B Linear time algorithm with ω = 4

In this section, we present our second algorithm whose sample complexity has a better dependency on the accuracy parameter ε. An overview of our 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 6.

Apart from improving the accuracy parameters, we also provide modifications to our algorithm that can achieve low rounds of adaptivity (roughly speaking, it means the number of times the algorithm needs to look at the sample set). More formally, in our access model, we define one round of adaptivity as follows: The algorithm selects a set of t = O(n 2 ) pairs of indices {(i ω , j ω )} ω↑[t] and query all ŵj ω (H i ω ) at once. The number of adaptivity rounds represents the total count of times the algorithm needs to repeat this process in order to produce its final output. This is particularly interesting when considering a federated learning setting in which the rounds of interactivity are important. The modification of our algorithm runs in time O(n 1+ϱ ) runs in O(1/↽) rounds of adaptivity.

Theorem 6. Suppose Algorithm 4 receives these parameters as input: ς ↔ [0, 1], φ ↔ (0, 1/4), ε, ϖ ↔ (0, 1). Also, assume the algorithm has access to a class of n hypotheses H, and a set of unmarked hypotheses in Q ↘ H where initially Q = H. Suppose the algorithm can query ŵj (H i )'s with error at most ε ↔ ↗ ε/6. The algorithm has one of the two possible outcomes: either it declares that ς < OPT; or it outputs a hypothesis H i such that: with probability at least 1 ↑ ϖ we have:

The algorithm runs in O(n/φ • T q ) time and O log 2 1/ς (n) rounds of adaptivity. Here T q is the time required to obtain each ŵj (H i ).

Algorithm 4 finds a hypothesis that is 4 max (ς, OPT) + ε close to P .

1: procedure SELECT-HYPOTHESIS(H, Q, ς, ε, ϖ, φ, , and query access to ŵj (H i )'s)

22:

return H i found by BOOST-SEED. else if BOOST-SEED returns "start over" then 27:

return SELECT-HYPOTHESIS(H, Q, s, ς, ε, ϖ)

28:

Output H ω .

31:

Output H i .

Proof. For the sake of argument, assume each of the sub-routines in the algorithm works as guaranteed with probability one (as oppose to the case where they work as expected with probability 1 ↑ ϖ ↔↔ ).

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 ς + 3ε ↔ , m)seed with high probability. Using Fact C.4, this seed is also a (2 ς+ε ↔ , 4 ς+5ε ↔ , m). In boosting seeds, we start with (2 ς + ε ↔ , 4 ς + 5ε ↔ , m) and we get (2 ς + ε ↔ , 4 ς + 5ε ↔ , m ↔ ) where m ↔ = ∝φ • m′. This statement is justified by Theorem 9, setting ⇀ = ⇀ ↔ = 2, and using the same values for a = 2, ς + ε ↔ and b = 4, ς + 5ε ↔ for our seeds. It is worth noting that the only parameter that changes while we boost is m.

Accuracy of the output Consider the case where we produce output when |Q| is zero. That implies that our algorithm marked all the hypotheses. Throughout the course of algorithms, we never mark a hypothesis H i unless we have found an evidence that →H i ↑ P → TV > ς. This was established by observing ŵj (H i ) > ς + ε ↔ , which implies →H i ↑ P → TV must be greater than ς; Or, showing a close-by hypotheses to H i is 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 i , →H i ↑ P → TV is greater than ς. Hence, when the size of Q is zero we can truly assert that "ς < OPT".

For the case that |Q| = 1, the algorithm focuses on H i , the only unmarked hypothesis left. If we found Ŵ (H i ) is greater than ς + ε ↔ , we can simply conclude that for every H i , →H i ↑ P → TV is greater than ς, and "ς < OPT". Otherwise, using Fact C.3, the H i is a valid answer:

In addition, the accuracy of the H i that is returned in Line 22 is guaranteed by the Theorem 9, and setting ⇀ = ⇀ ↔ = 2. Next, lets focus on the hypotheses we output after the "if" condition in Line 29. When Ŵ (H ω ) is small, we have:

When Ŵ (H ω ) is large, the analysis is very similar to Case 1 in the proof of Theorem 9. Again, by setting ⇀ = ⇀ ↔ = 2, and using the facts that

Number of recursions: Given Theorem 8 and Theorem 9, we only see "start over" when (1 ↑ 2φ) fraction of unmarked hypotheses in Q have been marked. Since we have n hypotheses, we do not start over more than O(log 1/ς (n)) times.

Running time: In the while loop, m decreases with a factor of φ every time we find a new seed. Hence, the total number of iterations is bounded by O(log 1/ς (n)). Using Theorem 8 and Theorem 9, invoking the procedures for finding a seed and boosting a seed each takes O(n log(n/ϖ ↔↔ )/φ • T q ) time. Thus, the total time complexity is:

Overall confidence parameter: The total number of subroutines we call here is at most O(log 2 1/ς (n)). Thus, by setting ϖ ↔↔ to O(ϖ/ log 2 1/ς (n)) and using the union bound, we can show the overall error probability is bounded by ϖ.

B.1 Finding initial seed

In this section, we describe an algorithm that receives parameter ς as input and finds a (ς + ε ↔ , 3 ς + 2ε ↔ , ∝φ • n′)-seed in roughly Õ(n/φ • T q ) time with high probability or declares "ς < OPT".

Algorithm 5 finds a (ς + ε ↔ , 3 ς + 3ε ↔ , m)-seed 1: procedure FIND-SEED(H, Q, ς, ε ↔ , ϖ, φ, and query access to ŵj (H i )'s)

Next, we show that if the algorithm outputs H i , then it is a (ς + ε ↔ , 3 ς + 3 ε ↔ , m)-seed with high probability. First, observe that Ŵ (H i ) 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 i to be a good seed holds as well:

is bounded by m. We have already established that ŵj (H i ) for every j ↔ [n] is bounded by 3 ς + 3 ε ↔ since Ŵ (H i ) is at most 3 ς + 3 ε ↔ . Hence, we only need to show that there are at most m hypotheses H j such that w j (H i ) is larger than ς + ε ↔ . Now, if there are more than m hypothesis H j in H such that ŵj (H i ) > ς + ε ↔ . Now, if we sample t := ⇑8 n log (2n/ϖ) /m⇓ hypotheses, we should observe at least one H j for which ŵj (H i ) is larger than ς + ε ↔ , with probability at least 1 ↑ ϖ/(2n). However, we know that such a hypothesis was never observed because we did not mark H i earlier. By the union bound, with a probability of at least 1↑ϖ/2, no such H i exists. Hence, with probability at least 1↑ϖ/2, H i is an (ς+ε ↔ , 3 ς+3ε ↔ , m ↔ )-seed as promised in the statement of the lemma.

Next, assume we output "start over." after finding an unmarked hypothesis H i . In this case, we know that H i is not marked and Ŵ (H i ) > 2ς + 3ε ↔ . Note that we have sampled t edges of H i , and we never see w j (H i ) > ς + ε ↔ . Using a very similar argument as we have above: one can show there cannot be more than m ↔ = ⇑φ • |Q|⇓ for which w j (H i ) > ς + ε ↔ with probability 1 ↑ ϖ/2 (for every H i ). That means, we will mark |Q| ↑ m ↔ many hypothesis in Q. If |Q| > t ↓ 1/φ, this implies that (1 ↑ 2φ) fraction of the hypothesis in Q are removed. If |Q| ↗ t, then we know all the hypothesis in Q have w j (H i ) ↗ ς + ε ↔ and all of them will be marked. Furthermore, we show that we did not wrongfully mark a hypothesis that was ς-close to P . Observe that the condition in Line 22 holds in two cases:

It is straightforward to show that H j is not ς-close to P since we have:

Even though ŵω (H j ) is small in this case, we can indirectly deduce that H j is not ς-close to P . By the definition of ŵj (H i ) and ŵi (H j ), we have:

On the other hand, by the triangle inequality, we have:

Therefore, in both of the cases above, we do not mark an ς-close distribution to P .

By the union bound over all the steps, our guarantees hold with probability 1 ↑ ϖ. In addition, it is not hard to see that the running time of the algorithm is O ((n

Rounds of adaptivity: It is straight forward to show that this algorithm can be implemented with a constant round of adaptivity. Let Q 0 denote the initial state of unmarked hypotheses at the algorithm's outset. Since hypotheses are marked in sequence, in round i, the set of unmarked hypotheses is

As a result, we can agree on the set of random H j 's in Q and H and request ŵj (H i ) within a single round. If the size of |Q i | is at most t, then we include all ŵj (H i ) for every i ↔ n and H j ↔ Q. Next, upon discovering an unmarked H i , we initiate another round of adaptivity to request all ŵj (H i ) and ŵj (H i ) for all j ↔ [n]. This enables the implementation of the rest of the algorithm.

B.2 Boosting a seed

In this section, we provide an algorithm that receives a (⇀ ς + ε ↔ , (⇀ + 2)ς + 5 ε ↔ , m)-seed and aims to find a (⇀ ↔ ς + ε ↔ , (⇀ ↔ + 2)ς + 5 ε ↔ , m ↔ )-seed with smaller m ↔ . That means, the size of M for this new seed is smaller which brings us closer to have enough time to fully investigate the set M for a future seed. Our algorithm runs in Õ(n • T q /φ) time where φ ⇔ m ↔ /m is our rate parameter. This running time is adaptive to our budget. If we are aiming for Õ(n) algorithm, we find a seed such that m ↔ is only smaller than m by a constant factor (constant φ); Alternatively, if we have more time, we can decrease m ↔ with a faster rate (smaller φ).

While our main goal is to find a better seed, our algorithm may not always be able to do so; However, it 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 Ĥ as the final output of the algorithm.

2. The algorithm finds a better seed as we aimed for.

3. The algorithm marks (1 ↑ 2φ) 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 n unmarked hypotheses to begin with, and we marked a large fraction of them every time, we do not start more than O(log 1/2ς (n)) times over the course of the algorithm. Our approach is presented in Algorithm 6, and we prove its performance in Theorem 9.

Algorithm 6 aims to find a better seed. 1: procedure BOOST-SEED(H, Q, H i , ς, ⇀, ⇀ ↔ , ε ↔ , ϖ, φ, and query access to ŵj (H i )'s)

H ω ↙ arg min Hj ↑M W (H j )

Return H i as the final answer. 9:

else 10:

Compute Ŵ (H ω ).

Return H ω as a seed.

13: else 14:

for

Mark H j in Q.

17:

return "Start over."

Theorem 9. Suppose Algorithm 6 receives these parameters as input: ς ↔ R ↘0 , ⇀, ⇀ ↔ ↓ 1, φ ↔ (0, 1/4), ε ↔ , ϖ ↔ (0, 1), and two non-negative integers n, m. Also, assume the algorithm has access to a class of n hypotheses H, and a set of unmarked hypotheses in Q ↘ H. It also receives a hypothesis H i ↔ H. The algorithm has one of the three possible outcomes listed below. Now, for any setting of such input parameters, if H i is a (⇀ ς + ε ↔ , (⇀ + 2)ς + 5 ε ↔ , m) seed, then the following guarantees hold for the outcome of Algorithm 6 with a probability of at least 1 ↑ ϖ:

1. If the algorithm outputs a hypothesis Ĥ as the final answer, then we have for every ε ↓ 6 ε ↔ :

2. If the algorithm outputs a hypothesis H ω as a new seed, then H ω is a (⇀ ↔ ς + ε ↔ , (⇀ ↔ + 2)ς + 5 ε ↔ , m ↔ )-seed where m ↔ := ∝φ m′.

Algorithm 7 computes W (H i ).

1: procedure COMPUTE-W (H, Q, H i , t, and query access to ŵj (H i )'s)

H j ↙ a uniformly random sample drawn from H 5:

H j ↙ a uniformly random sample drawn from Q 7:

for all H j ↔ Q do 11:

Return W .

3. If the algorithm requires us to start over, then we have marked at least (1 ↑ 2φ) of the unmarked hypotheses.

The algorithm runs in O(n • (log(n/ϖ)) • T q /φ) time and can be implemented in O(1) rounds of adaptivity.

Proof. Let M denote the set M ↼ φ+ε ↑ ,(↼+2)φ+5 ε ↑ (H i ). We consider the three possible outcomes of the algorithm, and prove the algorithm satisfied the desired guarantee in each of the three cases.

In this case, the algorithm will return H i as the final answer. We show that the total variation distance between H i and P is as desired. There are two possibilities depending on whether H i → is in M or not.

Case 1.1:

Using that H ω has the minimum W (H ω ) among all the hypotheses in M, we can bound OPT as follows:

We prove that H i is not too far from P . Note that since H i was an (⇀ ς + ε ↔ , (⇀ + 2) ς + 5 ε ↔ , m)-seed, we are guaranteed that Ŵ (H i ) is bounded by (⇀ + 2) ς + 5 ε ↔ . Using the above bound for OPT and Fact C.3, we get:

is bounded by ⇀ ς + ε ↔ . In this case, we have the following bound for the total variation distance between H i and P via Fact C.3:

In this case, we output H ω as a new seed. Given the assumptions of this case, we show that H ω is a (⇀ ↔ ς + ε ↔ , (⇀ ↔ + 2)ς + 5 ε ↔ , m ↔ )seed. First, Ŵ (H ω ) is at most (⇀ ↔ + 2) ς + 5 ε ↔ implying the first desired property for being an (⇀ ↔ ς + ε ↔ , (⇀ ↔ + 2)ς + 5 ε ↔ , m ↔ )-seed holds for H ω . Next, we show the second desired property for H ω : the size of M ↼ ↑ φ+ε ↑ , (↼ ↑ +2)φ+5 ε ↑ (H ω ) is bounded by m ↔ . At a high level, we expect the size of this set to be small; Otherwise, we would have observed one of these large ŵω (H j ) when we have sampled t hypotheses to compute W (H ω ).

Suppose H ω has more than m ↔ edges with ŵj (H ω ) > ⇀ ↔ ς + ε ↔ . Now, if we sample t := ⇑8 n log (2n/ϖ) /m ↔ ⇓ hypotheses, we should observe at least one H j for which ŵj (H ω ) is larger than ⇀ ↔ ς + ε ↔ , with probability at least 1 ↑ ϖ/(2n). However, we know that such a hypothesis was never observed because W (H ω ), which is the maximum of ŵj (H ω )'s, is bounded from above by ⇀ ↔ ς + ε ↔ . By the union bound, with a probability of at least 1 ↑ ϖ/2, no such H ω exists. Hence, with probability at least 1 ↑ ϖ/2, H ω is an (⇀ ↔ ς + ε ↔ , (⇀ ↔ + 2) ς + 5ε ↔ , m ↔ )-seed as promised in the statement of the lemma.

In this case the algorithm marks any unmarked hypothesis H j for which ŵω (H j ) > ς + ε ↔ or ŵj (H ω ) ↗ ⇀ ↔ ς + ε ↔ , and we start over. First, we show that we did not wrongfully mark a hypothesis that was ς-close to P . Observe that the condition in Line 15 holds in two cases:

It is straightforward to show that H j is not ς-close to P since we have:

Even though ŵω (H j ) is small in this case, we can indirectly deduce that H j is not ς-close to P . By the definition of ŵj (H ω ) and ŵω (H j ), we have:

On the other hand, by the triangle inequality, we have:

Therefore, in both of the cases above, we do not mark an ς-close distribution to P .

Second, we claim that we mark at least (1 ↑ 2 φ) fraction of the unmarked hypotheses in Q. Recall that when we compute W (H ω ) we also sample t hypotheses from the set of unmarked hypotheses, and we did not observe any edge ŵj (H ω ) that is larger than ⇀ ↔ ς + ε ↔ . With a very similar argument we had above, with probability 1 ↑ ϖ/(2n), we do not have more than

Otherwise, we would have seen one of these edges, and W (H ω ) would have been larger. By the union bound, this fact holds for every H ω . Hence, the "if" condition in Line 15 holds for over |Q| ↑ ⇑φ • |Q|⇓ of the unmarked hypotheses in Q, and the algorithm mark them. If |Q| ↓ 1/φ, it is easy to show that |Q| ↑ ⇑φ • |Q|⇓ is at least (1 ↑ 2 φ) • |Q|. Thus, we mark at least (1 ↑ 2 φ) fraction of the hypotheses in Q as we have claimed. Now, if |Q| ↗ 1/φ, it is easy to show that |Q| < t. Hence, the algorithm involves all the H j 's in Q to compute Ŵ (H ω ). Therefore, every single ŵj (H ω ) is at most ⇀ ↔ ς + ε ↔ and we mark all the hypotheses in Q.

By the union bound over all the steps, our guarantees hold with probability 1 ↑ ϖ. In addition, it is not hard to see that the running time of the algorithm is O ((m

Rounds of adaptivity: Our algorithm can be implemented in constant rounds of adaptivity.

To compute W 's, we can preselect the random H j 's. If Q contains fewer than t + 1 hypotheses, we include every ŵj (H i ) for each H j ↔ Q and i ↔ [n]. Upon discovering H ω , another round of adaptivity allows us to query every ŵj (H ω ) and ŵω (H j ) to calculate Ŵ (H ω ) and mark the hypotheses in Q.

C Preliminary facts and lemmas

Fact C.1. For all distribution P and for all probability event E defined under P , we have:

, where P |E denotes the probability distribution P when conditioned on the event E. Fact C.2. For every pair of distributions H i and H j , we have:

The following fact is adapted from [DL01, MS08, ABS23]. Fact C.3. Suppose H i → is the closest hypothesis to P in H(i.e., →H i → ↑ P → TV ). For every pair of hypotheses H i and H j , the following holds:

Proof. The proof is based on triangle inequality, and the definitions of w j (H i )'s and OPT. For every H j in H, we have:

Hence, Item 1 is proved. Now, if we set H j to be H i → , then →H i → ↑ P → TV is equal to OPT implying Item 2. Item 3 is concluded from Item 2 and the fact that w i → (H i ) is upper bounded by W (H i ). Fact C.5. Suppose we have a set of n hypotheses H, and a predicate, R(H) : H △ {0, 1}, that maps the hypotheses in H to zero or one. Assume H contains more than m hypotheses with R(H) = 1 for an arbitrary integer parameter 0 ↗ m < n. If we draw s ↓ 8 n log(ϖ →1 )/m hypotheses from H uniformly at random, we will observe at least one hypothesis with R(H) = 1 with probability at least 1 ↑ ϖ.

Proof. Let p denote the fraction of such hypothesis in H with R(H) = 1. Observe that p > 0 since there are at least m + 1 such hypothesis in H. Then, using the Chernoff bound, we have:

D Data structure for marked and unmarked hypotheses

Here, we describe a simple data structure that allows us to efficiently keep track of marked and unmarked hypotheses. Our data structure consists of two integers, n and t, and two arrays of size n: index[] and list[]. Here, n represents the number of hypotheses that the data structure supports. The list array is an arbitrary ordering of integers from 1 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 as a threshold quantity. The first t numbers in the list correspond to unmarked hypotheses, while the remaining numbers represent marked hypotheses. Initially, list is a list of integers from 1 to n in ascending order. And, for every hypothesis H i , 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 t to size. Next, we set list to be a list of integers from 1 to n in ascending order. To ensure consistency with the list, each index[i] is set to i. • mark(i): To mark hypothesis H i , we swap the element at index i with the element at index t in the list array, and then decrement t by 1.

• is_marked(i): Given our definition, if index[i] is less than or equal to t, then H i is unmarked; otherwise, it is marked. • is_all_marked(): If t is equal to zero, then it means all the hypotheses are marked.

• random_unmarked(): To select a random unmarked hypothesis, we generate a random integer r between 1 and t, and output the hypothesis at list[r]. • random_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.

It is easy to see that the initialization takes O(n) time, and the rest of the operations only take O(1) time.

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 a 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 in 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 can be expected to generalize to other settings. • It is fine to include aspirational goals as motivation as long as it 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 1.2 regarding potential improvements and future directions.

Guidelines:

• The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper. • The authors are encouraged to create a separate "Limitations" section in their paper.

• The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (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 on the scope of the claims made, e.g., if the approach was only tested on a few datasets or with a few runs. In general, empirical results often depend on implicit assumptions, which should be articulated. • The authors should reflect on the factors that influence the performance of the approach.

For example, a facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or a 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 of the proposed algorithms and how they scale with dataset size. • If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness. • While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an important role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.

Theory Assumptions and Proofs

Question: For each theoretical result, does the paper provide the full set of assumptions and a complete (and correct) proof?

Question: Does the paper provide open access to the data and code, with sufficient instructions to faithfully reproduce the main experimental results, as described in supplemental material? Answer: [NA] Justification: We do not have any experimental results. Guidelines: • The answer NA means that paper does not include experiments requiring code. • Please see the NeurIPS code and data submission guidelines (https://nips.cc/ public/guides/CodeSubmissionPolicy) for more details. • While we encourage the release of code and data, we understand that this might not be possible, so "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 NeurIPS code and data submission guidelines (https: //nips.cc/public/guides/CodeSubmissionPolicy) 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. If only a subset of experiments are reproducible, they should state which ones are omitted from the script and why. • At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable). • Providing as much information as possible in supplemental material (appended to the paper) is recommended, but including URLs to data and code is permitted. 6. Experimental Setting/Details Question: Does the paper specify all the training and test details (e.g., data splits, hyperparameters, how they were chosen, type of optimizer, etc.) necessary to understand the results? Answer: [NA] Justification: We do not 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 a level of detail that is necessary to appreciate the results and make sense of them. • The full details can be provided either with the code, in appendix, or as supplemental material. 7. Experiment Statistical Significance Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments? Answer: [NA] Justification: 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, confidence 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.) • The assumptions made should be given (e.g., Normally distributed errors). • It should be clear whether the error bar is the standard deviation or the standard error of the mean. • It is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have a 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 Question: For each experiment, does the paper provide sufficient information on the computer resources (type of compute workers, memory, time of execution) needed to reproduce 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 paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage. • The paper should provide the amount of compute required for each of the individual experimental runs 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 it into the paper).

Broader Impacts

Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?

Answer: [NA] Justification: Given the theoretical nature of our findings, we do not 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 or why the paper does not address societal impact.

• Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations. • The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is a 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 or 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).

Safeguards

Question: Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?

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 a 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 to usage guidelines or restrictions to access the model or implementing safety filters. • Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images. • We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make a best faith effort.

12. Licenses for existing assets Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?

Answer: [NA] Justification: 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 a 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.

• If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswithcode.com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of a dataset. • For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided. • If this information is not available online, the authors are encouraged to reach out to the asset's creators.