Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: The paper considers minimax optimality for some realizable interactive learning settings. A general separation is given between agnostic and realizable learners for the label complexity of active classification. Furthermore efficient algorithms are provided for minimizing the sample complexity of best arm identification and for minimizing the loss incurred while identifying the best arm (which is subsumed by usual regret minimization). Gaps between agnostic and realizable learners in the realizable setting are also shown for these settings. Experiments show that the new algorithms are competitive and can incorporate prior knowledge to obtain gains in sample complexity.
main_review: The paper presents (in clear, well-organized writing) some new potentially useful insights like the cost of using an agnostic learner in a realizable setting and considers best arm identification for general function classes (in the realizable setting). Computational efficiency is obtained by novel sampling techniques from a non-convex version space of functions, although it is not clear if the algorithms translate into practical implementations as n the number of arms grows. Also it would be nice to see how the sample complexity upper bounds compare with the real sample complexity of their algorithms in the experiments. In particular it is not clear what is the gap due the the -log(probability of sampling f*) term. A clearer description of what function classes the bounds are tight and sampling is efficient for would be helpful.
limitations_and_societal_impact: The authors adequately addressed the limitations and potential negative societal impact of their work.
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: Consider the problem of best arm identification: there are $n$ arms, each with a reward, and the goal is to select the best arm  with the best reward with as few pulls as possible. The query complexity of this specific problem in the realizable setting (where rewards correspond to an unknown function from a known family) is well understood (up to log factors), but there is no matching efficient algorithm. This paper provides nearly optimal algorithms for classes of functions that are convex (up to a discretization). Algorithms for related interactive learning problems are also considered. Finally, the authors present lower bounds for such problems that show that agnostic algorithms (not assuming realizability) can be much worse. 
main_review: Interactive learning (in the sense discussed in this paper) consists of gradually querying a set of points $x_1,x_2,\dots,x_n$ so as to obtain information about associated rewards/losses $y_1,\dots,y_n$. Different problems correspond to different goals to be reached with the queries. So-called best-arm identification consists of querying some $x_i$ with smallest possible loss in the least amount of time. A similar problem (apparently introduced here) is to minimize the losses of queried points up to the point where a best arm is found. Finally, in active learning the rewards/losses are binary labels, and the goal is to learn the function $f$ from a given class that best approximates the labels. 

This paper consider the realizable setting where the rewards satisfy $y_i=f(x_i)$ for an unknown function $f$ belonging to a known family $\mathcal{F}$ (the case where the $y_i$ may be noisy is considered in the Appendix). For best arm identification, reference [11] gives a nearly tight query complexity bound (without an efficient algorithm). One of the positive results of the present paper is an algorithm that is efficient under certain somewhat awkward assumptions: namely, that $\mathcal{F}$ is a family consisting of discretizations of functions that belong to a convex set $\mathcal{R}$. Cumulative loss minimization is dealt with similarly. Similarly, active learning is relegated to an appendix.

One drawback of the above algorithms is that they require the realizability assumption. The paper also shows that this is in some way unavoidable (this is the content of Propositions 1 through 3). 

As far as I can tell, this is a correct and nontrivial contribution with some interest. The main technical idea is replacing the ```````"version space" (where functions compatible with the data are considered) with a convex set. To understand it, first note that a natural version for query complexity problems is to keep a version space containing all functions $f$ compatible with the results that were seen. The gist of the authors approach is to replace this version space with a convex set in function space that consists of an intersection of polynomially many semispaces with the function class $\mathcal{F}$. Using sampling methods for these convex sets, this strategy can be made to work, and one may show that the sets quickly shrink until only one candidate function is left. This works under the assumption that $\mathcal{Y}$ is finite: for infinite sets, a different approach must be used, with less precise bounds. 

The results of this paper seem novel and important enough to warrant publication at NeurIPS. In particular, the problems posed here address natural open questions raised in [11] (from 2011), as well as some new problems. The lower bounds are also interesting, and experimental results against Bayesian optimization methods seem promising.

However, the exposition leaves a lot to be desired. I will itemize some issues in what follows. Do note that I have not written down typos, but there are many of them! 

* The authors are a bit too cavalier when they imply that sampling in convex bodies is always "efficient". There are subtleties involved, such as the need for membership oracles and the like. Some of those issues should be discussed in the appendix. 
* In particular, it would be nice to understand the complexity for at least one of the problems under consideration. 
* Similarly, actual query complexity bounds are never fully worked out for the algorithm Grails. It'd be nice to understand the query complexity of the proposed methods in some of the examples considered in the appendix.
* To sum up the above suggestions, it would be nice to see a full result for some simple case of the problems considered in the paper (eg. active classification with linear functions). In this example, all relevant parameters and the complexity upper bound should be worked out. 
* In section 2, the authors mention the realizable setting, and then define Active Classification without explaining what it looks like in the realizable setting. 
* The assumption that $\mathcal{F}_{\mathcal{R}}$ is obtained from $\mathcal{R}$ by discretization does not seem very natural and is hard to swallow. The one case where it makes a lot of sense is that of active classification, because $\mathcal{Y}=\{1,-1\}$ in that case. Unfortunately, that case is relegated to the appendix. Somewhat awkwardly, a lower bound for Active Classification is given in the main text.
* $\S$ 5.1: this is a minor technicality, but some of the halfspaces considered in the text are open.


limitations_and_societal_impact: Yes.
review_title: null

final_score: rating: 8: Top 50% of accepted NeurIPS papers, clear accept
review_content: summary: The authors prove that minimax optimal interactive learning algorithms must be realizability-based. They present 2 efficient algorithms for this setting and prove they are approximately minimax optimal.

main_review: Active learning is the classic approach for reducing label complexity during model learning. Years ago, many empirical experiments showed little improvement over random sampling which led to the suspicion that active learning doesn't work. It has since been demonstrated that active learning algorithms do exist which learn at an exponential rate [see the work of Balcan et al.]. This paper continues that line of work, showing that realizability is a key ingredient in active learning. 

Overall the paper is well structured, but notation dense. It would be easier to read if more equations were followed with "in words" or (approximate) conceptual descriptions. Also, previews such as "now we prove such and a such result, the approach is to do this and that" would increase readability. I recognize however, these additions are likely not feasible due to the length constraints.

The empirical experiments are a little light. Again, length constraints likely inhibit further experiments. 

limitations_and_societal_impact: The biggest limitations to this work are the computational complexity of the "efficient" algorithms, and the restriction to the noise-free setting. Both of which are noted by the authors.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: This paper presents a general algorithmic framework for interactive learning, which applies to bandit and active classification.
main_review: The paper positions its main contribution in a general framework for computationally efficient interactive learning, while making a strong assumption that the data are realizable. 

It is okay to confine to realizable setting but I am not convinced of the motivating example. The starting point is that for learning of threshold over a bounded interval, agnostic learner is inferior to realizable learner; thus authors decide to stick with the latter. I agree this example is true but it turns out that such motivation is superficial and seems diminish tremendous efforts in agnostic learning in the past decades. Furthermore, the nice query complexity shown in the example seems just a singular case; same result does not hold for more general and practical setup such as halfspace in $R^d$. 

I also found the presentation is confusing. It is claimed to develop a general framework for active classification, but neither Algorithm 1 nor 2 is committed to it.

For best arm identification, the dependence on sampling probability of $f^*$ is non-standard and is of little interest since it is unknown.

It is unfair (in fact, misleading) to compare Theorem 5 to [11] because Theorem 5 follows from an inefficient algorithm. What you can really do is to compare Theorem 4 to [11]. However, in this case, the above issue persists so there is no evidence that your algorithm outperforms.

My overall feeling is that the paper is too dense to follow, and the major technical contribution is vague. While it is interesting to see results for general loss functions, it leads an unknown quantity (i.e. sampling probability) in sample complexity so the bound is of little interest.

## updates after author rebuttal

Authors addressed most of my concerns. Authors also promise to state the results (i.e. "minimax optimal") in a more precise way. I am thus happy to raise my score.

limitations_and_societal_impact: yes
review_title: null

Meta-review: The paper presents an algorithm for solving a set of problems in the realizable interactive learning framework via a new sampling based algorithm. All the reviewers liked the theoretical results in the paper. There was considerable and productive discussion among the authors and the reviewers and in the end all the reviewers agreed that the results in the paper warrant publication but the authors must do a better job in the camera ready version of discussing the pros and cons of their bounds and how they related to prior work. 
Decision: Accept (Poster)