Near-Optimal Bounds for Learning Gaussian Halfspaces with Random Classification Noise
Authors: Ilias Diakonikolas
Jelena Diakonikolas
Daniel Kane
Puqian Wang
Nikos Zarifis
Venue: NeurIPS 2023 poster (2023)
Keywords: PAC Learning
Random Classification Noise

Abstract: We study the problem of learning general (i.e., not necessarily homogeneous) 
halfspaces with Random Classification Noise under the Gaussian distribution. 
We establish nearly-matching algorithmic and Statistical Query (SQ) lower bound results 
revealing a surprising information-computation gap for this basic problem. 
Specifically, the sample complexity of this learning problem is 
$\widetilde{\Theta}(d/\epsilon)$, where $d$ is the dimension and $\epsilon$ is the excess error. 
Our positive result is a computationally efficient learning algorithm with sample complexity
$\tilde{O}(d/\epsilon + d/\max(p, \epsilon))^2)$, where $p$ quantifies the bias of the target halfspace. 
On the lower bound side, we show that any efficient SQ algorithm (or low-degree test)
for the problem requires sample complexity at least 
$\Omega(d^{1/2}/(\max(p, \epsilon))^2)$. 
Our lower bound suggests that this quadratic dependence on $1/\epsilon$ is inherent for efficient algorithms.

Near-Optimal Bounds for Learning Gaussian Halfspaces with Random Classification Noise
Maas Diakonikolas
Jelena Diakonikolas University of Wisconsin, Madison jelenaecs. wisc.edu
University of Wisconsin, Madison ilias@cs wisc.edu
Daniel M. Kane
Puqian Wang
University of California, San Diego dakane@ucsd.com edu
University of Wisconsin, Madison
pwang3330visc.ede
Nikos Zarifis
University of Wisconsin, Madison zarifis@visc.edi
Abstract
We study the problem of learning general (i.e., not necessarily homogeneous) halfspaces with Random Classification Noise under the Gaussian distribution. We establish nearly-matching algorithmic and Statistical Query (SQ) lower bound results revealing a surprising information-computttiin gap for this basic problem. Specifically, the sample complexity of this learning problem (d/cc, where d is the dimension and is the excess error. Our positive result is a computationally efficient learning algorithm with sample complexity Ödde d/ /max (p, ))) where quantifies the bias of the target halfspace. On the lower bound side, we show that any efficient SQ algorithm (or low-degree test) for the problem requires sample complexity at least [2d (max(p, ))) Our lower bound suggests that this quadratic dependence on 1/c / is inherent for efficient algorithms.
Introduction
A halfspace or Linear Threshold Function (LTF) is any Boolean function h Rd + {+1} of the form h(x) = sign (w x + t), where w E R is the weight vector and E IR is the threshold. The function sign IR + {+1} is defined as sign(u) 1 if > 0 and sign(u) = -1 otherwise. The problem of learning halfspaces is a classical problem in machine learning, going back to the Perceptron algorithm [Ros58] and has had big impact in both the theory and the practice of the field Vap98 FS97). Here we study the problem of PAC learning halfspaces in the distribution- specific setting the presence of Random Classification Noise (RCN) (AL88). Specifically, focus on the basic case in which the marginal distribution on examples is the standard Gaussian one of the simplest and most extensively studied distributional assumptions.
In the realizable PAC model class), the class of halfspaces on Rd is efficiently learnable to 0-1 eиror using Õ(d/c) samples via linear programming (even in the distribution-Fr free setting). This sample complexity upper bound is information-theorrtiiaall optimal, even if we know priori that the distribution examples is well-hehaved (e.g., Gaussian or uniform). That is, the realizable setting, there an efficient algorithm for halfspaces achieving the optimal sample complexity (within logarithmic factors).
Val84b (i.e., when the labels are consistent with a concept in the
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

Learning Gaussian Halfspaces with RCN. The RCN model [AL88] is the most basic model of random noise. In this model, the label of each example is independently flipped with probability exactly 1), for some noise parameter 0 < ?) < 1/2. One of the classical results on PAC learning with RCN [Kea98] states that any Statistical Query (SQ) algorithm can be transformed into an RCN noise-tolerant PAC learner with at most a polynomial complexity blowup. Halfspaces are known to be efficiently PAC learnable in the presence of RCN, even in the distribution- free setting [BFKV97 Coh97 DKT21 DTK22]. Alas, all these efficient algorithms require sample complexity that is suboptimal within polynomial factors in d and 1/e.
The sample complexity of PAC learning Gaussian halfspaces with RCN is ((d/(( - 22)))). This bound can be derived, e.g., from [MN06], and the lower bound essentially matches the realizable case, up to a necessary scaling of (1 2n) Given the fundamental nature of this learning problem, is natural to ask whether computationaly efficient algorithm with (near-) optimal sample complexity (i.e., within logarithmic factors of the optimal) exists. That is, we are interested in a fine- fine-graine grained sample size versus computational complexity analysis of the problem. This leads us the following question:
Is there sample near-optimal and polynomial time algorithm for learning Gaussian halfspaces with RCN?
In this paper, we explore the above question and provide two main contributions - essentially resolving the question within logarithmic factors. On the positive side, give efficient algorithm with sample complexity O,,d/c d/ (max(p, <} )) for the problem. Here the parameter p E [0, 1/2] (Definition 1.2) quantifies the bias of the target function; a "balanced" function has p = 1/2 and a constant function has p= O. The worst-case upper bound arises when p O(e), in which case our algorithm has sample complexity of (d/d/ee). Perhaps surprisingly, we provide formal evidence that the quadratic dependence on the quantity 1/ max(p. }} in the sample complexity cannot be improved for computationally efficient algorithms. Our lower bounds apply for two restricted yet powerful models of computation, namely Statistical Query algorithms and low- polynomial tests. Our lower bounds suggest an inherent statistical statistical-compusee compulatioommttinallcccc tradeoff for this problem.
1.1 Our Results
We study the complexity of learning halfspaces with RCN under the Gaussian distribution. Let
C C= Rd + [=1}] f(x) sign(w x + {)} be the class of general (i.e., not necessarily
homogeneous) halfspaces in Rd. The following definition summarizes our learning problem.
Definition 1.1 (Learning Gaussian Halfspaces with RCN). Let 'D be distribution on (x, y) Rd x {+1} whose x-marginal Dx is the standard Gaussian. Moreover, there exists 1) E (0, 1/2)
and a target f C such that the label y of example x satisfies y = f(x) with probability 1- - 17 and
y (x) otherwise. Given e > O and sample access to D, the goal
ouiput a hypothesis h that
with high probability satisfies e (h) == -Pr [x(x) F y) S 1 +6
Our main contribution is a sample near-optimal efficient algorithm for this problem coupled with a matching statistical statisticalcoompuatioonn computational tradeoff for SQ algorithms and low-degree polynomial tests. turns out that the sample complexity of our algorithm depends on the bias of the target halfspace, defined below.
Definition 1.2 (p-biased function). For p E [0, 1/2), we say that Boolean function f .R. + {+1} is p-biased with respect to the distribution Dx. if min { (Fxx = 1], Prx-D, [f(x) = -1]} p.
For example, homogeneous halfspace fxx sign(w xx) under the standard Gaussian distribution
Dx = _ satisfies (xx_D,[[()]] = 0, and therefore has bias 1/2. For general halfspace f(x) sign(w x + t) with |/w]|2 1, it is not difficult to see that its bias under the standard Gaussian is approximately p ex/()exp(-1²) /2) (see Fact B.1
We can now state our algorithmic contribution.
Theorem 1.3, (Main Algorithmic Result) There exists an algorithm that, given c, 8 E 1/2) and N samples from distribution D satisfying Definition I.I runs in time O(dN/2) and returns
Throughout this introduction, it will be convenient to view n) constant bounded away from 1/2.

---

hypothesis h E C such that with probability at least 1 - 8, it holds 1 S + c. The sample complexity of the algorithm is N = = d + max(p(]-2n).e) (1/6).
Some comments are in order. We note that the first term in the sample complexity matches the information thhoorrttetttttceeeeo lower bound (within a logarithmic factor), even for homogeneous halfspaces (p 1/2); see, c.g.. [MN66] HYT5). The second term scaling quadratically with 1/ max (11 2n)p, e} is not informatiiontheorettie
necessary and dominates the sample complexity when P = (v))). In the worst-case, i.e., when p O,((), our algorithm has sample complexity (d) Perhaps surprisingly, show in Theorem 1.5 that this quadratic dependence is required for any computationally efficient SQ algorithm; and, via BBH 20). for any low-degree polynomial test.
Basics SQ Model. SQ algorithms are a broad class of algorithms that, instead of having direct access to samples, are allowed to query expectations of bounded functions of the distribution.
Definition 1.4 (SQ algorithms)). Let D be a distribution on R A statistical query is a bounded function q: F [-1,1] 1]. For >> O, the VSTAT(u) oracle responds to the query q with value such that IV- Ex~Dlg(xx [x)())]l S T, where
max(1/ u,, v /Vary=Dll ())]/u). We call the tolerance of the statistical query. A Statistical Query algorithm is an algorithm whose objective is to learn some information about an unknown distribution D by making adaptive calls to the corresponding oracle.
The SQ model was introduced in [Ka988 as natural restriction of the PAC model [Va184a Subse- quently, the model has been extensively studied in a range of contexts, see, e.g., [el16]. The class of SQ algorithms is broad and captures a range of known supervised learning algorithms. More broadly, several known algorithmic techniques in machine learning are known to be implementable using SQs (see, c.g., [FGR* 17 FGVI7)).
We can now state our SQ lower bound result.
Theorem 1.5 (SQ Lower Bound). Fix any constant c (0, and let d be sufficiently large. For any p ), any SQ algorithm that learns the class of p-biased halfspaces on Rd with Gaussian marginals in the presence of RCN with 17- = 1/3 to error less than + p/3 either requires queries of accuracy better than (2pd/2-1/A) i.e., queries to (ST /2-p)//)p) or needs make at least 20(4)) statistical queries.
Informally speaking, Theorem 1.5 shows that no SQ algorithm can learn p- biased halfspaces in the presence of RCN (with 77 1/3) to accuracy 17 + Occ) (considering p > e/2) with a sub-ex cub-exponential in ((()) many queries, unless using queries of small tolerance - that would require at least D /d/p") samples to simulate. This result can be viewed as near-optimal the problem, within the class of SQ algorithms. When p = 2e, the computational sample complexity lower bound we obtain is 22 ((vd/e²) That is, for sufficiently small e, the computational sample complexity of the problem (in the SQ model) is polynomially higher than its cntrmattion-thhorete sample complexity.
tradeoff for
Via 20), we obtain qualitatively similar lower bound in the low-degree polynomial testing model; see Appendix [
1.2 Our Techniques
Upper Bound. At high level, our main algorithm consists of three main subroutines. We start with simple Initialization (warm-start) subroutine which ensures that we can choose a weight vector wo with sufficiently small angle the target vector w This subroutine essentially amounts to estimating the degree-one Chow parameters of the target function and incurs sample complexity (tdd/max(p((1 2n)). )) We emphasize that our procedure does not require knowing the bias p of the target halfspace; instead, it estimates this parameter to a constant factor.
Our next (and main) subroutine is an optimization procedure that is run for Ō(1/²) different guesses of the threshold I. At high level, our optimization subroutine can be seen as a variant of Riemannian (sub)gradient descent on the unit sphere, applied to the empirical LeakyRel.U loss - defined as BeakyReLU,Ce (1 Ajul(u 2 0} + Aul 0} with parameter À set to 77, = w x,
3

---

and with samples restricted to a band, namely < |W X < <b-win with and b chosen as functions of the guess for the threshold t. The band restriction key in avoiding R(d/=²) dependence in the sample complexity; instead, we only require order- samples to be drawn for the empirical LeakyReI.U loss subgradient estimate. Using the band, the objective is restricted to a region where the current hypothesis incorrectly classifies a constant fraction of the mass from which we can perform "denoising" with constantly many samples.
For a sufficiently accurate estimate of t (which is satisfied by at least one of the guesses for which our optimization procedure is run), we argue that there is a sufficiently negative correlation between the empirical subgradient and the target weight vector w This result, combined with our initialization, enables us to inductively argue that the distance between the weight vector constructed by the optimization procedure and the target vector w' contracts and becomes smaller than e within order-log(1/e iterations. This result is quite surprising, since the LeakyReLU loss is nonsmooth (it is, in fact, piecewise linear) and we do not explicitly bound its growth outside the set of its minima (i.e., we do not prove local error bound, which would typically be used to prove linear convergence). Thus, the result we establish is impossible nonsmooth optimization. Additionally, we never explicitly use the LeakyReL.U loss function or prove that it minimized by w"; instead, we directly prove that the vectors w constructed by our procedure converge to the target vector w". At technical level, our result is enabled by novel inductive argument, which we believe may be of independent interest (see Lemma 2.8 for more details).
obtain using black-box results for
Since each run of our optimization subroutine returns a different hypothesis, at least one of which is accurate (the one using the "correct" guess of the threshold E), we need an efficient way select hypothesis with the desired error guarantee. This is achieved via our third subroutine - a simple hypothesis testing procedure, which draws fresh sample and selects a hypothesis with the lowest test error. By standard results (MN06), such a hypothesis satisfies our target error guarantee.
SQ Lower Bound. To prove our SQ lower bound, it suffices to establish the existence of large set of distributions whose pairwise correlations are small [FGR+ Inspired by the methodology of [KS177, we achieve this by selecting our distributions on labeled examples (x, y) to be random rotations of a single one-dimensional distribution that nearly matches low-order Gaussian moments, and embedding this in a hidden random direction. Our hard distributions are as follows: We define t), where v is randomly chosen unit vector and the threshold t is chosen such that Pfx = 1] = p. We then let y = fv(x) with probability 2/3, and (x) otherwise. By picking a packing of nearly orthogonal vectors on the unit sphere (i.c., set of vectors with pairwise small inner product), we show that each pair of these fv 's corresponding to distinct vectors in the packing have very small pairwise correlations (with respect to the distribution where x is a standard Gaussian and y is independent of x). While the results of (DKS17) cannot be directly applied to give desired corerlation bounds, the Hermite analytic ideas behind them useful in this context. In particular, the correlation between two such distributions can be computed in terms of their angle and the Hermite spectrum. A careful analysis (Lemma 3.3) gives an inner product that is O(cos(( ( p), where is the angle between the corresponding vectors. Combined with our packing bound, this is sufficient to obtain our final SQ lower bound result.
the halfspaces fv (x) sign(v
1.3 Related and Prior Work
A long line of work in theoretical machine learning has focused on developing computationally efficient algorithms for learning halfspaces under natural distributional assumptions in the presence of RCN and related semi-random noise models; see, e.g., [ABHU15] ABHZ16 YZ17 ZLC17 DKTZ20 [KT2200 DDK [DKK 21, tokK+22 Interestingly, the majority of these works focused on the special case of homogeneous halfspaces. We next describe in detail the most relevant prior work.
Prior work (YZ17 ZSA20 ZL21 gave sample near-optimal and computationally efficient learners for homogeneous halfspaces with RCN (and, more generally, bounded noise). Specifically, these works developed algorithms using near-optimal sample complexity of Ö,, (d/d/)). However, their algorithms and analyses are customized to the homogeneous case, and is not clear how to extend them for general halfspaces. In fact, since all of these algorithms are easily implementable in the SQ model, our SQ lower bound (Theorem L.5) implies that these prior algorithms cannot be adapted to handle the general case without an increase in sample complexity. Finally, [DKT222] gave an
algorithm with sample complexity (d/e²) to learn general Gaussian halfspaces with adversarial

---

label noise to enror O(OPT) + e, where OPT is the optimal misclassification error. Unfortunately. this algorithm does not suffice for our RCN setting (where OPT 17). since its error guarantee is significantly weaker than ours.
Very recent work [DK 1 gave SQ lower bound for y-margin halfspaces with RCN, which has some similarities to ours. Specifically, DDKK223 showed that any efficient SQ algorithm for that problem requires sample complexity ((1/(7))2 ((2)). Intuitively, the margin assumption allows for much more general family of distributions compared to Gaussian assumption here. In particular, the SQ construction of that work does not have any implications in our setting. Even though the Gaussian distribution does not have margin, it is easy see that it satisfies approximate margin property for y 1/vd. In fact, using an adaptation of our construction, believe can quantitatively strengthen the lower bound of [DDK*23] to 2(1/(77))) For more details, see Appendix A
1.4 Preliminaries
For n E L.. we define [n] = [l,....,....... We use lowercase bold characters for vectors and uppercase bold characters for matrices. For I2 and [d], x; denotes the i-th coordinate of x, and ||x |2 = x denotes the fo-m of x. We use x y for the inner product of x,y E Rdd and y) for the angle between x and y. We slightly abuse notation and denote by e, the 1th standard basis vector in Rd. We further use 14 to denote the characteristic function of the set i.e., (x) x E A and (x) 0 if & A. We use the standard O(-), (.),, (((-) asymptotic notation. We also use Ö-) to omit poly logaritoaai factors in the argument. We use E xr] for the expectation of the random variable æ according to the distribution D and Pr[e] for the probability of event E. For simplicity of notation, we omit the distribution when it is clear from the context. For (x, y) distributed according to D, we denote by Dx the distribution of x. As is standard, we use N to denote the standard normal distribution in d dimensions; i.e., with its mean being the zero vector and its covariance being the identity matrix.
Efficiently Learning Gaussian Halfspaces
In this section, we prove Theorem I.3 by analyzing Algorithm[[ [ As discussed the introduction and shown in Algorithm I there are three main procedures in our algorithm. The guarantees of our Initialization (warm start) procedure, which ensures sufficient correlation between the initial weight vector Wo and the target vector w", stated in Section 2.1 while the proofs and pseudocode are in Appendix B.I Our main results for this section, including the Optimization procedure and associated analysis, are in Section 2.2] The Testing procedure is standard and deferred to Appendix B.2 together with most of the technical details from this section.
Throughout this section, we assume that the parameter 7) (RCN parameter) is known. As will become clear from our analysis, a constant factor approximation to the value of 21 sufficient to obtain results. For completeness, show how to obtain such approximation in Appendix BB. For simplicity, we present the results for t 2 and < /2log(( 2n)/e). This is without loss of
Algorithm Main Algorithm
1: Input: 8, 77, e, sample access to distribution D
2: [Wo. = Initialization(6. n, c): c' = c/(1 27)
3: to = /2log(1/p), M = 8 (20og(4/p)) (10g(11p)) ++1
(c')²
4: Draw N₂ = ( dggg(1 (1/8) (1/) log(1/e2)
samples ((x(t), .y N from D
(1-2m))²
5: for m 1 M do
6: t. to + (m 1) 8 7m & eexp(t?n//
(e))
7: Wm = Optimization( Wo, bm; 7m, n. {(x(i) (6) |
8: end for
9: [Wout tou]] = Testing( (1.gg(((1.11)).... (W2, (W2, (WM,
10: return Wouts fout
5

---

Algorithm 2 Optimization
1: Input: Wo, i, Y. 7,, N2 i.i.d. samples (x(*), (0) from D
2: No0
(1-4p)/2x
16[1 1611--n) p 4- 0.00098; P(i, 4)
3: for == 0
K do
4: Let E(wk, 2) = fx - We x -
5: Let g( [w:: (1) y (0) 2(11 2n)sign( We x(1) +1) - y p(o))proww, (x(())
((wA) + N₂ Li=i g(w x+) (() 1 1/
N2
6:
p(t.5)
7: lik < 1k- (1
8: Wk+1 - |w -w -4
W
9: end for
return WK+1
generality. For the former, it is by the simple symmetry of the standard normal distribution that the entire argument translates into the case < O, possibly by exchanging the meaning of '+1' and '-1' labels. For the latter, we note that when the bias is small, i.e., for p S c/(2(1 2n)), constant hypothesis suffices.
2.1 Initialization Procedure
We begin this section with Lemma 2.1 which shows that given Ni = (1 (1f(((1)))))) log(1 (1))) i...d. samples from D, we can construct good initial point wo that forms an angle most x with the target weight vector w For our purposes, should be of the order 1/t. For S / log(//e)) where é' = c/(1 2nj), we can ensure that N₁ = (d/(y²(1 - 2n)²) (o)( The downside of the lemma, however, is that the number of samples N1 requires least approximate knowledge of the bias parameter p (or, more accurately, of e /²2) We address this challenge by arguing (in Lemma 2.2) that we can estimate p using the procedure described in Algorithm 4 without increasing the total number of drawn samples by factor larger than order-log(1/e))
Lemma 2.1 (Initialization via Chow Parameters). Given K. > O, define Pt = -E-112 NN Old/(k p, - 2) log(1/6)) and let ( E [Na] be i.i.d. samples drawn from D. Let u= ΣN (1) (6) and wo u/ m//|uu|/2 Then, with probability 1 we have ((wo, w*) S K.
We now leverage Lemma 2. to argue about the correctness of implementable Initialization procedure, stated as Algorithm in Appendix [.I] where the proofs for this subsection can be found.
Lemma 2.2. Consider the Initialization procedure described by Algorithm 4 in Appendix B. IfO S
t & / log((1 - -21)/c), then with probability at least - 6, cxp(-t² S p < 4 4xxp(
22) The
algorithm draws total of Ō max 2n)p. ef2)) samples and ensures that 0 w*) I min 50 3)
dlog(1/8)
2.2 Optimization
As discussed before, our Optimization procedure (Algorithm 2 can be seen as Riemannian subgradi- ent descent on the unit sphere. Crucial to our analysis is the use of subgradient estimates from Line and Line 6 where we condition on the event that the samples come from thin band, defined in Line 4 Without this conditioning, the algorithm would correspond to projected subgradient descent of the LeakyReLU loss on the unit sphere. The conditioning effectively changes the landscape of the loss function being optimized, which cannot be argued anymore to even be convex, as the definition of the band depends on the weight vector at which the vector g( (w) is evaluated. Nevertheless, as we argue in this section, the optimization procedure can carried out very efficiently, even exhibit- ing linear convergence rate. To simplify the notation, in this section denote the conditioned distribution Dle(w.) 8) by D(w, f). We carry out the analysis assuming the estimate is within additive ? of the true threshold value I; as argued before, this has to be true for at least one estimate i for which the Optimization procedure is invoked.

---

In the following lemma, we show that if the angle between a weight vector w and the target vector w" is from a certain range, we can guarantee that g(w) is sufficiently negatively correlated with w'. This condition is then used to argue about progress of our algorithm. The upper bound on A will hold initially, by our initialization procedure, and we will inductively argue that it holds for all iterations. The lower bound, when violated, will imply that the distance between w and w" is small, in which case we would have converged to a sufficiently good solution
w.
Lemma 2.3. Fix any e' E (0,1). Suppose that 0 S t S V2log(1/e) and w E Re is such that |[w l2 = L, and 0 = 0(w, w") satisfies the inequality é' exp(t2 (2) S 0 S 1/tt). Iflt - t c²2/8
and 7 = (1/2)c' exp(f2 (2), then E ((x.)))D(w, F) [g( w: y) w'] S - 2n) sin 8/ (2
Since, by construction, g(w) ) is orthogonal to w (see Line 3 in Algorithm 2). we can bound the norm of the expected gradient vector by bounding g( (w) u for some unit vectors u that are orthogonal to using similar techniques as in Lemma 2.3 To be specific, we have the following lemma.
Lemma 2.4. Under the assumptions of Lemma 2.3
E (xx.g))D(w. [g(w; w|][| S (1-2g)
V2F
The last technical ingredient that we need is the following lemma which shows a uniform bound on the difference between the empirical gradient g(w) and its expectation (for more details, see Lemma B.6 and Corollary B.8 in Appendix B
Lemma 2.5. Consider the learning problem from Definition 1.1 Let f be parameters satisfying
the conditions of Lemma 2.3 Let ō E (0, 1). Then using O (o/()/)()//)))/ ((1 - 2c)) samples
to construct g. for any unit vector w such that é' exp(t? /2) S ((w, w ) S 15t)), it holds with
probability at least - 8: ([(w)) ((x.)))D(w.))lB (gw)))lll(]]]ll.. S (1/4) E (x.)) .) h/gg())]le
We are now ready to present and prove our main algorithm-related result. A short roadmap for our proof is as follows. Since Algorithm [ constructs a grid with grid width c²²/8 /8 that covers all possible values of the true threshold t, there exists least one guess f that is el--elose to the true threshold We first show that to get halfspace with error at most e', it suffices to use this as the threshold and find a weight vector w such that the angle ((w, w") is of the order é'. which is exactly what Algorithm
2 does. The connection between 0 ((w, w*) and the error is conveyed by the inequality Pr[sign( w x + t) A sign( w- X + t)] < (0(w, )//T)) exp(-t²/22) be the parameter generated by Algorithm at iteration & for threshold i. We show that 0 (wxx w*) converges to zero
see Appendix B Let W
linear rate. To this end, we prove that under our carefully devised step size M4.. there exists an upper bound on || - -w'll. which contracts at each iteration. Note that since both We and w are on the unit sphere, we have ||W: w w = 2 sin sin (O(w,, w*) w2). Essentially, this implies that Algorithm produces a sequence of parameters wa such that ((Wk, w") converges to 0 linearly, under this threshold f. Thus, we can conclude that there exists halfspace among all halfspaces generated by Algorithm [ that achieves e' error with high probability.
Theorem 2.6. Consider the learning problem from Definition 1.1 Fix any unit vector Wu Rd such that 8(Wo. w") S min(1/(5t), T/2). Fix any e, > 0. Let > O be a threshold such that If - t S 2² /(8(1 - 2n) and let 9 = e/(2(1 - 2n)) exp((2/2)) Then Algorithm 2 uses N₂ = Ōdd(((1 - 2n)c) log samples from D, has runtime ((Ndd), and outputs weight vector such that h(x)- sign(w- x x+ t) satisfies Pr(h(x) # vl S 17 + with probability at least 1 8.
Proof. Let = (c/1 27), and denote by Wi the vector produced by the algorithm at ttth iteration for threshold f. For any unit vector and f8 - t| < e²2 /8, it holds Pr Prisign(w- x ++ ل sign(w" + t)] = <22/(4V2T 2 + o(w, w exp( -t? /2) (see Appendix B.2 for more details). Therefore, suffices to find a parameter w such that 8(w, w*) I .e'' exp(==/2). Note that since both w and w² are unit vectors, we have ||w- -wwlll2
2 (0/)) indicating that it suffices to minimize |ww- ww--llle efficiently. As proved in Section 2.1 we can start with an initial vector wo such that 0 O(wo, w*) < 1/(5t) by calling Algorithm 4 (in Appendix B. Denote 0z O(wa, w*) and consider the case when 02 2 e' eeexp(tt/22)
We establish the following claim:
-21)2 samples from distribution D, we have that if 02 2 e' eexp(12/2) /2) then with probubility at least 1 8: |[ w" w- w 112 (C1/2))u, sin 02 + 4CPHE.
Claim 2.7. Let C1 = (1 2n1) 201/v2m. 2m. Drawing =2= O(dlog((
7

---

It remains to choose the step size ak properly to get linear convergence. By carefully designing a shrinking step size, we are able to construct an upper bound Φ₁ on the distance of [| W using Claim 2.7 Importantly, by exploiting the property that both w and w" are on the unit sphere, we show that the upper bound is contracting at each step, even though the distance || wx could be increasing. Concretely, we have the following lemma.
Lemma 2.8. Let p = 0.00098 and Φu = (1 - p)* Then, setting p = (1 - sin (in00/22) S for k 1,... K.
it holds
Proof. Let O& (1- p) where p = 0.00098. This choice of p ensures that 32p² + 1020p-11-000 O. We show by induction that choosing a = (1 - 40) (1601) = (1- -p) - 4p)/
holds sin(0x/2) S &o.. The condition certainly holds for k = 1 since 0, E [0, 1/2.. Now suppose that sin(0 (Ox//02 2) S db for some A: 2 1. We discuss the following 2 cases: OR 2 (in( 2 foh
and sin (2) S _ First, suppose OE 2 sin(O 2 1 Since sin(0./2) S sin 0g. it also
holds sin 0g 2 i To.. Bringing in the fact that ||wa+1 1|2 2 2in O+++++++ + /1/ and || w
3
2 sin as well as the definition of jug. the conclusion of Claim 2.7 becomes:
(2 (in(0xx+1/2)) - (2 (2/2))² - (C1/2) sin 02 + 40 4p)
I _ 3/ 8 + C1 4p) 0 = 4 (1+ 4p)--4/)111)
4p)/512),
where in the second inequality we used sin 0x 2 3/2 の and in the last equality we used the definition of pi by which μi = (1 - 4p) (16C1). Since p is chosen so that 32p² + 1020p- - S O we have:
sin(0x+1/2) - dx / 1 - (1 -1))115) & (1 - -)) = (1 - p)
as desired. Next, consider sin( (z. 22) < (3/4)Ø4- Recall that Wk+1 = projs (w μ Wl:) and Wa E B, where E is the unit bal
P therefore. || W S |W g
Wi 2
aklli((w ((()))] la by the non-expansiveness of the projection operator. Furthermore, applying Lemma 2.5
and Lemma 2.4, it holds that ([ S (5/4)]| E ()).)) (yw..))/ll//l (2(w)]]22 < 2(1 - 2n)) V2T, i.e.,
we have | wx lla S 201; therefore, || wxll2 S 2,, which indicates that:
2(sin (0x+11 /2) - sin (0x/2)) = || - w wo || - 112 S [| - wxll2 S 21.
Since we have assumed 2in( S (3/4)²x, then it holds:
Φx+1 sin(0++1))))) 2 (1 p) Φ + d2 sin(On 22) (1 4p)0x/16 16 2 3(1 4p) 0, since we have chosen μı = (1 - 4p) hv (16C1). Hence, it also holds that sin(0x+1/ S Φx+1- 0
Lemma 2.8 shows that (in(0x/2) converges to 0 linearly. Therefore, using N₂ = ((doog(1/)) (1)))/(())))(111-))))))))))))()) 2n)2 samples, after K = (((1pp)) p) log lex(L/(exp(( /2)²)) Oloog iterations, we get a W such that 0K S (0n((x/2)) < e' exp(1= /2). Let h(x) == sign(w, (wK x x+1 i). Then holds that
the disagreement of h(x) and f(x) is bounded by Pr[h(x) + f(x) < é' (see Appendix B for
more details). Finally, since err (h) Pr(x.))-Dlh(xx (x(x) 7 y] = 17 + (1 2n) Prx-D, [h(x) *
sign(w" x x t)], for any h :Rd + [=1]. to get misclassification error at most + (with respect to Therefore, we get Prix,))> [sign x +1 # w] S t
the y), it suffices to use e -2))<)) samples. Since the algorithm runs for (loo((1/c) iterations, the overall runtime is ((Nd)). This completes the proof of Theorem 2.6
using N₂ log(1 /5)/((1 (0g1)))(1(( -
Proof Sketch of Theorem 1.3 From Lemma 2.2 get that with ((dd((112n)) samples our Ini-
tialization procedure (Algorithm 4) produces a unit vector wo so that 0(wo, w*) ) < min((1(5t)) a/2)
with high probability. We construct a grid of (e² /S(( 2n)) )-separate values, containing all the possible values of the threshold t of size roughly ~ 1/c². We run Algorithm 2 for each possible choice of the threshold t. Conditioned on the choice of and wo that satisfies the assumptions of Theorem 2.6, Algorithm Saorithm@outpee outputs a weight vector so that Pr(x.) (sign( (w- x-x++x f) + u) S 4 c.
Using standard concentration facts, we have that with a sample size of order ((d/((1 - 2n)c)) from D. we can output the hypothesis with the minimum empirical error with high probability.
O
"This is true because g(wa, (x) ) is orthogonal to Wx. and thus |[ g > 1. meaning that projections onto the unit ball and the unit sphere are the same in this case.
8

---

3 SQ Lower Bound for Learning Gaussian Halfspaces with RCN
To state our SQ lower bound theorem, we require the following standard definition.
Definition 3.1 (Decision/Testing Problem over Distributions). Let D be a distribution and D be family of distributions over R.d. We denote by B(2, D) the decision (or hypothesis testing) problem in which the imput distribution D' is promised satisfy either (a) D' D or (b) D' E 2, and the goal of the algorithm is to distinguish between these two cases.
Theorem 3.2 (SQ Lower Bound for Testing RCN Halfssacces). Fix E (0, (021 and let E N be sufficiently large. For any p 2 2-200 2-0(4", any SQ algorithm that learns the class of (at most) p-biased Gaussian halfspuces on I6 in the presence of RCN with n 1/3 to error less than v + p/3 either or needs to make least 20((") statistical queries.
requires queries (STAT(O(d)/2-
We note that our SQ lower bound applies to natural testing version of our learning problem. By standard reduction (see Lemma [.9). it follows that any learning algorithm for the problem requires either 20(d") many queries or at least one query to (STAT((Od 1--111///)))))))))))))))))) We also note that the established bound is tight for the corresponding testing problem (see Appendix (..).
Proof of Theorem 3.2 For any unit vector v E Rd, we define the LTF fx( = sign(v x - t), where t and denote p (rx~~vff(xx) = 1]. Let Dy be the distribution on (x, y) with respect to I with the random variable y supported on {+1]} } as follows: Pr(y = [x() x] = 1 - and x distributed as standard normal. Denote by Av the distribution Dv conditioned on y and by B
the distribution Dy conditioned on = -1 It is easy to see that
Ax(x) = (1))(11 + (1 27) [[)(())))))))))))))))))))))))))) 01)((1 + - 211)p)
and
(x(x) = -( - (1 > 0))/(1 -1 (17-(1-7) (1-22)))
17
Fix unit vectors V, u E IRd and let 0 be the angle between them. We hound from above the correlation between fx(x) and fu (x). Our main technical lemma is the following:
Lemma 3.3. Let (x) and fu(x) defined as above. Then it holds
E [[((())(((xx x
E x-N -EIlf(()) E x-N [f,x(()]] s 4 cot(O) exp(-t²) exp (I cos(
Proof of Lemma 3.3 We start by calculating the Hermite coefficients of the univariate function
sign( 2 t). We will use the fact that [s-.//iign( H)) 2: 2i, exp( /2) (see Claim C.7. Let c; be the Hermite cocfficient of degree i. Without loss of generality (due to the rotational invariance of the Gaussian distribution). we can assume that v = ej and u = cos fe sin 6eg. Using standard algebraic manipulations and orthogonality arguments (see Claim C.5 for more details), we have that
E (Vv(()
E
[sign(x) (csign(cos 0x1 + sin 0x2 - 1)] Σ cos' 0 220
X-N
X1 Xx
Note that Hxo(x) = therefore co (x)) Therefore, we have that
E x~ (x E cos' 0c2 + E. x~> [x(((( E [f)(
x~x
Let J ExZ1 cos' Oc7. To complete the proof, it remains bound the |J]. We show the following:
Claim 3.4. It holds that [J| S 4| co) exp(-()) exp (Os)()))
Proof of Claim 3.4 Note that from Claim C.7
we have that 2HH; (t) exp(-t//2) Vi, hence,
it holds that J = cos(()) exp( -2) Σ
0c
He? (1) tos 0. We use the following fact.
1=
Fact 3.5 (Mehler Formula, see, e.g.
Foa788)
For lpl and x, y 1R, it holds that
1
exp (
2 2 (x 3) vi
p *Hex (x) (x) exp ( 21 x (x² +22))
120
9

---

Applying Fact 3.5 for p cos(f) and t, we get that
|J] cos 0 exp( (-t²) Σ HHH (t) cos' 0 f 4| cos exp(-t²)
Σ
Hef (t) cos 0
120
cos(()) 112
4/ cot 0f exp( exp
(1 cosc0
This completes the proof of Claim 3.4
Using Claim 3.4 we get that
E X
(x(x)(((() - (x)(()) x
E [f((()]]]] S 4/)((()) exp(((2) (1 (los(
completing the proof of Lemma 3.3
We associate each v and u to a distribution Dv and Du. constructed as above. The following lemma
provides explicit bounds the correlation between the distributions Dv and D,. Recall that the pairwise correlation of two distributions with edfs D1. D2 with respect to a distribution with edf
D) is defined X (D1, D2) + Sagx D P1(x) D2(x)) (x)) (see Definition C. We have the following lemma (see Appendix C.4 for its proof):
Lemma 3.6. Let Do be a product distribution distributed as N {=1}. where Pr Do by 1]
Pr(xg) D. [y 1] p. We have XD. Du) 2(1122)) 2m) E[f (x) (x) (x) (xfu(x)))
and X (Dv; Do) S 2n) (E( Exfx(x))²).
For any e E (0.1/2), there exists set S of 20(d") unit vectors in Rd such that for any pair v # u E S satisfies IV ul < 1/2/2e (Fact C.4). We associate each
E S with fo and a distribution Dy and denote = {Dv, v E S). By the def- inition of S and Lemma 3.3 for any v.u E S, we have that (x 4d-1/2+e exp(-t)) exp (t//d (t/))/=0/2)2)) + (x Ex-xxfu(x)]] Since t/d//4-0/2 Ex-w(fv(x) Ex Exx)V[u
S
1/2 by assumption, we get that Ex (x d-1/2-c exp(((x) By Lemma 3.6 follows that XD, (Dv, Dw.) < C(1 - 2n) exp((t))d 11224 and (Dv, Do) I C(1 2x))exp(( (=t/(_(/22) where C > is absolute constant. From standard SQ machinery (see, e.g., Lemma C.3) we have that any SQ algorithm that solves the decision problem
B(D, Do), requires either 20(a") queries, or at least one query to VSTAT (exp(t)) (t)))//2+)) Noting
that p = ((exp(-12/2)// (by Fact B.1 completes the proof of Theorem 3.2
4 Acknowledgements
ID was supported by NSF Medium Award CCF-2107079, NSF Award CCF-1652B8 (CAREER). and a DARPA Learning with Less Labels (LwLL) grant. JD was supported by NSF Award CCF- 2007757 and by the U. S. Office of Naval Research under award number N00014-22-1-253 was supported by NSF Medium Award CCF-2107547 and NSF Award CCF-1553288 (CAREER). PW was supported in part by NSF Award CCF-2007757. NZ was supported in part by NSF award 2023239, NSF Medium Award CCF-2107079, and a DARPA Learning with Less Labels (LwLL) grant.
DK
10

---

References
[ABHU15] P. Awasthi, M. Balcan, Haghtalab, and R. Urner. Efficient learning of linear separators under bounded noise. In Proceedings of The 28th Conference on Learning Theory, COLT 2015, pages 167-190, 2015.
[ABHZ16] Awasthi, M. F. Balcan, N. Haghtalab, and H. Zhang. Learning and 1-bit compressed sensing under asymmetric noise. In Proceedings of the 29th Conference on Learning Theory, COLT 2016, pages 152-192, 2016.
[AL88] D. Angluin and P. Laird. Learning from noisy examples. Machine Learning, 2(4):343- 370, 1988.
20] M. Brennan, G. Bresler, S. Hopkins, J. Li, and T. Schramm. Statistical query algorithms and low-degree tests are almost equivalent. arXiv preprint (tt:::2009006//0. 2020.
[BFKV97] A. Blum, A. Frieze, R. Kannan, and S. Vempala. A polynomial time algorithm for learning noisy linear threshold functions. Algorithmica, 22 22(1/2):35-52, 1997.
[Coh97] E. Cohen. Learning noisy perceptrons by a perceptron in polynomial time. In Pro- ceedings of the Thirty-Eighth Symposium on Foundations of Computer Science, pages 514-521, 1997.
[DDK*23] I. Diakonikolas, J. Diakonikolas, D. M. Kane, P. Wang, and N. Zarifis. Information- computation tradeoff's for learning margin halfspacce with random classification noise. CoRR, abs/2306. 11122306..662,, 2023. Conference version in C3LT'23.
[DKK+200 I.
Diakonikolas, D. M. Kane, V. Kontonis, C. Tzamos, and N. Zarifis. A polynomial time algorithm for learning halfisacces with Tsybakov noise. arXiv, 2020.
[DKK+21] Diakonikolas, D. M. Kane, V. Kontonis, C. Tzamos, and N. Zarifis. Efficiently learning halfspaces with Tsybakov noise. STOC, 2021.
22] Diakonikolas, D. M. Kane, V. Kontonis, C. Tzamos, and N. Zarifis. Learning general halfspaces with general massart noise under the gaussian distribution. In STOC '22: 54th Annual ACM SIGACT Symposium on Theory of Computing, Rome, Italy, June 20 24, 2022, pages 874-885. ACM, 2022.
[DKS17] Diakonikolas, D. M. Kane, and A. Stewart. Statistical query lower bounds for robust estimation of high-dimensional gaussians and gaussian mixtures. In 2017 IEEE 58th Annual Symposium Foundations of Computer Science (FOCS), pages 73 84, 2017.
[DKS18] Diakonikolas, D. M. Kane, and A. Stewart. Learning geometric concepts with nasty noise. In Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2018, pages 1061-1073, 2018.
[DKT21] I. Diakonikolas, D. Kane, and C. Tzamos. Forster decomposition and learning halfs- paces with noise. In Advances in Neural Information Processing Systems 34: Annual Conference Neural Information Processing Systems 2021, NeurIPS 2021, pages 7732-7744, 2021.
[DKTZ20a] Diakonikolas, V. Kontonis, C. Tzamos, and N. Zarifis. Learning halfspaces with massart noise under structured distributions. In Conference on Learning Theory, COLT, 2020.
[DKTZ20b] Diakonikolas, V. Kontonis, C. Tzamos, and N. Zarifis. Learning halfspaces with Tsybakov noise. arXiv, 2020.
[DKT722] I. Diakonikolas, V. Kontonis, C. Tzamos, and N. Zarifis. Learning General Halfspaces with Adversarial Label Noise via Online Gradient Descent. In Proceedings of the 39th International Conference Machine Learning, 2022.
[DTK22] I. Diakonikolas, C. Tzamos, and D. M. Kane. A strongly polynomial algorithm for approximate forster transforms and its application to halfspace learning. CORR, abs/2212.03008. 2022. To appear in STOC'23.

---

[Fel16] V. Feldman. Statistical query learning. In Encyclopedia of Algorithms, pages 2090-2099
2016.
[FGR 17] V. Feldman, E. Grigoreseu, L. Reyzin, S. Vempala, and Y. Xiao. Statistical algorithms and lower bound for detecting planted cliques. J. ACM, 64(2):8118:377 2017.
[FGV17] V. Feldman, C. Guzman, and S. S. Vempala. Statistical query algorithms for mean vector estimation and stochastic convex optimization. In Philip N. Klein, editor, Proceedings of the -iihty-Eighth Anmual ACM-SIAM Symposium Discrete Algorithms, SODA 2017, pages 1265-1277. SIAM, 2017.
[oa778] D. Foata. A combinatorial proof of the mehler formula. Journal of Combinatorial Theory, Series A, 1978.
[FS97] Y. Freund and R. Schapire. decision-theoretic generalization of on-line learning and an application to boosting. Journal of Computer and System Sciences, 55(1):119-139, 1997.
[God55] H. Godwin. On generalizations of tchebychef's inequality. Journal of the American Statistical Association, 50(271):923-96) 1955.
[HY15] S. Hanneke and L. Yang. Minimax analysis of active learning. J. Mach. Learn. Res., 16:3487-3602, 2015.
[Kea98] M. J. Kearns. Efficient noise-tolerant learning from statistical queries. Journal of the ACM, 45(6):983-1006, 1998.
[MN06] Massart and Nedelec. Risk bounds for statistical learning. Ann. Statist., 34(5):2326 2366, 10 2006.
[Ros58] F. Rosenblatt. The Perceptron: probabilistic model for information storage and organization the brain. Psychological Review, 65:386-407, 1958.
[Val84a] L. Valiant. A theory of the learnable. Communications of the ACM, 27(11)1134-1142,
1984.
[Val84b] L. G. Valiant. A theory of the learnable. In Proc. 16th Annual ACM Symposium on Theory of Computing (STOC), pages 436-445 ACM Press, 1984.
[Vap98] V. Vapnik. Statistical Learning Theory. Wiley-Interscience, New York, 1998.
[YZ17] S. Yan and C. Zhang. Revisiting perceptron: Efficient and label-optimal learning of halfspaces. In Advances in Neural Information Processing Systems 30: Annual Conference Neural Information Processing Systems 2017, pages 1056-1066, 2017.
[ZL21] C. Zhang and Y. Li. Improved algorithms for efficient active learning halfspaces with massart and tsybakov noise. In Proceedings of The 34th Conference on Learning Theory, COLT, 2021.
[ZLC17] Y. Zhang, Liang, and M. Charikar. A hitting time analysis of stochastic gradient langevin dynamics. In Proceedings of the 30th Conference on Learning Theory, COLT 2017. pages 1980-2022, 2017.
[ZSA20] C. Zhang, Shen, and Awasthi. Efficient active learning of sparse halfspaces with arbitrary bounded noise. In Advances in Neural Information Processing Systems, NewrIPS, 2020.
12

---

Appendix
Organization The appendix is organized as follows: In Appendix A we provide additional comparison to prior work. In Appendix B we present the full version of Section 2
completing
proofs and providing supplementary lemmas omitted in the main body. In Appendix C we start with background on Hermite polynomials and the SQ model, followed by omitted proof' from Section B Finally, in Appendix
[
we prove our lower bound for low-degree polynomial testing.
A Comparison with Previous Work
Here we provide more detailed comparison with the very recent work of [DDK which gives an algorithm and an SQ lower bound for learning g-margin halfspacce the presence of RCN. We start by noting that the SQ-hard instance of [DDK*23 is based on discrete distribution on the hypercube. Consequently, neither the construction nor its analysis have any implications on the Gaussian setting studied here. More generally, the margin assumption intuitively captures much more general family of distributions than the Gaussian distribution (though, formally speaking, the two assumptions are incomparable, as the Gaussian only exhibits an approximate margin property). On the positive side, [DDK*2] I 23] gives an efficient algorithm for learning margin halfspaces in the presence of RCN with sample complexity ((1/(>²e2)) It is important to note that the homogeneity (i.e., origin--entered) assumption provably does not help for the margin case i.e., the case of homogeneous halfspaces with margin is as hard as the case of general halfspaces with a margin. In sharp contrast, our algorithm in this work has sample complexity that crucially depends on the unknown bias p of the target halfspace - interpolating between Odd/e) and Odde²).
B Full Version of Section 2
Throughout this paper, we frequently use the following fact. For x drawn from the standard normal distribution, the threshold t the definition of the halfspace can be related to the bias of fxx)
sign(w" .x x t), as follows.
Fact B.1 (Komatsu's Inequality). For any t E R, the bias p of a halfspace described by f(x)
sign(w" (w" xx+ t) can be bounded as:
2 eexp( SPS t+ +4
2 exxp(-1122
Tt 22
We begin by stating our main result, in Theorem 1.3 below, and providing high-level summary of the main algorithm, in Algorithm 3 We note that both the assumption that 2 and that t S /2 log((1 - 2n)//) are without loss of generality. For the former, it is by the simple symmetry of the standard normal distribution that the entire argument translates into the case < 0, possibly by exchanging the meaning of '+1' and '-1' labels. For the latter, we note that when the bias is small, i.c., for e/(2(1 2n)). constant hypothesis suffices. Thus, only the cases covered by Theorem 1.3 are of interest to us. For the rest of the section, we assume that is known a priori; we show in Appendix B.3 an efficient way to estimate it without increasing the sample complexity.
Theorem 1.3. (Main Algorithmic Result) There exists an algorithm that, given e, E 1/2) and N samples from a distribution D satisfying Definition I.1 runs in time O(dN/e) and returns hypothesis h E C such that with probability at least 1 o, it holds e (h) S + The sample log(1/6).
complexity of the algorithm is N = (TTT22))
max(p 1 22)).)3
Remark B.2. The sample complexity stated in Theorem 1.3 has two components: the first depends on e, and the second depends on the bias p. As we demonstrate in Section 3 the 1/p² term is required for computationally efficient SQ algorithms and low-degree tests. Moreover, the term ((dlog(1//) (8)/((1 2)) is information-theorriiiee optimal, even when p = 1/2, shown, e.g.. HY15).
At a high level, our main algorithm consists of three main subroutines, as summarized in Algorithm 3 The subroutines are specified in the rest of the section, where we analyze the sample complexity and the runtime of our algorithm, and, consequence, prove Theorem L.3 In more detail, the
13

---

Algorithm 3 Main Algorithm
1: Input: 6, 7, e, sample access to distribution D
2: [Wo- p Initialization(6, 7), e): é' c/(1 27)
3: to = V2log(L/p), M = 8 (1(1))(1/))) 22
+1
(c')²
4: Draw N₂ O d dllgg(1// log()/))) samples ((x(1) ) from D
(1-2n))
5: for m 1 M do
6: tm to + (m 1) 6
8 7m = exp((t?
7: Wm Optimization( wo, Lm: 7m, {(x(1) y (8) N2
8: end for
9: [Wout, toue] = Testing (W1, (1) (W2,
(WM, tM)
return Wout, tout
Initialization subroutine (specified in Algorithm ensures that we can choose vector wo from the unit sphere that forms sufficiently small angle with the target vector w", using (dd)))(1)))
2n))pp") samples. This can be seen warm-start for the main optimization procedure (specified in Algorithm ) Crucially, the Initialization procedure does not require knowing the bias p the target halfspacc; instead, it estimates this parameter to constant factor.
The Optimization procedure is run for different guesses of the threshold l (O(log(1/e) them). At a high level, it can be seen as a variant of Riemannian (sub) gradient descent on the unit sphere, applied to the empirical LeakyRLLUU loss defined as LeakyReLU, (u) (1 (1- A)u1 {u 2 and with samples restricted to a band,
of
with parameter X set to 77. u = with and b chosen as functions of the guess for the threshold t. The band restriction is key in avoiding d/c² dependence in the sample complexity, and instead only requiring order-(d (d/err(d// (d/c) samples be drawn for the empirical LeakyReLU loss subgradient estimate. For a sufficiently accurate estimate i of (which is satisfied by at least one of the guesses for which the Optimization procedure is run), we argue that there is sufficiently negative correlation between the empirical subgradient and the target weight vector w This result, combined with the Initialization result, then enables us to inductively argue that the distance between the weight vector constructed by the Optimization procedure and the target vector w* contracts and becomes smaller than within order-log (1/e) iterations. This result is quite surprising, since the LeakyReLU loss nonsmooth (it is, in fact, piecewise linear) and we do not explicitly bound its growth outside the set of its minima (i.e., we do not prove a local error bound, which would typically be used to prove linear convergence). Thus, the result as ours is impossible using black-box results for nonsmooth optimization. Additionally, we never even explicitly use the LeakyReLU loss function prove that it is minimized by w"; instead, we directly prove that the vectors w constructed by our procedure converge the target vector w On a technical level, our result is enabled by novel inductive argument, which we believe may be of independent interest.
0} + Aull u < 0} namely a < w x| <
Finally, since each run of the Optimization subroutine returns a different hypothesis, with only the one(s) with the guess of being sufficiently accurate satisfying our theoretical guarantee, we need a principled approach to selecting a hypothesis with the target error guarantee. This is achieved in the Testing procedure, which simply draws a fresh sample and selects a hypothesis with the lowest test error. By standard result due to [MN06), such hypothesis satisfies our target error guarantee.
B.1 Initialization Procedure
We begin this section with Lemma 2.1 which shows that for any R >> O, given N₁ - (dd 2m) (1)5) i.idd. samples from D. we construct good initial point wo that forms angle at most A with the target weight vector w For our purposes, x should be of the order 1. For
1 IS 2 (T/oe( where e' - e [1 2n)), we can ensure that N, O(d((p21 2n)) lo)(1/))). The downside of the lemma, however, is that the number of samples Ni requires at least approximate knowledge of the bias parameter p (or, more accurately, of e e-t²/2). We address this challenge by arguing (in Lemma 2.2) that we can estimate p using the procedure described in Algorithm without increasing the total number of drawn samples by factor larger than order-log(1/e)
14

---

Algorithm 4 Initialization
1: Input: 6, > 0
2: Let =
3: repeat
4:
j+j+1
5:
Pj 1
32 ( 48gg (og((oo((11 (og(((111)/))))
6:
Draw n2 =
new samples from
222
7:
u + -i= y (()
8: until ||u/||2 2 $ V (1 - 2n)p; or (1 - 2n)pps S
9: Let P 2p 1/ / 2(log(4) log( 1/p]])
-64x (2)(2
10: Draw N1 = x+11 2n
new samples from D
11: u 1 -ズ x (8) (1)
N.
12: Wn < 1//lu/12
return Wo. P
Lemma 2.1 (Initialization via Chow Parameters). Given K. > define Pt.
e Ni
(dd((k pr 21 - 2n 1o)( and let ,x(,)))))))))))))))))))) ) i E [N1] be i.idd. samples drawn drawn.rrom D. Let u= x and Wo u/|lul|z. Then, with probability 1 - 8, have 0(wo, w*) S k.
Proof. We start by showing that Exx,y)> [yxx] is parallel to w" and has nontrivial magnitude, and then draw our conclusions from there. In particular, we prove that
2 2n)p,w"
E
[ux]
(1)
(x-y)~
To do so, observe first that for any vector in the orthogonal complement of w* (i.e., such that
V. w 0), x v (projection of onto v) independent of w", as drawn from N. Thus, D( [x]] = O, which means that E(xx))-D(UX is either zero vector or parallel to w To determine the magnitude of this vector, we next look at the projection of E ((x.))=D(pp onto w Using that w x mieedmmnsional standard normal random variable, we have
E (sign(ww t)w" x| x
E [11 2 -t - 1f2 -t}2]
E =,]](+<<<<)))----
()= +2 E [1{= 1)2]
2~
2~N
2 [1
2mN
2
to0
26 12
2 +00
1(2-
2
V2T Jt
2 e 1/22
V Pp-
Recalling the definition of y, we now obtain Equation L.. We then conclude from Equation
that
plxx))) /1 2n)Pt. as || 1/2 1, by assumption.
The next step is to show that /े. Σ (1) (+) concentrates near its expectation. Note that yx /2-sub-Gaussian
22-sub-Crr Gaussian as x is standard normal, therefore, by the multiplicative Hoeffding bound,
Ni
Nix E E(x.g)) D (
Pr
E (x.I)~D
[x
E (x.0)>D
[x]]
< 2exp
N
128d
1=1
2
Nik (1 2
< 2exp
64Td
Thus, choosing
N₂ =
64md log (2/8) suffices to guarantee that
1u E D(xx)~D/xx\1>
5
[xxx)>>Dyxx]ll with probability at least - 8.
15

---

It remains to bound ((wo. w*), where wo u/ 1//lu//22 Since w" is unit vector, we have that with probability least 1 ò,
w
(u E (x.))>DD (2x))
w"
+ E (x,,)) [3x]
w
cos (wo, w")
|
E
(x,x))>0
[XX
112
(1 x² x²/8)]| (xx,)== yx 2
x²/
(1 + x² /8)
E (xx,))) /x 2
+ x²/8
where we have used that (xx,))~ [yx]
w" = E (x. myyx/=l
|yx|]12 (by Equation 11 and (u
E(x,))Dlyxx) w 2 -Sup::/wwll=> (u- ((x.))=D(yx)) w, which is greater than or equal to E (x.)) [yx] [|2, by the concentration argument used above.
As cos (Wo, w I 0(wo. w )2/4, we further have
n²2/4
0(wo, w / 1 R2/8 RR2/4.
yielding the desired result that O(wo. w 1 K.
We now leverage Lemma 2.1 to argue about correctness of Algorithm which provides an imple- mentable initialization procedure.
Lemma 2.2. Consider the Initialization procedure described by Algorithm 4 in Appendix B. If0= <
t S log((1 2n)/E), then with probability at least 1-6, exp(-t²/2) S < 4 expp( (exp(tt² --t² 22) The
algorithm draws a total of Ō d (lo()
max max 2n)p, x)² samples and ensures that 8(wo. w") S min 5r g).
Proof. Let é = = - (()) and J = [lgg2 (1/c')]. As we have shown in the proof of Lemma 2.1
vector uj satisfies
1 2 (1 2n))p;
(- ny m1 pp
- exp Since the algorithm runs for most J [log2 (1/ (1/c)] iterations, applying the union bound yields:
Pr
|uy - Elyx]] ll2 2
4
32nd
2 - (1 21)p;, Vjj = 1, 1, J
(- n2 22n)) 2n))²p3
Pr
[u, Elyx] 2 2
S 2J exp
8,
T
32md
where we plugged in ny 32nd (ogg log(1/)')))
Furthermore, recall that have proved in ( - /2). Hence, with probability at least 1 - 8, we
(1-27)
Lemma 2.1 that || [ ||
/ 122 2n) exp(
have that for all j 1.... J.
2 2 (1 2m) (exp( (opp(((//))))))))) - 42) s u S
2 21 27xp( p//4). π
(2)
Since we have assumed 0 < < / (oog((/ee). it must be exp( - 2222) 2 é'. thus the claimed bound on و holds the algorithm loop ends because j [log_ (1/e')] Consider now the case that the loop ends before reaching the upper bound on the number of iterations. Observe that when pj is still far away from cxp(-t2/2), i.e., when Pj > 2
2 shows that with probability at least - 6, 1 < (3/4)/2/7(11 - 27));; thus, the algorithm will continue to decrease our guess Pj- On the other hand, if P, is already small, i.e., if p5 S cxp(-t2/2)) Equation (2) implies /2/4) - 2n)p,, reaching the repeat-until loop termination condition. As any iteration of the algorithm reduces the value of Pj by a factor of 2, we conclude that the loop ends with Pj that satisfies ; exp(-t2/2) Σ Pj S cexp(-f2 f hence the bound on á follows as Đ = 2p,--
Equation
that || Luyle 2|
The bound on the total number of samples drawn by the algorithm follows by observing that for each iteration j of the repeat-until loop, n, = ONi), while there are Olog(1/ee)) total loop iterations.
To complete the proof, it remains to note that the bound on ş implies
/2 log((11)) < L < /2(1og(4) + log(111))
Hence & selected in the algorithm satisfies k < 1. Furthermore, since the algorithm runs for at least one iteration, it holds that ý 2p1 = 1. Thus, our choice of also guarantees that
57
22lgg))) < 3. It remains to apply Lemma 2.1
D
16

---

Algorithm 5 Optimization
1: Input: Wo, i, Y 7,, N2 i.idd samples (x(*) ()) from D
2: N40
(1-4p)
p 0.00098; P(i, 4)
16 2nn (4]]
3: for 0 K do
4: Let E(wk, 1) = fx - We x 1
5: Let g( [w: (1) ()) 2(1 2n)sign( We: x(1) +1) - -(0))proiw, (x(1)
6:
((wA) + N₂ Li=i g(w (+), y() [/x(")
N2
x+),
p(t.5)
7: ltk 1k- (1
8: Wh+1 - |w ww (0.
9: end for
return WK+1
B.2 Optimization
As discussed before, Optimization procedure (Algorithm 5) can be seen Riemannian subgradi- ent descent on the unit sphere. Crucial to our analysis is the use of subgradient estimates from Line 3 and Line 6 where condition the event that the samples come from thin band, defined in Line 4 Without this conditioning, the algorithm would correspond to projected subgradient descent of the LeakyRelJU loss the unit sphere. The conditioning effectively changes the landscape of the loss function being optimized, which cannot be argued anymore to even he convex, as the definition of the band depends the weight vector which the vector g( (w) is evaluated. Nevertheless, as we argue in this section, the optimization procedure can be carried out very efficiently, even exhibit- ing linear convergence rate, To simplify the notation, this section denote the conditioned distribution (l.(w.)) by D(w, E). We carry out the analysis assuming the estimate is within additive 2 the true threshold value f; as argued before, this has to be true for at least one estimate for which the Optimization procedure is invoked.
In the following lemma, we show that the angle between a weight vector w and the target vector w* is from a certain range, we can guarantee that g( (w) is sufficiently negatively correlated with w This condition then used to argue about progress of our algorithm. The upper bound on will hold initially, by initialization procedure, and will inductively argue that it holds for most iterations. The lower bound, when violated, will imply that the distance between w and w small, in which case would have converged to sufficiently good solution w.
Lemma 2.3. Fix any è' (0.1). Suppose that 0 st (log(1/ and w E Rd is such that ||w 1|2 = 1, and 0 = A(w, w*) satisfies the inequality é' exp((2/2) S 0 S 1/(5)). If 1 e /2/8 and 9 = (1/2))' exp((2 /2), then E(x,)) www.:./////wwwww (g(w: w*] S - 2n) sin 0 02/2//
Proof. To simplify the notation, in the following we write g(w) g(w; x, as (x, v) is clear from the context. Using the definition of conditional expectations well as the definition of D(w, 2), we have
E E(x.) w'I(E(w,()) Pr(E(w,()
E (X.9)>D((wB))
g(() w"]
[g(w) w w'|E(w, (x.))~D
E
We carry out the proof by bounding the numerator ((xx))((((w) w' t)}} Recall that E ((x.)))D(v/ [y|x] = (1-2n)sign((v (w")x+()). Furthermore, since the Gaussian distribution rotationally invariant, we can assume without loss of generality that and w" cos fe; + sin 6eg.
17

---

Therefore.
E
(g()): w wwW 1)3
(xay)~D
1 2T
E (sign(w w x+ 1) sigu(w"... x 1))projw- (x) w (E(w,
(x.))_D))
1- 27
E
(sign(xx + sign(cos 0x1 + sin Ox2 + ())(2)
2
x
(cos del + sin 022) (E(w,
=11 2n) sin 0
E x-DD
x2 si 0 I -t - x1 cos 0
(4)
where in the final equality, we used the fact that under the event E(w, 8), X1 w x is greater than or equal to -f and consequently, the expression sign(x1 f) sign (cos 0x1 + sin 6x2 + t) equals 2 when cos 0x1 + sin 0x2 is less than or equal zero, and it is zero all other cases.
Recall that under the assumptions of the lemma, It 8 S e²2 /8. To bound the expectation in Equation (4), we consider two possible cases: t 2 and S 1. The reason that we discuss these two cases is that when large, under the condition that - 2 x1 I -f+ and X2 sin 0 S -t -t-xx X2 cos it is guaranteed that x2 S O. On the other hand, when is small, it is possible that x2 2 0. However, we can show that even though X2 2 0 in some area of the band, the expectation E/ Exx2 1l (w l). s X2 sin S -t- x1 cos {}] is small since very small. This is handled in the following two claims, under the same assumptions as in the statement of the lemma.
Claim B.3. Ift 1, then
2 PP (w,,)(WW)) f)]
E [x,1(E(W, X2 sin < - x1 cos x
2t
Proof. When t 2 1, under event Eww f), we have
X2 sin
-1 X1 cos < -1 icos
S - - t + 2² (0)88
< 2sin 20022( + 1//8.
Since we have assumed t 2 1 and 0 2 e' exp(t? e2)( we further have
"2
X2 sin 0 < -2sin
(exp(1?) 1) S 0, / 8
where we used that sin(0/2) > 0/4 4, which holds for any 0 S n. Therefore, x2 S 0 when (E(w, 2). X2 sin 0 S -t cos { = 1.
Note that conditioning on E(w, 2) we have x < -i+ 9, hence it holds 1(E(w, x2, sin 0 S -t
X1 cos 0) 2 ([E((,)) X2 sin & - (-1 + 7) cos 0}. In addition, since 2 1 1- 22 /8, we have
1(E(w, i), X2 sin 0 < -t X1 cos 0} 2 ([8(w, 1), X2 sin 0 S -(1 - cos f) (c"2 (²// 4) cos 0).
Therefore, have the following upper bound:
E x>
[ 2), X2 sin O S - - X1 cos
X2 11E(w, 1). x2 S - (tan((/2) (22 +)) cot 01} x
E
where we used the trigonometric identity (1 - cos 0)/ sin = tan(0/2). Since x and X2 are independent standard normal random variables, the expectation the right-hand side of Equation (5) has the following closed form expression:
E
X2 1[8(W, w, 1), x2 S -1tan(0/2) - (e +) oot
x~D
-ttan(022-((2//884) cote
= =Pr(E(w, 8)]
exp(-x² dr
2T
Pr(g((, D)
2
cot 0 + f foo 2
exp
t tan
+
(6)
2T
2
8
18

---

Let us now bound l lan (2)+ g col col 0 O. Using the trigonometric inequalities lan(0/2) s 0/2 and cot 0 - 1/0, which hold for 0 E [0. 1T///2 and recalling that é' exp(t? /2) = 0 - 1/t),, we have
8 2
t0
E²
I. tan
+
cot 0 + cot <
g
2
8
0
<
10 8
2
V (log(1/ee
S 40
8
where the second inequality by the definition o and the bounds on and the third inequality is
by i - t s and t E /2log(1/e). Hence, combining Equation ( Equation we get
E (x,,(E(w,)) sin -t- x1 cos S Pr(E(w, 2) x
exp( exp(-(7/8))/2)
V2T
2 (r( D] S 2
(8)
as claimed.
We now proceed to the case where < 1.
Claim B.4. If L < 1, then
Pr Pr[E(w, .i]
(2, < -1 cos cos < xx
E
2v2n
Proof. In this case, it is possible that X2 2 0 when 1(8(w),xxsin) sin < - - x cos = 1.
However, since 5 = e' exp( 22/2 2 /2/8, it must be - -1 - -0 /2 + 9 2 - indicating
that -t -t- - (-ē + 3) cos v -t + cos S 0, hence X2 S 0 when [[E(w,)) f) S -t/ sin 0
(-É+t) cot 9} = 1. Therefore, we split the indicator ((8(w, f), X2 sin 0 S -t- x1 cos Q) into the
indicators of three sub-events:
((E(w, X2 S -1/ s/sin 0 x1 cot 0) = 11 { + (8)) + 1(8))
where
E = E(w, 2) n (xe & -t/sin - () cot
E = E(w, 1) n (0 S x2 S -l/sin sin 0 - x1 cot 0}
Eg E(w, 1) n (-1/ sin (-i -( 5) col < x2 S min sin - xx cotO, 0}}.
For Ex-D, [x, (1 H. observe first that
[{E}} = (( & -t/ sin 1 + fcot 0 - cot 0}
2 (E((w, x),x2 S -l/ + (1 /² /2/8) cot 0 fot 0}
Since X2 < 0 under E,, it then holds
E [x21 xx
E [x2][E(w, 0) -1/ sin (1 /8) cot 0 col 0) x-Dx
E x~Dx
[x2](E(w, 0), -1laan(0/2) "² / 0 - -Fcol
Pr(E(w, [)]
-1(ttan tan
0
" cot 1 + & cot 8) ))
(-2
exp
2t
2
following similar steps as in Claim B.3 Equation 5 Equation ( Again, note that we have assumed e/ex((((222) S < 1/(5t) and have chosen é' d'exp(( (272)/2 2, thus, using the fact that tan(0/2) 0/2, cot 0 < 1/0, we further get:
Pr[E(w, f)]
1
t0
2
3 2 )) +
2 2Pr(E( f)
E [x x
exp
+
<
22
2
2
80
3v2T
19

---

using the same arguments as in Equation Equation
88 For Ex~D, [xy1[Es]] note that X2 S 0
under Eg, hence Ex Xx2 {Eg] S O.
We now study Ex-D, [x2 1 { Observe that
]{ = { (E(w, t), < X2 f -t/sin 0 x1 cot cot
< (8( D) - x2 S -1/sin s/sinn cot 0}
S (E(,, 0),0 S x2 S ((1 cos / sin A (62 (8) c)t
where the first inequality results from the condition that x1 -f. Hence, the expectation Ex-D2 [x2 [E2}] can be upper-bounded by
(E(w, 5x S tan (B/2) + (c2 0 E [x21 (&2)] I x~Dx
x~
(ttan(0/2)(((")8)))))
Pr(E(w.()] /
exp(- (-z² /22 dr
22
-#tau(0/2)+(c
S Pr(E(w.f) f)] 0
T
dr
2x
Pr[e(w, f)] (t (ta((/)))) (c cot 0)2.
2/2n
We again use the fact that (0/() < 0 and cot 0 < 1/0, then recall that e' exp(t*/2) < < 1/((t),
e//0 S 1, thus, we get
Pr(e f)] E [x21( x-D
((10)=+("" = Pr(E(w. (1/25+c"//64) 1 Pr(E(w, t')l 2tT
22T
12v2m 2n
Combining with the derived upper bounds on Ex-D, [x2 (81) }} and EXLO, (x2 (E completes the proof.
Combining Claim B.4 and Claim B.3 we have Ex-Da ( 1), x2 sin -t x cos 0}
(r(E(w.())
2/20 Thus, plugging this result back to Equation (4) and then combining with Equation
we complete the proof of the lemma.
Since, by construction, g(w) is orthogonal to w (see Line5inn Algorithm 5). we can bound the norm of the expected gradient vector by bounding g(w)- for some unit vectors u that are orthogonal to w using similar techniques as in Lemma 2.3 To be specific, we have the following lemma.
Lemma 2.4. Under the assumptions of Lemma 2.3
E (x..)) (g( v)]l S (1-2n)
V
Proof. First, we show that for any vector that is orthogonal to both w and w", the expected gradient of g(w)- = g(w;x, x, y) is zero. As a consequence, Elg(w)] must lie in the 2-dimensional space spanned by and w To see that, observe first that
1 1-2n
(g(w) v]
E [1{E(W, 8), w x 0Jv proj - (x)]
(x.))
Pr(E(w, 1)
x>Dx
1-27 27
E [I(E(W, w x+150H E I x = 0,
where we used proj (x) Pr(E(w, 1)
x-Dx
X-D
(x (x-w)w w)w and w O, the fact that v is independent of and w* x, and that Ex-D, [v. x] = O. Furthermore, by construction, g(w) s(w) is orthogonal to w. This indicates that E E(x.))DD [g( [w] is parallel to w*, as both and w are unit vectors. Since x Dx is rotation invariant, we can assume w = e, and w" = cos de; + sin Beg. We thus only need to bound E ((x.)))D(ww,) (g(w] oz/. Recall that D(w, i) is the distribution conditioned on the band E(w, {x: -f w -f -(++) f) hence, by the definition of g( (w), have
E Exx
(E (E., (w, 8)
(g(w). e2]l (x.))=D(w.))
Pr(E(w, 1)]
(1 (1-23 27) Pr(g(w, i)]
[x2 I (E(w,), f), sin 0x2 S -t - cos cxs)x]]]] (9)
xx
20

---

To proceed, we discuss the cases where t S 1 and t 2 1, following similar steps as in Lemma 2.3
Claim B.5. Under the assumptions of Lemma 2.3 if then
W: x. 8)l|r 1 1 2n
E
(x.))>D(w.I)
22T
Proof. As shown in the proof of Claim B.3 when 1 2 the condition X2 -t/sin 0 X1 cot.
-f S -8+ 2+ f implies that X2 s 0. Hence, in this case have
1 [E i), X2 S 1/ sin x1 cot 0} S 1(E(w, X2 S 0},
and we can further conclude that
E [e (w,t). f), X2 sin 0 I -t x1 cos x
= (x,,((((.))) X2 S -t - x1 cos0
xrvD,
E x-
1x2, 2), x2 5 03]
Pr(E(w, D)
22T
Plugging this back into Equation (9) yields the claimed result.
When t & 1, we use a slightly different decomposition
1{E(w, f), x2 S 1/ sin 0 x1 cot 0} 1(8) + +(E)),
where
E E(w, {xe S -t/ sin x1 cot a, x2 S 0},
E = E(w, i) n {0 S x2 S - t/ sin x1 cot
By the definitions of these two events, we have
{
< 0,
E [x) 20. Dx
D
Since in the proof of Lemma
2.3 we have shown that
E
[ i), x2 S -1/ sin 0 - x, cot 0]] S 0,
D
it must hold that
E [x21(E(w, x25 x),2 xx
sin -i/ x1 cot
= E [x21
+ E [x
x~Dx
x~Dx
< E [x21(E]]1
Since {88} < 1 (E(w, (), X2 S 5.). we thus have
Pr(E(w, f)
E [x, x2 f/ sin x1 cot
/ 2m
Plugging this back into Equation
g completes the proof.
The following lemma establishes uniform convergence result for the empirical subgradient.
Lemma B.6. Consider the learning problem defined in Definition 1.] Fix 5 E (0, 1/2), and let be any absolute constant in (0, 1). Consider the following class functions for (x. v) ~ D:
F == (w): IR.d. ||w||2 1, exp (t² /2) < 0(w, w*) 1/(5t) where
g' g'(w;x, v) = / (1 - 27)ssgn(( w x 2) - 3) proj (x) w x E -i
and where & satisfies {f 8-th t| - e² f8 and 9/ (1/2)e' cxp(F2 /2). Then, using N Ō dlug(1/(6)) samples from D with probability at least 1 - ó, for any g'(w, E F it holds
Σ g (w; 10) (0)
E (x
Ig' (w; m))l S Sall E (x.1)DD
[g'(w;
21

---

x, v) and we further define Proof. For simplicity, we will use g'ww)to denote g' g.
B'(w) N
(w; (w;x(1) ,0))
By definition, g' s'(w) is orthogonal to w, hence is (w(w.. As already argued in the proof of Lemma 2.4 E E(x.))=Dl'((w) is also orthogonal to w. Thus, llg'(w) E(x,))> (ag') [g())]lla is determined by (g'(w) - (( (igg (w)l) w', where w' is a unit vector that orthogonal to w.
Fix unit vectors w, w' E Rd with w w' = O. We are going to make use of the following variant of Bernstein's 's inequality (see, e.g., [God55]).
Fact B.7. Let Xi...., X be zero mean i.i.d. random variables. Assume that for some positive reals
L, a > 0, it holds that E|| 1 s (1/2) ( kk.. Then, for any x E (0, (No?/(2L))
N
Pr
Σ
X, 2 2
S expp(==²)
We show that the random variable g'(w) w' satisfies the assumptions of Fact B.7 using the definition of g' which enforces g' (w;x, y) = 0 whenever 1 [w x we have that
For any k 2 2,
f + r1} = 0,
(x (w)( wh
E
E [[ x (- 9|H xxDx
E [|w'
x|*]
x
S Pr/w x E --,,- **]
where the last inequality comes from the fact that for random variable), it holds E[[=|*] (V2evk)* S C.Ck-21 for some absolute constants C1 and C2, and we choose C' to be a large enough multiple of C1, C2. Let 0² Pr(w x i-f, - A
Gaussian variable (e.g., Gaussian
Note that since A _ (fp((2//) /2), we have 0² 2 9 eexp 12) e'. Then, the condition of Fact B.7 is satisfied with o² j
Next, we show that we can bound || E ((x)) (w))llll from below. In Lemma 2.3 we showed that when e' exp(t2/22 s 0(w, w") S 1/(5t), 18 1| c²2 2/ and
/ exp(1 ( /2), it holds
E (g(w) w*] E Exx (g(w) w 1( X (-i, -i + HH (x.))>((w,)
Pr(w x E [- +f
Exx.)) (g' (w) w }]
< (1- 2n) sin (O(w, w"))
(10)
g²
2
Let W be unit vector orthogonal to w such that w = w cos(O(w (w, w")) + w sin(O(w, w w"). Then, recalling the fact that E(x,g)>DD Ig' (w)] also orthogonal w, we have:
E (x
Ig' [8(ww]ll==
sup vERd: (x,))D
E
Ig' (w))
E
Ig' (w)] w
(x.y)>D
E E(x,)) (g' (w)] w
sin (ww, w*)
1 2n
2 2m
where in the last line we used Equation conclude that
10 Thus, as σ² < 1 (it is defined a probability), we
g (w)]lla 2 (1- (1-21) 0²
E
(11)
(x,y)~D
2x
Applying Fact B.7 we now get that for any w' E [Rdd || 1,
Pr
D ('(w)
(w)
w'
E (x.y)>
(w) w']
> 2x / 02 N/N
$ <exp(-x²
22

---

Choosing
a(1-2n) 2/2x
Vo2N, where (0, 1) is an absolute constant, yields
E (w) w'] a(1 - 2n) o²
Pr
g (w) w'
exp(=NNa 222)) /(r))//(8)))))))))))))))))))
(x.a)~<
2v2x
In partieular, since the above inequality holds for any unit w', using Equation
[1]. it follows that
Pr g'
w'
E (x.0)~
('() w/ 2 all
E g (2(2)lll (x.))~D
I <xp( No 2n) 0² /(x))
(12)
remains to show that Equation 112 holds for all functions J. To do that, we apply the union bound along all the directions w', all the hypothesis w. A cover for these parameters will be of order (1/E))o()) Hence, we have that for any unit vector w E R with e' exp((
( /2) s 0(w, w S 1/(5t),
Pr
lgg (w)
E g' (w) 2 2 all
E
g' (w)]ll2
(x.))>
(x.0)~
I cxp(O(dlog(1/c))) exp( Napp-NNa11 - 2n) oz (8T)) S 88, where in the last inequality, used that 0² 2 /.. and N Ö(dlog (1 (0 2n)
Recall that for some fixed w and i, we have defined the empirical gradient vector in Line as:
No
g(w) N2P(1. 5)
g (w; ( y 1x E(ww
where P(f, Pr E i-f, -f+ Pr[E(w, f).. since w is a unit vector and w x follows standard Gaussian. Thus, g(w) = g'(w)/ ((w)/Pr(E( w, f)]. In addition, by definition we know that
E
(g[ [w)
[g(())/ [=))(( Pr(E(w, [)],
E
(xw.)
(x.9)~D
and so Lemma B.6 immediately implies the following corollary.
Corollary B.S. Consider the learning problem from Definition 1.1 Ler é', 8, y be parameters satis- 1/4. Then using (d (6)))((1 2e)) samples to construct g. for any unit vector w such that c' cxp(t)) /2) < A(w, w S 1/(5t), holds
fying the condition of Lemma B.6 and choose
with probability at least 8: [[ (w) (erww>>Exxppppaaae ((x.))>D(w.)) (g(gg())(]]l)) (1/4) E (x..)) www.)/lg(()))) [g(w)]ll2.
We are now ready to present and prove our main algorithm-related result. A short roadmap for our proof is as follows. Since Algorithm constructs a grid with grid-width c²2/8 that covers all possible values of the true threshold t, there exists at least one guess that is e"2-close to the true threshold We first show that to get halfspace with error at most c', it suffices to use this f the threshold and find a weight vector w such that the angle f(w, w*) is of the order c', which is exactly what Algorithm 5 does. The connection between f(w, w*) and the error is conveyed by the following fact:
Fact B.9 (see, e.g., Lemma 4.2 of DKSI8 ) Under the standard normal distribution, it holds:
0(w, w*) exp(-t
Pr[sign(w (w- x x +t) + (w" x t)
Let wa be the parameter generated by Algorithm 5 at iteration for threshold We show that 0(WE, w*) converges to zero at linear rate. To this end, we prove that under our carefully devised step size μą. there exists an upper bound on |W 221 which contracts at each iteration. Note that since both W and w* are on the unit sphere, we have ||w: w 2 sin (w,, w w²2/)). Essentially, this implies that Algorithm converges to linearly, under this threshold Thus, we can conclude that there exists halfspace among all halfspaces generated by Algorithm 3
5 produces a sequence of parameters wa such that ((wx, w*)
that achieves e' error with high probability.
23

---

Theorem 2.6. Consider the learning problem from Definition 1.1 Fix any unit vector Wo E Ra such that Woo w*) v min(1/(5t), T/2).
Fix any e, > 0. Let > 0 be a threshold such that j t S e² (8((1 )n)²), and let 9 = e 2n)) exp L (2)). Then Algorithm 2 uses N₂ = (dd((1 2n)c) log(1/))) samples from D. has runtime ((N2)), and outputs a weight vector w such that h(x)= sign(w. (w- x+ f) satisfies Pr(h(x) + vl S rj + with probability at least 1 6.
Proof. Let 2-2 and denote we as the parameter produced by the algorithm at Athh iteration under threshold (. Observe that for any unit vector w:
(w x + f) # sign (w" x ++]) t)]
Pr(sign( x 2) & sign( w x + f), sign(w - x + t) = sign(w (w' x + t)]
+ Pr[sign(w x + 8) sign(w x 1), sign( + 1) j sign(w (w* x -x+ ()
- PPr[sign(w x ن sign x + f) Pr (sign x + t) * sign(w" x t)].
Since If - t & <²2/ it holds
Pr[sign(w w x i) + sign(w x + t)]
Pr( max(t, Sw..x. -minttt
< 2/ 1
6²2
2t
4v2
In addition, as shown in Fact B.9 Pr Prisign(w w x t) # sign(w (w+ + t)] S O(w.w") exp(-t2/2);
thus,
l(w, w*) e²2
Pr|sign(w x x 1) A sign(w" x 1) 5
(13)
4
π
Therefore, it suffices to find a parameter w such that 0(w, w*) S n ex2(12/2). Note that since both w and w* are unit vectors, we have ||w w* 122 2sin (0/2), indicating that it suffices to minimize |ww- - w'll efficiently. As proved in Lemma 2.1 and Lemma 2.2 we can start with an initial vector wo such that 0(wo. w>) < 1/(5t) by calling Algorithm 4 Starting from this wo. show that |[ - w'lla ll2 contracts linearly whenever the angle between wa and w- is larger than e' exp(t? /2), thus we reach the required upper bound for this angle within logarithmic number of steps. Denote 0% = 8(w,, w*) and consider the case when 0g 2 c' exexp(t//2) /2).
2c)) samples from distribution D, we have that if 0 2 e' exp(t") (2) then with probability at least 1 5: || w w w 112 (C,/22 22 sin 02 + 1
Claim 2.7. Let C1 = (1 2n) 2T. Drawing N₂ = O(doog(1/))//
Proof. Observe first that since g( w&) ) is orthogonal to Wa. we have | م (w)) /
M (1((w))) 2 1, thus normalizing w (g(wa) equivalent to projecting We g (w)) to the unit ball B. Since we have assumed w E E, by the non-expansiveness of the projection operator and projs( w*) = w", we have:
WE (1 Wx)
W
w² [|proja (Wx -=g((w)) -w"l w"1
Wi
[&gg( W )l1
Wk (R@((w)) w 112-
Thus, expanding the squared norm on the right-hand side yields:
|| 3 < |w w' 1 2 Wk))
(W* w") + 22 ([(
|| w 1/ 2,4
E
(g(WL) w+]
(14)
(x.0) (a) (wa.))
+ 24r (g(wk)
E
[g(w w + (
(x.9) (x.y)-D(ww..
where in the first equality used the fact that g(w,) and ((..)) (og.))/g((w))) (g(w))) are both orthogonal to Wa. Without loss of generality (because of the rotational invariance), assume Wa ej and
24

---

w" = cos feg + sin deg. Then, again by the fact that both g(wa) and E (xx.) ())()) [(w)))] are
orthogonal to Wk. we have
g (w))
E (x.))~((w..))
g((w))) w = sin (g(w))))
E
(g(w))]) .2
(x.g)~ (w.()
S sin 0x ((([(s)))
E
g(w+)]]l2-
(x.))-((w,.))
Thus, further invoking Lemma 2,3 we have:
(1 2n) sin 0z
Wk+1 w'1 <
Wk
w"
2p1
2v2 2m
+ 2p sin 0R [[(=))
E (x.y)-D(w,.f)
(g( (xllg((w)))))))
(w))) (15)
Corollary B.8 (or Lemma 2.5 implies that with N2 (0)(lo((1))(((112))
2 samples in total, for any unit vector Wa satistying exp((t) /2) s 02 5 1/(5t) with probability least 1 holds:
- 1
(((w))
gg ( (lw)))ll
E (x.y)
(g(ww)lllz
(16)
(x.g)>
Recall that we have shown in the proof of Lemma 2.4 that E (x.x)) (lw..))))((()llll) (g(w))llle -
1-29,
V2r
therefore, Equation (16) further gives that with probability at least 1 - 6:
| (B(wx)ll2 (ww))
E
[g(wx)]]l (x..))-((w..))
E g((x)]ll
(xw.))((ww.))
2(1-21)) 22n)
(g(Wa)lll2
(17)
(x
v2w
Thus, plugging Equation 16 and Equation at least 1 8,
back into Equation
15 we get that with probability
2n
sin 02 + 2p4 1 21
2 2(1 - 2n)
WW+11 1
Wk w 31 2ptk 2
sin 02 + Mk
4
2n
2(1 2n))
Wk-
11
sin 02 + 2
(18)
2
Let C₁ = 1-2g V2x
Then Equation
18 is simplified to:
C₁ w"1
[W--1
w|
2 Mr sin 0g + +4
(19)
completing the proof of this claim.
remains choose the step size ba properly get linear convergence. By carefully designing shrinking step size, we are able to construct an upper-boul bound dy on the distance of [[ W using Claim 2.7 Importantly, by exploiting the property that both and w are the unit sphere, we show that the upper bound is contracting at each step, even though the distance [[ W could be increasing. Concretely, we have the following claim.
Lemma 2.8. Let p 0.00098 and de (1 /)²h Then, setting μa - 4p)))x/166C1) it holds sin(Ox/2) S d& for h = 1, K.
Proof. Let ch = (1 R where p = 0.00098. This choice of p ensures that 32p² + 1020p - 0. We show by induction that choosing
(1 4p) //1//(666)))))) = (1 (05-ph p)*(1 (1-111660 4p) (0))()66)))))))) ), it holds
sin (2)2)) di. The condition certainly holds for since 61 [0, 2/). Now suppose that
sin 22) Oe for some k 2 1. We discuss the following cases: Oz 2 sin (#x/2) 2 4 66 and
sin (2) o
25

---

First, suppose OE 2 sin(Ox/2)
2 oz.. Since sin(Ox/2) I sin 0x. it also holds sin 02 2 oz.
Bringing in the fact that | w ll2 2 sin and |W w'll2 (f /2), well as the definition of ua. Equation 19 becomes:
C₁
Ma sin O2 + 402 (1 -pp)
(2 S (2sin(0x/2))²
2
16C1
C1
3
C1(1
-4p)
I 4
P4
+
HROR
2
4
4
C
1
1
4p
-40%
+
4p
4
2
1601
1 (1+ + 8p)
4p)
4
512
where in the second line we used sin 02 oo and in the third line we used the definition of μu by
which μi=- = (1-4p)6)) 111-44)x//(1GC))) Since p is chosen so that 32p² + 1020p 1 S 0, we have:
1 (1 + 8p)(1 4p)
sin(0x+1/2) S Φb
512
(1+ + 8p) 4p)
S Φb
1
( - ()))x = =11 - (1)))
1024
as desired.
1 tb. Recall that Wk41 projs (W, sl.g(w:)) and we E B: therefore, ||W - W 2 S W pxg(w) (w) - - = uu [[[[@)))lll by the non-expansiveness of
Next, consider sin(Ox/2) <
3
the projection operator. Furthermore, applying Equation 17.. we have (l < 2C1; therefore, -
[|Wa+1 - w 5 21 which indicates that:
2(sin(0x+1 /2) 2)) = || - w"lla || - woll2 S || - wwlle S C1-
Since we have assumed (in(0//2) S co. then it holds:
Φx+1 sin(0x+1/2 /2 2 (1 - p)0x Øk + ob sin sin(01/2) - C1
1
4p
3(1 - 4p)
2 p + 70s 16 dx
t2 > 0,
16
since we have chosen μ4 = (1-4p) (16C1). Hence, it also holds that sin (xx1 I ox+1-
Lemma 2.8 shows that sin(01/2) converges to 0 linearly. Therefore, using N₂ log(L//0 (1/0))((111- Ree) samples, after K = 0 | ((xp((/eex(t/))))))e such that 0K < 2 s é' exp(t? /2). Let h(x) sign(w (WK + f). Equation [3 then implies that the disagreement of (xx and f(x) is bounded by:
= (log(1/(pee) iterations, we get a WK
22
Pr(M(x) # f(x)) <
Sc.
4v 2n
Furthermore, for any boolean function h Rd +11} it holds
( (h) = Pr [x(x) + v] = + (1 - 2n) Pr [h(x) + sign(w" x t)]. xxDxx
(x.")>D
Thus, to get misclassification eтror at most + (with respect to the y). we only need to use = c/(1 - 27), and we finally get that Pr(x.w)>((signi (sign( x + f) * y] S 17 + c, using N2 (ddlog()/))((( (1/))((L1))))))))) 2n)e)) samples. Since the algorithm runs for ((logL//e) iterations, the overall runtime is O(Nd)). This completes the proof of Theorem 2.6
Proof of Theorem T.3 From Lemma 2.2 we get that with (gd 1/6)/((1 - 2n))2²)) samples Algorithm 4 produces unit vector Wo that ((wo w*) min(1/(5t), T/2).
26

---

Since our guesses of the threshold Em m E [M] form grid of (e2/(8(1 22n) ) separated values on
the interval Iv log
t. which covers all possible values of the true threshold t,
there exists a m E [M] such that I - f S 22/(8(1 2n Thus, the condition of Theorem 2.6 is
satisfied by at least one input threshold. Given wo, let w Wm m E [M] be the weight vector produced by
Algorithm at call m = 1, M. From Theorem 2.6 we know that with O (oog(1/))/())) (2)) samples, with probability at least å we get a list of halfspaces {lm (x) hmm (x) sign Wm km),7) m 1,,-, ,M so that
Pr fm E [M] (xaa)>>
min
Ihm (x) * yl snte.
Finally, to pick the optimal hypothesis from the list, we utilize the following fact.
Fact B.10 (Equation (7) in [MN06]). Let D be distribution over R2 {+1}. Let F be concept set of boolean functions with VC dimension at most d. Let D be the empirical distribution obtained by drawing Od /5)/((11 2n))c) samples from DD Then holds that
min Pr [[(x) # S min Pr [x(x) + y] +e. FEF (x,))>
JEF (x.g)
Using the above fact and a sample size of N3 = log (/8))((( [1 - 2n)e)) from D, we output the hypothesis with the minimum empirical error. By Fact 1. we have that this will introduce an error at most e with probability at least 1 - 8. Since M (1/e²), the total number of calls of Algorithm in Algorithm is O(1/e),, and the runtime is ((Nd/²).
Algorithm 6 Testing Procedure
Input: Hypothesis weight vectors W1, W2...., Wm. and thresholds &,, t2,..., bm
Draw Na samples {(x(", (+) Na from D Calculate the test error (the fraction of misclassified points) for (x) = sign(W,., x - tm).
m [M] using {(x(1) ( ())
Let n. (x) = sign Wm X + tm). m E [M] be the halfspace with smallest empirical error.
return Wm. 4m
B.3 The Case Where Both 1) and p are Unknown
Throughout this section, we carried out the analysis assuming knowledge of the noise parameter fj- We now show how to relax this requirement, without changing the sample complexity (up to constant factors) and only affecting the algorithm runtime by a factor 1/e. In the following lemma, we show that with ((d (ogg(/))//(/))
2)) samples values of p and 1 - 21,, which suffice for determining the correct number of samples to draw in all three subprocedures of our main algorithm (i.c., can correctly determine N1, N2, and N3).
compute constant factor estimates of the
Lemma B.11. There is an algorithm that uses O(d log(L/))))(p(11 - 2n) samples, and with probability at least 1 8 outputs estimates p. ft, so that Cp p 2 P and C(1 24) (1 2n) 2
(1 - 21j), where C > 0 is a sufficient large absolute constant.
Proof Sketch. We note that Algorithm 4 can, in fact, be used to get an estimate of (1 2n)yp instead of only Therefore, Algorithm 4 outputs 2 so that 2 > (1 - 2n)p 2 &.
We assume for simplicity that f(x) is positively biased, i.e., Ex-N[S(x) > 0. Note that P(x.w)>/|1(p> = b}] (1 2ny) Prx-N(/(x) = b] + 7), where E {+1}. Because f(x) is positively biased, we have that Pr [T = 1] 2 1/2. Denote the random variable Z as 7 = (y 1 1} 1/2. Note that E|Z] (1 - (r) - Note that if p is less than sufficiently small constant, then Z 2 (1/4)(1 2n)) whereas if = 11/2, this expectation does not give any useful information. Note that by standard Chernoff bounds, using O(N log(1/8))
samples, where N a parameter, we can get estimates 2, so that E 2 > 2 /1/N. By letting N = (112)), we can distinguish between the cases that (1 - 2n) (Pr f( 1] 1/2) < 2, in
27

---

which case we have that is close to 1/2, therefore 2 is an estimate of 1 27j that satisfies our requirements. Otherwise, we are in the case where E 2 (1/4) 2n). Therefore, we run the following algorithm: In each round 8, we draw N₂- = -(22 log(log(1/)) /t)/5)) samples, and we check whether Z, VI/N, 2 1/2Z,- If 2, V1/N, 1/22,. we continue, otherwise stop and return 1/22,- which is an effective lower bound of (1 21)). The number of rounds is at most log(1/c), so by union bound, the probability of success is at least 6. After we have estimated an effective lower bound for (1 - 2n). we can get an estimate for the value of p. using the estimator
(recalling that 2 (1 2n)p 2 2).
While Lemma 1.11 is sufficient for ensuring that the number of samples our algorithm draws is not higher than when assuming the knowledge of 1). it is not sufficient for correctly translating the 0-1 error and guaranteeing that is bounded by 17 + O()). However, it is not hard to verify that if we run the Optimization procedure for an estimate f that is within Σe of then the correct 0-1 error bound of r) + Oc)) would follow. This is resolved by simply running the entire optimization component of the algorithm (including all calls to Algorithm(2) for a grid of e-separated values of in the range (0, 1/2). which must contain the true value of 17. It is immediate that this increases the runtime (and the number of hypothesis halfspaces) by factor O(1/e). Yet the same number of samples suffices for the optimization and testing, as all that we require is that at least one hypothesis is constructed using estimates of 1) and / that are sufficiently close to their true values (by order-e and order-e?, respectively, as discussed before).
C Omitted Content from Section 3
C.1 Background on Hermite Polynomials
We define the standard L' norms with respect to the Gaussian measure, i.e., lI = () We denote by L2(N) the vector space of all functions f : Rd + R such While, usually
that Ex-NIf [z)] < co. The usual inner product for this space is (f
one considers the probabilist's or physicist's Hermite polynomials, in this work we define the normal-
ized Hermite polynomial of degree to be Heo(z) 1, Hei (x) x, Hez(2))
_²_1
v2 He;
where by (æ; we denote the probabilist's Hermite polynomial of degree i. The un- normalized Hermite polynomials are defined as (z) exp(==² = (-1)ad' mxp(=s"/2) /2), The normalized Hermite polynomials Hei, Heg. He,,... form a complete orthonormal basis for the single dimensional version of the inner product space defined above. To get an orthonormal basis for L (NV, we multi- V e Na to define the d-variate normalized Hermite polynomial as Hev (x) = I Hc., (x;). The total degree of Hev V = = U/. Given a function f I.?, we compute its Hermite coefficients as f(V)= Ex and express it uniquely as Evena HeV) (x).
(w)
Vil
dzl
C.2
Additional Background on the SQ Model
To define the SQ dimension, we need the following definition.
Definition C.1 (Pairwise Correlation). The pairwise correlation of two distributions with probubility density functions (pdfs) D1, D2 X + R.., with respect to a distribution with pdf D) X - R+, where the support of D contains the supports of Dj and D2, is defined as XD( D1, D2) + ==
StEx Di (2())) (2)22)(z()ddz We say that collection of s distributions D (Di...., Dz) over X is (7, ()-correlated relative to a distribution D if (D, D2)1 S 7 for all i + j. and (D, D2)1 < f
The following notion of dimension effectively characterizes the difficulty of the decision problem.
Definition C.2 (SQ Dimension). For 7, 3 O, a decision problem B(D, D), where D is fixed and D is a family of distributions over X, let 8 be the maximum integer such that there exists D D C D such that D D is (rr, B) -)-corlllteedd relative to D and 1Dn) 2 8. We define the Statistical Query dimension with pairwise correlations (7r, B) of B to be s and denote it by SD(B, 7.
28

---

The connection between SQ dimension and lower bounds is captured by the following lemma. Lemma C.3 (FGR+17). Let B(D, D) be decision problem, where D is the reference distribution and 2 is a class of distributions over X. For , > O, let $ (D(B, 7 .). Any SQ algorithm that
solves B with probability least 2/3 requires at least 7/B queries the (STAT(1/7) oracle.
In order to construct a large set of nearly uncorrelated hypotheses, we need the following fact: Fact C.4 (see, e.g., (DKS17). Let d E Z4. Let 0 < c < 1/2. There exists collection S 2f unit vectors in Rd, such that any pair v, E S, with v * satisfies |v ul < dd11/2ee
C.3 Omitted Details from the Proof of Theorem 3.2
Claim C.5. Lel fx(x) sign(v 1) and fu(x) = sign(u x- () and let be the Hermite coefficient of He,, Then, it holds (x)ov(f((xff(xx)) = Ei= cos' 0 of where is the angle between and
Proof. We first need the following standard fact about the rotations of Hermite polynomials (see, e.g., Fact D.I in (DKS17):
Fact C.6. For 0 R. it holds (x, cos(0) + y sin 0) Ej (i) cos' 0 sin' i-j OHe, (z (z)
We have that E x
[x(((())fx(x)]]
E
[sign(xi (eliixiixxsssseeee ()sign(cos 0xi sin 0x2 - t)]
x1.30
E
Σ (x1))
CHeee 0x1 + sin 0x²) Σ
1=0
E
c.Hee(Xs)
E
(cos 6x, + sin 0x²)
xg--
cos' 0c, (c,Ho,(xx)) )
8 cos' c
E Xi Xm~A
(x1)
Σ
1=0
==0
where in the third equality, we used Fact C.6 and the orthogonality of the Hermite polynomials with respect the Gaussian.
We prove the following. Claim C.7. It holds that E.- (sign( (2) (1x)
Proof. Denote as (2) the non-normalized Hermite polynomial of order d. The Hermite polyno- mials are defined follows:
He) (=))))x((=2) (-1)- ( exp(==3/2) d=xx=''ex(((=))))
d=a
By taking the derivative over (which exists He; is polynomial and exp(-=²/2) is differentiable), we have that (Ho,(z) exp(-22 222 222)2)) = - 12). Therefore, we have that
E [sign( H))) /[ sign(z ())o
JEER
=2 /.- (2)))))))
where we used that SeeR (2) = 0 by the orthogonality of the Hermite Polynomials with respect the Gaussian measure. Furthermore, using that (fex(()))p((=2 He;- (2) we get that
E (sig(( ()){ =2 /. ( (-fee)
-t)G(((t)((())
29

---

By normalizing the Hermite polynomial, we complete the proof of Claim C.7
C.4 Proof of Lemma 3.6
We restate and prove the following lemma.
Lemma C.8. Let Do be product distribution over N x [+1), where Pr Pr = Pr(x.g)~D D. -y = 1] We have X.D D.) S
and x² Do) s (1 (E([((() - Ex]((x)]9).
Proof. We have that
XDo (Dv. Du)
Pr I = (Av, Pr -M= - (00xx((Bv.. (By. Bu) (x.))
(x,0)-,
= -L/D)xx((A,, A.) + (1/(1-)))xN))
We bound each term. Note that by construction Av(x) (T (1 2n) > 03)/(n+
(1 - 2n) (xxx
OH). Note that (xfv(x) > 0} = (f(x) + 1)/2. therefore Av(x)
G(x)(1 + (1
(1 2n)) Ex (fx))) Therefore.
(x( 1 (1 (1-2n) G(x)
(fv(x)
E -.A.f((x))) x-
p
Using the above, we get that (Av, Au) (1 - 2n)/p(B[ffv((tmceee fu(x) - (xf (xf((x))).
Similarly, we get that (Bv. B.) = (1 - 2n) (11 - -p) Ja (x) (x) E [x)))))
remains to bound (Dv, Do). Note that x ( Dn) -XDo ( Dv), hence, 2Dv: Do) S
(1 - 2n)) ([xxx((((x)] (x)x][(xx)(?).
C.5 Reduction of Testing to Learning
Lemma C.9 (Reduction of Testing to Learning). Any algorithm that learns halfspaces with 1/3 RCN noise can be used to solve the decision problem of Theorem 3.2
Proof. Assume that there is algorithm A which given 0 and distribution D with Gaussian X- marginals and corrupted with r = 1/3 random classification noise, outputs hypothesis h with Pr(xa))-D(Me (h(x) # < 17 + c. We can use A to solve the decision problem B3( B(Do, D). Note that
if the distribution were Do. then any hypothesis would get error at least 1j + (1 2n))p (as y is independent of x). If the distribution were one in the set D, then the algorithm for = (1 - 2n)p/2
would give a hypothesis such that Pr(x.y)-Dlh [h(x) * y] 17 + (1 27)p/2. So making one additional query of tolerance (1 2n)p would be able to solve the decision problem. This completes the proof.
C.6 Solving the Decision Problem Efficiently
In this section, we show that our SQ lower bound (Theorem 3.2 for the testing problem is, in fact, tight. We prove the following:
Theorem C.10 (Efficient Algorithm for Testing). Let d N and (0, 1) and let D be distribution
supported on Rd x {=1} such that Dx is the standard Gaussian on Rdd There exists an algorithm that, given N Cc//((e log(1/c)) samples from D, where C 0 is a sufficiently large absolute constant, distinguishes between the following cases with probability of error at most 1/3:
1. is independent of y. where (x,y) D.
2. y is f(x) corrupted with RCN for 1/3, where f is an LTF with Pr(f(x) 1] =
Proof. Let Z yx be the random variable where (x, y) D and let Zn (1/N) x(1) (0)) be the random variables where (x(1), ()),,, for i E [N] are samples drawn from D. The tester works as follows: If | 11 > d/N + ce (1ee, where > 0 is a sufficiently small universal constant, we answer that we are in Case otherwise that we are the Case We prove the correctness of the algorithm below.
30

---

We note that if we are in the Case then Z follows the standard Gaussian distribution. To see that, we show the following simple claim:
Claim C.11. Let x be distributed standard normal and let y supported in {+1} be random variable independent of x, then yx is distributed as standard normal.
Proof. We assume that y 1 with probability 1 1 for some vj E (0, ( Elexp(il.A) be
the characteristic function of A. Then, we have that dyx(t) Ej E(exp(ityx] = = (1-n) Elexp(itx) - (1 17) xx (t) + nt) = Øx (t). where in the last equality we used that
1 E [[(xpp(-ixx]
(t) = xx (t) as the standard normal distribution is symmetric. Therefore, Φyx(t) = (t),,, hence the distribution of yx and x is the same.
From Claim C.I1 we have that Z follows standard normal distribution if we are in Case I and therefore Zn follows (O, I/N).. Hence, | has mean d/N and standard deviation O(v d/N). By Chebyshev's inequality, answer correctly in this case with probability of at least 2/3.
We next analyze the case where Then for any orthogonal to V. we have that the random variables and (x u) are independent as y only depends on x v. Therefore, by Claim Cl.i we have that y(x u) standard normal, therefore yx - is standard (d - dimeenniio normal. Furthermore, note that from Equation that Elyx- v] = O ((e/)))((1/e) and Varlyx v| = (1). Therefore, we can write | |Z l|2 (1/N) d- g? + E²), where g: are distributed standard normal and E² is the contribution due to the noise. We show that with probability at least 2/3, it holds that | 113 2 d/N + ce2 (og(1/c). Note that with probability at least 9/10, we have that E O /log( (1/e]) by Chebyshev's inequality. Due to the independence of the directions, the random variables g, for i = 1...., 1 are independent of E. Hence, conditioned on the event that |E] = ( Laa///oo(/e])]l// we have that |Z, has mean (d - 1)/N + e log(L/e)) and standard deviation O O(Va/N). Hence, again the tester would succeed with probability of least 2/3.
Case Let f(x) = sign(v x + t) be the defining halfspace.
C.7 SQ Algorithm for Learning Halfspaces with RCN with Exponential Number of Queries
Here we show that there exists a query- ineffiinffi SQ algorithm that can be simulated with near- optimal sample complexity of (d/e).
Lemma C.12 (Inefficient SQ Algorithm). There is an SQ algorithm that makes 20()pooylog({/c) queries to VSTAT(1/c)) and learns the class of halfspaces on Rd in the presence of RCN with 17 1/3 with error at most 1) + C.
Proof Sketch. We note that it is always possible to design an exponential query SQ algorithm that achieves the optimal sample complexity of Óddcc) (if we were to simulate it with samples). One approach is to generate an e-cover G that encompasses all hypotheses in IR (with size roughly (1/e)d), )d),, and then utilize the query function ʃ(x, y) (hr (x) - y) 11 (h2(x) o y) for any h1, h2 G. It can be readily observed that the variance of f is at most the probability that hy(x) * h2()), which means that VSTAT(1/e) can distinguish which hypothesis, h or h2g yields smaller error. Note that if we were to simulate this SQ algorithm using samples, we would also need to do a union bound over the of all hypotheses.
D Lower Bound for Low-Degree Polynomial Testing
D.1 Preliminaries: Low-Degree Method
We begin by recording the necessary notation, definitions, and facts. This section mostly fol- lows [BBH+20).
R. Low-Degree Polynomials A function f R: + R² is a polynomial of degree at most l: if can be written in the form
=(z)= = (f) (6(())
31

---

where each f: R - R is polynomial of degree at most k. We allow polynomials to have random coefficients as long as they are independent the input z. When considering list-decodable estimation problems, an algorithm in this model of computation is polynomial f RR - RR where d1 the dimension of each sample, n is the number of samples, d2 the dimension of the output hypotheses, and & is the number of hypotheses returned. On the other hand, [BBH*20) focuses on binary hypothesis testing problems defined in Definition D.2
A degree-k: polynomial test for Definition D.2 is degree-k polynomial f IR + R and threshold t R. The corresponding algorithm consists of evaluating f on the input 21....;2: In and returning Ho if and only if fzz1...... 2n)) >
Definition D.1 (n-sample e e-good distinguisher). We say that the polynomial p. Rdx + R is an n-sample e --distinguishe for the hypothesis testing problem in Definition D.2
E
[(()]
E
E
[p(X)] 2 VVaaa (p(X).
X
We call the advantage of the distinguisher.
Let C be the linear space of polynomials with degree at most k. The best possible advantage is given by the low-degree likelihood ratio
E top
E D
[(X)]
E [(X)]I X-DO
E [(D Mereja
PEC X- 60m Ip (X)15
D
E
where denote D. D Do and the notation f denotes the orthogonal projection of f to C.
Another notation we will use regarding finer notion of degrees is the following: We say that the polynomial f' :n)= Rd + lR has sumplewise degree (r, k) if it is a polynomial, where each monomial uses at most different samples from .1,...,.h and uses degree at most for each of them. In analogy to what was stated for the best degree-k distinguisher, the best distinguisher of samplewise degree (r, k) -achieees advantage
( - 1 Dg" the notation fär.k now means the orthogonal projection of the space of all samplewise degree-(r; k) polynomials with unit norm.
We begin by formally defining hypothesis problem.
Definition D.2 (Hypothesis testing). Let Do be a distribution and S = (Dubues be a set of distributions on X. Let u be a prior distribution on the indices of that family. We are given access (via i.i.d. samples or oracle) to an underlying distribution where one of the two is true:
Ho: The underlying distribution Do-
Hi: First is drawn from p and then the underlying distribution is set to be Du-
We say that a (randomized) algorithm solves the hypothesis testing problem if it succeeds with non-trivial probability (i.e., greater than 0.9).
Definition D.3. Let Do be the joint distribution over the pairs (x, v) Rd x {+1} where x N and y Dolg) independently of x. Let Dy be the joint distribution over pairs (x. E Rd x {+1} where the marginal on y again Do(y) but the conditional distribution Ex(x(1)
of the form
Ay (as in Theorem 3.2 and the conditional distribution Ex(x - 1) is of the form By Define = {Fw)ves, for S being the set of d-dimensional nearly orthogonal vectors from Fact C.ce let the hypothesis testing problem be distinguishing between Do vs. S with prior being the uniform distribution on S.
In this section, we prove the following:
Theorem D.A. Let 0 < c < 1/2. Consider the hypothesis testing problem of Definition D33 For E Ze with d larger than an absolute constant, any n S 1/2 /p² and any even integer / we have that
2
E voup
(E 50, [(k))
S1.
D
32

---

We need the following variant of the statistical dimension from [BBH 20), which is closely related to the hypothesis testing problems considered in this section. Since this is slightly different definition from the statistical dimension (SD) used so far, we will assign the distinct notation (SDA) for it.
Notation For f R - R. g R R and a distribution D, we define the inner product ( (xx
and the norm II/| V(I,))n Definition D.5 (Statistical Dimension). For the hypothesis testing problem of Desinition D.2 we define the statistical dimension SDA(S, n, as follows:
SDA(S, 14, n) = max {
{ E IiD, D.)o. 111 EJ S for all events E s.l. Pr
[E] 2
d²
We will omit writing μ when it is clear from the context.
D.2 Proof of Theorem D.4
To prove Theorem D.4 we first need to bound the SDA of our setting. The following lemma translates the (7, -o-rorrllt of S to a lower bound for the statistical dimension of the hypothesis testing problem. The proof is very similar to that of Corollary 8.28 of [BHH 20] but it is given below for completeness.
< 1/2 and d, m Zy. Consider the hypothesis testing problem of Definition D.3 Then, for any 2 1,
Lemma D.6. Let 0
SDA (D. p (
p(92/22(d013) + 11) +1))) 29.
Proof. The first part is to calculate the correlation of the set S. By Theorem 3.2 we know that the set
is (7, corrrella with p²s)(d)e-112 and B 4p.
We next calculate the SDA according to Definition D.5 We denote by Ey the ratios of the density of
Ey to the density R. Note that the quantity (Eu. E 1 used there is equal to (Eu 1, E, 1).
Let E be event that has Pru.v [E] 1/92. For sufficiently large have that
E [Eu Ex) [88 < min M
18) Pr(F) 1,
1
3 max 0, |r|Pr|E]
1
q²
2(d)2/2-c ) =
p
12d)
Sp
20(ds)
q2 (2/200/013)) +1
where the first inequality uses that Pr(u v Pr|u = v, EJ/ Pr[E] and bounds the numerator
in two different ways: Pr/u v, Bl/ Pr Pr/u= v Pr Pr 1 and Pr/u
v, E Pr[E]= < Pr(E)/Pr(E] =
In BBH+ the following relation between SDA and low-degree likelihood ratio is established. Fact D.7 (Theorem 4.1 of (BBH+20) 20).. Let 'D be a hypothesis testing problem on Rd with respect to null hypothesis Do. Let n, k E N with even. Suppose that for all 0 S n' < n, (D) 2
100 (n/nl)². Then, for all r, || Euwy ( - D S
In Lemma D.6 we set n = 122d)1/2c//p and = v (n/n)) Then, SDA(S, 2
200 (n/n²) 2 (100n/n')* for l < /0 and then we apply the theorem above.
33


Reviews:
[{"review_id": "1Xns9mykwA", "reviewer": "Reviewer_m9mP", "summary": "This paper studies the problem of learning non-homogeneous halfspaces in the presence of Random Classification Noise, where the marginal distribution is standard Gaussian in $d$ dimensions. \n\nOn the upper bound side, this work provides an efficient algorithm that achieves learning an $\\epsilon$-optimal halfspace with sample complexity $\\tilde{O} (\\frac{d}{\\epsilon} +  \\frac{d}{\\max (p,\\epsilon)^2})$ where $p$ is the bias of the target halfspace. The algorithmic idea involves Initialization, Optimization, and final Testing subroutines. The algorithm runs for $O(1/\\epsilon^2)$ guesses of the threshold $t$ and selects the best output halfspace. \n\nOn the lower bound side, this work establishes a nearly matching lower bound that no efficient SQ algorithm can learn a Gaussian halfspace with $\\eta = 1/3$ with less than $\\Omega( \\frac{\\sqrt d}{\\max (p,\\epsilon)^2} )$ samples. ", "questions": "1. Could the main algorithm be modified a bit so that it could directly tell if the true threshold $t$ is significant enough and a constant hypothesis suffices?\n\n2. In Algorithm 1, the Optimization procedure is invoked for $M = O(1/\\epsilon^2)$ times, and $N_2 = \\tilde{O} (\\frac{d}{\\epsilon} )$ samples are drawn in each iteration. Could you please explain a bit more about why the total sample complexity (the dependence on $\\epsilon$) is less than $ \\tilde{O} (\\frac{1}{\\epsilon^3} )$?", "limitations": "There are no obvious limitations to be addressed in my opinion. \n\nOne question that might be interesting to study is if it is possible to attain matching bounds in $d$. ", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. This work studies learning halfspace with RCN, which is a fundamental problem in machine learning theory. Although it has been known that halfspaces are efficiently PAC learnable with RCN, this work refines the sample complexity of the previous works in the Gaussian marginal distribution setting. Moreover, it provides formal evidence that the quadratic dependence on $ \\frac{1}{\\max (p,\\epsilon)}$ is the best one can hope for an efficient algorithm. \n\n2. This paper is technically strong.\n\n3. Along with the formal technical statements and proofs, this work exhibits some valuable informal explanations and implications of the results, which makes it easier for the readers to understand and appreciate the significance of the results in this paper. \n\n4. The main algorithm consists of several subroutines, each coming with a nice explanation and theoretical performance guarantees. ", "weaknesses": "1. It could be nice to have a more comprehensive review of the related works. E.g., how is the sample complexity in this work related to the other papers on learning halfspaces with RCN with comparable settings?\n\n2. It could be good to include in the main algorithm the case where the threshold $t$ is significant. ", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the effort and the positive feedback. Below we respond to the reviewer’s questions in detail. \n\n1. (**Weakness 1**) Regarding the reviewer’s comment on the related works, we have added more detailed comparisons with prior works in the related work section and Appendix A in the final version. Importantly, we remark that there is no other work that provides an efficient algorithm with the optimal sample complexity under Gaussian marginals for **general** halfspaces in the presence of RCN. Most prior works (e.g., [1], [2]) mainly aim to find computationally efficient algorithms for **homogeneous** halfspaces with RCN. In Appendix A, we also compared our work to a very recent paper [3], where the authors studied the setting of RCN corrupted halfspaces with margin assumptions. \n\n2. (**Weakness 2 & Question 1**) Regarding the reviewer’s comment ‘could be good to include … the case where the threshold t is significant’ and the question about determining the case that a constant hypothesis suffices: In the realizable setting (or when $\\eta=O(\\epsilon)$), it is possible to distinguish between these cases by drawing ~$1/\\epsilon$ samples and checking if there are different labels. In the case where $\\eta=\\Omega(1)$, a constant fraction of the samples will have positive and negative labels, therefore this naive approach will not work. In our case for determining whether a constant hypothesis suffices, we point out that this can be done by looking at the value of $p$, instead of $t$. Indeed, as mentioned in lines 204-205, when $p=\\Theta(\\epsilon)$, a constant hypothesis would suffice.\n\n3. (**Question 2**) Regarding the reviewer’s question about why we only need $\\tilde{O}(d/\\epsilon)$ samples for the optimization subroutine rather than $\\tilde{O}(d/\\epsilon^3)$ samples, we would like to clarify that this is because we only draw one batch of samples before we start the optimization subroutine (line 4 in the main algorithm), rather than drawing fresh samples at each iteration. This is because our analysis leverages the uniform convergence of the empirical gradient estimation to the population gradient (under Gaussian), as manifested in Lemma B.6. The total sample complexity consists of the samples needed for the initialization subroutine, which is $\\tilde{O}(d/\\mathrm{max}(p,\\epsilon)^2)$, plus the samples needed for the optimization subroutine, which in total is of the order $\\tilde{O}(d/\\epsilon + d/\\mathrm{max}(p,\\epsilon)^2)$.\n\n4. (**Limitation**) Regarding the dependence on $d$: Our SQ lower bound applies to a natural testing (decision) version of our learning (search) problem (see Definition 3.1), which reduces to learning but is not necessarily equivalent to it. We show that any efficient SQ algorithm for this testing problem requires at least $\\Omega(\\sqrt{d}/\\mathrm{max}(p,\\epsilon)^2)$ sample complexity. Interestingly, we also show a matching upper bound for the testing problem (see Appendix C.6). It remains an interesting open question to develop a stronger lower bound technique that gives the correct dependence on $d$ for the learning problem. We conjecture that the sample complexity of our algorithm is optimal as a function of $d$ as well (within the class of all polynomial-time algorithms).\n\nReferences:\n\n[1] C. Zhang and Y. Li. Improved algorithms for efficient active learning halfspaces with massart and tsybakov noise. In Proceedings of The 34th Conference on Learning Theory, COLT, 2021.\n\n[2] C. Zhang, J. Shen, and P. Awasthi. Efficient active learning of sparse halfspaces with arbitrary bounded noise. In Advances in Neural Information Processing Systems, NeurIPS, 2020.\n\n[3] I. Diakonikolas, J. Diakonikolas, D. M. Kane, P. Wang, and N. Zarifis. Information-computation tradeoffs for learning margin halfspaces with random classification noise. CoRR, abs/2306.16352, 2023. Conference version in COLT’23.\n\n\n"}, {"review_id": "A7JTG5MFf6", "reviewer": "Reviewer_BT2g", "summary": "This paper gives new positive and negative results for the problem of learning general (nonhomogenous) Gaussian halfspaces under the random classification noise (RCN) model. The motivating question is whether there exists a polynomial time algorithm nearly achieving the (known) minimal sample complexity required for solving the problem.\n\nPositive result -- The authors give an efficient algorithm that solves this problem; this algorithm works with a sample complexity that is only off of the known optimal sample complexity by logarithmic factors. Specifically, the runtime of the algorithm is roughly $O(dN/\\varepsilon^2)$, where $N$ (sample complexity) is roughly $O(d/\\varepsilon^2 \\cdot \\log(1/\\delta))$ and $\\varepsilon$ is the target suboptimality. (note that I have omitted the dependences on the noise rate $\\eta$ and the bias $p$ of the target function -- both are probably optimal)\n\nTo obtain the positive result, there are three main algorithmic contributions. The first is an initialization step, which returns a vector whose correlation with the true weight vector is pretty high. The second is an optimization procedure that takes as input a guess for the threshold of the target halfspace and returns a halfspace of low error with that fixed threshold. The third is a procedure that tests several hypotheses and selects the one with the lowest error. \n\nNegative result -- The authors give a Statistical Query (SQ) model lower bound on the sample complexity of any algorithm solving the above problem -- either the statistical queries have to be very accurate, or there need to be an exponential number of queries made in order to recover a linear separator with nontrivial suboptimality. The authors also use a recent result almost equating SQ algorithms and low-degree tests to give a lower bound in the low-degree testing model. The exact statement is a bit technical, so I'll omit it here. It can easily be found in Theorem 1.5.\n\nEDIT 2023-09-01 -- As mentioned in my response, my review stands. Thank you for answering the questions!", "questions": "What do you think are interesting future directions? e.g. do you think it is possible to obtain an even faster algorithm for this problem? If so, do you think extensions of the ideas you presented are likely to work, or do you think a totally different algorithmic approach is necessary?\n\nI probably missed this in the paper, but what is known about this problem when the input distribution is uniform over the vertices of the hypercube (i.e., $\\mathsf{Unif}(\\{\\pm 1\\})^d$? Do the techniques you give in this work readily transfer to this setting? It feels to me as though the Boolean setting is a more basic variant of the problem you study, but I would believe that the two are morally very similar.", "limitations": "Yes", "rating": 7, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 4, "strengths": "The paper almost (up to pesky logarithmic factors) resolves the motivating question of whether the optimal sample complexity can be achieved by an efficient algorithm for this problem. The algorithmic primitives are natural and easy to understand. The problem is pretty fundamental.\n\nFinally, the paper is clearly presented.", "weaknesses": "There are minor typographic issues that can be cleaned up (e.g. spelling mistakes, long math strings, etc.) -- of course this is very minor.\n\nAlthough the optimality of the sample complexity is discussed, there appears to not be as much emphasis on the optimality of the runtime (in particular, the worst case dependence on $\\varepsilon$ in the runtime is $\\varepsilon^{-4}$ -- is this unavoidable?)", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the effort and the positive assessment. \n\nWe address specific comments and questions by the reviewer below.\n\n1. (**Weakness 2**) Regarding the reviewer’s comment ‘...not be as much emphasis on the optimality of the runtime…’: The focus of our work was to develop the first polynomial-time algorithm with near-optimal sample complexity (within the class of computationally efficient algorithms). We believe that a near-linear time algorithm  (i.e., an algorithm with runtime $\\tilde{O}(Nd)$) exists, and it is an interesting direction for future work. The bottleneck to achieve this with our current algorithm is estimating the unknown threshold to the desired accuracy. \n\n2. (**Question 1**) Future directions: A number of interesting future directions remain. An immediate open question is to strengthen the SQ lower bound to match our upper bound as a function of $d$ as well. We believe that our upper bound is tight up to log factors. Another direction concerns generalizing our algorithm to succeed for more general marginal distributions (e.g., isotropic log-concave) with the right sample complexity and understanding information-computation tradeoffs under such more general distributions.\n\n3. (**Question 2**) Uniform Distribution on Hypercube: We start by pointing out that we do not think our methods can be modified to work for the uniform distribution over the hypercube. The main reason is that the anti-concentration property, which played a vital role in our analysis, is no longer possessed under the uniform distribution on the hypercube. Ergo we cannot compute the probability mass of an $\\gamma_m$-width band (as we did in the Gaussian case), hence we are unable to utilize the gradient conditioned on the $\\gamma_m$-width bands. To the best of our knowledge, the only known algorithm for learning halfspaces with RCN over the hypercube involves using a distribution-free (RCN tolerant) PAC learner. As a result, the sample and computational complexity is polynomial, but the degree of the polynomial is potentially not optimal.  \n"}, {"review_id": "bMNfl8DUf0", "reviewer": "Reviewer_QgYm", "summary": "This paper studies the PAC learning complexity of half spaces (or linear threshold functions), when the labels are flipped randomly with some probability $\\eta$.\n\nFor realizable hypothesis classes, it is known that $O(d/\\epsilon)$ samples are enough to learn a halfspace with $\\epsilon$ 0-1 error. Under random classification error, the problem becomes much more challenging. This paper makes two contributions to this problem:\n- First, it presents an efficient algorithm with comparable scaling to $\\tilde O_{\\eta}(d/\\epsilon + d / (\\max(p, \\epsilon))^2 )$.\n- Second, it proves statistical query lower bounds that match the above upper bound under certain regimes of $\\eta$.\n\nThe upper bound involves three subroutines, including a warm start initialization that returns a vector close enough to the target. Second, it issues queries near the threshold, akin to learning a leaky ReLU loss. Lastly, it uses a simple hypothesis testing procedure, which draws a fresh sample and selects a hypothesis with the lowest test error.\n\nTher SQ lowe bound establishes the existence of a large set of distributions whose pariwise correlations are small. The construction builds on prior work of Diakonikolas, Kane and Steward (FOCS'17).", "questions": "- Is the assumption of $p$-biasedness necessary for showing the sample complexity guarantee?\n\n- The comparison with a concurrent work of Diakonikolas et al. (2023) needs to be stated more clearly.\n\n- How critical are the results inherent to Gaussian inputs?", "limitations": "The authors have not discussed the limitations of their work in the main text.\n\nThe paper is of a highly technical nature, so potential negative societal impacts of their work would be limited.", "rating": 5, "confidence": 2, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "S1) The paper makes two contributions to learning halfspaces with random classification noise--this would be a nice contribution to this literature. The results seem solid and technically challenging.\n\nS2) The authors make an effort to explain their results at a high level, which is helpful.", "weaknesses": "W1) My main concern with this paper is the presentation of their technical results; in particular, there is a large number of notations, many of which are not clearly explained or are difficult to follow. This would limit the potential audience of their work within the broader NeurIPS community.\n\nW2) There are some inconsistencies between the statements, in particular, line 10 and line 46, which should be fixed or better explained.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their time and effort in providing feedback. Below, we provide a response to the comments and questions raised by the reviewer.\n\n1. (**Weakness 1**) Regarding the reviewer’s comment: ‘main concern of this paper is the presentation of their technical result…’: We would like to argue that the definitions and relevant notation are already given clearly in the text and the algorithm. For example, the definition of $p$ (bias) and $t$ (threshold) are given in the introduction. In the main algorithm, $M$ is simply a parameter that denotes the total number of grid points we construct in $t$, and $\\gamma_m$ denotes the width of the band on which we conditioned the gradients, as displayed in line 4 of the optimization subroutine. We believe these notations and parameters are necessary for a clear and succinct description of our algorithm.\n\n2. (**Weakness 2**) Regarding the reviewer’s comment: `there are some inconsistencies between the statements, in particular, line 10 and line 46…’, we are afraid that the reviewer might have misunderstood our statements. In line 10, we presented our lower bound for learning general halfspaces under Gaussian with RCN, which is $\\Omega(d^{1/2}/\\mathrm{max}(p,\\epsilon)^2)$; whereas in line 46 we provided the sample complexity of our algorithm, which is $\\tilde{O}(d/\\epsilon + d/\\mathrm{max}(p,\\epsilon)^2)$, i.e., an upper bound for this problem. There is a gap in the dependence of $d$ between our upper bound and lower bound, and we believe it is an interesting question to obtain a matching lower bound as a function of $d$ as well.\n\n3. (**Question 1**) Regarding the reviewer’s first question (assumption on bias $p$): we emphasize that we do not make any assumptions on the bias $p$. The bias $p$ is an unknown parameter of the target halfspace (a number between $0$ to $1$). Our algorithm works for all possible values of $p$ and outputs a halfspace achieving error $\\eta + \\epsilon$. It turns out that the sample complexity of our algorithm depends on $p$. Importantly, our algorithm is adaptive in the sense that it does not need to know $p$ in advance. Finally, we reiterate that the sample complexity of our algorithm is near-optimal as a function of $p$ and $\\epsilon$ within the class of efficient SQ algorithms.\n\n4. (**Question 2**) Regarding the reviewer’s second question: A detailed comparison to the prior work of Diakonikolas et al. (2023) appears in Appendix A. The key points are that neither their algorithm nor their lower bound have any implications to our Gaussian setting. We will move this comparison to the main body in the revised version of the paper.\n\n5. (**Question 3**) Regarding the reviewer’s third question (on Gaussian distribution): We start by pointing out that the Gaussian assumption makes our SQ lower bound stronger, as it holds even for the basic case that the feature vectors are Gaussian distributed. The analysis of our algorithm is currently specific to the Gaussian distribution, as this was the goal of our work (understanding sample-time tradeoffs for learning general halfspaces with RCN in the Gaussian setting). That said, we believe that our algorithmic approach can be modified to give near-optimal algorithms for more general marginal distributions (such as log-concave distributions). We leave this as an interesting extension for future work."}, {"review_id": "0wOHMjLUIC", "reviewer": "Reviewer_2pgi", "summary": "The authors provide an algorithm to learn d-dimensional halfspaces under random classification noise upto error \\eps. The algorithm has time complexity O(dN/\\eps^2), where N is the number of samples; and sample complexity ~ \\tilde{O}(d/\\eps + d/\\eps^2). They also prove a lower bound, in the statistical query model, that requires \\Omega(\\sqrt{d}/\\eps^2) samples, unless the model makes high accuracy queries.", "questions": "Some of the writing in the proofs can be simplified, constants like 0.000098 can be jarring.", "limitations": "Yes, adequately discussed.", "rating": 7, "confidence": 2, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "- The problem of learning half spaces under noise is an important and fundamental problem in machine learning.\n- The results are tight in the statistical query model up to a factor \\sqrt{d}.\n- Clear and lucid technical overview..", "weaknesses": "No significant weaknesses.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the time and effort in providing feedback. We will make sure to polish the final version of the paper and simplify the statements where possible, as suggested.\n"}, {"review_id": "WoWjVs0JyD", "reviewer": "Reviewer_qpWY", "summary": "This paper studies the problem of learning Gaussian half-spaces with random classification noise. Given labeled data $(x,y)\\sim D$ where $x$ follows the standard Gaussian distribution,  a halfspace function $f$  such that $y=f(x)$ with probability $1-\\eta$ and $y=-f(x)$ with probability $\\eta$ and a precision parameter $\\epsilon$. The goal is to construct a halfspace function $h$ such that for  $(x,y)\\sim D$, $h(x)=y$ with probability at least $1-\\eta-\\epsilon$. \n\nThis paper provides lower and upper bounds on the sample/time complexity in the general case where $f$ can be biased: $p=\\min(Pr[f(x)=1],  Pr[f(x)=-1])\\neq 1/2 $. An efficient algorithm is proposed with a sample complexity $\\tilde{O}(d/\\epsilon + d/\\max^2(p,\\epsilon) )$. A lower bound on the sample complexity of $\\Omega(\\sqrt{d}/ \\max^2(p,\\epsilon) )$  is proved for SQ efficient algorithms.", "questions": "Do you think your results could be generalized to (some) distributions $D$ with non Gaussian marginal $D_x$? ", "limitations": "N/A", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "Generalizing the problem of learning Gaussian halfspaces with RCN to not necessarily homogeneous halfspaces is a good contribution. Moreover, the bad term of the sample complexity $\\tilde{O}( d/\\max^2(p,\\epsilon) )$ could not be improved in terms of the dependency in  $\\max(p,\\epsilon)$ thanks to the lower bound proved.\n\nThe algorithm is not a trivial generalization of the one for homogeneous halfspaces with RCN. ", "weaknesses": "One weakness is that the lower bound has does not match the upper bound in terms of the dependency in $d$. ", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the time and effort. We address specific questions/comments by the reviewer below. \n\n1. (**Weakness 1**) Gap between upper and lower bound (as a function of $d$): We refer the reviewer to bullet 4 in the response to reviewer m9mP for a detailed discussion. Our work showed an SQ lower bound of $\\Omega(d^{1/2}/\\mathrm{max}(p,\\epsilon)^2)$ for the testing version of the halfspace learning problem; we also provided a matching upper bound (see Appendix C.6). We conjecture that our learning algorithm attains the optimal sample complexity as a function of $d$ as well (within the class of polynomial time algorithms). It remains an interesting question to develop a lower bound with the correct dependence on $d$ for the learning problem.\n\n2. (**Question 1**) Regarding the reviewer’s question about an extension to non-Gaussian marginals: we believe that our algorithmic approach can be generalized to some log-concave distributions; this is left as an interesting direction for future work. We note that such an extension would require non-trivial extensions to our current analysis. \n\n"}, {"review_id": "2wxjes3tdc", "reviewer": "Reviewer_imug", "summary": "The paper considers the problem of learning $d$-dimensional halfspaces $h(x) = \\mathrm{sign}(w \\cdot x + t)$ over Gaussian marginals under random classification noise (where with probability $\\eta$, a sample is given the incorrect label). While the homogeneous case (where $t = 0$ and the bias $p = \\frac12$) by prior works, the paper focuses on the in-homogenous case where $t$ is unknown. The results give a nearly tight characterization of this regime:\n* Theorem 1.3 shows that there exists a polynomial-time algorithm for learning in-homogeneous halfspaces that uses $N = \\tilde{O}(d / ((1 - \\eta)\\epsilon) + d / \\max(p(1 - 2\\eta), \\epsilon)^2) \\log \\frac1\\delta$ samples. The algorithm (given and analyzed in Section 2 and Appendix B) works as follows:\n  * The Initialization procedure chooses a weight vector $w_0$ and predicts the bias $\\hat{p}$ by iteratively averaging together signed samples until the norm of their average is sufficiently large.\n  * The Optimization procedure locally updates $w_0$ by running Riemannian subgradient descent on a band of inputs on unit sphere of width $\\hat{t}$, for each $\\hat{t}$ belonging in an $\\epsilon$-net over all thresholds $t$.\n  * The Testing procedure identifies which threshold gives the lowest error on a new sample and outputs such a classifier.\n* Theorem 1.5 shows the near-optimality of the upper bound by showing that SQ-learning $p$-biased halfspaces under constant RCN requires either an exponential number of queries or at queries to an oracle of accuracy $d^{1/2 - c} / p^2$, whose dependence on $p$ matches the upper bounds.\n", "questions": "The upper and lower bounds have a substantial gap in $d$. Do the authors believe that this gap could be closed by a future work? And does a similar gap exist in the literature for learning homogeneous halfspaces? \n\nLikewise, do you expect it to be possible to prove a lower bound with a more sensitive dependence on the classification noise $\\eta$? It would be interesting to see if the problem gets much harder as the noise level approaches $\\frac12$.\n\nI don't exactly see why the Optimization procedure is subgradient descent on a leaky ReLU rather than just a scaled ReLU; if it were leaky, shouldn't there be another additive term in the gradient computation multiplied by $\\eta$, rather than just one term in the band multiplied by $(1 - \\eta)$? ", "limitations": "All limitations are well-documented in the assumptions underlying the theoretical results.", "rating": 7, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "The paper is well-written, the bounds are mathematically interesting and have clear proofs, and the matching dependence on $1 / p^2$ in the upper and lower bounds is a strong argument that these bounds are nearly optimal. While I did not review all of the details of the proofs in the appendices, I didn't find any technical red flags. Theorems and lemmas are well-stated and easy to follow.", "weaknesses": "A minor note: The pseudocode for Algorithm 1 could be written in way that makes it more easily digestible for readers. Some helpful details (like the sample complexity for Initialization and Testing) could be included, while terms like $M$ could probably be given asymptotically for simplicity.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their time and effort and their positive assessment. Below we reply to the questions in detail.\n\n1. (**Question 1**) We would like to remark that the optimal lower bound should have a linear dependence on $d$, since even for the simpler realizable case the sample complexity of PAC learning a halfspace has a linear dependence on $d$ (actually, the sample complexity is $\\tilde{O}(d/\\epsilon))$. However, note that a lower bound of $\\Omega(d/\\epsilon + \\sqrt{d}/\\mathrm{max}(\\epsilon,p)^2)$ follows from our results, where the first linear term $d/\\epsilon$ comes from the information-theoretic bound. Therefore it is the second term that should be potentially strengthened from $\\sqrt{d}$ to $d$. Improving our lower bound requires new techniques and it is an interesting future direction. For learning homogeneous halfspaces (with RCN under Gaussian) there is no statistical-computational tradeoff. There is an efficient algorithm using the information-theoretically optimal sample size (within $\\log$ factors). This also follows from our upper bound when $p=1/2$.  The conceptually interesting contribution of our work is that an information-computation gap appears for non-homogeneous halfspaces.\n\n2. (**Question 2**) Regarding question 2 about a lower bound that is more sensitive with $\\eta$: it is known that (even for computationally inefficient algorithms) there exists a sample complexity lower bound of order $\\Omega(d/((1-2\\eta)\\epsilon))$ for RCN (see line 36).\n\n3. (**Question 3**) Regarding question 3, we thank the reviewer for pointing this out. There is a typo in line 5 in the optimization subroutine, which we have fixed in the final version. The correct equation should contain $(1-2\\eta)$ instead of $1-\\eta$.\n\n"}]

Author rebuttal:
We thank all the reviewers for their time and effort in reading and reviewing our paper. In particular, we are encouraged by the positive feedback and that our paper is appreciated by the reviewers in the following aspects: (i) **clear presentation and lucidity** (m9mp, BT2g, QgYm, 2pgi, Imug) (ii) **technical solidness** (m9mp, QgYm), (iii) **significance of solving a fundamental problem in machine learning** (m9mp, BT2g, 2pgi, qpWY).

Meta-review: The paper nearly resolves the problem of learning general halfspaces under random classification noise with Gaussian marginals which is a fundamental problem in learning theory. The work shows a new statistical-computation gap for this problem under the SQ/low-degree testing framework by showing a computational lower bound of $\Omega(\sqrt{d}/\max(p, \epsilon)^2)$ compared to the known information theoretic bound of $\Theta(d/\epsilon)$. The authors further give a nearly matching (up to a $\sqrt{d}$ + log factors) upper bound. 

All reviewers agree that this is a good mathematical contribution and adds to the long line of work on this problem and its variants. Therefore, I recommend accepting the paper. I encourage the authors to include the feedback from the reviewers as they prepare the camera-ready. In particular, it would help to clean up the typos/inconsistencies in theorem statements, improve the exposition of the main algorithm, and move the related work discussion to the main paper.
Decision: Accept (poster)