Universal Rates for Active Learning

Authors: steve  hanneke
amin  karbasi
shay  moran
grigoris  velegkas
Venue: NeurIPS_cc_2024_Conference
Published: 2024-05-14 13:00:13

Abstract: In this work we study the problem of actively learning binary classifiers
  from a given concept class, i.e., learning by utilizing unlabeled data 
  and submitting targeted queries about their labels to a domain expert.
  We evaluate the quality of our solutions by considering the learning curves
  they induce, i.e., the rate of decrease
  of the misclassification probability as the number of label queries
  increases. The majority of the literature on active learning has 
  focused on obtaining uniform guarantees on the error rate which are
  only able to explain the upper envelope of the learning curves over families
  of different data-generating distributions. We diverge from this line of
  work and we focus on the distribution-dependent framework of universal
  learning whose goal is to obtain guarantees that hold for any fixed distribution,
  but do not apply uniformly over all the distributions. We provide a 
  complete characterization of the optimal learning rates that are achievable
  by algorithms that have to specify the number of unlabeled examples they
  use ahead of their execution. Moreover, we identify combinatorial complexity
  measures that give rise to each case of our tetrachotomic characterization.
  This resolves an open question that was posed by Balcan et al. (2010).
  As a byproduct of our main result,
  we develop an active learning algorithm for partial concept classes
  that achieves exponential learning rates in the uniform setting.

Main paper: 
 introduction: 
 The most prototypical type of learning is that of supervised learning, where an algorithm is given as input n labeled data points sampled i.i.d. from some unknown distribution and the goal is to output a function that has low probability of misclassifying new data from the same distribution. One caveat with this passive model of learning is that it fails to capture the settings in which unlabeled data is easily accessible, but obtaining their labels is costly. A natural example that fits this description is that of webpage classification. It is easy for any web crawler to collect information about billions of different webpages in a very short amount of time, however understanding which category a webpage belongs to usually requires human feedback. Perhaps the most commonly used way to model this problem is through the active learning framework in which the learner is given access to a large stream of unlabeled data and a budget of n queries that it can submit to a domain expert in order to obtain the label of some datapoint. The learner's goal is to submit queries for the labels of the most informative examples, and, as a result, eliminate some redundancy in the information content of labeled data.In this paper we study the optimal learning rates that are achievable by an active learning algorithm. In the passive learning setting, it is common to measure the quality of an algorithm by its learning curve, i.e., plotting the decay of its error rate as the number of training examples increases. In contrast, in the active learning setting, the resource we are interested in is the number of label queries the algorithm requests, so it is natural to consider the rate of decay of the misclassification probability as the number of queries n increases. Most of the prior works on active learning have focused on obtaining uniform guarantees on the error rate, i.e., guarantees that hold uniformly over the data-generating distributions. In this work we follow a different path and we view the problem through the lens of universal rates that was recently introduced by Bousquet et al. (2021) . In this framework we are aiming for guarantees that hold for all distributions, but they do not hold uniformly over them. In other words, we allow for distribution-dependent constants in the error rate. To make the distinction between uniform and universal rates clear, we first recall what uniform learnability of a hypothesis class H means. We say that H is uniformly learnable at rate R(n) if there exists a learning rule ĥn such that∃C, c > 0 ∀P ∈ RE(H) it holds that E[erP( ĥn )] ≤ C • R(c • n), ∀n ∈ N .The above expression states that there exists a learning rule ĥn and distribution-independent constants such that for all realizable distributions the expected error rate of the classifier is at mostC • R(c • n).The difference in the definition of universal learnability is that we swap the order of the quantifiers. To be more precise, we say that a class H is universally learnable at rate R(n) if there exists a learning rule ĥn such that∀P ∈ RE(H) ∃C, c > 0 such that E[erP( ĥn )] ≤ C • R(c • n), ∀n ∈ N .Note that in the above definition the constants c, C are distribution-dependent. As is evident from our main result and from prior results in universal learning (Bousquet et al., 2021; Hanneke et al., 2022; Kalavasis et al., 2022; Bousquet et al., 2022; Hanneke et al., 2023) this change in the definition affects the landscape of the optimal learning rates significantly.Active Learning. There has been a very long line of work deriving theoretical guarantees for active learning, both in the realizable and the agnostic setting (Cohn et al., 1994; Dasgupta, 2005; Balcan et al., 2006; Hanneke, 2007b,a; Dasgupta et al., 2007; Hanneke, 2009; Balcan et al., 2009 Balcan et al., , 2010;; Hanneke, 2012 Hanneke, , 2014;; Wiener et al., 2015; Hanneke and Yang, 2015; Beygelzimer et al., 2016) . As we alluded to before, most of these works focus on obtaining minmax guarantees, i.e., the bounds they provide hold in the worst case over a family of distributions. To be more precise, while many of these results have distribution-dependent guarantees, they are typically expressed in a way that aims to match a lower bound on the minmax performance over a family o distributions, with respect to some parameter, like the disagreement coefficient. For these reasons the results in these works do not capture the full spectrum of universal rates. We also remark that there are a few works that do study universal rates, e.g. Balcan et al. (2010) ; Hanneke (2012) ; Yang and Hanneke (2013) , but none of them have derived a complete characterization of the optimal rates.Universal Rates. The study of universal learning rates was put forth in the seminal work of Bousquet et al. (2021) who derived a complete characterization of the optimal rates in the supervised learning setting. Later, Kalavasis et al. (2022) extended these result to the multiclass setting, with a bounded number of classes, and Hanneke et al. (2023) improved upon this result by characterizing multiclass classification with an infinite number of labels. Subsequently, the work of Bousquet et al. (2022) derived more fine-grained results for binary classification compared to Bousquet et al. (2021) . The work that is most closely related to ours is Hanneke et al. (2022) which derives a complete characterization of the optimal learning rates in a very general interactive learning setting. In that setting, the learner is allowed to submit arbitrary binary valued queries about the unlabeled data. We provide a detailed comparison between our results and theirs in Section 1.5. Very recently, Attias et al. (2024) studied universal rates in the context of regression. they showed that there are such classes that are online learnable but none of their "extensions" to total concept classes is online learnable. The advantage of partial concepts is that they provide a convenient way to express data-dependent constraints. En route of obtaining our main result, we design active learning algorithms for partial concept classes. For a more detailed discussion about partial concepts we refer the reader to Appendix A.2.Learning Model. We now present formally the learning setting that we consider in this work. There is a domain X , which we assume to be a Polish space, and a concept class H ⊆ {0, 1} X , which satisfies standard measurability assumptions (see Definition A.1). We define a classifier h : X → {0, 1} to be a universally measurable function and its error rate is defined as er P (h) := P [(x, y) : h(x) ̸ = y], where P is the data-generating distribution over X × {0, 1}. When P is clear from the context we might drop the subscript P in er P (h). We call P realizable with respect to the hypothesis class H if inf h∈H er P (h) = 0. We denote by P X be the marginal distribution of P on X .Active Learning Model. We define an active learning algorithm to be a sequence of universally measurable functions which, given access to a stream of unlabeled data points from X that are drawn i.i.d. from P X and a label query budget n, output a classifier ĥn : X × {0, 1}. In this work we consider a non-adaptive active learning model, with respect to the unlabeled data. In particular, the learning algorithm needs to specify a function u : N → N so that u(n) is the number of unlabeled points it observes and n is the number of points for which it can request the label. The number u(n) is specified before the execution of the algorithm and cannot be modified based on the realization of the unlabeled sequence or the answers that it gets for the labels of the points it queries. We place no bound whatsoever on the function u(•). Also, the algorithm can only request the labels of points it has observed and not arbitrary points from X . We emphasize that the label requests that the algorithm makes can be adaptive, and can depend on answers to previous label queries. To the best of our knowledge, the active learning algorithms that have been proposed in the literature either fit into this model or they can be modified to satisfy the non-adaptivity restriction with negligible performance loss.Learning Rates. We now define formally what it means for an algorithm to achieve a learning rate R(n) in the universal learning model. We adopt the definition of Bousquet et al. (2021) .Definition 1.1 (Learning Rates (Bousquet et al., 2021) ). Fix a concept class H, and let R : N → [0, 1], R(n) n→∞ -→ 0 be a rate function, where n is the label query budget of the learner.• H is learnable at rate R if there is a learning algorithm ĥn such that for every realizable distribution P, there exist c, C for which E[er( ĥn )] ≤ CR(cn), ∀n ∈ N.• H is not learnable at rate faster than R if for all learning algorithms ĥn there exists a realizable distribution P and c, C for which E[er( ĥn )] ≥ CR(cn), for infinitely many n ∈ N.• H is learnable with optimal rate R if it is learnable at rate R and it is not learnable at rate faster than R.• H admits arbitrarily fast rates if for all rate functions R, it is learnable at rate R.• H requires arbitrarily slow rates if for all rate functions R, it is not learnable at rate faster than R.Combinatorial Measures. We now define some combinatorial complexity measures that our characterization relies on. To make the presentation easier to follow, we provide informal definitions.For the formal ones, we refer the reader to Appendix A.3. We first describe the Littlestone tree that was introduced by Bousquet et al. (2021) . Definition 1.2 (Littlestone Tree, Informal (see Definition A.8) (Bousquet et al., 2021) ). A Littlestone tree for H ⊆ {0, 1} X is a complete binary tree of depth d ≤ ∞ whose nodes are labeled by elements of X and the edges to the left, right child are labeled by 0, 1. We require that for every level 0 ≤ n < d and every path from the root to a node at level n there is some h ∈ H that realizes this path. We say that H has an infinite Littlestone tree if it has a Littlestone tree of depth d = ∞.We underline that this notion can be thought of as an infinite extension of the Littlestone dimension (Littlestone, 1988) of H. Recall that the Littlestone dimension is defined to be the largest d ∈ N for which H has a Littlestone tree of such depth and it is ∞ if one can construct Littlestone trees of arbitrary depth. Crucially, this is not the same as having a single tree whose depth is infinite, so one can see that infinite Littlestone dimension is not the same as having an infinite Littlestone tree.We next give the definition of the Vapnik-Chervonenkis-Littlestone tree (VCL) that was introduced by Bousquet et al. (2021) . Definition 1.3 (VCL Tree, Informal (see Definition A.10) (Bousquet et al., 2021) ). A VCL tree for H ⊆ {0, 1} X is a complete tree of depth d ≤ ∞ such that every level 0 ≤ n < d has nodes that are labeled by X n+1 with branching factor 2 n+1 and whose 2 n+1 edges connecting a node to its children are labeled by the elements of {0, 1} n+1 . We require that for every node at any level 0 ≤ n < d, the path from the root to this node is realized by some h ∈ H. We say that H has an infinite VCL tree if it has a VCL tree of depth d = ∞.Intuitively, the VCL tree combines the notions of the Littlestone tree and the VC dimension (Vapnik and Chervonenkis, 1971; Blumer et al., 1989) . The differences between the Littlestone tree and the VCL tree are that in the latter the size of the nodes increases linearly with the level and the branching factor increases exponentially, whereas in the former all the nodes are singletons and the branching factor is always two.We are now ready to introduce a new combinatorial measure which we call the star tree. Definition 1.4 (Star Tree, Informal (see Definition A.9)). A star tree for H ⊆ {0, 1} X is a complete tree of depth d ≤ ∞ such that every level 0 ≤ n < d has nodes that are labeled by (X × {0, 1})n+1with branching factor n + 1 and whose n + 1 edges connecting a node to its children are labeled by {0, . . . , n}. The label of the edge indicates the element of the node whose label along the path is flipped. We require that for every node at level 0 ≤ n < d, the path from the root to this node is realized by H. We say that H has an infinite star star tree if it has a star tree of depth d = ∞.Essentially, this definition combines the structure of a Littlestone tree with the notion of the star number (Hanneke and Yang, 2015) . Every node at level n consists of n + 1 labeled points and there are n + 1 edges attached to it. Each edge indicates which of the n + 1 points of the labeled node has its label flipped along every path that this edge is part of.We are now ready to state the main results of this work. Our first main result is a complete characterization of the optimal learning rates that a class H admits in the active learning setting. Theorem 1.5. For every concept class H exactly one of the following cases holds.• H is actively learnable at arbitrarily fast rates.• H is actively learnable at an optimal rate e -n .• H is actively learnable at o(1/n) rates, but requires rates arbitrarily close to 1/n.• H requires arbitrarily slow rates for active learning.Our next result characterizes exactly when these rates occur by specifying combinatorial complexity measures of H that determine which case of the tetrachotomy it falls into. Theorem 1.6. For every concept class H the following hold.• If H does not have an infinite Littlestone tree, then it is learnable at arbitrarily fast rates.• If H has an infinite Littlestone tree but does not have an infinite star tree, then it is learnable at optimal rate e -n .• If H has an infinite star tree but does not have an infinite VCL tree, then it is learnable at optimal rate o(1/n), but requires rates arbitrarily close to 1/n.• If H has an infinite VCL tree, then it requires arbitrarily slow rates.We remark that the landscape of the optimal rates looks significantly different compared to the passive setting (Bousquet et al., 2021) and the general interactive learning setting (Hanneke et al., 2022) . Our main result answers an open question that was posed in Balcan et al. (2010) , which asks for necessary and sufficient conditions for learnability at an exponential rate in the active learning setting.We now present examples of classes that witness each case of our tetrachotomic characterization.Arbitrarily-fast rates: Bousquet et al. (2021) give examples with no infinite Littlestone tree (e.g., thresholds on the integers, and positive halfspaces on N d ), hence learnable at arbitrarily fast rates.Exponential rates: Famously, threshold classifiers [a, ∞) over R have an infinite Littlestone tree and are actively learnable at exponential rate (even uniformly). A more interesting example is the class of interval classifiers [a, b] on R, which (also famously) has uniform rate 1/n for active learning (it has infinite star number), and has an infinite Littlestone tree, but it has no infinite star tree: for any choice of x in the root node, the edge labeling x as 1 has a version space with star number equal 4 (it is effectively 2 disjoint threshold problems), so the depth of that subtree is bounded. Therefore, by our theory, it is actively learnable at e -n universal rate (in stark contrast to the uniform rate 1/n).Sublinear rates: Halfspaces on R d have an infinite star tree but no infinite VCL tree. To construct that star tree, the key observation is that any set in convex position is a star set (Balcan et al., 2010) .Arbitrarily slow rates: Bousquet et al. (2021) provide examples of classes with an infinite VCL tree, such as the class of all claffisifiers, so these require arbitrarily slow rates in our setting as well.We now compare our characterization to the results of Bousquet et al. (2021) that prove an analogous result in the supervised learning setting. Let us first recall their main result which shows that in this learning model a class is universally learnable at:• Exponential rate e -n if and only if it does not have an infinite Littlestone tree.• Linear rate 1/n if and only if it has an infinite Littlestone tree but does not have an infinite VCL tree. • Arbitrarily slow rates if and only if it has an infinite VCL tree.As one can see, our results illustrate the advantage that active learning algorithms have over their supervised counterparts. We underline that the only case where active learning does not offer an improvement compared to the passive setting is when H has an infinite VCL tree.Let us now discuss the interactive learning model that was considered by Hanneke et al. (2022) . In this general model of interaction, the learner is allowed to ask arbitrary binary queries about any subset of the unlabeled data. In particular, these queries include, but are not limited to, label queries, comparison queries, and general membership queries. They show that the optimal rates that any class H admits are the following:• Arbitrarily fast if and only if it does not have an infinite Littlestone tree.• Exponential if and only if it has an infinite Littlestone tree but not an infinite VCL tree.• Arbitrarily slow if and only if it has an infinite VCL tree.We underline that the algorithm by Hanneke et al. (2022) that achieves arbitrarily fast rates uses only label queries and the number of unlabeled data u(n) that it uses can be chosen statically prior to the execution of the algorithm. Therefore, this result applies to the setting we consider in our work. Moreover, the lower bounds they provide also apply to our setting since (i) the queries that Hanneke et al. (2022) consider are more general, and (ii) their lower bounds hold even when the learner knows the marginal distribution P X . As is evident from our main result, the active learning setting provides a richer landscape of optimal rates compared to the general interactive learning setting of Hanneke et al. (2022) . In particular, just the absence of an infinite VCL tree for H does not necessarily imply that we can achieve (at least) exponential rates. To get this result, Hanneke et al. (2022) make strong use of these general queries in order to provide an algorithm that has a binary-search flavor and can learn partial concept classes with finite VC dimension at an exponential rate. Our main result shows that such guarantees are not achievable by using only label queries.The most technically innovative part of our work is the o(1/n) algorithm. Let us set up some terminology to facilitate our discussion. The version space of a concept class, given a labeled dataset S, is the set of concepts that classify all the elements of S correctly. Moreover, the VCL game is a Gale-Stewart game defined by Bousquet et al. (2021) that was used in their passive learning algorithm that achieves 1/n universal rate. The original (passive) learner from Bousquet et al. (2021) partitions a portion of the data into some number B(n) of batches, from which they construct partial concept classes of finite VC dimension by using the batches to play the VCL game against the player's winning strategy, and for each resulting partial concept class they run a separate learner on another portion of data and return a majority vote of their resulting classifiers. The latter part of this strategy could never work in the active learning setting, since the number of batches B(n) must be an increasing function of n, and applying an active learner for each partial concept class separately would require each to use (nearly) Ω(n) queries (to get the o(1/n) guarantee there), so the total number of queries would be (nearly) Ω(B(n)n) ≫ n, violating the label budget n. To resolve this, we ended up completely re-imagining how to use these partial concept classes. Rather than running a separate algorithm for each class, we run a single active learning algorithm, where individual decisions of whether to query involve voting over the partial concept classes. We first extend an algorithm of Hanneke (2012) (for total concepts) to achieve o(1/n) rate for partial concept VC classes (this required completely re-formulating Hanneke's analysis). The resulting algorithm involves estimating the probability that a random k-tuple is VC shattered by certain constrained version spaces. We replace this with an estimated average (over a select subset of partial concept classes) of this shattering probability, which we show composes appropriately with the analysis of the algorithm to obtain the o(1/n) rate. Comparing our work to the general interactive learning setting considered by Hanneke et al. (2022) , the main differences are (i) we design a new algorithm that uses only label queries and achieves exponential rates when H does not have an infinite star tree, a combinatorial measure we introduce in our work, (ii) we prove a o(1/n) lower bound in the setting where H has an infinite star tree, and (iii) we propose a novel active learning algorithm that achieves sublinear rates when H does not have an infinite VCL tree. 
arbitrarily fast rates: 
 As we explained before, the first case of the tetrachotomy in our characterization is a direct implication of the results by Hanneke et al. (2022) . To be more precise, they design an algorithm which achieves arbitrarily fast rates using only label queries. In order to do that, they need the number of unlabeled points u(n) to be an arbitrarily fast increasing function, that, nevertheless, can be specified in a non-adaptive manner prior to the execution of the algorithm. The result is summarized in Theorem 2.1. Theorem 2.1 (Hanneke et al. (2022) ). If H does not have an infinite Littlestone tree it is actively learnable with arbitrarily fast rates.For completeness, we present their algorithm in Figure 1 . Similary with the upper bound, the lower bound is an immediate consequence of a result from Hanneke et al. (2022) , since the learner can submit more informative queries in their model. Theorem 2.2 (Hanneke et al. (2022)) . If H has an infinite Littlestone tree, then H is not actively learnable at rate faster than exponential e -n . This holds even if P X is known to the learner.• It is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have a 96% CI, if the hypothesis of Normality of errors is not verified. • For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out of range (e.g. negative error rates). • If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text. 
exponentially fast rates: 
 In this section, we prove the second case in the tetrachotomy we have stated, i.e., that H is learnable at an exponential rate if and only if it has an infinite Littlestone tree and it does not have an infinite star tree. Our proof consists of two parts. First, we show that if H does not have an infinite star tree it is learnable at an exponentially fast rate. Then, we show that whenever H has an infinite star tree, the best achievable rate cannot exceed o(1/n). The omitted details can be found in Appendix C.The high-level approach to get the exponential rates algorithm follows the same spirit of the approaches from Bousquet et al. (2021) ; Hanneke et al. (2022) . First, we design an appropriate Gale-Stewart game (cf. Appendix A.2), i.e., a game between a learner and an adversary, that is associated with H in which the learner has a winning strategy if and only if H does not have an infinite star tree. The next step is to show that, in the limit, the winning strategy of the learner gives rise to a partial concept class F that has finite star number (see Definition A.7). Since this result is asymptotic, our approach is to consider several instances of this game, execute them for a finite number of steps, and obtain a partial concept class from each one. Then, we aggregate these classes into a majority class. The intuition is that, with high probability, most of the games will have induced classes whose star number is bounded by a distribution-dependent constant, so then we can show that the majority class will also have bounded star number, and this bound is distribution-dependent. Thus, our task boils down to actively learning a partial concept class whose star number is finite. In order to do that, we extend the approach that Hanneke and Yang (2015) used for total concept classes to the regime of partial classes. We believe that this result could be of independent interest.We first outline the Gale-Stewart game we use. Recall that every node of a star tree at depth n consists of n + 1 points along with their labels. There are n + 1 edges that connect the node with its children and the label of every edge indicates the point whose label is flipped along any path that uses this edge. Let us now describe the game G that we use in this setting. In every round τ ≥ 1 we have the following interaction between the learner P L and the adversary P A :• Player P A chooses points ( ⃗ ξ τ , ⃗ ζ τ ) = (ξ 0 τ , . . . , ξ τ -1 τ , ζ 0 τ , . . . , ζ τ -1 τ ) ∈ X τ × {0, 1} τ . • Player P L chooses η τ ∈ {0, . . . , τ -1}. • Player P L wins the game in round τ if H ⃗ ξ1, ⃗ ζ1,η1,..., ⃗ ξτ , ⃗ ζτ ,ητ := h ∈ H : h(ξ i s ) = ζ i s , if η s ̸ = i h(ξ i s ) = 1 -ζ i s , if η s = i , 1 ≤ s ≤ τ, 0 ≤ i < s = ∅.( The first step in our approach, is to make use of some Θ(n) label queries in order to obtain the labels of Θ(n) many points. The idea these labeled points in order to simulate the Gale-Stewart game we described above (see Appendix C.3 for the details). The main technical issue we need to handle is that we have no control over the number of rounds the game needs in order to terminate. Using ideas that have appeared in the universal learning literature, we use a portion of these labeled points to estimate some number tn so that, with at least some constant probability over the dataset, the game will terminate within tn many rounds. Then, we split the remaining of the labeled dataset into batches of size tn and we run the game on each batch. The outcome of each game gives us a pattern-avoidance function, i.e., a function that takes an input tuples of arbitrarily labeled points and changes the label of one of them so that the resulting labeled tuple is not consistent with the data-generating distribution P. In other words, the output of this function could not have been generated by the P. A technical complication we need to handle is that we obtain multiple such pattern avoidance functions, some of which are incorrect, but to make the presentation cleaner we explain the idea using a single pattern avoidance function g t * that produces inconsistent labels. The formal setting is handled in Appendix C.4. One way to think about this function is that it provides data-dependent constraints. Thus, it is natural to express such a constraint through a partial concept class. We defineF = f : X → {0, 1, ⋆} : (x 1 , f (x 1 )), (x 2 , f (x 2 )), . . . , (x t * , f (x t * )) / ∈ image( g t * ), ∀x 1 , . . . , x t * ∈ X t * .Notice that the constraint we have placed onF is satisfied if f (x i ) = ⋆, for some i ∈ [t * ].We consider the natural extension of the notion of star sets to the case of partial concept classes, i.e., we say that a labeled set S with labels in {0, 1} is a star set if S and its adjacent sets S ′ , whose labels are still restricted to be in {0, 1}, are obtainable using functions from F (see Definition A.7). A key observation is that the star number of F is bounded by t * -1. Another difficulty we need to overcome is that we do not know t * , since it is a random variable that depends on the realized sequence and its distribution might have heavy tails. To make our approach easier to follow, let us first assume that we do know t *1 . Then, our task boils down to actively learning a partial concept class.We now present an algorithm that achieves exponential rates when actively learning a partial concept class F that star number s < ∞. The idea of our approach is to reduce the problem of actively learning a partial concept to the well-studied problem of actively learning a total concept class. The algorithm is presented in Figure 2 . Let us explain the high-level ideas of the algorithm. First, we consider a large enough set of unlabeled data. Our goal is to find their labels using logarithmically many queries. To do that, we consider the uniform distribution over these unlabeled examples. Then, we use an algorithm from Hanneke and Yang (2015) (see Theorem C.1) which guarantees exponential rates when applied to a class with finite star number. Because the underlying distribution on the sample is uniform, with high probability, the algorithm will find the correct labels of all the points. Finally, we feed these labeled examples to the one-inclusion graph algorithm (Theorem A.5) to get the desired result. We are now ready to state our theorem. The proof is postponed to Appendix C.2. Theorem 3.2. There exists an active learning algorithm A for a partial concept class F which given a label budget n and access to unlabeled samples from a realizable distribution P * returns a classifier ĥn such that EP * [er( ĥn )] ≤ c 1 de -c2n/s , where c 1 , c 2 are absolute numerical constants, and s, d is the star number, VC dimension of F.The next step in the characterization is to show that if H has an infinite star tree, then it does not admit rates faster than sublinear. The proof starts by picking a random path on the infinite star tree. The target distribution is supported only on nodes of the selected path. Then, given some algorithm ĥn , we distribute the mass of the target probability distribution across the path, potentially skipping some nodes of it, in a way that creates an infinite sequence n i1 , n i2 , . . ., so that when the learner has label budget n ij , with some constant probability, it will only observe unlabeled points up to level k ij .Moreover, with at least some constant probability, it will not query the point of that level whose label is flipped along the target path. On that event, it makes a mistake with probability at leastC • p ij /k ij , where C is some absolute constant. Our choice of p ij , k ij guarantees that R(n j ) > p ij /k ij , where R(•)is the target sublinear rate function. Finally, we apply Fatou's lemma to get the desired result.For the full proof and the formal theorem statement, we refer the reader to Appendix C.5 
sublinear rates: 
 Our approach to achieve sublinear rates in the setting where H does not have an infinite VCL tree shares some high-level ideas with the one in Section 3, but many technical challenges make it significantly more involved. The main obstacle is that there is no active learning algorithm that achieves sublinear rates for VC classes uniformly over all realizable distributions. Recall that in the exponential rates setting, such an algorithm does exist (Hanneke and Yang, 2015) . Instead, the sublinear rates algorithm for VC classes from Hanneke (2012) depends on distribution-dependent constants in the sample complexity. The omitted details from this section can be found in Appendix D.Instead of the star tree Gale-Stewart game that was used to get the exponential rates guarantee, we use the VCL Gale-Stewart game Bousquet et al. (2021) (cf. Figure 6 ). To be more precise, we use ⌊n/5⌋ of the label budget to get the labels of ⌊n/5⌋ unlabeled points that come i.i.d. from P X . Then, we execute the VCL game onΘ( √ n) different batches of size Θ( √ n).Each of these games induces a partial concept class. We show how to obtain a P-dependent bound on the VC dimension that holds for most of these classes. Moreover, we show that for most of these classes the data-generating distribution P is realizable. Finally, we design a single active learning algorithm that combines information from all these classes and achieves sublinear learning rates. This algorithm builds upon Hanneke (2012) but is modified to work with partial concept classes instead of total concept classes. This requires a very different analysis and is the most technically involved part of our work.Let us now explain the main ideas of this algorithm and the challenges behind it. As we mentioned before, the number of queries that the algorithm from Hanneke (2012) needs to achieve the sublinear error rate depends on the underlying data-generating distribution. Thus, we cannot just get a large enough number of unlabeled samples, consider the uniform distribution over them and use the algorithm on this distribution. This is because the learning rate for H would depend on the uniform distribution U S over the sample S and not on the data-generating distribution P. To illustrate the ideas of the algorithm, we consider five different streams of i.i.d. (unlabeled) data S 1 , S 2 , S 3 , S 4 , S 5 . For the purposes of the subsequent discussion, we can imagine that these streams have infinite size, but as explained in description of the algorithm, we only need poly(n) unlabeled points. Let us first explain the use of S 5 . We use n/5 of our query budget to obtain the labels of the first n/5 points and then we use them to train a supervised learning algorithm from Bousquet et al. (2021) that achieves linear rate O(1/n). This is used for technical reasons in our analysis and in order to ensure that the classifier we output has, at most, linear error rate no matter how the active learning component of our algorithm behaves. Next, we use n/5 of the query budget to obtain the labels of the first n/5 points from S 1 . Then, we run the VCL game on these labeled datasets of size √ n/5 and obtain √ n different pattern avoidance functions y i √ n/5 that take as input ℓ i √ n/5 points (cf. Appendix D.2), where i ∈ [√ n]. Let F i √ n/5 := f : X → {0, 1, ⋆} : (f (x 1 ), . . . , f (x ℓ i √ n/5 )) ̸ = y i √ n/5 (x 1 , . . . , x ℓ i √ n/5 ) , i ∈ [ √ n] .First, we show that for a (1 -o( 1))-fraction of these partial concept classes P is a realizable distribution. Intuitively, this means that the partial concept class we obtain by running the VCL game on √ n many points is the same as the class we would have obtained if we were to run the game on infinitely many points (cf. Lemma D.4). Next, we need to estimate some number d n ∈ N which, as n → ∞, converges to the 9/10-quantile d * of the distribution of the VC dimension of the partial concept classes that are obtained by running the VCL game on infinitely many samples. We letd n := min d∈N ∃i 1 , i 2 , . . . , i 9/10• √ n ∈ [ √ n] : i 1 < i 2 < . . . < i 9/10• √ n , d F ij √ n/5 ≤ d, ∀j ∈ [9/10 √ n] ,where d(F) denotes the VC dimension of class F. Lemma D.5 shows that, for large enough n, d n = d * , with high probability, where d * ∈ N is such that with probability at least 9/10 over the random draw2 of the partial class, its VC dimension is at most d * . One technical complication we need to handle is that the concept classes we have obtained are estimated from a game on √ n many points instead of infinitely many points, so a o(1)-fraction of them do not correspond to samples from the correct distribution. To do that we use a robust version of the well-known Dvoretzky-Kiefer-Wolfowitz (DKW) inequality (cf. Theorem D.1) for estimating the CDF.Next, we use another n/5 of the query budget to obtain the labels of the first n/5 points of S 2 . We will make two distinctions regarding this stream. For the purposes of the analysis, we consider a fixed stream of infinitely many i.i.d. samples from P and we denote it by S ∞ 2 , but in the actual algorithm we use a dataset of size Θ(n) and we denote it by S n 2 . We defineV i n/5 := f ∈ F i √ n/5 : f (x) = y for the first n/5 points in S ∞ 2 ,to be the version space of F i √ n/5 defined on the first n/5 examples of S ∞ 2 . Moreover, we let V d * ,n/5 be a random version space that is sampled from the following process: we run the VCL game on an infinite stream of labeled data from P to get a pattern avoidance function y and then we define the partial concept class F in the same way as before. If the VC dimension of this class is greater than d * we discard it and restart the process. Otherwise, we let V d * ,n/5 be the version space of F on the first n/5 labeled points of S ∞ 2 . We take d * to be the 9/10-quantile of P as described before (cf. Lemma D.5). Given some k ∈ N, let p n,k := E[P k (x 1 , . . . , x k VC shattered by V d * ,n/5 )|S ∞ 2 ]where the expectation is over the draw of V d * ,n/5 , given the fixed S ∞ 2 . Let k * ∈ N be the largest number such that lim n→∞ p n,k * ̸ = 0. Notice that since, by definition, the VC dimension is bounded by d * such a number k * exists. From here on, we will only consider the version spaces V i n/5 that are obtained from some partial class with VC dimension at most d n . Let p n,k,i := P k (x 1 , . . . , x k VC shattered by V i n/5 ). Notice that for every k ≤ d n and every i ∈ [√ n] we can estimate this quantity to arbitrary precision using only unlabeled examples. We denote by p n,k,i these estimates.We now consider the first n 2 unlabeled points of the third data stream S 3 . For each such point X, letp X n,k := E[P k (x 1 , . . . , x k , X VC shattered by V d * ,n/5 )|S ∞ 2 , X]. Moreover, for each y ∈ {0, 1} let V (X,y) d * ,n/5 := {f ∈ V d * ,n/5 : f (X) = y}, p (X,y) n,k := E[P k (x 1 , . . . , x k VC shattered by V (X,y) d * ,n/5 )|S ∞ 2 , X], y ∈ {0, 1} .We define the quantities p X n,k,i , p(X,y)n,k,i in the same way for the realized version spaces. Again, by Hoeffding's bound, we can estimate these quantities to arbitrary precision using unlabeled data. Similarly as before, we denote these estimates by p X n,k,i , p(X,y) n,k,i .The idea is to make use of Lemma D.4 and show that the classes which have been obtained by a VCL game that has not converged will only affect our estimates by some o(1). This is formalized in Proposition D.6. Thus, we can usep n,k,i , p X n,k,i , p (X,y) n,k,i , in order to estimate p n,k, , p X n,k , p (X,y)n,k . We denote these estimates by p n,k, , p X n,k , p (X,y) n,k . These are the key quantities we use to infer the labels of unlabeled points. Our algorithm tries to infer the label of each unlabeled point X ∈ S 3 (cf. Figure 7 ) in the following way: ifp X n,k ≥ p n,k 2then we query the label of X, otherwise we infer the label to be arg max y∈{0,1} p (X,y) n,k . Lemma D.7 shows that the inferences are correct, when n is large enough. The main ingredient of the proof that remains to be handled is to show that the number of label queries we submit is sublinear in n. For that, it is sufficient to show that the probability that we query the label of a point is o(1). Lemma D.8 shows that when k = k * , this is indeed the case.Finally, since we do not know the true value of k * , we run the algorithm for every k ≤ d n . The active learning component of the algorithm gives us d n + 1 different labeled datasets, which we use to train d n + 1 instances of a supervised learning algorithm, such as the one from Bousquet et al. (2021) . Our analysis so far has shown that for sufficiently large n, at least one of these datasets will be correctly labeled with size ω(n). Thus, since the supervised learning algorithm has error linear in the size of its training set, at least one of these executions will give a classifier that has error o(1/n). The last step is to run a tournament among the d n + 2 different classifiers3 to choose the best one. This is handled by Lemma D.9 (Hanneke, 2012) . The main result of this section (cf. Theorem D.10), follows as a corollary of the results we have discussed. All the steps are summarized in Figure 7 .Lastly, a lower bound from Hanneke et al. (2022) completes our characterization (cf. Theorem D.11).i √ N /t , i ∈ [ √ N ],be the pattern avoidance functions from the previous step andfor every i ∈ [ √ N ] define F i √ N /5 := f : X → {0, 1, ⋆} : (f (x 1 ), . . . , f (x ℓ i √ N /5 )) ̸ = y i √ N /5 (x 1 , . . . , x ℓ i √ N /5) . (d) Run A p on S and let h k be its output. 
conclusion: 
 In this work we have provided a complete characterization of the optimal learning rates in active learning. It is an open question if it also holds when the learner knows the distribution P X .EQUATION8. Return ActiveSelect h 0 , . . . , h k , h p N , N/5, S 4 (cf. Figure 8 ). • The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.) • The assumptions made should be given (e.g., Normally distributed errors). • It should be clear whether the error bar is the standard deviation or the standard error of the mean. 
experiments compute resources: 
 Question: For each experiment, does the paper provide sufficient information on the computer resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?Answer: [NA] Justification:Guidelines:• The answer NA means that the paper does not include experiments.• The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage. • The paper should provide the amount of compute required for each of the individual experimental runs as well as estimate the total compute. • The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make it into the paper). 
code of ethics: 
 Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics https://neurips.cc/public/EthicsGuidelines?Answer: [Yes] Justification:Guidelines:• The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.• If the authors answer No, they should explain the special circumstances that require a deviation from the Code of Ethics. • The authors should make sure to preserve anonymity (e.g., if there is a special consideration due to laws or regulations in their jurisdiction). 
broader impacts: 
 Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?Answer: [NA] Justification: The work is primarily theoretical and does not have any immediate sociatal impact.Guidelines:• The answer NA means that there is no societal impact of the work performed.• If the authors answer NA or No, they should explain why their work has no societal impact or why the paper does not address societal impact. • Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.• The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is a direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster. • The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology. • If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML). 
safeguards: 
 Question: Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?Answer: [NA] Justification:Guidelines:• The answer NA means that the paper poses no such risks.• Released models that have a high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters. • Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images. • We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make a best faith effort.12. Licenses for existing assets Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?Answer: [NA] Justification:Guidelines:• The answer NA means that the paper does not use existing assets.• The authors should cite the original paper that produced the code package or dataset.• The authors should state which version of the asset is used and, if possible, include a URL. • The name of the license (e.g., CC-BY 4.0) should be included for each asset.• For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided. • If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswithcode.com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of a dataset. • For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.• If this information is not available online, the authors are encouraged to reach out to the asset's creators. 13. New Assets Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets? Answer: [NA] Justification: Guidelines:• The answer NA means that the paper does not release new assets.• Researchers should communicate the details of the dataset/code/model as part of their submissions via structured templates. This includes details about training, license, limitations, etc. • The paper should discuss whether and how consent was obtained from people whose asset is used. • We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution. • For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review. 
 
 Appendix: We recall some basic notions of measures and probabilities on Polish spaces. For a detailed treatment the reader is referred to Kechris (2012) ; Cohn (2013) . Our presentation follows Bousquet et al. (2021) .Polish Spaces. A Polish space is a separable topological space that admits a complete metric. For example, this category includes R n , any compact metric space, any separable Banach space, etc.Universally Measurable Functions. Let F be the Borel σ-field on some Polish space X and let µ be a probability measure. We denote by F µ the completion of F under µ, i.e., the collections of all subsets of X that differ from a Borel set on a set of zero measure. A set B ⊆ X is called universally measurable if B ∈ F µ for every probability measure µ. Moreover, a function f : X → Y is called universally measurable if f -1 (B) is universally measurable, for any universally measurable set B. An important property is that universally measurable sets and functions on Polish spaces are the same as Borel sets, from a probabilistic point of view.We are now ready to provide the definition of measurability of a concept class H. Definition A.1 (Measurability of H). Let X be a Polish space. We say that a concept class H ⊆ {0, 1} X , is measurable if there is a Polish space Θ and a Borel-measurable map h :X × Θ → {0, 1} so that H = {h(θ, •) : θ ∈ Θ}.We underline that Definition A.1 is very general and its only requirement is that H can be parameterized in some reasonable way.Gale-Stewart Games. We briefly discuss some basic and useful facts about Gale-Stewart games, a concept that was recently introduced to the learning theory community by Bousquet et al. (2021) . Our discussion follows Bousquet et al. (2021) ; Hanneke et al. (2022) . We refer to Bousquet et al. (2021) and references therein for a more detailed presentation. Let us fix sequences of sets X t , Y t for t ≥ 1. We consider infinite games between two players, a learner P L and an adversary P A , where in each round t ≥ 1, P A selects an element x t ∈ X t , and then P L selects an element y t ∈ Y t . The rules of the game are defined by a set W ⊆ t≥1 (X t × Y t ) of winning sequences for P L . This means that after an infinite sequence of consecutive plays x 1 , y 1 , x 2 , y 2 , . . ., we say that P L wins if (x 1 , y 1 , x 2 , y 2 , . . .) ∈ W; otherwise the winner is P A .A strategy is a rule used by each of the players to determine their next move, given the current state and the history of the game. Formally, a strategy for P A is a sequence of functions f t : s<t (X s × Y s ) → X t for t ≥ 1, so that P A plays x t = f t (x 1 , y 1 , . . . , x t-1 , y t-1 ) in round t. Similarly, a strategy for P L is a sequence of g t : s<t (X s × Y s ) × X t → Y t for t ≥ 1, so that P L plays y t = g t (x 1 , y 1 , . . . , x t-1 , y t-1 , x t ) in round t. We say that a strategy for P A is winning if playing that strategy always makes P A win the game no matter what P L plays; a winning strategy for P L is defined similarly. The main question in these infinite games is determine conditions under which one of the two players has a winning strategy in the game. We remark that when the game is finite it is not hard to easy that exactly one of the two players has such a strategy. In the context of infinite games, such a condition was introduced by Gale and Stewart (1953) : a W is finitely decidable if for every sequence of plays (x 1 , y 1 , x 2 , y 2 , . . .) ∈ W, there exists some n < ∞ so that(x 1 , y 1 , . . . , x n , y n , x ′ n+1 , y ′ n+1 , x ′ n+2 , y ′ n+2 , . . .) ∈ W for all choices of x ′ n+1 , y ′ n+1 , x ′ n+2 , y ′ n+2 , .. . In words, the condition that "W is finitely decidable" means that if P L wins the game, then she knows that after playing a finite number of rounds. Conversely, P A wins the game when P L does not win after any finite number of rounds. Such a game whose set W is finitely decidable is called a Gale-Stewart game. We use the following important result about Gale-Stewart games. Remark A.2 (Gale and Stewart (1953) ; Hodges et al. (1993) ; Kechris (2012) ). In any Gale-Stewart game exactly one between P A and P L has a winning strategy.The above result is purely existential and provides no information about the complexity of the winning strategies. Importantly, it is unclear whether winning strategies can be chosen to be measurable. The next result from Bousquet et al. (2021) addresses this concern.Theorem A.3 (Theorem B.1 from Bousquet et al. (2021) ). Let {X t } t≥1 be Polish spaces and {Y t } t≥1 be countable sets. Consider a Gale-Stewart game whose set W ⊆ t≥1 (X t × Y t ) of winning strategies for P L is finitely decidable and coanalytic. Then there is a universally measurable winning strategy.The following remark shows that we can, equivalently, let the strategy of the the learner P L and the adversary P A depend only on the choices of their opponent in the previous rounds.Remark A.4 (Bousquet et al. (2021) ). The strategy of P L is defined to be a sequence of functions y t = f t (x 1 , y 1 , . . . , x t-1 , y t-1 ) of the history of the game, where y 1 , . . . , y t-1 are defined similarly. Thus, we can equivalently let y t = f t (x 1 , . . . , x t-1 ). The same holds for the strategy of P A .Partial Concept Classes. The traditional PAC learning framework studies (mainly) total concept classes, i.e., classes of functions h : X → {0, 1} that are defined on every point x ∈ X . The caveat with total functions is that they do not provide a direct way to express data-dependent constraints. For example, if the space X is high-dimensional but the data that the leaner has to classify lie in a low-dimensional space, it is not clear how to encode this restriction through total concepts. This is very relevant to practical application of machine learning such as classification of images; the space X is the set of all possible values of the pixels of the image but most of these configurations of the pixels do not even correspond to an image of an object of interest. Alon et al. (2021) proposed and studied an extension of the PAC framework that allows one to capture such assumptions using partial concept classes, i.e., sets of functions f : X → {0, 1, ⋆}, where f (x) = ⋆ means that f is undefined at x. In the context of classification of images, when a classifier returns ⋆ it means that x does not belong to the space of valid images. Alon et al. (2021) extend a lot of notions, such as PAC learnability and the VC dimension, from the setting of total concept classes to the setting of partial concept classes (see, e.g., Definition A.6). To show how one can use partial classes, to express data-dependent constraints, we remark that Alon et al. (2021) illustrated how the class of d-dimensional linear classifiers with margin γ > 0 can be formulated as a partial class: we say that a sample (x 1 , y 1 ), . . . , (x n , y n ) ∈ R d × {0, 1} is (R, γ)-separable if all the points x 1 , . . . , x n lie in a (euclidean) ball of radius R, the 0-labeled examples and the 1-labeled examples are linearly separable, and the (euclidean) distance between the 0-labeled examples and 1-labeled examples is at least 2γ. Then, the classF R,γ = f : R d → {0, 1⋆} :(∀x 1 , . . . , x n ) ∈ supp(f ) : (x 1 , (f (x 1 )), . . . , (x n , (f (x n )) is (R, γ) -separable ,where supp(f ) is the set of all points where f (x) ̸ = ⋆, expresses the set of functions that satisfy these constraints. Remarkably, the VC dimension of F is bounded by O R 2 γ 2 (Alon et al., 2021) . Perhaps surprisingly, even though the PAC learnability of partial classes is characterized by the VC dimension (as it is the case with total classes), the ERM algorithm provably fails to learn partial classes. Thus, the algorithmic landscape is much richer and complicated compared to total classes. Moreover, there is no algorithmic way to extend a partial concept class to a total concept class without significantly increasing its VC dimension. For details, we refer to (Alon et al., 2021) .One-Inclusion Graph Algorithm. We state formally the guarantees of the one-inclusion graph algorithm (Haussler et al., 1994) .Theorem A.5 (One-Inclusion Graph Algorithm (Haussler et al., 1994) ). For any (total) concept class H whose VC dimension is bounded by d < ∞, there is an algorithm A : (X × {0, 1}) * × X → {0, 1} such that for any n ∈ N and any sequence {(x 1 , y 1 ), . . . , (x n , y n )} ∈ (X ×{0, 1}) n that is realizable w.r.t. H,1 n! σ∈Sym(n) 1{A(x σ(1) , y σ(1) , . . . , x σ(n-1) , y σ(n-1) , x σ(n) ) ̸ = y σ(n) } ≤ d n ,where Sym(n) denotes the symmetric group of permutations of {1, . . . , n}.In particular, Theorem A.5 implies immediately that if (x 1 , y 1 ), . . . , (x n , y n ) are i.i.d. from P then the classifier hn (•) := A(x 1 , y 1 , . . . , x n , y n , •) has E[er( hn )] ≤ d n+1 . We remark that Alon et al. (2021) showed that this result also holds for partial concept classes.Definition A.6 (VC Dimension of Partial Concept Classes (Alon et al., 2021) ). For a partial concept class F ⊆ {0, 1, ⋆} X , the VC dimension of F is defined to be the largest number d ∈ N such that ∃(x 1 , . . . , x d ) ∈ X d such that {(f (x 1 ), . . . , f (x d )) : f ∈ F } = {0, 1} d . Such a sequence (x 1 , . . . , x d ) is said to be shattered by F. If there is no bound on d we say that the VC dimension is ∞.The following definition of the star number is an adaptation of the definition in (Hanneke and Yang, 2015) .Definition A.7 (Star Number of Partial Concept Classes). For a partial concept class F ⊆ {0, 1, ⋆} X , the star number of F is defined to be the largest number s ∈ N such that ∃(x 1 , . . . , x s ) ∈ X s such that ∃f 0 ∈ F and ∀i ∈[s], ∃f i ∈ F : f i (x i ) = 1 -f 0 (x i ), f i (x j ) = f 0 (x j ) ̸ = ⋆, ∀j ∈ [s] \ {i}.If there is no bound on s we say that the star number is ∞.Definition A.8 (Littlestone Tree (Bousquet et al., 2021) ). A Littlestone tree for H ⊆ {0, 1} X is a complete binary tree of depth d ≤ ∞ whose internal nodes are labeled by X , and whose two edges connecting a node to its children are labeled by {0, 1}, such that every path of length at most d emanating from the root is consistent with a concept h ∈ H. Formally, a Littlestone tree is a collection0≤ℓ<d x ⃗ u : ⃗ u ∈ {0, 1} ℓ = {x ∅ } ∪ {x 0 , x 1 } ∪ {x 00 , x 01 , x 10 , x 11 } ∪ . . .such that for every path ⃗ y ∈ {0, 1} d and n < d, there exists h ∈ H so that h(x ⃗ y ≤ℓ ) = y ℓ+1 for 0 ≤ ℓ ≤ n. We say that H has an infinite Littlestone tree if there is a Littlestone tree for H of depth d = ∞. Definition A.9 (Star Tree). A Star tree for H ⊆ {0, 1} X of consists of a collection 0≤ℓ<d(x ⃗ u , z ⃗ u ) ∈ X ℓ+1 , {0, 1} ℓ+1 : ⃗ u ∈ {0} × {0, 1} × . . . × {0, 1, . . . , ℓ}such that for every level n < d, and ⃗ y ∈ {0} × {0, 1} × ... × {0, 1, . . . , n -1}, there exists some h ∈ H such that h(x i ⃗ y ≤k ) = f (z i ⃗ y ≤k , y k+1 ) for all 0 ≤ i ≤ k and 0 ≤ k ≤ n, where we denoteEQUATIONWe say that H has an infinite star tree if it has a star tree of depth d = ∞.EQUATION)). A Vapnik-Chervonenkis-Littlestone (VCL) tree for H ⊆ {0, 1} X of depth d ≤ ∞ consists of a collection 0≤ℓ<d {x ⃗ u ∈ X ℓ+1 , ⃗ u ∈ {0, 1} × {0, 1} 2 × ... × {0, 1} ℓ }such that for every level n < d, and ⃗ y ∈ {0, 1} × {0, 1} 2 × {0, 1} n+1 , there exists some h ∈ H such that h(x i ⃗ y ≤k ) = y i k+1 for all 0 ≤ i ≤ k and 0 ≤ k ≤ n, where we denote ⃗ y ≤k = (y 0 1 , (y 0 2 , y 1 2 ), . . . , (y 0 k , . . . , y k-1 k)), x ⃗ y ≤k = (x 0 ⃗ y ≤k , . . . , x k ⃗ y ≤k ).We say that H has an infinite VCL tree if it has a VCL tree of depth d = ∞.Figure 1 : Arbitrarily Fast Rates Algorithm (Hanneke et al., 2022) . Arbitrarily Fast Rates (Hanneke et al., 2022) : Input is a label budget N and a rate function R(n).1. m 1 ← ⌈2 ln(1/R(n))⌉. 2. m 2 ← ln(m12 2⌊ √ m 1 ⌋+2 /R(n)) R(n).3. Create sets S 1 = x 1 , . . . , x m1 , S 2 = x m1+1 , . . . , x m2 . 4. Split S 1 into ⌊ √ m 1 ⌋ batches of size ⌊ √ m 1 ⌋ and consider all the labeled prefixes of the batches in lexicographical order: b i,j denotes the i-th batch with the labeled prefix j, 1 ≤ j ≤ 2 ⌊ √ m1⌋+1 . 5. Let A 0 (•; b i,j ) be the output of the ordinal SOA trained on b i,j and denote g i,j (x) = A 0 (x; b i,j ).See (Bousquet et al., 2021) . 6. Evaluate the classifiers g i,j (•) on the points in S 2 . 7. Define a set F of equivalence classes: g i,j and g i ′ ,j ′ are in the same class iff they classify S 2 the same. 8. For each F ∈ F, definerank(F ) = min r : ∃ 1 ≤ i 1 < i 2 . . . < i ⌊ √ m1⌋/3 ≤ ⌊ √ m 1 ⌋, k 1 , . . . , k ⌊ √ m1⌋/3 ∈ [2 r+1 ] such that g ij ,kj ∈ F, 1 ≤ j ≤ ⌊ √ m 1 ⌋/3 ,or rank(F ) = ∞ if no such r exists. 9. Enumerate F = {F 1 , F 2 , . . .} so that rank(F ℓ ) is non-decreasing in ℓ, and pick any f ℓ ∈ F ℓ for each ℓ. 10. For each distinct i, j ≤ ⌊ √ n⌋ query the label of any point in S 2 on which f i , f j disagree. 11. If there is some f l which is correct on all the points we queried, return f l. 12. Otherwise, return any f ℓ . Before we prove our main result of this section, we present an omitted proof from the main body.Proof. Assume that H has an infinite star tree. Then, the adversary can start from the root of the tree and play ( ⃗ ξ 1 , ⃗ ζ 1 ) = (⃗ x ∅ , ⃗ z ∅ ) and for every strategy {η τ } τ ≥1 of the learner, P A can follow the path ⃗ y ≤τ = (η 1 , η 2 , . . . , η τ ) and play (⃗ x ⃗ y ≤τ , ⃗ z ⃗ y ≤τ ) in round τ + 1. Since the tree is infinite, there is noτ * ∈ N such that H ⃗ ξ1, ⃗ ζ1η1,..., ⃗ ξ τ * , ⃗ ζ τ * ,η τ * = ∅.For the other direction, assume that the adversary has a winning strategy. Then, we can define the treeT = 0≤ℓ<∞ (⃗ x ⃗ η , ⃗ z ⃗ η ) ∈ X ℓ+1 , {0, 1} ℓ+1 : ⃗ η i ∈ {0, 1, . . . , i -1}, 1 ≤ i ≤ ℓwhere (⃗ x η1,...,ητ-1 , ⃗ z η1,...,ητ-1 ) = ( ⃗ ξ τ (η 1 , . . . , η τ -1 ), ⃗ ζ τ (η 1 , . . . , η τ -1 )). The tree T is infinite by the definition of the winning strategy in G for P A . To prove the universal measurability of the winning strategy of P L , using Lemma A.3 it suffices to show that the set of winning strategies W of the learner is coanalytic. To this end, we consider its complementW c = ( ⃗ ξ, ⃗ ζ, ⃗ η) ∈ ∞ t=1 X t × {0, 1} t × {0, . . . , t -1} : H ⃗ ξ1, ⃗ ζ1,η1,..., ⃗ ξt, ⃗ ζt,ηt ̸ = ∅ = ∞ t=1 θ∈Θ t s=1 ( ⃗ ξ, ⃗ ζ, ⃗ η) : h(θ, ⃗ ξ i s ) = ⃗ ζ i s , if η s ̸ = i h(θ, ⃗ ξ i s ) = 1 -⃗ ζ i s , if η s = i , 0 ≤ i < s Notice that the set h(θ, ⃗ ξ i s ) = ⃗ ζ i s , if η s ̸ = i h(θ, ⃗ ξ i s ) = 1 -⃗ ζ i s , if η s = i, 0 ≤ i < s is Borel by the measurability assumption. Also, the intersection in the above expression are countable and the union is a projection of a Borel set. Hence, W c is analytic, so we have proven the claim.We now explain the approach to actively learn a partial concept class with finite star number at a uniform exponential rate. We first state a result from Hanneke and Yang (2015) about active learning of total concept classes with finite star dimension that we utilize in our construction.Theorem C.1 (Hanneke and Yang (2015) ). There exists an active learning algorithm A for a total concept class H which given a label budget n = c • s log(1/ε), where c is an absolute numerical constant and s is the star number of the class, and access to samples from a realizable distribution P * returns a classifier ĥn such that, with probability arbitrarily close to one, P * [ ĥn (x) ̸ = y] ≤ ε.We underline that the success probability of this algorithm does not depend on the query budget.Our algorithm for partial classes can be found in Figure 2 . We now prove the main result in this setting that we described in Theorem 3.2.Proof of Theorem 3.2. Let F be a partial concept class whose star number s is finite. Notice that since d ≤ s, its VC dimension is also finite. Let S = (X 1 , . . . , X m ) be m samples of the stream that A has access to, where m is some value to be determined. We also letH = {h : S → {0, 1} : ∃f ∈ F s.t. h(X i ) = f (X i ), ∀i ∈ [m]} .Now notice that H is, by definition, a total concept class and its star number, VC dimension is also at most s, d, respectively. Moreover, since P * is realizable with respect to F we have that, except for a measure-zero event, H ̸ = ∅. This can be seen as follows. Since the distribution P * is realizable, there exists a sequence of functions f k ∈ F so thatP * [f k (x) ̸ = y] < 1 2 k . Let us fix m ≥ 1. We have that ∞ k=1 Pr[∃s ≤ m : f k (x s ) ̸ = y s ] ≤ m ∞ k=1 P * [f k (x) ̸ = y] < ∞ ,where the first inequality is due to union bound. By Borel-Cantelli, with probability one, there exists for every m ≥ 1 a hypothesis f ∈ F so that f (x s ) = y s for all s ≤ m. For the rest of the proof, we condition on this probability one event E 0 . We definite P * to be the uniform distribution on the (labeled) sample. Our previous discussion shows that P * is realizable with respect to H. Now let us run algorithm A ′ from Theorem C.1 with ε = 1/(2m) and success probability 1/(2m). Let E 1 be the event that the error of the output h of A ′ is at most 1/(2m). We condition on this event for the rest of the proof. Notice that in this case, the algorithm will have figured out the correct label of every X i , 1 ≤ i ≤ m. Indeed, if for some i ∈ [m] we have that h(X i ) ̸ = Y i , then er( h) ≥ 1/m. Notice that, by the definition of H, we have that s( H) ≤ s(F). Moreover, the number of labels that A ′ requests is at most c • s log(2m), where c is some absolute numerical constant.Since we have m labeled samples, we can use them as input to the one-inclusion graph algorithm (see Theorem A.5). This algorithm guarantees thatE[er( ĥm )|E 0 , E 1 ] ≤ d(F) m + 1 .Thus, we get thatE[er( ĥm )] ≤ d(F) m + 1 + 1 m < d(F) + 1 m .It follows immediately from the definitions that d(F) ≤ s(F). The result follows by picking m = e c•n/s 2 .Exponential Rates for Partial Classes1. m ← e c•n/s2 , where c is the constant in Theorem C.1. 2. Take a sample of unlabeled data S = {X 1 , . . . , X m }.3. Define H to be the total class of the concepts in F that are not undefined on S, i.e.,H = {h : S → {0, 1} : ∃f ∈ F s.t. h(X i ) = f (X i ), ∀i ∈ [m]} .4. Let P be the uniform distribution over the sample {(X 1 , Y 1 ), . . . , (X m , Y m )}, whereY i is the true label of X i , i ∈ [m].5. Use the active learning algorithm from Hanneke and Yang (2015) on the distribution P (see Theorem C.1). 6. The aforementioned algorithm can find the labels of these m points after making at most O(s( H) log m) queries, where s( H) is the star number of H. 7. Use these m labeled points as input to the one-inclusion graph algorithm (Haussler et al., 1994) and get ĥ (see Theorem A.5).8. This algorithm guarantees linear error in m, i.e., E[er( ĥ)] ≤ d(F ) m+1 , where d(F) is the VC dimension of F. 9. Return ĥm . Star Tree Gale-Stewart Game with Finite Sequence and Estimation: Input is a labeled sequence {(x 1 , y 1 ), . . . , (x N , y N )} 1. Use ⌊N/2⌋ of the data to estimate tN (cf. Lemma C.5.). Let N = ⌊N/2 tN ⌋. 2. Use the remaining ⌊N/2⌋ of the data to run the star tree game (cf. Figure 5 ) and obtaing i tN , 1 ≤ i ≤ N . 3. Estimate for 1 ≤ i ≤ N F i = f : X → {0, 1, * } : ∀(x 1 , . . . , x τ tN ) ∈ X τ tN , x 1 , f (x 1 ), . . . , x τ tN , f (x τ tN ) / ∈ image g i tN .4. Estimate the 9/16-majority classF N m = f : X → {0, 1, ⋆} : ∀ℓ ∈ N, ∀(x 1 , . . . , x ℓ ) ∈ X ℓ , ∃ at least (9/16) N classes F j , 1 ≤ j ≤ N s.t.∃ f ∈ F j with ( f (x 1 ), . . . , f (x ℓ )) = (f (x 1 ), . . . , f (x ℓ )) .5. Return G ℓ : (X × {0, 1}) ℓ → {0, 1} ℓ∈N where G ℓ (x 1 , y 1 , . . . , x ℓ , y ℓ ) = 1 ∃f ∈ F N m : (f (x 1 ), . . . , f (x ℓ )) = (y 1 , . . . , y ℓ ) . Exponential Rates: Input is an unlabeled data stream {x 1 , x 2 , . . . , } and query budget n.1. Set number of unlabeled examples u n = ⌊n/2⌋ + e c•n , where c is the absolute constant in Theorem C.1. 2. Use ⌊n/2⌋ label queries to get the labels of the first ⌊n/2⌋ unlabeled points. 3. Call the Gale-Stewart subroutine (Figure 3 ) with points (x 1 , y 1 ), . . . , x ⌊n/2⌋ , y ⌊n/2⌋ . 4. Create the partial concept class 2 on the partial class F G with budget ⌊n/2⌋ and return its output.F G = f : X → {0, 1, ⋆} : ∀ℓ ∈ N, ∀(x 1 , . . . , x ℓ ) ∈ X ℓ , G ℓ (x 1 , f (x 1 ), . . . , x ℓ , f (x ℓ )) = 1 .To build some intuition, we first show how to use the game between the learner and the adversary discussed in Section 3 to get an asymptotic result. We call this the online setting. Assume that there is an infinite labeled sequence S = (x 1 , y 1 , x 2 , y 2 , . . .) that is consistent with H, i.e., for any t < ∞, there exists h ∈ H : h(x t ) = y t . We use S to simulate the game G between P A and P L which gives rise to a partial concept class F with finite star number. This approach is shown in Figure 5 .1. Let g 1 : X × {0, 1} → {0, 1} be the function that corresponds to the strategy of P L in the first round of G. 2. Initialize τ 0 ← 1. 3. Let g 1 (x, y) = (x, 1 -y) # In the first round the learner just flips the label. 4. For every t ≥ 1:• If (x t-τt-1+1 , y t-τt-1+1 , . . . , x t , y t ) ∈ image( g τt-1 ), witnessed by ⃗ c ′ τt-1 : # proceed to the next round in G.-τ t ← τ t-1 + 1. -g τt (•, •) := η τt (⃗ c ′ 1 , . . . , ⃗ c ′ τt-1 •, •), where η τt (⃗ c ′ 1 , . . . , ⃗ c ′ τt-1 •, •)is the strategy of P L in round τ t of G, given its history.g τt (x 0 , y 0 , . . . , x τt-1 , y τt-1 ) := (x 0 , y 0 , . . . , x τt-1 , y τt-1 ) : We first show as t → ∞ the game converges, i.e., there are no more realizable τ t * -tuples (x 1 , y 1 , . . . , x τ t * , y τ t * ) that belong to the image of g τ t * , for some finite number t * . To simplify the notation, we define g t * = g τ t * . Recall that this function is defined in Figure 5 .y i = y i , if g τt (x 0 , y 0 , . . . , x τt-1 , y τt-1 ) ̸ = i y i = 1 -y i , if g τt (x 0 , y 0 , . . . , x τt-1 , y τt-1 ) = i , 0 ≤ i < τ t • Else: τ t ← τ t-1 .Lemma C.2. If H does not have an infinite star tree, for any sequence x 1 , y 1 , x 2 , y 2 , . . . , that is consistent with H, there exists some finite number t * ∈ N, such that for all t > t * (x t-τt-1+1 , y t-τt-1+1 . . . , x t , . . . , y t ) / ∈ image( g t-1 ), τ t = τ t-1 , g t = g t-1 .Proof. Suppose that (x t-τt-1+1 , . . . , x t , y t-τt-1+1 , . . . , y t ) ∈ image( g t-1 ) happens an infinite sequence of times t 1 , t 2 , . . . . Since η τt is a winning strategy for the learner in G, we have that for some finite t * it holds that H ⃗ ξ1, ⃗ ζ1,η1,..., ⃗ ξ t * , ⃗ ζ t * ,η t * = ∅ (see Equation ( 1)), where ⃗ ξ i , ⃗ ζ i , η i are defined in Figure 5 . Hence, we have arrived in a contradiction.Similarly as in (Bousquet et al., 2021) , we remark the following about the measurability of the functions. Remark C.3 (Adapted from Bousquet et al. (2021) ). The strategy τ t depends in a universally measurable way on x ≤t , y ≤t . Moreover, the functions g t are universally measurable with respect to x ≤t , y ≤t and the arguments of their input. To be more precise, for all t ≥ 0, there exist the following universally measurable functionsT t : (X × {0, 1}) t → {1, . . . , t+1}, G t : (X × {0, 1}) t × s<t (X × {0, 1}) s → (X × {0, 1}) t ,so that τ t = T t (x 1 , y 1 , . . . , x t , y t ), g t (w 1 , z 1 , . . . , w τt , z τt ) = G t (x 1 , y 1 , . . . , x t , y t , w 1 , z 1 , . . . , w τt , z τt ) .In this section we show how to utilize our results in the online setting to design an algorithm that achieves exponential rates in the statistical setting. Our approach is similar in spirit as in Bousquet et al. (2021) ; Hanneke et al. (2022) . In particular, we adapt the approach of Hanneke et al. (2022) from the VCL game to the star tree game. The key steps are outlined in Figure 3 .Let P be a realizable distribution with respect to H and X 1 , Y 1 , X 2 , Y 2 , . . . , be an i.i.d. sequence from P. For the remaining of the section, we assume that H does not have an infinite star tree. Let us now set up the notation that we use in our proof. We denoteτ t := T t (X 1 , Y 1 , . . . , X t , Y t ), g t (w 1 , z 1 , . . . , w tτ , z tτ ) := G t (X 1 , . . . , X t , Y 1 , . . . , Y t , w 1 , z 1 , . . . , w tτ , z tτ ) ,where these functions are defined in Remark C.3. For any integer k ≥ 1, we define a "flipping" function g k : (X × {0, 1}) k → (X × {0, 1}) k to be a function that flips one of the labels of its input from 0 to 1 or vice versa. We also define the probability of error of this function as follows:per( g k ) = per k ( g k ) = P k ((x 1 , y 1 , . . . , x k , y k ) : (x 1 , y 1 , . . . , x k , y k ) ∈ image( g k )), i.e., the probability that a k-tuple drawn i.i.d. from P belongs to the image of g k . When there is no confusion about the domain of g k we will omit its dependence on k. Our first observation is that we get an algorithm that is consistent in the statistical setting. Our proof is an adaptation of Lemma 5.7 in Bousquet et al. (2021) . Lemma C.4. It holds that P[per( g t ) > 0] → 0 as t → ∞.Proof. We know that P is realizable so we can pick a sequence of hypotheses h k ∈ H such that er(h k ) ≤ 2 -k , k ∈ N. Taking a union bound over all t ≥ 1, we have thatk∈N P[h k (X s ) ̸ = Y s , for some s ≤ s] ≤ t k∈N er(h k ) < ∞.Thus, by the Borel-Cantelli lemma, it holds that h(X s ) = Y s , ∀s ≤ t for some h ∈ H (with probability one). LetT = sup s ≥ 1 : (X s-τs-1+1 , Y s-τs-1+1 , . . . , X s , Y s ) ∈ image ( g s-1) . Then, we know from Lemma C.2 that T is finite with probability one. Recall the law of large numbers for m-dependent sequences: if Z 1 , Z 2 . . . , is an i.i.d. sequence of random variables, thenlim n→∞ 1 n n i=1 f (Z i+1 , . . . , Z i+m ) = 1 m m i=1 lim n→∞ m n ⌊n/m⌋ j=0 f (Z mj+1+i , . . . , Z m(j+1)+i )+o(1) = E[f (Z 1 , . . . , Z m )] .Thus, we have thatP[per τt ( g t ) = 0] = P lim S→∞ 1 S t+S s=t+11 (Xs,Ys,...,Xs+τ t -1,Ys+τ t -1 )∈image( gt) = 0≥ P lim S→∞ 1 S t+S s=t+1 1 (Xs,Ys,...,Xs+τ t -1,Ys+τ t -1 )∈image( gt) = 0, T ≤ t = P[T ≤ t].We know that T is finite with probability one, so we have that P[per τt ( g t ) > 0] ≤ P[T > t] → 0, as t → ∞.Lemma C.4 guarantees that for some t * ∈ N, the Gale-Stewart game played on a set of t * points will have converged with probability at least 7/8, i.e., Pr [per( g t * ) > 0] ≤ 1/8 . This number t ⋆ depends on the distribution and is unknown to the learner. We first show how the learner can estimate a similar tn from the data. Our approach is an adaptation of Lemma 5.10 in Bousquet et al. (2021) , but we present the proof for completeness. Lemma C.5 (Adaptation of Lemma 5.10 in (Bousquet et al., 2021) ). For any N ∈ N, there exists a universally measurable tN = tN (X 1 , Y 1 , ..., X ⌊N/2⌋ , Y ⌊N/2⌋ ) whose definition does not depend on P so that the following holds. Set the critical time t * ∈ N be such thatPr [per( g t * ) > 0] ≤ 1/8 ,where the probability is over the training set of the algorithm. There exist C, c > 0 that depend on P, t ⋆ but not N so thatPr[ tN ∈ T ⋆ ] ≥ 1 -Ce -cN ,where the probability is over the training of the estimator tN and T * is the setT * = {1 ≤ t ≤ t ⋆ : Pr [per( g t ) > 0] ≤ 3/8} .Proof. We split this labeled set into two parts. The idea is to use the first one to run the Gale-Stewart game and the other one to estimate whether it has converged or not. For each1 ≤ t ≤ ⌊ N 4 ⌋ and 1 ≤ i ≤ ⌊ N 4t ⌋, we let τ i t := T t (X (i-1)t+1 , Y (i-1)t+1 , . . . , X it , Y it ) g i t (w 1 , z 1 , . . . , w τ i t , z τ i t ) := G t (X (i-1)t+1 , Y (i-1)t+1 , . . . , X it , Y it , w 1 , z 1 , . . . , w τ i t , z τ i t ). be the estimated quantities when we run Figure 5 on the i-th batch of the data. Next, for each t we estimate Pr[per( g t ) > 0] by the fraction of the g i t for which there is a tuple on the second quarter of the data that belongs to the image of g i t .For every fixed t, the data that the functions g i t i≤⌊N/2t⌋ are trained on are independent of each other and of the second half of the training set. This means that we can view every g i t i≤⌊N/2t⌋ as an independent draw of the distribution of g t . To estimate the error of the algorithm we use the second quarter of the training set. We let êt = 1 ⌊N/4t⌋ .êt ≤ e t = 1 ⌊N/4t⌋ ⌊N/4t⌋ i=1 1 {per( gt)>0} , with probability one. We define tN = inf{t ≤ ⌊N/4⌋ : êt < 1/4} , where we assume that inf ∅ = ∞.We now want to bound the probability that tN > t ⋆ . Using Hoeffding's inequality we get thatPr tN > t ⋆ ≤ Pr êt ⋆ ≥ 1 4 ≤ Pr e t ⋆ ≥ 1 4 = Pr e t ⋆ - 1 8 ≥ 1 8 = Pr e t ⋆ -E[et ⋆ ] ≥ 1 8 ≤ e -⌊N/4t ⋆ ⌋/32 .This implies that tN ≤ t ⋆ except for an event with exponentially small probability. Moreover, for all 1 ≤ t ≤ t ⋆ that Pr [per( g t ) > 0] > 3 8 , there is some ε > 0 such that Pr [per( g t ) > ε] > 1 4 + 1 16 (this holds by continuity). Now fix some 1 ≤ t ≤ t ⋆ such that Pr [per( g t ) > 0] > 3 8 (if it exists). Then, using Hoeffding's inequality again we get thatPr   1 ⌊N/4t⌋ ⌊N/4t⌋ i=1 1 {per( g i t )>ε} < 1 4   ≤ e -⌊N/4t ⋆ ⌋/128 .Whenever g is a function such that per(g) > ε, thenPr [{∃s : ⌊N/4⌋ + 1 ≤ s ≤ ⌊N/2⌋ -τ, (X s+1 , Y s+1 , . . . , X s+τ , Y s+τ ) ∈ image(g)}] ≥ 1-(1 -ε) ⌊(N -4)/4τ ⌋ ,since there are ⌊(N -4)/4τ ⌋ disjoint intervals of length τ . As we mentioned before, { g i t } i≤⌊N/4t⌋ are independent of (X s , Y s ) s>⌊n/4⌋ . Thus, applying a union bound we get that the probability that all g i t that have per τ i t ( g i t ) > ε make at least one error on the second half of the training set isPr 1 per τ i t ( g i t )>ε ≤ 1 ∃s:⌊N/4⌋+1≤s≤⌊N/2⌋-τ i t ,(Xs+1,Ys+1,...,X s+τ i t ,Y s+τ i t )∈image( g i t ) ≥ 1 - N 4t (1 -ε) ⌊(N -4)/4t * ⌋ ,where the last inequality holds since τ i t ≤ t * . Thus, we get thatPr[ tN = t] ≤ Pr êt < 1 4 ≤ N 4 (1 -ε) ⌊(N -4)/4t * ⌋ + e -⌊ N 4t ⋆ ⌋/128 .Using the previous estimates and applying a union bound, we get thatPr[ tN / ∈ T ⋆ ] ≤ e -⌊N/4t ⋆ ⌋/32 + t ⋆ N 4 (1 -ε) ⌊(N -4)/4t * ⌋ + t ⋆ e -⌊N/4t ⋆ ⌋/128 ≤ Ce -cn ,for some constants C, c > 0.Essentially, Lemma C.5 tells us that we can estimate a batch size tn , using only information from the data, so that, with probability 1 -Ce -cn , the star tree game will have converged when we run it on t labeled points. Following the approach of Hanneke et al. (2022) , the idea is to run the game multiple times, then create the partial concept classes that are induced by each execution, and, finally, aggregate them into a majority class (see Figure 3 ). We show that if most of the games have converged, then the majority class has bounded star number. This is made formal in Lemma C.6. We remark that Hanneke et al. (2022) showed a similar result regarding the VC dimension of the majority class.Lemma C.6. The majority class F N m defined in Figure 3 has star number that is bounded by some distribution-dependent constant ŝ, with probability at least 1 -e -c N , for some absolute constant c > 0.Proof. We know that there exists some s * such that, with probability at least 9/10, the star of any partial concept class F i is at most s * . We let X i = 1 {star number of Fi > s * } . Notice the all the X i 's are i.i.d. Bernoulli random variables with p ≤ 1/10, since the data that induce the classes F i are i.i.d.. Thus, we can use Hoeffding's inequality to bound the probability that more than 2/10 of them have star number greater than s * as followsPr   N i=1 X i ≥ (2/10) N   = Pr   N i=1 X i -(1/10) N ≥ (15/72) N   ≤ e -N /50 .We let E 1 be the complement of the event above and we condition on it for the rest of the proof. So, we know that at least 8/10 N of the partial concept classes F i have star number bounded by s * . We will bound the size ℓ of the star set of F N m . For any star sequenceS = (x 1 , y 1 , . . . , x ℓ , y ℓ ) ∈ (X ×{0, 1}) ℓ of F N m it holds that 1 ℓ ℓ j=1 1    1 N N i=1 1 {∃f ∈ F i : f (x j ) = 1 -y j , f (x p ) = y p , ∀p ∈ [ℓ] \ {j}} > 9/16    = 1 .Using Markov's inequality, we get that1 ℓ ℓ j=1 1 N N i=1 1 {∃f ∈ F i : f (x j ) = 1 -y j , f (x p ) = y p , ∀p ∈ [ℓ] \ {j}} > 9 16 .Swapping the summation gives us1 N N i=1 1 ℓ ℓ j=1 1 {∃f ∈ F i : f (x j ) = 1 -y j , f (x p ) = y p , ∀p ∈ [ℓ] \ {j}} > 9 16 ⇐⇒ 1 N N i=1 1 ℓ ℓ j=1 1 {∄f ∈ F i : f (x j ) = 1 -y j , f (x p ) = y p , ∀p ∈ [ℓ] \ {j}} ≤ 7 16 .Using Markov's inequality again, we get that1 N N i=1 1    1 ℓ ℓ j=1 1 {∄f ∈ F i : f (x j ) = 1 -y j , f (x p ) = y p , ∀p ∈ [ℓ] \ {j}} > 9/16    ≤ 16 9 • 1 N N i=1 1 ℓ ℓ j=1 1 {∄f ∈ F i : f (x j ) = 1 -y j , f (x p ) = y p , ∀p ∈ [ℓ] \ {j}} .This implies that1 N N i=1 1    1 ℓ ℓ j=1 1 {∄f ∈ F i : f (x j ) = 1 -y j , f (x p ) = y p , ∀p ∈ [ℓ] \ {j}} > 9/16    < 7/9 ⇐⇒ 1 N N i=1 1    1 ℓ ℓ j=1 1 {∃f ∈ F i : f (x j ) = 1 -y j , f (x p ) = y p , ∀p ∈ [ℓ] \ {j}} ≥ 7/16    ≥ 2/9 .Thus, we have shown that at least 2/9 of the partial concept classes witness at least 7/16 of the star patterns. By the definition of the star number, this means that all these classes have star number at least 7/16 • m -1. This is because we can drop all the points from S that correspond to star patterns that the class does not realize and the remaining set of labeled points is a star set. Since at least one these classes' star number is at most s * we have that 7/16 • m -1 ≤ s * , which means that m ≤ 16/7(s * + 1). Thus, we have shown that the star number of F N m is at most 16/7(s * + 1) = ŝ, with probability at least 1 -e -c N .Similarly as in Hanneke et al. (2022) , we define a sequence of universally measurable functionsG ℓ : (X × {0, 1}) ℓ → {0, 1} ℓ∈N where G ℓ (x 1 , y 1 , . . . , x ℓ , y ℓ ) = 1 ∃f ∈ F N m : (f (x 1 ), . . . , f (x ℓ )) = (y 1 , . . . , y ℓ ) .An equivalent interpretation of the previous lemma is that the star number of the partial class on which {G ℓ } ℓ∈N returns 1 has a distribution-dependent bound, with high probability. Lemma C.7 is an important component in the derivation of our result and it shows that {G ℓ } ℓ∈N return 1 on all finite subsets of the correctly labeled data sequence, with high probability. This result follows similarly as Lemma 7 in Hanneke et al. (2022) .Lemma C.7. The {G ℓ } ℓ∈N as defined above are universally measurable functions, and with probability at least 1 -Ce -cN , C, c > 0, the following hold:• The star number of the classF G = f : X → {0, 1, ⋆} : ∀ℓ ∈ N, ∀(x 1 , . . . , x ℓ ) ∈ X ℓ : G ℓ (x 1 , f (x 1 ), . . . , x ℓ , f (x ℓ )) = 1has a finite distribution-dependent upper bound ŝ.• ∀ℓ ∈ N, for (x 1 , y 1 , . . . , x ℓ , y ℓ ) ∼ P ℓ , G ℓ (x 1 , y 1 , . . . , x ℓ , y ℓ ) = 1 with conditional probability one (given G ℓ ).Proof. We condition on the event E 0 described in Lemma C.6. Notice that, by definition, a labeled sequence S = (x 1 , y 1 . . . , x ℓ , y ℓ ) ∈ (X × {0, 1}) ℓ is a star set of the class F G if and only if S is a star set of F N m . Hence, the bound on the star number follows immediately from Lemma C.6. We also condition on the event E 1 described in Lemma C.5. We now bound the probability that at least (13/32) N of the functions g i tN have per g i tN > 0. For any t ∈ T * , using Hoeffding's inequality we get thatPr   1 N N i=1 1 per g i tN > 0 > 13 32   = Pr   1 N N i=1 1 per g i tN > 0 - 3 8 > 1 32   ≤ exp -N /512 ,Since we know that tn ≤ t * , taking a union bound over all 1 ≤ t ≤ t * we get thatPr   1 N N i=1 1 per g i tN > 0 > 13 32 , tn ∈ T *   ≤ t∈T * Pr   1 N N i=1 1 per g i tN > 0 > 13 32   ≤ t * exp -N /512 .Thus, except for an event with exponentially small probability, at least 19/32 of the functions g i tN have per g i tN , with probability one. Notice that, by definition, if the partial class F i that corresponds to such a function cannot produce a labeling ⃗ y ℓ ∈ {0, 1} ℓ of some tuple ⃗ x ℓ ∈ X ℓ where ⃗ x ℓ ∼ P ℓ X , we can infer that this ⃗ y ℓ is not the correct labeling, and this inference will be valid with probability one over the draw of ⃗ x ℓ . Thus, with probability one, if the 9/16-majority cannot produce some labeling we have that at least one such partial class F j that corresponds to a correct g j tN cannot produce this labeling, so it is not the correct one. As a result, with probability one, if F N m cannot produce ⃗ y ℓ for ⃗ x ℓ we know that this is not the correct labeling. The measurability of {G ℓ } ℓ∈N follows by the measurability of all the g i tN i∈N . The proof of the lemma follows by noticing that the probability of all the events we have conditioned on can be bounded by 1 -C ′ e -c ′ N and that N = ⌊N/2 tN ⌋ ≥ ⌊N/2t * ⌋.We are now ready to prove the result about active learning at exponential universal rates. Our approach is summarized in Figure 4 .Theorem C.8. Assume that H ⊆ {0, 1} X does not have an infinite star tree. Then, H admits an active learning algorithm that achieves exponential rates.Proof. First, notice that the Gale-Stewart subroutine Figure 3 uses ⌊n/2⌋ points and the exponential rates algorithm for partial classes uses at most ⌊e c•n ⌋ points. This is because we define a uniform distribution over these points during its execution. To prove the learning rate guarantees, we first condition on the event E 0 described in Lemma C.7. Then, we have some partial concept class F G whose star number is finite by some distribution-dependent number ŝ and has the property that ∀ℓ ∈ N, for (x 1 , y 1 , . . . , x ℓ , y ℓ ) ∼ P ℓ , f (x 1 ) = y 1 , . . . , f (x ℓ ) = y ℓ for some f ∈ F G . Thus, the conditions of Theorem C.1 are satisfied and the conditional error rate of the output of our algorithm is E[er( ĥn )|E 0 ] ≤ c 1 de -c2n/ŝ . Since E 0 happens with probability at least 1 -Ce -cn , we see that the unconditional error of the output is E[er( ĥn )] ≤ c 1 de -C2n/ŝ + Ce -cn ≤ Ce -cn , for some distribution-dependent constants c, C > 0.Theorem C.9. Assume that H ⊆ {0, 1} X has an infinite star tree and let R(n) be a rate function withR(n) = o(1/n). Then, H requires rate R(n). Proof. Let ⃗ t = 0≤ℓ<∞ (x ⃗ u , z ⃗ u ) ∈ X ℓ+1 , {0, 1} ℓ+1 : ⃗ u ∈ {0} × {0, 1} × . . . × {0, 1, . . . , ℓ} ,be an infinite star tree. We also fix the learning algorithm ĥn . Recall that {u(n)} n∈N denotes the number of unlabeled samples that ĥn uses.We first pick a path on the tree uniformly at random. To be more precise, let ⃗ y = (y 1 , y 2 , . . .) be a sequence of independent random variables where y i is uniformly distributed in {0, . . . , i -1}. The idea is that ⃗ y specifies a random path on the tree. We define the target distribution P ⃗ y in an inductive way by specifying sequences {k i , p i , n i } i≥1 and putting mass p i on the node of the random path at level k i . Conditional on the given node, we distribute the mass among its points uniformly. Let us now be formal. For the base of the induction, we let p 2 = 1/2 and k 1 = 1. We will specify the value of p 1 later. For the inductive step, for any i ≥ 2, given the value of p i , k i-1 , we will specify k i , p i+1 . We let k i be the smallest integer so thatk i > k i-1 and R(⌊k i /8⌋) < p i /k i . Notice that since R(n) = o(1/n), k i < ∞. We let n i = ⌊k i /8⌋ and p i+1 = min 1 4u ni , p i 4 .Notice that since {p i > 0} i≥2 , i≥2 p i < 14 , by setting p 1 = 1 -i≥2 p i the sequence {p i } i≥1 can be used as a probability distribution. We are now ready to define P ⃗ y on X × {0, 1}. To make the notation simpler, for any ⃗ y and for k ≥ 1w j ⃗ y≤k-1 = 1 -z j ⃗ y≤k-1 , if j = y k z j ⃗ y≤k-1 , otherwise .For i ≥ 1, letP ⃗ y x j ⃗ y≤ki-1 , w j ⃗ y≤ki-1 = p i k i , 1 ≤ j ≤ k i -1 .Notice that, by the definition of p i , this is indeed a probability distribution. We now show that P ⃗ y is realizable. Since ⃗ t is a star tree, there exists some h ∈ H such that h x j ⃗ y ≤k = w j ⃗ y≤k-1 , for all 0 ≤ j ≤ k, and 1 ≤ k ≤ n. Thus, for the probability of error of h we have that er ⃗ y (h) := P ⃗ y [(x, y) ∈ X × {0, 1} : h(x) ̸ = y] ≤ k>n p k , so by taking n → ∞ we see that P ⃗ y is realizable for every ⃗ y. Moreover, we note that the mapping ⃗ y → P ⃗ y is measurable.We now let (X, Y ), (X 1 , Y 1 ), (X 2 , Y 2 ), . . . be i.i.d. samples drawn from P ⃗ y . We can draw them asX = x J ⃗ y≤T -1 , Y = w J ⃗ y≤T -1 , X j = x Jj ⃗ y≤Tj -1 , Y j = w Jj ⃗ y≤Tj -1, where (T, J), (T 1 , J 1 ), (T 2 , J 2 ), . . . are i.i.d. random variables, independent of the path ⃗ y, withPr[T = k i , J = j] = p i k i , for all i ≥ 1, 0 ≤ j ≤ k i -1.For all i ∈ N, let us define the eventE i 0 = T 1 ≤ k i , T 2 ≤ k i , .. . , T un i ≤ k i under which the algorithm has not received any unlabeled points from any level k j , j > i. Let us also call E i 1 the event that ĥni does not query the point whose label is flipped, i.e., the point x y k i ⃗ y≤ki-1 . Also, we denote E i 2 the event that the learner classifies at least one point of level k i incorrectly. Then, we have thatPr[E i 2 |E i 1 , E i 0 ] ≥ 1 - 1 (7/8 • k i ) ≥ 6 7 ,since there are at least (7/8) • k i points on this level that the learner has not queried, and under the events we have conditioned on the flipped point along the path is chosen uniformly at random among these points. We now bound Pr[E i 0 ]. Notice that j≥i+1 p j ≤ 4 3 p i+1 ≤ p i 3 ≤ 1 12 • u ni . Thus, Pr[E i 0 ] ≥   1 - j≥i+1 p j   un i ≥ 1 - 1 12 • u ni un i ≥ 9 10 .Finally, we need to bound Pr[E i 1 |E i 0 ]. Notice that Pr[E i 1 |E i 0 ] ≥ 7 8 ,since the learner has n label queries and there are at least 8n points. Putting it together, we can bound Moreover, notice thatEQUATIONPr[ ĥni (X) ̸ = Y |⃗ y] ≥ p i k i • Pr[E i 2 |⃗ y] ≥ R(n i ) • Pr[E i 2 |⃗ y] . Thus, we can see that Pr ⃗ y Pr[ ĥni ̸ = Y |⃗ y] ≥ 9 40 • R(n i ) ≥ 18 31 .Using Fatou's lemma, we have thatE lim sup i→∞ 1 R(n i ) Pr[ ĥni (X) ̸ = Y |⃗ y] ≥ E lim sup i→∞ 1 R(n i ) • min Pr[ ĥni (X) ̸ = Y |⃗ y], 9/40 • R(n i ) ≥ lim sup i→∞ 1 R(n i ) E min Pr[ ĥni (X) ̸ = Y |⃗ y], 9/40 • R(n i ) ≥ lim sup i→∞ 1 R(n i ) Pr ⃗ y Pr[ ĥni (X) ̸ = Y |⃗ y] ≥ 9/40 • R(n i ) • 9 40 • R(n i ) ≥ 9 40 • 18 31 = 81 620 ,where the first inequality is by the definition of min, the second inequality follows from Fatou's lemma, and the third inequality follows from Markov's inequality. We remark that Fatou's lemma can be applied here since1 R(n i ) min Pr ĥni (X) ̸ = Y |⃗ y , 9/40 • R(n i ) ≤ 9/40 .Thus, there must exist a realization of ⃗ y such that Figure 6 : The VCL Game (Bousquet et al., 2021) .E[er⃗ y ( ĥn )|⃗ y] ≥ C • R(n) ,VCL Game Subroutine (Bousquet et al., 2021) : Input is a labeled sequence {(x 1 , y 1 ), . . . , (x N , y N )}1. Let τ 0 ← 0. 2. In every step t ≥ 1 :• If η τt-1 (ξ 1 , . . . , ξ τt-1-1 , x t-τt-1+1 , . . . , x t ) = (y t-τt-1+1 , . . . , y t ) :-Let ξ τt-1 ← (x t-τt-1+1 , . . . , x t ) and τ t ← τ t-1 + 1. • Else, τ t ← τ t-1 .For completeness, we provide various algorithms and results that appeared in Bousquet et al. (2021) ; Hanneke et al. (2022) , which we utilize in our approach to get sublinear learning rates. It is instructive to start with an informal description of a pattern avoidance function g : X k → {0, 1} k . Intuitively, this function takes as input a k-tuple of unlabeled data generated by a realizable distribution P X and it returns a labeling of these data that is not the true labeling by P. They define per(g) = P k [x 1 , . . . , x k : g(x 1 , . . . , x k ) = (y 1 , . . . , y k )] . Bousquet et al. (2021) provide a way to obtain such a pattern avoidance function for any realizable distribution. This is obtained by a VCL game in Figure 6 which returns a function ⃗ y τt . Their following result shows that as the number of points N used in the VCL game grows, the probability that we obtain a pattern avoidance function that is incorrect goes to zero. Lemma D.2 (Correct Pattern Avoidance Function (Restatement of Lemma 5.7 (Bousquet et al., 2021) )). Consider the VCL game in Figure 6 . Then, Pr[per( ⃗ y τt ) > 0] → 0, as N → ∞.Finally, we remark that Bousquet et al. (2021) showed the following result. Theorem D.3 (Supervised Learning Linear Rates (Bousquet et al., 2021) ). If H does not have an infinite VCL tree there exists a supervised learning algorithm that can learn H at linear rate. Lemma D.5. Let P be the distribution of the VC dimension of the partial concept classes that are obtained by playing the VCL game on infinitely many i.i.d. samples from P. Let d * be the 9/10quantile of P. Then, for n ≥ n P , where n P is some P-dependent constant we have that d n = d * , with probability at least 1 -3e -CP•n 1/4 , where C P is a constant the depends on the data-generating distribution P.Proof. Consider the following experiment. We sample an infinite sequence of labeled points from P and we run the VCL game (cf. Figure 6 ) on this sequence. Let y be the pattern avoidance function that is obtained from that game defined over ℓ many points and let F := f : X → {0, 1, ⋆} : (f (x 1 ), . . . , f (x ℓ )) ̸ = y(x 1 , . . . , x ℓ ) . √ n i.i.d. samples. Notice that whenever we estimate F with accuracy C P the empirical 9/10-quantile will the same as the true 9/10-quantile. The DKW inequality (Theorem D.1) shows that this happens with probability 1 -2e -2C 2 P k . Let us call this even E 1 and condition on it. Next, we need to handle the fact that we do not obtain samples from partial concept classes that are generated from VCL games on infinitely many i.i.d. samples from P but merely on √ n many such samples. Let us consider the following experiment. We run the VCL game on k streams of infinitely many i.i.d. samples from P and if the game has not terminated within the first √ n rounds, we rewind the pattern avoidance function to the one that is obtained in that round. Then, Lemma D.4 shows that, with probability at least 1 -e -C•n 1/4 , we will only rewind the pattern avoidance function of a o(1)-fraction of these games will have converged. We call this event E 2 and we condition on it. Let us denote by F k the empirical CDF of the VC dimension of the partial concept classes obtained by this experiment. Under E 2 , we have that sup x∈N |F k (x) -F k (x)| = o(1). Thus, by taking n large enough so that the o(1) << C P , we see that the estimation of d n using the samples that are obtained from the truncated VCL game also converges to d * . The bound on the probability of error follows from a union bound over E 1 , E 2 . Proposition D.6. For n > n P , where n P is some distribution-dependent constant, given m = O(n 3 ) unlabeled samples we can estimate p n,k , p X n,k , p(X,y) n,kwith accuracy o(1), with probability at least 1 -C P • e -C ′ P n 1/4 , where C P , C ′ P > 0, are distribution-dependent constants.Proof. As we alluded to before, using O(n 3 ) unlabeled samples in total we can estimate the quantities p n,k,i , p X n,k,i , p (X,y)n,k,i with accuracy 1/n for each version space V i n/5 , with probability at least1 -C 1 √ ne -C2 √ n, where C 1 , C 2 > 0, are absolute constants. Let us denote these estimatesp n,k,i , p X n,k,i , p (X,y)n,k,i We condition on this event for the rest of the proof. Assume that n is large enough and condition on the events of Lemma D.4, Lemma D.5. Let us denote by i 1 , . . . , i k the indices of the partial concept classes whose VC dimension is bounded by d n = d * . By definition, k ≥ 9/10 √ n. Consider the following statistical experiment. We run the VCL game on infinitely many i.i.d. samples from P, we define the partial concept class obtained from the pattern avoidance function of the game, if the class has VC dimension at most d * we keep the sample, otherwise we discard it. Then, we define its version space on the first n/5 samples of S ∞ 2 . Let us call V i the version space obtained by the i-th sample of this experiment. Then, P k (x 1 , . . . , x k VC shattered by V i ) is an unbiased sample from the distribution whose expected value p n,k we are trying to estimate. Similarly for the rest of the quantities we have defined. Let us call these samples p n,k,i , p X n,k,i , p | = o(1), | S X n -p X n,k | = o(1), | S (X,y) n -p (X,y) n,k | = o(1), with probability at least 1 -Ce -C ′ •n 1/4, for some absolute constants C, C ′ > 0. We condition on this event.Notice that, under the events we have conditioned on, the samples p n,k,i , p X n,k,i , p 1), using the triangle inequality on all the previous estimations we see thatS n -S n | = o(1), | S X n -S X n | = o(1), | S (X,y) n -S X n | = o(1). Finally, let S n , S X n , S (X,y) n be the averages of p n,k,i , p X n,k,i , p (X,y) n,k,i . Since | p n,k,i -p n,k,i | = o(1), | p X n,k,i -p X n,k,i | = o(1), | p (X,y) n,k,i - p (X,y) n,k,i | = o(| S n -p n,k | = o(1), | S X n -p X n,k | = o(1), | S (X,y) n -p (X,y) n,k | = o(1), with probability at least 1 -C P • e -C ′ P n 1/4 . Lemma D.7. Let n > C S ∞ 2 , where C S ∞2 is some constant that depends on S ∞ 2 , P. Then, with probability at least 1 -C P • e -C ′ P n 1/4 , for every k ≤ k * , if p X n,k < p n,k 2 then y = argmax y∈{0,1} p (X,y) n,k is the correct label of X. Proof. Let n > C S ∞2 be large enough so that for all k ≤ k * we have that:• p n,k ≤ 100/99 • lim n→∞ p n,k ,• the guarantee from Proposition D.6 gives us thatp X n,k < p n,k 2 =⇒ p X n,k < 3 4 • p n,k , • and p (X,y) n,k ≥ 99 100 p n,k =⇒ p (X,y) n,k ≥ 95 100 p n,k p (X,y) n,k < 80 100 p n,k =⇒ p (X,y) n,k < 90 100 p n,k .We condition on these events for the rest of the proof. Since p n,k ≤ 100/99 • lim p n,k for the correct label y * we have that p Proof. Essentially, the proof of this result follows by Markov's inequality. Let us consider some large enough n and condition on the event described in Proposition D.6. Then, pX n,k * ≥ p n,k * 2 =⇒ p X n,k * ≥ p n,k * 4 , so it suffices to bound Pr p X n,k * ≥ p n,k * 4 .Using Markov's inequality, we have thatPr p X n,k * ≥ p n,k * 4 ≤ 4 E[p X n,k * ] p n,k * = 4p n,k * +1 p n,k * = o(1) .where we have used the fact that E[p X n,k * ] = p n,k * +1 and that p n,k * is bounded below by a constant. Sublinear Rates Algorithm [Adaptation from Hanneke (2012) ] Input is a label budget N and a passive learning algorithm A p 1. Let S 1 , S 2 , S 3 , S 4 , S 5 , U be sets of O(N 3 ) unlabeled points that are i.i.d. from P X .2. Request the labels of the first N/5 points of S 5 and run A p on this set. Let h p N be its output. 3. Request the labels of the first N/5 points of S 1 , split them into batches of size O( √ N ) and run the VCL game on them (cf. Figure 6 ).38th Conference on Neural Information Processing Systems (NeurIPS 2024).In Appendix C.4 we show how to obtain an etimate.This random draw is induced by an execution of the VCL game on infinitely many i.i.d. points from P.Recall that we have one more classifier from S5.This is because pi+1 ≤ pi/4.If only one these number exists, then we ignore the one that does not exist in the definition of CP. If none of these numbers exist then the estimation task is trivial. 


Decision: The reviewers are unanimous that this is an interesting work shedding light on the possible types of learning curves in active learning.

Reviews: review: paper_summary: paper_summary: This paper studies active learning for binary classification. The authors provide a complete characterization of the optimal learning rates for non-adaptive active learning algorithms. The authors also develop an active learning algorithm for partial concept classes with exponential rates.
strength_weakness: strength_weakness: It seems that the analysis heavily relies on the assumption that the active learning algorithm is non-adaptive. For completeness, can authors provided concrete examples of (i) non-adaptive active learning algorithms, and (ii) methods to convert existing active learning algorithms to its non-adaptive counterpart without performance degradation?
questions: questions: Besides the comments above, can author provide analysis on the computational aspects of the developed/studied active learning algorithms?
limitations: limitations: N/A
paper_summary: paper_summary: This paper deals with universal active learning of binary classes in the realizable setting, which continues important work in related universal settings (interactive, online, ...). The authors propose a star number based VCL-tree variant, which together with original VCL-trees  characterize the 4 possible rates of universal active learning.
strength_weakness: strength_weakness: Please address my questions below. Am more than happy to raise my score if my first question on $e^{-n}$ learning of intervals (vs $\Omega(1/\varepsilon)$ rate under the uniform distribution) is clarified.

--- rebuttal update ----
raised from 5 to 7.
questions: questions: Your example with learning intervals on the real line is indeed very surprising. For example, in the Balcan et al. [2010] paper you cite, the authors discuss that actively learning an interval $[a,b]\subseteq (0,1)$ requires $\Omega(1/\varepsilon)$ queries **under the uniform distirbution on $(0,1)$**. Please clarify this apparent contradiction to your $e^{-n}$ claim. Sorry if I am missing something trivial.

The $o(1/n)$ rates seem somewhat related to the rates achieved by Attias et al., [COLT 2024] for universal regression in the absolute loss case. Are there any connections?

Do high-probability bounds ($\geq 1-\delta$) make sense in this active universal setting? Hanneke and Yang [2015] managed to fully remove the dependence on $\delta$ for uniform active learning
limitations: limitations: See questions.
paper_summary: paper_summary: This work provides a characterization of distribution-dependent learning rates for realizable active learning in terms of combinatorial complexity measures on the hypothesis class -- the main result is that any hypothesis class is universally learnable (i.e. learnable with rate $CR(cn)$ for distribution dependent constants $C$ and $c$) with rate either arbitrarily small, exponentially, linear, or arbitrarily large, depending on a complexity measure profile of the class.
strength_weakness: strength_weakness: Pages 8-9 probably should be polished a bit before publication. I think the content of Appendix A.4, which compares the results to passive and interactive learning analogues of this paper and thus gives clear insight into the power of active queries, probably should take up some real estate in the main body in the next version of the paper.
questions: questions: The results of this paper state that the universal optimal rate of active learning is exponentially faster than that of passive learning when there does not exist an infinite star tree for $\mathbb{H}$. Do the authors feel that the concept of ``infinite star tree'' yields insight into the phenomenon of active learning algorithms tending not to outperform passive sampling in practice?
limitations: limitations: Yes

Comments: comment: Thanks for the clarifications! I have raised my score.
I'd like to thank the authors for their explanations.