Optimal Hypothesis Selection in (Almost) Linear Time

Authors: maryam  aliakbarpour
mark  bun
adam  smith
Venue: NeurIPS_cc_2024_Conference
Published: 2024-05-15 07:46:32

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$.

Main paper: 
 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 |/ϵ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) time1 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 .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.Min distance estimate [DL01] We refer to α as the accuracy parameter, ϵ as the error (or proximity) parameter, and δ as the confidence parameter of the algorithm.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 Õ(n•s•log(1/δ)) = Õ(n•log 2 (1/δ)/ϵ 2 )).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 δ.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.  
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∥Q 1 -Q 2 ∥ TV := sup S⊆X |Q 1 (S) -Q 2 (S)| to denote the total variation distance between Q 1 and Q 2 . We say Q 1 is ϵ-close to Q 2 if ∥Q 1 -Q 2 ∥ TV is at most ϵ. Conversely, we say Q 1 is ϵ-far from Q 2 if ∥Q 1 -Q 2 ∥TV 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:S i,j := {x ∈ X | H i (x) < H j (x)} if i ≤ j S j,i if i > j (2)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:EQUATIONThe 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 H i * .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 functionW (H i ) := max j∈[n] w j (H i ). Similarly, Ŵ (H i ) is defined to be max j∈[n] ŵj (H i ).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 probability1 -δ ′ every ŵj (H i ) is within ϵ ′ of w j (H i ): ∀i, j ∈ [n] : | ŵj (H i ) -w j (H i )| ≤ ϵ ′ .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. 
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 w j (H i ). In the formal proofs presented in subsequent sections, we will substitute each w j (H i ) with an estimated value ŵj (H i ).If the error of these estimates is below ϵ ′ = Θ(ϵ), it can be shown that the overall impact of this substitution on our final distance guarantee (Equation 1) is at most Θ(ϵ). See the "Refined access model" in Section 2 for further details.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 :w j (H i ) := |H i (S i,j ) -P (S i,j )| ≤ sup S⊆X |H i (S) -P (S)| = ∥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:∥H i -P ∥ TV ≤ ∥H i -H i * ∥ TV + ∥H i * -P ∥ TV = |H i (S i,j ) -H j (S i,j )| + OPT (By Eq. 3) ≤ w i * (H i ) + w i (H i * ) + OPT ≤ w i * (H i ) + 2 OPT.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:∥ Ĥ -P ∥ TV ≤ w i * ( Ĥ) + 2 OPT ≤ W ( Ĥ) + 2 OPT ≤ W (H i * ) + 2 OPT ≤ 3 OPT.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 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.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 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 W (H i )) is at least ℓ • ϵ ′ .w i (H j ) ≤ ϵ ′ • ℓ.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 H i * semi-distances, is at least (ℓ -1) ϵ ′ . Therefore, w i * (H i ) ≤ ϵ ′ + OPT. 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.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:M a,b (H i ) := {H j ∈ H | a < ŵj (H i ) ≤ 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)Ŵ (H i ) ≤ b, and 2) |M a,b (H i )| ≤ m.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 σ:1) If W (H ℓ ) ≤ T • σ, as we have discussed earlier, H ℓ is (T • σ + 2OPT)-close to P . This bound holds regardless of where H i * is. 2) Next, if W (H ℓ ) > T • σ,we cannot 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:∥H i * -P ∥ TV = b σ + 2 OPT ≤ b T + 2 OPT .Thus, regardless of whereH i * is, H i is (max(a, b/T ) + 2) • max (σ, OPT). Now, the algorithm is fairly straightforward. If W (H ℓ ) is small, output H ℓ ; otherwise, output H i .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.H i * ∈ M H i * ∈ H \ M W (H ℓ ) > T • σ ∥H i -P ∥ TV ≤ a • σ + 2 OPT ∥H i -P ∥ TV ≤ (b/T + 2)OPT W (H ℓ ) > T • σ ∥H ℓ -P ∥ TV ≤ T • σ + 2 OPT ∥H ℓ -P ∥ TV ≤ T • σ + 2 OPTTable 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|. W (H i ) ← 0 for every i ∈ [n] 3: k ← ⌊1/ϵ ′ ⌋ + 1 4: B 1 ← H 5: B 2 , . . . , B k ← ∅ 6: ϵ ′ ← ϵ/3 7: δ ′ ← δ/3 8: γ ← δ ′ 9: δ f n ← δ ′ /k 10: δ f p ← γ • δ ′ /(4 k n log(n))11:for ℓ = 1, . . . , k do ▷ Iterating over buckets 12:for i = 1, . . . , n do ▷ Iterating over hypotheses to find a prompting one 13:if |B ℓ | = 0 then 14:Break the "for" loop and move on to the next bucket.15:if IS-PROMPTING(B, ℓ, H i , γ, ϵ ′ , δ ′ ) then ▷ Checks if H i is prompting.16: C ℓ i ← 0 ▷ A counterif ŵi (H j ) > W (H j ) + ϵ ′ then 19: W (H j ) ← max W (H j ), ŵi (H j ) 20:Move H j to B ⌈ W (Hj )/ϵ ′ ⌉ 21:C ℓ i ← C ℓ i + 1 22: if C ℓ i C ℓ i +|B ℓ | < γ/2 then ▷ It indicates H i was not prompting. 23:Output ⊥ and halt.i ← 0 ▷ Restarts the "for" loop.25:if |B ℓ | ̸ = 0 then 26:Ĥ ← a random hypothesis in B ℓ 27:Output Ĥ and halt.A Almost linear time algorithm with α = 3 α = 3 α = 3In 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 γ:EQUATIONNext, 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 δ f n .PrEQUATIONGiven Equation (4) and Equation (5), we bound the probability of outputting a far Ĥ as follows:Pr Outputting Ĥ and ∥ Ĥ -P ∥ TV > 3 OPT + ϵ = k ℓ=1 Pr ∥ Ĥ -P ∥ TV > 3 OPT + ϵ | E ℓ • Pr[ [ [ E ℓ ] ] ] + k ℓ=1 Pr ∥ Ĥ -P ∥ TV > 3 OPT + ϵ | E ℓ • Pr E ℓ ≤ k ℓ=1 Pr[ [ [ E ℓ ] ] ] + k ℓ=1 γ • Pr E ℓ ≤ k • δ f n + γ ≤ 2 δ ′ .The last line is due to the fact that we set δ f n = δ ′ /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 mostlog 1/(1-γ/2) (|B ℓ |) + 1 ≤ 4 log(n)/γ times.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 (H i ) is in [0, 1]. Thus, W (H i ) is always between 0 ≤ W (H i ) ≤ 1 < kϵ ′ . Thus, it is not possible to reach |B ℓ | = 0 for all ℓ ∈ [k] in Line 25.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 δ f p 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:EQUATIONThe final inequality follows from setting δ f p = γ • δ ′ /(4 k n log(n)). Thus, we can bound the overall error probability as follows:Pr[ [ [ Wrong answer] ] ] = Pr[ [ [ Outputting ⊥] ] ] + Pr Outputting Ĥ s.t. ∥ Ĥ -P ∥ TV > 3 OPT + ϵ ≤ 3 δ ′ ≤ δ .The last inequality holds since δ ′ = δ/3.The initialization takes O(n + k) time. The algorithm runs over k buckets. For each bucket, we may restart the "for" loop O(log(n)/γ) times. Within each "for" loop before restarting, we invoke the IS-PROMPTING procedure O(n) times where, with the exception of one of them, all return false. Let T(i)false indicate the time that the procedure spends on H i in the false case. Also, set this quantity be T true if the procedure returns true (which happens at most once before restarting). If we find a prompting hypothesis, we query the ŵi (H j )'s O(n) times, and spend O(n • T q ) for this step. Hence, the total time complexity is:Total time complexity = O k • log(n) γ • n i T (i) false + T true + n • T q .Advanced version of IS-PROMPTING: We described the guarantees of the advanced version of the IS-PROMPTING 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 B ℓ during the procedure of IS-PROMPTING. We denote this quantity in the r-th search for the prompting hypothesisH i in bucket b ℓ via n (ℓ,i) r. Since the total number of hypotheses that we can remove is at most O(n), we have:n i T (i) false = n i O log δ -1 f n + log log δ -1 f p • T q /γ 2 + n (ℓ,i) r • T q /γ = O n • log δ -1 f n + log log δ -1 f p • T q /γ 2 + n • T q /γ = O n • log δ -1 f n + log log δ -1 f p • T q /γ 2Using the setting of our parameters,δ f p = γ • δ ′ /(4 k n log(n)) = O(n log n/(δ ϵ)) and δ f n = δ ′ /k = O(1/(δ ϵ)). n i T (i) false = O n δ 2 • log 1 δ ϵ + log log n δ ϵ • T q = O n δ 2 • log 1 δ ϵ + log log (n) • T q .Moreover, for the case that a prompting hypothesis is found:T true = O log δ -1 f p • log δ -1 f n + log log δ -1 f p • T q /γ 2 = O 1 δ 2 • log n δ ϵ • log 1 δ ϵ + log log n δ ϵ • T q = O 1 δ 2 • log n δ ϵ • log 1 δ ϵ + log log (n) • T q .Hence, the total time complexity is:Total time complexity = O k • log(n) γ • n i T (i) false + T true + n • T q = O log(n) δ 3 ϵ • n • log log n + n • log 1 δ ϵ + log 1 δ ϵ 2 • T q = Õ n δ 3 ϵ • T q .In this version, we only have one possible confidence parameter, which is min(δ f n , δ f p ). Hence, using Lemma A.2, we have:T (i) false = T true = O log (min(δ f n , δ f p )) -1 • T q /γ 2 . Total time complexity = O k • log(n) γ • n i T (i) false + T true + n • T q = O n • log(n) δ 3 ϵ • log n δ ϵ • T q = Õ n δ 3 ϵ • T q .Thus, the proof is complete.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 • 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:Number of queries to ŵi (H j )'s: O log(δ -1 )/γ 2 , Running time: O log(δ -1 ) • T q /γ 2 ,where T q is the time to obtain each ŵj (H i ).Proof. This is a simple application of the Hoeffding bound:Pr u t -E u t ≥ γ 4 ≤ 2 exp -2 t γ 2 ≤ δ .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:δ f p := Pr[ [ [ Returning true | H i substantially updates less than a γ/2 fraction] ] ] δ f n := Pr[ [ [ Returning false | H i substantially updates at least a γ fraction] ] ]Given the analysis of our algorithm, we can show that the probability of false positives must be aroundÕ(1/ |B ℓ |) = Õ(1/n).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/γ).6 Lemma A.3. Suppose we are given three parameters δ f p , δ f n , ϵ ′ ∈ (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 , δ f p , δ f n , 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 -δ f n .• If H i substantially updates less than γ/2 fraction of the hypotheses in B ℓ , then IS-PROMPTING returns false with probability at least 1 -δ f p .Algorithm 3 An algorithm to identify a prompting hypothesis.1: procedure IS-PROMPTING(B, ℓ, H i , γ, ϵ ′ , δ f n , δ f p , and query access to ŵj (H i )'s) 2: R ← log 3/2 1 δ f p 3: S 0 ← ∅ ▷ SG (r) j ← a random hypothesis in B ℓ 11: if ŵi G (r) j > W G (r) j + ϵ ′ then 12: u r ← u r + 1 13: S r ← S r ∪ {G (r) j } 14: 15: if |S r | -|S r-1 | < γ•t 8 then 16:for H j ∈ S r do 17:W (H j ) ← max W (H j ), ŵi (H j )18:MoveH j to B ⌈ W (Hj )/ϵ ′ ⌉ 19:return false 20:if ur t < 3 γ 4 then 21:for H j ∈ S r do 22:W (H j ) ← max W (H j ), ŵi (H j )23:Move H j to B ⌈ W (Hj )/ϵ ′ ⌉ 24:return false 25:return true• If the algorithm returns true, we have the following guarantees for the algorithm:Number of queries to ŵi (H j )'s: O log δ -1 f p • log δ -1 f n + log log δ -1 f p /γ 2 , Running time: O log δ -1 f p • log δ -1 f n + log log δ -1 f p • T q /γ 2 .• Suppose the algorithm returns false. Assume n(ℓ,i) rindicates the number of hypotheses that the algorithm removes from B ℓ . Then, we have the following guarantees for the algorithm:Number of queries to ŵi (H j )'s: O log δ -1 f n + log log δ -1 f p /γ 2 + n (ℓ,i) r /γ , Running time: O log δ -1 f n + log log δ -1 f p • T q /γ 2 + n (ℓ,i) r • T q /γ .fIn 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 δ f p . 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 δ f p .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:Pr[ [ [ Returning true | H i substantially updates less than γ/2-fraction] ] ] = Pr ∀r ∈ [R] : u r t ≥ 3γ 4 Pr u r t ≥ 3γ 4 R ≤ (2/3) R ≤ δ f pProbability 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 |S r | -|S r-1 | < γ•t 8 . 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)j be selected from S r-1 is |S r-1 | / |B ℓ |.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:Pr number of G (r) j ∈ S r-1 ≥ 5 γ • t 8 = Pr number of G (r) j ∈ S r-1 t ≥ 5 γ 8 = γ 2 • 1 + 1 4 ≤ Pr number of G (r) j ∈ S r-1 t > |S r-1 | |B ℓ | + γ 4 ≤ exp -2 t (γ/4) 2 ≤ δ f n 2 R .In Line 24, we return false if u r /t is less than 3 γ/4. By Chernoff bound, we have:Pr u r t < γ • 1 - 1 4 ≤ exp - t γ 3 • 4 2 = δ f n 2 R .Taking the union bound over all rounds, we obtain:Pr[ [ [ Returning false | H i substantially updates at least γ-fraction] ] ] ≤ δ f n .Running time: In the case the algorithm return true, the algorithm makes O(R /γ • T q . Thus, the proof is complete by setting R := log 3/2 (1/δ f p ) and t := 48 log(2R/δ f n )/γ 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 ℓ .Proof. We show that H i * can substantially update W of any far hypothesis in B ℓ . Let H f denote a (3 OPT + ϵ)-far hypothesis. First, observe that ŵi * (H f ) must be large compared to OPT:ŵi * (H f ) ≥ w i * (H f ) -ϵ ′ = |H f (S f i * ) -P (S f i * )| -ϵ ′ ≥ |H f (S f i * ) -H i * (S f i * )| -|H i * (S f i * ) -P (S f i * )| -ϵ ′ ≥ ∥H f -H i * ∥ TV -∥H i * -P ∥ TV -ϵ ′ (By Fact C.2) ≥ ∥H f -P ∥ TV -2 ∥H i * -P ∥ TV -ϵ ′ > 3 OPT + ϵ -2 OPT -ϵ ′ ≥ OPT + 2 ϵ ′ .In addition, OPT cannot be much smaller than ℓ ϵ ′ . The main reason is that all the buckets before B ℓ are empty. Hence, H i * belongs to a bucket B ℓ ′ where ℓ ′ is at least ℓ. By our definition of bucketing: W (H i * ) must be at least (ℓ -1) ϵ ′ . Hence we have:(ℓ -1) ϵ ′ ≤ W (H i * ) ≤ Ŵ (H i * ) ≤ W (H i * ) ≤ OPT .Note that we assume H f belongs to B ℓ , so Wf is less than ℓϵ ′ . Putting all these observation together, we achieve:Wf + ϵ ′ < ℓ ϵ ′ + ϵ ′ ≤ OPT + 2ϵ ′ < ŵi * (H f ) .Therefore, if we update Wf via ŵi * (H f ), then H i * can significantly improve Wf . This fact implies that H i * can removes all the bad hypothesis from B ℓ which concludes the proof of the lemma.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:∥ Ĥ -P ∥ TV ≤ 4 max (σ, OPT) + ϵ .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)if |Q| = 0 then 3: return "σ < OPT".if |Q| = 1 then 5:H i ← the only unmarked hypothesis left. 6: if Ŵ (H i ) > σ + ϵ ′ then 7:return "σ < OPT". δ ′′ ← δ/ 100 • log 1/(2η) (n) • log 1/(η) (n) 12: m ← ⌊η • n⌋ 13: Run FIND-SEED(H, Q, σ, ϵ ′ , δ ′′ , η) 14:if FIND-SEED declares "σ < OPT" then 15:return "σ < OPT".else if FIND-SEED returns "start over" then 17:return SELECT-HYPOTHESIS(H, Q, σ, ϵ, δ, η)H i ← the seed that FIND-SEED found.19:while m > 1 η do 20: Run BOOST-SEED(H, Q, H i , σ, κ = 2, κ ′ = 2, ϵ ′ , η) 21:if BOOST-SEED finds the final answer. thenreturn H i found by BOOST-SEED. 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:∥H i -P ∥ TV ≤ W (H i ) + 2OPT ≤ Ŵ (H i ) + ϵ ′ + 2OPT ≤ 3 max (σ, OPT) + 2ϵ ′ .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:∥H ℓ -P ∥ TV ≤ W (H ℓ )+2OPT ≤ Ŵ (H ℓ )+ϵ ′ +2OPT ≤ 2 σ+2ϵ ′ +2OPT ≤ 4 max (σ, OPT)+2ϵ ′ .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 Ŵ (H ℓ ) -ϵ ′ ≥ κ ′ σ and Ŵ (H i ) ≤ (κ + 2) σ + 5 ϵ ′ , we obtain:∥H i -P ∥ TV ≤ 4 max (σ, OPT) + 6ϵ ′ .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:O n η • log(n/δ) + log log 1/η (n) • log 2 1/η (n) • T q = Õ n • log(1/δ) • T q η .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 δ.Using Theorem 8 and Theorem 9, invoking the procedures for finding a seed and boosting a seed each takes O(1) rounds of adaptivity. Hence, the overall rounds of adaptivity is O log 2 1/η (n) rounds.Remark 7. One could argue that we have demonstrated the algorithm operates in Õ(n/η • T q ) time with a probability of 1 -δ. 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 can output ⊥ to indicate the algorithm's failure to produce a valid answer. With this adjustment, the time complexity remains low as desired.Corollary B.1. Suppose H is a class of n known hypotheses and P is an unknown hypothesis. Let ϵ and δ be two parameters in (0, 1). Assume the algorithm has access to accurate estimates of ŵj (H i )'s that have error at most ϵ ′ . If 3 ϵ ′ ≤ ϵ, then for every η ∈ (1/n, 1/4) there exists an (α = 4, ϵ, δ)proper learner for P in H. The running time of our algorithm isÕ((n/η) • log(1/δ) • log(1/ϵ) • T q ),and it can be implemented in O log 2 1/η (n) • log(1/ϵ) rounds of adaptivity.Proof. This is a direct corollary of Theorem 6 combined with a binary search over values of σ ∈ {ϵ ′ , ϵ ′ } where ϵ ′ := ϵ/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.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)2: m ← ⌊η • n⌋ 3: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:|M σ+ϵ ′ ,3 σ+3 ϵ ′ (H i )| ≤ m.This condition requires that the number of H j 's in H for which ŵj (H i ) is in (σ + ϵ ′ , 3 σ + 3 ϵ ′ ] 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:Case 1: ŵi (H j ) > σ + ϵ ′ ŵi (H j ) > σ + ϵ ′ ŵi (H j ) > σ + ϵ ′ .It is straightforward to show that H j is not σ-close to P since we have:∥H j -P ∥ TV ≥ w i (H j ) ≥ ŵi (H j ) -ϵ ′ > σ . Case 2: ŵi (H j ) ≤ σ + ϵ ′ ŵi (H j ) ≤ σ + ϵ ′ ŵi (H j ) ≤ σ + ϵ ′ and ŵj (H i ) ≤ σ + ϵ ′ ŵj (H i ) ≤ σ + ϵ ′ ŵj (H i ) ≤ σ + ϵ ′ .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:∥H i -H j ∥ TV = |H i (S i,j ) -H j (S i,j )| ≤ |H i (S i,j ) -P (S i,j )| -|P (S i,j ) -H j (S i,j )| = w i (H j ) + w j (H i ) ≤ ŵi (H j ) + ŵj (H i ) + 2 ϵ ′ ≤ 2σ + 2 ϵ ′ .On the other hand, by the triangle inequality, we have:∥P -H j ∥ TV ≥ ∥P -H i ∥ TV -∥H i -H j ∥ TV ≥ W (H i ) -∥H j -H i ∥ TV ≥ Ŵ (H i ) -ϵ ′ -∥H i -H j ∥ TV > 3 σ + 3 ϵ ′ -ϵ ′ -(2 σ + 2 ϵ ′ ) = σ .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• t + n) • T q ) = O(n • (log(n/δ)) • T q /η) time.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 isQ i := Q 0 ∩ H i , H i+1 , . . . , H n .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.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)2: m ′ ← ⌊η m⌋ 3: t ← ⌈8 n log (2n/δ) /m ′ ⌉ 4: for H j ∈ M do ▷ We denote M (κ σ+ϵ ′ , (κ+2)σ+5 ϵ ′ (H i ) by M. 5: W (H j ) ← COMPUTE-W (H, Q, H i , t) 6: H ℓ ← arg min Hj ∈M W (H j ) 7: if W (H ℓ ) > κ ′ σ + ϵ ′ then 8:Return H i as the final answer. 9:else 10:Compute Ŵ (H ℓ ).11: if Ŵ (H ℓ ) ≤ (κ ′ + 2) σ + 5 ϵ ′ then 12:Return H ℓ as a seed.13: else 14:forH j ∈ H do 15: if ŵℓ (H j ) > σ + ϵ ′ or ŵj (H ℓ ) ≤ κ ′ σ + ϵ ′ then 16:Mark H j in Q.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 ϵ ′ :∥ Ĥ -P ∥ TV ≤ max κ + 2, κ + 2 κ ′ + 2 • max (σ, OPT) + ϵ .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 ). for all H j ∈ Q do 11:W ← max W , ŵj (H i )12: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.Case 1:W (H ℓ ) > κ ′ σ + ϵ ′ W (H ℓ ) > κ ′ σ + ϵ ′ W (H ℓ ) > κ ′ σ + ϵ ′ .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:H i * ∈ M H i * ∈ M H i * ∈ M.Using that H ℓ has the minimum W (H ℓ ) among all the hypotheses in M, we can bound OPT as follows:OPT ≥ W (H i * ) ≥ Ŵ (H i * ) -ϵ ′ ≥ Ŵ (H ℓ ) -ϵ ′ ≥ W (H ℓ ) -ϵ ′ ≥ κ ′ σ .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:∥H i -P ∥ TV ≤ W (H i ) + 2 OPT ≤ Ŵ (H i ) + ϵ ′ + 2 OPT ≤ (κ + 2) σ + 6 ϵ ′ + 2 OPT ≤ κ + 2 κ ′ + 2 • OPT + 6 ϵ ′ ≤ κ + 2 κ ′ + 2 • max(σ, OPT) + ϵ . Case 1.2: H i * ̸ ∈ M H i * ̸ ∈ M H i * ̸ ∈ M. Since H i is a (κ σ + ϵ ′ , (κ + 2)σ + 5 ϵ ′ , m)-seed, ŵi * (H i ) is bounded by Ŵ (H i ) ≤ (κ + 2)σ + 5 ϵ ′ . Now that H i * is not in M, it must be the case that ŵi * (H i )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:∥H i -P ∥ TV ≤ w i * (H i ) + 2 OPT ≤ ŵi * (H i ) + ϵ ′ + 2 OPT ≤ κ σ + 2 ϵ ′ + 2 OPT ≤ (κ + 2) max(σ, OPT) + ϵ . Case 2: W (H ℓ ) ≤ κ ′ σ + ϵ ′ W (H ℓ ) ≤ κ ′ σ + ϵ ′ W (H ℓ ) ≤ κ ′ σ + ϵ ′ and Ŵ (H ℓ ) ≤ (κ ′ + 2) σ + 5 ϵ ′ Ŵ (H ℓ ) ≤ (κ ′ + 2) σ + 5 ϵ ′ Ŵ (H ℓ ) ≤ (κ ′ + 2) σ + 5 ϵ ′ .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.Case 3: W (H ℓ ) ≤ κ ′ σ + ϵ ′ W (H ℓ ) ≤ κ ′ σ + ϵ ′ W (H ℓ ) ≤ κ ′ σ + ϵ ′ and Ŵ (H ℓ ) > (κ ′ + 2) σ + 5 ϵ ′ Ŵ (H ℓ ) > (κ ′ + 2) σ + 5 ϵ ′ Ŵ (H ℓ ) > (κ ′ + 2) σ + 5 ϵ ′ .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:Case 3.1: ŵℓ (H j ) > σ + ϵ ′ ŵℓ (H j ) > σ + ϵ ′ ŵℓ (H j ) > σ + ϵ ′ .It is straightforward to show that H j is not σ-close to P since we have:∥H j -P ∥ TV ≥ w ℓ (H j ) ≥ ŵℓ (H j ) -ϵ ′ > σ . Case 3.2: ŵℓ (H j ) ≤ σ + ϵ ′ ŵℓ (H j ) ≤ σ + ϵ ′ ŵℓ (H j ) ≤ σ + ϵ ′ and ŵj (H ℓ ) ≤ κ ′ σ + ϵ ′ ŵj (H ℓ ) ≤ κ ′ σ + ϵ ′ ŵj (H ℓ ) ≤ κ ′ σ + ϵ ′ .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:∥H ℓ -H j ∥ TV = |H ℓ (S ℓ,j ) -H j (S ℓ,j )| ≤ |H ℓ (S ℓ,j ) -P (S ℓ,j )| -|P (S ℓ,j ) -H j (S ℓ,j )| = w ℓ (H j ) + w j (H ℓ ) ≤ ŵℓ (H j ) + ŵj (H ℓ ) + 2 ϵ ′ ≤ κ ′ σ + σ + 4 ϵ ′ .On the other hand, by the triangle inequality, we have:∥P -H j ∥ TV ≥ ∥P -H ℓ ∥ TV -∥H ℓ -H j ∥ TV ≥ W (H ℓ ) -∥H j -H ℓ ∥ TV ≥ Ŵ (H ℓ ) -ϵ ′ -∥H ℓ -H j ∥ TV > (κ ′ + 2) σ + 4 ϵ ′ -((κ ′ + 1) σ + 4 ϵ ′ ) = σ .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 m ′′ := ⌈η • |Q| • m/n⌉ ≤ ⌈η • |Q|⌉ hypotheses in Q such that ŵj (H ℓ ) > κ ′ σ + ϵ ′ . 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• t + n) • T q ) = O(n • (log(n/δ)) • T q /η) time.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.Fact C.1. For all distribution P and for all probability event E defined under P , we have:∥P -P |E ∥ TV = 1 -P (E) ,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:∥H i -H j ∥ TV = |H i (S ij ) -H j (S ij )| .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:1. ∥H i -P ∥ TV ≤ w j (H i ) + 2∥H j -P ∥ TV , 2. ∥H i -P ∥ TV ≤ w i * (H i ) + 2 OPT , 3. ∥H i -P ∥ TV ≤ W (H i ) + 2 OPT .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:∥H i -P ∥ TV ≤ ∥H i -H j ∥ TV + ∥H j -P ∥ TV = |H i (S i,j ) -H j (S i,j )| + ∥H j -P ∥ TV ≤ |H i (S i,j ) -P (S i,j )| + |P (S i,j ) -H j (S i,j )| + ∥H j -P ∥ TV = w j (H i ) + w i (H j ) + ∥H j -P ∥ TV ≤ w j (H i ) + 2∥H j -P ∥ TV .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 ). )/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:Pr[ [ [ r = 0] ] ] ≤ Pr r < s p 2 = Pr r s < 1 - 1 2 • p ≤ exp - s p 8 < exp - s m 8 n ≤ δ .D Data structure for marked and unmarked hypotheses 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.Question: For each theoretical result, does the paper provide the full set of assumptions and a complete (and correct) proof?• 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. Justification: Our results are a theoretical formulation of a fundamental problem in statistics and learning theory. They can be viewed as a computationally efficient version of existing results. Given the theoretical nature of our findings, we do not anticipate any harm to 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 a deviation from the Code of Ethics. • The authors should make sure to preserve anonymity (e.g., if there is a special consideration due to laws or regulations in their jurisdiction). 
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. 
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 are theoretical. As is standard in the field, we 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 to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file. 
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 not have any crowdsourcing experiments nor human subjects.Guidelines:• The answer NA means that the paper does not involve crowdsourcing nor research with human subjects. • Including this information in the supplemental material is fine, but if the main contribution of the paper involves human subjects, then as much detail as possible should be included in the main paper. • According to 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. 
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 crowdsourcing nor research with human subjects.• 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.38th Conference on Neural Information Processing Systems (NeurIPS 2024).This time bound assumes constant-time comparisons of the Hi's density functions. See Section 1.1.Theorem 4.1 in [AAC + 23] states the result for α = 27. However, according to personal correspondence with the authors, it is possible to modify their algorithm in conjunction with the minimum distance estimate and improve α to 9.We omit the arguments (H, P ) when they are clear from the context.This idea works to some extent, but it causes α to be increased by 2, which is not useful in our setting. See[ABS23] for more details.It is worth noting that we are using the E ℓ notation somewhat non-rigorously here. This notation does not represent the complementary event of E ℓ . Instead, it denotes the complementary event of E ℓ conditioning on the outputting of Ĥ from the bucket B ℓ .The parameters in this high-level discussion lack precision. For a rigorous analysis, refer to our proof of Lemma A.3. 
 
 Appendix:  


Decision: 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.

Reviews: review: paper_summary: paper_summary: This paper looks at proper distribution learning: given samples from
some distribution p, and a set of n candidate distributions H_i,
output one H_i that is close in TV; in particular, alpha * OPT + eps.
Surprisingly, this is possible with a sample complexity independent of
the domain size (as would be needed to actually estimate the TV).
There's been a long line of work aiming to improve the approximation
factor alpha.  alpha = 2 is possible for *improper* learners, but
proper learners can only hope for alpha = 3.  Getting alpha=3 in n^2 s
time is known; this paper gets that down to O~(ns) time (although an
extra eps factor in time, which they can avoid for alpha=4, and worse
delta dependence).
strength_weakness: strength_weakness: The algorithm overview is a bit vague, and could be written more
clearly.

The failure probability dependence isn't good.

The alpha=3 approach is a fairly simple extension of prior work, and
alpha=4 isn't so exciting.

I'm not sure that the constant here matters for the applications of
hypothesis selection.  Like, in the application where we choose a
cover for the class, presumably we can just make a finer cover?
questions: questions: Are there applications of hypothesis selection where the constant alpha matters?
limitations: limitations: Fine.
paper_summary: paper_summary: This paper introduces proper approximation algorithms for optimal hypothesis selection in the context of distribution learning.
The 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 
on $\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.
strength_weakness: strength_weakness: 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.

On 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.
questions: questions: -Table 1: Is the dependence on $1/\delta$ in $s$ just the standard $\log(1/\delta)$?  

-line 180: The order of logical quanitifiers can be reversed to get a slightly stronger and more illustrative statement here, correct?  
 
-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: limitations: Yes
paper_summary: paper_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)$
strength_weakness: strength_weakness: I want to give some minor suggestions. 

1. 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.

2. 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.

3. In line 327, I believe there is a typo in the equation $||H_{i^*}||_{TV}=...$
questions: 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: limitations: N/A
paper_summary: paper_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.

It 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.

This 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.

Here is an overview of Algorithm 1, outlined by the authors in Section 3:
- 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]$.
- 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$.
- 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.
- 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.
- 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.
strength_weakness: strength_weakness: 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.

Minor writing suggestions:
- 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.)
- Line 90: "a $O(\cdots)$ factor" --> "an $O(\cdots)$ factor"
- Line 270: "dependency" not capitalized.
questions: 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: Limitations are adequately addressed in Section 1.2.

Comments: comment: Thank you for your comment and for raising your score. 

We understand your concern regarding the direct usability of our algorithms in future work. While we cannot guarantee their applicability, our hope is that the novel perspective we introduced, along with the new algorithmic ideas, will lead to improvements in the time complexity of this problem. We will invest more effort in distilling the new algorithmic ideas and structural results into a form that is widely useful.
Thank you for your response.
Thanks for the reply. I do have a concern that the algorithmic techniques for the $\alpha=3$ case may not be very informative for future algorithmic development re: the discussion on prompting hypotheses above. However, in retrospect, I think this is probably a bit unfair, as I'm very far removed from the study of this particular problem. Thus, I revise my score to 5.

I do strongly encourage the authors do improve the presentation in the next version. Good work deserves good presentation.
Thanks for the response.
Thank you for your reply! I have no further questions, and my overall evaluation of the paper remains positive.