Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: summary: The authors in this work study the problem of learning univariate PTFs. They consider the active learning model. Active learning is generally, the model that asks specific labels of points. The authors, show that in fact if we just ask for the labels we cannot get any useful guarantees. So, the authors are considering a stronger model, which asks for the sign of the derivative in a specific point and they show that again any learner that has some advantage has to query until the d derivative (d is the degree of ptf).

Their main result is an upper and a lower bound in the number of required queries in this model. The lower and the upper bounds are differ in a $d^2$ factor. 

They also showed that if the roots of a PTF is uniformly distributed in [0,1] then again the same lower bound holds, but they can obtain a better upper bound that only losses $\tilde(O)(d)$ multiplicative factor.

Finally, they show that if we increase the dimension, then derivative queries cannot learn PTFs. 


strengths_and_weaknesses: 1. Overall, I find the results very interesting, especially the lower bounds. 
2. Even if the upper bounds are not matching the lower bounds, the upper bounds are using several nice and simple ideas and they interesting on their own.
3. The authors showed that the fact that they have no distributional assumptions is the reason they required such a strong model. When the distribution and the ptfs are from a nice distribution, then they do not need such a strong model. It would be interesting to see when this threshold phenomenon occurs, what are the milder assumptions that we do not need derivatives.

Weaknesses/Questions:
1. The authors are working on a very strong model: Perfect Learning. But what happens in the Active Learning model with distributional assumptions only? Do label queries suffice? Do we need at least one derivative to get $\log(1/\epsilon)$?

Other:
I suggest the authors to put a definition of perfect learning in an environment (lines 98-101).

questions: I would like to know the authors opinion about my question above.
limitations: no limitations
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 the setting of active PAC learning, the algorithm has access to (cheap) unlabeled data and can make (more expensive) queries for their labels adaptively. For the hypothesis of polynomial threshold functions (PTFs) considered in this work, the queries are more complex, asking for the derivatives of the underlying polynomial. In order to measure the adaptivity, the algorithm may send the queries in rounds. The paper considers the variant of active learning known as perfect learning, where the goal for the learning algorithm is to label a set of $n$ (adversarially selected) samples. It also considers the setting where the data distribution and the underlying hypothesis come from known distributions rather than being worst-case.
The first result states that the query complexity as a function of $n$ is between $d \log n$ and $d^3 \log n$, where $d$ is the degree of the PTF. The second result gives an algorithm that makes the queries in batches, in the cost of incurring worse the query complexity. That algorithm has near-optimal runtime. The third result shows that missing access to any of the derivatives renders active learning of PTFs impossible. The next two results concearn learning in the average-case model: Upper and lower bounds on query complexity (where queries now only use labels) for the case where the samples and roots of the PTF are uniform in $[0,1]$ and upper bounds for PTFs with Dirichlet roots. Finally, the paper shows that when going to more than one variable, derivative queries are no longer sufficient to learn PTFs (in the worst-case setting).

strengths_and_weaknesses: Significance: There is a substantial body of work studying active learning of halfspaces, one of the most basic hypothesis classes considered in learning theory. Moving to polynomial threshold functions, a generalization of halfpsaces is a natural and well-motivated direction. The upper and lower bounds in the paper the paper give a fairly complete answer to an interesting question. 

Quality: This review is mostly based on the short version of the paper and parts of the supplementary material corresponding to Sections 3 and 4. The key lemma for the wort-case active learning is Lemma 3.1 which finds partition in which every interval has the same sign pattern. The algorithm and coupon-collecting-based analysis for the average-case results seem fairly natural. The part about learning polynomials with Dirichlet roots needs considerable technical effort. Overall, the proofs I checked seem correct, although I have not gone through all the details. 

Clarity: The paper is well-written. Below line 251, ‘d’ is undefined (though it is defined in the supplementary material) .

Originality: Not all of the parts of the paper appear to be equally challenging, but overall the arguments are non-trivial and require novelty. I am not an expert in the topic/prior work but the contributions seem solid.

Overall, a good theoretical work. I recommend that the paper be accepted.

questions: It would be nice to expand a bit more on the infinite precision problems of prior work (lines 181-183) and in what sense derivative queries are better. 
limitations: The limitations are sufficiently addressed.
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: This paper introduces the problem of active learning of univariate $d$-degree polynomial threshold functions using so-called derivative queries, which are a novel, yet, natural enriched query type for this learning problem.

The authors discuss that usual label queries are not sufficient to learn in this setting already for degree 2 polynomials (corresponding to the well-known problem in active learning that learning linear thresholds / non-homogeneous halfspaces already in R^2 is not possible).

In the perfect learning setting (inferring all labels of a possibly adversarially given finite unlabelled dataset) the authors state near-tight lower and upper bounds and devise a algorithm achieving the query upper bound with near-linear runtime.

These results for perfect learning immediately imply bounds for classical $(\epsilon,\delta)$-based (PAC) active learning. However, to generalise the result to average-case bounds a more involved analyses is required.

They also state some distribution-dependent result for common families of distributions.

Lastly, they propose a simple variant where the points are not queried one-by-one but rather in batches and give an upper bound in terms of the batch-size.
strengths_and_weaknesses: This paper is a pleasant read and introduces a very interesting and quite natural active learning problem. The active learning community and general learning theory community should be interested in this work.

The authors discuss related work and introduce necessary background. 

This work is a strong introduction into this novel learning problem, devising near-tight bounds and efficient algorithms. Also various related aspects are discussed.

Minor suggestions:
* is perfect learning the same as "exact learning" (e.g., Hegedűs, Tibor, COLT 1995). Maybe mention it, as well in the related work.
* $f^{(0)}$ is not really defined, is it just $f$ itself (see e.g., line 106).
* the $p^{(i)}$ notation seems to be not yet defined in line 60.
* line 344: a "," missing in the Hessian? Also how exactly is the sign of a vector defined?
questions: There is still a gap in the inference dimension of the problem ($\Omega(d)$, and $O(d^2)$). Do the authors have first ideas or a hunch which one of the two is the "correct" tight one?

While the kernel/embedding view of this problem is shortly discussed, I would like to see a deeper discussion of this issue. How usual bounds for learning halfspaces (in the polynomial feature space) relate to the achieved here?
limitations: I don't thing that this work has limitations. Still some pointers and questions to look into:

Are large-margin bounds possible? Maybe related: Do bounds on the Lipschitz constant of the polynomial help?

Are there (simple) first positive results for multivariate polynomials? Maybe with even more powerful queries?

There are ways to completely get rid of the $\log 1/\delta$ in active learning upper bounds (Hanneke and Yang, 2015). Is this possible/useful here?
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 submission provides theory and algorithms for active learning polynomial threshold functions under access to derivatives of the underlying classifier. The submission provides analysis of proposed algorithms that have desirable query complexity and rounds of adaptivity. 
strengths_and_weaknesses: The strengths and weaknesses of the submission are compiled below. 

**Originality.** The paper looks at active learning polynomial threshold functions with access to the signs of derivatives of the underlying classifier, which is a new topic within the many previous related work. The paper uses some real estate to demonstrate that derivative queries are well motivated in theory and practice (line 45 and the corresponding paragraph) and the discovery that perfect learning under the worst case requires derivatives (Theorem 1.3) is quite interesting. 

**Quality and clarity.** Overall, the paper is nicely written. Past history and relevant literature discussions are adequate. Some minor questions are attached to the next "Questions" section. 

**Significance.** The paper is an interesting addition to a long list of papers in the active learning community and its topic and results are of adequate significance. 
questions: Some minor questions are listed here:

- Theorem 1.6 suggests that derivative queries for multivariate PTFs are insufficient in the worst case setting. This doesn't seem to be too surprising considering the fact that missing one derivative is undesirable for univariate PTFs. Are there other types of additional query information for the multivariate case so that perfect learning is possible with small amounts of queries?
- There exists quite a gap between the lower and upper bounds in Theorem 1.1; is there any intuition between the gap and what may be causing it? For example, is the lower bound too loose, the upper bound too loose, or a bit of both?
- This is a nice theory work --- can the practical implications / limitations of this work be clarified even further? Particularly, in the *worst case*, if all derivatives (up to degree $d$) are required, it seems like this would be an issue and would not be practically feasible. 
limitations: Some limitations are discussed in the paper. See above sections for suggestions/questions for improvement.
review_title: null

Meta-review: metareview: 
This paper contains a fresh and mathematically interesting theoretical analysis of a fundamental problem.
confidence: Certain
Decision: Accept