Reliable Learning of Halfspaces under Gaussian Marginals

Authors: ilias  diakonikolas
lisheng  ren
nikos  zarifis
Venue: NeurIPS_cc_2024_Conference
Published: 2024-05-14 21:33:53

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.

Main paper: 
 introduction: 
 Halfspaces (or Linear Threshold Functions) is the class of functions f : R d → {±1} of the form f (x) = sign(⟨w, x⟩ -t), where w ∈ R d is called the weight vector and t is called the threshold. The problem of learning halfspaces is one of the classical and most well-studied problems in machine learning -going back to the Perceptron algorithm [Ros58] -and has had great impact on many other influential techniques, including SVMs [Vap98] and AdaBoost [FS97] .Here we focus on the task of learning halfspaces from labeled examples. The computational complexity of this learning task crucially depends on the choice of the underlying model. For example, in the realizable PAC model (i.e., with clean labels), the problem is known to 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 of noisy labels. In the noisy setting, the computational complexity of the problem depends on the choice of noise model and distributional assumptions. In this work, we study the problem of distribution-specific 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 H d be the class of halfspaces on R d . Given 0 < ϵ < 1 and i.i.d. samples (x, y) from a distribution D supported on R d × {±1}, where the marginal D x is the standard Gaussian N (0, I), we say that an algorithm reliably learns H d to error ϵ if the algorithm with high probability outputs a hypothesis h : R d → {±1} such that Pr (x,y)∼D [h(x) = 1 ∧ y = -1] ≤ ϵ and Pr We say f = argmin f ∈G(D) Pr (x,y)∼D [f (x) = -1∧y = 1] is the optimal halfspace on distribution D and for the conditions above that hypothesis h satisfies, we say that h is ϵ-reliable with respect to H d on distribution D.In other words, a (positive) reliable learner makes almost no false positive errors, while also maintaining the best possible false negative error -as compared to any hypothesis with no false positive errors. Note that if there is no hypothesis 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 a one-sided analog 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, KK21]. 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 -where 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, Elk01] ). In a historical context, reliable learning is related to the Neyman-Pearson 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 new learning model defined to capture 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 a non-convex optimization problem. As pointed out in [KKM12] , distribution-specific reliable learning can be efficiently reduced to distribution-specific agnostic learning (such reduction preserves the marginal distribution). A natural question, serving as a motivation for this work, is whether reliable learning can be qualitatively easier computationallyfor 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 + ϵ, 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 L 1 -regression algorithm of [KKMS08] is an agnostic learner with complexity d O(1/ϵ 2 ) [DGJ + 09, DKN10]. Moreover, there is strong evidence that this complexity upper bound is tight, both in the Statistical Query (SQ) model [DKZ20, GGK20, DKPZ21] and under plausible cryptographic assumptions [DKR23, Tie23] . It is worth noting that the aforementioned hardness results hold even for the subclass of homogeneous halfspaces.Given the aforementioned reduction of reliable learning to agnostic learning [KKM12] , one can use L 1 -regression as a reliable agnostic learner for Gaussian halfspaces, leading to complexity d O(1/ϵ 2 ) . 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.Can we obtain faster algorithms for reliably learning Gaussian halfspaces, compared to agnostic learning?In this work, we provide an affirmative answer to 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 α ∈ [0, 1/2] of h : R d → {±1} under the Gaussian distribution as α = α(h)def = min(Pr x∼N d [h(x) = 1], Pr x∼N d [h(x) = -1]).The main result of this paper is encapsulated in the following theorem: Theorem 1.3 (Main Result). Let D be a joint distribution of (x, y) supported on R d × {±1} with marginal D x = N d and let α be the bias of the optimal halfspace on distribution D. There is an algorithm that uses N = d O(log(min{1/α,1/ϵ})) min 2 log(1/ϵ) O(log(1/α)) , 2 poly(1/ϵ) many samples from D, runs in poly(N, d) time and with high probability returns a hypothesis h(x) = sign(⟨w, x⟩-t) that is ϵ-reliable with respect to H d . Moreover, for ϵ < α/2, any SQ algorithm for the problem requires complexity d Ω(log(1/α)) .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 and computational complexity) for reliably learning Gaussian halfspaces, compared to agnostic learning. Specifically, as long as α > 0 is a universal constant, the overall complexity is polynomial in d and quasi-polynomial in 1/ϵ -as opposed to d poly(1/ϵ) in the agnostic setting. While the complexity of our algorithm (namely, the multiplicative factor that is independent of d) increases as the optimal halfspace becomes more biased, it always dominates the complexity of agnostic learning.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] ).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 × {±1} satisfies the reliability condition with respect to f :X → {±1} if Pr (x,y)∼D [f (x) = +1 ∧ y = -1] = 0 .Notice that h being ϵ-reliable on distribution D is equivalent to h having better false negative error compared with any f such that D satisfies the reliability condition with respect to f (instead of compared with the optimal halfspace). At the same time, given any fixed f , such a definition allows the adversary to arbitrarily corrupt negative labels, thus allowing more straightforward analysis.As follows from Definition 1.4, the adversary 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 are uncorrelated with any polynomial of degree at most log(1/α).To show 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 to show that SQ algorithms fail if they do not use queries with tolerance at most 1/d Ω(log(1/α)) or exponentially many queries.Reliable Learning Algorithm As discussed in the previous paragraph, an adversary can arbitrarily corrupt the labels which can make various algorithmic approaches fail. In more detail, the adversary can corrupt Ω(log(1/α)) moments. One of the main difficulties of this setting is that there may exist weight vectors w, w ′ with ∥w -w ′ ∥ 2 ≥ Ω(1) while at the same time the error of w and w ′ is nearly the same. This suggests that no 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. 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 subspace exists, we first prove that there exists a non-trivial polynomial p that correlates with the negative labels (the term nontrivial means that we cannot use the constant polynomial, as this trivially correlates with the labels); see Claim B.5. This means that the low-degree moment tensors, i.e., E (x,y)∼D [1{y = -1}x ⊗k ] for some k between 1 and O(log(1/α)), correlate non-trivially with (w * ) ⊗k . Thus, we can use these moment tensors to construct a low-dimensional subspace. We leverage the structure of the problem, namely that the negative labels are uncorrupted, to show that the correlation is in fact almost constant. As a consequence, this allows us to construct a subspace that depends only on the degree of the polynomial p.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 ∈ R d : w • x -t ≥ 0}, our algorithm conditions on a thin strip, projects the points x on the orthogonal complement of w, and re-applies the above structure result. This leads (with constant probability) to an increase in the correlation between w and w * . Assuming that the correlation is increased by β in each round with probability at least 1/3, we roughly need at most 1/β successful updates. Therefore, if we run our algorithm for 3 1/β steps, it is guaranteed that with probability at least 1/3 we will find a vector almost parallel to w * .Prior Algorithmic Techniques Roughly speaking, prior techniques for reliable learning relied on some variant of L 1 -regression. In that sense, our algorithmic approach departs from a direct polynomial approximation. Concretely, for distribution-free reliable learning, the algorithm from [KT14] uses a one-sided variant of L 1 regression -where instead of approximating the target function in L 1 , they use the hinge loss instead. For distribution-specific (in particular Gaussian) reliable learning of halfspaces, the only previous algorithm uses the reduction of [KKM12] to agnostic learning. While our algorithm also leverages polynomial approximation, our approach employs significantly different ideas and we believe it provides a novel perspective for this problem.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 R d into sufficiently small rectangles and searches in each one of them for a 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 O(log(1/α)) moments of the distribution (conditioned on y = -1) correlate with the unknown optimal hypothesis. This leads to an algorithm with significantly faster runtime.Our SQ lower bound leverages techniques from [DKPZ21] . Essentially, we formulate a linear program to construct a noise function that make 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.We use lowercase boldface letters for vectors and capitalized boldface letters for matrices and tensors. We use ⟨x, y⟩ for the inner product between x, y ∈ R d . For x, s ∈ R d , we use proj s (x) def = ⟨x,s⟩s ∥s∥ 2 2 for the projection of x on the s direction. Similarly, we use proj ⊥s (x) = x -proj s (x) for the projection of x on the orthogonal complement of s. Additionally, let x V ∈ R dim(V ) be the projection of x on the subspace V and reparameterized on R dim(V ) . More precisely, let B V ∈ R d×dim(V ) be the matrix whose columns form an (arbitrary) orthonormal basis for the subspace V , and letx V def = (B V ) ⊺ x.For p ≥ 1 and x ∈ R d , we use ∥x∥p def = ( n i=1 |x i | p )1/p to denote the ℓ p -norm of x. For a matrix or tensor T, we denote by ∥T∥ F the Frobenius norm of T.We use N d to denote the standard normal distribution N (0, I), where 0 is the d-dimensional zero vector and I is the d × d identity matrix. We use x ∼ D to denote a random variable with distribution D. For a random variable x (resp. a distribution D), we use P x (resp. P D ) to denote the probability density function or probability mass function of the random variable x (resp. distribution D). We also use Φ : R → [0, 1] to denote the cdf function of N 1 . We use 1 to denote the indicator function.For a boolean function h : R d → {±1} and a distribution D supported on R d × {±1}, we useR + (h; D) def = Pr (x,y)∼D [h(x) = 1∧y ̸ = 1] (resp. R -(h; D) def = Pr (x,y)∼D [h(x) = -1∧y ̸ = -1])to denote the false positive (resp. false negative) 0-1 error. 
algorithm for reliably learning gaussian halfspaces: 
 In this section, we describe and analyze our algorithm establishing Theorem 1.3. Due to space limitations, some proofs have been deferred to Appendix B. For convenience, we will assume that α (the bias of the optimal halfspace) is known to the algorithm and that the excess error satisfies ϵ ≤ α/3. These assumptions are without loss of generality for the following reasons: First, one can efficiently reduce the unknown α case to the case that α is known, by guessing the value of α. Second, if ϵ is large, there is a straightforward algorithm for the problem (simply output the best constant hypothesis).Notation: We use the notation H α d for the set of all LTFs on R d whose bias is equal to α. Given the above assumptions, it suffices for us to give a reliable learning algorithm for H α d instead of H d . The high-level idea of the algorithm is as follows. Without loss of generality, we assume that there exists an α-biased halfspace that correctly classifies all the points with label y = -1 -since otherwise, the algorithm can just return the hypothesis h(x) ≡ -1. 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 w 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 -O(t * 2 ) ϵ 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 (w * ) with at least some constant probability. Unfortunately, it is not easy to verify whether ⟨v, proj ⊥w (w * )⟩ is non-trivial. However, conditioned on the algorithm always getting a v that has good correlation, we show that it only takes at most log(1/ϵ) O(t * 2 ) steps to get sufficiently close to w * . Therefore, repeating this process 2 log(1/ϵ) O(t * 2 ) many times will eventually find an accurate approximation to w * .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 O(log(1/α))-degree polynomial that sign-matches the optimal hypothesis. Furthermore, using the fact that the optimal hypothesis always 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 O(log(1/α)) moments of the distribution D x 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 a random vector that lies in the high-influence directions (which form a 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 R d × {±1} with marginal D x = N d and ϵ ∈ (0, 1). Suppose D satisfies the reliability condition with respect to f (x) = sign(⟨w * , x⟩ -t * ) with t * = O log(1/ϵ) and Pr (x,y)∼D [y = -1] ≥ ϵ. Then there is an algorithm that draws N = d O(t * 2 ) /ϵ 2 samples, has poly(N ) runtime, and with probability at least Ω(1) returns a unit vector v such that ⟨v, w * ⟩ ≥ max(log(1/ϵ) -O(t * 2 ) , ϵ -O(1) ).We start by showing that for any distribution satisfying the reliability condition with respect to some f (x) = sign(⟨w * , x⟩ -t * ), there exists a degree-O(t * 2 ) zero-mean polynomial of the form p(⟨w * , x⟩) that has correlation at least 2 -O(t * 2 ) Pr (x,y)∼D [y = -1] with the labels.Lemma 2.2 (Correlation with an Orthonormal Polynomial). Let D be a joint distribution of (x, y) supported on R d × {±1} with marginal D x = N d . Suppose D satisfies the reliability condition with respect to f (x) = sign(⟨w * , x⟩ -t * ). Then there exists a polynomial p : R → R of degree at mostk = O(t * 2 + 1) such that E z∼N1 [p(z)] = 0, E z∼N1 [p 2 (z)] = 1 and E (x,y)∼D [y p(⟨w * , x⟩)] = 2 -O(t * 2 ) Pr (x,y)∼D [y = -1].Proof Sketch of Lemma 2.2. Note that since p is a zero-mean polynomial with respect to D x , we have that E (x,y)∼D [y p(⟨w * , x⟩)] = -2 E (x,y)∼D [1(y = -1) p(⟨w * , x⟩)] . Then, using the fact that the distribution D satisfies the reliability condition, the statement boils down to showing that for any ϵ-mass inside the interval [t * , ∞], the expectation of p on this ϵ mass is at least 2 -O(t * 2 ) . To prove this statement, it suffices to construct a polynomial p that is non-negative on [t * , ∞] and such that the ϵ/2-tail of p in that interval is at least 2 -O(t * 2 ) . To achieve this, we show that the sign-matching polynomial used in [DKK + 22] meets our purpose.Our algorithm will use the following normalized Hermite tensor.Definition 2.3 (Hermite Tensor). For k ∈ N and x ∈ R d , we define the k-th Hermite tensor as(H k (x)) i1,i2,...,i k = 1 √ k! Partitions P of [k]into sets of size 1 and 2 {a,b}∈P(-I ia,i b ) {c}∈P x ic .Given that there is such a polynomial, we show that if we take a flattened version of the Chowparameter 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 Appendix B for the proof. Lemma 2.4. Let D be the joint distribution of (x, y) supported on R d × {±1} with marginal D x = N d . Let p : R → R be a univariate, mean zero and unit variance polynomial of degree k such that for some unit vector v * ∈ R d it holds E (x,y)∼D [1(y = -1)p(⟨v * , x⟩)] ≥ τ for some τ ∈ (0, 1]. Let T ′m be an approximation of the order-m Chow-parameter tensorT m = E (x,y)∼D [1(y = -1)H m (x)] such that ∥T ′m -T m ∥ F ≤ τ /(4 √ k).Denote by V m the subspace spanned by the left singular vectors of flattened T ′m whose singular values are greater than τ /(4√ k). Moreover, denote by V the union of V 1 , • • • , V k . Then, for γ = Pr (x,y)∼D [y = -1], we have that 1. dim(V ) = O(γ 2 log(1/γ) k k 2 /τ 2 + 1), and 2. ∥proj V (v * )∥ 2 = Ω τ / √ kγ log(1/γ) k/2 .By Lemma 2.4, taking a random unit vector v in V will give us ⟨v,v * ⟩ ≥ ∥proj V (v * )∥/ dim(V ).We are ready to prove Proposition 2.1. For the algorithm pseudocode, see Appendix B.Proof Sketch of Proposition 2.1 . The idea is that the empirical estimate T ′m obtained usingd O(max{t * 2 ,1}) log(1/δ)/ϵ 2 many samples will satisfy ∥T ′m -T m ∥ F ≤ τ /(4 √ k)with high probability. 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/ϵ) -O(t * 2 ) . For ⟨v, w * ⟩ = ϵ -O(1) , the proof relies on a different version of Lemma 2.4.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 * ⟩ = Ω(1/ √ d). Let D ′ be the distribution of x ⊥w conditioned on x ∈ B, where B = {x ∈ R d : ⟨w, x⟩ -t * ≥ 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 h(x) = sign(⟨w ′ , x⟩ -t ′ ) with w ′ = w * ⊥w and |t ′ | ≤ |t * |.Lemma 2.5. Let D be the joint distribution of (x, y) supported on R d × {±1} with marginal D x = N d and ϵ ∈ (0, 1). Suppose D satisfies the reliability condition with respect to fEQUATION3. Pr (x ′ ,y)∼D ′ [y = -1] ≥ ϵ/2.Proof Sketch of Lemma 2.5. Item 1 follows from the definition. For Item 2, we consider two cases: t * > 0; and t * ≤ 0. For the case t * ≤ 0, we prove that the distribution D ′ satisfies the reliability condition with respect to h ′ (x) = sign(⟨w ′ , x⟩), where w ′ = w * ⊥w /∥w * ⊥w ∥ 2 . For the case t * > 0, we prove that the distribution D ′ satisfies the reliability condition with respect to h ′ (x) = sign(⟨w ′ , x⟩ -t ′ ), where w ′ = w * ⊥w /∥w * ⊥w ∥ 2 and t ′ = t * . Then Item 3 follows from the fact that h does not satisfyR + h (D) ≤ ϵ/2.By Lemma 2.5, given any current guess w such that h(x) = sign(⟨w, x⟩ -t * ) does not satisfy R + (h; D) ≤ ϵ/2, the corresponding distribution D ′ satisfies the reliability condition with respect to h ′ and Pr (x,y)∼D ′ [y = -1] ≥ ϵ/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 Ω(1) get a unit vector v such that ⟨v, w⟩ = 0 and ⟨v,w * ⟩ = log(1/ϵ) -O(t * 2 ) .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 in[DKK + 22]). Fix unit vectors v * , v ∈ R d . Let u ∈ R d such that ⟨u, v * ⟩ ≥ c, ⟨u, v⟩ = 0 and ∥u∥ 2 ≤ 1 with c > 0. Then, for v ′ = v+λu ∥v+λu∥2 , with λ = c/2, we have that ⟨v ′ , v * ⟩ ≥ ⟨v, v * ⟩ + λ 2 /2.Notice that because ∥proj ⊥w (w * )∥ 2 is unknown, we cannot always choose the optimal step size λ. Instead, we will use the same λ to do sufficiently many update steps such that after that many updates, we are certain that ∥proj ⊥w (w * )∥ 2 ≤ 3λ. We then take the new step size λ update = λ/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 we know the bias α, t must be either -Φ -1 (α) or Φ -1 (α). For convenience, we assume that t = Φ -1 (α). To account for the case that t = -Φ -1 (α), we can simply run Algorithm 1 twice and pick the output halfspace with the smallest t value (or even run a different efficient algorithm since t ≤ 0 as explained in Appendix B). For convenience, we also assumemin 2 log(1/ϵ) O(log(1/α)) , 2 poly(1/ϵ) = 2 log(1/ϵ) O(log(1/α)). To account for the other case, we can simply initialize the step sizeζ = ϵ c for a sufficiently large constant c instead of ζ = log(1/ϵ) -ct * 2. A detailed version of Algorithm 1 is deferred to Appendix B.Input: ϵ ∈ (0, 1), α ∈ (0, 1/2) and samples access to a joint distribution D of (x, y) supported onR d × {±1} with x-marginal D x = N d . Output: h(x) = sign(⟨w, x⟩ -t) that is ϵ-reliable with respect to the class H α d . 1. Check if Pr (x,y)∼D [y = -1] ≤ ϵ/2 (with sufficiently small constant failure probability). If so, return the +1 constant hypothesis. Set the initial step sizeζ = log(1/ϵ) -ct * 2, where c is a sufficiently large universal constant and t = Φ -1 (α). (x) = sign(⟨w, x⟩ -t) satisfies R + (h; D) ≤ ϵ/2. If so, go to Step (3). (b) With 1/2 probability, let w = -w. Let B = {x ∈ R d : ⟨w, x⟩ -t ≥ 0}, and let D ′ be the distribution of (x ⊥w , y) for (x, y) ∼ D given x ∈ B. Use the algorithm of Proposition 2.1 on D ′ to find a unit vector v such that ⟨v, w⟩ = 0 and v, proj ⊥w (w * )∥proj ⊥w (w * )∥2 ≥ ζ.Then update w as follows: w update = w+λv ∥w+λv∥2 . (c) Repeat Steps (2a) and (2b) c/ζ 2 times, where c is a sufficiently large universal constant, with the same step size λ. After that, update the new step size asλ update = λ/2. 3. Check if h(x) = sign(⟨w, x⟩ -t) satisfies R + (h; D) ≤ ϵ/2. If so, return h and terminate. Repeat Step (2) 2 1/ζ cmany times where c is a 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 α bias. We need to show that with high probability Algorithm 1 returns a hypothesish(x) = sign(⟨w, x⟩ -t) such that R + (h; D) ≤ ϵ and R -(h; D) ≤ R -(f ; D) + ϵ.To do so, it suffices to show thatR + (h; D) ≤ ϵ; given R + (h; D) ≤ ϵ, R -(h; D) ≤ R -(f ; D) + ϵfollows from our choice of t. For convenience, we can assume h never satisfies R + (h; D) ≤ ϵ/2 inStep (2a) (otherwise, we are done). We can also assume that the subroutine in Proposition 2.1 always succeeds since the algorithm repeats Step (2) sufficiently many times. Given the above conditions, using by Fact 2.6, one can show that each time after c/ζ 2 many updates in Step (2b), we must have ∥proj ⊥w w * ∥ 2 ≤ 3λ. Therefore, when we have λ ≤ ϵ/100, then ∥proj ⊥w w * ∥ 2 ≤ 3ϵ/100, which implies R + (h; D) ≤ ϵ/2. 
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 α-biased LTFs. We define the following decision problem over distributions. In order to construct such a family of distributions D, we start by constructing a joint distribution D ′ of (z, y) over R × {±1} such that the marginal distribution of z is N 1 and the conditional distributions z | y = 1 and z | y = -1 both match many moments with the standard Gaussian N 1 . Moreover, there is α probability mass on the positive side of the marginal distribution of z that is purely associated with y = 1 (i.e., E (z,y)∼D [y | z ≥ c] = 1 where c = Φ -1 (1 -α)). We then embed this distribution D along a hidden direction inside the joint distribution of (x, y) on R d × {±1} to construct a family of hard-to-distinguish distributions using the "hidden-direction" framework developed in [DKS17, DKPZ21] .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 of two distributions with pdfs D 1 , D 2 : R d → R + with respect to a distribution with density D : R d → R + , where the support of D contains the support of D 1 and D 2 , is defined asχ D (D 1 , D 2 ) def = R d D 1 (x)D 2 (x)/D(x)dx -1. Furthermore, the χ-squared divergence of D 1 to D is defined as χ 2 (D 1 , D) def = χ D (D 1 , D 1 ).In particular, the framework in [DKS17] allows us to construct a family of2 d Ω(1) distributions on R d × {±1} whose pairwise correlation is d -Ω(n)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 α-biased LTFs under Gaussian marginals with additive error ϵ < α/3.In order to construct such a distribution D ′ of (z, y) supported on R × {±1}, we reparameterize E (z,y)∼D ′ [y|z] as g(z). For a function g : R → R, we use ∥g∥ p = E t∼N1 [|g(t)| p ] 1/p for its L p norm. We let L 1 (R) denote the set of all functions g : R → R that have finite L 1 -norm.We use linear programming over one-dimensional functions in L 1 (R) 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(z) = 1 for all z ≥ c, where c = Φ -1 (1 -3 -2n /4), and(ii) E t∼N1 [g(z)z k ] = 0 for all k ∈ [n].Proof Sketch of Lemma 3.3. We let P n denote the set of all polynomials p : R → R of degree at most n and let L 1 + (R) denote the set of all nonnegative functions in L 1 (R). Then, using linear programming, we will get the following primal:find g ∈ L 1 (R) such that E z∼N1 [p(z)g(z)] = 0 , ∀p ∈ P n E z∼N1 [g(z)h(z)1{t ≥ c}] ≥ ∥h(z)1{z ≥ c}∥ 1 , ∀h ∈ L 1 + (R) E z∼N1 [g(z)H(z)] ≤ ∥H∥ 1 , ∀H ∈ L 1 (R)Then, using (infinite-dimensional) LP duality, we get that the above primal is feasible if and only if there is no polynomial of degree n such thatE t∼N1 [|p(t)|1(t ≤ c)] < E t∼N1 [p(t)1(t ≥ c)].Using Gaussian hypercontractivity (see [Bog98, Nel73] ), one can show that for every polynomial p and c ∈ R, it holdsE z∼N1 [|p(z)|] < 2 • 3 n E z∼N1 [|p(z)|] Pr z∼N1 [z ≥ c] 1/2 .From our choice of the parameter c, we have thatPr z∼N1 [z ≥ c] ≤ 3 -2n /4; thus, E z∼N1 [|p(z)|] < E z∼N1 [|p(z)|],which is a contradiction. Therefore, such a polynomial p cannot exist.We have proven the existence of the function g in Lemma 3.3. Now, we construct a joint distribution of (z, y) on R × {±1} such that E[y|z] is exactly g, as we discussed in the proof outline. For a joint distribution D of (x, y) supported on X × {±1}, we will use D + to denote the conditional distribution of x given y = 1; and D -for the distribution of x given y = -1. Lemma 3.4. For any sufficiently large n ∈ N, there exists a distribution D on R × {±1} such that for (z, y) ∼ D:(i) the marginal distribution D z = N 1 ; (ii) E (z,y)∼D [y|z = z ′ ] = 1 for all z ′ ≥ Φ -1 (1 -3 -2n /4); (iii) E (z,y)∼D [y] = 0 and E (z,y)∼D [z k ] = E (z,y)∼D [z k | y = 1] = E (z,y)∼D [z k | y = -1] for all k ∈ [n]; (iv) χ 2 (D + , N 1 ), χ 2 (D -, N 1 ) = O(1).Proof Sketch for Lemma 3.4. The properties here directly follow from the properties of g.Using the framework introduced in [DKS17, DKPZ21], we can construct a set of alternative hypothe-sis distributions D = {D v : v ∈ V } on R d × {±1}, where V is a set of exponentially many pairwise nearly-orthogonal vectors and the marginal distribution of each D v on direction v is the distribution D in Lemma 3.4. This effectively embeds the distribution D in a 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.Proof Sketch of the SQ hardness part of Theorem 1.3. Let D be the set of distributions discussed above. We also let D null be the joint distribution of (x, y) such that x ∼ N d and y ∼ Bern(1/2) independent of x. Then, using standard SQ dimension techniques, one can show that any SQ algorithm that solves B(D, D null ) requires either queries of tolerance at most d -Ω(log 1 α ) or makes at least 2 d Ω(1) queries. By reducing the decision problem B(D, D null ) to reliably learning α-biased LTFs with ϵ < α/3 accuracy, we get the lower bound part of the statement in Theorem 1.3.Organization The supplementary material is structured as follows: Appendix A includes additional preliminaries. Appendix B includes the omitted proofs from Section 2. Finally, Appendix C includes the omitted proofs from Section 3.We use S d-1 to denote the d-dimensional unit sphere, i.e., S d-1 def = {x ∈ R d : ∥x∥ 2 = 1}.Basics of the SQ Model In order to give an 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. D (D 1 , D 2 ) def = R d D 1 (x)D 2 (x)/D(x)dx -1. Furthermore, the χ-squared divergence of D 1 to D is defined as χ 2 (D 1 , D) def = χ D (D 1 , D 1 ).Then we introduce the following definitions and lemmata from [DKS17] showing pairwise correlation implies an SQ lower bound.Lemma A.2. Let B(D, D) be a decision problem, where D is the reference distribution and D is a class of distribution. For γ, β > 0, let s = SD(B, γ, β). For any γ ′ > 0, any SQ algorithm for B requires queries of tolerance at most √ γ + γ ′ or makes at least sγ ′ /(β -γ) queries.Definition A.3. We say that a set of s distribution D = {D 1 , • • • , D s } over R d is (γ, β)-correlated relative to a distribution D if χ D (D i , D j ) ≤ γ for all i ̸ = j,We require the following definitions used in our work.Definition A.5 (Normalized Hermite Polynomial). For k ∈ N, we define the k-th probabilist's Hermite polynomials He k : R → R as Hek (t) = (-1) k e t 2 /2 • d k dt k e -t 2 /2 . We define the k-th normalized Hermite polynomial h k : R → R as h k (t) = He k (t)/ √ k!.Furthermore, we use multivariate Hermite polynomials in 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 k ∈ N and x ∈ R d , we define the k-th Hermite tensor as(H k (x)) i1,i2,...,i k = 1 √ k! Partitions P of [k]into sets of size 1 and 2 {a,b}∈P(-I ia,i b ) {c}∈P x ic .We also give the following remark that fully reliable learning (see [KKM12] for the definition) reduces to one-sided reliable learning defined in Definition 1.1. The proof is already implicitly stated in the proof of Theorem 3 in [KKM12] .Fact A.7. For a joint distribution D of (x, y) supported on X × {±1}, let h + : X → {±1} (resp. h -: X → {±1}) be a hypothesis that is ϵ/4-reliable with respect to the concept class C on distribution D for positive labels (resp. for negative labels). Let hypothesis h be defined as h(x) = 1 if h + (x) = h -(x) = 1, h(x) = -1 if h + (x) = h -(x)= -1 and h(x) =? otherwise. Then h is ϵ close to the best fully reliable sandwich hypothesis for C on distribution D.Proof Sketch. We first show thatR + (h; D), R -(h; D) ≤ ϵ. Notice that R + (h; D) = Pr (x,y)∼D) [h(x) = 1 ∧ y = -1] ≤ Pr (x,y)∼D) [h + (x) = 1 ∧ y = -1] ≤ ϵ.The same holds for negative labels.To show Pr (x,y)∼D [h(x) =?] is ϵ-suboptimal. Assume, for the purpose of contradiction, there is a h′ such that R + (h ′ ; D), R -(h ′ ; D) ≤ ϵ and Pr (x,y)∼D [h ′ (x) =?] < Pr (x,y)∼D [h(x) =?] -ϵ. Notice that Pr (x,y)∼D [h(x) =?] = Pr (x,y)∼D [h + (x) = 1 ∧ h -(x) = -1] + Pr (x,y)∼D [h + (x) = -1 ∧ h -(x) = 1] ≤1 -Pr (x,y)∼D [h + (x) = 1] -Pr (x,y)∼D [h -(x) = -1] + Pr (x,y)∼D [h + (x) = 1 ∧ h -(x) = -1] ≤1 -Pr (x,y)∼D [h + (x) = 1] -Pr (x,y)∼D [h -(x) = -1] + ϵ/2 .Thus,EQUATIONThen, defineh ′ + : X → {±1} as h ′ + (x) = 1 if h ′ (x) = 1 and h ′ + (x) = -1 otherwise (h ′ -is defined similarly). We get Pr (x,y)∼D [h ′ + (x) = 1] + Pr (x,y)∼D [h ′ -(x) = -1] = 1 -Pr (x,y)∼D [h ′ (x) =?]. Using Equation (1) and Pr (x,y)∼D [h ′ (x) =?] < Pr (x,y)∼D [h(x) =?] -ϵ, we get Pr (x,y)∼D [h + (x) = 1]-Pr (x,y)∼D [h -(x) = -1] < Pr (x,y)∼D [h ′ + (x) = 1]-Pr (x,y)∼D [h ′ -(x) = -1]-ϵ/2 . Therefore, either Pr (x,y)∼D [h + (x) = 1] < Pr (x,y)∼D [h ′ + (x) = 1] -ϵ/4 or Pr (x,y)∼D [h -(x) = -1] < Pr (x,y)∼D [h ′ -(x) = -1] -ϵ/4, Thus, either h + or h -is not ϵ/4-suboptimal.This gives a contradiction.We define the bias of a halfspace h : R d → {±1} as min(Pr We show that for the problem in Theorem 1.3, in the case of ϵ ≥ 2α, the algorithm can just return one of the constant hypotheses. Let h + (resp. h -) be the +1 (resp. -1) constant hypothesis. Fact B.1. For the problem defined in Theorem 1.3, the case where ϵ ≥ 2α can be efficiently solved by returning h + if R + (h + ; D) ≤ 3ϵ/4 and returning h -otherwise.x∼N d [h(x) = 1], Pr x∼N d [h(x) = -1]),Proof. When the algorithm returns h + , it is easy to see that h + satisfies the reliable learning requirement in Definition 1.1. So we only consider the case that the algorithm returns h -.Given the algorithm returns h -, either there is an α-biased LTF f such that R + (f ; D) = 0 or none of the α-biased LTFs f satisfies R + (f ; D) = 0. For the case that none of the α-biased LTFs f satisfies R + (f ; D) = 0, it is easy to see h -is a valid answer from the definition of Definition 1.1. For the case that there is an α-biased LTF f such that R + (f, D) = 0, since the algorithm did not return h + , it must be the case that Pr (x,y)∼D [y = -1] > 3ϵ/4 > α. Therefore, we havePr x∼N d [f (x) = -1] = 1 -α. Thus, we get R + (h -, D) = 0 and R -(h -, D) ≤ R -(f, D) + α.This shows h -is ϵ reliable with respect to all α biased LTFs. This completes the proof.Theorem B.2 (Main Algorithmic Result). Let ϵ ∈ (0, 1/2) and let D be a joint distribution of (x, y)supported on R d × {±1} with marginal D x = N d . Let f = argmin f ∈H d ∧ R+(f ;D)=0 R -(f ; D)be the optimal halfspace and α be its bias which is unknown. Then, there is an algorithm that uses N = d O(log(min{1/α,1/ϵ})) min 2 log(1/ϵ) O(log(1/α)) , 2 poly(1/ϵ) many samples from D, runs in poly(N, d, 1/ϵ) time and with high probability returns a hypothesis h(x) = sign(⟨w, x⟩ -t) that is ϵ-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 Pr x∼N d [f (x) = -1] ≤ 1/2, then the problem can be solved efficiently. Lemma B.3. Let D be the joint distribution of (x, y) supported on R d × {±1} with the marginal D x = N d and ϵ ∈ (0, 1). Suppose the optimal halfspace f = argminf ∈H d ∧ R+(f ;D)=0 R -(f ; D) satisfies Pr x∼N d [f (x) = -1] ≤ 1/2.Then, there is an algorithm that reliably learns LTFs on D using N = O(d/ϵ 2 ) many samples and poly(N, d) running time.Proof. The algorithm is the following.1. First check if Pr (x,y)∼D) [y = -1] ≤ ϵ with sufficiently small constant failure probability. If so, return the +1 constant hypothesis.2. Otherwise, draw m = (d/ϵ) c many samplesS = {(x 1 , y 1 ), • • • , (x m , y m )} conditioned on y = -1. ByStep 1, the sampling efficiency here is Ω(ϵ) with high probability.3. solve the following semidefinite program for w ′ and t ′ :minimize t ′ such that ⟨w ′ , x⟩ -t ′ ≤0 , ∀(x, y) ∈ S ∥w ′ ∥ 2 ≤1Return the hypothesis h(x) = sign(⟨w, x⟩ -t) where w = w ′ /∥w ′ ∥ 2 and t = t ′ /∥w∥ ′ .Let f (x) = sign(⟨w [h(x) = 1] ≥ Pr (x,y)∼D [f (x) = 1]. Therefore, R -(h; D) = Pr (x,y)∼D [y = 1] -Pr (x,y)∼D [y = 1 ∧ h(x) = 1] = Pr (x,y)∼D [y = 1] -Pr (x,y)∼D [h(x) = 1] + R + (h; D) ≤ Pr (x,y)∼D [y = 1] -Pr (x,y)∼D [f (x) = 1] + ϵ = R -(f ; D) + ϵ .This completes the proof.We [h(x) = -1] ≤ 1 -α ≤ 1 -α f + ϵ/100 = Pr x∼N d [f (x) = -1] + ϵ/100 . Thus, R -(h; D) = Pr (x,y)∼D [y = 1] -Pr (x,y)∼D [y = 1 ∧ h(x) = 1] = Pr (x,y)∼D [y = 1] -Pr (x,y)∼D [h(x) = 1] + R + (h; D) ≤ Pr (x,y)∼D [y = 1] -Pr (x,y)∼D [f (x) = 1] + ϵ = R -(f ; D) + ϵ .This completes the proof.For convenience, we assume that α is known. This can be assumed without loss of generality as we discussed in Theorem B.2. Theorem B.4. Let ϵ ∈ (0, 1/2), α ∈ (0, 1/2] and let D be a joint distribution of (x, y) supported on R d × {±1} with marginal D x = N d . Assume that there is a halfspace in H α d that is reliable with respect to D. Then, there is an algorithm that uses N = d O(log(min{1/α,1/ϵ})) min 2 log(1/ϵ) O(log(1/α)) , 2 poly(1/ϵ) many samples from D, runs in poly(N, d, 1/ϵ) time and with high probability returns a hypothesis h(x) = sign(⟨w, x⟩ -t) that is ϵ-reliable with respect to the class of H α d .We provide the omitted proofs from Section 2.Notice that for any polynomial p such that E z∼N1 [p(z)] = 0, we haveE (x,y)∼D [y p(⟨w * , x⟩)] = -2 E (x,y)∼D [1(y = -1) p(⟨w * , x⟩)] .Therefore, it suffices for us to show that there is a zero mean and unit variance polynomial p such thatE (x,y)∼D [1(y = -1) p(⟨w * , x⟩)] = 2 -O(t * 2 ) Pr (x,y)∼D [y = -1] .Here, we will consider the sign-matching polynomial from [DKK + 22], which satisfies the following properties: Proof. We consider the polynomial p defined as:p(z) = q(z) - q(b) r(b) r(z) ,where q(z) = z 3k , r(z) = z 2k -(2k -1)!! and k is a sufficiently large odd integer such that 2|b| ≤ √ k ≤ 4 max(|b|, 1). We then take p(z) = p(z)/ E u∼N1 [p 2 (u)].For convenience, we first note that from Stirling's approximation for m ∈ Z + ,(m/2) m ≤ (2m -1)!! ≤ (2m) m .To prove that sign(p(z)) = sign(z -b), we first show that q(b) r(b) ≤ 0. Since q(b) ≥ 0, we just need to show r(b) ≤ 0. Notice r(b) = b 2k -(2k -1)!!, since 2|b| ≤ √ k and (2k -1)!! ≥ (k/2) k , thus r(b) ≤ ( √ k/2) 2k -(k/2) k ≤ 0. Therefore, considering q(z) = z 3k and r(z) = z 2k -(2k -1)!!, p(z) = q(z) - q(b) r(b) r(z)must be monotone increasing for z ≥ b and p(z) must also be monotone increasing for z ≥ b. Notice that p(b) = 0; therefore, p(z) > 0 for z > b. To show p(z) < 0 for z < -b, we prove it for the cases z ∈ [-b, +b) and z < -b. For z ∈ [-b, +b), notice that due to q(b) r(b) ≤ 0 and definition of q(z) and r(z),p(z) = q(z) - q(b) r(b) r(z) ≤ q(b) - q(b) r(b) r(b) < p(b) = 0 .Then, for z ≤ -b, we show that p(z) is monotone increasing. Notice that the derivative p′ (z) = kz 2k-1 (3z k -2 q(b) r(b) ), for z ≤ -b < 0, this is positive if and only if 3z k -2 q(b) r(b) < 0. If we can show b k ≥ -2 3 q(b)/r(b), then it is immediate that for any z ≤ -b, 3z k -2 q(b) r(b) < 0. The condition b k ≥ -2 3 q(b)/r(b) can be further simplified to (2k -1)!!/b 2k ≥ 5/3. Then considering 2b < √ k and (2k -1)!! ≥ (k/2) k , we have (2k -1)!!/b 2k ≥ (k/2) k /( √ k/2) 2k ≥ 2 k ,thus, the condition holds. Therefore p′ (z) > 0 for z < -b and p(z) must be monotone increasing for z < -b. Then combined with p(-b) < 0 which is implied from the previous case (z ∈ [-b, b]), we have p(z) < 0 for z < -b.For the Property 2, we show that p(z Given Claim B.5, we let p be the polynomial in Claim B.5 with b = -max(2|t * |, 4). Then, given that D satisfies the reliability condition with respect to f , it is easy to see the polynomial p(⟨w * , x⟩) satisfies the requirements. This completes the proof of Lemma 2.2.) = 2 -Θ(k) for z ∈ [0, b/2], z ∈ [-b/2, 0], z ∈ [-b, -b/2] and z ∈ [-∞, -b] separately. For z ∈ [0, b/2] notice that p(z) is convex for z ∈ [0, b]; therefore, it suffices to show p(0) = 2 -Θ(k) . Note that p(0) = q(b) r(b) (2k -1)!!/ E u∼N1 p2 (u), and we have q(b) r(b) ≥ b 3k / max(b 2k , (2k -1)!!) ≥ Ω(k) k/2 . Therefore, since E u∼N1 [p 2 (u)] ≤ (O(k)) 3kWe start by bounding the Frobenius norm of T m , i.e., ∥T m ∥ F . Notice that by taking p : R → R to be any degree-m polynomial such thatE x∼N d [p(x)] = 0 and E x∼N d [p(x) 2 ] = 1, then ∥T m ∥ F = max p E (x,y)∼D [1(y = -1)p(x)].We leverage the following standard fact about the concentration of polynomials lemma known as Bonami-Beckner inequality or simply Gaussian hypercontractivity. Fact B.6 (Hypercontractivity Concentration Inequality [Bog98, Nel73] ). Consider any m-degree, zero-mean and unit variance polynomial p : R d → R with respect to N d . Then, for any λ ≥ 0Pr x∼N d p(x) -E u [p(u)] ≥ λ ≤ e 2 e -(cλ 2 ) 1/m, where c is an absolute constant.Using Fact B.6, we have that for any zero mean and unit variance polynomial p,E (x,y)∼D [1(y = -1)p(x)] ≤ E (x,y)∼D [1(y = -1)|p(x)|] ≤ ∞ 0 min γ, e 2 e -(cλ 2 ) 1/m dλ = O γ log(1/γ) m/2 . Therefore, ∥T m ∥ F = O γ log(1/γ) m/2 .To prove the Property 1, since∥T ′m ∥ F ≤ ∥T m ∥ F + τ /(4 √ k) = O γ log(1/γ) m/2 + τ /(4 √ k),there can be at most∥T m ∥ 2 F / τ / √ k 2 = O(γ 2 log(1/γ) m k/τ 2 + 1) many singular vectors with singular values greater than τ /(4√ k). Therefore, dim(V ) is at most O(γ 2 log(1/γ) m k/τ 2 + 1).For the Property 2, suppose ∥projV (v * )∥ 2 = o τ / √ kγ log(1/γ) k/2, then we have for any m,∥v * ⊤ T ′m ∥ 2 ≤ ∥v * ⊤ T m ∥ 2 + τ /(4 √ k) ≤ ∥T m ∥ F ∥proj V (v * )∥ 2 + τ /(4 √ k)∥proj ⊥V (v * )∥ 2 + τ /(4 √ k) ≤ (5/8)τ / √ k .However, sinceE (x,y)∼D [1(y = -1)p(⟨v * , x⟩)] = k m=1 a i v * ⊤ T m v * ⊗m-1 ≥ τ for some a 2 1 + • • • + a 2 k = 1, we know there must be an m that v * ⊤ T m v * ⊗m-1 ≥ τ / √ k .Therefore, we can write∥v * ⊤ T ′m ∥ 2 ≥ ∥v * ⊤ T m ∥ 2 -τ /(4 √ k) ≥ τ / √ k -τ /(4 √ k) = (3/4)τ / √ k , which contradicts ∥v * ⊤ T ′m ∥ 2 ≤ (5/8)τ / √ k.This completes the proof.We first give the pseudocode for the algorithm in Proposition 2.1. 1. Let c 1 be a sufficiently large universal constant and c 2 be a sufficiently large universal constant depending on c 1 . Let S be a set of N = d c2max(t * 2 ,1) log(1/δ)/ϵ 2 many samples from D. For m = 1, • • • , c 1 t * 2 , with 1/2 probability, takeT ′m = E (x,y)∼uS [1(y = -1)H m (x)] ,to be the empirical chow-tensor on negative samples. Otherwise, takeT ′m = E (x,y)∼uS [yH m (x)] ,to be the empirical Chow-tensor on all samples. Let γ be the empirical estimation of Pr (x,y)∼D [y = -1] with error at most ϵ/100 with a sufficiently small constant failure probability.2. Take T′m ∈ R d×d m-1 to be the flattened version of T ′m , and let V m be the subspace spanned by the left singular vectors of T′m whose singular values are greater than 2 -ct * 2 γ where c is a sufficiently large constant. Let V be the union of all V m and output v to be a random unit vector chosen from V .Algorithm 2: Finding a Direction with High Correlation.We 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 ∈ Z + , and ϵ, δ ∈ (0, 1). Let D be a on R d × [±1] with standard normal marginals. There is an algorithm that with N = d O(m) log(1/δ)/ϵ 2 samples and poly(d, N ) runtime, outputs an approximation T ′m of the order-m Chow-parameter tensor T m = E (x,y)∼D [yH m (x)] such that with probability 1 -δ, it holds ∥T ′m -T m ∥ F ≤ ϵ.Proof. Let T ′m be the empirical estimation of T m using N = d cm log(1/δ)/ϵ 2 for sufficiently large universal constant c. We start by showingE (x,y)∼D ∥yH m (x)∥ 2 F ≤ d m . Notice that, E (x,y)∼D ∥yH m (x)∥ 2 F = E (x,y)∼D y 2 ∥H m (x)∥ 2 F ≤ E (x,y)∼D ∥H m (x)∥ 2 F = E x∼R d ∥H m (x)∥ 2 F .Notice that each entry of H m (x) must be some αh(x) where α ∈ [0, 1] and h(x) is a unit variance Hermite polynomial. Therefore,E (x,y)∼D ∥H m (x)∥ 2 F ≤ d m and thus E (x,y)∼D ∥yH m (x)∥ 2 F ≤ d m .Using the above, we haveE (x,y)∼D ∥yH m (x) -T m ∥ 2 F = E (x,y)∼D ∥yH m (x)∥ 2 F -∥T m ∥ 2 F ≤ d m .Then, applying Chebyshev's inequality gives ∥T ′m -T m ∥ F ≤ ϵ.We prove Proposition 2.1 for two cases: (a) max(log 1) . We first prove Case (a) as the other case is similar. For Case (a), it suffices for us to prove that ⟨v, w * ⟩ = log(1/ϵ) -O(t * 2 ) happens with Ω(1) probability given the algorithm chooses T ′m = E (x,y)∼uS [1(y = -1)H m (x)] (which happens with 1/2 probability). Let k = c 1 t * 2 and τ /(4(1/ϵ) -O(t * 2 ) , ϵ -O(1) ) = log(1/ϵ) -O(t * 2 ) ; and (b) max(log(1/ϵ) -O(t * 2 ) , ϵ -O(1) ) = ϵ -O(√ k) = 2 -ct * 2 γ. By Fact B.7, we have ∥T ′m -T m ∥ F ≤ τ /(4 √ k).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,⟨v, w * ⟩ = Ω τ / √ kγ log(1/γ) k/2 dim(V ) 1/2 = Ω τ 2 / log(1/γ) k k 3/2 γ 2 = Ω log(1/γ) -O(t * 2 ) k -3/2 . Since Pr (x,y)∼D [y = -1] ≥ ϵ, we have γ = Ω(ϵ). Also, considering k = O(max{t * 2 , 1}) = O (log(1/ϵ)), we get ⟨v, w * ⟩ = log(1/ϵ) -O(t * 2 ) .For Case (b), the proof remains the same except we take T ′m = E (x,y)∼uS [yH m (x)] and use fact below instead of Lemma 2.4. T m = E (x,y)∼D [yH m (x)] such that ∥T ′m -T m ∥ F ≤ τ /(4 √ k).Denote by V m the subspace spanned by the left singular vectors of flattened T ′m whose singular values are greater than τ /(4√ k). Moreover, denote by V the union of V 1 , • • • , V k . Then we have that 1. dim(V ) ≤ 4k/τ 2 , and 2. ∥proj V (v * )∥ 2 ≥ τ / 4 √ k .Then the same argument will give ⟨v, w * ⟩ = ϵ -O(1) . The above described algorithm uses at most N = d O(t * 2 ) /ϵ 2 samples and poly (N, 1/ϵ) runtime. This completes the proof of Proposition 2.1.Item 1 follows from the definition of D ′ and the fact that D has distribution D x = N d .For proving Item 2, we consider two cases: The first case is when t * > 0 and the second one when t * ≤ 0. For the case t * ≤ 0, we prove that the distribution D ′ satisfies the reliability condition with respect to h ′ (x) = sign(⟨w ′ , x⟩) where w ′ = w * ⊥w /∥w * ⊥w ∥ 2 . Notice that for any (x, y) such that x ∈ B and h ′ (x ⊥w ) = 1, we havef (x) = sign(⟨w * , x⟩ -t * ) = sign(⟨proj ⊥w (w * ), x⟩ + ⟨proj w (w * ), x⟩ -t * ) = sign(⟨w * ⊥w , x ⊥w ⟩ + ⟨proj w (w * ), x⟩ -t * ) ,where ⟨w * ⊥w , x ⊥w ⟩ ≥ 0 since h ′ (x) = sign(⟨w * ⊥w , x ⊥w ⟩/∥w * ⊥w ∥ 2 ) ≥ 0. Then we havef (x) ≥ sign(⟨proj w (w * ), x⟩ -t * ) = sign(⟨proj w (w * )/∥proj w (w * )∥ 2 , x⟩ -t * /∥proj w (w * )∥ 2 ≥ sign(⟨w, x⟩ -t * ) (2) ≥ sign(⟨w, x⟩ -t) = h(x) = +1 ,where Inequality 2 follows from the fact that ⟨w, w * ⟩ > 0, ∥proj w (w * )∥ 2 ∈ (0, 1] and t * ≤ 0. Since D satisfies the reliability condition with respect to f , we have that it must be the case y = +1. Therefore, D ′ satisfies the reliability condition with respect to h ′ .For the case t * > 0, we prove that the distribution D ′ satisfies the reliability condition with respect to h ′ (x) = sign(⟨w ′ , x⟩ -t ′ ) where w ′ = w * ⊥w /∥w * ⊥w ∥ 2 and t ′ = t * . Notice that for any (x, y) such that x ∈ B and h ′ (x ⊥w ) = 1, we havef (x) = sign(⟨w * , x⟩ -t * ) = sign(⟨proj ⊥w w * , x⟩ + ⟨proj w w * , x⟩ -t * ) = sign ∥w * ⊥w ∥ 2 ⟨w ′ , x⟩ -∥w * ⊥w ∥ 2 t * + ⟨proj w w * , x⟩ -(1 -∥w * ⊥w ∥ 2 )t * , where ∥w * ⊥w ∥ 2 ⟨w ′ , x⟩ -∥w * ⊥w ∥ 2 t * ≥ 0 since h ′ (x) = +1. Then we have f (x) ≥ sign(⟨proj w w * , x⟩ -(1 -∥w * ⊥w ∥ 2 )t * ) = sign 1 -∥w * ⊥w ∥ 2 2 ⟨w, x⟩ -(1 -∥w * ⊥w ∥ 2 )t * ≥ sign 1 -∥w * ⊥w ∥ 2 2 (⟨w, x⟩ -t * ) = h(x) = 1 ,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 to 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 R + (h; D) ≥ ϵ/2 impliesPr (x ′ ,y)∼D ′ [y = -1] = R + (h; D)/ Pr (x,y)∼D (x ∈ B) ≥ ϵ/2 .This completes the proof.We first give the algorithm in Theorem B.4, which is a more detailed version of Algorithm 1.Input: ϵ ∈ (0, 1), α ∈ (0, 1/2) and samples access to a joint distribution D of y) supported on R d × {±1} with x-marginal D x = N d . Output: h(x) = sign(⟨w, x⟩ -t) that is ϵ-reliable with respect to the class H α d . 1. Check if Pr (x,y)∼D [y = -1] ≤ ϵ/2 (with sufficiently small constant failure probability). If so, return the +1 constant hypothesis. If the parameters satisfymin 2 log(1/ϵ) O(log(1/α)) , 2 poly(1/ϵ) = 2 log(1/ϵ) O(log(1/α)) , then set the correlation parameter ζ = log(1/ϵ) -ct * 2, where c is a sufficiently large universal constant. Otherwise, set ζ = ϵ c for a sufficiently large universal constant c. For t = -Φ -1 (α) and t = Φ -1 (α), do Steps (2) and (3). Then, update w as follows: w update = w+λv ∥w+λv∥2 . (c) Repeat Steps (2a) and (2b) c/ζ 2 times, where c is a sufficiently large universal constant, with the same step size λ. After that, update the new step size asλ update = λ/2. 3. Check if h(x) = sign(⟨w, x⟩ -t) satisfies R + (h; D) ≤ ϵ/2.If so, add it in the set S. For each choice of value t in Step (1), repeat Step (2) 2 1/ζ c many times where c is 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,t)∈S t. Return the -1 constant hypothesis if S is empty.Algorithm 3: Reliably Learning General Halfspaces with Gaussian Marginals (detailed version of Algorithm 1).Proof of Lemma 2.5. Without loss of generality, we assume ϵ > α for the following reason. Suppose α ≤ ϵ, 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 α bias, namely,f = argmin f ∈H α d ∧R+(h;D)=0 R -(f ; D) .We prove that with high probability, Algorithm 3 returns a hypothesis h(x) = sign(⟨w, x⟩ -t) such that R + (h; D) ≤ ϵ and R -(h; D) ≤ R -(f ; D) + ϵ.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/ζ) returns a h with R + (h; D) ≤ ϵ/2. For convenience, we assume h never satisfies R + (h; D) ≤ ϵ/2 in 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 * ⟩ ≥ 0, since both happen with constant probability and we are running the update at most O(log(1/ϵ)/ζ 2 ) = poly(1/ζ) many times.Let η = ∥proj ⊥w w * ∥ 2 . Now, we will prove by induction that each time after c/ζ 2 many updates in step (2b), we always have ∥proj ⊥w w * ∥ 2 ≤ 3λ (without loss of generality, we assume λ is always at most a 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 v always satisfies v, proj ⊥w (w * ) η ≥ ζ, which implies ⟨v, proj ⊥w (w * )⟩ ≥ ηζ. Then we have ⟨w, w * ⟩ = 1 -η 2 ≥ 1 -η 2 . When we update w, there are two possibilities. Either λ > ηζ/2 or λ ≤ ηζ/2. If λ ≤ ηζ/2, using Fact 2.6, we will have ⟨w update , w * ⟩ ≥ ⟨w, w * ⟩ + λ 2 /2. If λ > ηζ/2, we haveproj ⊥wupdate (w * ) 2 = ∥proj ⊥w * (w update )∥ 2 ≤ ∥proj ⊥w * + λv)∥ 2 ≤ ∥proj ⊥w * (w)∥ 2 + λ ≤ 3λ .For the base case, when we do the first group of c/ζ 2 many updates, combining the two cases above and the fact that λ = ζ ≥ ηζ gives that after c/ζ 2 many updates, we must have ∥proj ⊥w w * ∥ 2 ≤ 3λ.For the induction case, given η ≤ 6λ (which follows from the previous group of c/ζ 2 many updates), combining the two cases above gives that after c/ζ 2 many updates, we must have ∥proj ⊥w w * ∥ 2 ≤ 3λ. This proves that after each group of c/ζ 2 many updates, we have ∥proj ⊥w w * ∥ 2 ≤ 3λ.Therefore, when we have λ ≤ ϵ/100, we get ∥proj ⊥w w * ∥ 2 ≤ 3ϵ/100, which implies R + (h; D) ≤ ϵ/2 since D satisfies the reliability condition with respect to f . Given R + (h; D) ≤ ϵ/2, using the fact that t-t * ≤ 0 (since we always output the hypothesis with the smallest t) impliesPr (x,y)∼D [h(x) = 1] ≥ Pr (x,y)∼D [f (x) = 1], we have that R -(h; D) = Pr (x,y)∼D [y = 1] -Pr (x,y)∼D [y = 1 ∧ h(x) = 1] = Pr (x,y)∼D [y = 1] -Pr (x,y)∼D [h(x) = 1] + R + (h; D) ≤ Pr (x,y)∼D [y = 1] -Pr (x,y)∼D [f (x) = 1] + ϵ = R -(f ; D) + ϵ .This completes the proof.We first restate our main SQ hardness result. Theorem C.1 (SQ Lower Bound for Reliable Learning). For any α > 0 that is at most a sufficiently small absolute constant and ϵ ∈ (0, α/3), any SQ algorithm that reliably learns α-biased LTFs (for positive labels) on R d under Gaussian marginals to additive error ϵ either (i) requires at least one query of tolerance at most d -Ω(log( 1 α )) , or (ii) requires at least 2 d Ω(1) queries.We let P n denote the set of all polynomials p : R → R of degree at most n and let L 1 + (R) denote the set of all nonnegative functions in L 1 (R). First, we write the conditions as the primal linear program.find g ∈ L 1 (R) such that E z∼N1 [p(z)g(z)] = 0 , ∀p ∈ P n g(z) ≥ 1 , ∀z ≥ c ∥g∥ ∞ ≤ 1 By introducing variables H ∈ L 1 (R) and h ∈ L 1 + (R), we rewrite the primal LP as find g ∈ L 1 (R) such that E z∼N1 [p(z)g(z)] = 0 , ∀p ∈ P n E z∼N1 [g(z)h(z)1{z ≥ c}] ≥ ∥h(z)1{z ≥ c}∥ 1 , ∀h ∈ L 1 + (R) E z∼N1 [g(z)H(z)] ≤ ∥H∥ 1 , ∀H ∈ L 1 (R)The following fact is an application of (an infinite generalization of) LP duality: Claim C.2. The LP above is feasible if there exists no polynomial p of degree n such thatE z∼N1 [|p(z)|1(z ≤ c)] < E z∼N1 [p(z)1(z ≥ c)] .Proof of Claim C.2. First, we introduce some notation. We use ( h, c) for the inequality E [β(z) h(z)] + c ≤ 0, where h ∈ L 1 (R) and c ∈ R. Moreover, let S be the set that contains all such tuples that describe the target system. For the set S, the closed convex cone over L 1 (R) × R is the smallest closed set S + satisfying the following: (a) if A ∈ S + and B ∈ S + then A + B ∈ S + ; and (b) if A ∈ S + then λA ∈ S + for all λ ≥ 0. 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 1 of [Fan68] ). If X is a locally convex, real separated vector space. Then, a linear system described by S is feasible (i.e., there exists a g ∈ X * ) if and only if (0, 1) ̸ ∈ S + .Our dual LP is defined by the following inequalities:(a) (p, 0) for p ∈ P n ;(b) (-h, -∥ h∥ 1 ) for all h(z) = h(z)1{z ≥ c}, where h ∈ L 1 + (R); and(c) and (H, -∥H∥ 1 ) for all H ∈ L 1 (R).Furthermore, the LP is also equivalent to breaking the last inequality into two, i.e., ( H1 , -∥ H1 ∥ 1 ) for all H1 (z) = H 1 (z)1{z < c}, where H 1 ∈ L 1 (R), and ( H2 , -∥ H2 ∥ 1 ) for all H2 (z) = H 2 (z)1{z ≥ c} where H 2 ∈ L 1 + (R). By taking the convex cone defined from the above inequalities, we get the following setS + = p -h + H1 + H2 , ∥ h∥ 1 -∥ H1 + H2 ∥ 1 p ∈ P n , h(z) = h(z)1{z ≥ c} for h ∈ L 1 + (R), H1 (z) = H 1 (z)1{z < c} for H 1 ∈ L 1 (R), H2 (z) = H 2 (z)1{z ≥ c} for H 2 ∈ L 1 + (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 a sequence (p i , h i , H1,i , H2,i ) so that (F i , λ i ) = p i -hi + H1,i + H2,i , ∥ hi ∥ 1 -∥ H1,i + H2,i ∥ 1 has F i converges to F lim with respect to L 1 -norm and λ i converges to λ lim . We claim then that (F lim , λ lim ) ∈ S + . First, notice that∥p i ∥ 1 ≤ ∥F i ∥ 1 + ∥ hi ∥ 1 + ∥ H1,i ∥ 1 + ∥ H2,i ∥ 1 ≤ ∥F i ∥ 1 + 3.Therefore, there must be a k such that for any i ≥ k, ∥p i ∥ 1 ≤ ∥F lim ∥ 1 + 4.Then, since an L 1 ball in P n with radius ∥F lim ∥ 1 + 4 is compact, there must be a subsequence of (p i , h i , H1,i , H2,i ) such that p i converges to p lim for some p lim ∈ P n . Notice that due to the positivity of hi and H2,i , it must be hi = (F i -p i ) -1(z ≥ c), H2,i = (F i -p i ) + 1(z ≥ c) and H1,i = (F i -p i )1(z < c). Therefore, hi , H1,i and H2,i converge to hlim = (F lim -p lim ) -1(z ≥ c), H2,lim = (F lim -p lim ) + 1(z ≥ c) and H1,lim = (F lim -p lim )1(z < c) respectively. Then by taking (p lim , h lim , H1,lim , H2,lim ), one can see that (F lim , λ lim ) ∈ S + .It only remains to verify that if there exists a polynomial p of degree n such thatE z∼N1 [|p(z)|1(z ≤ c)] < E z∼N1 [p(z)1(z ≥ c)] ,then (0, 1) ∈ S + . Let p be the polynomial satisfying the above. We can simply take hi = (p i ) + 1(z ≥ c), H2,i = (p i ) -1(z ≥ c) and H1,i = -p i 1(z < c). This givesp i -hi + H1,i + H2,i , ∥ hi ∥ 1 -∥ H1,i + H2,i ∥ 1 = (0, k) ∈ S + ,wherek = ∥(p i ) + 1(z ≥ c)∥ 1 -∥(p i ) -1(z ≥ c) -p i 1(z < c)∥ 1 = ∥(p i ) + 1(z ≥ c)∥ 1 -∥(p i ) -1(z ≥ c)∥ 1 -∥p i 1(z < c)∥ 1 = E z∼N1 [p(z)1(z ≥ c)] -E z∼N1 [|p(z)|1(z ≤ c)] > 0Then, by properly rescaling (0, k), we get (0, 1) ∈ S + . This completes the proof.Given Claim to prove Lemma 3.3, it only remains to show that there does not exist a polynomial p of degree at most n such thatE z∼N1 [|p(z)|1(z ≤ c)] < E z∼N1 [p(z)1(z ≥ c)] .First, the above condition implies thatE z∼N1 [|p(z)|1(z ≤ c)] < E z∼N1 [|p(z)|1(z ≥ c)] , thus E z∼N1 [|p(z)|] < 2 E z∼N1 [|p(z)|1(z ≥ c)].Using the Cauchy-Schwarz inequality, we getEQUATION)We then give the following claim.Claim C.4. Let p : R → R be any polynomial of degree at most n. Then, it holds thatE z∼N1 [|p(z)| 2 ] 1/2 ≤ 3 n E z∼N1 [|p(z)|] .Proof for Claim C.4. The proof is based on the following well-known fact: for any function g : R → R, it holds that (from Holder's inequality)EQUATIONWe then use Fact C.5 (Gaussian Hypercontractivity) to bound the term E z∼N1 [|g(z)| 4 ] 1/6 .Fact C.5 (Gaussian Hypercontractivity). Let p : R → R be any polynomial of degree at most l. Then, for q ≥ 2, it holdsE x∼N1 [|p(x)| q ] ≤ (q -1) ql/2 E x∼N1 [p 2 (x)] q/2. Now we apply Fact C.5 and choose l = n and q = 4. This impliesE z∼N1 [|p(z)| 4 ] ≤ 3 2n E z∼N1 [|p(z)| 2 ] 2 , which is E z∼N1 [|p(z)| 4 ] 1/6 ≤ 3 n/3 E z∼N1 [|p(z)| 2 ] 1/3. Plugging it into Equation (4), we get that for any polynomial p of at most degree-n,E z∼N1 [|p(z)| 2 ] 1/2 ≤ 3 n/3 E z∼N1 [|p(z)|] 1/3 E z∼N1 [|p(z)| 2 ] 1/3 . This implies E z∼N1 [|p(z)| 2 ] 1/2 ≤ 3 n E z∼N1 [|p(z)|] .Applying Claim C.4 to Equation (3), we getE z∼N1 [|p(z)|] < 2 • 3 n E z∼N1 [|p(z)|] Pr z∼N1 [z ≥ c] 1/2 .From our choice of the parameter c, we have that Pr z∼N1 [z ≥ c] ≤ 3 -2n /4, thusE z∼N1 [|p(z)|] < E z∼N1 [|p(z)|] ,contradiction. Therefore, such a polynomial p cannot exist. Thus, a function g satisfying the requirements in the body of the lemma exists.We let D be the unique distribution such that z ∼ N 1 E (z,y)∼D [y|z = z ′ ] = g(z ′ ) where g is the function from Lemma 3.3. We claim that D satisfies the conditions in this lemma's statement. Condition (i) is immediate from the definition of D. Then Condition (ii) is immediately implied from Condition (a) in Lemma 3.3.For Condition (iii), Condition (b) in Lemma 3.3 implies E z∼N1 [g(z)] = 0 which immediately implies E (z,y)∼D [y] = 0. To show thatE (z,y)∼D [z k ] = E (z,y)∼D [z k | y = 1] = E (z,y)∼D [z k | y = -1] for all k ∈ [n], notice that for all k ∈ [n], E (z,y)∼D [z k ] = Pr (z,y)∼D [y = 1] E (z,y)∼D [z k | y = 1] + Pr (z,y)∼D [y = -1] E (z,y)∼D [z k | y = -1] . (5)Moreover, from Condition (ii) of Lemma 3.3, we haveE (z,y)∼D [g(z)z k ] = E (z,y)∼D [yz k ] = Pr (z,y)∼D [y = 1] E (z,y)∼D [z k | y = 1] -Pr (z,y)∼D [y = -1] E (z,y)∼D [z k | y = -1] =0 .(6) Taking the difference between Equation (5) and Equation ( 6) givesE (z,y)∼D [z k ] = 2 Pr (z,y)∼D [y = -1] E (z,y)∼D [z k | y = -1] .Plugging in that Pr (z,y)∼D [y = -1] = 1/2, which follows from E (z,y)∼D [y] = 0 and y is supported on {±1}, we getE (z,y)∼D [z k ] = E (z,y)∼D [z k | y = -1] .Then, we haveE (z,y)∼D [z k ] = E (z,y)∼D [z k | y = 1] Pr (z,y)∼D [y = 1] + E (z,y)∼D [z k | y = -1] Pr (z,y)∼D [y = -1] ; therefore, E (z,y)∼D [z k ] = E (z,y)∼D [z k | y = -1] .Thus, Condition (iii) holds. Now, we show the fourth condition. We show the following claim.Claim C.6. It holds that χ 2 (D + , N 1 ) = O(1) .Proof.χ 2 (D + , N 1 ) = R P D+ (z) 2 P N1 (z) dz -1 = R P D+ (z) P D+ (z) P N1 (z) dz -1 ≤ R P D+ (z)/ Pr (z,y)∼D f [y = 1]dz -1 = Pr (z,y)∼D [y = 1] -1 R P D+ (z)dz -1 = Pr (z,y)∼D [y = 1] -1 -1 = O(1) ,where the inequality follows from the fact that P N1 (z) = P D+ (z) Pr ∼ D v , E (x,y)∼Dv [y|x = x ′ ] = 1 for all x ′ ∈ R d such that ⟨v, x ′ ⟩ ≥ Φ -1 (1 -α);(iii) Let D null be the joint distribution of (x, y) such that x ∼ N d and y = 1 with probability 1/2 independent of x. Then for any Du , D v ∈ D, χ D null (D u , D v ) = O(1) if u = v and χ D null (D u , D v ) = d -Ω(log 1/α) if u ̸ = v.Here, we give two lemmas from [DKPZ21] to construct a large set of distributions on R d × {±1} with small correlations. For a matrix A ∈ R m×n , we use ∥A∥ 2 to denote the spectral norm. Lemma C.8 (Correlation Lemma: Lemma 2.3 from [DKPZ21] ). Let g : R m → R and U, V ∈ R m×d with m ≤ d be linear maps such that UU T = VV T = I where I is the m × m identity matrix. Then, we have thatE x∼N d [g(Ux)g(Vx)] ≤ ∞ t=0 ∥UV T ∥ t 2 E x∼Nm [(g [t] (x)) 2 ]where g [t] denote the degree-t Hermite part of g.Note that we will use Lemma C.8 with m = 1 and n = 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 R d . Fact C.9 (Near-orthogonal Vectors: Fact 2.6 from [DKPZ21] ). For any 0 < c < 1/2, there exists a setV ⊆ S d-1 such that |V | = 2 d Ω(c) and for any u, v ∈ V ⟨u, v⟩ ≤ d c-1/2 .Proof of Lemma C.7. We define D in the following manner. We let D ′ be the distribution on R×{±1} in Lemma 3.4 for n = c log(1/α) where c is a sufficiently small universal constant such that 3 -2n /4 ≥ α. 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 = {D v : v ∈ V } where D v is the unique distribution on R d × {±1} generated in the following way. We first sample (z, y) ∼ D ′ and x ⊥ ∼ N d-1 . Then let B ⊥ ∈ R d×(d-1) be a matrix whose columns form an (arbitrary) orthonormal basis for the orthogonal complement of v. Let x = B ⊥ x ⊥ + zv and we define the distribution D v = D (x,y) . This effectively embeds the distribution D ′ along the hidden direction v in D v .To establish Condition (i) in this lemma, the definition of x combined with the fact that D z = N 1 (from Condition (i) in Lemma 3.4) implies the marginal distribution D x = N d .Then, for Condition (ii) in this lemma, we have that for anyx ′ ∈ R d such that ⟨v, x ′ ⟩ ≥ Φ -1 (1 -α), E (x,y)∼Dv [y|x = x ′ ] = E (z,y)∼D ′ [y = 1|z = ⟨v, x ′ ⟩] , from the definition of D v . Since 3 -2n /4 ≥ α, we have ⟨v, x ′ ⟩ ≥ Φ -1 (1 -α) ≥ Φ -1 (1 -3 -2n /4).Therefore, using the second condition in Lemma 3.4, we get E (x,y)∼Dv[y|x = x ′ ] = E (z,y)∼D ′ [y|z = ⟨v, x ′ ⟩] = 1 .For Condition (iii) in this lemma, notice that Condition (iii) in Lemma 3.4 implies Pr (x,y)∼Dv[y = 1] = Pr (x,y)∼Dv [y = -1] = 1/2 . Then, χ D null (D v , D v ) = Pr (x,y)∼Dv [y = 1]χ 2 (D + v , N d ) + Pr (x,y)∼Dv [y = -1]χ 2 (D - v , N d ) = 1 2 χ 2 (D + v , N d ) + 1 2 χ 2 (D - v , N d ) .D ∈ D. Let A be an algorithm that reliably learns α-biased LTFs with ϵ < α/3 accuracy and succeeds with 2/3 probability. We can simply give the i.i.d. samples from the distribution D to algorithm A. Given that A succeeds and outputs a hypothesis function h.If D = D null , then since A promises R + (h, D null ) ≤ ϵ. Since D null has y ∼ Bern(1/2) independent of x, this implies Pr (x,y)∼D [h(x) = 1] ≤ ϵ.Then we argue that if it is the other case i.e. D ∈ D, then given the algorithm succeeds, we must have Pr (x,y)∼D [h(x) = 1] ≥ α -ϵ instead. We suppose Pr Therefore, the output hypothesis h of A has to satisfyR -(h; D) ≤ 1/2 -α + ϵ . However, since Pr (x,y)∼D [h(x) = 1] < α -ϵ, we have R -(h; D) = Pr (x,y)∼D [h(x) ̸ = 1 ∧ y = 1] ≥ Pr (x,y)∼D [y = 1] -Pr (x,y)∼D [h(x) = 1] > 1/2 -α + ϵwhich contradicts the above. Thus it has to be Pr(x,y)∼D [h(x) = 1] > α -ϵ. If D = D null , then Pr (x,y)∼D [h(x) = 1] ≤ ϵ. Otherwise, we have Pr (x,y)∼D [h(x) = 1] ≥ α -ϵ.Since the gap between them is at least a constant α -2ϵ ≥ α/3 and Pr (x,y)∼D [h(x) = 1] can be estimated to inverse exponential accuracy on samples with high probability. • The authors should answer "Yes" if the results are accompanied by error bars, confidence 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.)• The assumptions made should be given (e.g., Normally distributed errors).• It should be clear whether the error bar is the standard deviation or the standard error of the mean. • It is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have a 96% CI, if the hypothesis of Normality of errors is not verified. • For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out of range (e.g. negative error rates). • 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. 
experiments compute resources: 
 Question: For each experiment, does the paper provide sufficient information on the computer resources (type of compute workers, memory, time of execution) needed to reproduce 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 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 as well as 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 it into the paper). 
code of ethics: 
 Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics https://neurips.cc/public/EthicsGuidelines?Justification: Our research conforms in every respect with the NeurIPS Code of Ethics.Guidelines:• The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.• If the authors answer No, they should explain the special circumstances that require a deviation from the Code of Ethics. • The authors should make sure to preserve anonymity (e.g., if there is a special consideration due to laws or regulations in their jurisdiction). 
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 is no societal impact of the work performed.• If the authors answer NA or No, they should explain why their work has no societal impact or why the paper does not address societal impact. • Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.• The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is a direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster. • The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology. • If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML). 
safeguards: 
 Question: Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?Answer: [NA]Justification: The work is theoretical.Guidelines:• The answer NA means that the paper poses no such risks.• Released models that have a high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters. • Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images. • We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make a best faith effort.12. Licenses for existing assets Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?Answer: [NA] Justification: This work does not use any assets.Guidelines:• The answer NA means that the paper does not use existing assets.• The authors should cite the original paper that produced the code package or dataset.• The authors should state which version of the asset is used and, if possible, include a URL. • The name of the license (e.g., CC-BY 4.0) should be included for each asset.• For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided. • If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswithcode.com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of a dataset. • For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided. 
 
 Appendix:  


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

Reviews: review: paper_summary: paper_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:
- the probability that f makes a false-positive error is at most $\epsilon$
- 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.

The 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))}}
, 2^{poly(1/\epsilon)})$. 

The algorithm first finds a candidate direction by estimating the Chow tensor. Consequently, the algorithm improves this hypothesis by performing a certain random walk. 

It 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.
strength_weakness: strength_weakness: - Not clear that the dependence on $\epsilon$ is best it can be.
- None of the algorithms run in fully polynomial time in all parameters.
questions: questions: - I think there is a missing parenthesis in the end of Theorem 1.3
- 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)$? 
- Is it correct that for these halfspaces your algorithm runs in time $d^{O(1} 2^{\log(1/\epsilon)^{O(1)}}$?
limitations: limitations: Limitations are discussed adequately.
paper_summary: paper_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))}$.
strength_weakness: strength_weakness: 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. 


Typos/suggested edits:

Line 14. “The problem of learning halfspaces is one the classical”

Line 40. “has since been extensively studies”

Line 53. “minimizing a lost function”

Line 69. “as a reliable agnostic learning for Gaussian halfspaces”

Line 84. missing close parens

line 94. “reduce the fully reliable learning”

line 105. “This implies that that”

line 214. “Let D be joint distribution”

Algorithm 1 caption “General Halspaces”

Line 511/525 “Reliable learning halfspaces”
questions: 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?

How does the equality in line 241 follow from Lemma 2.5?
limitations: limitations: Yes, the authors address the limitations of the work.
paper_summary: paper_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.
strength_weakness: strength_weakness: - 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.
questions: questions: N/A
limitations: limitations: N/A
paper_summary: paper_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.
strength_weakness: strength_weakness: 1. There are some room for improvement in writing.

   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.

   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.

   c) Some parts of the writing could be more clear, like "with high probability" in the definition.

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

3. 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?
questions: 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?

2. 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: limitations: I think the authors could give some future directions and potential improvements.

Comments: comment: Thanks for the response. I will keep my score and support its acceptance.
Thank you to the authors for answering my questions, this makes sense!
Thanks for your response! Actually the "corrupt negative labels are free" sentence is taken verbatim from your paper and you may want to change it.
Thank you for your response. I think it is appropriate to update my rating from 6 to 7