Active Learning Polynomial Threshold Functions
Authors: Omri Ben-Eliezer
Max Hopkins
Chutong Yang
Hantao Yu
Venue: NeurIPS 2022 Accept (2022)
Keywords: Statistical Learning Theory
Active Learning
Polynomial Threshold Functions
Enriched Queries

Abstract: We initiate the study of active learning polynomial threshold functions (PTFs). While traditional lower bounds imply that even univariate quadratics cannot be non-trivially actively learned, we show that allowing the learner basic access to the derivatives of the underlying classifier circumvents this issue and leads to a computationally efficient algorithm for active learning degree-$d$ univariate PTFs in $\tilde{O}(d^3\log(1/\varepsilon\delta))$ queries. We extend this result to the batch active setting, providing a smooth transition between query complexity and rounds of adaptivity, and also provide near-optimal algorithms for active learning PTFs in several average case settings. Finally, we prove that access to derivatives is insufficient for active learning multivariate PTFs, even those of just two variables.

Active Learning Polynomial Threshold Functions
Omri Ben-Eliezer Department of Mathematics Massachusetts Institute of Technology omribêmit: edu
Max Hopkins
Department of Computer Science and Engineering University of California, San Diego nmhopki @@eng...nnng...mmm ucsd.edu
Chutong Yang Department of Computer Science Stanford University yct1998@stanfors edu
Hantao Yu
Department of Computer Science Columbia University
hantao, yowcoouuoiiiie.m.omo edu
Abstract
We initiate the study of active learning polynomial threshold functions (PTFs). While traditional lower bounds imply that even univariate quadratics cannot be non-trivially actively learned, we show that allowing the learner basic access the derivatives of the underlying classifier circumvents this issue and leads to a computationally efficient algorithm for active learning degree-d univariate PTFs (d log(1 (1/))) queries. We extend this result to the batch active setting, providing smooth transition between query complexity and rounds of adaptivity, and also provide near-optimal algorithms for active learning PTFs in several average case settings. Finally, we prove that access to derivatives is insufficient for active learning multivariate PTFs, even those of just two variables.
1 Introduction
Today's deep neural networks perform incredible feats when provided sufficient training data. Sadly, annotating enough data train your favorite classifier can often be prohibitively expensive, especially in important scenarios like computer-assisted medical diagnoses where labeling requires the advice of human experts. This issue has led surge of interest in active learning, paradigm introduced to mitigate extravagant labeling costs. Active learning, originally studied by Angluin in 1988 [T) is in essence formed around two basic hypotheses: raw (unlabeled) data cheap, and not all data is equally useful. The idea is that by adaptively selecting only the most informative data to label, we can get the same accuracy without the prohibitive cost. As a basic example, consider the class of thresholds in one dimension. Identifying the threshold within some & accuracy requires about 1 1/8 labeled data points, but if we are allowed to adaptively select points we can use binary search to recover the same error in only log(1/8 labels, an exponential improvement!
Unfortunately, there's well-known problem with this approach: it breaks down for most non-trivial classifiers beyond ID-thresholds (2). providing no asymptotic benefit over standard non-adaptive methods. This has lead researchers recent years to develop slew of new strategies overcoming this obstacle. We follow an approach pioneered by Kane, Lovett, Moran, and Zhang (KLMZ) [ asking more informative questions. KLMZ suggest that if we are modeling access human expert, there's 's no reason to restrict ourselves to asking only about the labels of raw data; rather, we should be allowed access to other natural application-dependen questions as well. They pay partieular attention to learning halfspaces in this model via "comparison queries," which given æ, Rd ask which point is closer to the bounding hyperplane (think of asking a doctor "which patient more sick?"). Such queries had already shown promise in practice 6) and KLMZ proved they could be used
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

to efficiently active learn halfspaces in two-dimensions, recovering the exponential improvement seen for -D-thresholds via binary search. Beyond two dimensions, however, all known techniques either require strong structural assumptions 3 7. or the introduction of complicated queries (, 9 requiring infinite precision, a significant limitation in both theory and practice.
The study of active learning halfspaces can be naturally viewed as an attempt to extend the classical active learning of 1D-thresholds to higher dimensions. In this work, we take a different approach and instead study the generalization of this problem to higher degrees. In particular, we initiate the study of active learning polynomial threshold functions, classifiers of the form (g()p for x e R and p some underlying univariate polynomial. When the degree of p is 1, this reduces to the class of DD-thresholds. Similar to halfspaces, standard arguments show that even degree-two univariate PTFs cannot be actively learned To this end, we introduce derivative queries, a natural class-specific query-type that allows the learner weak access to the derivatives of the underlying PTF p.
Derivative queries are well-motivated both in theory and practice. A simple example is the medical setting, where a first-order derivative might correspond to asking "Is patient X recovering, or getting sicker?" Derivatives also play an essential role in our sensory perception of the world. Having two eyes grants depth perception [0), allowing us compute low-order derivatives across time-stamps to predict future object positions (e.g. for hunting, collision-vvoidance).. Multi-viewpoint settings also allow access to low order derivatives by comparing nearby points; one intriguing example the remarkable sensory echolocation system of bats, which emit ultrasonic waves while moving to learn the structure of their environment [TT. While high order derivatives may be more difficult to compute for human (or animal) oracle, they still have natural implications in settings such as experimental design where queries are measured mechanically (e.g. automated tests of a self-driving car system might reasonably measure higher order derivatives of positional data). Such techniques have already seen practical success with other query types typically considered too difficult for human annotators (see e.g. the survey of Sverchkov and Craven [2] on automated design in biology).
Our main result can be viewed as theoretical confirmation that this type of question is indeed useful: derivative queries are necessary and sufficient for active learning univariate PTFs. We prove that if the learner is allowed access to sign(p(f) (x)) (the i-th order derivative of p). PTFs are learnable in OOog(1)/ (1e)) queries, but require (2(1e) /s) queries if the learner is missing access even to a single relevant derivative. We generalize this upper bound to the batch setting as well, giving a smooth interpolation between query complexity and rounds of communication with data annotators (which
have costly overhead in practice).
We also study active learning PTFs beyond the worst-case setting. Specifically, we consider a setup in which the learner is promised that both points in E' and the underlying polynomial are drawn from known distributions. We propose a general algorithm for active learning PTFs in this model based on coupon collecting and binary search, and analyze its query complexity across a few natural settings. Notably, our algorithm in this model avoids the use of derivatives altogether, making it better adapted to scenarios like learning natural imagery where we expect the underlying distributions to be nice, but may not have access to higher order information like derivatives. Finally, we note that all of our upper bounds (in both worst and average-case settings) actually hold for the stronger 'perfect' learning model in which the learner aims to query-efficiently label fixed 'pool' of data with zero error. Perfect learning is equivalent to active learning in the worst-case model [3] 3), but is likely harder in the average-case and requires new insight over standard techniques in our setting.
We end our work with a preliminary analysis of active learning multivariate PTFs, where we prove a strong lower bound showing access to derivative information is actually insufficient active learn even degree-two PTFs in two variables. We leave upper bounds in this challenging regime (e.g. through distributional assumptions, additional enriched queries) as direction of future research.
1.1 Background
We briefly overview the basic theory of PAC-learning (in both the "passive" and "active" settings) and of the main model we study, perfect learning. We cover these topies much greater detail in the supplementary materials. PAC-Icarning, originally introduced by Valiant [14] and Vapnik and Chervonenkis [5), provides a framework for studying the learnability of pairs (X, H) where X is
By this we mean that adaptivity and the active model provide no asymptotic benefit over the standard "passive" PAC-model.
2

---

set and H = {h: X 11,1]} is a family of binary classifiers. A class (X, H)) is said to be PAC-leamable n)E,,) samples if for all E. 0, there exists an algorithm which for all distributions D over X and classifiers h E H, intakes labeled sample of size and outputs good hypothesis with high probability:
Pr (erTD, (A(S, S 2 6, S-im
where erD,,
P. Z A (()) # h(r)). Active learning is modification of the PAC- PAC-paradigm where the learner instead draws unlabeled samples, and may choose whether or not they wish to ask for the label of any given point. The goal is to minimize the query complexity q(E,)) 8), which measures the number of queries required to attain the same accuracy guarantees as the standard "passive" PAC-model described above. In the batch setting, the learner may send points to the oracle in batches. This incurs the same query cost as in the standard setting (a batch of m points costs m queries). but allows for finer-grained analysis of adaptivity through the round complexity r(e,8) 8) which measures the total number of batches sent to the oracle.
In this work, we study challenging variant of active learning called perfect learning (variants of which go by many names in the literature, e.g. RPU-learning [16]. perfect selective classification [1], and confident learning | In this model, the learner is asked label an adversarially selected size-n sample from X. The query complexity q(n) (respectively round complexity r(n)) is the expected number of queries (respectively rounds) required to infer the labels of all points in the sample. Perfect learning is well known to be equivalent to active learning to small factors in query complexity in worst-case settings, and is least hard the latter in the average-case discuss these connections in more depth in Section 2
We
In this work, we study the learnability of (E. Ha), the class of degree (at most) d univariate PTFs. In the worst-case setting, we allow the learner access to derivative queries: for any x E IR in the learner's s sample, they may query (ign(f()) (x)) for any i O..... and (() is f itself.
where f(() is the i-th derivative of
1.2 Results
Our main result is that univariate PTFs can be computationally and query ehery-efficiently learned in the perfect model via derivative queries.
Theorem 1.1 (Perfect Learning PTFs). The query complexity of perfect learning (R, Ha) with derivative queries is:
A(dlogn) n) S q(n)= S. Odd log n)..
Furthermore, there is an algorithm achieving this upper bound that runs in time Ö(n)).
By standard connections with active learning, this implies PTFs are active learnable in query com- plexity ((dlog(1/e)) S q(e, 5) Ô (d3 log((:)) when the learner has access derivative queries.
Theorem I.] is based on a deterministic algorithm that iteratively learns each derivative given higher order information. This technique necessarily requires a large amount of adaptivity which can be costly in practice. To mitigate this issue, we give a randomized algorithm that extends Theorem [.] to the batch setting, providing a smooth trade-off between (expected) query-optimality and adaptivity.
Theorem 1.2 (Perfect Learning PTFs Batch Setting). For any n E N and (1/log(n), 11, there exists a randomized algorithm perfectly learning size subsets of (IR, Ha) in
n
((1) 50
a
expected queries, and
r(n) < 1+ 2
expected rounds of adaptivity. Moreover, the algorithm can be implemented in Ö(n) expected time.
"In fact, this model actually precedes active learning, and has long been studied in the computational geometry literature for various concept classes such as halfspaces [17].
3

---

When a O[))))(())) this recovers the query complexity of Theorem 1.1 in expectation, but also gives much broader range of options, e.g. sub-linear query algorithms ((1) rounds of communication. In fact it is worth noting that even in the former regime the algorithm uses only ((log(n)) total rounds of communication, independent of the underlying PTF's degree. Finally, note that run-time is also near-optimal since (2))) time is required even to read the input.
To complement these upper bounds, we also show that PTFs cannot be actively learned all if the learner is missing access to any derivative.
Theorem 1.3 (Perfect Learning PTFs Requires Derivatives). Any learner using label and derivative queries that is missing access f() for some S i - d must make at least
((n) 2 9(n)
queries to perfectly learn (R. Ha).
This implies the query complexity of active learning PTFs with any missing derivative is 12(1/E).
In some practical scenarios, our worst-case assumption over the choice of distribution over IR and PTF h E Ha may be unrealistically adversarial. To this end, we also study a natural average case model for perfect learning, where the sample S C IR and PTF h E Ha are promised to come from known distributions. Section we show derivates are often unecessary this regime by providing generic label-only algorithm and proving query efficiency in basic scenarios. This is better suited than our worst-case analysis to practical scenarios like learning natural 3D- ---imgerry where we expect objects to come from nice distributions but don't ton't necessarily have higher order information.
We start by considering the basic scenario where both the sample and roots of our PTF are drawn uniformly at random from the interval [0, 1], a distribution we denote by Ujo.1]-
Theorem 1.4 (Learning PTFs with Uniformly Random Roots). The query complexity of perfect learning (R. Ha) when promised that the sample and roots are chosen from (0o1) is:
Ad n) S q(n) < (d² log d log n.)
While studying the uniform distribution is appealing due to its simplicity, similar results can proved for somewhat more realistic distributions. As an example, we study the where the (intervals between) roots of our polynomial are drawn from a Dirichlet distribution Dir(a), which has pdf:
f(1 - Id+1) x
II
where v, 2 0 and Στ; = This generalizes drawing a uniformly random point on the d-simplex. Theorem 1.5 (Learning PTFs with Dirichlet Roots). The query complexity of perfect learning (R, Ha) when the subsample $ U(0.1] and h ~ Dir(a.) is at most
(()) O dd log dloog n)
for a = 1 for a 2 2, and for a 2 2(log" n).
((n) = (d log + d dllog n)
((n) = (rd log m)
Moreover, this result is tight for constant a and sufficiently large n.
So far we have only discussed univariate PTFs. One might reasonably wonder to what extent our results hold for multivariate PTFs. fact, we show that derivative queries are insufficient (in the worst-case setting) for learning PTFs of even two variables.
Theorem 1.6 (Derivatives Can't Learn Multivariate PTFs). Let (R22, Hz) denote the class of degree- !wo, two-variate PTFs. The query complexity of perfectly learning (R², H2) is
q(n) M(r),,
even when the learner may query the sign of the gradient and hessian any point in its sample.
In other words, multivariate PTFs cannot be actively learned via access to basic derivative queries in the worst-case. It remains an interesting open problem whether there exist natural query sets that can learn multivariate PTFs, or whether this issue can be avoided average-case settings; we leave these questions to future work.

---

1.3 Related work
While to our knowledge active learning polynomial threshold func- tions has not been studied in the literature, the closely related problem of learning halfspaces is perhaps one of the best-studied problems in the field, and indeed in learning theory in general. It has long been known that halfspaces cannot be active learned in the standard model (2), but several series of works have gotten around this fact either by restricting the adversary, or empowering the learner. The first of these two methods generally involves forcing the learner to choose nice marginal distribution over the data, e.g. over the unit sphere [18), unit ball [19). log-concave [20], or more generally s-concave distributions [2I]. The second approach usually involves allowing the learner to ask some type of additional questions. This encompasses not only KLMZ's s
Active Learning Halfspaces:
[ notion of enriched
queries, but also the original "Membership query" model of Angluin to query any point in the overall instance space X rather than just on the subsample S C X. This model also particularly well-studied for halfspaccs where it is called the point-location problem 77 [9] and was actually studied originally by Meyer auf der Heide [77 in the perfect learning model even before Angluin's 's introduction of active learning.
22 who allowed the learner
17 25
Bounded degree PTFs may be viewed as a special set of halfspaces via the natural embedding to {1,z, 22, J...). Given this fact, it is reasonable ask why our work is not superseded by these prior methods for learning halfspaces. The answer lies in the fact that the query types used in these works are generally very complicated and require infinite precision. For instance, many use arbitrary membership queries (which are known to behave poorly in practice (26)), and even those that sacrifice on query complexity for simpler queries still require arbitrary precision (e.g. the "generalized comparisons" of [8). Indeed, learning halfspaces even in three dimensions with a simple query set remains an interesting open problem, and our work can be viewed as partial progress in this direction for sets of points that lie on an embedded low-degree univariate polynomial. For instance, one could learn the set S {(x, 3x. 5x"): a E [n]] C R with respect to any underlying halfspace sign( (e. -) + b) in O(log n.) queries using access to standard labels and the derivatives of the underlying polynomial.
Active Learning with Enriched Queries: Our work also fits into long line of recent studies on learning with enriched queries in theory and in practice. As previously mentioned, Angluin's [22] original membership query model can in a sense be viewed as the seminal work in this direction. and
many types of problem-speciffe enriched queries such comparisons (27 4 3
28 29]
9 30)
cluster-queries [3I 39. mistake queries [40, separation queries [1]. and more have been studied since. Along with providing exponential improvements in query complexity in theory, many of
these query types have also found use in practice 4 42 43 12] Indeed even complicated queries such as Angluin's 's original model that cannot be accurately assessed by humans (26) have found significant use in application to automated experimental design, where the relevant oracle is given by precise scientific measurements rather than a human (see e.g. the seminal work of King et al. "The Automation of Science" (43)) While we view first or second order derivatives as reasonable query types for human experts, higher order derivatives are likely more useful in this latter setting, e.g. in application to dynamical systems where one tracks object movement with physical sensors.
Average Case Active Learning: The average-cast model we study in this work is the 'perfect' or 'zero-error' variant of the average-case active learning model introduced by Dasgupta 2 (and implicitly in earlier work of Kosaraju, Przytycka, and Borgstrom (44)). These works gave generic greedy algorithm for active learning finite concept classes (X, H) over arbitrary prior distributions whose query complexity is optimal to within a factor of O(log(( approximation were later optimized in the literature on submodular optimization [45), and more recently extended to the batch setting [46). These works differ substantially from our setting as they focus on giving a generic algorithm for average-case active learning, rather than giving query complexity bounds for any specific class.
The exact constants of this
Perhaps more similar to our general approach are active learning methods based on Hanneke's 's disagreement coefficient [7], and Balcan, Hanneke, and Wortman's 's 48] work on active learning rates over fixed instead of worst-case hypotheses. Analysis based on these approaches typically takes advantage of the fact that for fixed distribution and classifier, the minimum measure of any interval can be considered constant. Our average-case setting can be thought of as a strengthening of this approach in two ways: first we are only promised (weak) concentration bounds on the probability this
5

---

measure is small, and second we work in the harder perfect learning model. This latter fact is largely what separates our analysis, as naive attempts combining prior techniques with concentration lead to 'imperfect" algorithms (ones with small probability of error). Moving from the low-error to zero-error regime in general a difficult problem P but is important in high-risk applications like medical diagnoses Fixing this issue requires analysis of new 'capped' variant of the coupon collector problem, and proving optimal query bounds requires further involved calculation that would be unnecessary in the low-error active regime.
2 Preliminaries
We now cover basic background on learning with enriched queries before sketching the proofs of our main results. Detailed information on all background and full versions of all proofs can be found in the supplementary materials.
Learning with Enriched Queries: Recall our learner is allowed to make derivative queries, that is given I. the learner may query sign(f()()) for any S, S d 1. Such queries have a number of natural interpretations, e.g. the relative distance of objects in image recognition ("is the pedestrian getting closer, or further away?"). Given PTF f Ha and point x S, it is useful to consider the collection of all derivative queries on which we call its sign pattern.
Definition 2.1 (Sign Pattern). The sign pattern of x E R with respect to f Ha is the vector in {-1,1)
SgnPat(f. [sign(f(=)), (.. (
More generally, given a family of binary queries (e.g. labels and derivative queries), let (T) denote the set of all possible query responses to x T given h (when Q consists of derivative queries, Q (T) is the set of sign patterns in T). Since we can rule out any hypotheses h' E H such that Qn- (T) + Q (T), we will be interested in the set of consistent hypotheses, H HlQ. (T), which satisfy Qn (T) = (T).. We say that Qn (S) infers the label of point E X when only has one possible label under the set of consistent hypotheses, that is when for some {-1,1):
VM' E HlQx(s): si)n())) =2
Inference Dimension: In their seminal work on the enriched query model, KLMZ 3 introduced inference dimension, a combinatorial parameter that exactly characterizes the query complexity of both perfect and active learning under enriched queries.
Definition 2.2 (Inference Dimension). The inference dimension of (X, H) with query set Q is the smallest & such that for any subset S C X of size k, Vh E H, 3z E S s.t. Qa(S) \ {x}) infers x. If no such k exists, then say the inference dimension is
KLMZ proved that query-efficient learning is possible if and only if inference dimension finite.
Theorem 2.3 (Inference Dimension Characterizes Active Learning [3] Theorem 1.5]). Let (X, H) be a class with inference dimension i with respect to query set Q. The expected query complexity of perfectly learning (X, H) i
I(min(n, k)) S ((z)) Ox (logn).
Similarly, the query complexity of active learning (X, H) is most
() S Ox ((10g d + log
and if l = oc, active learning gives no asymptotic improvement over standard passive bounds: (c, 2 ((1/e).
'While the low-error (active) and zero-error (perfect) models are equivalent in the worst-case setting it not clear whether this is true in average-case settings.
*We note that in this setting, the more natural model is Rivest and Sloan's [6 Reliable and Probably Useful (RPU) Learning. where the learner can abstain with low probability but may emr. Perfect learning finite samples is essentially equivalent to the RPU model in most settings by standard generalization techniques. including settings we study.
Formally the upper bound has some dependence
well, which costs an extra factor of in setting.

---

Worst-Case Active Learning PTFs
3.1 Upper Bounds
In this section, we sketch the proofs of our upper bounds Theorem 1.1 and Theorem 1.2 At a high level, both results follow from the fact that a PTF can be query-efficienly broken into small number monotone segments which act like thresholds. This is done two main steps. First, we observe that it is possible to break f into small number of segments sharing the same sign pattern. Lemma 3.1. For any degree-d polynomial f E Ha and set = {81 S... S sa). given sign( (x)) for all S S k and x S, it possible to partition into ((d)) contiguous, disjoint segments
I = [$1, si,b, In = [$i,+1, 8:2),
1 = +1)
such that each interval has fixed sign pattern, i.e. for every 1 < l j and s, E Ig: SgnPat(s, f()) SgnPat(s' s (()).
Moreover, this can done in O(n(d + n)) time.
Second, we observe that must be monotone on any interval with a fixed pattern. Lemma 3.2. If E Ha and < b E satisfy SgnPat(f()). a) SgnPat(F(), b), then f is monotone on [a, b].
Based on these facts, not hard to see that Theorem I.] is realized by the following iterative algorithm that learns each derivative in a top-down fashion until reaching f(0) itself.
Algorithm 1: (TBRATIVE-ALGGORTMM((..)
Result: Label all points in S Polynomial f Ha. Subset S S R
Input:
Algorithm:
Learn f((-1)(x) by binary search
2 f d
3 while i 2 do
Apply Lemma 3.1 to f()), partitioning S into j < O(dd -)) monotone segments {4+}
Learn f(( by running binary search separately each Le
1
i+i-1
7 end
The iterative approach gives simple, deterministic technique for learning PTFs with derivative queries, but comes at the cost of high level of adaptivity. We now give simple randomized algorithm that smoothly interpolates between the query-efficient and low-adaptivity regimes.
Algorithm 2 is batch variant of KLMZ's original algorithm underlying Theorem 2.3 The following batch variant of their upper bound follows from similar analysis (setting m above to 2kn²).
Theorem 3.3 (Inference Dimension - Batch Active Learning). Let (X, H)) be a class with inference dimension i with respect query set Q. Then for any E N and (1/log //log()), 1] and size n-subset C X, BATCH-KLL KLMZ labels all of S in
((n) 2Qror (2kn")
expected queries, and only
r(n) 51+
expected rounds of adaptivity, where Quor(m) is the number of queries available set of m points.
To prove Theorem 1.2 it therefore suffices to show that PTFs have bounded inference dimension with respect to derivative queries. In fact, this is essentially immediate from Lemma 3.. and Lemma 3.2 Any Ha be broken up into (dd² monotonic regions based on sign pattern. Given any three points in such a region the middle can always be inferred, so by the pigeonhole principle we have:
Lemma 3.4. The inference dimension of (R, Ha) with derivative queries is (dd))
In the supplementary materials, additionally prove an M(d) lower bound inference dimension.
7

---

Algorithm 2: BATCH- KLMZ(S,m)
Result:
Labels all points
Input:
Class (X, Subset S S X, Query set Q, Query Oracle Oq
Parameters: Inference dimension k. Batch size m, Iteration cutoff t
log(2) log 25
Algorithm:
8
So 4
for in runge / do
10
++0
while Qn (I) infers less than a m-2k fraction of S do
11
Sample T 8
13
Query T: Qb t OQ(T)
14
end
S411 - for E S (T) does not infer x} if S I m then
16
Query (Q(S(+1)
18
Return
19
end
end
3.2 Lower Bounds
We briefly discuss the proof techniques behind our lower bounds in Theorem 1.1 and Theorem 1.3 The former follows from a standard information theoretic argument, noting that degree-d PTFs result in (d)) possible labelings of any point subset. For the latter, let Q; denote the family of derivative queries without the ith derivative. Theorem 2.3 shows it is enough to prove the inference dimension of (R, Ha) with respect to Q; is infinite. By a simple induction, is sufficient to consider i = d- 1-11 1. This is done by exhibiting for all E N a family of PTFs (h.P1,.... .... PP and points S {sy) with respect to Qa-1, but
(s , 8n) such that and Pj indistinguishable h(s;)) (0))x(0 (sy)) We achieve such a construction by building a set of polynomials where each p; (d-1) sufficiently negative around s; force the function flip sign, but the points are sufficiently spread out that this cannot be detected on any other sj for j + i..
Average-Case Active Learning PTFs
We now sketch the proof of our average-case results. We briefly recall the model: given distributions Dx over IR and DH over Ha. we are interested in analyzing the expected number of queries needed infer all labels of sample S Dx with respect to h ~ Dh. We now present simple generic algorithm for this problem we call "Sample and Search." Given sample S C R:
1. Query the label (sign) of points from S uniformly at random until either: (a) We have queried all points in S.
(b) We see d sign flips in the queried points, i.e. we have queried æ1,..., .. and there exists indices i
i such that
sign(f(a:,)) + (I
for all j = ......d d. 2. If (b) occurred in the previous step, perform binary search on the points in S' between each pair (Zig; Ri, .) to find the sign threshold (and thereby labels) in that interval.
hard see Sample and Search infers all labels of points in by construction. The main challenge lies in analyzing its query complexity, and in particular step which can be thought of as variant of the classical coupon collector (CC) problem. In our setting, the "coupons" are made up by the intervals between adjacent roots, and their probability is given by the mass of the marginal distribution on that interval. With this in mind, let Y the random variable measuring the number of samples required to hit each interval (coupon) at least once, and let Z min(Y,n).

---

Proposition 4.1. The expected query complexity of the Sample and Search Algorithm is at most:
g(n)= S EDx,Da [4 dlogn. n.
It is worth noting that EDx. [Z] and EDx. [ differ drastically. As a basic example, consider the case where d = and we draw our n points and one root uniformly at random from [0, 1]. It is a simple exercise to show that ED Dr [Y] oc, whereas Ex Du [Z] (log n). With this in mind, we finish the section by sketching the proof of our average-case results. We focus on the setting of the uniform distribution (Theorem 1.4). The Dirichlet case (Theorem [.5) follows similar overall ideas, but requires more involved calculation and machinery to deal with dependence of the roots. In both cases, however, the first step is observe the following standard bound on Y conditional on the roots being well separated.
Lemma 4.2. For any I E Rt, let Ex denote the event that f ~ Du has measure at least 1 over Dx between any adjacent roots, the leftmost root and 0, and the rightmost root and 1. Then:
DD Ex] S Oxælog
To analyze the capped variable Z min n). we expand the expectation and cap the integral:
f
ED Dy [
D EDx [
dl s (d+
1 PD [Dx [Y] æ/dr. (1)
Jo
d+1
By Lemma 4.2 the righthand probability is lower bounded by the probability the minimum interval which can be computed directly in the uniform setting:
measure (denoted M) is 12( log
e clog d (1 c(d (1- log d
PDu [Dxx M
M
(2)
x
x
Plugging this back into Equation and computing the integral gives BiZ| S Old log()). To
prove the corresponding lower bound for this problem (appearing in Theorem 1.4, we appeal to classic information theoretic techniques. In particular, the expected number of binary queries to reveal the labels of S cannot be less than the entropy of the resulting distribution over labelings. In the uniform case, one can directly show the entropy (dd log(n)). so Sample and Search is off from the information theoretic optimum by at most factor of d.
We briefly remark on the challenges moving to the Dirichlet distribution. Due to the dependence of roots in this setting, bounding the minimum measure M in Equation (2) becomes substantially more difficult. For small a, we union bound over each variable and directly analyze the marginal distributions. For large we appeal to strong Bernstein-type concentration bounds on Beta distri- butions of Skorski [49]. The lower bound follows from a similar appeal to information theoretic techniques. The trick in this case is to observe the induced label distribution is exactly the well-studied "Dirichlet-Multioomii distribution whose asymptotic entropy known (see e.g. (50 Theorem 2)).
Beyond Univariate PTFs
Finally, sketch the proof of Theorem I.6 our lower bound on learning two-variate quadratics with derivative queries. Recall in this setting the learner is allowed to make af (11.81)). and Hessian queries of the form v1), By 82
gradient queries of the form sign Oz (11.11))
0f
82 sign Gudo (11, dady (I1, V1), ay0z (11, aydy (x1, (I1.V1) for any (x1, RR2 in the learner's 's sample (along with standard label queries).
82f
82
As in our worst-case lower bound for missing derivatives, we prove the inference dimension of this class is infinite. Our construction consists of n points distributed evenly on the quarter circle of radius 1 in the first quadrant. Consider the functions -2² y² czy (with c small enough), which have negative values for all label queries, gradient queries, and diagonal entries of the Hessian, and either all positive or all negative values for the off-diagonal. The goal is then to find functions h;; which flip the label on the ith point, but are indistinguishable from one of -x²- - -y² + ezy elsewhere (at least half the points are therefore indistinguishable from one of these choices, which gives an inference dimension lower bound of n/2 for any E N).

---

The idea is to consider rotations of the function f= zy c18², which is only positive for small sector dependent on c₁. h; chosen be the rotation where this sector contains only the ith point. To ensure the derivatives and diagonal Hessian values remain negative, we subtract (2 + y - 1) which does not change the value on the unit circle. Since the Hessian is symmetric for these functions, they also agree with one of -x²- - y² + ezy on the off-diagona giving the desired result.
10

---

References
[1] Dana Angluin. Queries and concept learning. Machine learning, 294):319-342, 1988.
[2] Sanjoy Dasgupta. Analysis of a greedy active learning strategy. Advances neural information processing systems, pages 337-344, 2005.
[3] Daniel M Kane, Shachar Lovett, Shay Moran, and Jiapeng Zhang. Active classification with comparison queries. 2017 IEEE 58th Annual Symposium on Foundations of Computer Science (FOCS), pages 355-366. IEEE, 2017.
[4] Amin Karbasi, Stratis Ioannidis, et al. Comparison-based learning with rank nets, arXiv preprint 1206: 4674, 2012.
[5] Fabian L Wauthier, Nebojsa Jojic, and Michael Jordan. Active spectral clustering via iterative uncertainty reduction. In Proceedings of the 18th ACM SIGKDD international conference Knowledge discovery and data mining, pages 1339-1347, 2012.
[6] Yichong Xu, Hongyang Zhang, Kyle Miller, Aarti Singh, and Artur Dubrawski. Noise-tolerant interactive learning using pairwise comparisons. In Advances in Neural Information Processing Systems, pages 2431-2440, 2017.
[7] Max Hopkins, Daniel Kane, and Shachar Lovett. The power comparisons for actively learning linear classifiers. Advances in Neural Information Processing Systems, 33, 2020.
[8] Daniel Kane, Shachar Lovett, and Shay Moran. Generalized comparison trees for point- locat-location problems. In International Colloquium on Automata, Languages and Programming. 2018.
[9] Max Hopkins, Daniel Kane, Shachar Lovett, and Gaurav Mahajan. Point location and active learning: Learning halfspaces almost optimally. In 2020 IEEE 6lst Annual Symposium Foundations of Computer Science (FOCS), pages 1044-1044. IEEE, 2020.
[10] Myron L Braunstein. Depth perception through motion. Academic Press, 2014.
[11] Gareth Jones and Emma C. Teeling. The evolution of echolocation in bats. Trends in Ecology & Evolution, 21(3):149-153 2006.
[12] Yuriy Sverchkov and Mark Craven. A review of active learning approaches to experimental design for uncovering biological networks. PLoS computational biology. 10054466 2017.
[13] Ran Yl-vaniv and Yair Wiener. Active learning via perfect selective classification. Journal of Machine Learning Research, 13(Feb):255-2799 2012.
[14] Leslie G Valiant. A theory of the learnable. In Proceedings of the sixteenth annual ACM symposium on Theory of computing, pages 436-445, ACM, 1984.
[15] Vladimir Vapnik and Alexey Chervonenkis. Theory of pattern recognition, 1974.
[16] Ronald Rivest and Robert Sloan. Learning complicated concepts reliably and usefully. In AAAI, pages 635-640, 1988.
[17] Friedhelm Meyer auf der Heide. A polynomial linear search algorithm for the n-dimensional knapsack problem. Annual ACM Symposium on Theory of Computing: Proceedings of the fifteenth annual ACM symposium Theory of computing, volume 1983, pages 70-79, 1983.
[18) Maria-Florina Balcan, Alina Beygelzimer, and John Langford. Agnostic active learning. Journal of Computer and System Sciences, 75(1):78-88 2009.
[19] Maria-Florina Balcan, Andrei Broder, and Tong Zhang. Margin based active learning. In International Conference Computational Learning Theory, pages 35-50. Springer, 2007.
[20] Maria-Florina Balcan and Phil Long. Active and passive learning of linear separators under log-concave distributions. In Conference on Learning Theory, pages 288-316, 2013.
[21] Maria-Florina Balcan and Hongyang Zhang. Sample and computationally efficient learning algorithms under s-concave distributions. arXiv preprint 07777.7703.07758 2017.
11

---

[22] Dana Angluin and Philip Laird. Learning from noisy examples. Machine Learning, 2(4):343- 370, 1988.
[23] Stefan Meiser. Point location in arrangements of hyperplanes. Information and Computation, 106(2):286-300 1993.
[24] Jean Cardinal, John Iacono, and Aurélien Ooms. Solving k-SUM using few linear queries. arXiv preprint
2015.
[25] Esther Ezra and Micha Sharir. A nearly quadratic bound for point-location in hyperplane arrangements, in the linear decision tree model. Discrete & Computational Geometry, (4): 755, 2019.
[26] Eric Baum and Kenneth Lang. Query learning can work poorly when a human oracle used.
In International joint conference on neural networks, volume 8, page 8, 1992.
[27] Kevin G Jamieson and Robert Nowak. Active ranking using pairwise comparisons. In Advances in neural information processing systems, pages 2240-2245 2011.
[28] Max Hopkins, Daniel Kane, Shachar Lovett, and Gaurav Mahajan. Noise-tolerans reliable active classification with comparison queries. In Conference on Learning Theory, pages 1957-2006. PMLR, 2020.
[29] Zhenghang Cui and Issei Sato. Active classification with uncertainty comparison queries. arXiv preprint arXiv:2008. 2004000000 2020.
[30] Max Hopkins, Daniel Kane, Shachar Lovett, and Michal Moshkovitz. Bounded memory active learning through enriched queries. arXiv preprint arXiv:2/02.05047, 2021.
[31] Hassan Ashtiani, Shrinu Kushagra, and Shai Ben-David. Clustering with same-cluster queries. arXiv preprint (tle::606.22000 2016.
[32] Sharad Vikram and Sanjoy Dasgupta. Interactive bayesian hicrarchical clustering. In Interna- tional Conference on Machine Learning, pages 2081-2090, 2016.
[33] Vasilis Verroios, Hector Garcia-Molina, and Yannis Papakonstantinou. Waldo: An adaptive human interface for crowd entity resolution. In Proceedings of the 2017 ACM International Conference Management of Data, pages 1133-1148, 2017.
[34] Arya Mazumdar and Barna Saha. Clustering with noisy queries. In Advances in Neural Information Processing Systems, pages 5788-5799, 2017.
[35] Nir Ailon, Anup Bhattacharya, and Ragesh Jaiswal. Approximate correlation clustering using same-cluster queries. In Latin American Symposium on Theoretical Informatics, pages 14-27. Springer, 2018
[36] Donatella Firmani, Sainyam Galhotra, Barna Saha, and Divesh Srivastava. Robust entity resolution using crowdoracle. IEEE Data Eng. Bull., 41(2):91-103, 2018.
[37] Sanjoy Dasgupta, Akansha Dey, Nicholas Roberts, and Sivan Sabato. Learning from discrimi- native feature feedback. Advances in Neural Information Processing Systems, 31:3955-3963, 2018.
[38] Barna Saha and Sanjay Subramanian. Correlation clustering with same-cluster queries bounded by optimal cost. arXiv preprint 1rXiv:1908.04997 2019.
[39] Marco Bressan, Nicolò Cesa-Bianchi Silvio Lattanzi, and Andrea Paudice. Exact recovery of mangled clusters with same-cluster queries. arXiv preprint urXiv:2006.04677 2020.
[40] Maria Florina Balcan and Steve Hanneke. Robust interactive learning. In Conference on Learning Theory, pages 20-1, 2012.
2012.
[41] Sariel Har-Peled, Mitchell Jones, and S. Rahul. Active learning convex body low dimensions. In ICALP, 2020.
12

---

[42] Buyue Qian, Xiang Wang, Fei Wang, Hongfei Li, Jieping Ye, and lan Davidson. Active learning from relative queries. In Twenty- Third International Joint Conference on Artificial Intelligence. Citeseer, 2013.
[43] Ross D King, Jem Rowland, Stephen G Oliver, Michael Young, Wayne Aubrey, Emma Byme, Maria Liakata, Magdalena Markham, Pinar Pir, Larisa N Soldatova, et al. The automation of science. Science, 324(5923):85-3) 89, 2009.
[44] S Rao Kosaraju, Teresa M Przytycka, and Ryan Borgstrom. On optimal split tree problem. In Workshop on Algorithms and Data Structures, pages 157-168. Springer, 1999.
[45] Daniel Golovin and Andreas Krause. Adaptive submodularity: A new approach to active learning and stochastic optimization. In COLT, pages 333-345, Citeseer, 2010.
[46) Hossein Esfandiari, Amin Karbasi, and Vahab Mirrokni. Adaptivity in adaptive submodularity. In Conference on Learning Theory, pages 1823-1846. PMLR, 2021.
[47] Steve Hanneke. A bound on the label complexity of agnostic active learning. In Proceedings of the 24th international conference on Machine learning, pages 353-360, 2007.
[48] Maria-Florina Balcan, Steve Hanneke, and Jennifer Wortman Vaughan. The true sample complexity of active learning. Machine learning, 80(2):111-139, 2010.
[49] Maciej Skorski. Bernstein-type bounds for beta distribution. arXiv preprint arXiv:2101.020% 2021.
[50] Krzysztof Turowski, Philippe Jacquet, and Wojciech Szpankowski. Asymptotics of entropy of the dirichlet-multnnoiial distribution. 2019 IEEE International Symposium on Information Theory (ISIT), pages 1517-1521,
13

---

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]
(b) Did you include complete proofs of all theoretical results? [Yes]
3. If you experiments..
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either the supplemental material or as 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 are using existing assets (e.g., code, data, models) or curating/releasing new assets...
(a) If your work uses existing assets, did you cite the creators? [N/A]
(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 a URL? [N/A]
(d) Did you discuss whether and how consent was obtained from people whose data you're rou'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 conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, if applicable? [N/A]
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent participant compensation? [N/A]
14


Reviews:
[{"review_id": "vno4DaM93B9", "reviewer": "Reviewer_up2u", "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. ", "questions": "Some minor questions are listed here:\n\n- 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?\n- 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?\n- 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.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The strengths and weaknesses of the submission are compiled below. \n\n**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. \n\n**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. \n\n**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. ", "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": "UJ4FIM5DvHT", "reviewer": "Reviewer_SBJT", "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.\n\nThe 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).\n\nIn 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.\n\nThese 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.\n\nThey also state some distribution-dependent result for common families of distributions.\n\nLastly, 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.", "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?\n\nWhile 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:\n\nAre large-margin bounds possible? Maybe related: Do bounds on the Lipschitz constant of the polynomial help?\n\nAre there (simple) first positive results for multivariate polynomials? Maybe with even more powerful queries?\n\nThere 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? ", "rating": 8, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "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.\n\nThe authors discuss related work and introduce necessary background. \n\nThis work is a strong introduction into this novel learning problem, devising near-tight bounds and efficient algorithms. Also various related aspects are discussed.\n\nMinor suggestions:\n* is perfect learning the same as \"exact learning\" (e.g., Hegedűs, Tibor, COLT 1995). Maybe mention it, as well in the related work.\n* $f^{(0)}$ is not really defined, is it just $f$ itself (see e.g., line 106).\n* the $p^{(i)}$ notation seems to be not yet defined in line 60.\n* line 344: a \",\" missing in the Hessian? Also how exactly is the sign of a vector defined?", "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": "T4Ifd3KW-_V", "reviewer": "Reviewer_RjhJ", "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.\nThe 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).\n", "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.", "rating": 8, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "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. \n\nQuality: 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. \n\nClarity: The paper is well-written. Below line 251, ‘d’ is undefined (though it is defined in the supplementary material) .\n\nOriginality: 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.\n\nOverall, a good theoretical work. I recommend that the paper be accepted.\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": "JmNJpe9vx72", "reviewer": "Reviewer_LNSA", "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).\n\nTheir 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. \n\nThey 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.\n\nFinally, they show that if we increase the dimension, then derivative queries cannot learn PTFs. \n\n", "questions": "I would like to know the authors opinion about my question above.", "limitations": "no limitations", "rating": 6, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "1. Overall, I find the results very interesting, especially the lower bounds. \n2. 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.\n3. 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.\n\nWeaknesses/Questions:\n1. 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)$?\n\nOther:\nI suggest the authors to put a definition of perfect learning in an environment (lines 98-101).\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": {}}]

Author rebuttal:

Decision: Accept