Universal Rates for Interactive Learning
Authors: Steve Hanneke
Amin Karbasi
Shay Moran
Grigoris Velegkas
Venue: NeurIPS 2022 Accept (2022)
Keywords: interactive learning
universal learning rates
learning theory

Abstract: Consider the task of learning an unknown concept from a given concept class;  to what extent does interacting with a domain expert accelerate the learning process? It is common to measure the effectiveness of learning algorithms by plotting the "learning curve",  that is, the decay of the error rate as a function of the algorithm's resources (examples, queries, etc). Thus, the overarching question in this work is whether (and which kind of) interaction accelerates the learning curve. Previous work in interactive learning focused on uniform bounds on the learning rates which only capture the upper envelope of the learning curves over families of data distributions. We thus formalize our overarching question within the distribution dependent framework of universal learning, which aims to understand the performance of learning algorithms on every data distribution, but without requiring a single upper bound which applies uniformly to all distributions. Our main result reveals a fundamental trichotomy of interactive learning rates, thus providing a complete characterization of universal interactive learning. As a corollary we deduce a strong affirmative answer to our overarching question, showing that interaction is beneficial. Remarkably, we show that in important cases such benefits are realized with label queries, that is, by active learning algorithms. On the other hand, our lower bounds apply to arbitrary binary queries and, hence, they hold in any interactive learning setting.

Universal Rates for Interactive Learning
Steve Hanneke
Amin Karbasi
Purdue University steve www.:ennnnnneemmalccomm com
Yale University, Google Research
amin. karbas cerrbasi@yylleeeee edu
Shay Moran Technion, Google Research smoran@technion. ac
Grigoris Velegkas
Yale University grigoriss.elegkaseee edu
Abstract
Consider the task of learning an unknown concept from a given concept class; to what extent does interacting with domain expert accelerate the learning process? It is common to measure the effectiveness of learning algorithms by plotting the "learning curve", that is, the decay of the error rate function of the algorithm's resources (examples, queries, etc). Thus, the overarching question in this work is whether (and which kind of) interaction accelerates the learning curve. Previous work in interactive learning focused on uniform bounds on the learning rates which only capture the upper envelope of the learning curves over families of data distribu- tions. We thus formalize our overarching question within the distribution dependent framework of universal learning, which aims to understand the performance of learning algorithms on every data distribution, but without requiring single upper bound which applies uniformly to distributions. Our main result reveals a fundamental trichotomy of interactive learning rates, thus providing complete characterization of universal interactive learning. As a corollary we deduce strong affirmative answer to overarching question, showing that interaction is benefi- cial. Remarkably, we show that in important cases such benefits are realized with label queries, that is, by active learning algorithmss. On the other hand, lower bounds apply to arbitrary binary queries and, hence, they hold any interactive learning setting.
Introduction
In supervised learning. arguably the most commonly studied variation of machine learning, we consider a learning algorithm that is typically given access a training of labeled examples, sampled from an unknown distribution. Based on this training set, the goal of the algorithm is to learn to output concept/function that maps data points to labels that the probability of making mistake on unseen (unlabeled) data, drawn from the same distribution, is minimized. However, this passive setting does not capture lot of applications data where labels are not readily available but the learner can interact with the domain expert (such human annotator) acquire more information about the data. Consider, for example, the task of email spam filtering. Service providers, such as Google, have easily access to billions of emails. However, obtaining labels (i.e., spam or not) usually requires human to read the content of those emails, a process that is quite costly. One way to model such tasks is through the interactive learning framework where the learning algorithm is given access unlabeled examples from which can then submit n queries to an expert in order to gain information about these examples. Such queries may include, but are not limited to, asking the labels of those
which there is an abundance unlabeled
large (potentially infinite) stream of
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

examples (e.g., is this email spam?) or comparing examples with one another (e.g., between these two emails which one looks more like spam?).
In this paper we would like to understand to what extent interacting with an expert who knows the target concept can accelerate the learning process. It is common measure the effectiveness of passive supervised learning processes by plotting the "learning curve", that is, the decay of the error rate as a function of the number of training examples. Analogously, for interactive learning algorithms one measures the decay of the error rate as a function of the number of queries the algorithm submitted the domain expert. The setting in which the learner is limited to asking label queries is called active learning. The overarching question in this work is whether (and which kinds of) interaction accelerates the learning curve?
Previous work on interactive learning has given rise to a large collection of general theories
KMT93
Das05 BBL009 [an007b] [Han07a DHM07 Handy YHCIO BH2 Han14 HY15
BHLZI6 KLMZ17 establishing guarantees on the error rate as a function of the number of queries of various types. However, most of these theories are primarily concerned with capturing a uniform (i.e., minimax) guarantee on the rates of convergence: that is, error bounds holding in the worst case over some family of distributions Even though these theories give rise a clean and elegant mathemati- cal framework, they do not fully explain the behavior of learning curves: due to the minimax nature of the guarantees they consider, they can only capture the upper envelope of the learning curves over a family of data distributions. The minimax perspective does not match practical and experimental machine learning. where the target distribution fixed and the number of training examples and queries varies according to the learner's 's resources and desired accuracy [CT90 CT92). In contrast, in order to observe the learning curve that corresponds to uniform/ninimax guarantees one would have to vary the data- generating distribution as the constraint on the number of queries the learner can make increases. We therefore formalize our overarching question within the distribution dependent framework of universal learning [BHM 221, a framework designed to understand optimal rates of convergence for learning curves. This framework aims to understand the best possible asymptotic rate of convergence that can hold for every data distribution, but without requiring
upper bound
which upplies uniformly to all of these distributions. While there have been a few past works to study universal rates for the special case of active learning (i.e., label queries) [BHW08 Han 2 YHE none have yet provided a complete characterization, and none have considered more general forms of interactive learning.
The main result of this paper is a complete characterization of universal interactive learning rates, for learners able to make arbitrary yes/no queries. Specifically, for such learners, we prove there is a fundamental trichotomy of possible optimal universal learning rates: any given concept class has an optimal rate decaying at either (i) arbitrarily fast rates, (ii) exponential rates, or (iii) arbitrarily slow rates. Moreover, the optimal rates for classes of type (i) can be attained by learning rules whose interaction is restricted to querying the labels of points in the (unlabeled) input sample. In other words, active learning with arbitrarily fast rates is possible for a variety of classes including, and rather surprisingly. for some classes with infinite VC dimension.
Furthermore, we pinpoint complexity measures to precisely categorize any concept class into one of the above three categories of optimal rate. Indeed, since these same complexity measures were also found by 2BHM+21 to characterize a trichotomy of rates for passive supervised learning, our results are directly comparable, and reveal strong benefit from interactive learning: namely, classes with optimal rate 1, for supervised learning have optimal rate e - for interactive learning (category ii), while classes with optimal rate e for supervised learning have optimal rates that are arbitrarily fast for interactive learning (category i).
In addition to these strong positive results, including for learning with simple label queries. we also note that our lower bounds on the achievable universal rates are quite powerful, as they apply to any interactive learning setting with binary- valued responses: for instance, in addition to label queries and general membership queries, they also apply to learners based on comparison queries [KLMZ17.
'To be clear, while many of these theories express distributionn-eeeendent guarantees, the guarantees are typically formulated with the intent of matching some kind of lower bound on the minimax performance over a family of distributions subject to some parameter value (c.g.. disagreement coefficient). For instance, most of these results involve factor based on the VC dimension or covering numbers, both of which could be unbounded, even in the most-favorabee scenarios discussed in the present work. As result, the craribttionddppedder guarantees in these works do not capture optimal universal rates.

---

We define an interactive learning algorithmn to be a sequence of universally measurable functions which, given access to an infinite stream of unlabeled data points from X' that are drawn i.i.d. from Px and a query budget n. output a classifier hn X' {0, 1}; we restrict the algorithm to depend on only a finite (though unbounded) number of the i.i.d. unlabeled examples, The goal this algorithm Finally, novel algorithmic principles arise from our universal interactive learning framework. Recall that passive learning in the distribution-Fri free PAC setting boils down to the Empirical Risk Mini- mization (ERM) principle via uniform convergence. Analogously, traditional interactive learning gives rise to simple querying policies such as the disagreement-based CAL algorithm [CAL99]] algorithm for label queries (which queries the labels of points that are uncertain), or general binary search strategics in cover of the class [КМиЯ in the case of general yes/no queries. Similarly to the ERM principle, these strategies achieve near-optimal distribution-fiee uniform rates, for their respective types of queries. and the design of learning algorithms able to achieve the optimal rates requires great care. Indeed, the learning rules we use to prove our main results rely on techniques only recently introduced to the learning theory literature,, such Gale-Stewart sequential games and adversarial online learning with infinite ordinal-valued I Littlestone dimensions [GS53 BHM Thus, the universal learning setting motivates the development of richer variety of algorithmic techniques.
contrast, in the universal setting the algorithmic landscape is richer
Uniform vs. Universal Rates. To make the distinction between uniform and universal rates more concrete, we first recall what uniform learnability means. (The notation will be introduced formally below.) A concept class H is uniformly learnable rate R(n) if there exists learning rule h. such that
(3C, 0) (vP E RE(H)) it holds that E[er(h.)] & CR(cn), Vn E.
In words, there exists learning rule h. and distribution-indeeendenn constants C, 0 so that for every realizable data-generating distribution P E RE(H) the expected error of the classifier E []er(h,,)] is bounded by CR((en.. The definition of universal learnability is obtained by a simple rearrangement of the quantifiers of the previous definition. concept class H is universally Iearnable at some rate R(n) there exists a learning rule h, such that
(vP E RE(H)) (3C, >> 0) such that E(er(h,)) S CR(Cn), Vn E.
Importantly, this subtle change in the definition allows the constants C, to be distribution- dependent. As is evident from our main result below, this, seemingly minor, change makes the landscape of the admissible learning rates of interactive learning algorithms vastly different.
1.1
Main Results
We next present the key definitions and summarize the main results of this work.
The learning problem consists of domain X, where assume X' to be a Polish space, and non- empty concept class H C (0, 1)x² We assume that HI satisfies standard measurability assumptions (see Appendix A.
classifier is a universally measurable function h h: X + {0, 1}. whose error rate is defined to be er(h) = er (h) == P((z, y) h(x) # y}. where P is probability distribution over X' x {0, 1). We say that is realizable with respect to if inf er(h) = O. We denote with Px its marginal distribution on X.
is to come up with classifiers whose expected error [(er(h,,)] decays as fast as possible as a function of the number of queries
The aim of this paper is to characterize the learning rates achievable by learning algorithm in a general interactive setting, where the algorithm can ask arbitrary binary-valued queries: i.e., any yes/no questions. These include, but are not limited to, label queries and comparison queries for data points, membership queries for any x E X, or any other query having binary answer. The formal abstraction for this notion of query is provided Appendix A.
We now formalize the notion of achievable learning rates in the universal learning model
BHM 21
Definition 1. BHM+21 Fix a concept class THI and let R + [0, 1), R(n) "=3 be a rate function.
3

---

H is learnable at rate R if there is a learning algorithm hn such that for every realiz- able distribution P, there exist distributiondeppeddent C' > 0, for which E(er(h.)) s CR(cn), Vn E N.
H is not learnable at rate faster than R if for all learning algorithms hn there exists realizable distribution P and e, C'> for which Eler(h,)] 2 CB((n)), for infinitely many
n E
H is learnable with optimal rate if it is learnable at rate R and is not learnable at rate faster than R.
H admits arbitrarily fast rates for all rate functions R, it is learnable at rate R.
H requires arbitrarily slow rates if for all rate functions R, is not learnable at rate faster than R.
It is known that, unlike the PAC model, in the universal learning setting every concept class IHT is learnable [Han21 HKSW2T
BHM 21]. Nevertheless, H might require arbitrarily slow learning
rates in some cases DGL9 While most of the above definitions parallel the definitions from the work of BHM*21 on supervised learning, the case of arbitrarily fast rates is new to the present work. While technically it would also arise in passive learning in the trivial cases of [[H]] = 1 or HI = (h. 1 h.. arises as a highly non-trivial and important case in interactive learning, with many interesting classes, even of infinite cardinality. Moreover, our proofs establishing arbitrarily fast rates develop a novel active learning technique (based purely on label queries).
We are now ready to state one of the main results of this work: fundamental trichotomy of optimal learning rates. That is, we show there are three possible optimal learning rates that class HI can admit in the interactive learning setting.
Theorem 1. For every concept class HI, exactly one of the following cases holds.
HH is interactively learnable with arbitrarily fast rates.
HH is interactively learnable at an optimal rale e
HH requires arbitrarily slow rates for interactive learning.
Our next result characterizes exactly when these rates occur by specifying combinatorial measures of H. that give rise to each one of these cases, Before we state this result, we need to discuss these combinatorial measures. We refer the reader to Appendix A.2 for the formal definitions. We first describe infinite Littlestone trees, which were introduced in BHM (Finite versions were studied previously by [it88)
Definition 2 (Informal (see Definition 5).. A Littlestone tree for H C {0, 1]x is complete binary tree of depth d S do whose nodes are labeled by elements of X and the edges to the left, right child are labeled by 0, 1, respectively. We require that for every level 0 S n < d 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 has an infinite Liutlstone tree it has Littlestone tree of depth
For some intuition, we refer the reader to Figure Ta We remark that this notion closely related to the Liulestone dimension of H.. The Littlestone dimension is defined to be the largest d E N such that H has Littlestone tree of depth d and it is oo if there are Littlestone trees of arbitrary depth. However, this does not necessarily imply that there is a single tree whose depth is infinite, so having infinite Littlestone dimension is not the same having an infinite Littlestone tree.
We next discuss the notion of a VCL tree introduced by 2HM++11.
Definition 3 (Informal (see Definition 5). A VCL tree for H C 13x is a complete tree of depth S Do such that every level S n d has nodes that are labeled by x=+1 with branching factor 2 and whose 2 edges connecting node to its children are labeled by the elements of (0, 1 1) We require that for every node at any finite level S n S d, the path from the root to this node is realized by some h E H. We say that H. has an infinite VCL. tree if it has a VCL tree of depth = co.
For a pictorial representation of VCL tree, we refer the reader to Figure Tb Intuitively, the difference between a Littlestone tree and VCL tree is that in the latter, the size of the nodes is increasing

---

BA N.
ROXf.a)) RERT mo) Merfcl
(rim the.
19- (-8 tho tha
20
31 E :
101
h(za)
10
M(x1)
18
b(r10)
(a)
(h)
Figure 1: (a) A Littlestone tree of depth is illustrated. (b) A VCL tree of depth 3 is illustrated. Figures are reproduced from [B with permission.
linearly with the depth of the tree and the branching factor is increasing exponentially. Recall that in Littlestone tree both quantities are constant. Intuitively, as move further down the VCL tree along any path, the class Iil needs to be able to shatter sets of increasing size, while respecting label constraints imposed by all previous levels of the path.
We now state our characterization on the optimal rates achievable by interactive learning algorithms.
Theorem 2. For every concept class H. the following hold:
If IH does not have an infinite Littlestone tree, then it is interactively learnable arbitrarily fast rate.
If has an infinite Littlestone tree but does not have an infinite VCL tree, then it interactively learnable with optimal rate e"h
If H. has an infinite VCL tree, then it requires arbitrarily slow rates.
The proof of this theorem is divided into two parts. Appendix B we provide the bounds relating to
we prove the bounds relating to VCL trees. It is easy see that Littlestone trees and in Appendix C
Theorem implies Theorem 0
We remark that when the learner has access to Px and not just to an infinite stream of i.idd data from it, then we can improve the first rate of the trichotomy.
Remark 1. the learner has access to the marginal distribution Px and H. does not have infinite Littlestone tree, then
achieve E[er(k,,)] = 0, after fintt (P-dependent) number E N.
As mentioned above, the algorithm which achieves the arbitrarily fast rates requires only label queries, which are, arguably, the simplest type of queries: that is, queries that select any unlabeled example X; from the i.i.d. stream and request the target concept's label for X,, Hence, this result applies to the traditional active learning setting.
H does not have infinite Littlestone tree, then there exists algorithm that achieves arbitrarily fast rates using only label queries.
Remark 2.
Interactive Passive Learning. We remark that results can be directly compared to the optimal universal rates for passive supervised learning, as characterized by [BHM+21] Specifically, BHM+ 21 provide the following characterization for the optimal rates achievable by learner that has access to n labeled examples that are drawn i.i.d. from P.
Theorem 3.
B1M+211 For every concept class HI (with H 2 3) the following hold:
If Hi does not have infinite Littlestone tree, then it is passively learnable with optimal rate
e
If has an infinite Littlestone tree but does not have an infinite VCL tree, then is passively learnable with optimal rate 3.
If HH has an infinite VCL tree, then it requires arbitrarily slow rates.
5

---

Our results illustrate the power of interactive learning algorithmss compared to their passive counter- parts. Notably, if H does have an infinite Littlestone tree, the rate is improved from exponential to arbitrarily fast; again, this is even achieved by an algorithm based purely on label queries. Moreover, using an interactive learning algorithm we achieve an exponential improvement in the case where H does not have infinite VCL tree but has an infinite Littlestone tree: reducing a rate for passive learning to em rate for interactive learning. Finally, when H. has an infinite VCL tree we cannot achieve any improvement even in the interactive setting.
Another important comparison is between the rates achievable in the universal vs uniform setting. Specifically, results of [MT93] imply that for interactive learning with arbitrary binary-valued queries, the optimal uniform rate is (i) 0 after bounded number of queries if [H]] < oc, (ii) e when finite, or (iii) does not converge 0 when the VC dimension
[H] = 30 but the VC dimension of of H. is infinite. Comparing to our result in Theorem P we note that the optimal universal rates allow richer families in each of the cases: that is, the category of any HI in the universal rates trichotomy is never worse than its category in the uniform rates trichotomy, and is often better. For instance, finite VC dimension certainly implies there is no infinite VCL tree, but the opposite is not true, and indeed there are classes of infinite VC dimension which do not even have an infinite Littlestone tree BHH+211 so that the uniform rates are vaccuous while the universal rates are arbitrarily fast.
1.2
Examples
Here we present examples of various hypothesis classes that illustrate the three possible optimal rates.
Example (Finite classes). Let be a finite hypothesis class over some domain X. It follows immediately that this class has infinite Littlestone tree. Thus, arbitrarily fast rates achievable. Recall that for passive learning, the optimal rate was e for this scenario. This illustrates the improvement compared to the passive universal learning setting, where the best achievable universal rate is exponential (BHM+
We then consider threshold classifiers over the natural numbers.
Example 2 (Threshold classifiers over N). Let X = N and consider H (h, :thh:teEN N, -12th Notice that even though there are Littlestone trees of arbitrary depth, there is no infinite Littlestone tree BHM Hence, it is learnable abitrarily fast rate in the interactive setting.
In the next example we consider threshold classifiers over the real numbers.
Example 3 (Threshold classifiers over R.). Let X' and H be the class of all threshold classifiers over the real line, i.e. HI = {he E IR, he 1122)). This class has infinite Littlestone tree. However, since VC dimension is finite, we know there is no infinite VCL tree, and hence the optimal rate is n
Next, an example with infinite VC dimension, which nevertheless is interactively learnable at an arbitrarily fast rate:
Example 4 (Unions of finite sets.). Let X = Up be the disjoint union of the sets Xx. where |&& = We also let H UgHg, where H3; {1s : C Xx The VC dimension of H. is infinite. However, notice that this class does not have an infinite Littlestone tree (BHM 211. Indeed, let x E X be the root of the tree. Then, only Hig can have h(x)) = Thus, there are finitely many hypotheses consistent with this branch from the root, implying the depth is always limited by the choice of root node. Thus, this class actively learnable an arbitrarily fast rate.
Finally, present an example that requires arbitrarily slow rates.
Example 5. Let H be the class of all measurable functions over X' = This class admits an infinite VCL tree 21V hence the learning rate in our setting is arbitrarily slow.
1.3 Techniques
In this section we briefly highlight some techniques that are important for our results. For a more extensive discussion, we refer the reader Appendix A.3]
Gale-Stewart Games. important tool that our algorithms build upon the theory of Gale-Stewart
games GS53. These games consist of two players, learner Pt and an adversary PA. that interact

---

over an infinite sequence of discrete timesteps. In every round t 2 1, the adversary presents an element 2, E X2 the learner and, subsequently, she picks an element y/: E V/, where D, are some sets. If some predetermined condition is met at some finite round & E N (e-g. a set of functions that are consistent with the choices of the players becomes empty), then player Pt. wins. If the interactions repeat for an infinite number of steps, then player PA wins. Thus, we can see that the winning strategy of Pt. is finitely decidable, which means that the learner knows she has won the game after a finite number of steps. The fundamental property that characterizes these games is that either the learner or the adversary has a winning strategy, i.e., playing according to this strategy makes them win the game irrespective of their opponent's 's moves [GS3 HW* Kee In this work, use games where PA chooses subsets of data and Pa chooses labels for the points, such that the possible play-outs correspond to either Littlestone VCL trees.
One- Inclusion Graph Predictor [HLW94). Another important component that we use is the one- inclusion graph predictor. This is passive learning algorithm that takes as input n labeled points that are drawn i.i.d. from P and an unlabeled example drawn from Pxx and returns the correct label with probability 1 - O(d/n), where d is the VC dimension of given function class F for which P is realizable; indeed, F may in fact be any partial concept class (see below).
Partial Concept Classes. The final building block that we use is subroutine that interactively learns partial concept classes. A partial concept class F is a set of partial functions ff : X - {0. 1, +)+ where f()) = * means that f is undefined at point x. Essentially, partial concepts provide framework to express data (ata-dependent assumptions (АНММТ]. We design an algorithm that achieves exponential rates when learning partial concept class F whose VC dimension is bounded (ef. Appendix C.2).
In our proofs of the universal rates, this class F is actually constructed algorithmically given a class H and the i...d unlabeled data.
2 Overview of the Proofs of the Main Result
In this section we provide an outline of the proof of the main results. We refer the reader to for the full proofs.
Appendix B C
Our lower bounds rely on establishing a connection between paths in the infinite tree and family of possible target concepts. Since the paths can be specified by binary strings, our lower bound results follow from lower bounds we prove for lossy coding, representing a universal variant of rate-distortion theory. We leave the details for the appendix, and spend the remainder of this section on outlining the upper bounds, to focus on the novel algorithmic aspects of this work.
Arbitrarily Fast Rates. We first design an algorithm that achieves arbitrarily fast rates whenever H does not have an infinite Littlestone tree. A key subroutine of our algorithm is the ordinal Standard Optimal Algorithm (SOA) [BHM+21]. Essentially, this algorithm generalizes the SOA Lit88 to handle the case of finite, but not uniformly bounded, Littlestone trees. For more extensive discussion we kindly refer to Appendix B Importantly, when this algorithm is executed on a (realizable sequence of labeled data (z1, 1/1 32, y/,.... it will stop making mistakes after a finite time t", However, t" depends on the sequence and there is no bound on how big it is. Our approach that achieves the arbitrarily fast rates is outlined in Figure 2
The intuition behind our algorithm is the following. If we take a large enough number of unlabeled points m, and consider all of their 2 possible classifications, there will be one that is correct. Let SJ be the correctly labeled set. For large enough mi, we know that the ordinal SOA trained on St will output classifier that is always correct. The issues that (i) we do not have access to the correct classification, and (ii) we do not know how large my needs to be. Since the data are generated by some distribution, the time of the last mistake also follows a distribution which can, potentially, have heavy tails. However, there is some (distributionddeeend)
number m E N for which, when the ordinal SOA is trained on a sequence of size m., with probability at least 1/2, will output a classifier that is correct on every point x E X. Thus, if we consider a lot of batches that have size least m and train the ordinal SOA using these batches, at least 1 1/3 of the executions will produce an always correct classifier, with high probability. To overcome the issue that we only have unlabeled data, we consider all the possible classifications of these batches and run the ordinal SOA on each one of them. Moreover, we know that all the correct classifiers produce the same
2 Thii means that for every 2 1, there is some he Hi such that he (x+) Vr, St
7

---

any realizable ArbitrarilyaattRaes Input is unlabeled data sequence 2i, #1,002,-.1 and query budget n.
1. Create sets S = 21,.... Im, S2 = 2m th. Tmng.
2. Split Si into Lvmi batches of size [ymi] and consider all the labeled prefixes of the batches in
lexicographical order: búj denotes the i-th batch with the labeled prefix j. S S 2L
Let (a.(:bb.)) be the output of the ordinal SOA trained on b., and denote g.. (x) = (a;; b.,)).
4. Evaluate the classifiers gh. (+) on the points in S2.
5. Define set If of equivalence classes: gt., and gv.s" are in the same class iff they classify So the same.
6. For each F E F, define
rank(F) min { 31 Sissi < i..... < //TTT/S I <\v< IVmil, ki,......................... |I 1/3 E 1
such that Ity. E ERiSiS S lyma /3
rank = if no such exists.
7. Enumerate F = F2..... so that rank (F)) is non-decreasing in f, and pick any fe E Fe for each E.
8. For each distinct i,j I LV query the label of any point in S2 which fú, fj disagree.
9. If there is some f/ which is correct on all the points we queried, return fg-
10. Otherwise, return any fr.
Figure 2: Arbitrarily Fast Rates Algorithm
output when executed on a new set of unlabeled data. This is why we use points from Sy and create equivalence classes of classifiers that have the same output on S2; this guarantees that all the correct classifiers will be in the same class Fe., with probability one. By taking S2 to be large enough, we make the probability that two classifiers which are in the same equivalence class differ on some x E X' arbitrarily small. Thus, it suffices to consider one representative fo from every equivalence class Fr. Finally, we show that there is ordering of these representatives which guarantees that, with arbitrarily high probability, the representative fr- of the class Fr- (which the correct classifiers belong to) has ranking at most i", where i" is distribution-dependeen constant. Thus, by requesting the labels of points on which pairs ft, fa. S. i,j < /n. disagree, we can just output the one that is correct on all these points, and if Lvn 2 i" such an f. will exist and will be fe. with arbitrarily high probability.
We emphasize that this algorithm uses only label queries, it also applies to the traditional active learning setting. Moreover, if the learner has access to the marginal distribution Px, then all the steps in the algorithm can be implemented exactly, i.e. with probability one, so the output will be classifier that has zero error rate with probability one.
Exponential Rates. We now move to the algorithm that achieves exponential rates whenever IH does not have an infinite VCL tree. As we discussed before, the fact that H. does not have an infinite Littlestone tree gives rise to an algorithm that makes finite number of mistakes sequence ......). In the case of finite VCL trees, [BHM+21 provide an algorithm, which given such sequence, learns after a finite number of steps to rule out patterns in the data. This means that, for some n" E N there is a function g 2 + {0, 13" such that g(z)..... ...)) are not the correct labels of the points (II,..... ..nn) BHM 21l obtain this function by defining an appropriate Sale-Sttewar game, called the VCL game. In every round t 2 1 of this game, the adversary selects a tuple (x)) xr. .y..... 1.A-1) E X of t unlabeled points and the learner picks their labels (uf: vg..... vo E f0. 1). The goal of the learner is to make the set of concepts from H that are consistent with the execution of the game empty. [BHM+21] show that if H. does not have an infinite VCL tree, then the learner has winning strategy and this strategy gives rise to the pattern avoidance function g we described earlier. Importantly, the pattern avoidance function helps us define partial concept class whose VC dimension is finite. For details, we refer to Appendix C.T
The first step in our algorithm, presented in Figure 4 is to half of the query budget to find the labels of [n/2] points in order to simulate the VCL game. The eventually correct pattern avoidance function g we described before, induces some data-dependent constraints. To make the idea of our approach easier to grasp, let us assume that we have access to both the function and to the number n. Then, the next step is to consider the partial concept class
F== = Uf : + 10 V(II.... xnr) E x=
ffa))....,,,.''.. # g(11,..... Tnx) mn-)].
8

---

Importantly, the VC dimension of F* is bounded by n² - 1, since it does not shatter any sequence of length n". Thus, we have reduced the problem interactively learning a partial concept class whose VC dimension is bounded. We provide such an algorithm in Figure 3
Portialinteractiveleennig Input is unlabeled data stream {x1,..... J and query budget
n1.
1. Take a large enough sample of unlabeled data S {a1,..., Fm
Let Hlls to be the total concept class of the functions in F that undefined on S, i.e.,
H|s (f f(z) + *x S},
whose domain is restricted to be S. # # this is a total class with
VC di menest on bounded by d.
H = 0, return an arbitrary classifier (e.g. the all-zero classifier).
Consider the set S of all the O(m²)) possible classifications of S.
Since the learner is allowed to use arbitrary binary queries, it can figure out the labels of all points using (dd log m) queries follows:
Divide S into two sets of equal size $1 and ask whether the true classification is in $, Based on the answer of the query, recurse to the appropriate set.
6. The last step is to use these m labeled points the training set for the one-inclusion graph supervised learning method of [HLW94] for the class F.
Figure 3: Interactive Learning with Partial Concept Classes
The idea of the approach is to take large enough sample S of m unlabeled points and consider the total concept class Hi C J of the functions that are not undefined on S, whose domain restricted is S. Then, HD* also has VC dimension that bounded by n 1, so there are at most ((m")) possible classifications of these points. The next step is to find the correct classification of these points using O(n" log m) binary queries in total. Finally, using these exponentially many labeled points as the training set for the onc-inclusion graph algorithm (cf. Theorem 5). we are able to get a classifier whose error rate decreases exponentially fast.
An important difficulty we need to overcome is that we do not know how long we need to run the VCL game for in order to get a correct pattern avoidance function g. Our approach, described in Figure 5 is to use N = /n/2] of our query budget to request the labels of some points in order to run the VCL game on. Then, utilizing a result from 21 we use [N/2] of the data in order to obtain some estimators εN such that running the game on y points produces a correct g with probability at least 5/8 (cf. Lemma 5). Having obtained these estimators, we split the remaining [N//2] into N = [N/(2fN)] batches of size ty. Subsequently, we run the VCL game each batch and obtain the functions gxx S S [N/(2ix)J. The choice of fn guarantees that, with high probability, least 9/16 of these functions will be correct pattern avoidance functions. Then, consider the partial concept classes F, that are induced by these functions, in a similar manner as we described before. Finally, we aggregate all these classes into majority class
(0, 1, Ve N, V(r,.................... ............. m2) E x 3 at least (9/16)N classes F,, N s.t. J.N f: x
3f E F, with (f(z)), ... = ((t)))))...))))(((()..)........ (f(0))...., f(x))
The motivation behind aggregating the classes is that (i) we can show that J. has bounded VC dimension, and (ii) if J& cannot produce labeling for an unlabeled tuple, then this is not the correct labeling (cf. Lemma 7). An equivalent way to describe Fй is through sequence of universallymmessurabbe measurable functions {Ge: (X x {0. 1))² + [0,1)] where
Ge( V1. ,1...,, ve)
3ʃ E N. (f(x))..... ((x))) (y1,...,91, .we...,))

---

ExponentialRates: Input an unlabeled data stream (ai....., } and query budget ns
1. Use [n/2] of the query budget to get the labels of "e.....::=../.0
2. Call the GSubroutine (cf. Figure 5) with points (1I1, vi)..... (7 ([/m///-
3. Create the partial concept class
FG {f: 1,*) ve E N, (Za, se) x,, Ge(Zi, f(x1), (...)..... se, f(e)) = 1}.
Run Algorithm on the partial class Fo with budget [n/2] and return output.
Figure 4: Exponential Rates Algorithm
GSubroutine: Input is a labeled data sequence {(T1, vI), (TN, (UNN UN)}-
1. Use [NV/] of the data estimate iN (cf. Lemma 5). Let Ñ = [N/22x]]
2. Use the remaining [N/2] of the data to run the VCL game (cf. Algorithm and obtain
Vix S N.
Estimate for 1 S i Ñ
Fi = {f:X + (0, 1, } V(z),.... F 1 Ex )x (f(xi))....,(( 1) # Viw (ar,...,, Rriw
si. )}
4. Estimate the 9/16 //16-iay class
F { (... xz) x , at at least (9/16) classes 5
E with ((te)))....
5. Return {Ge: (X' 13) 1)) v1........................... nt. ve) = 35 E Fй (((r1),..,,((())))) = (yi,..., ve)
LeN where
Ge(TI,VI......
Figure 5: Aggregate Function Subroutine
This leads us to the last step in our algorithm. So far, we have produced partial concept class F& with bounded VC dimension, that produces the correct labelings for any (finite) tuple. Thus, m
suffices to use the interactive learning algorithm with the [n/2] remaining queries that learns partial concept classes at an exponential rate, which we described before (cf. Figure 5).
3 Conclusion and Future Directions
In this paper we provide a complete characterization of universal interactive learning and reveal fundamental trichotomy of interactive learning rates. Moreover, we specify exactly which properties of the hypothesis class give rise to each case in the trichotomy. The general interactive model we consider makes our lower bounds particularly strong. We believe that there are important questions this line of work that are beyond the scope our paper and need to be addressed, such as characterizing the unlabeled sample complexity, studying weaker types of interactions such as label queries and comparison queries, and designing efficient and practical algorithms for natural classes.
Acknowledgments and Disclosure of Funding
Amin Karbasi acknowledges funding in direct support of this work from NSF (ISS-1445022, ONR (N00014- 19-1-2406), and the AI Institute for Learning-Fnate Enabled Optimization at Scale (TILOSS). Shay Moran is Robert Shillman Fellow; he acknowledges support by ISF grant 1225/20, by BSF grant 20 2018385, by an Azrieli Faculty Fellowship, by Israel PAC-VATAT, by the Technion Center for Machine Learning and Intelligent Systems (MLIS), and by the the European Union (ERC, GENERALIZATION. 101039692). Views 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 is supported by NSF (IIS (14-008),,,, an Onassis Foundation PhD Fellowship and Bodossaki Foundation PhD Fellowship.
10

---

References
[AHHM21] N. Alon, S. Hanneke, R. Holzman, and S. Moran. A theory of PAC learnability of partial concept classes. In Proceedings of the 62nd Annual Symposium on Foundations of Computer Science, 2021.
[BBL09] M.-F. Balcan, A. Beygelzimer, and J. Langford. Agnostic active learning. Journal of Computer and System Sciences, 75(1):78-89) 2009.
[BH12] M.-F. Balcan and Hanneke. Robust interactive learning. Proceedings of the 25th Conference on Learning Theory, 2012.
[BHLZ16] A. Beygelzimer, D. Hsu, J. Langford, and C. Zhang. Search improves label for active learning. In Advances in Neural Information Processing Systems 29, 2016.
[BHM+21] O. Bousquet, S. Hanneke, S. Moran, R. van Handel, and A. Yehudayoff. A theory of universal learning. In Proceedings of the 53td Annual ACM Symposium on the Theory of Computing, 2021.
[BHW08] M.-F. Balcan, S. Hanneke, and J. Wortman. The true sample complexity of active learning. In Proceedings of the 21st Conference on Learning Theory, 2008.
[CAL94] D. Cohn, L. Atlas, and R. Ladner. Improving generalization with active learning. Machine Learning, 15(2)2201-211, 1994.
[Coh13] Donald Cohn. Measure theory, volume 1. Springer. 2013.
[CT90] David Cohn and Gerald Tesauro. Can neural networks do better than the vapnik- chervonenkis bounds? Advances in Neural Information Processing Systems, 3, 1990.
[CT92] David Cohn and Gerald Tesauro. How tight are the vapnik-chervonenkis bounds? Neural Computation, 4(2):249-26) 1992.
[Das05] S. Dasgupta. Coarse sample complexity bounds for active learning, In Advances in Neural Information Processing Systems 18, 2005.
[DGL96] Devroye, L. Györfi, and Lugosi. A Probabilistic Theory of Pattern Recognition. Springer Verlag New York, Inc., 1996.
[DHM07] S. Dasgupta, D. Hsu, and C. Monteleoni. A general agnostic active learning algorithm. Advances in Neural Information Processing Systems 20, 2007.
[GS53] David Gale and Frank M Stewart, Infinite games with perfect information. Contributions the Theory of Games, 2(245-266):2-16 1953.
[Han07a] Hanneke. bound on the label complexity of agnostic active learning. In Proceedings of the t4 International Conference Machine Learning, 2007.
[Han07b] S. Hanneke. Teaching dimension and the complexity of active learning. In Proceedings the
of the 20th Conference on Learning Theory, 2007.
[Han09] S. Hanneke. Theoretical Foundations of Active Learning. PhD thesis, Machine Learning Department, School of Computer Science. Carnegie Mellon University, 2009.
[Han12] 12] Hanneke, Activized learning: Transforming passive to active with improved label complexity. Journal of Machine Learning Research, 13(5): 2012.
[Han14] S. Hanneke. Theory of disagreement- based active learning. Foundations and Trends in
Machine Learning, 7(2-3):131-30) 2014.
[Han21] S. Hanneke. Learning whenever learning is possible: Universal learning under general stochastic processes. Journal of Machine Learning Research, 22(130):1-116, 2021.
[HKSW21] Hanneke, A. Kontorovich, S. Sabato, and R. Weiss. Universal Bayes consistency in metric spaces. The Annals of Statistics, 49(4))2129-2150, 2021.

---

[HLW94] D. Haussler, N. Littlestone, and M. Warmuth. Predicting {0, 1]-functions on randomly drawn points. Information and Computation, 115(2):248-292) 1994.
[3]+93] Wilfrid Hodges, Hodges Wilfrid, et al. Model theory. Cambridge University Press, 1993.
[HY15] Hanneke and Yang. Minimax analysis of active learning. Journal of Machine Learming Research, 16(12):348733602, 2015.
[Kec12] Alexander Kechris. Classical descriptive set theory, volume 156. Springer Science & Business Media, 2012.
[KLMZ17] D. M. Kane, S. Lovett, S. Moran, and Zhang. Active classification with comparison queries. In 2017 IEEE 58th Annual Symposium Foundations of Computer Science, 2017.
[KMT93] S. R. Kulkarni, S. K. Mitter, and N. Tsitsiklis. Active learning using arbitrary binary valued queries. Machine Learning. 11:23-35, 1993.
[Lit88] N. Littlestone. Learning quickly when irrelevant attributes abound: new linear- threshold algorithm. Machine Learning, 2:285-318, 1988.
[Sau72] N. Sauer. On the density of families of sets. Journal of Combinatorial Theory (A), 13(1):145-147, 1972.
[YH13] L. Yang and S. Hanneke. Activized learning with uniform classification noise. In Proceedings of the 30th International Conference on Machine Learning, 2013.
[YHC10] Yang, S. Hanneke, and J. Carbonell. Bayesian active learning using arbitrary binary valued queries. In Proceedings of the 21st International Conference on Algorithmic Learming Theory, 2010.
Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes]
(c) Did you discuss any potential negative societal impacts of your work? [N/A]
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes] Yes, the theoretical model we are working on specified in Section
(b) Did you include complete proofs all theoretical results? [Yes] Due to space limita-
tions, the full proofs are postponed to the appendix/suppleemnntry material.
3. If you ran experiments...
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either in the supplemental material or URL)? [N/A]
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [N/A]
(c) Did you report error bars (e.g., with respect the random seed after running experi- ments multiple times)? [N/A]
(d) Did you include the total amount of compute and the type of resources used (c.g., type of GPUs, internal cluster, or cloud provider)? [N/A]
4. If you using existing assets (e.g., code, data, models) curating/releasing assets...
(a) If your work uses existing assets, did you cite the creators? [N/A]
12

---

(b) Did you mention the license of the assets? [N/A]
(c) Did you include any new assets either in the supplemental material or as URL? [N/A]
(d) Did you discuss whether and how consent was obtained from people whose data you're using/curating? [N/A]
(e) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [N/A]
5. If you used crowdsourcing or conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, applicable? [N/A]
(b) Did you describe any potential participant risks, with links Institutional Review Board (IRB) approvals, if applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent on participant compensation? [N/A]
13


Reviews:
[{"review_id": "xMTc-9obQGL", "reviewer": "Reviewer_whon", "summary": "This work studies the universal learning rate for interactive learning, which, unlike the uniform learning setting that captures an upper envelope of the learning curves over families of distributions, concerns the best possible rate of convergence for every data distribution. It shows that interactive learning does have benefits over passive learning by showing much superior convergence rates in each category of the fundamental trichotomy. In addition, the bounds established can apply to arbitrary types of queries as long as they are binary.\n", "questions": "The paper is overall very well written. The only thing is that it may distinguish the techniques in this paper from the priors. The algorithmic designs are very clearly presented but might be hard for the reader to compare with the prior works, e.g. BHM+21, without reading them.\n", "limitations": "No concerns.\n", "rating": 9, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "This paper considers a very important problem (in the modern machine learning community) of interactive learning and provides insights through the lens of universal learnability which are quite interesting and inspiring. For example, just by a mild rearrangement of the quantifiers in its definition, the learning rates characterize the learnability of problems from a totally different perspective. The authors were able to show the benefit of interactive learning in two different categories, that is, the optimal learning rate for different distributions can be arbitrarily fast rates and exponential, while in the passive learning paradigm, the rates were exponential and polynomial respectively. The different categories appear to be closely related to the dimensionality of the infinite Littlestone tree and the VCL tree. The authors propose algorithms together with rigorous analysis with techniques built upon some tools from the prior works that study passive settings, fitting into the interactive learning scenario.\n", "was_revised": false, "final_justification": "", "rebuttal": "", "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": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "vFdOLFOlCp", "reviewer": "Reviewer_gBuw", "summary": "The authors study interactive learning in [BHMYH21]’s, universal learning model. Universal learning studies the asymptotic error rate of classification in a distribution-dependent fashion, in the sense that a class $H$ is learnable at rate $R(n)$ if for every (realizable) joint distribution over the data there exist constants $c$,$C$ such that $\\mathbb{E}[err(h_n)] \\leq CR(cn)$. This better models practical ML settings where a target distribution is fixed before the number of samples is chosen. In the interactive setting, the algorithm is allowed to ask arbitrary binary queries  (the learner may also use a finite but unbounded number of unlabeled samples), and $n$ denotes the number of queries rather than number of samples.\n\nThe authors show that interactive learning in the universal setting is characterized by the same trifecta as passive learning, but with strictly improved rates. Namely, they show that a hypothesis class satisfies exactly one of the three following \n\n1. Learnable at arbitrarily fast rates\n2. Learnable at exponential rate\n3. Learnable at arbitrarily slow rates\n\nFurthermore, they give a combinatorial characterization of which classes fall into these categories: classes with no infinite Littlestone tree satisfy 1, classes with no infinite VCL tree satisfy 2, an class with an infinite VCL tree satisfy 3. [BHMYH21] showed the same trifecta for passive learning, where the rate of 1 is exponential, 2 is linear, and 3 is arbitrarily slow. Thus the authors in this work fully resolve when and by how much interaction helps in the universal setting.", "questions": "Is it the case that the rate of error decay with respect to unlabeled data is substantially worse than in its unlabeled counterpart? If so is it known this is necessary to the characterization?", "limitations": "Yes", "rating": 7, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "This paper resolves the problem of characterizing interactive learning with arbitrary binary queries in the universal setting (a question in a sense first proposed in [BHW08]). This is an important theoretical contribution to the field of active learning and the study of the universal model. The techniques in the work are a mix of strategies developed in [BHMYH21]’s original study of passive universal learning (e.g. analysis of Gale-Stewart games) and novel algorithmic techniques such as reduction to interactive partial learning. The paper is well-written and the authors do a nice job of fitting their work into the literature (though it might be nice to also mention Long’s original work on partial learning “On agnostic learning with {0,*,1}-valued and real-valued hypotheses”). The work is likely to be of strong interest to the (theoretical) active learning community and of fair interest to the learning theory community at large.\n\nThe main weakness of the work lies in the very strong model of interactivity it considers. Namely the work makes two main assumptions that are atypically strong for the active learning literature:\n\n1. The learner can make any binary query\n2. The learner has access to an unbounded number of unlabeled samples\n\nLearning with arbitrary binary queries is of theoretical interest, but is not particularly practically relevant. Even the membership query model (which allows arbitrary label queries) is too strong to be of interest in most applications. Similarly, it is typically assumed in active learning that the error rate with respect to unlabeled data also exhibits reasonable decay (in particular with a similar rate to what is enjoyed in the passive setting). Indeed in the uniform setting this can always be achieved. It is unclear from this work whether these issues are inherent and greatly affect the characterization of interactive universal learning, or merely artifacts of the proof.", "was_revised": false, "final_justification": "", "rebuttal": "", "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": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "FF8rCKB2xXd", "reviewer": "Reviewer_4rao", "summary": "In this paper, the universal learning framework is studied. In universal learning, unlike in uniform learning, the goal is to obtain decay rates for learning curves where the constants are potentially distribution-dependent. This can lead to improvement as compared to the distribution-independent formulation of uniform bounds. In contrast to previous work on universal learning, which focused on standard passive learning, this paper considers interactive learning, where the learner is allowed to send binary queries to an oracle. This includes the active learning setting, where the learner requests labels of unlabelled data. For this setting, three regimes of learning rates are shown, which give potentially dramatic improvements as compared to passive learning results for universal learning.", "questions": "The algorithms used in the proofs seem quite impractical. Do the presented results and conclusions have any concrete implications? Is it practically feasible to achieve the faster described rates with any computationally efficient algorithm?  \nWhat are the precise technical differences between your proofs and those of [BHM+21] for the passive setting?  \nHow vital is the assumption of realizability? Is this a technical simplification, or do the results completely break down in its absence?  \nWhat are the remaining questions in this line of work?\n\n\nMinor comments:  \nLine 176 \"and and\"  \nMissing space on line 342  ", "limitations": "The authors adequately discuss the limitations. Possibly, the practical considerations of the limitations of realizability, iid, and access to the unlabelled data distribution can be discussed further.", "rating": 8, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The paper is overall very well-written, and gives significant results in a pertinent area. While the extension from passive to interactive is in a sense straight-forward, the technical details are non-trivial and the proofs use new algorithmic ideas. While I did not go through the proofs in detail, everything seems sound and well-written based on a skim reading. The main body of the paper does a commendable effort in trying to convey the intuition of the proofs and results.\n\n\nIn terms of weaknesses, the paper could benefit from a discussion of practical aspects. The algorithms used in the proofs seems highly impractical in terms of actual learning tasks due to the computational requirements, such as running learning algorithms on all possible classifications of a set of unlabelled data. The intuitive description of the algorithms are still not entirely easy to grasp, but I understand if it is hard to simplify the presentation more.", "was_revised": false, "final_justification": "", "rebuttal": "", "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": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept