Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 9: Very Strong Accept: Technically flawless paper with groundbreaking impact on at least one area of AI/ML and excellent impact on multiple areas of AI/ML, with flawless evaluation, resources, and reproducibility, and no unaddressed ethical considerations.
review_content: 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.

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.

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.

limitations: No concerns.
review_title: null

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: 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.

The 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 

1. Learnable at arbitrarily fast rates
2. Learnable at exponential rate
3. Learnable at arbitrarily slow rates

Furthermore, 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.
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.

The 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:

1. The learner can make any binary query
2. The learner has access to an unbounded number of unlabeled samples

Learning 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.
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
review_title: null

final_score: rating: 8: Strong Accept: Technically strong paper, with novel ideas, excellent impact on at least one area, or high-to-excellent impact on multiple areas, with excellent evaluation, resources, and reproducibility, and no unaddressed ethical considerations.
review_content: 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.
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.


In 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.
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?  
What are the precise technical differences between your proofs and those of [BHM+21] for the passive setting?  
How vital is the assumption of realizability? Is this a technical simplification, or do the results completely break down in its absence?  
What are the remaining questions in this line of work?


Minor comments:  
Line 176 "and and"  
Missing 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.
review_title: null

Meta-review: metareview: This paper provides a characterization of learning rates for interactive learning in the universal learning framework. All reviewers praised the novelty and quality of this submission.
confidence: Certain
Decision: Accept