Venue: NeurIPS 2022 Conference

Reviews:

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: This paper considers learning of k-class classifiers using label and seed queries, where seed queries are special ones that ask for some labeled examples in the specified region. The paper proposes an algorithm which learns the concepts in polynomial time, where the complexity involves convex-hull margin, an extension of margin in linear classes. The paper also shows a lower bound of necessary queries which shows the tightness of the analysis. 

strengths_and_weaknesses: Strength:
- strong theory paper with a lower bound



Weakness:
- no experiments is done
questions: Are there any practical scenarios where seed queries are realizable? 
limitations: N/A
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: This paper tackles the problem of active learning on classifiers with strong convex hull margin classes. In this framework that generalizes SVM margins, it is known that the query complexity of learning with only label queries is exponential in the dimension and that learning with seed queries is computationally inefficient. Is designed in this paper an approach that combines label and seed queries to learn such classifiers with a low query complexity in polynomial time. In addition to the upper bound on the query complexity of the provided algorithm, is established here a worst case lower bound on the query complexity of learning a k-class classifier with strong convex hull margin.
strengths_and_weaknesses: Strengths:
- Presentation: the problem is well introduced and the main results are clearly presented
- Impact: some of the results established seem to be of general interest (in particular CPLearn’s guarantees) in addition to solving the problem of learning through label and seed queries with a computationally efficient algorithm whose total query complexity is polynomial in the dimension of the space.
- The paper is technically sound.

Weaknesses: 
- No experimental results limit the impact of the work.
- It would be nice to see some mentions of future work and remaining open problems

questions: For the query complexities, it seems like the lower bound is linear in the dimension while the upper bound for the label query is quadratic. 
- Which of the two could be improved?
- Are there interesting cases where the upper and lower bounds match?
- Is there a problem dependent quantity that characterizes the problem? 

Are the algorithms BinLearn and KClassLearn implementable in practice?

limitations: The assumptions made are adequately stated. It would be nice to more clearly address the limitations of the work: without empirical support the algorithms provided in this work seem more like proofs of concept and it feels like there are still some open problems on the query complexity upper bounds. The authors state that the potential negative societal impacts of their work is N/A due to its theoretical nature. It might still be valuable to mention what could go wrong if the suggested algorithms were actually deployed.
review_title: null

final_score: rating: 5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.
review_content: summary: This paper studies active learning of classifiers with margin (assumption of strong convex hull margin), by combining label and seed queries. Using seed queries only, the target classifier can be learned in $\mathcal{O}(m\text{log}n)$ -- for a set of n points in $\mathbb{R}^m$ -- but the algorithm has superpolynomial time complexity. The paper shows that using both label and seed queries, a binary classifier can be learned in $\text{poly}(n+m)$ time, using $\mathcal{O}(m \frac{\text{log}m}{\gamma})$ seed queries, where $\gamma$ is the strong convex hull margin and $\mathcal{O}(m^2 \text{log}n)$ label queries. These results are extended for multi-class classifiers with $k! k^2$ multiplicative overhead. The authors also show that the results hold even when only one class has strong convex hull margin, or when input points have bounded bit complexity.
strengths_and_weaknesses: The paper is written and presented well, the assumptions are stated well, and it solves a well motivated issue of efficiently leveraging seed queries, by combining with label queries. It also provides a novel efficient algorithm (CPLearn) for seed which provides the upper bound on seed queries.  


questions: The results and some algorithms seem novel, however I am not familiar with the area, so I cannot assess the significance fully. 
limitations: The assumptions are stated clearly and there are no negative direct negative societal impacts.
review_title: null

Meta-review: metareview: The problem is well introduced and the main results are clearly presented
While there are no experimental results, the theoretical contribution seems strong.
Please add the main open problems to the final version.


confidence: Certain
Decision: Accept