REVIEW 3 major objections 4 minor 15 references
Reliable Learning of Halfspaces under Gaussian Marginals
T0 review · 3 major / 4 minor · reviewed 2026-08-12 · deepseek-v4-flash
Pith's one-line read This paper proves that reliably learning halfspaces under Gaussian marginals is strictly easier than agnostically learning them: a new algorithm achieves quasi-polynomial complexity and a matching statistical-query lower bound pinpoints…
desk verdict The known-alpha algorithm is fresh and likely right, but the unknown-alpha reduction in the appendix has a real bug and the SQ tail constant is off; both are fixable, so the paper deserves a careful referee. read the letter →
The pith
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
The reading
What carries the argument
The algorithmic engine is a random walk over low-dimensional subspaces driven by low-degree moment information. The algorithm conditions on the strip $\{x:\langle w,x\rangle - t \ge 0\}$, projects onto the orthogonal complement of the current guess $w$, and estimates the Chow-parameter tensors $T_m = \mathbb{E}_{(x,y)\sim D}[\mathbf{1}\{y=-1\} H_m(x)]$ built from Hermite tensors $H_m$, the Gaussian analogues of monomials. A sign-matching polynomial of degree $O(\log(1/\alpha))$ guarantees that one of these tensors correlates with the optimal weight $w^*$, so a random unit vector from the top singular subspace of the estimated tensors gives an update direction correlated with the residual of $w^*$. Lemma 2.5, the preservation of the reliability condition after conditioning and projecting, lets the walk repeat, and each successful update increases correlation with $w^*$ by a controlled increment until the current hypothesis has false-positive error at most $\epsilon$.
What would settle it
Construct a Gaussian-marginal distribution satisfying the reliability condition for an optimal halfspace $f(x)=\mathrm{sign}(\langle w^*,x\rangle-t^*)$ for which Lemma 2.5 fails: after conditioning on a strip $\{x:\langle w,x\rangle-t\ge 0\}$ with $t-t^*\in[0,\epsilon/100]$ and projecting onto the orthogonal complement of $w$, every halfspace with threshold at most $|t^*|$ has positive false-positive mass. Such a distribution would break the random-walk recursion and constitute a counterexample to the algorithm's central geometric lemma.
Extended reading notes
Core claim
The paper's central claim is that under the standard Gaussian marginal, reliably learning halfspaces is strictly easier than agnostically learning them. Concretely, when the optimal halfspace has bias $\alpha$, the learner uses $N = d^{O(\log(\min\{1/\alpha,1/\epsilon\}))}\min(2^{\log(1/\epsilon)^{O(\log(1/\alpha))}},2^{\mathrm{poly}(1/\epsilon)})$ samples and runs in $\mathrm{poly}(N,d)$ time, returning a hypothesis with false-positive error at most $\epsilon$ and false-negative error at most $\mathrm{OPT}+\epsilon$. For constant $\alpha$ this is polynomial in $d$ and quasi-polynomial in $1/\epsilon$, whereas agnostic learning of Gaussian halfspaces requires $d^{\mathrm{poly}(1/\epsilon)}$-type complexity and is known to be hard; the companion SQ lower bound $d^{\Omega(\log(1/\alpha))}$ for $\epsilon<\alpha/2$ suggests the bias-dependent exponent is inherent. Conceptually, the paper argues that the one-sided error requirement removes the hardest part of agnostic learning.
Load-bearing premise
The algorithm's repeated random walk only works if, after slicing the Gaussian along the current hypothesis's positive strip and projecting onto the orthogonal directions, the induced distribution still satisfies the one-sided reliability condition with a threshold no larger than the original; if that geometric preservation can fail, the recursion cannot be restarted and the whole approach collapses.
Editorial extensions
If this is right
- For constant bias $\alpha$, the algorithm learns Gaussian halfspaces with sample complexity polynomial in $d$ and quasi-polynomial in $1/\epsilon$, improving on the previous $d^{O(1/\epsilon^2)}$ bound obtained by reduction to agnostic learning.
- The $d^{\Omega(\log(1/\alpha))}$ SQ lower bound for small excess error indicates that no statistical-query algorithm can remove the bias-dependent exponent.
- Reliable agnostic learning of Gaussian halfspaces is computationally separated from standard agnostic learning, whose complexity scales as $d^{\mathrm{poly}(1/\epsilon)}$.
- By the reduction noted in the paper, the same guarantee transfers to the fully reliable model, covering both signs of the threshold $t=\pm\Phi^{-1}(\alpha)$.
Reading between the lines
- The conditioning-and-projecting walk is not obviously tied to halfspaces: any concept class admitting a low-degree sign-matching polynomial under Gaussians might admit a similar one-sided learner, although the paper only proves the halfspace case.
- The lower-bound construction suggests that the difficulty of reliable learning is governed by the number of low moments an adversary can corrupt; testing algorithms that ignore moments of degree above $\log(1/\alpha)$ on the constructed family would make this intuition concrete.
- If the separation is robust, cost-sensitive losses with highly asymmetric misclassification costs may be computationally easier than symmetric 0-1 loss in distribution-specific settings, echoing the Neyman-Pearson perspective the paper cites.
Signed reviews
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The paper studies reliable agnostic PAC learning of halfspaces under standard Gaussian marginals, in which the learner must make almost no false positives and must match the best false-negative rate achievable by a halfspace with zero false positives. The main result (Theorem 1.3) is an algorithm with sample and computational complexity d^{O(log(min{1/α,1/ε}))} min(2^{log(1/ε)^{O(log(1/α))}}, 2^{poly(1/ε)}), where α is the bias of the optimal halfspace, together with an SQ lower bound of d^{Ω(log(1/α))} when ε < α/2. The algorithmic approach uses low-degree Hermite moment tensors of the negative-label conditional distribution to identify a low-dimensional subspace containing a good direction, and then performs a random walk with repeated conditioning on strips. The SQ lower bound uses an infinite-dimensional LP to construct a label function matching n moments and embeds it along a hidden direction. The paper also gives a reduction from fully reliable to one-sided reliable learning.
Significance. If the results are correct, they give the first strong evidence of a computational separation between reliable and agnostic learning for Gaussian halfspaces: for constant α the algorithm runs in time polynomial in d and quasi-polynomial in 1/ε, whereas agnostic learning requires d^{poly(1/ε)} under standard hardness assumptions, and the SQ lower bound suggests the d^{Ω(log(1/α))} dependence cannot be removed. The techniques, which exploit the clean negative-label side to obtain moment correlations and then perform a low-dimensional random walk, are interesting and differ from the earlier L1-regression reductions. The paper is transparent about its use of ideas from [DKK+22] and [DKPZ21] and supplies proofs for the borrowed pieces. However, the main theorem is not established as written because the unknown-α reduction can terminate with the constant -1 hypothesis, and the direction-finding subroutine's proof has a probabilistic gap. These issues are local and likely fixable, but they are load-bearing for the central claim.
major comments (3)
- [Appendix B.2, Theorem B.2 proof; Appendix B.8, Algorithm 3] The unknown-α reduction is invalid as written. In Step 2 of the proof of Theorem B.2, the outer loop accepts any hypothesis h returned by the Theorem B.4 subroutine for which R_+(h;D) ≤ ε. Algorithm 3 returns the constant -1 hypothesis whenever its candidate set S is empty (Step 4). For a guessed α > α_f, the precondition of Theorem B.4 ("there is a halfspace in H^α_d that is reliable with respect to D") can fail, so the subroutine may return -1. Since R_+(-1;D) = 0, the outer loop accepts it. If the optimal f is reliable and has positive mass α_f, then OPT ≤ Pr[y=1] - α_f, whereas R_-(-1;D) = Pr[y=1]; the false-negative error exceeds OPT + ε by roughly α_f, not by ε. The proof's statement that Step 2 is guaranteed to terminate for every α ≤ α_f only establishes late termination; it does not prevent early termination at α > α_f with the trivial hypothesis. The final paragraph identifies the loop variable α with the bias of the output hypothesis, which is false when the output is -1. A minimal fix is to make the subroutine signal failure instead of returning -1 and to have the outer loop continue on failure until α ≤ α_f.
- [Proposition 2.1 and Algorithm 2, Appendix B.6] The proof of Proposition 2.1 does not support the claimed Ω(1) success probability. Algorithm 2 chooses, for each m = 1,...,c1 t*^2 independently with probability 1/2, whether T'_m is the negative-label Chow tensor or the full-label Chow tensor. The proof of Case (a) assumes that the chosen tensors are the negative-label ones for the relevant m and states that this "happens with 1/2 probability"; however, the conjunction over the relevant m occurs with probability 2^{-k}, where k = Θ(t*^2) = Θ(log(1/ε)), which is not Ω(1) for small ε. Since Lemma 2.4 requires all T'_m to approximate the negative-label tensors, the mixed random choices are not covered by the proof. The algorithm should make a single global random choice between the two estimation methods, or the proof must handle the mixed case.
- [Appendix B.4, Claim B.5] The proof of Claim B.5 contains an incorrect inequality. The text asserts that |q(b)/r(b)| ≥ b^{3k}/max(b^{2k},(2k-1)!!) ≥ Ω(k)^{k/2}; the second inequality is false when k = Θ(b^2). For example, with b=4 and k=225 (which satisfies 2|b| ≤ sqrt(k) ≤ 4|b|), b^{3k}/(2k-1)!! is exponentially small, whereas Ω(k)^{k/2} is exponentially large. The desired conclusion that p(0) ≥ 2^{-O(k)} may still be true, but it is not established by the derivation. Since Claim B.5 is used to prove Lemma 2.2 and hence Proposition 2.1, the proof needs a corrected argument or an explicit citation to the corresponding construction in [DKK+22].
minor comments (4)
- [Appendix B.4, Claim B.5 proof] In the proof of Claim B.5, the line "≤ q(b) - q(b)/r(b) r(b) < p(b) = 0" should read "... = p̃(b) = 0"; as written it is confusing, and the strict inequality requires noting that q(z) is strictly increasing on [-b,b).
- [Appendix B.8, proof of Theorem B.4] The sentence "we can assume ... 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" is not precise: the event that the sign is favorable at every one of the poly(1/ζ) updates has probability 2^{-poly(1/ζ)}, not constant. The outer repetition in Step 3 compensates, but the proof should state this explicitly.
- [Section 2.2, Algorithm 1] Algorithm 1 uses the parameter ζ = log(1/ε)^{-c t*^2} even though t* is not known to the algorithm; the detailed Algorithm 3 avoids this by treating t* only in the analysis, but the main-text pseudocode should be clarified.
- [Appendix B.4, proof of Lemma 2.2] The proof of Lemma 2.2 uses the identity E[y p(⟨w*,x⟩)] = -2 E[1(y=-1)p(⟨w*,x⟩)] for zero-mean p, but it should explicitly state that the polynomial from Claim B.5 is normalized to zero mean and unit variance and that the normalization does not affect the correlation computation.
Circularity Check
No significant circularity: the algorithmic and SQ results are derived from stated distributional assumptions with self-contained proofs; self-citations are to independent prior theorems, not to the target result.
full rationale
The paper's positive result builds from Definitions 1.1 and 1.4 and derives the required correlation from a sign-matching polynomial (Lemma 2.2 with Claim B.5 proved), a spectral subspace lemma (Lemma 2.4 proved in Section B.5), a conditioning/geometric preservation lemma (Lemma 2.5 proved in Section B.7), and a random-walk contraction argument (Fact 2.6 is a simple vector-geometric fact). The SQ lower bound constructs a moment-matching function g via an infinite LP and hypercontractivity, then embeds it with the hidden-direction framework; no parameter is fitted to force a prediction, and no theorem's conclusion is used as its own premise. The paper does import Fact B.8 (Lemma 5.10 of [DKK+22]) and the correlation lemma Fact C.8 from [DKPZ21], which share authors with the present paper, but these are prior published statements whose assumptions do not include the target reliable-learning result and are not defined in terms of it; under the review rules they are independent evidence, not circularity. A separate correctness concern exists in the unknown-alpha reduction (Theorem B.2), where early termination on the constant -1 hypothesis may invalidate the termination argument, but that is a proof gap about loop behavior rather than a circular reduction, so it does not affect the circularity score.
Assumptions & free parameters
assumptions (3)
- domain assumption The marginal distribution of x is standard Gaussian N(0,I) in R^d.
- standard math Gaussian hypercontractivity (Bonami-Beckner) holds for all degrees used.
- standard math Infinite-dimensional LP duality, as in Fan 1968, is applicable to the feasibility LP in Lemma 3.3.
Cite this review
Pith. "Pith review of Reliable Learning of Halfspaces under Gaussian Marginals." pith.science (2026). https://pith.science/paper/R3J2IJER
@misc{pith2026241111238,
author = {Pith},
title = {Pith review of: Reliable Learning of Halfspaces under Gaussian Marginals},
year = {2026},
howpublished = {\url{https://pith.science/paper/R3J2IJER}},
note = {Machine review of arXiv:2411.11238}
}
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.
Reference graph
Works this paper leans on
-
[1]
If so, return the +1 constant hypothesis
First check if Pr(x,y)∼D)[y = −1] ≤ ǫ with sufficiently small constant failure probability. If so, return the +1 constant hypothesis
-
[2]
By Step 1, the sampling efficiency here is Ω( ǫ) with high probability
Otherwise, draw m = (d/ǫ)c many samples S = {(x1, y1), · · · , (xm, ym)} conditioned on y = −1. By Step 1, the sampling efficiency here is Ω( ǫ) with high probability
-
[3]
18 Let f (x) = sign( ⟨w∗, x⟩ −t∗) be the optimal hypothesis
Solve the following semidefinite program for w′ and t′: minimize t′ such that ⟨w′, x⟩ − t′ ≤0 , ∀(x, y) ∈ S ‖w′‖2 ≤1 Return the hypothesis h(x) = sign( ⟨w, x⟩ − t), where w = w′/‖w′‖2 and t = t′/‖w′‖2. 18 Let f (x) = sign( ⟨w∗, x⟩ −t∗) be the optimal hypothesis. We prove that h(x) = sign( ⟨w, x⟩ −t) is such that R+(h; D) ≤ ǫ and R−(h; D) ≤ R−(f ; D) + ǫ. S...
-
[4]
Run the algorithm in Lemma B.3 with ǫ′ = ǫ/2. If the output hypothesis h satisfies R+(h; D) ≤ ǫ with a sufficiently small constant failure probability, then output h and terminate
-
[5]
Set α = 1/2−ǫ/100 and run the algorithm in Theorem B.4 with ǫ′ = ǫ/2. If the output hypothesis h satisfies R+(h; D) ≤ ǫ with a sufficiently small constant failure probability, then output h and terminate. Otherwise, update α as α − ǫ/100. Repeat Step 2 until the algorithm terminates. Let f = argmin f ∈Hd ∧ R+(f ;D)=0 R−(f ; D) be the optimal halfspace and αf...
-
[6]
The sign of p(z) matches sign(z − b), i.e. sign(p(z)) = sign( z − b)
-
[7]
For any z ≤ b/2, we have |p(z)| = 2 −O(k). Proof. We consider the polynomial p defined as: ˜p(z) = q(z) − q(b) r(b) r(z) , where q(z) = z3k, r(z) = z2k − (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)/ √ Eu∼N1[˜p2(u)]. For convenience, we first note that from Stirling’s approxim ation for m...
-
[8]
Let S be a set of N = dc2max(t∗ 2,1) log(1/δ)/ǫ2 many samples from D
Let c1 be a sufficiently large universal constant and c2 be a sufficiently large univer- sal constant depending on c1. Let S be a set of N = dc2max(t∗ 2,1) log(1/δ)/ǫ2 many samples from D. For m = 1, · · · , c1t∗2, with 1/2 probability, take T′m = E (x,y)∼uS [1(y = −1)Hm(x)] , to be the empirical Chow-tensor on negative samples. Otherw ise, take T′m = E (x,y)...
Show all 15 references
-
[9]
Let V be the union of all Vm and output v to be a random unit vector chosen from V
Take ˜T′m ∈ Rd×dm−1 to be the flattened version of T′m, and let Vm 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 Vm and output v to be a random unit ...
-
[10]
dim(V ) ≤ 4k/τ 2, and
-
[11]
Then the same argument will give ⟨v, w∗⟩ = ǫO(1)
‖projV (v∗)‖2 ≥ τ / ( 4 √ k ) . Then the same argument will give ⟨v, w∗⟩ = ǫO(1). The above described algorithm uses at most N = dO(t∗ 2)/ǫ2 samples and poly (N, 1/ǫ) runtime. This completes the proof of Proposition 2.1 . B.7 Proof of Lemma 2.5 Item 1 follows from the definitio...
-
[12]
If so, return the +1 constant hypothesis
Check if Pr(x,y)∼D[y = −1] ≤ ǫ/2 (with sufficiently small constant failure probabil- ity). If so, return the +1 constant hypothesis. If the parameters satisfy min ( 2log(1/ǫ)O(log(1/α )) , 2poly(1/ǫ) ) = 2 log(1/ǫ)O(log(1/α )) , then set the correlation parameter ζ = log(1 /ǫ)−c...
-
[13]
Let the update step size λ = ζ and repeat the following process until λ ≤ ǫ/100
Initialize w to be a random unit vector in Rd. Let the update step size λ = ζ and repeat the following process until λ ≤ ǫ/100. (a) Use samples from D to check if the hypothesis h(x) = sign( ⟨w, x⟩ −t) satisfies R+(h; D) ≤ ǫ/2. If so, go to Step ( 3). (b) With 1/2 probability, ...
-
[14]
If so, add it to the set S
Check if h(x) = sign( ⟨w, x⟩ − t) satisfies R+(h; D) ≤ ǫ/2. If so, add it to the set S. For each choice of value t in Step ( 1), repeat Step ( 2) 21/ζc many times where c is a sufficiently large constant
-
[15]
Return the hypothesis h(x) = sign( ⟨w, x⟩ − t), where (w, t) = argmin (w,t)∈S t
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 Margin als (detailed version of Algorithm 1 ). Proof...
Reviewed August 12, 2026 · model on record in the stance chip above.
Discussion (0). Continue with ORCID to comment.