Hypothesis Selection with Memory Constraints
Authors: Maryam Aliakbarpour
Mark Bun
Adam Smith
Venue: NeurIPS 2023 poster (2023)
Keywords: Hypothesis selection
memory constrained algorithms
density estimation
limited space
TL;DR: In this work, we study the hypothesis selection problem in the presence of memory constraints, and we provide an algorithm that achieves a nearly optimal tradeoff between memory and the amount of data.

Abstract: Hypothesis selection is a fundamental problem in learning theory and statistics. 
Given a dataset and a finite set of candidate distributions, the goal is to select a distribution that matches the data as well as possible. 
More specifically, suppose we have sample access to an unknown distribution $P$ over a domain $\mathcal{X}$ that we know is well-approximated by one of a 
a class of $n$  distributions (a.k.a. hypotheses), $\mathcal{H} \coloneqq \{H_1, H_2, \ldots, H_n\}$. The goal is to design an algorithm that outputs a distribution $\hat{H} \in \mathcal{H}$ whose total variation distance from $P$ is nearly minimal.

In this work, we study the hypothesis selection problem under memory constraints. We consider a model where samples from $P$ are presented in a stream and we access each sample $x$ via ``PDF-comparison'' queries that allow us to compare the probability densities of any pair of hypotheses
at the domain point $x$ (i.e., is $H_i(x) < H_j(x)$?). This model allows us to study how much memory is needed at any point in time to store information about the portion of the stream seen so far.

Our main result is an algorithm that achieves a nearly optimal tradeoff between memory usage and the number of samples required. In particular, given $b$ bits of memory (for $b$ roughly between $\log n$ and $n$), our algorithm solves the hypothesis selection problem with $s$ samples, where $b \cdot s = O(n \log n)$. This result is optimal up to an $O(\log n)$ factor, for all $b$.

Hypothesis Selection with Memory Constraints
Maryam Aliakbarpour Department of Computer Science Rice University Houston, TX 77005
Mark Bun
Department of Computer Science Boston University Boston, MA 02215 mbun@bu edu
maryamarrice.. edu
Adam Smith
Department Computer Science
Boston University Boston, MA 02215 ads22@bu edu
Abstract
Hypothesis selection is fundamental problem in learning theory and statistics. Given a dataset and a finite set of candidate distributions, the goal is to select distribution that matches the data as well as possible. More specifically, suppose that we have sample access to an unknown distribution over domain X' that we know is well-approximated by one of class of n distributions (a.k.a. hypotheses), H = {HI,, H2....., H... The goal is to design an algorithm that outputs a distribution A E H whose total variation distance from is nearly minimal. In this work, we study the hypothesis selection problem under memory constraints. We consider a model where samples from P are presented in a stream and we access each sample æ via "PDF-comparison" queries that allow the probability densities of any pair of hypotheses at the domain point æ (i.c., is [1((x) (x)))). This model allows us study how much needs be stored, at any point in time, about the portion of the stream seen so far. Our main result is an algorithm that achieves a nearly optimal tradeoff between memory usage and sample complexity. In particular, given b bits of memory (for b roughly between log n and n)). our algorithm solves the hypothesis selection problem with s samples, where b. s On log n). This result is optimal up an O(log n) factor, for all b.
compare
Introduction
Learning the probability density function of observed data is a fundamental question in statistics with numerous applications in machine learning. Variants this problem have been studied for nearly a century. Hypothesis selection is classic version of this problem where the goal is to learn distribution within a pre-specified class. Let = (H,, Hz,..., Hn) } be class of known distributions over the same domain X. Suppose that we have sample access to an unknown distribution P over X' which is in, or very close to, member of H. The goal is design an algorithm that outputs distribution A E H whose total variation distance to is close to that of the closest distribution in H. A great deal of effort has been dedicated to solving this problem using number of samples that does not depend on the domain size | Perhaps surprisingly, one can learn unknown distribution P H. with (log samples, independent of the domain size. In contrast, learning an arbitrary distribution over requires (((x samples. Refined guarantees for this problem have been studied extensively, building understanding of the accuracy, sample
37th Conference on Neural Information Processing Systems (NeurIPS 2023).

---

complexity, and computational efficiency achievable, as well as the compatibility of hypothesis
selection with robustness and privacy Yat85] DL96 DL97 DLOT MS08 DDS12 DK14 DKST7
ADLS17
BKM19
BKSW19 CKM+19
GKK 20 ABH 20 BBK 21
In this paper, we expand upon the emerging theory of learning with limited memory [SD Raz 18 4hal4 DS18 DGKRT9 SSVI9
by studying hypothesis selection from this new perspective. We strive to answer the following questions: Given working memory of b bits, how many data points (samples) do we need to solve the hypothesis selection problem? Prior work assumes that we can store all the samples in the memory, which can be quite large when we aim to learn distribution over extremely large objects, such as, DNA sequences, gene expression data, text data, and brain image data.
BES22 AMNW22
We consider a model where samples are processed one at a time in a stream. Similar to models in [GR22 23, AF23]. we access each sample x via queries that allow to compare the PDF of Hy's at point and we measure the size of the memory retained between processing samples. Our main result an algorithm that achieves a nearly optimal tradeoff between the memory size and the number of samples s. Given b bits of memory (for b roughly between log n and n), our algorithm solves the hypothesis selection problem with s samples where b- O(n log n)). A result of Shamir [Sha14, Theorem 2] gives a class of n hypotheses H such that any algorithm that learns unknown distributions in H requires s b = 12()). Our tradeoff is thus optimal up to a O(log n) factor.
1.1 Main result
Suppose we have a class of n known distributions H. == {H1. Hz...., H and an unknown distribution P. We aim to design proper learning algorithm that outputs distribution in H whose total variation distance to P is comparable to that of the closest distribution in H. The algorithm has access a stream of i.i.d. samples drawn from P. At every given point, the algorithm can look at one sample, namely x, in the stream and query a PDF-comparator oracle by sending i, E [m]. and receiving bit indicating if (x) < H, (x). This is equivalent to asking whether sample æ in the Scheffé set of two distributions H; and Hj. which is defined as the set of elements to which Hj assigns higher probability than H4: The algorithm can also discard the current sample and move on to the next one. In addition to having access to the samples of P. we have more direct access to the known distributions in H. The algorithm can query the probability masses of the Scheffé sets according to each H; as is customary in the literature [DLO1] MS08]. This assumption can be relaxed; only estimates of such probabilities are needed, which can be obtained if we have sample access to H,'s. Further details are available in Remark 3 To summarize our access model, our algorithm can
make one of the following types of queries: 1) Request new sample. 2) Query the compaaaart
on the current sample x and ask if HI(x) < H, (r) for every pair of indices i. E [m]. 3) Asks for
the probability mass of Scheffé set between Ht, and Hj according to H, for every pair of indices i E [ri].
The accuracy of our output distribution is measured with respect to how far the best distribution in H. is from P. We define OP. P) = min ||P H [| When H. and P are clear from context, we denote this simply by OPT. With this setup in mind, we define a proper learning algorithm (with promise) for hypothesis selection. The term "promise" refers to the extra parameter I that the al algorithm receives as input: the learner may assume that OPT < Г. (See Remark 2 for the case where I is not provided.)
Definition 1.1. Suppose A has sample access to an unknown distribution P. And, can query the probabilities of the Scheffé sets according to each H; and a PDF-comparator for every pair of hypotheses in H. Assume A is given an additional input parameter r > O. We say algorithm H if the following holds: for every distribution P. if T OPT (H. P) then, with probability at least 8 over its input sample (drawn i.i.d. from P) and internal coin tosses, A outputs a distribution A E H such that:
an (a. c, 8) 5)-proper learner with a promise for
|P- A IIv a r+..
(I)
One can generally reduce and 5 by increasing the number of samples taken or the time spent, whereas the value of OPT, and hence T, inherent to the problem instance. Therefore, it is more important and challenging to design algorithms that minimize the multiplicative parameter
2

---

Main theorem: Our main result is a proper learner (with promise) that obtains a nearly optimal tradeoff between memory and data. Formally, we have the following theorem:
Theorem 1. There exists constant for which the following holds. Let H be an arbi- trary class consisting of n distributions, and let e > 0. For every natural number b where c- (logn n- logg(oo n))e)) S b S n, there exists an (a 9,,, = 0.1)-proper learner (with promise) for H using bits of memory and the following number of samples:
n logn
1 c²
()))
log
when S log log n
log
1 log
log n2 )) when
log log R b n.
2²
Roughly speaking, this theorem says that given b bits of memory that suffice perform basic opera- tions such as keeping track of indices and counting samples (i.e., b = S (log n + log((log n) /c))), then 8 b Rv On log(m)) (?) samples suffice to solve the hypothesis selection problem. A result of Shamir [Sha14] Theorem 2] gives class of n hypotheses H such that every algorithm that learns random P in H requires
b = ((n).. Our tradeoff is thus optimal up to an O(log)) n) factor. We speculate that our result is tight even for the class considered in [Shal4], but we leave the proof of a tighter lower bound to future work.
Remark 2. Both versions of the hypothesis selection problem (with and without a promise that OPT < I) have been extensively studied (e.g. (DLO1) DK14J). For simplicity, we present our result when I' is given a priori. Section (eroondddeebbbbe reduction that yields a similar result when I' is not provided; the accuracy guarantee is analogous to that of Equation 7 but for slightly larger a.
1.2 Overview of our key ideas and other results
Background on comparing two hypotheses: Like many previous hypothesis selection algorithms, our algorithm relies the ability to compare two hypotheses Hi and H2 based the probabilities of their Scheffé set S. We estimate P(S), and declare H; the winner for which H, (S) is closer to P(S). This natural approach works especially well when P (H1 H2) or when P is much closer to one of the two hypotheses. Intuitively, a near-optimal hypothesis H should win many comparisons against other hypotheses. A typical hypothesis selection algorithm will run toumnment to identify such an H. The primary advantage of using Scheffé based comparisons is that they are inexpensive to compute. Only Oloog n/e²) samples are sufficient estimate the probability masses of all Scheffé sets within an error of c. This exceptional sample efficiency enables the hypothesis selection algorithms circumvent the lower bound of | for distribution learning cases where we have prior knowledge that P is close to a particular class of distributions.
That being said, the Scheffé based comparisons are not straightforward. One challenge is that these comparisons are not ideal: even if our estimates of the probabilities of the Scheffé sets were perfect, we might pick the hypothesis that is further from P in total variation distance (because $ is just one event and might not ideally distinguish P from either H1 or H2). Furthermore, comparisons are not transitive (again, because we measure only Scheffé set probabilities). Essentially the only useful property they have this: if H, is I-ccose P. it will win; if H1 is much further from P (by a constant factor) than both I' and || H22 Pl[Tv, then it will lose. These issues make the outputs of comparisons hard interpret and complicate their use for selection.
To elaborate on our approach, we start by defining a acceptable hypotheses, and our general terminology for referring the quality of the hypothesis. We partition the hypotheses into three groups: 1) Excellent hypotheses, whose distance to P is r. 2) Decent hypotheses, whose distance to P is larger than I, but smaller than T c. These distances are set in a way that decent hypothesis may win against an excellent hypothesis. Decent hypotheses are challenging to deal with because they may fool us into believing that an excellent hypothesis not a good output, yet later they may lose against a very far hypothesis. 3) Unacceptable hypotheses, whose distance to P is larger than 3r + e, which will lose to every excellent hypotheses. We say a hypothesis is acceptable if it is either excellent or decent. Generally, the goal is to find an acceptable hypothesis.
Our terminology:
3

---

1.2.1 Random ladder tournament
The main technical tool we introduce is a simple algorithm we call the random ladder tournament, which is inspired by ladder tournaments, type of tournaments used in games and sports. Our algorithm finds an acceptable hypothesis using a linear number of comparisons. The algorithm proceeds in rounds as follows. Holding to a single hypothesis in each round, we sample a uniformly random hypothesis from H. and compare it to the current hypothesis. The winner proceeds to the next round. Our novel analysis of this tournament shows that after O(HH) rounds, either the final winner produced at the end of the tournament or a winner selected randomly along its trajectory will be acceptable with high probability.
Proof overview: As previously mentioned, comparisons often far from ideal: Even when the excellent hypothesis wins at a certain step, there is no guarantee that it would remain the winner till the end. To evade this issue, we utilize our knowledge of the upper bound of OPT, denoted by T, and modify the comparisons in a way that ensures the excellent hypothesis never loses once it wins. In our comparisons, we favor the current winner; If the distance of the current winner to P on the Scheffé set is at most I. we declare the current winner as the winner (even when the opponent hypothesis seems closer). Clearly, the excellent hypothesis will never be more than I away for P on any set. Hence, it will never lose again.
However, what happens when the excellent hypothesis never wins? At each step, we pick each hypothesis in H. uniformly at random, implying the excellent hypothesis is expected to be chosen in at least (1) steps in our algorithms. The fact that the random hypothesis loses the current winners of those steps indicates that those winners must be acceptable hypotheses; otherwise, the excellent hypothesis would have won them. Additionally, the fact that the excellent hypothesis appears as the random hypothesis in O()) steps and loses to all of them, confirms that constant fraction of the current winners are indeed acceptable. By combining these observations, we prove that the random ladder tournament will either find the excellent hypothesis at the end or encounter many acceptable hypotheses along the way.
Implementing the tournament with memory constraints: This algorithm is highly effective technical tool for solving our problem. It can be implemented in a very memory-effiiientt manner. The algorithm processes the hypotheses in an "online" fashion, and it does not need to memorize the result of any past comparisons. At any given moment, it only remembers two hypotheses: the current hypothesis and the next randomly drawn hypothesis. And, if we draw fresh samples for every comparison, we can implement this algorithm by storing essentially O(1) numbers but sampling O(n log(n) data points. On the other extreme, we can implement this algorithm with very little data, i.e., Olog 2) samples, but large amount of memory by storing an appropriate "summary" of samples (e.g., the probabilities of all the Scheifé sets in ( bits).
We leverage this flexibility in memory usage of the random ladder tournament and provide an algorithm that only uses b bits of memory. We perform the comparisons in the random tournament in blocks of size I. For each block of comparisons, we draw new samples and store a summary of them. We pick the parameter / in way that the summary fits in b bits, and it is sufficient for perform the next the & comparisons. For example, if t Vb, we can store the number of samples in all the Scheffé sets of t hypotheses in b bits. This summary is enough for us to perform any comparisons between those hypotheses. Combined with a novel surtary-Sorted lists, described in Section 2.2.2 we get a tradeoff of the form s b R: On log" (n)) In Section 3.2. we presented this tradeoff alongside another tradeoff (with better dependence to e, but worse dependence to log n). Both of these tradeoff are worse than our main result, in a sense that is larger by a factor of ([pol((log()) 1/e)). However, the these results are yielding more accurate proper learners; For the random ladder tournament, 3, while in our main result 9.
Simpler linear-time selection: The random ladder tournament leads to new results for the hypoth- esis selection problem outside of the scope of our original motivation for this paper. If we ignore memory constraints and store every sample, the random ladder tournament algorithm is simultane- ously near-optimal in terms of number of samples, time, and accuracy - to our knowledge, it is the first such algorithm. Specifically, it makes linear number of comparisons and uses Ollog n/e²) samples from P. which are both optimal for worst-case choices of H. Moreover, finds a hypothesis with optimal accuracy under a promise. More precisely, it finds a hypothesis in H that is roughly
4

---

3 3--close to P given a parameter I' that is guaranteed to be at least OPT. This is essentially opti- mal, as no proper learning algorithm can achieve accuracy better than 3 OPT [BKMI9 even when T= OPT is given to the algorithm. Furthermore, with simple adjustment to our algorithm, one can solve the hypothesis selection problem without any knowledge of I in nearly linear time and with roughly the same number of samples and obtain a 5 OPT-close hypothesis in H. See Section C
1.2.2 Improved tradeoff by hypothesis filtration
The flexibility of the random ladder tournament already results in memory-date tradeoffs, but these are suboptimal by a factor of poly(log n, 1/c). To improve the result, we design an algorithm called filter, that picks an acceptable hypothesis with modest chance. While this chance is not high, we can use the output of the filtration and run the random ladder tournament on these filtered hypotheses. Since the quality of the input hypotheses in this second round is better, the random ladder tournament can be implemented effectively on smaller set H and results in a better tradeoff. Hence, we obtain our main result. See Section f.r the proof of our main results. Below, we give a short description of the filter algorithm. We defer the full description and the proofs to Section [.3]
hypothesis filtration:
The best approach to finding an acceptable hypothesis drastically depends the quality of the hypotheses in H. For example, if there is no decent hypothesis in H. any single elimination tournament will easily find an excellent hypothesis due to the fact that any comparison involving at least one excellent hypothesis will declare the excellent hypothesis the winner. On the other hand, if there are a lot of decent hypotheses, then there is a decent chance that randomly selected hypothesis is decent, hence an acceptable one. The filtration algorithm works by combining these two observations. The algorithm randomly performs one of the following, each with probability 1/2: 1) draws a set of random hypotheses. Assuming there no decent hypothesis in the set, it runs group elimination tournament (see below), and outputs the result. 2) It outputs random hypothesis in H. One can show that if the decent hypotheses are scarce in H. we have a decent chance of getting an excellent hypothesis and no decent hypothesis in the random set; hence, we find an excellent hypothesis via our group elimination algorithm. On the other hand, if the decent hypotheses are abundant, then we have a decent chance of picking one in the second step. By selecting each strategy with a probability 1/2, we preserve half of the success probability in whichever case holds. While this probability is not a lot, it is larger than 1/n (the probability of picking the excellent hypothesis from H). We take advantage of this fact, and show one can run the random ladder tournament in fewer rounds and obtain the desired result. See Section [B.3 for more details.
Group elimination tournament: Our second technical tool is an algorithm that finds an excellent hypothesis if no decent hypothesis exists in H. This algorithm is combination of a singlc-elimination tournament and an all- -o---aaaiinnt-llll tournament. In this algorithm, at every step, we partition the hypotheses into multiple groups, run a previously known all all-go-against-all tournament within each group (say minimum distance estimate [DLOT MS08), and then send the winners of each group to the next round. If group contains an excellent hypothesis, then in an all-go-against--a tournament, we will pick an excellent hypothesis as the winner. Hence, an excellent hypothesis will "bubble up" in each round and be declared the final winner. With careful choice of group sizes and the number of rounds, this algorithm can be implemented using O(n) bits of memory and O(log n) samples under the assumption that the hypotheses are indexed from 1 to A technical challenge that arises, however, is that we need to run this algorithm on a subset of roughly O(b) random hypotheses (so that we can run it within memory bound of b). However, storing b random indices already requires O(b Obblog n) space. We show that we can instead draw indices pseudorandomly using a pairwise independent generator that can be implemented in small space. See Section B.I for more details.
1.3 Related work
Prior to our work, numerous studies have investigated the problem of hypothesis selection in various settings. In their seminal work, Yatracos [Yat85), and Devroye and Lugosi [LL6 DL97 DLO1 present algorithms to find a close distribution in H based on only estimation of the probabilities of the Scheffé sets of pairs of hypothesis in H. These approaches suggest that only need accurate
estimation of the probability that P assigns to ( ?)
O(n²) sets, resulting in sample complexity proportional to Ollog n.) instead of ()) For a comprehensive overview, see Chapter 6 in (DLOI).
Mahalanabis and Stefankovic in [MS08] provide an algorithm with linearly many probes to P and = 3 but they require an exponential time pre- pre-processing of the class H H Daskalakis and Kamath
It is worth noting that do not have any pre- pee-processing step in this paper.
5

---

in D give hearly-linear time algorithm that given an upper bound on OPT - T, returns H such that H Pl TV I aa.Te e for some large constant = 512. Acharya et al. in AJOOS4 AFJ 18) provide a On log n) time algorithm that finds a hypothesis with accuracy guarantee of 9. For proper learners, Bousquet et al. in [BКМ19 showed that the best in Equation | that one can hope for is a = as long as the sample complexity does not grow with the domain size | Aamand et al. in 23AC+ also study statistical computational tradeoff's (time-data) for the hypotheses over discrete domains. Unlike our work, their setting allows pre-processing of the class H. in polynomial time.
There is long history of research focusing on a special case of this problem where H is specific structured class of distributions such as mixtures of Gaussians [KVV12 DK14 SOAJ14 KSS18
ABMI8 ABH 20), histograms [Pea95 CDSS14 CDKL22), and polynomials [ADLSI7. The abstract hypothesis selection we study here is commonly used as subroutine solving these problems (usually in conjunction with some sort of a cover method). For a survey of results,
see Dial6].
Lastly, there is another field of study that tackles question similar to ours: the problem of sorting items with noisy comparisons. One can view hypothesis selection as the task of finding the minimum item. With the exception of [AF]+ 18] that we have discussed above, these probabilistic noise models do not capture the geometric structure presenting in our problem. Therefore, we did not find any of these result yielding an immediate solution to our problem.
2 Preliminaries
2.1 Notation
Let [n]] denote the set {1, 2, ..). Suppose that we have a probability distribution I over a domain X. For element x in X, P(x) denotes the probability of z. We assume X' is the domain of all the probability distributions in this article. For any subset of the domain S, P(S) denotes the sum of the probabilities of all the elements in S. We denote the total variation distance between two distributions Pi and P2 by [| - P2l/TV. and it is defined as maxşç (P) P2(S] where S is any measurable subset of the domain. We say P is e-close to Q iff P Ql at most e. Also, we say e-far from Q iff P QlITy is greater than e. We denote the Scheffé set of two distributions as follows: S(H, H2) = {x E X (x)x) < H2(z)}
2.2 Basic tools
In this section, we focus our primary tools we have used throughout this article. First, we start with a comparisons algorithm that allows us to compare two hypotheses. Next, we use the fact that one estimate the probabilities of the Onn?) many Scheffé sets up to error e (for some small constant c < 1) with probability at least 5 using Ollo((//)) (n/))/2) samples from P.
2.2.1 Comparing two hypotheses
Our algorithms works based basic operation that allows us compare two hypotheses H1 and Hz based on the probabilities of their Scheffé sets. We pick the hypothesis that appears to be closer to P and declare it the winner (and the other hypothesis the loser). The challenging part is that these comparisons are not ideal. As in, even when our estimations of the probabilities of the Scheffé sets are accurate enough, we may pick hypothesis that is further. However, one can guarantee that if the distance of the further hypothesis among H1 and H2 is much worse than the distance of the closer one, the comparison procedure would never select as the winner. The algorithm is given three parameters: I) I: an upper bound for OPT; 2) e: indicating the estimation error for the Scheffé set probabilities ((e); and 3) the confidence parameter ò. Upon invoking this algorithm, it determines the result of the comparison with the guarantees formalized in the following lemma:
Lemma 2.1. Upon receiving three parameters: r, C, and 8, Algorithm | uses (log((1/8){{) samples and satisfies the following guarantees with probability at least
If H2 is --close to P, then the algorithm returns H1.
If H, is (max (T, || Pl]rv) + H2 Pllrv + e) e)-far from P, then the algorithm re- turns Hz.
6

---

The proof of this lemma is provided in Section D
Algorithm Choosing between two hypotheses
procedure C Hy. r, c, 6, sample access to P)
2:
Draw m = (log 1/5)/²") samples from P
q - fraction of samples from P in S(H,, H2) using the PDF-comparator.
4:
Pi + H1 (S, H, H2)).
P2 x H2 (S H2)).
6:
c/c
if Fl - al ST+ d' or 1pi - q S lp - then
8:
Output H1.
Hi is the winner.
9:
else
10:
Output H2.
H2 is the winner.
Remark 3. While we have assumed that we have access to the probabilities of the Scheffé sets in the above algorithm, this assumption is not necessary. In fact, can obtain similar guarantees Lemma 2. ass long as we have estimates of these probabilities to accuracy e e for a sufficiently small constant e < 1. Hence, our result can be adjusted to the setting that we have sample access H 's instead.
Our terminology based on comparisons: We say a distribution H is excellent iff || [ - 1ly is I. We usually use H" to denote excellent hypothesis. We say distribution H is decent iff || PllTv is greater than I, but smaller than 3 r + e. It implics that a decent hypothesis may win an excellent H E H. We say a distribution H is acceptable iff it is excellent or decent. And, say distribution H is unacceptable iff it is not acceptable. Note that is impossible for an unacceptable hypothesis to win an excellent hypothesis with probability greater than 8. Throughout this article, when we say valid comparisons, we refer to an event in which the Scheffé sets are estimated accurately, so the conditions in Lemma 2.1 hold. Since have only (n²) many Scheffé sets, using Ollo((n88//e) samples is enough to assume all the comparisons are valid with a probability of at least - 6.
2.2.2 Space efficient sample summaries for comparisons within a batch of hypotheses
In order to obtain sample efficiency, we need sufficient information about samples that enables us to reuse the same set of samples for multiple comparisons. Below, we describe two approaches to summarize the sample set.
Scheffé counts. Observe that compare two hypotheses H1 and H2, only use the count of the number of samples in their Scheffé set S(H,, H2). Hence, instead of storing samples directly, for every pair of hypotheses in H., we store the number of samples in their Scheffé set. We refer to this number as the Scheffé counts. If we have m samples, we can store all the O(n²) Scheffé counts using O(n log m) bits.
Storing each sample via sorted list. In this approach, store succinct summary of cach sample that allows us to infer its membership in each Scheffé set. This information suffices to perform the comparisons we need later. To store a sample x, save ordered list of hypotheses that is sorted according to the probability of x (the PDF at point 2)). That is, we store a list of indices i1, 12....,44 in such that H,, (x) < H,, (x:) I < H,, (2) (use hypothesis indices to break the tie). The summary of a single sample can be computed in O(n log n) time and takes (On log n) bits of space store. Now, to compare the PDF of two hypotheses H, and Hj, we simply can find and in the list and check whether precedes in the list Alternttvvly if we want to compare PDF's s faster, we can store the indices in another list call dz that maps indices to list positions. We set d, [ie] = E simple check if dz(() dz).).
for every l [n]] In this case, to compare the PDF's,
2.2.3 All all-gslagainst-all tournament
There are standard techniques the literature to solve hypothesis selection problem when the estimates of all the Scheffé sets are available. See Chapter 6 in [DLOT] and [MS08] These approaches
PIt is worth noting that we may not answer the PDF-comparison correclly when H²(x) = H, (x). However. since r does not contribute to the discrepancy between H, and Hy. its inclusion (or exclusion) to the Scheffé set is inconsequential.
7

---

Algorithm Random ladder tournament
procedure RANDOM LADDER TOURNAMENT(H, Po. I, e, sample access to P and D)
2: h +- 12000/po]
3: Q < an empty list.
4:
Wo <
> Assume Wo is hypothesis that always loses.
5:
for = 1, ..... & do
6:
R; f a random hypothesis drawn from D
W. COMPARE(W.-.. R2 r, 6, 1/(100
8:
Add W; to Q. with probability po-
9: Add WE to Q.
10:
Output random hypothesis Q-
suggest that we only need accurate estimation of the probability that P assigns to ((1H(( =O sets, therefore, the sample complexity can be proportionate (logn) instead of (( For a formal statement, see Fact D.I
3 Random ladder tournament
In this section, we focus on the Random ladder lournament which is a proper learner (with promise) of in finite class of hypotheses, H. The algorithm is given parameter an upper bound for OH, X). It outputs H E H such that, with high probability we have: || TV S 3T + c. Bousquet et al. in [КММ1 have shown that no proper learner can achieve an error better than 3PT c unless the sample complexity grows with the domain size [X Their lower bound holds even when the algorithm is provided with r = OPT. Hence, the factor 3 above is optimal.
For clarity in our presentation, in Section 3.1 we present the random ladder tournament assuming that: 1) We set the confidence parameter to be a small constant (6 0.1). 2) the algorithm can call the COMPARE subroutine without specifying how this subroutine is implemented. In Section A.T we show one can modify this algorithm to work for arbitrary small confidence parameter 5. Also, in Section 3.2, we discuss how one can implement this algorithm with memory constraints. We use the sample summary approaches described in Section 2.2.2] and we obtain two (sub-optimal) memory-date tradeoffs for this algorithm.
3.1 Random ladder tournament with no memory constraints
In this section, we present the random ladder tournament that solves the hypothesis selection problem while a parameter I is given to the algorithm as an upper bound for OPT. For this result, we assume there is meta distribution over H. denoted by D. with non-negligible probability po draw a hypothesis that is OPT-close. The algorithm considers hypotheses one at a time where at step i, we draw R, from the meta distribution. While later we use this algorithm with other meta distributions, it may help the reader to view the meta distribution as uniform distribution over a set of hypotheses. H. In this case, if we draw random hypothesis from H. it is guaranteed be r-close to P with probability po 2 1/n. Our algorithm finds a sufficiently close hypothesis using (1/po) comparisons.
At high-level, our algorithm goes through list of randomly drawn hypotheses from D, compares them, and keeps track of the current winner hypothesis. We denote the current winner hypothesis at step by W,. Initially, we start with Wo being equal a fake hypothesis that loses to any other hypothesis. Then at every step, we take randomly drawn hypothesis R; and compare it with W We the current winner of step W,. be the winner of a comparison between W,- and RG We show that after k = (1/Po) steps either the final winner, Wt, is an P-close hypotheses, or many of W, 's that we have encountered are close to P. That is, either WA an excellent hypothesis or random W; is an acceptable choice. To exploit this fact at every step, we add each W; to list, namely Q, with some small probability. At the end, we also add Wx to Q. We prove a random hypothesis in Q will be close to P with high probability. Algorithm 2 shows the formal description of our approach, and we prove its performance Theorem Figure lustratee a visual representation of the algorithm.

---

Theorem 4. Suppose we can draw i.i.d. random hypotheses from an arbitrary meta distribution 'D over H. And, we have a hypothesis P that we aim to learn properly H. Assume we are given parameters po and I such that the probability that random hypothesis is P-close to P is at least po- For any 6 (0, 1), Algorithm (a = 3,6, 0.1 proper learner (with promise) for the class H.
Proof. First, note that each comparison, invoked in Line 7 will satisfies the properties of Lemma 2. with probability at least 1 1/ k-) Hence, using Lemma 2.1 and the union bound, one can assume with probability 0.99 for all the comparisons we have:
If W; is r'cclose to P. it will not lose; it remains as the current winner for the rest of the steps: W.- W1+1
Wk.
If W is (31' + e)-far from P. and R; is I'-close to P. then W; is equal to Rt
For the rest of this proof, we fix the response of comparisons for which the above conditions hold. The randomness used in the rest of this proof only depends on the randomness the meta distribution over hypotheses and the internal coin tosses of the algorithm.
Our goal is to show that most of the hypotheses in the list, Q, are acceptable, so a randomly selected hypothesis in will be acceptable as well. Our first step acceptable hypotheses in Q is high compared to the size of Q. For each in [k]. we define an indicator random variable I, that is if add an acceptable hypothesis the Q at step i Line [8] and zero otherwise. Also, we define another indicator variable Tx+1 corresponding to the event that the final WR. which we added Q in Line g is an acceptable hypothesis. More formally, we have:
show that the expected number of
4 Wris acceptable, and we add W. to in Line
Vi [k]
Tx+1 = 1 W acceptable.
Clearly, the sum 4's indicates the number acceptable hypotheses Q, so we focus on finding a lower bound for the expected value of this quantity. Let be the probability of W; being acceptable. Without loss of generality. we set an equal to zero. is not hard to see that: E[L] = Po a, for E [k]. Moreover for the last indicator variable, we have:
B[ = Pr[We We being acceptable] 2 Pr[[[ - Pllrv ST]
Σ
Pr[W,- loses to R2, and R. Pllrv S D and R, does not lose to R,41, Rs42, .... Rx
Assuming the pairwise comparisons are done perfectly, R, being -'close to P. automatically implies that R₁ does not lose go any of the hypotheses Rit1,..., Rg. Thus, we have:
E[ 2 Σ
Pr[ loses to R3 and R Pl[tv $ TT]
Pr[W,-1 loses to R; |R, - Plltv =T] Pr[ - -Pllv $ r].
Note that the probability of RR; PllTy < certainly win any hypotheses that (3 c)a-frr from P. Thus, the event that W, is (3T + c)-far must have lower probability than the event that W,- loses to R, Therefore, obtain the following lower bound:
T is at least Now given that RG is P-close to P, it will
E Σ Pr[ Pllv > (eT++) [R, Pllrv ST) Po
Σ Pr[ being unacceptable RR Pll & T] Po
Recall that we pick R3 independently from all the previous hypothesis, R1, R2...., ..,, Ri-15 so one can say Wi1 is independent of R. This implies:
9

---

k
El1++1
Pr W being unacceptable] Po =
Σ (1 ai-1) po .po
i=1
Putting all together, the expected value the sum of I is:
E
po aa + (ii-1) po lo Po + po (ax -0a) 2 k po
==1
The last inequality above is due the fact that on to zero. Note that the above equation states that the expected number of acceptable hypotheses in Q is at least k Po- On the other hand, the expected number of hypotheses in Q k Po 1. Thus, the expected number of unacceptable hypotheses in Q is at most one. Now, by Markov's inequality, the probability that we have more than 50 unacceptable hypotheses in Q most 0.02. And, by the Chernoff bound, we know that the probability of having less than 1000 many hypothesis in Q is at most:
Pr[ #hypotheses in Q 1000] Pr Bin po) < k Po
(-
k 110
S exp
S 10-100
2
It not hard to see that the ratio of unacceptable hypotheses the total number of hypotheses in Q is at most 50/1000=0.05, Therefore, a random hypothesis in Q is acceptable with probability at least 0.95. Hence, by the union bound the total error probability is bounded by:
Pr Pr[Outputting unacceptable hypothesis]
< Pr[Outputting unacceptable hypothesis valid comparisons
Pr(at least one invalid comparisons] 0.05 + 0.01 < 0.1
Therefore, the proof' is complete.
3.2 Memory-data tradeoffs random ladder tournament
As we have discussed, one of the advantages of Algorithm i is its flexibility in the usage of memory and data. In the following, we describe tradeoff that we can obtain for this algorithm using the sample summaries presented in Section tradeoff: suppose we have b bits of memory. We choose the largest integer t so that we can store the sample summary needed to compare t hypotheses. Then, we run the random ladder tournament while we draw new samples and refresh the sample summary at every t step. Our two described sample summaries Scheff' e counts and the sorted list lead to the following memory-dat tradeoffs. Although these tradeoff's are not as tight as our main result (by factors of log n and 1/e), they have better accuracy guarantees (a = 3 instead of a = 9 in our main result).
At a high-level, the following is how we achieve the
Lemma 3.1. Suppose we have n hypotheses in H. For every po 2 L/n, e, and an integer between two and k (1)/p)), one can implement Algorithm in such away that it uses:
s =
0=0
1
log Po e2
samples, and
b b=0 b=o log log loogPo'
)) tlggn bits of memory.
tpo
Lemma 3.2. Suppose we have n hypotheses in H. For every Po 2 1/n, e, and an integer I. between two and k @1 (1/) one can implement Algorithm such away that uses:
s == 0 0
1
log logro") 22
b= o
log(pō 1) logn
samples, and
+ t tlogn
bits of memory.
too
22
For the proofs of the above lemmas, see Section
A.2
10

---

Acknowledgement
MA was supported by NSF awards CNS-2120667, CNS-2120603, CCF-19348444 and BU's Hariri Institute for Computing. This work was predominantly done while MA was affiliated with Boston University and Northeastern University. MB was supported by NSF awards CCF- 1947889 and CNS- 2046425, and Sloan Research Fellowship. AS was supported part by NSF awards CCF-1763786 and CNS-212066) as well as Faculty Awards from Google and Apple.
References
[AAC*23] Anders Aamand, Alexandr Andoni, Justin Y. Chen, Piotr Indyk, Shyam Narayanan, and Sandeep Silwal. Data structures for density estimation. In Proceedings of the 40th International Conference on Machine Learning. PMLR, 2023.
[ABH* 20] Hassan Ashtiani, Shai Ben-David, Nicholas J. A. Harvey, Christopher Liaw, Abbas Mehrabian, and Yaniv Plan. Near-optimal sample complexity bounds for robust learning of gaussian mixtures via compression schemes. J. ACM, 67(6)3221-32224 2020.
[ABM18] Hassan Ashtiani, Shai Ben-David and Abbas Mehrabian. Sample-efficient learning of mixtures. In Sheila A. Mcllraith and Kilian Q. Weinberger, editors, Proceedings of the Thirty-Second AAAI Conference on Artificial Intelligence, pages 2679-2688 AAAI Press, 2018
[ADLS17] Jayadev Acharya, Ilias Diakonikolas, Jerry Li, and Ludwig Schmidt. Sample-optimal density estimation in nearly-linear time. In Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA, pages 1278-1289) SIAM, 2017.
[AF23] Tomer Adar and Eldar Fischer. Refining the adaptivity notion in the huge object model. CoRR, abs/2306. 16129, 2023.
[AF]+ 18] Jayadev Acharya, Moein Falahatgar, Ashkan Jafarpour, Alon Orlitsky, and Ananda Theertha Suresh. Maximum selection and sorting with adversarial comparators. The Journal of Machine Learning Research, 19:59:1-5::31, 2018.
[AJOS14] Jayadev Acharya, Ashkan Jafarpour, Alon Orlitsky, and Ananda Theertha Suresh. Sorting with adversarial comparators and application to density estimation. In 2014 IEEE International Symposium on Information Theory, pages 1682-1686, 2014.
[AMNW22] Maryam Aliakbarpour, Andrew McGregor, Jelani Nelson, and Erik Waingarten. Esti- mation of entropy in constant space with improved sample complexity. In S. Koyejo, S. Mohamed, A. Agarwal, D. Belgrave, K. Cho, and A. Oh, editors, Advances in Neural Information Processing Systems, volume 35, pages 32484-32486. Curran Associates, Inc., 2022.
[BBK+21] Olivier Bousquet, Mark Braverman, Gillat Kol, Klim Efremenko, and Shay Moran. Statistically near-optimal hypothesis selection. In 62nd IEEE Annual Symposium on Foundations of Computer Science, FOCS 2021, Denver, CO, USA, February 7-10, 2022, pages 909-919. IEBE, 2021.
[BBS22] Gavin Brown, Mark Bun, and Adam Smith. Strong memory lower bounds for learning natural models. In Proceedings of Thirty Fifth Conference on Learning Theory COLT, 2022.
[BKM19] Olivier Bousquet, Daniel Kane, and Shay Moran. The optimal approximation factor in density estimation. In Alina Beygelzimer and Daniel Hsu, editors. Proceedings of the Thirty-Secome Conference on Learning Theory, volume 99 of Proceedings of Machine Learning Research, pages 318-341. PMIR, 25-28 Jun 2019.
[BKSW19] Mark Bun, Gautam Kamath, Thomas Steinke, and Zhiwei Steven Wu. Private hypoth- esis selection. In Hanna M. Wallach, Hugo Larochelle, Alina Beygelzimer, Florence d' Alché-Buc,, Emily B. Fox, and Roman Garnett, editors, Advances Neural Infor- mation Processing Systems 32: Annual Conference Neural Information Processing

---

Systems 2019, NeurIPS 2019, December 8-14, 2019, Vancouver, BC, Canada, pages 156 167-167,20 2019.
[CDKL22] Clément L. Canonne, Ilias Diakonikolas, Daniel Kane, and Sihan Liu. Nearly-tight bounds for testing histogram distributions. In Advances in Neural Information Process- ing Systems 35 (NeurIPS), 2022. To appear.
[CDSS14] Siu-on Chan, Ilias Diakonikolas, Rocco A. Servedio, and Xiaorui Sun. Npar-optimal density estimation in near-linear time using variable-width histograms. In Advances in Neural Information Processing Systems 27: Annual Conference on Neural Information Processing Systems 2014, December 8-13 2014, Montreal, Quebec, Canada, pages 1844 1852. 2014.
[CFG+23] Sourav Chakraborty, Eldar Fischer, Arijit Ghosh, Gopinath Mishra, and Sayantan Sen. Testing of index-invariant properties in the huge object model. In 36th Annual Conference on Learning Theory- COLT, 2023.
[CKM* 19] Clément L. Canonne, Gautam Kamath, Audra McMillan, Adam D. Smith, and Jonathan R. Ullman. The structure of optimal private tests for simple hypotheses. In Moses Charikar and Edith Cohen, editors, Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, STOC 2019, Phoenix, AZ, USA, June 23-26, 2019, pages 310-321. ACM, 2019.
[DDS12] Constantinos Daskalakis, Hias Diakonikolas, and Rocco A. Servedio. Learning poisson binomial distributions. In Howard J. Karloff and Toniann Pitassi, editors, Proceedings of the 44th Symposium on Theory of Computing Conference, STOC 2012, New York, NY, USA, May 19 22, 2012, pages 709-728. ACM, 2012.
[DGKR19] Ilias Diakonikolas, Themis Gouleakis, Daniel M. Kane, and Sankeerth Rao. Communi- cation and memory efficient testing of discrete distributions. In Alina Beygelzimer and Daniel Hsu, editors, Proceedings of the Thirty-Second Conference on Learning Theory, volume 99 of Proceedings of Machine Learning Research, pages 1070-1106. PMLR, 25-28 Jun 2019.
[Dia16] Ilias Diakonikolas. Learning structured distributions. In CRC Handbook of Big Data, pages 267-283. 2016
[DK14] Constantinos Daskalakis and Gautam Kamath. Faster and sample near-optimal algo- rithms for proper learning mixtures of gaussians. In Conference on Learning Theory, pages
PMLR, 2014.
[DKS17] Ilias Diakonikolas, Daniel M. Kane, and Alistair Stewart. Statistical query lower bounds for robust estimation of high- sige-dimensional gaussians and gaussian mixtures. In Chris Umans, editor, 58th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2017, Berkeley, CA, USA, October 15-17, 2017, pages 73-84, IEEE Computer Society, 2017.
[DL96] Lue Devroye and Gábor Lugosi. A universally acceptable smoothing factor for kernel density estimates. The Annals of Statistics, 24(6):2499 - 2512, 1996.
[DL97] Luc Devroye and Gâbor Lugosi. Nonasymptotic universal smoothing factors, kernel complexity and Yatracos classes. The Annals of Statistics, 25(6):2626 - 2637, 1997.
[DL01] Luc Devroye and Gâbor Lugosi. Combinatorial methods in density estimation. Springer, 2001.
[DS18] Yuval Dagan and Ohad Shamir. Detecting correlations with little memory and com- munication. In Sébastien Bubeck, Vianney Perchet, and Philippe Rigollet, editors, Proceedings of the 31 Conference On Learning Theory, volume 75 of Proceedings of Machine Learning Research, pages I 1145-1198. PMLR, 06-09 Jul 2018
12

---

[GKK 20] Sivakanth Gopi, Gautam Kamath, Janardhan Kulkarni, Aleksandar Nikolov, Zhi- wei Steven Wu, and Huanyu Zhang. Locally private hypothesis selection. In Jacob Abernethy and Shivani Agarwal, editors, Conference on Learning Theory, COLT 2020, 9- July 2020, Virtual Event [Graz, Austrial, volume 125 of Proceedings of Machine Learning Research, pages 78861186. PMLR, 2020.
[GR22] Oded Goldreich and Dana Ron. Testing Distributions of Huge Objects. In Mark Braverman, editor, 13th Innovations in Theoretical Computer Science Conference (ITCS 2022). volume 215 of Leibniz International pages 78:1-78:15 19, Dagstuhl, Germany, 2022. Schloss Dagstuhl Leibniz-Zentrum für Informatik.
Pronaloooooo Proceedings in Informatics (LIPlcs),
[KMV12] Adam Tauman Kalai, Ankur Moitra, and Gregory Valiant. Disentangling gaussians. Commun. ACM, 13--120, 2012.
[KSS18] Pravesh K. Kothari, Jacob Steinhardt, and David Steurer. Robust moment estimation and improved clustering via sum of squares. In Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2018, Los Angeles, CA, USA, June 25-29, 2018, pages 1035-1046. ACM, 2018.
[MS08] Satyaki Mahalanabis and Daniel Stefankovic. Density estimation in linear time. In 2/st Annual Conference Learning Theory COLT, pages 503-512, 2008
[Pea95] Karl Pearson. Mathematical contributions to the theory of evolution. ii. skew variation in homogeneous material. [abstract]. Proceedings of the Royal Society of London, 57:257-260, 1895.
[Raz18] Ran Raz. Fast learning requires good memory: A time-space lower bound for parity learning. Journal of the ACM (JACM), 66(1):1-18, 2018.
[SD15] Jacob Steinhardt and John Duchi. Minimax rates for memory- -ounded sparse linear regression. Peter Grünwald, Elad Hazan, and Satyen Kale, editors, Proceedings of The 28th Conference Learning Theory, volume 40 of Proceedings of Machine Learning Research, pages 1564-1587. PMLR, 03-06 Jul 2015.
[Sha14] Ohad Shamir. Fundamental limits of online and distributed algorithms for statistical learning and estimation. In Advances in Neural Information Processing Systems 27: Annual Conference on Neural Information Processing Systems 2014, December 8-13 2014, Montreal, Quebec, Canada, pages 163-171, 2014.
[SOAJ14] Ananda Theertha Suresh, Alon Orlitsky, Jayadev Acharya, and Ashkan Jafarpour. Near-optimal- -sapll estimators for spherical gaussian mixtures. In Z. Ghahramani, M. Welling, C. Cortes, N. Lawrence, and K. Weinberger, editors, Advances in Neural Information Processing Systems, volume 27, 2014.
[SSV19] Vatsal Sharan, Aaron Sidford, and Gregory Valiant. Memory-sample tradeoffss for linear regression with small error. In Moses Charikar and Edith Cohen, editors, Proceedings of the 51st Annual ACM SIGACT Symposium Theory of Computing, STOC, pages 890-901. ACM, 2019.
[Vad12] Salil P. Vadhan. Pseudorandomness. Foundations and Trends@ in Theoretical Computer Science, 7(1-3):1-336, 2012.
[Yat85] Yannis G. Yatracos. Rates of convergence of minimum distance estimators and kol- mogorov's 's entropy. The Annals of Statisties, 13(2):768 -774, 1985.
13

---

R, 's drawn from according the meta distribution.
R1
R2
RS
winner
Wo
Compare
W1
Compare
W2
Compare
WR
Wi's are added to Q with some small probability.
Wi is always added to Q.
selected from members of Q uniformly at random.
H
Figure Random ladder tournament
A Random ladder tournament (cont.)
Figure Iillustrates visual representation of the algorithm.
A.1 Amplitying the confidence parameter
In this section, we describe how one can amplify the confidence parameter of the random ladder tournament. Note that to keep = 3, should avoid any two-step process that comes up with collection of hypotheses to narrow down the possible choices and then pick an acceptable hypothesis among them. Such approaches generally lead to the random ladder tournament for a longer time, a random hypothesis in Q will be acceptable with very high probability. In particular, if we set k, the number of steps equal to (11((8 po)) (instead of setting & = (11po))) we find an acceptable hypothesis with probability at least 1.
or higher. Here,
argue that if we run
Corollary A.1. Suppose that can draw i.i.d. random hypotheses from arbitrary mela distri- bution D over H. And, we have a hypothesis that we aim to learn properly H. Assume we are given parameters Po and T such that the probability that a random hypothesis drawn from the meta distribution is I'cclose to is at least po- For any e, E (0, 1), Algorithm can modified to an ( po)).
(a = (,=3,,,, (.,,))ppre --proper learner (with promise) for class H. by setting k = [2 12/0 0 /pol
Proof. Note that 5 in Theorem 4 is 0. Hence, it suffices to focus 5 0.1. As have shown in the proof of Theorem 4 the expected number of unacceptable hypotheses in Q is at most one. Let H be random hypothesis in Q. Let t = 12/57, and set le to 12t/po]. It is not hard to see that the probability of / being unacceptable is bounded by 6:
14

---

Pr Pr(fi is is (3T +))-far Pr H is unacceptable(3 +
Pr[ a random hypothesis in Q unacceptable]
E[# unacceptable hypotheses in Q |Q] = Pr[ = f].
Now, we separate the first terms in the summation, and bound them from above by the probability of [Q] being at most t. Moreover, we use the fact that the size of |Q] is essentially binomial random variable drawn from Bin(k, po) plus one. Hence, we obtain:
A+1
E unacceptable hypotheses in Q = Pr[[Q] = E
Pr f (3T + f-aa - Pr[[Q|s
Σ
1=0+1
E # unacceptable hypotheses in Q]
Pr (innkk, po)
+
k po
< Pr
Bin(k,
<
+
2
k Po
6
1
6
35
$ exp
S exp
S
2
28
2
(By the Hoeffding inequality)
where the last inequality holds due to the fact that e11(28) < 66/4 / for 6 & 0.1. Hence, the proof
complete.
A.2 Proofs of Memory-data tradeoffs of random ladder tournament
Lemma 3.1.
Suppose we have n hypotheses in H. For every po 2 1/n, e, and an integer between in such away that it uses:
two and k = O /po), one can implement Algorithm 2
s s=
(1
1 po
log Po"
samples, and
b b=0 (log
0
log log
llgn bits of memory.
e
Proof. Recall that it suffices to draw m == O(lo Pa /e2) samples to make sure the comparisons make in Line aare accurate with probability least 0.99. Since obtain this accuracy bound via the union bound, we may reuse the samples. The idea here is to process every hypotheses together with the same set of samples. To implement this algorithm in bits of memory, random hypotheses and store their indices using Ot log n)) bits. Then, we draw m sample and store the Scheffé counts of every pair of hypotheses that are drawn. Counting the number of samples in each Scheffé sets takes (log m) = Ollog((gg n)/e)) bits. And, there are O((2) many of them. Now, we can make all the comparisons between the hypotheses using O log m) O(t tog(logp~1/0 bits. Now, we run the first steps of Algorithm 2 and compute the current winner up to round Wr. Then, repeat this process for w, and the next t- random hypotheses with fresh samples until we reach the end of k hypotheses. Since at each round we process t hypotheses (with the exception of the first round), the number of rounds is [[k: 1)/(t 1)] (t1((t po)). so we use (mm/ / Po)) samples in total. Hence, Algorithm 2 uses O(log n/ (te? Po)) samples and O(t log(log n/c) + log n) bits of memory overall.
first draw t
Lemma 3.2. Suppose we have n hypotheses in H. For every Po 2 1/n, e, and an integer between two and k (11/p)), one implement Algorithm in such away that uses:
(1 1
log Po 2²
b b= o 01. log(p, ') logn
samples, and
+ t logn bits of memory.
1po
e²
15

---

R, are the output of the filtering algorithm.
Filtering algorithm
Filtering algurithm
Filtering algorithm
R1
R2
RR
winner
Wn
Compure
Wi
Compare
Compare
We
Random Ladder Toumament
i1
Figure 2: The sketch of our approach for the main result
Proof. The proof is very similar the proof of Lemma 3.1 However, instead of using the Scheffé counts the sorted lists store the samples. The only difference is that to process hypotheses, we will need (m t logn) Ot log Po log n/c²) bits instead of Ot log m) bits. This observation concludes the proof.
B
Main result
In this section, we present an algorithm that achieves the tradeoff described in our main theorem. As have described in Section [.2] we obtain our main result by running the random ladder tournament on the hypotheses filtered by filtering algorithm.
Recall that in the random ladder tournament, the algorithm can draw random hypothesis such that with a probability of at least Po. is I'-close hypothesis. The number of comparisons made in the random ladder tournament is approximately k == ( /po). To reduce k, we design randomized filtering algorithm that produces an acceptable hypothesis (3T + c')-close descent probability. Roughly speaking, this probability is min(1//n b/n). Although this probability is not very high, still greater than 1/n,, which allows us execute the random ladder in fewer steps. The only caveat is that must now run the random ladder tournament with new parameter I' 31 + e'. Hence, the accuracy guarantee of the resulting hypothesis will also based on I', and we will obtain (9 [ + -cco)s hypothesis to P. Figure illustrates a visual representation of this approach.
P) with a certain
The filtering algorithm operates on the basis of simple observation: the excellent hypothesis H* will not lose to any unacceptable hypotheses (those that are (3 I + f'rr Therefore, if there is no decent hypothesis, one can identify the excellent hypothesis where the algorithm pairs all hypotheses, compares them, and repeats this process while only the winners advance to the next round. Conversely, if numerous decent hypotheses exist, suggests that random hypothesis will have reasonable chance of being decent (and hence acceptable). The
through an elimination tournament,
16

---

filtering algorithm combines these two strategies and does the following for each with probability a half:
1. It outputs a random hypothesis.
2. It runs an elimination tournament under the assumption that there are no decent hypotheses, then outputs the result.
This approach leads to finding an excellent or decent hypothesis with an acceptable chance regardless of how scarce the decent hypotheses are.
Note that to run elimination algorithm, need memorize the winners of each round. Hence, implementing the second part above with limited memory is not trivial. Therefore, we focus on a randomly sampled subset of elements and provide algorithm that is extremely memory efficiint. Roughly speaking. the algorithm processes n hypotheses using only O(n) bits of memory. This is one of the key components of our result that allows to avoid extra log n factors and achieve the tradeoff 8. b x On log n.)
The algorithm operates in rounds, employing a tree-like structure. In each round of this algorithm, group a carefully chosen number of hypotheses and run all-against-all tournament among them. Next, the winner of each group proceeds to the next round. We continue this process until we find a single winner.
In Section B.1 we describe the group elimination tournament. In Section B.2
we detail how to
conduct the group elimination tournament on random set of n' hypotheses while utilizing only n' bits of memory. In Section B.3 we outline the filtering algorithm. Finally, we conclude with Section B.4 which combines all the pieces together and presents the proof of our main result.
B.1 Group elimination tournament
In this section, we focus on the case that there no decent hypothesis in H. That is, every hypothesis that is OPT-far from P will lose to hypothesis H with || Pl|TV OPT. The main advantage of this assumption is that if we have a knockout style tournament: only an OPT-close hypothesis will survive to the top. Here, we propose an algorithm that implements knockout style tournament, which we call group elimination tournament. However, instead of comparing two hypotheses at every step, run the all-go-against-all tournament among small group of hypotheses and send the winner to the next round. For simplicity, this section, we describe our approach in Algorithm 3 where assume memory restriction. We prove the performance of this algorithm in Theorem For discussion on how to implement this algorithm using roughly (n)) bits memory, see Section B.2
Algorithm Hypothesis selection with no decent hypothesis
1: procedure HYPOTHESIS- SEEEIIS--EEEEEE--NEEEEE No-DECENT(HL, n, c, 8, sample access P)
2: H4, t 7L
for l = 1,
do G, 0,, +- Partition Hr into groups of size gr-
4:
Het1 +-
6:
S= {(i,))ag} E G2,99, (e.. such that H; E G and H, E 9 Draw my samples. For each sample, update the Scheffé counts of S(H,, (f. for G = G1, ...,..... Gor.i do
Gecs
7:
9:
Run ALL-GO-AGAINST-AN
U.URRAAMET(PPC...0////.0 over the hypotheses
in group G.
10:
Add the winner to the set He+1- Return the hypothesis in H1+1-
11:
Lemma B.1. Suppose we have set of hypotheses' H. {H H2,..., H,,} and an unknown hypothesis P which we wish to properly learn in H. Suppose there are no decent hypothesis in H. that all hypotheses in H are either OcT-elese, or they will lose any OPT-close hypothesis. For every 2 < r S n, there exists an algorithm that uses O(log(log, n) log(1/5) + log n)/e?) samples from P. and it outputs H that is -lo-elose to P with probability 1-6 8.
17

---

Round #
# hypotheses
group size
# groups # winners
space
91 = [rrl
81/91 S 5n/vi
O(n.r-log(log(/00/44
82 = [n/gil
92 = (vr) 1.5
82/92 S 1//1125
(hrrr-log(lo((//0///
83
[n/(9192)1
93 (VP)2.28) 2.257
83/93 S n/322.35
(/n.r-lo((lo((1/0///
O 96 log mi)
[VT))1G-11]
se/9c S -(1.5)
gr
[=1
98
98
O
log (og(1/6)
Table 1: Branching factors in the tree structure
Proof. The algorithm runs in I. rounds. At round E [Z], start with 8; hypotheses. We partition them into groups of size ge. For each round, we draw my == O(log(g)) /8) fresh samples. We keep track of the number of samples in the Scheffé sets of every pair of hypotheses that same group. Using the Scheffé counts, we run an all-go-against-ai tournament in each group G, with overall confidence probability - 8 (6 gi) and find the winner. Then, we repeat this process among the winners in the next round until we end up with only one hypothesis. See Algorithm 3 for the deseription.
the
Parameters:
We set the group sizes as follows:
91
[VT]
ge [(FF)
x ---
vl (2....,4
(2)
We start with 81 The number of hypotheses in the l-th round is:
St
8
n
p1.5c 1-1
n
V (2..,,,., L).
(3)
-t-1
9s
The equation above is due to Fact D.2 and Fact D.3
Observe that we stop our process when only one hypothesis is left: the ultimate winner. Thus, is the smallest integer such that s1+1 is one. That is, I[ D8 2 n. It is not hard to show that is O (log (log, n)) due the following argument. For any 2 logi. (log, + 1), one can show Il 9r is at least n via Fact D.3
II E=1
ge 2 n 1.5h-11 2
Therefore, L cannot be larger than flogi.s (log, 1)7.
We describe how set parameters in Table
18

---

Sample complexity:
For round E, we draw my fresh samples. Thus, the total number of samples
is:
Te log
samples
my
Σ 0
2
8
1=1
8=1
L log(1/0)
+0
log.0 ge
22
L 1og(1/5)
log II 9t
e²
2
L log((/)))
+ log n
log(log, n) log(1/6) + log
62
e2
Note that the last line we use the fact that I ge is poly(n) which is not difficult to prove using the following argument: We define L to be the smallest integer such that IL ge is at least Thus, Il-1 De is at most n. Hence, we have:
L-1
L-1 ge S
L II
2.5
II ge = OL II gi s (0(
II
ge
Suppose G is a group in round l that contains an OPT-close hypothesis. For the all-ao-against-all tournament round we use me Ollogge 0(log(2//6)/3 samples. That implies we estimate the probability of all the Scheffé sets in G with accuracy with probability at least 6/(6 ge). Given that tournament has to output an OPT-close hypothesis with probability - 87(6
Correctness:
not have any decent hypothesis, using Fact the all-go-against-al
Now, let (()) be the group round one that H belongs to. Let g be the group that the winner of Clearly, the all--o-against-all tournament over (+) will return an OPT-close hypothesis with probability
(()) belongs to in round two, and similarly define: g(a)...., ....., (()).
8/ (6 (6g)) if G contains an OPT-close hypothesis. Thus, using the union bound, the probability that the final group
((L) does not output an OPT-close hypothesis is bounded by the following:
L
L
L
Fr[Outuut hypothesis is not OPT close]
<
(VF))-15*
1.5
Σ (VF))
6
6
1=1
t=1
t=1
1/4
r
1/4
8.
1/4
B.2 Memory usage of Algorithm 3
In this section, provide an approach implement Algorithm using roughly O(n) bits of memory and prove our main theorem.
Theorem Suppose we have a set of n hypotheses H = {H1, H2...., Hn} and an unknown hypothesis P which we wish to properly learn in H. Suppose there are decent hypothesis in H. that is all hypotheses in H are either OPT-close or they will lose to any OPT-close hypothesis. For every 2 S there exists algorithm that uses O(n r log (log(1/5) bits of memory and O(log (logg(og, n)) log(1/5) + log e))) samples from P. and it outputs H that OPT-close to with probability 1 8.
Proof. Note that there are two main sets of values that we need to store. First, the values of the Scheffé counts at every round that allow to perform the all all-go-against-all tournaments. Second, the
19

---

indices of the winner hypotheses that go to the next round. Below, we discuss bounding the memory usage for each part.
Memory usage of Scheffé counts: Here, we show to store the Scheffé counts, we need On (og(log1/00//4 bits at every round. For a single group of size there are O ) pairs of hypotheses, therefore Scheffé sets, so we require Olg me) bits to count the number of samples in all the sets. Thus, in round E, we need the following number of bits:
space # groups O llog me)m =0
o7 log mé
g1
0 st 91
(log.r log
loog( (ogg(16))
62
log log(1/0)
88 .0
ge (logge)
n
Next, we show the last term in the last line is O(r). For round 1, the memory bound holds since
vr loool (rr( I r. Now for 222 2 using Equation 3 we have:
o
5t (
(log 91) = =0
De log -11155(-1-11
=0 (T- ge loooogg ge = O(r).
96
12
Hence, the bit complexity at every step is:
o n- r. log 1og(1/6)
Storing the indices: Note that to run the comparisons, one needs the true indices of the hypotheses to query the PDF-comparator or draw a sample. Thus, in the trivial implementation of our algorithm, we potentially need On log n.) bits to keep track of the indices of the winners at every round. In this section, we explain how one can implement our algorithm in memory manner, so keeping track of the winners' indices does not take more than (nn) at every round.
We start by the following assumption that there is natural ordering among the hypotheses: H1, ..,... Hn. In this way, for the first round we do not need to remember the set of indices, we only need to remember n. At every level, we group "adjacent" hypotheses together and preserve this natural ordering. More precisely, at round one with group size g1. the groups are:
G1 (H1 H2,.. Hgg).
G2 = (Hg +1, - H2g
Gra (
Hn)
For the next round, we keep list of (n/91] 1 winners. However, instead of fully writing down the index of the winners, we use O(log(9)) bits per each, and save the index of the winner within the group. For the next round, we partition the hypotheses into groups of size 92 keeping the "adjacent" hypotheses in the same group. We repeat the same process to store the winners. However now, each winner are "representing" O - 92) hypotheses, so we need (log(g) 92)) bits to store its index.
We continue this approach. At round f > 1, we have a list of st = O(n/ II; f-1 9:) hypotheses, and require Ollog II!- g.) many bits to do so. Thus, at every step need ((n) bits of memory.
Note that at every point in the process, it is easy to compute the actual index from the stored index. If right before starting round i, the j-th index in the list k. then the true index is:
f-1
NEWINDEX = (j - 1)
II
g. + k.
20

---

B.3 Filtering acceptable hypotheses
In this section, we describe filtering algorithm that allow us to pick an acceptable hypothesis with a modest chance. Our algorithm is simple we draw roughly n' < n hypothesis at random. If one of these hypothesis is OCT-clese, and there is no decent hypothesis among them, Algorithm returns an excellent hypothesis. On the other hand, if there are a lot of decent hypotheses, then there is a modest chance that a randomly selected hypothesis is decent, hence an acceptable one.
In the description of Algorithm D assume we have class of hypotheses of size n, and roughly O(n) bits of memory. However, we aim to use this algorithm random hypotheses in roughly O(n') bits of memory. The primary challenge here is that we need roughly Onn' log n) many bits to memorize which hypotheses are participating. and we cannot use the "natural ordering" of the hypotheses that for a mapping that maps indices in [n'] to a random set of indices in [x] in a memory-efficie To do so, we relax our requirement regarding that we need draw n' random hypotheses uniformly from H. Instead, we are looking for a set of random pairwise independent indices while finding the index of the selected elements requires small amount of memory. This relaxation gives process that filters acceptable hypotheses:
setting that we can process n'
in the proof of Theorem [ Thus, we are looking
manner.
Theorem 6. Suppose we have a set of n hypotheses H = {H H2,..., Hn and an unknown hypothesis P which we wish to properly learn in H. For every positive integer n' n, there exists an algorithm that uses On' log(L/e)) bits of memory and ((log n)/²) samples from P. and it outputs H that is excellent or decent with the probability:
n'
1
Pr H is excellent or decent.
2 min
16n 4n
Proof. First, we start off by describing how we randomly pick n' hypotheses from the set of n hypotheses. We use a standard technique for generating pairwise independent random indices described in [Vad12] Chapter 3.5]. The following is the description of randomized mapping that for any given index [n'] gives an index in [n]] that can be computed memory efficient manner.
Let q be a prime number between and 2n (n < q < 2n). Such g always exists via the Bertrand- Chebyshev theorem for any n. 2 2. Without loss of generality, we assume we have hypotheses by adding fake hypotheses H that lose any other hypothesis. Now, consider the finite field of Zy. Proposition 3.24 in [Vad12] implies that if we use two random numbers a and b in Z.p then the following mapping generates a set of pairwise independent indices:
fa,(()) = a x x+++ (mod q).
More precisely, by iterating x from to n', this randomized mapping selects n' hypotheses with the following indices: (1,, f2, fa.b)). (n') Note that to compute this mapping, we only need to memorize a and 6, which requires O(log n) bits, significantly smaller compared to On log n) which we would need to memorize n' random indices. Using the pairwise independence of the indices generated by this mapping, it is not too difficult to show that with some modest chance we pick exactly one excellent hypothesis and no decent hypothesis with this mapping.
Lemma B.2. For a prime q, assume we have a class of q hypotheses that contains L, > excellent hypotheses and la decent hypotheses. Let a # O and b be two random numbers in Z, selected uniformly at random. Let H' be the set of following hypotheses: (Hfas()) : [n']] for which fe,(2) a x + b (mod q). If (tc + ta)/q S 1/(2n'), ) then the probability that H' contains exactly one excellent hypothesis and no decent hypothesis is at least n' te/(2g) g).
See Section D for the proof of this lemma.
'Witoout loss of generality, assume Ho is Hq.
21

---

Algorithm Filtering Algorithm
procedure EYPOTHESESS-ILLERRRR
sample access P)
2:
C <- toss up a coin.
3:
if C' is head then
4:
Draw random in [n]]
5:
H + H;
else
7:
-- the first prime number that is at least n
< a random number in [q
9:
b <- random number in [g]
10:
H' <- {Ha-r (mod
[n']]
11:
H +
,',,
12:
Output H.
R2 ss are Hazzt (mod
R2
Ped!
Random Hypothesis in 76
Hj
Group Elimination Algorithm
with probability 1/2
with probability 1/2
Figure 3: The sketch of the filtering algorithm
The algorithm: Assume H. contains te 2 prefect hypotheses and tu decent hypotheses. The algorithm is simple: with probability half we set H to random hypothesis from H. And, with probability half we use the randomize mapping to pick n' hypotheses and run Algorithm 3 with parameters 0.5 and visual representation of the filtering algorithm.
on them. And, we output the output of that algorithm. Figure shows
The probability of getting an acceptable hypothesis by picking random one is (te + ta)/n, Note that if this quantity least 1/2n', the statement of the lemma is true. Thus, assume (t. + ta)/ /n less than 1/2n' which implics that (te + tta//g is less than 1/2n' n'. Given this condition, by the above lemma, our randomized mapping selects set hypotheses with only one excellent hypothesis and no other acceptable hypotheses with probability at least n' (2 q). And, since we set d to half, with probability at least half, Algorithm 3 will choose the excellent hypothesis as its output. Using that g < and Pr[C tail] = 1/2, with probability least n'' lz/(8 $ n /(16), A the excellent hypothesis as desired in the statement. Hence, the proof is complete.
C
22

---

B.4 Putting everything together
Theorem 1. There exists constant for which the following holds. Let H. be arbi- Irary class consisting of n distributions, and let E > 0. For every natural number b where c. (log n - log (log n))e)) s b S n, there exists (a e, = 0.1) -.lo-rr learner (with promise) for H. using bits of memory and the following number of samples:
logn n
log ())
when S
log log
logog n
log 12
log
when log S S n.
2
Proof. Here, combine the filtering algorithm and the random ladder tournament to prove the upper bound. We first use the filtering algorithm, Algorithm{4 [ to increase the probability of getting acceptable hypothesis (3 [ + e'-close P) with parameter e' </4. Then, use the random ladder tourmament, AlgorithmP 2 to select an acceptable hypothesis among the hypotheses that have passed the filtering, Note that the random ladder tournament, we need to use new I" parameter, that 31 +'.
Here, we use the memory bounds provided in Theorem and Lemma 3.1 for these two algorithms. Fix two small constants co, that determine later. Let / be the largest integer such that:
log
t log
t + t logn S cnb.
Note that given our lower bound for b, one can find a that is least two. Set n' follows:
n'' min
C1 b Tog((/e)*
2 vn
We consider two cases in the following:
Case 1: n' < 2 /n. In this case, n' is equal b/ log (1/e). One can run Algorithm 4 and find an acceptable hypothesis with probability == min(n' (16n), 1/(4n')) = =n'/(16n) Now in this case, invoke Algorithm 4 (11pp) times, and in each round we use O(log n/e2) samples. samples. Therefore overall,
Furthermore, the random ladder tournament uses O(llg (t O(too our sample complexity is:
(1
log n
logn 2
n log n'
0
(1+
= 0
= 0
Po
2
Po
2
log n
n log b
log 1)
2
Case 2: n' 2 n.. Similar to the previous case, we would like to run Algorithm 4 and find an acceptable hypothesis with probability = min(n' (1, 1/44n)) 1/(4 Now, since n' S c1 b/ log()/e), we may be able run multiple instances Algorithm 4 in parallel while using the same number of samples. Let this stage is:
b/(n' log(1/e)). Now, the number of samples we use for
o
(
1
log
0 n'
(TT
log n
= (log(1/c) logn
rpo
bea
Now, we focus on the number of samples we need for the random ladder tournament. Note that should be:
23

---

b logn' V log (llog n)/e) )
t @ min
Thus, the following amount of samples:
0 1
log n2
Vn
log
0
Po
22
b- min (logn)-1, (vb log (log n)) -1
2
max (logn, volog ()ogn)
log n b
n log n 2
log
0
=
log
vn
Putting these two cases together, obtain the desire sample-memory tradeoff's:
#samples #bits O ( log n e2
llog n 22
log
Regarding the accuracy guarantee, it is not hard to see that in the filtration algorithm, with modest probability, we pick a distribution that is (3T' + e')-close to P. Now, we run the random ladder tournament with new I" = 31 + Then, get hypothesis with accuracy:
3Г + (3T 06 96 +6.
Hence, the proof is complete.
C Proper learner without promise
Throughout this paper, we mainly focus on proper learners with promise, for which the algorithm is given parameter I', and we are promised that OPT is most I'. In this section, focus on the case where no such information available to the algorithm. First, we formally define a proper learner without promise.
Definition C.1. Suppose A has sample access to an unknown distribution P. And, can query the probabilities of the Scheffé sets according each H; E H and PDF-comparator for every pair of hypotheses in H. We say algorithum A is an (a, e, -r-ope learner for if the following holds: for every distribution P, and for every class of n distributions H. with probability at least 1 8 over its input sample (drawn i...d. from P) and internal coin tosses, A outputs distribution H e H. such that:
|P 1P- A a OPT +e.
Here, provide reduction from a proper learner without promise to proper learner with promise. At high level, we perform a binary search over possible values of I' in (0, 1). At every step, we try value of T. and least OPT or not, A may return hypothesis that seems close to P, and it hard to refute that the suggested value of I' is at least OPT. For this reason, we look into the output of A, say H. and see we find evidence that H is far from P. We check the distance between H and P on every Scheffé set of H. More precisely, we check W (H) is larger than (a OPT + <) where (HH) defined as follows for every hypothesis Hę:
A with I r The main challenge is that regardless of T being
W(H)) = max H. (8(H,, H.) (S(H,, JE(M)(
24

---

Now, if (HH) is larger than (c-OPT++), then one can imply that H is not (a 1D-OPT++ to P. therefore, I'm must have been less than OPT. On the other hand, if W (H) is at most (a: OPT + c), show H is not too far away from P (even when Im is less than OPT). Putting these observations together and accounting for errors in estimation of W [), obtain reduction that is described in Algorithm and we prove its accuracy in Theorem
Algorithm Reduction from a proper learner without promise to proper learner with promise
procedure B(H, a, e, c', 6, 8', sample access P, and oracle access to A))
2:
Te --00 0
TA 1
I1 A (H, lh E, 6)
5:
while r - T > do
Im + T4 +
6:
Ā A (H, r em,,,,
((F) Estimate (ff with error most e' and with probability least 8'.
if (H)) S a +c then
10:
Fá + mm
11:
Å + H
12:
else
13:
re
I'm
Output f1
14:
Theorem 7. Fix five parameters 6, 1), and L. Assume that A is an (a, 8)- proper learner (with promise). Suppose that we can estimate the probabilities of all the Scheffé sets according P with additive error most e' and with probability at least 1 - 8'. Then, B, described in Algorithm 5 is an (a + 2, (a + 1) 2,,t. 8') proper learner (without promise) where is defined [log2(1/0)
Proof. Our goal here is to show that for the output hypothesis A with probability at least - + have:
| - PlTv < (a + 2) OPT + (a + 1)e + 2
(4)
Observe that at every iteration of the while loop in the algorithm, 1 I' is divided by two. Thus, the while loop takes [1o]][//<)] iterations. Thus, is the number times that we invoke A in Algorithm Each time A works as expected with probability 1 5. Hence, using the union bound, with probability t- 6, we can assume all invocations of A result in correct answers. addition, with probability - 8', all the estimates we for P (S(ff, H.)) in Line 8 are accurate up
most e' with probability at least 1 - 8'. Hence, by the union bound, the following event happens with probability at lest 1 (t 5 8'): In every invocation of A, if OPT is below the given parameter Т, then A returns hypothesis, H, that is (aT c)-close P. And, W(H) is most af + c'. Hence, for the rest of this proof, assume this event holds, and we prove Equation
additive error e'. Hence, - (61)-wahh
Consider П and De in the final iteration of while loop in Algorithm Observe that the output Á is what A has found when it was invoked with input = TT. Now, we consider two cases as follows:
Case 1: OPT < Ta: In this case, A is (a F4 + e)-close to P Pb our assumption that A works as expected. Thus, | Plltv is at most I' + e. This upper bound is written based on I' while we aim to find an upper bound on distance that only contains OPT. For this purpose, we need to use the fact that why the binary search algorithm stoped at this particular Tr. For Tr, we have two possibilities: either I' is zero; Or, have run A with I = l's and we have not found desired H.
25

---

In both cases, F3 is a lower bound on OPT. Thus, we have:
OPT 2 T 2 l - c.
Now, using this relationship between aa and OPT, we obtaín:
H1 - P s a (Pt
implying Equation 4
Case OPT Tx In this case, clearly, aa cannot one (since OPT at most one). Thus, FT was set in Line 10 implying that W (H) is at most a a + e'. Since we assumed the estimation W (H) was accurate up to error e', we have:
w(t W(t) td
Given this bound on W (HH., we show that H cannot be far from P. Let H be a hypothesis in H that is OPT-close P. Then, we use the definition of the Scheffé sets and the triangle inequality bound the distance between H and P.
| Pl < H H + H PPlTv
(by triangle inequality)
(s H H
HH (s [, H )) + +1 PPlIr (by dfn. of Scheffé set)
A (s (((,)))
p (s (f1, (it,
+ |H - Plhv (by triangle inequality)
A (i) (H,
2 -P
Now, use the definition of W (H) and conclude:
- PlIvv < (( + 2 2| Plivv W(I) + 2OPT
$ a + E 2e' + 2OPT S (a 2) OPT +c+26.
Therefore, the proof complete.
Corollary C.2. For every parameters é" and 8" in (0. 1). there exists an (a 5, e., 8 8')-proper learner (without promise) that uses (log(n/8")/ ((g(() samples and runs δ n// 88" ())) time.
Proof. First, we start off with the parameters: We set == e"/6, = / 8'
82, and
the number of iterations in Algorithm Using the Chernoff bound and reusing all samples, we can estimate all the Scheffé sets with additive error at most c' with probability least 1 1-8' 8'.
= 8"/ (2 where == [log
Note that based Corollary A.I the random ladder tournament (with arbitrarily small confidence parameter) is (a = 3, 6) -proper learner (with promise) that uses O (log(n/8)/ee²) samples and
runs in O n log(n/8")/ 8" 2)"))) time. We use this learner as our A and run the reduction algorithm with the parameters we specified carlier. Now, using Theorem we obtain proper learner without promise that satisfies the following guarantee with probability at least 8" (8' + t))
[ PlItv S (a + 22 OPT + (a 1)e + 2e' 5- OPT + +e".
26

---

Regarding the time complexity, the while loop in Algorithm is repeated & times. In each iteration, we compute W (H) which takes n log (n/8") / (e")² time, and we call the random ladder tournament (i.e, A). Hence, the overall time complexity is:
o o (
log (n/6")
lolloog(////) log (1/e") 8" (e")²
( 8" (Em)2
8 (
Hence, the proof is complete.
Memory-data consumption of reduction algorithm: Besides the sample and memory usage of A. B needs to keep track (()) numbers and also computes W (H). Now, given bits of memory, we can partition 7/ into consecutive blocks of size one block of size r, we keep track of the Scheffé counts of H and the hypotheses in the block. For each round we use (l)og(n)) /c²) samples, ane we have (nn/r) rounds. Thus, the total number of samples is Onn/r (Iog(n)/e3) Thus, for this part we will have:
(n))gg()og(n/c))))) At every round,
process
n log
log
b O
loog
22
Remark 8. Using the reduction algorithm with the memory-data tradeoff described above, can translate our main theorem, Theorem to a (a = e1,,,0.1)) prroper learner (without promise) incurring additional factors of poly (log log(n), log(1/e)).
D Auxiliary lemmas and facts
Fact D.1. [adapted from Theorem in (MS08]) For every pair i, E [r]], let qıj denote estimate of the probabilities of the Scheffé set of He and Hj according to P. Let H be the hypothesis that minimizes of the following:
á arg max min HEH jE(n]((
H. (S(H,,,,, H2)) qisl
For every and 8, if we estimate qı using O(log(n/8)/e)) samples from P, then H satisfies the following guarantee:
| X||Tv 30PT +e.
Lemma 2.1.
Upon receiving three parameters: r, and 8, Algorithm 7 uses O(log(1/8)/e²)
samples and satisfies the following guarantees with probubility at least
If H2 is T-close to P, then the algorithm returns H1.
Hi (max (T, ||H2 Pllrv) ||H2 Pllrv e)-far from P. then the algorithm re- turns Hz.
Proof. Let g. Pt, and p2 denote the true probability the Scheffé set of H1 and H2 according to P. H1, and Hy:
y= P(S(S, H2)),
P1 := (S(H,, H2)),
P2 = H2(S(H,, H2))
And, let q be the estimate of from the samples. the Using the Hoeffding bound, one can show that O(log (1))((/))/() samples. Now, if
lg @l most c' = c/2 with probability - 6, since Hr Pllty at most r, then |p1 must be at most I' implying:
1P @l 1p + -T+
27

---

Therefore, the algorithm outputs H1 as the winner.
Now, we show the second guarantee. the total variation distance between H₃ and P. 1| - Plltv. is greater than (max (I', /1///- X [Tv) 1| X |||TV + e), then by the triangle inequality and
the definition of total variation distance, we will have:
P1
2 P1 P2 - lp2 - 9 2 P1
P2
P2 q 19 -
2 1 H2llTV - || PllTv
(By the definition the Scheffé set S(H, H2))
A || H PV[Tv- 2| Pl[TV-
max (I, [[2 x(lvv) + E-
max +T' |p2 +t')
M max c'' |p2 + q 41)
N max (T + , Ip2 ii)
Thus, the algorithm outputs H2 as the winner.
Lemma B.2. For prime q, assume have class of hypotheses that contains t. 2 excellent hypotheses and ta decent hypotheses. Let a + and be two random numbers in Zg selected uniformly random. Let H' be the set of following hypotheses: fa x [n/1} for which fa,(() x + (mod q). If (t. + tta/q S 1/(2n'), then the probability that Ht' contains exactly one excellent hypothesis and no decent hypothesis is at least (2
Proof. Using Proposition 3.24 in V2d12 the mapping is in fact class of pairwise independent hash functions. That is, the following holds:
Fix two indices E Zp and x E [n']. The probability of mapping to i is:
Pro,(fa,(()) =
Fix four indices i,j E 2, and x, E [n'] where x + y. The probability of mapping æ to and y j is:
Prav(fas(x)- = and fa) 5] q²
Suppose Hig and Hy indicate the of excellent and decent hypotheses respectively. Fix an index i for which H; is an excellent hypothesis. Suppose one of the indices in [n'], say J, is mapped to i. Now, the probability of another hypothesis in He Ha being chosen for fixed index y # x in [n'] is:
Pra. H (a.)(())mod g) E He U Hd fa,((x) =
E
Pro,olfa,(()) = fa,((z) =
st. H, ((((UU)))))(
Prav(faply) = j and fa,((T)
Pra.h =
jst. H (.E((()
le + 1s 1
Hence, the expected number hypotheses (other than H₂) that are selected is:
E #y [n'] (x) s.t. H Ha 9) E He U Ha fa,((r) = i] (n' (n'-1) 1) (1e + la
8
n' (1e + +aa
q
28

---

The last inequality is due to the assumption we have: (te tta/q S 1/(2')). Next, by Moarkov's s inequality, the probability that the number of y are least one (that two times the expected value) is at most 1/2. Hence, if x: is mapped to Hi with probability at least 1/2, there is no other excellent or decent hypothesis is selected.
Now, we compute the probability that an excellent hypothesis is selected and other excellent decent hypothesis is selected as follows:
Pra.o[One excellent hypothesis and no decent one]
Pr(fa.b(z) i(mod q) and no other hypothesis in He U Hais selected] =E[n'] HiGH.
Σ
Σ
Σ
Σ Pr[fab(() = i(mod s)]
DE(n' HiEHl
Pr [no E [n'] \ (o) s.t. (mnd q) E He U Ha fa,((x) = i(mod g)
Pr[Jab(3))= = i(mmdd 4) n' le
Σ Σ
29
xE(n') H.EH.
Hence, the proof is complete.
Fact D.2. Let n. 0, be three positive integers. Then, we have:
[n/a]
ab
Proof. Let r denote the remainder of n divided by a. If O, then the claim trivial. Therefore, -1.. Let be the remainder of divided by a Clearly, 8 has to be of the form: L.a + for E {0, .,...,b. b- 1}. Hence, we have
assume r is in (1,2.....4 - 1}.
[n/a]
+ 0
n
+
b
ab
ab Lab_
a
(t + 1)
a
n
11
+
+
lab
ab
Lab
a
Fact D.3. Given the definition of the ge 's in Equation
for any positive integer we have:
II 9. 2 155-1
Proof. By the properties of the geometric series, we obtain:
9 2 (VT) 1551 = =(Vr) Eis Eimi 1.5 = -(77)1.5-1))00.-1 -115--1
29


Reviews:
[{"review_id": "NjlYqaLqzm", "reviewer": "Reviewer_5dQu", "summary": "This paper studies the problem of agnostic distribution learning where i.i.d. samples are generated from an unknown distribution $X$. The goal is to find the best distribution from a given set of finite distributions $\\\\{H_1,\\cdots,H_n\\\\}$ that is closest to $X$ under total variation distance. The authors specifically study the sample complexity, under which the memory that is needed to store the information of the samples is bounded. The main contribution is a trade-off between the number of bits of the memory and samples needed, which is tight up to a $\\log n$ factor in the minimax sense.\n\nThe main proof technique is based on the so called \"random ladder tournament\". This differs from conventional approach that first estimating the probability of Scheffé sets of all pairs in $\\\\{H_1,\\cdots,H_n\\\\}$ and then selecting a distribution closest to the estimates. In contrast, the authors propose an ingenious streaming algorithm that tracks the \"best\" distribution in an online fashion, which is suited for achieving their desired trade-off between memory usage and sample complexity.", "questions": "See comments above.", "limitations": "No issue with negative societal impact.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "The paper's primary strength lies in its novel \"random ladder tournament\" algorithm. This algorithm effectively achieves a memory-efficient sample complexity for agnostic distribution learning. The approach incorporates some interesting technical ideas that may be of independent  interest. As far as I'm aware, this particular scenario has not being studied in the literature.", "weaknesses": "My main concern regarding this paper is its overall significance to the machine learning community. The paper has a strong TCS flavor, and the introduced model appears somewhat contrived. Specifically, the derived trade-offs, though mathematically intriguing, do not offer any surprising insights. Thus, its practical implications and utility within a broader machine learning context may be limited.\n\nAdditionally, the paper's presentation could certainly benefit from some improvements. The authors dedicate a significant portion of the introduction to outlining their techniques, which, unfortunately, are quite challenging to grasp without delving into the substantive technical details found mainly in the appendix.\n\nI would recommend eliminating most of this preliminary discussion and focusing primarily on the \"random ladder tournament\" argument, as outlined in Section 3. Providing a more detailed and accessible explanation of this central argument could make the paper more digestible for readers. Following this, a more straightforward discussion of the techniques used to improve the logarithmic terms would be better placed and easier to understand. This reordering should contribute to a more coherent and engaging narrative throughout the paper.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "> overall significance to the machine learning community\n\nHypothesis selection is a fundamental problem in statistical learning theory. The formulation we study here abstracts and generalizes many specific distribution selection/estimation tasks (some of which are discussed in the book of Devroye and Lugosi, \"Combinatorial Methods in Density Estimation\").\n\nMeanwhile, when one takes a computational perspective, memory and communication are important resources to control in practical implementations, and their study gives rise to a variety of theoretical questions. \n\nOur goal in formulating this problem was to study memory/sample tradeoffs in a general setting, and we hope our results serve as a launching point for studying these resources systematically.\n\nNote that general hypothesis selection algorithms (i.e., ones that do not use information specific to the distributions under consideration) play an important role in several model-specific learning learning problems. This includes the Gaussian mixture-learning algorithms of Daskalakis and Kamath. Papers on this topic regularly appear at NeurIPS. Examples include: \n\n[Private hypothesis selection](https://papers.nips.cc/paper_files/paper/2019/hash/9778d5d219c5080b9a6a17bef029331c-Abstract.html). M Bun, G Kamath, T Steinke, S Z  Wu. *NeurIPS 2019*\n[Nearly tight sample complexity bounds for learning mixtures of gaussians via sample compression schemes](https://proceedings.neurips.cc/paper_files/paper/2018/hash/70ece1e1e0931919438fcfc6bd5f199c-Abstract.html). Ashtiani, S. Ben-David, N. Harvey, C. Liaw, A. Mehrabian, and Y. Plan. *NeurIPS 2018*\n[Near-Optimal-Sample Estimators for Spherical Gaussian Mixtures](https://proceedings.neurips.cc/paper/2014/hash/c0f168ce8900fa56e57789e2a2f2c9d0-Abstract.html). A T Suresh, A Orlitsky, J Acharya, A Jafarpour. *NIPS 2014*\n[Near-optimal density estimation in near-linear time using variable-width histograms](https://papers.nips.cc/paper_files/paper/2014/hash/287e03db1d99e0ec2edb90d079e142f3-Abstract.html). S Chan, I Diakonikolas, R Servedio, X Sun. *NIPS 2014*\n\n\n\n> I would recommend [...] focusing primarily on the \"random ladder tournament\" \n\nThat's a good suggestion. It agrees with some of the comments from other reviewers. We will try to implement it in future short versions of the paper (whatever the outcome at NeurIPS)."}, {"review_id": "8Emy0Gpr7J", "reviewer": "Reviewer_5jdF", "summary": "The authors study the problem of hypothesis testing for pdfs in a streaming model. The problem is to find a hypothesis H* (corresponding to a pdf) from a family {H1,...,Hn} that is closest to an unknown pdf P. The input is a stream of points drawn i.i.d. from P. At any time step the algorithm can ask for a new point or query a scheffe set of two distributions Hi and Hj in {H1,..,Hn}. \n\nThe main theorem in the paper shows that the algorithm can \"learn\" P properly by using O(n\\log n/b\\cdot\\frac{\\log(1/\\eps)}{\\eps^2}) queries, where b is the memory used. This is close to optimal - within log n factor. \n\nNote: \n- proper learning a pdf means: |P-H*|_TV\\le\\alpha\\cdot OPT({H1,...,Hn}, P)+\\eps.\n- scheffe set of two distributions H1, H2 is {x : H1(x)<H2(x)} ", "questions": "Why not design an online Neyman-Pearson test - compute approximate log likelihoods based on the query results? The log-likelihood can then be used to upper bound the TV distance. ", "limitations": "NA. The paper is theoretical in nature and is fairly upfront about it.", "rating": 6, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "- Clean presentation and summary at the beginning of the paper.\n- Almost tight bounds (upto log factors)", "weaknesses": "- Perhaps the model can be motivated better? Why the restriction to scheffe sets?\n- Worth comparing the algorithm to vast statistical literature on Neyman-Pearson tests using log-likelihood computation.\n- Need to compare and cite some of the vast literature on orienteering tournaments in directed graphs - I suspect some of the underlying results may already be known.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "\n> Why the restriction to scheffe sets?\n\nScheffé set queries provide a generic computational model for expressing algorithms that apply to many families of distributions; this avoids assumptions on particular data formats or functional forms for the distributions. Scheffé queries are also sufficient for implementing existing algorithms for hypothesis selection. The fact that our algorithms only need to access the distribution family $\\mathcal{H}$ using Scheffé set queries makes our positive results stronger.\n\nWe note that the nearly-matching lower bounds, based on communication-complexity arguments, apply to all algorithms -- in particular, including those not based on Scheffé sets.\n\n> Need to compare and cite some of the vast literature on  orienteering tournaments in directed graphs\n\nWe appreciate the suggestion. Unfortunately, we had trouble identifying which technical ideas would be relevant to our submission. We searched for papers on orienteering, but only found work on a class of NP-complete optimization problems that are variants on the Traveling Salesman problem. (A representative example is \"The Directed Orienteering Problem\" by Nagarajan and Ravi in *Algorithmica* 2011.) Perhaps the reviewer could point us to a starting point for the literature they had in mind?\n\n> vast statistical literature on Neyman-Pearson tests\n\nWe will add some further discussion of this literature. However, note that maximum likelihood approaches do not generally work well for hypothesis selection in total variation ($\\ell_1$) distance, even when we just want to select among two distributions. This is discussed, for example, in the textbook of Devroye and Lugosi, Section 6.4. We reproduce their counterexample here.\n\nSuppose $H_1$ is a uniform distribution over $[-1, 1]$, and $H_2$ is a uniform distribution over $[\\delta, 1+\\delta]$ for some parameter $\\delta \\in [0,0.5)$ that we determine later. Let $P$ be the uniform distribution over $[0,1]$. Then\n$$0.5 = \\|H_1 - P\\|_{tv} > \\|H_2 - P\\|_{tv} = \\delta\\,.$$\nThe correct output for the selection problem is  $H_2$ once $\\delta$ is sufficiently small (say, sub-constant). However, the MLE will select $H_1$ if any  of the data samples fall in $[0,\\delta]$. For $\\delta \\gg 1/s$, where $s$ is the number of samples, we will see a sample in $[0,\\delta]$ with high probability. There is thus a fairly wide range of $\\delta$ for which  the maximum likelihood estimate will be incorrect."}, {"review_id": "ZrKPZjE8jp", "reviewer": "Reviewer_Awx8", "summary": "The paper studies the problem of hypothesis selection under a memory constraint. Here one is given $n$ distributions $H_1, \\dots, H_n$ with access to an oracle that can output 1) $H_i(H_j > H_k)$ for any $i,j,k$ and 2) $1(H_i(x) > H_j(x))$ for any $i,j$ and any point $x$ in the underlying space. Given a stream of observations $x_1,x_2...$ from some unknown $P$ the task is to select an estimator $\\hat{H} \\in (H_i)_{i=1}^n$ that is as close as possible to $P$ in TV distance up to a multiplicative and additive constant $\\alpha,\\epsilon$ respectively. Moreover, one wishes to do so using at most $b$ bits of memory at any point during the algorithm. \n\nThe author's main result Theorem 1 shows that $s$ samples from $P$ are sufficient to output a suitable estimator with constant error probability, provided $bs \\gtrsim \\tilde{\\mathcal \\Omega}(n\\log(n)/\\epsilon^2)$ and note that $bs \\gtrsim n$ is necessary by previous work. They achieve this result by introducing multiple technical ideas, the main one being the 'random ladder tournament'. ", "questions": "I would suggest to shorten (or remove) the proof of theorem 4 and to replace it with a (sketch) proof of the memory-sample trade-off. ", "limitations": "The authors address limitations. ", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- The paper is mostly clearly written \n- The paper appears technically sound\n- The paper introduces simple but novel technical ideas that not only near-optimally tackle their proposed problem, but also recover other known results. ", "weaknesses": "- My main concern is that due to the technical nature of the paper the short format of neurips is simply not enough for a meaningful presentation of the results. The motivating problem is under a memory constraint, yet just as one would learn how one can trade off memory for samples in the random ladder tournament (Lemma 3.1) the paper ends. More generally, from the main text, I don't feel like I have learnt how the algorithm actually works. In sections 1.2, 2 and 3 we are given glimpses of the key technical ideas necessary but it doesn't feel cohesive. \n\n\nTypos:\nPage 4 \"Results in a better...\"", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "> due to the technical nature of the paper the short format of neurips is simply not enough for a meaningful presentation of the results\n\nWe will endeavor to present at least some of the main ideas concisely in any future short versions, at NeurIPS or elsewhere. Like many NeurIPS submissions with detailed technical components, we present full descriptions of our algorithms and their analyses in the supplementary materials.\n\nWe intended Section 2.1 to explain our key ideas and the general flow of the paper. We selectively chose the random ladder tournament to be the main technical tool we present in addition to one of our basic tradeoffs presented in Lemma 3.1. We will add a more detailed discussion regarding these results in the main body of the paper (see also the response to Reviewer 5dQu).\n\nRegardless of the outcome of the NeurIPS reviewing process, we will upload the full version of our work to arXiv.\n"}, {"review_id": "9eEAXCyGks", "reviewer": "Reviewer_8owE", "summary": "The paper studies hypothesis selection in a streaming setting, with samples arriving online. The main result gives a near-optimal memory-sample trade-off for hypothesis selection.  Along the way, the paper invents several new techniques to avoid expensive memory usage of prior work.", "questions": "To avoid the assumption of having access to the probability of Scheffe sets, have you considered approaches that don’t require Scheffe sets at all? I understand that the minimum distance estimate [DL01, MS08] is used in the all-go-against-all tournament step. Can ideas like that be used throughout, so we don’t need query Scheffe sets? \n", "limitations": "The author(s) have discussed some future directions, though I think a conclusion section summarizing these would be great.", "rating": 7, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "This is one of the most classic questions in nonparametric statistics. Prior work [MS08, DK14] have tackled the run-time problem. I believe that its memory efficiency is also an important aspect. This paper offers exactly such a study.\n\nAt a technical level, the paper nearly resolves the question, up to some minor logarithmic factors. The high-level approach is simple and may be practical. The techniques, as far as I know, are novel and could potentially be used by later works. I have not checked the proof details in the appendix, but based on the main body, the main arguments are sound.\n\nThe paper is generally well-written. \n", "weaknesses": "I do not find any major weakness of this paper. \n\nOne thing I should point out is that the imperfect comparison issue (discussed in section 2.2.1) has been studied in the literature of noisy sorting. In fact, I believe the main result from the random ladder tournament, *at least* in the offline setting (section 3.1), can be derived simply in a blackbox way from Theorem 3.8 of Sorting and Selection with Imprecise Comparisons by Miklós Ajtai, Vitaly Feldman, Avinatan Hassidim and Jelani Nelson (TALG 2015) (https://dl.acm.org/doi/10.1145/2701427). In particular, their $\\delta$ is your $3\\Gamma$, the error gap between good and bad hypotheses in the comparison procedure (Algorithm 1). Their number of items there is your number of hypotheses, both denoted by $n$. So up to another factor of $k=3$, applying their randomized max-finding algorithm would yield a hypothesis that’s $9\\Gamma$ close to the optimal.  (Another related work is https://arxiv.org/abs/1606.02786 where an improved algorithm is given and an application to hypothesis selection is explicitly derived. I have not checked the details, though.)\n\nI would ask the author(s) to confirm this and see if an alternative argument using the paper above can be made and whether it’s interesting. \n\nI should note that this, if true, does not trivialize the results in this paper. The algorithm of Ajtai et al cannot be implemented in the memory-constrained setting, below a memory size of $n^{1/3}$. Also in the offline setting, the resulting constant is not optimal for the hypothesis selection problem. \n\n\n \n\nMinor comments\n---\nLine 62–67: list these two query access assumptions as \\begin{itemize}\n\nLine 65: “ the probabilities of the Scheffé sets”  — I think it’s more clear to refer to this as “the probability masses of the Scheffe sets”.\n\nLine 117: “we sample a uniformly random new hypothesis from H” — Please clarify: is this sampling with replacement, if I view the meta-distribution as uniform over the n input hypotheses? That is, a hypothesis can be selected multiple times against the same single hypothesis in memory. \n\nLine 202: Regarding [MS08], mention that the simple linear-time selection from Appendix A doesn’t do such expensive preprocessing.\n\nLine 265: Can you clarify in which scenario or parameter regime would you use Scheffé counts? (I didn’t read the appendix.) Note that the memory usage of this technique is quadratic in $n$. Hence, are you tracking these counts on a small subset of hypotheses?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "> the main result from the random ladder tournament, ... can be derived simply ... from ...(https://dl.acm.org/doi/10.1145/2701427). \n\nThank you for the reference. We will be sure to add it to our discussion of previous work. That said, we did not see how the main result can be derived in a blackbox way from Theorem 3.8.\n\nDefining $val(H) := \\|H - P\\|_{tv}$, we can view hypothesis selection as the task of approximately minimizing $val(H_i)$ over $i \\in [n]$ given a noisy comparator for these values. To apply their Theorem 3.8 to this task, we need to identify the distance parameter $\\delta$ for which our COMPARE subroutine (our Theorem 1) is always guaranteed to produce the correct comparison between two hypotheses whose values are at least $\\delta$ far apart. For every pair of hypotheses $H_i, H_j$, our COMPARE subroutine correctly reports that $val(H_i) \\ge val(H_j)$ as long as $val(H_i) \\ge 3 \\cdot val(H_j)$, and this is tight.\n\nThus, the distance parameter we can achieve is lower bounded by $\\delta \\ge \\min\\{val(H_i), val(H_j)\\}$. Taking the maximum over all pairs $i, j$, we see that the best (smallest) $\\delta$ we can achieve is the second largest value of $val(H_i) = \\|H_i - P\\|_{tv}$, taken over all $i \\in [n]$. This can be arbitrarily large as a multiple of $OPT = \\min_{i \\in [n]} \\|H_i - P\\|_{tv}$, and so approximating the minimum value to within $O(\\delta)$ may not bring us within $O(OPT)$.\n\nOf course, would be happy to be corrected on this point if the reviewer has a different argument in mind.\n\n-----------------------------\n\n> Another related work is https://arxiv.org/abs/1606.02786 where an improved algorithm is given ...\n\nThis paper (henceforth \"AFJOS16\") is absolutely relevant, and we thank the reviewer for pointing it out.\n\nAFJOS16 contains an algorithm for solving hypothesis selection (density estimation) making linearly many comparisons and running in $O(n\\log n)$ time, that achieves accuracy ratio $\\alpha = 9$. \n\nAs far as we understand, our algorithms improve on AFJOS16 in two respects. \n1. It is not straightforward how to implement the AFJOS16 algorithms with $o(n)$ bits of memory. In particular in their \"Q-Select\" algorithm, one maintains a set of hypotheses of size $\\Omega(n)$. \n2. The accuracy parameter $\\alpha$ we obtain is better (smaller) than that of AFJOS16. Note that AFJOS16 solves the density estimation problem without promise (no knowledge of $\\Gamma$), so to draw a fair comparison, we make this statement about the \"no promise\" version of our algorithm achieving $\\alpha = 5$ (which is less than the factor of 9 they achieve). See Section A, Theorem A.2 of our submission.\n \nWe will make sure to cite and discuss this paper in future versions of the paper. \n\n-----------\n\n> Line 117: “we sample a uniformly random new hypothesis from H” — Please clarify: is this sampling with replacement,...\n\nGood question. We draw the hypotheses from a meta distribution in an i.i.d. manner. If the meta distribution is a uniform distribution over $\\mathcal{H}$, then we sample uniformly from $\\mathcal{H}$ with replacement, implying that hypotheses can be selected several times. These repetitions  do not affect our analysis as long as we ensure that $H^*$ shows up with probability at least $p_0$ at every step.\n\nWe use the generality of the meta-distribution in our main result, where we apply the ladder to the (not necessarily uniform) distribution on hypotheses that comes from the output of a particular subroutine. \n\nA second reason is that the meta-distribution version of the ladder allows to amplify the success probabiltiy of the algorithm by running for more steps without changing the approximation guarantee. (Naive ways of amplifying success probability require another layer of comparisons, which changes the approximation constant.)\n\nWe will edit our text to make sure these points are clear. \n\n-------------\n\n>Line 265: Can you clarify in which scenario or parameter regime would you use Scheffé counts? ...\n\n\nYour observation on quadratic memory use of Scheffé counts is right. For algorithm with $b$ bits, we focus on $t \\approx \\tilde{O}(\\sqrt{b})$ hypotheses. $t$ is chosen so $O(t^2)$ Scheffé counts fit in $\\Theta(b)$ bits for any comparison among $t$ hypotheses.\n\nWe have used the Scheffé counts for two results:\n1) A basic tradeoff presented in Lemma C.1\n2) Main result presented in Section E.4.\n\nWe discuss each of these in a bit more detail in case it is helpful:\n1. We start by off the sketch for our basic tradeoff: We store the Scheffé counts for $t$ random hypotheses. In this way, we can easily compare these $t$ hypotheses, so we can run the random ladder tournament for $t$ steps. We repeat this process again. We take the winner of the last step  and add $t-1$ random hypotheses. Draw fresh sample and obtain the Scheffé counts of these $t$ hypotheses, and move forward with another $t-1$ steps of the random ladder tournament. This approach leads to a tradeoff described in Lemma C.1. This tradeoff is off by a factor of $t \\approx \\sqrt{b}$ due to the inefficincy of the Scheffe counts. However, this tradeoff has a better dependency on $\\epsilon$ (and in some way on $\\log n$) than what one gets from  Lemma 3.1: in Lemma C.1 we have $b \\approx O(t^2)$ instead of $b \\approx O(t \\log n/\\epsilon^2)$ in Lemma 3.1.\n\n2. We exploit this advantage of Scheffé count later in the proof of our main result. The reason that we can tolerate this extra factor of $\\sqrt{b}$ is that in the final algorithm the random ladder is used on only $k$ filtered hypotheses where $k \n\\ll n$ (roughly, $k \\approx \\sqrt{n})$. Hence, we have some slack to tolerate $\\sqrt{b}$. On the other hand, if we use the other simple tradeoff (Lemma 3.1) that is based on sorted lists, we get a factor of $1/\\epsilon^4$ that we cannot improve. Therefore, while the simple tradeoff of Lemma C.1 is worse than Lemma 3.1, this is the tradeoff we used in our main theorem. See Section E.4 in the supplementary material for more details. "}]

Author rebuttal:
We thank the reviewers for their time and thoughtful comments. We will incorporate all the editorial comments. 
Please find the individual responses to the reviewers below. 

Meta-review: The authors study the classic problem of hypothesis selection but under memory constraints. They define a certain query model where the leaner can compare the pdf values of the distributions at the given data point. The authors then present an algorithm that achieves (near) optimal tradeoff between memory and sample complexity in a certain sense: the number of bits (memory) times the number of samples used is O(n.log n), matching a known lower bound.

The reviewers were quite positive about the paper, and found the contributions significant. There was some doubt about the relevance of the algorithmic (i.e., memory efficiency) contributions to the NeurIPS community. There were also concerns about the quality of the presentation and the reviewers thought the setting (the query model as well as the tradeoff measure) could be better justified. The authors are therefore encouraged to elaborate more on the model, and perhaps discuss the distributed learning under information constraints angle in more details.

I recommend acceptance.
Decision: Accept (poster)