Active Learning of General Halfspaces: Label Queries vs Membership Queries
Authors: Ilias Diakonikolas
Daniel Kane
Mingchen Ma
Venue: NeurIPS 2024 poster (2024)
Keywords: Active Learning
Membership Query
Linear Separator
Primary area: learning_theory
TL;DR: We study learning general halfspaces under Gaussian marginals using queries, proving a strong separation between the classic active learning model and membership query learning model for the problem.

Abstract: We study the problem of learning general (i.e., not necessarily homogeneous) 
halfspaces under the Gaussian distribution on $\mathbb{R}^d$ 
in the presence of some form of query access. 
In the classical pool-based active learning model, where the algorithm is
allowed to make adaptive label queries to previously sampled points, 
we establish a strong information-theoretic lower bound ruling out non-trivial
improvements over the passive setting. Specifically, we show that
any active learner requires label complexity of 
$\tilde{\Omega}(d/(\log(m)\epsilon))$, where $m$ is the number of unlabeled examples. 
Specifically, to beat the passive label complexity of $\tilde{O}(d/\epsilon)$, 
an active learner requires a pool of $2^{\mathrm{poly}(d)}$ unlabeled samples.
On the positive side, we show that this lower bound 
can be circumvented with membership query access, 
even in the agnostic model. Specifically, we give a computationally efficient 
learner with query complexity of $\tilde{O}(\min(1/p, 1/\epsilon) + d\mathrm{polylog}(1/\epsilon))$
achieving error guarantee of $O(\mathrm{opt}+\epsilon)$. Here $p \in [0, 1/2]$ 
is the bias and $\mathrm{opt}$ is the 0-1 loss of the optimal halfspace. 
As a corollary, we obtain a strong separation 
between the active and membership query models. 
Taken together, our results characterize the complexity of learning 
general halfspaces under Gaussian marginals in these models.

Active Learning of General Halfspaces: Label Queries vs Membership Queries
Ilias Diakonikolas" University of Wisconsin- Maddison ilias@cs. eisc
Daniel M. Kane"
University of California, San Diego dakane@cs, uesd.edu
Mingehen Ma*
University of Wisconsin- mingchen@cs. wisc. edu
Abstract
We study the problem of learning general (i.e., not necessarily homogeneous) halfspaces under the Gaussian distribution on IR in the presence of some form of query access. In the classical pool-based active learning model, where the algorithm is allowed to make adaptive label queries to previously sampled points, we establish lower bound ruling out non-trivial improvements
strong peormatiinn-hhoreee over the passive setting. Specifically, we show that any active learner requires label complexity of ((d/(log(m)))) where m is the number of unlabeled examples. Specifically, to beat the passive label complexity of Ö(d/e), an active learner requires a pool of 2Poly(d) unlabeled samples. On the positive side, show that this lower bound can be circumvented with membership query access, even in the agnostic model. Specifically, we give computationally efficient learner with query complexity of Ó(min (1pp, 1/e] + dpolylog(1/e) (1/e)) achieving error guarantee of Ooppt + e). Here E [0, 1/2] is the bias and opt is the 0-1 loss the optimal halfspace. As corollary, we obtain strong separation between the active and membership query models. Taken together, our results characterize the complexity of learning general halfspaces under Gaussian marginals in these models.
Introduction
In Valiant's PAC learning model [Val84a, Va184b], the learner is given access to random labeled examples and aims to find accurate approximation to the function that generated the labels. The standard PAC model "passive" in the sense that the learner has no control over the selection of the training set. Here we focus interactive learning between learner and domain expert that can potentially lead to significantly more efficient learning procedures. A standard such paradigm is (pool-based) active learning [MN+98] 98], where the learner has access to large pool of unlabeled examples S and has the ability to (adaptively) select a subset of and obtain their labels. We will henceforth refer to this type of data access label query access. An that of PAC learning with membership queries [Ang88, Fe109]. A membership query (MQ) allows the learner to obtain the value of the target function any desired point in the support of the marginal distribution. This model captures the ability to perform experiments or the availability of expert advice. While in active learning, the learner allowed to query the labels of previously sampled points from S, in MQ learning the learner has black-box access to the target function. We refer the reader Appendix A for formal definitions of these two learning models. Roughly speaking, when
stronger interactive model
Equual Contribution
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

the size of S becomes exponentially large (so that it is good cover of the space), the model of active learning "converges" the model of learning with MQs. This intuitive connection will be useful in the proceeding discussion.
Active learning is motivated by the availability of large amounts of unlabeled data at low cost. As such, the typical goal in this model is to develop algorithms with qualitatively improved label complexity (compared to passive learning) at the expense of a larger- but, ideally, still reasonably bounded- set of unlabeled data. Over the past two decades, a large body of work in theoretical machine learning has studied the possibílities and limitations of active learning in a variety of natural and important settings; see, e.g. [FSST97, Das04, Das05, DKM05, BBZ07, BHV10 H 14, HY DMRT24? J.
A prototypical setting where active learning leads to substantial savings is for the task of learning homogeneous Linear Threshold Functions (L.FFs) or halfspaces. An LTF is any function h : Rd -> {+1} of the form h(x=)= sign(w: 2: + f), where 5 is called the weight vector and & is called the threshold. If = 0, the halfspace is called homogeneous. The problem of learning halfspaces is one the classical problems in machine learning, going back to the Perceptron algorithm [Ros58] and has had great impact on many other influential techniques, including SVMs [Vap97] and AdaBoost [FS97].
For the class of homogeneous halfspaces under well-behaved distributions (including the Gaussian and isotropic log- log-concave distributions), prior work has established that log (1/)) label queries suffice, where d is the dimension and E is the desired accuracy [BBZ07, DKM05, BL13]. Moreover, there computationally efficient algorithms with near-optimal label complexity for this task [ABL17, YZ17, She21], even in the agnostic model that achieve error ((pp++<). Unfortunately, this logarithmic dependence on 1/c breaks down for general (potentially biased) halfspaces. Intuitively, this holds because if the bias of a halfspacce (the probability mass of the small class) is p. then we need to obtain least 1/p labeled examples before we see the first point in the small class. This implies an information-theorrtie label complexity lower bound of Mmin { 1/pp 1/e for realizable PAC learning under the uniform distribution on the sphere. Hanneke et al. [BHV I0] showed an information- -hemattio-tthoortiic label complexity upper bound of ((L1p) halfspaces under the uniform distribution on the sphere (via an exponential-ting algorithm).
//]-+ + e log( (/e)) [Das05], even
log(L/e) for general
In summary, prior to this work, the possibility that there is an active learner with label complexity (d [dloo((//c) + min /1/p. 1/c]) and unlabeled sample complexity poly(d/c) remained open. Our first main result is an cormmation-theoretee lower bound ruling out this possibility.
Theorem 1.1 (Main Lower Bound). For any active learning algorithm A, there is a halfspace ht that labels S with bias p such that if A makes less than (dd/ (p log(m))) label queries over S, a set of m ii.d. points drawn from N (0, I), then with probability at least 2/3 the halfspace h output by A has error more than p/2 with respect to h².
In particular, if is chosen as O(E log(1/e)), learning a p-bias halfspace with error Ce (for any fixed constant C) would require learning algorithm to either make (((d/) label queries or have a pool of 2d unlabeled examples. Our information -thooretic lower bound essentially shows that the active setting does not provide non-trie non-trivial advantages for the class of general halfspaces, unless the learner is allowed to obtain exponentially many unlabeled examples. (As already mentioned, in this extreme setting, the active learning model approximates PAC learning with MQs.) This motivates the study of learning halfspaces in the stronger model with MQs, where better upper bounds may be attainable.
To circumvent the aforementioned lower bound, we consider the stronger model of PAC learning with MQs. We are interested in understanding the query complexity of learning general halfspaces under the Gaussian distribution. We study this question in the agnostic learning model and establish the following positive result, the proof of which can be found in Appendix G:
Theorem 1.2 (Main Algorithmic Result), Consider the problem of agnostic PAC learning halfspaces with membership queries under the Gaussian distribution. There is an algorithm such that for every labeling function y(æ) and every 6 E 1), it makes M = (min{1/p 1/c] -dpolloolyyy memberships queries, runs in poly(d, M) time, where p is the bias of the optimal halfspace h", and outputs an h E H such that with probability at least 1 - d, err(h) < Oopp +e).
In this paper, we use Os to hide the dependence on polylog (1/6))
2

---

In other words, we provide a computationally efficient constant factor agnostic query learner with query complexity (mmin(1/p. 1/c] - dpolylog(1/e)) Due to known dBoly(1/<) complexity lower bounds for achieving optimal error of opt + [DKZ220, DKPZ21, DKR23), the majority of work [DKS18, DKTZ22] in the passive PAC model has focused on designing efficient learners achieving a constant factor approximation of (( passive learning algorithms have sample complexity poly(d, 1/e). Note that, by Theorem 1.1. it is impossible to modify these algorithms (for general halfspaces) to achieve an active learner with low label complexity.
In the realizable setting under the Gaussian distribution, a learner may query many points that are extremely far from the origin to find examples from the small class with few queries. However, such an algorithm is quite fragile to even tiny amount of noise. In particular, the query complexity achieved by our algorithm establishing Theorem 1.2 nearly optimal in the agnostic setting.
On the one hand, (d (og(/c) queries are required because describing a halfspace up to error c requires d dllo((/e) (1/c) bits of information [KMT93]. On the other hand, we argue that the overhead term of (2(mmm(1//) 1/c]) cannot be avoided in the agnostic setting. Such a statement can be deduced from a lower bound of [HKLL20]: they showed that in the realizable setting, any algorithm requires at least (((1p))==(1) MQs to see the first example from the small class (where p is the bias of the target halfspace with respect to the uniform distribution on the unit ball); they also showed a similar lower bound of (2(1p) if the underlying distribution is the uniform distribution over the unit sphere. As the dimension d increases, the standard Gaussian distribution is very well approximated by the uniform distribution over a d-dimensional sphere with radius ~ vd. Thus, an exponentially small level of noise would make every query far from this sphere contain useful information. This allows us show that, under the Gaussian distribution with a tiny amount of label noise, (2((Lp))'00) ((()) queries are needed to see a single example from the small class. The proof of this statement is essentially identical to the argument in [HKL200 for unit ball. The reader is referred to that work for the details.
1.1 Preliminaries
For halfspace = =ig)=sign( x t), E St- O, we use p(t) Pr (h(x) = 1) to denote its bias. For a halfspace h(x), we define its Chow-Parameter under the standard Gaussian distribution to be Ez~N(0.1) æh(x). Let y(r) Ed + [+1} be (randomized) labeling function for examples in R4, We denote by err(h)
(t) + v(=)) to be the error of the hypothesis h and opt minke и err(h), where H is the class of halfspaces over Rdd We will use h" to denote the halfspace with an error equal to opt. When there is no confusion, we will use to denote the bias of the optimal halfspace h".
Let Dr be a distribution over Rd, y(z) be a labeling function over Rd and S ((,,,,((;)) ) be a set of i.i.d. examples drawn from the distribution D over Rd x {+1] such that the marginal distribution of D is Dz, A membership query takes an æ in the support of Dz as input and outputs vxx).. A label query takes an F;, where (æi, v(x))) E S as input and outputs y(x;). learning algorithm A is allowed to use membership queries/label queries and aims to output halfspace hypothesis h such that (fr(h)- O(opt + e) by making as few queries possible.
2 Nearly-Tight Lower Bound on Label Complexity: Proof of Theorem 1.1
In this section, prove our information theorrtic lower bound on the label complexity of active learning general halfspaces under the Gaussian distribution.
Before presenting our proof, we provide high-level intuition behind Theorem 1.1 and the strategy of our proof. Previous work, see, e.g. [Das04, DKM05, HKL.00, showed that if is a set of examples drawn uniformly from the unit sphere, and if h- is a halfspace with bias that is chosen uniformly, the following holds: no matter which query strategy a learning algorithm A uses, for the first r queries, in expectation only pr of them fall into the small cap on the sphere cut by ltt. Thus, if A makes less than 1 1/(2p) queries, it will with constant probability not see any negative examples; and it is therefore impossible to learn the target halfspace.
3

---

In the Gaussian case, we will use similar but stronger idea. If we are able to learn h" up to error p/2 with few queries, then we can randomly partition S into two sets, use the first set to learn the halfspace and use the second part to find d negative examples by paying another ((d) queries in expectation. Formally, we have the following statement, the proof of which can be found in Appendix B.1.
Lemma 2.1. Suppose there is an active learning algorithm that can make r label queries over a pool S of m 2 poly(d/p examples drawn from ((0, T) and learn any halfspace h² h=(x)) sign(w" xx+tt" with bias p up to error p/2 with probability at least 2/3. Then there is an algorithm such that given a
pool of 2m random examples S drawn from the standard Gaussian distribution with hidden labels
by some halfspace ht (xx) = sign(w" x + t²) with bias p. it makes r + Odd) queries and finds
negative examples from S with probability 1/2.
We will show that finding d negative examples from S requires many queries. The idea is that since S is sampled from a standard Gaussian in high dimensions, every pair of examples is almost orthogonal unless m is as large as 2d. If we have made 1/c queries over S and found our first negative example, then this negative example will only provide us with very little knowledge to find the next negative example- as no example in the pool has large correlation with it. Therefore, it will still take us another approximately 1/c queries to find the next negative example. Such an issue only disappears after we have already found roughly d negative examples; at which time, the average of the d examples has a good correlation with w'. Therefore, would take us roughly d/e queries in total. We remark that such an argument is hard to formalize, because, besides negative examples, the algorithm has also seen many positive examples in the process. It is thus challenging to argue that the algorithm cannot make good use of the information obtained from these positive examples.
To overcome this difficulty, our proof strategy works as follows. Each algorithm A can be described as a decision tree. Each tree node represents the example queried in given round. Every time the algorithm sees a negative example, moves to the left; otherwise, it moves to the right. Suppose that
A wants to find k negative examples with queries. Then there are at most (X) I (er/k))* paths of the tree, where A successfully finds k negative examples, and for each of the paths there are exactly
k examples that are negative upon queried. For a k-tuple of examples, we will derive deterministic condition such that if the k examples satisfy the condition, a random halfspace with bias p will have only roughly de probability to label all of the k examples negative.
Formally, we establish the following technical lemma (see Appendix B.2 for the proof).
Lemma 2.2. Let A R be a matrix with row vectors 21...., .Kk Let C >> 0 for some sufficiently large constant C. Let h² = sign(u (w" I + t*) ) be a random halfspace with bias with w" ~ 5 chosen uniformly from 5 if || - a s (t)((t)))) then with probability at most O (pplog(1/p)) where p is the bias of h- under the Gaussian distribution, h (x+) - for i = .k. k.
Thus, if the ( tuples all satisfy such a condition. then A will succeed with a fairly tiny probability unless r is larger than k/pp. So, in the last step of the proof, we will show in Lemma 2.3 that by taking with high probability every k-tuple of examples in S will satisfy the
k z d/ d/(log(m))p (ologmmm))lylg(11/////1 deterministic condition. Thus, no algorithm can succeed with constant probability, unless it makes ((d/pp D(d//plog(m)) (og(m))) queries. The proof of Lemma 2.3 can be found in Appendix B.3.
Lemma 2.3. Let S C Edd be a set of m examples drawn i.i.d. from N I). Let to > C >>00 0 for sufficiently large constant C and k- O(d/ log(m)(t*)) )t). Then, with probability at least 2/3, for every k-tuple of examples (ZI,..., Ix) C S, AA dI 1l2 S d/(t)),, where A E lxd be matrix with row vectors Fi,..., Tt.
Proof of Theorem 1.1. We will start by showing that, given a set S of m points drawn i.i.d. from Gaussian distribution, the following holds. With probability at least 2/3, for every algorithm A there exists a halfspace h- = sign(w" x + t*) with bias p such that if AA makes only = (dd/plog(m) label queries over S. then with probability at least 2/3 it will not be able to find negative examples in S for some ho < d. By Yao's minimax principle, it is sufficient to show that there is a distribution over halfspaces h1 such that for any deterministic active learning algorithm, the following holds: given mn random Gaussian examples, if the learning algorithm makes r queries, with probability 2/3 cannot find l negative examples. We will fix the threshold 1" of ht and draw w" uniformly from the unit sphere.

---

By Lemma 2.3, we know that by choosing k = (dd log log(m) (t"))) with probability at least 2/3, for every k-tuple of examples 111...., F. E S. || d S d/ where A E R is a matrix with vectors .1...., Zk.. By Lemma 2.2, we know that every k-tuple of examples #1,.... 2* E S has a probability a², which is at most Opp log p)* to be labeled all negative by the random halfspace ht.. Notice that every query algorithm can be expressed as a binary tree T. Each node of the tree represents an example where the algorithm makes queries at time. If the example at node is negative, then the algorithm will query the left child of v, and otherwise it will query the right child of v. The algorithm stops making queries when either it has queried r examples or it has queried k negative examples. In particular, for given search algorithm, there are at most (x) different possible outcomes where it successfully finds k negative examples. Furthermore, for each of the possible outcomes, there a set of it examples in S that correspond to the negative examples the algorithm finds. Thus, the probability that the algorithm successfully finds k negative examples is bounded above by the probability that there exists one of the (x) k-tuples of examples in S that are all labeled negative by h², Such probability can be bounded above by
[ (1) at = (Tx T ((plogg)()) s 2/3,
(pd(pllog(n)))) (ogglmllyyyyyog//))) By Lemma 2.1, we know that if we can make O(d/ (p log(m) lolpoommooyllo(..... (olyyogg(//)) label queries to learn a p-biased halfippace up to error p/2 over set S of m/2 Gaussian examples, then we can use ('d/ (p log(m) polyllooyyg////) queries to find d negative examples among m Gaussian points. This leads to contradiction. Thus, the label complexity of the learning problem is ((d/(plog(m)) as desired.
r S O(k/plog(L/p))
3 Robust Learning of General Halfspaces with MQs: Proof of Theorem 1.2
In this section, we present our main algorithmic result, Theorem 1.2. We refer the readers to Appendix G for the full proof of Theorem 1.2. Throughout the paper, we will assume for convenience that the noise level opt S c. Such an assumption can made without loss of generality, as discussed in Appendix C.I. We first present our main algorithm, Algorithm 1. Algorithm I will maintain a list of polylog(1/c) candidate hypotheses at least one of which has error (opt + c). We will then use a standard tournament approach to find an accurate hypothesis among them.
Algorithm 1 QUERY LEARNING HALFSPACE(Efficien Agnostic Learning Halfspaces with Queries)
Input: error parameter E (0, 1), confidence parameter E (0,
Output: halspace i(x:)) sign(W i), where i S , 0
C C00
> Create a list of candidate hypothesises C
Use (minn1//p 1/ch) queries to estimate p by some ý such that P S S 28 (or verify < Ce and return +1, the constant hypothesis).
Let ta. to > such that a halfspace with threshold ta has bias 2p and with threshold to has bias p. Build grid points la2 > Guess the true threshold 1² with l' E (lo, (o.,4.....
< < .... < Lp 4, such that |1++1 4. = (og(l1/ (1/))))())))))))) vi < 1-
for j . 1b do
Repeat the following procedure polylo)()/))oo(((0)) times
Wp < INITIALIZATION(G, tj, //polylog(1/c)
> Find a wy E 1d as a warm start Find a wr E Sd-1 close enough to w² and
(WT, 2) + REANF (Wa, Ljz e.6 has//oollog11////
i close enough to t* based on wo
Add new candidate hypothesis to C Find a good hypothesis from C using Lemma C.I, a standard tournament approach return/
C C UU (sign(WT - x x +{}
At the beginning of Algorithm I, we will use random queries to approximately estimate the bias p of the optimal halfspace up to a constant factor. As we will discuss in Appendix C.2, such an estimation can be done with only Ó(min (1/p, 1/e)) queries by applying a doubling trick to the coin estimation problem. In particular, if we find p Ce, can directly output a constant hypothesis as it has
5

---

error only O(e). Since t* is unknown to us. such an approach can prevent us from using some t' which is much larger than in the rest of the learning procedure, which will potentially lead to a larger query complexity. With such a ý. 1. will fall into reasonable range [La, fo]. We next partition [ta,ta) into a grid of size 0(1/ / log(1/e)) and use each of the grid points as an initial guess of t². In particular, at least one of these grid points i, is O(1 (1c) close to t". Although such 1 is not accurate enough to be used in the final output hypothesis, as l" S (loo((/ee, we will show later that such a Lj is enough for us to use it to learn w", L accurately. Suppose now we have such a good 1z. We will design two subroutines that make use of t to produce a good hypothesis sign( x + f). The first algorithm will take i, and the noise level c as its input and produce a unit vector we as an initialization. We will show in Section 3.2 that as long as It3 - t-| S 1 11/log(1) (c)),, we can with probability at least 1/ log (1/c) produce some We such that ((wg. w S ((1/t)). By repeating such an initialization algorithm polylog(1/e) times, with high probability one of these runs will succeed.
In particular, such algorithm has query complexity of O(L/p p- + dpolylog (L/e)) Now assume have such a wo as a warm-start, Our second subroutine is to refine the direction wo and the threshold ty. More specifically, we will maintain a unit vector wi such that 0; = 0(w; w=) and an upper bound og for sin(0,/2) In each round of the refining algorithm, we will use ((d) queries to update w/g- In particular, in each round o; will decrease by a constant factor and thus after at most T (llo((1/)) rounds, we will have (frr2) I or = Cc exp(t3/ /2). As we will show in Section 3.1, provided the correct t", sign(w7 (WT + t*) is at most O(e) far from h" However, to output good hypothesis, we still need to learn L* up to a high accuracy. When 1* is small, we even have to estimate up to error (c)), which typically needs many queries. However, as we will show in Section 3.1, given wr close enough to w", we are able to combine the localization technique used in [DKS18] with this fact to learn t" using only (log(1/e)) queries. This gives overview of Algorithm and its query complexity.
3.1 Refining A Warm-Start
We will start by discussing how to refine a warm start we by proving the following theorem. The proof of the theorem and the main algorithm, Algorithm can be found in Appendix D.5.
Theorem 3.1. Let (z) sign(w* x + t²) be a halfspace such that err(h*) = opt S c. Let t' < Vlog(1/e), we E s be inputs of Algorithm 3. If t' - -1/ log(1/e) S t S v, t' exp((t')) S 1/(Ce) and sin(f(wo. w²) w²) S do == min(1/t', 1/22,, then Algorithm 3 makes M = (ddollloog)()/) membership queries, runs in poly(d, M) time, and outputs (wT,C) 8) such that with probability at least 0(6), err(sigu(wT x + 0)) - O(e).
St" St As we discussed in Section 3, we will assume we have some t' such that 1' - 1/og/// and some wo such that sin(0//2) 2) σ mi/(1 1/2), i.e., some initial knowledge of t", w". Our algorithm runs in iterations and will maintain some wy in round i. We will maintain some unit vector w; and use ||w, - w0|] = 2 (0000/ to measure the progress made by Algorithm 3. The method we use to update wa is simple projected gradient descent algorithm. Specifically, we will construct a random vector G, over R2 such that G, L w. and in expectation g; = E G. has bounded length and a good correlation with respect to w". We will show in the following lemma that by estimating E G, up to constant error with 9: and using the update rule w = projss 1 (w; + p.g.). we are able to significantly decrease 0, The proof of Lemma 3.2 can be found in Appendix D.
Lemma 3.2. Let w", W; E 5d-1 such that w" = a,w;; + bou, where u E 5 u 1 Wi, ag by > 0, at 13 = Let 0; A(w;, ) Let G2 be random vector drawn from some distribution DD such that with probability 1, G; 1 We Let 9: be the mean of G.. Let ge be the empirical mean of G; and pg O. The update rule 1i+1 = projsa-i (wi + mi.ie) satisfies the following property.
|| - w² 1 1| < ||w, - w01 -
-2p4b1g. - u + 2p,bbe ll - 9ell + p16 ||
Furthermore, (fsin(0./2) S σ; E (0, 1) and there exist constant C1, such that gi . 2 c1/10, < |ل
and [|g gil || < 02 S e1 /40, then there exist constant C1, C2 > 8 such that by
taking pr = as/Ci and 0:41 = (1- 1/C)),,, it holds that sin (0++1/2) S 0141- In particular, if sin (0./2) < 3/ and | ll S then sin (0:+1/2) S dit1 always holds.
In the rest of the section, we will show that as long as wi is not good enough, we can always efficiently construct random vector G. whose expectation points to the correct direction and we can use very

---

few queries to estimate its expectation up to desired accuracy. We adapt the localization technique used in [DKS18] achieve this goal.
3.1.1 Finding A Good Gradient via Localization
In the i-th round of Algorithm 3, we write w" a,8; + buu, where u, E @St-1, u; 1 wa, at 0i,b, > 0, a + by 1. Recall that og is an upper bound we maintain for si), We will construct the random gradient as follows
G = proiu -(u.),
where ~ N(0, 1), T juu and E (0,4') is scalar. To see why G; is good choice, we will start by analyzing G, assuming the noise rate opt = 0. To simplify the notation, denote by (2)) = sign((a,w, + bb,,//,)== (t* at)/o;) and gi = (o))( proju =l)(2) A simple calculation gives us the following result.
Fact 3.3. Ler h(x) = sign(w- x +o++ t) be a halfspace. Let u E S such that w = av + bu, where a, > 0, +02 = 1, u E 5d-1 u v. Let 8, o > 0 be real numbers and define A = -1--(1---) For each 2 E Rd define ă == A 1/2 - sv. Then h(2)) = E(z). where is the following halfspace
{(z) = sign( (av + bu/a) + +tt (t- -aass/))
Fact 3.3 implies that if opt 0. then it always holds that f((z) == y(A! 2--22zwu tw;) f((2), Vz Rd and we can view 2 as examples labeled by a halfspace (=). In particular, Eg-N(0.1) 2f)(2) :) is the Chow-Parameter of the halfspace (z) under the standard Gaussian distribution.
Fact 3.4 (Lemma C.3 in [DKS18)). Let h(x) = sign(w x + (), where w 5d-1 be a halfspace. Then E E zh(2) V 2 exp (-t2/2)w.
By Fact 3.4, in the noiseless case, 1 =f((z) is parallel to (a.w; + byus/o;) with length 1'- and 9: = T. is exactly the u, component of the Chow- ((exp(-T?)), where T: 0. o Parameter. In particular, if T; constant, then by estimating 9i using í up small constant error using ((d) queries, as o,t' < and b, I O(o,), it is easy to check T; can be bounded by some universal constant. However, as we mentioned before, we only know I ---t" t" Tog(1/e3 when w; getting close to w", o; could become very small and an error of 1/ log(1/e) could potentially blow up T, making the signal we want quite small. Such issue is problematic for the algorithm, especially when fi()) is a noisy version of (2).. To overcome such an issue, we prove the following structural lemma in Appendix D.2 showing that we can always check whether the choice of / is good or not, by looking at the bias of {(=), using (1) queries. Using this method, we can perform a binary search for to find a correct choice in most log(1/c) rounds. Furthermore, as long as we select the correct must hold that [ - 1" < (o;)) In particular, or Ce exp( (2)) such a / is a good enough estimate for 1" to be used in the final hypothesis.
able to use Lemma 3.2 improve ut, Assuming we set i = t',
S such that w" a,w; + b,ug where u, Sdd11 u 1 Wig ag b, > 0, a. + 62 = 1. Let t", ,t',, tt, be positive real numbers such that 0 S to I t, ta l<(z) sign((a,w; b.u./a.)z + (1" al) (),) and
Lemma 3.5. Let w", W/
S oi,
and oet' < Define Ti t6//0
g. EzeN(o..) projw (2) for some Ee '0,t). Then the following three properties hold.
There exists an interval Ie C [0, t') of length at least os such that for every E Le, [T]] S 5.
When [T:] S 6, it holds that gi u; = ||@a|| and e --9b, S |l < 119
3. For every [ 1*| > 40o and i < L', [T. > 10.
3.1.2 Robustness Analysis
So far, we have only considered the case when opt. O. Due to the presence of noise, is impossible for us to estimate g. EEEN((.)) proju, (2) because only have noisy version fi(z) of
7

---

(12).. In this section, we will show that as long as w; is close to w and It' - -1' S 1/ log(1/e), the probability that for a Gaussian point 2, (2) + f((2) is at most tiny constant. This is incomparable with the bias of (2) if is chosen correctly, and does not affect the algorithm too much. We start with the following lemma which bounds the probability of (((2 # f((z).
Lemma 3.6. Let (x)) sign(w" I + t²) be a halfspace such that err(h") = opt S c. Ler i o, l' be real numbers such that i S t' and o,l! S 11 S 1122. Let w² = a, + beug where w, E 5d-11, u I. Ws, 02, by > 0, 0,a + bi. 1. Define E4(2) = sign (a,w0 + bbus/a,)= + (1" - /oi) and fi(z) - = 2- tws). Then Prz~N(u,))liie + fi(=)) S exxp((² /2+ 4)/or. In particular, if a, 2 C (t)p(())2222) for some sufficient large constant C, then there is a sufficiently small constant с such that (r=-)No.)((((2)) # f((2)) S c c e-
The proof of Lemma 3.6 leverages the (u, s, o)- rejection procedure introduced in [DKS18] (see Appendix D.3). We will use Lemma 3.6 to analyze the gradient descent approach we described in the presence of noise. Formally, we establish the following lemma (see Appendix D.4 for the proof).
Lemma 3.7. Let w", W; E Sd-1 such that w' = a,W; + b,ug where u, E Sdd11 u 1 wi, at, b, > 0, at + bi = 1. Let 1", t", E,, be positive real numbers such that 0 < t*" S t', sin(0,/2) S os T, 2 (ex)((t))/2)), and o,t' S 1. Let h² (x) = sign(w" x + t*) be a halfspace such that ---
err (h*) opt S c. Define T; == o.v/2+62/off 4(=)) = sign((a,w, + b,u//o.)z + (t* - at) /
Di EMEN(O.I) proju! 2=1()) and 9i EsEN(on) proju? =f), where fi(e) = s(A!/² tw:: for some i E [0, 17, Let n = Nr # si(z)) and ps be the probubility that fi(z) = -1. Then the following two properties hold.
1. pf (e-18 11 1-11,, then [T. 6 and if [T:]]
< 5, then pi E (c-16 e-16
2. 9: u, 2 G. - - 2/en / log( 1/m) and | < | + 2 / log(L/m))
Lemma 3.7 says as the noise level is small, will not affect the structure lemma we established in Lemma 3.5 too much, and thus we are able to find the correct threshold i by checking the probability of f((z)= = -1. Furthermore, as long as we choose the correct threshold f, gs. the noisy version of g: still satisfies the conditions in the statement of Lemma 3.2 and thus can be used to improve w,.
3.2 Finding A Good Initialization
In Section 3.1, we have shown that given some wh non-trivially close to w² and some 1' such that t log{1/=] S t* < t', we can use Algorithm 3 to learn good hypothesis with high probability. In this section, we show how to find such good initialization wy using a few membership queries. The most common way to get such a warm-start is by robustly estimating the Chow- Parameter (see for example [She21, YZ17J) using Fact 3.4. Such an approach does not work for general halfspaces because the length of the length of the roughly d/p random queries to estimate. In this section, we show how to overcome such an issue using label smoothing technique, which has been useful in related problems [DKK+23], The main results in this step can be summarized as follows. The proof of Theorem 3.8 is deferred to Appendix E.2
can be as small as Ö(p), and thus needs
Theorem 3.8. Let het) = sign(w" x t²) and y(x) be any labeling function such that err(h") opt S c S 1/C for some large enough constant C. If (t --1 S 1/ (og(1/c), then with probability at least 1/3, Algorithm 2 makes M = Ó(1/ d loo((//)) (1()), runs in poly(d, M) time, and outputs ht/////gl/////))/ where 17 c/p.
some wy such that sin(f(ws, (Wo, w²) w²)/2) I max/min 1/2),
Due to the space limitations, here we only consider the case when /* is not extremely large, which roughly covers the regime when (r/loo((//)) 1/nn) < 1/t. This suffices to capture some of the ideas and illustrate the power of the smoothed labeling. For the case when 7/ ///oog11/ (l/g))))) 1/t, we still able to find such a warm start by leveraging the smoothed label method in combination with the technique used in Section 3.1 in a more complicated way. We postpone this analysis to Appendix F. Our algorithm, Algorithm 2, to find a warm start is presented as follows.
To analyze Algorithm 2, we introduce the following definitions and notations.
8

---

Algorithm 2 INITIALIZATION I ((Finding a good initialization under unextreme threshold)
Input: error parameter (0, 1), confidence parameter E (0, 1), threshold / > 0
Output: Wo E Sd Keep some I NO, 1) and query y(x) until see some zo such that y(zo) -1 for i .,..., m (d (od(oo)(()))) do
Sample 2, N(0 1) and query ((=6") == u(vi pp + pzi) with p min mi/nt1/t11)
Let ug 1 Σi= 20((z))) )
m
return Wp == uo uoll
Definition 3.9 (Smoothed Label). Let x E Rd be a point and y(z) be any labeling function. For
P E [0, 11, define the random variable ā = v1- p²xx + pz, where z ~ (N, The smoothed label of with parameter p defined as ū(x)) :- v(ā).
We will require the following fact (whose proof follows via direct calculation):
Fact 3.10. Let h² (z) sign(w" x ++) be halfspace. Let x, E Re and define ā := V1 p²x pz. Then h(=)= == 11" (z) = sign(w" 2 + (1" + +11 - p²w=" x)/p) is another halfspace for = with
threshold (t* + /1 pp x\/p.
Let h* = sign(u" w= I + t*) be an optimal halfspace and let y(x) be any labeling function such that err(h") = opt I c. For x E Rd, we denote by n)x) := Pr(h (ø) + "(z)). the noise level of the smoothed label. Assuming that are given a random negative example Fu, then with constant probability, it is close to the decision boundary, i.e., w" 300 E (-1" 7., -("). This implies that the threshold of h, the halfspacc corresponding to the smoothed label at To. is between (-1,1), 1). Moreover, the Chow-Parameter of under the standard Gaussian distribution is parallel to w" with constant length, by Fact 3.4. If opt 0, then for every S Vlog(1/e), we only need another (od((/c)) queries to estimate the Chow-Parameter of h up to error (1//t); thus, we get a warm start We such that sin(0 < 1/t, given it t- t'1 is small. Therefore, the total number of queries use to Algorithm 2 is Ó(1/p d (log(1/)) However, in general, it is impossible to estimate w" up to arbitrary accuracy - even using an infinite number of queries - because of the presence of noise. In fact, using random 20 is important for Algorithm 2 to succeed. If we are given some adversarially selected Zo. even if it is close to the decision boundary, the above method can easily fail. This is because almost all the queries we made are in a small neighborhood of xo and could be corrupted by noise arbitrarily. However, we show in Appendix E. that, with a probability at least 2/3, the noise level n7(2)) of the smoothed label around Zu at most (c/p), if xo a random example given y(z))= = 11; and thus we can still estimate w" to a desired accuracy provided c/p is not too large.
t²) be a halfspace and y(x) be any labeling function such that err(h") opt S Let (O, conditioned on y(æ:) =-1 be Gaussian example with negative label. 1f > for some large enough constant C, then with probability at least 1/2 we have 17(z)) 5c/p and w" E (-t" 1/t", )²)
Lemma 3.11. Let h² (x) = sign(w" x t²)
Finally, we briefly discuss how obtain a warm start when the threshold 1" is very large. The details of this method can be found in Appendix F. By Theorem 3.8, when is small, we are only able to get some wi such that sin(0 w²)) < OogyTog(11/)) for e/p. One possible approach to use the localization technique we use in Section 3.1 to refine such wo. However, such an approach fails because after localization the noise rate would be possibly larger than the length of the Show-Parameter that we want to estimate. This makes it impossible for to learn the useful signal. On the other hand, [DKS18] gave a randomized localization method that can make the expected noise level sufficiently smaller than the length of the will succeed with constant probability in each round of refinement. Unfortinately, such an approach cannot used in a query-efficient manner, because to implement such a method we need to know 0wws, w²) up to an error 1/ log(1/e). in each round of refinement. This implies that if we make random guess of 0 (ws, w " the probability of success in each round drops to only 1/ log(1/e). which requires to rerun the whole algorithm too many times in order to succeed once.
we want to estimate; and thus

---

Such an issue could be addressed in similar but more complicated way to the method we use in Lemma 3.5, by looking at the bias of the halfspace after localization. The second issue is that even the noise level is smaller than the length of the Chow-Paramete we want to estimate, the length of the Chow-Parameter is only 1/p", for some small constant c, as we can only make 0g smaller than some small constant. This still requires to use d/pº queries to estimate it. Such an issue can again be addressed using the smoothed label method, where we use only 1/pf queries to search a small class example and use another (dd queries to estimate the Phow-Parammttr. Importantly, even such method only succeeds with constant probability overall. As the refinement stage only runs for Olog log(1/e)) rounds, we only need to rerun the entire algorithm ([log(1/e) times to succeed once.
Acknowledgement
Ilias Diakonikolas was supported by NSF Medium Award CCF-2107079, NSF Award CCF-1652862 (CAREER), Sloan Research Fellowship, and a DARPA Learning with Less Labels (LwLL) grant. Daniel M. Kane was supported by NSF Medium Award CCF-2107547 and NSF Award CCF-1553288 (CAREER). Mingehen Ma was supported by NSF Award CCF-2144298 (CAREER).
References
[ABL17] Pranjal Awasthi, Maria Florina Balcan, and Philip M Long. The power of localization for efficiently learning linear separators with noise. Journal of the ACM (JACM), 63(6):1-27, 2017.
[Ang88] Dana Angluin. Queries and concept learning. Machine learning, 2:319-344 0022,3222 1988.
[BBZ07] Maria-Florina Balcan, Andrei Broder, and Tong Zhang. Margin based active learning. In International Conference Computational Learning Theory, pages 35-50. Springer, 2007.
[BV100] Maria-Florina Balcan, Steve Hanneke, and Jennifer Wortman Vaughan. The true sample complexity of active learning. Machine learning, 80:1 1-119,, 2010.
[BL13] Maria-Florina Balcan and Phil Long, Active and passive learning of linear separators under log-concave distributions. In Conference on Learning Theory, pages 288-37 -16. PMLR, 2013.
[Das04] Sanjoy Dasgupta. Analysis of a greedy active learning strategy. Advances in neural information processing systems, 17, 2004.
[Ds055] Sanjoy Dasgupta. Coarse sample complexity bounds for active learning. Advances in neural information processing systems, 18, 2005.
[DG03] Sanjoy Dasgupta and Anupam Gupta. An elementary proof of a theorem of johnson and lindenstrauss. Random Structures & Algorithmss 22(1):60-65. 2003.
[DKK+23) Ilias Diakonikolas, Daniel M Kane, Vasilis Kontonis, Christos Tzamos, and Nikos Zarifis. Agnostically learning multi-index models with queries. arXiv preprint arXiv:2312.16616 2023. Conference version in FOCS'24 24.
[DKK*24] 24] Ilias Diakonikolas, Daniel Kane, Vasilis Kontonis, Sihan Liu, and Nikos Zarifis. Effi- cient testable learning of halfspaces with adversarial label noise. Advances in Neural Information Processing Systems, 36, 2024.
[DKM05] Sanjoy Dasgupta, Adam Tauman Kalai, and Claire Monteleoni. Analysis of perceptron- based active learning. In Learning Theory: 18th Annual Conference Learning Theory, COLT 2005, Bertinoro, Italy, June 27-30, 2005. Proceedings 18, pages 263. Springer, 2005.
10

---

[DKPZ21] I. Diakonikolas, D. M. Kane, T. Pittas, and N. Zarifis. The optimality of polynomial re- gression for agmostic learning under gaussian marginals in the SQ model. In Proceedings The 34th Conference Learning Theory, COLT, 2021.
[DKR23] I. Diakonikolas, D. M. Kane, and L. Ren. Near-optimal cryptographic hardness of agnostically learning halfspaces and relu regression under gaussian marginals. CoRR, abs/2302.06512, 2023.
[DKS18] Ilias Diakonikolas, Daniel M Kane, and Alistair Stewart. Learning geometric concepts with nasty noise. In Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, pages 1061-1073, 2018.
[DKT722] Ilias Diakonikolas, Vasilis Kontonis, Christos Tzamos, and Nikos Zarifis. Learning gen- eral halfspaces with adversarial label noise via online gradient descent. International Conference Machine Learning, pages 51 5118-5141. PMLR, 2022.
[DK720] Ilias Diakonikolas, Daniel Kane, and Nikos Zarifis. Near-optimal sq lower bounds for agnostically learning halfspaces and relus under gaussian marginals. Advances Neural Information Processing Systems, 111156666-1596,, 2020.
[DMRT24] Ilias Diakonikolas, Mingchen Ma, Lisheng Ren, and Christos Tzamos. Fast co-training under weak dependence via grreambbased active learning. In Forty-first International Conference Machine Learning, 2024.
[Fe109] Vitaly Feldman. On the power of membership queries in agnostic learning. The Journal of Machine Leurning Research, 10:163-182, 2009.
[FS97] Y. Freund and R. Schapire. decision-theoreee generalization of on-line learning and an application to boosting. Journal of Computer and System Sciences, 55(1):119-139 1997.
[FSST97] Yoav Freund, H Sebastian Seung, Eli Shamir, and Naftali Tishby. Selective sampling using the query by committee algorithm. Machine learning, 28:133-168, 1997.
[H* 14] Steve Hanneke et al. Theory of disagreement-basel active learning. Foundations and Trends@ in Machine Learning, 7(2-3):131-33) 2014.
[HKL20] Max Hopkins, Daniel Kane, and Shachar Lovett. The power of comparisons for actively learning linear classifiers. Advances in Neural Information Processing Systems, 33:6342- 6353, 2020.
[HY15] Steve Hanneke and Liu Yang. Minimax analysis of active learning. J. Mach. Learn. Res., 16(1):3487-300,, 2015,
[KMT93] Sanjeev R Kulkarni, Sanjoy K Mitter, and John N Tsitsiklis. Active learning using arbitrary binary valued queries. Machine Learning, 11:23-35, 1993.
[KM224] Vasilis Kontonis, Mingchen Ma, and Christos Tzamos. The gain from ordering in online learning. Advances in Neural Information Processing Systems, 36, 2024.
[MN+988 Andrew McCallum, Kamal Nigam, et al. Employing em and pool-based active learning for text classification. In ICML, volume 98, pages 350-358. Citeseer 1998.
[Ros58] Frank Rosenblatt. The perceptron: a probabilistic model for information storage and organization in the brain. Psychological review, 65(6):386, 1958.
[She21] Jie Shen. On the power of localized perceptron for label-optimal learning of halfspaces with adversarial noise. In International Conference on Machine Learning, pages 9503- 9514. PMLR, 2021.
[Val84a] L. Valiant. A theory of the learnable. Communications of the ACM, 114111111341114 1984.
[Val84b] I. G. Valiant. theory of the learnable. In Proc. 16th Annual ACM Symposium on Theory of Computing (STOC), pages 436-445. ACM Press, 1984.
11

---

[Vap97] Vladimir N Vapnik. The support vector method. In International conference on artificial neural networks, pages 261-271 Springer, 1997.
[Ver18] R. Vershynin. Ilihh-Dimensional Probability: An Introduction with Applications in Data Science. Cambridge Series in Statistical and Probabilistic Mathematics. Cambridge University Press, 2018
[YZ17] Songbai Yan and Chicheng Zhang. Revisiting perceptron: Efficient and label-optimal learning of halfspaces. Advances in Neural Information Processing Systems, 30, 2017.
12

---

Supplementary Material
Here we give an organization of the supplementary material. In Appendix A, we present the formal definition of agnostic learning with membership queries and label queries. In Appendix B, we present the omitted proofs in Section 2 about the information -atetritntteeoeicclal lower bound. In Appendix C. we discuss why we can without loss of generality assume the noise level opt I and how to learn p up to constant factor with (11/p) queries. In Appendix D, we present the omitted proofs in Section 3.1 about how learn a good hypothesis given a good initialization. In Appendix E.2, we present the omitted proofs in Section 3.2 about how to find a good initialization when the threshold is not extremely large. In Appendix F, we design an algorithm that finds a good initialization when the threshold is very large. In Appendix G, we prove Theorem 1.2.
A Active Learning with Membership Queries and Label Queries
Definition A.1 (Active Learning Halfspace with Membership Queries). Let H {/(x)) sign(w: I ++1) +)= Rd + [ w E 1 0} be the class of halfspaces over X = = The labeling function y(x) X {+1] is random randomfunction that maps each X to an unknown binkrr random variable. For each h E H. denote by err(h) = Pr (h(z) # y(z)). opt == miDSCH erT and le (x) = sign(w" - x + 1*) any halfspace with error opt. A membership query takes x E X as an input and returns a label y ~ y(x)) We say learning algorithm A is a constant-approximate learning algorithm for every labeling function v(z), and for every Ō E (0, 1), it outputs some h E H by udaptively making memberships queries, such that with probability at least 1 6, err(h) I Oopt E). The query complexity of A is the total number of membership queries it uses during the learning process.
Definition A.2 (Active Learning Halfspace with Label Queries). Let H = =[b(x)= sign(w - I +):
Rd {=1}1 I we E 5 1 2 0} be the class of halfspaces over X = =Rk.. Let D be distribution over dRd x } such that D., the marginal distribution over x is the standard Gaussian distribution (0, 1). For each h E H, denote by err(h) = ((( (h(x)= + v). opt == minneH err sign(w w= x + t²) any halfspace with error opt. Let S be a set of m i...d. labeled examples drawn from D. An active learning algorithm with label query is given S but with hidden labels and is allowed to make a label query for each x E S and see its label y. We say learning learning algorithm if for every distribution D and for every 6 E (0, 1), it outputs some h E H by adaptively making label queries over a set of m examples drawn i.i.d. from D. such that with probability at least 1 - 8, err(h) S O(opt + <). The label complexity of A is the total number label queries made over S during the learning process
and h² (x)
algorithm A a constant-approxmnan
B Omitted Proofs in Section 2
B.1 Proof of Lemma 2.1
Proof of Lemma 2.1. Let A be such a learning algorithm. We select random set of m examples S1 and give eтror p/2 2 with respect to h", This implics that given a Gaussian example, with probability at least p/2 it will predict negative, and given it predicts negative, with probability least 1/2 it is actually negative. Since m is at least poly(d, 1/p), we know that with enough high probability, at least ((d) examples will be predicted by negative by h and at least constant fraction of these examples are actually negative. Thus, given such h with probability least 3/4, we can find d negative examples in S by randomly querying (d) examples that are predicted as negative by h.
A. With probability at least 2/3, A makes queries and learns halfspace h with
B.2 Proof of Lemma 2.2
Let u = Aw" = (w* UI,...., w² xK) T. Consider the projection of w" over the subspace spanned by the row vectors of A. ATAATAAA (AAT)- Aw"",
Aw". Assuming that .i...., Zy all negative, then ||aa| >
13

---

k(tt)?. This implies that the square of the norm of the projection of w* onto the subspace is B = (w*)TAT A (AAT)-AAw"
v (AAT) 2 ||ll / /I|AA T 1l 2 /(t*) ||
Since w" is uniformly chosen from the unit sphere, by Lemma B.1 in [KMT24], the square norm of wt projected onto fixed k k-dimensional subspace is random variable drawn from a beta distribution B =z²). By Lemma 2.2 in [DG03], if AA
112 S d(1 ((1((1))))
Pr B 2 /(t))////////////////// ((t))/|/AATT
112) & exp
k
d(t
)2
1 - log(
d(1T)²
))
2
AAA
112
|AA 112
(t*)
1 d(tT)²
exp(-
1))
||ATT12
||A ll2
O((()) exp(- (t*)²
k
2 (1 0(1/(t))))))
(19) 1) &
(O(()))) 1 exp(-
- (O(plog(1/))))
1'
2
The last inequality follows by Fact D.4.
B.3 Proof of Lemma 2.3
We will first show that for a given A E Rxxd ||AAT dd|12 is small with high probability the rows of A are drawn ii.d. from d-dimensional standard Gaussian. Let be an 1/4-net of 5 According to [Ver we know that [W] S ea and ||AAT diI|2 I 2uuPuEN |w (AAT dr)u Thus, to show that || AAT d/||, is small with high probability, it is equivalent show with high probability for every u E N,, |u (AAT - dd) is small.
Fix E N to be unit vector. We have
a AA TA du T u Σ(u (u A,)² d. j=1
Notice that each T AA is a standard Gaussian variable and thus Σラ= (u A,)² chi-squared distribution with freedom d. By [Ver18], have
Pr
(u A2) d 2 2Ed < 2exp (-d(2/2)..
Since [W < ak, we know that
Pr (|AAT dT|1, 2 Ed)
< Pr
|u (AAT ddyu > 2nd uEN
sup
$ 2exp(33k dg2
Since there are at most (T) such t-tuples of examples, the probability that there exists a k-tuple such
that AA dl|/2 is larger than éd = ((d((t))) is at most
2 m k
exp(3k - -55 2
em & k
=loogerr//// /b))) s 2/3. exp(3h - dE² < 2 exp(-(dE²) 3k 3
by choosing io (((log(r)()))) and 011((t)33.
C Omitted Details in Section 3
C.1 Discussion the Noise Level opt
Assuming we know some a such that S a/2 S opt S a, then learning h upto error O +) is equivalent to learning it up to error O(a). By guessing e2' for i = O,..., (llog(//e),
14

---

can always obtain desired a and use it to run the learning algorithm and get a good hypothesis. Such an approach will generate list of ((log(1/e) different hypotheses, finding good enough hypothesis among them only costs polylog(1 queries using standard tournament approach, such as the following lemma.
Lemma C.I (Lemma 3.6 in 24))+ Let e, E 1) and D a distribution over R x {0, } Given a list of hypothesises (* 1==1; there is an algorithm that draws O(k² log log(k/6)/e) unlabeled examples from D and performs O(k² log(d/5)) label queries in poly(d, (d, e, e, times and output a hypothesis h such that
(h(x) + v) s 10 min (2,9)n
Pr
Pr (1 + 4) te.
#E (-a))~
C.2 Approximate Bias Estimation Using Queries
In this part, we describe a simple approach to estimate the bias p up to constant factor using ((1/p) queries. To do this we will estimate Præ--N(.
1),,))))) the noise version of p as -1),
[ -p S e. If we can estimate ý such that 2/2 S S p or verify that p s (C - 1)e, then á satisfies our purpose.
By Chebyshev's ' inequality. if < 3p/4, then taking O(1/p) random queries at x and computing able verify this fact by checking whether the empirical probability is less than 5p/6. On the other hand, if 4p/5 S S p. with probability 2/3 are able verify this fact by checking whether the empirical probability is greater than 5p/66 6. Furthermore, by repeating this approach O(log(1/8) times and using a majority voting trick,
the empirical probability of (z)) = -1, with probability 2/3,
boost the probability of success up - 6. We will the above approach for I = (4/5) / for i = 0, I,... until we find p 2 (4/5)p or C'e for some constant C". In the first case (4/5)p < 5 < (25 p and find good approximation for p and thus for p. In the second case, we can conclude that is smaller than (e))
D Omitted Proofs from Section 3.1
Algorithm REFINE(Learn the correct direction w* based on a warm start wo)
Input: Intial direction wp 1d-1 1, 1'' > O, an approximate threshold, error parameter E (0, 1),
confidence parameter 8 E 10
Output: wr E Sd-1, an approximation w", i IR an approximation of t*
Let é' Cte /2) m Od), ((lo(()/e)) do + min(1/tt,1/2) Let C1, C2 be large enough constants
for i = 0,..., do do
A T Find & E 2c,..., t'} using the following binary search method, if no such i is found, then stop the algorithm and return WT = & Find the correct threshold construct the gradient.
1l-oo)oue w;,t M4 <- a./Ci
Draw (llo)()))) Gaussian samples x ~ N (0. f). query A! 2 tw, and compute p(t), the empirical probability that a query returns 1. If p() < e e-17, properly decrease f, if p(t) > e 17 properly increase Otherwise, declare that f is found. for j = 1, ..... do
Draw 2j ~ N(o, I), make queries at ě₁ : A!/22, 2, Ews, and denote by fi(2y) the result Construct the gradient Gradient Descent Use the threshold found in the last round
S: + 1 プØ projw; (z)f((2;))
WH+1 projs-- (w; (4g.)) 0:41 (1- 1/C2)0;
Z-i
return WT,
D.I Proof of Lemma 3.2
Proof of Lemma 3.2. We first observe that
|| |1:41 w² 1| llprojga- (w; + (...)) (oojs=r(w""]] < I|ws + n.g. =='
15

---

It remains to upper bound ||u, + MsGi - w² We have
|0 + pr.e w" 112 ||ws - w w=11" 2uiri (wi w²) u ||
||w; w 11 2449: w" + u 11
I|w; w" 1| 2p4g: w² + 2u ..) - w- + μ |1
||w; wt 112 2/49: w² + 24,, (9: 9:) b,u + 14 11 1
I|l; wt 1| 2/49: w² + 2p l19: 9ill μf 9 Il?
||w, - w 112 24 2 2p,b, 11 - All + pf 1
Here, in the second equality, we use the fact that D. w; and in the fourth equality, we use the fact that (gs- 9i) =w= = (g: 9:) a,w; + (0: 9:) b,u (gi 9.) beu.
Next, assume that (in(0; /2) o; and show that we can carefully choose parameter (4; 044 1 to make (0 < 0++1- We consider two cases. In the first case, we assume / (0,/2) S dg. Since ||w; w01 = 2 sin d: by Lemma 3.2, we have
2
sin 0++1
0 ) ,² 5p;b: 2p.cob: + p.ce +
(2 sin
2
s 4 c
S 40 5a/c1 (20)) +
+ +
$ 4(1 5c, /cl/(8C)) + = : -11-
where use the fact that b, S 2 sin (0:/2) s 3 and the fact that C₁ can be made large enough. In the second case, we assume sin (0. < 3 4. In this case, using the fact that
0 sin( 0i ()) = ||l;+1 - =' lw. w1ll I [ will S I|u, + 149. - will = 14; 11
2(sin( 2
We have
0i+1
0:
O2+1
(
0++1
sin(
di+1 - -sin(
(sin(
sin
2
2
30;
|
1
1
C ),,20
0+1
C₁
C2
where the last inequality holds because the parameter C1, C2 can be chosen larger than 8.
Lemma 3.2 implies that if has enough correlation with respect to w, but is also not too long, then by estimating I. up to some error, we can ensure I|w, w=Il drops significantly each round. Formally, we have the following corollary.
Corollary D.1. In Algorithm 3, denote by 0, 0ww", wi). Assume that sin < as. If there exist a suitable constant ei and a small enough constant C2 such that w"' 2 110 || S ei and l1g. g.ll S C2. Then there exists large enough constant C1, O2 such that by taking p4 a Et/C1, holds that sin
8i+1 2
< (1 - 1/O2)o
Proof of Corollary D.I. Since I|w; w0 sin 8. by Lemma 3.2, we have
0.+1 )² < (2 8: - 5140 + +24020 + t4
(2sin
2
< 40 - 50/c1/Ci + 20202/ (ogo2/Ci+@00l c
< Ao² 50 + 20 22
< 4(1 5c//(4C;) + =
where the third and the fourth incqualities hold when C₁ is large enough.
16

---

D.2 Proof of Lemma 3,5
Proof of Lemma 3.5. We first prove Item 1. Since T; is monotone decreasing function on i, and
t", it remains to show that for every i such that t"
[7, s Notice that
1" a.t
1"
a,l
i
az
i
L*
Ti
+
+15
5.
(I)
0 0IV a 0//03
0i
0:
0
By Fact 3.3, we know that
2 exp( -T,
biu:/o;
=
v 1//07
Since +a/ 2 / and [T I 5, we immediately obatin Item Finally, we prove Item 3.
Using the monotone property of T, we prove the case where t < t" -00; and the case > t" + +40; proved symmetrically. We have
- az
i- at
400;
T. = 0: 0.V 0 + o
4 2 10,
0.
0.va + 1//0
V50;
where the first inequality holds because Equation (1).
D.3 Proof of Lemma 3.6
To prove Lemma 3.6, we first introduce the following definition called (v, a)- rejection procedure. Definition D.2 ((v, s, a)- rejection procedure). Let u E Rd be unit vector and a be real numbers such that a < 1. Given a point x E Rd, (v, o)- rejection procedure accepts it with probability
exp (- - --1(0-))(0
- (1/011))//22
and rejects it otherwise.
(v. 8, 0)) rejection procedure satisfies the following property.
Lemma D.3 (Lemma C.7, Lemma C.8 in [DKS18)). If (0, 1) is fed into the (v,s,o) rejectioi procedure, then it is accepted with probability a exp(-s²//20)) - 0 ))) In particular, when as S and < 1/2, the accepted probability is at least exp(-s² 4). Moreover, the distribution conditioned on acceptance is that of (-ssu, Av,a),
where A = (1 0 yoo"
Proof of Lemma 3.6. Let ã := A1/2 Tw By Fact 3.3, know that (((=) h 11()), Rd. By Lemma 3.6, we know that if N(0, T), then ~ N(-tw;; A:), which be by feeding Gaussian random vector into the (w;, E, a.) -rejectoo procedure conditioned acceptance. Since err(h*) = opt I and the accepted rate at least o exp(-= s2 /2 - 4), we know from Lemma 3.6 that
Pr (L((2) + f((2)) 2~N(0.1)
Pr (h* + fa(z)) < ccxp(#/2+ 4)/or.
s~N((
In particular, of 2 C' (txp((t')222)) we have eexp(e/2 4)/o, < (Eexp(P//2+ + 4)) (Ceexp((U)}/22) =e//0==cse"
D.4 Proof of Lemma 3.7
Before presenting the proof, we state the following two facts that will be used in our proof.
Fact D.4 (Komatsu's ' Inequality). For any t E R the bias of a halfspace h(x) sign(w" + +)) can be bounded as
2 exp( exp(-11/2)
Sps 2 exxp(-12/2)
T VTL+VP= -
aL+ 44
17

---

Fact D.5 (Lemma B.4 in [DKTZ22]). Let D be distribution on R& x {+1} with standard normal I--margin and let w, u be two orthogonal unit vectors. Let B be any interval over and let S(x. y) be any event over I& { such that S(x, v) _ {w-x E B3 then holds
Pr(w- E EB), Pr(S(x,
(lu al ((((x, v)}) s 2/e PV log( D
Proof of Lemma 3.7. We start by proving the first part of Lemma 3.7. By Lemma 3.6, know
that M/s == Prz~ (4)(2) + f((=)) I e This implies that PPr (f:(z) = -1) - pi s
e 40 We first show that when is in reasonable range, [2 < 6. Assuming by contradiction that
[T:l 2 6, then by Fact D.4, the bias of (z)) must be most exp(-1, / (2T;) < 20 which
implies that it cannot be the case where P; E (e_ 18 e 18). Similarly, if [T:] < 5, then by
Fact D.4, the bias of (2) must be least exp( exp(-T7/2) 22/2) 2 e 15.5, As the noise level f S 46 we have P. E (e 18 e 18).
Next, we prove the second part of Lemma 3.7. We start by bounding the correlation between yi and 14.- We have
9s Ug
E =0N().1)
proj (
- -())))
= 9: U4
E
proj 2(((2)))))))))))))) - f((x)) us
(EN(
2 9: 04
E bi =
{[(((()))))))))))))))))))()))[ + [1)))
(0,)
9. U4 2 log(L/T)),
where the third and the last inequalities hold because u, 1 wy and Fact D.5.
We next bound the norm of gr- Since both Si and 9i are orthogonal uy, is sufficient to show that for every unit vector Ws.
9i
ul
S gg . + 4/en /lg(/// We have
19: 2
E REN((.1)
proj 2(1((2) + f((z) 4x2)) u
E
proj
p =f(())
M(=)) 04 l4 - 2[1(4(=) # f((2))
=EN(O.I)
< [ uil
+
E
< 1g ue| + 2 erjy log(1/1h)
D.5 Proof of Theorem 3.1
In this section, we present the proof of Theorem 3.1. Before presenting the proof, we present the following fact that will be a crucial part of our proof.
Fact D.6 (Lemma 4.2 in [DKS18]). Under the standard normal distribution for every pair of unit vector w, w and real number t,
Pr(sign(w" x + # sign(w: + t)) sin(O(w, w²))
exp(-t2/12)
2
Proof of Theorem 3.1. Denote by 0 == 0(w, w*). We will first show by induction that with high probability in the i-th round of Algorithm 3, sin (in// < o.. Assuming this is correct, since σT Ceexy (t')2 /2 for some large constant C. We will have
(1' +1(((1 (11)))111)) S Ceexp( (1))
(r(sigu(w" x x +t* # sign(w x x+tt)) & Ceexp(
[lo(1/e) = =(e).
(2)
18

---

Since opt I this implies that by providing a good enough estimation t", we found a hypothesis with error at most O(e). Now we show that this is actually true. For sin(0 /2) S oo holds by our assumption.
Now, assume this is correct for the i-round and we show this holds with high probability for the i + 1-th round. We will show that with high probability the gradient Ji we use in the update w = pr (w; + (.ğ:) satisfies the condition of Lemma 3.2.
Recall that we have the following notations.
w- a,W;; + b.ug. T. a1aa7t65007
1' ---
(=) sign((a,w; + bous/o))= + (t' - -al)/o)), di = BZEN(O.) proju: zf((z) and yi = E projn! =f)(z), where fi(2) u(A!?2= tws)). And 1/: = Pr Pr (4(=)) # fı(z))
e 40 by Lemma 3.6.
We first show that with high probability, Algorithm 3 must be able to select a correct threshold < t' such that [T:] S 6. Denote by p; the probability that fi(z) 1. We notice that for each fixed / by randomly querying ([oog(1/6) fi(=), we can with high probability check if p; E (e-17, 1 e- 17 or not. This can be done using the same method we used Appendix C.2.
Since 2 = sin 0:/2 S sin 00/20/2 2) S. Ji we know from Lemma 3.7 that as long as we find some E 17
such that p; E (e-17 1 e 17). we have have [T:] S 6. By Lemma 3.5 and Lemma 3.7, we know
that there exists interval 4, S [0, t'] of length at least Ø; >> such that for every & E 4, [Ty] < 5 and thus p. E (e-16, 1 - e e-1).. ). Thus, by performing a binary search at most ( /e)) times,
with high probability, we are able to find such a such that [T]] < 6. Given that we find such a correct f, we will consider two cases.
First, we assume that 3a:/4 < sin(0;/2) o.. We will show that with high probability di and its empirical estimation de satisfy the condition in the statement of Corollary D. and thus prove sin (0.+1/2) S 0++1- Since (rol)+=(((2) is I-subgaussian random vector, by Hoeffding's 's inequality,
we know that with (dd samples of 2, with high probability we have l|g. - -.ll S c2 S e 40.
By Lemma 3.7 and Lemma 3.5, we have
by |1% e- 100e
P: U4 9s U1 2/en: Saahyyloga Tog(1/n)) 2
40
2
c-1 100c 40 c 20 C1
Oi |ل S |1 + 11g. gell S |ل + 2/
/log(1 /logl
1mm))) + 40 3e 19 S 10c1.
Thus, by Corollary D.I, we can conclude that sin (/-1 s (1- 1/C2)o, = 0++1, for a large constant C2.
Next, we consider the case where s0n//. < 30./4. In this case, as we have shown that || is bounded by some universal constant, the condition of Lemma 3.2 is fulfilled automatically and thus sin (0++1/2) < (1 - 1/C2)a, = I++1, for large constant C2.
By induction, with a high probability for each i, we have sin(0./2) S o, and thus wr is a good approximation of w". It remains to show that is also a good approximation of t" Recall that f = f such that [Trl < 6. Lemma 3.5 implies that [ - t+ s 400T = 40Cc exp (t')²/2 /2. Thus,
-1 |0- i| eepp( (1" -111 -0- ----
11)2
Pr (sign(wT x + 1*) A sign(wr + f) s (2m)) No..(
2
S (2x) 400' exp( (t')2 - (t" 1t- - -E12
S (2m) - 440Ceepp22((( -t" + 400T))
S 1 (400x + log(1/e)) ))
0(sexp(80'oor).
Since ort' = Olet' exp((t))/2)) and t' (2exp((t))/22) I 1/(Ce). we can conclude that Prz-N(o.1) (sign(wr x + +*) 4 sign(WT x + +)) < O(e). Thus, with high probability err(sign(WT x + f)) < O(e).
19

---

Finally, we count the number of queries used by Algorithm 3. In each round of the algorithm, we perform (log(1/e)) binary searches find the correct parameter f. each of which takes us only ((1 queries. We also make ((d) queries to construct 9i in each round of the algorithm. Thus, each round of Algorithm 3 takes Od + (o)) queries. Since there are at most (llog(1/e) rounds, the query complexity of Algorithm 3 is O(dpolylog(1/e))
E Omitted Proofs from Section 3.2
E.1 Proof of Lemma 3.11
Proof of Lemma 3.11. Denote by D the conditional distribution of x ((0 given y(2) 1. Recall that
Pr (v(x) -1) 2 z~N((,1)
Pr (h" = -1) c
(0.1)
We will first show that E2wD-N(x) s O(c/p). Denote by Z = v pi: + p2, where
D= 2 ~ N(0, I), then
Pr x~ N(...)) E 7(xx) w~D-
1(h pxx + pz) + v( / p2v + pz)] = Pr 1t [z))
Since and x are independent, we notice that Z can be simulated via the following reject sampling process. We draw I ~ I), and Z ~ N (0, I) to construct Z /11 p²x + pz and accepted Z when y(z) = -1. Since /1 p² ((0, +)++ pN I)= = N 10, Z can be seen as reject sampling process with an accepted rate at least (1 (1-11/1 p/C)p. Since the noise rate opt S e, we know that
E ((x)
Pr 1
(h" (Z) + v(z) 51-1100
By Markov's inequality, we know that with probability at least 3/4, n7(x) S 5c/p, with D- Next, we show that with a constant probability a negative example x must be close to the decision boundary of h² We have
- +
Pr z~D-
w² x <= -t- -
W B 1x< -t- - 11 t
1
Pr (x) = -1)
Pr
anD
x~D 11 (1)=-1
+ Pr (li = +1)
Pr
10 18 < -1- 77
xw/-
z~D 2 (2-)2) +2)=+1)
10 w0- - 1
w 1="x0< -t" - 2/C
Pr
+ 1/C S
Pr
x>D [1h (x)==1
2~ ((, (m)=-1)
(t" + 1
) (1*)2
1/41/1 (o((-22/2)ds
exp(-s² /2)ds +2/C exp(
2/C
2
-exp(- (2t" 1/1))/t), 2/C Se -1 - 2/C.
2
where in the third inequality, we use Fact D.4.
Thus, by union bound, with probability at least 1/2, it simultaneously holds that 77(xr) 5e/p and
" S -t" - -/("..
20

---

E.2 Proof of Theorem 3.8
Proof of Theorem 3.8. We consider two cases. First, if < 1, then each z standard Gaussian. We have
24 is drawn from the
U0
E (=) N1.
40
E zy(2)
E zy(2)
E =~N(0.1)
x2)
2~N(
2~~((0,1)
40
20,((0,1) 2y(z)
E
E
zy(2)
E
x2)
(~,((
z~N(0.1)
VA
40
E
28(2)
sup
E Iu (1((3) + (2))))
(U,))
wESA-1 z~N(0,1)
IA
40
zy(z)
+ /
(0,I
where the last inequality holds because of Fact D.5. Since each 2,0(2;) is standard Gaussian, by Hoeffding's 's inequality, we have
mr² ) > polylog(S);
Pr( up
E z0,))
zy(z)
2 2exp(- d
when 2 ((d/r2).. By taking (20)o((1/0)-1, obtain that [uo (o zy(=)] s (20 log(1/e))) with high probability. Thus
2h)))) s (20log(1/0) + < (1log(1/e)-)) N(N()
Uo
By Fact 3.4, know that Eg~N(o.1) (2) Ew² for some & 2 e=1 which also implies that
||uo|| 2 11/2 because up sufficiently close to (2 zh (2).
Since
40
E N(.()
zh 22"(2)
=11uol"
+
E (0.1)
2h
-2
E so.(
2x)
|luol| cos f(wo. w²)
2
E
zh" (2)
|uol|| (1 cos ((wo, w=')
(0,))
4
E
zh (2)
|loo|| [illssnnn (0n w²) w²) 1/2)
we get sin(0(wo, Wo, w²2 V |lu0 Ez- zh~ (z) E 2h" ||ol|| <
0(1/logg (o1/)))(//c). In particular as c < 1/C for some large enough C, we conclude that sin(O(wp, w² )/2) S max/min 1/2,, (VOn/oo((//n])
We next address the case when t > 1. By Lemma 3.11, we know that with probability at least 1/2, we have (x) I 5c/p and w² . E (-t" 1/t", -t*). We will assume these two events happen in the rest of the proof. Let N(0, 7) and by Fact 3.10, define
1" + V1 - Fu" _0)-
Mx)) = h*(x)) sign(w". 2
21

---

By Lemma 3.11, we know that Nr., h(z) # i(xo) n70z0) S Se/p. Similar to the first case,
we have
u0
=h(=)
=
u0
E =1j(10)
+
2ÿ((x0)
E =h(z)
20.()
N0,,1,
2~,((
17
40
E
zh(z)
+
zh(z)
zh(z)
N0,1)
(0,1(
110
E
20(11o)
sup
E |u- ((0(z0) # h(x))
10.1)
wESd-1 N0,1)
x VA
E
=ū(z))
+2Ven(mn) ( Vlo((1 (og(1/1(20))
max (Oog((oo))olllgg( (/500 (
where in the second last inequality we the fact that 1110 (g,,(( =0(x))) S
(/(10))))g((/e) & 1/(100t) with high probability. Since p = 1/t, It ---t" I 1/log(1/c) and
S Vlog(1// 1/e) log((/e). the threshold Tp :" :"+ ""+VI-p"u " to can be bounded as follows. /1 p²(t" + 1-)
STp 1111 - VI
ur /()) 1
Fact 3.4 implies that No),( zh(2)= = Ew for some & 2 e-
Since uo is close to Eg~N(0.1)
||ma|| 2 1/2 Thus, we obtain that
sin(f(wo, w²) w²) = v uo z~N10.1)
2
E
zh(z)
/4
E
2h)
|ooll
S max(min((1/::12))000m 0(1
F
Finding a Good Initialization with an Extreme Threshold
By Theorem 3.8, we know that Algorithm 2 can only find some wo such that sin(O./2) S Onn/log(1 (1/)), where 7) = e/p when is small such that // hr//oo((/m)) > O(1/t). In this section, we design algorithm that finds warm start with non-negligible probability of success when the threshold 1. falls in this range. Formally, we prove the following theorem.
Theorem F.1. Let ht (xr) sign( (w' x + (*) be halfspace with bias p and y(x) be any labeling function such that err(h") ) = opt I E S 1/C for some large enough constant C. Let be a scalar such that t t- 10/oog(11/
S t" < and 1/(400t) I /og 1/1) S 1/C for some large enough constant C, where 1) = e/p, Algorithm 5 makes M = Ô(1 /p + d dloo(1/e)) membership queries, runs poly(d, M) time and with probability at least 1/polylog(// oulputs some wp such that sin(O(wo, w² )/2) 1/t.
The high-level idea of our algorithm is follows. Although Algorithm 2 will not provide us Wo such that 6, < (1/)), tn is still smaller than a sufficiently small constant. We want to use the localization technique refine wo so that after T rounds of refinement, sin(Or/2) σT 1/t. Recall in Appendix D, we introduce Definition D.2, (v. 8, a -rejection procedure, which can be simulated using membership query. Passing Gaussian random point to the (v, o )r-rejection procedure, according to Lemma D.3, we will get another distribution over IR [11 that behaves the same another halfspace/ h'.
In this section, we want to design (v, s, o rejjecctio procedure such that the direction of the halfspace / has a constant correlation with respect to w" and the noise level after the rejection procedure is much smaller than the length of the Chow-Parameter of It. Write w' a; + byu. We want to set up e wi, a = 1/1 and (a,l, a,t + b.) uniformly. Such method is called the randomized threshold method in [DKS18]. This method has the following property.
22

---

Lemma F.2 (Proposition C.11 in [DKS18]). Let a, b, 0 such that a² + 62 = 1 and t larger than some constant C. Let w E S Let s ~ lat, at bj uniformlly For each x E R the expected probability that x is accepted by the (w, 8, -rejectcno procedure is at most a r/bb where a = 1/tl.
Lemma F.2 implies that in expectation over the randomness of s, only o/ //b,- /bb-ffraction of the noisy points will pass the (W,, 8, o )rejectiinn procedure. If we use query to simulate such a rejection procedure, by Lemma D.3, with a constant probability, the noise rate among our queries would be O(cexp(s² s² /b.) However, as do not know b;, using some b that is slightly far from b, would make the noise level too high for us to learn the signal we want. To overcome this, we design the following test approach to show that given b, we can with high probability check if it can be used to construct the rejection procedure or not and in particular, when b - 1/ log(1/e) < by < b, such b is guaranteed pass our test.
Lemma F.3. Let h" (x) = ssign w=' x + t") be halfspace and y(z) be any labeling function such Sd-1 be unit vector such that w² a ww= + b' u. a², b² > 0 and (a²)² + (6+)² = 1, b < 1/4. Let t > 0 such that t texp(t2/2) I 1/(Ce) for a sufficiently large constant C. Let a E (0,1) such that a² + b² 1. Let b, t, w, 5 be input of Algorithm 4. Let 8 ~ (at. at + b) uniformly. Denote by p(b, 8) be bias of a halfspace with threshold Tux := (t as) /b. Let {(2) = sign((a" ow b²u). .2 t aass) 8) be halfspace with bias ps. where If the probability that ps > p(b,,) s) 1/4iz is at most 1/2. then with probability at least 1 - 8, Algorithm 4 output "No". If the probability that p. p(b, s)/2 is at least 29/30 /90 then with probability at least 1 - 8, Algorithm 4 (s(L/p2(b, (b))))))))))))))))))))))))) = Os(L/
that err(h* opt S E. Let
outut "Yes". Furthermore, the query complexity of Algorithm
In particular, when b" 2 1.5/l 2 1.5/ ///////o(/) bb-b- S 1/ log(///) and |t - 1s1 s
1/ log(1/e), with probability at least 1 - 8, Algorithm 4 will output "Yes".
Algorithm 4 ANGLE TEST(Check if is good approximation for sin (w)
Input: A direction w, confidence parameter 8 E (0, 1), threshold t >> O, parameter b Output: "Yes" or "No"
Count < 0.
A 4- 7 - (1 0²) yun'", o 1/6
Compute a = VI B
Let Ths (1-as)/u as)/b and p(b.s) 8) be the bias of halfspace with threshold The do
for i = 1. ... T = OOlogg( T..(o..011
Draw 8 ~ (al, al + b) uniformly
Draw m ((1/)((b, s)) N(0, 1) and query y(A= sw)).
Compute pL, the empirical probability of y(Az - sw) = -1
if p. p(b,s)/3 then
Count + Count+1
if Count >> 37/4 then
return "Yes" elsereturn "No"
Proof of Lemma F.3. By Lemma D.3 and Lemma F.2, we know that over the randomness of s, with probability at least 5/6, := Pr (h* (Axz sw) # y(Az sw)) S 6c exp(s²/2) /2//b. We assume, for now, such an event happens. We first show that such a noise rate is much smaller than s). Write = al + E, where & E [0, b). then we have
c ccxp(s?/2) 1 Tbe exp( (T2
Tosc
5² TT
$²
(t- as)²
exp(
S tteepp(
+
2
26
82
(1
ass)
< 1(lexp(12 122)
expl
//C
2
21²
12
(at + {)2
(622 og)²
= C- exp(
+
+
2
2
212
= c-l expl (E2 + aZg²
)) < C e:= (C")
(3)
2
b²
23

---

where, in the first inequality, we use the fact that Tos S bt, in the second inequality, we use the fact that exp(t?) /2) < 1/(Ce) for a sufficiently large constant C, and in the last inequality, we use the fact that a² + b² = 1, < b2. By Fact D.4, we know that exp( exp(- bz/ /2//TT/ is at most 3 times p(b, 8), and thus 1) S p(b, 8)/C' for a large enough constant C².
ow + -b) -2 By Fact 3.3, we know that the ground truth label E(z) = /1" (AZz - sw) = sign( (wwwwwwwwwwwwaaaaa
t- a s). By Hoeffding's 's inequality, with high probability, we are able to estimate the probability of (AAz sw) = -1 up to error p(b, s)/20 using Ó(1/p² (b, s)) queries. In particular, since The S tb < 1/4, by Fact D.4, we know that p(b, 8) > p1/4 and will cost us only ((1//)) queries.
If the probability that pa > p(b,,)) s)/4 is at most 1/2, then in each round i of Algorithm 4, with probability least 1/3 it holds simultaneously that P. < p(b,,), s)/4 and v) S p(b, s)/C', In this case, with high probability p. < p(b,, /3/3 and Count does not increase. Thus, with probability at least 1 6, after T = (l1g())))) rounds, Count- < 3T/ /4 by Hoeffding's inequality.
Similarly. if the probability that p. > p(b, s) is at least 29/30, then in each round i of Algorithm 4, with probability at least 4/5 it holds simultancously that p. > p(b, s) and 17 S p(b, s)/C". In this case, with high probability p.: > p(b, /3/3 and Count increases. Thus, with probability at least 1 5, after T = (1))(()6)) rounds, Count > 37/ /4 by Hoeffding's s inequality.
Finally, we show that when 16" - 6] < 1/ log(1/e) and when |t - 11 s 1/ log(1/e), Algorithm with high probability outputs "Yes". To do this, we will show the true threshold of {(z) is close to Tis We have
t a
ta 0"
t as
01lo((1/c)-)) b*
Tos S
+ |t- as
v /br + 0a
b-
b
6- b
S (llog(L/e) 1/2 + 1Pt(bb - ba)
b*b
O(log(1/e) + (1))g(//)--)==-- (1log(1/e)-)))
By Fact D.4, it holds with probability that Ps p(b, s)/2.
Now assume that we have sin()./2) I os. then b, S 20 This implies that by testing = 3
20; - (og()/)) for j = 0, 1...., we only need O(log(1/e). rounds to find the correct b. With this fact, we have the following Algorithm 5.
Proof of Theorem F.I. Let = 6(w,, w²) and write wt = nqw t,,,, where a,, b, > 0, 0, +b² = 1. By Algorithm 2, we know that with probability at least 1/3, s0n/2 I D(e/pv/oo(p/ec) will assume sin(fb/2) I </pv/lo(pp/e holds throughout the proof, since the constant before can always be assumed to be normalized as 1/C is large enough. In round of the algorithm, we write w" = a,w; + b,u; where a,, b, > 0, aa + b3 = 1. Similar to the analysis of Algorithm 3, we will show that if sin(0,/2) I a, then with probability 1/3 it also holds that sin(0.+1 < 0++1- If this is true then since 1/t ///log(1// after O(log (og(1/e) rounds, have (ann0 < 1/t with probability at least 1/ 1/polylog(//e..
We
Recall the notation in the proof of Lemma F.3. Given b, we define p(b, 8) to be the bias of a halfspace with threshold Té.s (t as) By Fact 3.3, we define f(=) = h² (Az sw;) = sign((agow) + beu)- z + 1" a;s) the ground truth label of y(Az swu),, Lg to be its threshold and Ps to be the bias of {(z).
By Lemma F.3, we know that as long as b, > 1.5/t, with high probability Algorithm 4 will output "Yes" for some i such that with probability at least 1/2, ps > p(,,s) p1/4, On the other hand, by Equation (3), we know that with probability at least 5/6, 7/ == Pr (E(=) # y(Az sw:)) S p(b, s) s)" for a sufficiently large constant C'. Thus, with probability at least 1/3, p. p(6, s)/2 and 7) S p(b, s) hold simultaneously. For now, we assume this happens and we will analyze the smoothed label around some 20 such that y(Azo sw;) 11. By Fact 3.10, the smoothed label
24

---

Algorithm 5 INITIALIZATION 2(Finding a good initialization under extreme threshold)
Input: error parameter (0, 1), confidence parameter E (0, 1), threshold / >> 0
Output: wo E Sd
Run Algorithm 2 to get a E Sd-1, Let on = log(p//) be a parameter for i = o..... .....
, T = Oloo (1/()/))) do Run Algorithm with input w; and b 20; - lug(1/e5, J = ,,....,,, log((1/e Let b be the first parameter such that Algorithm 4 outputs "Yes"
If Algorithm 4 outputs "No" for all or the we use less than 1/1, then return wy,
Let v 11-8 B and i. = (t (,, where s [ât, ät + 6]. Estimate the probability Pis of p. y(Az swa) -1 for [(, I) up error p 1100
using Ö ((/1/p) queries. Let (g be the threshold of halfspace with bias yi,
1/t Draw ~ N(0, 1) and query y(Az - sw;) until some 2g such that y(Az - sw;) = -1 is
A + I (1 oz) yw;wt,
drawn
Draw ~ NO, I), for E [m]] m = (dd) and query fi(z;) = y<A(V<1 p2o pzo pzi) sw.).
where P = [C,
9i m Zi=1 projm, ! zz)( w - projge- (w; + mag:)
0:+1 + (1 1/O2]0; p++1 = (1 - 1/C1)
return WT
around Eg with respect to halfspace {()) can be seen as a halfspace
Lo (2)) sign W; 24 + Tp,s);
where W; = (a:ow; + b,u:)/ (a 63 and Tp.s = f.+ /1 1//1pp
By Fact 3.10 and Lemma 3.11, we know that with probability at least 1/2, such a 20 satisfies
1. W, 20 (-t, 1/t,, -t)
2. the noise level of the smoothed label is at most 5n/ps S 1/C" for some large enough constant C"
Since Ps p(b. s), we can bound the threshold Tp.s by
-2 l. VI- o² (1. +
to(1 (11-v12 VI
p²) < tt/ffa 22
< Tpp
(4)
because f, is at least close to t, up small constant factor, otherwise p. would be far from P.. Com- bine Equation (4) and Fact 3.4, we know that (x/~N((,1)) pr z'E20 (=') Φ \ for some
made
Φ E (e-2,1). 1). Since the noise level of the smoothed label around 2n is as small as 1/C" for some large enough constant C", by Hoeffding's inequality, we know that ||] E proj..! 2'2 (=')
can be smaller than some tiny constant with high probability.
As always holds that o; 2 1/t for each we will consider two cases. In the first case, sin s 3 and [|g:l] |I is bounded by some universal constant.
In the second case, we have 3 Eg,,N(,,)) proj.,== (2)) Viaoa)+4 (g,,N( proj.;; (2') sin(0.41/2) < (1 - 1/C1)o; = -++11
sin(O:/2) I as In this case know that tbui for some &b e which implies that
u.b.
2
2 5 Using Lemma 3.2, know that (a
b.
Finally, we prove the query complexity of Algorithm By Theorem 3.8, it takes us 0(1/p dlog(L/e)) queries to get some we by running Algorithm 2. After obtaining wo in each round of
25

---

Algorithm 4, we will rum Algorithm 4 ((log(1/e)) times to find desired 6 and each round takes us ((1/ s 1/p" < 1/v/P queries, because p(6) is the bias of a halfspace with threshold T3 = bt, which is smaller than by a tiny constant factor. Furthermore, after obtaining ô takes us ((1/p(b) + d (o)(1/e)) queries perform the gradient descent update. So, in total Algorithm 5 has query complexity at most O(1/p dlog(1/e)).
G Proof of Theorem 1.2
Proof of Theorem 1.2. We first show the correctness of Algorithm 1. When we run Algorithm 1, we will start with some interval [La ls] such that any halfspace with a threshold E [la 4s) must have bias
(p). Next, Algorithm partition [fu, [8] into grid such that 11 -
/og( 1/)). This implies
that there must be some t, E [t,, 6a] such that łj - -1/ log((og((1//)) and Algorithm 5, long as p Ce, with probability at least 1/polylog(1/e), we can find some We such that sin(Ou/2 22) I min(1/t, 1/2]. In particular, by running Algorithm or Algorithm polylog(1/c) times, at least one of these Wy satisfies the condition. Furthermore, with such wa. know from Theorem 3.1 that we can with high probability get some h such that err err(h) S (Opt e). Thus within the list C. of the candidate hypotheses maintained by Algorithm at least one of them has error (opt + e). By Lemma C.I, we can with high probability find hypothesis among C, whose error is at most 10 times the error of the best hypothesis in C and thus has error O + c).
< t* S tz. By Theorem 3.8
Next, prove the query complexity of Algorithm 1. According Appendix C.2, know that finding an interval [Ka, fa] costs us (min 1/c)) queries. If we find p Ce then are done. Otherwise, we will run the initialization algorithm and the refinement algorithm. By Theorem 3.8 and Algorithm 5, each time we run an initialization algorithm, it takes us ((1/p dpolylog(1/0) queries. By Algorithm 3, each time we run Algorithm 3, it takes us O(d log (1/e) queries. Since we will run these algorithms at most polylog(1/e /e) times. We will in total make O(1/p+ oooppoopoyyyoo/// (ipolyoo(1/e)) queries. Finally, by Lemma C.I, finding good hypothesis from the list of candidate hypotheses will only take us polylog(1/c) queries. Thus, we conclude the query complexity of Algorithm is Ómmin(1/p 1/c] + dpolylog(1/e)).
H Implementing the Learning Algorithm via A Small-Class Oracle
In this section, we discuss how to implement Algorithm 1 to get an even smaller query complexity Ós(d- polylog(L/e),, assuming there is an oracle that can return a random small-class example. Before presenting the definition of the small-class oracle, we remind the reader that the notation Ô hides the dependence on polylog(1/e) (1/e), and the notation Og hides the dependence on polylog(1/8). A small class oracle is defined as follows.
Definition H.1 (Small-Class Oracle). Let be a distribution over Rdd x (+1} and h* = sign(w* 1),, w Sd-1 1 >> be an optimal halfspace such that err(h") = opt minkgH err(h). small-class oracle EX(() (D) draws (x. y) D ly=1 and returns xc
In other words, a small-class oracle simulates the following rejection sampling procedure, where learner keeps drawing N0, I), querying its label and stops when it sees some 2o with (xs) = 1. Such a procedure requires Q(1/p) queries to implement, which is costly when is small.
By Theorem 3.1, even without the small-class oracle, the query complexity of Algorithm 3 is always Ös(d- polylog(1/66 (oyylog(//))...... Thus, a small-class oracle would only help reduce the query complexity of Algorithm 2 and Algorithm 5. In the rest of the section, we show that by calling the small-class oracle (s( (ppolyyogg(1/e) times, we can reduce the query complexity of Algorithm 2 and Algorithm 5 to Ōs(d polylog(1/e)).
26

---

We first consider Algorithm 2. By Theorem 3.8, the query complexity of Algorithm 2 is Õ(1/p- - d dllo((/c)), where Line 3 in Algorithm 2 takes 1/p queries to find random small-class example and Line 4-Line 5 in Algorithm 2 takes Ód lo)(1/e)) queries. As a small-class oracle simulates the same rejection sampling procedure as Line 3 in Algorithm 2. we can implement Line 3 in Algorithm 2 with a single small-class oracle. Thus, by single call of the small-class oracle, we are able to implement Algorithm 2 with Ód polylog(1/e)) query complexity.
Next, we consider Algorithm 5. Each implementation of Algorithm 5 runs in Ollog log(1 (c) iterations. In each iteration, we call Algorithm 4 volylog(1/c) /c) times in Line 5, use queries to estimate Pe in Line 9, find a single-small class example in Line 11 and improve the current hypothesis with (dd queries in Line 12. Furthermore, only operations in Line 5, Line 9, and Line 11 have query complexity much larger than polylog(1/c) Thus, we only need to show with a small-class oracle, we can significantly reduce the query complexity of these steps.
We start with Algorithm 4. In Line 9 in Algorithm 4, we use query to estimate the probability of u(Az-sw) = -1 1 with an error up to error p(b, s). By Lemma D.3, we know that if we pass random sample x ~ (O. I) to the (w, 8, 8) )-rjectinn procedure, then the resulting distribution is [N-su; A). Thus, the probability of y(Az - sw) = -1 is exactly equal to the fraction of negative examples among examples that pass the (w, (. -rejectinn procedure. Specifically, for the (w, s, -eeeectio procedure, we denote by the probability that a random example passes the rejection procedure and denote by q- the probability that random negative example passes the rejection procedure and p the fraction of the negative example. Then we have Pr (y(Az sw) = -1) = pg-/g. This implies that we know p and q-, then estimating Pr (y(Az - sw) = -1) is equivalent to estimating q-, which can be done by calling the small-class oracle several times and estimate the probability that these examples pass the (w. s, o)) -rejectionn procedure. By Lemma D.3, we know that exp( s /22(1 - o})) can be computed precisely using the parameter s. However, do not know p precisely, as this requires us to know t" up to a high accuracy. To overcome this only need ensure the correctness of the algorithm when our guess is close to t". In fact, when It - t-| S 1/ 1/lo((1/6 /c), á E [[1 - 1/C)p, (1 11+1 1/C)p) for some large enough constant C, which is enough for ensuring the correctness of Algorithm 4. So, to estimate Pr,) (v(Az - sw) = -1) up to error p(b, s), we only need to estimate q- up to error qp(b, s)/p We have
difficulty, we use P. the bias of halfspace with threshold f, because
p(b, s)g-
[xexp(p== //) T., exp(-TEs/2) 1 exx((-t//2)
2 Q
2 0
exp
s2 ((1-)2-12)/22)) 112))211)
P
The
(
(12- (al + E)2 ( (t- alat + E)
2 (2)
2 Ω
Tho
exp (112 - -2 -Tb))/2)) = Ω Tox
exp
b
= =(((IThb)) 2 101/1((11)) log(1/))),
(5)
where we use Fact D.4 and s at + E E b0. This implies that we only need to call a small class oracle (1) = (p(polllog(1/e) times to estimate q- and thus can compute Pr.= (y(Az sw) = -1) up to error p(b, s). In particular, in this implementation, we only need to call the small-class oracle and do not need to make membership queries.
Similarly, to implement Line in Algorithm we also only need call the small-class oracle Ôs()) times and do not need to make membership queries.
Finally, we show that by calling the small-class oracle (1) times, we are able to implement Line 11 in Algorithm 5. By Lemma D.3, Line 11 in Algorithm 5 draws random negative example that passes the (w,, s, σ -rejectionn procedure. By Lemma F.3, we know that p. = pq-/9 4 2 l(p(b, s)). This implies that g- > l(p(b, s)/pp) 2 Q211 log(1/))). by Equation (5). Thus, with high probability, we only need to pass Os (log(1 /e)) examples from the small class oracle to the (10,, 8, a orejjeccti procedure to get one negative example that passes this rejection procedure. Thus, in each iteration of Algorithm 5, we will call Ō₂ times the small-class oracle and make (s()) membership queries.
In summary, we count the number of queries in Algorithm I using the new implementation with a small class oracle. Notice that with a small-class oracle, we do not need to worry about using some guess much larger than 1" because the query complexity in the initialization step now has no dependence on the bias of the target halfspace. So we do not need to implement line 4 in Algorithm I
27

---

but only need to guess t' = 1/ log(1/e) for i= O..... [po)ylog(1/e)]. This means in Algorithm 1, we will call Algorithm 2 and Algorithm 5 in total at most polylog(1/c) times, so we will make (1(1) small-class oracles and make Os(d polylog(//c) membership queries.
28

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
The abstract summarizes the results provided in Theorem 1.1 and Theorem 1.2. The introduction summarizes the motivations of this paper and describes prior work's contributions.
Justification:
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize other settings.
is fine to include aspirational goals as motivation as long as is clear that these goals not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations the work performed by the authors?
Answer: [Yes]
Justification:
The limitations of this paper discussed in the introduction of the paper.
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those not discussed in the paper.
The authors encouraged to create separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested few datasets with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or speech-to-tex system might not be used reliably provide closed captions for online lectures because it fails handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairess.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
29

---

Answer: [Yes]
Justification: The statement of each theorem provides all the assumptions and we provide complete proofs for all statements that are either in the main body of the paper in the appendix.
Guidelines:
The answer NA means that the paper does include theoretical results. All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide a short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental Result Reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that it affects the main claims and/or conclusions the paper (regardless whether the code and data are provided or not)?
Answer: [NA]
Justification: This paper is theoretical and does not contain experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, or if the contribution a specific model and empirical evaluation, it may be necessary to either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way accomplish this, but reproducibility instructions for how to replicate the results, access to a hosted model (e.g.. in the case of large language model), releasing of a model checkpoint, other means that appropriate to the research performed.
also be provided via detailed
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make it clear how to reproduce that algorithm.
(b) the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is a new model (e.g., a large language model), then there should either way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reprodueibility may be tricky in some cases, in which authors are welcome to describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers have some path reproducing or verifying the results.
5. Open access to data and code
30

---

Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, as described in supplemental material?
Question:
Answer: [NA]
Justification:
This paper is theoretical and does not contain experiments.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nips.. cc/
for more details.
While we encourage the release of code and data, we understand that this might not be possible, "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for a new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https:
wtips.cc/ppblicc//eecccc getic//guiee...e CoodeSummii agionPolicy for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones omitted from the script and why.
At submission time, preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (c.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [NA]
Justification: This paper is theoretical and does not contain experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can provided either with the code, in appendix, or as supplemental material.
7. Experiment Statistical Significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [NA]
Justification: This paper is theoretical and does not contain experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
31

---

The assumptions made should be given (e.g.. Normally distributed errors).
It should be clear whether the error bar is the standard deviation the standard error of the mean.
is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out range (e.g. negative enror rates).
If error bars reported in tables plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information the com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [NA]
Justification: This paper is theoretical and does not contain experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental rums as well as estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported the paper (e.g., preliminary or failed experiments that didn't 't make into the paper).
9. Code Of Ethics
Question: Does the research conducted the paper conform, in every respect, with the NeurlPS Code of Ethics https: http////errrpppeeeee//ee wccppublic/tthicccuuiiiiii
Answer: [Yes]
Justification: Our research conforms in every respect with the NeurIPS Code of Ethics.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make to preserve anonymity (e.g., if there is special consid- eration due to laws or regulations in their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: This work theoretical and we not see any immediate implications on society.
Guidelines:
The answer NA means that there no societal impact of the work performed.
If the authors answer NA or No. they should explain why their work has no societal impact why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
32

---

The conference expects that many papers will be foundational research and not tied particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology being used intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms monitor how system learns from feedback over time, improving the efficiency and accessibility of MI..
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification:
This paper is theoretical.
Guidelines:
The answer NA means that the paper poses such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Lieenses for existing assets
Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper. properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [NA]
Justification: This work does not use any assets.
Guidelines:
The answer NA means that the paper does existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (c.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (c.g., website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswi thcode. com com/dataseta has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
33

---

If this information is not available online, the authors are encouraged to reach out to the asset's 's creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification: This work does not any assets.
Guidelines:
The answer NA means that the paper does not release new assets,
Researchers should communicate the details of the dataset/code/moodl as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification:
The paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsoureing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According the NeurIPS Code of Ethies, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: The paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing research with human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurlPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
34


Reviews:
[{"review_id": "vnORRQFwH2", "reviewer": "Reviewer_dMkP", "summary": "This paper studies the classical problem of distribution-dependent---here standard normal disitrbution---active learning of non-homogeneous halfspaces using label and membership queries in the realizable and agnostic setting. There are two main contributions.\n\n1. A strong lower bound in the label query setting essentially showing that no significant improvement against (passive) supervised learning is possible (as long as no exponential number of unlabeled samples are used).\n2. An upper bound in the membership query setting achieved by an efficient (poly-time) algorithm.\n\nThe achieved bounds depend on the bias $p$ (of the target halfspace $w^Tx+p\\geq 0$), which make these results target/hypothesis dependent.\n\nThese results extends previous ones on the simpler problem of learning homogeneous halfspaces, where exact rates have been known and fit into similar line sof work, e.g., results under the uniform distribution on the sphere, instead of Gaussian.", "questions": "While interesting, the standard normal assumption is rather strong and limiting. Are there any possibilities to extend your results to broader families of distributions, e.g., sub-Gaussian, log-concave, ... ? Even just more general Gaussians ($\\mathcal{N}(\\mu,\\Sigma)$)?", "limitations": "See question.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "* Strong near-optimal bounds for a well studied setting of actively learning halfspaces\n* Devise a near-optimal poly-time algorithm in the membership query setting, while most previous work ignore computational aspects or provide only exponential time algorithms.", "weaknesses": "While interesting, technically deep and novel, the results are somewhat limited, due to the quite strong standard normal assumption, see question below.\n\nComments:\n* Maybe consider changing adding something like \"under the Gaussian distribution\" to the title. Otherwise it might seem a bit too general.\n\n\n---rebuttal---\nraised score from 5 to 6.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We would like to thank the reviewer for the constructive feedback. We respond to the comments and questions from the reviewer as follows.\n\nWe first want to make some comments on the reviewer’s summary.\n\n## Remark on the summary: \nWe do not view our work as a simple extension of previous work. Prior work had only studied the label complexity of learning *homogeneous* halfspaces. Though the label complexity of active learning homogeneous halfspaces under structured distributions (such as the Gaussian or the uniform distribution over the unit sphere) had been studied for 20 years, prior to our work there was little known for the setting of learning a general halfspace. We resolve this fundamental question in this paper, by characterizing the optimal label complexity as a function of the bias of the target halfspace. A surprising conceptual implication of our result is that, unlike learning a homogeneous halfspace, no pool-based active learning method can improve the label complexity over that of passive learning settings. Importantly, we go beyond the model of pool-based active learning and show that one can actually beat passive learning in terms of label complexity using membership queries. Specifically, we develop the first (robust to adversarial label noise) query learning algorithm with optimal query complexity. As a bonus, our algorithm is computationally efficient (not only query efficient) and potentially practical. To achieve this, we develop a number of novel technical tools that may be useful in other contexts. \n\nWe next respond to the comment and weakness about the strong distributional assumption pointed out by the reviewer.\n\n## Distributional assumptions:\n\nWe start by pointing out that while we did not state the distributional assumption explicitly in the title (to avoid making the title too long),  such an assumption is clearly stated in the abstract. Since there is very little known about the label complexity of learning general halfspaces, studying the problem under the Gaussian distribution is a major first step in understanding this fundamental problem. Related to this, similar distributional assumptions were also made in early pioneering works on studying active learning homogeneous halfspaces --- such as [DKM05, BBZ07] --- and were extended by many follow-up works. At a technical level, to characterize the optimal label complexity, we develop novel techniques that we expect could be used as a foundation to study this learning problem in more general settings. With respect to our lower bound, the Gaussian distributional assumption renders the statement even stronger (since it holds even when the data is Gaussian). It has been well-known that in pool-based active learning, at least $1/p$ labels are needed to learn a $p$-biased halfspace. Despite significant interest in this question for over two decades, this lower bound has not been improved since the work [Das04]. We believe that the techniques developed in our paper to prove the lower bound could also be leveraged to establish lower bounds for other query learning problems.\n\nRegarding more general distributions: if the marginal distribution is a general Gaussian (with unknown mean and covariance), we could first use unlabeled examples to learn the marginal distribution (this can be done efficiently with polynomially many unlabeled examples); and thus reduce the problem to the case where the marginal distribution is a standard Gaussian by applying an affine transform. We believe it is also possible to design learning algorithms under all log-concave distributions, by building on our techniques. However, even in the passive learning model, efficient algorithms for agnostically learning general halfspaces are only known under the Gaussian distribution [DKS17,DKTZ22] --- with a significantly sub-optimal label complexity. We expect that there will be follow-up works that study the label complexity of learning general halfspaces under broader classes of structured distributions, such as isotropic log-concave distributions. \n\n> References\n\n>[BBZ07] Balcan, Maria-Florina, Andrei Broder, and Tong Zhang. \"Margin based active learning.\" International Conference on Computational Learning Theory. Berlin, Heidelberg: Springer Berlin Heidelberg, 2007.\n\n>[DKM05]Dasgupta, Sanjoy, Adam Tauman Kalai, and Claire Monteleoni. \"Analysis of perceptron-based active learning.\" International conference on computational learning theory. Berlin, Heidelberg: Springer Berlin Heidelberg, 2005.\n\n\n>[Das04]Dasgupta, Sanjoy. \"Analysis of a greedy active learning strategy.\" Advances in neural information processing systems 17 (2004).\n\n>[DKS17]Diakonikolas, Ilias, Daniel M. Kane, and Alistair Stewart. \"Learning geometric concepts with nasty noise.\" Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing. 2018.\n\n>[DKTZ22]Diakonikolas I, Kontonis V, Tzamos C, Zarifis N. Learning general halfspaces with adversarial label noise via online gradient descent. InInternational Conference on Machine Learning 2022 Jun 28 (pp. 5118-5141). PMLR.", "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": "", "extra_scores": {}}, {"review_id": "L4HdgIuFlK", "reviewer": "Reviewer_amzj", "summary": "This paper considers active learning of general (non-homogeneous) halfspaces under Gaussian distribution. Define p=P(Y=-1). On the one hand, it proves that, roughly speaking, with standard label queries, one cannot learn a classifier with O(opt+epsilon) error that requires polynomially many unlabeled samples and $O(d\\log\\frac{1}{\\epsilon}+\\text{min}(1/p, 1/\\epsilon))$ labels. On the other hand, with membership queries, it gives a computationally efficient algorithm that achieves $O(d\\text{poly}\\log(\\frac{1}{\\epsilon})+\\text{min}(1/p, 1/\\epsilon))$.", "questions": "N/A", "limitations": "N/A", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- This paper considers an interesting open problem learning theory: a lot of research has considered learning homogeneous halfspaces, but what is the limit for non-homogeneous halfspaces? It gives an interesting result that it can't be very efficiently learned under the standard label query paradigm, even assuming gaussian distribution and noise-free, while membership query could help.\n\n- The proposed method is sound and technically non-trivial, though I have not checked proofs in Appendix.\n\n- The paper is written clearly in general, and explains high-level intuitions well.", "weaknesses": "- For the upper bound / algorithmic result, it looks to me it is highly depended on the Gaussian (or \"nearly\" symmetric) assumption. Does that mean that membership queries may not even be enough if the data distribution is more general?\n\n- Also for the upper bound / algorithmic result, it aims at achieving O(opt+epsilon) instead of opt+epsilon error. I understand that in general the latter is proven to be hard, but it would be nice if there is a discussion about if the latter can be achieved with some assumptions about noise.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We want to thank the reviewer for appreciating our work and providing us with constructive feedback. We respond to the points made by the reviewer below.\n\n## Strong marginal distributional assumption:\nWe start by pointing out that this is the first work that studies the label complexity of learning general halfspaces; focusing on the basic setting that the data follows the Gaussian distribution is an important first step in this direction. For more general structured distributions, we believe that the techniques (such as the localization for general halfspaces) used in our algorithm could be extended to more general marginal distributions. However, to achieve optimal label complexity, more careful analysis is needed. It is worth mentioning that even in the passive learning setting, efficient algorithms for agnostically learning general halfspaces are only known under the Gaussian distribution. Thus, we expect that there will be follow-up works that study the optimal label complexity of learning general halfspaces under more general distributional assumptions such as isotropic log-concave distributions. Finally, we would like to refer the reviewer to our response to Reviewer dMkP which answers this question in more detail.\n\n## Different noise models:\nThe agnostic (or adversarial label noise) model used here is one of the strongest noise models in the literature.  A number of  pioneering prior works focused on this noise model in the context of passive and active learning; see, e.g., [ABL17,DKS17]. We believe that in weaker noise models, such as Random Classification noise, a similar algorithm could achieve error $opt+\\epsilon$. We view this as a moderately interesting direction, as in such models one could make repeated queries to a single point and obtain the correct label (with high probability). On the other hand, membership query is defined over the support of the marginal distribution. As a result, many membership query learning algorithms take this advantage to learn by making many queries over regions with very small probability mass. For example, in the realizable setting, if the marginal distribution is Gaussian, then one can easily find small class examples by querying points that are extremely far from the origin, which makes the learning algorithm very fragile. This is also an important motivation for studying adversarial label noise. We can use adversarial label noise to model such a regime and restrict the power of query (an exponentially small level of noise suffices for this purpose). From this point of view, studying other types of label noise is beyond the scope of this paper. We will add these questions as future directions in a revised version of the manuscript.", "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": "", "extra_scores": {}}, {"review_id": "cwTIpgLpNy", "reviewer": "Reviewer_goh3", "summary": "The paper studies the question of active learning halfspaces over $\\mathbb{R}^d$, under the Gaussian distribution in two different models: Label queries and membership queries. In the label queries model, the authors prove a lower bound implying that the learner must have a pool of size $exp(d)$ in order to do better (in terms of samples/queries) than a passive learner. In the membership queries model, the authors prove that the above lower bound can be circumvented by using the strength of membership queries, and provide an upper bound which is better than the optimal sample complexity bound of passive learners. The upper bound is given by an efficient semi agnostic learner (a learner with risk guarantee of the form $O(opt + \\epsilon)$).", "questions": "Questions:\n\n1. In line 157, I don't understand what does it mean that an argument is \"hard to formalize\". Do you mean that it is counter-intuitive?\n3. In line 205, do you mean that an upper bound $\\epsilon$ on the noise level is *given* to the learner beforehand?\n\n\nSuggestions:\n1.  I would recommend writing a \"technical overview\" section that separates the high-level novel ideas from known techniques and technical details.\n2. Add a discussion on future research. For example, in Theorem 1.2: can we do better in the realizable setting? Can we do better by using an inefficient learner?\n\n\nTypos:\n1. Line 337: \"the length of the length of\"\n2. Line 389: \"unfortinately:", "limitations": "Yes.", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "1. The studied problem is of a fundamental nature.\n2.  The lower bound and its circumvention via membership queries are interesting.\n3. The upper bound algorithm is efficient.", "weaknesses": "1. I find the introduction not clear enough. For example, I do not understand how the upper bound in line 56 settles with the lower bound in line 54. The upper bound has no dependence on $1/\\epsilon$. Also, how does Theorem 1.1 relate to those bounds? The bounds relate to the uniform distribution while the theorem relates to the Gaussian distribution.\n2. Line 93 says: \"The overhead term cannot be avoided in the agnostic setting...\". It is not discussed whether it can be avoided in the realizable setting.\n3. While the results are potentially interesting, I think that the presentation of the paper needs to be improved. High level ideas and technical details are mixed, which makes the paper hard to follow.\n4. No discussion on possible future research.\n5. The results are applicable to a relatively limited setting of halfspaces under the Gaussian distribution.\n6.  While the upper bound algorithm is efficient, it only gives a \"semi-agnostic\" guarantee in the form of $O(opt + \\epsilon)$. However, the constant hidden in the $O$ notation is not specified (at least not in the theorem), and it can sometimes be important. In some scenarios it might be perfectly reasonable that $opt = 1/1000$. So, if the hidden constant is at least $500$, the guarantee is no better than random guessing in those cases. It could be interesting to design an inefficient learner with better risk guarantees.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We want to thank the reviewer for the feedback. We will revise the writing in the updated version of this manuscript. We will also include a section that discusses future directions. Below, we respond to the weaknesses and questions pointed out by the reviewer.\n\n## Confusion in the introduction:\n>I do not understand how the upper bound in line 56 settles with the lower bound in line 54. The upper bound has no dependence on $1/\\epsilon$\n\nThe upper bound of $(1/p)d^{3/2}\\log(1/\\epsilon)$, achieved by an exponential time algorithm, is significantly worse than the naive lower bound of $\\min(1/p,1/\\epsilon)+d \\log(1/\\epsilon)$. Note that $1/p$ is at least $\\min(1/p,1/\\epsilon)$ and $d^{3/2}\\log(1/\\epsilon)$ is larger than $d \\log(1/\\epsilon)$.\n>How does Theorem 1.1 relate to those bounds? The bounds relate to the uniform distribution while the theorem relates to the Gaussian distribution.\n\nIt is well-known that, in high-dimensions, the Gaussian distribution is well-approximated by the uniform distribution over the sphere with radius roughly $\\sqrt{d}$. As a result, the learning problems under these two marginal distributions are almost equivalent. One could easily modify the calculation used in the proof of Theorem 1.1, to obtain the same lower bound for the uniform distribution over the unit sphere. Since the Gaussian distribution is arguably a more well-studied distribution in the literature (and the calculation is cleaner), we chose to study it instead of the uniform distribution over the unit sphere in this paper.\n\n>Line 93 says: \"The overhead term cannot be avoided in the agnostic setting...\". It is not discussed whether it can be avoided in the realizable setting.\n\nWe included a brief discussion about why this term can be avoided in the realizable setting; see lines 88-91. Roughly speaking, the membership query model is fairly strong in the distribution-specific and realizable setting. This can render the learning task somewhat straightforward. Specifically, since the support of the Gaussian distribution is the whole Euclidean space, the learner can choose to query many points extremely far from the origin to quickly get small class examples; and then determine the decision boundary of the target halfspace using binary search. Such a naive method can avoid the overhead term and achieve a low label complexity. In contrast, if the support of the distribution is the unit sphere, then the $(\\min\\{1/p,1/\\epsilon\\}+d \\log(1/\\epsilon))$ lower bound also holds in the membership query setting; as the learner is not allowed to query outside the sphere. This is an additional motivation to study the agnostic setting, since an exponentially small level of noise can make points far from the origin provide no information. We refer the reviewer to our response to reviewer vQ1c for more details.\n\n## Distributional assumption:\n\nWe start by pointing out that this is the first work that studies the label complexity of learning general halfspaces; focusing on the basic setting that the data follows the Gaussian distribution is an important first step in this direction. For more general structured distributions, we believe that the techniques used in our algorithm could be extended to more general marginal distributions. However, to achieve optimal label complexity, more careful analysis is needed. It is worth mentioning that even in the passive learning setting, efficient algorithms for agnostically learning general halfspaces are only known under the Gaussian distribution. Thus, we expect that there will be follow-up works that study the optimal label complexity of learning general halfspaces under more general distributional assumptions. Finally, we would like to refer the reviewer to our response to Reviewer dMkP which answers this question in more detail.\n\n## $O(\\mathrm{opt}+\\epsilon)$ guarantee:\nWe want to point out that learning up to error $O(opt+\\epsilon)$ is a standard benchmark --- many works can only achieve $O(\\sqrt{opt}+\\epsilon)$ or $O(opt\\sqrt{\\log(1/opt)}+\\epsilon)$) in robust learning theory. There is a long line of works in this direction; see [ABL17,YZ17,DKS17] for some representative works. In particular, if $opt=0$, i.e., in the realizable setting, our algorithm learns the target hypothesis within error $\\epsilon$ (for any desired $\\epsilon>0$). As we mentioned in the introduction, previous work in the realizable setting uses an exponential time algorithm to learn up to error $\\epsilon$ with a significantly sub-optimal query complexity. On the other hand, learning up to error $opt+\\epsilon$ is known to be computationally intractable, even under the Gaussian distribution, as we mentioned in the introduction. This is why such a guarantee is usually not considered in this direction.\n\n>[ABL17] Awasthi, Pranjal, Maria Florina Balcan, and Philip M. Long. \"The power of localization for efficiently learning linear separators with noise.\" Journal of the ACM (JACM) 63.6 (2017): 1-27.\n\n>[YZ17]Yan, Songbai, and Chicheng Zhang. \"Revisiting perceptron: Efficient and label-optimal learning of halfspaces.\" Advances in Neural Information Processing Systems 30 (2017).\n\n\n\n## Questions from the reviewer:\n\n>In line 157, I don't understand what does it mean that an argument is \"hard to formalize\". Do you mean that it is counter-intuitive?\n\nIn line 147, we have provided intuition why such a lower bound makes sense. But it is hard to use formal mathematics to turn such an intuition into a proof. This is because we have to make analysis conditioned on very complicated probability events. On the other hand, the technique we used in this paper bypasses this difficulty.\n>In line 205, do you mean that an upper bound ϵ on the noise level is given to the learner beforehand?\n\nAs we discussed in Appendix C.1, we can without loss of generality assume that $opt<\\epsilon$; otherwise, we can use a standard doubling trick to guess such a noise level and repeat the algorithm $\\log(1/\\epsilon)$ times.", "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": "", "extra_scores": {}}, {"review_id": "9jenOq0zQP", "reviewer": "Reviewer_88gR", "summary": "This paper first provides a lower bound on active learning using label queries. This lowerbound is nearly tight compared with upperbound for label queries. To get around the lowerbound, the authors study active learning using membership query, which means the algorithm can directly access the random function that gives the label y to x. The membership query is clearly stronger than label queries and hence, the authors manage to prove an upperbound. The authors also mentioned lowerbounds in membership query from other work.", "questions": "How do you know whether to use initialization for an extremely large threshold(section F) or not (section E)?\nI think it would make the paper easier to read if the authors could describe what 3.1 is doing at high level. \nI think there is a small notation error in A.2(sample (x,y)\\sim D instead of N(0, I)).", "limitations": "N/A", "rating": 7, "confidence": 2, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "The settings of active learning using label query and membership query are very natural and well-studied. The authors manage to provide a nearly-tight lowerbound and an interesting upperbound for general halfspace. The strategy they use in both proofs like considering negative examples in samples for lowerbound and finding a subclass using good initialization and fine-tuning seems to be intuitive and interesting.", "weaknesses": "I think the results are very interesting but the paper writing can be improved.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We want to thank the reviewer for appreciating our work and providing constructive feedback. We will improve the writing in the revised version of this work. Below, we answer the question from the reviewer. \n\n## Using the correct initialization algorithm: \n\nThis is a good question: how to estimate the true threshold plays a very important role of controlling the query complexity. In fact, we do not need to know such a threshold at the beginning; we guess such a threshold up to an additive $1/\\log(1/\\epsilon)$ error and use the guess to determine which initialization algorithm to use. The guessed threshold will be refined in the learning process.", "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": "", "extra_scores": {}}, {"review_id": "YXX9Nub40N", "reviewer": "Reviewer_vQ1c", "summary": "This paper studies the problem of actively learning non-homogeneous half-spaces under Gaussian distribution. It shows that in the pool based model, any active learner cannot do better than the passive learner in terms of label complexity, unless exponentially many unlabelled examples are drawn. On the other hand, it shows that in the membership query model, there exists active learner that can outperform the passive learner, thus demonstrating a separation between these two models.", "questions": "1. As I mentioned, is there a better MQ bound or simpler algorithm in the realizable case? In the realizable case is it possible to get $\\text{OPT}+\\epsilon$ exactly?\n\n2. Is there some distribution that is natural and actively can have an advantage over passive learning? I still believe active learning would have some advantages in many instances over passive for learning non-homogenous half-space in the pool-based setting.\n\n3. On the other hand, is it easy to extend your result to more general distributions? Like log-concave distributions?", "limitations": "It's better to have a conclusion section to talk about future directions.", "rating": 7, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "1. This paper settled down the open problem whether it is possible to learn non-homogeneous half-spaces using $O(d\\log(1/\\epsilon)+\\min(1/p,\\epsilon))$ labelled data and $O(d/\\epsilon)$ unlabelled data under the Gaussian distribution in the pool-based active learning setting. It then shows that this label complexity is achievable under the membership query model, thus there's a separation of the two models. This result and technique used is complete and novel.\n\n2. This paper is well-organized. It gives enough motivation and background information to the problem and discussed related work.\n\n3. The writing is very clearly for most of the part. Notations are well-defined and the math is rigorous.", "weaknesses": "1. (I would adjust my rating based on the response of this point). The only real issue I have here is that I'm not fully convinced by your conclusion that \"in the pool-based model, active learning has no improvements over passive unless the pool size is exponential\". The passive bound has an explicit dependence on $\\epsilon$ while your Theorem 1.1 doesn't. It only has a dependence on $1/p$. If $p$ is constant, your conclusion is not correct. So your conclusion only holds for some regime of $p$. This also makes me wonder how tight this lower bound is, is it possible to have a lower bound with $\\epsilon$ appearing explicitly here?\n\n2. The lower bound holds for the realizable case while the upper bound holds for the upper bound is for the agnostic setting. This leaves a gap in the realizable upper bound and potentially easier algorithms.\n\n3. The paper is getting a bit too technical at the end. All the writings are extremely well, especially the lower bound part, but it gets more technical in section 3 and it's hard to follow for me.\n\n     i) I think it's better to give some examples in section 3, explaining the intuition more and moving some of the lemmas to appendix.\n\n     ii) It feels like your MQ algorithm isn't completely new but used the framework/idea/techniques (like the localization) from previous works. It's better to start with a simpler algorithm and explain what's new in your paper. \n\n     iii) It might be better to have a conclusion section to discuss some future directions.\n\n4. There're some very tiny typos.\n\n   i) In the abstract, your lower bound is $\\Omega(d/\\log(m)\\epsilon)$ while in your theorem it is $\\Omega(d/\\log(m)p)$.\n\n   ii) In algorithm 1, what's the subroutine TEST C? In the appendix you have a subroutine named ANGLE TEST.\n\n   iii) Line 337, you typed \"the length of\" twice.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We want to thank the reviewer for appreciating our work and providing useful suggestions. We next respond to the comments from the reviewer as follows.\n\n## The benefit of pool-based active learning:\nWe start by commenting on the statement of Theorem 1.1. In the statement, we show that to learn a $p$-biased halfspace up to error $O(p)$, one need to make at least $d/p$ queries. Since $p \\ge \\epsilon$, this lower bound also holds if we want to learn a $p$-biased halfspace up to error $\\epsilon$. On the other hand, $d \\log(1/\\epsilon)$ is the minimum amount of information to describe a halfspace up to error $\\epsilon$. Thus, for $\\epsilon\\le p$, one can naively get a lower bound of $d/p+d \\log(1/\\epsilon)$. If $p$ is large, then of course pool-based active learning can beat passive learning. This has already been shown in the literature that studies learning homogeneous halfspaces. If we place no restriction on $p$, then in the worst case, we need to pay $d/\\epsilon$ many label queries to learn an $\\epsilon$-biased halfspace. Thus, the $d/\\epsilon$ lower bound stated in the abstract is consistent with the statement of Theorem 1.1\n\nWe next point out that the power of membership queries is used to obtain the warm start. Provided a warm start, the refinement step can be simulated using pool-based active learning efficiently (this can be verified based on Lemma D.3). So, if $p$ is not very small, we can take the average of roughly $\\tilde{O}(d)$ small class examples and use the mean as a warm start; this takes $\\tilde{O}(d/p)$ label queries. In this case, we obtain an efficient pool-based active learning algorithm with $d/p+d\\log(1/\\epsilon)$ label complexity, which gives some benefit for learning balanced halfspaces. However, such a benefit vanishes when $p$ approaches  $\\epsilon$.\n\n## Potential simple algorithm in the realizable setting using MQ:\nWe first note that in the realizable setting our algorithm also achieves error $opt+\\epsilon$ (since $opt=0$). Furthermore, we want to mention that membership query learning can be too strong for distribution-specific learning in a realizable setting as the problem becomes a geometric problem and can sometimes be trivial. This is one reason why membership query is widely studied in the noisy setting instead. Recall that membership query is defined over the support of the marginal distribution. Assuming the underlying distribution is uniform distribution over the unit sphere instead, one can first pay $1/p$ queries on the sphere to get an example from the small class. Based on this example, one can do $d$ times binary searches to find $d$ examples $\\epsilon$-close to the decision boundary. This gives a simple learning algorithm in the realizable setting with an optimal query complexity $\\min\\(1/p,1/\\epsilon)+d\\log(1/\\epsilon)$. If the distribution is Gaussian, the support is the whole space instead. As we mentioned in line 88-91, one can query examples that are very far from the origin to easily get a small class example and thus avoid the overhead term $1/p$. In such a simple learning algorithm, many queries are made over regions with a very small probability mass, which makes the algorithm very fragile. This is one of the reasons why we consider agnostic learning in this paper. Since in high dimension, Gaussian well approximates the uniform distribution over a sphere with radius $\\sqrt{d}$, if we add an exponentially small level of label noise, then queries outside such a sphere provide no useful information to the learner.\n\n## Overview of novel ideas and techniques:\nWe will add such an overview to intuitively explain the new techniques developed in the paper. It should be emphasized that even though we use some form of localization (which is a previously developed technique) to refine a warm start, to match the optimal query complexity, several new ideas are required. Intuitively, even to naively estimate the bias of the target function, one roughly needs $1/\\epsilon^2$ many queries. Surprisingly, we managed to learn the direction and the bias of the target halfspace simultaneously with a low query complexity. Moreover, even in the localization step, new ideas are needed to handle the issue that the true threshold is unknown (as previous work mainly handles the homogeneous case). Besides the ideas about localizations, we also introduced novel ideas to design robust algorithms to obtain a good initialization with a low query complexity. Before this work, initializations are usually obtained by estimating Chow-parameters and need significantly more queries. Furthermore, the techniques we developed for proving our lower bound give the first improvevement over the $1/p$ bound by [Das04]; we believe the ideas of the proof can be applied to other problems. \n\n\n## Distributional assumption:\nWe start by pointing out that this is the first work that studies the label complexity of learning general halfspaces; focusing on the basic setting that the data follows the Gaussian distribution is an important first step in this direction. For more general structured distributions, we believe that the techniques (such as the localization for general halfspaces) used in our algorithm could be extended to more general marginal distributions. However, to achieve optimal label complexity, more careful analysis is needed. It is worth mentioning that even in the passive learning setting, efficient algorithms for agnostically learning general halfspaces are only known under the Gaussian distribution. Thus, we expect that there will be follow-up works that study the optimal label complexity of learning general halfspaces under more general distributional assumptions such as isotropic log-concave distributions. Finally, we would like to refer the reviewer to our response to Reviewer dMkP which answers this question in more detail.", "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": "", "extra_scores": {}}]

Author rebuttal:
We thank the reviewers for their time and effort in providing feedback. We are encouraged by the positive comments, and that all the reviewers appreciated the paper for the following (i) theoretically interesting (**dMkP,amzj,goh3,88gR,vQ1c**), (ii) technically deep and novel (**dMkP,amzj,goh3,88gR,vQ1c**), (iii) mathematically clear and rigorous (**amzj,vQ1c**). We address the individual questions and comments by the reviewers separately.

Meta-review: This paper gives new positive and negative results on active learning non-homogeneous halfspaces under Gaussian distributions. The reviewers acknowledged the novelty of the lower bound (in going beyond the Dasgupta'04 lower bound), as well as the novelty of the upper bound result and algorithm under the membership query model. This can serve as a basis for follow-up works on active learning nonhomogeneous halfspaces with broader unlabeled data distributions. 
 
We encourage the authors to incorporate the discussions in the final version, e.g. making explicit the argument of the necessity of O(min(1/p, 1/eps)) label complexity for MQ algorithms in the agnostic setting, by giving a formal proposition.
Decision: Accept (poster)