Specifically, for any polynomial $g:\mathbb{R}^{n}\mapsto\mathbb{R}$ of
degree-$d$, for $\epsilon<t<\epsilon^{2/K}$, it holds

$\displaystyle\operatorname*{\mathbf{Pr}}_{\mathbf{x}\sim\mathcal{N}(\mathbf{0},\mathbf{I})\mid\bar{\mathcal{P}}_{i}}\left[\left|g(\mathbf{x})\right|<t\;\left\|g\right\|_{\mathcal{N}(\mathbf{0},\mathbf{I})\mid\bar{\mathcal{P}}_{i},L_{2}}\right]\leq
t^{1/(2d)}\,,$

and for all $t>0$, it holds

$\displaystyle\operatorname*{\mathbf{Pr}}_{\mathbf{x}\sim\mathcal{N}(\mathbf{0},\mathbf{I})\mid\bar{\mathcal{P}}_{i}}\left[\left|g(\mathbf{x})\right|>t\epsilon^{-1/K}\left\|g\right\|_{\mathcal{N}(\mathbf{0},\mathbf{I})\mid\bar{\mathcal{P}}_{i},L_{2}}\right]\leq
O_{d,K}\left(t^{-K}\right).$

  2. 2.

Each set $\bar{\mathcal{P}}_{i}$ has non-trivial probability mass under
$\mathcal{N}(\mathbf{0},\mathbf{I})$, i.e.,

$\operatorname*{\mathbf{Pr}}_{\mathbf{x}\sim\mathcal{N}(\mathbf{0},\mathbf{I})}\left[\mathbf{x}\in\bar{\mathcal{P}}_{i}\right]>\epsilon^{3+5md}\;\operatorname*{\mathbf{Pr}}_{\mathbf{x}\sim\mathcal{N}(\mathbf{0},\mathbf{I})}\left[\mathbf{q}(\mathbf{x})\in
R\right].$

  3. 3.

Define $\bar{\mathcal{P}}:=\bigcup_{i}\bar{\mathcal{P}}_{i}$. The points from
the given set $\mathcal{P}$ that are not included in $\bar{\mathcal{P}}$ have
small probability mass, i.e.,

$\operatorname*{\mathbf{Pr}}_{\mathbf{x}\sim\mathcal{N}(\mathbf{0},\mathbf{I})}\left[\mathbf{x}\not\in\bar{\mathcal{P}},\mathbf{x}\in\mathcal{P}\right]<\epsilon^{2}\operatorname*{\mathbf{Pr}}_{\mathbf{x}\sim\mathcal{N}(\mathbf{0},\mathbf{I})}\left[\mathbf{q}(\mathbf{x})\in
R\right].$

  4. 4.

$\bar{\mathcal{P}}$ is approximately contained in a slightly larger set
compared to $\mathcal{P}$, i.e.
$\tilde{\mathcal{P}}:=\\{\left|p(\mathbf{x})\right|<2\epsilon,\mathbf{q}(\mathbf{x})\in
R\\}$. In particular, it holds

$\operatorname*{\mathbf{Pr}}_{\mathbf{x}\sim\mathcal{N}(\mathbf{0},\mathbf{I})}\left[\mathbf{x}\in\bar{\mathcal{P}},\mathbf{x}\not\in\tilde{\mathcal{P}}\right]<\epsilon^{2}\;\operatorname*{\mathbf{Pr}}_{\mathbf{x}\sim\mathcal{N}(\mathbf{0},\mathbf{I})}\left[\mathbf{q}(\mathbf{x})\in
R\right].$

  5. 5.

$\bar{\mathbf{q}}$ is level-$(k-1)$ super non-singular with respect to the
tuple $(\epsilon,d,K,M=3)$.

Moreover, the algorithm runs in time
$\mathrm{poly}(n^{d})\;\mathrm{poly}_{d,\ell,k,K}(1/\epsilon)$.

###### Proof.

Let $S=\\{q_{1},\cdots,q_{\ell}\\}$ be the set of polynomials corresponding to
the coordinates of $\mathbf{q}$. By our assumption, $\mathbf{q}$ is Level-$k$
super non-singular with respect to the tuple $(\epsilon,d,K,M=3)$. Thus, by
definition, the set $S$ is
$(\epsilon^{1/(3^{k+1}d^{2}K)},f_{d,K,M=3}^{(k)}(\ell))$ super non-singular.
Since $f_{d,K,M=3}^{(k)}(\ell)=C_{d,\ell,f^{(k-1)},M=3}$ by its definition,
using Theorem 4.1, we can extend the set into another
$(\epsilon^{1/(3^{k}d^{2}K)},f^{(k-1)}_{d,K,M=3}(m))$ super non-singular set
$\\{q_{1},\cdots,q_{\ell},q_{\ell+1},\cdots,q_{m}\\}$, where
$m=O_{d,\ell,f^{(k-1)}_{d,K,M=3}}(1)=O_{d,\ell,k,K}(1)$ by 6.2, such that
there exists a composition polynomial $h:\mathbb{R}^{m}\mapsto\mathbb{R}$ and
an error polynomial $e:\mathbb{R}^{n}\mapsto\mathbb{R}$ satisfying

$\displaystyle
p(\mathbf{x})=h(q_{1}(\mathbf{x}),\cdots,q_{m}(\mathbf{x}))+e(\mathbf{x})\,,\,\left\|e\right\|_{L_{2}}\leq\epsilon^{3}.$
(56)

Moreover, we can find the decomposition in Equation 56 in time
$\mathrm{poly}(n^{d})\;\mathrm{poly}_{d,\ell,f^{(k-1)}_{d,K,M=3},M=3}(1/\epsilon)$,
which is simply $\mathrm{poly}(n^{d})\;\mathrm{poly}_{d,\ell,k,K}(1/\epsilon)$
by 6.2.

Define $\bar{\mathbf{q}}:\mathbb{R}^{n}\mapsto\mathbb{R}^{m}$ to be the
vector-valued polynomial whose $i$-th coordinate is $q_{i}$. Then by
definition, $\bar{\mathbf{q}}$ is Level-$(k-1)$ super non-singular with
respect to the same tuple $(\epsilon,d,K,M=3)$. This guarantees Condition (5)
in the proposition is satisfied.

With the decomposition and its associated polynomial transformation
$\bar{\mathbf{q}}$ in our hand, we begin our search of axis-aligned rectangles
in the $m$-dimensional output space of $\bar{\mathbf{q}}$. The first step is
to restrict our search space to a very large rectangle that is obtained by
extending the original $\ell$-dimensional rectangle $R$ in all the remaining
$(m-\ell)$ dimensions:

$\bar{R}:=R\times[-\alpha_{\ell,d}\log^{d/2}(m/\epsilon),\alpha_{\ell,d}\log^{d/2}(m/\epsilon)]^{m-\ell}\,,$

where $\alpha_{\ell,d}$ is some number that depends on $\ell,d$ that we will
specify later. Since we have $\left\|q_{i}\right\|_{L_{2}}=1$ for all
$i\in[m]$, by the union bound and the concentration of polynomials (Lemma
3.15), it holds

$\displaystyle\operatorname*{\mathbf{Pr}}_{\mathbf{x}\sim\mathcal{N}(\mathbf{0},\mathbf{I})}\left[\bar{\mathbf{q}}(\mathbf{x})\not\in\bar{R}\right]<\exp\left(-\Omega(\alpha_{\ell,d})^{2/d}\log(1/\epsilon)\right).$

Since we also assume that
$\operatorname*{\mathbf{Pr}}_{\mathbf{x}\sim\mathcal{N}(\mathbf{0},\mathbf{I})}\left[\mathbf{q}(\mathbf{x})\in
R\right]>\mathrm{poly}_{d,\ell}(\epsilon)$, it is not hard to see that if we
choose $\alpha_{d,\ell}$ to be sufficiently large given $d,\ell$, we then have

$\displaystyle\operatorname*{\mathbf{Pr}}_{\mathbf{x}\sim\mathcal{N}(\mathbf{0},\mathbf{I})}\left[\bar{\mathbf{q}}(\mathbf{x})\not\in\bar{R}\right]<\epsilon^{3}\operatorname*{\mathbf{Pr}}_{\mathbf{x}\sim\mathcal{N}(\mathbf{0},\mathbf{I})}\left[\mathbf{q}(\mathbf{x})\in
R\right].$ (57)

We next partition the rectangle $\bar{R}$ into small rectangles
$\\{\bar{R}_{i}\\}$, each of side length $\epsilon^{4d}$. Since the side
length of the rectangle $\bar{R}$ is
$2\alpha_{d,\ell}\log^{d/2}(m/\epsilon)=\mathrm{poly}_{d,\ell,k,K}(\log(1/\epsilon))$
(recall that $m=O_{d,\ell,k,K}(1)$), it is not hard to see that the number of
sub-rectangles we end up with is at most

$\left(\mathrm{poly}_{d,\ell,k,K}(\log(1/\epsilon))\;\epsilon^{-4d}\right)^{m}\leq\mathrm{poly}_{d,m,k,K}(\log(1/\epsilon))\;\epsilon^{-4dm}\leq\epsilon^{-5md}\,,$

where the last inequality is true if $\epsilon$ is sufficiently small given
$d,m,k,K$. These will be the candidate rectangles we use to define the output
set $\bar{\mathcal{P}}_{i}$.

Let $\tilde{\mathcal{N}}$ be the empirical distribution of
$\mathcal{V}=\mathrm{poly}_{m,d}(1/\epsilon)$ i.i.d. samples from
$\mathcal{N}(\mathbf{0},\mathbf{I})$. Among the small rectangles, we pick the
ones that are (i) not too light, and (ii) contain a significant fraction of
points satisfying $\left|p(\mathbf{x})<\epsilon\right|$. More formally, the
selection rule is given by

$\operatorname*{\mathbf{Pr}}_{\mathbf{x}\sim\tilde{\mathcal{N}}}\left[\bar{\mathbf{q}}(\mathbf{x})\in{\bar{R}}^{(i)}\mid\mathbf{q}(\mathbf{x})\in
R\right]>2\epsilon^{3+5md}\;,\;\operatorname*{\mathbf{Pr}}_{\mathbf{x}\sim\tilde{\mathcal{N}}}\left[\left|p(\mathbf{x})\right|<\epsilon\mid\bar{\mathbf{q}}(\mathbf{x})\in{\bar{R}}^{(i)}\right]>2\epsilon^{3}.$

Note that this step can be completed in time
$\mathrm{poly}(n^{d})\;\mathrm{poly}(\mathcal{V})\;\epsilon^{-5md}$. The final
output of the algorithm will simply be
$\bar{\mathcal{P}}_{i}=\\{\mathbf{x}:\bar{q}(\mathbf{x})\in\bar{R}_{i}\\}$ for
those $\bar{R}_{i}$ that are retained after the selection. Hence, this shows
that the total runtime is
$\mathrm{poly}(n^{d})\;\mathrm{poly}_{d,\ell,k,K}(1/\epsilon)$.

We proceed to show the sets produced satisfy Conditions (1)-(4) in Proposition
6.3. Let $\mathcal{K}$ be the family of sub-rectangles kept and $\mathcal{T}$
be the family of sub-rectangles discarded after the selection procedure. If we
take $\mathcal{V}=\mathrm{poly}_{m,d}(1/\epsilon)$ many samples, with high
probability, we will have the following probability mass separation between
the rectangles from $\mathcal{K}$ and from $\mathcal{T}$ under
$\mathcal{N}(\mathbf{0},\mathbf{I})$.
For all the sub-rectangles $R^{(i)}\in\mathcal{K}$ picked, we have

$\displaystyle\operatorname*{\mathbf{Pr}}_{\mathbf{x}\sim\mathcal{N}(\mathbf{0},\mathbf{I})}\left[\bar{\mathbf{q}}(\mathbf{x})\in{\bar{R}}^{(i)}\mid\mathbf{q}(\mathbf{x})\in
R\right]>\epsilon^{3+5md}\text{ and
}\operatorname*{\mathbf{Pr}}_{\mathbf{x}\sim\mathcal{N}(\mathbf{0},\mathbf{I})}\left[\left|p(\mathbf{x})\right|<\epsilon\mid\bar{\mathbf{q}}(\mathbf{x})\in{\bar{R}}^{(i)}\right]>\epsilon^{3}.$
(58)

For all the sub-rectangles $R^{(i)}\in\mathcal{T}$ removed, we have

$\displaystyle\operatorname*{\mathbf{Pr}}_{\mathbf{x}\sim\mathcal{N}(\mathbf{0},\mathbf{I})}\left[\bar{\mathbf{q}}(\mathbf{x})\in{\bar{R}}^{(i)}\mid\mathbf{q}(\mathbf{x})\in
R\right]<3\epsilon^{3+5md}\text{ or
}\operatorname*{\mathbf{Pr}}_{\mathbf{x}\sim\mathcal{N}(\mathbf{0},\mathbf{I})}\left[\left|p(\mathbf{x})\right|<\epsilon\mid\bar{\mathbf{q}}(\mathbf{x})\in{\bar{R}}^{(i)}\right]<3\epsilon^{3}.$
(59)

Notice that Equation 58 establishes Condition (2) in Proposition 6.3.

For each $\bar{R}_{i}\in\mathcal{K}$, we claim that
$\mathcal{N}(\mathbf{0},\mathbf{I})$ conditioned on
$\bar{\mathbf{q}}(\mathbf{x})\in\bar{R}_{i}$ satisfies good
(anti-)concentration. Indeed, the mass of the set under
$\mathcal{N}(\mathbf{0},\mathbf{I})$ is at least
$\epsilon^{3+5d}\operatorname*{\mathbf{Pr}}_{\mathbf{x}\sim\mathcal{N}(\mathbf{0},\mathbf{I})}\left[\mathbf{q}(\mathbf{x})\in
R\right]\geq\mathrm{poly}_{d,m}(1/\epsilon)$ by Equation 58, and the set
$\\{q_{1},\cdots,q_{m}\\}$ is at least
$\left(\epsilon^{1/(3^{k+1}d^{2}K)},f_{d,K,M}^{(k)}(m)\right)$-super non-
singular. As long as $k\geq 0$, we then have
$\epsilon^{1/(3^{k+1}d^{2}K)}\geq\epsilon^{1/(3d^{2}K)}$, and
$f_{d,K,M}^{(k)}(m)\geq C_{d,m,K}$. Hence, (anti-)concentration properties of
the conditional distribution follows from Theorem 5.1. This establishes
Condition (1) in Proposition 6.3.

We next verify that the union of the produced sets, i.e.,
$\bigcup_{\bar{R}_{i}\in\mathcal{K}}\\{\mathbf{x}:\mathbf{q}(\mathbf{x})\in
R^{(i)}\\}$, contains almost all the points from
$\\{\mathbf{x}:\left|p(\mathbf{x})\right|<\epsilon\,,\,\mathbf{q}(\mathbf{x})\in
R\\}$. Throughout our algorithm, a point $\mathbf{x}$ may be missed due to
three different reasons. First, it may be removed if it does not lie in the
giant rectangle where we begin our search, i.e.
$\bar{\mathbf{q}}(\mathbf{x})\not\in\bar{R}$. Equation 57 implies that the
probability mass of these points under $\mathcal{N}(\mathbf{0},\mathbf{I})$ is
at most
$\epsilon^{3}\operatorname*{\mathbf{Pr}}_{\mathbf{x}\sim\mathcal{N}(\mathbf{0},\mathbf{I})}\left[\mathbf{q}(\mathbf{x})\in
R\right]$. Secondly, the point may be thrown if it lies in some small
rectangle $\bar{R}_{i}\in\mathcal{T}$. By Equation 59, there are two subcases.
In the first subcase, this rectangle is thrown due to its probability mass
being too small, i.e.,

$\operatorname*{\mathbf{Pr}}_{\mathbf{x}\sim\mathcal{N}(\mathbf{0},\mathbf{I})}\left[\bar{\mathbf{q}}(\mathbf{x})\in\bar{R}_{i}\right]<3\epsilon^{3+5md}\;\operatorname*{\mathbf{Pr}}_{\mathbf{x}\sim\mathcal{N}(\mathbf{0},\mathbf{I})}\left[\mathbf{q}(\mathbf{x})\in
R\right].$

In total, there are at most $\epsilon^{-5md}$ light rectangles. So the total
probability mass of $\mathbf{x}$ discarded in this case is bounded above by
$3\epsilon^{3}\operatorname*{\mathbf{Pr}}_{\mathbf{x}\sim\mathcal{N}(\mathbf{0},\mathbf{I})}\left[\mathbf{q}(\mathbf{x})\in
R\right]$ under $\mathcal{N}(\mathbf{0},\mathbf{I})$. In the second subcase,
we have

$\operatorname*{\mathbf{Pr}}_{\mathbf{x}\sim\mathcal{N}(\mathbf{0},\mathbf{I})}\left[\left|p(\mathbf{x})\right|<\epsilon|\bar{\mathbf{q}}(\mathbf{x})\in\bar{R}_{i}\right]<3\epsilon^{3}.$

This is equivalent to

$\operatorname*{\mathbf{Pr}}_{\mathbf{x}\sim\mathcal{N}(\mathbf{0},\mathbf{I})}\left[\left|p(\mathbf{x})\right|<\epsilon\,,\,\bar{\mathbf{q}}(\mathbf{x})\in\bar{R}_{i}\right]<3\epsilon^{3}\operatorname*{\mathbf{Pr}}_{\mathbf{x}\sim\mathcal{N}(\mathbf{0},\mathbf{I})}\left[\bar{\mathbf{q}}(\mathbf{x})\in\bar{R}_{i}\right].$

By construction, the union of all rectangles $\bar{R}_{i}$ gives rise to
$\bar{R}$. Moreover, since the first $\ell$ dimensions of $\bar{R}$ and
$\bar{\mathbf{q}}$ are identical to those of $R$ and $\mathbf{q}$
respectively, it is not hard to see that the set
$\\{\mathbf{x}:\bar{\mathbf{q}}(\mathbf{x})\in\bar{R}\\}$ is a subset of
$\\{\mathbf{x}:\mathbf{q}(\mathbf{x})\in R\\}$. Consequently, the total mass
of the points removed due to this reason is also no more than
$3\epsilon^{3}\operatorname*{\mathbf{Pr}}_{\mathbf{x}\sim\mathcal{N}(\mathbf{0},\mathbf{I})}\left[\mathbf{q}(\mathbf{x})\in
R\right]$ under $\mathcal{N}(\mathbf{0},\mathbf{I})$. In summary, the total
mass discarded from the original set $\\{\mathbf{x}:\mathbf{q}(\mathbf{x})\in
R\\}$ is no more than

$O(\epsilon^{3})\;\operatorname*{\mathbf{Pr}}_{\mathbf{x}\sim\mathcal{N}(\mathbf{0},\mathbf{I})}\left[\mathbf{q}(\mathbf{x})\in
R\right]<\epsilon^{2}\;\operatorname*{\mathbf{Pr}}_{\mathbf{x}\sim\mathcal{N}(\mathbf{0},\mathbf{I})}\left[\mathbf{q}(\mathbf{x})\in
R\right]$

under $\mathcal{N}(\mathbf{0},\mathbf{I})$. This establishes Condition (3) in
Proposition 6.3.

Finally, we verify that the extra points outside the set
$\\{\mathbf{x}:\left|p(\mathbf{x})\right|<2\epsilon,\mathbf{q}(\mathbf{x})\in
R\\}$ included in
$\bigcup_{\bar{R}_{i}\in\mathcal{K}}\\{\mathbf{x}:\bar{\mathbf{q}}(\mathbf{x})\in\bar{R}_{i}\\}$
have small probability mass. It is clear that all the sets produced are
subsets of $\\{\mathbf{x}:\mathbf{q}(\mathbf{x})\in R\\}$ by the construction
of the sub-rectangles $\bar{R}_{i}$’s. Hence, it remains to show that the
value of $p$ evaluated at these subsets is not too big. Recall that the
polynomial $p$ can be written as

$p(\mathbf{x})=h(\mathbf{q}(\mathbf{x}))+e(\mathbf{x})$

by our decomposition. Fix some $\bar{R}_{i}\in\mathcal{K}$. By our selection
rule of $\mathcal{K}$ (Equation 58), we know that there is at least some
$\mathbf{x}^{*}$ in the set
$\\{\mathbf{x}:\bar{\mathbf{q}}(\mathbf{x})\in\bar{R}_{i}\\}$ such that

$\left|h(\mathbf{q}^{\prime}(\mathbf{x}^{*}))+e(\mathbf{x}^{*})\right|=\left|p(\mathbf{x}^{*})\right|<\epsilon.$

Consider another point
$\mathbf{y}\in\\{\mathbf{x}:\bar{\mathbf{q}}(\mathbf{x})\in\bar{R}_{i}\\}$.
Since $R^{(i)}$ has side-length $\epsilon^{4d}$ by construction and its
coordinates are at most $\mathrm{poly}_{d,\ell,k,K}(\log(1/\epsilon))$ far
from the origin, we know that
$\left\|-\bar{\mathbf{q}}(\mathbf{y})\right\|_{2}\leq\sqrt{m}\epsilon^{4d}$
and
$\max\left(\left\|\bar{\mathbf{q}}(\mathbf{x}^{*})\right\|_{2},\bar{\mathbf{q}}(\mathbf{y})\right)\leq\sqrt{m}\mathrm{poly}_{d,\ell,k,K}(\log(1/\epsilon))$.
Moreover, by the guarantees of Theorem 5.1, we have that
$\left\|h\right\|_{L_{2}}<\epsilon^{-3d-1}$. Notice that $h$ is a degree-$d$,
dimension-$m$ polynomial. Hence, Corollary 3.24 implies that

$\left|h(\bar{\mathbf{q}}(\mathbf{x}^{*}))-h(\bar{\mathbf{q}}(\mathbf{y}))\right|\leq
O_{d,m}(1)\;\mathrm{poly}_{d,\ell,k,K}\left(\log(1/\epsilon)\right)\;\epsilon^{-3d-1}\;\epsilon^{4d}<\epsilon^{2}\,,$

as long as $\epsilon$ is sufficiently small given $d,\ell,k,K$. It suffices to
argue that $\left|e(\mathbf{y})-e(\mathbf{x}^{*})\right|$ is not too large. If
it were the case that
$\left|e(\mathbf{y})-e(\mathbf{x}^{*})\right|<\epsilon^{2}$, we would then
have

$\left|p(\mathbf{y})\right|\leq\left|p(\mathbf{x})\right|+\left|h(\bar{\mathbf{q}}(\mathbf{x}^{*}))-h(\bar{\mathbf{q}}(\mathbf{y}))\right|+\left|e(\mathbf{y})-e(\mathbf{x}^{*})\right|\leq\epsilon+O(\epsilon^{2})<2\epsilon.$

Then the produced sets would be _exactly_ contained in the set
$\tilde{\mathcal{P}}=\\{\mathbf{x}:\mathbf{q}(\mathbf{x})\in
R,\left|p(\mathbf{x})\right|<2\epsilon\\}$. Unfortunately, this is not true in
general. However, since $\left\|e\right\|_{L_{2}}<\epsilon^{3}$ by the
guarantees of Theorem 4.1, we can show that the mass of the points which do
not satisfy $\left|e(\mathbf{y})-e(\mathbf{x}^{*})\right|<\epsilon^{2}$ is
small. In particular, by Lemma 3.15, we know that

$\operatorname*{\mathbf{Pr}}_{\mathbf{x}\sim\mathcal{N}(\mathbf{0},\mathbf{I})}\left[\left|e(\mathbf{x})\right|>\alpha_{d,\ell}^{d/2}\log^{d/2}(1/\epsilon)\epsilon^{3}\right]\leq\epsilon^{\Omega(\alpha_{d,\ell})}.$

Recall that
$\operatorname*{\mathbf{Pr}}_{\mathbf{x}\sim\mathcal{N}(\mathbf{0},\mathbf{I})}\left[\mathbf{q}(\mathbf{x})\in
R\right]>\mathrm{poly}_{d,\ell}(\epsilon)$ by our assumption. Hence, when
$\alpha_{d,\ell}$ is sufficiently large given $d,\ell$, we will have

$\operatorname*{\mathbf{Pr}}_{\mathbf{x}\sim\mathcal{N}(\mathbf{0},\mathbf{I})}\left[\left|e(\mathbf{x})\right|<\alpha_{d,\ell}^{d/2}\log^{d/2}(1/\epsilon)\epsilon^{3}<\epsilon^{2}\right]>1-\epsilon^{3}\operatorname*{\mathbf{Pr}}_{\mathbf{x}\sim\mathcal{N}(\mathbf{0},\mathbf{I})}\left[\mathbf{q}(\mathbf{x})\in
R\right].$

Since the only additional points that are included in the sets produced but
excluded from $\tilde{\mathcal{P}}$ are those satisfying
$\left|e(\mathbf{x})\right|>\epsilon^{2}$, it is not hard to conclude that
Condition (4) in the proposition is satisfied. We have verified all the
properties listed in the proposition. This concludes the proof of Proposition
6.3. ∎

##  7 Learning Polynomial Threshold Functions using Super Non-Singular
Polynomials

In this section, we present an efficient algorithm that learns an unknown
polynomial threshold function under the Gaussian distribution in the presence
of an $\mathrm{opt}$ fraction of adversarial corruptions, and achieves error
$O_{c,d}(\mathrm{opt}^{1-c})$ for any desirable constant $c>0$. The formal
statement of our theorem is as follows:

######  Theorem 7.1 (Main Algorithmic Result, Formal Statement).

Let $\epsilon,\mathrm{opt},\eta,c\in(0,1),d\in\mathbb{Z}_{+}$. Let $D$ be the
distribution of $(\mathbf{x},y)\in\mathbb{R}^{n}\times\\{\pm 1\\}$, where
$\mathbf{x}$ follows the standard Gaussian distribution, and $y$ is the output
of some unknown degree-$d$ PTF evaluated at $\mathbf{x}$. Given an
$\mathrm{opt}$-corrupted version of a set of
$n^{O(d)}\mathrm{poly}_{d,c}(1/\epsilon)\log(1/\eta)$ i.i.d. samples from $D$,
there exists an algorithm, with computation complexity at most
$n^{O(d)}\mathrm{poly}_{d,c}(1/\epsilon)\log(1/\eta)$, that computes a
decision list $h:\mathbb{R}^{n}\mapsto\\{\pm 1\\}$ consisting of at most
$\mathrm{poly}_{d,c}(1/\epsilon)$ degree-$d$ PTFs such that, with probability
at least $1-\eta$, it holds

$\operatorname*{\mathbf{Pr}}_{(\mathbf{x},y)\sim D}[h(\mathbf{x})\neq y]\leq
A_{c,d}~{}\mathrm{opt}^{1-c}+\epsilon\,,$

where $A_{c,d}>0$ is an absolute constant depending only on $c,d$.

We now provide an overview of the algorithm. The high-level framework is to
implement an iterative localization strategy through the application of the
Polynomial-Set-Partitioner from Proposition 6.3 developed in Section 6.
Roughly speaking, by applying the Polynomial-Set-Partitioner, we can
approximately partition an unclassified area defined by polynomial
transformations into subsets such that the Gaussian distribution conditioned
on each subset within the partition satisfies good (anti-)concentration
properties. Once such a partition is identified, we will next run a robust
margin perceptron algorithm (see Algorithm 1) on each of the conditional
distributions. Under good (anti)-concentration properties, the margin
perceptron algorithm can output a PTF such that the prediction is accurate for
all but $\epsilon^{\Omega(1/d)}$ fraction of low-margin points under
$\epsilon$-fraction of adversarial corruptions (see Proposition 7.3).
Consequently, combining the PTFs learned from different conditional
distributions then gives a hypothesis capable of accurately classifying all
but an $\epsilon^{\Omega(1/d)}$ fraction of data points within the region. The
process continues iteratively: the algorithm is given a new unclassified
region and applies the perceptron update until the remaining unclassified mass
is reduced to a negligible fraction, specifically
$O_{c,d}(\mathrm{opt}^{1-c})$.

Before proceeding with the proof of Theorem 7.1, we first present our robust
margin-perceptron algorithm. This routine is the main ingredient of our
algorithm. Given a distribution that satisfies some good concentration and
anti-concentration properties, Algorithm 1 robustly estimates a weak learner
that classifies almost all the points.

Input: Sample access to an at most $\epsilon$-corrupted oracle of the
distribution $D$; access to $\mathbf{x}$-marginals $D_{\mathbf{x}}$, see
Definition 1.1, $K>0$.

Parameters: $F=\epsilon^{1-8/\sqrt{K}},\gamma=\epsilon^{4/\sqrt{K}}$ and $C>0$
a sufficiently large absolute constant.

Output: A vector $\mathbf{w}$ and a region $B$ so that:
$\operatorname*{\mathbf{Pr}}_{(\mathbf{x},y)\sim
D}[\mathrm{sign}({\mathbf{w}}\cdot\mathbf{x})\neq y\mid B]\leq
C_{K}(\epsilon)^{1-O(1/\sqrt{K})}$ and $B=\\{(\mathbf{x},y)\mid
y\neq\mathrm{sign}(\mathbf{w}\cdot\mathbf{x}),|\mathbf{w}\cdot\mathbf{x}|\geq\gamma\|\mathbf{w}\|_{D_{\mathbf{x}},L_{2}}\\}$.

  1. 1.

$t\leftarrow 0$.

  2. 2.

Let $\mathbf{q}^{(t)}$ be an estimator of
$\operatorname*{\mathbf{E}}_{(\mathbf{x},y)\sim D}[y\mathbf{x}]$ using the
algorithm of 7.4.

  3. 3.

Let
$B_{t}=\\{(\mathbf{x},y)\mid|\mathbf{q}^{(t)}\cdot\mathbf{x}|\geq\gamma\|\mathbf{q}^{(t)}\|_{D_{\mathbf{x}},L_{2}}\\}$
and $B_{t}^{\prime}=\\{(\mathbf{x},y)\mid
y\neq\mathrm{sign}(\mathbf{q}^{(t)}\cdot\mathbf{x}),|\mathbf{q}^{(t)}\cdot\mathbf{x}|\geq\gamma\|\mathbf{q}^{(t)}\|_{D_{\mathbf{x}},L_{2}}\\}$

  4. 4.

While $\operatorname*{\mathbf{Pr}}[B_{t}^{\prime}]\geq 2F$ and
$t<O(\epsilon^{-C})$, do

    1. (a)

Let $\mathbf{p}^{(t)}$ be an estimator of
$\operatorname*{\mathbf{E}}_{(\mathbf{x},y)\sim
D}[y\mathds{1}\\{y\neq\mathrm{sign}(\mathbf{q}^{(t)}\cdot\mathbf{x})\\}\mathbf{x}\mid(\mathbf{x},y)\in
B_{t}]$ using the algorithm of 7.4.

    2. (b)

$\mathbf{q}^{(t+1)}=\mathbf{q}^{(t)}+\lambda_{t}\mathbf{p}^{(t)}$, where
$\lambda_{t}=(1/4)\|\mathbf{q}^{(t)}\|_{D_{\mathbf{x}},L_{2}}\operatorname*{\mathbf{Pr}}[B_{t}^{\prime}]\gamma/\|\mathbf{p}^{(t)}\|_{D_{\mathbf{x}},L_{2}}^{2}$.

    3. (c)

$t\leftarrow t+1$.

  5. 5.

Return $\mathbf{q}^{(t)}$.

Algorithm 1 Perceptron Update

######  Remark 7.2.

In what follows, we will overload our norm notation and for a vector
$\mathbf{w}\in\mathbb{R}^{n}$ we denote by
$\|\mathbf{w}\|_{D_{\mathbf{x}},L_{p}}$ its distributional $L_{p}$ norm when
it is treated as a linear function of $\mathbf{x}$, i.e.,
$\|\mathbf{w}\|_{D_{\mathbf{x}},L_{p}}=\Big{(}\operatorname*{\mathbf{E}}_{\mathbf{x}\sim
D_{\mathbf{x}}}[|\mathbf{w}\cdot\mathbf{x}|^{p}\Big{)}^{1/p}$. We continue to
denote the common norm of $\mathbf{w}$ by
$\|\mathbf{w}\|_{p}=\Big{(}\sum_{i=1}^{n}|\mathbf{w}_{i}|^{p}\Big{)}^{1/p}$
when we treat it as a vector of $\mathbb{R}^{n}$.

######  Proposition 7.3.

Let $\epsilon\in(0,1)$, $K\in\mathbbm{Z}_{+}$, $C,C_{1}>0$, and $D$ be a
distribution on $\mathbb{R}^{n}\times\\{\pm 1\\}$. Assume the following
statements are true.

  1. 1.

The samples $\mathbf{x}$ are labeled with respect to an unknown function
$f(\mathbf{x})=\mathrm{sign}(\mathbf{w}^{\ast}\cdot\mathbf{x})$ for some
$\mathbf{w}^{\ast}\in\mathbb{R}^{n}$.

  2. 2.

The covariance matrix of the marginal distribution $D_{\mathbf{x}}$ satisfies
$\operatorname*{\mathbf{E}}_{\mathbf{x}\sim
D_{\mathbf{x}}}[\mathbf{x}^{\top}\mathbf{x}]\preccurlyeq 2\mathbf{I}$.

  3. 3.

The $\mathbf{x}$-marginal distribution $D_{\mathbf{x}}$ satisfies anti-
concentration, i.e.,

$\operatorname*{\mathbf{Pr}}_{\mathbf{x}\sim
D_{\mathbf{x}}}[|\mathbf{v}\cdot\mathbf{x}|\leq
t\|\mathbf{v}\|_{D_{\mathbf{x}},L_{2}}]\leq t^{C}\,,$

for some number $C>0$, and for all $t\in(\epsilon,\epsilon^{2/{\sqrt{K}}})$.

  4. 4.

$D_{\mathbf{x}}$ has concentration, i.e.,

$\operatorname*{\mathbf{Pr}}_{\mathbf{x}\sim
D_{\mathbf{x}}}[|\mathbf{v}\cdot\mathbf{x}|>t\|\mathbf{v}\|_{D_{\mathbf{x}},L_{2}}]\leq
C_{1}t^{-K}\,,$

for some $C_{1}>0$ and all $t>0$

Then Algorithm 1 given access to an $\epsilon$-corrupted version of
$\mathrm{poly}(n/\epsilon)$ i.i.d. samples from $D$, runs in sample-polynomial
time, and with probability at least $2/3$ computes a weight vector
$\widehat{\mathbf{w}}$ such that

$\operatorname*{\mathbf{Pr}}_{(\mathbf{x},y)\sim
D}[\mathrm{sign}(\widehat{\mathbf{w}}\cdot\mathbf{x})\neq y\mid B]\leq
C_{1}^{1/K}~{}O_{C,K,d}(\epsilon^{1-O(1/\sqrt{K})})\,,$

where
$B=\\{\mathbf{x}:|\mathbf{w}\cdot\mathbf{x}|\geq\gamma\|\mathbf{w}\|_{D_{\mathbf{x}},L_{2}}\\}$
for $\gamma=\epsilon^{4/\sqrt{K}}$.

###### Proof.

We set the parameters $\gamma=\epsilon^{4/\sqrt{K}}$ and
$F=\epsilon^{1-8/\sqrt{K}}$. We denote by $D^{c}$ the distribution $D$ that is
at most $\epsilon$-corrupted. First, we show that we can robustly estimate
$\operatorname*{\mathbf{E}}_{(\mathbf{x},y)\sim D}[y\mathbf{x}]$. We will use
of following fact.

######  Fact 7.4 (Proposition 2.2 of [DKS18]).

Fix $\epsilon,\xi\in(0,1)$ and let $D$ be a distribution on
$\mathbb{R}^{n}\times[-1,1]$ corresponding to pairs labeled according to some
function $f:\mathbb{R}^{n}\mapsto[-1,1]$, i.e.,
$(\mathbf{x},f(\mathbf{x}))\sim D$. Assume that $D$ satisfies the following:
(i) concentration, i.e., $\operatorname*{\mathbf{Pr}}_{\mathbf{x}\sim
D_{\mathbf{x}}}[|\mathbf{v}\cdot\mathbf{x}|>t\|\mathbf{v}\|_{D_{\mathbf{x}},L_{2}}]\leq
Ct^{-K}$, for some $C>0$ and for all $t>0$, (ii) bounded variance in each
direction, i.e., $\operatorname*{\mathbf{E}}_{\mathbf{x}\sim
D_{\mathbf{x}}}[\mathbf{x}\mathbf{x}^{\top}]\preccurlyeq\Sigma$. Then, there
is an algorithm that given an $\epsilon$-corrupted set $S$ from $D$ with
$|S|=O(n\mathrm{poly}(1/\epsilon,1/\xi))$ and a description of the
$\mathbf{x}$-marginals $D_{\mathbf{x}}$, runs in $\mathrm{poly}(|S|)$ time and
outputs $\mathbf{q}\in\mathbb{R}^{n}$, such that
$\|\operatorname*{\mathbf{E}}_{\mathbf{x}\sim
D_{\mathbf{x}}}[f(\mathbf{x})\mathbf{x}]-\mathbf{q}\|_{2}\leq
c\|\Sigma\|_{2}C^{1/K}\epsilon^{1-1/K}$ with probability at least $1-\xi$,
where $c>0$ is an absolute constant.

For the rest of the proof, let $c>0$ be the absolute constant from 7.4. Note
that for our distribution and for any band
$B=\\{\mathbf{x}:|\mathbf{w}\cdot\mathbf{x}|\geq\gamma\|\mathbf{w}\|_{D_{\mathbf{x}},L_{2}}\\}$,
we have that the distribution $D^{c}$ conditioned on $B$ is at most
$O(\epsilon/\operatorname*{\mathbf{Pr}}[B])=O(\epsilon)$ corrupted, because
$\operatorname*{\mathbf{Pr}}[\mathbf{x}\in B]\geq
1-\gamma^{C}=1-\epsilon^{Cc}=\Omega(1)$. Let $\mathbf{q}^{(0)}$ be a robust
estimator (given by 7.4) of $\operatorname*{\mathbf{E}}_{(\mathbf{x},y)\sim
D}[y\mathbf{x}]$ with error at most $cC_{1}^{1/K}\epsilon^{1-1/K}$, i.e.,
$\|\operatorname*{\mathbf{E}}_{(\mathbf{x},y)\sim
D}[y\mathbf{x}]-\mathbf{q}^{(0)}\|_{2}\leq cC_{1}^{1/K}\epsilon^{1-1/K}$ . We
first show that $\mathbf{q}^{(0)}$ is well-correlated with
$\mathbf{w}^{\ast}$.

######  Claim 7.5.

It holds that
$\mathbf{q}^{(0)}\cdot\mathbf{w}^{\ast}\geq(1/2)\epsilon^{2/\sqrt{K}}$.

###### Proof.

Using that $\mathbf{q}^{(0)}$ is equal to
$\operatorname*{\mathbf{E}}_{(\mathbf{x},y)\sim D}[f(\mathbf{x})\mathbf{x}]$
with error at most $cC_{1}^{1/K}\epsilon^{1-1/K}$, we get that

$\mathbf{q}^{(0)}\cdot\mathbf{w}^{\ast}\geq\operatorname*{\mathbf{E}}_{\mathbf{x}\sim
D_{\mathbf{x}}}[|\mathbf{w}^{\ast}\cdot\mathbf{x}|]-cC_{1}^{1/K}\epsilon^{1-1/K}\;.$

Using the anti-concentration, i.e., property (ii) of Proposition 7.3, we get
that $\operatorname*{\mathbf{E}}_{\mathbf{x}\sim
D_{\mathbf{x}}}[|\mathbf{w}^{\ast}\cdot\mathbf{x}|]\geq\rho(1-\rho^{C})$. We
can assume without loss of generality that $\epsilon$ is less than a
sufficiently small constant depending on $C,K$ and $C_{1}^{1/K}$. Otherwise,
the constant hypothesis is $O(\epsilon)$. Hence, it holds that
$1-\epsilon^{C/\sqrt{K}}\geq 1/2$. It follows that for
$\rho=\epsilon^{2/\sqrt{K}}$, we have that
$\rho(1-\rho^{C})\geq\epsilon^{2/\sqrt{K}}/2$, and therefore
$\mathbf{q}^{(0)}\cdot\mathbf{w}^{\ast}\geq\epsilon^{2/\sqrt{K}}/2$. ∎

Denote as
$B_{t}=\\{|\mathbf{q}^{(t)}\cdot\mathbf{x}|\geq\gamma\|\mathbf{q}^{(t)}\|_{D_{\mathbf{x}},L_{2}}\\}$.
While the mass of the region
$B_{t}^{\prime}=\\{y\neq\mathrm{sign}(\mathbf{q}^{(t)}\cdot\mathbf{x}),|\mathbf{q}^{(t)}\cdot\mathbf{x}|\geq\gamma\|\mathbf{q}^{(t)}\|_{D_{\mathbf{x}},L_{2}}\\}$
is larger than our threshold or the maximum number of iterations have not
exceeded our threshold (Step (4)), our algorithm updates the current
hypothesis using the following update rule:

$\mathbf{q}^{(t+1)}\leftarrow\mathbf{q}^{(t)}+\lambda_{t}\mathbf{p}^{(t)}\;,$

where $\mathbf{p}^{(t)}$ is a robust estimator of
$\operatorname*{\mathbf{E}}_{(\mathbf{x},y)\sim
D}[f^{\prime}(\mathbf{x})\mathbf{x}\mid B_{t}]$, where
$f^{\prime}(\mathbf{x})=f(\mathbf{x})\mathds{1}\\{y\neq\mathrm{sign}(\mathbf{q}^{(t)}\cdot\mathbf{x})\\}$,
obtained by the algorithm of 7.4. Let
$F_{t}=\operatorname*{\mathbf{E}}_{(\mathbf{x},y)\sim D}[(\mathbf{x},y)\in
B_{t}^{\prime}]\geq F$ (see Step (4)) and denote by $D_{t}$ the distribution
$D$ conditioned on the event $B_{t}$. Note that the true mass of the region
$B_{t}$ with respect to the distribution $D$ is at least $1/2$. We claim that
the distribution $D_{t}$ satisfies the assumptions of 7.4. First, note that
the corruption level of $D_{t}$ is at most $2\epsilon$, furthermore for the
distribution $D_{t}$, it holds that
$\operatorname*{\mathbf{Pr}}_{\mathbf{x}\sim(D_{t})_{\mathbf{x}}}[|\mathbf{v}\cdot\mathbf{x}|>t\|\mathbf{v}\|_{D_{\mathbf{x}},L_{2}}]\leq
2\operatorname*{\mathbf{Pr}}_{\mathbf{x}\sim
D_{\mathbf{x}}}[|\mathbf{v}\cdot\mathbf{x}|>t\|\mathbf{v}\|_{D_{\mathbf{x}},L_{2}}]\leq
2C_{1}t^{-K}$. Moreover, for any unit vector $\mathbf{v}\in\mathbb{R}^{n}$, it
holds that
$\operatorname*{\mathbf{E}}_{\mathbf{x}\sim(D_{t})_{\mathbf{x}}}[(\mathbf{v}\cdot\mathbf{x})^{2}]\leq
4$. Therefore, $D_{t}$ satisfies the assumptions of 7.4 but with parameters
$C=2C_{1}$, $\|\Sigma\|_{2}\leq 4$ and at most $2\epsilon$ corruption rate.

Using 7.4 on the distribution $D_{t}$, we have that for our robust estimator
$\mathbf{p}^{(t)}$, it holds that
$\|\mathbf{p}^{(t)}-\operatorname*{\mathbf{E}}_{(\mathbf{x},y)\sim
D}[f^{\prime}(\mathbf{x})\mathbf{x}\mid(\mathbf{x},y)\in B_{t}]\|_{2}\leq
8cC_{1}^{1/K}\epsilon^{1-1/K}$. We show that by choosing appropriately the
stepsize $\lambda_{t}$, we decrease the norm of
$\|\mathbf{q}^{(t)}\|_{D_{\mathbf{x}},L_{2}}$ in each iteration. We show the
following:

######  Claim 7.6.

Assume that $\lambda_{t}=(1/2)\gamma
F_{t}/\|\mathbf{p}^{(t)}\|_{D_{\mathbf{x}},L_{2}}^{2}$. Then it holds that
$\|\mathbf{q}^{(t+1)}\|_{D_{\mathbf{x}},L_{2}}\leq\|\mathbf{q}^{(t)}\|_{D_{\mathbf{x}},L_{2}}(1-(1/16)F_{t}^{2/K}\gamma^{2}/C_{1}^{2/K})^{1/2}$.

###### Proof.

Note that by definition, we have that

$\displaystyle\mathbf{q}^{(t)}\cdot\mathbf{p}^{(t)}$
$\displaystyle\leq\operatorname*{\mathbf{E}}_{(\mathbf{x},y)\sim
D}[f^{\prime}(\mathbf{x})\mathbf{q}^{(t)}\cdot\mathbf{x}\mid
B_{t}]+8cC_{1}^{1/K}\epsilon^{1-1/K}\|\mathbf{q}^{(t)}\|_{D_{\mathbf{x}},L_{2}}$
$\displaystyle=-\operatorname*{\mathbf{E}}_{(\mathbf{x},y)\sim
D}[|\mathbf{q}^{(t)}\cdot\mathbf{x}|\mathds{1}\\{y\neq\mathrm{sign}(\mathbf{q}^{(t)}\cdot\mathbf{x})\\}\mid(\mathbf{x},y)\in
B_{t}]+8cC_{1}^{1/K}\epsilon^{1-1/K}\|\mathbf{q}^{(t)}\|_{D_{\mathbf{x}},L_{2}}$
$\displaystyle\leq-(\gamma
F_{t}-8cC_{1}^{1/K}\epsilon^{1-1/K})\|\mathbf{q}^{(t)}\|_{D_{\mathbf{x}},L_{2}}\leq-(\gamma
F_{t}/2)\|\mathbf{q}^{(t)}\|_{D_{\mathbf{x}},L_{2}}\;,$ (60)

where we used that $\gamma F_{t}\geq\epsilon^{1-2/\sqrt{K}}\geq
8cC_{1}^{1/K}\epsilon^{1-1/K}$ for all $F_{t}\geq F$. Next, we calculate the
norm of $\mathbf{p}^{(t)}$. We have that

$\displaystyle\|\mathbf{p}^{(t)}\|_{D_{\mathbf{x}},L_{2}}$
$\displaystyle\leq\sup_{\mathbf{v}\in\mathbb{R}^{n},\|\mathbf{v}\|_{D_{\mathbf{x}},L_{2}}=1}\operatorname*{\mathbf{E}}_{(\mathbf{x},y)\sim
D_{t}}[|\mathbf{v}\cdot\mathbf{x}|\mathds{1}\\{y\neq\mathrm{sign}(\mathbf{q}^{(t)}\cdot\mathbf{x})\\}]\leq
2C_{1}^{1/K}F_{t}^{1-1/(K-1)}\;,$

where in the last inequality we used the concentration of the tails.
Therefore, we have that

$\displaystyle\|\mathbf{q}^{(t+1)}\|_{D_{\mathbf{x}},L_{2}}^{2}$
$\displaystyle=\|\mathbf{q}^{(t)}\|_{D_{\mathbf{x}},L_{2}}^{2}+2\lambda_{t}\mathbf{q}^{(t)}\cdot\mathbf{p}^{(t)}+\lambda_{t}^{2}\|\mathbf{p}^{(t)}\|_{D_{\mathbf{x}},L_{2}}^{2}$
$\displaystyle\leq\|\mathbf{q}^{(t)}\|_{D_{\mathbf{x}},L_{2}}^{2}-\lambda_{t}\gamma
F_{t}\|\mathbf{q}^{(t)}\|_{D_{\mathbf{x}},L_{2}}+4C_{1}^{2/K}F_{t}^{-2/K}\lambda_{t}^{2}$
$\displaystyle\leq\|\mathbf{q}^{(t)}\|_{D_{\mathbf{x}},L_{2}}^{2}-\lambda_{t}(F_{t}\gamma/2)\|\mathbf{q}^{(t)}\|_{D_{\mathbf{x}},L_{2}}$
$\displaystyle=\|\mathbf{q}^{(t)}\|_{D_{\mathbf{x}},L_{2}}^{2}(1-(1/16)F_{t}^{2/K}\gamma^{2}/C_{1}^{2/K})\;,$

where we used that $\lambda_{t}=(1/2)\gamma
F_{t}/\|\mathbf{p}^{(t)}\|_{D_{\mathbf{x}},L_{2}}^{2}$. ∎

Finally, we show that $\mathbf{p}^{(t)}$ does not decrease the correlation
with $\mathbf{w}^{\ast}$ by a lot. We show the following

######  Claim 7.7.

It holds that
$\mathbf{w}^{\ast}\cdot\mathbf{p}^{(t)}\geq-8cC_{1}^{1/K}\epsilon^{1-1/K}$.

###### Proof.

Note that $\mathbf{p}^{(t)}$ is a robust estimator of
$\operatorname*{\mathbf{E}}[f^{\prime}(\mathbf{x})\mathbf{x}\mid|\mathbf{q}^{(t)}\cdot\mathbf{x}|\geq\gamma\|\mathbf{q}^{(t)}\|_{D_{\mathbf{x}},L_{2}}]$
with error $8cC_{1}^{1/K}\epsilon^{1-1/K}$ and it holds that
$\operatorname*{\mathbf{E}}[f^{\prime}(\mathbf{x})\mathbf{w}^{\ast}\cdot\mathbf{x}\mid|\mathbf{q}^{(t)}\cdot\mathbf{x}|\geq\gamma\|\mathbf{q}^{(t)}\|_{D_{\mathbf{x}},L_{2}}]\geq
0$, therefore we have that

$\displaystyle\mathbf{w}^{\ast}\cdot\mathbf{p}^{(t)}\geq-8cC_{1}^{1/K}\epsilon^{1-1/K}\;.$

∎

From 7.6, we have that after
$t=\Theta(\log(1/\epsilon))C_{1}^{2/K}/(\gamma^{2}F^{2/K})$ iterations, we
have that

$\displaystyle\mathbf{q}^{(t)}\cdot\mathbf{w}^{\ast}$
$\displaystyle\leq\|\mathbf{q}^{(t)}\|_{D_{\mathbf{x}},L_{2}}\leq\|\mathbf{q}^{(0)}\|_{D_{\mathbf{x}},L_{2}}(1-\epsilon^{C_{3}/(2K)+2/K})^{t/2}\leq\epsilon^{1/2}\;.$

On the other hand, we have that

$\displaystyle\mathbf{q}^{(t)}\cdot\mathbf{w}^{\ast}$
$\displaystyle\geq\mathbf{q}^{(t-1)}\cdot\mathbf{w}^{\ast}+\lambda_{t}\mathbf{p}^{(t-1)}\cdot\mathbf{w}^{\ast}$
$\displaystyle\geq\mathbf{q}^{(0)}\cdot\mathbf{w}^{\ast}-8cC_{1}^{3/K}\epsilon^{1-1/K}t\gamma/F^{1-2/(K-1)}$
$\displaystyle\geq(1/2)\epsilon^{2/\sqrt{K}}-C^{\prime}C_{1}^{3/K}\epsilon^{(1-1/K)(8/\sqrt{K})}\log(1/\epsilon)$
$\displaystyle\geq(1/2)\epsilon^{2/\sqrt{K}}-C^{\prime}C_{1}^{3/K}\epsilon^{3/\sqrt{K}}\geq(1/4)\epsilon^{2/\sqrt{K}}\;,$

where $C^{\prime}>0$ is an absolute constant and we used that
$\gamma=\epsilon^{4/\sqrt{K}}$ and $F=\epsilon^{1-8/\sqrt{K}}$, therefore we
get that $(1/4)\epsilon^{2/\sqrt{K}}\leq\epsilon^{1/2}$, which is a
contradiction. Therefore, after at most
$O(\log(1/\epsilon)/(\epsilon^{c_{3}}))$ iterations for some absolute constant
$c_{3}>0$, we have that
$\operatorname*{\mathbf{E}}[\mathds{1}\\{y\neq\mathrm{sign}(\mathbf{q}^{(t)}\cdot\mathbf{x}),|\mathbf{q}^{(t)}\cdot\mathbf{x}|\geq\gamma\|\mathbf{q}^{(t)}\|_{D_{\mathbf{x}},L_{2}}\\}]\leq
F=\epsilon^{1-8/\sqrt{K}}$. To conclude the proof, note that by the anti-
concentration assumption, we have that
$\operatorname*{\mathbf{E}}[\mathds{1}\\{|\mathbf{q}^{(t)}\cdot\mathbf{x}|\geq\gamma\|\mathbf{q}^{(t)}\|_{D_{\mathbf{x}},L_{2}}\\}]\geq
1-\gamma^{C}=1-O(\epsilon^{4C/\sqrt{K}})\geq 1/2$ and the result follows. This
completes the proof of Proposition 7.3. ∎

Input: Access to at most $\mathrm{opt}^{1/\sqrt{K}}$-corrupted samples from a
distribution $D$, $\mathrm{opt},\epsilon,K>0$.

Output: A $d$-degree PTF $h$ and interval $I$ so that:
$\operatorname*{\mathbf{Pr}}_{(\mathbf{x},y)\sim D}[h(\mathbf{x})\neq y\mid
I]\leq O_{d,K}(\mathrm{opt}_{I}^{1-1/\sqrt{K}})+\epsilon\,,$ and a list of
unclassified regions $Q$.

Parameters: $c>0$ sufficiently small absolute constant.

  1. 1.

Let $Z=\\{\epsilon,\ldots,\mathrm{opt}^{O(1/\sqrt{K})}\\}$.

  2. 2.

For each $\epsilon^{\prime}\in Z$, do

    1. (a)

Run Algorithm 1 for $\log(1/\eta)$ times with parameters $\epsilon^{\prime},K$
and get $T=\\{(p_{1},I_{1})\ldots(p_{\log(1/\eta)},I_{\log(1/\eta)})\\}$.

    2. (b)

For each $(p,I)\in T$, if $\operatorname*{\mathbf{Pr}}_{(\mathbf{x},y)\sim
D}[p(\mathbf{x})\neq y\mid\mathbf{x}\in I]\leq O(\epsilon^{\prime
1-8/\sqrt{K}})$, then keep $(p,I)$ and stop the search.

  3. 3.

Use Proposition 6.3 and output a list $Q$ of unclassified regions with respect
to $(p,I)$.

  4. 4.

Return $(p,I),Q$.

Algorithm 2 Partial-Classifier

As outlined in our discussion, our algorithm partitions the unclassified
regions into more manageable sub-regions. In particular, the partition ensures
that the resulting distributions conditioned on each of the sub-regions
satisfy good (anti-)concentration properties. To facilitate this, we introduce
the following definition, which characterizes the attributes of each
subregion. Specifically, given a polynomial transformation $\mathbf{q}$ and a
rectangle $R$ we want the normal distribution conditional on
$\mathbf{q}(\mathbf{x})\in R$ to have both good anti-concentration and
concentration behavior, while $\mathbf{q}$ is also level-k super non-singular.

######  Definition 7.8 ((Anti-)concetrated Polynomial Slab).

Let $\mathbf{q}:\mathbb{R}^{n}\mapsto\mathbb{R}^{\ell}$ and a rectangle
$R\in\mathbb{R}^{\ell}$. We say that a tuple $(\mathbf{q},R)$ is an
$(\epsilon,k,K,d,\ell,\zeta)$-(anti-)concentrated if the following properties
are satisfied:

  1. 1.

Let $\mathcal{P}=\\{\mathbf{x}\in\mathbb{R}^{n}:q(\mathbf{x})\in R\\}$, then
for any polynomial $g:\mathbb{R}^{n}\mapsto\mathbb{R}$ of degree-$d$, for
$\epsilon<t<\epsilon^{2/K}$, it holds

$\displaystyle\operatorname*{\mathbf{Pr}}_{\mathbf{x}\sim\mathcal{N}(\mathbf{0},\mathbf{I})\mid{\mathcal{P}}}\left[\left|g(\mathbf{x})\right|<t\;\left\|g\right\|_{\mathcal{N}(\mathbf{0},\mathbf{I})\mid{\mathcal{P}},L_{2}}\right]\leq
t^{1/(2d)}\,,$

and for all $t>0$, it holds

$\displaystyle\operatorname*{\mathbf{Pr}}_{\mathbf{x}\sim\mathcal{N}(\mathbf{0},\mathbf{I})\mid{\mathcal{P}}}\left[\left|g(\mathbf{x})\right|>t\left\|g\right\|_{\mathcal{N}(\mathbf{0},\mathbf{I})\mid{\mathcal{P}},L_{2}}\right]\leq
O_{d,K}\left(\epsilon^{-1}t^{-K}\right)\;.$

  2. 2.

The mass of $\mathcal{P}$ is lower bound by $\zeta$, i.e.,
$\operatorname*{\mathbf{Pr}}_{\mathbf{x}\sim\mathcal{N}(\mathbf{0},\mathbf{I})}[q(\mathbf{x})\in
R]\geq\zeta$.

  3. 3.

$\mathbf{q}$ is level-$k$ super non-singular with respect to the tuple
$(\epsilon,d,K,M=3)$.

Our subsequent proposition demonstrates that Algorithm 2 classifies a region
that fulfills the (anti-)concentration property of Definition 7.8. Algorithm 2
employs Algorithm 1 to categorize the majority of points effectively.
Subsequently, it decomposes any remaining unclassified region into a list of
smaller subregions, each inheriting the (anti-)concentration property of
Definition 7.8.

######  Proposition 7.9.

Let $n,k,d,\ell,K\in\mathbb{Z}_{+}$, and $\epsilon,\mathrm{opt},\eta\in(0,1)$.
Let $D$ be a distribution on $\mathbb{R}^{n}\times\\{\pm 1\\}$ such that (i)
$D$ is at most $\mathrm{opt}$-corrupted with respect an unknown $d$-degree
PTF, (ii) the $\mathbf{x}$-marginal of $D$ follows standard $n$-dimensional
normal. Let $(\mathbf{q},R)$ be
$(\mathrm{opt},k,K,d,\ell,\zeta)$-(anti-)concentrated. Let $D_{Q}$ be the
distribution conditioned on $\mathbf{q}(\mathbf{x})\in R$. There exists an
algorithm (Algorithm 2) that draws
$N=O(n^{d})\mathrm{poly}_{K,d}(d,1/\epsilon)\log(1/\eta)$ at most
$\mathrm{opt}^{1/\sqrt{K}}$-corrupted samples from $D_{Q}$, runs in sample-
polynomial time and with probability at least $1-\eta$ computes:

  1. 1.

A set of $m$-dimensional vector-valued polynomial
$\mathbf{q^{\prime}}:\mathbb{R}^{n}\mapsto\mathbb{R}^{m}$ where
$m=O_{d,\ell,K}(1)$ and a set of $m$-dimensional axis-aligned rectangles
$\\{R^{(1)},\ldots R^{(t)}\\}$ with $t\leq\mathrm{opt}^{-2m}$ satisfying

    1. (a)

For each $R^{(i)}$, the tuple $(\mathbf{q}^{\prime},R^{(i)})$ is
$(\mathrm{opt},k-1,K,d,m,\zeta)$-(anti-)concentrated.

    2. (b)

For the union of the sets
$S:=\bigcup_{i}\\{\mathbf{x}:\mathbf{q}^{\prime}(\mathbf{x})\in R^{(i)}\\}$,
it holds that

$\operatorname*{\mathbf{Pr}}_{\mathbf{x}\sim\mathcal{N}(\mathbf{0},\mathbf{I})}\left[\mathbf{x}\in
S\mid\mathbf{q}(\mathbf{x})\in R\right]<\mathrm{opt}^{c/(2d)}\,.$

  2. 2.

An at most $d$-degree polynomial $p$ and a region $I=\\{q(\mathbf{x})\in R\cap
S^{c}\\}$ such that

$\operatorname*{\mathbf{Pr}}_{(\mathbf{x},y)\sim
D_{Q}}[\mathrm{sign}(p(\mathbf{x}))\neq y\mid\mathbf{x}\in I]\leq
C_{d,K}\mathrm{opt}_{I}^{1-O(1/\sqrt{K})}+\mathrm{opt}+\epsilon\,,$

for some absolute constant $C_{d,K}>0$.

###### Proof.

From Definition 7.8, for any $\rho\in(\mathrm{opt},\mathrm{opt}^{2/K})$, we
have that for any polynomial $p:\mathbb{R}^{n}\mapsto\mathbb{R}$, it holds

$\operatorname*{\mathbf{Pr}}_{\mathbf{x}\sim
D_{Q}}\left[p(\mathbf{x})<\rho\;\|p(\mathbf{x})\|_{D_{Q},L_{2}}\right]\leq\rho^{1/(2d)}.$
(61)

In what follows for a tensor
$\mathbf{A}\in\mathbb{R}^{k_{1}\otimes\cdots\otimes k_{m}}$ we define
$\mathbf{A}^{\flat}$ its flattening to a vector of $\mathbb{R}^{k_{1}\cdots
k_{m}}$. Let $\mathbf{z}=((\mathbf{x},1)^{\otimes d})^{\flat}$ and denote as
$D_{\otimes}$ the distribution of $\mathbf{z}$. Notice that the $\mathbf{z}$
contains a basis for all polynomials of degree at most $d$, so the dimension
of $\mathbf{z}$ is $(n+1)^{d}$. Then for any vector
$\mathbf{v}\in\mathbb{R}^{(n+1)^{d}}$, we have that
$\mathbf{v}\cdot\mathbf{z}$ is an at most $d$-degree polynomial, therefore we
have that for any $\mathbf{v}\in\mathbb{R}^{(n+1)^{d}}$ it holds that

$\operatorname*{\mathbf{Pr}}_{\mathbf{z}\sim
D_{\otimes}}\left[|\mathbf{v}\cdot\mathbf{z}|<\rho\;\|\mathbf{v}\cdot\mathbf{z}\|_{D_{\otimes},L_{2}}\right]\leq\rho^{1/(2d)}.$

We first show that we can transform $\mathbf{z}$ so that the covariance of
$\mathbf{z}$ is equal to identity. Note that
$\operatorname*{\mathbf{E}}[\mathbf{z}\mathbf{z}^{\top}]$ is Hermitian matrix,
so it can be written as
$\operatorname*{\mathbf{E}}[\mathbf{z}\mathbf{z}^{\top}]=\mathbf{P}\mathbf{D}\mathbf{P}^{\top}$,
for some diagonal matrix $\mathbf{D}$ and orthonormal matrix $\mathbf{P}$. Let
$\mathbf{T}=\mathbf{P}\mathbf{D}^{-1/2}$ and let
$\mathbf{z}^{\prime}=\mathbf{T}\mathbf{z}$. It holds that
$\operatorname*{\mathbf{E}}[\mathbf{z}^{\prime}(\mathbf{z}^{\prime})^{\top}]=\mathbf{I}$.
Furthermore, note that if $\mathbf{v}\cdot\mathbf{z}$ is a polynomial before
the transformation, then
$(\mathbf{T}^{-1}\mathbf{v})\cdot\mathbf{z}^{\prime}=\mathbf{v}\cdot\mathbf{z}$.
Therefore all the polynomials can be expressed in the new space. To calculate
the $\mathbf{P},\mathbf{D}$, we can run standard Gram–Schmidt
orthonormalization and get a $\gamma$-approximation (in $L_{2}$ sense) of
these matrices with $\mathrm{poly}(d/\gamma)$ samples and time.

Denote by $\mathcal{C}$ the at most $\mathrm{opt}^{1/\sqrt{K}}$-corrupted
oracle to the distribution $D_{Q}$. Before we apply Algorithm 1 to find a new
hypothesis, we need to guess the corruption rate of $\mathcal{C}$. For this
purpose, we construct a list
$Z=\\{\epsilon,2\epsilon,\ldots,\mathrm{opt}^{1/\sqrt{K}}\\}$ containing all
the possible corruption levels. If $\mathrm{opt}_{Q}$ is the true corruption
level of $\mathcal{C}$, then there exists $\mathrm{opt}^{\prime}\in Z$, such
that
$\mathrm{opt}_{Q}\leq\mathrm{opt}^{\prime}\leq\mathrm{opt}_{Q}+2\epsilon$.
Therefore, for the correct noise rate, from Proposition 7.3 using Algorithm 1
with probability at least $2/3$, we get a polynomial
$p:\mathbb{R}^{n}\mapsto\mathbb{R}$ and a set $I=\\{|p(\mathbf{x})|\geq
2\mathrm{opt}_{Q}^{4/\sqrt{K}}\\}$ so that

$\operatorname*{\mathbf{Pr}}_{(\mathbf{x},y)\sim
D_{Q}}[\mathrm{sign}(p(\mathbf{x}))\neq y\mid\mathbf{x}\in I]\leq
C_{K,d}(\mathrm{opt}_{I}+\epsilon)^{1-O(1/\sqrt{K})}\,.$

By running the same procedure $\log(1/\eta)$ and testing the result, we can
amplify the probability of this procedure to $1-\eta$. Note that from Equation
61, we have that

$\operatorname*{\mathbf{Pr}}[\mathbf{x}\in I\mid\mathbf{q}(\mathbf{x})\in
R]\geq 1-(\mathrm{opt}_{Q})^{2/(d\sqrt{K})}\geq 1-(\mathrm{opt})^{2/(dK)}\;,$
(62)

where we used that $\mathrm{opt}_{Q}\leq\mathrm{opt}^{1/\sqrt{K}}$. To
classify the rest of the points in the set $\\{q(\mathbf{x})\in
R,\mathbf{x}\not\in I\\}$, we need to split the region into smaller sets using
Proposition 6.3. From Proposition 6.3, given the polynomial $p$ and the
current polynomial vector $q$ for some $m=O_{d,K,\ell}(1)$, we get the
following: a new $m$-dimensional vector-valued polynomial
$\mathbf{q^{\prime}}:\mathbb{R}^{n}\mapsto\mathbb{R}^{m}$ and a set of
$m$-dimensional axis-aligned rectangles $\\{R^{(i)}\\}$ of size at most
$\mathrm{opt}^{-2m}$ satisfy so that the sets for each $i$, it holds that
$(\mathbf{q}^{\prime},R^{(i)})$ is
$(\mathrm{opt},k-1,K,d,m,\epsilon^{3+5md}\zeta)$-(anti-)concentrated.
Moreover, let $S:=\bigcup_{i}\\{\mathbf{x}:\mathbf{q}^{\prime}(\mathbf{x})\in
R^{(i)}\\}$ , we have that $\operatorname*{\mathbf{Pr}}[\mathbf{x}\in
S,\mathbf{x}\in I\mid q(\mathbf{x})\in R]\leq\mathrm{opt}^{2}$ and
$\operatorname*{\mathbf{Pr}}[\mathbf{x}\not\in S,\mathbf{x}\not\in
I\mid\mathbf{q}(\mathbf{x})\in R]\leq\mathrm{opt}^{2}$. Define $J=(I\cup
S^{c})-S$. Note that for the region $J$ it holds that
$\operatorname*{\mathbf{Pr}}[\mathbf{x}\in J\mid\mathbf{q}(\mathbf{x})\in
R]\geq\operatorname*{\mathbf{Pr}}[\mathbf{x}\in I\mid\mathbf{q}(\mathbf{x})\in
R]-\mathrm{opt}^{2}$ and therefore, he have that
$\operatorname*{\mathbf{Pr}}_{(\mathbf{x},y)\sim
D_{Q}}[\mathrm{sign}(p(\mathbf{x}))\neq y\mid\mathbf{x}\in J]\leq
C_{K,d}(\mathrm{opt}_{I}+\epsilon)^{1-O(1/\sqrt{K})}+\mathrm{opt}\,.$ and that
$\operatorname*{\mathbf{Pr}}[\mathbf{x}\in J\mid\mathbf{q}(\mathbf{x})\in
R]\geq 1-2(\mathrm{opt})^{2/(dK)}$.

∎

Input: Access to at most $\mathrm{opt}$-corrupted samples from a distribution
$D$ over $\mathbb{R}^{n}\times\\{\pm 1\\}$, noise rate $\mathrm{opt}>0$,
parameters $\epsilon,K>0$

Output: A decision list of PTFs $h$ so that:
$\operatorname*{\mathbf{Pr}}_{(\mathbf{x},y)\sim D}[h(\mathbf{x})\neq y]\leq
O_{d,K}(\mathrm{opt}^{1-O(1/\sqrt{K})})+\epsilon$.

  1. 1.

Run Algorithm 2 on $D$ and get $h=\\{(p,I)\\}$, $Q$.

  2. 2.

While $Q$ is not empty, do

    1. (a)

$(\mathbf{q},R)\leftarrow\mathrm{pop}(Q)$.

    2. (b)

Let $D_{Q}$ be the distribution $D$ conditioned on $\mathbf{q}(\mathbf{x})\in
R$.

    3. (c)

Run Algorithm 2 on $D_{Q}$ and get $\\{(p,I)\\}$, $Q^{\prime}$.

    4. (d)

Let $Q=Q\cup Q^{\prime}$ and $h=h\cup\\{p,I\\}$.

  3. 3.

Return $h$.

Algorithm 3 Combined Algorithm

###  7.1 Proof of Theorem 7.1

Let $\mathcal{C}$ be the $\mathrm{opt}$-corrupted oracle access to the
distribution $D$. For any event $Q$, we denote $\mathcal{C}_{Q}$ the oracle
access to the distribution $D_{Q}$ i.e., the distribution $D$ conditioned on
the event $Q$. We can simulate $\mathcal{C}_{Q}$ from $\mathcal{C}$ by
accepting only points that satisfy the event $Q$. We denote as
$\mathrm{opt}_{Q}$ the corruption rate of the oracle $\mathcal{C}_{Q}$. Let
$k$ be a sufficiently large multiply of $d$ and $C_{K}=O(1/\sqrt{K})$. We can
assume without loss of generality that $\mathrm{opt}$ is less than an absolute
constant $C^{\prime}=O_{d,K}(1)$ Otherwise, the constant hypothesis will have
error $O(C^{\prime})$. Moreover, if $\epsilon>\mathrm{opt}$ then we can take
$\mathrm{opt}=\epsilon$ as the error guarantee of the algorithm will be
$O(\epsilon^{1-O(1/\sqrt{K})})$. Otherwise, we can assume that
$\mathrm{opt}/2<\epsilon<2\mathrm{opt}$ as we can find a $2$-approximation of
$\mathrm{opt}$ by re-running the algorithm $1/\epsilon$ times. The
distribution is standard $d$-dimensional normal, hence, it satisfies the
assumptions of Proposition 7.9 for $\mathbf{q}(\mathbf{x})=\mathbf{1}$ and
$R=\mathbb{R}^{n}$. Therefore, from Step (1), we get a polynomial $p$ and a
region $I$ so that $\operatorname*{\mathbf{Pr}}_{(\mathbf{x},y)\sim
D}[\mathrm{sign}(p(\mathbf{x}))\neq y\mid\mathbf{x}\in I]\leq
C^{\prime}(\mathrm{opt}+\epsilon)^{1-C_{K}}\,.$ First, note that our algorithm
in Step (2), maintains a list of unclassified regions $Q_{1},\ldots,Q_{\xi}$.
In order to show that our algorithm works, we need to show that in each
iteration, we decrease the unclassified region and we output a classifier that
classifies accurately most of the points. We first show that we can remove the
regions with noise rates more than $\mathrm{opt}^{C_{K}}$ as their total mass
contributes to the error at most $\mathrm{opt}^{1-C_{K}}$. Denote with
$\Xi_{1},\ldots,\Xi_{l}$ the regions in $Q$ so that
$\operatorname*{\mathbf{Pr}}_{(\mathbf{x},y)\sim D}[p^{*}(\mathbf{x})\neq
y\mid\Xi_{i}]\geq(\mathrm{opt})^{C_{K}}.$ We show that
$\operatorname*{\mathbf{Pr}}_{(\mathbf{x},y)\sim
D}[\mathbf{x}\in\cup_{i=1}^{l}\Xi_{i}]\leq\mathrm{opt}^{1-C_{K}}$.

######  Claim 7.10.

It holds that $\operatorname*{\mathbf{Pr}}_{(\mathbf{x},y)\sim
D}[\mathbf{x}\in\cup_{i=1}^{l}\Xi_{i}]\leq\mathrm{opt}^{1-C_{K}}$.

###### Proof.

Let $A\cup_{i=1}^{l}\Xi_{i}=\mathbb{R}^{n}$. We have that

$\displaystyle\mathrm{opt}$
$\displaystyle=\operatorname*{\mathbf{Pr}}_{(\mathbf{x},y)\sim
D}[p^{*}(\mathbf{x})\neq y]$
$\displaystyle=\operatorname*{\mathbf{Pr}}_{(\mathbf{x},y)\sim
D}[p^{*}(\mathbf{x})\neq y\mid\mathbf{x}\in
A]\operatorname*{\mathbf{Pr}}_{\mathbf{x}\sim D_{\mathbf{x}}}[\mathbf{x}\in
A]+\sum_{i=1}^{l}\operatorname*{\mathbf{Pr}}_{(\mathbf{x},y)\sim
D}[p^{*}(\mathbf{x})\neq
y\mid\mathbf{x}\in\Xi_{i}]\operatorname*{\mathbf{Pr}}_{\mathbf{x}\sim
D_{\mathbf{x}}}[\mathbf{x}\in\Xi_{i}]$
$\displaystyle\geq\sum_{i=1}^{l}\operatorname*{\mathbf{Pr}}_{(\mathbf{x},y)\sim
D}[p^{*}(\mathbf{x})\neq
y\mid\mathbf{x}\in\Xi_{i}]\operatorname*{\mathbf{Pr}}_{\mathbf{x}\sim
D_{\mathbf{x}}}[\mathbf{x}\in\Xi_{i}]\geq\mathrm{opt}^{C_{K}}\operatorname*{\mathbf{Pr}}_{\mathbf{x}\sim
D_{\mathbf{x}}}[\mathbf{x}\in\cup_{i=1}^{l}\Xi_{i}]\;.$

By rearranging the above inequality, the result follows. ∎

Next, we show that in each iteration, we remove a large mass and we classify
optimally the points of this mass. Let $(\mathbf{q},R)$ be the element, we pop
from $Q$ at Step (2a). For some $k\in\mathbb{Z},\ell>0$, the $(\mathbf{q},R)$
is $(\epsilon,k,K,d,\ell,\epsilon)$-(anti-)concentrated. For this region one
of two events can happen: Either the corrupted oracle $\mathcal{C}_{Q}$ has a
corruption rate more than $\mathrm{opt}^{C_{K}}$ in which case Step (2c) gives
a constant hypothesis in this region, or we are given a partial classifier
$(p,I)$ and a new set of regions $\\{\mathbf{q}^{\prime},R^{(i)}\\}$ that are
$(\epsilon,k-1,K,d,m,\epsilon^{3+5md})$-(anti-)concentrated, for
$m=O_{\ell,K}(1)$. For the partial hypothesis, we have from Proposition 7.9,
that

$\operatorname*{\mathbf{Pr}}_{(\mathbf{x},y)\sim
D_{Q}}[\mathrm{sign}(p(\mathbf{x}))\neq y\mid\mathbf{x}\in I]\leq
C_{K,d}^{\prime}\mathrm{opt}_{I}^{1-C_{K}}+\mathrm{opt}+\epsilon\,,$

Note that $\operatorname*{\mathbf{Pr}}[\mathbf{x}\in I\mid q(\mathbf{x})\in
R]\geq 1-\mathrm{opt}_{I}^{c/(2d)}$, therefore in each step we remove at least
$\operatorname*{\mathbf{Pr}}[q(\mathbf{x})\in R](1-\mathrm{opt}_{I}^{c/(2d)})$
mass.

Let $S_{i}$ be the unclassified regions on depth $i$. This means that set
$S_{i}$ is a union of sets $R^{(i)}$ that are constructed after $i$
applications of Polynomial-Set-Partitioner. We show that after $t=O(dC_{K})$
steps, we have classified all but $O(\mathrm{opt})$ mass. Note that after $t$
iterations, we have that
$\operatorname*{\mathbf{Pr}}_{\mathbf{x}\sim\mathcal{N}(\mathbf{0},\mathbf{I})}\left[\mathbf{x}\in
S_{t}\right]\leq\mathrm{opt}^{C_{K}ct/(2d)}$, hence for $t=O(dC_{K})$ this is
of order $\mathrm{opt}$. Therefore, we can drop the remaining sets. To analyze
the correctness of our algorithm, we denote the following, let
$\\{(p_{1},I_{1}),\ldots,(p_{T},I_{T})\\}$ be the decision list classifier and
let $\Xi$ be the union of regions discarded because the corruption rate was
more than $\mathrm{opt}^{C_{K}}$. We denote as $h(\mathbf{x})$ the classifier
that if $\mathbf{x}\in I_{i}$ for some $i$ then
$h(\mathbf{x})=\mathrm{sign}(p_{i}(\mathbf{x}))$. We have that

$\displaystyle\operatorname*{\mathbf{Pr}}_{\mathbf{x}\sim\mathcal{N}(\mathbf{0},\mathbf{I})}\left[h(\mathbf{x})\neq
y\right]$
$\displaystyle\leq\sum_{i=1}^{T}\operatorname*{\mathbf{Pr}}_{\mathbf{x}\sim\mathcal{N}(\mathbf{0},\mathbf{I})}\left[\mathrm{sign}(p_{i}(\mathbf{x}))\neq
y\mid\mathbf{x}\in
I_{i}\right]\operatorname*{\mathbf{Pr}}_{\mathbf{x}\sim\mathcal{N}(\mathbf{0},\mathbf{I})}\left[\mathbf{x}\in
I_{i}\right]$
$\displaystyle+\operatorname*{\mathbf{Pr}}_{\mathbf{x}\sim\mathcal{N}(\mathbf{0},\mathbf{I})}\left[\mathbf{x}\in\Xi\right]+\operatorname*{\mathbf{Pr}}_{\mathbf{x}\sim\mathcal{N}(\mathbf{0},\mathbf{I})}\left[\mathbf{x}\not\in\cup_{i}I_{i}\right]\;.$

We have shown that
$\operatorname*{\mathbf{Pr}}_{\mathbf{x}\sim\mathcal{N}(\mathbf{0},\mathbf{I})}\left[\mathrm{sign}(p_{i}(\mathbf{x}))\neq
y\mid\mathbf{x}\in I_{i}\right]\leq
C_{K,d}^{\prime}(\mathrm{opt}_{I_{i}})^{1-C_{K}}+\mathrm{opt}+\epsilon$.
Therefore we have that

$\displaystyle\sum_{i=1}^{T}\operatorname*{\mathbf{Pr}}_{\mathbf{x}\sim\mathcal{N}(\mathbf{0},\mathbf{I})}\left[\mathrm{sign}(p_{i}(\mathbf{x}))\neq
y\mid\mathbf{x}\in
I_{i}\right]\operatorname*{\mathbf{Pr}}_{\mathbf{x}\sim\mathcal{N}(\mathbf{0},\mathbf{I})}\left[\mathbf{x}\in
I_{i}\right]$ $\displaystyle\leq
C_{K,d}^{\prime}\sum_{i=1}^{T}(\mathrm{opt}_{I_{i}}^{1-C_{K}}+\mathrm{opt}+\epsilon)\operatorname*{\mathbf{Pr}}_{\mathbf{x}\sim\mathcal{N}(\mathbf{0},\mathbf{I})}\left[\mathbf{x}\in
I_{i}\right]$ $\displaystyle\leq
C_{K,d}^{\prime}\mathrm{opt}^{1-C_{K}}+\epsilon\;,$

where the last inequality follows from the power means inequality.
Furthermore, from 7.10, we have shown that
$\operatorname*{\mathbf{Pr}}_{\mathbf{x}\sim\mathcal{N}(\mathbf{0},\mathbf{I})}\left[\mathbf{x}\in\Xi\right]\leq\mathrm{opt}^{1-C_{K}}$.
Finally, we have shown that
$\operatorname*{\mathbf{Pr}}_{\mathbf{x}\sim\mathcal{N}(\mathbf{0},\mathbf{I})}\left[\mathbf{x}\not\in\cup_{i}I_{i}\right]=O(\mathrm{opt})$.
Therefore,

$\operatorname*{\mathbf{Pr}}_{(\mathbf{x},y)\sim D}\left[h(\mathbf{x})\neq
y\right]\leq C_{K,d}^{\prime}(\mathrm{opt})^{1-C_{K}}+\epsilon\;.$

This completes the proof of Theorem 7.1.

## References

  * [ABL17] P. Awasthi, M. F. Balcan, and P. M. Long.  The power of localization for efficiently learning linear separators with noise.  J. ACM, 63(6):50:1–50:27, 2017.
  * [BEK02] N. Bshouty, N. Eiron, and E. Kushilevitz.  PAC Learning with Nasty Noise.  Theoretical Computer Science, 288(2):255–275, 2002.
  * [BFKV96] A. Blum, A. M. Frieze, R. Kannan, and S. Vempala.  A polynomial-time algorithm for learning noisy linear threshold functions.  In 37th Annual Symposium on Foundations of Computer Science, FOCS ’96, pages 330–338, 1996.
  * [BL13] M. Balcan and P. Long.  Active and passive learning of linear separators under log-concave distributions.  In Conference on Learning Theory, pages 288–316. PMLR, 2013.
  * [CW01] A. Carbery and J. Wright.  Distributional and $L^{q}$ norm inequalities for polynomials over convex bodies in $R^{n}$.  Mathematical Research Letters, 8(3):233–248, 2001.
  * [Dan15] A. Daniely.  A PTAS for agnostically learning halfspaces.  In Proceedings of The 28th Conference on Learning Theory, COLT 2015, pages 484–502, 2015.
  * [Dan16] A. Daniely.  Complexity theoretic limitations on learning halfspaces.  In Proceedings of the 48th Annual Symposium on Theory of Computing, STOC 2016, pages 105–117, 2016.
  * [DDFS14] A. De, I. Diakonikolas, V. Feldman, and R. A. Servedio.  Nearly optimal solutions for the chow parameters problem and low-weight approximation of halfspaces.  J. ACM, 61(2):11:1–11:36, 2014.
  * [DDS12] C. Daskalakis, I. Diakonikolas, and R. A. Servedio.  Learning Poisson Binomial Distributions.  In Proceedings of the 44th Symposium on Theory of Computing, pages 709–728, 2012.
  * [Der65] M. Dertouzos.  Threshold Logic: A Synthesis Approach.  MIT Press, Cambridge, MA, 1965.
  * [DGJ+10] I. Diakonikolas, P. Gopalan, R. Jaiswal, R. Servedio, and E. Viola.  Bounded independence fools halfspaces.  SIAM Journal on Computing, 39(8):3441–3462, 2010.
  * [DGK+20] I. Diakonikolas, S. Goel, S. Karmalkar, A. R. Klivans, and M. Soltanolkotabi.  Approximation schemes for ReLU regression.  In Conference on Learning Theory, COLT, volume 125 of Proceedings of Machine Learning Research, pages 1452–1485. PMLR, 2020.
  * [DHK+10] I. Diakonikolas, P. Harsha, A. Klivans, R. Meka, P. Raghavendra, R. A. Servedio, and L. Y. Tan.  Bounding the average sensitivity and noise sensitivity of polynomial threshold functions.  In STOC, pages 533–542, 2010.
  * [DK19] I. Diakonikolas and D. M. Kane.  Degree-$d$ Chow parameters robustly determine degree-$d$ PTFs (and algorithmic applications).  In Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, STOC 2019, 2019, pages 804–815. ACM, 2019.
  * [DK23] I. Diakonikolas and D. M. Kane.  Algorithmic high-dimensional robust statistics.  Cambridge University Press, 2023.
  * [DKK+16] I. Diakonikolas, G. Kamath, D. M. Kane, J. Li, A. Moitra, and A. Stewart.  Robust estimators in high dimensions without the computational intractability.  In Proceedings of FOCS’16, pages 655–664, 2016.
  * [DKMR22] I. Diakonikolas, D. M. Kane, P. Manurangsi, and L. Ren.  Cryptographic hardness of learning halfspaces with massart noise.  CoRR, abs/2207.14266, 2022.  Conference version in NeurIPS’22.
  * [DKN10] I. Diakonikolas, D. M. Kane, and J. Nelson.  Bounded independence fools degree-$2$ threshold functions.  In FOCS, pages 11–20, 2010.
  * [DKPZ21] I. Diakonikolas, D. M. Kane, T. Pittas, and N. Zarifis.  The optimality of polynomial regression for agnostic learning under gaussian marginals in the SQ model.  In Proceedings of The 34th Conference on Learning Theory, COLT, 2021.
  * [DKR23] I. Diakonikolas, D. M. Kane, and L. Ren.  Near-optimal cryptographic hardness of agnostically learning halfspaces and relu regression under gaussian marginals.  In ICML, 2023.
  * [DKS18] I. Diakonikolas, D. M. Kane, and A. Stewart.  Learning geometric concepts with nasty noise.  In Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2018, pages 1061–1073, 2018\.
  * [DOSW11] I. Diakonikolas, R. O’Donnell, R. A. Servedio, and Y. Wu.  Hardness results for agnostically learning low-degree polynomial threshold functions.  In Proceedings of the Twenty-Second Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2011, 2011, pages 1590–1606. SIAM, 2011.
  * [DRST14] I. Diakonikolas, P. Raghavendra, R. A. Servedio, and L. Y. Tan.  Average sensitivity and noise sensitivity of polynomial threshold functions.  SIAM J. Comput., 43(1):231–253, 2014.
  * [DS14] A. De and R. A. Servedio.  Efficient deterministic approximate counting for low-degree polynomial threshold functions.  In Symposium on Theory of Computing, STOC 2014, 2014, pages 832–841. ACM, 2014.
  * [DSTW10] I. Diakonikolas, R. Servedio, L.-Y. Tan, and A. Wan.  A regularity lemma, and low-weight approximators, for low-degree polynomial threshold functions.  In CCC, pages 211–222, 2010.
  * [DV04] J. Dunagan and S. Vempala.  A simple polynomial-time rescaling algorithm for solving linear programs.  In Proceedings of the 36th Annual ACM Symposium on Theory of Computing, pages 315–320, 2004.
  * [Hau92] D. Haussler.  Decision theoretic generalizations of the PAC model for neural net and other learning applications.  Information and Computation, 100:78–150, 1992.
  * [HKM14] P. Harsha, A. R. Klivans, and R. Meka.  Bounding the sensitivity of polynomial threshold functions.  Theory of Computing, 10:1–26, 2014.
  * [Kan10] D. M. Kane.  The Gaussian surface area and noise sensitivity of degree-d polynomial threshold functions.  In CCC, pages 205–210, 2010.
  * [Kan11] D. M. Kane.  k-independent gaussians fool polynomial threshold functions.  In IEEE Conference on Computational Complexity, pages 252–261, 2011\.
  * [Kan12a] D. M. Kane.  A pseudorandom generator for polynomial threshold functions of gaussian with subpolynomial seed length.  CoRR, abs/1210.1280, 2012.
  * [Kan12b] D. M. Kane.  A structure theorem for poorly anticoncentrated gaussian chaoses and applications to the study of polynomial threshold functions.  In FOCS, pages 91–100, 2012.
  * [KKMS08] A. Kalai, A. Klivans, Y. Mansour, and R. Servedio.  Agnostically learning halfspaces.  SIAM Journal on Computing, 37(6):1777–1805, 2008.  Special issue for FOCS 2005.
  * [KL93] M. J. Kearns and M. Li.  Learning in the presence of malicious errors.  SIAM Journal on Computing, 22(4):807–837, 1993.
  * [KLS09] A. Klivans, P. Long, and R. Servedio.  Learning Halfspaces with Malicious Noise.  Journal of Machine Learning Research, 10:2715–2740, 2009.
  * [KOS08] A. Klivans, R. O’Donnell, and R. Servedio.  Learning geometric concepts via Gaussian surface area.  In Proc. 49th IEEE Symposium on Foundations of Computer Science (FOCS), pages 541–550, Philadelphia, Pennsylvania, 2008.
  * [KSS94] M. Kearns, R. Schapire, and L. Sellie.  Toward Efficient Agnostic Learning.  Machine Learning, 17(2/3):115–141, 1994.
  * [Lan12] S. Lang.  Real and functional analysis, volume 142.  Springer Science & Business Media, 2012.
  * [MP68] M. Minsky and S. Papert.  Perceptrons: an introduction to computational geometry.  MIT Press, Cambridge, MA, 1968.
  * [MT94] W. Maass and G. Turan.  How fast can a threshold gate learn?  In S. Hanson, G. Drastal, and R. Rivest, editors, Computational Learning Theory and Natural Learning Systems, pages 381–414. MIT Press, 1994\.
  * [Mur71] S. Muroga.  Threshold logic and its applications.  Wiley-Interscience, New York, 1971.
  * [MZ10] R. Meka and D. Zuckerman.  Pseudorandom generators for polynomial threshold functions.  In STOC, pages 427–436, 2010.
  * [Nel73] E. Nelson.  The free markoff field.  Journal of Functional Analysis, 12(2):211–227, 1973.
  * [OST20] R. O’Donnell, R. A. Servedio, and L.-Y. Tan.  Fooling gaussian ptfs via local hyperconcentration.  In Proccedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, STOC 2020, 2020, pages 1170–1183. ACM, 2020.
  * [She09] A. Sherstov.  The intersection of two halfspaces has high threshold degree.  In Proc. 50th IEEE Symposium on Foundations of Computer Science (FOCS), 2009.
  * [SW19] A. A. Sherstov and P. Wu.  Near-optimal lower bounds on the threshold degree and sign-rank of ac${}^{\mbox{0}}$.  In Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, STOC 2019, 2019, pages 401–412. ACM, 2019.
  * [Tie23] S. Tiegel.  Hardness of agnostically learning halfspaces from worst-case lattice problems.  In COLT, 2023.
  * [TTV09] L. Trevisan, M. Tulsiani, and S. P. Vadhan.  Regularity, boosting, and efficiently simulating every high-entropy distribution.  In IEEE Conference on Computational Complexity, pages 126–136, 2009\.
  * [Val85] L. Valiant.  Learning disjunctions of conjunctions.  In Proceedings of the Ninth International Joint Conference on Artificial Intelligence, pages 560–566, 1985.