Robust learning of halfspaces under log-concave marginals
Authors: Jane Lange
Arsen Vasilyan
Venue: NeurIPS 2025 spotlight ()
Keywords: adversarial robustness
linear classifiers
agnostic learning
Primary area: theory

Abstract: We say that a classifier is $\text{\emph{adversarially robust}}$ to perturbations of norm $r$ if,
with high probability over a point $x$ drawn from the input distribution, there is no point within distance $\le r$ from $x$ that is classified differently. 
The $\text{\emph{boundary volume}}$ is the probability that a point falls within distance $r$ of a point with a different label.
This work studies the task of learning a hypothesis with small boundary volume, where the input is distributed as a subgaussian isotropic log-concave distribution over $\mathbb{R}^d$.

Linear threshold functions are adversarially robust; they have boundary volume proportional to $r$.
Such concept classes are efficiently learnable by polynomial
regression, which produces a polynomial threshold function (PTF), but PTFs in general may have boundary volume $\Omega(1)$, even for $r \ll 1$.

We give an algorithm that agnostically learns linear threshold functions and returns a classfier with boundary volume $O(r+\varepsilon)$ at
radius of perturbation $r$.
The time and sample complexity of $d^{\tilde{O}(1/\varepsilon^2)}$ matches the 
complexity of polynomial regression.

Our algorithm augments the classic approach of polynomial regression with three additional steps:\
$\quad$ a) performing the $\ell_1$-error regression under $\ell_1$ noise sensitivity constraints,\
$\quad$ b) a structured partitioning and rounding step that returns a Boolean classifier with error $\mathrm{opt} + O(\varepsilon)$ and noise sensitivity $O(r+\varepsilon)$ simultaneously, and \
$\quad c)$ a local corrector that ``smooths'' a function with low noise sensitivity into a function that is adversarially robust.

Robust learning of halfspaces under log-concave marginals
Jane Lange" MIT j jlange@mit. edu
Arsen Vasilyan"
UT Austin Arsen/asilyaan@gaill.c com
Abstract
We say that classifier adversarially robust to perturbations of norm if, with high probability over point x drawn from the input distribution, there is no point within distance I from that is classified differently. The boundary volume the probability that a point falls within distance of point with a different label. This work studies the task of computationally efficient learning of hypotheses with small boundary volume, where the input is distributed subgaussian isotropic log-concave distribution over Rd..
Linear threshold functions are adversarially robust; they have boundary volume proportional r. Such concept classes efficiently learnable by polynomial regression, which produces polynomial threshold function (PTF), but PTFs in general may have boundary volume 2(1), even for r << 1.
We give an algorithm that agnostically learns linear threshold functions and returns a classifier with boundary volume (fr+s) at radius of perturbation The time and sample complexity of d0(1/=²) matches the complexity of polynomial regression. Our algorithm augments the classic approach of polynomial regression with three additional steps:
performing the & ferrrr regression under noise sensitivity constraints, b) structured partitioning and rounding step that returns Boolean classifier with error opt + O(=) and noise sensitivity O(r + z) simultaneously. and c) a local corrector that "smooths" a function with low noise sensitivity into a function that is adversarially robust.
1 Introduction
predictor robust to adversarial examples if for most possible inputs, a small perturbation will not cause the input to be misclassified. We define the boundary volume the probability, the input distribution, that a point is close to the boundary:
(f) Pr 3e ||=|| S and f(x) + f(x + =)].
z~D
The sum the boundary volume and the classification error a natural upper bound on the standard notion of robust risk:
RobRisk
Pr (x.n)~>
[2 ||=||| < and # f(x + +
In this work, we discuss computationally efficient learning of classifiers with optimal classification error and boundary volume, thus minimizing the robust risk.
Alphabetical order.
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

There is large body of research on adversarial robustness in machine learning, the focus of which to assess the robustness of classifiers commonly deployed in practice see [BCM* +1 13, GSS14, SZS+ 14], as well as [KM18] for an overview of the topic. It is well known that deep networks trained on classic benchmark data sets, such as ImageNet, can he "tricked" into misclassifying test input by making perturbation so small that it cannot be detected by humans, and that training robust models is a challenge in practice.
In this work we consider linear threshold functions (halfspaces), one of the most basic and well- known concept classes. As robustness benchmark, we consider the robustness of a proper learning algorithm one that outputs a hypothesis that is a halfsppace. For a halfspace, when the input distributed according the d-dimensional standard Gaussian - or more generally, a subgaussian isotropic log- log-concave distribution the probability that an input falls within Euclidean distance of the classification boundary is (r)); thus 1 (rr) fraction of inputs are robust to adversarial perturbations of norm A proper agnostic learner would output hypothesis with the following guarantees:
Agnostic approximation: Pria.w * h(x)) opt + E, where opt is the classification error of the best halfspace, and
Adversarial robustness:
Boundary (h) < ((r).
However, the state of the art for agnostically learning halfspaces is an improper algorithm an algorithm that does not output a halfspace, but instead outputs a polynomial threshold function (PTF). Polynomial regression with randomized rounding learns halfspaces over A( Ia) with time and sample complexity d0(1/=") and satisfies the accuracy guarantee [DGJ+ 09, KKMS08). In fact, the efficiency of polynomial regression is due to the inherent robustness of halfspaces their small surface area! However, there exist degree-1/s" PTFs with boundary volume (2(1) even at small radius of perturbation," and this algorithm makes no guarantee that its output robust.
No proper agnostic learning algorithm with 20(d) running time for general subgaussian isotropic log-concave distributions known, and for the Gaussian distribution the state of the art for proper
learning is (01/==)) [DKK+21], The complexity of proper learning in these settings is still an open question. We cireumvent the possible difficulty of proper learning by giving an improper algorithm that still satisfies both the accuracy and robustness properties. Our algorithm has time and sample complexity d(()/e²), matching the run-time of the best (improper and non-robust) agnostic learning algorithm [DGJ+09] Up to polylogarithmic factors in the exponent, this also matches the statistical query lower bound for agnostically learning halfspaces [DKPZ21].
1.1 Main result
Our main result is an improper agnostic learner (Algorithm 1) for halfspaces that outputs an adversar- ially robust hypothesis.
Theorem 1.1 (Adversarially robust learning of halfspaces, informal version of Theorem 3.1). Let D be a distribution over IR x {-1,1} such that the Re-marginal is subgaussian, isotropic, and nog-conavve. There is an algorithm that takes a robustness radius r, an accuracy parameter and a sample of size (oll/²") from DD With high probability, it outputs a hypothesis h: Rdd - (-1,1)
with the following guarantees:
Agnostic approximation: (((()) # vl opt + O(E), where opt is the classifica-
tion error of the best halfspace.
Adversarial robustness: Boundary,, (h) 0(r).
1.2 Technical overview and intermediate results
Our algorithm and its analysis have three main components, which may be of independent interest. Two of the components solve a relaxation of the robust learning problem, and the third transforms the almost-robust hypothesis into a robust one. The relaxed learner produces a hypothesis with small
Consider the PTF sign 1/622 æ:). which has boundary volume 2(()) over AC La) at any radius 2 s?.

---

noise sensitivity (a notion of boundary volume with random perturbations instead of adversarial perturbations) and small isolation probability (the probability that the local noise sensitivity around point is very high). To formally define these two quantities, we need the following notion:
Definition (Local noise sensitivity). We define the local noise sensitivity f (2) at noise scale y as
(1)(z) =
E (1)(()) 2-.( ( - f(x + nz)1]-
We remark that when J is Boolean-valued, this is equivalentyy
())()) = Pr [f(x) + f f(x nz)]
Pr 20
We now define the noise sensitivity and the isolation probability: Definition (Distributional noise sensitivity). The noise sensitivity of function f at noise scale on distribution DD is defined as
E NS),,())=
=nD 2 (+
(1)
We remark that when D = (0, Ta), our definition of distributional noise sensitivity differs from the standard definition of Gaussian noise sensitivity.
Definition (Isolation probability). We call a point isolated if its local noise sensitivity is over threshold. The isolation probability of a function f relative to threshold is
is.D.,(J.)) = Pr Pr (n)())))))))))))))))))))))())) 4.
æ~D
Intuitively, function can have low distributional noise sensitivity and still not be adversarially robust, if the classification boundary lies near many isolated points scattered throughout the domain. For this reason, after learning hypothesis with low noise sensitivity, apply the local correction algorithm which we describe below, which eliminates regions of high local noise sensitivity (isolated points).
1.2.1 Local correction of adversarial robustness (Algorithm 3)
The part of our algorithm that transforms an almost-robust hypothesis into a robust one is a local corrector for adversarial robustness. Local correctors are part of the family of local computation algorithums, or LCAs [RTVX11, ARVX12]: fast randomized algorithms that compute parts of large object without constructing the object in its entirety. Local correctors, also known as local property reconstructors [ACCL08], are LCAs that evaluate queries to a nearby object that satisfies desired property; in our case that object an adversarially robust hypothesis. Our algorithm uses local correction in the fashion of [LRV22]: to "append" a local corrector with a fixed random seed to non-robust hypothesis in order to globally correct the hypothesis.
We analyze very simple LCA that makes queries to a function and outputs queries to a nearby function with reduced boundary volume. This algorithm estimates the local noise sensitivity at æ, and changes the label of x if the local noise sensitivity is too high. This is, in essence, the smoothing procedure discussed in [LAG + 19, LCWC. CRK19]. We give guarantees on the boundary volume and the eтror introduced by the smoothing procedure in terms of the relaxed robustness properties of the input function (the noise sensitivity and isolation probability).
Lemma 1.2 (Local corrector for adversarial robustness, informal version of Theorem C.1). Ler a. S.r E (0. 1). Let f R + 11 be degree-k polynomial threshold function with noise sensitivity < and isolation probability & There is an efficient randomized algorithm ROBUSTNESSL.CA that makes black-box queries to and answers black-box queries to function : Rdd + 1-1,1} that satisfies the following with high probability:
Adversarial robustness: Boundary 50(a +)
Small distance: Pra-p(g(2) # [(x)) < 0(3 +).
We use this algorithm a "deterministic" fashion, where calls the local corrector share the same random seed, which is good with high probability. When the random seed is good, the guarantees

---

hold for all x E R This allows us to append the local corrector and its fixed seed to some degree-k PTF, creating a deterministic robust hypothesis that can be evaluated in (4)) time.
From the guarantees of the local corrector and the desired guarantees of the overall algorithm, determine that we must feed the local corrector a PTF error opt + O(e), noise sensitivity O(r), and isolation probability O
1.2.2 Polynomial regression under noise sensitivity constraints (Algorithm 2)
Our first step in finding such a PTF is learn a polynomial with low error, noise sensitivity, and isolation probability in the & disitnaee regime.
Theorem 1.3 (Learning a polynomial, informal version of Theorem 3.3). There is an algorithm with time and sample complexity d0(1/²) that takes samples from the distribution D and, with high probability, returns degree- (1//=) polynomial p with the following properties:
Accuracy: err(p) - opt O(e).
Low noise sensitivity: NS(p) - Or + E), and
Low isolation probability: iso(p) - (s))
We achieve this with convex programming. The & noise sensitivity is a convex constraint, and use a convex upper bound on the l analogue of the isolation probability. We minimize error over the set of degree-O(1/e")) polynomials under these constraints. To show that a feasible polynomial of eπror opt + O(z) exists, we show that the halfspace-approxiie approximating polynomial given in [DGJ 09] satisfies the constraints under any subgaussian isotropic log-concave distribution.
1.2.3 Randomized partitioning and rounding (Algorithm 5, Algorithm 4)
With p in hand, we must then round p to some polynomial threshold function sign(p- t) that satisfies the error, noise sensitivity, and isolation probability constraints. Simply rounding at a uniformly random threshold /. ~ [-1,1], 1], as in [KKMS08], does result in error opt + O(e), noise sensitivity O(r), and isolation probability (ee) in expectation, but doesn't ' guarantee that the conditions ever hold simultaneously for the same t. Thus, running the local corrector on just one rounded function would not guarantee a hypothesis with the right properties. In this step, we find a "deterministic mixture" of rounded functions that simultancously satisfies the three conditions: partition of the domain into parts, where each part is rounded at different threshold. The corrector is run on each part separately.
first attempt at finding such a partition would be allow have O(1/E²) parts. Observe that the eиror, noise sensitivity, and isolation probability concentrate with deviation E when averaging over ((1/=²) random thresholds. Thus. an equal- weighttd mixture of O(1/=²) independent random roundings would satisfy all of the guarantees simultaneously with high probability. But suppose we partitioned the domain into 1/E² sets of equal mass we can't guarantee robustness for any point near the boundaries of these sets, and the total volume of these boundaries scales inversely with which is undesirable. To minimize the increase in boundary volume due to partitioning, it necessary to find partition of constant size.
We show that there exists a mixture of four rounded functions satisfying all the constraints simultane- ously by applying Carathéodory's 's theorem ([Car07]), and we find the mixture by linear programming.
To understand how to turn the mixture into a partition, consider the example of handling just the error when y is a deterministic function of x. The error of the mixture is
Σ EE[4]
w, err(sign(p - tz)) S opt + O(e),
'We remark that in setting where each call to the corrector is allowed to fail independently with prohability the query complexity can be reduced from d04) (o(k).oog) log(1/))/e" to (log(1/6))e)) (1")) and the assumption that If is degree-k PTF can be dropped. This is not applicable in our setting but might be desired in non-learning application of local correction for robustness.

---

where w; is the mixing weight of the hth PTF. For each in the mixture. there is set of volume err esiisig t,)) consisting of the points misclassified by sign(p - tz). We want to partition the domain such that a wy-fraction of this falls into the 5th part, that
Σ [z is in the 7t part and & sign(p(æ) - 4.) = Σ my erresiigg - 14)) [E[4]
We cite theorem of [DHV06], which says, essentially, that projecting on random unit vector causes the set to be very close to cormally-disriiutte with high probability. Thus, our partition is according to the inner product with a random unit vector u, and the parts are intervals J1,..., Jr of Gaussian mass wi....: respectively. With high probability, the sets of misclassified points and the sets for which robustness is guaranteed by the corrector are all partitioned with the correct weights.
Theorem 1.4 (Randomized partitioning, informal version of Theorem 3.4). Let p be a polynomial scttisfying the guarantees of Theorem 1.3. There an algorithm that outputs a unit vector u, rounding thresholds t ,,....,ty ir and partition of the real line into intervals JI,... J4 such that the hypothesis
h(x) Σ ROBUSTNESSLCA(signuGGs - (.)) 11 u) E Jal
has the following properties with high probability:
Accuracy: err(h) S opt + O(E),
. Robustness: Boundaryp, (h) S O(r + +
The time complexity is ((16))
1.3 Verifiable robustness
The work of [GKVZ22] discusses the planting of "backdoors" in learned classifiers structured violations of the robustness condition - and the impossibility of efficiently distinguishing a robust model from a backdoored one in the most general case. The takeaway is that when training is performed by an untrusted service, it is not generally possible to verify that hypothesis is robust, even if description of the hypothesis available. However, our learning algorithm produces hypothesis with a specific structure that can be checked, and the reduced expressivity of this structure allows robustness to be verifiable. Under complexity assumptions, the robustness of our algorithm'ss output can be verified in the following way:
Corollary 1.5 (Deterministic verifiability, informal version of Corollary D.1). P = BPP. then there is learning algorithm B that, given access to labeled samples from subgaussian isotropic log- con-conavve distribution, runs in time (011)22) and produces a hypothesis h with the following guarantees*:
Agnostic approximation: h satisfies Pr(r.a)-((((r) (h(x) * vl S opt + O(E), where opt the misclassification error of the best halfspace.
Verifiable robustness: There is an efficient deterministic verifier that takes as input hypothesis g and a point x E Rd., and always rejects if
3z ||=1|2 S r and g(x) + g(x++))
If is the output of B, then the verifier accepts with probability at least 1 - O(r + E) over x drawn from D.
As a result, training can be done entirely by an untrusted service who claims to be using our learning algorithm, but may not be. The verifier checks whether the hypothesis matches the format our learning algorithm produces, rejects if it doesn't 't match, and performs a robustness test that is sound if it does match. The user must trust that the error of the hypothesis really is opt O(e), but does not have to place any trust in the service to guarantee robustness - there is a deterministic algorithm that
Agnosttc approximation holds with high probability, whereas verifiable robustness always holds (determin-
istically).
5

---

the user can perform to verify that most points are not near the boundary. Furthermore, in setting where the user performs some of the construction of the hypothesis (but need not access any training data), verifiable robustness can be made unconditional, but the soundness of the verifier can fail with small probability over the randomness of the hypothesis construction, See Appendix D for further discussion.
1.4 Related work.
Adversarially robust learning. Several recent papers study adversarially robust learning of various concept classes in the distribution-free PAC setting. These papers also generalize the set of adversarial perturbations beyond the &g ball. Some consider lp perturbations and some consider fully arbitrary
sets.
The works of [CBM18, MHS19] show that there is essentially no statistical separation between robust learning and standard learning; thus any gap in the hardness of these tasks must be computational. The works of [BLPRI9, DNV19, 19, ADV 19] exhibit concept classes and perturbation sets such that, under standard hardness assumptions, robust learning is computationally harder than standard learning. The work of [SHS* 18] exhibits some concept classes and perturbation sets such that a high robust risk inevitable.
The work of [MGDS20] gives algorithm for robustly learning halfspaces in the realizable setting where the data is assumed to be labeled by a halfspace with random classification noise. The works of [DKM20, DKM19] give algorithms for robust, proper, agnostic learning of halfspaces; however, the data distributions are assumed to be supported on the unit ball. When scaled up to match the parameters of our setting- - distributions concentrated on a radius-v ball - the running times of these algorithms have an exponential dependence on vd.
The work of [ADV19] also studies robust learning in the distribution free setting. They give an algorithm for learning halfspaces and degree-2 PTFs with robustness under Eg boundded perturbations.
In the distributton specific setting, [GKKW21] gives an algorithm for learning monotone conjunctions with robustness to perturbations of (log n) Hamming distance, under Lipschitz distributions on the Hamming cube. As mentioned earlier, the proper agnostic learner of [DKK +1] is robust learner for halfspaces under the Gaussian distribution.
Other work on learning halfspaces. See Section 1 for comparison of our work with [DGJ+09, KKMS08J. Under general log-concave distributions, [ABL17] gives an algorithm for semiagnostic proper learning of trigin-centers halfspaces under log- log-concave distributions, i.c. the algorithm gives a halfspace with error (optt) + E, where opt is the error of best halfspacc. In contrast to this, our work focuses on obtaining the optimal opt + eтror. [Dan15] gives poly-time method of achieving error (1 + a a)opt + under for any constant a, but via an improper learning algorithm that uses polynomial regression". The work of [DKK+21], in addition to the do(a/=") algorithm for achieving error opt + for halfspaces under the Gaussian distribution (discussed in Section 1), gives poly-time proper learning algorithm for origin-centern cegtered halfspaces that achieves error (1 + a aoppt + (similar [5an15]). All algorithms in [DKK+211 are highly specific to Gaussian distributions and do not extend to, for example, to the uniform distribution over [-1, 1, 1]d and other sub-Gaussian log-coneave distributions.
2 Preliminaries
When dealing with a distribution D over Rd x (+1), we will sometimes overload the notation to use the symbol D to refer to the mar-inaaa of D. Analogously, when dealing with a collection S of pairs (z44 y:)} } in Rd x {+1} we will sometimes write Pra-s[.... - to refer to Pr(x.))=s when the values are not referenced.
'The algorithm of [5an15] also applies only to the Gaussian distribution, and not to general sub- Gaussian log log-concave distributions.

---

2.1 Perturbation and robustness models
Definition 2.1 (r-boundary volume). The boundary volume of a function f at radius on distribution DD is defined as
Boundary (f) Pr Br ||2112 S and f(x) # f(x + 2)].
Definition 2.2 (Local noise sensitivity). We define the local noise sensitivity (5,((1) at noise scale
as
(5)((x)= =
(0.(() so-N( (o f(z + n=)l].
IE [2lf(e)
We remark that when f is Boolean-valued. this is equivalently
Φ),(()) = Pr [f(x) + f(x + n=)]-
Definition 2.3 (Distributional noise sensitivity). The noise sensitivity function f at noise scale y) on distribution is defined as
(f).,(f)= E [f]n(()] a~D
Definition 2.4 (Isolation probability). We call a point isolated if its local noise sensitivity is over threshold. The isolation probability of function f relative to a threshold is
isoD.,(J.() = Pr (x) > 0.
æ~D
We also use a convex relaxation of the isolation indicator and define vb to be its expectation:
( == 10 E [1( > 0.6] (0),)(x) -0.))]
z~D
Note that (f) is an upper bound on iso(f.0.7)
2.1.1 Noise sensitivity approximators
Below, we introduce the notion of local noise sensitivity approximator. Many of the algorithms introduce will use such an approximator as a black box they can query (see Algorithm 1, Algorithm 5, Algorithm 4 and Algorithm 3). We first introduce local noise sensitivity approximator and some related notions, and present a randomized method for efficiently instantiating it."
Definition 2.5 (Local noise sensitivity approximator for PTFs). For degree parameter an algorithm & is an E-accurate noise sensitivity approximator if whenever is given (i) a degree-k polynomial threshold function f, (ii) a noise rate (0, 1), and (iii) point x E RR, it outputs value @ (5,(2)) such that
())((x)
)gm(t)) Se. SE.
Definition 2.6. Let ò be as in the definition above. Then we define the empirical noise sensitivity and isolation probabilities
(S) = IE IND
(x)((x) and is,D,n(s.)) EE 1(65,(()) > t).
We also define
()) = 10 E [1 znD
> 0.6] (0) -
2.2 Distances and errors
Definition 2.7 (Error and optimal error). We will denote the error of a hypothesis on a distribution
crrp(h) = E
(x.y)~ [2)1(x) vl]
and remark that when h is Booleun-valued this is equivalently
errp(h) Pr (r.))~D
[h(x)) + v)-
'In Appendix A. randomized construction of ē is given and in Appendix D a deterministic method is presented assuming BPP P.
7

---

Relative to a sample set we use
e
[b(x)) - y/
(C.y)ES
We will often denote by opt the optimal error of function f with respect to concept class F:
opt == inf e
g
In this work, F is always the class of linear threshold functioon over R
2.3 Miscellaneous
We will use the notation of the form a = + c as a shorthand for |a - bl S c. We will also drop subscripts, particularly on Φi and ø, when they are clear from context. Throughout this work, wherever there is noise, the noise scale 17 always 10r, where is the desired robustness radius. We use the notation ~ [-1, to denote that f is drawn uniformly from [-1,1].
3 Results and pseudocode of our main algorithm
Our main result is the following. It states the correctness and running time of the main algorithm, ROBUSTLEARN.
Theorem 3.1 (Correctness and complexity of Algorithm 1). Let 2 d-1/7, let r, 8 E (0, 1), and let C' be sufficiently large absolute constant. Furthermore, let à be an E-accurate local noise sensitivity approximator for degree-k PTFs over R2, where Clogg and let the running time and query 8a
complexity of & be T.
Let F be the class of linear threshold functions over Rd and D be distribution Rd {-1,1) whose R -m-aainnaal is isotropic. subgaussian and log- log-concave. The algorithun ROBUSTLEARN, given ii.d sample access to the distribution 'D, with probability at least - ((() returns a hypothesis Rd + {+1} for which the following hold:
orr S opt + 0(s)
Boundaryp, (h) S 0(r
The running time and sample complexity are poly (dlos(11/))/"" (og_//)))"__o((((()) log(116)) -T).
Corollary 3.2. By instantiating ò with the algorithm of Appendix A.I, which evalu- ates queries in poly ( (dus) -ooe time, ROBUSTLEARN runs in total time poly (1/32 log(1/6)).
Algorithm ROBBUSTLEARN s,
1: Input: sample access to distribution D over Rd {+1], error bound e, confidence bound 6, robustness radius
2:
3: Uses: local noise sensitivity approximator ô.
(See Definition 2.5)
4: Output: hypothesis Rd - (-1,1}
5: p:= LEARNREALVVLLUED (D.c.r).
(See Algorithm 2) (See Algorithm 5)
6: return COMPUTECLASSIFEERDDDD...
The algorithm has two "phases": LEARNREALVALUED, which solves a convex relaxation of learning task, and COMPUTECLASSIFIER which rounds the real-valued hypothesis to Boolean one with small boundary volume. We present and analyze these algorithms in Appendix B.3 and Appendix C.3 respectively.

---

Theorem 3.3 (Correctness of Algorithm 2, LEARNREALVALUED) Let r E (0.1), and let 'D be a distribution over R x {+1} whose R Ramarginal is a subgaussian isotropic log-concave distribution over R Let F be the class of halfspaces on R Then, for some sufficiently large absolute constant C, the algorithm LearnReal given E, 6 and sample access to D, runs in time poly (110)1(()))))))) and will with probability at least - (ō) return degree-O(log' (1/E)/e²) polynomial p for which the following hold:
I
IE (m.y)~
(sigu(e- 00000 < 100r +
(2)
k~ (1111
Pr
E
2 0.7
S (((s,,
(3)
(x.
| [-,]]
E
Pr (x,
sign(p(<) - t) + vl S opt O(e).
(4)
8 1.1]
Theorem 3.4 (Correctness of Algorithm 5, COMPUTECLASSIFEEN Let 2 d-1/7 and 8, > Let & be an é-accurate local noise sensitivity approximator for degree-k PTFs over Rd, Let D be distribution over I2 x {-1,1} such that the -maaiinaall is isotropic and log-concave. Let p. Rd - IR be polynomial of degree most satisfying
E
E [(x,y)>
Osign( 9) oo
$ 100r + +OE),
(5)
k 1,1]
Pr
E [-1-1,1]
(sign((((s) 10 (x)) 2 0.7 s O(s).
(6)
Then the algorithm COMPUTECLASSIFIER P. r,), given sample access to and query access to o, outputs a hypothesis h : Id + {-1, 1} such that the following properties hold with probability least (()):
ch) <
E 1-1-1.1
(errp(sign(p +))] + 0(s)
Soundaryp,rO0 (h) S O(r +e).
The running time and number of queries to à are poly(d 1/E log(1/0)))
3.1 Proof of Theorem 3.1.
In this section we prove the main theorem assuming Theorem 3.4 and Theorem 3.3.
Proof of Theorem 3.1. By Theorem 3.3, with probability - O()), the output of LEARNREAL.
VALUED is degree-k polynomial satisfying
E
I (a (osign(p-
< 100r + 0(s),
(7)
1,1]
Pr
E
(eeien( (x) 2 0.7
S Oce),
(8)
b- |w1-1,11 (D
E
Pr(x.)) (sign(p(<) t) + vll < opt + 0(s).
(9)
[=11
This polynomial p is the input to COMPUTECLASSIFIER We see that the premises of Theorem 3.4 are satisfied by the guarantees of Equation (7) and Equation (8). Taking the conclusions of Theorem 3.4 and combining with Equation (9) we see that the hypothesis h we return satisfies
(h) <
E
ferp (sign(p +))] + O(s) S opt O(s),
Boundary p.r (h) < 0(r e),
which concludes the proof of correctness.

---

We now analyze the sample complexity and rumning time. By Theorem 3.3, LEARNREALVALUED takes (O/le=(()/))=") (lo(y))oo((/)))) time and samples. By Theorem 3.4, since the degree of is Oloog" (1/=)/=²) and d' 1/7, COMPUTECLASSIFEER takes
and queries to ø. Evaluations of take time т, so the total running time poly((og( 1/)) time
poly(d"o=(u/e)//)) 1og(1/6) .)),
and all components succeed with probability 2 (6)).
Acknowledgments
We thank Ronitt Rubinfeld for proving insightful comments on a draft of this paper. We are also thankful to Vinod Vaikuntanathan for helpful discussions regarding backdoors and verifiable robustness.
Jane Lange is supported by NSF Awards CCF-2006664 and CCF-2310818, and NSF Graduate Research Fellowships Program, and Arsen Vasilyan is supported in part by NSF AI Institute for Foundations of Machine Learning (IFML), NSF awards CCF-2006664, CCF-2310818 and Big George Fellowship. Part of this work was conducted while the authors were visiting the Simons Institute for the Theory of Computing.
References
[ABL17] Pranjal Awasthi, Maria Florina Balcan, and Philip M Long. The power of localization for efficiently learning linear separators with noise. Journal of the ACM (JACM), 63(6):1-27, 2017.
[ACCL08] Nir Ailon, Bernard Chazelle, Seshadhri Comandur, and Ding Liu. copperty-preserving data reconstruction. Algorithmica, 51:160-182, 2008.
[ADV19] Pranjal Awasthi, Abhratanu Dutta, and Aravindan Vijayaraghavan. On robustness to adversarial examples and polynomial optimization. In Hanna M. Wallach, Hugo Larochelle, Alina Beygelzimer, Florence d' D'Alcéé-Buc Emily B. Fox, and Roman Garnett, editors, Advances in Neural Information Processing Systems 32: Annual Conference on Neural Information Processing Systems 2019, NeurlPS 2019, December 8-14, 2019, Vancouver, BC, Canada, pages 13737-13747, 2019.
[Ant95] Martin Anthony. 61(2):91-103, July 1995.
Classification by polynomial surfaces.
Discrete Appl. Math.,
[ARVX12] Noga Alon, Ronitt Rubinfeld, Shai Vardi, and Ning Xie. Space-efficient local computa- tion algorithms. In Proceedings of the twenty-third annual ACM-SIAM symposium on Discrete Algorithmss, pages 1132-1 139. SIAM, 2012.
13) Battista Biggio, Igino Corona, Davide Maiorca, Blaine Nelson, Nedim Smndic, Pavel Laskov, Giorgio Giacinto, and Fabio Roli. Evasion attacks against machine learning at test time. In Hendrik Blockeel, Kristian Kersting, Siegfried Nijssen, and Filip Zelezný, editors, Machine Learning and Knowledge Discovery in Databases- European Conference, ECML PKDD 2013, Prague, Czech Republic, September 23-27, 2013, Proceedings, Part III, volume 8190 of Lecture Notes in Computer Science, pages 387-402, Springer, 2013.
[BLPR19] Sébastien Bubeck, Yin Tat Lee, Eric Price, and Ilya Razenshteyn. Adversarial examples from computational constraints. In International Conference Machine Learning, pages 831-840. PMLR, 2019.
[Car07] C. Carathéodory. Über den variabilitätsbereich der koeffizienten von potenzreihen, die gegebene werte nicht annehmen. (mit 2 figuren im text). Mathematische Annalen, 14:95-115, 1907.
[CBM18) Daniel Cullina, Arjun Nitin Bhagoji, and Prateek Mittal. Pac-learning in the presence of adversaries. Advances in Neural Information Processing Systems, 31, 2018.
10

---

[CRK19] Jeremy Cohen, Elan Rosenfeld, and Zico Kolter. Certified adversarial robustness via randomized smoothing. In international conference on machine learning, pages 1310-1320. PMLR, 2019.
[Dan15] Amit Daniely. A ptas for agnostically learning halfspaces. In Conference on Learning Theory, pages 184-502. PMLR, 2015.
[DGJ+09] Ilias Diakonikolas, Parikshit Gopalan, Ragesh Jaiswal, Rocco Servedio, and Emanuele Viola. Bounded Independence Fools Halfspaces, February 2009. Number: arXiv:0902.3755 arXiv:0902.3757 [es].
[DHV06] Sanjoy Dasgupta, Daniel Hsu, and Nakul Verma. A concentration theorem for projec- tions. In Proceedings of the Tienty-Second Conference on Uncertainty in Artificial Intelligence, pages 114-121, 2006.
[DKK*21] Ilass Diakonikolas, Daniel M Kane, Vasilis Kontonis, Christos Tzamos, and Nikos Zarifis. Agnostic proper learning of halfspaces under gaussian marginals. In Mikhail Belkin and Samory Kpotufe, editors, Proceedings of Thirty Fourth Conference on Learning Theory, volume 134 of Proceedings of Machine Learning Research, pages 1522-1551, PMLR, 15-19 Aug 2021.
[DKM19] Ilias Diakonikolas, Daniel Kane, and Pasin Manurangsi. Nearly tight bounds for robust proper learning of halfspacce with a margin. In Hanna M. Wallach, Hugo Larochelle, Alina Beygelzimer, Florence d' A'Alhé-Buu, Emily B. Fox, and Roman Garnett, editors, Advances in Neural Information Processing Systems 32: Annual Conference on Neural Information Processing Systems 2019, NeurlPS 2019, December 8-14, 2019, Vancouver. BC, Canada, pages 10473-10484, 2019.
[DKM20] Ilis Diakonikolas, Daniel M. Kane, and Pasin Manurangsi. The complexity of adver- sarially robust proper learning of halfspaces with agnostic noise. In Proceedings of the 34th International Conference on Neural Information Processing Systems, NIPS '20. Curran Associates Inc., 2020.
[DKPZ21] Ilias Diakonikolas, Daniel M Kane, Thanasis Pittas, and Nikos Zarifis. The optimality of polynomial regression for agnostic learning under gaussian marginals in the sq model. In Conference on Learning Theory, pages 1552-1584. PMLR, 2021.
[DKS18] Ilias Diakonikolas, Daniel M Kane, and Alistair Stewart. Learning geometric concepts with nasty noise. In Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, pages 1061-1073, 2018.
[DMR18] Luc Devroye, Abbas Mehrabian, and Tommy Reddad. The total variation dis- tance between high-dimensional gaussians with the same mean. arXiv preprint arXiv:1810.086993 2018.
[DNV19] Akshay Degwekar, Preetum Nakkiran, and Vinod Vaikuntanathan. Computational limitations in robust classification and win-win results. In Conference on Learning Theory, pages 994-1028. PMLR, 2019.
[Duc23] John Duchi. VC-dimension, covering. and packing, 2023. Accessed: 2025-05-11 http://wwbsaaaffuuuddddddsssssss
[GKK23] Aravind Gollakota, Adam R Klivans, and Pravesh K Kothari. A moment- matchhng approach to testable learning and new characterization of rademacher complexity. In Proceedings of the 55th Annual ACM Symposium on Theory of Computing, pages 1657-1670, 2023.
[GKKW21] Pascale Gourdeau, Varun Kanade, Marta Kwiatkowska, and James Worrell. On the hardness of robust classification. Journal of Machine Learning Research, 22(273):1-29, 2021.
[GKVZ22] Shafi Goldwasser, Michael P Kim, Vinod Vaikuntanathan, and Or Zamir. Planting undetectable backdoors in machine learning models. In 2022 IEEE 63rd Annual Symposium Foundations of Computer Science (FOCS), pages 931- IEEE, 2022.

---

[GM11] Olivier Guédon and Emanuel Milman. Interpolating thin-shell and sharp dengeeddniationn estimates for isotropic log-concave measures, 2011.
[GSS14] lan J. Goodfellow, Jonathon Shlens, and Christian Szegedy. Explaining and harnessing adversarial examples. CoRR, fbss/441..652,, 2014.
[KKMS08] Adam Tauman Kalai, Adam R Klivans, Yishay Mansour, and Rocco A Servedio. Ag- nostically learning halfspaces. SIAM Journal on Computing, 37(6):1777-1005, 2008.
[KM18] Zico Kolter and Alcksander Madry, Adversarial robustness - theory and practice. 2018.
[9AG+19] Mathias Lecuyer, Vaggelis Atlidakis, Roxana Geambasu, Daniel Hsu, and Suman Jana. Certified robustness to adversarial examples with differential privacy. 2019 IEEE Symposium Security and Privacy (SP), pages 656-672, 2019.
[LCWC] Bai Li, Changyou Chen, Wenlin Wang, and Lawrence Carin. Second-order adversarial attack and certifiable robustness.
[LRV22] Jane Lange, Ronitt Rubinfeld. and Arsen Vasilyan. Properly learning monotone func- tions via local correction. In 2022 IEEE 63rd Annual Symposium on Foundations of Computer Science (FOCS), pages 75-80 75-86. IEEE, 2022.
[MGDS20] Omar Montasser, Surbhi Goel, Ilias Diakonikolas, and Nathan Srebro. Efficiently learning adversarially robust halfspaces with noise. International Conference on Machine Learning, pages 7010-7021. PMLR, 2020.
[MHS19] Omar Montasser, Steve Hanneke, and Nathan Srebro. Ve classes are adversarially robustly learnable, but only improperly. In Conference on Learning Theory, pages 2512-2530. PMLR, 2019.
[RTVX11] Ronitt Rubinfeld, Gil Tamir, Shai Vardi, and Ning Xie. Fast local computation algo- rithms. arXiv preprint 1 2011.
[8HS+18] Ali Shafahi, W Ronny Huang, Christoph Studer, Soheil Feizi, and Tom Goldstein. Are adversarial examples inevitable? arXiv preprint arXiv: Ntt::/800902/000 2018.
[SW14] Adrien Saumard and Jon A Wellner. Log-concavity and strong log-concavity: review. Statistics surveys, 8:45, 2014.
SSZS+14] Christian Szegedy, Wojciech Zaremba, Ilya Sutskever, Joan Bruna, Dumitru Erhan, Ian J. Goodfellow, and Rob Fergus. Intriguing properties neural networks. In Yoshua Bengio and Yann LeCun, editors, 2nd International Conference on Learning Representations, ICLR 2014, Banff. AB, Canada, April 14-16, 2014, Conference Track Proceedings, 2014.
[VDVW09] Aad Van Der Vaart and Jon A Wellner. A note on bounds for ve dimensions. Institute of Mathematical Statistics collections, 5:103, 2009.
[VW97] AW van der Vaart and Jon A Wellner. Weak convergence and empirical processes with applications to statistics. Journal of the Royal Statisticul Society-Series A Statistics in Society, 160(3))59--608 1997.
A Further preliminaries
A.1 Randomized implementation of à
Let l' be a sufficiently large of i.i.d. samples from (0 1a). Below, we show that the choice of as the following empirical estimate will satisfy Definition 2.5 with high probability over the choice of T:
1
[x(z)
f(x + n2)
)
T
2
12

---

Fact A.1 ([Amt95]). The VC dimension of the class of polynomial threshold functions of degree lo is @ d 0(d*)
Fact A.2 (Concentration of expectations from VC dimension). Let C be a concept class and 'D be a distribution over R For some sufficiently large absolute constant C, the following is true. With probability least å over sample S of i.i.d samples from D, with ||| 2 C- VC(C) log(1/0)/e² the following holds:
sup /EC 2ND
[ff()) - T
Σ
f(z)
S..
ZET
We will call a sample set "representative" of distribution D for a concept class if it satisfies the above success condition.
Claim A.3 (Representative samples provide accurate noise sensitivity estimates), Let C be the class of degree-k PTFs. Let T be a set of points in Rd that representative for N Ia) for C (in the sense of Fact A.2). Then with probability 1 over T, the following holds for all f E C, x E Rd. and rj E (0, 1):
TITT((I)- (1)((x) Se.
Proof. Observe that for any fixed x, the function g(z) ((xx) f(x + m7) is member of C. Thus by Fact A.2, we have with probability that
I~T 2~ (0.1a) [s(2]] Ss.
[g(2]]
The claim follows from observing that (x) [1E[((()) + 1), and thus
1
- -
E 2n
[9(2)] SE.
20,(0.,1))
A.2 Distances and errors
The following facts about the еπтоr and local noise sensitivity after rounding a real-valued function to Boolean follow directly from linearity of expectation.
Fact A.4 (Randomized rounding). Let and be real-valued functions. Let the rounded function fo be defined as
fx(x) = sign(f(x) -t),
and likewise for gr- Then,
Pr [f((x) + w/]
[f(x)
E to b-(-1111
5 E
(a.i)DD
(a.y)~D
2
[f(x) - 9(x)
Pr (f(()) + se(wa)]
5 E
4~| 1.1| (R.U)D
(..D)~
2
Similarly.
E (0 [~ 1-1-1,1)
s (x) and E [n).T(( $0 (z)
[-|11,1]
for any x, y) and
Finally, the following is standard fact, see for example (DMR18). Fact A.S (TV distance between one-dimensional Gaussians). For all p1, #2 in R and 01, in R we have
dr oi, of))
3|0 03
μ1 pzl
20
201
See Appendix A.1 for the definition of 5.
13

---

A.3 Miscellaneous
We say that is a randomized Boolean function over R if f maps every point in R to a random
variable f(z) over {0. 1]. Sometimes we will write f(x) = Ber(p). to denote that f(x) = 1 with probability p and 0 with probability 1 1- p. In Appendix E, miscellaneous claims about uniform convergence are shown, which are used in the analysis of Algorithm 2.
B Pseudocode and analysis of LearnRealValued
In this section we present and analyze our algorithm for learning a polynomial with small noise sensitivity and isolation probability.
Algorithm 2 LEARRREALLALLUED((
1: Input: Sample access distribution D, error bound robustness radius
2: Output: hypothesis (- {-1,1]d - R
Set k == (1/e)
4: for in (1,... (1)) do
5:
S: = [Cdck log(1/6)/E8 i.i.d draws from DJ.
6:
T; = log(/))) /E² ii.d draws from (0, Ia)}
7:
Let p; be the output of the following convex program:
Domain: polynomials over R2 of degree k.
Minimize: E(ryes (p(x) --y) yl
Constraints:
Define o(t),,T,10r = 1 ELer [f(x) [(00((((n)))))))))))))))))))))=1
Define p.. = 10 1[6(F) > 0.6) (6(x) - 0.6)
Constraint 1: [S] Eves Pp.T,
100r +e
Constraint [ST Eves (p.T,10r(2)) Se
8: i = argmin, (E(r,))
[pila)_w)
9: p = pr..
10: return
B.1 Facts about log-concave distributions.
Definition B.1. distribution D over Rd is called S-suub-Gassiin for any unit vector u:
Prz [u u x² > f] s exp(-Ct?)
for any t 2 0. We say sub-Gaussian, if D is muub-Gassiin for some absolute constant C.
See e.g. [SW14] for the following fact:
Fact B.1. If Dy and D2 are log-concave distributions over Rd, then the convolation of D and Dz is also log-concave distribution over Rd.
Likewise, the following fact follows directly from the definition of sub-Gaussian distribution:
Fact B.2. If D1 and D2 sub- Gaussian distributions over R.d. then the convolution of D1 and D also a sub-Gaussia Gaussian distribution over Rd
The following fact can be found in [SW14]:
Fact B.3. If a distribution D over Rd is isotropic log-concave, then the projection of D on any linear subspace in IRd is likewise log-concave.
The following two facts can be found in [GKK23], [ABL17] and the references therein.
Fact B.4. If a distribution D over Rdd isotropic log-concave, then for some absolute constant Ca. for any unit vector u and every interval J C. IR, we have Pra-Dl(u, J] |J].
14

---

Remark B.5, It follows from a direct change-of- basis argument that Fact B.4 still holds if the premise that the distribution D is isotropic" is replaced by slightly more general premise that D mean zero and satisfies:
Taxd 3 Fog [x="] 3 200Taxd
For the following fact, see e.g. [DKSI8] and the references therein:
Fact B.6. If a distribution D over R is log- eog-concave, then for some absolute constant Ca if p is a degree-k polynomial for which Ee~D((p(z))> 1, then for any B >> e it is the case that
Piæ~D((p(z)) BJ S exp(-CcBB/k)
One can use the fact above to conclude the following:
Observation B.7. If distribution D over R is log-concave, then for some absolute constant C5+ for every degree-k polynomial it is the case that
VELND(P(<>))
Ee<Dlp(=)]]
(Cgk)Cok
Proof. Without loss of generality, assume that Ee>D((p(x))) = 1. For any B 2 0, we have
Em~D|lp(>>]] Ex~D(pp(x)) 1 p(x)sal
1 - EgdD [l{(x)1 [p()]|=
(10)
B
B
Using Fact B.6, we have
toc
F E ((t))((())
(1k)
>ra= 3)BB
8=D
O(k)
(8))34/221 10pa0/2-1ep((COCC exp(-C,0r)BB (
3'=0
which allows to conclude that
( (0()))
Eg>Dlp((>)| p
B
B
Taking equal (C" for sufficiently large absolute constant C², and substituting the bound above into Equation (10) finishes the proof.
B.2 Approximating halfspaces with polynomials
Claim B.8. Let h be linear threshold function over IR. Then, for every absolute constant C, there exists polynomial p of degree (11/²² log" (1/e)), such that for any C-sub-Gaussian log-concave distribution D over Rd satisfying Laxd 3 En [xxx"
log"(1/E)),
200 have
F - p(=) S O())
Remark B.9. Recall that a distribution D is log-concave if the logarithm of the probability density function of is concave. Note that the constants hidden by the O(-) notation in Claim B.8 are allowed to depend the sub-Guuse Sau--aussiantty constant C.
To prove the claim above, we will need the following proposition from [DG]+09]:
Fact B.10 ([DG)+09) 09]). There exist absolute constants C4 and Cs, such that for every s (0,0.1) there exists a univariate polynomial P satisfying the following. Denoting a == C, log(1/]] and
2
K = Cs log -0
log² 1/s) it is the case that
The degree of P is at most K.
.
P(t)) E (ign(t),sign(( + for all in 111/2-1222 U [0. 1/2].
'Recall that the condition that D) is isotropic means that 1) has and covariance laxd-
15

---

P(t) E
in [-2a. 0]
[P(() S 2 (4t)* for all [t] 2 1/2.
The proof below follows closely the line of reasoning in [DGJ+ 09] and is included for completeness.
Proof of Claim B.8. For a unit vector u h(x) = sign(u x - r) (assuming T = for now)
If | > log(1/E) the statement follows immediately by taking P to be the constant polynomial that equals to sign(7) everywhere in Rd. The error between h and P will be upper-bounded by O(e) via Definition B.1 and Remark B.5.
Otherwise, we have |T| Σ log(1/s). Let P be the polynomial Fact B.10 and take w := 1og 1/e
1/2 for a sufficiently large absolute constant Co. Denoting by Drojocted the projec-
Co
tion of distribution D on the unit vector we can bound the error as follows using Fact B.10:
Fig-D(ssign(
- P((u- x T)/w)ll = Fizz
[[sig([ -T) -P((== r)/w)ll s
(
2 2-
E+2 Pr Donccual 2-2 S w/w-r= S 0]+ Be Deniecsas
2
+1 ((==-))//(21/2
(11)
The second term above is bounded by ((aw) due to Fact B.4 and Remark B.5, We also note that for sufficiently large absolute constant Cs we gave |r|/w < 0.1. Therefore, whenever (z T)/w] 1/2 we also have 2 0.4w. This allows to upper bound
since |r| S log(1/s) and =- Cs log" 1/e 1/2
ExwD Flsggls x. -T)- P((u. x- ((tuvx-)//w]] S
{2
(2. (4. w
+ +.1) K +1) 1 11//00.10 S
8 + O(aw) + Dawssooad
[(3 (5
2 x
e + (aw) Eiz- Dassssed
11/20.
(12)
w
Decomposing the interval [0.4, oo] into union U 00.4 2 - 2 and using Definition B.1 and Remark B.5 we can now upper- upper-bound bound the last term above as follows:
EgnDauossnd (3 5 2) K
))
1 11/20.40
2
(3 (4-2 Pra Denicnal | 2'-11 20.1... s
1=0
Σ (4- exp( exp(-C((i-3u))) (13)
Substituting K = 0 log" 1/c
and Co
log" 1/s
1/2
we can bound each term in the sum above
log" 1/5
C C.2i-3 -3 log" 1/c
(4.2 exp( 3 ww) < exp (i 2)-20-0
82
For a sufficiently large absolute constant Cg the above is at most e/2i+1, which substituted into Equation (13) gives us
(3 (5. (3.
K
E Prosessed
11 1 Sc.
Finally, substituting the inequality above into Equation (12), we get
Ex-D [ssign[ (u- æ) P(u z/w) = 0(s),
finishing the proof.
16

---

B.3 Analyzing LearnReal
Theorem 3.3 (Correctness of Algorithm 2, LEARNREALVALUED, Let r E (0,1), and let DD be distribution over R {=1} whose R -marrinalll is a subgaussian isotropic log-concave distribution over RS. Let F be the class of halfspaces on R Then, for some sufficiently large absolute constant C, the algorithm LearnReal
given E, 5 and sample access to D, runs in time poly (dolog (11e))=²) and will with probability at least (() return (loge- polynomial for which the following hold:
E
IE (x.y)~
(Psign(p--)1000 0,100(11]] 1 100r + O(=),
(2)
[-]-1,11
Pr
|~1-1,1] (sign(p(()) 10)
E
0.7
S ((ss),
(3)
(x.1))D
E
Pr (sign(p(>) t) + vl (r.D))D
I opt O(c).
(4)
8 1.11
We first argue that the run-time is indeed (1e)o=" The algorithm operates with polynomials of degree k Olog* (1=)/e² (10))(1=))/=" over R which are described via (k) coefficients. It remains to show that the constraints for the optimization task are indeed convex the coefficients the polynomial p. Recall that the constraints are:
Constraint 1: 19 EvEs (p.1110((1) & 100r +
Constraint [ EVES 1p. S
To see that these constraints are indeed convex, first note that, by definition of (0. and the triangle inequality, we have for any pair of polynomials pr, P2, x Rdd and a E [0, 1]
ō (aps (1-0))a)) (x) a&p, .T 10 (1 a) T (z))
(14)
which implies that Constraint 1 is convex. Likewise, reclalling the definition of ab
p == 10 (6(2)) > 0.6] (6(z)), - 0.6),
and combining with Equation (14) we see that
+
S
a (.).p..r.o0r
We now proceed to the proof of correctness, the following claim will be key to our argument, which will be proven in the next subsection (Appendix B.4):
Claim B.11. For any specific iteration of the algorithm, the polynomial ps will satisfy the following:
F( ( (1))) s 100r + +(s),
(15)
E [o < O(e),
(16)
and the following holds with probability at least 0.9:
(pa(x)
vl
S
< min (PI (f(x) # vl) + Oss),
(17)
2
JeF
We now prove Theorem 3.3 assuming Claim B.11.
Proof of Theorem 3.3. First we note that for sufficiently large value of the absolute constant C, with probability at least - O()) for all i {1.... log 1/8), the set S, will satisfy Claim E.2, Claim E.3 and Fact E.5, and the set T, will satisfy Claim E.2. Furthermore, since the main iteration is repeated
17

---

(loo 1/6) times, the we see that with probability 1 - (6) the polynomial p ps- will satisfy Equations 15, 16 and 17. Denoting = S.- and T T,-, we have
Since satisfies Claim
[p-[-111] (x [ssin(lp 1), 10r (z)]
- Eg [111- [xxs)s (ssgn(n--t).n (2)]] + 0(=) =
< [ E ((yy)s (utgu(p-0),r (x)
+ O(e) & ((),)) (p.T.100(0)) + O(e) S 100r + O(e)
Since satisfies Claim A.3, and WL.0 0.02.
By Fact A.4
By Equation (15)
which gives us Equation (2). We now derive Equation (3) follows:
Since S satisfies Claim E.3
Pr 100[--1,1]@siin((ttt (m.
0.7] Σ
Pr (m.
E
1), 2 0.67 + +(e)) -
< Pr [ [ (z) 2 0.65] + O(E) S (() (o.). + O(e).
0 By Equation (16)
Since satisfies Claim A.3, and WLOG 0.02.
By Fact A.4 and definition of (Section 2.1)
Finally, we derive Equation (4) follows:
Since satisfies Faet E.5
Fea(-111 (errD (sign(p - 1)] S F eris [sign(p 1)]] + O(e)
[p(x)) vl (c)
(Za))s
opt + O(e)
By Equation (17) and defn of opt
By Fact A.4
B.4 Proving Claim B.11
Finally, we finish this section by proving Claim 1. Inspecting the algorithm LeamReall we see that the linear program is always feasible for any input dataset S;, because the all-zeros polynomial will satisfy the constraints in the linear program (i.e. Equations and 16). remains to show that with probability at least 0.9 there exists polynomial p; satisfying all three of Equations 15, 16 and 17.
Suppose f is the optimal halfspacce for D, i.e.
PT(aa)~D [f" (x) # v] min (Pr(a..) (f(x) # v)) /EF
(18)
Let D marrgnnll denote the Rd -mrainaaa of D, and let D' mmaagiinal denote distribution of 10rz, where is sampled from D marginal and is sampled from A' Ia). Since Dmorginal is assumed to be sub- Gaussian log-concave, Fact B.1 and Fact B.2 tell us that D Dimagimal is also sub-Gaussian log-coneave. Furthermore, since Dmarginal is isotropic (i.c. has mean zero and identity convariance) and r is in (0, 1) we see that
Ia = Ea- [xx 101 Therefore, Claim B.8 tells that for sufficiently large absolute constant C" there is polynomial of p" of degree C' [1/e] for which Eg- p=))) 0(E)
2²
-
(19)
Ex-Dr meginal (z)--((x))) > (())
(20)
Recall that for each element (x, 3) in S,, the variable x is distributed according to Dmarggial- Similarly, for each (x. y) in S, and z in T. the sum 10rz is distributed D' D'marginat- This allows us to use inequalities above conclude that with probability least 0.99 have
E(ny) [Ip" (z) f [x)1] < O())
(21)
E( [Ip" (xr + 10rz) - (xx 10rz) < 0(s)
(22)
In the remainder of this section we show that with probability at least 0.9 over the choice of S, and
T, the choice p. = p² will indeed satisfy Equations 15, 16 and 17.
18

---

B.4.1 Bounding Dampraa 10r and Daurpiaa k (x)]
Recall that (x) sign(u T) for some unit vector and real 7. Here, we show that f satisfies the following two inequalities
Eg- Daanina 10-- 100 (x)] S 60r;
(23)
ExnDini ( (2:) 0.
(24)
Indeed, fix specific value of x. Recall that f0r 10r (x) is the probability that sign(u r) + (20(ww(w(000)))))
where z is sampled from ( La). With probability least 0.5 over the choice
of Z we have sign(u=2) = sign(u-x-1) --) which leands to sign(u-2: r) o sign(u - (x++ 10r=) -T).
Thus, 10r, (z) < 0.5 and substituting this into the definition of we see that (b(x) 0, which proves Equation (24).
Now consider points z in I2 such that -u-x 7| is in the interval [10r (i 1), 10r -i] for integer i. We have the following two observations:
By Fact B.4, we see that the probability over x sampled from mmrrginal that |u 7| is in the interval [10r
1), 10r i] can be upper-bounded by 20r.
For fixed for which Ju 7| is in the interval [10r (i 1), 10r i]. via Chebyshev's incquality, it follows that
10r(i (110010 10)
10r
)
2) = max (1, (i-1
(1(2-1
Prz~A((o (a) (igg((ux---)) + sign(ut (x++xxx+022))) - r)] S max 1,
Combining the two observations above, we see that
1, (1 )
1
2
Ez 10 10r (x)] s 20r max
- 60r,
which yields Equation (23).
B.4.2 Bounding ((n,)) 10p .. 10))) and ((r.a)) (bpp 10
We observe that
p'(x) (x 10rz)
(( (T(()) (pp., (x Tn
(z) fx 10rz)
px(x) (x)
p² + 10r2) fz + 10rz)
E(gy)s snii
+1
+ + (a I
2
2
2
E (0r))
11'(x) (*(x) F. InT lp (x 10rz) fx : 100z))
=0(e) by Equations 21 and 22
(25)
Analogously, by inspecting the definition of vi, see that for any we have
Wp (x) Wy..n, (x) < (x) - p" (x)) + 0(1) FE [1 + 102) p² 10=)
Averaging over æ S., we have
E( 1 2 (x)
((xa))s 10p T. 10r +0()) (E 1p'))))))"(())>))))))))))()))>)) 1=((x)=f((x) + E(z.)))
pp(x + 10r2) f" + 10r2)l)
O()) by Equations 21 and 22
(26)
Recall that /' is (=1]-valued function, which implies that ă 10r x and z. This allows us to use the Chebyshev's inequality to conclude that:
(x: + 10rz) is in [0, for all
Ez, 05 (x) 2 10 (2) 5o
VIT.
19

---

Inspecting the definition of db, we see that for any z it is the case that
(2) - - 0(1) - - 100 (z),
which implies that
Er, wby 1.)) vy (x))
V
Averaging the inequalities above over in Sü we have:
Ër, [ic.e)>ss [ [, 05 10)
||
00
VITil
ET. ((a))) I (x) -
0o
VITA
Thus, with probability at least 0.99 over the choice of Tú we have
B(nay~s [ōj- [ōp-:n.1or(x]] - E(aw)~s 00 (0r (x)]
[1 (0) - 20-
(
1
- (ay))s
so
VITil
(27)
E ( x (x)) (s [-)((>)] ((x)))
- - 0o
VTI
(28)
Again, recalling that f is a (+1) 1-valued function, we see that df 10r is in [0, 1] for all x and y is likewise bounded by ((1) in absolute value. This allows us use the Chebyshev's inequality to conclude that with probability at least 0.99 over the choice of S; we have:
1
B( (65 (0)) EengDanii 10, 10. (x)] SO
(29)
VISA
E Exgy) (1y- (x)] Ex (1 (x) 50
(30)
V
Overall, combining Equation (23), Equation (29), Equation (27) and Equation (25) we see that with probability least 0.97 over the choice of S; and 7; is the case that
E (a.,))ss 10p- (x)] S 60r + O()).
Similarly, combining Equation (24), Equation (30), Equation (28) and Equation (26) we see that with probability least 0.97 over the choice of S; and T. it is the case that
B 16 . (z)] S O(E).
B.4.3 p" has small empirical error.
Finally, we argue that with probability 0.99 we have E( (x) O(e). Indeed, Hoeffding's inequality implies that with probability least 0.995 we have
( (x))))
lf (x) vl
E
2 +
whereas Markov's inequality tells us that with probability 0.995 we have
[x) (x))]] 0(1)
[x
p²
E(g,y)s
E
O(e).
2
Overall, we see that with probability least 0.99 holds that
Ip"
yl
ff(()) yl
1p' fx))
ff(()) y
E(
< E(ayy)
+ Exx
< E
+0(e)
2
2
2
2
20

---

C Pseudocode and analysis of ComputeClasifier
C.1 Local correction of adversarial robustness
Theorem C.I (Correctness and complexity of Algorithm 3). Let & be an e-accurate local noise sensitivity approximator for degree-k PTFs over R and let T be the run-time and query complexity of ó. Then there exists an algorithm ROBUSTNESSLCA, (2, 9, r) that takes x in R query access to function R + {-1,1}, perturbation size parameter r in (0. The algorithm makes ( queries to 9. runs in time ((T + d), and satisfies the specifications below.
Let be a distribution over Rd, and let g be a degree-k PTF. Let the function R {-1, 13 be defined as h(x)= = ROBUSTNESSLCA (z, r). Then the following properties hold:
a) PLæ~p(g(s) + h(x)) & isoD, 10. 0.8).
b) Prawplog,1rr (x) 0.1) > 1 0 (NSD
c) For every in R if (x) I 0.1, then for every at with || x/l S we have h(x') = h(x).
Algorithm 3 KOBUSTTEESSLCA(R.....)
Input: point æ E Rd, black-box representation of function g RRd + {-1,1}.
2:
robustness radius r
3: Uses: local noise sensitivity approximator ş.
(See Definition 2.5)
4: Output: b E {}
5: if 6g,100r > 0.8 then
6: return - ((x)
7: else
8: return (xx)
Proof. Inspecting the algorithm ROBUSTNESSLCA. we see that condition (a) follows directly, as only isolated points have their labels changed. Meanwhile, condition (b) follows directly from Markov's inequality and the definition of NS (Section 2.1.1).
To show condition (c), first recall that by the assumption that & is an e-accurate approximator, for every degree-k polynomial threshold function g and every x in Rd we have
- (z)))) - (o) S < 0.01,
(31)
where for the last assumed without loss of generality that 0.01. This implies that whenever (x) < 0.1 we have 0g.10r (x) & 0.11. Suppose x' has distance most r from æ. Since dg. (x) is defined as
1g.10 2~N(0.11))
Pr [g(x) # g((x 10rz)].
we see that
(o(a) * g(x' + 10r=)] 5 N0.(0.)1))
Pr
Pr =~~(00,1)) ,, [g(x) * g(x 10rz)] drv (N(,, 100r
(10, N(( 100r?Ta))
[g(x) g(x + 10r2)] + 1| x'1
Pr (0,.)
20r
where the last inequality is implied by Fact A.5. Overall, since we know that 10 (x) S 0.11 and
|| x' have
Pr
(Ø(x) # g(a' + 10rz)] & 0.16.
Now, we consider the following two cases:
21

---

Suppose (=²) (xx): then the above implies that 09.10- S 0.16, which combined with Equation (31) implies that 0z 10. (0.100(())) (x') S 0.17. Therefore, by inspecting the algorithm ROBUSTNESSLCA we see that h((²) g(x') - g(x) = h(x).
On the other hand, suppose 9 = - gz)). Then, we have Φg 10, (2') 2 - 0.16 = 0.84.
which combined with Equation (31) implies that 10, 2 0.83. Therefore, by inspecting the algorithm ROBUSTNESSLCA we see that h1(²)) = - -((') = g(x) h(x).
In either case, we have h(2') h(z).
C.2 Finding good rounding thresholds
Theorem C.2 (Correctness of Algorithm 4), Let E E (0, 1) and D be distribution over R x {+1}.
Let e be an e-accurate local noise sensitivity approximator for degree-k k PTFs over R Letp R + R. be polynomial of degree S lo satisfying the following:
E
IF
(eign(e- 10. <100r + O(e),
(32)
1.1] (ar,)))
Pr (m,y)-D
[
2 0.7 S 0(e).
(33)
The algorithm COMPUTEROUNDINGTHHSSSIOL.
outputs real numbers t1, t1, t3. t4 and Wi, W2 W3,, W4 E [0, 1] such that Σ, wy = 1. Let the hypotheses g1 92. 93. 91 be defined
ga ( = sigu(p(x)) - t2).
Then the following properties hold with probability at least 1 0
Σ. w; (gr s En E.w.-..nlerro(signfff t))1 + 0(s)
Σn W; NS (9)) - 200r + Os)).
E, w/ isop 10r
1orp100rrss.... (g,, 0.8) < O(s).
We argue that with high probability over the choice of the O(1/=²) random rounding thresholds, the weightwe mixture of the rounded functions has each the desired properties.
Claim C.3 (Properties of the equal mixture of all rounding thresholds). Let e E (0, 1). Let p Rd
R. be polynomial of degree < k satisfying the following:
11-(-1111 E(E www.ooollliiippoooooooe
S
Pr (2.0)DD
Eier- 1.11 piee--nnl@@nggttttopppopoo (x) 2 0.75 s (Es).
Let θ be set of 100/E² real numbers drawn uniformly and independently from [-1, 1). Then the following hold with probability 2 0.99:
(a) Eugelerrp - -))] s (err +((s)
(b)
(x) < 2x O(e)
(c) Exce (Pr (ttppPprelllsppp-aaap
> 0.8]| - O(c)
Proof of Claim C.3. We will show that each of the conditions holds with high probability, then union bound.
22

---

Algorithm 4 CCMMUTEROUUDDINGTTISSSSSOO
Input: sample access to D, robustness radius r.
error bound E, confidence bound 3: Uses: local noise sensitivity upproximator 6.
2:
(See Definition 2.5)
4: Output: thresholds { = t1, 12, 13, 44 E [-1, 1] and weights oi = w1, W2, Wa, Wa E [0, 1]
5: Initialize
Ø.
6: M + -100/s² log" (1/6) i.i.d. samples (x, y) from D
7: for i E [log(1/0]] do
8: for E [100/=²] do
9:
Draw rounding threshold & u.a.r from [-1, 1] and define rounded function pz(x)
sign (p(z) t).
Let err, = err (pt).
11:
Let NS; = IMd EEEE Pur (x)).
12:
Let iso, = I
[M EzEm 1l po, 2 0.8].
13:
Let q: = Wui,,NNs,. iss,)
14:
Add qt to Q.
15:
opt = [Q] (s. (erre)
for tuple 91 92. Is. Qa Q* do Solve the linear program with variables w1, W2, Ws, defined by the following con-
17:
straints:
E Wi = 1
== wili,1 S opt - Cs
C' a sufficiently large absolute constant.
== Wiqi2 S 200r + Cs
E W4Kks S Cs
If a solution is found, return E== 11, f2, 13, 44 and W1, 022 W3 M44
19: return
(a) = ert (sign(p - t)). We have [a[X]] = |0] BBwo-nnnlerrp(iignn( - t))
and we apply Hoeffding's inequality:
Pr
E (erpossign(p
t))]
E perru(sign())) t))] +
1~
|--1111
= Pr[( - [[X])/ exp(-2e" -100/22) = 0.001.
(b) We have by assumption that
E
() S
Let X = Eice lowinll - which has expectation < | .a. Then by
Hoeffding's inequality, have
Pr|X/|0| > + < Pr[(X E[X])/10] exp(-2e² -000e²) < 0.001.
(c) We have by assumption that PraND [EL 1, (diinmpp (x) 2 0.75] < O We want to bound
Pr t- Dn
())) 0.75).
We can upper bound this by
(Es)
F. Pr (sign(p-
E. [ 0.05]
tw
1-1--1111
O(E) + Pr Pr (dsign(n (010--1,11100ipn6ee (x)] 0.05).
23

---

Let X = Eieo Osign(p-t) (z); (x);; by Hoeffding's inequality we have
Pr
E L~8
[sinn( Eey-t--nl(0stooo-))/(/ 0.05 Pr((X - [[X]/ 0.05
S exp( (2 0.025 (100/E²))
S E/1000.
Thus, combining all three probabilities, have:
Pr Pr Pr (esignto-)))110 (x) Ee (Fv--1-1u1(00amm6-ooo0oooo11 0.05] E/1000 anD @ (~0
Then we apply a Markov bound:
Pr
Pr 2-Di
(0sinn(p- E 11n---1._100sppppppp0...... 0.05) > & s 0.001
Union bounding over the conditions, we have that all three conditions hold simultaneously with probability at least 0.99 over the choice of O.
Now will show the existence of mixture using four rounding thresholds from O and show that COMPUTRROUDDINGTHRSSSIO.. finds it. We will make use of the following well-known theorem of Carathéodory.
Theorem C.4 (Carathéodory's 's theorem [Car07]), Let P C R be a set of points and Conv (P) be its convex hull. For any p E Couv(P) (P), there exists a set C P of + points such that p can be written convex combination of points in S.
Proof of Theorem C.2. We first note that since is an e-acourate local noise sensitivity approximator for degree-k PTFs, Equations 32 and 33 respectively imply that
E
E
Geign p- 10)) < 100r + O(e),
(34)
[H.N)~D
Pr [ (00mm(p-0)10000 (0-00 0.75) S O(s).
(35)
b~1-1.11
Thus, the assumptions of Claim C.3 hold with = 100r. For a threshold f, let the three-dimensional point 9: == (err,, NS,, iso;) be defined in COMPUTEROUNDING H.HHIIN....S.... First we argue that each of these estimates is O(E)- Each estimate is the expectation of a random variable bounded [o, 1), so by Hoeffding's s inequality we have
Pr[lerr; err (sign(p - f))1 2 S exp( 25a [M]),
and likewise for each NS, and iso,, We set M large enough that this probability is < 8/2 exp(-100/85 giving more than enough room union bound over the log(1/6) -000))330----0000000 timates. Likewise, by the Hoeffding bound, we have with probability 1 - that
300/ =² es-
opt E.-(-1.1] (eigg t)) E.
Thus with probability at least 1 - 5, all estimates are e-accurate. Then, by Claim C.3, we have that with large constant probability q² of the points {ge t E Q} that satisfies the linear constraints
the randomness of the set θ, there exists convex combination
q" [1] Bew--anfeerr((iinnf2 ())] O(e) < opt Cse
q" [2[ < 200r + C'
(²(3] < Cs.
We assume 0.05 without loss of generality.
24

---

for sufficiently large constant C. That linear combination is the equal-weighted mixture Eigo By Theorem C.4, since the qi 's are points R it possible to write q" convex combination of four members of {ge í E )). Thus, for some 4-tuple in Q', the linear program is feasible. DOMPUTERROUNDDNGTHRRRRRRS returned.
searches every possible tuple, guaranteeing that solution
By repeating log(1/6) times with independent draws of θ the large constant success probability is boosted to -.
C.3 Randomized set partitioning
Algorithm 5 COMPUTECLASSIFTER p, &,
1: Input: sample access to D, polynomial p.
2:
robustness radius r, error bound E, confidence parameter
3: Uses: local noise sensitivity approximator p.
(See Definition 2.5)
4: Output: Classifier h Rd {+1].
5: (t1, 22, t3, tq. W1, W2, Wgg wa) + COMPUTRRULNDIGCTEESSHODSSSSS
(See Algorithm 4).
(1/6)/E² samples from D (for sufficiently large constant C*) 7: for i [log[1/0)] do
Steat
8: M < 10d i.i.d. samples (z, y) from D
9: For E {1, (1....,4 4]. define the following Boolean functions: let
(x)x) = ROBUSTNESSI.CA(Ar,, sign(p 44),))
(See Algorithm 3)
RobustIndicators (z) 1 [[ 10) s 0.1]
10: For each (1,-.., 4}, let
N +-
E
1ly + h.(x))
(NNjjM
144
E (x.))MM
RobustIndicator(())
Obtain an orthonormal span( P1, p1. 141.
collection of vectors {ui,"". ua/2
orthogonal to
12:
Generate a uniformly random unit vector u" in span(u1,"" u2/2).
Compute partition of the real line into intervals J of Gaussian mass wT ..... W4 respectively.
Check if the following hold for each i [4]:
E
[1 # (x)))) (e,"") Jj]
E
[1ly * hz(z)) w. C'e
(ar.t) -Seatt
(a.y) Seaee
(for sufficiently large constant C²).
E
[RobustIndicatorr([]] A (z, u²) E Ji]
E Sentt
[RobustIndicatorr((]] w; = C'e)
(x0.3)~ Steat
15: If so, return the function h defined
1 h(x) = Σ hx(x) 1[(u",2) J.)
16: return
In this section, we will prove the correctness of COMPUTECLASSIFEER As explained in the previous section, the output of COMPUTER ANDOMTHRESHOLLDS for rounding. The goal is for a small collection of sets the sets of points misclassified by each threshold and the sets of points for which ROBUSTNESSL guarantees robustness each be partitioned such that wi of their mass falls into the tth part for each i.
list of four weights and four thresholds
25

---

The partition is set of intervals along a unit vector chosen uniformly from the subspace orthogonal the estimated mean vectors the sets we want partition. The intervals are chosen have mass w.....; W4 under the one-dimensional standard Gaussian. We will argue that with high probability over the choice of the random unit vector, of our sets will approximately normally distributed in their projections on this vector, and thus the intervals will contain the right proportion of their mass. The key fact underlying this argument comes from the following theorem of [DHV06]:
Theorem C.5 (Concentration random projections: special case of Theorem 11 of [DHV06]). Let D be a distribution over Ra with mean zero and covariance bounded by Xmax in operator norm. Assume also that D is supported only on points x satisfying |=l| 2 vvd. For a unit vector v, let De denote the distribution of (x,, v), D, and let Pil-1 denote the distribution of || /Vd, D. With probability at least
Amax In(1/E)
exp (-22
EtV2d
max In(1/E)
over a uniformly random unit vector v, the following holds for all intervals J:
Pr 1a E] D-D
[ Se. a~D
Pr
*~((0,00))
We apply this theorem the distributions induced by distribution conditioned on a (potentially randomized) indicator, such as the indicator of a point being misclassified by hypothesis;
aim to partition. This is underlying
will represent that indicator r(x). After projecting the subspace orthogonal to our mean estimates, these distributions will still not have mean exactly
zero, so we incorporate error term into our analysis to account for that. The resulting claim the following:
Claim C.6 (Masses of intervals under random projections). Let r(x) be a randomized Boolean function over R2, P d/2- d/2--dimensionl linear subspace in R&, and J S R be an interval. Let P be d/2 x d matrix whose rows are orthonormal busis for P. Assume the following hold for some B1, B2 E (0, 1) and B3
Bounded mean: ||P (PEzDD(()))i 31.
Thin-shell support: Every x for which r(x) can be nonzero satisfies
IPll = 1 + $2. vd/2
Large support: BR=DDr(())] 2 B3.
For unit vector v. let D denote the distribution of (Ix v), conditioned on r(x) 1. With probability at least
(1+8//3)) exp -S2 =3 - -231)
5 B1 2,2 2,3 )3))d In(1/e)(1+
over v drawn uniformly from unit vectors in P, we have
Pr [2 E] Pr [z E J] z~N(0.1)
< +2)+
Proof. Let == En r(() = =]. We will define D to be the distribution of P(x p)) and DlilI to be the distribution of [i p)1ly fillz//a// /a/2, where x is drawn from conditioned on r(z)
We aim to apply Theorem C.5 to the zero-mean distribution D in the d/2 dimensional space P. and find the appropriate bounds for and Xmax-
Bounding v: By the thin-shell assumption, every for which r(x) can be nonzero satisfies
[Poll2 2 / /d/2(1 (2). Thus for any such æ, we have [[ m)ll2 2 vd/2(1 B2)
26

---

[Pull2 by triangle inequality. Now we just need to bound |P
r(x)= =11 11/
|P 2
P E 1
P [
D(x) (r,(((a) =
JEER x.
Pra, (r(z) =1
2
P E (r())
E [x)]
PP Ez [r or
81
E [x))
by the bounded-mean and large support assumptions. This gives us v 2 1 - 82 8s //2 d/2
and thus y² 2 111-232 232 -
8 a/2
2
- - by the assumption that B3 2 1/ d/2.
As a/y
Bounding Amax: We want spectral bound on EE A.D [xx²]] We have:
(= (P) 1))
E
DnD 2.7
Fig [r.)
I.
[xxx" + 14²" znp nx²)] pd
83
RND
Since has mean zero, and IE. F(rx") has operator norm and PIupT'T has operator norm 2 ||Pull we have
+ |PHll2
1+ 11/1/3
Amax
E Dr D.P
Jow
Ba
33
Substituting these parameters into Theorem C.5 gives the claimed failure probability bound. The condition that holds with high probability is that for intervals J, we have
[3
[ J] anD
SE.
s~(((0,0))
By the thin-shell assumption, the bound on ||Plll and the triangle inequality, D1H11 is supported on [1 - 31/33 33, 1 + /1/33 + 32). Then by the TV distance bound for Gaussians, we have for any a in the support of DIHI
3/1 o2
drv (V10
<0(3/ B2),
2
so we have
Pr Dre
[2 J
Pr [z J. O(E + 81/Bs + 32). z~N(0.11
We now substitute the definition of (D),p) and use the fact that is in P.
Pr [a E J]= p.
Pr Pr [((( p), E J]
m-D
Pr Pr. 1) (), J]
Pr ly + (1.0) J..
w-D:
So we have
Pr [z + (4,0) E J]- Dr.
Pr [ E J < 0((= + 81/3s + +3))
2>
27

---

By applying the uniform convergence property of Theorem C.5 for all intervals to shift J, we have
Pr 22 () E J| S + B2). =~N10,11)
Pr E~Di
[a E
By anticonceettaation of the Gaussian distribution and the fact that (e, ((),0)| B11/3,, we have
Pr [a (M, u) E JJ = Prz=N/o,n) JJ] J/| 2 (0.1)
Combining everything, we have
Pr [= E JJ =
Pr 1a J z-N(0,1)
S 5s + (2)
with probability at least
(1+ In(1/E)
exp (-90
E 5'Ba(1 232 23 )d
(1 ))
33 20.1-283 -231)
as desired.
now argue that for r indicating a set of large Gaussian volume and P being orthogonal to good approximation to the mean of the assumptions of Claim C.6 are satisfied with small values of [3.
The following facts are relevant this proof.
Fact C.7 (Thin-shell concentration of log- log-concave variables [GM11]). Let X be isotropic random vector with log eogecce density in R.. Then there are universal constants c, C such that for all I 120 0,
Pr |1X122 1 2 S Cexp(-odd1 min((1/Vd)) 1/Va)).
Corollary C.8. Let X be an isotropic random vector with log-concave density in Rd. Then there is universal constant C such that for any > 0,
Pr
X val z C(d ((dlo)(1))))) Se.
Fact C.9 (Thin-shell concentration of Gaussian variables (standard fact)). Let X be a standard Gaussian in Rd. Then
Pr ||x|||- va 2 s 2cxp(-t/4).
Claim C.10 (Log-concave distributions satisfy assumptions of Claim C.6). be an isotropic log-concave distribution over R and K be sufficiently large constant depending on those given by Fact C.7. Let r be randomized Boolean function such that EgD [r(x)] 2 (3, and pur)) be such that for all E [d].
p(();: - (EE = 1/d.
Let P be d/2-dimensional linear subspace orthogonal to üu(r), and P be d/2 x matrix whose rows are an orthonormal basis for P. Let Ttrune the truncation of r defined as
|all22
1/K Ind
Ttrune (x) = r())
vd/2
Va/2
Then the following conditions hold:
Bounded mean:
||P FaaDD (x)x]l2 S O(V1/d).
Thin-shell support: Every x for which Ttrune (x) can be nonzero satisfies
||
+
V4/2
10K44/3 tnd
Va/2
LLarge support: Ep-D /Ttuunc (x) 8
28

---

Furthermore, PIæ~D(r(z) # (x)) & O(1/d).
Proof. First we will prove the final inequality,
Pr [r(x) # (trmm(()) S O(1d). a>D
Since the projection of 'D by P is a log-concave distribution over R (Fact B.3), this inequality follows from from Corollary C.8 applied P(D) with & = 1/d. We now prove the other conditions.
Bounded mean: Let
p(Ttrunc)
E' (x) and p(r) = E (x()))) aND
x>D
First we claim that for every i, |p(Trrmnc): - m(rrssl S 1/d. We have E [r())) 1 [r(x)) # Peraue (eruue(>)]]
p(r); ((eerane);
$ (Tteranc); + E|| 1[((x) # Ttruue (x)
S ((rrrune)i + t= 10k Ind
t C Ceeppppdd /d)dt
S (Trernne); +C
8 exp( exp(-ct3/10 /d)dt
1=10Ka//1nd
S (Teruue); + C
u. expl cxpplccuddjd
m)
S (Ferann)); + exp(-(11K c) ((10K d) c (d/c)²
$ (Teruue); + 1/d.
(by setting K sufficiently large)
A symmetric argument lower bounds p(r); by u((erune); 1/d. Now we bound |P (PPp(rerunc)lle We have ||Pp(Pttrunc)ll I SuPue (U, (( Consider unit
vector P. We have
(u, ((Ftrunc) = (u, (((truun) - u(r)) + (u, - M(r) + A(r))
W4
+0
d
d
iE(d
2/vd. d.
Thin-shell support: This follows immediately from the definition of Ptrune-
Large support: This follows immediately from the assumption that (o-w) B and the fact that Pr.- (r(( (r(x) # Ptrume(x)) < O(1/d).
Claim C.11 (Accuracy of the mean estimates). Let S be a set of 10d points drawn frow a distribution D with covariance I4. Let F be a collection of eight (possibly randomized) Boolean functions over Rdd. Then with probability at least 1 - O(d-3) 33, the following holds for all f F and i E [d]:
1 <x 21f(x) - E xzf(x) 1/d.
-
ZET
Proof. By the fact that D has covariance Ia, we have Var(I:) = 1 and Var | by Chebyshev's inequality
Σ 2;) xx)
1/[T],
1
10df
Pr T
E RND
[x+((
Exs(()
0.01d-4
[
T
29

---

Set [T] = 10d"; then the deviation becomes 10d2 TFT a. Union bounding over F and E [d], we have
with probability at least - 3d, all f and satisfy
1 Σ x,f(2) - E xxf(z) 1 T
aND
.ET
Claim C.12 (Accurate partitioning (randomized) sets). Let be a distribution over IR& (-1, such that the R Re-marginal isotropic log-concave. Let s d Let F be the set of eight (possibly randomized) Boolean functions over IR given by RobustIndicator; and ErrorIndicator; (z) 1ly & h;(x)) E [4]. Let WI..... w4 be the weights returned by COMPUTEROUNDINGTTRRES OLDS and ....... JA be the intervals generated by COMPUTECLASSIFEER Then with probabillity at least 1 O()), the following holds for all f and all i [4]:
Pr Kx, u) J(A(()) = Pr [f() =1] wi + O(e). RND
z~D
1/ poly(n). Consider only the functions f E F such that Pr(f(=) = 2 for the others, the statement holds trivially. COMPUTECIASSIFIER estimates the means μ4, u i E [4] of the functions from its sample of size 10d then sets P be linear subspace orthogonal to all of these. By Claim C.11 we have that with probability - (d-33) the mean-accuracy assumption of Claim C. 10 is satisfied. Thus, by Claim 10 the assumptions of Claim C.6 are satisfied with the following parameters:
Proof. First we will claim that each iteration succeeds with probability
B1 O(v1/d)
B2 O(d 1/6 Ind)
B3 = E ((1d))
COMPUTECLASSIFEE then generates uniform random unit vector u P and four intervals J1 JI...J/ J/ of Gaussian volume W1...., W4. By Claim C.6, with high probability over u, the following holds for each Jr:
Pr D~ (+))=
(x, u) E J,} = w, + (33/33 + 32 - = 0
laking the conjunction with the event that f(x) = 1 gives us the desired
Pr (x, u) E JAA(() = 1] = Pr
[f(x) = 1] (w, + 0(=)) I Pr Pr(f(x) = 1] w, O()). z~D
ZND
anD
The failure probability is
(1 (n/33)(nn1///
E 3B2(1 2,2 - 23:)d
53 e3,3((1 232 2,11)
exp
-Ω
In(1/e) B1/Ba)
(1 + o(1) Im(L/E)
(1 o(1))
-S2
e1(1 o(1))
exp
[n(1/e)1++(([))
In(1/))
edd
g4
exp
In(1/s)
1/6 exp (-
By our assumption that > ((d- 1/7), this term is dominated by exp(-Q(dVT)), The total failure probability is dominated by the ((d probability of failure for the mean estimation. Thus, we have that with probability 2 1 - 1/ poly (d), no bad tail events occur, and the guarantee holds for all E and E [4].
The following boosting argument is relevant only when 8 is smaller than this = d failure probability. In each iteration we test the accuracy of the partition by comparing
Pr[[z, u) J, f() 1] to Pr[f(z) = =1]
30

---

for each function f. It suffices for these estimates to be accurate up to additive error. By Chernoff bound, for a test set of size (1lo((1/))/={) all estimates are E-acourate with probability at least 1 - 8² so that after union bounding over all iterations the estimates are still accurate with probability
least 8. Since d 2 the probability that a good partition is not found any of the log(1/6) independent attempts most 2- 1/6) 8. Thus, the total failure probability most 26. 0
C.4 Correctness and complexity of Algorithm 5.
Now will finish the analysis of COMPUTECLASSIFEES restated here for convenience.
Theorem 3.4 (Correctness of Algorithm 5, COMPUTECLASSIFIER, Let 2 d-1/7 and 8, r Let be an e-uccurate local noise sensitivity approximator for degree-k PTFs over R². Let D be distribution over R x {-1,1} such that the R Re-marginal is isotropic and log-concave. Let Rd + IR be polynomial of degree at most satisfying
E
E (1,
Osign [s < 100r +O()),
(5)
Pr
|~| (-1-1,11 ( 10 0.7 S 5(ss.
E
(6)
(a.
Then the algorithm COMPUTECTAASSIFFER(... r,,,, given sample access to and query access to ã. outpus a hypothesis h IR + {-1, 1} such that the following properties hold with probability at least (
(h) <
E 1-11
(erpossign( ())] O(s)
Boundary p.r S Or
The running time and number of queries to é are poly(d 1/E log()/))))
Proof of Theorem 3.4. By Theorem C.1 and the triangle inequality, we have that all e [4] satisfy
(i) Pr(w.)/D (x) # v] S errp (sign(p (p- (.)) + 1or 12).
(ii) EEeD [Robustindicator, (x)] 2 1- O(S (sign(p - t;))
(iii) For every x such that RobustIndicator,(5 = and x' : || z' S r. we have h₂(x²) =
hx(x).
First we will handle the error condition. By Theorem C.2, we have that with probability 1 1 0(6)),
(errp(sign(p t2) + (sr tz), 0.8))
(erro(sign(p - 1))] + O(e).
to [-1]
Thus, we have
Σ SE
Pr [h((2)) vl (x,0)
E (errosign(p- - O(s))
1|-1111
By Claim C.12, then have with probability 2 O(6).
Σ Pr [h,(x) * y (z, u²) J
E (errn(sign(p t))] + O(z).
(a.))D vE[1]
|~| 1
Therefore, applying the definition of h. we have
ch) < En-1-1.jlerr((sign66 t))] O(e).
31

---

Now we analyze the robustness condition. By Theorem C.2, we have that with probability 2 1-0(6).
Σ
wi (siiioo 4)) S +e).
By a Markov bound and the definitions of RobustIndicator and NS, we have the following for each
[[ = Pr P (eigu((p- (.) (1) S 0.1]] = Pr[ (r(0sigo(o- 0.9]
1 Pr (b(x) 0.9/NS(sign(22 4.)) B[(((x)]]
2 NS(iinnn -t).
Thus we have
Σ xE(4]
E [RooustInnicatoo.((1
w;
(x)]
Σ wi (1
g ED (iign 1,,
D
iE(4)
2 1 - Σ
10
ED (
9
iE
2 1 - Orr + E).
By Claim C.12 we then have with probability 2 1 - 5,
Σ E. AND *E
[RobustTndicator (x)) [ n²) J.]] 2 ( +).
We now claim that for each Jr, all with RobustIndicator: away from the interval boundary satisfy the adversarial robustness condition
such that (²), is at least
Vz | x'112 S r and h(x) = h(x²).
Since æ is r away from the interval boundary, all x' such that || - 2ا112 I r satisfy (x',u") E J. so they are also labeled by h4 By Theorem C.I, all a with Robustindicator,fa the robustness condition in hú, so, since they are also r away from the boundary, they satisfy the robustness condition in h. Thus we have
1 satisfy
Boundaryp,,.0 N
Σ vE(4]
E (Robust(nndicator:(s)) [K,, u²) E J.ll) znD
Pr Ka, u²) within of an interval boundary]
x~D
2 -1-0(r+))-01p
where the boundary probability is bounded by O(r) due to Fact B.4. Thus when all subroutines successful, the guarantees of the theorem hold. The total success probability is 2 1 O(5) after union bounding the failure probabilities of all subroutines. This concludes the proof of correctness.
We now analyze the rumning time and query complexity to é. COMPUTEROUNDANGTHRSSSOOO called once. For log(1/8) iterations, it estimates err, NS,, iso; for each of 100/=² rounding thresh- olds I; this step makes (log(( (1/))/=²) queries to á and takes poly(d 1/e log(1/5)) additional time, due the evaluations of the degree-k polynomial p. Then solves linear program of constant size for (100/=2)$ iterations. The total running time and query complexity of COMPUTEROUND. INGTHRESHOLDS are dominated by the first term, which is poly 1/5 log(1/5))-
is
The rest of COMPUTECLASSIFIN repeats log(1/8) times and does the following each repetition:
a) evaluate [ar) * y] and RobustIndicalor, (x) for each E [4] and (ar, y) in M,
b) obtain basis orthogonal to the estimated mean vectors, random unit vector in this space, and partition of the real line into intervals
c) check accuracy of the partition with respect to Stest-
32

---

Each evaluation of 1[h((x) # vi makes one query to á and takes ( time, as it simply calls ROBUSTNESSLCA, which makes one evaluation of degree-k PTF and one call to c. Each evaluation of RoobstIIndicaton (x) makes one query Φ and takes (11) additional time. Thus items (a) and (c) take (O(k) time and queries. For item (b), obtaining the basis takes poly(d) time by Gaussian elimination, and approximating the interval boundaries can be done in poly time by using a numerical s-approximation the error function"
1 VT f e-1/2
erf(()
Overall, the total time and query complexity of COMPUTECLASSIFIER poly(d 1/e log(1/))). as desired.
D Verifiable robustness
In this section we prove that under complexity assumptions, the robustness guarantee of our learning algorithm can be made efficiently verifiable as discussed in Section 1.3. The verifier certifies that point satisfies the robustness condition. We formally state this result:
Corollary D.1 (Deterministic verifiability). If BPP. then there is a learning algorithm B that, given access to labeled samples from a subgaussian isotropic log log-concave distribution, runs in time (0(1/6") log(1/8) and produces a hypothesis h with the following guarantees:
Agnostic approximation: With probability least 1 0()), Pr(x.ii-((((a) + yl S opt O(e), where opt the misclassification error of the best halfspace.
Verifiable robustness: There is verifier that runs in time dō1l/E7) that takes inpul circuit g and a point x E RRd that always rejects if
3e: 1|=12 S and g(z) + g(x + z).
Ifg = h, then with probability at least 06) over the randomness of B, the verifier accepts with probability at least 1 - O E) over D.
use the following fact:
Fact D.2 (Derandomized estimation of Φ). P BPP, then there exists deterministic algorithm running in time do(k) poly(1/e) that takes as input a degree-k PTF f. a radius т, and an input x E Rd and outputs an estimate 61.10r (z) such that (1,10r(I) = 10,100 E.
Proof. Observe that there is a randomized algorithm running in d0(k) /E² time that takes as input threshold t and decides if ( f, succeeding with probability 2 2/3 whenever Φ (2:) + or ( < t - This is the algorithm that samples O(1/=²) points from from.N AN Ia) and evaluates f(x + 10rz) on each them to estimate o; its analysis a Chernoff bound. P BPP, then there
exists a deterministic algorithm for this decision problem also running in time (O(k), (oly)) (1ly(1/s). Since (x) E [0, 1]. we can binary search with log (1/s) iterations to find a such that (x ) t te. O
The learning algorithm is simply ROBUSTLEARN, augmented to provide some extra information, with the estimates of & provided by the deterministic estimator. The verifier checks that the hy- pothesis matches "template:" this will prove that the unknown circuit fact of the form that ROBUSTLEARN is supposed to return, and for which our correctness analysis holds. Since for any hypothesis matching the template, any point x for which ((x) < 0.1 satisfies the robustness condition, the verifier will then deterninistically estimate ((r).
We define the template below:
Such numerical approximations standard and take poly(1/e) time. Altematively, could randomized algorithm that takes poly samples from the gaussian and uses them to approximate the relevant values w.. Note that we presented the w; 's as exact for conciseness, but since Claim C.12 already guarantees only an ((e) accurate partition, we see that an additional e error in the estimation of the w, is asymptotically irrelevant.
33

---

Lemma D.3 (Hypothesis template). Fix set B of basis functions for the set of degree-k polymomials over R There an algorithm COMPILE that takes as input a |B -length vector of real-valued coefficients, real numbers t,....,,, a unit vector u E R., and real numbers 01 C2 c3. For each i [4], let the PTF h4 be defined
(
h₂(z)= = sign
vbb
BE
Let the intervals Ji,..., JA be the partition of the real line induced by c1, C2,02,09 Cz. The algorithm outputs a circuit computing the hypothesis
h(x))=
Σ ROBUSTNESSL.CA r,, [K,, u) E Jt]-
It also outputs each of the PTFs h1...., h4- The running time is (Ok).
Proof. Observe that there is a deterministic algorithm running in do(k) time that takes as input all of the given parameters and the input x, and evaluates h(x)), using the deterministic implementation of & in ROBUSTNESSLCA. Therefore there is circuit of size do(k) with the same behavior. The algorithm COMPILE takes this circuit and hardcodes all the input parameters except for z, then outputs the resulting circuit. This takes time d0()) and the output is a circuit that takes z as input and evaluates hxx). By the same argument, (k() time COMPILE can also output the PTFs , h4.
We include pseudocode of the verifier below. For brevity we will refer to the package of data taken as input by COMPILE as data.
Algorithm 6 VERIFY x, e, data):
I: Input: circuit point E IR", robustness radius r, error tolerance s, hypothesis parameters data
2: h. hi, hs, h4 + COMPILE(data)
3: if & then return reject.
4: Let u be the unit vector in data and , Jg be the partition induced by the interval boundaries
C1, C22 Cz in data.
5: Let be the interval such that (z, u) E Jr.
6: if 10,, (x) > 0.1 then return reject.
7: if (x,, u) cgl S for any of the interval boundaries C₁2 C22 C3 data then return reject,
8: return accept.
Proof of Corollary D.I. The learning algorithm B is ROBUSTLEARN, but with the following modifi- cation: records its parameters in data package, outputs COMPILE((Ata) as its final hypothesis, and outputs data as well. By the guarantees of ROBUSTLEARN, with probability at least 1 O satisfies the agnostic approximation guarantee. When VERIFY is called on the output h of since is the output of COMPILE, it always passes the first check. By inspecting the proof of Theorem C. we and is at least distance from thus the verifier rejects all points such that on, (x) > 0.1. Since it also rejects if & is within r of a boundary, all accepted points satisfy the robustness condition. Furthermore, by inspecting the proofs of Theorem 3.4 and Theorem C.I, we see that whenever ROBUSTLEARN succeeds (probability - O())), we have that at least 1 - Orr + e) fraction of points ~ D satisfy dn, (I) 0.1 and are at least away from any boundary, and are thus verifiably robust. Thus, the verifiable robustness guarantee holds.
see that in fact robustness holds for all such that 6b, (a:) < 0.1
each of the interval boundaries. By Fact D.2, we have 16s, (x) 6h, (x))
The running time of COMPILE for PTFs degree Ō(1/=²) is (01//²²) (Lemma D.3). The running time of VERIFY is this plus the running time of the deterministic estimator for 6, which is also (11/=²) (Fact D.2). Thus the total running time is ((1/=²))
34

---

Remark D.4. We note that without the assumption that P P BPP, there is randomized analogue of Corollary D.1 where the user compiles the final hypothesis, rather than verifying the one provided by ROBUSTLEARD Rather than outputting circuit h, ROBUSTI can just output data, and the user can COMPILE it with randomized implementation of ROBUSTNESSLCA in time d0(//")) -log(1/0)) in which case the soundness of the verifier holds with probability - 8 for the compiled hypothesis.
E Uniform convergence claims
Finally, we will need to following observation about the uniform convergence fo empirical approxi- mations of local noise sensitivity é. First, we need the following fact:
Fact E.1 ([VW97], also see lecture notes [Duc23]). A function class C of VC dimension A and every distribution Do. there is an E-cOver H of C of size at most == (O()))s)O(A) L.e H is discrete subset of C of size B and for every f in C we have h in H for which
Prz=Dolf(z) + h(z)] S
Claim E.2. Let C be the class of degree-k PTFs over RR. let D be probability distribution over R and let E [0, 1] be fixed. Then, for some constant C, if S is a collection of (dt /E) log 1/8 i.i.d. examples from D, then with probability at least 1 (6).
max SEC
Ex [x)] F
O(E))
(36)
Proof. We now use Fact E.I. For us, is the class of degree-k PTFs, and we have A dO(k)
Taking the distribution Do to be an equal-weight mixture of (i) the distribution D in the premise of this claim and (ii) the convolution of D with the normal distribution (00 nyla) we see that for every f in C there is h in H for which"
PFe-D(f(a) + M()] S 25,
(37)
Pr D (0.
[f + n=) * h(x n=)] < 2e,
(38)
which via the definition of & and the triangle inequality implies that
(Drm(()))))))) (n.n(()))
E EE-D(orn(T)] - Bxnplónnn (x)] 5 EN-D
S <2 - h(xx)l + E
[I + 112) - h(x + m=)l] S O(s). (39)
anD z~N(0.1a)
By the standard Hoeffding bound, since o and & are always in [0, 1], with probability 1 - 6/2 for every h in H we have
Ez- Ez-s(ón.(()) EZ~D (dn,(()))))) S Olog(( (6)) S E,
(40)
VIS
where the last step for both inequalities follows by substituting HH) [S), A and taking C' to be a sufficiently large absolute constant. We also know that with for sufficiently large absolute constant C, with probability 1 8 the set S satisfies Fact E.6, which means that:
sup PPr-~sifia # f2(=)] - Pl # f2(=)] S O(s). fi.fEC
(41)
From the above, we can also conclude that with probability 8 over S for every pair f1, f2 in C we have the following:
Pr E>S (0.1a)
[fi( + n2) * fa(2 + nz)] Pr
anD N(
[fí( + m7) + f2(2 œ + n2)l s
E
((,,t
Prans[fi( + m2) + fe(2 + nz)l - Pra-Dlfih + n2) + fz(1 + n2)] S <
<O(e) by defining fs(a) fa n=), fa()) := fa(z ny), observing fa and f4 are also degree PTTss and using Equition (41)
(42)
Note that the emror Do is the average of the emors in the inequalities below.
35

---

Using the definition of Φ. the triangle inequality, and Equations 41 and 42 we also see that
(Em-sloh.n()) - Exwglos, 1 2 PP + [()) + Pr
anS 11(x + 112) + f(x nz)] 5 z~)(
2Prz-Dlh(e) [1(x) + [())] + Pr anD [h(x + 1/2 + f(x + nz)] S O(e), (43) z~N((0,1a)
where in the last step we substituted Equation (37) and Equation (38). Finally, we put all the inequalities together. By combining the triangle inequality with Equations 39, 40 and 43 we derive Equation (36).
Claim E.3. Let C be the class of degree-k PTFs over Rd let be a probability distribution over Rd and let E [0, 1] be fixed. Then, for some constant C, if S is a collection of (d /e) log 1/8 i.i.d. examples from D, then with probability at least 1 (5)) for every polynomial p it holds that
Pr FRee--1.1(0simnoote)--o.. 2 0.7| < Pr [ 1.11 (isisn(oo- 2 0.67] + +(()) (44) a>D
wnD
Proof. Let Celipped be the class of degree-k clipped polynomials, i.e. functions polipped R - [-1,1] of the form
if p(x) 21
clipped (x)
if p(z) -1 otherwise
p(z)
where p a degree-k polynomial. We first argue the following
Observation E.4. For any distribution Do over Rd, there a subset of Celipped of size (O(1)/e)0ld"/)) /e), i.e. such that for every clipped in Colipped we have
min E Dolppolpppppee (pcppppd (z) (<))]]]<0(( kg
(45)
Proof. We form H by considering an 2-nntt HiTr for degree-2k PTFs, and taking H to consist of functions of the form
h(x) -E(-1.-1te-1122.....
Σ
T f+(x),
where each (z) is some function in fx) By Fact E.I, we see that Hpir has size (O(1)/s)o(d)) and therefore (by a counting argument) the size of H defined above is indeed (0(1)/a)0ld) /e)
We can write for every x and plipped in Celipped the following inequality:
Σ
T. 1 dippedd (x) (T, + +e] S plipped (x) 5
16(-1,-1t,-112-
+1}
Σ
(T (pctippe E (T, + +e]], (46)
7E(-1,-1te,- 11.......
we observe that each indicator 1 [p (z) (T, t + e]] equals a degree- 2k polynomial threshold function, and therefore there is some fr in HPTE for which
Egg-D D. [1ppdl)p)d()))) (x) (T, + =]] f s O
which substituted into Equation (46) allows us to conclude that
En Da
y (lipped
Σ
T. (xx)
S <0(s),
rE(-1,-1+s,
which concludes the proof that for pliipedd in Celipped we have h Rdd in H for which Equation (45) holds.
36

---

We finish the proof of the observation, by resolving one last issue: as defined the set H is not a subset of Celipped However, we consider the set H' consisting of functions f of the form
H' {f argminnEy-Dooll (19(() h(=)]]] h E H.
gE
then we see by the triangle inequality that H' still satisfies Equation (45), has size of at most | and H' a subset of Celipped
We continue the proof of Claim E.3 We can wite:
Piie----l(Piguuppss))-oooa = P [|igg((((<) t) + sign(p(x + +z) - t)1
p pelipped (x) - pelipped (x + n=)
E,-N(o,1))
Oprined ,y (x) (47)
2
We will overload the notation for ø and define Systired (2) to be the expression above. We further define the following auxiliary quantity:
o yermou ., (2) - 0.67
Sptiered sy (x)
if o yyiieed .n (z) 2 0.7 if o f., (x)
100 (Oyddtped .,(2), 0.67)
(0.67,0.7)
By construction, the function satísfies the following properties for every x;
1 1cngetinees (,()) 2 0.67] I Sprinon .,(x)) S 1 10 .y ,,(x) 0.7]
(48)
Spgtto (x) cippes
p: mn (z) S 0())
/ sir m (x) 0 cirood .n (z)
(49)
Taking the distribution Da to be equal-weight mixture of (i) the distribution D in the premise of this claim and (ii) the convolution of with the normal distribution (0, nTaa) we see that for every pilipped in Celiped there is h in H for which"
Pra D
plpp cpppeed (x) - h(x) s 2c,
(50)
DnD (0,,aa
Up clipped (x + nz) h(2 + m=>i $ 2E,
(51)
which via the definition of & for clipped polynomials and the triangle inequality implies that
Egg pop (x)] ExwDlon olo.. (z)] S ExWD
@operoee (x) (z),)(z))
< 2 E El (z) - h[=)]] +E anD (0.Jaa)
clolloood (x + n2) - h(x + m2)ll & O()). (52)
Together with Equation (49), this implies that
O - -onn(()) S O(e). (53)
EEwD in (z)] EE=D (x), S 0(1) EAND
By the standard Hoeffding bound, since & and & are always in [0, 1), with probability 1 5/2 for every h in H we have
Ex (x). - EEZED [n,)(()]]
S Olog((
S e,
(54)
v Sis
1
EzwsiEh. EZND (x)]
< Oloog( H| S E,
(55)
VIST
where the last step for both incqualities follows by substituting [l], [S]. A and taking C be sufficiently large absolute constant.
Note that the enror Do is the average of the two emror in the inequalities below.
37

---

We observe that Fact E.6 and Equation (46) together imply that
sup
Exwsl clippd
(x)
P2
clipped
(x) Egw De clipped (2))
(x) P2
clipped
(x)
- O(s).
Cirpal Cirped ECdlopes 122
(56)
From the above, we can also conclude that with probability 1 - å over S for every pair clipped in Celipped we have the following:
clipped
P2
P1
clipped
(x + 112)== - p1 clipped
(x 122)
n2) -E
x~N(0.1a) [pp clipped (x + nz) P2
clipped
(x + m12
5
((,
E [
Egws plipped (x + 112) - p2 (x + nz) Ex D pilipodd (ar + n=) - p2 (x + n=) S 50(s)
clipped
elipped
[O(c) by defining plpppll
(a) = Pt. ( (ar 122), P4 and using Equation (56)
(x) p2 (ar + q=).
(57)
We now come back to the setting of Equation (50). p lipped is a function in Celipped and h in H satisfies Equation (50). Using the definition of Φ. the triangle inequality, and Equations 56 and 57 also that
E E sonns - si ppp .n)
(1))
2 Pr [(((x) - p clippdd (x) Pr Pr
(m)( |1(s + nz) pelipeed (xr + +=>>) s
PPrzDDlh(e (/(=> # f(x)] + Pr
reD [h(x + nz) # f(x + n=)l & O(s), (58) s>o((
where in the last step substituted Equation (50) and Equation (51). By Equation 49, we that Ea E (x)] - O (59)
[E>s((h. - -e s O(1) |
Analogously, by combining the triangle inequality with Equations 53, 55 and we derive the following:
max FEC
(ersskEr.n1)))) - Ee- s O(s),
(60)
which together with Equation (48) and Equation (47) implies Equation (44).
The following claims follow from VC theory (see e.g. [VDVW09] and the references therein):
Fact E.5 (Generalization bound from VC dimension). Let be concept class and D be a distribution over Rd. For some sufficiently large absolute constant C, the following is true. With probability least 1 å over a sample of i.i.d. samples from D, with |S] C. VC(C) (ogg(1/)//= the following holds:
sup (err = fec
Fact E.6. Let be a concept class with VC dimension A and D) be distribution Rd. For sufficiently large absolute constant C, let S be collection of CA Then, the following holds with probability least 1 -
z log(1/8) i.i.d. examples from D.
sup f.J
(P # f2(2)] - Pr PraDDffi (1) f2(2)] s (s)).
(61)
Equation (46) tells that the difference p1 P2 be e-approximated in L.p norm by a function of the form Σre(- 22-e-+, - -++e....+2
T [x)),, where each f+ a degree-2k PTF, Then. Fact E.6 together with triangle inequality tells us that the inequality above holds when C' is sufficiently large absolute constant.
38

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: Our work focuses on robustly learning linear classifiers under isotropic sub- gaussian log-concave marginals, and our introduction and abstract reflect this.
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 as is clear that these goals attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations the work performed by the authors?
Answer: [Yes]
Justification: Our algorithm only works under strong distributional assumption, and it produces hypothesis that not linear classifier. These limitations are thoroughly discussed in the introduction.
Guidelines:
The answer NA means that the paper has limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect the scope of the claims made, e.g., if the approach was only tested on a few datasets or with few runs. In general, empirical results often depend implicit assumptions, which should be articulated.
The authors should reflect the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low or images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory assumptions and prool's
Question: For each theoretical result, does the paper provide the full of assumptions and complete (and correct) proof?
39

---

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

---

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

---

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

---

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

---

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

---

Question: Does the paper describe the usage of LLMs if it is important, original, or non-standard component of the core methods this research? Note that if the LLM used only for writing, editing, or formatting purposes and does not impact the core methodology, scientific rigorousness, or originality of the research, declaration is not required.
Answer: [NA]
Justification: LLMs used only for minor suggestion regarding LaTeX.
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 LLM policy (https //tp:///eeuupppeeeeee 220p:///////ooooeeeeee////////// for what should or should not be described.
45


Reviews:
[{"review_id": "Yhi6xNnqd7", "reviewer": "Reviewer_7bYh", "summary": "This paper presents an efficient algorithm for learning halfspaces that are robust against adversarial perturbations. That is, the probability that a random example is within distance $r$ of its closest point on the other side of the halfspace (called “boundary volume”) scales linearly with $r$. The method is designed for data from subgaussian, isotropic, log-concave distributions. While standard methods like polynomial regression are efficient, they can yield non-robust polynomial threshold functions (PTFs), which also constitutes an improper learner. This new algorithm overcomes the former limitation, producing a classifier with a guaranteed boundary volume of $O(r+\\epsilon)$ and a misclassification error of opt+$O(\\epsilon)$, where opt denotes the optimal misclassification error. The time and sample complexity of $d^{\\tilde{O}(1/\\epsilon^2)}$ matches that of the state-of-the-art non-robust algorithms. Technical contributions of the paper include performing $\\ell_1$-error polynomial regression under noise sensitivity constraints, a randomized partitioning and rounding method designed to find a classifier that has 3 desired properties simultaneously and finally a local computation algorithm for correction. Specifically, the latter algorithm receives classification queries for a polynomial threshold function and answers according to a robust classifier that is not too far from it. Lastly, the paper introduces the concept of verifiable robustness, showing that under the assumption P=BPP, the output model's robustness can be efficiently and deterministically checked (or with some error probability without making the assumption).\n  Minor comment: \nPage 6: footnote 3 seems incomplete.", "questions": "In theorem 1.1, your guarantees rely on the input distribution being subgaussian, isotropic, and log-concave. How sensitive do you expect the algorithm's performance to be if these assumptions are slightly violated? Have you considered extending these results to more general distributions, perhaps with weaker guarantees?", "limitations": "yes", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 4, "clarity": 3, "significance": 4, "originality": 3, "strengths_and_weaknesses": "The paper introduces novel techniques to obtain a robust version of a fundamental problem in machine learning, without sacrificing sample complexity or computational efficiency. The authors are still using an improper learning algorithm, which is in line with prior work, while a proper learning algorithm would be preferable in general.", "was_revised": true, "final_justification": "I am satisfied with the answers to my questions by the reviewers and I am therefore keeping my recommendation for acceptance.", "rebuttal": "Thank you for pointing out the incomplete footnote. It should say “The algorithm of [Dan15] also applies only to the Gaussian distribution, and not to general sub-Gaussian log-concave distributions.”\n\nIndeed improperness is a limitation of our algorithm. Agnostic proper learning in this setting is a longstanding open problem. \n\nSome distributional assumptions are necessary to evade NP-hardness results, and furthermore some assumptions are necessary for the class of halfspaces itself to be adversarially robust – without anticoncentration, a distribution could place a lot of mass on the classification boundary.\n\nThe assumption that the distribution is isotropic is not crucial: if the covariance matrix has all eigenvalues between a pair of positive constants $C_1$ and $C_2$, one can perform a change basis and reduce the problem to the isotropic case (while preserving adversarial robustness). If covariance has eigenvalues very close to zero, halfspaces stop being adversarially robust under such distributions.\n\nRegarding the other assumptions, not much is known about learning halfspaces without these assumptions even in the non-robust improper setting, and not much is known about how learning algorithms perform when the assumptions are slightly violated. If log-concavity is assumed but subgaussianity is not assumed, the best run-time given in [KKMS ‘08] is doubly exponential in $1/\\epsilon$ (which is much slower than the algorithms on which our work focuses). No non-trivial algorithms are known if only subgaussianity is assumed. \n\nThe question of slightly relaxing the log-concavity assumption is currently an active area of research, but is not fully understood even for regular (non-robust) agnostic learning. Though there are algorithms that handle distributions $\\epsilon$-close in TV distance to specific distributions [Goel, Shetty, Stavropoulos, Vasilyan NeurIPS 2024], there is no non-trivial algorithm known that achieves error $opt+O(\\epsilon)$ for all distributions $\\epsilon$-close to log-concave in TV distance (outside of the brute-force $2^d$ time algorithms)."}, {"review_id": "VlKFoAhNGE", "reviewer": "Reviewer_3HgY", "summary": "A problem of learning half spaces is considered here. The requirements on the learning algorithm are twofold, first, the learned classifier has larger error than the best halfspace classifier by at most $\\epsilon$, and second, the volume of the classifier r-boundary is  $O(r)$. The classifiers r-boundary volume is defined as the probability (over the data distribution) that there is for an input x another point y such that ||x-y|| < r and h(x) and h(y) differ.\n\nFirst, relaxed learner produces $1/\\epsilon^2$-degree polynomial thresholding hypotheses (somewhat uniformly) robust to random (not necessarily adversarial) perturbations via convex programming. Then, a local corrector is used; roughly speaking, it computes probability that a random perturbation changes decision of the classifier. If this probability is high, the label is flipped.\n\nThe derived sample complexity then almost matches the sample complexity of the non-robust learning up to polylog factors in the exponent (the sample complexity is exponential in both cases, thus the exponential polylog factor differences are \"fine\").", "questions": "-", "limitations": "-", "rating": 4, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 2, "originality": 2, "strengths_and_weaknesses": "The paper is very technical but it somewhat successfully tries to be accessible. The considered problem is pretty niche without direct applications in the practice of adversarial robustness (for instance, because of the exponential sample complexity), but it solves the considered problem within a reasonable completeness. The presented techniques seem to be often borrowed from other works, but I am not able to comment if the applications are inovative or straightforward. Some technical novelty is clearly present.", "was_revised": true, "final_justification": "-", "rebuttal": "Indeed our running time is exponential in $1/\\epsilon$, as is all previous work on learning halfspaces up to error $opt+\\epsilon$, and thus it is meant for settings where $d$ is the limiting parameter. We note that prior to our work, no algorithm with run-time better than $2^{\\Omega(d)}$ was known for the task we consider.\n\nAn exponential dependence on $1/\\epsilon^2$ in the running time is believed to be necessary due to the statistical query lower bound for agnostically learning halfspaces [Diakonikolas, Kane, Pittas, Zarifis ‘21] which is also exponential in $1/\\epsilon^2$. There are also run-time lower bounds based on commonly accepted cryptographic hardness assumptions [Diakonikolas, Kane, Ren ICML 2023].\n\nRegarding the novelty of our techniques:\n- The use of low-degree approximating polynomials for learning is a well-established technique; however this work introduces a proxy for adversarial robustness and shows that polynomial optimization under this constraint is feasible. This type of analysis is new in this work.\n- The use of local correction for learning continues a line of work that is a few years old (introduced in [LRV22]). Previous work uses local correction only to ensure monotonicity of a hypothesis; this is the first application of this technique outside of that setting. \n- The randomized partitioning and rounding strategy is, to the best of our knowledge, new in this work."}, {"review_id": "Io05avuIHP", "reviewer": "Reviewer_d9eS", "summary": "This paper presents an efficient algorithm for adversarially robust learning of halfspaces under subgaussian isotropic log-concave distributions. The algorithm achieves both low classification error and small boundary volume, ensuring robustness to adversarial perturbations. The authors build on polynomial regression techniques, augmenting them with structured rounding and local correction steps to ensure both robustness and efficiency. The results match the best known runtimes for non-robust agnostic learning and provide verifiable robustness guarantees.", "questions": "1. The work focuses on subgaussian isotropic log-concave distributions. It would be helpful to understand how critical these assumptions are. Have the authors considered whether the approach or guarantees extend to broader families of distributions? Even a brief discussion on the feasibility or limitations of such relaxations would add value.\n\n2. It would be interesting to see how the proposed techniques perform beyond the theoretical setting, e.g., on synthetic or real data with more complex structure. Experiments validating the theoretical guarantees or exploring tradeoffs in practice would strengthen the work.\n\n3. Another promising direction could be applying the proposed correction and smoothing techniques to existing robust models (e.g., adversarially trained networks). For instance, could the smoothing procedure help improve or measure robustness in practical deep learning models?", "limitations": "yes.", "rating": 4, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 4, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths:\n\nClarity: The paper is exceptionally well-written and clearly structured. The technical content is explained with clarity, and the motivation behind each algorithmic step is easy to follow. The coverage of related work is thorough and positions the contribution well in the context of existing literature.\n\nSignificance and Originality: The combination of noise-sensitivity-aware learning, randomized partitioning, and local correction for achieving robust classification is a compelling and original approach. The contribution is clearly stated and supported by theoretical analysis.\n\nWeaknesses:\nOne point that could be elaborated is the transition from the standard worst-case adversarial perturbation model (expressed via boundary volume) to average-case robustness notions like noise sensitivity. The intuitive and technical connection between the two robustness notions could benefit from a more explicit discussion, particularly early in the paper (e.g., Section 1.2). Making this bridge more transparent would improve accessibility for readers less familiar with these distinct robustness perspectives.", "was_revised": true, "final_justification": "In the rebuttal, the authors agreed adding the discussion I recommended for the local and global noise sensitivity. \n\nRegarding my questions, I got a sufficient answer for the first question. For 2 and 3, the authors left further experiments for future work. In my opinion the paper can benefit from some experiments, but it introduce interesting algorithm and theoretical analysis that can stand for its own.", "rebuttal": "Thank you for suggesting a more thorough discussion of the relationship between adversarial robustness and noise sensitivity. Intuitively, a function can have low global noise sensitivity and not be adversarially robust, when the classification boundary lies near many “isolated” points scattered throughout the domain. Each such isolated region has high local noise sensitivity; thus by using local noise sensitivity as the proxy for local correction, we eliminate these regions. We will add a discussion of this to the final version of this paper.\n\nRegarding Question 1, we repeat the discussion given in response to reviewer 7bYh:\n\nSome distributional assumptions are necessary to evade NP-hardness results, and furthermore some assumptions are necessary for the class of halfspaces itself to be adversarially robust – without anticoncentration, a distribution could place a lot of mass on the classification boundary.\n\nThe assumption that the distribution is isotropic is not crucial: if the covariance matrix has all eigenvalues between a pair of positive constants $C_1$ and $C_2$, one can perform a change basis and reduce the problem to the isotropic case (while preserving adversarial robustness). If covariance has eigenvalues very close to zero, halfspaces stop being adversarially robust under such distributions.\n\nRegarding the other assumptions, not much is known about learning halfspaces without these assumptions even in the non-robust improper setting, and not much is known about how learning algorithms perform when the assumptions are slightly violated. If log-concavity is assumed but subgaussianity is not assumed, the best run-time given in [KKMS ‘08] is doubly exponential in $1/\\epsilon$ (which is much slower than the algorithms on which our work focuses). No non-trivial algorithms are known if only sub-Gaussianity is assumed.\n\nRegarding Questions 2 and 3, we agree that experimental results would be interesting and consider this an avenue for future work. Analyzing the effects of local correction on other models is an interesting direction for future work as well."}, {"review_id": "G98BsyFZd6", "reviewer": "Reviewer_mppR", "summary": "This paper considers the problem of agnostically learning halfspaces. That is given any Boolean function f over a well behaved (subgaussian and logconcave in this case) distribution D one wants to learn a hypothesis h so that Pr_{x sim D}(h(x) neq f(x)) <= OPT +eps, where OPT is the error of the best possible halfspace approximator. This can be done in d^O~(1/eps^2) samples using the L1 regression algorithm, which returns a hypothesis of a low degree PTF. On the other hand while the best-approximating halfspace is robust against adversarial examples (in the sense that for a random input x the probability that there is a nearby input y with |x-y| < r, with h(x) neq h(y) is small (O(r)), the PTF hypothesis may well not satisfy this. This paper develops techniques to learn hypothesis that both achieve the agnostic learning error guarantee but also satisfy this kind of adversarial robustness.\n\nThe basic idea seems to be the following:\nThe L1 regression algorithm uses linear programming to find a degree k (for k some O~(1/eps^2)) polynomial minimizing the empirical L1 loss E[|p(x)-f(x)|]. We would like to also add a constraint along the lines of E_x[ max_{|y-x|<r} |p(x)-p(y)| ] = O(r), which would ensure the kind of robustness that we want. Unfortunately, the maximization cannot be efficiently solved here. Instead, they replace this with a proxy E_{z ~ N(0,r*I)}[|p(x)-p(x+z)|], which can be efficiently approximated via sampling. It is not hard to show (using standard constructions) that there are polynomials that get OPT+eps error while simultaneously keeping this notion of noise sensitivity small.\n\nBy thresholding p, one obtains a boolean function with appropriate error and small \"noise sensitivity\" (i.e. probability that h(x) neq h(x+z) where x ~ D and z ~ N(0,r*I)). From here they say that a point x is isolated if Pr_z(h(x) neq h(x+z)) is large. It is then not hard to show that if two nearby points have different values of f, then at least one of them must be isolated. It can then be shown that flipping the value of h at all isolated points gives rise to a function with appropriately good adversarial robustness assuming that there are not too many points with modestly high noise sensitivity. To ensure that this doesn't flip too many points, one needs to add another constraint to the convex program to ensure that not too many points are isolated, however this is doable without affecting satisfiability.\n\nOne final issue is that the thresholding for p must be randomized and *on average* the total error is at most OPT+eps and *on average* the adversarial robustness is O(r+eps), but there is no guarantee that these are satisfied simultaneously. Fortunately, one can find only a few different thresholds that if averaged achieve this and by piecing the resulting functions together can obtain something appropriate.\n\nEssentially all of the proofs were in the appendices so I did not read them in detail (NOTE TO THE PC: THIS IS A TERRIBLE SYSTEM THAT FORCES PEOPLE TO WRITE WORSE PAPERS THAT CANNOT BE CHECKED FOR CORRECTNESS ANYWAY WITHOUT READING THE EXTRA MATERIAL), but I did read enough to convince myself that the main results could be proved along the lines suggested.", "questions": "The organization of the introduction should be rethought in order to not have to rely so much on the use of terms that have not yet been properly defined.", "limitations": "Yes", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 2, "significance": 2, "originality": 3, "strengths_and_weaknesses": "Strengths:\n* This seems like an interesting new problem direction\n* The paper introduces some non-trivial new technical ideas\n\nWeaknesses:\n* My biggest issue here is presentational. Many of the main results are introduced *before* the terminology necessary to make sense of them. This is especially bad as they use terms like \"noise sensitivity\" in non-standard ways. This makes it very hard to follow the introduction without reading it twice. The authors should put more thought into how to organize the introduction so that it is readable.\n* I also worry some about the more general applicability of these ideas. The notion of noise sensitivity that they introduce seems to work well for functions that essentially depend on only a few directions, but I worry that for even slightly more complicated functions it will fail badly as the distribution of x and x+z are very far from each other. For example the function 1{|x| > sqrt{d}(1+delta)} will have noise sensitivity almost 1 at almost all Gaussian inputs x, suggesting that this technique has little hope of success to generalize to degree-2 threshold functions.", "was_revised": true, "final_justification": "I am torn between ratings of 4 and 5 here.\n\nThis is a nice result and my main specific issues were presentational which the authors will (hopefully) fix. However, I do not think that I can justify this paper has having a \"high impact on at least one sub-area of AI or moderate-to-high impact on more than one area of AI\" (realistically, I feel like the impact of this paper is going to be that it will lead to a handful of followup works and be cited a couple dozen times additionally by people who just want to say that this paper had some theoretical results about this issue), as required by the description of the 5 rating. So, despite pushing the limits of the \"use sparingly\" instruction, I believe I have to keep my official rating at a 4.", "rebuttal": "Thank you for suggesting that the introduction be reorganized for clarity. In the final version of this paper, we will state our definitions of isolation probability and noise sensitivity early in the technical overview so that it can be self-contained. We can also use an alternative term such as “perturbation sensitivity” to avoid confusion between our notion and the standard definition of noise sensitivity.\n\nThe current work focuses on the highly natural and basic class of halfspaces. Halfspaces are a fundamental class of functions, and there has been a large number of works that exclusively focus on this class of functions. Historically, algorithms designed for halfspaces have frequently yielded algorithms for further hypothesis classes with further technical work, but for this paper we did not directly aim to develop algorithms for other hypothesis classes.\n\nOne generalization we had in mind was simple polytopes, which have low boundary volume and low noise sensitivity in the sense presented in this paper. Currently, robustly learning even intersections of two halfspaces remains an open problem, and we think that techniques similar to ours may be useful for this problem.\n\nWe agree that the class of low-degree PTFs are a natural target for future work. It is correct that using our definition of local noise sensitivity there is a large volume of points for which the local noise sensitivity is large. However, one could potentially try to sidestep this by considering a noise distribution that uses rescaling similar to the more standard Ornstein–Uhlenbeck process, together with ideas presented in this work."}, {"review_id": "zKnyqzlOtO", "reviewer": "Reviewer_2jUf", "summary": "This paper presents a novel and efficient algorithm for agnostically learning linear separators (halfspaces) under the assumption that the data's marginal distribution is isotropic and log-concave. The learned hypothesis is constructed from a Polynomial Threshold Function (PTF).\n\nThe paper makes two primary contributions:\n1.  **Adversarial Robustness:** The algorithm produces a classifier that is provably robust against adversarial perturbations. This is formalized by guaranteeing a small \"boundary volume\" ($O(r+\\epsilon)$ for a perturbation radius $r$), meaning that for most inputs, small perturbations do not cause a misclassification. This robustness is achieved while matching the optimal classification error ($opt+O(\\epsilon)$) and the state-of-the-art sample complexity ($d^{\\tilde{O}(1/\\epsilon^2)}$) of the best *non-robust* learning algorithms for this problem.\n2.  **Verifiable Robustness:** Under the standard complexity assumption $P=BPP$, the paper provides an efficient, deterministic verifier. This allows a user to certify that any specific input point is robustly classified by the learned hypothesis, addressing the practical problem of trusting models from untrusted sources.", "questions": "1.  Regarding verifiable robustness and the $P=BPP$ assumption:\n    - The name for Corollary 1.5, \"Deterministic robustness,\" is a bit confusing. Since the robustness guarantee for the hypothesis still holds probabilistically over the data distribution, would \"Deterministic Verifiability\" be a more accurate term? The key deterministic part seems to be the verifier itself, which can check any given point without randomness.\n    - There appears to be a minor inconsistency in the presentation of Algorithm 6 (VERIFY). The input description on line 1 of the algorithm box mentions taking a point $x$ and an error tolerance $\\epsilon$, but the function signature at the top of the box is `VERIFY(g, r, eps, data)`. Could the authors clarify the intended signature and inputs?\n    - Are consecutive runs of the verifier on different points $x_1$ and $x_2$ independent? It seems they are in the $P=BPP$ setting, since the verifier is deterministic. Does this independence still hold for the randomized verifier mentioned in Remark D.4, or does the analysis change given that the hypothesis itself is constructed with randomness?\n\n2.  The assumption $\\epsilon \\ge d^{-1/7}$ in Theorem 3.1 is a key technical condition. Could the authors add a brief remark explaining where in the proof this is necessary (it seems to be for the concentration of random projections in Claim C.6) and whether it is likely a limitation of the current analysis or potentially fundamental to the partitioning technique?", "limitations": "Yes", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 4, "clarity": 4, "significance": 3, "originality": 3, "strengths_and_weaknesses": "### Strengths\n\nThis paper presents a theoretical advance in robust learning, with clean technical insights and outstanding clarity.\n\n- **Significance and Originality:** The paper addresses a core challenge in robustness: designing efficient learners that are provably robust. It gives the first algorithm to efficiently and robustly learn halfspaces in the agnostic setting under general log-concave distributions, matching the error guarantees and sample complexities of non-robust learners. Establishing _verifiable robustness_ is practically important for developing certifiably safe machine learning systems.\n    \n- **Technical Quality:** The technical contribution is deep, innovative, and very well-executed. The approach combines three key components, each introducing new ideas:\n    \n    1. Constrained Polynomial Regression: The learner fits a polynomial under convex constraints that enforce low noise sensitivity and isolation probability—critical for robustness.\n        \n    2. Structured Rounding and Partitioning: The real-valued polynomial is converted to a Boolean classifier using a randomized mixture (via Carathéodory’s theorem and LP) that preserves error and robustness. This mixture induces a partition with low boundary complexity.\n        \n    3. Local Correction: A final smoothing step turns a low-sensitivity classifier into one that is certifiably robust to adversarial perturbations.\n        \n    \n- **Clarity:** The paper is exceptionally well-written. The introduction clearly motivates the problem and outlines the solution, while the technical sections provide a detailed and accessible analysis.\n    \n---\n### Weaknesses\n\nThis is a very strong submission, but a few presentation details could be improved:\n\n- The role of proper learning in the introduction could be clarified. Line 37 frames proper learning as a robustness benchmark, but it is not immediately clear that the proposed algorithm is _improper_. Since efficient proper agnostic learning remains an open problem, it would help to state explicitly and early that the paper achieves halfspace-level robustness without giving a proper learning algorithm.\n    \n- The informal versions of the main theorems (1.1 and 1.4) should reflect that the guarantees are probabilistic. Phrasing the results as holding “with high probability” would better align with the formal statements (Theorems 3.1 and 3.4). Adding forward references would also improve navigability.", "was_revised": true, "final_justification": "I find the technical parts of the paper well-written and only the introduction needs improvement, so the presentational issue seems minor to me (in contrast to another reviewer). The result is strong, so I maintain my positive score.", "rebuttal": "Thank you for suggesting that we mention that our algorithm is improper earlier in the introduction, add “with high probability” and forward references to the improper statements, and change the name “deterministic robustness” to “deterministic verifiability.” We will address these points in the final version of this paper.\n\nThank you for pointing out as well that the function signature of Verify and the input description do not match. The intended inputs are $g, x, r, \\epsilon, data$. We will fix this inaccuracy in the final version of this paper.\n\nRegarding the behavior of the randomized verifier, consecutive runs of the verifier on different points are not supposed to be independent; our guarantee is stronger than that. Rather, with probability $\\ge 1 - \\delta$ (over the choice of the samples of $N(0,I_d)$ used to implement the $\\hat{\\phi}$ estimator), soundness holds simultaneously for all points in $\\mathbb{R}^d$. \n\nThe condition $\\epsilon > d^{-1/7}$ is indeed used for the partitioning step; it is because the failure probability of the concentration of projections has large powers of $\\epsilon$. It may be possible with tighter analysis to decrease this power, but not below $\\epsilon^4$, since that is the dependence given in [DHV ’06]. We would like to emphasize that when $\\epsilon = d^{-1/7}$ the run-time is $2^{d^{O(1)}}$ which is exponential in $d$. Furthermore, for such small values of $\\epsilon$, run-times of this form are believed to be necessary (even for regular improper learning) due to statistical query lower bounds we cite in this work. Since one of the main goals of this paper is to develop algorithms with run-times much faster than $2^{d^{O(1)}}$, we do not focus on the parameter regime where $\n\\epsilon < d^{-1/7}$."}]

Author rebuttal:

Meta-review: The authors propose an algorithm for agnostically learning linear threshold classifiers that are adversarially robust. This is a theoretical paper, and it is the first (in a sense efficient) method for solving this problem. The robustness guarantee seems to be weaker  than then standard PAC adversarial learning framework. Nevertheless, the reviewers found the problem setting interesting, the results illuminating, and the proof techniques novel and sophisticated. Overall, this is a strong theory paper that defines and solves a challenging optimization problem.
Decision: Accept (spotlight)