Smoothed Agnostic Learning of Halfspaces over the Hypercube
Authors: Yiwen Kou
Raghu Meka
Venue: NeurIPS 2025 poster ()
Keywords: Agnostic learning
Smoothed analysis
Boolean halfspaces
Polynomial approximation
Learning theory
Primary area: theory

Abstract: Agnostic learning of Boolean halfspaces is a fundamental problem in computational learning theory, but it is known to be computationally hard even for weak learning. Recent work \citep{chandrasekaran2024smoothed} proposed smoothed analysis as a way to bypass such hardness, but existing frameworks rely on additive Gaussian perturbations, making them unsuitable for discrete domains. We introduce a new smoothed agnostic learning framework for Boolean inputs, where perturbations are modeled via random bit flips. This defines a natural discrete analogue of smoothed optimality generalizing the Gaussian case. Under strictly subexponential assumptions on the input distribution, we give an efficient algorithm for learning halfspaces in this model, with runtime and sample complexity $\tilde{O}(n^{\mathrm{poly}(\frac{1}{\sigma\epsilon})})$. Previously, such algorithms were known only with strong structural assumptions for the discrete hypercube—for example, independent coordinates or symmetric distributions. Our result provides the first computationally efficient guarantee for smoothed agnostic learning of halfspaces over the Boolean hypercube, bridging the gap between worst-case intractability and practical learnability in discrete settings.

Smoothed Agnostic Learning of Halfspaces over the Hypercube
Yiwen Kou Department of Computer Science, UCLA Los Angeles, CA, US evankou@cs..o cc..ka...
Raghu Meka
Department of Computer Science, UCLA Los Angeles, CA, US raghum @ cs.ucla.edu
Abstract
Agnostic learning of Boolean halfspaces is fundamental problem in computational learning theory, but is known to be computationally hard even for weak learning. Recent work (Chandrasekaran et al. 2024) proposed smoothed analysis bypass such hardness, but existing frameworks rely on additive Gaussian perturba- tions, making them unsuitable for discrete domains. We introduce a new smoothed agnostic learning framework for Boolean inputs, where perturbations are modeled via random bit flips. This defines a natural discrete analogue of smoothed opti- mality generalizing the Gaussian case. Under strictly subexponential assumptions on the imput distribution, we give an efficient algorithm for learning halfspaces this model, with runtime and sample complexity (npolyy( (t) Previously, such algorithms were known only with strong structural assumptions for the discrete hypercube-for example, independent coordinates or symmetric distributions. Our result provides the first computationally efficient guarantee for smoothed agnostic learning of halfspaces over the Boolean hypereube. bridging the gap between worst-case intractability and practical learnability in discrete settings.
way
Introduction
Halfspaces, or linear threshold functions (LTFs), are one of the most fundamental concept classes in machine learning. In the realizable setting (Valiant) 1984), they are efficiently learnable by classical algorithms such as the Perceptron (Rosenblatt) 1958] Novikoff 1963). Winnow (Littlestone) 1987). large-margin methods like Support Vector Machines (Cortes and Vapnik] 1995). or by linear programming. These methods exploit linear separability and can perform well even in the presence of irrelevant features.
In contrast, the agnostic learning framework (Haussler 1992 Kearns et al.) 1992). which allows for
arbitrary label noise, poses significant algorithmic challenges. this setting, the goal find hypothesis that competes with the best in a concept class, without assuming that the data is linearly separable. However, agnostic learning of halfspaces is computationally hard in the worst case: even weak dearning-achievinn еттог marginally better than random guessing is NP-hard under standard complexity assumptions, both in continuous domains (Feldman al., 2009) and on the Boolean hypercube (Guruswami and Raghavendra] 2009).
To overcome these barriers, several restricted models have been studied. For example, under random classification noise (RCN), halfspaces remain learnable using modified Perceptron algorithms or linear programming (Blum al.) 1996; Cohen 1997). Under Massart noise, where adversarial flips are bounded in probability, recent work has led to efficient learning algorithms (Awasthi et al.)
2015 Diakonikolas al., 2019 2020 2021). Other lines of work exploit structure in the input distribution:
Kalai et al. 2008 gave improper agnostic learning algorithms under uniform, spherical,
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

or Log-concave distributions by approximating halfspaces with low-degree polynomials, extending earlier Fourier-based methods (Linial al. 1993).
more recent and promising direction based on smoothed analysis, which was introduced to explain the practical performance of algorithms that worst-case hard (Spielman and Teng. (001). In learning theory, Chandrasckaran et al. (202)) proposed a smoothed agnostic framework in which the learner competes with the best classifier under slight random perturbations of the inputs. This relaxation enables efficient algorithms for learning low-dimensional concepts, even when worst-case learning is intractable. However, their approach is tailored to continuous domains and relies on additive Gaussian noise, and hence is not suitable for discrete domains such as the Boolean hypercube.
Our contribution. We develop a discrete analogue of smoothed agnostic learning for Boolean concept classes over {+1] where additive Gaussian noise is ill-defined. Instead of perturbing examples in Fuclidean space, introduce bit-flipping noise: each input coordinate is independently flipped with probability a. This gives rise to a new benchmark for learning that captures robustness small discrete perturbations, interpolating between classical agnostic learning (a 0) and random guessing (a = 1/2).
To formalize this, we begin by recalling the standard agnostic learning objective.
Definition 1.1 (Agnostic Optimality) Let X be a domain and F be a class of functions f {+1}. Let 'D be distribution over labeled examples (x. E X x {+1}. The agnostic error of F under D is defined
opt
inf ((xx)))l((( + y/. FEF
We define smoothed variant of this benchmark, in which each input is perturbed before evaluation. This definition is general and does not assume any particular structure of the domain or distribution.
Definition 1.2 (Smoothed Optimality) Let X' be a domain and F be a class functions f : {=1}. Let be a distribution over labeled examples (x. E X {=1} and Pa (x) be a perturbation distribution of x over X. Define the smoothed agnostic error as:
opt, = inf I (xx.))-DDxxP.. + y).
feF
In standard agnostic learning, the goal is to compete with opt under D. Following Chandrasekaran et al. (2024), instead compete with opt, in Definition T.2
Definition 1.3 (Smoothed Agnostic Learning) Fix c,a > O and 5 E (0, 1). algorithm learns the class F in the o-smoothed agnostic setting if, given ii.dd samples from DD it outputs hypothesis h X {+1} such that with probability at least 8:
P P(x.))<D(((x + v] S opt, +e.
As an example. Chandrasekaran et (024) study the case where X = R2" and the perturbation distribution is additive Gaussian noise: (x) Nx Nxx,o²I,). This formulation relies on the Euclidean structure of æ. and does not extend to discrete domains. In our setting. we consider
X' = (+1)* 1 and define perturbations via random bit flips: (x(x) x @ where ~ No is a product distribution with 2, -1 with probability and otherwise. This defines natural smoothed learning model for the Boolean hypercube that avoids embedding the domain into IR...
Under this framework, we show that halfspaces over the Boolean cube are efficiently learnable in the smoothed agnostic model under mild distributional assumptions. Our approach extends the classical poolynooiia regression framework this smoothed setting, The key idea is that every Boolean halfspace, when composed with small random bit-flip perturbations, admits a low-degree polynomial approximation under the input distribution. To establish this, we analyze a smoothed version of the halfspace defined via noise operator (Definition 3.2), and construct approximators using herry-Esseen-type arguments combined with critical index analysis handle irregular weight vectors. We obtain the following result:
Theorem 1.4 (Subgaussian-Informn see also Theorem 4.8p Let D be a distribution on {+1)"*
{+1} with sub-gaussian x-marginal of variance proxy of There exists algorithm that learns
2

---

the class of linear threshold functions in the o-smoothed setting with N = n mr) log(1/6) samples and poly(n, N) runtime.
This is the first result that establishes efficient smoothed agnostic learning of halfspaces over the Boolean hypercube. While our algorithm is improper, it achieves strong generalization guarantees under natural distributions. Previously, such results for the hypercube were only known under very restricted distributions as discussed below.
2 Related Work
Distributional Assumptions in Halfspace Learning: It is well-understood that agnostically
learning halfssaces is intractable in the worst case (Feldman et 20099 Guruswami and Raghavendral
2009), even under relatively benign noise models (Diakonikolas et al. 2022). This has motivated a
long line of distribution--pecifff algorithms that guarantee learnability by leveraging assumptions on the data distribution. Early work focused on uniform or product distributions, where powerful
Fourier-analytic techniques yield low-degree approximations (Linial et al., 1993; Klivans al.,
2004a| Blais et al.) 2010). Under the uniform hypercube distribution, halfspace concepts exhibit strong Fourier concentration and low noise sensitivity (O [O'Donnel] [202]), enabling efficient learning via low-degree polynomial approximation (Klivans et al. (2004a). This was extended to symmetric distributions in Wimmer (2010) and to arbitrary product distributions in Blais et al. (2010). However, beyond these there are very few general classes of distributions over they hypercube where halfspaces are agnostically learnable.
For continuous distributions, halfspaces were shown to be agnostically learnable under log-concave distributions by Kalai et al. (2008) and this was later extended to intersections and other functions of halfspaces in Kane et al. (2013). Much like the discrete setting, until the recent work of Chan drasekaran et al. (2024). most positive results required strong structural assumptions on the marginal distribution of the examples. This work introduced new smoothed agnostic model which led to several new results for learning halfspaces and functions of halfspaces for a much broader class of distributions (e.g., sub-gaussian or sub-exponential densities). Our work continues this progression to very general distributions, but focuses on the Boolean domain and shows that only mild tail bounds (strictly sub-exponential) suffice for efficient learning in the smoothed setting.
Noise Models and Smoothed Analysis: In parallel to distributional assumptions on X, comple- mentary line of work has tackled label noise models and smoothed analysis. The classical noise models include random classification noise (RCN), where each label independently flipped with some probability. BBlum et al. 1996) gave the first polynomial-ting time algorithm for learning a halfspacc under random classification noise, exploiting the fact that halfspace's margin makes relatively robust to independent label flips. A stronger noise model is the Massart noise model, which bounds the adversary by a flipping probability n < 1/2 on each example. Diakonikolas et al. (2020) gave an efficient algorithm for learning halfspaces with Massart noise over log- log-concave distributions. On the other hand, with adversarial (malicious) noise, learning halfspaces requires additional assumptions.
Klivans et al. (2009) designed efficient algorithms for origin-centered halfspaces under malicious noise by assuming isotropic log-concave distribution and small noise rate. In smoothed analysis of learning, one assumes that either the data (Blum and Dunagan 2002 Kane et al., (003)) or the target concept (Chandrasekaran et al. 2024) is randomly perturbed, so that pathological arrangements are avoided. Chandrasekaran et al. (2024) introduced smoothed agnostic PAC model in Ed where the
learner competes against the best classifier that is robust to slight Gaussian perturbations of examples. Our work can be seen as Boolean analogue of this idea: rather than perturbing continuous inputs, we require the optimal halfspace to be stable under small random label flips.
3 Preliminaries
We review relevant definitions from Boolean function analysis that will allow us to define a discrete smoothing operator and justify using it in place of the original linear threshold function. We use definitions from the analysis of Boolean functions over product spaces, following the framework of Mossel et al. (2005). Let (S), (1)) pi),................. )..... (Rn, (m)) be finite probability spaces and let (Ω. 11) denote their product. In our setting, we take Ω = [+1} and define μ to be the product distribution N..
where each coordinate is 1 with probability 1 and 1 with probability o, independently.
3

---

Definition 3.1 (p-noisy copy) Given x E St and p [0, p-noisy copy of x is random vector y N,)x),, where each coordinate yi independently set 2, with probability p and an independent draw from pi with probability 1
Definition 3.2 (Noise operator p) For any function f T is defined as
R and p E [0, 1}, the noise operator
(x) By
This definition generalizes the Bonami-Beckner operator (Kahn et al. 1988) when is the uniform distribution on the hypereube. Intuitively, Tpf a smoothed version of computed by averaging over neighborhood of x with geometric decay controlled by p. In particular, Tif f. and as decreases from fp. suppresses high-frequency components of This operator will be used as our main tool for constructing smoothed approximations to Boolean threshold functions.
Definition 3.3 (Noise stability and noise sensitivity) For any : + R, the noise stability at parameter is defined
Splf) (f.Tff)
If [+1}, the noise sensitivity parameter E [0, 1] is given by
1 S1-5((f) ---51-6(7) Px- o(x) * f(y)].
NS&(f)
Equivalently, (ff (f + f(y) where r and have Hamming correlation 18.. This quantity captures the robustness of f to small input perturbations.
It is well-known that natural Boolean functions with low total influence low-degree Fourier concentration exhibit low noise sensitivity. In particular, linear threshold functions are noise-stable under both uniform (Peres) (004) and general product distributions (Blais et al. (0100). The following lemma bounds the noise sensitivity of halfspaces over arbitrary product spaces.
Lemma 3.4 (Theorem 3.2 in Blais et al. (2010) Let f - {=1} is linear threshold function, where the domain = Q2 x x On has the product distribution = μ4 x X pln Then NS S oo.
This bound implies that for - 8 close to 1, the smoothed function T closely approximates the original threshold function f. This justifies our strategy of working with Tęf instead of f in the smoothed learning setting: any learner that performs well on Tpf will, up to a small error, also succeed on f.
Notation. We use small boldface characters for vectors and capital bold characters for matrices. We use [d] to denote the set {1, 2.... d}. For vector Rd and [d]. zy denotes the i-th coordinate of x, and ||||2 == v /
im x² the & norm of x. For x, E Idd, we use (x,y) = Din 3&8h as the inner product between them and x ① y (I191, Iayaa the Hadamard product between them. We use {{E} to be the indicator function of some event For (x, y) distributed according to D, we denote >x to be the marginal distribution of
4 Technical Overview
In this section, we outline the main steps of our analysis. Our approach follows a reduction based strategy: we reduce smoothed agnostic learning of Boolean halfspaces to the problem of approximat- ing a smoothed halfspace by a low-degree polynomial, which can then be learned via L1 regression (Section 4.1.. We begin by replacing the original target fz) f(x z) with a smoothed surrogate Ti- Ti-pfx ZZ) (Definition 3.2), facilitating approximation by low-degree polynomials (Section[4.)
To handle the biased distribution arising from noise perturbation, we introduce a rerandomization and conditioning trick that rewrites each bit as a mixture involving uniform random variables. This allows us to express the smoothed function as conditional expectation over uniformly random inputs, making amenable to quantitative central-limit theorems (Berry-Esseen estimates; Section 4.3) We
then use case analysis facilitated by decomposition of the weight vector (Section 4.4

---

1. If a small number of large coordinates (the "head") dominate, the halfspace's output is primarily determined by those coordinates, and we can approximate the function directly.
2. Otherwise, the remaining "tail" is regular, and we apply the Berry-Esseen theorem to approximate the Boolean sum by a Gaussian. This reduces the problem to the continuous setting, where we leverage Gaussian-basee techniques (the density ratio method from Chandrasckaran et al. (2024) to construct low-degree polynomial approximations.
Together, these ingredients yield an efficient smoothed learner for Boolean halfspaces under strictly sub-exponential input distributions.
4.1 High-Level Approach via Ligression
Our starting point is the L1 pollonoomia regression method for agnostic learning. particular, Kalai et al. (2008) established a powerful reduction from agnostic learnability to low-degree polynomial approximation.
Algorithm 1 L1 Polynomial Regression Algorithm
Input: Sample S = {(x', ((x",,'),.. y')...., (x y²), degree bound d
1: Find polynomial p of degree d to minimize
1
Σ p((0)) y²
N
(This can be done by expanding examples to include all monomials of degree I and then performing L1 linear regression.)
2: Output hypothesis h(x) = sign(p(a) - t), where t E [-1, 1] is chosen to minimize the classifi- cation error on S.
Theorem 4.1 (Theorem 5 in Kalai et al. (008)) Suppose mindeg(e) Sa Ep, [[((x) -(xx))-c(x)) c(x)]] S ffr some degree and any e. the concept class C. Then, for output by the degree-d L1 polynomial regression algorithm with N = poly(n'/)) /c) examples, Eg-d= (P (P(x)))D(/( * yll < opt c, where opt min P ((x.))=lf(xx) + y). we we repeat the algorithu = O(log(1/))/e) times with fresh examples each, and let be the hypothesis with lowest ervor on an independent test set of size ([log(L/8)/²)), then with probability at least 1 - 5, P ((x.,))D(h(() # yl S opt +
Theorem 4.1 says that if the target function f can be approximated in L1 by low-degree polynomial p with error most e, then one can efficiently learn f misclassification error opt + c, where opt is the Bayes-optimal error rate under distribution D. Once such a polynomial is shown to exist, Theorem 4. implies a computationally efficient learning algorithm with sample complexity N po (1g()
4.2 Smoothed Learning as Non-Worst-Case Approximation
The challenge is that an arbitrary halfspace f fx) sign( (w, x) 0) might not be well-approximated by any low-degree polynomial over worst-case input distributions. Following Chandrasekaran et al. 2024.. we view smoothed learning as a form of non-worst-case approximation. In this smoothed agnostic setting, the learner's ss "effective" target concept is the mapping (x, z) + f(x @ z). where z E {+1)" " is random noise vector independent of with close to 0 meaning only tiny fraction of bits are flipped on average. We extend the L1 -egeressiio reduction to handle this scenario. In particular, we prove an analogue Kalai al. 2008) 's result tailored to the smoothed model:
Theorem 4.2 Suppose minaeg(rs) EE..D.DDD........ lP2 f(x C zi]l S for some degree d and any halfspace f. where Dx any distribution on (+1]". Then, for h output by the degree-d L polynomial regression algorithm with N poly (n" /c) examples, Eg-DV [PP (Fxxa))D(((() + vll S opt, + e. If we repeat the algorithu = O(log(1 /8)/ee) times with fresh examples each, and let be the hypothesis with lowest error on an independent test set of size (log(1/8) / then with probability at least - 8. ((xx)))((((x) # v] opt, +e.
5

---

After this reduction, our task reduces to a purely approximation thheoretic problem: we need to construct, for each noise vector z, polynomial Px(x) in the variable x such that the expected L emor over the smoothing process remains small:
Ex~NN,x~DA [px (x) f(x o oz)] S.
To achieve this, we treat the smoothing noise and consider x as fixed parameter, This reduces the problem to approximating the function [z) f(x o 2). We replace fx(z) with its smooth approximation by applying the generalized Konaai--Becknn operator (Definition 3.2 on z.
71-psx(2) (x=
Applying Lemma 3.4 with = 0 we obtain:
E Ez~N, [[Ti-p/x(z) fx(x]] S..
Therefore, if we can find a low-degree polynomial that approximates Ti Ti-pfx(z) (z) well in L1, that polynomial will also succeed in approximating fx (z). The remainder of our technical approach will be devoted to constructing such polynomial approximator for the smoothed halfspace Ti-pfx(z).
4.3 From Biased to Uniform Distribution the Hypercube
To construct low-degree polynomial approximations, we analyze the noise-smoothed function Ti -i-psx Recall that for fixed input x, we define fx (z) f(x z). and suppose f(-) sign((w,) 0). Then we have:
Ti (z) = Ey-NN ((x) (signi C x. 0)] By-As (xx) (sign(( (u, -0]]
where we define w
Here, N₂ denotes a product distribution over {=1]" where each bit z; is with probability 1 - and -1 with probability The vector is (1 pnnoss copy of (Definition 3.1 with probability - p, 3/ = 2; otherwise, y/s redrawn independently from No with probability Therefore, y ~ No. correlated with z, follows biased distribution on the hypercube. To facilitate polynomial approximation, we aim to reduce this to a form where the randomness comes from uniform distribution. To achieve this, we introduce rerandomization trick that rewrites each
coordinate yi as:
Vi = =1 (1-11)) (1- + LT, (1 - -1))= + 4+(1 m.) + lameei
where
w.p.
w.p. 1
w.p. 20 m, 0 w.p. 1 - 20
4 =
0 w.pp 1-p . - w.p.
with E; being Radmacher random variable (uniform over {=1)).
This decomposition captures the full noise process: I, is an indicator that determines whether the coordinate is kept 2 (with probability 1 p) or resampled as т, (N₂); ) (with probability p). The variable m; is then used to rerandomize т₁. since т; can be viewed as taking the value 1 with probability 1 2a (when m. 0) uniform random bit e; with probability 2a (when m, =).
key benefit that, conditional on I and m, the random component e follows the uniform distribution on (+1) ) We now condition on (1, m) and express the smoothed function as:
Ti Fi-pf((2) = E,. Ey (sign( (u, y) - f)] m]] = Ei.m [sign( (u, O m Oc) + 6) ml
where b is deterministic shift depending the coordinates fixed by 1.m.
Given that is uniform distribution on hypercube, the inner sum behaves like sum of independent (+1} random variables. Under mild regularity condition (Definition 4.3) on the weight vector
u, we can apply the Berry-Esseen Theorem to approximate this inner distribution by Gaussian. Specifically, we approximate:
(u, o é) x AO0 | O 1@ m 1
(4.1)
Substituting into the earlier expression yields the Gaussian smoothed Gaussian-smoothed
approximation:
T (x)) E,,m (0..ll/o [sign(s (s + 0)]1 m)
This reduces our setting to the Gaussian noise model analyzed in [handrasekaran et al. (2024) for which efficient low-degree polynomial approximations known. In particular, the density ratio method developed in that work can be applied to approximate Ti Ti=pfx(z) with small L error.

---

4.4 Handling Irregularity via Critical Index Analysis
Recall that the approximation in (4.1) relies on the Berry-Esser Theorem, which introduces uniform approximation error of ((( uolomila
for the cumulative density function. This can be further bounded by O( |nooom/ | ). Note that each coordinate L,m; is equal to I with probability 2po and O otherwise. By concentration, we have ||u @ 1 @ m| R (2pa))//11|)g so the approximation error becomes ((po) 11/2 [ This motivates the following regularity condition:
nolombe
1/2
Definition 4.3 (regularity) For vector E RD, is a-regular if [|]] S a: |w||2-
Given this definition, we see that if is o-regular, then the approximation in (4.1 holds with Loe error 0((pr)-1/²a) Since w and {+1}", the regularity of is equivalent that of For such "good" (i.e., o-regular with small a) weight vectors w. we can construct low-degree polynomial approximators by reducing to the Gaussian setting analyzed in Section 4.3 and Chandrasckaran et al. (2024).
However, we must also handle the "bad" or irregular cases, where (u, 1@ ( @ deviates significantly from Gaussian behavior. To deal with such irregular w. we employ critical index analysis, a standard tool in the analysis of Boolean halfspaces (Servedio, 2006 Matulef et al., 2010 Diakonikolas et al. 2010 Meka and Zuckerman 2010 O' Donnell and Servedio 2011 Diakonikolas and Servedio 2013
Definition 4.4 (o-critical index) For u R", assume that |u, 2 ...
|u,.]. We define the a-
critical index E((:) of halfspace h(x) sign((u, x) 0) as the smallest index i E [m] for which |u,] S a- where := V /
Intuitively, the a-critical index is the first index i such that the tail weight vector (u, un) is a-regular. Our earlier argument covers the case i = 1, where the entire vector is regular. Using this framework, we obtain the following structural result:
Lemma 4.5 (Critical Index Decomposition) Without loss of generality, let u w ② x with entries
sorted in non-increasing magnitude, i.e., |ui|
> |un]- Suppose x follows (a, X)-strictly
sub-exponential distribution on {=1]". For any fixed z, there exists a threshold = K(a, c) O( [og((1 + a)/a² + log(1/c)) (og()//)//// paa") such that one of the following two conditions holds:
1. For some H < K, the tail vector (wH+I,''* ) is a-regular, where is to be choosen later.
2. For H K and at least 1 fraction of x, it holds that
Py-Mi [sign( (u, Yn) + (ur,yr) - 0) + sign((u,. .H) - 8) S where uy = (u.,... u.).
(4.2)
This lemma is proved by analyzing two cases, depending on whether the critical index É(a) satisfies 1 < ((a) < K, E(a:) K. In the former case, set H f(a) 1, and uy is o-regular. In the latter case, the head vector forms a sufficiently long geometrically decaying sequence [41] 2 ... 2 |um| ensure that the influence of the remaining tail vector uy on the halfspace output is negligible. That is, with high probability, sign( (u, - 0) as sign( ((u,( 0).
We now show how to construct low-degree polynomial approximators in both cases.
Case When ur is a-regular, we condition on yи. For each fixed yи, the function becomes regular halfspace in yr:
[x(Y)) sign((ur,y7) 0), where 0 = 0 (ux,Yn).
We apply the techniques Chandrasckaran et al. (2024) to approximate this with a low-degree polynomial. One subtlety is that directly applying their construction leads to a degree polynomial in 10//||rl|2. 2. To address this, an indicator trick to define:
Pyn (x) = (ign((uH,X0 - 0) (KuH yH) - -0 > C- C- ((uu.yH))
Pyn (x) 1l (KuH, 0 < C. | |urll2))
7

---

where Pyn (x) can be constructed using the idea from Chandrasekaran et al. (2024) since | controlled. The indicator functions are low-degree polynomials degree most H, since they only depend on H variables and any function f [+1] -> IR can be represented by degree at most multilinear polynomial.
Case 2: If the second condition of the lemma holds, we approximate Ti Ti-pfx(z) directly using sign((uæ, - 0). Since this depends only on the first H coordinates, can be exactly represented as polynomial of degree at most H.
In either case, obtain a low-degree polynomial approximator for the smoothed function Tı Tx-
4.5 Results
Using this framework, we establish the following approximation bound:
Definition 4.6 (Strictly Sub-exponential Distributions) A distribution D on Rd is (a, A)-strictly sub-exponential for all ||v||2 = 1, Px (x v\ > 1 e-te/(t//)"
Lemma 4.7 Fix > O and sufficiently large universal constant C. > O. Let 'D be a (a, X)- strictly sub-exponential distribution on {=1]". Let f: {+1}" - {+1} be linear thresh- old function. There exists family of polynomials Pa parameterized by z of degree at most ((Coo=ANoo((1) +)lo((1/c)/c) 6(1+)))) such that EN,N, Bx.DNlaxxllll(x] - fx(z)]] is at most c.
Given the polynomial approximation and the degree upper bound, one can directly run L1 polynomial regression (Algorithm(]) [ as stated in Theorem 4.2, We now can get our main theorem for strictly sub-exponential distributions.
Theorem 4,8 Let D be distribution on [+1]" (+13 such that the marginal distribution is (ax, X)-
strictly sub-exponential. There exists algorithm that draws N = -)Poly(A//ee) ( log(1/8) /8) samples, runs in time poly(n, N), and computes a hypothesis h(x) such that, with probubility at least 1 - 8, it holds that P (x + h(x)) S opl +
Our main theorem shows that any Boolean halfspacc on {=1}" can be learned agnostically in the smoothed model under strictly cub-exponential input distributions. This result holds in a general and challenging setting where prior techniques fail, and achieves efficient runtime and sample complexity. Table Taleeeoomee compares our guarantees with the most relevant prior works. Conceptually, our contributions extend the scope of agnostic halfspace learning in two fundamental directions:
Relaxing distributional assumptions via smoothed optimality: A key technical contribution is our use of a smoothed benchmark opt, (Definition 1.3 instead of the worst-case error opt (Definition [.] enabling learning under substantially weaker distributional assumptions. In particular, we show that halfspaces remain efficiently learnable under general strictly sub-exponential marginals, which is a significant relaxation compared to the strong structural assumptions required in earlier work. For example, the Fourier-batt based techniques of Klivans et al. (2004b): Kalai et al., (2008); Blais al.) (2010) exploit spectral concentration under uniform or product distributions to obtain low-degree polynomial approximations. To go beyond the product setting, Wimmer (2010) generalized previous techniques to symmetric group to handle germutation-invarian distributions. However, these methods break down when the input has more dependencies or heavier tails. In contrast, our approach succeeds under strictly sub-exponential marginals by combining bit-flip smoothing with critical index dccomposition and Berry-Esseen approximation, enabling polynomial approximation without requiring coordinate independence permutation invariant structure.
Extending the smoothed learning framework to the Boolean hypercube: second core contribu- tion is our extension of smoothed agnostic learning to the Boolean domain {+1}", where additive Gaussian perturbations used in prior smoothed models are not well-defined. In continuous domains, several tools, including Gaussian surface area bounds (Klivans et al. 2008). log-concave concentra- tion inequalities (Kane et al.) 2013), 3). and Gaussian smoothing combined with density ratio techniques (Chandrasekaran et al. 2024), enable efficient agnostic learning of halfspaces. However, none of these directly apply to the hypercube. Our analysis circumvents this barrier by performing a case analysis based on the critical index of the weight vector: either a small number of head coordinates
8

---

Table 1: Comparison of agnostic learning of halfspaces. We ignore the polynomial logarithmic factors
1/6.
Work
Domain
Distribution
Bench.
Smooth
Complexity
Kalai al.
2008
( (+1)) )m
Uniform
opt
None
n 0(A))
Kalai
2008
Sm-1
Uniform opt
None
Kalai al.
2008
I"
Log-concave
opt None
n ((a(e))
(
Klivans et al. (008)
IR"
Gaussian opt
None
(
Wimmer (2010)
[B]"
Perm-Inv
opt None
n expl (low loot 4 201)
Kane et al. (2013)
I
Sub-exp
opt.
Input noise
npoly(( (o
Chandrasckaran et al. 2024
R"
Strictly Sub-exp
opt.
Concept noise
(p)
Ours
(+1)"
Strictly Sub-exp
opt
Concept noise
dominate and effectively determine the output, or the remaining tail is regular, allowing us to invoke the Berry-Esseen theorem to approximate the Boolean tail sum by Gaussian, thereby enabling the use of continuous tools developed in prior work (Chandrasekaran et al. 2024).
5 Conclusion and Open Problems
In this work, we extended the smoothed agnostic learning framework to the Boolean hypercube, and demonstrated that halfspaces are efficiently learnable with respect to a broad class of input distributions (strictly sub-exponential marginals). Our approach combines tools from smoothing analysis, conditional polynomial approximation, and critical index decomposition construct low- degree polynomial approximators in a discrete setting where standard analytic techniques are not applicable. By competing with smoothed benchmark opt,,, guarantee circumvents known hardness results for agnostic learning over the hypercube, while matching the sample and runtime complexity of prior work in continuous domains.
Our current techniques apply only to single halfspaces, and the polynomial degree and runtime degrade as the smoothing parameter becomes small. In addition, our analysis requires strictly sub- exponential tail assumptions, and it remains unclear whether comparable guarantees are achievable under weaker conditions. Our results also suggest potential link to agnostic learning under smoothed input distributions, analogous to the Gaussian framework continuous domains (Kalai and Teng 2008 Kalai et al. 2009; Kane al. 2013 Chandrasckaran et al. 2024), Formalizing this connection in the Boolean setting appears subtle, due to the lack of Euclidean geometry and the discrete nature of fit-flip noise, and we leave it an intriguing direction for future work.
An important open question is whether these techniques can be extended to intersections of multi- ple halfspaces. While our framework theoretically supports such generalizations under smoothed optimality, a major technical challenge arises in adapting critical index analysis to this setting. For single halfspace, sorting the coordinates of the weight vector by magnitude plays central role in identifying regular and irregular components. However, in the case of multiple halfspaces, each weight vector may induce different ordering over coordinates, making it difficult to define unified notion of "head" and "tail" variables. As a result, applying a shared conditioning or decomposition strategy becomes nontrivial. Developing new structural insights or approximation techniques that can handle this multi-directional irregularity remains an open problem.
More broadly, this raises the question of how far the smoothed learning framework can be pushed. Can yield efficient algorithms for learning other complex Boolean concept classes (e.g., DNF formulas, decision lists, or polynomial threshold functions of higher degree) under heavy-tailed distributions? Can be made adaptive to unknown noise levels or to distributions that do not satisfy strict tail bounds? We leave these questions for future work.

---

Acknowledgments and Disclosure of Funding
We sincerely thank the anonymous reviewers for their helpful comments. The authors acknowledge support in part from the National Science Foundation under Award CCF-2217033 (EnCORE: Institute for Emerging CORE Methods in Data Science).
References
AWASTHI, P., BALCAN, M.-F., HAGHTALAB, N. and URNER, R. (2015). Efficient learning of linear separators under bounded noise. In Conference on Learning Theory. PMLR.
BLAIS, E., O'DONNELL, R. and WIMMER, K. (2010). Polynomial regression under arbitrary product distributions. Machine learning 80 273-294.
BLUM, A. and DUNAGAN, J. (2002). Smoothed analysis of the perceptron algorithm for linear programming. In Proceedings of the Thirteenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA '02, Society for Industrial and Applied Mathematics, USA.
BLUM, A., FRIEZE, A. M., KANNAN, and VEMPALA, S. S. (1996). polynomial-tin algorithm for learning noisy linear threshold functions. Algorithmica 22 35-52.
CHANDRASEKARAN, G., KLIVANS, A., KONTONIS, V., MEKA, R. and STAVROPOULOOS, K. (2024). Smoothed analysis for learning concepts with low intrinsic dimension. In The Thirty Seventh Annual Conference Learning Theory. PMLR.
COHEN, E. (1997). Learning noisy perceptrons by a perceptron in polynomial time. Proceedings 38th Anmual Symposium on Foundations of Computer Science.
CORTES, C. and VAPNIK, V. (1995). Support- vector networks. Machine learning 20 273-297.
DIAKONIKOLAS, I., GOPALAN, P., JAISWAL, R., SERVEDIO, R. A. and VIOLA, E. (2010). Bounded independence fools halfspaces. SIAM Journal on Computing 39 3441-3462.
DIAKONIKOLAS, I., GOULEAKIS, T. and TZAMOS, C. (2019). Esstibution-indeeendee pac learning of halfspaces with massart noise. Advances in Neural Information Processing Systems 32.
DIAKONIKOLAS, I., IMPAGLIAZZO, R., KANE, D. M.. LEI, R., SORRELL, J. and TZAMOS, C. (2021). Boosting in the presence of massart noise. In Conference on Learning Theory. PMLR.
DIAKONIKOLAS, I., KANE, D., MANURANGSI, P. and REN, L. (2022). Cryptographic hardness of learning halfspaces with massart noise. Advances in Neural Information Processing Systems 35 3624-3636.
DIAKONIKOLAS, I.. KONTONIS, V., TZAMOS, C. and ZARIFIS, N. (2020). Learning halfspaces with massart noise under structured distributions. Conference on Learning Theory. PML..
DIAKONIKOLAS, I. and SERVEDIO, R. A. (2013). Improved approximation linear threshold functions. computational complexity 22 623-677.
FELDMAN, V.. GOPALAN, P., KHOT, S. and PONNUSWAMI, A. (2009). On agnostic learning of parities, monomials, and halfspaces. SIAM Journal on Computing 39 606-645.
GURUSWAMI, V. and RAGHAVENDRA, P. (2009). Hardness of learning halfspaces with noise. SIAM Journal on Computing 39 742-765.
HAUSSLER, D. (1992). Decision theoretic generalizations of the pac model for neural net and other learning applications. Information and Computation 100 78-150.
KAHN J., KALAi, G. and LINIAL, N. (1988). The influence of variables on boolean functions, In [Proceedings 1988] 29th Annual Symposium on Foundations of Computer Science.
KALAI, A. T., KLIVANS, A. R., MANSOUR, Y. and SERVEDIO, (2008). Agnostically learning halfspaces. SIAM Journal Computing 37 1777-1805.
10

---

KALAI, A. T., SAMORODNITSKY, A. and TENG, S.-H. (2009). Learning and smoothed analysis. In Proceedings the 2009 50th Annual IEEE Symposium on Foundations of Computer Science. FOCS '09, IEEE Computer Society, USA.
KALAI, A. T. and TENG, S.-H. (2008), Decision trees are pac-learnable from most product distributions: smoothed analysis. arXiv preprint arXiv:0812.0933
KANE, D., KLIVANS, A. and MЕKA, R. (2013). Learning halfspaces under log-concave densities: Polynomial approximations and moment matching. In Conference Learning Theory. PMLR.
KEARNS, M. J., SCHAPIRE, R. E. and SELLIE, L. M. (1992). Toward efficient agnostic learning. In Proceedings of the Fifth Anmual Workshop on Computational Learning Theory. COLT 192, Association for Computing Machinery, New York, NY, USA.
KLIVANS, R., LONG, P. M. SERVEDIO, R. A. (2009). Learning halfspaces with malicious noise. Journal of Machine Learning Research 10 2715-2744
KLIVANS, A. R., O' D'ONNEELL, R. and SERVEDIO, R. A. (2004a). Learning intersections and thresholds of halfspaces. Journal of Computer and System Sciences 68 808 840.
KLIVANS, A. R., O' O'DONNELL, R. and SERVEDIO, R. A. (2004b). Learning intersections and thresholds of halfspaces. Journal of Computer and System Sciences 68 408-840. Special Issue on FOCS 2002.
KLIVANS, A. R., O'DONNELL, and SERVEDIO, (2008). Learning geometric concepts via gaussian surface area. 2008 49th Annual IEEE Symposium on Foundations of Computer Science 541-550.
LINIAL. N., MANSOUR, Y. and NISAN, N. (1993). Constant depth circuits, fourier transform, and learnability. Journal of the ACM (JACM) 40 607-620.
LITTLESTONE, N. (1987). Learning quickly when irrelevant attributes abound: new linear- threshold algorithm. In 28th Annual Symposium on Foundations of Computer Science (sfes 1987).
MATULEF, K., DONNELLL,, R., RUBINFELD, R. and SERVEDIO, R. A. (2010). Testing halfspaces. SIAM Journal on Computing 39 2004-2047.
MEKA, R. and ZUCKERMAN, D. (2010). Pseudorandom generators for polynomial threshold functions. In Proceedings of the Forty-second ACM Symposium on Theory of Computing.
MOSSEL, E., D'DNNLL,, R. and OLESZKIEWIC7, K. (2005). Noise stability of functions with low influences: invariance and optimality. In 46th Annual IEEE Symposium Foundations of Computer Science (50CS005). IEFE
NOVIKOFF, A. B. (1963). On convergence proofs on perceptrons. In Proceedings of the Symposium on the Mathematical Theory of Automata. Polytechnic Institute of Brooklyn.
O' D'DONNELL,, R. (2021). Analysis of boolean functions. arXiv preprint arXiv:2105. 10386
O' O'DONNELL, R. and SERVEDIO, R. A. (2011). The chow parameters problem. SIAM Journal Computing 40 165-199.
PERES, Y. (2004). Noise stability of weighted majority. arXiv preprint math/0412377
ROSENBLATT, F. (1958). The perceptron: probabilistic model for information storage and organi- zation the brain. Psychological review 65 386.
SERVEDIO, R. (2006). Every linear threshold function has low-weight approximator. In 2 Annual IEEE Conference on Computational Complexity (CCC'06).
SPIELMAN, D. and TENG, S.-H. (2001). Smoothed analysis of algorithms: Why the simplex algorithm usually takes polynomial time. In Proceedings of the thirty-third annual ACM symposium on Theory of computing.
VALIANT, L. G. (1984). A theory of the learnable. Commun. ACM 27 1134 1142-1142.
WIMMER, K. (2010). Agnostically learning under permutation invariant distributions. In 2010 IEEE 51st Annual Symposium on Foundations Computer Science.

---

A Bonami-Beckner Operator Approximation
We show that for any linear threshold function : =1113" {+1} the approximation error L of operator Ti pI to f can be upper bounded by O(Vp).
Lemma A.I For any linear functioon f {+1}+ + {+1] and o, p E [0, 1), holds that
5
BgnN, (111-1(()) [(x)] -
2 zVP.
Proof By triangle inequality and special case of Lemma have
3.4 when Q = {=1}" and μ = No, we
Eg-N, (Ti-N(((Tipf(() - f(z)l] = EzeNa (
f(z)]
EznNo [By ((y)
f(y) - f(x)]]
2B -e 1[f(y) * f())]
S (f)
5 $ zvD.
Therefore, choosing p O(22) makes this error most 6/2.
B
Polynomial Approximation for Ti (z)
We now approximate Ti-p(x(z) using polynomial for the more general class strictly sub- exponential distributions.
Definition B.1 (Strictly Sub-exponential Distributions) A distribution D on IR is (a, A)-strictly sub-exponential for all ||v||2 1, Fx>>ll(x, v)l 2- - (//2)**>
Our main goal this section prove the following polynomial approximation result in Lemma 4.7 Suppose f(x) (ign((w,rr x) 0). Denote w ④ x u. Without loss of generality, suppose that |un] 2 U2l 2 ... 2 |u.ll Then, have
Ti Tz) Ey (sign( Ow 0)] Ey- (sign(((, (u, -0)]
To obtain a polynomial approximation of (z), we first prove Lemma 4.5
Proof Let
I(a,c) = 11/1///////1111///////1/1111//11 + 2 [|
(bggL///joog((/////e))= (0 (mxx
(og (\, 1) log max m (a)e)aa))))
([(o(((()))0(((])))))))>+)) ( log (oge////)/a
O(lgg( +
where C' == (1 -1-220 2po) Alog (2/e) + logg(2/e)
If a-critical index {(a) I[a, c), then the first condition holds by taking H ((a) If the a-critical index E(c) 2 L(a, <). we will show that the second condition holds.
By Lemma 5.5 in Diakonikolas et al. (2010), there exist set of nicely separated coordinates
G (ū1, i2, (,) C where i, < i2 <... < l and i - is = [ logo11/// /a such that |M6 S |ua. 1/3 for any & 1]. Then by Claim 5.7 in Diakonikolas et al. (2010), for any two
points X2 E {+1), we have (uc.xi) x1) (ug, x²)
Wi.1 Take f log [/e)/ por For any
12

---

fixed assignment to the variables in H \ G, we have
0 - [,
y
Willi
Py
Σ REG
W:lli (0-
E
Uith
[use|
0
Σ
U:tl/
4
4
iEHYC
iEHNG
P Vy = x1] x=E(1
max
< po) Se pat E,
where the second inequality because there's at most one point an interval of length ju; given that (uG. X1) are well-separated. The third inequality is because
max (P(y: 11, Ply 1]} v max [1 pa, pa)) = - pa;
if 2; 1, if = -1.
max [P( P|y -1] z max o), p(1 -(1--)) p(1--pp1-) 111 po,
By our choice of L(a, t),t, is we have
L(a,e) - i, 2 L(a,e) [log(1/e)/oo] [(4/a²) log(L/a)] 22lo(C/o))/a.
By applying Lemma 5.5 in Diakonikolas et al. (2010), we have
||T||22 = or < (v a2) luu, S C |uaal-
Therefore, by Lemma C.1 for least 1 fraction of x, holds with probability at least y that
||rll2
(ur,
(u) 01 =
Σ wiYh -
4
REH
Then, follows that with probability at least - e of we have
sign (u.. yH) (ur. 0) sign ((uH. 0).
Now are ready to construct our polynomial. We consider the two cases in Lemma 4.5
separately.
Case the weight vector w of the LTF falls into the second case of Lemma 4.5 notice that
( YH) 0) Sign((wa) @ XH.YH) 0) can be represented as polynomial py (x) of
degree at most H = since only coordinates of x are relevant. In this case, we take our final polynomial as
(x( = Ey~N1 (xy = Ey-Ni (ww O XH, YH) - 0)]-
Let A(x) be defined as the error term EEZ-N [|px(x) - Ti Tx-pfx(2]]] We have that for at least - fraction of it holds that
(xx) Ez EynNi (x)) (sign( XH.YH) 0)] Ey-Ni (x) [sign( (w о xx,y 8)]
S EzuNs ( sign( (WH XH) 0) sign( ④ xx,y) 0]]]
2Ez~NN [Pymni (ign OzH.НH² - 0) * sign( ( 2 x,,) 0]]
<
It follows that the final J,, approximation enror
ExwD, [En.N [xpx(x) Ti Ti-pfx(z)]]
=ExDD [Axx)]
Exx,D D2 (A(x)l"good" "good" x) IPx-D, ("x"o,""good ("good" x] + Ex (A() x] PX-DD ["bad" x]
$ 2c 1 2 4e.
Here "good" refers to the at least 1 - fraction of x such that the approximation in 4.2 holds.
13

---

Case 2: If the weight vector w of the LTF falls into the first case of Lemma 4.5 following approximation
we consider the
Pyn (x) sign((us, yn) 8) -1 (IKu,, yn) 0 C || l12)
+ +Pyn (x) (KuH,, 0 - C. ||url22),
where C = (1 2po) A log गो (2/e) v 2 (2/(( and Py (x) will be choosen later as (B.5) In
this case, we take our final polynomial as
Pz(x) = By (x)]
Let ( be defined as the L, error term ER [xxx(x) Ti-pfx (z)]]. For notation simplicity, we denote (yn (uuryy)) 0 C. ||u|||2] event Then, we have
A (xx
E8 (4 (x)] - - 10) fx(y)) 1 [811]
E By~~N1 (py (x) fx(x)) [8]]
S Egnn
By~Ni (py (x) fx(x)) 1[ [y> (py fx(y)) 1[89]
EErNs
By-Mi (x) sign( (u, y) 0) sign((u 8)) ][81]
(x
BanNo [By (sign)) (u,y) - 0) - Tx)))) [[9]]
A2(x)
Notice that by Lemma C.1 for at least c fraction x, (ur,yr)) S C- ||u |l2 holds for least 1 fraction of y. For such x and under event E, we have
Kur, Yr) I C² ||ur lla < (u).yn) 0),
then it follows that
sign( (u, (u,y) 0) 1[ sign((ug, + (ur,yr) 0) 1[E] sign (igu(uu,,yH) 0) 1[8].
Then, for at least 1 fraction of x we have
E By~Nii,(a)) [(sign(((u y) 0) sign( YH) - 0)) 1[8]]
$ Ey By~Mi .(x) (( sign (u, y) - 0) (ign((u..yel - 0)) 1[ "good" y|
P (e) ""good" y]
+ Ey-Ni (x) sign y) - 0) sign((un. - 0)) 1[8]|"ba'" y]
Py Py~Ni "bbdd" y]
50+2. 2c.
Here "good" y refers to the least fraction of such that (ur, yT) < C- ||uT||a holds. Therefore, we have
Ex [1(()) ExnD, (x) x) Px ("good" x]
+ E Ex [ (x) "bad" x] .PNND, ("bad" x]
$ Ex D. A (x) "good" x] 2-c
< 2c + 2c = 4c.
Here "good" x refers to the at least 1 e fraction of x such that holds.
$ C- -e-rllllllll 2 1 1-c
Next we consider bounding (x(x) by constructing proper low-degree polynomial Py (x) as follows. Recall that NZ)p(z)) where y, 2; with probability 1 p and yı randomly drawn from NG, with
14

---

probability we use the following rerandomization trick for random vector yr: for each coordinate of yr. let
y: = (1 - 24 + 1,Ts
- y/ (1 1,), + 4(1 - m.) + lampeer
(B.1)
72 (1 mm,) mç6ii
where
1 w.p. P ww.pp111
1 w.p. 1
[1 w.p. 20
mm
-1 w.p. a
w.p. 1 20
and E is Radmacher random variable. Let random variable A yu -0. 0. Then by B. we have
A yu. -0
Yu) + ((ur,yr) -
Yu) + (ur, (1r -1)) @ 2r) + (ur, (1r 11r-myn (17-m7)) 0 0 (ur, mr O ET)
(uH.YH) + (ur, - (ur, lr @ mr @eT).
:=b
where VT: = (1T - IT) 2r + l @ (1r mr). Then we have
Ti-pfx(z) = Py-N11p(00 (iggn((())) (u 0)
1 E E
Eyn.A (sign y E E+]
fy. mr [E)lsign(A))y,, my] 1[y= E E9]
br
[(1 [11-2PA(a A < 0ly Ir my)) 1yy E
Iy
[1 2P
(1-2P'B B - bbyn ly myl) 1y e 89],
and
A2(x)
By (x) sign((u - 1 E E9]
Ey (Tx(() 1yy E E
(1- EynNi ,(x) [Fx(x) 1y E E8]]
Exnsi
By Theorem C.3
we have
B
Ur ly my la 3 Up 3 my
sup FER
S x brlr, (xx) S
|u O l O m
where C" is constant. Therefore, we have
Ti Ti-pfx(z) - Byn.r.mm [11-20
(1-20) -2-20 ||T l7 2 m
1 I (ynEEt)
| -byy,, l7, mr] +
< 2By .r.
1 E79
[ur In o
[u @
mr
ll
2C' Eyn.dr.m
1yy E
|ur ②
l
my
llz
[u ④ l
mrll
< 2C Eyn.Jrmm
1yy
E EE9
|u
my
lz
Notice that this case ur is o-regular and 4mm takes with probability 2p and with probability 1 2po, then by Lemma C.2 for least 1 fraction of (Ir, my) it holds that
| 1 < (po) Trrlea a
||u lr mz
(B.2)
long the condition S par / /lo /log(//))))) [/e)/2 holds.
15

---

Notice that
- 2Φ
(y Ir, mr)
ur
m
-3 X) y, lr; mr).
let
(z)
By dy my ex (ignnni)nggga my) 1(07: mr) E Ei) Ilyn E E
where & is the event regarding the randomness of (Ir, my) such that B.2 holds, then
[pfx(z) Tz)x(z)
|PIB < -bly Ir, mr] o0
2 28 .T.m
|ur ④ IT 2 mrlla
E Ei] 1[yи 89]
+ Eyn Ir. mr
1 - 1-2PPBB v -byn lr mrll 1((r. mr) Efl 1ly E E
| ② lr 2 mr|k
< 2C' By
1 mr) E & 1ly E
|ur O lr 2 mr
+ Eyndr.m
[ m7) E Ef] 1[y E E
$ 20" (po) 3 +
< 20" (2po/ log(1/e)) +e
I 2c,
as long as p (oo(log)(////) Then, we have
BenD,Eann [[Tffx() Tzfx(z) S 2E.
Now we only need to consider polynomial approximatio for Tzfx(z). We can recenter the expecta- tion around zero follows:
E (x-N(b.lww (13) by, my]
1...Kt//lwwoorrrmmm1....... (iign wT lr urlla s)ly,, mr]
sign( |T L O my s). N1ss |r @ ly o mr 22, 1)
Enqq
ys. lr, my
((s)
E sign( [TT o ly C mr 8) e $ l0g
V2T
Iwroly la
Y yH, mt
where elll
For the simplicity of the following analysis, we define random variable
uu, VT)
(Wr C Xr, VT)
(Wr O VT,
|r vrlla
| @ o
|wr O vrlla
Since is (a, strictiy sub-exponential, then satisfies the following concentration inequality:
P Px~D, |||| > t < 2 (1/2)+1a
16

---

Then, we can rewrite:
(un,y - 0) + (ur, vT)
((um,yn) - 0) + ||wr @ vrll2 |[ @ ly @ emrle l2
Wr ② lp Commp 2
wwy @ lp @ mrll
For simplicity, denote
WT V
(uH. yn)
c= |wr ② ly ④ mrl12
Wr @ by @ my
Notice that under condition (1r, my) E & and condition Yи & we have
|c| ((u:yH))
|urll2
I C
S C. (po) 112 =
(B.3)
ww @ lr @ my lla
WW ② lr m 2
|a| Ww (1r 1r)
Zr 1l2
Wy ly (1r mr)l
[w @ ly
@ m
Wr (Ir 1r)
|| @ Irll2
|w @ l @ myl2
[wrll ||2
WT ④ 17 m7l12
$ (po))-1/2 -1/2
(B.4)
where C = (1 -20r). Alog tox (4/c) + / log(2/)). We also have
az + G,
WT @ 17 C my
and hence
myl
(azse)2
sign([[wr 1p m s) -- foR (aazto)
Eg E
YH. 1, my
2
C
sign([[WT O lr m s) 2 102 Q(s). c( 20)
E
yH. lT, m7)
V2T
Then, we have
T Tz)
Eyndr.m
E
lr, mr] 1[(,,, m7) E &i] 1 E9]
2,2
EEnndr,m
[ my) E1] 1yy 84]
WT I my ll2 s) & lo) ca(o-c)xtddo-80 10) yH. ly my
E.s sign(
We now define polynomial (x(x) approximating Tzfx(z). To do this, we approximate e }a²x" and ca(s-c)a using polynomials æ. First, we use a polynomial pi (x) to approximate ja?==" This polynomial is given by the following lemma. We choose the parameters later.
Lemma B.2 Let E Z4. Let x be random variable satisfying the (o, A)-stricaly sub-exponential tail bound. Then there exists a polynomial q of degree
11/a ( Bobloo(abb 2/a (log(1/e)) max(11/2+1/a) (1/////a)///a) 01/a²)
where C a sufficiently large constant such that the approximation error R. ((((x) - upper bounded by 2c.
17

---

Second, to approximate en(s-o)z, we use the function Pz(z, (a c)r) S T] where (a) 1 + Σ s¹ the degree & 1 Taylor approximation of ex. We choose degree & and threshold T later. Thus our final approximation of Tzfx(z) is
Px(yH, lT, mT) = pi (ar) 1 sign(1 wT @ lr @ mrlle se e -- -og Q(x)
cc(=-t)) p2(2, yn. lr, mr]:
Pyn (x) = Bm,,mr ( lT, mr) 1 my) E &.],
(B.5)
xx(x) = Byn INH (x) y E E
We now want to bound the L1 enror tern Ex~D, Ez~,, [x)) -pfx(z)]]- To help us analyse the error, we define the "hybrid" function Pa (x) such that
B Bo-.(0011) sign([[Wr ly mrll2 8) e -log Q(s)
Px Px bT, mT)
22
((00-30) p2(1, 8) y H, l7, mr]:
(x(x) Byn.r mu [Dx(H lr, my) 1(0r, my) E Eil 1ly E E9].
We have that
D RA,,, (1ix(x) T1-pfx(2)]
S EXND, EANN. [1(x(x) Ti Ti- Tx=n(x(()]]] - Enn,, [[ Pa (x)
Ax(x)
Ai(x)
We now bound Ax(x) and (x separately. We have that
(x) < Eg Eyn lr ma [e- 20²=2 E E
-lx ((x) (0)
p2(x, s)
1 [(Ir,m) E Ei] 1ly E Eq]
Observe that Ax(x) can be bounded as the expected sum of the following two terms:
Asi (x, mT)
2
-1gg -o (c) cla(a-cjal
EanQ
la(s c)al* 1[[s| s T
2tT
Ag2 (x, YH, 1y, mr)
222
E le - -lo Q(s) c00--2o) 4c) ca(s-c)x 1||s| > TT].
2m
where the first term't 's bound comes from the fact that (xx(x) e²1 - .. |
del
18

---

We first bound A31. We have that
A31 Ax, 1r, mr)
e- 2 100 Q(e), cllo-2o) cla(e-ckel, [[ss| 7|
(laco) + |aTx)))
B
2t
k!
(lacr) laTxx))
Te- (a)to))))))
V Q(s) ESNQ
1| T
k!
(lacr) |aTxx:1
Te (c==(o-))))
+
BENQ
1[ s ST]
k!
V2T ((s)
(lacr) + |aTTx11
[N(s; + 1,
(kl)²
Q(s)
+ (lacr) |aTTrr))22
[[88; az; 1)
E
(k!)²
((s)
2 2((acx) + laTTax))*
k!
where the second inequality is by cla(s-c)al < ca(s-c)e + e a((--)c) Then, we have
Ex BE
Byn dr Amr (x. mr) [[(r,, mr) E Ei] 1yy e E
Byndr.mm (acco)
+ |aTx|>*
< Dx
Ex-Ns
[ mr) e &i] 1yy Eq]
h!
(lacrl + |aTTx)* Bx
Eyn
1 [ m7) E E fly 8
h!
Under condition (lr, mT) E and condition yu E E we have BB3 and B.4 and hence
(Jacol + laTx))*
ExnD,
1(0r mr) E E fly e E
la' k ((c| + (TI)* B
k! la ((c'l + (TI)* CX.. (
k
ita +
kd
(+a)
14a 126
$ 6,
when
k 2 (C')a'((le) + (TT) log(1 log( + (1 + a)
(B.6)
and C' is a large enough constant. The second inequality used Lemma C.5 We now bound Ag2. We have that
T (=--((ant))
Ax2 (x2 yH, my) = Eenq
1|s1 > T7
Q(s)
N(s;ar+c,111 27
/ Ben@
P. Pawe [|s| > T
Q($)
Celax+ol T-
< C' Mlexlt el) T/2
The third inequality is based on the following claim.
19

---

Lemma B.3 Define the distribution Q on I. with density function Q(s) e-141 12. Then there exist a universal constant such that for every b E E. holds that
(V b, 12
1
2
B
- Cell.
Q(s)
Thus, we have that
Ba,No Byn.r.m, (x, yH, lr. mr). 1[(7, mr) E E 1ly E {
Ex
Bz Byn 1r (Ceeilartttll) - 1[(,, my) E &i] 1ly E {1]
$ BxxD2
-BzNNo
E Byn.rmm
ExnD_ (let(aaz)t))) e T/2 1[(7, mr) E Eii 1ly E E
I Ez
Byn.r.mr
ExNDe CC [[[r,,m) E &i] 1ly E
E1] e 1-
BxnDx C (CM (a's)) ججم
Eyn
O" ('' 12_ 1-/-T
S,
when
T (a (d'))t+a |d'l + 2oogoo('' (ogg(C// /e).
By
B.3 and (B.4) we can take
T = -1o))) log(1/e))
x1+
(B.7)
The third last inequality is by Lemma C.6 Plugging this into the bound for k in (.6).. we can take
h: S (C'a (C'a'X(2n" + (a' ++ + (og((C/)) log(1/c)) 1+
+1++a)
for constant C "" By B.3 and B.4), we know that
(po) (po) -1+ 2 log logg (1/0) 1+ + (1+a),
k: < ("' (²
(B.8)
where C!" is large constant.
We now bound (x).). We have that
,
By br mr [[ (r,,,)) - (y In, mr)l 1 [(r, mr) E Ei [yn E E81]
1
Eg Eyn Vy my [le fa²u² (
Eangle 3 -lg +(s))+((=-)) 9) s2(
V2x
1((r my) E Ei] 1yy E E9]
Notice that
-lo log ((s)) {) p2 (2, s))) (Bangle 2
< EnnQle 5² 2102 ((0) o.1 Ean (22 s)
(
(N(s: 27 Q(s)
(a(s (lls-cpoo -c)))) 2 [|]s/ ST]
EanQ
i!
(a) 100 2
< Cell..
200
20

---

where the last inequality is by Lemma B.3 Thus, we have
Bx<Dx(A1(2)
< Eg E Yy Bx ||e $0²=² p1(z))
- +10 p2(2, s)]]
[BmoQe
[0r, my)
Eil 1ly E E9]]
|a| |a| + Mc1)
By by my Ex ||ee _000² - pi(t)] Ciee!
S Ez
i!
11) Ilyn E 89]
Denote
[a| + +cD"
As(yn, mr) = BxND le la'x" -x](x) Che !s
i!
1 mTT E Ei] 1yy Eq
We have
ssyy,,r,m, mT)
S 1''cke1/2 v Bx (ee 2att" - (xx)²
[0r, my) E Ei fy e E9]
(a]{(T)) + + 2
Bx
1 mr) E Ei] 1yy E &
i!
1=0
[(T) l 2
< C'ele'1/2.8
Ex
1((r, mr) E Ei] 1 E Eq]
i!
< <C'el''/2.. 8.
| + le'l)²
2
max 1isk-1
CA2i.
2i
IFa
2i
e 1
22
1+0
i!
1 + a
< CC"6g
2k
1
Se
when 8 chosen accordingly. The third inequality by Lemma C.5
B.2 and taking the exponent b as 2, the degree of pı (z) required to get the error is 2/a 77) (log(1/0) max(1. ) C1/a²)
By Lemma
(a x²
=0 X² 22 1+1/a (C'lo(aa A)) 2/a
(log(1/e) [o'(((TT')) (cl) + (k+ 1/4) (144)) 2/a+1 2/0t1(1//22)
-0 (C 2)) 2/a (log(1/c) + |a'((TT] + (d]) + 18/2 2/001 c2/a²). (ot
By using B.3 and B.4 and plugging the order of k, T (3.7 and (B.8), we know the degree of
(1 is
((00))-11/2) (C (Clog((o0) (+ -) (po) +1 x1+ log log g (1/c)) 1+? c :.
=0((C(po)- llog(1 (1()) log(())))((++))))
21

---

Putting everything together, we get that the degree of Px(x) is at most 2H + deg(p1) + deg(p2) which is
O X1/a² log(LL//) + +((((o)))+ Alog(1/e) b
Plugging in the order of p - (2(E2) and - 00po log(1/e)), the degree be bounded by
((Co- 01))))))))))))))))))
C Proofs of Auxiliary Lemmas
C.1 Proof of Theorem
Proof Let f be the optimal halfspace that achieves opt.- Let Pa be the polynomial of degree at most d such that
x
(C.1)
Consider the sample dataset S [();;,:)) in a single run of Algorithm 1
Let ps be the polynomial chosen by the algorithm and hg be the corresponding hypothesis that the algorithm outputs. By the proof of Theorem 4.1 Kalai et al. (2088), we have that
Σ [[,s(x)) + vo
Σ 1/ Ps(x;)]
N
2N
Notice that ps is the minimizer of the error, and thus beats any polynomial Pz we choose, we have
Σ Ut
ps(xx:) I ERNN,
Σ 1y4 pa(xii]
2N
2N
N
N
ExWNa
Σ
(x; Oz) Px(x;)]
+ +RZN
U:
(x, oz)
2N
2N
i=1
(1(S)
A2(3)
By C.1
we can bound (S) as follows:
Es-Don [S)] 2 Dx px(x)]] S ze.
By the optimality of fr, we have
Esnpen [A) (xx.j) D 2)
- [1 (x 2)] opt.
Thus, we obtain
(x,) # wi] S opt, + 2
Es-
Since our hypothesis hg is polynomial threshold function of degree d on variables, VC theory tells us that for N = poly(n
(nd///) /c), we have that
ES-DOn (hxx))) + vil I opt +
4
By Markov's inequality, on any single repetition of the algorithm, we have that
7 opt, + - PS-DAn P ((x.))D(hssx)) * vl 2 opt + - opt, 7 <
16'
Hence, after r O(log(1/8)/a repetitions of the algorithm, with probability at least 8/2, one of them will have P P(x.)) (xs( # y) < opt, + fc.. In this case, using an independent set of size (llog(1/8)))), probability most 8/2, we will choose with enror > opt, + e.
22

---

C.2
Proof of Lemma B.3
Proof The proof below is straightforward calculation by completing the squares.
E
(V(5;b,1))
1
2x
bs=b)²
---ldss
2 R
_e
-- 2|a1
1
/
(b-b))
π
1
(a 2) ds +
1 c-(o-b)--p
/
$
J3
J/3
1
-(- 2)) + do
1
E
π JR
b+4
b+7
+ n
2e 1
V π
C.3 Proof of Lemma B.2
Proof Let p(x) = Edeg(n) q.r' be the polynomial obtained from Lemma C.4 with error c/2
and = (log(L/E)) to be choosen later. Our final polynomial g(x) = p a x²) Clearly, deg(g) 2. deg(p) =
We now bound the error.
[g((((x) - e )
= Ex (a(xx) e - tu²=" 22o 11a2>2/2 < 27] + Ex [((()) - - t......0 2 7
= v BB [(((x)
Ex, 1 1022 T]]
2e - 1
Sct V E. [(((x) _ y2b]
where the last inequality is by the tail bound of (a, X)-strictly sub-exponential random variable.
We now bound E. (g(x) e 3a²=" ) We have that
E. [(((z) e- )
< Eu [(l(x)])]+ 1)ab]
+
s Ex ( 1+
deg(p)
Ica
20
a
28
2
m
(deg(p) 2)
deg(p)
max
|cp
2b
deg(p) a abi E, 2ba max =
k=0
22bi
S ChC llg((//)
deg(p) max
abb E 2b0
1=0
22bi
Chyy Tlog(1/o)
deg(p)
a max 1=1
C'bi
4bi
1+a
464
1+a
4881
220i
I+a
1+ a
Cb
Tlog(l/o))
150
450
$ é (
where the third last inequality is by Lemma all together, get that
C.5
Here C, C² are large enough constant. Putting
E, (g(xx) - - --- 2=2002
Ui
< 2c C /logl//////////laa///a
-,27, 21
2c
23

---

Choosing
T (= (C 1o log (og(1/))))))) 2/a (1og(1/c) m (Cmm)
where C" is large constant makes the total error less than 2e, Since i' (log(1//e)) the degree of the final polynomial is O(yTlog(1/e)) which
T = (0)222) (C log' (ab) (ab)//oo(11/e)) // ( (2.l///))mmmx0.///////// (121)
C.4 Other Auxiliary Lemmas
Lemma C.1 Suppose x is a distribution on {+1}" that is (a, X)-strictly subexponential and y distributed as N1- N1-p(Z). For any fixed T S [n] and fixed n, with probability at least of x, holds that
Py Kur. C. ||ur 2 21-c.
where 11 W ② X and C = (1 - 2po) A log Tें (4/c) + v 21og(2/6).
Proof By Hoeffding's inequality, have
Fy (u) - Eyl yT)il 2 21] s 2exp (-
12
2 2|/ur
Therefore, with probability at least 1 - e holds that
(ur, yr)
By Eylkrryrr) (2log(2/e) By + 22 log(2/e)
| 12
Notice that
y [u.ii] u/Ely,] u, ((1 ([1-p)z + p(1 -2r)),
Ey
yrh) (u) (1 p) Σ u:2 p(1 - 20r) Σg U4
EET
iET
-11 p) (WT ZT, XT) + p(1 20) (WT, XT):
since x is (a,, A)-strictly subexponential, have
Px ((W,
t. t-|//]lla]] s 2exxp (- (t/2)1ta),
and
Px ((WT o zr, xT) > t [ [l]]] s 2xxp (- (((/2))ta).
Thus, with probability at least - c of x holds that
(wr,xT) < Alog To. (4/c) //wrl2
and
[wT ② XT)x < X log (4/c) ||wr|22
Notice that x is distributed {+1)" and hence ||ur||2 ||wT @ x ||wr||2, then with probability least 1 of y it holds that
Kut.
Ey E
(2g/(2//c ||uT|l2
< (1 - p) ( 3 kr, X7) + p(1 - 20) 1(w,, x7) + /2 log(/ee) ||urlla
$ ((1 - p) p( 20)) A log -: (4/c)
|W l| + / log((2/)
||ur||2
(C.2)
< (1 2po) > log -े= (4/e) || / 2 log(2/e)) ||ur ||2
= C || 1|
where == (1 2por) Alog 1+m (4/e) + (log(//e).
24

---

Lemma C.2 Suppose that the vector E IR" is a-regular, ie.. l| S a 1| Suppose u is n-dimennional random vector where each coordinate is I with probability p and 0 with probability
1 p independenty. If S pl (l//(1//)///) then with probability least 1 6 over the randomness of u it holds that
oo a 1lwl22 c. a || @ u1/2.
where c c= (p- /log(1/6)/2 a) 4. If condition a S p/ V (2lo((16)) holds, then with probability at least ô the randommess it holds that
|| S a |wl12 & (p/2) $ || @ u112.
Proof By Hoeffding's inequality and notice that (w,u, wf, we obtain
uf B/u,1 puf and 0 I (w;u,)² -
2t
P ||w c uul2 p. 1w S -t) s exp
||
l1
2t
S exp
w
2t
S exp
a2 W
where the second inequality is by the definition of the infinity norm, and the third incquality is by the a-regularity condition. Therefore, with probability at least - 6, we can get
u 1 2 p //w122 log(1/8)
||
2
Then, with probability at least - 8, holds that
|/| S a- ||/l2 S a (p (p-1
log (1/8)
[| UuIl2.
2
Theorem C.3 Bessey-ssseen CLT) Let X1,X2, X2,..., be independent random variables with E[X,] 0, [ = of > 0, and El X,1 = Pi < co. Also, lel
X1 X2
X
S, Vo +
be the normalized n-th partial sum. Denote F,, the edf of Sn, and O the edf of the standard normal distribution. Then for all n there exists an absolute constant C such that
72
sup ( zEk
Ps.
Lemma C.4 (Lemma D.11 in Chandrasekaran et al. (2024)) For T > 0 and error > 0, there exists a polynomial p such that
1. suPxe(o. (p(x) - -
2. deg(p) S
= = w=(oog((/)))
3. p(x) -deg(r) cx where lcil < CV/Too((//)) for all < deg(p). Here C is large enough constant.
Lemma C.5 If x is (a, A)-stricttly sub-exponential random variable satisfying Pe[la] t 2 t then the k-th moment is upper bounded by:
] CX*
(
14a
1+
where C. is a universal constant.
25

---

Proof By the layer cake representation and the tail bound, we have
1 = / th-1 Pall > tldt =
2k Jo th-1 e (1/2)/= dt.
Making the substitution (1/2) i.e. == A and dl
d tho ds, we get
Ita
|x[1x|11 S 2k:
Xk- Ak-1 gi-a
k-1
X
x rea ds
1
2 (o
8t
sitm-1
e ds
1 a 50
2
k
1 T+a)
Notice that (a)) < 122-1126-2 for positive constant C, then have
Ex[x=|1 s
k I+a T+a
2
C(
ria-3
E 1ia
1i
Lemma C.6 If x is (a, st-strictly sub-exponential random variable satisfying Pa[(æ) t S 2 (1///)) then for any a > 0
[e & 3e (aX))++1
Proof We split the integral into parts at threshold T, which choose later:
By [1 = Ex [ealz] 1 [[xc| < 7]] + Ex [ealo] [[[=] 2 T]
S -e² Ey [e I [| T].
By the layer cake representation and the tail bound, we have
1[ 2 r7] = f ae .Pl[a tldt s 2a I eat - dt.
Eg [ Choose 7 to be
Then, we have (1/ 2 2at for 1: 2 T and hence
E, [ 1| 2 T7] s 2a
c c dt = 22
Thus,
[ < + 20 oT < aT =36 (a2)
26

---

NeurIPS Paper Checklist
The checklist is designed encourage best practices for responsible machine learning research, addressing issues of reproducibility, transparency, research ethics, and societal impact. Do not remove the checklist: The papers not including the checklist will be desk rejected. The checklist should follow the references and follow the (optional) supplemental material. The checklist does NOT count towards the page limit.
Please read the checklist guidelines carefully for information on how to answer these questions. For each question in the checklist:
You should answer [Yes], [No], or [NA]-
[NA] means either that the question Not Applicable for that particular paper or the relevant information is Not Available.
Please provide short (1 (1-2 sentence) justificatin right after your answer (even for NA).
The checklist answers are an integral part of your paper submission. They are visible to the reviewers, area chairs, senior area chairs, and ethics reviewers. You will be asked to also include it (after eventual revisions) with the final version of your paper, and its final version will be published with the paper.
The reviewers of your paper will be asked While "[Yes] " is generally preferable to "[No]" ", it is perfectly acceptable to answer "[No] providded a proper justification is given (e.g., "error bars expensive" or "we were unable to find the license for the dataset we used"). In general, answering binary way, we
the checklist one of the factors in their evaluation.
reported because it would be too computationally
"[No] " or "[NA] is not grounds for rejection. While the questions are phrased acknowledge that the true answer is often more nuanced, so please just use your best, judgment and write justification elaborate. All supporting evidence can appear either in the main paper or the supplemental material, provided in appendix. If you answer [Yes] to a question, in the justification please point to the section(s) where related material for the question can be found.
IMPORTANT, please:
Delete this instruction block, but keep the section heading "NeurIPS Paper Checklist",
Keep the checklist subsection headings, questions/answers and guidelines below.
Do not modify the questions and only use the provided macros for your answers.
Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: The abstract and introduction clearly state the paper's main contribution: discrete analogue of smoothed agnostic learning for Boolean halfspaces under strictly nub-exponential distributions, along with a computationally efficient learning algorithm. These claims are supported by the theoretical results in the main body (Section 4.5
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made the paper and important assumptions and limitations. A No or NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
It is fine to include aspirational goals as motivation as long it is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors?
27

---

Answer: [Yes]
Justification: The limitations our work are discussed in the conclusion section of this paper (Section 5).
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create separate "Limitations" section their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is low images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community, Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory assumptions and proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and a complete (and correct) proof?
Answer: [Yes]
Justification: All theoretical results are clearly stated with assumptions, and full proof's provided in the main paper or the supplementary material. Lemmas and tools from prior work are cited and contextualized.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but they appear in the supplemental material, the authors encouraged provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should properly referenced.
4. Experimental result reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided not)?
Answer: [NA]
28

---

Justification:
The paper is entirely theoretical and does not include empirical experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution is specific model and empirical evaluation, it may be necessary to either make it possible for others to replicate the model with the same dataset, provide access the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how replicate the results, access to a hosted model (e.g., in the case of a large language model), releasing of a model checkpoint, or other means that are appropriate the research performed.
While NeurlPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily new algorithm, the paper should make it clear how to reproduce that algorithm. (b) the contribution is primarily a new model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is new model (e.g.. a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors welcome deseribe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [NA]
Justification: No datasets or code are used or required, as the paper does not include experiments.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nips.ce)
www.sabmissioooooooooooo for more details.
While encourage the release of code and data, we understand that this might not be possible, so "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https //nips cc/ httpll/ccggiidee/ooeeestttoiioio
for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
29

---

The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental setting/details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary understand the results?
Answer: [NA]
Justification:
No experimental setting is involved; the paper is theoretical.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to a level of detail that is necessary appreciate the results and make sense of them.
The full details can be provided either with the code, appendix, or as supplemental material.
7. Experiment statistical significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer:
[NA]
Justification: The paper does not include empirical results or plots requiring error bars or statistical tests.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, statistical significance tests, 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, 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).
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 should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful 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.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [NA]
Justification: No experiments conducted; compute resources used.
30

---

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, cloud provider, including relevant memory and storage.
The paper should provide the amount of compule 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).
9. Code of ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurlPS Code of Ethics
Answer: [Yes]
Justification: The research is theoretical, complies with NeurlPS ethical guidelines, and does not raise ethical concerns regarding data use, privacy, or fairness.
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 cireumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g.. there a special consid- eration due to laws or regulations in their jurisdiction).
10. Broader impacts
Question: Does the paper discuss both potential positive socictal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification:
The paper is purely theoretical.
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 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 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 (c.g., gated release models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility ML).
11. Safeguards
Question: Does the paper describe safeguards that have been put in place for responsible release of data models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
31

---

Answer: [NA]
Justification:
The paper does not release data, models, or tools with potential misuse risk.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do require this, but we encourage authors to take this into account and make 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:
No external datasets, models, or software assets are used.
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 dataset.
The authors should state which version the asset used and, possible, include 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, paperswi thcode. com datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that re-packaged, both the original license and the license of the derived asset (if has changed) should be provided.
If this information is not available online, the authors are encouraged to reach out to the asset's s creators.
New assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification:
No new datasets software assets are introduced.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details the dataset/codeemmodll as part their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and research with human subjects
32

---

Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well as details about compensation (if any)?
Answer: [NA]
Justification:
No human subjects or crowdsourcing are involved.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According to the NeurIPS Code of Ethies, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals or equivalent for research with human subjects
Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/review based the requirements of your country or institution) were obtained?
Question:
Answer: [NA]
Justification: No IRB approval necessary, as no human subjects are involved.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing research with human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent)
may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
16. Declaration of LLM usage
Question: Does the paper describe the usage of LLMs if it is an important, original, or non-standard component of the core methods in this research? Note that if the LLM is used only for writing, editing, formatting purposes and does not impact the core methodology, scientific rigorousness, or originality of the research, declaration is not required.
Answer: [NA]
Justification: No LLMs were used in developing or supporting the core scientific contribu- tions of this research.
Guidelines:
The answer NA means that the core method development in this research does not involve LLMs any important, original, non-standard components.
Please refer to our L.LM policy http:://eeerrippccc/////eeeeee/e for what should or should not be described.
33


Reviews:
[{"review_id": "0wiB69oq0w", "reviewer": "Reviewer_PZPU", "summary": "This paper studies agnostic PAC learning of halfspaces over the Boolean hypercube. Without further assumption this problem is hard. The authors tackle the smoothed setting, recently introduced  introduced by Chandrasekaran et al. (2024), which is based on smoothed analysis from computational complexity. Here the goal is not too output a predictor whose true loss is close to the best true loss in class (i.e., over all halfspaces), but instead the true less of the output predictor should be small compared to the best predictor in class over a slightly *perturbed* instance. This makes the analysis less worst-case. Additionally they assume subgaussian (or somewhat more general strictly subexponential) marginal distributions. While Chandrasekaran et al. (2024) study halfspaces in $R^d$ with Gaussian perturrbations here instead halfspaces over $\\\\{0,1\\\\}^n$ are studied (with bit flips).This requires a new perturbation model and various adaptations of previous techniques to achieve a sample complexity and runtime of roughly $n^{\\mathrm{poly}(\\cdot)}$. Relying on Kalai et al. (2008) they reduce linear classification problem to a $L_1$ polynomial regression problem. By replacing the target function with a smooth surrogate and further technical ingredients (from the analysis of Boolean halfspaces) they end up with two cases: either the normal vector is dominated by a small number of components (which can be estimated directly) or the CDF can be approximated well enough through the Berry-Esseen theorem (and thus the problem is reduced to the Gaussian case of Chandrasekaran et al. (2024)).", "questions": "Perhaps a somewhat naive question about Def. 4.6. on $(\\alpha,\\lambda)$-strictly sub-exponential distributions: Isn't any distribution defined over $\\\\{-1,1\\\\}^n$ strictly subexponential for some appropriate $(\\alpha,\\lambda)$? As the domain is bounded it should even be subgaussian? In particular for $t\\ge 2\\sqrt n$, or so, the tail probability is simply zero. Or would we get a bad dependence on $n$ through that argument. Please clarify.", "limitations": "yes.", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 2, "significance": 3, "originality": 2, "strengths_and_weaknesses": "This is a well written, interesting, and technical paper continuing an important line of work. The smoothed agnostic case is well motivated and this paper nicely transfers the results of Chandrasekaran et al. (2024) from $R^d$ to the Boolean case.\n\nMoreover, this paper (by going from worst-case to smoothed/average case) allows substantially more general distributions over the hypercube than were previously studied, such as uniform or product distributions.\n\nThe main weakness is the following. **Once addressed I am more than happy to raise my score**. What I am missing is a broader discussion on hardness, tightness, and, in general, necessity/a justification of the various assumptions. For example\n* It is discussed (in the related work and in other places) that agnostically learning halfspaces over the Boolean cube is hard, making various distributional and related assumptions justified. However it is not clear why these hardness results remain valid in this new smoothed setting. Perhaps in the smoothed setting learning with arbitrary distributions is indeed not hard? This is not clear to me from the submission.\n* From PAC theory we get that $O(n/\\epsilon^2)$ samples suffice roughly (VC is $n+1$). Is it clear that a sample complexity/runtime of $O(\\mathrm{poly}(n))$ is hard in this smoothed case? This would make the achieved results here—a sample complexity/runtime of $O(n^{\\mathrm{poly}(\\cdot)})$—more justified. \n* In line 201 it is claimed that arbitrary halfspaces might not be well approximated with a low degree polynomial in the worst-case. While this is true in Chandrasekaran et al. (2024) for $R^d$ it is unclear whether this is still true Boolean cube case.\n\nPlease correct me if I missed something above/or am wrong.", "was_revised": true, "final_justification": "Authors addressed my concerns. This is a strong paper and should be accepted.", "rebuttal": "**Q1:** It is discussed that agnostically learning halfspaces over the Boolean cube is hard, making various distributional and related assumptions justified. However it is not clear why these hardness results remain valid in this new smoothed setting. Perhaps in the smoothed setting learning with arbitrary distributions is indeed not hard?\n\n**A1:** We thank the reviewer for this insightful question. Our goal is indeed to provide a positive result in the smoothed setting, but we do not claim that smoothing automatically eliminates all computational hardness. Rather, we identify natural and sufficient conditions—namely, bit-flip noise and strictly sub-exponential marginals—under which agnostic learning becomes tractable.\n\n1. **Hardness remains as $\\sigma\\to0$:** Our algorithm runs in time $n^{poly(\\sigma_0/\\sigma\\epsilon)}$, where $\\sigma$ is the bit-flip noise rate and $\\sigma_0$ is a distribution-dependent constant. Further, it is easy to deduce from existing agnostic learning results that some exponential dependence on sigma is necessary (for example, $\\sigma\\sim1/poly(n)$ corresponds essentially to no perturbation; at a more fine-grained level, conditional lower bounds of the form $n^{\\tilde{\\Omega}(1/\\epsilon^2)}$ for agnostic learning under the uniform distribution work by reducing to sparse parity with noise on roughly $1/\\epsilon^2$ variables and here taking $\\sigma\\ll1/\\epsilon^2$ will reduce perturbations with noise rate $\\sigma$ to no noise.) Thus, our result interpolates between the intractable agnostic case and a tractable smoothed setting, rather than bypassing known barriers entirely. We will revise the paper to add this observation.\n\n2. **Smoothing may mitigate but not necessarily eliminate worst-case structure:** Bit-flip noise introduces independent perturbations to each coordinate, and this smoothing can help regularize the learning problem. However, it remains unclear whether smoothing alone suffices to guarantee low-degree polynomial approximability for arbitrary base distributions. For example, a base distribution concentrated on a low-dimensional subcube or with heavy tails in certain directions may still retain problematic structure even after bit-flip noise. Our current analysis therefore assumes a strict sub-exponential tail condition to ensure sufficient concentration in all directions. Whether this tail decay assumption is necessary or can be removed remains an interesting open question.\n\n3. **Analogy with smoothed analysis in TCS:** Our framework is consistent with the broader tradition of smoothed analysis [2], where worst-case hardness is overcome under mild random perturbations plus structural conditions. For example, the simplex method remains exponential in the worst case, yet becomes polynomial under Gaussian perturbations. Similarly, our result shows that bit-flip smoothing and tail decay are sufficient (but not excessive) assumptions to enable tractable learning.\n\n**Q2:** From PAC theory we get that $O(n/\\epsilon^2)$ samples suffice roughly (VC is $n+1$). Is it clear that a sample complexity/runtime of $O(\\mathrm{poly}(n))$ is hard in this smoothed case?\n\n**A2:** It is indeed correct that the sample complexity of agnostically learning halfspaces is $O(n/\\epsilon^2)$ due to the VC dimension. However, this is an information-theoretic guarantee — it does not imply the existence of an efficient (i.e., polynomial-time) algorithm that achieves this rate.\n\nEven under the uniform distribution, which satisfies our assumptions, computationally efficient agnostic learning is known to be conditionally hard [1]. Therefore, while a polynomial sample size suffices in principle, achieving polynomial runtime remains a nontrivial challenge without further assumptions.\n\nOur contribution is to identify conditions — namely, bit-flip noise and strictly sub-exponential marginals — under which agnostic learning becomes not only statistically feasible (which it always was), but also computationally efficient. This situates our work within the broader theme of beyond-worst-case analysis, where additional structure is leveraged to overcome known computational barriers.\n\n**Q3:** In line 201 it is claimed that arbitrary halfspaces might not be well approximated with a low degree polynomial in the worst-case. While this is true in Chandrasekaran et al. (2024) for $R^d$ it is unclear whether this is still true Boolean cube case.\n\n**A3:** We thank the reviewer for raising this excellent point. The claim in line 201—that arbitrary halfspaces may not admit good low-degree polynomial approximations in the worst case—does indeed extend to the Boolean cube.\n\nWhile every Boolean function can be exactly represented by a degree-$n$ polynomial, the key issue is whether low-degree polynomials can approximate arbitrary halfspaces under general distributions. For instance, under the uniform distribution, various tools (e.g., hypercontractivity and Fourier concentration) enable low-degree approximations of regular halfspaces [1]. Under product distributions, spectral concentration results have been used to obtain low-degree approximators [3].\n\nHowever, these techniques rely on significant structure—uniformity, independence, or symmetry—which may be absent in general sub-exponential distributions. In such settings, standard polynomial approximation techniques (e.g., based on orthogonal polynomials or moment bounds) break down due to uncontrolled tail behavior or dependence.\n\nThis motivates our use of smoothed analysis: by applying bit-flip noise, we effectively regularize the target function. The resulting smoothed halfspace admits good low-degree approximations after conditioning and re-randomization, even under unstructured sub-exponential marginals. Thus, the statement in line 201 reflects this fundamental limitation of worst-case polynomial approximation on the Boolean cube, which our smoothing strategy is designed to overcome.\n\n**Q4:** Isn’t any distribution over $\\\\{\\pm 1\\\\}^n$ strictly sub-exponential for some approximate $\\lambda$? As the domain is bounded it should even be subgaussian? In particular for $\\lambda=1$, or so, the tail probability is simply zero. Or would we get a bad dependence on $\\lambda$ through that argument?\n\n**A4:** While it is true that distributions over $\\\\{\\pm1\\\\}^n$ have bounded support, and hence projections $\\langle w, x \\rangle$ are bounded in $[-\\\\|w\\\\|_1, \\\\|w\\\\|_1] \\subseteq [-\\sqrt{n}, \\sqrt{n}]$, our assumption in Definition 4.6 is stronger than mere boundedness, and it plays a crucial role in enabling low-degree polynomial approximation. In particular, as the reviewer says we would get bad dependence on $\\lambda$ (and as a result exponential dependence on the dimension) if we just use boundedness.\nIn particular, our proof relies on controlling the low-order moments of $\\langle w, x \\rangle$ under the input distribution to bound the error of Taylor expansions of smooth surrogates. The $(\\lambda, \\alpha)$-strictly sub-exponential condition ensures moment growth is controlled in all directions and in a way that is independent of the ambient dimension $n$. This is critical to obtaining an $O(\\epsilon)$ polynomial approximation error.\n\nTo clarify, the uniform distribution over $\\\\{\\pm1\\\\}^n$ satisfies the $(\\lambda, \\alpha)$-strictly sub-exponential condition with $\\lambda = 2, \\alpha = 1$, using Hoeffding’s inequality. This covers the regime $t = O(\\log(1/\\epsilon))\\ll\\sqrt{n}$, where our approximation guarantees operate. We will clarify this in the final version and include the uniform distribution as a canonical example.\nLastly, our condition subsumes all sub-Gaussian distributions (corresponding to $\\alpha = 1$) and excludes those with only linear tail decay $(\\alpha = 0)$. This includes common marginals such as unbiased or biased product distributions on $\\\\{\\pm1\\\\}^n$, making the assumption both meaningful and practically relevant.\n\n**References:**\n\n[1] Kalai, Adam Tauman, et al. \"Agnostically learning halfspaces.\" SIAM Journal on Computing 37.6 (2008): 1777-1805.\n\n[2] Spielman, Daniel, and Shang-Hua Teng. \"Smoothed analysis of algorithms: Why the simplex algorithm usually takes polynomial time.\" STOC. 2001.\n\n[3] BLAIS, E., O’DONNELL, R. and WIMMER, K. (2010). Polynomial regression under arbitrary product distributions. Machine learning 80 273–294."}, {"review_id": "0lZ0qZdeTL", "reviewer": "Reviewer_Mp29", "summary": "This work studied the problem of agnostic learning halfspaces with Boolean marginal under the smoothed agnostic learning setting. Interestingly, the authors showed that, the target halfspace can be learned (in the sense of $\\sigma$-smoothed agnostic learning) under very general $\\sigma_0$-sub-gaussian marginals on the boolean hypercube using $O(n^{poly(\\sigma_0/\\sigma\\epsilon)})$ samples. Prior work often requires strong assumptions of the marginal distribution, e.g., the marginal is a product distribution etc. The main idea is to replace the target halfspace with its smoothed version, and then approximate the smoothed halfspace using low-degree polynomials. Important techniques includes an analysis of the weights using critical index and applying Berry-Essen to invoke continuous tools.", "questions": "I wonder is there an upper bound on the 0-1 loss of the output hypothesis?", "limitations": "no negative societal limitations.", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 4, "clarity": 4, "significance": 3, "originality": 4, "strengths_and_weaknesses": "1. The paper is written in a very clear and fluent way, with many explanations and intuitions.\n2. The paper is strong and solid in techniques.\n3. It is interesting to see that it is possible to learn halfspaces agnostically under the smoothed analysis setting.", "was_revised": true, "final_justification": "I recommend acceptance.", "rebuttal": "**Q:** I wonder if there is an upper bound on the 0-1 loss of the output hypothesis?\n\n**A:** We thank the reviewer for the encouraging feedback and for raising this thoughtful question. \n\nOur algorithm’s guarantee is with respect to the smoothed agnostic error—i.e., it outputs a hypothesis $h$ such that $P_{(x,y)\\sim D}[h(x)\\neq y]\\leq opt_{\\sigma}+\\epsilon$, where $opt_{\\sigma}$ denotes the minimum achievable error by any halfspace evaluated on $\\sigma$-bit-flip-perturbed examples. This is consistent with the goal of smoothed analysis, which seeks to evaluate performance on slightly perturbed instances to mitigate worst-case pathologies.\n\nAs for the true 0–1 loss of the output hypothesis on unperturbed examples, we do not provide an upper bound in terms of the standard agnostic error $opt_0$, since doing so would contradict known hardness results. In particular, prior work [1] shows that agnostically learning halfspaces over the Boolean cube is computationally hard, even under simple distributions like the uniform distribution. Therefore, without further assumptions, we cannot hope to relate the true 0–1 loss of our hypothesis to the best achievable 0–1 loss in the original distribution.\n\nThat said, in practice, the output hypothesis may still achieve low 0–1 error under benign distributions—especially if the optimal halfspace is stable under small perturbations. Our result ensures that, under bit-flip noise and sub-exponential marginals, the learner competes with the smoothed optimum efficiently.\n\nWe hope this clarifies the scope and motivation of our guarantees.\n\n**References:**\n\n[1] Kalai, Adam Tauman, et al. \"Agnostically learning halfspaces.\" SIAM Journal on Computing 37.6 (2008): 1777-1805."}, {"review_id": "7Ks5NFaHlS", "reviewer": "Reviewer_zBEU", "summary": "This paper considers the setting of smoothed agnostic learning halfspace on a hypercube.\nThis setting differs from the previous work (CKKM24) in the sense that the previous work considers learning on \\R^d, while this one considers learning on the hypercube.\nNamely, the setting considered here is the following:\nGiven a sample access to a joint distribution (x,y) over {\\pm 1}^n\\times {\\pm 1}, the algorithm need to output a hypothesis with error small\ncompared to the smoothed agnostic error,\ndefined in Definition 1.2.\n\nGiven the setting, further assume that the distribution is $(\\alpha,\\lambda)$-subexponential (Definition 4.6), the algorithms run in time \n$n^{poly({(\\lambda/(\\sigma\\epsilon))}^{{(1+1/\\alpha)}^3}}$ and learns to error opt+\\eps where opt is the smoothed optimal error above.\nThe high-level approach here follows the L1 regression algorithm framework from KKMS08, which boils down to showing that the concept function can be approximated by a polynomial of corresponding degree to small L1 norm (Lemma 4.7).\nThe notion of approximation is defined in Lemma 4.2. \nI'm then having trouble following the authors' argument.\nIn particular, in lines 214-223:\n216 states that the approximation polynomial (as a function of x) needs to be the same for every z (which is consistent with Lemma 4.7 and 4.2).\nThen 221 states that the polynomial (now as a function of z) needs to approximate the function f_x(z).\nI assume that this means now this polynomial needs to be fixed for every x to approximate a function on z, which is inconsistent with the above and it wan't clear to me that one would imply the other.", "questions": "Can the authors clarify my question about 214-223 (as I mentioned above)?\nI'm happy to revise the review if I misunderstood it.", "limitations": "Yes.", "rating": 5, "confidence": 1, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 1, "significance": 2, "originality": 2, "strengths_and_weaknesses": "Weaknesses:\nSome parts of the presentation are confusing, especially lines 214-223, which I mentioned earlier.", "was_revised": true, "final_justification": "The authors have clarified my confusions.", "rebuttal": "**Q:** Given the setting, I’m having trouble following the authors' argument between lines 214–223. Line 216 suggests that the approximation polynomial (as a function of $x$) needs to be the same for every $z$, which matches Lemmas 4.2 and 4.7. But line 221 seems to suggest constructing a polynomial in $z$ to approximate $f_x(z)$, which would require fixing $x$ instead. This appears inconsistent, and it's unclear how one implies the other.\n\n**A:** The confusion arises from a misinterpretation of the roles of $x$, and $z$ in our construction. \n\nTo clarify, our goal, as stated in Theorem 4.2, is to construct a family of low-degree polynomials $\\{p_z(x)\\}$—each of which is a polynomial in $x$ for a fixed noise vector $z$. There is no requirement that a single polynomial in $x$ must work for all $z$, nor that $p_z(x)$ be a polynomial in $z$ when $x$ is fixed. If $p_z(x)$ is a polynomial in $x$ for each $z$, then the sum of such polynomials over $z$ would also be a polynomial.\n\nTo analyze and construct such polynomials, we temporarily fix $x$ and define $f_x(z) := f(x \\odot z)$, which allows us to study the smoothed function via the operator $T_{1-\\rho} f_x(z)$ acting on $z$. This step is purely analytical: it enables the use of tools like the Berry–Esseen theorem, which apply to functions over random noise vectors. This perspective—treating $f_x(z)$ as a function of $z$—helps us approximate the expected value of $f(x \\odot z)$, which in turn determines the value of the polynomial $p_z(x)$.\n\nTo be clear: we do not construct a polynomial in $z$. Instead, the role of $z$ is to index the family of polynomials $\\{p_z(x)\\}$; for each fixed $z$, we define a corresponding polynomial $p_z(x)$ in $x$, and this is what is ultimately used in the L1 regression algorithm. The approximation argument involving $f_x(z)$ and $T_{1-\\rho}$ is a technical tool that helps derive these $x$-polynomials.\n\nThis shift in viewpoint is subtle but is important. We will revise this part to more clearly underscore this shift and explain the purpose of introducing $f_x(z)$. \n\nThank you again for highlighting this, and we welcome further questions."}, {"review_id": "1IJ4I6wHZh", "reviewer": "Reviewer_PoAm", "summary": "The work studies and extends the smoothed learning setting introduced in [Chandrasekaran et al 2024].\nThis setting is a relaxation of the agnostic learning model, aiming to sidestep computational hardness results via relaxing the learning objective as follows. In the agnostic learning model, the learning algorithm is required to achieve error $opt+\\varepsilon$, where $opt$ is the smallest classification error in the hypothesis class.\n\nIn the smoothed learning model of [Chandrasekaran et al 2024] the classifier is only required to compete with hypotheses that are robust to a small amount of Gaussian noise in the input. Formally, the prediction error should be $opt_{smooth}+\\varepsilon$, and $opt_{smooth}$ is the smallest **smoothed loss** in the hypothesis class. The smoothed loss of a hypothesis $h$  is defined in [Chandrasekaran et al 2024] as the probability that $h(x+\\sigma z)\\neq y$ where $(x,y)$ comes from the data distribution and $z$ is the Gaussian noise. \n\nConceptually, if the smoothed loss of a hypothesis is close to its prediction error, then the hypothesis is robust to noise, and vice versa.  \nFor many hardness results, the optimal classifiers are fragile to small amounts of Gaussian noise, and this new notion of optimality allows [Chandrasekaran et al 2024] to sidestep such hardness results.   \n\nThe original setting in [Chandrasekaran et al 2024] focuses on continuous domain $\\mathbb{R}^d$, whereas this work focuses on distributions over the $n$-dimensional bit strings $\\\\{\\pm 1\\\\}^n$. The Gaussian perturbations studied in [Chandrasekaran et al 2024] are not appropriate for $\\\\{\\pm 1\\\\}^n$, because such perturbation will map points in $\\\\{\\pm 1\\\\}^n$ to points outside of $\\\\{\\pm 1\\\\}^n$. To remedy this, this paper considers smoothing perturbations that flip each of the bits with probability $\\sigma$. This type of perturbation has been widely studied in the context of theory of Boolean functions.\n\nThis work gives an algorithm that:\n- Makes an assumption that the training marginal is $\\sigma_0$-sub-Gaussian. This is a very mild assumption on the tail behavior of the distribution. The work also considers the more general family of $(\\alpha, \\lambda)$-strictly sub-exponential distributions. \n- Considers the hypothesis class of linear classifiers.\n- Gives a classifier with prediction error of $opt_{smooth}+\\varepsilon$, where $opt_{smooth}$ is defined with respect to Boolean bit flips described above.\n- Has run-time is $n^{poly(\\frac{\\sigma_0}{\\sigma \\epsilon})}$\n\nThe algorithm is based on the low-degree method of [Kalai et al '08]. This algorithm is analyzed by showing that halfspaces are well-approximated by polynomials of degree $poly(\\frac{\\sigma_0}{\\sigma \\epsilon})$. The analysis\n involves combining the analysis of [Chandrasekaran et al 2024] with techniques from Critical Index theory. Conceptually, if no single variable has a large weight for the linear classifier, the inner product of the added noise with the normal vector is distributed similar to a Gaussian (via a central limit theorem), and thus methods of [Chandrasekaran et al 2024] can be used. Otherwise, the paper shows that one can use methods similar to [Diakonikolas et al 2010] to separate the high-weight variables and handle these high-weight variables separately.", "questions": "- The run-time is $n^{poly(\\frac{\\sigma_0}{\\sigma \\epsilon})}$. Is the polynomial factor hidden by $poly$ optimal in some sense?\n- One way to think about the technical approach is that it combines the ideas in [Chandrasekaran et al 2024] with the overall approach in [Diakonikolas et al 2010]. To better understand the originality of your approach, could you elaborate on the biggest specific points of difference between your approach and [Diakonikolas et al 2010]?\n- Does your work imply distribution-specific agnostic learning algorithms with respect to smoothed distributions? (i.e. distributions formed by starting with an arbitrary sub-Gaussian distribution and adding independent noise). If this is the case, I think this should be highlighted.", "limitations": "I think that the paper would benefit from a section titled \"Limitations\" in which the main limitations are summarized. This would make the limitations clearer to a wider audience.", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 4, "clarity": 4, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths\n- Smoothed agnostic learning has recently attracted a lot of attention as a promising framework for sidestepping hardness results in theory of machine learning.\n- This work extends some of the results in [Chandrasekaran et al 2024] into a natural setting in the Boolean cube, and has the potential to stimulate future extensions for general product distributions. \n\nWeaknesses\n- Compared to [Chandrasekaran et al 2024], the scope of this work is more narrow, because this work only considers the class of halfspaces. In contrast, [Chandrasekaran et al 2024] handle a much more general class of functions that includes functions of low Gaussian surface area embedded into a low-dimensional subspace. For example, the class of functions studied in [Chandrasekaran et al 2024] includes intersections of halfspaces, but this work does not handle intersections of halfspaces.", "was_revised": true, "final_justification": "Based on the detailed comparison with [Diakonikolas et al] contained in the rebuttal, I think it is appropriate to raise my score to 5 (Accept), based on technical novelty.", "rebuttal": "We thank the reviewer for the constructive feedback and thoughtful questions. Below, we address each point in turn.\n\n**Q1:** The runtime is $n^{poly(\\sigma_0/\\sigma\\epsilon)}$. Is the polynomial factor hidden by poly optimal in some sense?\n\n**A1:** We thank the reviewer for the thoughtful question. We interpret the question as asking whether the degree of the polynomial hidden in the runtime expression $n^{poly(\\sigma_0/\\sigma\\epsilon)}$ is optimal under our assumptions—or whether it could be improved.\n\nThis dependence arises from the degree of the polynomial needed to approximate the smoothed halfspace. Specifically, Lemma 4.7 shows that to achieve \\epsilon-approximation under a $(\\alpha,\\lambda)$-strictly sub-exponential distribution, it suffices to use a polynomial of degree $d=(\\frac{C\\lambda\\log(1/\\epsilon)}{\\epsilon\\sigma^{1/2}})^{\\Theta((1+\\frac{1}{\\alpha})^{3})}$. In the special case of $\\sigma_0$-sub-gaussian distributions, this simplifies to $d=(\\frac{C\\sigma_0\\log(1/\\epsilon)}{\\epsilon\\sigma^{1/2}})^{\\Theta(1)}$. This degree then drives the runtime via a reduction to L1-regression, yielding the stated complexity.\n\nWe do not claim that this exponent is tight in all regimes. In fact, the analysis in Theorem 4.8 is somewhat conservative: tighter control over moments or distribution-specific structure could reduce the required degree, possibly improving the exponent of degree $d$ with a smaller constant factor. However, we believe the polynomial dependencies on $\\sigma_0, 1/\\sigma, 1/\\epsilon$ in the exponent are still necessary in our analysis. In particular, dependence on $1/\\sigma$ is unavoidable: as $\\sigma\\to 0$, our complexity approaches that of standard agnostic learning, which is known to be computationally hard even under the uniform distribution [1]. Thus, the complexity lower bound aligns with known hardness as $\\sigma\\to 0$, and our result can be seen as a smooth transition from hardness to tractability.\n\nIf the reviewer had a different notion of optimality in mind, we’d be happy to clarify further.\n\n**Q2:** One way to think about the technical approach is that it combines the ideas in [2] with the overall approach in [3]. To better understand the originality of your approach, could you elaborate on the biggest specific points of difference between your approach and [3]?\n\n**A2:** We appreciate the reviewer’s insightful comparison between our approach and that of [3]. While both works share high-level similarities—such as the use of low-degree polynomial approximations and critical index-based decomposition—their goals, techniques, and assumptions differ substantially.\n\n**Purpose and setting:** The goal of [3] is to construct pseudorandom generators that fool halfspaces under the uniform distribution using bounded independence. Their focus is on indistinguishability and derandomization. In contrast, our focus is algorithmic: we aim to learn halfspaces efficiently in the smoothed agnostic setting over the Boolean cube, under strictly sub-exponential marginals. Our objective is to design a learner that competes with the smoothed optimum $opt_{\\sigma}$, rather than showing indistinguishability under limited independence.\n\n**Differences in use of polynomials:** Both works use low-degree polynomial approximations, and are similar in this regard. However, the way polynomials are constructed is fundamentally different.  In [3], a single polynomial is constructed in a somewhat direct-way by carefully reducing the question to a univariate approximation problem. In our case, we essentially construct a distribution over polynomials (we get a different polynomial $p_z(x)$ for each $z$, and the final approximating polynomial is essentially of the form $E_z[p_z(x)]$). \n\nFurther, although both approaches use critical index decomposition to handle irregular weight vectors, the construction of polynomial approximators is different in both goal and implementation.\n\nIn the small critical index case, both our work and [3] condition on the “head” variables and analyze the regular “tail.” In [3], after fixing the head, the tail defines an $\\epsilon$-regular halfspace under the uniform distribution. The authors show that such functions can be fooled by bounded-independence distributions, using sandwiching polynomials that tightly bound the target function from above and below. These sandwiching polynomials are constructed by reduction to a univariate problem. \n\nIn contrast, after conditioning on the head, we analyze the function $f(x \\odot z)$, and approximate its smoothed version $T_{1-\\rho} f_x(z)$. The tail remains a regular Boolean halfspace, which we approximate by a Gaussian via the Berry–Esseen theorem. This enables the use of the density ratio (probability tilting) technique from [2] to approximate the expected value of the smoothed function with a low-degree polynomial. Importantly, because the head is small and fixed in this step, the final approximator remains low-degree in the Boolean domain, making it suitable for L1 regression. Note that after conditioning on the head, our approach differs from [3].\n\nFor the large critical index case, both works use the idea that the head dominates the decision. In [3], this is used to argue that the head variables give sufficient bias to fool the function even under pairwise independence. In our setting, the dominance of the head allows us to exactly represent the function as a low-degree Boolean polynomial, which can then be directly used in regression.\n\n**Distributional assumptions:** [3] assumes the uniform distribution over $\\\\{\\pm1\\\\}^n$. In contrast, our results hold under strictly sub-exponential marginals, which are significantly more general. This generality introduces new technical challenges—for instance, ensuring that regularity and Gaussian approximation continue to hold under dependent noise. We address these using smoothing, critical index decomposition, and novel tools such as discrete noise operators and rerandomization techniques.\n\nWhile we are inspired by the structural decomposition used in [3], our work addresses a fundamentally different problem. Our goals (agnostic learning vs. pseudorandomness), approximation objectives (expected L1 error vs. pointwise bounds), and assumptions (general sub-exponential marginals vs. uniform distribution) all differ substantially. Moreover, our analysis introduces new techniques tailored to the smoothed Boolean setting. We believe these differences position our work as a distinct contribution to the study of efficient learning under noise and distributional uncertainty. \n\n**Q3:** Does your work imply distribution-specific agnostic learning algorithms with respect to smoothed distributions? (i.e. distributions formed by starting with an arbitrary sub-Gaussian distribution and adding independent noise). If this is the case, I think this should be highlighted.\n\n**A3:** We appreciate the reviewer’s suggestion and the opportunity to clarify the connection to agnostic learning under smoothed distributions. Indeed, it is possible that smoothed-agnostic model is strictly more general than learning under smoothed distributions as happens in the Gaussian case (e.g., as in [2]). However, this could be a bit trickier to do in the Boolean case and we leave this as an interesting extension for future work. We will revise the paper to highlight this direction. \n\n**Q4:** I think that the paper would benefit from a section titled \"Limitations\" in which the main limitations are summarized. This would make the limitations clearer to a wider audience.\n\n**A4:** We thank the reviewer for the constructive suggestion regarding a clearer discussion of limitations. We agree that summarizing the main limitations in a dedicated section will improve accessibility for a broader audience. In the camera-ready version, we will add a new “Limitations” section immediately preceding the Conclusion and Future Work. This section will explicitly highlight key constraints of our approach—including the restriction to halfspaces, the dependence of runtime on $\\sigma$, the necessity of tail decay assumptions, and the current focus on Boolean inputs with bit-flip noise. We will also revise the organization of the final sections accordingly for better clarity.\n\n**References:**\n\n[1] Kalai, Adam Tauman, et al. \"Agnostically learning halfspaces.\" SIAM Journal on Computing 37.6 (2008): 1777-1805.\n\n[2] Chandrasekaran, Gautam, et al. \"Smoothed analysis for learning concepts with low intrinsic dimension.\" COLT 2024.\n\n[3] Diakonikolas, Ilias, et al. \"Bounded independence fools halfspaces.\" SIAM Journal on Computing 39.8 (2010): 3441-3462.\n\n[4] Kane, Daniel, Adam Klivans, and Raghu Meka. \"Learning halfspaces under log-concave densities: Polynomial approximations and moment matching.\" COLT 2013."}]

Author rebuttal:

Meta-review: This paper studies the problem of agnostically learning halfspaces on the hypercube under a natural class of distributions in a smoothed setting. The authors provide a dimension-efficient algorithm for this learning task. The reviewers agreed that this is a technically non-trivial and interesting contribution that meets the bar for the conference.
Decision: Accept (poster)