Active Learning of General Halfspaces: Label Queries vs Membership Queries

Authors: ilias  diakonikolas
daniel m kane
mingchen  ma
Venue: NeurIPS_cc_2024_Conference
Published: 2024-05-15 16:37:10

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.

Main paper: 
 introduction: 
 In Valiant's PAC learning model [29, 30] , the learner is given access to random labeled examples and aims to find an accurate approximation to the function that generated the labels. The standard PAC model is "passive" in the sense that the learner has no control over the selection of the training set.Here we focus on interactive learning between a learner and a domain expert that can potentially lead to significantly more efficient learning procedures. A standard such paradigm is (pool-based) active learning [26] , where the learner has access to a large pool of unlabeled examples S and has the ability to (adaptively) select a subset of S and obtain their labels. We will henceforth refer to this type of data access as label query access. An even stronger interactive model is that of PAC learning with membership queries [1, 18] . A membership query (MQ) allows the learner to obtain the value of the target function on 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 is 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 to Appendix A for formal definitions of these two learning models. Roughly speaking, when the size of S becomes exponentially large (so that it is a good cover of the space), the model of active learning "converges" to 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 boundedset of unlabeled data. Over the past two decades, a large body of work in theoretical machine learning has studied the possibilities and limitations of active learning in a variety of natural and important settings; see, e.g. [20, 6, 7, 9, 3, 4, 21, 22, 17, 32] .A prototypical setting where active learning leads to substantial savings is for the task of learning homogeneous Linear Threshold Functions (LTFs) or halfspaces. An LTF is any function h : R d → {±1} of the form h(x) = sign(w • x + t), where w ∈ S d-1 is called the weight vector and t is called the threshold. If t = 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 [27] and has had a great impact on many other influential techniques, including SVMs [31] and AdaBoost [19] .For the class of homogeneous halfspaces under well-behaved distributions (including the Gaussian and isotropic log-concave distributions), prior work has established that O(d log(1/ϵ)) label queries suffice, where d is the dimension and ϵ is the desired accuracy [3, 9, 5] . Moreover, there are computationally efficient algorithms with near-optimal label complexity for this task [2, 34, 28] , even in the agnostic model that achieve error O(opt + ϵ). Unfortunately, this logarithmic dependence on 1/ϵ breaks down for general (potentially biased) halfspaces. Intuitively, this holds because if the bias of a halfspace (the probability mass of the small class) is p, then we need to obtain at least 1/p labeled examples before we see the first point in the small class. This implies an information-theoretic label complexity lower bound of Ω(min{1/p, 1/ϵ} + d log(1/ϵ)) [7] , even for realizable PAC learning under the uniform distribution on the sphere. Hanneke et al. [4] showed an information-theoretic label complexity upper bound of Õ((1/p)d 3/2 log(1/ϵ)) for general halfspaces under the uniform distribution on the sphere (via an exponential-time algorithm).In summary, prior to this work, the possibility that there is an active learner with label complexity O(d log(1/ϵ) + min{1/p, 1/ϵ}) and unlabeled sample complexity poly(d/ϵ) remained open. Our first main result is an information-theoretic lower bound ruling out this possibility. Theorem 1.1 (Main Lower Bound). Let S be a set of m i.i.d. points drawn from N (0, I). With probability at least 2/3, for any active learning algorithm A, there is a halfspace h * that labels S with bias p such that if A makes less than Õ(d/(p log(m))) label queries over S, then with probability at least 2/3 the halfspace ĥ output by A has error more than p/2 with respect to h * .In particular, if p is chosen as Θ(ϵ log(1/ϵ)), learning a p-bias halfspace with error Cϵ (for any fixed constant C) would require a learning algorithm to either make Ω(d/ϵ) label queries or have a pool of 2 d unlabeled examples. Our information-theoretic lower bound essentially shows that the active setting does not provide 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(x) and for every ϵ, δ ∈ (0, 1), it makes M = Õδ (min{1/p, 1/ϵ}+dpolylog(1/ϵ)) 1 memberships queries, runs in poly(d, M ) time, where p is the bias of the optimal halfspace h * , and outputs an ĥ ∈ H such that with probability at least 1 -δ, err( ĥ) ≤ O(opt + ϵ).In other words, we provide a computationally efficient constant factor agnostic query learner with query complexity Õ(min{1/p, 1/ϵ} + dpolylog(1/ϵ)). Due to known d poly(1/ϵ) complexity lower bounds for achieving optimal error of opt + ϵ [11, 13, 14] , the majority of work [15, 16] in the passive PAC model has focused on designing efficient learners achieving a constant factor approximation of O(opt + ϵ)These passive learning algorithms have sample complexity poly(d, 1/ϵ). 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 a tiny amount of noise. In particular, the query complexity achieved by our algorithm establishing Theorem 1.2 is nearly optimal in the agnostic setting.On the one hand, Ω(d log(1/ϵ)) queries are required because describing a halfspace up to error ϵ requires d log(1/ϵ) bits of information [25] . On the other hand, we argue that the overhead term of Ω(min{1/p, 1/ϵ}) cannot be avoided in the agnostic setting. Such a statement can be deduced from a lower bound of [23] : they showed that in the realizable setting, any algorithm requires at least Ω((1/p) 1-o(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 Ω(1/p) 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 ∼ √ d. Thus, an exponentially small level of noise would make every query far from this sphere contain no useful information. This allows us to show that, under the Gaussian distribution with a tiny amount of label noise, Ω((1/p) 1-o(1) ) queries are needed to see a single example from the small class. The proof of this statement is essentially identical to the argument in [23] for unit ball. The reader is referred to that work for the details.For a halfspace h(x) = sign(w• x + t), w ∈ S d-1 , t > 0, we use p(t) = Pr x∼N (0,I) (h(x) = -1)to denote its bias. For a halfspace h(x), we define its Chow-Parameter under the standard Gaussian distribution to be E x∼N (0,I) xh(x). Let y(x) : R d → {±1} be a (randomized) labeling function for examples in R d . We denote by err(h) = Pr x∼N (0,I) (h(x) ̸ = y(x)) to be the error of the hypothesis h and opt = min h∈H err(h), where H is the class of halfspaces over R d . We will use h * to denote the halfspace with an error equal to opt. When there is no confusion, we will use p to denote the bias of the optimal halfspace h * . Let D x be a distribution over R d , y(x) be a labeling function over R d and S = {(x i , y(x i ))} m i=1 be a set of i.i.d. examples drawn from the distribution D over R d × {±1} such that the marginal distribution of D is D x . A membership query takes an x in the support of D x as input and outputs y(x). A label query takes an x i , where (x i , y(x i )) ∈ S as input and outputs y(x i ). A learning algorithm A is allowed to use membership queries/label queries and aims to output a halfspace hypothesis ĥ such that err( ĥ) ≤ O(opt + ϵ) by making as few queries as possible.2 Nearly-Tight Lower Bound on Label Complexity: Proof of Theorem 1.1In this section, we prove our information-theoretic 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. [6, 9, 23] , showed that if S is a set of examples drawn uniformly from the unit sphere, and if h * is a halfspace with bias p 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 h * . Thus, if A makes less than 1/(2p) queries, it will with constant probability not see any negative examples; and it is therefore impossible to learn the target halfspace.In the Gaussian case, we will use a 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 O(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 ≥ poly(d/p) examples drawn from N (0, I) and learn any halfspace h * (x) = sign(w * •x+t * ) 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 h * (x) = sign(w * • x + t * ) with bias p, it makes r + O(d) queries and finds d 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 2 d . If we have made 1/ϵ 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 a large correlation with it. Therefore, it will still take us another approximately 1/ϵ 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, it would take us roughly d/ϵ 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 a given round. Every time the algorithm sees a negative example, it moves to the left; otherwise, it moves to the right. Suppose that A wants to find k negative examples with r queries. Then there are at most r k ≤ (er/k) 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 a deterministic condition such that if the k examples satisfy the condition, a random halfspace with bias p will have only roughly p k 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 k×d be a matrix with row vectors x 1 , . . . , x k . Let t * > C > 0 for some sufficiently large constant C. Let h * (x) = sign(w * • x + t * ) be a random halfspace with bias p withw * ∼ S d-1 chosen uniformly from S d-1 . If AA ⊤ -dI 2 ≤ O(d/(t * ) 2 ), then with probability at most O(p log(1/p)) k , where p is the bias of h * under the Gaussian distribution, h * (x i ) = -1 for i = 1, . . . , k.Thus, if the r k tuples all satisfy such a condition, then A will succeed with a fairly tiny probability unless r is larger than k/p. So, in the last step of the proof, we will show in Lemma 2.3 that by taking k ≈ d/(log(m)polylog(1/p)), with high probability every k-tuple of examples in S will satisfy the deterministic condition. Thus, no algorithm can succeed with a constant probability, unless it makes Ω(d/(p log(m))) queries. The proof of Lemma 2.3 can be found in Appendix B.3. Lemma 2.3. Let S ⊆ R d be a set of m examples drawn i.i.d. from N (0, I). Let t * > C > 0 for a sufficiently large constant C and k = O(d/ log(m)(t * ) 4 ). Then, with probability at least 2/3, for every k-tuple of examples {x 1 , . . . , x k } ⊆ S, AA ⊤ -dI 2 ≤ d/(t * ) 2 , where A ∈ R k×d be a matrix with row vectors x 1 , . . . , x k .Proof of Theorem 1.1. We will start by showing that, given a set S of m points drawn i.i.d. from a 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 A makes only r = Õ(d/p log(m)) label queries over S, then with probability at least 2/3 it will not be able to find k negative examples in S for some k ≤ d. By Yao's minimax principle, it is sufficient to show that there is a distribution over halfspaces h * such that for any deterministic active learning algorithm, the following holds: given m random Gaussian examples, if the learning algorithm makes r queries, with probability 2/3 it cannot find k negative examples. We will fix the threshold t * of h * and draw w * uniformly from the unit sphere. By Lemma 2.3, we know that by choosing k = O(d/ log(m)(t * ) 4 ), with probability at least 2/3, for every k-tuple of examples x 1 , . . . , x k ∈ S, AA ⊤ -dI 2 ≤ d/(t * ) 2 , where A ∈ R k×d is a matrix with row vectors x 1 , . . . , x k . By Lemma 2.2, we know that every k-tuple of examples x 1 , . . . , x k ∈ S has a probability α k , which is at most O(p log p) k to be labeled all negative by the random halfspace h * . 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 a time. If the example at node v 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 a given search algorithm, there are at most r k different possible outcomes where it successfully finds k negative examples. Furthermore, for each of the possible outcomes, there is a set of k examples in S that correspond to the k 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 3 Robust Learning of General Halfspaces with MQs: Proof of Theorem 1.2In 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 ≤ ϵ. Such an assumption can be made without loss of generality, as discussed in Appendix C.1. We first present our main algorithm, Algorithm 1. Algorithm 1 will maintain a list of polylog(1/ϵ) candidate hypotheses at least one of which has error O(opt + ϵ). We will then use a standard tournament approach to find an accurate hypothesis among them.Algorithm 1 QUERY LEARNING HALFSPACE(Efficient Agnostic Learning Halfspaces with Queries)Input: error parameter ϵ ∈ (0, 1), confidence parameter δ ∈ (0, 1) Output: halspace ĥ(x) = sign( ŵ • x + t), where ŵ ∈ S d-1 , t > 0 C ← ∅ ▷ Create a list of candidate hypothesises C Use Õ(min{1/p, 1/ϵ}) queries to estimate p by some p such that p ≤ p ≤ 2p (or verify p < Cϵ and return +1, the constant hypothesis). Let t a , t b > 0 such that a halfspace with threshold t a has bias 2p and with threshold t b has bias p.a = t 0 < t 1 < • • • < t ψ = t b such that |t i+1 -t i | = 1/(2 log(1/ϵ)), ∀i ≤ ψ-1.▷ Guess the true threshold t * with t ′ ∈ {t 0 , t 1 , . . . } for j = 0, . . . , ψ do Repeat the following procedure polylog(1/ϵ) log(1/δ) times w 0 ← INITIALIZATION(ϵ, t j , δ/polylog(1/ϵ)) ▷ Find a w 0 ∈ S d-1 as a warm start (w T , t) ← REFINE(w 0 , t j , ϵ.δ/polylog(1/ϵ)) ▷ Find a w T ∈ S d-1 close enough to w * and t close enough to t * based on w 0 C ← C ∪ {sign(w T • x + t)} ▷ Add a new candidate hypothesis to C Find a good hypothesis ĥ from C using Lemma C.1, a standard tournament approach return ĥAt the beginning of Algorithm 1, 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. We will design two subroutines that make use of t j to produce a good hypothesis sign(w T • x + t).The first algorithm will take t j and the noise level ϵ as its input and produce a unit vector w 0 as an initialization. We will show in Section 3.2 that as long as |t j -t * | ≤ 1/ log(1/ϵ), we can with probability at least 1/ log(1/ϵ) produce some w 0 such that θ(w 0 , w * ) ≤ O(1/t j ). By repeating such an initialization algorithm polylog(1/ϵ) times, with high probability one of these runs will succeed.In particular, such an algorithm has a query complexity of Õ(1/p + dpolylog(1/ϵ)). Now assume we have such a w 0 as a warm-start. Our second subroutine is to refine the direction w 0 and the threshold t j . More specifically, we will maintain a unit vector w i such that θ i = θ(w i , w * ) and an upper bound σ i for sin(θ i /2). In each round of the refining algorithm, we will use Õ(d) queries to update w i . In particular, in each round σ i will decrease by a constant factor and thus after at most T = Õ(log(1/ϵ)) rounds, we will have sin(θ T /2) ≤ σ T = Cϵ exp(t 2 j /2). As we will show in Section 3.1, provided the correct t * , sign(w T • x + t * ) is at most O(ϵ) far from h * . However, to output a good hypothesis, we still need to learn t * up to a high accuracy. When t * is small, we even have to estimate t * up to error O(ϵ), which typically needs many queries. However, as we will show in Section 3.1, given w T close enough to w * , we are able to combine the localization technique used in [15] with this fact to learn t * using only O(log(1/ϵ)) queries. This gives an overview of Algorithm 1 and its query complexity. 
when |t: 
 i | ≤ 6, it holds that ḡi • u i = ∥ ḡi ∥ and e -19 b i /σ i ≤ ∥ ḡi ∥ ≤ 2e -19 . 3. For every t -t * > 40σ i and t < t ′ , |T i | > 10. 
refining a warm-start: 
 We will start by discussing how to refine a warm start w 0 by proving the following theorem. The proof of the theorem and the main algorithm, Algorithm 3 can be found in Appendix D.5.Theorem 3.1. Let h * (x) = sign(w * • x + t * ) be a halfspace such that err(h * ) = opt ≤ ϵ. Let t ′ ≤ log(1/ϵ), w 0 ∈ S d-1 be inputs of Algorithm 3. If t ′ -1/ log(1/ϵ) ≤ t * ≤ t ′ , t ′ exp((t ′ ) 2 /2) ≤ 1/(Cϵ)and sin(θ(w 0 , w * )/2) ≤ σ 0 := min{1/t ′ , 1/2}, then Algorithm 3 makes M = Õδ (dpolylog(1/ϵ)) membership queries, runs in poly(d, M ) time, and outputs (w T , t) such that with probability at least 1 -O(δ), err(sign(wT • x + t)) ≤ O(ϵ).As we discussed in Section 3, we will assume we have some t ′ such that t ′ -1/ log(1/ϵ) ≤ t * ≤ t ′ and some w 0 such that sin(θ 0 /2) ≤ σ 0 = min{1/t ′ , 1/2}, i.e., some initial knowledge of t * , w * . Our algorithm runs in iterations and will maintain some w i in round i. We will maintain some unit vector w i and use ∥w i -w * ∥ = 2 sin(θ i /2) to measure the progress made by Algorithm 3. The method we use to update w i is a simple projected gradient descent algorithm. Specifically, we will construct a random vector G i over R d such that G i ⊥ w i and in expectation g i = E G i has bounded length and a good correlation with respect to w * . We will show in the following lemma that by estimating E G i up to constant error with ĝi and using the update rule w i+1 = proj S d-1 (w i + µ i ĝi ), we are able to significantly decrease θ i . The proof of Lemma 3.2 can be found in Appendix D.1.Lemma 3.2. Let w * , w i ∈ S d-1 such that w * = a i w i + b i u, where u ∈ S d-1 , u ⊥ w i , a i , b i > 0, a 2 i + b 2 i = 1. Let θ i = θ(w i , w * ).Let G i be a random vector drawn from some distribution D such that with probability 1, G i ⊥ w i . Let g i be the mean of G i . Let ĝi be the empirical mean of G i and µ i > 0. The update rule w i+1 = proj S d-1 (w i + µ i ĝi ) satisfies the following property,∥w i+1 -w * ∥ 2 ≤ ∥w i -w * ∥ 2 -2µ i b i g i • u + 2µ i b i ∥ ĝi -g i ∥ + µ 2 i ĝi 2 .Furthermore, if sin(θ i /2) ≤ σ i ∈ (0, 1) and there exist constantc 1 , c 2 such that g i • u ≥ c 1 /10, ∥ ĝi ∥ ≤ c 1 and ∥g i -ĝi ∥ ≤ c 2 ≤ c 1 /40, then there exist constant C 1 , C 2 > 8 such that by taking µ i = σ i /C 1 and σ i+1 = (1 -1/C 2 )σ i , it holds that sin (θ i+1 /2) ≤ σ i+1 . In particular, if sin(θ i /2) ≤ 3σ i /4 and ∥ ĝi ∥ ≤ c 1 then sin (θ i+1 /2) ≤ σ i+1 always holds.In the rest of the section, we will show that as long as w i is not good enough, we can always efficiently construct a random vector G i whose expectation points to the correct direction and we can use very few queries to estimate its expectation up to a desired accuracy. We adapt the localization technique used in [15] to achieve this goal.In the i-th round of Algorithm 3, we write w * = a i w i + b i u i , whereu i ∈ S d-1 , u i ⊥ w i , a i , b i > 0, a 2 i + b 2 i = 1.Recall that σ i is an upper bound we maintain for sin(θ i /2). We will construct the random gradient as followsG i := proj w ⊥ i zy(A 1/2 i z -tw i ),where z ∼ N (0, I), A i = I -(1 -σ 2 i )w i w t i and t ∈ (0, t ′ ) is a scalar. To see why G i is a good choice, we will start by analyzing G i assuming the noise rate opt = 0. To simplify the notation, denote byℓ i (z) = sign((a i w i + b i u i /σ i )z + (t * -a t)/σ i ) and ḡi = E z∈N (0,I) proj w ⊥ i zℓ i (z). A simple calculation gives us the following result. Fact 3.3. Let h(x) = sign(w • x + t) be a halfspace. Let v ∈ S d-1 such that w = av + bu, where a, b > 0, a 2 +b 2 = 1, u ∈ S d-1 , u ⊥ v. Let s, σ > 0 be real numbers and define A = I -(1-σ 2 )vv t . For each z ∈ R d , define z := A 1/2 z -sv. Then h(z) = ℓ(z), where ℓ is the following halfspace ℓ(z) = sign((av + bu/σ) • z + (t -as)/σ) .Fact 3.3 implies that if opt = 0, then it always holds that f i (z) := y(A1/2 i z -tw i ) = ℓ i (z), ∀z ∈ R d and we can view z as examples labeled by a halfspace ℓ i (z). In particular, E z∼N (0,I) zf i (z) is the Chow-Parameter of the halfspace ℓ i (z) under the standard Gaussian distribution. Fact 3.4 (Lemma C.3 in [15] ). Let h(x) = sign(w • x + t), where w ∈ S d-1 be a halfspace. ThenE z∼N (0,I) zh(z) = 2 π exp (-t 2 /2)w. By Fact 3.4, in the noiseless case, E z∼N (0,I) zf i (z) is parallel to (a i w i + b i u i /σ i ) with length Θ(exp(-T 2 i )), where T i = t * -ai t σi √ a 2 i +b 2 i /σ 2 iand g i = ḡi is exactly the u i component of the Chow-Parameter. In particular, if T i is constant, then by estimating g i using ĝi up to a small constant error using Õ(d) queries, we are able to use Lemma 3.2 to improve w i . Assuming we set t = t * , asσ i t ′ ≤ 1 and b i ≤ O(σ i ),it is easy to check T i can be bounded by some universal constant. However, as we mentioned before, we only know |t ′ -t * | ≤ 1 log(1/ϵ) , when w i getting close to w * , σ i could become very small and an error of 1/ log(1/ϵ) could potentially blow up T i , making the signal we want quite small. Such an issue is problematic for the algorithm, especially when f i (z) is a noisy version of ℓ i (z). 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 t is good or not, by looking at the bias of ℓ(z), using Õ(1) queries. Using this method, we can perform a binary search for t to find a correct choice in at most log(1/ϵ) rounds. Furthermore, as long as we select the correct t, it must hold that t -t * ≤ O(σ i ). In particular, as σ T = Cϵ exp((t ′ ) 2 /2), such a t is a good enough estimate for t * to be used in the final hypothesis. Lemma 3.5. Let w * , w i ∈ S d-1 such that w * = a i w i + b i u i , whereEQUATIONσ i t ′ ≤ 1. Define T i := t * -ai t σi √ a 2 i +b 2 i /σ 2 i , ℓ i (z) = sign((a i w i + b i u i /σ i )z + (t * -a t)/σ i ) and ḡi = E z∈N (0,I) proj w ⊥ i zℓ i (z) for some t ∈ [0, t ′ ].Then the following three properties hold. 1. There exists an interval I t ′ ⊆ [0, t ′ ] of length at least σ i such that for every t ∈ I t ′ , |T i | ≤ 5.So far, we have only considered the case when opt = 0. Due to the presence of noise, it is impossible for us to estimate ḡi = E z∈N (0,I) proj w ⊥ i zℓ i (z) because we only have a noisy version f i (z) of ℓ i (z). In this section, we will show that as long as w i is close to w * and |t ′ -t * | ≤ 1/ log(1/ϵ), the probability that for a Gaussian point z, ℓ i (z) ̸ = f i (z) is at most a tiny constant. This is incomparable with the bias of ℓ z (z) if t is chosen correctly, and does not affect the algorithm too much. We start with the following lemma which bounds the probability ofℓ i (z) ̸ = f i (z). Lemma 3.6. Let h * (x) = sign(w * • x + t * ) be a halfspace such that err(h * ) = opt ≤ ϵ. Let t, σ i , t ′ be real numbers such that t ≤ t ′ and σ i t ′ ≤ 1, σ i ≤ 1/2. Let w * = a i w i + b i u i , where u i ∈ S d-1 , u ⊥ w i , a i , b i > 0, a 2 i + b 2 i = 1. Define ℓ i (z) = sign((a i w i + b i u i /σ i )z + (t * -a t)/σ i ) and f i (z) = y(A 1/2 i z -tw i ). Then Pr z∼N (0,I) (ℓ i (z) ̸ = f i (z)) ≤ ϵ exp( t2 /2 + 4)/σ i . In particular, if σ i ≥ C exp((t ′ ) 2 /2)ϵ, for some sufficient large constant C, then there is a sufficiently small constant c such that Pr z∼N (0,I)(ℓ i (z) ̸ = f i (z)) ≤ c ≤ e -40 .The proof of Lemma 3.6 leverages the (v, s, σ)rejection procedure introduced in [15] (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 i ∈ S d-1 such that w * = a i w i + b i u i , where u i ∈ S d-1 , u ⊥ w i , a i , b i > 0, a 2 i + b 2 i = 1. Let t * , t ′ , σ i , ϵ be positive real numbers such that 0 ≤ t * ≤ t ′ , sin(θ i /2) ≤ σ i , σ i ≥ C exp((t ′ ) 2 /2)ϵ, and σ i t ′ ≤ 1. Let h * (x) = sign(w * • x + t * ) be a halfspace such that err(h * ) = opt ≤ ϵ. Define T i := t * -ai t σi √ a 2 i +b 2 i /σ 2 i , ℓ i (z) = sign((a i w i + b i u i /σ i )z + (t * -a t)/σ i ), ḡi = E z∈N (0,I) proj w ⊥ i zℓ i (z) and g i = E z∈N (0,I) proj w ⊥ i zf i (z), where f i (z) = y(A 1/2 i z -tw i ) for some t ∈ [0, t ′ ]. Let η i := Pr z∼N (0,I) (ℓ i (z) ̸ = f i (z)) and p i be the probability that f i (z) = -1. Then the following two properties hold.1. If p i ∈ (e -18 , 1 -e -18 ), then |T i | < 6 and if |T i | < 5, then p i ∈ (e -16 , 1 -e -16 ). 2. g i • u i ≥ ḡi • u i -2 √ eη i log(1/η i ) and ∥g i ∥ ≤ ∥ ḡi ∥ + 2 √ eη i log(1/η i ).Lemma 3.7 says as the noise level is small, it will not affect the structure lemma we established in Lemma 3.5 too much, and thus we are able to find the correct threshold t by checking the probability of f i (z) = -1. Furthermore, as long as we choose the correct threshold t, g i , the noisy version of ḡi still satisfies the conditions in the statement of Lemma 3.2 and thus can be used to improve w i .In Section 3.1, we have shown that given some w 0 non-trivially close to w * and some t ′ such that t ′ -1 log(1/ϵ) ≤ t * ≤ t ′, we can use Algorithm 3 to learn a good hypothesis with high probability. In this section, we show how to find such a good initialization w 0 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 [28, 34] ) using Fact 3.4. Such an approach does not work for general halfspaces because the length of the length of the Chow-Parameter can be as small as Õ(p), and thus needs roughly d/p random queries to estimate. In this section, we show how to overcome such an issue using a label smoothing technique, which has been useful in related problems [12] . The main results in this step can be summarized as follows. The proof of Theorem 3.8 is deferred to Appendix E.2 Theorem 3.8. Let h * (x) = sign(w * • x + t * ) and y(x) be any labeling function such that err(h * ) = opt ≤ ϵ ≤ 1/C for some large enough constant C. If |t -t * | ≤ 1/ log(1/ϵ), then with probability at least 1/3, Algorithm 2 makes M = Õ(1/p + d log(1/ϵ)), runs in poly(d, M ) time, and outputs some w 0 such that sin(θ(w 0 , w * )/2) ≤ max{min{1/t, 1/2}, O(η log(1/η)}, where η = ϵ/p. Due to the space limitations, here we only consider the case when t * is not extremely large, which roughly covers the regime when η log(1/η) ≤ 1/t. This suffices to capture some of the ideas and illustrate the power of the smoothed labeling. For the case when η log(1/η) > 1/t, we are 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.Input: error parameter ϵ ∈ (0, 1), confidence parameter δ ∈ (0, 1), threshold t > 0 Output: w 0 ∈ S d-1 Keep some x ∼ N (0, I) and query y(x) until see some x 0 such that y(x 0 ) = -1for i = 1, . . . , m = Õ(d log(1/ϵ)) doSample z i ∼ N (0, I) and query ỹ(x(i) 0 ) := y( 1 -ρ 2 x 0 + ρz i ) with ρ := min{1/t, 1} Let u 0 := 1 m m i=1 z i ỹ(x (i) 0 ) return w 0 := u 0 / ∥u 0 ∥To analyze Algorithm 2, we introduce the following definitions and notations. Definition 3.9 (Smoothed Label). Let x ∈ R d be a point and y(x) be any labeling function. For ρ ∈ [0, 1], define the random variable x = 1 -ρ 2 x + ρz, where z ∼ N (0, I). The smoothed label of x with parameter ρ is defined as ỹ(x) := y(x).We will require the following fact (whose proof follows via a direct calculation):Fact 3.10. Let h * (x) = sign(w * • x + t * ) be a halfspace. Let x, z ∈ R d and define x := 1 -ρ 2 x + ρz. Then h(z) := h * (x) = sign(w * • z + (t * + 1 -ρ 2 w * • x)/ρ) is another halfspace for z with threshold (t * + 1 -ρ 2 w * • x)/ρ.Let h * = sign(w * • x + t * ) be an optimal halfspace and let y(x) be any labeling function such that err(h * ) = opt ≤ ϵ. For x ∈ R d , we denote by η(x) := Pr(h * (x) ̸ = ỹ(x)), the noise level of the smoothed label. Assuming that we are given a random negative example x 0 , then with constant probability, it is close to the decision boundary, i.e., w * • x 0 ∈ (-t * -1 t * , -t * ). This implies that the threshold of h, the halfspace corresponding to the smoothed label at x 0 , is between (-1, 1). Moreover, the Chow-Parameter of h under the standard Gaussian distribution is parallel to w * with a constant length, by Fact 3.4. If opt = 0, then for every t ≤ log(1/ϵ), we only need another Õ(d log(1/ϵ)) queries to estimate the Chow-Parameter of h up to error O(1/t); thus, we get a warm start w 0 such that sin(θ 0 /2) ≤ 1/t, given |t -t * | is small. Therefore, the total number of queries we use to run Algorithm 2 is Õ(1/p + d log(1/p)). 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 a random x 0 is important for Algorithm 2 to succeed. If we are given some adversarially selected x 0 , 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 x 0 and could be corrupted by noise arbitrarily. However, we show in Appendix E.1 that, with a probability at least 2/3, the noise level η(x 0 ) of the smoothed label around x 0 is at most O(ϵ/p), if x 0 is a random example given y(x 0 ) = -1; and thus we can still estimate w * to a desired accuracy provided ϵ/p is not too large. Lemma 3.11. Let h * (x) = sign(w * • x + t * ) be a halfspace and y(x) be any labeling function such that err(h * ) = opt ≤ ϵ. Let x ∼ N (0, I) conditioned on y(x) = -1 be a Gaussian example with a negative label. If p > Cϵ for some large enough constant C, then with probability at least 1/2 we have η(x) ≤ 5ϵ/p and w * • x ∈ (-t * -1/t * , -t * ).Finally, we briefly discuss how to obtain a warm start when the threshold t * is very large. The details of this method can be found in Appendix F. By Theorem 3.8, when p is small, we are only able to get some w 0 such that sin(θ(w 0 , w * )) ≤ O(η log(1/η)) for η = ϵ/p. One possible approach is to use the localization technique we use in Section 3.1 to refine such w 0 . However, such an approach fails because after localization the noise rate would be possibly larger than the length of the Chow-Parameter that we want to estimate. This makes it impossible for us to learn the useful signal. On the other hand, [15] gave a randomized localization method that can make the expected noise level sufficiently smaller than the length of the Chow-Parameter we want to estimate; and thus will succeed with constant probability in each round of refinement. Unfortinately, such an approach cannot be used in a query-efficient manner, because to implement such a method we need to know θ(w i , w * ) up to an error 1/ log(1/ϵ), in each round of refinement. This implies that if we make a random guess of θ(w i , w * ), the probability of success in each round drops to only 1/ log(1/ϵ), which requires to rerun the whole algorithm too many times in order to succeed once.Such an issue could be addressed in a 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-Parameter we want to estimate, the length of the Chow-Parameter is only 1/p c , for some small constant c, as we can only make θ 0 smaller than some small constant. This still requires us to use d/p c queries to estimate it. Such an issue can again be addressed using the smoothed label method, where we use only 1/p c queries to search a small class example and use another Õ(d) queries to estimate the Chow-Parameter. Importantly, even such a method only succeeds with constant probability overall. As the refinement stage only runs for O(log log(1/ϵ)) rounds, we only need to rerun the entire algorithm O(log(1/ϵ)) times to succeed once.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-theoretical lower bound. In Appendix C, we discuss why we can without loss of generality assume the noise level opt ≤ ϵ and how to learn p up to a constant factor with Õ(1/p) queries. In Appendix D, we present the omitted proofs in Section 3.1 about how to 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 = {h(x) = sign(w • x + t) : R d → {±1} | w ∈ S d-1, t ≥ 0} be the class of halfspaces over X = R d . The labeling function y(x) : X → {±1} is a random function that maps each x ∈ X to an unknown binary random variable. For each h ∈ H, denote by err(h) = Pr x∼N (0,I) (h(x) ̸ = y(x)), opt := min h∈H err(h) and h * (x) = sign(w * • x + t * ) any halfspace with error opt. A membership query takes x ∈ X as an input and returns a label y ∼ y(x). We say a learning algorithm A is a constant-approximate learning algorithm if for every labeling function y(x), and for every ϵ, δ ∈ (0, 1), it outputs some ĥ ∈ H by adaptively making memberships queries, such that with probability at least 1 -δ, err( ĥ) ≤ O(opt + ϵ). 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 = {h(x) = sign(w • x + t) : R d → {±1} | w ∈ S d-1 , t ≥ 0} be the class of halfspaces over X = R d . Let D be a distribution over R d × {±1} such that D x ,the marginal distribution over x is the standard Gaussian distribution N (0, I). For each h ∈ H, denote by err(h) = Pr (x,y)∼N (0,I) (h(x) ̸ = y), opt := min h∈H err(h) and h * (x) = sign(w * • x + t * ) any halfspace with error opt. Let S be a set of m i.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 ∈ S and see its label y. We say a learning algorithm A is a constant-approximate learning algorithm if for every distribution D and for every ϵ, δ ∈ (0, 1), it outputs some ĥ ∈ 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 -δ, err( ĥ) ≤ O(opt + ϵ). The label complexity of A is the total number label queries made over S during the learning processB Omitted Proofs in Section 2 B.1 Proof of Lemma 2.1Proof of Lemma 2.1. Let A be such a learning algorithm. We select a random set of m examples S 1 and give it to A. With probability at least 2/3, A makes r queries and learns a halfspace ĥ with error p/2 with respect to h * . This implies that given a Gaussian example, with probability at least p/2 it will predict negative, and given it predicts negative, with probability at 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 ĥ and at least a constant fraction of these examples are actually negative. Thus, given such a ĥ with probability at least 3/4, we can find d negative examples in S by randomly querying O(d) examples that are predicted as negative by ĥ.Let v = Aw * = (w * • x 1 , . . . , w * • x k ) ⊤ . Consider the projection of w * over the subspace spanned by the row vectors of A, A ⊤ (AA ⊤ ) -1 Aw * . Assuming that x 1 , . . . , x k are all negative, then ∥v∥ 2 ≥ k(t * ) 2 . This implies that the square of the norm of the projection of w * onto the subspace isB := (w * ) ⊤ A ⊤ (AA ⊤ ) -1 Aw * = v ⊤ (AA ⊤ ) -1 v ≥ ∥v∥ 2 / AA ⊤ 2 ≥ k(t * ) 2 / AA ⊤ 2 .Since w * is uniformly chosen from the unit sphere, by Lemma B.1 in [24] , the square norm of w * projected onto a fixed k-dimensional subspace is a random variable drawn from a beta distributionEQUATION)) k ≤ (O(p log(1/p))) k .The last inequality follows by Fact D.4.We will first show that for a given A ∈ R k×d , AA ⊤ -dI 2 is small with high probability if the rows of A are drawn i.i.d. from d-dimensional standard Gaussian. Let N be an 1/4-net of S k-1 .According to [33] , we know that |N | ≤ e 3k and AA ⊤ -dI 2 ≤ 2 sup u∈N u t (AA ⊤ -dI)u . Thus, to show that AA ⊤ -dI 2 is small with high probability, it is equivalent to show with high probability for every u ∈ N , u ⊤ (AA ⊤ -dI)u is small.Fix u ∈ N to be a unit vector. We haveu ⊤ AA ⊤ u -du ⊤ u = d j=1 (u ⊤ A j ) 2 -d.Notice that each u ⊤ A j is a standard Gaussian variable and thus d j=1 (u ⊤ A j ) 2 is a chi-squared distribution with freedom d. By [33] , we havePr   d j=1 (u ⊤ A j ) 2 -d ≥ 2ξd   ≤ 2 exp -dξ 2 /2 .Since |N | ≤ e 3k , we know thatPr AA ⊤ -dI 2 ≥ ξd Pr sup u∈N u ⊤ (AA ⊤ -d)u ≥ 2ξd ≤ 2 exp(3k -dξ 2 /2).Since there are at most m k such k-tuples of examples, the probability that there exists a k-tuple such that AA ⊤ -dI 2 is larger thanξd = O(d/(t * ) 2 ) is at most 2 m k exp(3k -dξ 2 /2) ≤ 2 em k k exp(3k -dξ 2 /2) ≤ 2 exp(-(dξ 2 /2 -3k -k log(er/k))) ≤ 2/3, by choosing k = d/(log(r)(t * ) 4 ) and ξ = O(1/(t * ) 2 ).C Omitted Details in Section 3C.1 Discussion on the Noise Level optAssuming we know some α such that ϵ ≤ α/2 ≤ opt ≤ α, then learning ĥ upto error O(opt + ϵ) is equivalent to learning it up to error O(α). By guessing α = ϵ2 i for i = 0, . . . , O(log(1/ϵ)), we can always obtain a desired α and use it to run the learning algorithm and get a good hypothesis. Such an approach will generate a list of O(log(1/ϵ)) different hypotheses, finding a good enough hypothesis among them only costs polylog(1/ϵ) queries using a standard tournament approach, such as the following lemma. Lemma C.1 (Lemma 3.6 in [10] ). Let ϵ, δ ∈ (0, 1) and D a distribution over R d × {0, 1}. Given a list of hypothesises {h (i) } k i=1 , there is an algorithm that draws O(k 2 log(k/δ)/ϵ) unlabeled examples from D x and performs O(k 2 log(d/δ)) label queries runs in poly(d, ϵ, δ) times and output a hypothesis ĥ such that Pr (x,y)∼D ( ĥ(x) ̸ = y) ≤ 10 mini∈[k] Pr (x,y)∼D (h (i) (x) ̸ = y) + ϵ.In this part, we describe a simple approach to estimate the bias p up to a constant factor using Õ(1/p) queries. To do this we will estimate p = Pr x∼N (0,I) (y(x) = -1), the noise version of p as |p -p| ≤ ϵ. If we can estimate p such that p/2 ≤ p ≤ p or verify that p ≤ (C -1)ϵ, then p satisfies our purpose. By Chebyshev's inequality, if p ≤ 3p/4, then taking O(1/p) random queries at x and computing the empirical probability of y(x) = -1, with probability 2/3, we are able to verify this fact by checking whether the empirical probability is less than 5p/6. On the other hand, if 4p/5 ≤ p ≤ p, with probability 2/3 we are able to verify this fact by checking whether the empirical probability is greater than 5p/6. Furthermore, by repeating this approach O(log(1/δ)) times and using a majority voting trick, we can boost the probability of success up to 1 -δ. We will run the above approach for p = (4/5) i /2 for i = 0, 1, . . . until we find p ≥ (4/5)p or p = C ′ ϵ for some constant C ′ . In the first case (4/5)p ≤ p ≤ (25/24)p and we find a good approximation for p and thus for p. In the second case, we can conclude that p is smaller than O(ϵ) D Omitted Proofs from Section 3.1 Algorithm 3 REFINE(Learn the correct direction w * based on a warm start w 0 ) Input: Intial direction w 0 ∈ S d-1 , t ′ > 0, an approximate threshold, error parameter ϵ ∈ (0, 1), confidence parameter δ ∈ (0, 1)Output: w T ∈ S d-1 , an approximation of w * , t ∈ R, an approximation of t * Let ϵ ′ = Cϵ exp(t ′2 /2) m = Õ(d), T = O(log(1/ϵ ′ )) σ 0 ← min{1/t ′ , 1/2}. Let C 1 , C 2 be large enough constants for i = 0, . . . , T do A i ← I -(1 -σ 2 i )w i w t i , µ i ← σ i /C 1 Find t ∈ {0,ϵ, 2ϵ, . . . , t ′ } using the following binary search method, if no such t is found, then stop the algorithm and return w T = 0. ▷ Find the correct threshold to construct the gradient.Draw O(log(1/δ)) Gaussian samples z ∼ N (0, I), query A 1/2 i z -tw i and compute p( t), the empirical probability that a query returns -1. If p( t) < e -17 , properly decrease t, if p( t) > e -17 , properly increase t. Otherwise, declare that t is found.for j = 1, . . . , m do Draw z j ∼ N (0, I), make queries at zj := A 1/2 i z j -tw i and denote byf i (z j ) the result ĝi ← 1 m m j=1 proj w ⊥ i (z j f i (z j )) ▷ Construct the gradient w i+1 ← proj S d-1 (w i + µ i ĝi ), σ i+1 ← (1 -1/C 2 )σ i ▷ Gradient Descent t ← t▷ Use the threshold found in the last round return w T , t D.1 Proof of Lemma 3.2Proof of Lemma 3.2. We first observe that∥w i+1 -w * ∥ 2 = ∥proj S d-1 (w i + µ i ĝi ) -proj S d-1 (w * )∥ 2 ≤ ∥w i + µ i ĝi -w * ∥ 2 .It remains to upper bound ∥w i + µ i ĝi -w * ∥ 2 . We have∥w i + µ i ĝi -w * ∥ 2 = ∥w i -w * ∥ 2 + 2µ i ĝi • (w i -w * ) + µ 2 i ∥ ĝi ∥ 2 = ∥w i -w * ∥ 2 -2µ i ĝi • w * + µ 2 i ∥ ĝi ∥ 2 = ∥w i -w * ∥ 2 -2µ i g i • w * + 2µ i (g i -ĝi ) • w * + µ 2 i ∥ ĝi ∥ 2 = ∥w i -w * ∥ 2 -2µ i g i • w * + 2µ i (g i -ĝi ) • b i u + µ 2 i ∥ ĝi ∥ 2 ≤ ∥w i -w * ∥ 2 -2µ i g i • w * + 2µ i b i ∥g i -ĝi ∥ + µ 2 i ∥ ĝi ∥ 2 . = ∥w i -w * ∥ 2 -2µ i b i g i • u + 2µ i b i ∥g i -ĝi ∥ + µ 2 i ∥ ĝi ∥ 2 .Here, in the second equality, we use the fact that ĝi ⊥ w i and in the fourth equality, we use the fact that(g i -ĝi ) • w * = (g i -ĝi ) • a i w i + (g i -ĝi ) • b i u = (g i -ĝi ) • b i u.Next, we assume that sin(θ i /2) ≤ σ i and show that we can carefully choose parameter µ i , σ i+1 to make sin(θ i+1 /2) ≤ σ i+1 . We consider two cases. In the first case, we assume 3σ i /4 sin(θ i /2) ≤ σ i . Since ∥w i -w * ∥ = 2 sin θi 2 , by Lemma 3.2, we have(2 sin θ i+1 2 ) 2 ≤ (2 sin θ i 2 ) 2 -5µ i b i + 2µ i c 2 b i + µ 2 i c 2 1 ≤ 4σ 2 i -15σ 2 i c 1 /(2C 1 ) + 4c 2 σ 2 i /C 1 + c 2 1 σ 2 i /C 2 1 ≤ 4σ 2 i -5σ 2 i c 1 /(2C 1 ) + σ 2 i c 1 /(10C 1 ) + c 2 1 σ 2 i /C 2 1 ≤ 4(1 -5c 1 /(8C 1 ) + c 1 /(80C 2 1 ) + c 2 1 /(2C 2 1 ))σ 2 i := 4(1 -1/C 2 ) 2 σ 2 i, where use the fact that b i ≤ 2 sin(θ i /2) ≤ 3σ i /2 and the fact that C 1 can be made large enough.In the second case, we assume sin(θ i /2) < 3σ i /4. In this case, using the fact that2(sin( θ i+1 2 ) -sin( θ i 2 )) = ∥w i+1 -w * ∥ -∥w i -w * ∥ ≤ ∥w i+1 -w i ∥ ≤ ∥w i + µ i ĝi -w i ∥ = µ i ∥ ĝi ∥ .We haveσ i+1 -sin( θ i+1 2 ) = σ i+1 -sin( θ i 2 ) -(sin( θ i+1 2 ) -sin( θ i 2 )) ≥ σ i+1 - 3σ i 4 - σ i ∥ ĝi ∥ C 1 ≥ ( 1 4 - 1 C 2 - 1 C 1 )σ i > 0,where the last inequality holds because the parameter C 1 , C 2 can be chosen larger than 8.Lemma 3.2 implies that if g i has enough correlation with respect to w * but is also not too long, then by estimating g i up to some error, we can ensure ∥w i -w * ∥ drops significantly each round. Formally, we have the following corollary.Corollary D.1. In Algorithm 3, denote by θ i = θ(w * , w i ). Assume that sin θi 2 ≤ σ i . If there exist a suitable constant c 1 and a small enough constant c 2 such that g i • w * ≥ c 1 σ i /10, ∥ ĝi ∥ ≤ c 1 and ∥g i -ĝi ∥ ≤ c 2 . Then there exists large enough constant C 1 , C 2 such that by takingµ i = σ i /C 1 , it holds that sin θi+1 2 ≤ (1 -1/C 2 )σ i .Proof of Corollary D.1. Since ∥w i -w * ∥ = 2 sin θi 2 , by Lemma 3.2, we have(2 sin θ i+1 2 ) 2 ≤ (2 sin θ i 2 ) 2 -5µ i σ i + 2µ i c 2 σ i + µ 2 i c 2 1 ≤ 4σ 2 i -5σ 2 i c 1 /C 1 + 2c 2 σ 2 /C 1 + c 2 1 σ 2 i /C 2 1 ≤ 4σ 2 i -5σ 2 i c 1 /C 1 + 2σ 2 /C 2 1 + c 2 1 σ 2 i /C 2 1 ≤ 4(1 -5c 1 /(4C 1 ) + 1/(2C 2 1 ) + c 2 1 /(2C 2 1 ))σ 2 i := 4(1 -1/C 2 ) 2 σ 2 i, where the third and the fourth inequalities hold when C 1 is large enough.Proof of Lemma 3.5. We first prove Item 1. Since T i is a monotone decreasing function on t, and t ′ > t * , it remains to show that for every t such that t -t * ≤ σ i , |T i | ≤ 5. Notice thatEQUATIONBy Fact 3.3, we know thatḡi = 2 π exp(-T 2 i /2) b i u i /σ i a 2 i + b 2 i /σ 2 i . Since a 2 i + b 2 i /σ 2 i ≤ √ 5and |T i | ≤ 5, we immediately obatin Item 2. Finally, we prove Item 3. Using the monotone property of T i , we prove the case where t < t * -40σ i and the case t > t * + 40σ i can proved symmetrically. We haveT i = t * -a i t σ i a 2 i + b 2 i /σ 2 i = t * - t σ i a 2 i + b 2 i /σ 2 i + t -a i t σ i a 2 i + b 2 i /σ 2 i ≥ 40σ i √ 5σ i -4 ≥ 10,where the first inequality holds because of Equation (1).To prove Lemma 3.6, we first introduce the following definition called (v, s, σ)rejection procedure. Definition D.2 ((v, s, σ)rejection procedure). Let v ∈ R d be a unit vector and s, σ be real numbers such that σ < 1. Given a point x ∈ R d , (v, s, σ)rejection procedure accepts it with probabilityexp -(σ -2 -1)(v • x + s/(1 -σ 2 )) 2 /2and rejects it otherwise.(v, s, σ)rejection procedure satisfies the following property. Lemma D.3 (Lemma C.7, Lemma C.8 in [15] ). If x ∼ N (0, I) is fed into the (v, s, σ)rejection procedure, then it is accepted with probability σ exp(-s 2 /(2(1 -σ 2 ))). In particular, when σs ≤ 2 and σ ≤ 1/2, the accepted probability is at least σ exp(-s 2 /2 -4). Moreover, the distribution on x conditioned on acceptance is that of N (-sv, A v,σ ), whereA v,σ = I -(1 -σ 2 )vv t .Proof of Lemma 3.6. Let z := A 1/2 i z -tw i . By Fact 3.3, we know that ℓ i (z) = h * (z), ∀z ∈ R d . By Lemma 3.6, we know that if z ∼ N (0, I), then z ∼ N (-tw i , A i ), which can be seen by feeding a Gaussian random vector into the (w i , t, σ i )-rejection procedure conditioned on acceptance. Since err(h * ) = opt ≤ ϵ and the accepted rate is at least σ exp(-s 2 /2 -4), we know from Lemma 3.6 that Pr z∼N (0,I)(ℓ i (z) ̸ = f i (z)) = Pr z∼N (0,I) (h * (z) ̸ = f i (z)) ≤ ϵ exp( t2 /2 + 4)/σ i . In particular, if σ i ≥ C exp((t ′ ) 2 /2)ϵ, we have ϵ exp( t2 /2 + 4)/σ i ≤ ϵ exp( t2 /2 + 4) / Cϵ exp((t ′ ) 2 /2) ≤ e 4 /C := c ≤ e -40 .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 ∈ R the bias p of a halfspace h(x) = sign(w * • x + t) can be bounded as2 π exp(-t 2 /2) t + √ t 2 + 4 ≤ p ≤ 2 π exp(-t 2 /2) t + √ t 2 + 2 .Fact D.5 (Lemma B.4 in [16] ). Let D be a distribution on R d × {±1} with standard normal x-margin and let w, u be two orthogonal unit vectors. Let B be any interval over R and let S(x, y) be any event over R d × {±1}, such that S(x, y) ⊆ {w • x ∈ B} then it holdsE D (|u • x| 1{S(x, y)}) ≤ 2 √ e Pr(S(x, y)) log( Pr(w • x ∈ B) Pr(S(x, y))).Proof of Lemma 3.7. We start by proving the first part of Lemma 3.7. By Lemma 3.6, we know that η i := Pr z∼N (0,I) (ℓ i (z) ̸ = f i (z)) ≤ e -40 . This implies that Pr z∼N (0,I) (ℓ i (z) = -1) -p i ≤ e -40 . We first show that when p i is in a reasonable range, |T i | < 6. Assuming by contradiction that |T i | ≥ 6, then by Fact D.4, the bias of ℓ i (z) must be at most exp(-T 2 i /2)/(2T i ) ≤ e -20 , which implies that it cannot be the case where p i ∈ (e -18 , 1 -e -18 ). Similarly, if |T i | < 5, then by Fact D.4, the bias of ℓ i (z) must be at least exp(-T 2 i /2)/20 ≥ e -15.5 . As the noise level η i ≤ e -40 , we have p i ∈ (e -18 , 1 -e -18 ).Next, we prove the second part of Lemma 3.7. We start by bounding the correlation between g i and u i . We haveg i • u i = E z∈N (0,I) proj w ⊥ i z(ℓ i (z) + f i (z) -ℓ i (z)) • u i = ḡi • u i - E z∈N (0,I) proj w ⊥ i z(ℓ i (z) -f i (z)) • u i ≥ ḡi • u i - E z∈N (0,I) |u i • z|1{ℓ i (z) ̸ = f i (z)} ≥ ḡi • u i -2 √ eη i log(1/η i ),where the third and the last inequalities hold because u i ⊥ w i and Fact D.5.We next bound the norm of g i . Since both ḡi and g i are orthogonal to w i . It is sufficient to show that for every unit vector u ⊥ w i ,|g i • u| ≤ | ḡi • u| + 4 √ eη i log(1/η i ).We have|g i • u| = E z∈N (0,I) proj w ⊥ i z(ℓ i (z) + f i (z) -ℓ i (z)) • u = ḡi • u i - E z∈N (0,I) proj w ⊥ i z(ℓ i (z) -f i (z)) • u i ≤ | ḡi • u i | + E z∈N (0,I) |u i • z|1{ℓ i (z) ̸ = f i (z)} ≤ | ḡi • u i | + 2 √ eη i log(1/η i ).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 [15] ). Under the standard normal distribution for every pair of unit vector w, w * and real number t,Pr(sign(w * • x + t) ̸ = sign(w • x + t)) ≤ sin(θ(w, w * )) 2 exp(-t 2 /2).Proof of Theorem 3.1. Denote by θ i := θ(w i , w * ). We will first show by induction that with high probability in the i-th round of Algorithm 3, sin(θ i /2) ≤ σ i . Assuming this is correct, since σ T = Cϵ exp (t ′ ) 2 /2 for some large constant C. We will haveEQUATIONSince opt ≤ ϵ, this implies that by providing a good enough estimation of t * , we found a hypothesis with error at most O(ϵ). Now we show that this is actually true. For i = 0, sin(θ 0 /2) ≤ σ 0 holds by our assumption. Now, we 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 ĝi we use in the update w i+1 = proj w ⊥ i (w i + µ i ĝi ) satisfies the condition of Lemma 3.2. Recall that we have the following notations.w * = a i w i + b i u i . T i := t * -ai t σi √ a 2 i +b 2 i /σ 2 i , ℓ i (z) = sign((a i w i + b i u i /σ i )z + (t * -a t)/σ i ), ḡi = E z∈N (0,I) proj w ⊥ i zℓ i (z) and g i = E z∈N (0,I) proj w ⊥ i zf i (z), where f i (z) = y(A 1/2 i z -tw i ). And η i := Pr z∼N (0,I) (ℓ i (z) ̸ = f i (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 ≤ t ′ such that |T i | ≤ 6. Denote by p i the probability that f i (z) = -1. We notice that for each fixed t by randomly querying O(log(1/δ)) f i (z), we can with high probability check if p i ∈ (e -17 , 1 -e -17 ) or not. This can be done using the same method we used in Appendix C.2.Since b i /2 = sin θ i /2 ≤ sin(θ i /2) ≤ σ i , we know from Lemma 3.7 that as long as we find some t such that p i ∈ (e -17 , 1 -e -17 ), we have have |T i | ≤ 6. By Lemma 3.5 and Lemma 3.7, we know that there exists an interval I i ⊆ [0, t ′ ] of length at least σ i > ϵ such that for every t ∈ I i , |T i | < 5 and thus p i ∈ (e -16 , 1 -e -16 ). Thus, by performing a binary search at most O(log(1/ϵ)) times, with high probability, we are able to find such a t such that |T i | < 6. Given that we find such a correct t, we will consider two cases.First, we assume that 3σ i /4 ≤ sin(θ i /2) ≤ σ i . We will show that with high probability g i and its empirical estimation ĝi satisfy the condition in the statement of Corollary D.1 and thus prove sin(θ i+1 /2) ≤ σ i+1 . Since proj w ⊥ i zf i (z) is 1-subgaussian random vector, by Hoeffding's inequality, we know that with Õ(d) samples of z, with high probability we have ∥g i -ĝi ∥ ≤ c 2 ≤ e -40 . By Lemma 3.7 and Lemma 3.5, we haveg i • u i = ḡi • u i -2 √ eη i log(1/η i ) ≥ b i ∥ ḡi ∥ σ i e -19 -100e -40 ≥ e -19 -100e -40 ≥ e -20 := c 1 . ∥ ĝi ∥ ≤ ∥g i ∥ + ∥g i -ĝi ∥ ≤ ∥ ḡi ∥ + 2 √ eη i log(1/η i )) + e -40 ≤ 3e -19 ≤ 10c 1 .Thus, by Corollary D.1, we can conclude that sin(θ i+1 /2)≤ (1 -1/C 2 )σ i = σ i+1 , for a large constant C 2 .Next, we consider the case where sin(θ i /2) < 3σ i /4. In this case, as we have shown that ∥ ĝi ∥ is bounded by some universal constant, the condition of Lemma 3.2 is fulfilled automatically and thus sin(θ i+1 /2)≤ (1 -1/C 2 )σ i = σ i+1 , for a large constant C 2 .By induction, with a high probability for each i, we have sin(θ i /2) ≤ σ i and thus w T is a good approximation of w * . It remains to show that t is also a good approximation of t * . Recall that t = t < t ′ such that |T T | < 6. Lemma 3.5 implies that t -t * ≤ 40σ T = 40Cϵ exp (t ′ ) 2 /2. Thus,Pr x∼N (0,I) sign(w T • x + t * ) ̸ = sign(w T • x + t) ≤ (2π) -1 t * -t exp(- (t * -t * -t ) 2 2 ) ≤ (2π) -1 40Cϵ exp( (t ′ ) 2 -(t * -t * -t ) 2 2 ) ≤ (2π) -1 40Cϵ exp(2t ′ (t ′ -t * + 40σ T )) ≤ (2π) -1 40Cϵ exp(2t ′ (40σ T + 1 log(1/ϵ) )) = O(ϵ exp(80t ′ σ T )). Since σ T t ′ = O(ϵt ′ exp((t ′ ) 2 /2)) and t ′ exp((t ′ ) 2 /2) ≤ 1/(Cϵ), we can conclude that Pr x∼N (0,I) sign(w T • x + t * ) ̸ = sign(w T • x + t) ≤ O(ϵ). Thus, with high probability err(sign(wT • x + t)) ≤ O(ϵ).Finally, we count the number of queries used by Algorithm 3. In each round of the algorithm, we perform O(log(1/ϵ)) binary searches to find the correct parameter t, each of which takes us only Õ(1) queries. We also make Õ(d) queries to construct ĝi in each round of the algorithm. Thus, each round of Algorithm 3 takes Õ(d + log(1/ϵ)) queries. Since there are at most O(log(1/ϵ)) rounds, the query complexity of Algorithm 3 is Õ(dpolylog(1/ϵ)).E Omitted Proofs from Section 3.2 (h * (x) = -1) -ϵ ≥ (1 -1/C)p.We will first show thatE x∼D -η(x) ≤ O(ϵ/p). Denote by Z := 1 -ρ 2 x + ρz, where x ∼ D -, z ∼ N (0, I), then E x∼D -η(x) = Pr x∼D -,z∼N (0,I) 1{h * ( 1 -ρ 2 x + ρz) ̸ = y( 1 -ρ 2 x + ρz)} = Pr Z 1{h * (Z) ̸ = y(Z)}.Since z and x are independent, we notice that Z can be simulated via the following reject sampling process. We draw x ∼ N (0, I) and Z ∼ N (0, I) to construct Z = 1 -ρ 2 x + ρz and accepted Z when y(x) = -1. Since 1 -ρ 2 N (0, I) + ρN (0, I) = N (0, I), Z can be seen as a reject sampling process with an accepted rate at least (1 -1/C)p. Since the noise rate opt ≤ ϵ, we know thatE x∼D - η(x) = Pr Z 1{h * (Z) ̸ = y(Z)} ≤ (1 -1/C) -1 ϵ/p.By Markov's inequality, we know that with probability at least 3/4, η(x) ≤ 5ϵ/p, with x ∼ D -.Next, we show that with a constant probability a negative example x must be close to the decision boundary of h * . We havePr x∼D -w * • x < -t * - 1 t * = Pr x∼D - (h * (x) = -1) Pr x∼D -|{h * (x)=-1} w * • x < -t * - 1 t * + Pr x∼D -(h * (x) = +1) Pr x∼D -|{h * (x)=+1} w * • x < -t * - 1 t * ≤ Pr x∼D -|{h * (x)=-1} w * • x < -t * - 1 t * + 1/C ≤ Pr x∼N (0,I)|{h * (x)=-1} w * • x < -t * - 1 t * + 2/C = ∞ t * +1/t * exp(-s 2 /2)ds/ ∞ t * exp(-s 2 /2)ds + 2/C ≤ exp(- (t * + 1 t * ) 2 -(t * ) 2 2 ) + 2/C = exp(- (2t * + 1/t * )/t * ) 2 ) + 2/C ≤ e -1 + 2/C,where in the third inequality, we use Fact D.4.Thus, by union bound, with probability at least 1/2, it simultaneously holds that η(x) ≤ 5ϵ/p and w * • x ≤ -t * -1/t * .Proof of Theorem 3.8. We consider two cases. First, if t ′ < 1, then each x (i) 0 = z i is drawn from the standard Gaussian. We haveu 0 - E z∼N (0,I) zh * (z) = u 0 - E z∼N (0,I) zy(z) + E z∼N (0,I) zy(z) - E z∼N (0,I) zh * (z) ≤ u 0 - E z∼N (0,I) zy(z) + E z∼N (0,I) zy(z) - E z∼N (0,I) zh * (z) ≤ u 0 - E z∼N (0,I) zy(z) + sup u∈S d-1 E z∼N (0,I) |u • z| 1(y(z) ̸ = h * (z)) ≤ u 0 - E z∼N (0,I) zy(z) + 2 √ eϵ log(1/ϵ),where the last inequality holds because of Fact D.5. Since each z i y(z i ) is a standard Gaussian, by Hoeffding's inequality, we havePr( u 0 - E z∼N (0,I) zy(z) ≥ r ≤ 2 exp(- mr 2 d ) ≤ polylog(δ),when m ≥ Ω(d/r 2 ). By taking r = (20 log(1/ϵ)) -1 , we obtain that u 0 -E z∼N (0,I) zy(z) ≤ (20 log(1/ϵ)) -1 with high probability. Thusu 0 - E z∼N (0,I) zh * (z) ≤ (20 log(1/ϵ)) -1 + 2 √ eϵ log(1/ϵ) ≤ O(log(1/ϵ) -1 ).By Fact 3.4, we know that E z∼N (0,I) zh * (z) = ξw * for some ξ ≥ e -1 , which also implies that ∥u 0 ∥ ≥ e -1 /2, because u 0 sufficiently close to E z∼N (0,I) zh * (z).Sinceu 0 - E z∼N (0,I) zh * (z) 2 = ∥u 0 ∥ 2 + E z∼N (0,I) zh * (z) 2 -2 E z∼N (0,I) zh * (z) ∥u 0 ∥ 2 cos θ(w 0 , w * ) ≥ 2 E z∼N (0,I) zh * (z) ∥u 0 ∥ (1 -cos θ(w 0 , w * )) = 4 E z∼N (0,I) zh * (z) ∥u 0 ∥ sin 2 (θ(w 0 , w * )/2), we get sin(θ(w 0 , w * )/2) ≤ u 0 -E z∼N (0,I) zh * (z) 2 /4 E z∼N (0,I) zh * (z) ∥u 0 ∥ ≤ O(1/ log(1/ϵ)).In particular as ϵ < 1/C for some large enough C, we conclude that sin(θ(w 0 , w * )/2) ≤ max{min{1/t, 1/2}, O(η log(1/η)}.We next address the case when t > 1. By Lemma 3.11, we know that with probability at least 1/2, we have η(x) ≤ 5ϵ/p and w * • x ∈ (-t * -1/t * , -t * ). We will assume these two events happen in the rest of the proof. Let z ∼ N (0, I) and by Fact 3.10, defineh(z) := h * ( x0 ) = sign(w * • z + t * + 1 -ρ 2 w * • x 0 ρ ) .By Lemma 3.11, we know that Pr z∼N (0,I) h(z) ̸ = ỹ(x 0 ) = η(x 0 ) ≤ 5ϵ/p. Similar to the first case, we haveu 0 - E z∼N (0,I) z h(z) = u 0 - E z∼N (0,I) z ỹ(x 0 ) + E z∼N (0,I) z ỹ(x 0 ) - E z∼N (0,I) z h(z) ≤ u 0 - E z∼N (0,I) z h(z) + E z∼N (0,I) z h(z) - E z∼N (0,I) z h(z) ≤ u 0 - E z∼N (0,I) z ỹ(x 0 ) + sup u∈S d-1 E z∼N (0,I) |u • z| 1(ỹ(x 0 ) ̸ = h(z)) ≤ u 0 - E z∼N (0,I) z ỹ(x 0 ) + 2 √ eη(x 0 ) log(1/η(x 0 )) ≤ max{O(η(x 0 ) log(1/η(x 0 ))), 1/(50 log(1/ϵ))} ≤ max{O(η log(1/η)), 1/(50t))} ,where in the second last inequality we use the fact thatu 0 -E z∼N (0,I) z ỹ(x 0 ) ≤ 1/(100 log(1/ϵ)) ≤ 1/(100t) with high probability. Since ρ = 1/t, |t -t * | ≤ 1/log(1/ϵ) and t * ≤ log(1/ϵ) ≪ log(1/ϵ), the threshold T ρ = t * + √ 1-ρ 2 w * •x0 ρcan be bounded as follows.-1 ≤ t * -1 -ρ 2 (t * + 1 t * ) ρ ≤ T ρ ≤ t * (1 -1 -ρ 2 ) ρ ≤ tt * /(t) 2 ≤ 1 + o(1).Fact 3.4 implies that E z∼N (0,I) z h(z) = ξw * for some ξ ≥ e -1 . Since u 0 is close to E z∼N (0,I) z, ∥u 0 ∥ ≥ e -1 /2. Thus, we obtain thatsin(θ(w 0 , w * )/2) ≤ u 0 - E z∼N (0,I) z h(z) 2 /4 E z∼N (0,I) zh * (z) ∥u 0 ∥ ≤ max{min{1/t, 1/2}, O(η log(1/η)}.By Theorem 3.8, we know that Algorithm 2 can only find some w 0 such that sin(θ 0 /2) ≤ O(η log(1/η)), where η = ϵ/p when p is small such that η log(1/η) > O(1/t). In this section, we design an algorithm that finds a warm start with a non-negligible probability of success when the threshold t * falls in this range. Formally, we prove the following theorem. Theorem F.1. Let h * (x) = sign(w * • x + t * ) be a halfspace with bias p and y(x) be any labeling function such that err(h * ) = opt ≤ ϵ ≤ 1/C for some large enough constant C. Let t be a scalar such that t -1/ log(1/ϵ) ≤ t * ≤ t and 1/(400t) ≤ η log(1/η) ≤ 1/C for some large enough constant C, where η = ϵ/p, Algorithm 5 makes M = Õ(1/p + d log(1/ϵ)) membership queries, runs in poly(d, M ) time and with probability at least 1/polylog(1/ϵ), outputs some w 0 such that sin(θ(w 0 , w * )/2) ≤ 1/t.The high-level idea of our algorithm is as follows. Although Algorithm 2 will not provide us a w 0 such that θ 0 ≤ O(1/t), θ 0 is still smaller than a sufficiently small constant. We want to use the localization technique to refine w 0 so that after T rounds of refinement, sin(θ T /2) ≤ σ T = 1/t. Recall in Appendix D, we introduce Definition D.2, (v, s, σ)-rejection procedure, which can be simulated using membership query. Passing a Gaussian random point to the (v, s, σ)-rejection procedure, according to Lemma D.3, we will get a another distribution over R d × {±1} that behaves the same as another halfspace h ′ .In this section, we want to design a (v, s, σ)-rejection procedure such that the direction of the halfspace h ′ 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 h ′ . Write w * = a i w i + b i u i . We want to set up v = w i , σ = 1/t and s ∼ (a i t, a i t + b i ) uniformly. Such a method is called the randomized threshold method in [15] . This method has the following property.Lemma F.2 (Proposition C.11 in [15] ). Let a, b, t > 0 such that a 2 + b 2 = 1 and t larger than some constant C. Let w ∈ S d-1 . Let s ∼ [at, at + b] uniformly. For each x ∈ R d , the expected probability that x is accepted by the (w, s, σ)-rejection procedure is at most σ/b, where σ = 1/t.Lemma F.2 implies that in expectation over the randomness of s, only σ/b i -fraction of the noisy points will pass the (w i , s, σ)-rejection 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(ϵ exp(s 2 /2)/b i ). However, as we do not know b i , using some b that is slightly far from b i 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 a b, we can with high probability check if it can be used to construct the rejection procedure or not and in particular, when b - 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 z∼N (0,I) (h * (Az -sw) ̸ = y(Az -sw)) ≤ 6ϵ 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 p(b, s). Write s = at + ξ, where ξ ∈ [0, b], then we have1/ log(1/ϵ) < b i < b,EQUATIONwhere, in the first inequality, we use the fact that T bs ≤ bt, in the second inequality, we use the fact that t exp(t 2 /2) ≤ 1/(Cϵ) for a sufficiently large constant C, and in the last inequality, we use the fact that a 2 + b 2 = 1, ξ 2 < b 2 . By Fact D.4, we know that exp(-T 2 bs /2)/T bs is at most 3 times p(b, s), and thus η ≤ p(b, s)/C ′ for a large enough constant C ′ . By Fact 3.3, we know that the ground truth label ℓ(z) = h * (Az -sw) = sign((a * σw + b * u) • z + t * -a * s). By Hoeffding's inequality, with high probability, we are able to estimate the probability of y(Az -sw) = -1 up to error p(b, s)/20 using Õ(1/p 2 (b, s)) queries. In particular, since T bs ≤ tb < 1/4, by Fact D.4, we know that p(b, s) > p 1/4 and will cost us only Õ(1/ √ p) queries.If the probability that p s > p(b, s)/4 is at most 1/2, then in each round i of Algorithm 4, with probability at least 1/3 it holds simultaneously that p s < p(b, s)/4 and η ≤ p(b, s)/C ′ . In this case, with high probability ps < p(b, s)/3 and Count does not increase. Thus, with probability at least with high probability outputs "Yes". To do this, we will show the true threshold of ℓ(z) is close to T bs . We havet * -a * s (b * ) 2 + (a * σ) 2 -T bs ≤ t * -a * s b * - t -as b ≤ O(log(1/ϵ) -1 ) b * + |t -as| 1 b * - 1 b ≤ O(log(1/ϵ) -1/2 ) + b 2 t(b -b * ) b * b = O(log(1/ϵ) -1/2 ) + O(t log(1/ϵ) -1 ) = O(log(1/ϵ) -1/2 ).By Fact D.4, it holds with probability 1 that p s > p(b, s)/2.Now assume that we have sin(θ i /2) ≤ σ i , then b i ≤ 2σ i . This implies that by testing b = 2σ i -j log(1/ϵ) for j = 0, 1, . . . , we only need O(log(1/ϵ)) rounds to find the correct b. With this fact, we have the following Algorithm 5.Proof of Theorem F.1. Let θ i = θ(w i , w * ) and write w * = a i w i +b i u i , where a i , b i > 0, a 2 i +b 2 i = 1. By Algorithm 2, we know that with probability at least 1/3, sin(θ 0 /2) ≤ O(ϵ/p log(p/ϵ)). We will assume sin(θ 0 /2) ≤ ϵ/p log(p/ϵ) holds throughout the proof, since the constant before ϵ/p log(p/ϵ) can always be assumed to be normalized as 1/C is large enough. In round i of the algorithm, we write w * = a i w i + b i u i where a i , b i > 0, a 2 i + b 2 i = 1. Similar to the analysis of Algorithm 3, we will show that if sin(θ i /2) ≤ σ i then with probability 1/3 it also holds that sin(θ i+1 /2) ≤ σ i+1 . If this is true then since 1/t > 1/ log(1/ϵ) after O(log log(1/ϵ)) rounds, we have sin(θ T /2) ≤ 1/t with probability at least 1/polylog(1/ϵ).Recall the notation in the proof of Lemma F.3. Given b, we define p( b, s) to be the bias of a halfspace with a threshold T b,s = (t -âs)/ b. By Fact 3.3, we define ℓ(z) = h * (Az -sw i ) = sign((a i σw i + b i u) • z + t * -a i s) the ground truth label of y(Az -sw i ), t s to be its threshold and p s to be the bias of ℓ(z).By Lemma F.3, we know that as long as b i > 1.5/t, with high probability Algorithm 4 will output "Yes" for some b such that with probability at least 1/2, p s > p( b, s)/2 > p 1/4 . On the other hand, by Equation (3), we know that with probability at least 5/6, η := Pr z∼N (0,I) (ℓ(z) ̸ = y(Az -sw i )) ≤ p(b, s)/C ′ for a sufficiently large constant C ′ . Thus, with a probability at least 1/3, p s > p( b, s)/2 and η ≤ p( b, s)/C ′ hold simultaneously. For now, we assume this happens and we will analyze the smoothed label around some z 0 such that y(Az 0 -sw i ) = -1. By Fact 3.10, the smoothed label Estimate the probability ps of p s = y(Az -sw i ) = -1 for z ∼ N (0, I) up to error p 1/4 /100 using Õ( 1/p) queries. Let ts be the threshold of a halfspace with bias psA ← I -(1 -σ 2 )w i w t i , σ = 1/t Draw z ∼ N (0, I) and query y(Az -sw i ) until some z 0 such that y(Az 0 -sw i ) = -1 is drawn Draw z i ∼ N (0, I), for i ∈ [m], m = Õ(d) and query f i (z i ) := y(A( √ 1 -ρz 0 +ρz i )-sw i ), where ρ = 1/ ts g i ← 1 m m i=1 proj w ⊥ i z i f i (z i ), w i+1 ← proj S d-1 (w i + µ i g i ) σ i+1 ← (1 -1/C 2 )σ i µ i+1 = (1 -1/C 1 )σ i+1 return w Taround z 0 with respect to halfspace ℓ(z) can be seen as a halfspaceℓ z0 (z i ) = sign(W i • z i + T ρ,s ), where W i := (a i σw i + b i u i )/ (a i σ) 2 + b 2 i and T ρ,s = ts+ √ 1-ρ 2 Wi•z0 ρBy Fact 3.10 and Lemma 3.11, we know that with probability at least 1/2, such a z 0 satisfies1. W i • z 0 ∈ (-t s -1/t s , -t s )2. the noise level of the smoothed label is at most 5η/p s ≤ 1/C ′′ for some large enough constant C ′′ Since p s > p( b, s)/2, we can bound the threshold T ρ,s byEQUATIONbecause ts is at least close to t s up to a small constant factor, otherwise ps would be far from p s . Combine Equation (4) and Fact 3.4, we know thatE z ′ ∼N (0,I) proj w ⊥ i z ′ ℓ z0 (z ′ ) = ϕ uibi √ (aiσ) 2 +b 2 i, for some ϕ ∈ (e -2 , 1). Since the noise level of the smoothed label around z 0 is as small as 1/C ′′ for some large enough constant C ′′ , by Hoeffding's inequality, we know that g i -E z ′ ∼N (0,I) proj w ⊥ i z ′ ℓ z0 (z ′ ) can be smaller than some tiny constant with high probability.As it always holds that σ i ≥ 1/t for each i, we will consider two cases. In the first case, sin(θ i /2) ≤ 3σ i /4 and ∥g i ∥ is bounded by some universal constant.In the second case, we have 3σ i /4 ≤ sin(θ i /2) ≤ σ i . In this case we know thatE z ′ ∼N (0,I) proj w ⊥ i z ′ ℓ z0 (z ′ ) = ϕ uibi √ (aiσ) 2 +b 2 i= ψu i for some ψ ≥ e -4 , which implies that Guidelines:E z ′ ∼N (0,I) proj w ⊥ i z ′ ℓ z0 (z ′ ) • u i ≥ ψ bi √ (aiσ) 2 =b 2 i ≥ e -5• The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper. • The authors are encouraged to create a 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 on a few datasets or with a 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, a facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or a speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to 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 fairness. • While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a 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 important role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.Question: For each theoretical result, does the paper provide the full set of assumptions and a complete (and correct) proof?• The assumptions made should be given (e.g., Normally distributed errors).• It should be clear whether the error bar is the standard deviation or the standard error of the mean. • It 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 a 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 of range (e.g. negative error rates). Guidelines:• The answer NA means that there is no societal impact of the work performed.• If the authors answer NA or No, they should explain why their work has no societal impact or 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.• The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is a 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 is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology. • If there are 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 to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML). 
safeguards: 
 Question: Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?Answer: [NA] Justification: This paper is theoretical.Guidelines:• The answer NA means that the paper poses no such risks.• Released models that have a 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 to 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 a best faith effort.12. Licenses 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 not use 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 a URL. • The name of the license (e.g., CC-BY 4.0) should be included for each asset.• For scraped data from a particular source (e.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, paperswithcode.com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of a 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.In this paper, we use O δ to hide the dependence on polylog(1/δ). 
 
 Appendix:  


Decision: 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.

Reviews: review: paper_summary: paper_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.

1. 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).
2. An upper bound in the membership query setting achieved by an efficient (poly-time) algorithm.

The achieved bounds depend on the bias $p$ (of the target halfspace $w^Tx+p\geq 0$), which make these results target/hypothesis dependent.

These 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.
strength_weakness: strength_weakness: While interesting, technically deep and novel, the results are somewhat limited, due to the quite strong standard normal assumption, see question below.

Comments:
* Maybe consider changing adding something like "under the Gaussian distribution" to the title. Otherwise it might seem a bit too general.


---rebuttal---
raised score from 5 to 6.
questions: 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: limitations: See question.
paper_summary: paper_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))$.
strength_weakness: strength_weakness: - 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?

- 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.
questions: questions: N/A
limitations: limitations: N/A
paper_summary: paper_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)$).
strength_weakness: strength_weakness: 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.
2. 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.
3. 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.
4. No discussion on possible future research.
5. The results are applicable to a relatively limited setting of halfspaces under the Gaussian distribution.
6.  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.
questions: questions: Questions:

1. 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?
3. In line 205, do you mean that an upper bound $\epsilon$ on the noise level is *given* to the learner beforehand?


Suggestions:
1.  I would recommend writing a "technical overview" section that separates the high-level novel ideas from known techniques and technical details.
2. 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?


Typos:
1. Line 337: "the length of the length of"
2. Line 389: "unfortinately:
limitations: limitations: Yes.
paper_summary: paper_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.
strength_weakness: strength_weakness: I think the results are very interesting but the paper writing can be improved.
questions: questions: How do you know whether to use initialization for an extremely large threshold(section F) or not (section E)?
I think it would make the paper easier to read if the authors could describe what 3.1 is doing at high level. 
I think there is a small notation error in A.2(sample (x,y)\sim D instead of N(0, I)).
limitations: limitations: N/A
paper_summary: paper_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.
strength_weakness: strength_weakness: 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?

2. 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.

3. 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.

     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.

     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. 

     iii) It might be better to have a conclusion section to discuss some future directions.

4. There're some very tiny typos.

   i) In the abstract, your lower bound is $\Omega(d/\log(m)\epsilon)$ while in your theorem it is $\Omega(d/\log(m)p)$.

   ii) In algorithm 1, what's the subroutine TEST C? In the appendix you have a subroutine named ANGLE TEST.

   iii) Line 337, you typed "the length of" twice.
questions: 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?

2. 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.

3. On the other hand, is it easy to extend your result to more general distributions? Like log-concave distributions?
limitations: limitations: It's better to have a conclusion section to talk about future directions.

Comments: comment: Thanks for the response. I will keep my score and support its acceptance.
Thanks for the comments. I raised my score.
Thank you for your explanation. I will keep my score as 7.
Thank you for your response, I adjusted my rating.
Thank you very much for addressing my comments and questions.
My main concern regarding this paper, as a very non-expert in active learning, was (and still is) it's inaccessible writing style.
I believe that the paper can highly benefit from adding a "technical overview" section, and from making another pass on it, while trying to read it from the eyes of a non-expert, and revise it accordingly. This is especially important if you "expect that there will be follow-up works".
However, since the authors commit to "revise the writing", I will update my final score.