Universal Rates for Active Learning
Authors: Steve Hanneke
Amin Karbasi
Shay Moran
Grigoris Velegkas
Venue: NeurIPS 2024 poster (2024)
Keywords: Universal Rates
Active Learning
Primary area: learning_theory
TL;DR: We provide a complete characterization of the universal rates landscape of active learning.

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.

Universal Rates for Active Learning
Steve Hanneke
Amin Karbasi
Purdue University
Yale University
steve steve.hanneker. haa.reehhhanneeeema...oomm
amin kwrbaarrbassi...... eea.eeyallleee........ee.oo
Shay Moran Technion, Google Research
Grigoris Velegkas
Yale University
smoran@technion.c
Abstract
In this work we study the problem of actively learning binary classifiers from 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 our solutions by considering the learning curves they induce, i.c., 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- genereteeennnggggg distributions. We diverge from this line of work and we focus on the distribution-deppedder dependent framework universal learning whose goal 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 wnlabeled examples they use ahead their execution. Moreover, we identify combinatorial complexity measures that give rise to each case of our tetrachotomic characterization. This resolves open question that was posed by Balcan et al. (2010). As a byproduct of our main result, develop active learning algorithm for partial concept classes that achieves exponential learning rates in the uniform setting.
Introduction
The most prototypical type of learning that of supervised learning, where an algorithm is given as input labeled data points sampled i.i.d. from some unknown distribution and the goal is to output 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
very short amount of time, however understanding which category a webpage belongs to usually requires human feedback. Perhaps the most commonly used way model this problem through the active learning framework in which the learner is given access to a large stream of unlabeled data and budget of n queries that it can submit to 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, result, eliminate some redundancy in the information content of labeled data.
In this paper we study the optimal learning rates that are achievable by active learning algorithm. In the passive learning setting. it common measure the quality of an algorithm by its learning curve, i... plotting the decay of its error rate as the number of training examples increases, In contrast, in the
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

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 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 hata-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. (202I). ). 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 distributionddeeenden 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 rate R(n) if there exists learning rule h. such that
(3C, 0) (vP E RE(H)) it holds that (lcr)(hn)] C. -((c- nn Vn EN
The above expression states that there exists a learning rule hn and distribution-independeen constants such that for all realizable distributions the expected error rate of the classifier is at most C- R(c- n).. The difference in the definition of universal learnability is that 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 hn such that
(vP E RE(TT) (= 0) such that (ler)(((n)] S C.
CRR(c- R(c--), Vn E N.
Note that in the above definition the constants e, Cre distributtonn-deeedeent. As is evident from main result and from prior results in universal learning (Bousquet et al. 2021: Hanneke et al. 2022 Kalavasis et al.] [022;; Bousquet et al. [022]] Hanneke et 2023) this change in the definition affects the landscape of the optimal learning rates significantly.
1.1 Related Work
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
cct al. 2006 Hanneke 2207bb a; Dasgupta et al. 2007 Hanneke [209 Balcan et al.) 2009 2010
Hanneke 2012 Wiener et al. 2015 Hanneke and Yangl [015 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 family of distributions. To be more precise, while many of
these results have distributionndeepedeen guarantees, they are typically expressed in a way that aims to match lower bound on the minmax performance over family 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 few works that do study universal rates, e.g. [alcan et al. (2010); Hanneke 2012); Yang and Hanneke (2013), but none of them have derived complete characterization of the optimal rates.
The study of universal learning rates was put forth in the seminal work of Bousquet et al. (202T) who derived complete characterization of the optimal rates in the supervised learning
Universal Rates.
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 Boussqet et al. (002)) derived more fine-grained results for binary classification compared to Bousquet al. (02TT)
The work that is most closely related to ours is Hanneke et al. (2022) which derives complete
characterization of the optimal learning rates in 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.
Partial Concept Classes. The vast majority of the literature in learning theory has focused on total concept classes, i.e., classes that consist of functions that are defined everywhere on the instance domain. Recently, Areently,AAoon&& et al. (202T) proposed a learning theory of partial concept classes, i.e., classes that consist of functions that can be undefined on some parts of the instance domain. Later, Kalavasis jet al. (2022) extended some of the results to the multiclass setting, with a finite number of labels. Recently, Cheung et al. (2023) studied partial concept classes in the context of online learning and

---

they showed that there are such classes that are online learnable but none of their "extensions" to total concept classes online learnable. The advantage of partial concepts that they provide convenient way to express data-dependent constraints. En route of obtaining our main result, we design active learning algorithms for partial concept classes. For more detailed discussion about partial concepts we refer the reader to Appendix A.2
1.2 Formal Setting
Learning Model. We now present formally the learning setting that we consider in this work.
There is a domain X, which assume to be Polish space, and concept class HI C {0, 10, which satisfies standard measurability assumptions (see Definition [.I]. We define a classifier h: X2 + {0, 1 to be a universally measurable function and its error rate is defined as erp (h) := P P((z,)) y) h(x))= * y]. where P is the data-generating distribution over X' x {0, 1J. When P is clear from the context we might drop the subscript P in crp We call P realizable with respect to the hypothesis class H if infRcH (rp = O. We denote by Px be the marginal distribution of P on A'
Active Learning Model. We define an active learning algorithm to be a sequence of universally measurable functions which, given access to stream of unlabeled data points from X' that are drawn i..dd from Px and label query budget n, output classifier h. X {0. 1). In this work consider a non-adaptive active learning model, with respect to the unlabeled data. In particular, the learning algorithm needs to specify function 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) 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 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 con-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) x " be a rate function, where n is the label query budget of the learner.
H is learnable at rate R if there is learning algorithm hn such that for every realizable distribution P, there exist c, C for which E Ejer(h.)) C.R(en), Vnn N.
H is not learnable at rate faster than R if for all learning algorithms hn there exists realizable distribution P and c, C for which Bler([o.)] 2 CR(cn), for infinitely many n E N.
Hl learnable with optimal rate R if is learnable at rate R and 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.
IH 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 Boousque et al. (202T).
Definition 1.2 (Littlestone Tree, Informal (see Definition A.8
(Bousquet et al. 2021 ). A Litlestone
tree for IH C {0, 1e a complete binary tree of depth oo 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 < d
3

---

and every path from the root to a node at level n. there is some h E H. that realizes this path. We say that H. has an infinite Littlestone tree if it has a Littlestone tree of depth d 00.
We underline that this notion can be thought of as an infinite extension of the Littlestone dimen- sion (Littlestone 1988) of HI. Recall that the Littlestone dimension defined to be the largest d E N for which HI has a Littletoone tree of such depth and it is oo if one can construct Littlestone trees of arbitrary depth. Crucially, this is not the same as having a single tree whose depth 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- Chwrrohennis--iitteeeeee by Bousquet et al. (2021).
tree (VCL) that was introduced
Definition 1.3 (VCL Tree, Informal (see Definition A.10 (Bousquet al. 2021 A VCL. tree for HI S (0.1)* } is a complete tree of depth d. < do such that every level O I n. < Thas nodes that are labeled by xn+1 with branching factor 2 and whose 2 edges connecting a node its children are labeled by the elements of {0, 1]u+1 We require that for every node at any level O S n. < d, the path from the root to this node is realized by some IiI. We say that H. has an infinite VCL tree if has VCL tree of depth d xc.
Intuitively, the VCL tree combines the notions of the Littlestone tree and the VC dimension (Vapnik and Chervonenkis] [971 [llumer et al.] 1989). The differences between the Littlestone tree and the VCL tree are that 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 S {0, 1)x is complete tree of depth d S oo such that every level 0 S n < d has nodes that are labeled by (X {0, 13)"+1 with branching factor n n 1 and whose n. + 1 edges connecting a node to its children are labeled by ..). 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 O S 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
cc.
Essentially, this definition combines the structure of a Littlestone tree with the notion of the star number (Hanneke and Yang 2015). Every node level consists of 1 labeled points and there are n - 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.
1.3 Main Results
We are now ready to state the main results of this work. Our first main result is a complete characteri- zation of the optimal learning rates that 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.
HH is actively learnable at an optimal rate e
H is actively learnable at o(1/n) rates, but requires rates arbitrarily close to 1/n.
HH requires arbitrarily slow rates for active learning.
Our next result characterizes exactly when these rates occur by specifying combinatorial complexity measures of HI that determine which case of the tetrachotomy falls into.
Theorem 1.6. For every concept class H. the following hold.
If HH does not have an infinite Littlstonee tree, then it is learnable at arbitrarily fast rates.
If H. has infinite Littlestone tree but does not have an infinite star tree, then it is learnable at optimal rate e en.
If HH 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 the passive setting (Bousquet et al., (021) and the general interactive learning setting (Hanneke et al. (022). Our main result answers an open question that was posed in Balcan al. (2010), which asks for necessary and sufficient conditions for learnability at an exponential rate in the active learning setting.
1.4 Examples
We now present examples of classes that witness each case of 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 hence learnable at arbitrarily fast rates.
Exponential rates: Famously, threshold classifiers [a, oo) over I have 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 IR, which (also famously) has uniform rate 1/nn for active learning (it has infinite star number), and has an infinite Littlestone tree, but it has no infimite star (ree: for any choice of x in the root node, the edge labeling is effectively 2 disjoint threshold problems), so the depth of that subtree is bounded. Therefore, by our theory, it is actively Iearnable
has version space with star number equal 4 (it
universal rate (in stark contrast to the uniform rate 1/n)..
Sublinear rates: Halfspaces on Rd have 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. (202T) provide examples of classes with an infinite VCL tree, such the class of all claffisfiiers, so these require arbitrarily slow rates in our setting as well.
1.5 Comparison to Supervised Learning and General Interactive Learning Setting
We now compare our characterization to the results of Bousquet et al. (202T) that prove an analogous result in the supervised learning setting. Let first recall their main result which shows that in this learning model a class is universally learnable at:
Exponential rate e 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 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 HI 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 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 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 Px. 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 Hi does not necessarily imply
5

---

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 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.
1.6 Technical Challenges
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 concept class, given a labeled dataset S, is the set of concepts that classify all the elements of S correctly. Moreover, the VCL game Gale-Stewart game defined by [Bousquet al. (202T) that was used in their passive learning algorithm that achieves 1nn universal rate. The original (passive) learner from Bousquet et al. (2021) partitions a portion of the data into some number (m) 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 (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) (2(n) queries (to get the o(1/n) guarantee there), so the total number of queries would be (nearly) ()((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 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 '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 show composes appropriately with the analysis of the algorithm to obtain the (1/n)) rate. Comparing our work to the general interactive learning setting considered by Hanneke al. 2022), the main differences are (i) we design new algorithm that uses only label queries and achieves exponential rates when HH does not have an infinite star tree, a combinatorial measure we introduce in our work, (ii) we prove o(1/n) lower bound in the setting where HI has an infinite star tree, and (iii) we propose a novel active learning algorithm that achieves sublinear rates when HI does not have an infinite VCL tree.
2 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 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 adn-adaetive manner prior to the execution of the algorithm. The result is summarized in Theorem 2.1
Theorem 2.1 (Hanneke et al. (2022)). ) If HH does not have an infinite Littlestone tree it is actively learnable with arbitrarily fast rates.
For completeness, we present their algorithm in Figure Similary with the upper bound, the lower bound is an immediate consequence of result from Hanneke al. (2022), since the learner can submit more informative queries in their model.
Theorem 2.2 (Hanneke et al. (2022)). If HH has an infinite Littlestone tree, then H is not actively learnable at rate faster than exponential e e". This holds even if P x is known to the learner
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 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 learnable at an exponentially fast rate. Then, we show that whenever HI has an infinite star tree, the best achievable rate cannot exceed o(1/n). The omitted details can be found in Appendix C

---

3.1 Exponential Rates Algorithm: High-Level Overview
The high-level approach to get the exponential rates algorithm follows the same spirit of the ap- proaches from Bousquet et al.] (2021): Hanneke et al. (2022). First, we design an appropriate game (cf. Appendix ). i.e., game between a learner and an adversary, that is associated with IHT in which the learner has a winning strategy if and only if THI 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 partial concept class F that has finite star number (see Definition A.7). Since this result asymptotic, our approach is to consider several instances of this game, execute them for a finite number of steps, and obtain 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 constant, so then we can show
classes whose star number is bounded by distribution-dependdee that the majority class will also have bounded star number, and this bound is distribution -eppnddnnnddeedeettt. Thus, our task boils down to actively learning partial concept class whose star number is finite. In order to do that, we extend the approach that (annekee and Yang (2013) used for total concept classes to the regime of partial classes. We believe that this result could be of independent interest.
3.2 The Star Tree Game
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 6 that we use in this setting. In every round 2 we have the following interaction between the learner PL and the adversary PA:
Player PA chooses points (E+, (.) (E)..... (ST......
. EI-1 15 GF.....GTT X" x 10.13
Player PL chooses 77 E {o..... T- 1}.
Player PL wins the game in round 7 if
h(E)) = C h(E))) = 1- C.
#
M...i.m............ = E
=i nf
is easy to see that the winning condition for PL. is finitely decidable (cf. Appendix A.2 hence 6 is Gale-Stewart game. Recall that this means exactly one player between the adversary and the learner has a winning strategy. Using a result regarding the measurability of winning strategies in Gale-Stewart games that was shown by Bousquet et al. (202T) (see Theorem A.3) can prove the following connection between 6 and the existence of infinite star trees ( see Appendix C. for the proof).
Lemma 3.1. The class H does not have an infinite star tree if and only if Pt. has a universally measurable winning strategy in G.
The first step in our approach, is to make use of some O(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 for the details). The main technical issue 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,
a portion of these labeled points to estimate some number f., so that, with at least some constant probability over the dataset, the game will terminate within f,, many rounds. Then, we split the remaining of the labeled dataset into batches of size in and we run the game on each batch. The outcome of each game gives us 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. 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 ge- 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 partial concept class. We define
F = {1= X + 1,+1,
(22, ((x2)), ...,, ((x)) & image(@e)) ), V Io E X²
7

---

Notice that the constraint we have placed on F is satisfied if f(z;) *, for some i E [t*]. We consider the natural extension of the notion of star sets the case of partial concept classes, i... we say that a labeled set S with labels in (0. (0.1) } is 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 approach easier to follow, let us first assume that we do know / [ Then, our task boils down to actively learning a partial concept class.
3.3 Active Learning of Partial Concept Classes with Finite Star Number
We now present an algorithm that achieves exponential rates when actively learning a partial concept class F that star number s < co. The idea of our approach is to reduce the problem of actively learning partial concept to the well-studied problem of actively learning 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 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 Yangl (015) (see Theorem C.T) which guarantees exponential rates when applied to class with finite star number. Because the underlying distribution on the sample 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 for a partial concept class F which given label budget n and access to unlabeled samples from realizable distribution P returns classifier hn such that Ep- [er(h.)] S cide / where C1s C2 are absolute numerical constants, and s, is the star number, VC dimension of F.
3.4 Slower than Exponential is Sublinear
The next step in the characterization to show that if H has an infinite star tree, then 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 hns we distribute the mass the target probability distribution across the path, potentially skipping some nodes of it, in a way that creates infinite sequence Nig : .ig..... so that when the learner has label budget nzy. with some constant probability, it will only observe unlabeled points up to level ke,- 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 least C' P.,,/Ki where C' some absolute constant. Our choice of pty, ky guarantees that R(n,) > Pt, /ki,: 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
4 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 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-dependeett 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 get the exponential rates guarantee, we use the VCL Gale-Stewaa game Bousquet et al. (202T) (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 Px. Then, we execute the VCL game on O (v)n) different batches of size ((vr), Each of these games induces a partial concept class. We show how to obtain P d-dependent bound on the VC dimension that
In Appendix C.4 we show how obtain etimate.
8

---

holds for most of these classes. Moreover, we show that for most of these classes the data gentraatng 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 data-genenn 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 Us over the sample S and not on the data setiaaggeeegnngg distribution P. To illustrate the ideas of the algorithm, we consider five different streams of i.i.d. (unlabeled) data S1, S2, S3, S4, S5. 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 S5. 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. (021)) that achieves linear rate ((1nn). This is used for technical reasons in our analysis and in order ensure that the classifier we output has, at most, linear error rate no matter how the active learning component of our algorithm behaves. Next, Then, we run the VCL game on these labeled datasets of size vn/5 and obtain vn different pattern avoidance functions y //m/ that take as input l'
use n/5 of the query budget to obtain the labels of the first n/5 points from S1.
vn/s points (ef. Appendix D.2 D.2.. where i E [vn]. Let
F
Vayo )) 4 #M ( Vn/3 = {s |: x +) (f(I)),..... Me
Ir m ) I
First, we show that for a (1 ((()))ffraction of these partial concept classes P is realizable distribution. Intuitively, this means that the partial concept class we obtain by running the VCL game on vni many points is the same as the class we would have obtained if we were run the game on infinitely many points (cf. Lemma D.4p. Next, we need to estimate some number d, E N which, as + oc, converges to the 9/ 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 let
a, min dEN
{ [i2, i2, ................................ 89/10-//n E [V/)] :1 < .... < i9/20-/nod d (Ftm))) S d, Vj 19/10/1l)
where dFF) denotes the VC dimension of class F. Lemma D.5 shows that, for large enough n. dn = d', with high probability, where d' E N is such that with probability at least 9/10 over the random draw 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 o(1) ((1)-frrd -fraction of them do not correspond to samples from the correct distribution. To do that we use a robust version of the well-known Kiefekk-KKKereoooooleo
(DKW) inequality (cf. Theorem D.I 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 S2. We will make two distinctions regarding this stream. For the purposes of the analysis, we consider fixed stream of infinitely many i.i.d. samples from P and we denote it by S but in the actual algorithm we use dataset of size (nn) and we denote it by Sy. We define
1/s = { { E Vays : f(x) = y for the first n/5 points in S
to be the version space of F vn/s defined on the first n/5 examples of Sg Moreover, we let Va-,n/s 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 get a pattern avoidance function ÿ and then we define the par- tial 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 Va-.n/5 be the version space of F on the first n/55 labeled points of S55 We take d to be the 1/10--qammee of P as described before (ef. Lemma D.5). Given some A E N, let Pn, := EE[ (œ1. ... Zy VC shattered by Va- ../ss))ss S where the expecta- tion is over the draw of Va-,n/5. given the fixed Sg Let k- E N be the largest number such that
This random draw is induced by an execution of the VCL game infinitely many i.i.d. points from P.

---

lim Po # O. Notice that since, by definition, the VC dimension is bounded by d' such a num- ber k- exists. From here on, we will only consider the version spaces n/5 that are obtained from some partial class with VC dimension at most du Let Pr,k,i = PK (z1, T VC shattered by Vn/s)- Notice that for every & S dz and every i E [v'] we can estimate this quantity to arbitrary precision using only unlabeled examples. We denote by Pn.k, these estimates.
We now consider the first n² unlabeled points of the third data stream Sy. For each such point X, let PA,K == EI) Tk, X VC shattered by Va vnt,,/55) S2 X]. Moreover, for each y E {0, 1) let
v((xa) d',n/5 = (S E Var : [(X) = =y},
(X.22) Pn,k = EIP (x1, Ty VC shattered by d' dd'm///) 152 x1, E (0, 13.
(X.y) We define the quantities p p,,,, Pn,k. in the same way for the realized version spaces. Again, by Hoeffding's bound, can estimate these quantities to arbitrary precision using unlabeled data. Similarly as before, we denote these estimates by P. pr.k,s P ((X.)) The idea is to make use of Lemma D.4 and show that the classes which have been obtained by VCL game that has not converged will only affect our estimates by some (1)) This is formalized in Proposition D.6 Thus, we can use (X.v) We denote these estimates by Po,k, Pa,k. Pn,k., P Pn.k, in order to estimate pn.k. Pi, Pr,k
((..))
((X.)) These are the key quantities we use to infer the labels of unlabeled points.
Our algorithm tries infer the label of each unlabeled point X S3 (ef. Figure 7 in the fol- lowing way: if Px 2 Pa.k then we query the label of X, otherwise we infer the label to be 2
_(X,)) arg (0. Pr.k Leema 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 point is o(1) Lemma D.& shows that when k = k., this is indeed the case.
Finally, since we do not know the true value of k", we the algorithm for every k S -zz. The active learning component of the algorithm gives us d, + different labeled datasets, which we use train d, + instances of supervised learning algorithm, such as the one from Bousquet et al. (022)) analysis so far has shown that for sufficiently large nt, least 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( //n.). The last step is to run a tournament among the d,,, + 2 different classifier 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 corollary of the results we have discussed. All the steps are summarized in Figure 7
p. Our
Lastly, lower bound from Hanneke et al. (022) completes characterization (cf. Theorem D.11
5 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 Px.
Acknowledgments
Amin Karbasi acknowledges funding in direct support of this work from NSF (IS-1145002)) ONR (N00014- 19-1-2406), and the AI Institute for Dearning-Enabler Optimization Scale (TILOS). Shay Moran is Robert J. Shillman Fellow; he acknowledges support by ISF grant 1225/20. by BSF grant 2018385. by Israel PAC-VATAT. by the Technion Center for Machine Learning and Intelligent Systems (MLIS), and by the the European Union (ERC, GENERALIZATION and opinions expressed are however those of the author(s) only and do not necessarily reflect those of the European Union or the European Research Council Executive Agency. Neither the European Union nor the granting authority can be held responsible for them. Grigoris Velegkas was supported in part by the AI Institute for Learning- Enableed Optimization at Scale (TILOS).
101039692). Views
Recall that have one more classifier from Ss.
10

---

References
N. Alon, S. Hanneke, R. Holzman, and S. Moran. 2021. Theory of PAC Learnability of Partial Concept Classes. In Proceedings of the 62nd Annual Symposium on Foundations of Computer Science.
Idan Attias, Steve Hanneke, Alkis Kalavasis, Amin Karbasi, and Grigoris Velegkas. 2024. Universal Rates for Regression: Separations between Cut-Off and Absolute Loss. In The Thirty Seventh Annual Conference on Learning Theory. PMLR, 359-405.
M.-F. Balcan, A. Beygelzimer, and J. Langford. 2006. Agnostic Active Learning.. In Proceedings of the 23rd International Conference on Machine Learning.
M.-F. Balcan, A. Beygelzimer, and J. Langford. 2009, Agnostic Active Learning. J. Comput. System Sei. 75, (2009), 78-89.
M.-F. Balcan, S. Hanneke, and Wortman Vaughan. 2010. The True Sample Complexity of Active Learning. Machine Learning 80, 2-3 (2010), 111-139.
A. Beygelzimer, D. J. Hsu, J. Langford, and C. Zhang. 2016. Search improves label for active learning. In Advances in Neural Information Processing Systems 29.
A. Blumer, A. Ehrenfeucht, D. Haussler, and M. Warmuth. 1989. Learnability and the Vapnik- Chervonenkis Dimension. Journal of the Association for Computing Machinery 36, 4 (1989), 929-965.
Olivier Bousquet, Steve Hanneke, Shay Moran, Jonathan Shafer, and Ilya Tolstikhin. 2022. Fine- Grained Distribution-Dependde Learning Curves. arXiv preprint arXiv:2208. 14615 (2022).
O. Bousquet, S. Hanneke, S. Moran, R. van Handel, and A. Ychudayoff. 2021. A Theory of Universal Learning. In Proceedings of the 53dd Annual ACM Symposium on the Theory of Computing.
Tsun-Ming Cheung, Hamed Hatami, Pooya Hatami, and Kaave Hosseini. 2023, Online Learning and Disambiguations of Partial Concept Classes. arXiv preprint arXiv:2303.17572 (2023).
D. Cohn, L. Atlas, and R. Ladner. 1994. Improving Generalization with Active Learning. Machine Learning 15, 2 (1994), 201-221.
Donald Cohn. 2013. Measure theory. Vol. Springer.
Dasgupta. 2005. Coarse Sample Complexity Bounds for Active Learning, In Advances Neural Information Processing Systems 18.
S. Dasgupta, D. Hsu, and C. Monteleoni. 2007. A General Agnostic Active Learning Algorithm. In Advances in Neural Information Processing Systems 20.
David Gale and Frank Stewart. 1953. Infinite games with perfect information. Contributions to the Theory of Games 2, 245-266 (1953), 2-16.
S. Hanneke. 2007a. A Bound the Label Complexity of Agnostic Active Learning, In Proceedings of the 24th International Conference on Machine Learning.
Hanneke. 2007b. Teaching Dimension and the Complexity of Active Learning, In Proceedings of the th Conference on Learning Theory.
S. Hanneke. 2009.
Theoretical Foundations of Active Learning. Ph. D. Dissertation. Machine Learning Department, School of Computer Science, Carnegie Mellon University.
Activized Learning: Transforming Passive to Active with Improved Label Complexity. Journal of Machine Learning Reseurch 13, 5 (2012), 1469-1587.
Hanneke. 2012.
S. Hanneke. 2014. Theory of Eisagreement-Baseee Active Learning. Foundations and Trends in Machine Learning 7, 2-3 (2014), 131-309.
Steve Hanneke, Amin Karbasi, Shay Moran, and Grigoris Velegkas. 2022. Universal Rates for Interactive Learning. In Advances in Neural Information Processing Systems.

---

Steve Hanneke, Shay Moran, and Qian Zhang. 2023. Universal Rates for Multiclass Learning. In The Thirty Sixth Annual Conference on Learning Theory. PMLR, 5615-5681.
Hanneke and Yang. 2015. Minimax Analysis of Active Learning. Journal of Machine Learning Research 16, 12 (2015), 3487-3602.
D. Haussler, N. Littlestone, and M. Warmuth. 1994. Predicting {0, 1}-Funcciios Randomly Drawn Points. Information and Computation 115, 2 (1994), 248-292
Wilfrid Hodges, Hodges Wilfrid, et al. 1993. Model theory. Cambridge University Press.
Alkis Kalavasis, Grigoris Velegkas, and Amin Karbasi. 2022. Multiclass Learnability Beyond the PAC Framework: Universal Rates and Partial Concept Classes, arXiv preprint arXiv:2210.02297 (2022).
Alexander Kechris. 2012. Classical descriptive set theory. Vol. 156. Springer Science & Business Media.
N. Littlestone. 1988. Learning quickly when irrelevant attributes abound: A new linear-threshold algorithm. Machine Learning (1988), 285-318.
V. Vapnik and A. Chervonenkis. 1971. On the uniform convergence of relative frequencies of events to their probabilities. Theory of Probability and its Applications 16, (1971), 264-280.
Y. Wiener, S. Hanneke, and R. El- Yaniv.. 2015. A Compression Technique for Analyzing Disagreement-BE -Bsse Active Learning. Journal of Machine Learning Research 16, 4 (2015), 713-745.
L. Yang and S. Hanneke. 2013. Activized Learning with Uniform Classification Noise. In Proceedings of the 30th International Conference on Machine Learning.
12

---

A Omitted Details from Section 1
A.1 Formal Definition of Learning Setting
We recall some basic notions of measures and probabilities on Polish spaces. For a detailed treatment the reader is referred to Kechris (2012): 2
Cohn (2013). Our presentation follows [Bousquet al.
Polish Spaces. A Polish space is separable topological space that admits a complete metrie. For example, this category includes R", any compact metric space, any separable Banach space, etc.
Universally Measurable Functions. Let & be the Borel o-field on some Polish space X' and let be a probability measure. We denote by 3r the completion of & under μe i.c., the collections of all subsets of X' that differ from Borel set on a set of zero measure. A set B C X' is called universally measurable if B E 3r for every probability measure μ.. Moreover, a function f X + y is called universally measurable if (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 be Polish space. We say that a concept class C {0, 1) is measurable if there is Polish space O and a Borel-measurable map h X x Q -> {0, 1 so that H (h(0, 0 θ}.
We underline that Definition A.] is very general and its only requirement is that HH can be parameter- ized in some reasonable way.
A.2 Omitted Preliminaries
Gale-Stewart Games. We briefly discuss some basic and useful facts about Gale-Steeaa games, a
concept that was recently introduced to the learning theory community by Bousquet al. (202T). Our discussion follows [Bousquet et al. (2021): Hanneke et al. (202)). We refer to Bousquet et al. T and references therein for more detailed presentation. Tet us fix sequences of sets Xr, Di for 72T We consider infinite games between two players, a learner PL and an adversary PA where in each round t N 1, PA selects an element 2G E Xr, and then Pt selects an element y/ E V/. The rules of the game are defined by a set W C I1 (K₁ x )i) of winning sequences for Pt. This means that after an infinite sequence of consecutive plays 1 Vi, I2 U2,..., we say that Py. wins (111, y1, T2, 3/, E W: otherwise the winner is PA-
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, strategy for PA is a sequence of functions fa [X x V.) + Xe for 2 1, so that PA plays I₁ = fe( Bi...., T1-1, 31-1) in round t. Similarly, a strategy for PL a sequence of 9: IX,, V/)) X, + Ve for 2 1, so that PL plays V/- Se (31 - (F in round We say that a strategy for PA is winning if playing that strategy always makes PA win the game no matter what PL plays: a winning strategy for PL is defined similarly. The main question these infinite games is determine conditions under which one of the two players has winning strategy in the game. We remark that when the game is finite it is not hard easy that exactly one of the two players has such strategy. In the context of infinite games, such a condition was introduced by Gale and Stewart (1953): W is finitely decidable if for every sequence of plays (I1, V/, 22, ./,...) E W. there exists some n < oo so that
(α1, Ml........ Ln, Un, 1n 1h+11 " 1h+2 E W
for all choices of 1'41 V 2242 2 In words, the condition that "W is finitely decidable" means that if PL wins the game, then she knows that after playing a finite number of rounds. Conversely, PA wins the game when PL does not win after any finite number of rounds.
Such game whose set Wi is finitely decidable is called a StewaStewart game. We use the following important result about Gale-Stewart games.
Remark A.2 (Gale and Stewart (1953); Hodges et al. (193)); Kechris 2012)). )) In any Gale-Stewart game exactly one between PA and Pt has a winning strategy.
13

---

The above result is purely existential and provides no information about the complexity of the winning strategies. Importandly is unclear whether winning strategies can be chosen be measurable. The next result from Bousquet et al. (202T) addresses this concern.
Theorem A.3 (Theorem B.1 from Bousquet et al. (022))) Let {X+)121 be Polish spaces and (Y))21 be countable sets. Consider a Gale-Stewart game whose set W S [I x Yi) of winning strategies for Pt. is finitely decidable and coanalytic. Then there a universally measurable winning strategy.
The following remark shows that we can, equivalently. let the strategy of the the learner PL and the adversary PA depend only the choices of their opponent in the previous rounds.
Remark A.4 (Bousquet et al. (222I). The strategy of PL is defined be sequence of functions Y1- = fe Bi...., 31 yt-1) of the history of the game, where yı.... 1t-1 are defined similarly. Thus, we can equivalently let yo f.( The same holds for the strategy of Pa.
Partial Concept Classes. The traditional PAC learning framework studies (mainly) total concept classes, i.e., classes of functions h X - 10.1} that are defined on every point æ E X. The caveat with total functions is that they do not provide direct way to express data-dependení constraints. For example, the space X' is high- nigh-dimensional but the data that the leaner has to classify lie in a low-dimensional space, it is not clear how 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. Allnn et al. (2021) proposed and studied 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 fx) = * means that f is undefined r. In the context of classification of images, when a classifier returns
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 the setting of partial concept classes (see, e.g., Definition A. To show how one can use partial classes, to express dete-ddeennent constraints, we remark that Alon al. (202I) illustrated how the class of d-dimensional linear classifiers with margin y > 0 can be formulated as partial class: we say that a sample (11. y1),-- ................. nnn yn) E Rdd {0, 1} is (R, --separable all the points T1,..., Fn lie in a (euclidean) ball of radius R. the O-labeled examples and the 1-labeled examples are linearly separable, and the (euclidean) distance between the O-labeled examples and 1-labeled examples is at least 2n Then, the class
FR. = R + {0, 1+} :VxI,,.... E supp(f):
(I1, (f(z))) ..... (In: (f(xn) 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 bounded by O R² (Alnn et al. 2021p. 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 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 HI whose VC dimension is bounded by d < oo, there is an algorithm A (X x 13)**) x X + {0, 1} such that for any n E N and any sequence {(11, (1).. (In, }n)} E (X' x {0, 13)" that is realizable w.r.t. IH.
d 1[A(Fo()) Bol):.... Io(n-1); Bo(n (0 1) Ro(n)) ) F vo(n)}
Σ (n)ym(n)
n!
where Sym(n) denotes the symmetric group of permutations of n1).
14

---

In particular, Theorem A.5 implies immediately that if (a1, 81)..... (In, Un) are i..d. from P then the classifier (-) 1 y1....,... Ln. Vns-) has Ejer(ha)] - πtI We remark that Alon al. (2021) showed that this result also holds for partial concept classes.
A.3 Omitted Definitions
Definition A.6 (VC Dimension of Partial Concept Classes (Alon et al. 2021)). For a partial concept
class F C {0, 1,* the VC dimension of F is defined to be the largest number d E N such that 3(21,.... Ra) E X such that {(f(z))..... f(ra) E F} = {0.1} 1] Such sequence (21,...., Fa) said be shattered by F. If there no bound on we say that the VC dimension c0.
The following definition of the star number is an adaptation of the definition in (Hanneke and Yang 2013).
Definition A.7 (Star Number of Partial Concept Classes), For a partial concept class F C {0, +}* the star number of F is defined to be the largest number E N such that (2 1. ................................ 2g) X2 such
that 3fo E F and vi E [s), Ff; E F fi(z;) = fo(m)), f((2;) = fo(2;) * E [s] (i). If there is bound
say that the number
Definition A.8 (Littlestone Tree (Bousquet et al.) 2021)). ) Littlestone tree for H S {0. 11 is complete binary tree of depth d S co whose internal nodes are labeled by X, and whose two edges connecting node to its children are labeled by {0, 11, such that every path of length at most d emanating from the root is consistent with concept h E H. Formally, Littlestone free is collection
U Osted
( : TE [00113)) = {=0
(0o, U {2o0- Zo1 Z 211} U...
such that for every path T E {0, 1]d and < d, there exists h E IHI that h(gge) We41 for 0 < 2 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). Star tree for H S {0. 1)x of consists of a collection
U {(rg, zx) (x (0,1){+1) ū E (0) {0. 1] x x 10. Osted
0}
such that for every level n < and [0} (0, 1) x ... 10, 1, , n-
1 1}, there exists some E HII such that hila", gge) = S gex 1k for all 0 S < k and < S n, where we denote
Jsk (91.82......... yb), Ijex (1 $go Bgc)
TTck (Fgen)
* $gch
yu+t1 #i otherwise
f( f Uk+1)
Tex
We say that HI has an infinite star tree if it has a stur tree of depth d = ao.
Definition A.10 (VCL Tree Bousquet et al. (2021)). h. A Somnil-Cherromenss-lllleessss ( (VCL) tree for [ C 10 of depth d I consists of collection
U (aa A x JE _ (0, x x... x {0,133} usted
such that for every level d, and ğ E [0. 1} x 10. x 10,1)*t1 there exists some H such that h( = Vi.11 for all 0 < i < and 0 < k n. where we denote
J<k (vi (v2
22)
k-
Ijsh = (igg T5.)
We say that HI has infinite VCL tree it has VCL tree of depth d = oo.
15

---

Figure 1: Arbitrarily Fast Rates Algorithm (Hanneke al. 2022
Arbitrarily Fast Rates (Hanneke et al., 2022): : Input a label budget and a rate function R(n).
1. my f
[2n(1/R(m))]]
In(m: (B(m))
2. m2 f-
R(x)
3. Create sets S1 = 21...... 2m S2 = 2mi+1r +1 Tmm.
4. Split S₁ into Ly/mi] batches of size [ymi] and consider all the labeled prefixes of the batches in lexicographical order: big denotes the i-th batch with the labeled prefix
j. S S 2lyma]+1
5. Let Ao(;;
the output of the ordinal SOA trained on b,. and denote (ı.( (z bt.).
See (Bousquet al. 2021
6. Evaluate the classifiers (-) the points in S2-
7. Define F of equivalence classes: gt.j and gr.," are in the same class iff they classify S2 the same.
8. For each F' IF, define
Fank(F)- = min
r 11:11 S 1i1is <2...... < [/m]j/ S LVmil, .i...., l [ymil// /3 E [2
such that Kig.k, E FF,1 piisjs mi
or rank(F)) = oo if no such exists.
9. Enumerate == (FFi, F2. so that rank(F;) is non-decreasing in E, and pick any
Se E F& for each
10. For each distinct j S |vn] query the label of any point in S2 on which ft, fj disagree.
11. If there is some fü which is correct on all the points we queried, return fr.
12. Otherwise, return any fe.
B Omitted Details from Section
C Omitted Details from Section 3
C.1 Proof of Lemma
Before we prove our main result of this section, we present an omitted proof from the main body.
Proof. Assume that IH has infinite star tree. Then, the adversary start from the root of the tree and play (5,51 (1) (Te, Z and for every strategy (1r)+21 of the learner, PA follow the path Ter (m,,72.- 7/.............................. 77) and play (Z in round + 1. Since the tree is infinite, there is no N such that H E.
For the other direction, assume that the adversary has winning strategy. Then, we can define the tree
T= U OSEC00
(T En) E (x 10.++1(0,110))) (0,11 t E {0, 1, .......-- - sise
where (Tom.... Eq .. ( (mm..................... -)))). The tree T is infinite by
the definition of the winning strategy G for PA. To prove the universal measurability the winning strategy of PL, using Lemmal A.3 suffices to show that the set of winning strategies W of the learner
16

---

is coanalytic. To this end, we consider its complement
W
(E (E E U x {0,13' x (0,...,t-11)) 13) G.........................
Entim & #
t=1
- =uur (5:.:::
h(0, (.) = 1 53. if 1f ,si<s}
h(0, 5:) C. if +
110 ==1
1(0, = 2 if + ,0
Notice that the set sumption. Also, the intersection in the above expression are countable and the union is a projection of Borel set. Hence, W is analytic, so we have proven the claim.
| is Borel by the measurability as-
h(0, =1 - if
C.2 Active Learning of Partial Classes with Finite Star Number: Exponential Uniform Rate
We now explain the approach actively learn partial concept class with finite number at uniform exponential rate. We first state 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 (015)). There exists an active learning algorithm A ffrr a total concept class IH which given a label budget n constant and $ is the star number of the class, and access to samples from a realizable distribution P returns a classifier hn such that, with probability arbitrarily close to one, P* p'(hn(1)) # vl S E.
(o)()))), where is absolute numerical
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 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 s, its VC dimension is also finite. Let S = (XI...., Xm) be m samples of the stream that A has access to, where m some value to be determined. We also let
Å (h: + (0,1) Aʃ E s.t. I(X.) f(X.) Vi E [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" realizable with respect to have that, except for measure-zent event, H + This can be seen as follows. Since the distribution P* is realizable, there exists sequence of functions fa F so that
P'[[(() + < 2
Let fix m 2 1. We have that
Σ
Pr|Bssm: m: fe(x.) + yol I m Σ P'(f((()) + vl < <0,
where the first inequality is due to union bound. By Borel-Cantelli, with probability one, there exists for every a hypothesis F so that f(x.) = ys for all I m. For the rest of the proof, we condition on this probability one event Eg. We definite P to be the uniform distribution on the (labeled) sample. Our previous discussion shows that P realizable with respect to H. Now let us run algorithm A' from Theorem C.I with 5 = 1/(2m) and success probability 1/(2m). Let E, be the event that the error of the output h of A'' is most 1/(2m). We condition 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,, 1 < i S m. Indeed, if for some i E [mm] we have that h((,)) f Y,, then er > 1/m. Notice that, by the definition of H. we have that s (Hl) < s(F). Moreover, the number of labels that A' requests is at most e log(2m)) where e 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 that
d(F)
(fer(hmm)) Eil
m +
17

---

6. The aforementioned algorithm can find the labels of these m points after making Thus, we get that
d(F) 1 d(F) +1
(ler(hm)) v m+1
It follows immediately from the definitions that d(F) S sFF). The result follows by picking e/n
m
Exponential Rates for Partial Classes
1. f- gon/s where c the constant in Theorem C.I
2. Take sample of unlabeled data S (X1,-.
m
3. Define H. be the total class of the concepts in F that undefined on S, i.e.,
{h: : + {0, 3f E F.t. M(x)) = Vi [m]]
4. Let P be the uniform distribution over the sample (IX,, (Xms Ym)), where Y; is the true label of X,, à [m]].
Use the active learning algorithm from Hanneke and Yang 2015) on the distribution P (see Theorem C.I).
most (HF) log m) queries, where a(H) is the star number of HH..
Use these m labeled points as input to the one-inclusion graph algorithm (Haussler
et al. 1994) and get h (see Theorem A.5)
This algorithm guarantees linear error in m, i... Efer(h)) S
m=+11 where d(F) is the
VC dimension of F. Return Am..
Figure 2: Exponential Rates Algorithm for Partial Classes.
Star Tree Gale-Stewart Game with Finite Sequence and Estimation: Input is a labeled sequence ((11,91), (IN. }N)}
1. Use [N/2] of the data to estimate fnv (cf. Lemma C.5 Let N [NV/fn
2. Use the remaining [N/2] of the data run the star tree game (cf. Figure 5) and obtain
f iiiis N.
3. Estimate for Ñ
F { |:x -1 (0, 1, V(II,..... Iea ) ) x (1))
..., Tryy I (Itte )) $ image (Tew )
4. Estimate the 11j6-iajrrty class
FN { f:x- (0,-,0011+1 ve N, xr) x2, 3 at least (9/16)N classes F3. S s Ñ s.t.
3f E F, with
(f(az)...,,
5. Return {Ge: (X (0,1)) (0, 13} HHEN where
Ge(z1,V1,.... Fz, ve) = 3s E F (f(z))....))) (((e)),.,(((E)))) =
we
Figure Majority Class Estimation Through Star Games.
18

---

Figure 4: Exponential Rates Algorithm.
Exponential Rates: Input is unlabeled data stream (51 22.---1 } and query budget
1. Set number of unlabeled examples un [n/2] + e where 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 with points
{ ... [n/ )
4. Create the partial concept class
Fg = [f: {0, +) VŁ E N, V(Z)....... xe) E X at.
f(re) = 1}.
5. Run Figure 2 on the partial class FG with budget [n/2] and return its output.
C.3 The Online Setting
To build some intuition, first show how use the game between the learner and the adversary discussed in Section to get an asymptotic result. We call this the online setting. Assume that there an infinite labeled sequence there exists h E HI h(xx)) ye. We use S to simulate the game 6 between PA and PL which gives rise to a partial concept class F with finite star number. This approach is shown in Figure 5
(I1 //. Z2, 3/....) that is consistent with H, i.e., for any t oc,
Star Gale-Stewart Game with Infinite Sequence
1. Let 91 X x {0, 1} - {0,1} be the function that corresponds to the strategy of PL in the first round of G.
Initialize To + 1.
3. Let (x; y) = (x. y)
In the first round the learner just flips the label.
4. For every 2 1:
If ( 1+1; Ut- - .......,................... Te, Me) image(ūn.n): witnessed by 7 # proceed to the next round in G.
Ti t- T(-1 +
Dr. (1)))) nr, (2
(G..... .., - ). where Th, (C),
; is the strategy
of PL in round Ti of C, given its history.
F7. (In, y0:
-1, V7- = (0o, yo,
It, Dr. -1)
{
yi yi:
if 9r. (ro, y0. Cr. 1, U7,
#
,ssi<n
Vi 1 yir
if 9r. (ro, yo. ... Ir, 1 UT,
Else: + T--1-
Figure 5: Star Gale-Stewart Game on Infinite Sequences.
We first show as 1 - the game converges, i.e., there are no more realizable -u-lle (I1, Bi...., Tr,- )r.-) that belong to the image of Jr,.. for some finite number t*. To simplify the notation, we define gr- Tr.. Recall that this function is defined in Figure
Lemma C.2. If does not have an infinite star tree, for any sequence I1, $1, 22, V2 ......, that is consistent with HI, there exists some finite number t E N, such for all > t*
(It-
30- Mtte:itttttt------ Lt. ... Mr) ) & image(gr-1).n T--1. 9.
Tt, yt T--1 ... -...; Wt) image(Or-1) happens infinite sequence of times 4, l,..... Since yr, is a winning strategy for the learner in G. we have that for some finite (* it holds that IHIl & M.... E.-,, -n-- in Figure 5 Hence, we have arrived in contradiction.
Proof. Suppose that (xt- (xt-
Ø (see Equation (1)) where &., G. y are defined
19

---

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 Vst- Moreover, the functions It are universally measurable with respect to Tgg; USt and the arguments of their imput. To be more precise, for all I 2 0, there exist the following universally measurable functions
U (0.11)*) (1,))) - (X {0, Ast
T (X x (0,1))* (1....,,t1) G. (0,00)))
so that
To
= ,., Bc), ge(wi, 21,...,, Wx, 2T,) Ge( 01...., Dr, W1, 21..... Weg Zr,).
C.4 From the Online to the Statistical Setting
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 in [Bousquet et al. 2021); Hanneke et al. (2022). In particular, we adapt the approach of Hanneke et al. (2022) from the VCL game the tree game. The key steps outlined in Figure
Let P be a realizable distribution with respect to and X1, Y1, X2, Yg,..., be an i.i.d. sequence from P. For the remaining of the section, assume that H. does not have infinite star tree. Let us now set up the notation that we use in our proof. We denote
To = ( ,,, Xx, Yt), 9e(W1, Z1, Wt, == G.(X.......... = X,, YI, Y,, WT E...... We, zt,)
where these functions are defined in Remark C.3 For any integer k 2 1, we define a "flipping" function Os (X' {0, 1})* - (X' x (0, 1})* to function that flips one of the labels of its input
from O to 1 or vice versa. We also define the probability of error of this function as follows:
per Ox) = per (āx) = p k ([z1, Vi...., Tk. ykk) (I1, .1..,,,.. Tk, yk) E image((x))
i.e. the probability that k-tuple drawn i.i.d. from P belongs the image of Øz- When there is confusion about the domain of ZK we will omit its dependence on k. Our first observation is that we get algorithm that is consistent in the statistical setting. Our proof adaptation of Lemma 5.7
in Bousquet et al. al. (2021).
Lemma C.4. It holds that P(per(ā.) > 0) 0 as co.
Proof. We know that realizable so we can pick a sequence of hypotheses hy E HH such that er(hx) S 2 k E N. Taking a union bound over all t 2 1, we have that
Σ Pl)h(X))) + Y., for some s] S er(hu) cc.
Thus, by the Borel-Cantelli lemma, it holds that h(X.) Ys, Vs S for some h E TH (with probability one). Let
T sup {s 1: (Xg-r.-++1 Y t X., Y.) image (āe-))
Then, we know from Lemma C.2 that 7 finite with probability one. Recall the law of large numbers
for m-dependent sequences: if 21, Zz .... is an i.i.d. sequence of random variables, then
[n/m]
lim 1 E((44) Z+mm)=
1 m
lim
f(Zmjtiti Z tol) E(f(Z,, ... Zm))
n2 1=1
Thus, we have that
t+
Psper* Th (#:)= = =]= =P
lim
1
Σ
1xx, Y. Xe........
=
S
5
++S
2 P
lim
1 1(x, Y N.... (
= 0 55.55 <t
S
s=t-1
P < t).
We know that is finite with probability one, so we have that P[per (g:) > 0] S PP 4 - 0, as
t + co.
0
20

---

Lemma C.4 guarantees that for some t* E N. the Gale-Stewart game played on set of t" points will have converged with probability at least i.e. Pr [per(g-) 0] - 1/8 This number t* depends on the distribution and is unknown to the learner. We first show how the learner can estimate similar in from the data. Our approach an adaptation Lemma 5.10 Bousquet et al. (2021). but we present the proof for completeness.
i.e.
Lemma C.5 (Adaptation of Lemma 5.10 in (Bousquet et al. 2021)). For any N E N, there exists a universally measurable ix (X1, Yi.... XLN/2 Y (1/22) whose definition does not depend on P so that the following holds. Set the critical time t* E N be such that
Pr Pr[per(Gre) ) 0] - 1/8,
where the probability is over the training set of the algorithm. There exist C, > that depend on P. t but not N that
PrliN E TT) 1- 1
where the probability is over the training of the estimator iN and T is the set
T" (1 S St Pr (p(e(((::) > 0] s 3/8).
Proof. We split this labeled set into two parts. The idea is to use the first one to run the Gale-Stewar game and the other one to estimate whether it has converged or not. For each 1 S S L and
1 H i ar we let
7े =
Y(-
(I- 1)(+1 X Ya.)
(w1,, 21..... W ==
(1-1) Xit, Yus, W1 E1, ....... Wrys
be the estimated quantities when we run Figure 5 on i-th batch of the data. Next, for each we estimate Pr Pr[per(0:) > 0] by the fraction of the for which there is tuple on the second quarter of the data that belongs to the image of g. For every fixed t, the data that the functions { [N/21 trained on independent of each other and of the second half of the training set. This means that we can view every {Øt is LN/21c as an independent draw of the distribution of gt. To estimate the error of the algorithm
the second quarter of the training set. We let
|
1
N//4
1 [WALLAAHHSSSS
S1 Eimage(ūt))
Now observe that
[N/11
1
Se [N/4t]
(per(G))>0)
with probability one. We define
EN = inf & |N/4] è < 1/4),
where we assume that inf @ = oc.
We now want to bound the probability that iN t". Using Hoeffding's inequality get that
1 < Pr Gt 2 4
Pr fiN > r] < Pr
c. 2
= Pr
Ct-
=
Pr e+- Ele-- 2 S e -IN/44 LN/44
4
8
8
This implies that y & t" except for an event with exponentially small probability. Moreover, for all 1 < t t* that Pr [per(ot) holds by continuity). Now fix some using Hoeffding's inequality again we get that
> g. there is some 0 such that Pr [per(ğt) > <}> + (this
S such that Pr [per(ğt) > 0] > (if it exists). Then,
N/41
1
Pr
Σ
1 (per()))e)
< SE-1N/441/12
N//41
Whenever g is a function such that per(g) > E, then
Pr [[3s: [N/4] + +1s [N/2] T, (Xo+1, Y Yo41. Xetri Yetr) image(g))] 1-(1 =))((N- (2)((N-4)/1) ((([N-))/4])
21

---

since there are (DN-44/447 disjoint intervals of length As we mentioned before, fo hi N7/4) N are independent of (X,,, x>)s>>/a mn/4). [n/4]] Thus, applying union bound we get that the probability that all oi that have per" (+) > e make at least one emror on the second half of the training set
Pr 1
- 1 | (
Kort if x (Eimage
(1 - ()
2
4t
where the last inequality holds since T/ 2 t*, Thus, we get that
Pr[in t] s Pr & ] < N
(1 -))00 +e - L |
Using the previous estimates and applying union bound, get that
Pr(iN & T*) S e 1-11//441//222 t
(1 - =-)0 + 1N--11//411125 < Ce
for some constants C, > O.
Essentially, Lemma C.5 tells that we can estimate a batch size En, using only information from the data, that, with probability 1 Ce-on the star tree game will have converged when we run it on i 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 B3. We show that if most of the games have converged, then the majority class has bounded star number. This made formal in Lemma C.6 We remark that Hanneke et al. 2022) showed similar result regarding the VC dimension of the majority class.
Lemma C.6. The majority class F defined in Figure has star number that is bounded by some distributionn constant s, with probability at least - e ecN for some absolute constant O.
Proof. We know that there exists some 5" such that, with probability at least 9/10, the star of any partial concept class F, is at most s* We let X, = [star number J; s-). Notice the all the X, are i..d. Bernoulli random variables with p S 1/10, since the data that induce the classes Fg are i.i.d.. Thus,
Hoeffding's 's inequality to bound the probability that more than 2/10 10 of them have star number greater than s" as follows
N
Pr Σ
x, 2 (2/10)
= Pr Σ x: (1/10)N 2 (15/72) S5-50
We let E be the complement of the event above and we condition on it for the rest of the proof. So, we know that at least 1/10Ñ of the partial concept classes F, have star number bounded by s* We will bound the size f of the star set of J. For any star sequence S (x1, V1....,.. Fe. ve) E (X'x x (0, 1 of F it holds that
...
Up. Vp [4] (i)) > 9/16
Using Markov's inequality, we get that
e - up vp E [8] (0))
N
16"
22

---

Swapping the summation gives us
9
y Vp [4] (5}}
16
j=1
Ñ
1
7
Σ
Vp. Ap [4| (}} 5
16
Using Markov's inequality again, we get that
N
1
Hff f(x,)( = -- f(Tp) - = Ub Vp E [4 (i}) > 9/16 K
1=1
j=1
16
Σ
Σ
(4] (1
9
N
j=1
This implies that
(())): -1 Up vp (4] (1) > 9/16
< =
j=1
N
1 Σ j=1
e F. -1
vp [4] (1} 2 7/16 2 2/9.
Thus, have shown that least 2/9 of the partial concept classes witness 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 that correspond to star patterns that the class does not realize and the remaining set of labeled points is star set. Since at least one these classes' star number is at most s* we have that 7/16 m I s*, which means that m < 16/7(s" + 1). Thus, we have shown that the star number of J is at most 16/7(s* + 1) S, with probability at least eo
Similarly as in Hanneke et al. (002)), we define a sequence of universally measurable functions [Ge: (X (0. 1)) {0, 1 where
EEN
Ge(x1. (1.11.91..... zz. ve) ==ff (
9e)
An equivalent interpretation of the previous lemma is that the star number of the partial class on which {Ge) returns has distribution -eppbuddnnnddeeeenttt bound, with high probability. Lemma C.7 is an important component in the derivation our result and it shows that {Ge) HEN 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 {Ge) teN as defined above are universally measurable functions, and with proba- bility at least 1 Ce -oN Ce-oN CC,c> > 0, the following hold:
The star number of the class
FG
: VEEN, V(ri,...,, E Ge(mi, ((1)), f(xe)) 1}
has a finite distribution-dependemm upper bound s.
VL E N, for (I1, "t, Tt, ~ Pd, Ge(XI, It, y1) = with conditional proba-
bility one (given Gt).
Proof.
We condition on the event Ey described in Lemma C.6 Notice that, by definition, labeled
sequence S = (æ1, V1 ..., Ze, ye) (X {0, 13) is star set of the class FG if and only if S is
23

---

star set of F.A Hence, the bound on the star number follows immediately from Lemma C.6 We
also condition on the event & described Lemma C.5
We now bound the probability that least
(13/32) N of the functions Dix have per we get that
Fix)
O. For any i E T", using Hoeffding's 's inequality
Ñ
Pr
per Fiv
>0}>
13
Pr
1
per
Fix
> >0}
1
S exp
(-N/512)
32
8
32
2=1
Since we know that in S 1", taking a union bound over all
$ 1 1 1" we get that
N
N
Pr
per
giN
> 0)
13
i
ET
Σ
Pr
per
)
Jo
> 0
13
32
32
T
t exp
/512
Thus, except for an event with exponentially small probability, at least 19 19/32 of the functions Ti have per a with probability one. Notice that, by definition, if the partial class F; that corresponds
to such function cannot produce labeling ūe {0, 1} of some tuple Z. E X where V P we can infer that this Te is not the correct labeling, and this inference will be valid with probability one over the draw of Ze. Thus, with probability one, if the 9/16-majority cannot produce some labeling we have that at least one such partial class F, that corresponds to a correct T cannot
produce this labeling, so it is not the correct one. As result, with probability one, if F cannot produce de for Ze we know that this not the correct labeling. The measurability of {Ge)een follows by the measurability of all the (
'ie The proof of the lemma follows by noticing that the probability of all the events we have conditioned Ñ [ 2 [N/2/"].
be bounded by 1 C'e-c'N and that
We are now ready to prove the result about active learning at exponential universal rates. Our approach summarized in Figure 4
Theorem C.8. Assume that H C 1)* does not have infinite star tree. Then, Hi admits 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 [eeT]] points. This is because we define a uniform distribution over these points during its execution. To prove the learning rate guarantees, condition on the event E, described in Lemma C.7 Then, we have some partial concept class Fg whose star number is finite by some distributiin--ependded
first
number 5 and has the property that Ae E N, for (I), ... .2,, Vr) ~ Pf, f(z)) = .I...., f(z)) ye for some f E Fa. Thus, the conditions of Theorem C.r satisfied and the conditional error rate of the output of our algorithm ((er(h,)) [E&) < cide--anj Since & happens with probability at least - Če - ên we see that the unconditional error the output B(er(h,.)) s cide -Cn/6 + Ce-ên < Ce for some distribution-deeendenn constants c, C C>( 0.
C.5 Sublinear Rates Lower Bound
Theorem C.9. Assume that H C 1)x has an infinite star tree and let R(n) be rate function with R(n) = o(1nn). Then, H. requires rate R(n).
Proof. Let
== U
{T za) ,1, T (0) x {0,1} .... 10.1,...,. {}
OSEE00
24

---

be an infinite star tree. We also fix the learning algorithm hn Recall that {u(n))ner denotes the number of unlabeled samples that hn uses.
We first pick a path on the tree uniformly at random. To be more precise, let 1ī - (31, , y2,...) be sequence of independent random variables where yi uniformly distributed in {0, (0,..... idea is that !/ specifies a random path on the tree. We define the target distribution Pg in an inductive way by specifying sequences {kt, Pt, n: 121121 and putting mass p; on the node of the random path at level kG. Conditional on the given node, we distribute the mass among its points uniformly. Let us now be formal. For the base of the induction,
13. The
let p2 1/2 and kj 1. We will specify the value of p1 later. For the inductive step, for any i 2 2, given the value of pt, k5-1. we will specify k3, Pr+1- We let h; be the smallest integer so that k; > k; and Ra (s/8)) pi/ks Notice that
since R(n) = o11 /n), ka < co. We let = /8] and
min 1
Pi+1
4tn;
4
Notice that since {p- > 03.22 Σize Pi by setting pt -1-E ps the sequence {p: can be used as a probability distribution. We are now ready to define Py on X x {0,1}. make the notation simpler, for any ij and for l 21
j=j= = yk otherwise
w JSk-1
#
2
2
For 2 1, let
(1 ( w
Pi k;
Py Notice that, by the definition of pi, this is indeed probability distribution. We now show that Py is realizable. Since i' star tree, there exists some h HH such that
. 1ssjs k; 1.
BSk-
h (1
Nsk
for all 0 S & k, and S k < n. Thus, for the probability of error of h we have that
(hy(h) = Py [z, v) E X x {0, h(x)) # yl pk
so by taking n - oc we see that py is realizable for every J. Moreover, we note that the mapping ÿ - is measurable.
We now let (X,Y), (X1, Y1), (X2, Y2).... be i.i.d samples drawn from Pg. We can draw them as
X = Y w W X,
Y, ==
where [T, J2), J2).... are i.dd random variables, independent of the path J. with
Pr[T K; 5] =
Pi k;
for all 2 J,0 1 -
For all i E N, let us define the event F = (Ti S T2, Ke, Tun; I kz under which the algorithm has received any unlabeled points from any level kj,j > i. Let also call Ej the event that frg does not query the point whose label is flipped, i.e., the point x -1sk-11' Also, we denote Eg the event that the learner classifies at least one point level k, incorrectly. Then, we have that
Pr[E
(7/8- k.)
since there are at least (7/8) - ks points on this level that the learner has not queried, and under the events we have conditioned the flipped point along the path is chosen uniformly random among these points. We now bound Pr(Ej] Notice that
Σ 1211
Pj S Pit1
Pi 5
<
3
12 Uns
'This is because pi+1 pi/4.
25

---

Thus,
pr[F
2
1
Σ
Pj
12 unn
10
821+1
Finally, we need to bound Pr[Ei] Eg). Notice that
Pr[Ei|E]
8
since the learner has n label queries and there are least 8n points. Putting together, we can bound
Pr[Ea] = Pr[Eg Ej. Egl Pr[C]]Ej Pr[EE]
6
7
9
7 10
27
40
which using reverse Markov's inequality implies that
18
Pr
Pr
Er
Z
40
31
Moreover, notice that
Pr[hn, (X) + Y
Ps
Priea
2 R(n)) Pr[E
ki
Thus, we can see that
Pr Pr(hn. #
YY
>
9
R(m+)
2
18
40
31
Using Fatou's lemma, we have that
min (rihhn (X) Y/M m(n)) }
limsup Pr(h (X) + 1 t-x R(ns)
2 E
sup 1+000
R(n:)
limsup 10000
E
min Pr[hn (X) * YlM 9/400 R(n:)
}
R(n,)
limsup
1
Pr
Pr Pr[hn, Y 2 9/40 R(n.))
9.
R(()))
(+000
R(n.)
40
9
>
40 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 since
min {Pr [i.. [x, (X) * Y1v .9/40- R(n)) s 9/40.
R(n,)
Thus, there must exist realization of such that
Elerg((n.)l0) 2 C R(n):
infinitely often, where C is some absolute constant. Choosing P Py for this realization of concludes the proof.
D
Omitted Details from Section 4
D.1 Useful Tools
Theorem D.1 (Dvoretzky-Kiefee Kiefer-Wolfowizz (DKW) Inequality). Let be the CDF of some distri- bution D supported on IR, E N and F, be the empirical CDF obtained from i..dd samples from D. Then, Ve > 0 have that
Pr
sup Fr (x)
F(x)) < 26-2ne" 2ne²
26

---

Figure 6: The VCL Game (Bousquet al. 2021
VCL Game Subroutine Bousquet et al. 2021): Input is labeled sequence (11,)1).... (IN. UN)}
1. Let To <
In every step t 2 1:
If 17-1166 (51,.... -
= (Vt - Mt):
+l,
Let f--- t- (Ie- +he 21) and T, t- 7t-1 +
Else, f- Tt-1-
D.2 The VCL Game
For completeness, we provide various algorithms and results that appeared in Bousquet et al. (2021) Hanneke al. (2022), which we utilize in our approach to get sublinear learning rates. instructive to start with informal description of pattern avoidance function this function takes as input a k-tuppe of unlabeled data generated by realizable distribution Px and
X + {0, 13 Intuitively,
it returns labeling of these data that is not the true labeling by P. They define
per ()) -P
(Z 2g)) (y1 (/.....,y1)))) 91)]
Bousquet al. (2021) provide way obtain such a pattern avoidance function for any realizable distribution. This is obtained by a VCL game in Figure which returns function V.. Their following result shows that 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 al. 2021 )) Consider the VCL game in Figure 6 Then, Pr(per(ūr.) 0] 0, as N
Finally, we remark that Bousquet et al. 2222)) showed the following result.
Theorem D.3 (Supervised Learning Linear Rates (Bousquet et al., (021)). If TH does not have an infinite VCL tree there exists supervised learning algorithm that can learn H. linear rate.
D.3 Omitted Details of the Sublinear Rates Algorithm
Lemma D.4. Let Fi papss E [V be the partial concept classes that are obtained by playing the VCL game on vn/5 examples that are generated i.idd. from P. Then, with probability at least - e-- C- where C > is some absolute constant, P. is realizable distribution for -fractionnni of these classes.
Proof. Let //ass be the pattern avoidance function that is obtained from the i-th batch of vn/5 i..dd samples from P. Since we know that Pr[per(G,a.t 0] - 0 as n co (cf. Lemma D.2 for any >> there is some be such that the batch size vn/5 is at least bg then Pr[per w//s) 0] << Hence, for every n there is some 5n = =(1) so that when the batch size is vn/5 we have that Pr[per m ( > 0] < En. Notice that whenever per py wo/s) 0 the distribution P is realizable with respect to the corresponding class F Vn/s Let us set 8n 1/8, Using Hoeffding's inequality -l---nn where C' some absolute constant,
we have that with probability at least 1 - C. at least (1 En - 6,)) - -facttinn of the VT/5 will have per = 0. Since 8, + En = =(1) we have shown the claim.
2i
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/10- quantile of P. Then, for 2 np, where np is some P-dependent constant have that a, d". with probability at least distribution P.
-4-x--14 where Cp constant the depends on the geta-ggnnrrtting
27

---

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 be the pattern avoidance function that is obtained from that game defined over l many points and let
f = (f X + fo, 1,
f(zz) + (21......,
Let d' E N be the smallest number such that
Pr(d(F) S d') > 9/10.
Let F' be the CDF of the distribution of the VC dimension of F, let dj < d' < d2 be the largest, small- est n such that F(d1) & F(d"), F(dz) + F(d") and let Cp = min(F(d") -F(("))F((()) F(dz) F(d")) L4.44.et Let F FR be the empirical CDF of the distribution obtained on vn ii.d samples. Notice that whenever we estimate F' with accuracy Cp the empirical 9/ 9/10-quantile will the same as the true 9/10-quantile The DKW inequality (Theorem D.I shows that this happens with probability 1 - 2e 2C Let us call this even E, 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...d. samples from but merely on vn many such samples. Let us consider the following experiment. We run the VCL. game on k streams of infinitely many i.idd samples from P and if the game has not terminated within the first vn 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 o(1) f(1)-fraction of these games will have converged. We call this event Es and we condition on it. Let us denote by Fs the empirical CDF of the VC dimension of the partial concept classes obtained by this experiment. Under E2, we have that supzeN [x) (z)) o(1). Thus, by taking n large enough so that the o(1) << Cp, we see that the estimation of d,, 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 E2.
-- 1/4
we will only rewind the pattern avoidance function of a
Proposition D.6. For n > np, where np is some distributtion-deendeen constant, given m = On1)) unlabeled samples
(X.g) with accuracy o(1), with probability at least estimate Pn,ks PX, Pa,k
1 C-Cp. e C/pl// where Cp, Cp > 0, are distribution-depeedennt constants.
Proof. As we alluded to before, using O(n²) unlabeled samples in total we can estimate the quan- (X.z) with accuracy L/n for each version space V with probability at least 1 Civne C2v7 where C₁,C2 > O, are absolute constants. Let denote these estimates Pn,ke: Po,k, Pn. Pn.k.i We condition on this event for the rest of the proof.
tities Prik pix Pn.k,,sPP,k
(X.a)
Assume that is large enough and condition on the events of Lemma D.4 Lemma D.5 Let us denote by i1...., the indices of the partial concept classes whose VC dimension is bounded by d, = d' By definition, h 2 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 version space on the first n/5 samples of 53. Let us call 7 the version space obtained by the i-th sample of this experiment. Then, p*
VC shattered by V7) is an unbiased sample from the distribution whose expected value Pn,, we are trying to estimate, Similarly for the rest of the quantities we have defined. Let us call these samples k P. Ph.kk.tP
x(Xay) and denote by Sn, 5XX (xx,) their empirical estimates over 9/10// many samples. Hoeffding's inequality gives us that S.S,- Po,k = o(1), |5 p. o(1), 15 x(),)) Pn,k p.x-0) = o(1), with probability at least Ce 2/4 for some absolute constants C² > O. We condition on this event.
(X.) Notice that, under the events have conditioned on, the samples Pu,k,is Pn.k, Pa,k. obtain from running the VCL game on OV)n)) T2) many samples, differ from the samples Pn. Ph k Po,ka
x
x)
If only one these number exists, then we ignore the one that does not exist in the definition of Cp. none of these numbers exist then the estimation task is trivial.
28

---

on sublinear number of terms. Moreover, the absolute difference on the terms they disagree on bounded by Thus, denote by Sny SX :Sn g(X.y) the average of these values we have that n averages of Pr,k. P. kn, PakKi
s Snl = = 5
((1),155 ((). 5 = =(1). Finally, let S., Sx ((x.2) be the ((x)) Since Pn,,,. Po, o(1), F P o(1), Pr,k,
(X..) o11, using the triangle inequality on all the previous estimations we see that |S,t - Pn,kl Pn.k.
o(1), S Pr. = o(1), (St
- -Pn,k (xxxa) o(1), with probability at least - Cp e Gi,nl/4
Lemma D.7. Let n > Csgo, where Csp is some constant that depends on S2 ,P. Then, with proba- bility at least Cp -- for every every K S k", if Pa then y = argmax (e(0)) Pa,k
((xa)
the correct label X. X.
Proof. Let n > Oss be large enough so that for all & S k* we have that:
Pn,k I 100/99
lim P n-
the guarantee from Proposition D.6
gives that
Pu.k
3
Pn,
Pn,
4 Pn,
2
and
Pn,k
(X.y)
99
Pn.k
x(X.v)
2
95
Pu.k
100
100
(N.))
80
((.))
90
Po,k 100 Pu.k
Pa,k
100 Pn,k-
We condition on these events for the rest of the proof. Since Pa,k S 100/99 limm, Pn,K for the
correct label y" have that (x,")) pxxaa > 99/100 Pn.k. Moreover, since P, < 3/4. Pn, for the other
label y² holds that p (x9) 80/100- Pr,k- Thus, under the event have conditioned
on have that argmax, (0.1) P (x,))
will indeed be the correct label. The correctness probability
follows directly from Proposition D.6
Puga=] Lemma D.8. For ks = K- we have that Pr Pr. 2
o(1).
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 2 P.,.- Pa.k' so it suffices bound Pi,k- 4
Pr x
Pu.
2
4
Using Markov's inequality, we have that
4 E p.x
Pr 1 2
Pr,k
4
Pu.k-
4p
Pn,k-
=(())
where we have used the fact that Elpxx = P and that Pr.k is bounded below by a constant.
29

---

We now state the guarantees of ActiveSelect (Hanneke) 2012). We note that the original statement of the result did not specify the size the unlabeled dataset that the algorithm uses, but straightforward adaptation of it shows that with (nn²) many unlabeled data its enror guarantee changes increases by O(1/n²).
Lemma D.9 (Hanneke (2012). A call ActiveSelect (cf Figure 8 with N classifiers (h1s--.. h }. a query budget of m, and (NN2 /n²) unlabeled points makes at most m label queries and if lig the classifier returns, then with probability at least er(1 er(Ngg S minke[N] er(ha) + O(1/n²).
C₁ Ne C2/m/(N² log(N)), we have
are now ready prove the main result in this section. The algorithm summarized in Figure 7 Theorem D.10. Assume that H S {0, 1,x² does not have an infinite VCL tree. Then, admits an active learning algorithm that achieves sublinear rates.
Proof. We have all the main ingredients we need prove our result. Let us fix some S whose elements are i.i.d. from P. Conditioning on the results of Lemma D.7] Lemma D.8 we have that for large enough n, which depends on S we can obtain labeled dataset L,, whose size is (n)..
Feeding this dataset into the supervised learning algorithm from Bousquet et al. (202T) gives as classifier hn that, conditioned on 2 and the events E we have described, has error
Eler(hn)) F = o(1/n).
Moreover, probability of E is also o(//n), so we get
E(er(hn))S?? o(1/n).
Similarly, for the output h of ActiveSelect, we have that
(hx) ST o(1/n) E E(er(T..)] = (11n),
where the second bound comes from the fact that we feed into ActiveSelect the output of the passive learning algorithm hg from Bousquet et al. (2021) (cf.. Theorem D.3 whose bound does not not depend on S
Let us call R(n) the error rate of our algorithm. To show that E E[R(n)) = o(1n) it suffices to prove that lim sup, E(n- R(n)] 0. Fatou's lemma gives us that
lim suspum R(m) lim sup El R()) n=
n-
lim sup
E [B|n R(n)
n-
ST
< E [im sups E [5]]
n=+00
where Fatou's lemma applies since E[n R(n) < Op where Cp is some P P-dependem constant. This is because, almost surely S the expected enror of hg is bounded by Cp/nn
D.4 Arbitrarily Slow Rates Lower Bound
Theorem D.11 (Hanneke et al. (2022)). If H. has an infinite VCL tree, no active learning algorithm can achieve rates that are faster than arbitrarily slow.
D.5 Omitted Figures
30

---

(X. Figure 7: Sublinear Rates Algorithm.
Sublinear Rates Algorithm [Adaptation from Hanneke [0012) Input is label budget N and a passive learning algorithm Ap
1. Let S2, S3, S4, Ss, U be sets of O(N*) unlabeled points that are i..d. from Px.
2. Request the labels of the first N points of S and run Ap on this set. Let Ry be its output.
Request the labels of the first N/5 points of Si, split them into batches of size O(VN) and run the VCL game on them (cf. Figure 6).
4. Let T / [VN], be the pattern avoidance functions from the previous step and for every E [vN] define
F /N/S = {::x (0,1)),,,) (f(r)),...... ((0 +
(. tt UNio
Let
āy = min deN
19/10.07 301 iz 15/102....../100. [VN]
i < is <
b 9/100 v
d(F))
/
VN
S
<dvjj
[9/10VN]
6. Request the labels of the first N/5 points of S and let
Vays FEEFNNSS f(x) for these N/5 point
7. For k = 0. 0....,,d dx:
(a) Let Sy be the next n examples in Sy and my = N/(5(dx + 1)) be the label budget.
(b) Let S =}
(c) For each point X E Sz E (0,1):
i. Estimate PN,A, PN PN.K using V/5 and fresh unlabeled points from U described in Proposition
(X.9)
ii If PN S PN,N/2 infer y argmax 1E(0,1) PN. otherwise request the label y/" of X. ii.. Append (X,y", S and update the label budget my. If my 0 jump to Step (d).
(d) Run Ap on 3 and let hig be its output.
8. Return ActiveSelect (fho.... Ju,, n NN/5, S1) (cf. Figure 81.
31

---

Figure 8: ActiveSelect Algorithm (Hanneke 2012).
ActiveSelect (Hanneke 2012) Input is a set of classifiers {hi..... h label budget m, sequence of unlabeled examples U.
1. For each j. k E N1....,N) s.t. j < k: J[L 3) In(eT)
(a) Let Rys the first
points in un {x hy(x) + hx(x)) (if such
value exists).
(b) Request the labels for Ryk and let Qjk be the set of labeled examples.
(C) Let maj = erq, (hx).
2. Return hg. where = max (k E {1...., L.J. : maxjek maj S 7/12).
32

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: The main body and supplementary material of the submission provide proofs for all the claims.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
is fine to include aspirational goals as motivation as long as is clear that these goals not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations the work performed by the authors?
Answer: [Yes]
Justification:
We formally define the mathematical model our results hold for.
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create a separate "Limitations" section their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is low images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't 't acknowledged judgment and recognize that individual actions in favor of transparency play impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
the paper. The authors should use their best
3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
33

---

Justification:
We present full proofs in the main body and the supplementary material.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated referenced in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but they appear in the supplemental material, the authors are encouraged to provide short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental Result Reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that affects the main claims and/or conclusions of the paper (regardless whether the code and data are provided or not)?
Answer: [NA]
Justification:
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution is a specific model and empirical evaluation, it may be necessary to either make possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g.. in the case of large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) the contribution is primarily a new algorithm, the paper should make clear how to reproduce that algorithm.
(b) the contribution is primarily a new model architecture, the paper should describe the architccture clearly and fully.
(c) If the contribution is new model (e.g., a large language model), then there should either way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome to describe the particular way they provide for reprodueibility. the case of closed-source models, may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
34

---

Answer: [NA]
Justification:
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please the NeurlPS code and data submission guidelines (https://nips... cc/
pub / gui Codeeuumie ss ssionn cisionnolicc
for more details.
While we encourage the release of code and data, we understand that this might not be possible, so "No" an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https //nips. cc/ wwwpiictguiiiooooooo / /eddiddee//deeeeeeee CooeeeeeeeSeeeeeee CoddeSumieeeee Submiss wwwssssoiiiigg.e.. for more details.
The authors should provide instructions on data access and preparation, including how access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [NA]
Justification:
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, or as supplemental material.
7. Experiment Statistical Significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer: [NA]
Justification:
Guidelines:
The answer NA means that the paper does include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, statistical significance tests, at least for the experiments that support main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call a library function, bootstrap, etc.)
The assumptions made should be given (e.g.. Normally distributed errors).
should be clear whether the error bar is the standard deviation the standard error of the mean.
35

---

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 96% CI, if the hypothesis of Normality of enrors is not verified.
For asymmetric distributions, the authors should be careful to show in tables or figures symmetric error bars that would yield results that are out of range (e.g. negative eтror rates).
If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of exccution) needed to reproduce the experiments?
Question:
Answer: [NA]
Justification:
Guidelines:
The answer NA means that the paper does include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, cloud provider, including relevant memory and storage.
The paper should provide the amount compute required for each of the individual experimental runs well 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 failed experiments that didn't make into the paper).
9. Code Of Ethics
Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics
Question:
Answer: [Yes]
Justification:
Guidelines:
The answer NA means that the authors have reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., there a special consid- eration 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 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.
36

---

The conference expects that many papers will be foundational research and not tied particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology being used intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there 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 monitor how system learns from feedback over time, improving the efficiency and accessibility of MI..
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification:
Guidelines:
The answer NA means that the paper poses such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere usage guidelines 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 best faith effort.
12. Lieenses 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 existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (c.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (c.g., website), the copyright and terms of service of that source should be provided.
assets are released, the license, copyright information, and terms of use the package should be provided. For popular datasets, papers thcode com dataaetteett has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
37

---

If this information is not available online, the authors are encouraged to reach out to the asset's 's creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification:
Guidelines:
The answer NA means that the paper does not release new assets,
Researchers should communicate the details of the dataset/code/moodl as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification:
Guidelines:
The answer NA means that the paper does not involve crowdsoureing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According the NeurIPS Code of Ethies, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification:
Guidelines:
The answer NA means that the paper does involve crowdsourcing research with human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurlPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
38


Reviews:
[{"review_id": "MU3OPGvrBn", "reviewer": "Reviewer_aq73", "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.", "questions": "Besides the comments above, can author provide analysis on the computational aspects of the developed/studied active learning algorithms?", "limitations": "N/A", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 4, "strengths": "The authors provide a complete characterization of the optimal learning rates for non-adaptive active learning algorithms: arbitrarily fast, exponential, o(1/n), and arbitrarily slow. These results answers an open question by Balcan et al. 2010.", "weaknesses": "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?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We would like to thank the Reviewer for their detailed feedback. Please find our answers to your questions below.\n\n> 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?\n\nWe would like to clarify that the non-adaptivity assumption is on the number of *unlabeled* examples that the algorithm requests. In particular, at the beginning of the execution, the algorithm specifies an arbitrarily large number of unlabeled examples that it will use. For example, this number could be $e^{e^{e^n}}$, where $n$ is the number of label queries it has (or something even larger than that). The label requests that the algorithm makes are indeed adaptive, and can depend on the unlabeled examples as well as the answers to previous label requests. Moreover, the only part of our characterization that relies on that assumption is the lower bound for the $o(1/n)$ rates. We believe that this is a mild assumption to make, since it still allows for the *label requests* to be done *adaptively*, and we place no upper bound whatsoever on the number of unlabeled examples it can request at the beginning of the execution. Furthermore, we believe that a construction similar to the one we use in our lower bound can also be used to handle the case where we do not place any such restrictions on the type of access to the unlabeled examples, but the technical details get more involved. \n\nTo give some more concrete examples, the well-known CAL algorithm of Cohn, Atlas, Ladner [1] or the Activized Learning algorithm of Hanneke [2] can be slightly modified to fit within our model by specifying a sufficiently large number of *unlabeled* examples that they need at the beginning of the execution.\n\n\n[1] Cohn, D., Atlas, L. and Ladner, R., 1994. Improving generalization with active learning. Machine learning, 15, pp.201-221.\n\n[2] Hanneke, S., 2012. Activized learning: Transforming passive to active with improved label complexity. The Journal of Machine Learning Research, 13(1), pp.1469-15\n\n> Besides the comments above, can author provide analysis on the computational aspects of the developed/studied active learning algorithms?\n\nThis is an interesting question. The computational complexity analysis depends on the type of access we have to the underlying hypothesis class. Our main goal in this work is to come up with approaches that give the optimal rates with respect to the sample complexity of this problem, which is always the first step to understanding the computational complexity. In their current form, our algorithms are not computationally efficient, but we hope and believe that they will inspire computationally efficient approaches that work for, potentially, restricted classes and data-generating distributions.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "RZbqhygz3y", "reviewer": "Reviewer_CFsL", "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.", "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.\n\nThe $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?\n\nDo 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": "See questions.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "A strong paper with deep results further continuing the line of work on universal learning, this time active learning. This work nicely complements the \"universal rates of interactive learning\" paper where general queries are studied, while here only more common label queries are allowed.\n\nThe star number based modification of VCL trees is nice and natural.", "weaknesses": "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.\n\n--- rebuttal update ----\nraised from 5 to 7.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We would like to thank the Reviewer for their detailed feedback. Please find our answers to your questions below.\n\n> Intervals and Balcan et al. [2010].\n\nThis is a good point to clarify. Balcan et al. (2010) distinguish between the *true* query complexity and the *verifiable* query complexity of a learning task. The $\\Omega(1/\\varepsilon)$ query lower for learning intervals under the uniform distribution you refer to holds for the *verifiable* query complexity, not for the *true* query complexity, which is the definition we consider in our work (and in prior works in universal rates). \n\nThe *verifiable* query complexity refers to the number of queries needed to both produce an $\\varepsilon$-good classifier *and* prove that its error is no more than $\\varepsilon$ (with high probability). The *true* query complexity refers to the number of queries needed to only output such an $\\varepsilon$-good classifier. \n\nMore formally, for a given $\\mathcal{H}$ and marginal distribution $\\mathcal{D}$ over $\\mathcal{X},$ a function $Q(\\varepsilon, \\delta, h^*)$ is a *verifiable* query complexity if there exists an algorithm $A(n,\\delta)$ that outputs a classifier $h_{n,\\delta}$ and a value $\\hat \\varepsilon_{n,\\delta} \\in (0,1)$ after making at most $n$ label queries, so that for any target labeling function $h^* \\in \\mathcal{H}, \\varepsilon, \\delta \\in (0,1)$ and for any query budget $n$ it holds that $\\Pr[\\mathrm{er}(h_{n,\\delta}) \\leq \\hat \\varepsilon_{n,\\delta}] \\geq 1-\\delta,$ and for any $n \\geq Q(\\varepsilon, \\delta, h^*)$ it holds that $\\Pr[\\mathrm{er}(h_{n,\\delta}) \\leq \\hat \\varepsilon_{n,\\delta} \\leq \\varepsilon] \\geq 1-\\delta.$ \nThe definition of *true* query complexity reads the same way, except now the algorithm is *not* required to output $\\hat{\\varepsilon}_{n,\\delta}$. To illustrate how this subtle difference can have a big impact on the query complexity, consider learning intervals over $(0,1)$ under the uniform marginal distribution, and let us ignore the dependence on $\\delta$ for simplicity.\n\nConsider two cases: first assume that the target interval is the empty one. Then, there is a learning algorithm that needs 0 queries to learn a $\\varepsilon$-good classifier (in fact, a zero error classifier). On the other hand, if the target interval has width $w > 0$, there is a learning algorithm that learns an $\\varepsilon$-good classifier needing $O(1/w + \\log(1/\\varepsilon)) = O(\\log(1/\\varepsilon)) $ queries using the following strategy: initially the algorithm queries points uniformly at random until it finds some point $x^*$ that has label +1 (this will take roughly $1/w$ many queries) and then does binary search on the two intervals $[0,x^*], [x^*,1]$ to find two $\\varepsilon$-approximate endpoints of the target interval, which requires $O(\\log(1/\\varepsilon))$ many queries. Thus, overall the strategy to learn an $\\varepsilon$-good classifier for all target intervals is the following two phase approach: start querying points uniformly at random until either a point with label 1 appears, or the query budget runs out. In the former case, proceed to the “binary search” phase, otherwise output the all zero classifier. The previous argument shows that the *true* query complexity of this algorithm is $O(\\log(1/\\varepsilon))$.\nLet us now consider the *verifiable* query complexity. If the target interval is the empty one, then for any given query budget $n$, the previous algorithm (and in fact, any algorithm) can only guarantee that its error is at most $O(1/n)$ (with high probability). However, if we consider its learning curve for all different values of $n$, we will observe an exponentially fast decay no matter what the target interval is, which is exactly what the definition of universal rates is capturing.  \n\nFor a more formal discussion of the two definitions of sample complexity, we kindly refer you to Definition 1, 2 of Balcan et al. (2010) and the subsequent discussion in their paper. \n\nPlease let us know if this clarifies your concern.\n\n> Attias et al. (2024).\n\nAttias et al. [COLT 2024] show that there *exists* a class for which $o(1/n)$ rates are tight in the setting of regression. In our work, we give a *complete characterization* of the classes for which $o(1/n)$ rates are tight in the context of active learning for binary classification. Moreover, their result shows that a class cannot be learned at a rate faster than $o(1/n)$  when it has an infinite (scaled version of the) Littlestone tree, whereas our result shows that a class cannot be learned at a rate faster than $o(1/n)$ when it has an infinite star tree.\nFurthermore, the reason that the $o(1/n)$ rates appear in our work and the $o(1/n)$ rates appear in Attias et al. [COLT 2024] are fundamentally different. In a nutshell, we get $o(1/n)$ because when the class has only finite VCL trees the probability that our algorithm queries the label of an unlabeled point is decreasing as $n \\rightarrow \\infty$, and we can make correct inferences of the labels of the points we do not query. This allows us to get a set $S$ with  $|S| = \\omega(n)$  correctly labeled points, and then train a supervised learning algorithm on these points, which has error $O(1/|S|) = o(1/n)$. In the construction of Attias et al. [COLT 2024], they get $o(1/n)$ rates because the magnitude of the errors they make on unseen points decreases, in expectation, as $n \\rightarrow \\infty$. \nWe will add a discussion comparing the two works in the next version of our paper. \n\n> High-prob. bounds.\n\nStudying high-probability bounds in the universal rates setting is an interesting direction. So far, all the works on universal rates have focused on establishing bounds that hold in expectation, in order to provide a cleaner characterization of the landscape of the optimal learning rates. It is an interesting future direction to see for which regimes the dependence on $\\delta$ can be fully removed; for instance, for arbitrarily fast rates this is immediate.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "mb1BfApbYn", "reviewer": "Reviewer_cBhF", "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.", "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": "Yes", "rating": 8, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "This work presents an important contribution to a recent line of work on universal rates which includes similar characterizations in the passive and interactive learning settings. It naturally generates comparisons to the \"rate partitions\" in the passive and interactive settings given in prior work. The authors introduce a new complexity measure which serves to distinguish hypothesis classes for which the more powerful interactive querying model admits faster universal rates than the standard active learning model, as well as to distinguish hypothesis classes which admit exponential universal rate speed-up over passive learning. Given that the search for settings where active strategies can yield an exponential speedups over passive learning has long been a primary focus in the field of active learning, this seems to me to be a noteworthy contribution.", "weaknesses": "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.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We would like to thank the Reviewer for their detailed feedback. Please find our answers to your questions below.\n\n> 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.\n\nThank you for the suggestions. If the paper gets accepted, we will certainly make use of the extra space to polish the presentation of pages 8-9 and bring the context of Appendix A.4 to the main body.\n\n> 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 $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?\n\nThank you for your question. Our work aims to understand the fundamental capabilities and limitations of the active learning setting itself.  We do not aim to explain phenomena which may have been observed for specific heuristic active learning methods which have been applied in practice.  This is also an interesting subject, worthy of a separate study.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: The reviewers are unanimous that this is an interesting work shedding light on the possible types of learning curves in active learning.
Decision: Accept (poster)