Reliable Learning of Halfspaces under Gaussian Marginals
Authors: Ilias Diakonikolas
Lisheng Ren
Nikos Zarifis
Venue: NeurIPS 2024 spotlight (2024)
Keywords: reliable learning
agnostic learning
halfspace
proper leaning
statistical query
Primary area: learning_theory

Abstract: We study the problem of PAC learning halfspaces in the 
reliable agnostic model of Kalai et al. (2012).
The reliable PAC model  
captures learning scenarios where one type of error is 
costlier than the others. Our main positive result is a 
new algorithm for reliable learning 
of Gaussian halfspaces on 
$\mathbb{R}^d$ with sample and computational complexity 
$d^{O(\log (\min\{1/\alpha, 1/\epsilon\}))}\min (2^{\log(1/\epsilon)^{O(\log (1/\alpha))}},2^{\mathrm{poly}(1/\epsilon)})$, 
where $\epsilon$ is the excess error and $\alpha$ 
is the bias of the optimal halfspace. We complement our upper bound with 
a Statistical Query lower bound 
suggesting that the $d^{\Omega(\log (1/\alpha))}$ dependence is best possible. 
Conceptually, our results imply a strong computational separation 
between reliable agnostic learning and standard agnostic 
learning of halfspaces in the Gaussian setting.

Reliable Learning of Halfspaces under Gaussian Marginals
Ilias Diakonikolas University of Wisconsin-Madison ilias@cs wisc.edu
Lisheng Ren
University of Wisconsin-Madison Iren290wisc. edu
Nikos Zarifis
University of Wisconsin-Madisee zarifis@visc.ed
Abstract
We study the problem of PAC learning halfspaces in the reliable agnostic model Kalai et al. (2012). The reliable PAC model captures learning scenarios where type of error is costlier than the others. Our main positive result a new algorithm for reliable learning of Gaussian halfspaces on Rd with sample and computational complexity
Ollog(min((//a1//0
(1)) (2poly(1/c),
where is the excess error and a is the bias of the optimal halfspace. We comple- ment our upper bound with Statistical Query lower bound suggesting that the ([log(1/a) dependence is best possible. Conceptually, our results imply strong computational separation between reliable agnostic learning and standard agnostic learning of halfspaces in the Gaussian setting.
1 Introduction
Halfspaces (or Linear Threshold Functions) is the class of functions f : RRd - {+11} of the form f(x) = sign((w x) - t), where w E Idd is called the weight vector and is called the threshold. The problem of learning halfspaces is one of the classical and most well-studied problems in machine learning-goinn back to the Perceptron algorithm [Ros58]-as and has had great impact on many other influential techniques, including SVMs [Vap98] and AdaBoost [FS97].
Here we focus on learning halfspaces from random labeled examples. The computational complexity of this task crucially depends on the choice of the underlying model. For example, in the realizable PAC model (i.e., with clean labels), the problem known be efficiently solvable (see, e.g., (MT94]) via a reduction to linear programming. Unfortunately, this method is quite fragile and breaks down in the presence noisy labels. the noisy setting, the computational complexity of the problem depends the choice of noise model and distributional assumptions. In this work, study the problem cittriiution-speccii PAC learning of halfspaces, with respect to Gaussian marginals, in the reliable agnostic model of [KKM12]. Formally, we have the following definition.
Definition 1.1 ((Positive) Reliable Learning of Gaussian Halfspaces). Let Ha be the class of half- spaces on Rdd, Given 0 < e 1 and i..dd. samples (x, y) from distribution supported on Rd {+1}, where the marginal Dx the standard Gaussian N(0, I), we say that an algorithm reli- ably learns Ha error if the algorithm with high probability outputs hypothesis h RRd {+1)
such that Pr(x.)>D(bb [b(x)] 1 Ay = -1] S 6 and Pr(x.) [b(x) = -1 ^ = 1] s OPT
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

where OPT def (E(() Pr(xx)=D(f(x) = 1Ay 1], with
G(D)= = [f E Ha: Pr
[f(x) = 1Ay = -1 -)) =
(x,))
We say that f argmin JEg(D) Pl(x.g)=D(((xx-- -1Ay 1] is the optimal halfspace distri- bution D and for the conditions above that hypothesis h satisfies, we say that h is e-reliable with respect to Ha on distribution D.
In other words, a (positive) reliable learner makes almost no false positive errors, while also main- taining the best possible false negative error-as compared to any hypothesis with no false positive errors. Note that if there is no hypothesis (in the target class) that makes no false positive errors, then essentially we have no requirement for the false negative error of the returned hypothesis. The algorithm can then simply return the -1 constant hypothesis.
The reliable agnostic PAC model was introduced by [KKM12] as one-sided analogue of the classical agnostic model [Hau92, KSS94), and has since been extensively studied in a range of works; see, e.g., [KKM12, KT14, GKKT17,, DJ19, GKKM20, KK21J. The underlying motivation for this definition comes from learning situations where mistakes of one type (e.g.. false positive) should be avoided at all costs. Typical examples include spam detection-wweeee incorrectly detecting spam emails is much less costly than mislabeling an important email as spam-and detecting network failures-where false negatives may be particularly harmful. Such scenarios motivate the study of reliable learning. which can be viewed as minimizing a loss function for different costs for false positive and false negative errors (see, e.g., [Dom99, ElkÖ1]). In a historical context, reliable learning is related to the Sryyman-Pearsor criterion [NP33] in hypothesis testing, which shows that the optimal strategy to minimize one type of error subject to another type of error being bounded is to threshold the likelihood ratio function. More recently, reliable learning has been shown [KK21] to be equivalent to the PQ-learning model [GKKM20] a recently introduced learning model motivated by covariance shift.
The algorithmic task of agnostic reliable learning can be quite challenging. While reliable learning can be viewed as minimizing a loss function with different cost for false positive and false negative error, in general, such a loss function will result in non-convex optimization problem. As pointed out in [KKM12], distribution-specifiee reliable learning can be efficiently reduced to distribution-speciin agnostic learning (such reduction preserves the marginal distribution). A natural question, serving as a motivation for this work, is whether reliable learning is qualitatively easier computationally- for natural concept classes and halfspaces in particular.
Before we state our contributions, we briefly summarize prior work on agnostically learning Gaussian halfspaces. Recall that, in agnostic learning, the goal is to output a hypothesis with error OPT + e, where OPT is the optimal 0-1 error within the target class. Prior work has essentially characterized the computational complexity of agnostically learning Gaussian halfspaces. Specifically, it is known that the L1 polynomial regression algorithm of [KKMS08] is an agnostic learner with complexity do(1/e)) [DGJ+09, 09, DKN1OJ. Moreover, there is strong evidence that this complexity upper bound tight, both in the Statistical Query (SQ) model [DKZ.20, GGK20, DKPZ21] 1] and under plausible cryptographic assumptions [DKR23, Tie233. It is worth noting that the aforementioned hardness results hold even for the subclass of homogeneous halfspaccs.
Given the aforementioned reduction of reliable learning to agnostic learning [KKM12], one can use -rrrerressonn as a reliable agnostic learner for Gaussian halfspaces, leading to complexity do(1/e)), Prior to this work, this was the best (and only known) reliable halfspace learner. Given the fundamental nature of this problem, it is natural to ask if one can do better for reliable learning.
Is it possible to develop faster algorithmss for reliably learning Gaussian halfspaces compared to agnostic learning?
In this work, provide affirmative answer this question. To formally state our main result, we need the notion of the bias of a Boolean function.
Definition 1.2 (Bias of Boolean Function). We define the bias a E [0, of Id + {+1}} under
the Gaussian distribution as a = a(h) def (PTxx-xx, = 1], Prx = -1]).
The main result of this paper is encapsulated in the following theorem:

---

Theorem 1.3 (Main Result). Let D be joint distribution of (x.v) supported on R x {#1} with marginal Dx Na and let a be the bias of the optimal halfspace on dis- tribution D (with respect to Desinition 1.1). There is an algorithm that uses N (0 min
220ol((100) many samples from D. runs in poly(N, d) time, and with high probability returns a hypothesis l((x) = sign( (w, x) - i) that is e-reliable with respect to Ha. Moreover, for < ax2,, any SQ algorithm for the problem requires complexity ((lo)))/a))
For more detailed theorem statements of our upper and lower bounds, see Appendix B for the algorithmic result and Appendix C for the SQ hardness result.
Theorem 1.3 gives a significantly more efficient algorithm (in terms of both sample complexity and computational complexity) for reliably learning Gaussian halfspaces, compared to agnostic learning- Specifically, as long as a > 0 is a universal constant, the overall complexity is polynomial in d and muasi-polynomial in 1/c- as opposed to dPaly(1/e) in the agnostic setting. While the complexity of our algorithm (namely, the multiplicative factor that is independent of d) increases the optimal halfspace becomes more biased, it is always bounded above by the complexity of agnostic learning.
Finally, we note that our algorithm also applies to the fully reliable learning model [KKM12], since one can easily reduce the fully reliable learning to positive reliable and negative reliable learning (as observed in [KKM12]).
1.1 Overview of Techniques
Instead of directly considering the optimal halfspace for a distribution D (as defined in Definition 1.1), we introduce the following definition as a relaxation.
Definition 1.4 (Reliability Condition). We say that a distribution D supported on X x { satisfies the reliability condition with respect to f X + {=1} if (f. = +1 -1] = 0.
Notice that h being e-reliable on distribution D is equivalent to h having better false negative error compared with any f such that satisfies the reliability condition with respect to f (instead of compared with the optimal halfspace). At the same time, given any fixed f, such definition allows the adversary to arbitrarily corrupt negative labels, thus allowing for more manageable analysis.
We start with a brief overview of our SQ lower bound construction, followed by the high-level idea enabling nearly matching algorithm.
SQ Lower Bound As follows from Definition 1.4 and the subsequent discussion, the adversary in reliable learning can arbitrarily corrupt the negative labels. We leverage this idea to construct an instance where the corruption level suffices to match many moments, meaning that labels y uncorrelated with any polynomial of degree at most log(1/a) To prove this, we construct an (infinite) feasibility Linear Program (LP) with the following properties: if the LP is feasible, there exists an instance for which no low-degree polynomial correlates with the labels; see Lemma 3.3. To show the existence of such an instance, we leverage a technique from [DKPZ21] that exploits (an infinite generalization of) LP duality. Specifically, we show that it is possible to add noise to the labels whose uncorrupted value is negative so that all low-degree moments are uncorrelated with the observed labels y. This implies that no algorithm that relies on low-degree polynomials can succeed for reliable learning. This allows us show that SQ algorithms fail they do not use queries with tolerance at most 1/ (log((()/a) or exponentially many queries.
Reliable Learning Algorithm As discussed in the previous paragraph, an adversary can arbitrarily corrupt the negative labels which can make various algorithmic approaches fail. In more detail, the adversary can corrupt (loog (1/x:) moments; that is, any SQ algorithm needs to rely on higher-order moment information. One of the main difficulties of this setting is that there may exist weight vectors
w, w' with ||w - w w/| 2 (1) while at the same time the 0-1 error of w and w' is nearly the same. This might suggest that approach can verify that the algorithm decreases the angle between the current weight vector and the optimal vector. To overcome this obstacle, we develop an algorithm that performs a random walk over a "low-dimensional" subspace. To establish the correctness of our
3

---

algorithm, we prove that at some point during its execution, the algorithm will find a weight vector sufficiently close to the optimal vector.
To show that such a low-dimensional subspace exists, we proceed as follows: We first prove that there exists non-trivial polynomial p of degree (1log(1/o) that correlates with the negative labels (by the term nontrivial, we are referring to the requirement that we cannot use the constant polynomial, as this trivially correlates with the labels); see Claim B.5. This implies that the low-degree moment lensors, i.e., ((x.y)><D (I = - for some A between and (llog(/a)), correlate non- trivially with (w*)e*, where w' is the target weight vector. Thus, we can use these moment tensors to construct a low-dimensional subspace. We leverage the structure of the problem, namely that the (observed) negative labels are uncorrupted, to show that the correlation is in fact almost constant. As a consequence, this allows us to construct a subspace whose dimension depends only on the degree of the polynomial p (which is O(log(1/a)) and the desired excess error
We then proceed as follows: in each round, as long as the current solution w is not optimal, i.e. there are negative samples on the region {x E R w X t 2 0}, our algorithm conditions on a thin strip, projects the points x on the orthogonal complement of w. and reapplies the above structure result. This leads (with constant probability) to an increase in the correlation between w and w". Assuming that the correlation increased by /3 in each round with probability at least 1/3, we roughly need at most 1/3 successful updates. Therefore, if we run our algorithm for 31/8 steps, it is guaranteed that with probability at least 1/3 we will find vector almost parallel to w".
Prior Algorithmic Techniques Roughly speaking, prior techniques for reliable learning relied on some variant of Ly-regression. In that sense, our algorithmic approach departs from a direct polynomial approximation. Concretely, for distribution reliable learning, the algorithm from [KT14) uses a one-sided variant of L1 regression-where instead approximating the target function in ln norm, they use the hinge loss instead. For distribution-ssecifie (and Gaussian in particular) reliable learning of halfspaces, the only previous approach uses the reduction of [KKM12] to agnostic learning. While our algorithm also leverages polynomial approximation, our approach employs significantly diffcrent ideas and we believe it provides a novel perspective for this problem.
Technical Comparison with Prior Work Our algorithm shares similarities with the algorithm of [DKK*22] for learning Gaussian halfspaces with Massart noise (a weaker semi-random noise model). Both algorithms perform a random walk in order to converge to the target halfpace. Having said so, our algorithm is fundamentally different than theirs for the following reasons. The algorithm of [DKK* + 22] partitions Rd into sufficiently angles and searches in each one of them for direction to update the current hypothesis at random. Our algorithm instead conditions on y = -1, which are the points that are uncorrupted, and uses the guarantee (that we establish) that the first 2(log (1/a) moments of the distribution (conditioned y = 11 correlate with the unknown optimal hypothesis. This leads to an algorithm with significantly faster runtime.
Our SQ lower bound leverages techniques from [DKP721]. Essentially, we formulate a linear program to construct a noise function that makes all low-degree polynomials uncorrelated with the labels y. This condition suffices to show that no SQ algorithm can solve the problem without relying on higher moments. To prove the existence of such a noise function, we use (a generalization of) LP duality of an infinite LP, which provides the necessary conditions for the existence of such a function.
1.2 Related Work
This work is part of the broader research program of characterizing the efficient Icarnability of natural concept classes with respect to challenging noise models. The complexity of this gen- eral learning task depends on the underlying class, the distributional assumptions and the choice of noise model. A long line of prior work has made substantial progress in this direction for the class of halfspaces under Gaussians (and other natural distributions), and for both semi- random [ABHUI5, DKTZ20a, ZSA20, DKTZ20b, DKK+ 20, -2b, D and adversarial noise IKKMS08, KOS08, KLS09, ABL17, DKS18, DKTZ20e, 2 DKTZ22). An arguably surprising conceptual implication of our results is that the complexity of reliable learning for Gaussian halfspaces is qualitatively closer to the semi-random case.

---

1.3 Preliminaries
We use lowercase boldface letters for vectors and capitalized boldface letters for matrices and tensors. We use y) ) for the inner product between x,y Rd. For x, E IR,, we use (x) def (x.a)s for the projection of x on the s direction. Similarly, we use projus (x) = =x proj, (x) for the projection of x on the orthogonal complement of s. Additionally, let x IV)im()) be the projection of x on the subspace V and reparameterized on (Rdim(V). More precisely, let By E RRdxdm((V) be the matrix whose columns form an (arbitrary) orthonormal basis for the subspace V, and let xV def TB For p 1 and E Rd, use ||x def (Ei=1 (x,P) to denote the f--norm of x. For matrix or tensor T, we denote by || the Frobenius norm of T.
T>ill
We use Nu to denote the standard normal distribution (0, I), where O is the d-dimensional zero vector and I is the d x d identity matrix. We use x ~ D to denote a random variable with distribution D. For a random variable (resp. distribution D), we use Px (resp. PD) to denote the probability density function or probability mass function of the random variable x (resp. distribution D). We also use 4. IR + [0, 1] denote the edf function of NG. We use to denote the indicator function.
For a boolean function h Rd - {+1} and a distribution D supported on Rd x {=1}. we use def R2 (h; D) def Pr(x.))>(h((>> = 1Ay + 1] (resp. R_ (h; D) PF(x,))n/M(x)- = 1Ay + -1) to denote the false positive (resp. false negative) 0-1 error.
2 Algorithm for Reliably Learning Gaussian Halfspaces
In this section, we describe and analyze our algorithm establishing Theorem 1.3. Due to space limitations, some proof's have been deferred to Appendix B. For convenience, we will assume that a (the bias of the optimal halfspacce is known to the algorithm and that the excess error satisfies without loss of generality for the following reasons: First, one
S a/3. These assumptions can efficiently reduce the unknown a case to the case that a is known, by guessing the value of a. Second, if is large, there is straightforward algorithm for the problem (simply output the best constant hypothesis).
Notation: We the notation H22 for the set of all LTFs on Id whose bias is equal to Given the above assumptions, it suffices for us to give a reliable learning algorithm for HC instead of Ha.
The high-level idea of the algorithm is as follows. Without loss of generality, we assume that there exists an a- e-biased halfspace that correctly classifies all the points with label -1 -insence otherwise the algorithm can just return the hypothesis h(x) =11.
Let f(x) = sign( (w*, . x) - t²') be the optimal halfspace and let w be our current guess of w". Assuming that w" is not sufficiently close to and the hypothesis that classifies all the points as negative is not optimal, we show that there exists a low-degree polynomial of the form p( (W, x)) with correlation at least 2-0((" with the negative labels. By leveraging this structural result, we use a spectral algorithm to find a direction v that is non-trivially correlated with proj (w") with at least some constant probability.
Unfortunately, is not easy verify whether (v, proj (w*)) }} non-irivial. However, conditioned on the algorithm always getting a v that has good correlation, we show that it only takes at most (og(1/e)0(t)) o(r?) steps to get sufficiently close to w* Therefore, repeating this process 21og(1/s)0(0) many times will eventually find accurate approximation to w".
The structure of this section as follows: In Section 2.1, we give our algorithm for finding a good direction. Section 2.2 describes and analyzes our random walk procedure.
2.1 Finding a Non-Trivial Direction
Here we present an algorithm that finds a direction that correlates non-trivially with the unknown optimal vector. We first show that there exists a zero-mean (log(1 ([loo(1/))))a) /d))ree polynomial that
sign-matches the optimal hypothesis. Furthermore, using the fact that the optimal hypothesis always
5

---

correctly guesses the sign of the negative points, this gives us that the polynomial correlates with the negative (clean) points. Using this intuition, our algorithm estimates the first ([log(//a)) moments of the distribution Dx conditioned on y = -1. This guarantees that at least one moment correlates with the optimal hypothesis, as a linear combination of the moments generates the sign-matching polynomial. Then, by taking random vector that lies in the high-influence directions (which form low-dimensional subspace), we guarantee that with constant probability, this vector correlates well with the unknown optimal vector. The main result of the section is the following.
Proposition 2.1. Let D be a joint distribution of (x, y) supported on Rd x {+1} with marginal Dx Na and c E (0, 1). Suppose D satisfies the reliability condition with respect to f(x)
sign((w",x) 1*) with t* = =0 =0 (Vlog(1/e) and Pr(x.y)=D''' =-1 2
Then there is an
algorithm that draws N = =d0(0') samples, has poly(N) runtime, and with probability at least (11) returns unit vector v such that "r)"") 2 max(log(1/e) max)(oog((()-00))),000 ((1).
We start by showing that for any distribution satisfying the reliability condition with respect to some f (x) sign( (ww", x) - -t",, there exists degree- zero-mean polynomial of the form p((w" x)) that has correlation at least 2 2-0((=3) Pr(x.y)=DDy -1] with the labels.
Lemma 2.2 (Correlation with an Orthonormal Polynomial), Let D be a joint distribution of (xx y) supported Red {+1] } with marginal Dx = NNa- Suppose D satisfies the reliability condition with respect to fxx sign( (w", x) +²). Then there exists polynomial
RR + R of degree at most k = O(t +1) such that (2~A((((2) = O, Ex-Ni (v²())()) = 1 and E(x.)) pl (w", x)]]
2 2-0((²)) Pr(x.)>DDy== =- -1].
Proof Sketch of Lemma 2.2. Note that since is a zero-mean polynomial with respect to Dx, we have that E(x,y)=Dl pl (w", x))] = -2 (x.x)) [y p( (w", x)] Then, using the fact that the distribution D satisfies the reliability condition, the statement boils down to showing that for any
c-mass inside the interval oo], the expectation of p on this mass is at least 2 2-0(t"?) To prove this statement, it suffices to construct a polynomial p that is non-negative on [t" oo] and such that the </ e/2-tail of p in that interval is at least 2-0(="), To achieve this, we show that the sign-matching polynomial used in [DKK* + 22] meets our purpose.
Our algorithm uses the following normalized Hermite tensor.
Definition 2.3 (Hermite Tensor). For E N and x E R", we define the k-th Hermite tensor as
HH (x) )s..a.....
1
Σ
X
VI!
Partitions P [k] ta.bjEP size and 2
{CtE
Given that there is such a polynomial, we show that if we take flattened version of the Chow- parameter tensors (which turns them into matrices) and look at the space spanned by their top singular vectors, then a non-trivial fraction of w* must lie inside this subspace. We prove the following lemma, which is similar to Lemma 5,10 in [DKK* 22]. See Appendix B for the proof.
Lemma 2.4. Let D be the joint distribution of (x, v) supported on I& x {+11} with marginal Dx = Na- Let p: + T. be a univariate, mean zero and unil variance polynomial of degree k such that for some unit vector v² E Rd it holds E(x,)))- = -1)p((v,, x))] 2 T for some E (0. 1]. Let Tm be an approximation of the order-m Chow-paramens
tensor T E(xx)))(( =
-m) such that "T" || S <T((AVk). Denote by Vm the subspace spanned by the left singular vectors of flattened T'm whose singular values are greater than T/ r/(4/k). Moreover, denote
by V the union of Vi,... ... Vv. Then, for = Pr(x.g)~Dly = -1], we have that
//2 and 2. ||projy (v*) 2 (T/ (Vh log(1 (0g(1/))))))) 11)
1. dim(V) = 00000(12200000
By Lemma 2.4, taking random unit vector v in V will give us v*) 2 [I*)ojy(v"))// (Vm. We are ready to prove Proposition 2. For the algorithm pscudocode, see Appendix B.

---

Proof Sketch of Proposition 2.1. The idea is that the empirical estimate T obtained using d'(maxit" 11) log(1/o)/é many samples will satisfy | T ability. Then, by Lemma 2.2 and Lemma 2.4, if we take v to be a random unit vector in V, with constant probability we will have (v, w*) = log(1/e) log(L/e))-0('" -(()), For (v, w") = =0(1) the proof relies on a different version of Lemma 2.4.
<</(Av)) with high prob-
2.2 Random Walk to Update Current Guess
We now describe how we use Proposition 2.1 to construct an algorithm for our learning problem. Let w be the current guess for w" For convenience, we assume that (w, w") = (2(1/Vd). Let D' be the distribution of x- conditioned on x E B, where B {x E Rd (w, x) -t- 2 0}. We next show that the x-marginals of D' are standard Gaussian and that D' satisfies the reliability condition
with respect to the halfspace hxx) = sign( bign((w',a x) t') with w' = w Iw and |t'| S |t%|
Lemma 2.5. Let D be the joint distribution of (x, y) supported on I& x {+1} with marginal
Dx Na and e E 1). Suppose D satisfies the reliability condition with respect to fxx) sign((w" (w", .x) x)-1"), Suppose that h(x) sign( (ww, x) - -1) with (w, w²) )²) >> O and 1-1" E 10,
does not satisfy Ro (D) S 6/2. Let B = {x E Rd (w,x) -t 1 0} and D' be the distribution of
(x'1)= (x" v) given X E B, then
1. D' has marginal distribution Dx= = Na-1.
2. D' satisfies the reliability condition with respect to li(x)) = sign((w', - 1'), where w' w Tw /l|w> 1w 1|2 and |t'] I \ and
3. Pr y = -1] 2 e/2.
Proof Sketch of Lemma 2.5. Item 1 follows by definition. For Item 2, we consider two cases: t" >> O: and to S 0. For the case t S O, we prove that the distribution D' satisfies the reliability condition with respect to N((x)= = =sign( (ign((w', x)). where w' = w*1 /|| [|2. For the case t" >> 0, we prove that the distribution D' satisfies the reliability condition with respect to h lx(x) sign((w', xx) - ('), where w' w² Lw /I[w* Lw 12 and 1' t*. Then Item follows from the fact that h does not satisfy R (D) e/2.
By Lemma 2.5, given any current guess w such that h(x) = sign( sign((w.xx (w.x)- -1) does not satisfy R4 (h; D) S s/2,, the corresponding distribution D' satisfies the reliability condition with respect to h and Pr(x.y)~>r [y/ = -1] 2 e/2. Therefore, D' satisfies the assumptions of Proposition 2.1. So, if we apply the algorithm in Proposition 2.1, we will with probability at least 22(1) get a unit vector v such that (v, w) 0 and (v. w*) = log((1))) log(1/))-0()")
The following fact shows that by updating our current guess in the direction of v with appropriate step size, we can get an updated guess with increased correlation with w
Fact 2.6 (Correlation Improvement, Lemma 5.13 [DKK Fix unit vectors v", . Rd Let Rd such that (u, v*) 2 c, (u, v) 0 and ||ll| I with >> 0. Then, for v = v++uu with = c/2, we have that (v', v*) N (v, + 22/2.
[|v+Aunlaa'
Notice that because |lrro (w w )l is unknown, we cannot always choose the optimal step size X. Instead, we will use the same À to sufficiently many update steps such that after that many updates, we are certain that [|proj (w") < 3A. We then take the new step size Aupdate X/2 and repeat this process, until w and w are sufficiently close to each other.
We are now ready to describe our algorithm (Algorithm 1) and prove its correctness.
Notice that given that we know the bias a, t must be either ( t - (a)). For convenience, we assume that t = x- (a). To account for the case that t = - + (a), we can simply run Algorithm twice and pick the output halfspace with the smallest / value (or even run different efficient algorithm, since L & O as explained in Appendix B). For convenience, we also assume min (e) (e) 22pol(11())
21og(1 2log(1/e) (lw0///)))))
To account for the other case, we can
simply initialize the step size el for sufficiently large constant instead of Ç = log(1/e)-et*
7

---

A more detailed version of Algorithm is deferred to Appendix B.
Input: E (0,1), a E (0, 1/2) and samples access to a joint distribution D of (x, y) supported Rd {+1} with x- marginal Dx .Na.
Output: h(x) = sign( (w, x) t) that e-reliable with respect to the class H2--
1. Check if (r(xx))=DD = -1] v e/2 (with sufficiently small constant failure probability). If so, return the +1 constant hypothesis. Set the initial step size Ç log(1/e))at where is sufficiently large universal constant and Φ (a).
2. Initialize to be random unit vector in R.. Let the update step size À Ç and repeat the following process until À $ e/100.
(a) Use samples from to check if the hypothesis 1((x) sign( x) 1) satisfies R+ (h; D) S c/2. If so, go to Step (3). (b) With 1/2 probability, let w the distribution of (x w., y) for (x.v)
w. Let B (x E Rd (w, x) - 1 0}, and let D'
given B. Use the algorithm of Proposi-
tion 2.1 D' to find unit vector such that (v, w) 0 and V. [|pro] [[pro] (w
proj (ww) 2
Then update w as follows: Wupdate
tv
1
(c) Repeat Steps (2a) and (2b) c/C² times, where e a sufficiently large universal constant,
with the same step size X. After that, update the new step size Aupdate X/2.
3. Check if h(x) sign( (w, x) t) satisfies R4 (h; D) S e/2. 2. If so, return h and terminate.
Repeat Step (2) 2//5" many times where is sufficiently large constant.
Algorithm 1: Reliably Learning General Halfspaces with Gaussian Marginals.
Proof Sketch of the algorithmic part of Theorem 1.3. Let f(x) = sign((w", x) - t²) be the optimal halfspace with a bias. We need to show that with high probability Algorithm returns a hypothesis f(xx) = sign( (w, x) - such that R4 (h; D) S and R R_ D) S R- D);
To do so, it suffices to show that R4 (h; D) S e; given (h; D) S S, R. (h; D) S (): follows from our choice of t. For convenience, Step (2a) (otherwise, we are done). We can also assume that the subroutine Proposition 2.1 always succeeds since the algorithm repeats Step (2) sufficiently many times. Given the above conditions, using Fact 2.6, one can show that each time after c/C² many updates in Step (2h), we must have [[proj w w 1|2 < 3A. Therefore, when we have À S e/100, then ||proj w" l| S 3e/100, which implies R4 (h: D) 6/2.
assume h never satisfies
c/2 in
L
3 Nearly Matching SQ Lower Bound
In this section, we establish the SQ hardness result of Theorem 1.3. Due to space limitations, some proofs have been deferred to Appendix C.
Proof Overview To establish our SQ lower bound for reliable learning, we first prove an SQ lower bound for a natural decision version of reliably learning a- LTFs. We define the following decision problem over distributions.
Definition 3.1 (Decision Problem over Distributions). Let be a fixed distribution and 'D be distribution family. We denote by BBD, D) the decision problem in which the input distribution D' is promised to satisfy either (a) D' D or (b) D' D, and the goal is to distinguish the two cases with high probability.
We show that given SQ access to a joint distribution D of (x. supported on TRd x (+1) with marginal Dx= NO, I), it is hard solve the problem B(D, D) with the following distributions.
(a) Null hypothesis: D is the distribution so that y with probability 1/2 independent of x.
8

---

(b) Alternative hypothesis: D E D, where D is a family of distributions such that for any distribution D D. there exists an o-biased LTF f such that R4 (f: O.
In order to construct such family of distributions D, we start by constructing joint distribution D of (z: y) over R x { such that the marginal distribution of z W and the conditional distributions Iyy- and
-1 both match many moments with the standard Gaussian M1 Moreover, there a probability mass on the positive side of the marginal distribution
that is purely associated with y 1 (i.e.. (( 2 2 cl 1 where ② (1 a)). We then embed this distribution D along hidden direction inside the joint distribution of (x, y) on R {#1} construct family of hard-to-distinguish distributions using the "hidden-direction" framework developed in [DKS17] and enhanced in [DKPZ21, DKRS23].
We can now proceed with the details of the proof. We start by defining the pairwise correlation between distributions.
Definition 3.2 (Pairwise Correlation). The pairwise correlation two distributions with pdfs D1, D2
Rd F with respect a distribution with density D IRd + RT,, where the support of D def contains the support of D1 and D2, defined as XD (D,, D2) Sae Di (x))))(x))/((x))))
1.
Furthermore, the x-squared divergence of D1 D is defined as (D D)
def xD(D1, D1).
In particular, the framework in [DKS17] allows us to construct family of 2 distributions on R x {+1} whose pairwise correlation is d d-Q(() where n is the number of matching moments D' has with the standard Gaussian. Then, using standard SQ dimension techniques, this gives an SQ lower bound for the distinguishing problem. After that, we reduce the distinguishing problem to the problem of reliably learning a-biased LTFs under Gaussian marginals with additive error a/3.
In order to construct such a distribution D' of (z, y) supported on x (+1), we reparameterize (( [2] as g(). For a function g : IR + R, we use ||l1|p = E [lg(t) for its Lp norm. We let I (R) denote the set of all functions g R + R that have finite -n-oo..
We use linear programming over one-dimensional functions in L L'( space to establish the existence of such a function. Specifically, we show the following:
Lemma 3.3. For any sufficiently large n N, there exists a function g -R+ [-1, +1] such that g satisfies the following properties:
(i) g(2) for all 2 2 c, where c= x 1- -1-222 /4), and
(ii) EL-Ni = 0 for all le E [n].
Proof Sketch of Lemma 3.3. We let Pa denote the of all polynomials p I of degree most n and let L (R) denote the set of all nonnegative functions in (R). Then, using linear programming, will get the following primal: find such that
E L E [p(=)g(=)]
=0,
Vp E Pa
E (o()))()) eni,
vh. E (R) 2] (> cHI,,
E 19(2 (z)) ||]| M>
HA E L (R)
Then, using manfnite-dimensinn LP duality, we get that the above primal is feasible if and only there is no polynomial of degree such that E.-N, ([ S c)] < E.-x, (p(() 2 c)).
Using Gaussian hypercontractivity (see [Bog98, Nel73]), one show that for every polynomial p and e E RR, it holds
1/2
E [[(x)]]] 2-33" E [P(())]] M
Pr 12 2 c) =~\i
From our choice of the parameter e, we have that Pr [a 2 cl 3- 2n /4; thus, Ne [Ix())]) Eg-Mn [Ip())]], which is a contradiction. Therefore, such a polynomial p cannot exist.
<
0

---

We have proven the existence of the function g in Lemma 3.3. Now, we construct joint distribution of (2,3) on R x { such that E[y|2] is exactly 9. as we discussed the proof outline. For joint distribution D of (z, y) supported on X x {+1}, we will use D+ to denote the conditional distribution
given y = I; and D_ for the distribution of x given y = -1.
Lemma 3.4. For any sufficiently large N, there exists distribution D lR {+1} such that for (z, v) ~ D:
(i) the marginal distribution D= =Ni
(ii) E(s z'] for all z' 2 (1- 3-2n /4);
(iii) E(a.)~Dlul = 0 and E ((..))~D(22) ((aw)~Dl2* 1 == -| -B(aa)-D y= = for all
E [n]:
(iv) (D.,))))) = 0(1).
Proof Sketch for Lemma 3.4. The properties here directly follow from the properties of g.
Using the framework introduced in [DKSI7, DKPZ21], we can construct set of alternative hypothe- sis distributions D {Dv nearly-orthogonal vectors and the marginal distribution of each Dy on direction v is the distribution D in Lemma 3.4. This effectively embeds the distribution in hidden direction v. The size of the family 'D is exponential in d, and the distributions in it have small pairwise correlations. The details of D are deferred to Appendix C. Now, we are ready to give a proof sketch for the SQ hardness part of our main theorem Theorem 1.3.
V) on R x {+1}, where V a set of exponentially many pairwise
the set of distributions discussed above. We also let Duull be the joint distribution of (x, y) such that x ~ Na and y Bern (0rn(11/) independent of x. Then, using standard SQ dimension techniques, one can show that any SQ algorithm that solves (DD, Duult) requires either queries of tolerance at most d- 2 or makes at least 200) queries. By reducing the decision problem B(D, D to reliably learning a-biased LTFs with e < ox/3 accuracy, we get the lower bound part of the statement in Theorem 1.3.
Proof Sketch of the SQ hardness part of Theorem 1.3. Let
Conclusions and Open Problems
In this paper. we study the problem of learning halfspaces under Gaussian marginals in the reliable learning model. Our main contribution is the design of the first efficient learner for this task whose complexity beats the complexity of agnostically learning this concept class. Moreover, we provide rigorous evidence, via an SQ lower bound, that no fully-polynomial time algorithm exists for general halfspaces. The obvious open question whether the dependence on the complexity of our algorithm can be improved. Specifically, is it possible to design a reliable learner with complexity Is it possible to obtain similarly efficient reliable learners under more general marginal distributions (c.g., strongly log log-concave or discrete distributions)? More broadly, would be interesting to characterize the computational separation between (distribution-se) -specciiiiiissiiiccc reliable and agnostic learning for other natural concept classes.
(o)) pol) poly(1/e)) ?
10

---

Acknowledgements
ID was supported in part by NSF Medium Award CCF-2107079 and an H.I. Romnes Faculty Fellowship. LR was supported in part by NSF Medium Award CCF-2107079, NZ was supported in part by NSF Medium Award CCF-2107079.
References
[ABHU15] P. Awasthi, M. F. Balcan, N. 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.
[ABL17] P. Awasthi, M. Balcan, and M. Long. The power of localization for efficiently learning linear separators with noise. J. ACM, 63(6):50:1-50:2) 2017.
[Bog98] 1998.
Bogachev. Gaussian measures. Mathematical surveys and monographs, vol. 62,
[DG]+09] I. Diakonikolas, P. Gopalan, R. Jaiswal, Servedio, and E. Viola. Bounded indepen- dence fools halfspaces. In Proc. 50th IEEE Symposium Foundations of Computer Science (FOCS), pages 171-180, 2009.
[DJ19] A. Durgin and B. Juba. Hardness of improper one-sided learning of conjunctions for all uniformly falsifiable esps. In Algorithmic Learning Theory, ALT, volume 98 of Proceedings of Machine Learning Research, pages 369-382, 2019.
[DKK+20] I.
Diakonikolas, M. Kane, Kontonis, C. Tzamos, and N. Zarifis. polynomial time algorithm for learning halfspaces with Tsybakov noise. arXiv, 2020.
[DKK* + 21a] I. Diakonikolas, D. M. Kane, V. Kontonis, C. Tzamos, and N. Zarifis. Agnostic proper learning of halfspaces under gaussian marginals. In Proceedings of The 34th Conference on Learning Theory, COLT, 2021.
[DKK (xxx*11b) 21b] I. Diakonikolas, D. M. Kane, V. Kontonis, C. Tzamos, and N. Zarifis. Efficiently learning halfspaces with Tsybakov noise. STOC, 2021.
[DKK I. Diakonikolas, D. M. Kane, V. Kontonis, C. Tzamos, and N. Zarifis. Learning general halfspaces with general Massart noise under the gaussian distribution. STOC '22: 54th Annual ACM SIGACT Symposium on Theory of Computing, Rome, Italy, June 20 24, 2022, pages
ACM, 2022.
[DKN10] I. Diakonikolas, D. M. Kane, and J. Nelson. Bounded independence fools degree-2 threshold functions. In FOCS, pages 11-20, 2010.
[DKPZ21] I. Diakonikolas, M. Kane, T. Pittas, and Zarifis. The optimality of polynomial regression for agnostic learning under gaussian marginals, In Proceedings of The 34th Conference on Learning Theory, COLT, 2021.
[DKR23] I. Diakonikolas, D. M. Kane, and L. Ren. Near-optimal cryptographic hardness of agnostically learning halfspaces and relu regression under gaussian marginals. In International Conference on Machine Learning, ICML, volume 202 of Proceedings of Machine Learning Research, pages 7922-7938, 2023.
[DKRS23] I. Diakonikolas, D. Kane, L. Ren, and Y. Sun. SQ lower bounds for non non- gaussian component analysis with weaker assumptions. In Advances in Neural Information Processing Systems 36: Annual Conference on Neural Information Processing Systems 2023, NeurIPS 2023, 2023.
[DKS17] I. Diakonikolas, D. M. Kane, and A. Stewart. Statistical query lower bounds for robust estimation of dige-dimensional gaussians and gaussian mixtures. In 2017 IEEE 58th Annual Symposium on Foundations of Computer Science (FOCS), pages 73-84, 2017.
11

---

[DKS18] I. 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.
[DKTZ20a] I. Diakonikolas, V. Kontonis, C. Tzamos, and N. Zarifis. Learning halfspaces with Massart noise under structured distributions. In Conference on Learning Theory, COLT, 2020.
[DKTZ20b] I. Diakonikolas, V. Kontonis, C. Tzamos, and N. Zarifis. Learning halfspaces with Tsybakov noise. arXiv, 2020.
[DKTZ20c] I. Diakonikolas, V. Kontonis, C. Tzamos, and N. Zarifis. Non-convex SGD learns halfspaces with adversarial label noise. In Advances in Neural Information Processing Systems, Neur/PS, 2020.
[DKTZ22] I. Diakonikolas, V. Kontonis, C. Tzamos, and N. Zarifis. Learning general halfspaces with adversarial label noise via online gradient descent. In International Conference Machine Learning, ICML 2022, volume 162 of Proceedings of Machine Learning Research, pages 5118-5141. PMLR, 2022.
[DK720] I. Diakonikolas, D. M. Kane, and N. Zarifis. Near-optimal SQ lower bounds for agnostically learning halfspaces and ReLUs under Gaussian marginals. In Advances in Neural Information Processing Systems, NeurIPS, 2020.
[Dom99] P. M. Domingos. Metacost: A general method for making classifiers cost-sensitive. In Proceedings of the Fifth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pages 155-164, 1999.
[EIk01] C. Elkan, The foundations of cost-sensitive learning. In Proceedings of the Seventeenth International Joint Conference on Artificial Intelligence, IJCAL, pages 973-978, 2001.
[Fan68] K. Fan. On infinite systems of linear inequalities. Journal of Mathematical Analysis and Applications, 21(3):475 448, 1968.
[FGR+ 17] V. Feldman, E. Grigorescu, L. Reyzin, S. Vempala, and Y. Xiao. Statistical algorithms and a lower bound for detecting planted cliques. J. ACM, 64(2):8:1-8:77 2017.
[FS97] Y. Freund and R. E. Schapire. A deeisionnttheoetti generalization of on-line learning and an application to boosting. Journal of computer and system sciences, 55(1):119~ 139, 1997.
[GGK20] S. Goel, A. Gollakota, and A. R. Klivans. Statistical-query lower bounds via functional gradients. In Advances in Neural Information Processing Systems, NeurIPS, 2020.
[GKKM20] S. Goldwasser, A. T. Kalai, Y. Kalai, and O. Montasser. Beyond perturbations: Learning guarantees with arbitrary adversarial test examples. In Advances in Neural Information Processing Systems, NeurIPS, 2020.
[GKKT17] S. Goell, V. Kanade, A. R. Klivans, and J. Thaler. Reliably learning the relu in polyno- mial time. In Proceedings of the 30th Conference on Learning Theory, COLT 2017, volume 65 of Proceedings of Machine Learning Research, pages 1004-1042, 2017.
[Hau92] D. Haussler. Decision theoretic generalizations of the PAC model for neural net and other learning applications. Information and Computation, 100:78- 150, 1992.
[KK21] A. T. Kalai and V. Kanade. Efficient learning with arbitrary covariate shift. In Algorith- mic Learning Theory, 2021, volume 132 of Proceedings of Machine Learning Research, pages 850-864, 2021.
[KKM12] A. T. Kalai, V. Kanade, and Y. Mansour. Reliable agnostic learning. J. Comput. Syst. Sei., 78(5): 140:-14899999 2012.
[KMMS08] A. Kalai, A. Klivans, Y. Mansour, and R. Servedio. Agnostically learning halfspaces. SIAM Journal Computing, -77) 2008. Special issue for FOCS 2005.
12

---

[KLS09] A. Klivans, P. Long, and R. Servedio. Learning Halfspaces with Malicious Noise. Journal of Machine Learning Research, 10:2715-2740, 2009.
[KOS08] Klivans, R. O'Donnell, and R. Servedio. Learning geometric concepts via Gaussian surface area. In Proc. 49th IEEE Symposium on Foundations of Computer Science (FOCS), pages 541-550, Philadelphia, Pennsylvania, 2008.
[KSS94] M. Kearns, R. Schapire, and L. Sellie. Toward Efficient Agnostic Learning. Machine Learning, 11223):115-144 1994.
[KT14] V. Kanade and Thaler. crarbutioo-independded reliable learning. In Proceedings of The 27th Conference on Learning Theory, COLT, volume 35 of JMLR Workshop and Conference Proceedings, pages 3-24, 2014.
[MT94] W. Maass and G. Turan. How fast can a threshold gate learn? In Hanson, Drastal, and R. Rivest, editors, Computational Learning Theory and Natural Learning Systems, pages 381-414. MIT Press, 1994.
[Ne173] Nelson. The free markoff field. Journal of Functional Analysis, 12(2):11-2277, 1973.
[NP33] J. Neyman and S. Pearson. On the problem of the most efficient tests for statistical hypotheses. Trans. R. So. Lond. Ser. A Contain. Pap. Math. Phys. Character, 231:281- 337, 1933.
[Ros58] F. Rosenblatt. The Perceptron: probabilistic model for information storage and organization in the brain. Psychological Review,
1958.
[Tie23] S. Tiegel. Hardness of agnostically learning halfspaces from worst-case lattice problems. The Thirty Sixth Annual Conference on Learning Theory, COLT, volume 195 of Proceedings of Machine Learning Research, pages 3029-3064, 2023.
[Vap98] V. Vapnik. Statistical learning theory. Wiley, 1998.
[ZSA20] C. Zhang, J. Shen, and P. Awasthi. Efficient active learning of sparse halfspaces with arbitrary bounded noise. Advances in Neural Information Processing Systems, NeurlPS, 2020.
13

---

Appendix
Organization The supplementary material structured as follows: Appendix includes additional preliminaries. Appendix B includes the omitted proofs from Section 2. Finally, Appendix C includes the omitted proofs from Section 3.
A Additional Preliminaries
We use gd-1 to denote the d-dimensional unit sphere, i.e., gd-1 def fx E Rd: |x|12 1}.
Basics of the SQ Model In order to give SQ lower bound for reliable learning, we first present the basics of the SQ model. We define the pairwise correlation, which is used for the SQ lower bound. Definition A.1 (Pairwise Correlation). The pairwise correlation of two distributions with probability density function D1, D2 IR + R2 with respect to distribution with density D IR - R+, where the support of D contains the support of Dj and D2, is defined as XD i1, D2) def Ja D2(x) ((xxxx 1, Furthermore, the X-squared divergence of DI to D is defined def
as D) = Di)
We require the following definitions and lemmata from [FGR 17] connecting pairwise correlation and SQ lower bounds.
Definition A.2. We say that set of distribution D = {DI,... D&} over Rd is (7, -ooreelltt relative to a distribution D if XD (D(,;; D2) S 7 for all i + j, and (D(D;, D2) S 3 for j. Definition A.3 (Statistical Query Dimension). For 3, >> 0, a decision problem B(D, D), where D is a fixed distrihution and 'D is a family of distribution, let 8 be the maximum integer such that there exists a finite set of distributions DD S D such that DD (7, (7,3))correlaated relative to and (Dol 2 The Statistical Query dimension with pairwise correlations (y, B) of B is defined to be and denoted by s = SD(B, 71, 3).
Lemma A.4. Let B(D, D) be a decision problem, where D is the reference distribution and D is a class of distribution. For 7,8 0, let (D(B,r,3) For any of 0, any SQ algorithmn for B requires queries of tolerance al most v7 +7 or makes at least 87 (3 - 7) queries.
Basics of Hermite Polynomials We require the following definitions used in our work.
Definition A.S (Normalized Hermite Polynomial). For k E N, we define the k-th probabilist's Hermite polynomials Heg R R (t)(t) (- f2, 8 normalized Hermite polynomial h2 R as hz(t) = Hex (t)/Vkl.
ef We define the k-th
diz
Furthermore, we use multivariate Hermite polynomials the form of Hermite tensors (as the entries in the Hermite tensors are re-scaled multivariate Hermite polynomials). We define the Hermite tensor as follows.
Definition A.6 (Hermite Tensor), For l E N and x E Rd, we define the k-th Hermite tensor as
(Hg ) (x.).)
Σ
(-In
X1. {ctE
Vk!
Partitions P of [k] {a.DJEP
and 2
We also point out that fully reliable learning (see [KKM12] for the definition) reduces to one-sided reliable learning (Definition 1.1). The proof is implicit in the proof of Theorem 3 in [KKM12] and we include it here for completeness.
Fact A.7. For a joint distribution D of (x. y) supported on X x {+1}, let h4 : + {+1}
(resp. h- : X - {+1}) be a hypothesis that e/4-reliable with respect to the concept class C on distribution D for positive labels (resp. for negalive labels). Lei hypothesis h be defined as h(x) if h (x) h- = 1, l((x) = -1 if = hx(x) = and h((x) =? otherwise. Then close to the best fully reliable sandwich hypothesis for C. on distribution D.
14

---

Proof Sketch. We first show that R+ D), (h; D) S E. Notice that
R4 (h;
Pr [h(x) = 11y -1] م Pr (x
(x)== =1 se.
(x,0)~D
The same holds for negative labels.
To show that Prix.))-(higg [h(x) =?] is c-suboptimal, assume (for the purpose of contradiction) that there an h such that R2 (V: D), R- (M'; D) S and Pr(xc))=D(!(( =?] Pr(x,)>>(h(
?] - c. Notice that
Pr [h(x) =?]
(x.9)rDD
= Pr 1h+ (x) A h (x) = -1]+ Pr Mh+ (x)+xx)= - AI =1] (x.,))m-
(x,1)mn
<1 Pr 11 (x) =1] Pr 1h- (x) =-1]+ Pr [h+ hh -1]
(x,))=D
(x.n)~~
(x.8))n
21
Pr (x)x)) =1] Pr ih- (x) -11 tc/2.
(x.g)>D
(x,0)~D)
Thus,
1+ = 1] + Pr hh- (x) = $1| Pr [h(x) =? + c/2. (x.y)>
Pr
(1)
(x.y)~=
(x.y)~D
Then, define 44 X + {=1} as (x)
(x()(()(()))))) = and (x) - otherwise (h' is defined
similarly). We get Pr Pr(x.))-D( 144 ( (x) = 1] Pr (r(xx))>Dlhh (x) = -1] = Pr(x,)) (t' (x) =?].
Using Equation (I) and Pr Prix.)) D (x) =?] Pr P [h(x) =?] - E, we get
Pr (x) = =1]- Pr h (x) 11] < Pr 14
[x(x)) (x)
1| Pr I (x) (x)= -1/-
(x..))m
(x.g)>D
(x,y)~~)
(x,y)~
Therefore, either Pr(x.)~D h+ (x) = 1] < Pr (x(x))~ M4 (x) = 1] c/4 or
Pr (x) = 11] Pr [h' = 11] c/4. (x,y)~
(x.g)~
Thus, either h4 or h- is not c/-subbopiiall. This gives a contradiction.
B Omitted Proofs from Section 2
We define the bias of function h Rd - {+1) min min [h(x) = 1], Prxmss(M((x) =-1). and define Hg to be the set of all LTFss whose bias is a. Let f = argmin a (T:D) R-(;; D) be the optimal reliable hypothesis and a be the bias of f.
B.1 Reliably Learning Halfspaces with Gaussian Marginals when 2a
We show that for the problem in Theorem 1.3, in the case of e 2 2a, the algorithm can just return one of the constant hypotheses. Let h4 (resp. h be the +1 (resp. -1) constant hypothesis.
Fact B.1. For the problem defined in Theorem 1.3, the case where e 2 2a can be efficiently solved by returning h4 if R4 (h4; D) < 3e/4 and returning h otherwise.
Proof. When the algorithm returns h4, it is easy to see that h4 satisfies the reliable learning require- ment in Definition 1. So we only consider the case that the algorithm returns h...
Given the algorithm returns fr,,, either there is an bibsee LTF f such that (f: = 0 or none of the bibieeed LTFs f satisfies R. (f: D) 0. For the case that none of the a-biased LTFs f satisfies (f; D) = 0, is easy to see h_ is a valid answer from the definition of Definition I.1. For the case that there is a-biased LTF f such that R, (f, D) O, since the algorithm did not return h4. it must be the case that Pr
= -1] > 3c/4 > a. Therefore, we have -1] = 1 - a. Thus, we get (h_, D) and R (h_, D) S R (f, D) + a. This shows h_ is reliable with respect to all biased LTFs. This completes the proof.
Prx~N,
O
15

---

B.2 Reliably Learning Halfspaces with Gaussian Marginals: Case of Unknown a
Here we establish our main result:
Theorem B.2 (Main Algorithmic Result), Let 6 E (0, and let be a joint distribution of (x. y) supported on Rd [+13 with marginal Dx = No. Let f argmin JeHa R4 R+(DDD)= R-(5; D) be the optimal halfspace and a be its bias which is unknown. Then there is algorithu that uses N = d'Ologgmiin (0//// 1/4,1/e)) min (o0oes/))) 22pol((1c)) many samples from D, runs in poly(N, d, 1/c) time and with high probability returns a hypothesis h(x) = sign( (w, x) t) that is e-reliable with respect to the class of LTFs.
To prove Theorem B.2, we need to use the algorithm in the following lemma as a black box. The lemma shows that if the optimal halfspace f satisfies PFx-NN = =-1] S 1/2, then the problem can be solved efficiently.
Lemma B.3. Let D be the joint distribution of (x, y) supported on R x {+ with marginal
Dx = No and 10. Suppose the optimal halfspace f argmin R4 (4:D))= R_ R-(f; D) satisfies Prx~Nal[(x) = -1] S 1/2. Then there an algorithm that reliably learns LTFs on D using N = O(d/6") many samples and poly (N, d) running time.
Proof. The algorithm is the following:
1. First check if (r( ly -1] with sufficiently small constant failure probability. If so, return the +1 constant hypothesis.
Otherwise, draw m = (d/c)² many samples 5 = ((x, V1). (Xm- ymm) conditioned on y 1. By Step the sampling efficiency here is 32(e) with high probability.
Solve the following semidefinite program for w' and t':
minimize such that (w',x) - 1' 50, v(x,8) E
6'
||w/l2 $1
Return the hypothesis h(x)= sign((w, x) t), where w/ /l/l///ll and f1/l[w'|lz.
Let f(x) sign( (wx x) t") be the optimal hypothesis. We prove that h(x) sign((w: x) t) is such that (4; I E and R_ (h; D) < D) Since consistent with all the negative samples, we have t* < O. Notice that w and ta is a feasible solution to the above program: therefore, t' St and must have t = t'/ll w [| t' < t", which implies that Pr(xx))D(h(() 1) 2 (r(x)))D(/(xx-- = 11. Therefore,
have (h; D) < From the assumption that Prx-walf(
-1] < 1/2,
(h; Pr 1] Pr yy =1-=1M 1 =1]
(x,))~
(x.y)~
Pr [y =1] Pr [1(x) 1] +R+ D)
(x.))~D)
(x.I)~D)
< Pr [y [1]]] Pr [f(x) +c
+
(x,y)~D
(x.y)>
R- (ʃ: D) +e.
This completes the proof.
We now prove Theorem B.2.
Proof of Theorem B.2. The algorithm is the following:
Run the algorithm in Lemma B.3 with é' </2. If the output hypothesis satisfies (h: D) S with sufficiently small constant failure probability, then output h and terminate.
16

---

2. Set a 1/20-/1100 and run the algorithm in Theorem B.4 with c' = c/2. the output hypothesis h satisfies R4, (h; D) with a sufficiently small constant failure probability, then output h and terminate. Otherwise, update as a - e 1/100. Repeat Step 2 until the algorithm terminates.
Let f = argminn A R1 (I:D)=0 R- (1; D); be the optimal halfspace and aj be its bias which unknown. Suppose the algorithm terminates. Let a be the bias of the output hypothesis It is easy to see that R+ (h; D) S with high probability; therefore, it only remains to show R (h: D) I (J: D) + Notice that if Prx~Na in Step 1. Therefore, without loss of generality, we assume Prx-Na (x) Theorem B.4, it is easy to see that a 2 aj e/100 since given any a S a, Step is guaranteed to terminate. Therefore, we have
-1] S 1/2, the algorithm will terminate
-1] 2 1/2. Then, by
Pr [h(x) -1 -1 1 a +0/100 Pr [[(x) - +e/100 x~.Va
x~
Thus,
Rh Pr [y = 1] Pr /|| = 1 A -xxx==11 =1 (x.y)~
(x.1)~
Pr [y| 1] Pr [1(x) 1] RR;(1:11 D)
(x.y)~D
(x.))~D
I Pr [1 Pr [f(x) =1] +c
(x,y)=D) (x,y)~
(): +E
This completes the proof.
B.3 Reliably Learning Halfspaces with Gaussian Marginals for the Case S <x/2
For convenience, we assume that a known. This can be assumed without loss of generality as we discussed in Theorem B.2.
We show the following:
Theorem B.4. Lel e E (0,1/2), (0, and let D be joint distribution of (x,y) supported on Id {=1} with marginal Dx NNa- Assume that there is half- space in HD that is reliable with respect to D. Then, there is an algorithm that uses N (000ogmmi((//////0000 min (2log(1/e)00xx1//) 200ly(1/e)) many samples from D, runs in poly d, 1/e) time and with high probability returns hypothesis h(x) sign( (w. x) f) that e-reliable with respect to the class of H
Below we provide the omitted proofs from Section 2.
B.4 Proof of Lemma 2.2
Notice that for any polynomial p such that Ez-MV [p(=)] = 0, we have
E
[pp((W", x))] = - E
[1 11)p(('',
(x.y)~
(x.y)~
Therefore, it suffices for us to show that there is a zero mean and unit variance polynomial such that
E
11y==1) x))] = 2 o(1*2)
Pr (x.g)>>
= -1]
(x,y)>
Here we will consider the sign-matching polynomial from [DKK 22], which satisfies the following properties:
Claim B.5. Let b T.. and b 2 4. There exists a zero mean and unit variance polynomial p R R of degree k = O(b)) such that
The sign of p(2) matches sign(z - b). i.e. sign(p(2)) = sign(z - b).
2. For any S b/2, we have (p(z) = -2 -0())
17

---

Proof. We consider the polynomial defined as:
p(z) - =[(=== g(6) r(b) (z)
where ((2) = 23 r(2) 2* (2k: 1)!! and &s is sufficiently large odd integer such that 2 S vk S 4 max( 1). We then take p(=) f(=)/ v En (n]].
For convenience, we first note that from Stirling's s approximation for m E Z",
(m/2) < (2m 1)!! < (2m)
To prove that (pgn(p(z)) sign(= b), we first show that 2(
(b) < 0. Since g(b) 2 0, we just need
to show r(b) S O. Notice r(b)- = 12 (2k - 1!!!, since 2|b] S v and (2k 1)!! 2 (k/2)*. thus
r(b) - (Vk/2) (k/2)* & O. Therefore, considering g(z) = 33ر and r(z) = 22 (2k 1)!!,
<(b) r(b) r(z)
x(z) = q(=)
must be monotone increasing for = 2 b and p(z) must also be monotone increasing for = 2 b. Notice that pbb) 0; therefore, p(z) > 0 for b. To show p(z) 0 for < bb, we prove it for the cases
g(b) I 0 and the definition of g(2) 2 E [-b, +b) and z < -b. For 2 E [-b, +b), notice that due to r(b) and r(z).
g(b) r()) < (b))
((6)
x==) = a(=)
r(b) r0) < p(b) 0.
r(b)
Then, for < bb. we show that p(z) is monotone increasing. Notice that the derivative (z) = 222h-1 100-22233 13=* k 2 2 ) for S b O, this is positive if and only if 3z*
2.2()
0. If we can < 0. The condition
F(D
show by 2 -bb(b)/r(b), then it is immediate that for any S -b, 3z 2 9(6b
r()
b* 2 (b))(((b can be further simplified to (2k - 1)!1/12* 2 5/3. Then considering 2b < Vh and (2k- 1)!! 2 (k/2)* &,, we have
2kk 1)!1/62* (1//2)/
2
thus the condition holds. Therefore, f'(x) 0 for < -b and p(z) must be monotone increasing for z < -b. Then combined with the condition p( b(-b) < 0, which is implied from the previous case (= E (-b, we have p(z) < 0 for < -b.
For the Property 2, we show that p(2) = 2 (kk) for E [0, 6/2], = [-b/2, 2 E [-b, - 6/2] and = E -b] separately. For E [0, 6/2] notice that p(z) is convex for = É [0, 6]: therefore.
suffices to show p(0) = 2 Note that p(0) = Jक (2k 1)!!/ V Eu-As (()), and we
9(b) r(b) 2 83h/ maxx("* (2k 1)!!) 2 (/k) Therefore, since Ea-Ai [p)(w)] S (O(K)))3 we have p(0) 2 2-0() This completes the proof of the case 2 E [0, 8/2). For the case 2 E [-b/2, 0j. it immediately follows from the fact that (p(-z) 2 Ip(2] by the definition. For the case [- -/. we have p(z) < (p(b) (b/2)3²) /// Eu-Ni (2(u) < 2 O(k), Then, the case 2 E oc, -6 immediately follows from the fact that p(z) is monotone increasing in this interval.
have
This completes the proof of Property 2.
Given Claim B.5, we let p be the polynomial in Claim B.5 with b = max Then, given that D satisfics the reliability condition with respect to f. it is easy to see the polynomial .x) satisfies the requirements. This completes the proof of Lemma 2.2.
B.5 Proof of Lemma 2.4
We start by bounding the Frobenius norm of Tm, i.e., || Notice that by taking p: - R to
be any degree-m polynomial such that Ex-N, [p())] 0 and (o(x)(p(()" = 1, then | maxp E(x.))x [y
(1 = - -))](x)]. We leverage the following standard fact about the concentration of polynomials lemma known as -eeni-r inequality simply Gaussian hypercontractivity.
18

---

Fact B.6 (Hypercontractivity Concentration Inequality [Bog98, Nel73]). Consider any m-degree, unit variance polynomial p F - I with respect Na. Then, for any
[((x) Eip(u)] 2 S e² (c
Pr. X
where è is an absolute constant.
Using Fact B.6, have that for any zero mean and unit variance polynomial p,
[y -))p(())] - L. min (7,62e- (cap)um) da
E (x.9)~
[y (1y==1)pp(x -1)((x)] _ E
(x.aeD
=0 (1(()0((1/))m//)
Therefore,
| || = 0 (> (og(1/>))m//)
To prove the Property 1, since
| || I T + T/(4Vk) - O (7/1g(11/))m/) + +4(4/)))
Tm / (T/VR) 2 = 0(2 log( m//////+ + 1) many singular vectors with
there can be at most
singular values greater than 7/(4vk). Therefore, dim V) is at most O7²² log(1/>)"" 1).
For the Property 2, suppose [projy(v")ll = (7/ (viry log(1 log(1/7)4//2) then we have for any m,
||v TTm 2 S ||
T la + (44//)
| plroprrjyy (v (v')l2 7 / (rooovl(v))))) +T S (5/8)T/Vk.
However, since E ((x,)>bD((() = - 11)p((v x))] = Σm= a.v* T 0m-1 2 r for some of
...+ of = 1, we know there must be an m such that
6m 2T/Vk.
Therefore, we can write
|Tm 1a 2 || T T T/
(3/4////
which contradicts ||v TT 112 S (5/8)5/v/ This completes the proof.
B.6 Proof of Proposition 2.1
The pseudocode for the algorithm establishing Proposition 2.1 given Algorithm 2.
We can now prove Proposition 2.1.
Proof of Proposition 2.1.
We first introduce the following fact about learning Chow tensors.
Fact B.7, Fix m L4, and e, 8 E (0, 1). Let D be distribution on Rd x [=1] with standard normal
marginals. There is an algorithm that with N domm) log(1/5)/e² samples and poly N) runtime, outputs an approximation Tm of the order-m Chow-parameler lensor T E b H (x))
such that with probability 1 - 5, it holds T T r S
Proof. Let Tm be the empirical estimation of T using N dm log(1/8)/e² for sufficiently large universal constant We start by showing ((x,)>D [l [1 d Notice that,
[ [x)
| E x-RR
[[ (x)
(x.g)>>
(x.g)~
(x
Notice that each entry of H (x) must be some ax)(x) where a E [0, and lx() is a unit variance Hermite polynomial. Therefore, E [ (x)] S dm and thus Exx,)> [ [x)] <
dm
Using the above, we have
E
[I) TT
E (x) - T < dd
(x
(x,y)~D
Then, applying Chebyshev's inequality gives
mm T S.
19

---

Input: Sample access to a joint distribution of (x, y) supported on I& x {+1} with the marginal Dx = =Na. Let 8 E (0, 1) and suppose D satisfies the reliability condition with respect to LTF
f(x) = sign( (ww x) -²) with t* = =0 (log(1/e) and Pr(x.y)~nlB = -11 2
Output: With probability at least 22)1, the algorithm outputs unit vector v such that (v, w") =
max (log(1/))-0(=), (00)
1. Let e1 be a sufficiently large universal constant and cg be a sufficiently large universal constant depending on c₁. Let S be a set N desmax(e" log many samples from D. For m 1, "..",,0 ,,tt"" with 1/2 probability, take
T
E (x.1)~us
[1 -I)
to be the empirical Chow-tensor negative samples. Otherwise, take
T E [H)""(()) (x.9)muS
to be the empirical Chow-tensor on all samples. Let be the empirical estimation of Prox.))=D(y/ 1] with error most c/100 with a sufficiently small constant failure probability.
2. Take T pdxdd= be the flattened version of T and let Vn be the subspace spanned by the left singular vectors of I' whose singular values are greater than at ? where is sufficiently large constant. Let V be the union of all Vn and output to be random unit vector chosen from V.
Algorithm 2: Finding a Direction with High Correlation.
We prove Proposition 2.1 for two cases: (a) max(log(1()--Ot)) ,,C(()) = -(t" and (b)
(aa(loo(14)--0(1))) ( ((1)) = o(1), We first prove Case (a) as the other case is similar. For Case (a), suffices for us prove that (v, w*) log -l happens with R(11) probability given the algorithm chooses T (x.,), (1 = - 1)HH" (which happens with 1/2 probability). T [| <</(4v/) Then from Lemma 2.2 and Lemma 2.4, if we take v to be a random vector in V, we will with constant probability have,
Let c2t²2 and 7/(4vk) 2- 2-ott By Fact B.7, have || T
2 ( (VF7looogg()))11
w-)
Ω 1 (188(11))))441222
dim(V)
= (1(ggg(1/)) -(1 -3/2) x/
Since Pr(x.)~Dly = 11 2 c, we have y = (2c). Also, considering k = (max ( .1)) =
O (log(1/e)). we get (v, w*) log(1/))-O(t')) 0
For Case (b), the proof remains the same except we take T'm Ex H (x)] and use fact below instead of Lemma 2.4.
Fact B.8 (Lemma 5.10 in IDKK+221] Let D be the joint distribution of (x, supported on Rd x (+1} with the marginal Dx No. Letp R + R. be univariate, mean zero, unit variance polynomial of degree k such that for some unit vector v* E I&d it holds E(x,)) (up((v", x)]] 2 for some E (0, 1). Let Tm be approximation of the order-m Chow-parameter tensor T ((x,)>=D (y (x)] such that '| Tm |F S </(Ak/)) Denote by Vma the subspace spanned by the left singular vectors of flattened Tm whose singular values are greater than 1ainn//(44 /44k/) Moreover, denote by V the union of Vi,..., Vs. Then have that
1. dim(V) S 4k/7², and
20

---

Ilprojv (v*)l22 2 7/ (4V%).
Then the same argument will give (v, w*) e(1) The above described algorithm most N do("9)/² samples and poly (N,1/e) 1/e) runtime. This completes the proof of Proposition 2.1.
B.7 Proof of Lemma 2.5
Item 1 follows from the definition of D' and the fact that D has marginal distribution Dx =
For proving Item 2, consider two cases: The first case is when t* > 0 and the second one when t S.O. O. For the case t* 2 0, we prove that the distribution D' satisfies the reliability condition with respect to hx(x) = sign( (w', x)) where w' = -- /Il [ -w 122 Notice that for any (x, y) such
that x E and h (x [xxww] 1, we have
f(x) sign( (w" ,x) -²)
sign( (proj (w") x) (projw (w"), - 1*)
sign( ((w" w , w) + (projw (w" ),))) - -("),
where Lw- Lw x-w) 2 0 since 1' N'(x) = sign((vg (ww Lw x /||l -w (12) 2 0. Then we have
f(x) 2 sign((proj,, (w"), ), -t")
sign((projw, (projw (w")/ //llpr//jww///// (w") 112, - t" /1pprroww (Mn)(w
sign( (w, x) - -t))
(2)
sign( (w.x) x) - t)
h(x) +1,
where Inequality (2) follows from the fact that ww) ) > O, [[proj (w")lla E (0, 1] and t" S 0. Since D satisfies the reliability condition with respect to have that must be the y +1. Therefore, D' satisfies the reliability condition with respect to /i"
For the case t* O, we prove that the distribution D' satisfies the reliability condition with respect to h hx( = sign( (ww, x) t') where w' = w= /||w>_w|/ and t' = t². Notice that for any (x, v)
such that x E B and h'(x' w) = 1, we have
[(x) sign( ((w", , x) -t")
(proj www x)) + (projw w',x] t*)
sign (Iw" w "12 x) - ||w" 1w "12t" 1tt""-0 + (projw w x) - - l|w"
w "I12)t")
where ||w~_w|le (l/'ww')) ) I 1120" 2 since 1((x) = +1. Then we have
f(x) sign((projw. wi, x) (1 (1))))
sign
|| -ww.-wil3 (w,x) (1 1| (ww_w||22))
l| w ((w,x) - -t)) h((x)= =1
sign
where the second equation follows from (w, w*) > 0 and the third one follows from t* > 0. Since D satisfies the reliability condition with respect f. we have that it must be the case y +1. Therefore, D' satisfies the reliability condition with respect to h',
For proving Item 3, notice that R4 (h; D) 2 c/2 implies
Pr by = 1] = R4 (h; D)/ (x' (
Pr (x E B) 2 c/2. (x,m)
This completes the proof.
21

---

B.8 Proof of Theorem B.4
We first give the algorithm in Theorem B.4, which is more detailed version of Algorithm 1.
Input: e (0, 1), (0, 1/2) and sample access a joint distribution D of (x, y) supported
Rd {+1] with x-marginal Dx -Na-
Output: h(x) = sign( (w, x) t) that c-reliable with respect to the class H2-
1. Check if Pr(xa))DD -1] I c/2 (with sufficiently small constant failure probability). If SO, return the +1 constant hypothesis. If the parameters satisfy
min (00g((1))00m))//0)) .200ly(1/6) = 20og 2l0g(1/e)00bgg//0)
then set the correlation parameter ( constant. Otherwise, set Ç Ç e" for sufficiently large universal constant c. For t = ④ (a) and / = (a)), do Steps (2) and (3).
where e is a sufficiently large universal
2. Initialize w to be a random unit vector in R4. Let the update step size À = ={ and repeat the following process until À S e/100.
(a) Use samples from D to check if the hypothesis 1((x) sign((w, (w, x) 1) satisfies R² (h; D) & c/2. If so, go to Step (3). (b) With 1/2 probability, let the distribution of (x-w, v) for (x, ~ D given E B. Use the algorithm of Proposi-
w. Let B = EX (w, x) -t 0}. and let D' be
tion 2.1 on D' to find a unit vector v such that (v, w) = 0 and
proj w. (w')
2 C.
[proo w(
Then, update w as follows: Wupdate
t+ [
(c) Repeat Steps (2a) and (2h) e/C² times, where e is sufficiently large universal constant, with the same step size A. After that, update the new step size as Xupdate = X/2.
3. Check if f(x) = sign( (w, x) - t) satisfies R4 D) I c/2. If so, add it to the set S. For each choice of value in Step (I), repeat Step (2) 21/5" many times where e a sufficiently large constant.
4. Let S' be the set in Step (3). Return the hypothesis h(x) = sign( (w, x) t), where (w,t) argmin(w.e)es' Return the -1 constant hypothesis if S is empty.
Algorithm 3: Reliably Learning General Halfssacce with Gaussian Marginals (detailed version of Algorithm l).
Proof of Theorem B.4. Without loss of generality, we assume > for the following reason. Sup- pose S C, then we can simply return one of the constant hypotheses that is closest to f. Let f(x) = sign( (w", : x) - -t) be the optimal LTF with a bias, namely,
argmin SEHSAR (f;D)=0
R=;
We prove that with high probability, Algorithm returns hypothesis h(x) - sign((w, x) such that R+ (h; D) I e and (h; D) < (f: + c. Notice that at some point, we will run Step (2) with t = t" We show that given t = t", Step (2) will with probability 2 poly(1/S) returns a h with R4 (h; D) S e/2. For convenience, we assume h never satisfies R4 (4; D) S e/2 Step (2a) (otherwise, we are done). Furthermore, we assume the subroutine algorithm in Proposition 2.1 used in Step (2b) always succeed, and we always have (w, w*) 2 since both happen with constant probability and we are running the update at most
poly(1/{) many times.
Let [|proj w 1/2. Now, we will prove by induction that each time after c/5² many updates in step (2b), we always have [|proju w < 3λ (without loss of generality, we assume À is always most sufficiently small constant). Notice that by Lemma 2.5 and Proposition 2.1, we have that at each update, given the subroutine algorithm in Proposition 2.1 succeeds, the update direction
always satisfies proj ( (w') <. which implies (v, proj (w*)) 2 n/C. Then we have
(w, w (w,w")
VI 1 272 When update w, there are two possibilities. Either À > nC/2
22

---

1 I n///. If S n//2,, using Fact 2.6, we will have (w (aaddate w (w, w + 2 IfA n5/2.
we have
proj Wapest (w))l
-lpproj_w- (Wopdatell) 1 S Ippro__w- - www Av)1l2
< I|proj_w (w)ll2 A 3A.
For the base case, when we do the first group of c/C² many updates, combining the two cases above and the fact that À For the induction case, given S 6λ (which follows from the previous group of c/C² many updates), combining the two cases above gives that after e/ç² many updates, must have proj ww w ll 3X. This proves that after each group of c/5² many updates, we have [proj__ w" 2 32.
T gives that after c/(² many updates, we must have |proj Lw w 2/11 3A.
Therefore, when we have À S </110,, we get ||proj wall w S 3e/100, which implies R4 (h: D) S c/2 since satisfies the reliability condition with respect to f. Given R4 (h; D) 5e/2, using the fact that ( - I 0 (since we always output the hypothesis with the smallest () implies Pr(x.))D (h(x)
1 2 (f( = 1], we have that
R- (h;
Pr Iy = 1]
Pr Iy = 1 h(x)
(x.I)~
(x.))~D
Pr [y [y=1] (x.y)~D
Pr [h(x) 1] R+
(x.y)~
Pr /y/ -y=1] Pr [f(x) = 1] +| e (f: D) te.
(x,3)~~*
(x,y)~>*
This completes the proof.
C Omitted Proofs from Section
We first restate our main SQ hardness result.
Theorem C.1 (SQ Lower Bound for Reliable Learning). For any a >> 0 that is a sufficiently small absolute constant and e a/3), any SQ algorithm that reliably learns a- e-bbasee LTFs (for positive labels) on Rdd under Gaussian marginals to additive error e either (i) requires at least one query of folerance at most ( ()),, or (ii) requires at least (11) queries.
C.1 Proof of Lemma 3.3
We let Pn denote the set of all polynomials R - R of degree at most and let L7 (R) denote the set of all nonnegative functions in L (RR). First, write the conditions the primal linear program.
find such that
g g (R)
E [p(2)g(2)] = =0, Vp E Pr 2
g(2) 21,
V2 c
I|o| $
By introducing variables H E (R) and h (Rt), we rewrite the primal LP as
find
g (R)
such that
E [p(2)g(2)] 00 N
Vp P.
vh E L E (o(=)) 2 [M{b)|{> 2 cll. g
E M~ (z))
< |
WH E (R)
The following fact is application of (an infinite generalization of) LP duality:
23

---

Claim C.2. The LP above is feasible if there exists no polynomial p of degree n such that
E 2~N1
[p(=)]]( $ [c]] E soN, (=
Proof of Claim C.2. First, we introduce some notation. We use (h,c) for the inequality Eg-N [(=) + I 0, where h E L (R) and c E R. Moreover, let S be the set that con- tains all such tuples that describe the target system. For the set S, the closed convex cone over (+(R) x R is the smallest closed set S., satisfying the following: (a) if A E S+ and E S+ then A + B S+; and (b) if A E S+ then AA E S+ for all À 2 O. Note that the S., contains the same feasible solutions as S. In order to prove the statement, we need the following LP duality from [Fan68].
Fact C.3 (Theorem I of [Fan68]). X is a locally convex, real separated vector space. Then, a linear system described by S is feasible (i.e., there exists a g E X²* ) if and only if (0, S+.
Our dual LP is defined by the following inequalities:
(a) (p, 0) for p E Pni
(b) h - [1]]1] for all h(z) 1==)1 c), where h E 14 (R); and
(c) and (H))) for all E L (R).
Furthermore, the LP is also equivalent breaking the last inequality into two, i.., (H1, (|H 111) for
all (=) Hi (=) (= c). where Hi (R), and (H2, H2 [11) for all f2(() H2(=) cf where H2 E L._ (R). By taking the convex cone defined from the above inequalities, we get the following
S+ = (p-h h + H1 + H2, | - | + Halli)
PmP Pr.
h(=) h(=) for E LLR),,
H₂(2) (z)z) < c] for H1 E L (R),
H²(2) = H2(=) 2 c} for H2 E L (R)
We first show that S.+ is closed. To do so, we prove that S+ is closed under limits. First, we assume, in order to reach a contradiction, there is sequence (pi, h2, H1, H2,,) that
(Fi, Ac) (p. ---ha The + H1, + H2,5 || | + H2,ell1)
has F; converges Prim with respect to Ln-morm and D converges to Atim We claim then that (Fim: (imm S4. First, notice that ||p:]| S || |1 + |h4 + 11 + || S [|]l]
Therefore, there must be k such that for any 2 k, ||p:]] S || +
Then, since L1 ball in Pa with radius [| l|2 + 4 is compact, there must be a subsequence of (pi, Hy H222) such that ps converges Plim for some piim Pn. Notice that due to the
positivity of h4 and H2,5, must be h; = (F. p:) 1(2 2 c), H2.5 (F, 17.-pP p 1(2 2 c) and H1, (F)- < c). Therefore, h4. H1 and H2, converge to him = (Fiim - Plim) 1(2 2 c). Нz = (Fum - Pium) ) 1 2 c) and H1,mm = (Fim [[ < c) respectively. Then by taking (pim, him. H1.lim H2, one can see that (Fim Aum) E S4.
only remains to verify that if there exists a polynomial p of degree n such that
E [[]p())][(( s c)] < E M
[= c)],
z
then (0, 1) E S.. Letp be the polynomial satisfying the above. We can simply take hn (pi)+
c), Нz = (pt) [(= 2 e) and fi, 1p.1 < c). This gives
(p. h2 + Hes + Hz.5 | - |/ + H2,lll) (0. k) E S+.
24

---

where
k 1(x)) (= c]] [(x)
(2 p < (1)))) e]] ((.) [1 2 c)|l (2 <
- E. z~Mi b(=))(( c)] E (=< S >
Then, by properly rescaling (0, k). we get (0, E St. This completes the proof.
Given Claim C.2, to prove Lemma 3.3, only remains show that there does not exist polynomial p of degree at most n such that
E (= 2~
E (=()) c)) swni
First, the above condition implies that E [[x(2)] < 2 E 2 e)}. Using the Cauchy-Schwarz inequality, we get
1/2
E [[p(2)] W~M
<2 E 1P 2~M1
Pr [z 2 2m
(3)
We then give the following claim.
Claim C.4. Let IR + R be any polynomial of degree at most Then, it holds that
E 2-M1
[b(=))]] < 3"
2 [[(()]]]-
E
Proof for Claim C.4. The proof is based the following well-known fact: for any function g R R. it holds that (from Holder's inequality)
E [Io()))²}= 2
= s [lx(=)
[g{{)|+
E [l]()))]//3 2Mi
thus
E S
[19
E [3 I9(=))1)
E 2
(4)
s
We then use Fact C.5 (Gaussian Hypercontractivity)) to bound the term Ez-A, [[{(=)
Fact C.5 (Gaussian Hypercontractivity). Let p + be any polynomial of degree at most l. Then, for 2 2, it holds
9/2
E [I(()) 1)21/2 2
E a~
[x(()))
Now apply Fact C.5 and choose 3 Eg-Ar [Ip(2)]?13, which is Es-,i [|p(2))*11/ 3r/3 Ez-As (lp(2)) Plugging it into Equa- tion (4), we get that for any polynomial of at most degree-n,
and 4. This implies E.-A; [Ip()))* s
s [1p(2)) < 3m/3
E
2
s>,
This implies
E [1(22 M
3r 3"
E [[((=)]]
Applying Claim C.4 to Equation (3), get
1/2
E [[[(=)]] < 3m s
E [l(())]
Pr (2 [=> c) 2M
end
From choice of the parameter have that Prewi [z 2 2 2n 2//2n/4.5 /4, thus
[+(())]] E [l(())]] 2
E
z
contradiction. Therefore, such a polynomial p cannot exist. Thus, function g satisfying the requirements in the body of the lemma exists.
25

---

C.2 Proof of Lemma 3,4
We let D be the unique distribution such that Ni and ((..))))1) 2
= where g is the function from Lemma 3.3. We claim that D satisfies the conditions in this lemma's 's statement. Condition (i) immediate from the definition D. Then Condition (ii) immediately implied from Condition (a) in Lemma 3.3.
For Condition (iii), Condition (b) in Lemma 3.3 implies Ez-An [=)) 0 which immediately implies ((a.))) [v] 0. To show that
E (#.0)~D
|=*]
E (=N0~D
y y
E
[=*
y
-11
(2.0)~D
for all & E [n]. notice that for all k E [n]]
E [2*] Pr Iv 11 E
v 1|
Pr
- =--11
E
12t y= -1]. (5)
(=.g)~
(s.y)~D
(2.y)m=
(2.y)~
(2.0)/D
Moreover, from Condition (ii) Lemma 3.3, we have E [0(=)==]= (x,0)=
E [y=*]] (a,0)~
Pr yy - (#.)~ (2.0))
E
y --
Pr
Iy -1
E
1
y1
-1]
(a.t)~D*
(2.0))
=0.
(6)
Taking the difference between Equation (5) and Equation (6) gives
E (xa))D
[=*] = Pr [y -1]
y
-1]
(a.vi~D
(=.))~
Plugging in that Pr Pr(s.))DD = -1] = 1/2, which follows from (( [y] = 0 and y is supported on (#1), ,, we get
E [2*]
E 12t
1y=-1].
(a.0)~ ~
(e.y)~/D
Then, we have
E
[++]
E
1]
Pr
[V = 1] +
E
12
1y
-1] Pr IV = - 1] (2.9)~
(2,3)~
(#,0)~D
(#:0)=D
(+.9)~
therefore,
E (2.8)~
E (=,y)~
y -1]
Thus, Condition (iii) holds.
Now, we show the fourth condition. We show the following claim. Claim C.6. It holds that x2 (D+,N = 0(1).
Proof.
[
PD. (z)2 dz -
xD4
PNi (2)
PD. (2)
PD. (z)
dz
PNi (2)
< PD, (2)
Pr [y = 1]d2 -
JR
(z,y)~DD
Pr [y = 11 11==1
Pp. (z)dz
(#a))>
jR
Pr [V = 1| - 1 -1) (=.0)D
where the inequality follows from the fact that
(=) PD. (z) Pr
- p
PD (2) Pr [y - PD, (z) Pr by 1], (x.0)~
(2.9)DD
(#.8)~
which implies PD. (z) (z) < 1/ Pr(,.))DD) 1]. The same holds for x (D_, This completes the proof of Claim C.6.
The proof of (D_, 0(1) is similar to Claim C.6. This completes the proof of Lemma 3.4.
26

---

C.3 Construction of the Alternative Hypothesis Distribution Set D
Lemma C.7. For any sufficiently small > 0, there exists a distribution famity D {Dv : vve
supported on _d x {=1} where [D] = 2d satisfying the following:
(i) For any Dv E D and (x ~ Dv, the marginal xx = Nai
(ii) For any Dv E D and (x,8) Dv. E(x,))DD,lVl wuxx x"] 1 for all x' E R such that
(v,x') 2 + a1-
(ii) Let Dmull be the joint distribution of (x, such that ~ Na and y 1 with probability 1/2 independent of x. Then for any Dus Dv E D, XD (Du, Dv) 0(1) if u = and D (uu Dv) d--1(log1))) 1/a) if u + V.
Here, we give two lemmas from [DKP721] to construct a large set of distributions on I2d x {+1} with small correlations. For a matrix A E mR we use || A|2 to denote the spectral norm.
Lemma C.8 (Correlation Lemma: Lemma 2.3 from [DKPZ2IJ). Let g IR + R and U, V E Rmxdd with d be linear maps such that UU VVT where I is the m m identity matrix. Then, we have that
E ((Ux))(VVX) S
Σ JUV
E N
(x)]))
X--Na
t=
where gdd denote the degree-t Hermite part of
Note that we will use Lemma C.8 with m and d so that the linear maps U and V become vectors. We then introduce the following well-known fact, which states that there are exponentially many near-orthogonal vectors in Rdd
Fact C.9 (Near-orthogonal Vectors: Fact 2.6 from [DKPZ21]) For any 0 < c < 1/2, there exists a V, (u. I 1/21
set V C Sdt11 such that [ 2d((() and any u,
Proof of Lemma C.7. We define Dn the following manner. We let D' be the distribution on Rx { clog(1/a) where is sufficiently small universal constant such that 3 2n /42 a. We take V to be the set of vectors in Fact C.9 with c = 1/4. Then we consider the set of distributions D = (Dv : v E V] where Dy is the unique distribution on Rd {+1) generated in the following way. We first sample (2.y) D' and X1 No-1. Then let B E (d-1) be matrix whose columns form (arbitrary) orthonormal basis for the orthogonal complement of v. Letx = Bix: x + zv and we define the distribution D. = D(x.)). This effectively embeds the distribution D' along the hidden direction v in Dy.
in Lemma 3.4 for
To establish Condition (i) in this lemma, the definition of x combined with the fact that D2 = Ni (from Condition (i) in Lemma 3.4) implies the marginal distribution Dx = =Na-
Then, for Condition (ii) in this lemma, we have that for any x' E Rd such that (v, 2 20 (1 a).
E
xx
E (x.0)~ by 1|z (v,x'),
(x,))~D
3-13--2 3-2n from the definition of Dy. Since 3 /4 442 2 a. we have (v, wxx') 2 + a) 2 t (1-32-2
Therefore, using the second condition in Lemma 3.4, we get
E (x.y)~D
[ x x'] (z.y)~Dr
E
|u|= (v,x') 1
For Condition (iii) in this lemma, notice that Condition (ii) in Lemma 3.4 implies
Pr [y 1] Pr -1] 1/2. (x
(x.y) Dr
Then,
XDmau (D..D))
Pr [y [y=1]>200 ID
Pr [y (x.))~D.
(x.g)DDb
1
(D .a) + 1
2x2(D, 2
2
2
27

---

We show that the first term x²(D, = 0(1). x2,,, = O(1) can be shown in the exact same way. Notice that
xDD = [ PDs (u)² du -1
PNa (u)
PDt [B111 22) dudz
Rd-1 ( zv)
PNo (u))PDr+(2)" dudz
JR. JRA-1 PNa_1 (u)=( (z)
PNa (u)du [ Por (z)2
PAs (z) dz
Dd =x (N1) O(1),
where the last equality follows from Condition (iv) of Lemma 3.4. Therefore
1 (Dt .V) +
1 / (D, 0(1)
Xpaau (D.. 2
For Du, Dv E DD where u o v, we have
XDaul (Du, Dv) Prly (D Dt) Prly - -1w
1
X (D D+) +
2 X.v (.).
We show that XNa (D D+) same way. Notice that
Dt) = d 221lo 1) XN. (D. D7) = d --lo 2) can be shown in the exact
/
P Dt (w) (w)
(D, D+)
dw -1
ga
(w)
P PDt (proj in (w) + proj.. (w)) P (proj (w) + projo (w))
dw
(w)(w)
PNia-i (w-") (w") (N (w-r)
(w
-1 dw-
dw
PNo(w)
(w++
PDr+ (w
(Na(W)
PN, (w>) dw 1
JR
PNi (ww)
Let R + IR be g(2) def (z) PNi (z) and apply Lemma C.8 and Condition (iii) of Lemma 3.4,
we get
x
(o)))))))
+ Σ (D Dt) <
d-a
d
E
t=++1
<d f( X21 (D* .Ni)
Ailox )
where the last equality follows form Condition (iv) of Lemma 3.4. This completes the proof of Lemma Lemma C.7.
C.4 Proof of Theorem C.I
Let D be the set of distributions in Lemma C.7. We also let Dmall be the joint distribution of (x, v) such that x ~ Na and y ~ Bern(1/2) independent of x. We consider the decision problem of ((D, Daut). Using Lemma A.4 with ?' = d log(?), we can see that any SQ algorithm that solves ((D, Dmnt) requires either queries of tolerance most d- + makes at least 20) queries.
We then reduce the decision problem B(D, Damu) to reliably learning a-biased LTFs with 6 < a/3 accuracy. Let D be an instance of B(D, Dman) which need to decide either D Dmoil or
28

---

DE D. Let A be an algorithm that reliably learns a- a-biased LTFs with < a/3 accuracy and succeeds with 2/3 probability. We can simply give the i..d. samples from the distribution to algorithm A. Suppose that A succeeds and outputs a hypothesis function h. If D) D then since A promises (h, Pmil) S c. Since Duull has y ~ (ern(1/2) independent of x, this implies Pr(xx))-((((x ( = 1] S 6.
Then we argue that if we in the alternative case, i.e., D E D, then given that the algorithm succeeds, we must have Pr(x.y)~DD [/(()) = 1] 2 instead. We assume Pr(x.g)-D(((( (x()) 1] < a - and prove a contradiction. If Dv D, then by the first property in Lemma C.7, there must be an a- a--iased LTF e such that ( (]((x) = 1 2 a and (rxxa)>-(((()) = 1 AAy -1] = 0. Combining this with the fact that Pr(x.))~D(r = 1] = 1/2, we have (_ D) = Pr(c(x) = -1Ay = Σ 1/2 - a. Therefore, the output hypothesis h of has to satisfy
R- - 1/2 a t
However, since Pr(x.)) (x() 1] < a
have
D): Pr [xx) LAY 1] 2 Pr by -1 Pr [h(x) > 1/2 a a (x.y)~
(x,8)~>
(x
which contradicts the above. Thus, it has to be Pr(xa))n(h(f) (h(x) 1] > a-
If D Dulll then Pr(x,))-D(((x (b(())
S Otherwise, we have Pr(x.y)~Dh((s h(xx) = =|
Since the gap between them is at least a constant 2x 2 a/3 and Pr(x,y)-D [h() = can be
estimated inverse exponential accuracy on samples with high probability. Thus, we can distinguish the two cases of B(D, Dmmn) with high probability.
29

---

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

---

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

---

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

---

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

---

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

---

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


Reviews:
[{"review_id": "s3akL7HMKx", "reviewer": "Reviewer_wFKn", "summary": "This paper studies reliable learning of halfspaces in $d$ dimensions. Reliable learning is a framework in learning theory in which the learning algorithm is required to output a classifier $f$ satisfying:\n- the probability that f makes a false-positive error is at most $\\epsilon$\n- The probability that f makes a false-negative error is at most $opt+ \\epsilon$, where $opt$ is the smallest error rate achievable by a classifier in the class $\\mathcal{G}$ that has zero false-positive error.\n\nThe work gives a reliable learning algorithm for the class of $\\alpha$-biased halfspaces when the data marginal is the standard Gaussian distribution. A halfspace is $\\alpha$-biased if on a Gaussian input it has probability at least $\\alpha$ to take either of the two possible output values. The run-time of the algorithm is $d^{O(\\log(min(1/\\alpha,1/\\epsilon)))}min(2^{\\log(1/\\epsilon)^{O(log(1/\\alpha))}}\n, 2^{poly(1/\\epsilon)})$. \n\nThe algorithm first finds a candidate direction by estimating the Chow tensor. Consequently, the algorithm improves this hypothesis by performing a certain random walk. \n\nIt is shown that any statistical-query algorithm has to take at least $d^{\\log 1/\\alpha}$ time for this task. Statistical-query algorithm are a wide family of algorithms that includes virtually all algorithms studied in learning theory.", "questions": "- I think there is a missing parenthesis in the end of Theorem 1.3\n- Is it possible that for every small constant $c$, if $\\alpha$ is promised to be at least $c$, then there is an algorithm running in time $\\poly(d/\\epsilon)$? \n- Is it correct that for these halfspaces your algorithm runs in time $d^{O(1} 2^{\\log(1/\\epsilon)^{O(1)}}$?", "limitations": "Limitations are discussed adequately.", "rating": 7, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "- Reliable learning is a natural framework asking for approximately-best classifier that makes false positive rarely. Considering halfspaces over Gaussian data is arguably the most natural setting to study. However, prior to this work little was known about this question.\n- The run-time compares favorably with the run-time of $d^{poly(1/\\epsilon}$ that is known to be best for the more challenging agnostic model. This is true for all values of bias $\\alpha$, but is especially true when $\\alpha$ is a small constant.\n- The methods developed in this work seem potentially interesting in their own right.", "weaknesses": "- Not clear that the dependence on $\\epsilon$ is best it can be.\n- None of the algorithms run in fully polynomial time in all parameters.", "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 reviewing our paper and for the positive feedback. Below, we provide specific responses to the points and questions raised by the reviewer.\n\n> Is it possible that for every small constant $c$, if $\\alpha$ is promised to be at least a constant, then there is an algorithm running in time $\\mathrm{poly}(d/\\epsilon)$?\n\n*Response:* Yes, it is possible in principle. Our lower bound does not rule out this possibility.\n\n> Is it correct that for these halfspaces, your algorithm runs in time $\\mathrm{poly}(d)2^{\\mathrm{polylog}(1/\\epsilon)}$?\n\n*Response:* Yes, for any constant $\\alpha$, our algorithm runs in $\\mathrm{poly}(d)2^{\\mathrm{polylog}(1/\\epsilon)}$ time.\n\n> It is not clear that the dependence on $\\epsilon$ is the best it can be.\nNone of the algorithms run in fully polynomial time in all parameters.\n\n*Response:* We want to remark that although the dependence of the running time on $\\epsilon$ might not be the best possible, it is still an exponential improvement over the previously best-known algorithm for the problem. Moreover, fully polynomial dependence on all parameters seems unlikely, given our SQ lower bound. Specifically, the $d^{\\Omega(\\log(1/\\alpha))}$ dependence is inherent for SQ algorithms.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "ctoq1U68Wk", "reviewer": "Reviewer_ZrmL", "summary": "This work studies agnostic learning of halfspaces in the reliable learning model, which guarantees a halfspace with nearly no false positives and a nearly optimal false negative rate, where the optimal false negative rate is defined relative to a class of halfspaces with no false positives. The authors prove sample and computational bounds for this learning task under a standard Gaussian distributional assumption, dramatically improving the previously known bounds that followed from reduction to general agnostic learning under the same distributional assumption. They also show a statistical query lower bound of $d^{\\Omega(\\log(1/\\alpha))}$.", "questions": "In line 222, I’m confused about the signs. Doesn’t the interval $[t^*, \\infty]$ correspond to positive labels, and don’t we want the expectation of p within this region to be negative?\n\nHow does the equality in line 241 follow from Lemma 2.5?", "limitations": "Yes, the authors address the limitations of the work.", "rating": 8, "confidence": 2, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "This work furthers our understanding of the sample and computational complexity of learning halfspaces under challenging noise models. The techniques used to obtain the algorithmic result are very interesting, and while technically involved, the overview of the proof approach in the main body is well-structured and modular (if still hard to follow as someone with little familiarity with the related work).", "weaknesses": "While the page-limits are restrictive, I would have benefited from some additional handholding even in the overview. The introduction of Lemma 2.5 was particularly opaque, for instance. \n\n\nTypos/suggested edits:\n\nLine 14. “The problem of learning halfspaces is one the classical”\n\nLine 40. “has since been extensively studies”\n\nLine 53. “minimizing a lost function”\n\nLine 69. “as a reliable agnostic learning for Gaussian halfspaces”\n\nLine 84. missing close parens\n\nline 94. “reduce the fully reliable learning”\n\nline 105. “This implies that that”\n\nline 214. “Let D be joint distribution”\n\nAlgorithm 1 caption “General Halspaces”\n\nLine 511/525 “Reliable learning halfspaces”", "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 reviewing our paper and for the positive feedback. Below, we provide specific responses to the points and questions raised by the reviewer.\n\n> In line 222, I’m confused about the signs. Doesn’t the interval $[t^*,\\infty]$ correspond to positive labels, and don’t we want the expectation of $p$ within this region to be negative?\n\n*Response:* In Lemma 2.3, our goal is to show that $\\mathbf{E}_D[y\\,p(\\mathbf{x})]$ is large. Therefore, ideally, we want the polynomial $p$ to be positive on regions with positive labels and negative on regions with negative labels.\n\n> How does the equality in line 241 follow from Lemma 2.5?\n\n*Response:* There is a typo in the equality in line 241, where there should be an $\\Omega(\\cdot)$ in the right-hand side. This follows from the fact that the correlation between two random $d$-dimensional unit vectors is at least $\\Omega(1/\\sqrt{d})$ with high probability. Lemma 2.5 gives a lower bound on $||\\mathrm{proj}_V(\\mathbf{v}^*)||_2$, which implies $|\\langle \\mathbf{v},\\mathbf{v}^*\\rangle |$ is sufficiently large for a randomly chosen unit vector $\\mathbf{v}$.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "AVPeiP8SHR", "reviewer": "Reviewer_ae3s", "summary": "This paper considers learning halfspaces with Gaussian marginals in a reliable learning setting, where the learner has to guarantee that the error of the output classifier is less than $\\epsilon$ (and we assume such a classifier exists). It is known that the reliable learning problem can be efficiently reduced to agnostic learning, but the sample complexity for agnostic learning is high ($d^{O(1/\\epsilon)}$). This paper proposes an algorithm that has a much better sample complexity (polynomial in d, but still quasi-polynomial in $1/\\epsilon$), and it provides a lower bound showing that one cannot do much better w.r.t. d.", "questions": "N/A", "limitations": "N/A", "rating": 7, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- This paper considers an interesting learning theory problem.\n- The results look nontrivial.\n- The methods look sound, though I'm not familiar with the techniques used here and did not check the proofs.\n- It is written clearly, and explains the intuition well.", "weaknesses": "- Though this is an interesting theory problem, it is not entirely clear to me how significant the results are. Specifically, what is the importance or implication of the computational separation between agnostic and reliable learning found in this paper, especially given that the proposed algorithm is still super-polynomial.", "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 reviewing our paper and for the positive feedback. We respond to the point raised by the reviewer regarding the significance of our result. \n\nOur result is the first to establish a computational separation between reliable and agnostic learning in the distribution-specific setting for the class of halfspaces. While our algorithm has superpolynomial runtime (as a function of the excess error $\\epsilon$ and the bias $\\alpha$), it achieves an exponential improvement over the previous best-known algorithm for the problem. Moreover, the underlying algorithmic technique is likely to be useful for related reliable learning tasks. It it worth noting that our algorithm runs in $\\mathrm{poly}(d)$ time for any constant $\\alpha$ and moderately small values of the parameter $\\epsilon$ (namely up to $1/\\mathrm{polylog}(d)$). On the other hand, for agnostic learning, one incurs super-polynomial time for *any* $\\epsilon= o(1)$ (even if $\\alpha=1/2$). Finally, we believe that our work provides fundamental insights into the task of reliable learning and lays the foundations for the development of practical algorithms for the task.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "4Ffq1nvIHq", "reviewer": "Reviewer_ezCR", "summary": "This paper studies the problem of agnostic reliable learning with Gaussian margin. It gives a novel algorithm with improved running time and sample complexity bound and this suggests that agnostic reliable learning is easier than agnostic learning. It also gives a Statistical Query lower bound matching some terms of the upper bound as an evidence that the upper bound is tight.", "questions": "1. In this paper and some other papers, the lower bounds are SQ lower bounds. As far as I know, SQ lower bounds are weaker than PAC lower bounds (SQ learnable implies PAC learnable but not the other way around), is there some difficulty to get a PAC lower bound for the problem?\n\n2. As far as I know, active learning doesn't seem to help with agnostic learning halfspaces (Gaussian margin, arbitrary noise), could it improve the sample complexity bound for agnostic reliable learning (with Gaussian margin).", "limitations": "I think the authors could give some future directions and potential improvements.", "rating": 7, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. The result of this paper is novel and complete.\n\n   a. The running time and sample complexity of the proposed algorithm is a big improvement from the previous $d^{O(1/\\epsilon^2)}$ and the algorithm is completely new.\n\n   b. The algorithm, lower bound and analysis are all highly non-trivial and technically sophisticated, showing a deep understanding of the problem. I think there's lots of technical novelties in the paper.\n\n   c. The fact that there's a separation between agnostic reliable learning and agnostic learning is interesting and it's a contribution to formally establish this.\n\n   d. The paper gives a non-trivial SQ lower bound matching some terms of the upper bound, suggesting its tightness.\n\n2. The writing of the paper is decent. Enough background knowledge is given. Math related parts is clearly defined and the proof is rigorous. The paper is organized and non-technical part is not hard to follow.", "weaknesses": "1. There are some room for improvement in writing.\n\n   a) As someone who is quite familiar with PAC and many classical learning problems but not familiar with reliable learning/learning Gaussian margin halfspaces, I find the introduction to the problem could be more clear, especially I think you can do a better job explaining the adversary's strategy and behavior, the \"corrupt negative labels are free\" part is worth more insights.\n\n   b) I do find the paper really technical, but I think it is intrinsic. As someone who is not familiar with your algorithmic framework [DKK+22] and some technical parts (for example, the use of polynomials), I think more explanation could be helpful.\n\n   c) Some parts of the writing could be more clear, like \"with high probability\" in the definition.\n\n2. I do find the SQ lower bound a bit weak. It doesn't have a dependence on $\\epsilon$, is there any known lower bounds on $\\epsilon$?\n\n3. The agnostic learning lower bound doesn't have a dependence on $\\alpha$, but the agnostic reliable learning bound has such a dependence, why? You assumed that $\\alpha$ is a constant, if it's not, is there any complications in your conclusion?", "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 reviewing our paper and for the positive feedback. \n\n> I do find the SQ lower bound a bit weak. It doesn't have a dependence on $\\epsilon$, is there any known lower bounds on $\\epsilon$?\n\n*Response:* The point of our SQ lower bound is that the joint dependence between the dimension $d$ and the bias $\\alpha$ of the target concept is inherently quasi-polynomial, namely $d^{\\Omega(\\log(1/\\alpha))}$ (assuming that $\\alpha \\geq 2\\epsilon$). This lower bound holds for any $2\\epsilon \\leq\\alpha$. Importantly, we provide the first such lower bound for reliable learning of Gaussian halfspaces. We do not know of a super-polynomial lower bound on $\\epsilon$ and leave this as an open question for future investigation. \n\nAt a more technical level, our construction establishes an SQ lower bound for a natural testing version of the problem (that is easier than learning). This testing problem is in fact solvable with SQ complexity $d^{\\Theta(\\log(1/\\alpha))}$ (both upper and lower bound). The dependence on $\\epsilon$ in our upper bound is due to the fact that we need to search for a good solution via a random walk, as explained in lines 108-130. \n\n\n\n> The agnostic learning lower bound doesn't have a dependence on $\\alpha$, but the agnostic reliable learning bound has such a dependence, why? You assumed that $\\alpha$ is a constant, if it's not, is there any complications in your conclusion?\n\n*Response:* For agnostically learning Gaussian halfspaces, the $d^{\\mathrm{poly}(1/\\epsilon)}$ SQ lower bound holds even for $\\alpha=1/2$, which suggests that the agnostic problem does not become harder with smaller $\\alpha$. We show in our work that this is not the case for the reliable learning task. Intuitively, in the agnostic model, the adversary can corrupt an $\\epsilon$-fraction of the labels anywhere on the entire domain. On the other hand, in the reliable setting, the adversary can only corrupt labels inside the region $c(\\mathbf{x})=-1$ (where $c$ is the target concept). As a result, one needs degree-$\\mathrm{poly}(1/\\epsilon)$ polynomials to not be fooled by noise in agnostic learning. While in reliable learning, our Lemma 2.3 shows that a degree-$O(\\log (1/\\alpha))$ polynomial suffices (where $\\alpha$ is the bias of concept $c$ and $\\alpha\\geq \\epsilon$). It is also worth mentioning that for the special case of $\\alpha=1/2$, we get $\\mathrm{poly}(d/\\epsilon)$ runtime for reliable learning via an easy algorithm (see Lemma B.3).  \n\nFinally, we remark that we do not assume anywhere that the parameter $\\alpha$ is a constant. Our algorithm works for any value of $\\alpha$ (even if it is not known a priori to the algorithm).\n\n\n> In this paper and some other papers, the lower bounds are SQ lower bounds. As far as I know, SQ lower bounds are weaker than PAC lower bounds (SQ learnable implies PAC learnable but not the other way around), is there some difficulty to get a PAC lower bound for the problem?\n\n*Response:* While SQ lower bounds are viewed as strong evidence of hardness in learning theory, we acknowledge that the SQ model is a restricted model of computation. So, in principle, it may possible to surpass SQ algorithms. On the other hand, there are very few such examples in the literature (and none for learning halfspaces with noise). Alternatively, one could try to prove reduction-based hardness (from a plausibly average-case hard problem, e.g., in cryptography). There are a few such reductions in the literature, and in some cases they have been directly inspired from the SQ-hard instances. A recent example that is relevant for us is for the task of agnostically learning Gaussian halfspaces, where [DKR23] (building on the SQ lower bounds of [DKZ20]) gives a cryptographic lower bound (assuming the subexponential hardness of LWE). Their technique requires a hard distribution whose marginal in the hidden direction is (roughly speaking) a mixture of periodic signals, which cannot be adapted for our hard distribution here. It remains an interesting open problem to establish reduction-based hardness for our problem. \n\n> As far as I know, active learning doesn't seem to help with agnostic learning halfspaces (Gaussian margin, arbitrary noise), could it improve the sample complexity bound for agnostic reliable learning (with Gaussian margin).\n\n*Response:* We agree with the reviewer that active learning does not seem to help with agnostic learning halfspaces under Gaussian marginals. It is not clear to us whether active learning can help in the reliable learning case. This is an interesting open question for future work.\n\n> I think the authors could give some future directions and potential improvements.\n\n*Response:* We are happy to add some future directions in the revised version. An immediate open question is whether one can improve the dependence of the runtime as a function of $\\epsilon$ from quasi-polynomial down to polynomial. \n\n> the \"corrupt negative labels are free\" part is worth more insights.\n\n*Response:* In fact, corrupting negative labels is not free, as the adversary has an $\\epsilon$ budget to corrupt negative labels. However, the adversary is restricted to only corrupting the \"true\" negative labeled samples as compared to the agnostic model.\n\n> More explanation on the use of polynomial\n\n*Response:* In lines 116-123, we explained the high-level idea of using polynomials to learn. We are happy to add further explanations to make the intution more transparent. \n\n[DKZ20] I. Diakonikolas, D. Kane, and N. Zarifis. Near-Optimal SQ Lower Bounds for Agnostically Learning Halfspaces and ReLUs under Gaussian Marginals. In Advances in Neural Information Processing Systems, NeurIPS, 2020.\n\n[DKR23] I. Diakonikolas, D. M. Kane, and L. Ren. Near-Optimal Cryptographic Hardness of Agnostically Learning Halfspaces and ReLU Regression under Gaussian Marginals. In International Conference on Machine Learning, ICML, 2023.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:
We thank all reviewers for taking the time to read our manuscript carefully and for providing constructive and insightful feedback. 

We provide detailed responses to each reviewer separately. We look forward to engaging in further discussion with the reviewers, answering questions, and discussing improvements.

Meta-review: All reviewers agree that the paper studies an important problem, establishes sound results regarding the sample and computational complexity of distribution-dependent reliable learning, and introduces novel techniques that may find other applications in learning theory. In addition, a nearly matched statistical-query lower bound is established, showing the near-optimality of the proposed approach.

In more detail, authors observe that under the current noise model, it may be (information-theoretically) impossible to distinguish a candidate halfspace from the target one even though their L2-distance is bounded away. To resolve this fundamental issue, they propose a novel approach that performs random walk on a lower dimension and show that the random walk will hit a point at which the distance to the target halfspace is significantly decreased. Such techniques move away from prior works, which applied applied reduction to agnostic noise. As a result, the obtained sample and computational complexity are always lower than those of agnostic learning; in fact, for a wide regime, they are significantly lower.

The paper is very well written and easy to follow.
Decision: Accept (spotlight)