# Near-Optimal SQ Lower Bounds for Agnostically Learning Intersections of
Halfspaces

Daniel Hsu, Clayton Sanford, Rocco A. Servedio, Emmanouil V. Vlatakis-
Gkaragkounis Columbia University<EMAIL_ADDRESS>Supported by NSF
grants CCF-1740833, IIS-1563785, and a Sloan Re-search Fellowship.Columbia
University<EMAIL_ADDRESS>Supported by an NSF GRFP fellowship, NSF
grant CCF-1563155, and DH’s Google Faculty Research Award. Columbia
University<EMAIL_ADDRESS>Supported by NSF grants CCF-1814873,
IIS-1838154, CCF-1563155, and by the Simons Collaboration on Algorithms and
Geometry.Columbia University<EMAIL_ADDRESS>Supported by NSF
grants CCF-1703925, CCF-1763970,CCF-1814873, CCF-1563155, and by the Simons
Collaborationon Algorithms and Geometry.

#  Near-Optimal Statistical Query Lower Bounds for Agnostically Learning
Intersections of Halfspaces with Gaussian Marginals

Daniel Hsu, Clayton Sanford, Rocco A. Servedio, Emmanouil V. Vlatakis-
Gkaragkounis Columbia University<EMAIL_ADDRESS>Supported by NSF
grants CCF-1740833, IIS-1563785, and a Sloan Re-search Fellowship.Columbia
University<EMAIL_ADDRESS>Supported by an NSF GRFP fellowship, NSF
grant CCF-1563155, and DH’s Google Faculty Research Award. Columbia
University<EMAIL_ADDRESS>Supported by NSF grants CCF-1814873,
IIS-1838154, CCF-1563155, and by the Simons Collaboration on Algorithms and
Geometry.Columbia University<EMAIL_ADDRESS>Supported by NSF
grants CCF-1703925, CCF-1763970,CCF-1814873, CCF-1563155, and by the Simons
Collaborationon Algorithms and Geometry.

###### Abstract

We consider the well-studied problem of learning intersections of halfspaces
under the Gaussian distribution in the challenging _agnostic learning_ model.
Recent work of Diakonikolas et al. (2021b) shows that any Statistical Query
(SQ) algorithm for agnostically learning the class of intersections of $k$
halfspaces over $\mathbb{R}^{n}$ to constant excess error either must make
queries of tolerance at most $n^{-\tilde{\Omega}(\sqrt{\log k})}$ or must make
$2^{n^{\Omega(1)}}$ queries. We strengthen this result by improving the
tolerance requirement to $n^{-\tilde{\Omega}(\log k)}$. This lower bound is
essentially best possible since an SQ algorithm of Klivans et al. (2008)
agnostically learns this class to any constant excess error using $n^{O(\log
k)}$ queries of tolerance $n^{-O(\log k)}$. We prove two variants of our lower
bound, each of which combines ingredients from Diakonikolas et al. (2021b)
with (an extension of) a different earlier approach for agnostic SQ lower
bounds for the Boolean setting due to Dachman-Soled et al. (2014). Our
approach also yields lower bounds for agnostically SQ learning the class of
“convex subspace juntas” (studied by Vempala, 2010a) and the class of sets
with bounded Gaussian surface area; all of these lower bounds are nearly
optimal since they essentially match known upper bounds from Klivans et al.
(2008).

##  1 Introduction

Linear threshold functions, or _halfspaces_ , are ubiquitous in machine
learning. They arise in the context of many statistical models for
classification (Duda et al., 1973), and they are the focus of many well-known
machine learning methods, including Perceptron (Rosenblatt, 1962), Support
Vector Machines (Vapnik, 1982), and AdaBoost (Freund and Schapire, 1997). In
this work, we consider the problem of agnostic learning for a natural and
well-studied generalization of this function class: _intersections of
halfspaces_.

Although many efficient algorithms for learning halfspaces have been developed
to handle a wide variety of settings (Blumer et al., 1989, Blum et al., 1998b,
Kalai et al., 2008, Awasthi et al., 2017, Diakonikolas et al., 2021a), known
algorithms for intersections of halfspaces are conspicuously limited in scope
and applicability. Indeed, no efficient PAC learning algorithms are known even
for the case of intersections of two halfspaces. There, a learner faces a
“credit assignment” problem when considering negative examples, as either of
the two halfspaces may be responsible for an example being classified as
negative, but the learner is not privy to this information. This prevents a
straightforward formulation of the learning problem as a linear program, which
had sufficed in the case of learning single halfspaces.

Because of the apparent difficulty of going beyond single halfspaces, much of
the progress has come from learning under “nice” data marginal distributions,
such as the uniform distribution or the Gaussian distribution (Blum and
Kannan, 1997, Vempala, 1997, 2010b, Klivans et al., 2004, Kalai et al., 2008,
Klivans et al., 2008, Vempala, 2010a, Kane, 2014). The fastest algorithm to
date for agnostically learning intersections of halfspaces under Gaussian
marginals in $\mathbb{R}^{n}$ is $L^{1}$ polynomial regression (Kalai et al.,
2008), which was shown by Klivans et al. (2008) to successfully learn up to
any constant excess error in time $n^{O(\log k)}$. (Under the additional
assumption of realizability, Vempala (2010a) showed that when $k=o(n)$,
preprocessing with principal component analysis improves this running time to
$\operatorname*{poly}(n,k)+k^{O(\log k)}$.) Since this upper bound has
resisted improvement for several years, attention has turned to trying to
prove lower bounds, and such lower bounds are the subject of this paper.

The Statistical Query (SQ) model of Kearns (1998) offers an attractive setting
for proving unconditional lower bounds against a broad class of learning
algorithms. SQ learning algorithms can access data only through imperfect
estimates of the expected values of query functions with respect to the data
distribution. Nearly all known learning algorithms, including those of Kalai
et al. (2008), Klivans et al. (2008) and Vempala (2010a), can be implemented
within the SQ model, so lower bounds in the SQ model are evidence for the
computational difficulty of a learning problem. Because these algorithmic
results for agnostic learning hold only under “nice” marginal distributions,
it is of interest to prove _distribution-dependent_ SQ lower bounds under the
same marginals.

The pioneering work of Dachman-Soled et al. (2014) provided a blueprint for
proving such distribution-dependent SQ lower bounds. They proved an
equivalence between the approximation resilience of functions in a concept
class and the SQ agnostic learnability of that class, and used this
equivalence to obtain the first super-polynomial SQ lower bounds for
agnostically learning the important concept class of monotone juntas under the
uniform distribution. To establish SQ lower bounds for agnostic learning under
Gaussian marginals, Diakonikolas et al. (2021b) extended the approach of
Dachman-Soled et al. (2014) using new duality arguments and embedding
techniques. In doing so, they obtained lower bounds for agnostically learning
a number of Boolean concept classes (as well as some real-valued concept
classes). For intersections of $k$ halfspaces, their agnostic SQ lower bound
is $n^{\tilde{\Omega}(\sqrt{\log k})}$, which should be contrasted with the
$n^{O(\log k)}$ upper bound of Klivans et al. (2008). In fact, they
conjectured that it may be the upper bound that is loose.

Our results prove that the algorithmic results of Klivans et al. (2008) are
indeed nearly optimal. Specifically, we show that any SQ algorithm that
agnostically learns intersections of $k\leq\exp(O(n^{0.245}))$ halfspaces to
any constant excess error must have complexity at least
$n^{\tilde{\Omega}(\log k)}$. The notion of complexity is made more precise in
the informal theorem statement below.

######  Theorem 1 (Informal version of Theorem 18).

Any SQ algorithm that agnostically learns intersections of $k$ halfspaces to
excess error $\epsilon$ under Gaussian marginals requires either
$2^{n^{\Omega(1)}}$ queries or at least one query of tolerance
$n^{-\tilde{\Omega}(\log k+1/\epsilon^{2})}$.

This result is nearly optimal for any constant $\epsilon$, up to a $\log\log
k$ factor in the exponent, because the $n^{O(\log k)}$ time and sample
complexity upper bounds from Klivans et al. (2008) can be achieved by an SQ
algorithm. We note that by the AM-GM inequality the exponent
$\tilde{\Omega}(\log k+1/\epsilon^{2})$ in our lower bound is always at least
$\tilde{\Omega}(\sqrt{\log k}/\epsilon)$, which is the exponent from the SQ
lower bound of Diakonikolas et al. (2021b), but can also be significantly
stronger.

In fact, when $k$ is small ($k=O(n^{0.49})$) we show that the hardness of
learning intersections of $2k$ halfspaces is already present in the easier
problem of learning a simple subset of the class: the family of
$k$-dimensional cubes. This result, given in Theorem 7, relies on new
technical facts about the $L^{1}$-error approximation degree of cube functions
under Gaussian marginals. Our bounds additionally imply new hardness results
on learning functions with bounded Gaussian surface area and convex subspace
juntas (see Theorems 20 and 21 respectively).

###  1.1 Techniques

Our proofs follow the blueprints of Dachman-Soled et al. (2014) and
Diakonikolas et al. (2021b) and build upon them by using weak learning lower
bounds from De and Servedio (2021) and new technical innovations for proving
resilience with respect to continuous measures. Put roughly, Dachman-Soled et
al. (2014):

  1. (a)

introduced a notion of _approximate resilience_ on the Boolean cube and
established an equivalence to $L^{1}$ approximate degree using linear
programming duality;

  2. (b)

used a combinatorial argument to show that if a $k$-dimensional function $f$
is approximately resilient, then there exists a family of $k$-juntas
($n$-dimensional embeddings of $f$ for $n\gg k$) that is hard to agnostically
learn in the SQ model;

  3. (c)

used Boolean Fourier analysis to prove approximate resilience for the
$\mathsf{Tribes}$ function (a monotone read-once DNF); and

  4. (d)

proved a tighter approximate resilience bound for other monotone Boolean
functions by combining a hardness result on weak learning of Blum et al.
(1998a) with an agnostic learning algorithm based on $L^{1}$ polynomial
approximation by Kalai et al. (2008).

To transfer this methodology to the Gaussian measure on $\mathbb{R}^{n}$,
Diakonikolas et al. (2021b):

  1. (a′)

extended the equivalence of approximate resilience and $L^{1}$ approximate
degree to Gaussian marginals with a more technical argument involving an
infinite linear program and the Hahn-Banach Theorem;

  2. (b′)

showed that $L^{1}$ polynomial inapproximability of a $k$-dimensional function
implies the hardness of SQ-learning a family of $n$-dimensional embeddings of
$f$ applied to $k$-dimensional subspaces111The underlying hard problem is
distinguishing a standard (multivariate) Gaussian from a distribution that
differs from the standard Gaussian only in the high-order moments of a
$k$-dimensional projection (Diakonikolas et al., 2017).; and

  3. (c′)

lower-bounded the $L^{1}$ approximate degree of an intersection of $k$
halfspaces using a new connection with Gaussian noise sensitivity.

Our results are obtained using a hybrid of the Dachman-Soled et al. (2014) and
Diakonikolas et al. (2021b) approaches. More precisely, we rely on (a′) and
(b′) to establish agnostic SQ lower bounds over Gaussian marginals for
approximately resilient functions, but we draw inspiration from (c) instead of
(c′) to bound the approximate resilience of the $\mathsf{Cube}_{k}$ function
by directly analyzing its Hermite representation. We also draw inspiration
from (d) when we lower-bound the approximate resilience of other intersections
of halfspaces by using a recent hardness result from De and Servedio (2021)
for weak learning those functions.

In more detail, Theorem 7 proves the hardness of learning the restricted class
of $k$-dimensional cubes for $k=O(n^{0.49})$ in $n$-dimensional space by
directly bounding the approximate resilience of a single cube function,
$\mathsf{Cube}_{k}:\mathbb{R}^{k}\to\mathbb{R}$. That is, we show that
$\mathsf{Cube}_{k}$ is close in $L^{1}$-distance to a bounded function that is
orthogonal to all polynomials of degree $d=\tilde{\Omega}(\log k)$. To
construct this bounded function, we develop a new argument which is inspired
by (c) but is significantly more technically involved. Due to the
unboundedness and continuity of our $\mathcal{N}(0,I_{n})$ setting, our
argument requires a careful iterative construction, which involves defining a
thresholding transform that reduces the low-degree Hermite coefficients of its
input while maintaining its boundedness and taking the limit of applying the
transform an infinite number of times. The key properties of
$\mathsf{Cube}_{k}$ for this argument are the boundedness of its outputs and
its small low-degree Hermite weight. The approximate resilience of
$\mathsf{Cube}_{k}$ provides an almost-tight bound on the $L^{1}$ approximate
degree of the function, and the main result follows by direct application of
(a′) and (b′).

Theorem 14, which shows the hardness of learning to constant accuracy the
broader classes of all intersections of $k$ halfspaces for any
$k=\exp(O(n^{0.245}))$, instead relies on the combination of recent lower
bounds on the number of queries needed to weakly learn intersections of $k$
halfspaces from De and Servedio (2021) and well-known algorithmic results of
Kalai et al. (2008) for agnostically learning functions with bounded $L^{1}$
approximate degree. This approach draws inspiration from (d). We show that the
$L^{1}$ approximate degree of a random intersection of $k$ halfspaces must be
at least $\tilde{\Omega}(\log k)$ with high probability, since otherwise there
would be a contradiction between the aforementioned works: Kalai et al. (2008)
would provide an algorithm to weakly learn intersections of halfspaces using
fewer queries than the lower bound established by De and Servedio (2021). As
before, these bounds on polynomial inapproximability translate to SQ learning
lower bounds via the machinery of Diakonikolas et al. (2021b).

All of the above arguments are for constant excess error (constant
$\epsilon$). We introduce the dependence on $\frac{1}{\epsilon}$ in Theorem 18
by augmenting the previously-considered intersections of $k$ halfspaces with a
single halfspace (in an additional dimension) that passes through the origin.
Ganzburg (2002) showed that a single halfspace has $L^{1}$
$\epsilon$-approximate degree $\Omega(\frac{1}{\epsilon^{2}})$, and we use
this to show that our new intersection of halfspaces has approximate degree
$\tilde{\Omega}(\log k+\frac{1}{\epsilon^{2}})$.

###  1.2 Related work

Efficient algorithms are known for PAC learning intersections of halfspaces
under certain marginal distributions. Baum (1990) gave an algorithm for
learning two homogeneous halfspaces under origin-symmetric distributions, and
the same algorithm is now known to also succeed under mean-zero log-concave
distributions (Klivans et al., 2009). For PAC learning intersections (and
other functions) of $k$ general halfspaces, algorithms are known for the
uniform distribution on the unit ball (Blum and Kannan, 1997), the uniform
distribution on the Boolean cube (Klivans et al., 2004, Kalai et al., 2008,
Kane, 2014), Gaussian distributions (Klivans et al., 2008, Vempala, 2010a),
and general log-concave distributions (Vempala, 1997, 2010b). In most of these
cases, the dependence on $k$ in the running time is $n^{\Omega(k)}$ or worse
(the exceptions are the algorithms for Gaussian or uniform on
$\smash{\\{-1,1\\}^{n}}$ marginals). In fact, only the $L^{1}$ polynomial
regression algorithm is known to succeed in the agnostic setting, and only
under Gaussian or uniform on $\\{-1,1\\}^{n}$ marginals (Klivans et al., 2008,
Kane, 2014). Finally, efficient algorithms are also known for PAC learning
intersections of any constant number of halfspaces under marginals satisfying
a geometric margin condition (Arriaga and Vempala, 2006, Klivans and Servedio,
2008), and also for learning intersections (and other functions) of halfspaces
using membership queries (Kwek and Pitt, 1998, Gopalan et al., 2012).

Our work focuses on hardness of learning intersections of halfspaces. Besides
the SQ lower bounds of Diakonikolas et al. (2021b) for (agnostic) learning
under Gaussian marginals (which built on the closely related work of Dachman-
Soled et al. (2014)), there is other evidence for the difficulty of this
learning problem. First, distribution-free PAC learning—both proper learning
and improper learning with certain hypothesis classes—is known to be NP-hard
(Blum and Rivest, 1992, Megiddo, 1988), and lower bounds on the threshold
degree of intersections of two halfspaces due to Sherstov (2013) rule out
efficient algorithms that use polynomial threshold functions as hypotheses.
Cryptographic lower bounds (Klivans and Sherstov, 2006) give further evidence
that distribution-free PAC learning is hard even if the learner is permitted
to output any polynomial-time computable hypothesis. (The distribution-free
correlational SQ lower bounds of Gollakota et al. (2020) give similar evidence
for restricted types of learners.) These lower bounds leave open the
possibility that fixed-distribution PAC learning is tractable, but again there
is evidence against this, at least for certain classes of learning algorithms.
Klivans and Sherstov (2007) showed that there is a (non-uniform) marginal
distribution on the Boolean cube under which the SQ dimension of intersections
of $\sqrt{n}$ halfspaces is at least $\smash{2^{\Omega(\sqrt{n})}}$; this
implies lower bounds for (weak) SQ learning under that distribution. Finally,
Klivans et al. (2008) gave membership query lower bounds for learning certain
convex bodies under Gaussian marginals. These lower bounds are exhibited by
intersections of $k$ halfspaces for sufficiently large $k$, but they do not
rule out $\operatorname*{poly}(n)$ query algorithms unless $k$ is at least
polynomially large in $n$. Moreover, these lower bounds are insensitive to the
error parameter $\epsilon$ sought by the learner, and in particular do not
become higher for subconstant $\epsilon$.

###  1.3 Organization

In Section 3 we prove Theorem 7, which gives an $\smash{n^{\tilde{\Omega}(\log
k)}}$ SQ lower bound for agnostically learning intersections of $k$ halfspaces
(in fact, $k$-dimensional cubes) to constant excess error when
$\smash{k=O(n^{0.49}).}$ Section 4 gives a similar SQ lower bound for larger
values of $k$ (using different arguments and less structured intersections of
halfspaces which are not cubes). Section 5 improves the quantitative results
of both these sections by allowing for subconstant excess error, thereby
establishing Theorem 1 (see Theorem 18 in Section 5 for a detailed theorem
statement). Appendix A extends our results to the concept class of functions
with bounded Gaussian surface area and convex subspace juntas, and gives some
observations on lower bounds for $L^{1}$ polynomial approximation.

##  2 Preliminaries

###  2.1 Functions in Gaussian space

For any $k\in\mathbb{N}$, the standard Gaussian distribution on
$\mathbb{R}^{k}$ is denoted by $\mathcal{N}(0,I_{k})$. For $q\geq 1$, let
$\smash{\|f\|_{q}=\smash{\mathbb{E}_{{\mathbf{x}}\sim\mathcal{N}(0,I_{k})}[|f({\mathbf{x}})|^{q}]^{1/q}}}$
denote the $L^{q}$-norm of $f\in L^{q}(\mathcal{N}(0,I_{k}))$, and let
$\left\langle
f,g\right\rangle=\mathbb{E}_{{\mathbf{x}}\sim\mathcal{N}(0,I_{n})}[f({\mathbf{x}})g({\mathbf{x}})]$
denote the inner product between $f,g\in L^{2}(\mathcal{N}(0,I_{k}))$. For a
multi-index $\smash{J\in\mathbb{N}^{k}}$, let $\\#J$ denote the number of
nonzero elements of $J$, and let $\smash{|J|=J_{1}+\cdots+J_{k}}$. Let
$\mathcal{P}_{k,d}$ denote the family of all polynomials
$p:\mathbb{R}^{k}\to\mathbb{R}$ of degree at most $d$.

In Appendix B, we recall basic facts about the _Hermite polynomials_
$\\{H_{J}\\}_{J\in\mathbb{N}^{k}}$, which form an orthogonal basis for
$L^{2}(\mathcal{N}(0,I_{k}))$, as well as some tools based on Gaussian
hypercontractivity.

###  2.2 Agnostic learning under Gaussian marginals and Statistical Query
learning

We recall the framework of agnostic learning under Gaussian marginals. Given a
concept class ${\cal C}$ of functions from $\mathbb{R}^{n}$ to $\\{-1,1\\}$,
an agnostic learning algorithm is given access to i.i.d. labeled examples
$({\mathbf{x}},{\mathbf{y}})$ drawn from a distribution ${\cal D}$ over
$\mathbb{R}^{n}\times\\{-1,1\\}$, where the marginal of ${\cal D}$ over the
first $n$ coordinates is $\mathcal{N}(0,I_{n})$. Intuitively, a successful
agnostic learning algorithm for ${\cal C}$ is one which can find a hypothesis
that correctly predicts the label ${\mathbf{y}}$ almost as well as the best
predictor in ${\cal C}$. More precisely, an _agnostic learning algorithm for
${\cal C}$ under Gaussian marginals with excess error $\epsilon$_ is an
algorithm which, with high probability, outputs a hypothesis function
$h:\mathbb{R}^{n}\to\\{-1,1\\}$ such that
$\Pr_{({\mathbf{x}},{\mathbf{y}})\in{\cal
D}}[h({\mathbf{x}})\neq{\mathbf{y}}]\leq\mathrm{OPT}+\epsilon$, where
$\mathrm{OPT}=\inf_{f\in{\cal C}}\Pr_{({\mathbf{x}},{\mathbf{y}})\in{\cal
D}}[f({\mathbf{x}})\neq{\mathbf{y}}].$ The special case of $\mathrm{OPT}=0$
corresponds to (realizable) PAC learning under the Gaussian distribution.

The above definition is for a learning scenario in which the learner has
access to individual random examples. In the well-known Statistical Query (SQ)
learning model, the learning algorithm cannot access individual examples from
${\cal D}$ but instead has access to a “STAT oracle.”

######  Definition 2.

A learning algorithm $\mathcal{A}$ has access to a _STAT oracle_ if
$\mathcal{A}$ makes queries with a function
$g:\mathbb{R}^{n}\times\\{-1,1\\}\to[-1,1]$ and a tolerance parameter $\tau>0$
and recieves an estimate of the expectation
$\mathbb{E}_{({\mathbf{x}},{\mathbf{y}})\sim\mathcal{D}}[g({\mathbf{x}},{\mathbf{y}})]$
that is accurate up to additive error $\pm\tau$. An algorithm $\mathcal{A}$
with access to a STAT oracle is an _SQ agnostic learning algorithm_ for
concept class $\mathcal{C}$ if it returns with high probability a hypothesis
$h:\mathbb{R}^{n}\to\\{-1,1\\}$ such that
$\Pr_{({\mathbf{x}},{\mathbf{y}})\in{\cal
D}}[h({\mathbf{x}})\neq{\mathbf{y}}]\leq\mathrm{OPT}+\epsilon$.

###  2.3 Resilience and $L^{1}$ polynomial approximation

Dachman-Soled et al. (2014) established a useful connection between lower
bounds for SQ agnostic learning under the uniform distribution on
$\\{-1,1\\}^{n}$ and the notion of _resilience_ for bounded functions. This
connection was extended to the Gaussian setting by Diakonikolas et al.
(2021b), and it also plays an essential role in our results.

Intuitively, a function is “resilient” if it has zero correlation with all
low-degree basis functions. More formally, we have the following:

######  Definition 3.

A function $g:\mathbb{R}^{n}\to[-1,1]$ is _$d$ -resilient_ if $\left\langle
g,p\right\rangle=0$ for every $p\in\mathcal{P}_{n,d}$ (equivalently,
$\left\langle g,H_{J}\right\rangle=0$ for every $|J|\leq d$). For
$0\leq\alpha<1$, a function $f:\mathbb{R}^{n}\to[-1,1]$ is said to be
_$\alpha$ -approximately $d$-resilient_ if there exists a $d$-resilient
_witness_ $g:\mathbb{R}^{n}\to[-1,1]$ such that
$\left\|f-g\right\|_{1}\leq\alpha$.

Next we define the notion of $L^{1}$ polynomial approximation:

######  Definition 4.

Given $0\leq\epsilon<1$ and $f:\mathbb{R}^{n}\to[-1,1]$, we say that the
_$L^{1}$ $\epsilon$-approximate degree of $f$_ is the smallest value $d\geq 0$
such that there exists a polynomial $p\in\mathcal{P}_{n,d}$ satisfying
$\left\|f-p\right\|_{1}\leq\epsilon.$

Definition 4 is of course equivalent to $d$ being the largest value such that
every polynomial $p$ of degree at most $d-1$ has $\|f-p\|_{1}>\epsilon.$

Using linear programming duality, for the setting of functions
$f:\\{-1,1\\}^{n}\to[-1,1]$ and the uniform distribution over
$\\{-1,1\\}^{n}$, Dachman-Soled et al. (2014) established an _equivalence_
between the $L^{1}$-distance to the closest $d$-resilient bounded function
(cf. Definition 3) and the best possible accuracy of $L^{1}$ polynomial
approximation by degree-$d$ polynomials (cf. Definition 4). They did this by
showing (see their Theorem 1.2) that for $f:\\{-1,1\\}^{n}\to[-1,1]$, if the
former quantity is $\alpha$ then the latter quantity is $1-\alpha$.

This equivalence was extended to the setting of Gaussian space (our domain of
interest in the current work) by Diakonikolas et al. (2021b); a more involved
argument is required for this setting, essentially because now the linear
programming duality involves an infinitely large linear program, but the
result still goes through. The proof of their Proposition 2.1 establishes the
following:222The statement of Proposition 2.1 of Diakonikolas et al. (2021b)
only goes in one direction (that $L^{1}$ polynomial approximate degree implies
approximate resilience), but the proof establishes both directions.

######  Lemma 5 (Equivalence of approximate resilience and $L^{1}$ approximate
degree).

A function $f:\mathbb{R}^{n}\to[-1,1]$ is $\alpha$-approximately $d$-resilient
if and only if its $L^{1}$ $(1-\alpha)$-approximate degree is $d$.

In the Boolean hypercube setting, Dachman-Soled et al. (2014) combined their
$L^{1}$ polynomial approximation characterization of resilience with standard
SQ lower bounds and standard results on the existence of combinatorial designs
to show the following: if $f:\\{-1,1\\}^{k}\to\\{-1,1\\}$ is an
$\alpha$-approximately $d$-resilient function, then (roughly speaking; see
their Lemma 2.1 for a precise statement) any concept class of functions from
$\\{-1,1\\}^{n}$ to $\\{-1,1\\}$ containing all “embeddings” of $f$ (according
to the combinatorial design) admits a Statistical Query lower bound.

Diakonikolas et al. (2021b) carried out a similar-in-spirit argument in the
setting of Gaussian space. We note that their result is significantly
technically more challenging than the analogous argument of Dachman-Soled et
al. (2014); it builds on recent SQ lower bounds for distinguishing
distributions due to Diakonikolas et al. (2017), and uses embeddings of low-
dimensional functions in hidden low-dimensional subspaces rather than
combinatorial designs. We record their key result below, which will be
crucially used for all of our agnostic SQ lower bounds:

######  Lemma 6 (Diakonikolas et al., 2021b, Theorem 1.4).

Let $n,m\in\mathbb{N}$ with $\smash{m\leq n^{a}}$ for any $0<a<1/2$, and let
$\smash{\epsilon\geq n^{-c}}$ for a suitably small absolute constant $c>0$.
Given any function $f:\mathbb{R}^{m}\to\\{-1,1\\}$, let $d$ be the $L^{1}$
$(2\epsilon)$-approximate degree of $f$.333By 5, this condition is equivalent
to $f$ being $(1-2\epsilon)$-approximately $d$-resilient. Let ${\cal C}$ be a
class of $\\{-1,1\\}$-valued functions on $\mathbb{R}^{n}$ which includes all
functions of the form $F(x)=f(Px)$ for all $P\in\mathbb{R}^{m\times n}$ such
that $PP^{\mathsf{T}}=I_{m}$. Any SQ algorithm that agnostically learns ${\cal
C}$ under $\mathcal{N}(0,I_{n})$ to error $\mathrm{OPT}+\epsilon$ either
requires queries with tolerance at most $n^{-\Omega(d)}$ or makes at least
$2^{n^{\Omega(1)}}$ queries.

##  3 Hardness of SQ learning to constant excess error via approximate
resilience

The main result of this section is Theorem 7, which, roughly speaking, shows
that any SQ algorithm that makes a sub-exponential number of statistical
queries and agnostically learns the concept class of “embedded $k$-dimensional
cubes” (for $k=O(n^{0.49})$) to any constant excess error that is bounded
below $\frac{1}{2}$ must make queries of tolerance
$\smash{n^{-\Omega(\log(k)/\log\log k)}}$. (Note that this gives a special
case of Theorem 1 in which the excess error $\epsilon$ is constant and
$k=O(n^{0.49}).$) This is done by establishing that the $k$-dimensional cube
function is approximately resilient; recall that by Definition 3, this means
that it is close in $L^{1}$ distance to a bounded function that is orthogonal
to all low-degree polynomials.

We define the function $\mathsf{Cube}_{k}:\mathbb{R}^{k}\to\\{-1,1\\}$ as
$\mathsf{Cube}_{k}(y):=\textrm{sign}(\theta_{k}-\left\|y\right\|_{\infty})$.
(Note that this is equivalent to
$\smash{\mathsf{Cube}_{k}(y)=2\prod_{i=1}^{k}\mathbbm{1}\left\\{\left|y_{i}\right|\leq\theta_{k}\right\\}-1}$.)
In words, $\mathsf{Cube}_{k}^{-1}(1)$ is the axis-aligned origin-centered
solid cube with side length $2\theta_{k}$, where $\theta_{k}\geq 0$ is chosen
to ensure that
$\mathbb{E}_{{\mathbf{y}}\sim\mathcal{N}(0,I_{k})}[\mathsf{Cube}_{k}({\mathbf{y}})]=0$.
Note that $\mathsf{Cube}_{k}$ is an intersection of $2k$ halfspaces.

######  Theorem 7.

For sufficiently large $n$ and $k$, with $k=O(n^{0.49})$, define the concept
class $\mathcal{C}=\\{x\mapsto\mathsf{Cube}_{k}(Px):P\in\mathbb{R}^{k\times
n},PP^{\mathsf{T}}=I_{k}\\}$. Any SQ algorithm that agnostically learns
$\mathcal{C}$ to excess error $\frac{1}{2}\left(1-\frac{1}{k^{0.49}}\right)$
requires $2^{n^{\Omega(1)}}$ queries or at least one query of tolerance
$n^{-\Omega(\log(k)/\log\log k)}$.

This strengthens the bounds of Diakonikolas et al. (2021b) for the regime of
$k=O(n^{0.49})$ and constant excess error, improving the
$\smash{n^{-\tilde{\Omega}(\sqrt{\log k})}}$ tolerance requirement to
$\smash{n^{-\tilde{\Omega}(\log k)}}$. Theorem 7 follows directly from 5 and 6
and the following lemma:

######  Lemma 8.

For sufficiently large $k$, the function $\mathsf{Cube}_{k}$ is
$\alpha$-approximately $d$-resilient for $\alpha={k^{-0.49}}$ and
$d=\Omega(\log(k)/\log\log k)$.

The proof of 8 has two main ingredients: a bound on the Hermite weight of
$\mathsf{Cube}_{k}$ that is contained in its low-degree coefficients (9), and
an approximate resilience guarantee for functions with bounded low-degree
Hermite weight (10). We prove 8 in Section 3.2 by applying those two lemmas
and choosing an appropriate setting for $d$ in terms of $k$.

######  Lemma 9.

For any sufficiently large $k$, and any $d\geq 0$,444See Appendix B for
notation for Hermite coefficients.

$\sum_{\left|J\right|\leq
d}\widetilde{\mathsf{Cube}_{k}}(J)^{2}\leq\frac{20d(3\ln k)^{d}}{k}.$

We prove this lemma in Section C.1 by exactly computing the Hermite
coefficients of one-dimensional centered interval functions (27) and using
those values to carefully bound the $\mathsf{Cube}_{k}$ Hermite coefficients.
At a high level, our bounds on the low-degree Hermite coefficients of
$\mathsf{Cube}_{k}$ are similar in flavor to the bounds of Mansour (1992) on
the low-degree Fourier coefficients of the read-once “tribes” CNF over the
Boolean hypercube.

######  Lemma 10.

For sufficiently large $k$, $d\geq 2$, and $f:\mathbb{R}^{k}\to\\{-1,1\\}$,
let $\gamma:=\smash{\sum_{|J|\leq d}\widetilde{f}(J)^{2}}$. Then $f$ is
$\alpha$-approximately $d$-resilient for $\alpha=\smash{\gamma^{0.498}(72\ln
k)^{d/2}}.$

The proof of 10 is given in Section 3.1 and is somewhat technically involved.
Our argument modifies and extends a proof idea from Dachman-Soled et al.
(2014), which they use to show that the function
$\mathsf{Tribes}:\\{-1,1\\}^{k}\to\\{-1,1\\}$ is approximately resilient.
Starting with the $\mathsf{Tribes}$ function, their approach is essentially to
(i) discard its low-degree Fourier component; (ii) truncate the resulting
function so it does not take very large values; (iii) again discard the low-
degree Fourier component of (ii) (since the truncation could have reintroduced
some low-degree Fourier component); and (iv) normalize the result of (iii) to
give an $L^{\infty}$ norm of at most 1. They show that this yields a new
function that (1) has zero low-degree Fourier weight, (2) takes output values
that are bounded in $[-1,1]$, and (3) is close to the original
$\mathsf{Tribes}$ function in $L^{1}$ distance.

In our setting we have the same high level goals of achieving (1-3), but
achieving boundedness is significantly more difficult on the unbounded domain
$\mathbb{R}^{k}$ than on the finite hypercube $\\{-1,1\\}^{k}$. Our witness to
the approximate resilience of $\mathsf{Cube}_{k}$ is not constructed in a
single shot (in contrast to Dachman-Soled et al.), but rather is constructed
gradually through an iterative process.

###  3.1 Approximate resilience of functions with small low-degree weight
(Proof of 10)

In this section, we prove 10. Our key tool is the
$\mathrm{TruncHigh}_{d,\tau}$ transformation, defined below, and a careful
iterative application of $\mathrm{TruncHigh}_{d,\tau}$ to produce a witness to
the approximate resilience of a given Boolean function $f$ with small low-
degree Hermite weight.

######  Definition 11.

For any $f\in L^{2}(\mathcal{N}(0,I_{k}))$ and $d\in\mathbb{N}$, let
$\mathrm{Low}_{d}$ and $\mathrm{High}_{d}$ be $L^{2}(\mathcal{N}(0,I_{k}))\to
L^{2}(\mathcal{N}(0,I_{k}))$ transformations that reduce a function to its
low-degree and high-degree Hermite components respectively, i.e.

$\displaystyle\mathrm{Low}_{d}[f]:=\sum_{\left|J\right|\leq
d}\tilde{f}(J)H_{J},\quad\text{and}\quad\mathrm{High}_{d}[f]:=\sum_{\left|J\right|>d}\tilde{f}(J)H_{J}=f-\mathrm{Low}_{d}[f].$

For any $\tau>0$, the truncation transformation
$\mathrm{TruncHigh}_{d,\tau}:L^{2}(\mathcal{N}(0,I_{k}))\to
L^{2}(\mathcal{N}(0,I_{k}))$ is

$\displaystyle\mathrm{TruncHigh}_{d,\tau}[f](x)$
$\displaystyle:=\mathrm{High}_{d}[f](x)-\mathrm{High}_{d}[f](x)\mathbbm{1}\left\\{\left|\mathrm{Low}_{d}[f](x)\right|>\tau\right\\}$
$\displaystyle\hphantom{:}=\begin{cases}\mathrm{High}_{d}[f](x)&\text{if
$\left|\mathrm{Low}_{d}[f](x)\right|\leq\tau$},\\\
0&\text{otherwise.}\end{cases}$

The purpose of $\mathrm{TruncHigh}_{d,\tau}[f]$ is to shrink the low-degree
weight of $f$ while staying bounded in $L^{\infty}$ and close to $f$ in
$L^{1}$. These properties are given in the following propositions.

######  Proposition 12.

If $\left\|f\right\|_{\infty}<\infty$, then
$\|\mathrm{TruncHigh}_{d,\tau}[f]\|_{\infty}\leq\left\|f\right\|_{\infty}+\tau.$

###### Proof.

$\mathrm{TruncHigh}_{d,\tau}[f](x)$ is non-zero only if
$\left|\mathrm{Low}_{d}[f](x)\right|\leq\tau$. In that case, it is clear that
$\left|\mathrm{TruncHigh}_{d,\tau}[f](x)\right|=\left|\mathrm{High}_{d}[f](x)\right|=\left|f(x)-\mathrm{Low}_{d}[f](x)\right|\leq\left|f(x)\right|+\tau$.∎

######  Proposition 13.

For any $k\geq 1$ and $d\geq 2$, fix some $a>1$ and
$\rho\geq\left\|\mathrm{Low}_{d}[f]\right\|_{2}$ and let

$\tau:=\rho\left(4e\ln(3k)+\frac{8e}{d}\ln\left(\frac{a\left\|f\right\|_{2}}{\rho}\right)\right)^{d/2}.$
(1)

Then, (i)
$\|\mathrm{Low}_{d}[\mathrm{TruncHigh}_{d,\tau}[f]]\|_{2}\leq\frac{\rho}{a}$,
and (ii) $\|\mathrm{TruncHigh}_{d,\tau}[f]-f\|_{1}\leq 2\rho$.

We prove 13 in Section C.2.

Note that there is a tension in the choice of the truncation parameter $\tau$.
If $\tau$ is too large, then $\mathrm{TruncHigh}_{d,\tau}[f]$ might still take
large values. But if $\tau$ is too small, then the low-degree weight of
$\mathrm{TruncHigh}_{d,\tau}[f]$ might not become much smaller compared to
that of $f$. The proof of 10 works by applying $\mathrm{TruncHigh}_{d,\tau}$
iteratively with a carefully chosen decreasing schedule of $\tau$-values. This
process converges to a function that is bounded, has zero low-degree weight,
and is sufficiently close to $f$, and this function certifies the
$\alpha$-approximate $d$-resilience of $f$.

###### Proof of 10.

Since any $f$ with $\left\|f\right\|_{\infty}\leq 1$ is trivially
1-approximately $d$-resilient for all $d\geq 0$, we may assume that
$\alpha<1$. We define a sequence of functions $(f_{i})_{i\in\mathbb{N}}$ by
$f_{0}:=f$ and $f_{i}:=\mathrm{TruncHigh}_{d,\tau_{i}}[f_{i-1}]$ for $i\geq
1$, where

$\tau_{i}:=\frac{\left\|\mathrm{Low}_{d}[f_{0}]\right\|_{2}}{4^{(i-1)d}}\left(4e\ln(3k)+\frac{8e}{d}\ln\left(\frac{4^{id}\left\|f_{i-1}\right\|_{2}}{\left\|\mathrm{Low}_{d}[f_{0}]\right\|_{2}}\right)\right)^{d/2}.$
(2)

We’ll show that the sequence $(f_{i})_{i\in\mathbb{N}}$ has a limit in
$L^{2}(\mathcal{N}(0,I_{k}))$ that yields a witness to the
$\alpha$-approximate $d$-resiliance of $f$. To do this, it will suffice to
show the following claims for all $i\geq 1$:

Claim 1.

$\tau_{i}\leq\frac{\alpha}{3\cdot 2^{i}}$.

Claim 2.

$\left\|f_{i}\right\|_{\infty}\leq
1+\frac{\alpha}{3}\sum_{\iota=1}^{i}\frac{1}{2^{\iota}}\leq
1+\frac{\alpha}{3}$.

Claim 3.

$\left\|\mathrm{Low}_{d}[f_{i}]\right\|_{2}\leq\frac{1}{4^{id}}\left\|\mathrm{Low}_{d}[f_{0}]\right\|_{2}\leq\frac{\alpha}{6\cdot
4^{id}}$ and $\left\|f_{i}-f_{i-1}\right\|_{1}\leq\frac{\alpha}{3\cdot
4^{(i-1)d}}$.

We now explain why this is enough to prove the lemma. Claim 2. ensures that
$\|f_{i}\|_{\infty}\leq 1+\alpha/3$, while Claim 3. (for all $i$) ensures that
$\|f_{i}-f_{0}\|_{1}\leq\sum_{\iota=1}^{i}\|f_{\iota}-f_{\iota-1}\|_{1}\leq
2\alpha/3$ (by the triangle inequality), and also
$\lim_{i\to\infty}\|\mathrm{Low}_{d}[f_{i}]\|_{2}=0$. By a limit argument
(31), the sequence $(f_{i})_{i\in\mathbb{N}}$ converges in
$L^{2}(\mathcal{N}(0,I_{k}))$ to some $f^{*}\in L^{2}(\mathcal{N}(0,I_{k}))$
with $\|f^{*}\|_{\infty}\leq 1+\alpha/3$, $\mathrm{Low}_{d}[f^{*}]=0$, and
$\|f^{*}-f\|_{1}\leq 2\alpha/3$. This proves the lemma because one of $f^{*}$
and $f^{**}:=f^{*}/\|f^{*}\|_{\infty}$ witnesses that $f$ is
$\alpha$-approximately $d$-resilient. Indeed, if $\|f^{*}\|_{\infty}>1$, then
$\|f^{**}\|_{\infty}=1$, $\mathrm{Low}_{d}[f^{**}]=0$, and

$\left\|f-f^{**}\right\|_{1}\leq\left\|f-f^{*}\right\|_{1}+\left\|f^{*}-f^{**}\right\|_{\infty}\leq\frac{2\alpha}{3}+\left(1-\frac{1}{\left\|f^{*}\right\|_{\infty}}\right)\left\|f^{*}\right\|_{\infty}\leq\alpha,$

where the first inequality uses the triangle inequality and comparison of
$\|\cdot\|_{1}$ and $\|\cdot\|_{\infty}$.

It remains to prove Claim 1., Claim 2., and Claim 3. for all $i\geq 1$ by
induction on $i$.

For the base case $i=1$, $\tau_{1}\leq\frac{\alpha}{6}$ (Claim 1.) is an
immediate consequence of the upper bound on $\tau_{1}$ from Fact 30 in Section
C.3, which relies on having $\|f_{0}\|_{\infty}=1<\frac{4}{3}$. 12 and the
bound on $\tau_{1}$ imply $\left\|f_{1}\right\|_{\infty}\leq
1+\frac{\alpha}{6}$ (Claim 2.). By taking $a=4^{d}$ and
$\rho=\left\|\mathrm{Low}_{d}[f_{0}]\right\|_{2}$, 13 implies that
$\|\mathrm{Low}_{d}[f_{1}]\|_{2}\leq\smash{\frac{1}{4^{d}}}\left\|\mathrm{Low}_{d}[f_{0}]\right\|_{2}$
and $\|f_{1}-f_{0}\|_{1}\leq 2\left\|\mathrm{Low}_{d}[f_{0}]\right\|_{2}$. We
conclude the base case of Claim 3. by observing that
$\left\|\mathrm{Low}_{d}[f_{0}]\right\|_{2}\leq\tau_{1}\leq\frac{\alpha}{6}$
by Fact 30.

We prove the inductive step by assuming that the three claims all hold for
some fixed $i\geq 1$ and showing that they also hold for $i+1$. By applying
Fact 30 with $\left\|f_{i}\right\|_{\infty}\leq
1+\frac{\alpha}{3}\leq\frac{4}{3}$ from step $i$ of Claim 2., we have
$\tau_{i+1}\leq\frac{\alpha}{3\cdot 2^{i+1}}$ (step $i+1$ of Claim 1.). Step
$i+1$ of Claim 2. is immediate from 12, the bound on $\tau_{i+1}$, and a
geometric sum:

$\|f_{i+1}\|_{\infty}\leq\|f_{i}\|_{\infty}+\tau_{i+1}\leq
1+\frac{\alpha}{3}\sum_{\iota=1}^{i+1}\frac{1}{2^{\iota}}\leq
1+\frac{\alpha}{3}.$

We apply 13 with $a=4^{d}$ and
$\rho=\smash{\frac{1}{4^{id}}}\left\|\mathrm{Low}_{d}[f_{0}]\right\|_{2}$555Note
that $\rho\geq\left\|\mathrm{Low}_{d}[f_{i}]\right\|_{2}$ by step $i$ of Claim
3., which is necessary for 13. to obtain

$\|\mathrm{Low}_{d}[f_{i+1}]\|_{2}\leq\smash{\frac{1}{4^{(i+1)d}}}\left\|\mathrm{Low}_{d}[f_{0}]\right\|_{2}\quad\text{and}\quad\left\|f_{i+1}-f_{i}\right\|_{1}\leq\smash{\frac{2}{4^{id}}}\left\|\mathrm{Low}_{d}[f_{0}]\right\|_{2}.$

Combining this with the bound
$\left\|\mathrm{Low}_{d}[f_{0}]\right\|_{2}\leq\frac{\alpha}{6}$ completes
step $i+1$ of Claim 3..

Hence, the three claims hold for all $i\geq 1$ by induction, which concludes
the proof. ∎

###  3.2 Approximate resilience of $\mathsf{Cube}_{k}$ (Proof of 8)

Let $d=\frac{\ln k}{125\ln\ln k}$. By 9, for sufficiently large $k$ we have

$\displaystyle\gamma:=\sum_{\left|J\right|\leq
d}\widetilde{\mathsf{Cube}_{k}}(J)^{2}$ $\displaystyle\leq\frac{20d(3\ln
k)^{d}}{k}.$

10 guarantees that $\mathsf{Cube}_{k}$ is $\alpha$-approximately $d$-resilient
for

$\displaystyle\alpha$ $\displaystyle=\gamma^{0.498}(72\ln
k)^{d/2}\leq\exp\left(-0.498\ln k+0.00799\ln k+o(\ln k)\right)\leq k^{-0.49}.$

This completes the proof of 8. ∎

##  4 Hardness of SQ learning to constant excess error via weak learning lower
bounds

In this section we give a different proof of our main agnostic SQ hardness
result for learning intersections of $k$ halfspaces to constant excess error.
While Theorem 7 established hardness for a highly structured subclass of this
concept class (consisting of suitable embeddings of the $\mathsf{Cube}_{k}$
function), the current argument only applies to the broader class of all
intersections of $k$ halfspaces. However, an advantage of the current argument
is that it holds for a wider range of values of $k$ (up to
$2^{O(n^{0.245})}$). In more detail, in this section we prove the following:

######  Theorem 14.

For sufficiently large $n$ and any $k=2^{O(n^{0.245})}$, any SQ algorithm that
agnostically learns the class of intersections of $k$ halfspaces over
$\mathbb{R}^{n}$ to excess error $c$ requires either $2^{n^{\Omega(1)}}$
queries or at least one query of tolerance $n^{-\Omega(\log(k)/\log\log k)}$.
(Here $c>0$ is an absolute constant independent of all other parameters.)

As discussed in Section 1.1, the proof of Theorem 14 follows the high-level
approach of Theorem 1.4 of Dachman-Soled et al. (2014). Rather than analyzing
the Hermite spectrum of the hard-to-learn functions (as was done in Section
3), the argument combines the agnostic learning algorithm of Kalai et al.
(2008) with a (slight extension of a) recently-established lower bound on the
ability of membership query (MQ) algorithms to weakly learn intersections of
halfspaces.

We first recall the following lower bound from De and Servedio (2021):

######  Lemma 15 (De and Servedio, 2021, Theorem 2).

For sufficiently large $m$, for any $q\geq m$, there is a distribution
$\mathcal{D}_{\mathrm{actual}}$ over centrally symmetric convex sets of
$\mathbb{R}^{m}$ with the following property: for a target convex set
$\bm{f}\sim\mathcal{D}_{\mathrm{actual}}$ for any MQ algorithm $A$ making at
most $q$ many queries to $\bm{f}$, the expected error of $A$ (the probability
over $\bm{f}\sim\mathcal{D}_{\mathrm{actual}}$, any internal randomness of
$A$, and a Gaussian ${\mathbf{x}}\sim\mathcal{N}(0,I_{n})$, that the output
hypothesis $h$ of $A$ is wrong on ${\mathbf{x}}$) is at least
$\smash{\frac{1}{2}-{\frac{O(\log q)}{\sqrt{m}}}}$.

We require the following corollary of 15, which we prove in Section D.1.

######  Corollary 16.

For sufficiently large $n$, for all $q\geq m$, there is a distribution
$\mathcal{D}$ over intersections of $q^{101}$ halfspaces such that for a
target function $\bm{f}\sim{\cal D}$, any MQ algorithm $\mathcal{A}$ making at
most $q$ queries to $\bm{f}$ has expected error at least
$\frac{1}{2}-\frac{O(\log q)}{\sqrt{m}}$ (where the expectation is over
$\bm{f}\sim\mathcal{D}$ and any internal randomness of $\mathcal{A}$, and the
the accuracy is with respect to $\mathcal{N}(0,I_{n})$).

Theorem 14 follows immediately from 6 and the following lemma.

######  Lemma 17.

For any $k=2^{O(n^{0.245})}$, there exists an intersection of $k$ halfspaces
$f:\mathbb{R}^{m}\to\\{-1,1\\}$ that has $L^{1}$ $\frac{1}{2}$-approximate
degree $d=\Omega(\log(k)/\log\log k)$, where $m=O(n^{0.49}).$

###### Proof.

First we note that we may assume $k$ is at least some sufficiently large
absolute constant as specified below through the choice of $q$ (since
otherwise, because of the $\Omega(\cdot)$ in the specification of $d$, there
is nothing to prove). Suppose that every intersection of $k$ halfspaces $f$
over $\mathbb{R}^{m}$ has $L^{1}$ $\frac{1}{2}$-approximate degree at most
$d-1$; we will prove the lemma by showing that $d$ must be
$\Omega(\log(k)/\log\log k).$

Let $q=k^{1/101}$ and let $\mathcal{S}\subseteq\mathbb{R}^{n}$ be the subspace
of $\mathbb{R}^{n}$ spanned by the first $m=c_{1}\ln^{2}q$ coordinates, where
$c_{1}$ is a sufficiently large universal constant specified below and $q$ is
chosen sufficiently large (relative to $c_{1}$) so that $q\geq m$ and $m$
satisfies the “sufficiently large” requirement of 16. By 16, there is a
distribution $\mathcal{D}$ over intersections of at most $k=q^{101}$
halfspaces over $\mathcal{S}$ such that any membership query algorithm making
at most $q$ queries to an unknown $\bm{f}\sim{\cal D}$ outputs a hypothesis
with expected error at least $\smash{\frac{1}{2}-\frac{O(\log q)}{\sqrt{m}}}$.
For a sufficiently large setting of $c_{1}$, this expected error is at least
$\smash{\frac{1}{2}-\frac{O(\log q)}{\sqrt{c_{1}}\ln q}}\geq 0.49.$

By the assumption that every intersection of $k$ halfspaces has $L^{1}$
$\frac{1}{2}$-approximate degree at most $d-1$, if the agnostic learner of
Theorem 5 of Kalai et al. (2008) is run on any intersection of $k$ halfspaces
over the first $m$ coordinates, then it uses
$s:=\operatorname*{poly}(m^{d}/\epsilon)$ labeled examples from
$\mathcal{N}(0,I_{n})$, runs in $\operatorname*{poly}(s)$ time, and with
probability at least (say) $0.9$ outputs a hypothesis $h$ with error at most

$\epsilon+\frac{1}{2}\min_{p\in\mathcal{P}_{n,d}}\left\|f-p\right\|_{1}\leq\epsilon+\frac{1}{4}$

(see Theorem 1.3 of Dachman-Soled et al. (2014)). Taking $\epsilon=0.15$ and
observing that a labeled example from $\mathcal{N}(0,I_{n})$ can be simulated
using a single membership query, we see that for the concept class of
intersections of $k$ halfspaces over the first $m$ coordinates, there is a
membership query algorithm ${\cal A}$ that makes at most $m^{c_{2}d}$ many
membership queries and with probability at least $0.9$ achieves error at most
$0.4$; hence the expected error of this MQ algorithm is at most $0.9\cdot
0.4+0.1\cdot 1=0.46$.

Comparing the conclusions of the previous two paragraphs, we see that
$m^{c_{2}d}\geq q,$ and hence (recalling that $m=c_{1}\ln^{2}q$ and
$q=k^{1/101}$), we get that

$d\geq{\frac{\ln q}{c_{2}\ln m}}=\Omega(\log(k)/\log\log k),$

which proves the lemma. ∎

##  5 Hardness of SQ learning to arbitrary excess error

In this section, we strengthen both of the SQ lower bounds from Sections 3 and
4 by combining them with lower bounds on the $L^{1}$ $\epsilon$-approximate
degree of halfspaces due to Ganzburg (2002). By doing so, we improve the lower
bounds to $n^{\Omega(\log(k)/\log\log(k)+1/\epsilon^{2})}$ for agnostically
learning intersections of $k$ halfspaces to excess error $\epsilon$ for any
$\smash{\epsilon\geq n^{-c}}$ (cf. 6). By the arithmetic-geometric mean
inequality, this lower bound is always at least as strong as the
$n^{\smash{-\tilde{\Omega}(\log^{1/2}(k)/\epsilon)}}$ lower bound of
Diakonikolas et al. (2021b).

Let $k,m$ be as described in 17. We construct an intersection of $k+1$
halfspaces over $\mathbb{R}^{m+1}$ by taking the intersection of

  * •

the $k$ halfspaces identified in 17 over $\mathbb{R}^{m}$; and

  * •

an origin-centered halfspace orthogonal to the $(m+1)$-st coordinate basis
vector.

Appendix E formally bounds the $L^{1}$ approximate degree of intersections of
this construction of half spaces and proves a strengthening of Theorem 14,
which is our main agnostic SQ lower bound:

######  Theorem 18 (Formal version of Theorem 1).

For any $k=2^{O(n^{0.245})}$ and any $\epsilon\geq n^{-c}$ for a suitably
small absolute constant $c>0$, any SQ algorithm that agnostically learns
intersections of $k$ halfspaces to excess error $\epsilon$ under Gaussian
marginals requires either $2^{n^{\Omega(1)}}$ queries or at least one query of
tolerance $n^{-\Omega(\log(k)/\log\log k+1/\epsilon^{2})}$.

## References

  * Abramowitz and Stegun (1972) M. Abramowitz and I. A. Stegun.  _Handbook of Mathematical Functions_.  Dover, 1972.
  * Arriaga and Vempala (2006) R. I. Arriaga and S. S. Vempala.  An algorithmic theory of learning: Robust concepts and random projection.  _Machine Learning_ , 63(2):161–182, 2006.
  * Awasthi et al. (2017) P. Awasthi, M. F. Balcan, and P. M. Long.  The power of localization for efficiently learning linear separators with noise.  _Journal of the ACM_ , 63(6):1–27, 2017.
  * Ball (1993) K. Ball.  The Reverse Isoperimetric Problem for Gaussian Measure.  _Discrete and Computational Geometry_ , 10:411–420, 1993\.
  * Baum (1990) E. B. Baum.  A polynomial time algorithm that learns two hidden unit nets.  _Neural Computation_ , 2(4):510–522, 1990.
  * Blum and Kannan (1997) A. L. Blum and R. Kannan.  Learning an intersection of a constant number of halfspaces over a uniform distribution.  _Journal of Computer and System Sciences_ , 54(2):371–380, 1997.
  * Blum and Rivest (1992) A. L. Blum and R. L. Rivest.  Training a 3-node neural network is NP-complete.  _Neural Networks_ , 5(1):117–127, 1992.
  * Blum et al. (1998a) A. L. Blum, C. Burch, and J. Langford.  On learning monotone Boolean functions.  In _Thirty-Ninth Annual Symposium on Foundations of Computer Science_ , 1998a.
  * Blum et al. (1998b) A. L. Blum, A. Frieze, R. Kannan, and S. Vempala.  A polynomial-time algorithm for learning noisy linear threshold functions.  _Algorithmica_ , 22(1):35–52, 1998b.
  * Blumer et al. (1989) A. Blumer, A. Ehrenfeucht, D. Haussler, and M. K. Warmuth.  Learnability and the Vapnik-Chervonenkis dimension.  _Journal of the ACM_ , 36(4):929–965, 1989.
  * Bonami (1970) A. Bonami.  Étude des coefficients de Fourier des fonctions de $L^{p}(G)$.  _Annales de l’institut Fourier_ , 20(2):335–402, 1970.
  * Dachman-Soled et al. (2014) D. Dachman-Soled, V. Feldman, L.-Y. Tan, A. Wan, and K. Wimmer.  Approximate resilience, monotonicity, and the complexity of agnostic learning.  In _Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms_ , 2014.
  * De and Servedio (2021) A. De and R. A. Servedio.  Weak learning convex sets under normal distributions.  In _Thirty-Fourth Annual Conference on Learning Theory_ , 2021.
  * De et al. (2021) A. De, S. Nadimpalli, and R. A. Servedio.  Convex influences.  _arXiv preprint arXiv:2109.03107_ , 2021.
  * Diakonikolas et al. (2017) I. Diakonikolas, D. M. Kane, and A. Stewart.  Statistical query lower bounds for robust estimation of high-dimensional Gaussians and Gaussian mixtures.  _Fifty-Eighth Annual Symposium on Foundations of Computer Science_ , 2017.
  * Diakonikolas et al. (2021a) I. Diakonikolas, D. M. Kane, V. Kontonis, C. Tzamos, and N. Zarifis.  Efficiently learning halfspaces with Tsybakov noise.  In _Fifty-Third Annual ACM Symposium on Theory of Computing_ , 2021a.
  * Diakonikolas et al. (2021b) 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 _Thirty-Fourth Annual Conference on Learning Theory_ , 2021b.
  * Duda et al. (1973) R. O. Duda, P. E. Hart, and D. G. Stork.  _Pattern Classification and Scene Analysis_.  Wiley New York, 1973.
  * Feller (1968) W. Feller.  _An Introduction to Probability Theory and Its Applications_.  John Wiley & Sons, Inc., 3rd edition, 1968.
  * Freund and Schapire (1997) Y. Freund and R. E. Schapire.  A decision-theoretic generalization of on-line learning and an application to boosting.  _Journal of Computer and System Sciences_ , 55(1):119–139, 1997.
  * Ganzburg (2002) M. I. Ganzburg.  Limit theorems for polynomial approximations with Hermite and Freud weights.  In _Approximation Theory X: Wavelets, Splines, and Applications_ , Innovations in Applied Mathematics, pages 211–221. Vanderbilt University Press, 2002.
  * Gollakota et al. (2020) A. Gollakota, S. Karmalkar, and A. R. Klivans.  The polynomial method is universal for distribution-free correlational SQ learning.  _arXiv preprint arXiv:2010.11925_ , 2020.
  * Gopalan et al. (2012) P. Gopalan, A. R. Klivans, and R. Meka.  Learning functions of halfspaces using prefix covers.  In _Twenty-Fifth Annual Conference on Learning Theory_ , 2012.
  * Gross (1975) L. Gross.  Logarithmic Sobolev inequalities.  _American Journal of Mathematics_ , 97(4):1061–1083, 1975.
  * Kalai et al. (2008) A. T. Kalai, A. R. Klivans, Y. Mansour, and R. A. Servedio.  Agnostically learning halfspaces.  _SIAM Journal on Computing_ , 37(6):1777–1805, 2008.
  * Kane (2014) D. M. Kane.  The average sensitivity of an intersection of half spaces.  In _Forty-Sixth Annual ACM Symposium on Theory of Computing_ , 2014\.
  * Kearns (1998) M. Kearns.  Efficient noise-tolerant learning from statistical queries.  _Journal of the ACM_ , 45(6):983–1006, 1998\.
  * Klivans and Servedio (2008) A. R. Klivans and R. A. Servedio.  Learning intersections of halfspaces with a margin.  _Journal of Computer and System Sciences_ , 74(1):35–48, 2008.
  * Klivans and Sherstov (2006) A. R. Klivans and A. A. Sherstov.  Cryptographic hardness for learning intersections of halfspaces.  In _Forty-Seventh Annual IEEE Symposium on Foundations of Computer Science_ , 2006.
  * Klivans and Sherstov (2007) A. R. Klivans and A. A. Sherstov.  Unconditional lower bounds for learning intersections of halfspaces.  _Machine Learning_ , 69(2):97–114, 2007.
  * Klivans et al. (2004) A. R. Klivans, R. O’Donnell, and R. A. Servedio.  Learning intersections and thresholds of halfspaces.  _Journal of Computer and System Sciences_ , 68(4):808–840, 2004.
  * Klivans et al. (2008) A. R. Klivans, R. O’Donnell, and R. A. Servedio.  Learning geometric concepts via Gaussian surface area.  In _Forty-Ninth Annual IEEE Symposium on Foundations of Computer Science_ , 2008.
  * Klivans et al. (2009) A. R. Klivans, P. M. Long, and A. K. Tang.  Baum’s algorithm learns intersections of halfspaces with respect to log-concave distributions.  In _Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques_. 2009.
  * Kwek and Pitt (1998) S. Kwek and L. Pitt.  PAC learning intersections of halfspaces with membership queries.  _Algorithmica_ , 22(1):53–75, 1998.
  * Mansour (1992) Y. Mansour.  An $O(n^{\log\log n})$ Learning Algorithm for DNF under the Uniform Distribution.  In _Fifth Annual Workshop on Computational Learning Theory_ , 1992\.
  * Megiddo (1988) N. Megiddo.  On the complexity of polyhedral separability.  _Discrete & Computational Geometry_, 3(4):325–337, 1988.
  * Nazarov (2003) F. Nazarov.  _On the Maximal Perimeter of a Convex Set in $\mathbb{R}^{n}$ with Respect to a Gaussian Measure_, pages 169–187.  Springer Berlin Heidelberg, 2003.
  * Nelson (1973) E. Nelson.  Construction of quantum fields from Markoff fields.  _Journal of Functional Analysis_ , 12(1):97–112, 1973.
  * O’Donnell (2014) R. O’Donnell.  _Analysis of Boolean functions_.  Cambridge University Press, 2014.
  * Rosenblatt (1962) F. Rosenblatt.  _Principles of Neurodynamics_.  Spartan Books, 1962.
  * Sherstov (2013) A. A. Sherstov.  Optimal bounds for sign-representing the intersection of two halfspaces by polynomials.  _Combinatorica_ , 33(1):73–96, 2013.
  * Vaaler (1985) J. D. Vaaler.  Some extremal functions in Fourier analysis.  _Bulletin of the American Mathematical Society_ , 12(2):183–216, 1985.
  * Vapnik (1982) V. N. Vapnik.  _Estimation of Dependences Based on Empirical Data_.  Springer-Verlag, 1982.
  * Vempala (1997) S. S. Vempala.  A random sampling based algorithm for learning the intersection of half-spaces.  In _Thirty-Eighth Annual Symposium on Foundations of Computer Science_ , 1997.
  * Vempala (2010a) S. S. Vempala.  Learning convex concepts from Gaussian distributions with PCA.  In _Fifty-First Annual Symposium on Foundations of Computer Science_ , 2010a.
  * Vempala (2010b) S. S. Vempala.  A random-sampling-based algorithm for learning intersections of halfspaces.  _Journal of the ACM_ , 57(6):1–14, 2010b.

##  Appendix A Discussion

###  A.1 Agnostic SQ lower bounds for learning functions of bounded Gaussian
surface area and convex $m$-subspace juntas

In this appendix, we note that our arguments imply agnostic SQ lower bounds
for several classes of $\\{-1,1\\}$-valued functions over $\mathbb{R}^{n}$
that were studied by Vempala (2010a) and Klivans et al. (2008). Our lower
bounds essentially match the upper bounds for those classes by Klivans et al.
(2008).

Functions with bounded Gaussian Surface Area. Recall the definition of
Gaussian Surface Area:

######  Definition 19.

Let $f:\mathbb{R}^{n}\to\\{-1,1\\}$ be such that
$\\{x\in\mathbb{R}^{n}:f(x)=1\\}$ is a Borel set. The _Gaussian surface area_
of $f$ is defined to be

$\Gamma(f):=\liminf_{\delta\to
0}\frac{\mathop{\mathrm{Pr}}\displaylimits_{{\mathbf{x}}\sim\mathcal{N}(0,I_{n})}\left[f({\mathbf{x}})=-1\
\text{and}\ \exists y\in f^{-1}(1)\ \text{s.t.}\
\left\|{\mathbf{x}}-y\right\|_{2}\leq\delta\right]}{\delta}.$

Let ${\cal C}_{s}$ denote the class of all Borel sets in $\mathbb{R}^{n}$ with
Gaussian surface area at most $s$. The main result of Klivans et al. (2008,
Theorem 25) is that ${\cal C}_{s}$ is agnostically learnable to accuracy
$\mathrm{OPT}+\epsilon$ by an SQ algorithm that makes
$n^{O(s^{2}/\epsilon^{4})}$ queries, each of tolerance
$n^{-O(s^{2}/\epsilon^{4})}$. Their agnostic learning algorithm for
intersections of $k$ halfspaces, mentioned earlier, is obtained from this
result by combining it with the fact, due to Nazarov (2003), that any
intersection of $k$ halfspaces has Gaussian surface area at most $O(\sqrt{\log
k}).$

Let $s=O(n^{0.1225})$, let $m=n^{0.49}$ and let
$k=\smash{2^{s^{2}}=2^{O(\sqrt{m})}}$. By 17 there is an intersection of $k$
halfspaces over $\mathbb{R}^{m}$ that has $L^{1}$ $\frac{1}{2}$-approximate
degree $\Omega(s^{2}/\log s)$, and by Nazarov’s upper bound on Gaussian
surface area, this function has Gaussian surface area at most $O(s)$.
Combining this with 6, we immediately obtain that for any $s\leq
O(n^{0.1225})$, any SQ agnostic learning algorithm that achieves constant
excess error under Gaussian marginals for the class ${\cal C}_{s}$ either
requires queries with tolerance at most $n^{-\Omega(s^{2}/\log(s))}$ or makes
at least $2^{n^{\Omega(1)}}$ queries. Combining this with the arguments of
Section 5, we get the following result for ${\cal C}_{s}$:

######  Theorem 20.

For sufficiently large $n$, any $s=O(n^{0.1225})$, and any $\epsilon\geq
n^{-c}$ for a suitably small absolute constant $c>0$, any SQ algorithm that
agnostically learns the class ${\cal C}_{s}$ to excess error $\epsilon$
requires either $2^{n^{\Omega(1)}}$ queries or at least one query of tolerance
$n^{-\Omega(s^{2}/\log(s)+1/\epsilon^{2})}$.

Convex subspace juntas. Vempala (2010a) gave a learning algorithm (in the
realizable, i.e., non-agnostic, setting) for a class of functions that we
refer to as _convex $m$-subspace juntas_. A function
$f:\mathbb{R}^{n}\to\\{-1,1\\}$ is a convex $m$-subspace junta if $f$ is the
indicator function of a convex set $K$ with a normal subspace of dimension
$m$; equivalently, $f$ is an intersection of halfspaces all of whose normal
vectors lie in some subspace of $\mathbb{R}^{n}$ of dimension at most $m$
(note that the number of halfspaces in such an intersection may be arbitrarily
large or even infinite).

Vempala’s algorithm learns to accuracy $\epsilon$ and runs in time
$\operatorname*{poly}(n,2^{m}/\epsilon,m^{\tilde{O}(\sqrt{m}/\epsilon^{4})})$
in the realizable ($\mathrm{OPT}=0$) setting of learning under Gaussian
marginals. As alluded to in Section 1, this algorithm uses principal component
analysis to do a preprocessing step and then runs the algorithm of Klivans et
al. (2008). The analysis crucially relies on a Brascamp-Lieb type inequality
(Lemma 4.7 of Vempala, 2010a) which, roughly speaking, makes it possible to
identify the “relevant directions”); however, this breaks down in the non-
realizable (agnostic) setting. The best known agnostic learning result for the
class of convex $m$-subspace juntas under Gaussian marginals is the SQ
algorithm of Klivans et al. (2008), which makes $n^{O(\sqrt{m}/\epsilon^{4})}$
statistical queries, each of tolerance at least
$n^{-O(\sqrt{m}/\epsilon^{4})}$. This performance bound for the algorithm
follows immediately from Theorem 25 of Klivans et al. (2008) and the upper
bound, due to Ball (1993), that any convex set in $\mathbb{R}^{m}$ has
Gaussian surface area at most $O(m^{1/4}).$

Let $m\leq n^{0.49}.$ By 17 there is a convex $m$-subspace junta (an
intersection of $2^{O(\sqrt{m})}$ many halfspaces, all of whose normal vectors
lie in an $m$-dimensional subspace of $\mathbb{R}^{n}$) that has $L^{1}$
$\frac{1}{2}$-approximate degree $\Omega(\sqrt{m}/\log m).$ Combining this
with 6 and the arguments of Section 5, we obtain the following lower bound:

######  Theorem 21.

For sufficiently large $n$, any $m\leq n^{0.49}$, and $\epsilon\geq n^{-c}$
for a suitably small absolute constant $c>0$, any SQ algorithm that
agnostically learns the class of convex $m$-subspace juntas to excess error
$\epsilon$ requires either $2^{n^{\Omega(1)}}$ queries or at least one query
of tolerance $n^{-\Omega(\sqrt{m}/\log m+1/\epsilon^{2})}$.

###  A.2 On lower bounds for $L^{1}$ polynomial approximation

One of the contributions of Diakonikolas et al. (2021b) is that it introduced
new analytic techniques for obtaining lower bounds on the $L^{1}$ approximate
degree of functions $f:\mathbb{R}^{n}\to\\{-1,1\\}$. In particular,
Diakonikolas et al. (2021b) established a new structural result that
translates a lower bound on the Gaussian Noise Sensitivity of any function
$f:\mathbb{R}^{n}\to\\{-1,1\\}$ to a lower bound on the $L^{1}$ approximate
degree of $f$.

######  Definition 22 (O’Donnell, 2014, Definition 11.9).

Given $0\leq\rho\leq 1$ and $f:\mathbb{R}^{n}\to\\{-1,1\\}$, the _Gaussian
Noise Sensitivity of $f$ at correlation $1-\rho$_, written
$\mathrm{GNS}_{\rho}(f)$, is

$\mathrm{GNS}_{\rho}(f):=\Pr_{({\mathbf{x}},{\mathbf{g}})\sim{\cal
N}(0,I_{n})^{\otimes 2}}\Bigl{[}f({\mathbf{x}})\neq
f((1-\rho){\mathbf{x}}+\sqrt{2\rho-\rho^{2}}{\mathbf{g}})\Bigr{]}.$

Equivalently, $\mathrm{GNS}_{\rho}(f)$ is the probability that
$f({\mathbf{x}})\neq f({\mathbf{y}})$ where ${\mathbf{x}},{\mathbf{y}}$ are
standard $n$-dimensional Gaussians with correlation $1-\rho$.

######  Theorem 23 (Diakonikolas et al., 2021b, Theorem 1.5).

Let $f:\mathbb{R}^{n}\to\\{-1,1\\}$ and let $p:\mathbb{R}^{n}\to\mathbb{R}$ be
any polynomial of degree at most $d$. Then

  1. 1.

$\left\|f-p\right\|_{1}\geq\Omega(1/\log
d)\cdot\mathrm{GNS}_{(\ln(d)/d)^{2}}(f).$

  2. 2.

For any $\epsilon>0$, we have
$\left\|f-p\right\|_{1}\geq\mathrm{GNS}_{\epsilon}(f)/4-O(d\sqrt{\epsilon}).$

In contrast with $L^{2}$ polynomial approximation (for which the degree
required for $\epsilon$-approximation can be “read off” of the Hermite
expansion), polynomial approximation in $L^{1}$ is much less well understood.
Thus it is interesting and useful to have general tools for $L^{1}$
approximate degree bounds such as Theorem 23, and conversely, it is of
interest to understand the limitations of such tools.

Diakonikolas et al. (2021b) use Theorem 23 to prove an $L^{1}$ approximate
degree lower bound for intersections of $k$ halfspaces. They first show that
for a particular666This function $f^{\prime}$ is very similar to the
$\mathsf{Cube}_{k}$ function; instead of upper and lower bounding each of the
$k$ coordinates $x_{1},\dots,x_{k}$, it only upper bounds each coordinate.
intersection of $k$ halfspaces $f^{\prime}$ over $\mathbb{R}^{k}$, for each
$\tau<\Theta(1/\log k)$ it holds that
$\mathrm{GNS}_{\tau}(f^{\prime})=\Theta(\sqrt{\tau\log k})$. Combining this
with item (1) of Theorem 23 gives that any polynomial $p$ for which
$\|f-p\|_{1}\leq\epsilon$ must have
$d\geq\Omega(\smash{\frac{\log^{1/2}k}{\epsilon}}).$ Our resilience results
for the $\mathsf{Cube}_{k}$ function give a stronger $L^{1}$ approximate
degree lower bound, and combining this with the $\mathrm{GNS}$ bound from
Diakonikolas et al. (2021b) gives an example of a function for which the bound
of part (1) of Theorem 23 is not tight.

In more detail, recall that our 8 states that the $\mathsf{Cube}_{k}$ function
is $k^{-0.49}$-approximately $\Theta(\log(k)/\log\log k)$-resilient. An
entirely similar analysis to the proof of 8 shows that the function
$f^{\prime}$ of Diakonikolas et al. (2021b) is also $k^{-0.49}$-approximately
$d:=\Theta(\log(k)/\log\log k)$-resilient, i.e., there is a function
$g:\mathbb{R}^{k}\to[-1,1]$ which has zero correlation with every polynomial
of degree at most $d-1$ and which has $\|f^{\prime}-g\|_{1}\leq k^{-0.49}.$ By
5, the existence of this resilient $g$ implies that every polynomial $p$ of
degree at most $d-1$ must have

$\|f^{\prime}-p\|_{1}\geq 1-\frac{2}{k^{0.49}},$

which is close to one for large $k$.

Now consider what can be obtained from the $\mathrm{GNS}$ bound of
Diakonikolas et al. (2021b). Since

$\mathrm{GNS}_{((\ln(d-1))/(d-1))^{2}}(f^{\prime})=\sqrt{{\frac{\Theta((\log\log
k)^{4})}{(\ln k)^{2}}}\cdot\ln k}={\frac{\Theta((\log\log k)^{2})}{\sqrt{\ln
k}}},$

part (1) of Theorem 23 only gives that every polynomial $p$ of degree at most
$d-1$ has

$\|f^{\prime}-p\|_{1}\geq\Omega\left(\frac{\log\log(k)}{\sqrt{\log
k}}\right).$

This bound is close to zero for large $k$.

##  Appendix B Hermite polynomials and Gaussian hypercontractivity

Let $\\{h_{j}\\}_{j=0}^{\infty}$ be the (unnormalized) probabilists’ Hermite
polynomials

$h_{j}(x):=(-1)^{j}e^{x^{2}/2}\frac{\operatorname{d\\!}{{}^{j}}}{\operatorname{d\\!}x^{j}}e^{-x^{2}/2},\quad
j=0,1,2,\dotsc.$ (3)

These polynomials form an orthogonal basis for the Hilbert space
$L^{2}(\mathcal{N}(0,1))$; more precisely, we have $\langle
h_{j},h_{j^{\prime}}\rangle=j!\cdot\delta_{j,j^{\prime}}$. For any $f\in
L^{2}(\mathcal{N}(0,1))$, the Hermite coefficients $\widetilde{f}(j)$ of $f$
are given by

$\widetilde{f}(j):=\frac{1}{\sqrt{j!}}\left\langle f,h_{j}\right\rangle.$

Let $\\{H_{J}\\}_{J\in\mathbb{N}^{k}}$ be the multivariate Hermite
polynomials, which correspond to a tensor product of the univariate Hermite
polynomials above. That is,

$H_{J}(x):=\prod_{i=1}^{k}h_{J_{i}}(x_{i}).$

These polynomials form an orthogonal basis for $L^{2}(\mathcal{N}(0,I_{k}))$,
and we have that $\left\langle
H_{J},H_{J^{\prime}}\right\rangle=J!\delta_{J,J^{\prime}}$, where
$J!=J_{1}!\cdots J_{k}!$. For any $F\in L^{2}(\mathcal{N}(0,I_{k}))$, the
Hermite coefficients $\widetilde{F}(J)$ of $F$ are given by

$\widetilde{F}(J):=\frac{1}{\sqrt{J!}}\left\langle F,H_{J}\right\rangle.$

Additional properties of the Hermite polynomials can be found in Chapter 22 of
Abramowitz and Stegun (1972) and Section 11.2 of O’Donnell (2014).

Our results—particularly those in Section 3.1—rely on bounds powered by
Gaussian hypercontractivity. We recall the basic Gaussian hypercontractive
inequality for low-degree polynomials (Bonami, 1970, Nelson, 1973, Gross,
1975):

######  Fact 24.

For a polynomial $p\in\mathcal{P}_{d}$ and any $q\geq 2$,
$\left\|p\right\|_{q}\leq(q-1)^{d/2}\left\|p\right\|_{2}$.

In particular, we will use the following bound on the fourth moment of Hermite
polynomials, which follows immediately from Fact 24 and standard bounds on the
norm of Hermite polynomials:

######  Fact 25.

$\left\|H_{J}\right\|_{4}\leq 3^{d/2}\left\|H_{J}\right\|_{2}\leq
3^{d/2}\sqrt{J!}$.

We will also use the following concentration bound, which follows from
Gaussian hypercontractivity using Markov’s inequality:

######  Fact 26 (O’Donnell, 2014, Theorem 9.23).

For any polynomial $p:\mathbb{R}^{k}\to\mathbb{R}$ of degree $d$ and any
$t\geq e^{d}$,

$\Pr_{{\mathbf{x}}\sim\mathcal{N}(0,I_{n})}{[\left|p({\mathbf{x}})\right|\geq
t\left\|p\right\|_{2}]}\leq\exp\left(-\frac{d}{2e}t^{2/d}\right).$

###### Proof.

Consider any $q\geq 2$.

$\displaystyle\mathop{\mathrm{Pr}}\displaylimits\left[\left|p({\mathbf{x}})\right|\geq
t\left\|p\right\|_{2}\right]$
$\displaystyle=\mathop{\mathrm{Pr}}\displaylimits\left[\left|p({\mathbf{x}})\right|^{q}\geq
t^{q}\left\|p\right\|_{2}^{q}\right]\leq\frac{\left\|p\right\|_{q}^{q}}{t^{q}\left\|p\right\|_{2}^{q}}\leq\left(\frac{(q-1)^{d/2}}{t}\right)^{q}\leq\left(\frac{q^{d/2}}{t}\right)^{q}.$

Let $q=\frac{t^{2/d}}{e}$, which has $q\geq 2$ because $t\geq e^{d}$. Then,

$\displaystyle\mathop{\mathrm{Pr}}\displaylimits\left[\left|p({\mathbf{x}})\right|\geq
t\left\|p\right\|_{2}\right]$
$\displaystyle\leq\left(\frac{1}{e^{d/2}}\right)^{t^{2/d}/e}=\exp\left(-\frac{d}{2e}t^{2/d}\right).\qed$

##  Appendix C Supporting lemmas and proofs for Section 3

###  C.1 Small low-degree Hermite weight of $\mathsf{Cube}_{k}$ (Proof of 9)

We recall 9.

See 9

We note that by the analysis of $\mathsf{Cube}_{k}$ by De et al. (2021,
Example 14), the upper bound of 9 in the case $d=2$ is tight up to constant
factors.

Our proof of 9 uses the product structure of $\mathcal{N}(0,I_{k})$ and the
fact that $\mathsf{Cube}_{k}$ is essentially a product of univariate interval
functions over disjoint variables. Thanks to these properties, it suffices to
analyze the Hermite coefficients of interval functions of the right width.

For any $\theta\geq 0$, let $f_{\theta}:\mathbb{R}\to\\{0,1\\}$ be the
indicator function for the interval $[-\theta,\theta]$, i.e.,

$f_{\theta}(x):=\mathbbm{1}\left\\{\left|x\right|\leq\theta\right\\}.$

Then, $\mathsf{Cube}_{k}$ can be written as

$\mathsf{Cube}_{k}(x)=2\prod_{i=1}^{k}f_{\theta_{k}}(x_{i})-1.$

Since $\theta_{k}$ is chosen to ensure that
$\mathop{\mathbb{E}}\displaylimits_{{\mathbf{x}}\sim\mathcal{N}(0,I_{k})}\left[\mathsf{Cube}_{k}({\mathbf{x}})\right]=0$,
the Hermite coefficients of $\mathsf{Cube}_{k}$ are given by

$\widetilde{\mathsf{Cube}_{k}}(J)=\begin{cases}0&\text{if $J=0$},\\\
2\prod_{i=1}^{k}\widetilde{f_{\theta_{k}}}(J_{i})&\text{otherwise}.\end{cases}$

###### Proof of 9.

We may assume that $d\leq k/(2e^{2}\ln k)$, since otherwise the claimed bound
on $\sum_{|J|\leq d}\widetilde{\mathsf{Cube}_{k}(J)}^{2}$ is more than one.

By 27 (stated and proved below), $\widetilde{f_{\theta_{k}}}(J_{i})=0$ for any
odd $J_{i}$. Hence, the only Hermite coefficients that may be non-zero are
those corresponding to multi-indices $J\in\mathbb{N}^{k}$ with (i) only even
components, and (ii) $1\leq|J|\leq d$. Let $\mathcal{J}$ denote this set of
multi-indices. For any such $J\in\mathcal{J}$,

$\displaystyle\widetilde{\mathsf{Cube}_{k}}(J)^{2}=4\prod_{i=1}^{k}\widetilde{f_{\theta_{k}}}(J_{i})^{2}$
$\displaystyle=4\prod_{i:J_{i}=0}\widetilde{f_{\theta_{k}}}(J_{i})^{2}\prod_{i:J_{i}\geq
2}\widetilde{f_{\theta_{k}}}(J_{i})^{2}$ $\displaystyle\leq
4\prod_{i:J_{i}\geq
2}\left[\left(1+\sqrt{\frac{e}{J_{i}}}\theta_{k}\right)^{2(J_{i}-1)}e^{-\theta_{k}^{2}}\right]$
$\displaystyle\leq
4\left(1+\sqrt{\frac{e}{2}}\theta_{k}\right)^{2(|J|-\\#J)}e^{-\theta_{k}^{2}\\#J},$

where the first inequality uses the fact that
$|\widetilde{f_{\theta_{k}}}(0)|\leq 1$ (27) and the bound from 28 (stated and
proved below). To bound the sum $\sum_{|J|\leq
d}\widetilde{\mathsf{Cube}_{k}}(J)^{2}=\sum_{J\in\mathcal{J}}\widetilde{\mathsf{Cube}_{k}}(J)^{2}$,
we partition the terms by the value of $\\#J$. Note that $\\#J$ must satisfy
$1\leq\\#J\leq\left\lfloor d/2\right\rfloor$, since $J$ is not all zeros, and
every non-zero component of $J$ is at least two. Therefore,

$\displaystyle\sum_{|J|\leq d}\widetilde{\mathsf{Cube}_{k}}(J)^{2}$
$\displaystyle=\sum_{t=1}^{\left\lfloor
d/2\right\rfloor}\sum_{J\in\mathcal{J}:\\#J=t}\widetilde{\mathsf{Cube}_{k}}(J)^{2}$
$\displaystyle\leq
4\left(1+\sqrt{\frac{e}{2}}\theta_{k}\right)^{2(d-1)}\sum_{t=1}^{\left\lfloor
d/2\right\rfloor}|\\{J\in\mathcal{J}:\\#J=t\\}|\cdot e^{-\theta_{k}^{2}t}.$
(4)

The definition of $\mathcal{J}$ and standard binomial coefficient inequalities
provide a bound on the number of $J\in\mathcal{J}$ with $\\#J=t$ for $t\geq
1$:

$\displaystyle\left|\\{J\in\mathcal{J}:\\#J=t\\}\right|$
$\displaystyle={k\choose
t}\left|\\{S\in\mathbb{N}^{t}:\left|S\right|\leq\left\lfloor
d/2\right\rfloor,S_{i}>0\text{~{}for all $i\in[t]$}\\}\right|$
$\displaystyle={k\choose
t}\left|\\{S\in\mathbb{N}^{t}:\left|S\right|\leq\left\lfloor
d/2\right\rfloor-t\\}\right|$ $\displaystyle={k\choose t}{\left\lfloor
d/2\right\rfloor\choose t}\leq\left(\frac{e^{2}kd}{2t^{2}}\right)^{t}.$

Therefore, we can bound the final expression from (4) by

$\displaystyle
4\left(1+\sqrt{\frac{e}{2}}\theta_{k}\right)^{2(d-1)}\sum_{t=1}^{\left\lfloor
d/2\right\rfloor}\left(\frac{e^{2}kd}{2t^{2}}e^{-\theta_{k}^{2}}\right)^{t}$
$\displaystyle\leq 4\left(1+\sqrt{e\ln
k}\right)^{2(d-1)}\sum_{t=1}^{\left\lfloor
d/2\right\rfloor}\left(\frac{e^{2}d\ln k}{t^{2}k}\right)^{t}$
$\displaystyle\leq 8\left(1+\sqrt{e\ln k}\right)^{2(d-1)}\cdot\frac{e^{2}d\ln
k}{k}\leq\frac{20d(3\ln k)^{d}}{k},$

where the first inequality uses the bounds on $\theta_{k}$ from Lemma 29, and
the second inequality uses the assumption $d\leq k/(2e^{2}\ln k)$. ∎

The preceding proof relies on three supporting lemmas: 27 and 28 compute and
bound the Hermite coefficients of $f_{\theta}$; Lemma 29 gives upper- and
lower-bounds on $\theta_{k}$.

Let $\phi(x)=\frac{1}{\sqrt{2\pi}}e^{-x^{2}/2}$ denote the probability density
function of the one-dimensional Gaussian distribution $\mathcal{N}(0,1)$.

######  Lemma 27.

For all $j\geq 0$, the Hermite coefficients of $f_{\theta}$ are as follows:

$\widetilde{f_{\theta}}(j)=\begin{cases}\int_{-\theta}^{\theta}\phi(x)\operatorname{d\\!}x&\text{if
$j=0$},\\\ 0&\text{if $j$ is odd},\\\
-\frac{2}{\sqrt{j!}}h_{j-1}(\theta)\phi(\theta)&\text{if $j\geq 2$ is
even}.\end{cases}$

###### Proof.

Recalling the definition of univariate Hermite polynomials from Appendix B,
the degree-$0$ coefficient $\widetilde{f_{\theta}}(0)$ is

$\widetilde{f_{\theta}}(0)=\int_{-\infty}^{\infty}f_{\theta}(x)\phi(x)\operatorname{d\\!}x=\int_{-\theta}^{\theta}\phi(x)\operatorname{d\\!}x.$

The degree-$j$ coefficient, for $j\geq 1$, is

$\displaystyle\widetilde{f_{\theta}}(j)$
$\displaystyle=\frac{1}{\sqrt{j!}}\int_{-\infty}^{\infty}f_{\theta}(x)h_{j}(x)\phi(x)\operatorname{d\\!}x=\frac{1}{\sqrt{j!}}\int_{-\theta}^{\theta}h_{j}(x)\phi(x)\operatorname{d\\!}x$
$\displaystyle=\frac{1}{\sqrt{j!}}\int_{-\theta}^{\theta}-\frac{\operatorname{d\\!}}{\operatorname{d\\!}x}\left[h_{j-1}\phi(x)\right]\phi(x)\operatorname{d\\!}x=\frac{1}{\sqrt{j!}}\Big{\\{}-h_{j-1}(x)\phi(x)\Big{\\}}\Big{\rvert}_{-\theta}^{\theta}$
$\displaystyle=\frac{1}{\sqrt{j!}}\left(h_{j-1}(-\theta)-h_{j-1}(\theta)\right)\phi(\theta).$

The third equality follows from the identity
$h_{j}(x)\phi(x)=-\frac{\operatorname{d\\!}}{\operatorname{d\\!}x}\left[h_{j-1}\phi(x)\right]$
for $j\geq 1$, which follows from the definition in (3). The last equality
uses that $\phi(x)$ is an even function.

Furthermore, if $j$ is odd, then $h_{j-1}(-\theta)=h_{j-1}(\theta)$, and hence
$\widetilde{f_{\theta}}(j)=0$. If $j$ is even and $j\geq 2$, then
$h_{j-1}(-\theta)=-h_{j-1}(\theta)$, and hence
$\widetilde{f_{\theta}}(j)=-\frac{2}{\sqrt{j!}}h_{j-1}(\theta)\phi(\theta)$. ∎

We bound the even-degree Hermite coefficients of the interval function by
bounding each univariate Hermite polynomial, which provides the following
coefficient bound.

######  Lemma 28.

For any even $j\geq 2$ and any $\theta\geq 0$,

$\widetilde{f_{\theta}}(j)^{2}=\frac{4}{j!}h_{j-1}(\theta)^{2}\phi(\theta)^{2}\leq\left(1+\theta\sqrt{\frac{e}{j}}\right)^{2(j-1)}e^{-\theta^{2}}.$

###### Proof.

The equality is by 27. For the inequality, we define the following values:

$A_{j,\theta}:=\frac{1}{\sqrt{j!}}\left|h_{j-1}(\theta)\right|,\qquad
B_{j,\theta}:=\sqrt[4]{\frac{2e^{2}}{\pi
j^{3}}}\left(1+\theta\sqrt{\frac{e}{j}}\right)^{j-1}.$

We show that $A_{j,\theta}\leq B_{j,\theta}$. Since
$\widetilde{f_{\theta}}(j)^{2}=(2/\pi)A_{j,\theta}^{2}\cdot e^{-\theta^{2}}$,
this inequality implies that $\widetilde{f_{\theta}}(j)^{2}$ is at most
$(2/\pi)B_{j,\theta}^{2}\cdot e^{-\theta^{2}}$, which is easily verified to be
at most the claimed upper bound in the statement of 28.

We expand $A_{j,\theta}$ using an explicit formula for the Hermite polynomial
(Abramowitz and Stegun, 1972, Equation 22.3.11), followed by a change of
variable:

$\displaystyle A_{j,\theta}$
$\displaystyle=\frac{1}{\sqrt{j!}}\left|h_{j-1}(\theta)\right|$
$\displaystyle=\frac{(j-1)!}{\sqrt{j!}}\left|\sum_{m=0}^{j/2-1}\frac{(-1)^{m}\theta^{j-1-2m}}{2^{m}m!(j-1-2m)!}\right|$
(explicit formula for $h_{j-1}(\theta)$)
$\displaystyle=\frac{(j-1)!}{\sqrt{j!}}\left|\sum_{\text{odd}\
\ell=1}^{j-1}\frac{(-1)^{\frac{j-1-\ell}{2}}\theta^{\ell}}{2^{\frac{j-1-\ell}{2}}\left(\frac{j-1-\ell}{2}\right)!\ell!}\right|.$
(change of variable)

Thus, by the triangle inequality,

$\displaystyle A_{j,\theta}$ $\displaystyle\leq\sum_{\text{odd}\
\ell=1}^{j-1}\frac{(j-1)!}{\sqrt{j!}}\cdot\frac{\theta^{\ell}}{2^{\frac{j-1-\ell}{2}}\left(\frac{j-1-\ell}{2}\right)!\ell!}=\sum_{\text{odd}\
\ell=1}^{j-1}\frac{\sqrt{2}}{2^{j/2}}\binom{j-1}{\ell}\frac{(j-1-\ell)!}{\sqrt{j!}\left(\frac{j-1-\ell}{2}\right)!}(\sqrt{2}\theta)^{\ell}.$
(5)

We employ Stirling’s approximation $\sqrt{2\pi n}(n/e)^{n}e^{1/(12n+1)}\leq
n!\leq\sqrt{2\pi n}(n/e)^{n}e^{1/(12n)}$ to bound each term in the sum from
(5). For any odd $\ell\in[1,j-3]$:

$\displaystyle\frac{\sqrt{2}}{2^{j/2}}\binom{j-1}{\ell}\frac{(j-1-\ell)!}{\sqrt{j!}\left(\frac{j-1-\ell}{2}\right)!}(\sqrt{2}\theta)^{\ell}$
$\displaystyle\leq\frac{\sqrt{2}}{2^{j/2}}\binom{j-1}{\ell}\sqrt[4]{\frac{2}{\pi
j}}\left(\sqrt{\frac{e}{j}}\right)^{j}\left(\frac{2(j-1-\ell)}{e}\right)^{\frac{j-1-\ell}{2}}(\sqrt{2}\theta)^{\ell}$
$\displaystyle=\binom{j-1}{\ell}\sqrt[4]{\frac{2e^{2}}{\pi
j^{3}}}\left(\theta\sqrt{\frac{e}{j}}\right)^{\ell}\left(1-\frac{1+\ell}{j}\right)^{\frac{j-1-\ell}{2}}$
$\displaystyle\leq\sqrt[4]{\frac{2e^{2}}{\pi
j^{3}}}\binom{j-1}{\ell}\left(\theta\sqrt{\frac{e}{j}}\right)^{\ell}.$

We handle the final term, $\ell=j-1$, separately:

$\displaystyle\frac{\sqrt{2}}{2^{j/2}}\binom{j-1}{\ell}\frac{(j-1-\ell)!}{\sqrt{j!}\left(\frac{j-1-\ell}{2}\right)!}(\sqrt{2}\theta)^{\ell}$
$\displaystyle=\frac{\sqrt{2}}{2^{j/2}}\frac{1}{\sqrt{j!}}(\sqrt{2}\theta)^{j-1}\leq\frac{\sqrt{2}}{2^{j/2}}\frac{1}{(2\pi
j)^{1/4}}\left(\sqrt{\frac{e}{j}}\right)^{j}(\sqrt{2}\theta)^{j-1}$
$\displaystyle=\frac{1}{(2\pi
j)^{1/4}}\sqrt{\frac{e}{j}}\left(\theta\sqrt{\frac{e}{j}}\right)^{j-1}\leq\sqrt[4]{\frac{2e^{2}}{\pi
j^{3}}}\binom{j-1}{\ell}\left(\theta\sqrt{\frac{e}{j}}\right)^{\ell}.$

Therefore, we upper-bound the summation from (5) term-by-term, and then
further simplify bound by including additional non-negative terms in the
summation:

$\displaystyle A_{j,\theta}$ $\displaystyle\leq\sqrt[4]{\frac{2e^{2}}{\pi
j^{3}}}\sum_{\text{odd}\
\ell=1}^{j-1}\binom{j-1}{\ell}\left(\theta\sqrt{\frac{e}{j}}\right)^{\ell}$
$\displaystyle\leq\sqrt[4]{\frac{2e^{2}}{\pi
j^{3}}}\sum_{\ell=0}^{j-1}\binom{j-1}{\ell}\left(\theta\sqrt{\frac{e}{j}}\right)^{\ell}$
$\displaystyle=\sqrt[4]{\frac{2e^{2}}{\pi
j^{3}}}\left(1+\theta\sqrt{\frac{e}{j}}\right)^{j-1}=B_{j,\theta}.\qed$

######  Lemma 29.

For sufficiently large $k$, $\sqrt{2\ln k-\ln(2\ln
k)}\leq\theta_{k}\leq\sqrt{2\ln k}$.

###### Proof.

Recall that $\theta_{k}$ is defined so that
$\mathop{\mathbb{E}}\displaylimits_{{\mathbf{x}}\sim\mathcal{N}(0,I_{k})}\left[\mathsf{Cube}_{k}({\mathbf{x}})\right]=0$.
In other words, it is the median value of
${\mathbf{y}}:=\max_{i\in[k]}|{\mathbf{x}}_{i}|$, where
$({\mathbf{x}}_{1},\dotsc,{\mathbf{x}}_{k})\sim\mathcal{N}(0,1)^{\otimes k}$.
Therefore, it suffices to show that for $l_{k}:=\sqrt{2\ln k-\ln(2\ln k)}$ and
$u_{k}:=\sqrt{2\ln k}$, we have $\Pr[{\mathbf{y}}<l_{k}]\leq
1/2\leq\Pr[{\mathbf{y}}<u_{k}]$. Note that for any $t\geq 0$,
$\Pr[{\mathbf{y}}<t]=(1-\Pr_{{\mathbf{x}}_{1}\sim\mathcal{N}(0,1)}[|{\mathbf{x}}_{1}|\geq
t])^{k}$. Using the Mills ratio bound (see, e.g., Feller, 1968, Lemma 2 on
page 175) and $1-x\leq e^{-x}$ for all $x\in\mathbb{R}$,

$\displaystyle\Pr[{\mathbf{y}}<l_{k}]$
$\displaystyle\leq\left(1-\left(\frac{1}{l_{k}}-\frac{1}{l_{k}^{3}}\right)\sqrt{\frac{2}{\pi}}e^{-l_{k}^{2}/2}\right)^{k}$
$\displaystyle=\left(1-\frac{1}{\sqrt{2\ln k-\ln(2\ln
k)}}\left(1-o(1)\right)\sqrt{\frac{2}{\pi}}\cdot\frac{\sqrt{2\ln
k}}{k}\right)^{k}$
$\displaystyle\leq\exp\left(-\left(1-o(1)\right)\sqrt{\frac{2}{\pi}}\right)\leq\frac{1}{2}$

by the choice of $l_{k}$ and assumption that $k$ is sufficiently large.
Similarly (but now using $1-x\geq e^{-x/(1-x)}$ for $x<1$),

$\displaystyle\Pr[{\mathbf{y}}<u_{k}]$
$\displaystyle\geq\left(1-\frac{1}{u_{k}}\sqrt{\frac{2}{\pi}}e^{-u_{k}^{2}/2}\right)^{k}$
$\displaystyle=\left(1-\frac{1}{\sqrt{\pi\ln k}}\cdot\frac{1}{k}\right)^{k}$
$\displaystyle\geq\exp\left(-\left(1+o(1)\right)\frac{1}{\sqrt{\pi\ln
k}}\right)\geq\frac{1}{2}.\qed$

###  C.2 Properties of $\mathrm{TruncHigh}_{d,\tau}$ for sufficiently large
$\tau$ (Proof of 13)

We recall 13.

See 13

###### Proof of 13, part (i).

We first bound the low-degree Hermite coefficients of
$\mathrm{TruncHigh}_{d,\tau}(f)$. Fix some $J$ with $\left|J\right|\leq d$.
Then

$\displaystyle\left|\widetilde{\mathrm{TruncHigh}_{d,\tau}[f]}(J)\right|$
$\displaystyle\leq\left|\widetilde{\mathrm{High}_{d}[f]}(J)\right|+\frac{1}{\sqrt{J!}}\left|\mathop{\mathbb{E}}\displaylimits\left[\mathrm{High}_{d}[f]({\mathbf{x}})\mathbbm{1}\left\\{\left|\mathrm{Low}_{d}[f]({\mathbf{x}})\right|>\tau\right\\}H_{J}({\mathbf{x}})]\right]\right|$
$\displaystyle\leq\frac{1}{\sqrt{J!}}\left\|\mathrm{High}_{d}[f]\right\|_{2}\sqrt{\mathop{\mathbb{E}}\displaylimits\left[\mathbbm{1}\left\\{\left|\mathrm{Low}_{d}[f]({\mathbf{x}})>\tau\right|\right\\}H_{J}({\mathbf{x}})^{2}\right]}$
$\displaystyle\leq\frac{1}{\sqrt{J!}}\left\|f\right\|_{2}\mathop{\mathrm{Pr}}\displaylimits\left[\mathrm{Low}_{d}[f]({\mathbf{x}})>\tau\right]^{1/4}\left\|H_{J}\right\|_{4}$
$\displaystyle\leq\frac{1}{\sqrt{J!}}\left\|f\right\|_{2}\exp\left(-\frac{d}{8e}\left(\frac{\tau}{\left\|\mathrm{Low}_{d}[f]\right\|_{2}}\right)^{2/d}\right)3^{d/2}\sqrt{J!}$
$\displaystyle\leq\left\|f\right\|_{2}\exp\left(-\frac{d}{8e}\left(\frac{\tau}{\rho}\right)^{2/d}\right)3^{d/2}.$

The first inequality follows from the linearity of the Hermite expansion and a
triangle inequality. The second follows by Cauchy-Schwarz and the definition
of $\mathrm{High}_{d}(f)$. The third follows from
$\left\|\mathrm{High}_{d}[f]\right\|_{2}\leq\left\|f\right\|_{2}$ and another
application of Cauchy-Schwarz. The fourth uses Fact 25 and Fact 26 (note that
(1) gives ${\tau}/{\left\|\mathrm{Low}_{d}[f]\right\|_{2}}\geq e^{d}$, so Fact
26 can indeed be applied).

Now we consider the full Hermite expansion of
$\mathrm{Low}_{d}(\mathrm{TruncHigh}_{d,\tau}(f))$ and plug in $\tau$ to
retrieve the claim:

$\displaystyle\left\|\mathrm{Low}_{d}[\mathrm{TruncHigh}_{d,\tau}[f]]\right\|_{2}^{2}$
$\displaystyle=\sum_{\left|J\right|\leq
d}\widetilde{\mathrm{TruncHigh}_{d,\tau}[f]}(J)^{2}\leq
k^{d}\left\|f\right\|_{2}^{2}\exp\left(-\frac{d}{4e}\left(\frac{\tau}{\rho}\right)^{2/d}\right)3^{d}$
$\displaystyle\leq(3k)^{d}\left\|f\right\|_{2}^{2}\exp\left(-d\ln(3k)-\ln\left(\frac{a^{2}\left\|f\right\|_{2}^{2}}{\rho^{2}}\right)\right)=\frac{\rho^{2}}{a^{2}}.$

In the first inequality, we used the fact that the number of $k$-dimensional
multi-indices $J$ with $|J|\leq d$ is at most $k^{d}$ for $d\geq 2$. ∎

###### Proof of 13, part (ii).

We have

$\displaystyle\left\|\mathrm{TruncHigh}_{d,\tau}[f]-f\right\|_{1}$
$\displaystyle\leq\left\|f-\mathrm{High}_{d}[f]\right\|_{1}+\left\|\mathrm{High}_{d}[f]\mathbbm{1}\left\\{\left|\mathrm{Low}_{d}[f]\right|>\tau\right\\}\right\|_{1}$
$\displaystyle\leq\left\|\mathrm{Low}_{d}[f]\right\|_{1}+\left\|\mathrm{High}_{d}[f]\right\|_{2}\sqrt{\mathop{\mathrm{Pr}}\displaylimits\left[\left|\mathrm{Low}_{d}[f]\right|>\tau\right]}$
$\displaystyle\leq\left\|\mathrm{Low}_{d}[f]\right\|_{2}+\left\|f\right\|_{2}\sqrt{\mathop{\mathrm{Pr}}\displaylimits\left[\left|\mathrm{Low}_{d}[f]\right|>\tau\right]}$
$\displaystyle\leq\left\|\mathrm{Low}_{d}[f]\right\|_{2}+\left\|f\right\|_{2}\mathop{\mathrm{Pr}}\displaylimits\left[\left|\mathrm{Low}_{d}[f]\right|>\tau\right]^{1/4},$

where the first inequality is by the triangle inequality and the definition of
$\mathrm{TruncHigh}_{d,\tau}$, the second is Cauchy-Schwarz, and the third is
monotonicity of norms and
$\left\|\mathrm{High}_{d}[f]\right\|_{2}\leq\left\|f\right\|_{2}$. We once
again use Fact 26 and $\tau$ to obtain

$\displaystyle\left\|\mathrm{TruncHigh}_{d,\tau}[f]-f\right\|_{1}$
$\displaystyle\leq\rho+\left\|f\right\|_{2}\exp\left(-\frac{d}{8e}\left(4e\log(3k)+\frac{8e}{d}\log\left(\frac{a\left\|f\right\|_{2}}{\rho}\right)\right)\right)$
$\displaystyle\leq\rho+\frac{\rho}{a}\leq 2\rho.\qed$

###  C.3 Proof of exponential decay of $\tau_{i}$ for 10

######  Fact 30.

For any fixed $i\geq 1$ and

$\tau_{i}:=\frac{\left\|\mathrm{Low}_{d}[f_{0}]\right\|_{2}}{4^{(i-1)d}}\left(4e\ln(3k)+\frac{8e}{d}\ln\left(\frac{4^{id}\left\|f_{i-1}\right\|_{2}}{\left\|\mathrm{Low}_{d}[f_{0}]\right\|_{2}}\right)\right)^{d/2}$

from (2), if $\left\|f_{i-1}\right\|_{\infty}\leq\frac{4}{3}$, then
$\tau_{i}\leq\frac{\alpha}{3\cdot 2^{i}}$ for
$\alpha=\left\|\mathrm{Low}_{d}[f_{0}]\right\|_{2}^{0.996}(72\ln k)^{d/2}.$ In
addition, $\tau_{1}\geq\left\|\mathrm{Low}_{d}[f_{0}]\right\|_{2}$.

###### Proof.

We first consider the case where $i=1$. A sufficiently large choice of $k$
yields the following:

$\displaystyle\tau_{1}$
$\displaystyle=\left\|\mathrm{Low}_{d}[f_{0}]\right\|_{2}\left(4e\ln 3k+8e\ln
4+\frac{8e}{d}\ln\left(\frac{1}{\left\|\mathrm{Low}_{d}[f_{0}]\right\|_{2}}\right)\right)^{d/2}$
$\displaystyle[\left\|f_{0}\right\|_{2}=1]$
$\displaystyle\leq\left\|\mathrm{Low}_{d}[f_{0}]\right\|_{2}\left(11\ln
k+\frac{1000e}{\left\|\mathrm{Low}_{d}[f_{0}]\right\|_{2}^{1/125d}}\right)^{d/2}$
$\displaystyle[4e\ln 3k+8e\ln 4\leq 11\ln k;\ \ln x\leq x]$
$\displaystyle\leq\left\|\mathrm{Low}_{d}[f_{0}]\right\|_{2}\left({\frac{12}{\left\|\mathrm{Low}_{d}[f_{0}]\right\|_{2}^{1/125d}}\ln
k}\right)^{d/2}$ $\displaystyle[\forall x\geq 1,\ 11\ln k+1000ex\leq 12x\ln
k]$ $\displaystyle=\left\|\mathrm{Low}_{d}[f_{0}]\right\|_{2}^{0.996}(12\ln
k)^{d/2}\leq\frac{\alpha}{6}.$

Observe that $\tau_{1}\geq\left\|\mathrm{Low}_{d}[f_{0}]\right\|_{2}$ for
sufficiently large $k$, because the base of the exponent will always be at
least 1.

For fixed $i\geq 2$, we prove $\tau_{i}\leq\frac{\alpha}{e\cdot 2^{i}}$ by
bounding $\frac{\tau_{i}}{\tau_{1}}$. Using the assumption that
$\left\|f_{i-1}\right\|_{2}\leq\left\|f_{i-1}\right\|_{\infty}\leq\frac{4}{3}$,

$\displaystyle\frac{\tau_{i}}{\tau_{1}}$
$\displaystyle=\frac{1}{4^{(i-1)d}}\left(\frac{4e\ln(3k)+\frac{8e}{d}\ln(4^{id}\left\|f_{i-1}\right\|_{2})-\ln\left\|\mathrm{Low}_{d}[f_{0}]\right\|_{2}}{4e\ln(3k)+\frac{8e}{d}\ln(4^{d}\left\|f_{0}\right\|_{2})-\ln\left\|\mathrm{Low}_{d}[f_{0}]\right\|_{2}}\right)^{d/2}$
$\displaystyle\leq\frac{1}{4^{(i-1)d}}\left(\frac{\ln 4^{(i+1)d}}{\ln
4^{d}}\right)^{d/2}\leq\left(\frac{i+1}{16^{i-1}}\right)^{d/2}\leq\frac{1}{4^{id/2}}\leq\frac{1}{2^{i-1}}.\qed$

###  C.4 Proof of convergence of $f_{i}$’s in 10

The proof of 10 constructs a sequence of functions $f_{0},f_{1},\dots\in
L^{2}(\mathcal{N}(0,I_{k}))$ with the following properties for any $a$, $b$,
and $c$ having $b\geq 4$ and $c\leq 2$:

  1. 1.

For all $i$, $\left\|f_{i+1}-f_{i}\right\|_{1}\leq\frac{a}{b^{i}}$.

  2. 2.

For all $i$, $\left\|f_{i}\right\|_{\infty}\leq c$.

  3. 3.

$\lim_{i\to\infty}\left\|\mathrm{Low}_{d}(f_{i})\right\|_{2}=0.$

We now prove that such a sequence has a limit in $L^{2}(\mathcal{N}(0,I_{k}))$
with the desired properties, as given in the following proposition.

######  Proposition 31.

For the sequence described above, there exists some $f^{*}\in
L^{2}(\mathcal{N}(0,I_{k}))$ such that $\mathrm{Low}_{d}(f^{*})=0$,
$\left\|f^{*}\right\|_{\infty}\leq c$, and
$\left\|f^{*}-f_{i}\right\|_{1}\leq\frac{2a}{b^{i}}$ for all $i$.

Towards the proof of 31, we first show that properties (1) and (2) imply an
additional property about $L^{2}$ distances between iterates.

######  Lemma 32.

For all $i$, $\left\|f_{i+1}-f_{i}\right\|_{2}\leq\sqrt{\frac{2ac}{b^{i}}}$.

###### Proof.

By the triangle inequality we have $\left\|f_{i+1}-f_{i}\right\|_{\infty}\leq
2c$, and from this the bound is immediate from Holder’s inequality:

$\displaystyle\left\|f_{i+1}-f_{i}\right\|_{2}$
$\displaystyle\leq\sqrt{\left\|f_{i+1}-f_{i}\right\|_{\infty}\left\|f_{i+1}-f_{i}\right\|_{1}}\leq\sqrt{2c\cdot\frac{a}{b^{i}}}.\qed$

The following is immediate from 32 and the fact that
$L^{2}(\mathcal{N}(0,I_{k}))$ is complete (because it is a Hilbert space).

######  Corollary 33.

The sequence $f_{0},f_{1},\dots$ is a Cauchy sequence in
$L^{2}(\mathcal{N}(0,I_{k}))$ and converges to some $f^{*}\in
L^{2}(\mathcal{N}(0,I_{k}))$.

Before completing the proof of 31, we recall the following topological fact
concerning functional spaces $L^{2}$ and $L^{\infty}$.

######  Lemma 34.

For any probability measure $\mu$ on $\mathbb{R}^{k}$ and any $\alpha>0$,

$I_{\alpha}:=\left\\{f\in
L^{2}(\mu):\left\|f\right\|_{\infty}\leq\alpha\right\\}\ \text{is a closed set
in $L^{2}(\mu)$}.$

###### Proof.

Consider any functional sequence $(f_{n})_{n\in\mathbb{N}}$ in $I_{\alpha}$
such that $f_{n}\to f$ in $L^{2}(\mu)$ as $n\to\infty$. It is clear that the
limit $f$ belongs to $L^{2}(\mu)$ since $L^{2}(\mu)$ is, by itself, closed.
Thus, it suffices to prove that
$\mathop{\mathrm{Pr}}\displaylimits_{{\mathbf{x}}\sim\mu}\left[\left|f(x)\right|\leq\alpha\right]=1$.
Fix any $\varepsilon>0$ and $n\in\mathbb{N}$.

$\displaystyle\mathop{\mathrm{Pr}}\displaylimits_{{\mathbf{x}}\sim\mu}\left[|f({\mathbf{x}})|>\alpha+\varepsilon\right]$
$\displaystyle=\mathop{\mathrm{Pr}}\displaylimits\left[|f({\mathbf{x}})|>\alpha+\varepsilon\
\wedge\ |f_{n}({\mathbf{x}})|\leq\alpha\right]$
$\displaystyle\leq\mathop{\mathrm{Pr}}\displaylimits\left[|f({\mathbf{x}})-f_{n}({\mathbf{x}})|>\varepsilon\right]$
$\displaystyle\leq\frac{1}{\varepsilon^{2}}\int_{\mathbb{R}^{k}}|f(x)-f_{n}(x)|^{2}\mathrm{d}\mu(x)=\frac{\left\|f-f_{n}\right\|_{2}^{2}}{\varepsilon^{2}}.$

The final step follows from Chebyshev’s inequality. By assumption, we have
$\|f-f_{n}\|_{2}\to 0$ as $n\to\infty$. For every $\varepsilon>0$, we have
$\mathop{\mathrm{Pr}}\displaylimits\left[|f({\mathbf{x}})|>\alpha+\varepsilon\right]=0$.
Hence, $\|f\|_{\infty}\leq\alpha$ and $f\in I_{\alpha}$. ∎

######  Lemma 35.

$f^{*}$ satisfies the properties given in 31.

###### Proof.

Let $B_{i}=\\{g\in L^{2}(\mathcal{N}(0,I_{k})):\
\left\|g-f_{i}\right\|_{2}\leq 2\sqrt{\frac{2ac}{b^{i}}}\\}$ be the closed set
containing all functions in a small $L^{2}$-ball around the $i$-th iterate.
Note that $B_{i+1}\subset B_{i}$ for all $i\geq 0$ and that $\bigcap_{i\geq
0}B_{i}=\\{f^{*}\\}$. We prove each property of 31.

  1. 1.

Suppose that $\left\|\mathrm{Low}_{d}(f^{*})\right\|_{2}\geq\epsilon$ for any
fixed $\epsilon>0$. For any sufficiently large $i$,

$\left\|f^{*}-f_{i}\right\|_{2}\geq\left\|\mathrm{Low}_{d}(f^{*})-\mathrm{Low}_{d}(f_{i})\right\|_{2}\geq\left\|\mathrm{Low}_{d}(f^{*})\right\|_{2}-\left\|\mathrm{Low}_{d}(f_{i})\right\|_{2}\geq\epsilon-\frac{\epsilon}{2}=\frac{\epsilon}{2}.$

This would mean that exists some $i^{\prime}$ such that
$\left\|f^{*}-f_{i^{\prime}}\right\|_{2}\geq
2\sqrt{\frac{2ac}{b^{i^{\prime}}}}$, but then $f^{*}$ would lie outside
$B_{i^{\prime}}$, which is a contradiction.

  2. 2.

Let $I=\\{g\in L^{2}(\mathcal{N}(0,I_{k})):\ \left\|g\right\|_{\infty}\leq
c\\}$. By 34 (with $\mu=\mathcal{N}(0,I_{k})$), $I$ is closed in
$L^{2}(\mathcal{N}(0,I_{k}))$ and $f_{0},f_{1},\dots$ is a sequence in $I$
with limit $f^{*}\in L^{2}(\mathcal{N}(0,I_{k}))$, we must have that $f^{*}\in
I$ as well. Thus, $\left\|f^{*}\right\|_{\infty}\leq c$.

  3. 3.

Fix any $i\geq 0$. Choose some $i^{\prime}>i$ such that
$b^{i^{\prime}}\geq\frac{18b^{2i}c}{a}$. Because $f^{*}\in B_{i^{\prime}}$, it
follows that
$\left\|f_{i^{\prime}}-f^{*}\right\|_{1}\leq\left\|f_{i^{\prime}}-f^{*}\right\|_{2}\leq
2\smash{\sqrt{\frac{2ac}{b^{i^{\prime}}}}}\leq\frac{2a}{3b^{i}}$. Thus,

$\left\|f^{*}-f_{i}\right\|_{1}\leq\left\|f_{i^{\prime}}-f_{i}\right\|_{1}+\left\|f^{*}-f_{i^{\prime}}\right\|_{1}\leq\sum_{\iota=i}^{i^{\prime}-1}\frac{a}{b^{\iota}}+\frac{2a}{3b^{i}}\leq\frac{a}{b^{i}}\sum_{\iota=0}^{\infty}\frac{1}{4^{\iota}}+\frac{2a}{3b^{i}}=\frac{2a}{b^{i}}.\qed$

##  Appendix D Supporting proof for Section 4

###  D.1 Existence of a hard-to-weak-learn intersection of halfspaces (Proof
of 16)

See 16

###### Proof.

In the proof of 15, $\mathcal{D}_{\mathrm{actual}}$ is a distribution which is
supported on intersections of finitely many halfspaces. In more detail, for
$\Lambda=q^{100}\ln 2$ and some $M\gg\Lambda$ (the exact value is not
important for our purposes), a draw of
$\bm{f}\sim\mathcal{D}_{\mathrm{actual}}$ is defined in the proof of Theorem 2
of De and Servedio (2021) to be an intersection of $H_{\bm{f}}\leq M$
halfspaces from a fixed collection $\\{h_{1},\dots,h_{M}\\}$, where each
halfspace $h_{i}$ is independently included in the intersection with
probability $\frac{\Lambda}{M}$. Note that the expected number of halfspaces
included in $\bm{f}$ is $\mathbb{E}\left[H_{\bm{f}}\right]=\Lambda$.

We define $\mathcal{D}$ to be the conditional distribution of
$\mathcal{D}_{\mathrm{actual}}$ conditioned on
$\bm{f}\sim\mathcal{D}_{\mathrm{actual}}$ being an intersection of at most
$q^{101}$ halfspaces. By Markov’s inequality, we have that $H_{\bm{f}}\leq
q^{101}\ln 2\leq q^{101}$ with probability at least $1-{\frac{1}{q}}$. We
bound the expected accuracy of the classifer $h$ returned by $\mathcal{A}$ for
random $\bm{f}\sim\mathcal{D}$ by comparing it to the expected error of a
random $\bm{f}\sim\mathcal{D}_{\mathrm{actual}}$:

$\displaystyle\mathop{\mathrm{Pr}}\displaylimits_{\bm{f}\sim\mathcal{D},\mathcal{A},{\mathbf{x}}}\left[h({\mathbf{x}})\neq\bm{f}({\mathbf{x}})\right]$
$\displaystyle=\mathop{\mathrm{Pr}}\displaylimits_{\bm{f}\sim\mathcal{D}_{\mathrm{actual}},\mathcal{A},{\mathbf{x}}}\left[h({\mathbf{x}})\neq\bm{f}({\mathbf{x}})\mid
H_{\bm{f}}\leq q^{101}\right]$
$\displaystyle\geq\mathop{\mathrm{Pr}}\displaylimits_{\bm{f}\sim\mathcal{D}_{\mathrm{actual}},\mathcal{A},{\mathbf{x}}}\left[h({\mathbf{x}})\neq\bm{f}({\mathbf{x}}),H_{\bm{f}}\leq
q^{101}\right]$
$\displaystyle\geq\mathop{\mathrm{Pr}}\displaylimits_{\bm{f}\sim\mathcal{D}_{\mathrm{actual}},\mathcal{A},{\mathbf{x}}}\left[h({\mathbf{x}})\neq\bm{f}({\mathbf{x}})\right]-\mathop{\mathrm{Pr}}\displaylimits_{\bm{f}\sim\mathcal{D}_{\mathrm{actual}},\mathcal{A},{\mathbf{x}}}\left[H_{\bm{f}}>q^{101}\right]$
$\displaystyle\geq\frac{1}{2}-\frac{O(\log
q)}{\sqrt{m}}-\frac{1}{q}\geq\frac{1}{2}-\frac{O(\log q)}{\sqrt{m}},$

where in the last line we used that ${\frac{1}{q}}=\frac{O(\log q)}{\sqrt{m}}$
(with room to spare) since $q\geq m$. ∎

##  Appendix E Supporting lemmas and proofs for Section 5

In what follows we describe our approach to strengthen the SQ lower bounds
from Section 4; the lower bounds from Section 3 can be similarly strengthened
in an entirely analogous fashion. Recall the intersection $k+1$ halfspaces
over $\mathbb{R}^{m+1}$ obtained by taking the intersection of

  * •

the $k$ halfspaces identified in 17 over $\mathbb{R}^{m}$; and

  * •

an origin-centered halfspace orthogonal to the $(m+1)$-st coordinate basis
vector.

This intersection of $k+1$ halfspaces $f:\mathbb{R}^{m+1}\to\\{-1,1\\}$ can be
written as $f(x_{1},\dots,x_{m+1})=f_{1}(x_{1},\dots,x_{m})\wedge
f_{2}(x_{m+1})$, where $f_{1}:\mathbb{R}^{m}\to\\{-1,1\\}$ is the intersection
of $k$ halfspaces given in 17, $f_{2}:\mathbb{R}\to\\{-1,1\\}$ is the
$\textrm{sign}(\cdot)$ function which outputs 1 on an input $z$ iff $z>0$, and
the “$\wedge$” of two values from $\\{-1,1\\}$ is 1 iff both of them are 1.

The following lemma gives a lower bound on the approximate degree of $f$ in
terms of the approximate degrees of $f_{1}$ and $f_{2}$.

######  Lemma 36.

Let ${\mathbf{z}}_{1}$ and ${\mathbf{z}}_{2}$ be independent random variables
in $\mathbb{R}^{n_{1}}$ and $\mathbb{R}^{n_{2}}$, respectively. Fix any
$\epsilon>0$ and $g_{i}\colon\mathbb{R}^{n_{i}}\to\\{-1,1\\}$ for
$i\in\\{1,2\\}$ with
$c:=\min\\{\Pr_{{\mathbf{z}}_{1}}[g_{1}({\mathbf{z}}_{1})=1],\Pr_{{\mathbf{z}}_{2}}[g_{2}({\mathbf{z}}_{2})=1]\\}>0$.
Then the function $g\colon\mathbb{R}^{n_{1}+n_{2}}\to\\{-1,1\\}$ defined by
$g(z_{1},z_{2}):=g_{1}(z_{1})\wedge g_{2}(z_{2})$ has $L^{1}$
$(c\epsilon)$-approximate degree at least $\max\\{d_{1},d_{2}\\}$ (with
respect to the joint distribution of $({\mathbf{z}}_{1},{\mathbf{z}}_{2})$),
where $d_{i}$ is the $L^{1}$ $\epsilon$-approximate degree of $g_{i}$ (with
respect to the marginal distribution of ${\mathbf{z}}_{i}$).

###### Proof.

Assume without loss of generality that $d_{1}\geq d_{2}$. For a
$\\{-1,1\\}$-valued function $h$, let $h^{\prime}={\frac{h+1}{2}}$ (so
$h^{\prime}$ is the $\\{0,1\\}$-valued version of $h$). We observe that
$c=\min\\{\mathbb{E}_{{\mathbf{z}}_{1}}[g^{\prime}_{1}({\mathbf{z}}_{1})],\mathbb{E}_{{\mathbf{z}}_{2}}[g^{\prime}_{2}({\mathbf{z}}_{2})]\\},$
and that $d_{i}$ is the $L^{1}$ $(\epsilon/2)$-approximate degree of
$g^{\prime}_{i}$.

Let $d$ be the $L^{1}$ $({c\epsilon/2})$-approximate degree of ${g^{\prime}}$,
and let $p^{\prime}$ be a degree-$d$ polynomial over
$\mathbb{R}^{n_{1}+n_{2}}$ satisfying
$\mathbb{E}_{{\mathbf{z}}_{1},{\mathbf{z}}_{2}}[|{g^{\prime}}({\mathbf{z}}_{1},{\mathbf{z}}_{2})-{p^{\prime}}({\mathbf{z}}_{1},{\mathbf{z}}_{2})|]\leq{c\epsilon/2}$.
For this polynomial $p$,

$\displaystyle\min_{{z_{2}\in\mathbb{R}^{n_{2}}:{g^{\prime}_{2}}(z_{2})=1}}\mathbb{E}_{{\mathbf{z}}_{1}}[\left|{g^{\prime}}({\mathbf{z}}_{1},z_{2})-{p^{\prime}}({\mathbf{z}}_{1},z_{2})\right|]$
$\displaystyle\leq\mathbb{E}_{{\mathbf{z}}_{1},{\mathbf{z}}_{2}}\left[\left|{g^{\prime}}({\mathbf{z}}_{1},{\mathbf{z}}_{2})-{p^{\prime}}({\mathbf{z}}_{1},{\mathbf{z}}_{2})\right|\cdot\frac{{g^{\prime}_{2}}({\mathbf{z}}_{2})}{\mathbb{E}_{{\mathbf{z}}_{2}}[{g^{\prime}_{2}}({\mathbf{z}}_{2})]}\right]$
$\displaystyle\leq\frac{\mathbb{E}_{{\mathbf{z}}_{1},{\mathbf{z}}_{2}}[\left|{g^{\prime}}({\mathbf{z}}_{1},{\mathbf{z}}_{2})-{p^{\prime}}({\mathbf{z}}_{1},{\mathbf{z}}_{2})\right|]}{c}\leq\frac{\epsilon}{2}.$

So there exists $z_{2}\in\mathbb{R}^{n_{2}}$ such that

$\mathbb{E}_{{\mathbf{z}}_{1}}[\left|{g^{\prime}}({\mathbf{z}}_{1},z_{2})-{p^{\prime}}({\mathbf{z}}_{1},z_{2})\right|]=\mathbb{E}_{{\mathbf{z}}_{1}}[\left|{g^{\prime}_{1}}({\mathbf{z}}_{1})-{p^{\prime}}({\mathbf{z}}_{1},z_{2})\right|]\leq\frac{\epsilon}{2}.$

Letting $p=2p^{\prime}-1$, since $g=2g^{\prime}-1$, there exists
$z_{2}\in\mathbb{R}^{n_{2}}$ such that

$\mathbb{E}_{{\mathbf{z}}_{1}}[\left|g({\mathbf{z}}_{1},z_{2})-p({\mathbf{z}}_{1},z_{2})\right|]=2\,\mathbb{E}_{{\mathbf{z}}_{1}}[\left|g^{\prime}_{1}({\mathbf{z}}_{1})-p^{\prime}({\mathbf{z}}_{1},z_{2})\right|]\leq\epsilon.$

Since $p(\cdot,z_{2})$ is a polynomial over $\mathbb{R}^{n_{1}}$ of degree at
most $d$, it follows that the $L^{1}$ ${(\epsilon/2)}$-approximate degree of
${g^{\prime}_{1}}$ is at most $d$. Hence $d\geq d_{1}=\max\\{d_{1},d_{2}\\}$.
Since the $L^{1}$ $(c\epsilon/2)$-approximate degree of $g^{\prime}$ (which is
$d$) is the same as the $L^{1}$ $(c\epsilon)$-approximate degree of $g$, the
lemma is proved. ∎

By 17, the $L^{1}$ ${\frac{1}{2}}$-approximate degree of $f_{1}$ is at least
$\Omega(\log(k)/\log\log k)$, and hence so is its $L^{1}$
$(4\epsilon)$-approximate degree (for $\epsilon\leq 1/8$). A lower bound on
the $L^{1}$ $(4\epsilon)$-approximate degree of $f_{2}$ is given by the
following result of Ganzburg (2002).

######  Lemma 37.

For any $\epsilon>0$, the $L^{1}$ $\epsilon$-approximate degree of the
$\textrm{sign}(\cdot)$ function is $\Omega(1/\epsilon^{2})$.

37 (presented as Corollary B.1 of Diakonikolas et al. (2021b)) is a direct
consequence of Theorem 1 of Ganzburg (2002) and Theorem 4 of Vaaler (1985).

We are now almost ready to apply 36 to our intersection of $k+1$ halfspaces
obtained via $f_{1}$ (from 17) and $f_{2}$ (the sign function). We just need
to ensure that each of $f_{1}$ and $f_{2}$ takes value $+1$ with sufficient
probability. First, observe that $f_{1}$ satisfies $\Pr_{{\mathbf{x}}\sim{\cal
N}(0,I_{m})}[f_{1}({\mathbf{x}})=1]\geq 1/4$, since otherwise the
$1/2$-approximate degree of $f$ would be zero, as witnessed by the constant
$-1$ function. Moreover, $\Pr_{{\mathbf{x}}\sim{\cal
N}(0,1)}[f_{2}({\mathbf{x}})=1]=1/2$ by symmetry of ${\cal N}(0,1)$. So, we
have established that both $f_{1}$ and $f_{2}$ take value $+1$ with
probability at least $1/4$, and that also they have $(4\epsilon)$-approximate
degrees $\Omega(\log(k)/\log\log k)$ and $\Omega(1/\epsilon^{2})$,
respectively. Therefore, 36 implies a lower bound on the $L^{1}$
$\epsilon$-approximate degree of $f$, as stated in the following lemma.

######  Lemma 38.

For any $k=2^{O(n^{0.245})}$ and any $\epsilon>0$, there is an intersection of
$k+1$ halfspaces $f\colon\mathbb{R}^{m+1}\to\\{-1,1\\}$ with $L^{1}$
$\epsilon$-approximate degree $\Omega(\frac{\log k}{\log\log
k}+\frac{1}{\epsilon^{2}})$, where $m=O(n^{0.49})$.

38 and 6 together imply Theorem 18.

See 18