# An initial alignment between neural network and target
is needed for gradient descent to learn

Emmanuel Abbe  Ecole Polytechnique Fédérale de Lausanne (EPFL)
<EMAIL_ADDRESS>Elisabetta Cornacchia  Ecole Polytechnique Fédérale de
Lausanne (EPFL)
<EMAIL_ADDRESS>Jan Hązła  Ecole Polytechnique Fédérale de Lausanne
(EPFL)
<EMAIL_ADDRESS>Christopher Marquis  Ecole Polytechnique Fédérale de
Lausanne (EPFL)
<EMAIL_ADDRESS>
###### Abstract

This paper introduces the notion of ’’Initial Alignment‘‘ (INAL) between a
neural network at initialization and a target function. It is proved that if a
network and a Boolean target function do not have a noticeable INAL, then
noisy gradient descent on a fully connected network with normalized i.i.d.
initialization will not learn in polynomial time. Thus a certain amount of
knowledge about the target (measured by the INAL) is needed in the
architecture design. This also provides an answer to an open problem posed in
[AS20a]. The results are based on deriving lower-bounds for descent algorithms
on symmetric neural networks without explicit knowledge of the target function
beyond its INAL.

##  1 Introduction

Does one need an educated guess on the type of architecture needed in order
for gradient descent to learn certain target functions? Convolutional neural
networks (CNNs) have an architecture that is natural for learning functions
having to do with image features: at initialization, a CNN is already well
posed to pick up correlations with the image content due to its convolutional
and pooling layers, and gradient descent (GD) allows to locate and amplify
such correlations. However, a CNN may not be the right architecture for non-
image based target functions, or even certain image-based functions that are
non-classical [LLM+18]. More generally, we raise the following question:

> Is a certain amount of ’initial alignment‘ needed between a neural network
> at initialization and a target function in order for GD to learn on a
> reasonable horizon? Or could a neural net that is not properly designed but
> large enough find its own path to correlate with the target?

In order to formalize the above question, one needs to define the notion of
’alignment‘ as well as to quantify the ’certain amount‘ and ’reasonable
horizon‘ notions. This paper focuses on the ’polynomial-scaling‘ regime and on
fully connected architectures, but we conjecture that a more general
quantitative picture can be derived. Before defining the question formally, we
stress a few connections to related problems.

A different type of ’gradual‘ question has recently been investigated for
neural networks, namely, the ’depth gradual correlation‘ hypothesis. This
postulates that if a neural network of low depth (e.g., depth 2) cannot learn
to a non-trivial accuracy after GD has converged, then an augmentation of the
depth to a larger constant will not help in learning [MSS19, AZL20]. In
contrast, the question studied here is more of a ’time gradual correlation‘
hypothesis, saying that if at time zero GD cannot correlate non-trivially with
a target function (i.e., if the neural net at time zero does not have an
initial alignment), then a polynomial number of GD steps will not help.

From a lower-bound point of view, the question we ask is also slightly
different than the traditional lower-bound questions posed in the learning
literature that have to do with the difficulties of learning a class of
functions irrespective of a specific architecture. For instance, it is known
from [BFJ+94, Kea98] that the larger the statistical dimension of a function
class is, the more challenging it is for a statistical query (SQ) algorithm to
learn, and similarly for GD-like algorithms [AKM+21]; these bounds hold
irrespective of the type of neural network architectures used.

A more architecture-dependent lower-bound is derived in [AS20b], where the
junk-flow is essentially used as replacement of the number of queries, and
which depends on the type of architecture and initialization albeit being
implicit. In [SSM21], a separation between fully connected and CNN
architectures is obtained, showing that certain target functions have a
locality property and are better learned by the latter architecture. In a
different setting, [TAY21] gives a generalization lower bound for decision
trees on additive generative models, proving that decision trees are
statistically inefficient at estimating additive regression functions.
However, none of the bounds in these works give an explicit figure of merit to
measure the suitability of a neural network architecture for a target.

One can interpret such bounds, especially the one in [AS20b], as follows. If
the function class is such that for two functions $F,F^{\prime}$ sampled
randomly from the class, the typical correlation is not noticeable, i.e., if
the cross-predictability (CP) is given by

$\displaystyle\operatorname{CP}(F,F^{\prime}):=\mathbb{E}_{F,F^{\prime}}\langle
F,F^{\prime}\rangle^{2}=n^{-\omega_{n}(1)},$ (1)

(where we denoted by $\langle.\rangle$ the $L^{2}$-scalar product, namely, for
some input distribution $P_{\mathcal{X}}$, $\langle
f,g\rangle=\mathbb{E}_{x\sim P_{\mathcal{X}}}[f(x)g(x)]$ and by
$\omega_{n}(1)$ any sequence that is diverging to $\infty$ as $n\to\infty$),
then GD with polynomial precision and on a polynomial horizon will not be able
to identify the target function with an inverse polynomial accuracy (weak
learning), because at no time the algorithm will approach a good approximation
of the target function; i.e. the gradients stay essentially agnostic to the
target.

Instead, here we focus on a specific function — rather than a function class —
and on a specific architecture and initialization. One can engineer a function
class from a specific function if the initial architecture has some
distribution symmetry. In such case, if the original function is learnable,
then its orbit under the group of symmetry must also be learnable, and thus
lower bounds based on the cross-predictability or statistical dimension of the
orbit can be used. Such lower bounds are no longer applying to any
architecture but exploit the symmetry of the architecture, however they still
require knowledge of the target function in order to define the orbit.

In this paper, we would like to depart from the setting where we know the
target function and thus can analyze the orbit directly. Instead, we would
like to have a ’proxy‘ that depends on the underlying target function and the
initialized neural net $\operatorname{NN}_{\Theta^{0}}$ at hand, where the set
of weights at time zero $\Theta^{0}$ are drawn according to some distribution.
In [AS20a], the following proposal is made (the precise statement will appear
below): can we replace the correlation among a function class by the
correlation between a target function and an initialized net in order to have
a necessary requirement for learning, i.e., if

$\displaystyle\mathbb{E}_{\Theta^{0}}\langle
f,\operatorname{NN}_{\Theta^{0}}\rangle^{2}=n^{-\omega_{n}(1)},$ (2)

or in other words, if at initialization the neural net correlates negligibly
with the target function, is it still possible for GD to learn111Even with
just an inverse polynomial accuracy, a.k.a., weak learning. the function $f$
if the number of epochs of GD is polynomial? We next formalize the question
further and provide an answer to it.

Note the difference between (1) and (2): in (1) it is the class of functions
that is too poorly correlated for any SQ algorithm to efficiently learn; in
(2) it is the specific network initialization that is too poorly correlated
with the specific target in order for GD to efficiently learn.

While previous works and our proof relies on creating the orbit of a target
function using the network symmetries and then arguing from the complexity of
the orbit (using cross-predictability [AS20a]), we believe that the INAL
approach can be fruitful in additional contexts. In fact, the orbit approaches
have two drawbacks: (1) they cannot give lower-bounds on functions like the
full parity222we call full parity the function $f:\\{\pm 1\\}^{n}\to\\{\pm\\}$
s.t. $f(x)=\prod_{i=1}^{n}x_{i}$. that have no complex orbit (in fact the
orbit of the full parity is itself under permutation symmetries), (2) to
estimate the complexity measure of the orbit class (e.g., the cross-
predictability) from a sample set without full access to the target function,
one needs labels of data points under the group action that defines the orbit
(e.g., permutations), and these may not always be available from an arbitrary
sample set. In contrast, (i) the INAL can still be small for the full parity
function on certain symmetric neural networks, suggesting that in such cases
the full parity is not learnable (we do not prove this here due to our
specific proof technique but conjecture that this result still holds), (ii)
the INAL can always be estimated from a random i.i.d. sample set, using basic
Monte Carlo simulations (as used in our experiments, see Section 5).

While the notion of INAL makes sense for any input distribution, our
theoretical results are proved in a more limited setting of Boolean functions
with uniform inputs. This follows the approach that has been taken in [AS20b]
and we made that choice for similar reasons. Furthermore, any computer-encoded
function is eventually Boolean and major part of the PAC learning theory has
indeed focused on Boolean functions (we refer to [SSBD14] for more on this
subject). We nonetheless expect that the footprints of the proofs derived in
this paper will apply to inputs that are iid Gaussians or spherical, using
different basis than the Fourier-Walsh one.

Our general strategy in obtaining such a result is as follows: we first show
that for the type of architecture considered, a low initial alignment (INAL)
implies that the implicit target function is essentially high-degree in its
Fourier basis; this part is specific to the architecture and the low INAL
property. We next use the symmetry of the initialization to conclude that
learning under such high-degree Fourier requirement implies learning a low CP
class, and thus conclude by leveraging the results from [AS20b]. Finally, we
do some experiments with the types of architecture used in our formal results,
but also with convolutional neural nets to test the robustness of the original
conjecture. We observe that generally the INAL gives a decent proxy for the
difficulty to learn (lower INAL gives lower learning accuracy). While this
goes beyond the scope of our paper — which is to obtain a first rigorous
validation of the INAL conjecture for standard fully connected neural nets —
we believe that the numerical simulations give some motivations to pursue the
study of the INAL in a more general setting.

##  2 Definitions and Theoretical Contributions

For the purposes of our definition, a neural network $\operatorname{NN}$
consists of a set of neurons $V_{\operatorname{NN}}$, a random variable
$\Theta^{0}\in\mathbb{R}^{k}$ which corresponds to the initialization and a
collection of functions
$\operatorname{NN}_{\Theta^{0}}^{(v)}:\mathbb{R}^{n}\to\mathbb{R}$ indexed
with $v\in V_{\operatorname{NN}}$, representing the outputs of neurons in the
network. The Initial Alignment (INAL) is defined as the average squared
correlation between the target function and any of the neurons at
initialization:

######  Definition 1 (Initial Alignment (INAL)).

Let $f:\mathbb{R}^{n}\to\mathbb{R}$ be a function and $P_{\mathcal{X}}$ a
distribution on $\mathbb{R}^{n}$. Let $\operatorname{NN}$ be a neural network
with neuron set $V_{\operatorname{NN}}$ and random initialization
$\Theta^{0}$. Then, the $\operatorname{INAL}$ is defined as

$\displaystyle\operatorname{INAL}(f,\operatorname{NN}):=\max_{v\in
V_{\operatorname{NN}}}\mathbb{E}_{\Theta^{0}}\langle
f,\operatorname{NN}_{\Theta^{0}}^{(v)}\rangle^{2},$ (3)

where we denoted by $\langle.\rangle$ the $L^{2}$-scalar product, namely
$\langle f,g\rangle=\mathbb{E}_{x\sim P_{\mathcal{X}}}[f(x)g(x)]$.

While the above definition makes sense for any neural network architecture, in
this paper we focus on fully connected networks. Thus, in the following
$\operatorname{NN}$ will denote a fully connected neural network. Our main
thesis is that in many settings a small INAL is bad news: If at initialization
there is no noticeable correlation between any of the neurons and the target
function, the GD-trained neural network will not be able to recover such
correlation during training in polynomial time.

Of particular interest to us is the notion of INAL for a single neuron with
activation $\sigma$ and normalized Gaussian initialization.

######  Definition 2.

Let $f:\mathbb{R}^{n}\to\mathbb{R}$, $\sigma:\mathbb{R}\to\mathbb{R}$ and let
$P_{\mathcal{X}}$ be a distribution on $\mathbb{R}^{n}$. Then, we abuse the
notation and write

$\displaystyle\operatorname{INAL}(f,\sigma):=\mathbb{E}_{w^{n},b^{n}}\left[\Big{(}\mathbb{E}_{x\sim
P_{\mathcal{X}}}f(x)\sigma((w^{n})^{T}x+b^{n})\Big{)}^{2}\right]\;,$ (4)

where $w^{n}$ is a vector of iid $\mathcal{N}(0,1/n)$ Gaussians and $b^{n}$ is
another independent $\mathcal{N}(0,1/n)$ Gaussian. In the following, for
readability, we will write $w=w^{n}$ and $b=b^{n}$, omitting the dependence on
$n$.

In the following, we say that a function $f:\mathbb{N}\to\mathbb{R}_{\geq 0}$
is _noticeable_ if there exists $c\in\mathbb{N}$ such that
$f(n)=\Omega(n^{-c})$. On the other hand, we say that $f$ is _negligible_ if
$\lim_{n\to\infty}n^{c}f(n)=0$ for every $c\in\mathbb{N}$ (which we also write
$f(n)=n^{-\omega_{n}(1)}$).

######  Definition 3 (Weak learning).

Let $(f_{n})_{n\in\mathbb{N}}$ be a sequence of functions such that
$f_{n}:\mathbb{R}^{n}\to\mathbb{R}$ and $(P_{n})$ a sequence of probability
distributions on $\mathbb{R}^{n}$. Let $(A_{n})$ be a family of randomized
algorithms such that $A_{n}$ outputs a function
$\operatorname{NN}_{n}:\mathbb{R}^{n}\to\mathbb{R}$. Then, we say that $A_{n}$
_weakly learns_ $f_{n}$ if the function

$\displaystyle
g(n):=\big{|}\mathbb{E}_{x\sim\mathcal{P}_{n},A_{n}}[f_{n}(x)\cdot\operatorname{NN}_{n}(x)]\big{|}$
(5)

is noticeable.

In this paper, we follow the example of [AS20b] and focus on _Boolean_
functions with inputs and outputs in $\\{\pm 1\\}$. We consider sequences of
Boolean functions $f_{n}:\\{\pm 1\\}^{n}\to\\{\pm 1\\}$, with the uniform
input distribution $\mathcal{U}^{n}$, meaning that if $x\sim\mathcal{U}^{n}$,
then for all $i\in[n]$, $x_{i}\overset{iid}{\sim}\operatorname{Rad}(1/2)$. We
focus on fully connected neural networks with activation function $\sigma$,
and trained by noisy GD — this means GD where the gradient‘s magnitude per the
precision noise is polynomially bounded, as commonly considered in statistical
query algorithms [Kea98, BFJ+94] and GD learning [AS20b, MKAS21, AKM+21]; see
Remark 4 for a remainder of the definition. We consider activation functions
that satisfy the following conditions.

######  Definition 4 (Expressive activation).

We say that a function $\sigma:\mathbb{R}\to\mathbb{R}$ is _expressive_ if it
satisfies the following conditions:

  * a)

$\sigma$ is measurable and _polynomially bounded_ i.e. there exists $C,c>0$
such that $|\sigma(x)|\leq Cx^{c}+C$ for all $x\in\mathbb{R}$.

  * b)

Let the Gaussian smoothing of $\sigma$ be defined as
$\Sigma(t):=\mathbb{E}_{Y\sim\mathcal{N}(0,1)}[\sigma(Y+t)]$. For each
$m\in\mathbb{N}$ either $\Sigma^{(m)}(0)\neq 0$ or $\Sigma^{(m+1)}(0)\neq 0$
(where $\Sigma^{(m)}$ denotes the $m$-th derivative of $\Sigma$).

######  Remark 1.

  * i)

Note that we have the identities $d_{m}=\frac{\Sigma^{(m)}(0)}{m!}$, and
$\sigma=\sum_{m=0}^{\infty}d_{m}H_{m}$, where $H_{m}$ are the probabilist‘s
Hermite polynomials. Therefore, an equivalent statement of the second
condition in Definition 4 is that there are no two or more consecutive zeros
in the Hermite expansion of $\sigma$.

  * ii)

Many functions are expressive, including ReLU and sign (see Appendix B for the
proofs of those two cases).

  * iii)

On the other hand, it turns out that polynomials are _not_ expressive, as they
do not satisfy point $b)$. This is necessary for our hardness results to hold,
since for an activation function $P$ which is a polynomial of degree $k$ and
$M$ a monomial of degree $k+1$ it can be checked that
$\operatorname{INAL}(M,P)=0$, but constant-degree monomials are learnable by
GD.

Let us give one more definition before stating our main theorem.

######  Definition 5 (N-Extension).

For a function $f:\mathbb{R}^{n}\to\mathbb{R}$ and for $N>n$, we define its
_N-extension_ $\overline{f}:\mathbb{R}^{N}\to\mathbb{R}$ as

$\displaystyle\overline{f}(x_{1},x_{2},...,x_{n},x_{n+1},x_{n+2},...,x_{N})=f(x_{1},x_{2},...,x_{n}).$
(6)

We can now state our main result which connects INAL and weak learning.

######  Theorem 1 (Main theorem, informal).

Let $\sigma$ be an expressive activation function and $(f_{n})$ a sequence of
Boolean functions with uniform distribution on $\\{\pm 1\\}^{n}$. If
$\operatorname{INAL}(f_{n},\sigma)$ is negligible, then, for every
$\epsilon>0$, the $n^{1+\epsilon}$-extension of $f_{n}$ is _not_ weakly
learnable by $\operatorname{poly}(n)$-sized fully-connected neural networks
with iid initialization and $\operatorname{poly}(n)$-number of steps of noisy
gradient descent.

######  Remark 2.

Theorem 1 says that Boolean functions that have negligible correlation for
_some_ expressive activation and Gaussian iid initialization, cannot be
learned by neural networks utilizing _any_ activation on a fully-connected
architecture and any iid initialization.

######  Remark 3.

Consider a sequence of neural networks $(\operatorname{NN}_{n})$ utilizing an
expressive activation $\sigma$. We believe that the notion of
$\operatorname{INAL}(f_{n},\operatorname{NN}_{n})$ is relevant to
characterizing if a family of Boolean functions $(f_{n})$ is weakly learnable
by noisy GD on those neural networks. On the one hand, if
$\operatorname{INAL}(f_{n},\operatorname{NN}_{n})$ is noticeable, then at
initialization there exists a neuron from which a weak correlation with
$f_{n}$ can be extracted. Therefore, in a sense weak learning is achieved at
initialization.

On the other hand, assume additionally that the architecture is such that
there exists a neuron computing $\sigma(w^{T}x+b)$, where $x$ is the input and
$(w,b)$ are initialized as iid $\mathcal{N}(0,1/n)$ Gaussians. (In other
words, there exists a fully-connected neuron in the first hidden layer.) Then,
by definition of INAL, if $\operatorname{INAL}(f_{n},\operatorname{NN}_{n})$
is negligible, then also $\operatorname{INAL}(f_{n},\sigma)$ is negligible.
Accordingly, by Theorem 1, an extension of $(f_{n})$ is not weakly learnable.

While we do not have a proof, we suspect that a similar property might hold
also for some other architectures and initializations.

Note that we obtain hardness only for an extension of $f_{n}$, rather than for
the original function. Interestingly, in some settings GD can learn the
function, while the $2n$-extension of the same function is hard to learn333
For example, for the Boolean parity function $M_{n}(x)=\prod_{i=1}^{n}x_{i}$
with both the input distribution and the weight initialization iid uniform in
$\\{\pm 1\\}$ and cosine activation [BA21].. However, we are not sure if such
examples can be constructed for the continuous Gaussian initialization that we
consider.

##  3 Formal Results

In this section, we write precise statements of our theorems. For this, we
need a couple of more definitions.

######  Definition 6 (Cross-Predictability).

Let $P_{\mathcal{F}}$ be a distribution over functions from $\mathbb{R}^{n}$
to $\mathbb{R}$ and $P_{\mathcal{X}}$ a distribution over $\mathbb{R}^{n}$.
Then,

$\displaystyle\operatorname{CP}(P_{\mathcal{F}},P_{\mathcal{X}})=\mathbb{E}_{F,F^{\prime}\sim
P_{\mathcal{F}}}[\mathbb{E}_{X\sim
P_{\mathcal{X}}}[F(X)F^{\prime}(X)]^{2}]\;.$ (7)

######  Definition 7 (Orbit).

For $f:\mathbb{R}^{n}\to\mathbb{R}$ and a permutation $\pi\in S_{n}$, we let
$(f\circ\pi)(x)=f(x_{\pi(1)},\ldots,x_{\pi(n)})$. Then, we define the _orbit_
of $f$ as

$\displaystyle\operatorname{orb}(f):=\\{f\circ\pi:\pi\in S_{n}\\}\;.$ (8)

Let us now give the full statement of our main theorem.

######  Theorem 2.

Let $(f_{n})$ be a sequence of Boolean functions with $f_{n}:\\{\pm
1\\}^{n}\to\\{\pm 1\\}$ and $x\sim\mathcal{U}^{n}$ and let $\sigma$ be an
expressive activation.

If $\operatorname{INAL}(f_{n},\sigma)$ is negligible, then, for every
$\epsilon>0$, the cross predictability
$\operatorname{CP}(\operatorname{orb}(\overline{f_{n}}),\mathcal{U}^{N})$ is
negligible, where $N=n^{1+\epsilon}$ and
$\operatorname{orb}(\overline{f_{n}})$ denotes (uniform distribution on) the
orbit of the $N$-extension of $f_{n}$.

More precisely, if $\operatorname{INAL}(f_{n},\sigma)=O(n^{-c})$, then
$\operatorname{CP}(\operatorname{orb}(\overline{f_{n}}),\mathcal{U}^{N})=O(n^{-\frac{\epsilon}{1+\epsilon}(c-1)})$.

Applying [AS20b][Theorem 3] to Theorem 2 implies the following corollary. We
refer to Appendix E for additional clarifications on the notion of a fully
connected neural net.

######  Corollary 1.

Let $f_{n}$ and $\sigma$ be as in Theorem 2 with negligible
$\operatorname{INAL}(f_{n},\sigma)$ and let $\epsilon>0$ with
$N=n^{1+\epsilon}$ and $\overline{f_{n}}$ denote the $N$-extension of $f_{n}$.

Let $\operatorname{NN}=(\operatorname{NN}_{n})$ be any sequence of fully
connected neural nets of polynomial size. Then, for any iid initializaton, and
any polynomial bounds on the learning rate, learning time $T=(T_{n})$, noise
level and overflow range, the noisy GD algorithm after $T$ steps of training
outputs a neural net $\operatorname{NN}^{(T)}$ such that the correlation

$\displaystyle
g(n):=\big{|}\mathbb{E}_{\operatorname{NN}^{(T)}}\langle\operatorname{NN}^{(T)},\overline{f_{n}}\rangle\big{|}$
(9)

is negligible.

More precisely, if $\operatorname{INAL}(f_{n},\sigma)=O(n^{-c})$, then for a
noisy GD run for $T$ steps on a fully connected neural network with $E$ edges,
with learning rate $\gamma$, overflow range $A$ and noise level $\tau$ it
holds that

$\displaystyle g(n)=O\left(\frac{\gamma T\sqrt{E}A}{\tau}\cdot
n^{-\frac{\epsilon}{4(1+\epsilon)}(c-1)}\right)\;.$ (10)

######  Remark 4.

In the result above, the neural net can have any feed-forward architecture
with layers of fully-connected neurons and any activation such that the
gradients are almost surely well-defined. The initialization can be iid from
any distribution (which can depend on $n$). We remark that the result of
Corollary 1 can be strengthen to apply to any initialization such that the
distribution of the weights in the first layer is invariant under permutations
of input neurons. We refer to Appendix E for more details.

The algorithm considered is noisy gradient descent444In fact, it can be SGD
with batch size $m$ for large enough $m$. using any differentiable loss
function, meaning that at every step an iid $\mathcal{N}(0,\tau^{2})$ noise
vector is added to all components of the gradient, where $\tau$ is called the
_noise level_. Furthermore, every component of the gradient during the
execution of the algorithm whose evaluation exceeds the _overflow range_ $A$
in absolute value is clipped to $A$ or $-A$, respectively. This covers in
particular the bounded ’precision model‘ of [AKM+21].

For the purposes of function $g(n)$, it is assumed that the neural network
outputs a guess in $\\{\pm 1\\}$ using any form of thresholding (eg., the sign
function) on the value of the output neuron. See [AS20b][Section 2.3.1].

##  4 Proof of Main Theorem

In this section we sketch the proof of Theorem 2. We first state basic
definitions from Boolean function analysis, then we give a short outline of
the proof, and then we state main propositions used in the proof. Finally, we
show how the propositions are combined to prove Theorem 2 and Corollary 1.
Further proofs and details are in the appendices.

We introduce some notions of Boolean analysis, mainly taken from Chapters 1,2
of [O’D14]. For every $f:\\{\pm 1\\}^{n}\to\mathbb{R}$ we denote its Fourier
expansion as

$\displaystyle f(x)=\sum_{S\subseteq[n]}\hat{f}(S)M_{S}(x),$ (11)

where $M_{S}(x)=\prod_{i\in S}x_{i}$ are the standard Fourier basis elements
and $\hat{f}(S)$ are the Fourier coefficients of $f$, defined as
$\hat{f}(S)=\langle f,M_{S}\rangle$. We denote by

$\displaystyle W^{k}(f)$ $\displaystyle=\sum_{S:|S|=k}\hat{f}(S)^{2}$ (12)
$\displaystyle W^{\leq k}(f)$ $\displaystyle=\sum_{S:|S|\leq
k}\hat{f}(S)^{2}\;,$ (13)

the total weight of the Fourier coefficients of $f$ at degree $k$
(respectively up to degree $k$).

######  Definition 8 (High-Degree).

We say that a family of functions $f_{n}:\\{\pm 1\\}^{n}\to\mathbb{R}$ is
’’high-degree‘‘ if for any fixed $k$, $W^{\leq k}(f_{n})$ is negligible.

##### Proof Outline of Theorem 2.

  1. 1.

We initially restrict our attention to the basis Fourier elements, i.e. the
monomials $M_{S}(x):=\prod_{i\in S}x_{i}$ for $S\in[n]$. We consider the
single-neuron alignments $\operatorname{INAL}(M_{S},\sigma)$ for expressive
activations. We prove that these INALs are noticeable for constant degree
monomials (Proposition 1).

  2. 2.

For a general $f:\\{\pm 1\\}^{n}\to\mathbb{R}$ we show that the initial
alignment between $f$ and a single-neuron architecture can be computed from
its Fourier expansion (Proposition 2). As a consequence, for any expressive
$\sigma$, if $\operatorname{INAL}(f,\sigma)$ is negligible, then $f$ is high-
degree (Corollary 2).

  3. 3.

We construct the extension of $f$ and take its orbit
$\operatorname{orb}(\overline{f})$. Since the extension has a sparse structure
of its Fourier coefficients, that guarantees that the cross-predictability of
$\operatorname{orb}(\overline{f})$ is negligible (Proposition 3).

  4. 4.

In order to prove Corollary 1, we invoke the lower bound of [AS20b] (Theorem
3) applied to the class $\operatorname{orb}(\overline{f})$ .

A crucial property of the expressive activations is that they correlate with
constant-degree monomials. To emphasize this, we introduce another definition.

######  Definition 9.

An activation $\sigma$ is _correlating_ if for every $k$, the sequence
$\operatorname{INAL}(M_{k},\sigma)$ is noticeable, where we think of
$M_{k}(x)=\prod_{i=1}^{k}x_{i}$ as a sequence of Boolean functions for every
input dimension $n\geq k$.

Furthermore, if there exists $c$ such that for every $k$ it holds
$\operatorname{INAL}(M_{k},\sigma)=\Omega(n^{-(k+c)})$, then we say that
$\sigma$ is _$c$ -strongly correlating_.

######  Proposition 1.

If $\sigma$ is expressive (according to Definition 4), then it is 1-strongly
correlating.

The proof of Proposition 1 is our main technical contribution. Since the
magnitude of the correlations is quite small (in general, of the order
$n^{-k}$ for monomials of degree $k$), careful calculations are required to
establish our lower bounds.

In fact, we conjecture that any polynomially bounded function that is not a
polynomial (almost everywhere) is correlating.

Then, we show that $\operatorname{INAL}(f,\sigma)$ decomposes into monomial
INALs according to its Fourier coefficients:

######  Proposition 2.

For any $f:\\{\pm 1\\}^{n}\to\mathbb{R}$ and any activation $\sigma$,

$\displaystyle\operatorname{INAL}(f,\sigma):=\sum_{T\in[n]}\hat{f}(T)^{2}\operatorname{INAL}(M_{T},\sigma)\;.$
(14)

As a corollary, functions with negligible INAL on correlating activations are
high-degree:

######  Corollary 2.

Let $\sigma$ be an activation with
$\operatorname{INAL}(M_{k^{\prime}},\sigma)=\Omega(n^{-k_{0}})$ for
$k^{\prime}=0,1,\ldots,k$. Then, $W^{\leq
k}(f_{n})\leq\operatorname{INAL}(f_{n},\sigma)O(n^{k_{0}})$.

In particular, if $\sigma$ is correlating and
$\operatorname{INAL}(f_{n},\sigma)$ is negligible, then $(f_{n})$ is high
degree.

Finally, the cross-predictability of $\operatorname{orb}(\overline{f_{n}})$ is
negligible for high degree functions.

######  Proposition 3.

Let $\epsilon>0$ and $(f_{n})$ a family of Boolean functions. Let
$(\overline{f_{n}})$ denote the family of $N$-extensions of $f_{n}$ for
$N=n^{1+\epsilon}$, and consider the uniform distribution on its orbit.

If $(f_{n})$ is high degree, then
$\operatorname{CP}(\operatorname{orb}(\overline{f_{n}}),\mathcal{U}^{N})$ is
negligible. Furthermore, if for some universal $c$ and every fixed $k$ it
holds $W^{\leq k}(f_{n})=O(n^{k-c})$, then
$\operatorname{CP}(\operatorname{orb}(\overline{f_{n}}),\mathcal{U}^{N})=O(n^{-\frac{\epsilon}{1+\epsilon}\cdot
c})$.

######  Theorem 3 ([AS20b], informal).

If the cross-predictability of a class of functions is negligible, then noisy
GD cannot learn it in poly-time.

We provide here an outline of the proof of Proposition 1, and refer to
Appendix A for a detailed proof. We further prove Proposition 3 and Theorem 2.
The proofs of the remaining results are in appendices.

##### Proof of Proposition 1 (outline).

The main goal of the proof is to estimate the dominant term (as $n$ approaches
infinity) of $\operatorname{INAL}(M_{k},\sigma)$, and show that it is indeed
noticeable, for any fixed $k$. We initially use Jensen inequality to lower
bound the INAL with the following

$\displaystyle\operatorname{INAL}(M_{k},\sigma)\geq\mathbb{E}\left[\mathbb{E}_{|\theta|,x}\left[M_{k}(x)\sigma({w}^{T}x+b)\mid\operatorname{sgn}(\theta)\right]^{2}\right],$
(15)

where for brevity we denoted $\theta=(w,b)$, $|\theta|$ and
$\operatorname{sgn}(\theta)$ are $(n+1)$-dimensional vectors such that
$|\theta|_{i}=|\theta_{i}|$ and
$\operatorname{sgn}(\theta)_{i}=\operatorname{sgn}(\theta_{i})$, for all
$i\leq n+1$. By denoting $|w|_{>k},x_{>k}$ the coordinates of $|w|$ and $x$
respectively that do not appear in $M_{k}$, and by
$G:=\sum_{i=1}^{k}w_{i}x_{i}+b$ we observe that

$\displaystyle\mathbb{E}_{|w|_{>k},x_{>k}}[\sigma(w^{T}x+b)]=\mathbb{E}_{Y\sim\mathcal{N}(0,1-\frac{k}{n})}\left[\sigma(G+Y)\right],$
(16)

since $\sum_{i=k+1}^{n}w_{i}x_{i}$ is indeed distributed as
$\mathcal{N}(0,1-\frac{k}{n})$. We call the RHS the ’’$n$-Gaussian smoothing‘‘
of $\sigma$ and we denote it by
$\Sigma_{n}(z):=\mathbb{E}_{Y\sim\mathcal{N}(0,1-\frac{k}{n})}\left[\sigma(z+Y)\right]$.
We will compare it to the ’’ideal‘‘ Gaussian smoothing denoted by
$\Sigma(z):=\mathbb{E}_{Y\sim\mathcal{N}(0,1)}[\sigma(z+Y)]$.

For polynomially bounded $\sigma$, we can prove that $\Sigma_{n}$ has some
nice properties (see Lemma 1), specifically it is $C^{\infty}$ and
polynomially bounded and it uniformly converges to $\Sigma$ as $n\to\infty$.
These properties crucially allow to write $\Sigma_{n}$ in terms of its Taylor
expansion around $0$, and bound the coefficients of the series for large $n$.
In fact, we show that there exists a constant $P>k$, such that if we split the
Taylor series of $\Sigma_{n}$ at $P$ as

$\displaystyle\Sigma_{n}(G)=\sum_{\nu=0}^{P}a_{\nu,n}G^{\nu}+R_{P,n}(G),$ (17)

(where $a_{\nu,n}$ are the Taylor coefficients and $R_{P,n}$ is the remainder
in Lagrange form), and take the expectation over $|\theta|_{\leq k}$ as:

$\displaystyle\mathbb{E}_{|\theta|_{\leq k},x_{\leq
k}}\left[M_{k}(x)\Sigma_{n}(G)\right]$
$\displaystyle=\sum_{\nu=0}^{P}a_{\nu,n}\mathbb{E}_{|\theta|_{\leq k},x_{\leq
k}}\left[M_{k}(x)G^{\nu}\right]+\mathbb{E}_{|\theta|_{\leq k},x_{\leq
k}}\left[R_{P,n}(G)\right]$ (18) $\displaystyle=:A+B,$ (19)

then $A$ is $\Omega(n^{-P/2})$ (Proposition 4), and $B$ is $O(n^{-P/2-1/2})$
(Proposition 5), uniformly for all values of $\operatorname{sgn}(\theta)$. For
$A$ we use the observation that $\mathbb{E}_{|\theta|_{\leq k},x_{\leq
k}}\left[M_{k}(x)G^{\nu}\right]=0$ for all $\nu<k$ (Lemma 3), and the fact
that $|a_{P,n}|>0$ for $n$ large enough (due to hypothesis b in Definition 4
and the continuity of $\Sigma_{n}$ in the limit of $n\to\infty$, given by
Lemma 1). For $B$, we combine the concentration of Gaussian moments and the
polynomial boundness of all derivatives of $\Sigma_{n}$.

Taking the square of (19) and going back to (15), one can immediately conclude
that $\operatorname{INAL}(M_{k},\sigma)$ is indeed noticeable.

###  4.1 Proof of Proposition 3

Let $f=f_{n}$ and let $\hat{f}$ be the Fourier coefficients of the original
function $f$, and let $\hat{h}$ be the coefficients of the augmented function
$\bar{f}$. Recall that $\bar{f}:\\{\pm 1\\}^{N}\to\\{\pm 1\\}$ is such that
$\bar{f}(x_{1},...,x_{n},x_{n+1},...,x_{N})=f(x_{1},...,x_{n})$. Thus, the
Fourier coefficients of $\bar{f}$ are

$\displaystyle\hat{h}(T)$ $\displaystyle=\begin{cases}\hat{f}(T)&\text{ if
}T\subseteq[n],\\\ 0&\text{ otherwise}.\end{cases}$ (20)

Let us proceed to bounding the cross-predictability. Below we denote by $\pi$
a random permutation of $N$ elements:

$\displaystyle\operatorname{CP}(\operatorname{orb}(\overline{f_{n}}),\mathcal{U}^{N})$
$\displaystyle=\mathbb{E}_{\pi}\left[\mathbb{E}_{x}\left[\bar{f}(x)\bar{f}(\pi(x))\right]^{2}\right]$
(21)
$\displaystyle=\mathbb{E}_{\pi}\left[\left(\sum_{T\subseteq[N]}\hat{h}(T)\hat{h}(\pi(T))\right)^{2}\right]$
(22)
$\displaystyle=\mathbb{E}_{\pi}\left[\left(\sum_{T\subseteq[n]}\hat{f}(T)\hat{h}(\pi(T))\cdot\mathds{1}\left(\pi(T)\subseteq[n]\right)\right)^{2}\right]$
(23)
$\displaystyle\overset{C.S}{\leq}\mathbb{E}_{\pi}\left[\left(\sum_{S\subseteq[n]}\hat{h}(\pi(S))^{2}\right)\right.\cdot\left.\left(\sum_{T\subseteq[n]}\hat{f}(T)^{2}\mathds{1}\left(\pi(T)\subseteq[n]\right)\right)\right]$
(24)
$\displaystyle\leq\sum_{T\subseteq[n]}\hat{f}(T)^{2}\cdot\mathbb{P}_{\pi}\left(\pi(T)\subseteq[n]\right).$
(25)

Now, for any $k$ we have

$\displaystyle\operatorname{CP}(\operatorname{orb}(\overline{f_{n}}),\mathcal{U}^{N})$
$\displaystyle\leq\sum_{T:|T|<k}\hat{f}(T)^{2}\cdot\mathbb{P}_{\pi}\left(\pi(T)\subseteq[n]\right)+\sum_{T:|T|\geq
k}\hat{f}(T)^{2}\cdot\mathbb{P}_{\pi}\left(\pi(T)\subseteq[n]\right)$ (26)
$\displaystyle\leq
W^{<k}(f)+\mathbb{P}_{\pi}\left(\pi(T)\subseteq[n]\mid|T|=k\right)\;,$ (27)

where the second term in (27) is further bounded by (recall that
$N=n^{1+\epsilon}$):

$\displaystyle\mathbb{P}_{\pi}\left(\pi(T)\subseteq[n]\mid|T|=k\right)$
$\displaystyle=\frac{\binom{n}{k}}{\binom{N}{k}}$ (28)
$\displaystyle\leq\frac{\left(\frac{ne}{k}\right)^{k}}{\left(\frac{N}{k}\right)^{k}}$
(29) $\displaystyle=e^{k}\frac{n^{k}}{N^{k}}=e^{k}n^{-\epsilon\cdot k}.$ (30)

Accordingly, for any $k\in\mathbb{N}_{>0}$ it holds that

$\displaystyle\operatorname{CP}(\operatorname{orb}(\overline{f_{n}}),\mathcal{U}^{N})\leq
W^{<k}(f)+e^{k}n^{-\epsilon k}\;.$ (31)

Now, if $(f_{n})$ is a high degree sequence of Boolean functions, then
$W^{<k}(f)$ is negligible for every $k$, and therefore the cross-
predictability in (28) is $O(n^{-k})$ for every $k$, that is the cross-
predictability is negligible as we claimed.

On the other hand, if for some $c$ and every $k$ it holds that $W^{\leq
k}(f_{n})=O(n^{k-c})$, then we can choose $k_{0}:=\frac{c}{1+\epsilon}$ and
apply (31) to get
$\operatorname{CP}(\operatorname{orb}(\overline{f_{n}}),\mathcal{U}^{N})=O(n^{-\frac{\epsilon}{1+\epsilon}\cdot
c})$.

###  4.2 Proof of Theorem 2

Let $\sigma$ be an expressive activation and let $(f_{n})$ be a sequence of
Boolean functions with negligible $\operatorname{INAL}(f_{n},\sigma)$. By
Proposition 1, $\sigma$ is correlating, and by Corollary 2 $(f_{n})$ is high-
degree. Therefore, by Proposition 3, the cross-predictability
$\operatorname{CP}(\operatorname{orb}(\overline{f_{n}}),\mathcal{U}^{N})$ is
negligible.

For the more precise statement, let $(f_{n})$ be a sequence of Boolean
functions with $\operatorname{INAL}(f_{n},\sigma)=O(n^{-c})$. By Proposition
1, $\sigma$ is 1-strongly correlating. That means that for every $k$ we have
$\operatorname{INAL}(M_{k},\sigma)=\Omega(n^{-(k+1)})$. By Corollary 2, for
every $k$ it holds $W^{\leq k}(f_{n})=O(n^{k+1-c})$. Finally, applying
Proposition 3, we have that
$\operatorname{CP}(\operatorname{orb}(\overline{f_{n}}),\mathcal{U}^{N})=O(n^{-\frac{\epsilon}{1+\epsilon}(c-1)})$.

Figure 1: Comparison of INAL and generalization accuracy for three Boolean
functions. On the left, we estimate the INAL between each target function and
a 2-layers ReLU fully connected neural network with normalized gaussian
initialization. On the right, we train the network to learn each target
function with SGD with batch 1000 for 100 epochs. We observe that low INAL is
bad news. Figure 2: Comparison of INAL and generalization accuracy for binary
classification in the CIFAR dataset. On the left, we estimate the INAL between
the neural network and the target function associated to each task. On the
right we train a CNN with 1 VGG block with SGD with batch size 64 for 100
epochs. We observe that a significant difference in the INAL corresponds to a
significant difference in the generalization accuracy achieved.

##  5 Experiments

In this section we present a few experiments to show how the INAL can be
estimated in practice. Our theoretical results connect the performance of GD
to the Fourier spectrum of the target function. However, in applications we
are usually given a dataset with data points and labels, rather than an
explicit target function, and it may not be trivial to infer the Fourier
properties of the function associated to the data. Conveniently, the INAL can
be estimated with sufficient datapoints and labels, and do not need an
explicit target.

##### Experiments on Boolean functions.

In our first experiment, we consider three Boolean functions, namely the
majority-vote over the whole input space (${\rm
Maj}_{n}(x):=\operatorname{sgn}(\sum_{i=1}^{n}x_{i})$), a $9$-staircase (${\rm
S_{9}(x):=\operatorname{sgn}(x_{1}+x_{1}x_{2}+x_{1}x_{2}x_{3}+...+x_{1}x_{2}x_{3}...x_{9})}$
and a $3$-parity ($M_{3}(x)=\prod_{i=1}^{3}x_{i}$), on an input space of
dimension $100$. We take a 2-layer fully connected neural network with ReLU
activations and normalised Gaussian iid initialization (according to the
setting of our theoretical results), and we train it with SGD with batch-size
1000 for 100 epochs, to learn each of the three functions. On the other hand,
we estimate the INAL between each of the three targets and the neural network,
through Monte-Carlo. Our observations confirm our theoretical claim, i.e. that
low INAL is bad news. In fact, for the 3-parity and the 9-staircase, that have
very low INAL ($\sim$1/20 of the majority-vote case), GD does not achieve good
generalization accuracy after training (Figure 1).

##### Experiments on real data.

Given a dataset $D=(x_{m},y_{m})_{m\in[M]}$, where $x_{m}\in\mathbb{R}^{n}$,
and $y_{m}\in\mathbb{R}$, and given a randomly initialized neural network
$\operatorname{NN}_{\Theta^{0}}$ with $\Theta^{0}$ drawn from some
distribution, we can estimate the initial alignment between the network and
the target function associated to the dataset as

$\displaystyle\max_{v\in
V_{NN}}\mathbb{E}_{\Theta^{0}}\left[\left(\frac{1}{M}\sum_{m=1}^{M}y_{m}\cdot\operatorname{NN}_{\Theta^{0}}^{(v)}(x_{m})\right)^{2}\right],$
(32)

where the outer expectation can be performed through Monte-Carlo
approximation.

We ran experiments on the CIFAR dataset. We split the dataset into 3 different
pairs of classes, corresponding to 3 different binary classification tasks
(specifically cat/dog, bird/deer, frog/truck). We take a CNN with 1 VGG block
and $\operatorname{ReLU}$ activation, and for each task, we train the network
with SGD with batch-size 64, and we estimate the INAL according to (32). We
notice that also in this setting (not covered by our theoretical results), the
INAL and the generalization accuracy present some correlation, and a
significant difference in the INAL corresponds to a significant difference in
the accuracy achieved after training. This may give some motivation to study
the INAL beyond the fully connected setting.

##  6 Conclusion and Future Work

There are several directions that can follow from this work. The most relevant
would be to extend the result beyond fully connected architectures. As
mentioned before, we suspect that our result can be generalized to all
architectures that contain a fully connected layer anywhere in the network.
Another direction would be to extend the present work to other continuous
distributions of intitial weights (beyond gaussian). As a matter of fact, in
the setting of iid gaussian inputs (instead of Boolean inputs), our proof
technique extends to all weight initialization distributions with zero mean
and variance $O(n^{-1})$. However, in the case of Boolean inputs that we
consider in this paper, this may not be a trivial extension. Another extension
on which we do not touch here are non-uniform input distributions.

##### Acknowledgements

We thank Peter Bartlett for a helpful discussion.

## References

  * [AKM+21] Emmanuel Abbe, Pritish Kamath, Eran Malach, Colin Sandon, and Nathan Srebro.  On the power of differentiable learning versus PAC and SQ learning.  In Advances in Neural Information Processing Systems, volume 34, 2021.
  * [AS20a] Emmanuel Abbe and Colin Sandon.  On the universality of deep learning.  In Advances in Neural Information Processing Systems, volume 33, pages 20061–20072, 2020.
  * [AS20b] Emmanuel Abbe and Colin Sandon.  Poly-time universality and limitations of deep learning.  arXiv:2001.02992, 2020.
  * [AZL20] Zeyuan Allen-Zhu and Yuanzhi Li.  Backward feature correction: How deep learning performs deep learning.  arXiv:2001.04413, 2020.
  * [BA21] Enric Boix-Adsera.  Personal communication, 2021.
  * [BFJ+94] Avrim Blum, Merrick Furst, Jeffrey Jackson, Michael Kearns, Yishay Mansour, and Steven Rudich.  Weakly learning DNF and characterizing statistical query learning using Fourier analysis.  In Symposium on Theory of Computing (STOC), pages 253–262, 1994\.
  * [Kea98] Michael Kearns.  Efficient noise-tolerant learning from statistical queries.  Journal of the ACM, 45(6):983–1006, 1998.
  * [LLM+18] Rosanne Liu, Joel Lehman, Piero Molino, Felipe Petroski Such, Eric Frank, Alex Sergeev, and Jason Yosinski.  An intriguing failing of convolutional neural networks and the CoordConv solution.  In NeurIPS, pages 9628–9639, 2018.
  * [MKAS21] Eran Malach, Pritish Kamath, Emmanuel Abbe, and Nathan Srebro.  Quantifying the benefit of using differentiable learning over tangent kernels.  In Marina Meila and Tong Zhang, editors, Proceedings of the 38th International Conference on Machine Learning, volume 139 of Proceedings of Machine Learning Research, pages 7379–7389. PMLR, 18–24 Jul 2021.
  * [MSS19] Eran Malach and Shai Shalev-Shwartz.  Is deeper better only when shallow is good?  In Advances in Neural Information Processing Systems, volume 32, pages 6429–6438, 2019.
  * [O’D14] Ryan O‘Donnell.  Analysis of Boolean Functions.  Cambridge University Press, 2014.
  * [SSBD14] Shai Shalev-Shwartz and Shai Ben-David.  Understanding Machine Learning - From Theory to Algorithms. Cambridge University Press, 2014.
  * [SSM21] Shai Shalev-Shwartz and Eran Malach.  Computational separation between convolutional and fully-connected networks.  In International Conference on Learning Representations (ICLR), 2021\.
  * [TAY21] Yan Shuo Tan, Abhineet Agarwal, and Bin Yu.  A cautionary tale on fitting decision trees to data from additive models: generalization lower bounds, 2021.
  * [Win12] Andreas Winkelbauer.  Moments and absolute moments of the normal distribution.  ArXiv, abs/1209.4340, 2012.

##  Appendix A Proof of Proposition 1

For an activation $\sigma:\mathbb{R}\to\mathbb{R}$, we denote its $v$-Gaussian
smoothing as

$\displaystyle\Sigma_{v}(t):=\mathbb{E}_{Y\sim\mathcal{N}(0,v)}[\sigma(Y+t)].$
(33)

We also write $\Sigma:=\Sigma_{1}$ for brevity. As mentioned, we will be
working with functions that are _polynomially bounded_ , ie., such that there
exists a polynomial $P$ with $|\sigma(x)|<P(x)$ holding for all
$x\in\mathbb{R}$. We will use the fact that such polynomial can be assumed
wlog to be of the form $|\sigma(x)|<Cx^{\ell}+C$ for some $C>0$ and
$\ell\in\mathbb{N}_{\geq 0}$ (since any polynomial can be upper bounded by a
polynomial of such form). Note that if $\sigma$ is a measurable, polynomially
bounded function, then $\Sigma_{v}$ is well defined for every $v>0$.

We now state the intermediate step in the proof of Proposition 1:

######  Lemma 1 (Conditions on $\Sigma$ and $\Sigma_{v}$).

If $\sigma$ is a measurable, polynomially bounded function, then it satisfies
the following conditions:

  1. i)

$\Sigma_{v}\in C^{\infty}(\mathbb{R})$ for every $v>0$;

  2. ii)

For every $k\in\mathbb{N}_{\geq 0}$ and $v>0$,
$\Sigma_{v}^{(k)}(t):=\frac{\partial^{k}}{\partial t^{k}}\Sigma_{v}(t)$ is
polynomially bounded. Furthermore, this bound is uniform, that is,
$|\Sigma_{v}^{(k)}(t)|<Ct^{\ell}+C$ holds for every $t\in\mathbb{R}$ and every
$1/2\leq v\leq 1$, for some $C,\ell$ that do not depend on $v$.

  3. iii)

For all $k\in\mathbb{N}_{\geq 0}$, it holds
$|\Sigma^{(k)}_{1-\epsilon}(0)-\Sigma^{(k)}(0)|=O(\epsilon)$.

Lemma 1 is then used in the proof of

######  Lemma 2.

Let $\sigma$ be expressive (according to Definition 4). Then, for every $k\geq
0$ and $P\geq k$ such that $\Sigma^{(P)}(0)\neq 0$, it holds that
$\operatorname{INAL}(M_{k},\sigma)=\Omega(n^{-P})$.

In particular, from Lemma 2 it follows that if $\sigma$ is expressive, then it
is correlating. Furthermore, since by condition b) in Definition 4 for every
$k$ we have $\Sigma^{(k)}(0)\neq 0$ or $\Sigma^{(k+1)}(0)\neq 0$, by Lemma 2
it holds $\operatorname{INAL}(M_{k},\sigma)=\Omega(n^{-(k+1)})$ and $\sigma$
is $1$-strongly correlating.

In the following subsections we prove Lemma 1 and Lemma 2.

###  A.1 Proof of Lemma 1

In the following let $\phi_{v}$ denote the density function of
$\mathcal{N}(0,v)$, ie.,
$\phi_{v}(t)=\frac{1}{\sqrt{2v\pi}}\exp\left(-\frac{t^{2}}{2v}\right)$. Note
the relation to the standard Gaussian density $\phi=\phi_{1}$ where
$\phi_{v}(t)=\frac{1}{\sqrt{v}}\phi(t/\sqrt{v})$.

We recall some useful facts about the derivatives of $\phi_{v}$. First, it is
well known that for $\phi$ it holds $\phi^{(k)}(t)=P_{k}(t)\phi(t)$ for some
polynomial $P_{k}$ of degree $k$. This formula extends to $\phi_{v}$ according
to

$\displaystyle\phi_{v}^{(k)}(t)$
$\displaystyle=\frac{1}{\sqrt{v}}\frac{\mathrm{d}^{k}}{\mathrm{d}t^{k}}\phi(t/\sqrt{v})=v^{-k/2-1/2}\phi^{(k)}(t/\sqrt{v})=v^{-k/2-1/2}P_{k}(t/\sqrt{v})\phi(t/\sqrt{v})$
(34) $\displaystyle=v^{-k/2}P_{k}(t/\sqrt{v})\phi_{v}(t)\;.$ (35)

i) Let us write $\phi_{v}(t)=(\phi_{v/2}\ast\phi_{v/2})(t)$ where $\ast$
denotes the convolution in $\mathbb{R}$, i.e. $(g\ast
h)(y)=\int_{\mathbb{R}}g(x)h(y-x)dx$. Thus,

$\displaystyle\Sigma_{v}=\sigma\ast\phi_{v}=(\sigma\ast\phi_{v/2})\ast\phi_{v/2}.$
(36)

Now, $\sigma\ast\phi_{v/2}$ is in $L_{1}(\mathbb{R})$, since $\sigma$ is
measurable and polynomially bounded. Furthermore, $\phi_{v/2}$ is in
$L_{1}(\mathbb{R})$ and $C^{\infty}(\mathbb{R})$. Therefore, by formulas for
derivatives of convolution, $\Sigma_{v}\in C^{\infty}(\mathbb{R})$.

ii) Let us start with the claim that $\Sigma_{v}^{(k)}$ is polynomially
bounded for every $v$ and $k$. For that, we recall some facts. First, it is
easy to establish by direct computation that if $\sigma$ is polynomially
bounded, then $\Sigma_{v}=\sigma\ast\phi_{v}$ is also polynomially bounded.
Furthermore, if $P$ is any polynomial, then also $\sigma\ast(P\phi_{v})$ is
polynomially bounded (this can be seen, eg., by observing that for every $P$
and every $v^{\prime}>v$ there exists $C$ such that $|P\phi_{v}|\leq
C\phi_{v^{\prime}}$).

Accordingly, using (34) and (36) we have that

$\displaystyle\Sigma_{v}^{(k)}=(\sigma\ast\phi_{v/2})\ast\phi_{v/2}^{(k)}=(\sigma\ast\phi_{v/2})\ast(P_{k,v}\phi_{v/2})$
(37)

is polynomially bounded.

Let us move to the second claim with uniform bound. For that let $k\geq 0$ and
$1/2\leq v\leq 1$. Let $v^{\prime}:=v-1/4$ and note that $1/4\leq
v^{\prime}\leq 3/4$. Then, we have the sequence of bounds on functions which
hold pointwise:

$\displaystyle|\Sigma_{v}^{(k)}|$
$\displaystyle=\left|(\sigma\ast\phi_{1/4})\ast\phi_{v^{\prime}}^{(k)}\right|\leq
C_{1}\left(|\sigma\ast\phi_{1/4}|\ast|P_{k}(x/\sqrt{v^{\prime}})|\phi_{v^{\prime}}\right)$
(38) $\displaystyle\leq
C_{1}\left(|\sigma\ast\phi_{1/4}|\ast(C_{2}+C_{2}(x/\sqrt{v})^{2\ell})\phi_{v^{\prime}}\right)$
(39) $\displaystyle\leq
C_{3}\left(|\sigma\ast\phi_{1/4}|\ast(C_{4}+C_{4}x^{2\ell})\phi\right)\;,$
(40)

which is now bounded by a polynomial which does not depend on $v$.

iii) Recall,

$\displaystyle\Sigma_{v}^{(k)}(0)=\int_{-\infty}^{\infty}(\phi_{v/2}\ast\sigma)(x)\cdot\frac{\partial^{k}}{\partial
t^{k}}\phi_{v/2}(x+t)\Big{|}_{t=0}dx,$ (41)

where we denoted by $\phi_{v/2}^{(k)}$ the $k$-th derivative of $\phi_{v/2}$.
Firstly, note that

$\displaystyle\frac{\partial^{k}}{\partial
t^{k}}\phi_{v/2}(x+t)\Big{|}_{t=0}=\frac{\partial^{k}}{\partial(x+t)^{k}}\phi_{v/2}(x+t)\Big{|}_{t=0}=\phi_{v/2}^{(k)}(x).$
(42)

Let us give a formula for the k-th derivative of the Gaussian density:

$\displaystyle\phi_{v}^{(k)}(x)=\phi_{v}(x)\cdot(-1)^{k}v^{-2k}\cdot\sum_{l=0}^{k}D_{l,k}\left(\frac{x}{\sqrt{v}}\right)^{k-l},$
(43)

where $D_{l,k}$ is a constant that does not depend on $v$, specifically

$\displaystyle D_{l,k}:=B_{(2k+l)\frac{1-(-1)^{l}}{2}}\cdot
2^{\frac{l}{2}}\cdot\frac{\Gamma(\frac{l+1}{2})}{\Gamma(\frac{1}{2})}\cdot\cos\left(\frac{l\pi}{2}\right)$
(44)

where $\Gamma(.)$ denotes the Gamma function and $B_{n}$ are the Bernoulli
numbers. The exact values of the $D_{l,k}$ will not be relevant for this
proof. Thus,

$\displaystyle\Sigma_{v}^{(k)}(0):=\int_{-\infty}^{\infty}(\phi_{v/2}\ast\sigma)(x)P_{v/2,k}(x)\phi_{v/2}(x)dx,$
(45)

where we denoted
$P_{v/2,k}(x)=(-1)^{k}v^{-2k}\cdot\sum_{l=0}^{k}D_{l,k}\left(\frac{x}{\sqrt{v}}\right)^{k-l}$.
On the other hand,

$\displaystyle\Sigma_{1}^{(k)}(0):=\int_{-\infty}^{\infty}(\phi_{v/2}\ast\sigma)(x)P_{1-v/2,k}(x)\phi_{1-v/2}(x)dx,$
(46)

and

$\displaystyle|\Sigma_{v}^{(k)}(0)-\Sigma_{1}^{(k)}(0)|=\Big{|}\int_{-\infty}^{\infty}(\phi_{v/2}\ast\sigma)(x)\cdot\left(P_{v/2,k}(x)\phi_{v/2}(x)-P_{1-v/2,k}(x)\phi_{1-v/2}(x)\right)\Big{|}.$
(47)

We note that

$\displaystyle P_{1-v/2,k}(x)=$
$\displaystyle\frac{(1-\frac{v}{2})^{-2k}}{(\frac{v}{2})^{-2k}}\left(\frac{v}{2}\right)^{-2k}(-1)^{k}$
(48)
$\displaystyle\cdot\left(\sum_{l=0}^{k}D_{l,k}\left(\frac{x}{\sqrt{v/2}}\right)^{k-l}+D_{l,k}\left[\left(\frac{x}{\sqrt{1-v/2}}\right)^{k-l}-\left(\frac{x}{\sqrt{v/2}}\right)^{k-l}\right]\right)$
(49) $\displaystyle=$
$\displaystyle\frac{(1-\frac{v}{2})^{-2k}}{(\frac{v}{2})^{-2k}}P_{v/2,k}(x)$
(50)
$\displaystyle+\left(1-\frac{v}{2}\right)^{-2k}(-1)^{k}\sum_{l=0}^{k}D_{l,k}\left(\left(\frac{x}{\sqrt{1-v/2}}\right)^{k-l}-\left(\frac{x}{\sqrt{v/2}}\right)^{k-l}\right).$
(51)

Recalling $\epsilon=1-v$, and expanding for such $\epsilon$ we get

$\displaystyle\left(1+\frac{2\epsilon}{1-\epsilon}\right)^{-2k}P_{v/2,k}(x)+(1+\epsilon)^{-2k}\frac{(-1)^{k}}{2^{-2k}}\sum_{l=0}^{k}D_{l,k}x^{k-l}\frac{(1-\epsilon)^{k-l}-(1+\epsilon)^{k-l}}{(1+\epsilon)^{\frac{k-l}{2}}(1-\epsilon)^{\frac{k-l}{2}}}$
(52) $\displaystyle=$
$\displaystyle\left(1-4k\frac{\epsilon}{1-\epsilon}+o(\epsilon)\right)P_{v/2,k}(x)$
(53)
$\displaystyle+(1-2k\epsilon+o(\epsilon))\frac{(-1)^{k}}{2^{-2k}}\sum_{l=0}^{k}D_{l,k}x^{k-l}\frac{-2(k-l)\epsilon+(\epsilon)}{(1+\frac{k-l}{2}\epsilon+o(\epsilon))(1-\frac{k-l}{2}\epsilon+o(\epsilon))}$
(54) $\displaystyle=$
$\displaystyle\left(1-4k\frac{\epsilon}{1-\epsilon}\right)P_{v/2,k}(x)+O(\epsilon)\mathcal{P}_{k}(x),$
(55)

where $\mathcal{P}_{k}(x)$ is a polynomial in $x$ of degree $\leq k$.
Moreover,

$\displaystyle\phi_{1-v/2}(x)$
$\displaystyle=\frac{e^{-\frac{x^{2}}{v}}}{\sqrt{2\pi
v/2}}\cdot\sqrt{\frac{v/2}{1-v/2}}\cdot
e^{-\frac{x^{2}}{2}\left(\frac{1}{1-\frac{v}{2}}-\frac{2}{v}\right)}$ (56)
$\displaystyle=\phi_{v/2}(x)\cdot\left(1-\frac{2\epsilon}{1+\epsilon}\right)^{1/2}\cdot
e^{x^{2}\frac{2\epsilon}{(1+\epsilon)(1-\epsilon)}}$ (57)
$\displaystyle=\phi_{v/2}(x)\cdot\left(1-\frac{\epsilon}{1+\epsilon}+o(\epsilon)\right)\cdot\left(1+x^{2}\frac{2\epsilon}{(1+\epsilon)(1-\epsilon)}+o(\epsilon)x^{4}\right)$
(58) $\displaystyle=\phi_{v/2}(x)\cdot\left(1+(x^{2}-1)O(\epsilon)\right).$
(59)

Plugging these bounds in the previous expression, we get

$\displaystyle|\Sigma_{v}^{(k)}(0)$ $\displaystyle-\Sigma_{1}^{(k)}(0)|$ (60)
$\displaystyle=\Big{|}\int_{-\infty}^{\infty}(\phi_{v/2}\ast\sigma)(x)\cdot\left(P_{v/2,k}(x)\phi_{v/2}(x)-P_{1-v/2,k}(x)\phi_{v/2}(x)\left(1+(x^{2}-1)O(\epsilon)\right)\right)\Big{|}$
(61)
$\displaystyle=\Big{|}\int_{-\infty}^{\infty}(\phi_{v/2}\ast\sigma)(x)\phi_{v/2}(x)\cdot\left(P_{v/2,k}(x)-P_{1-v/2,k}(x)\left(1+(x^{2}-1)O(\epsilon)\right)\right)\Big{|}$
(62)
$\displaystyle=\Big{|}\int_{-\infty}^{\infty}(\phi_{v/2}\ast\sigma)(x)P_{v/2,k}(x)\phi_{v/2}(x)\cdot\left(1-(1-O(\epsilon)+(x^{2}-1)O(\epsilon))+O(\epsilon)\mathcal{P}_{k}(x)\right)\Big{|}$
(63) $\displaystyle=O(\epsilon)\;.$ $\displaystyle\hfill\qed$ (64)

###  A.2 Proof of Lemma 2

Note that we only need to show that
$\operatorname{INAL}(M_{k},\sigma)=\Omega(n^{-P})$ for the first index $P$
such that $P\geq k$ and $\Sigma^{(P)}(0)\neq 0$. By Definition 4, we only need
with two cases $P=k$ and $P=k+1$. From now on, let us consider a fixed pair of
$k$ and $P$.

We denote by $x\in\\{\pm 1\\}^{n}$ the vector of all inputs, by
$w\in\mathbb{R}^{n}$ the vector of all weights and by $b\in\mathbb{R}$ the
bias. Additionally, we denote $\tau_{i}:=\operatorname{sgn}(w_{i})$, and by
$\tau\in\\{\pm 1\\}^{n}$ the vector of all weight signs. Recall that we
consider $w_{i},b\overset{iid}{\sim}\mathcal{N}(0,\frac{1}{n})$ and that for
$g,h:\\{\pm 1\\}^{n}\to\\{\pm 1\\}$ and $\mathcal{U}^{n}$ being the uniform
distribution over the hypercube, we denote $\langle
g,h\rangle=\mathbb{E}_{x\sim\mathcal{U}^{n}}[g(x)h(x)]$. We have

$\displaystyle\operatorname{INAL}(M_{k},\sigma)$
$\displaystyle=\mathbb{E}_{w,b}\left[\langle M_{k},\sigma\rangle^{2}\right]$
(65)
$\displaystyle=\mathbb{E}_{|w|,\tau,|b|,\operatorname{sgn}(b)}\left[\langle
M_{k},\sigma\rangle^{2}\right]$ (66)
$\displaystyle\overset{(C.S.)}{\geq}\mathbb{E}_{\tau,\operatorname{sgn}(b)}\left[\mathbb{E}_{|w|,|b|}\big{[}\langle
M_{k},\sigma\rangle\mid\tau,\operatorname{sgn}(b)\big{]}^{2}\right],$ (67)

where (67) follows by Cauchy-Schwartz inequality. We will prove a lower bound
on the inner expectation $\left(\mathbb{E}_{|w|,|b|}\langle
M_{k},\sigma\rangle\right)^{2}$ which is independent of $\tau$ and
$\operatorname{sgn}(b)$. Accordingly, from now on consider $\tau$ and
$\operatorname{sgn}(b)$ to be fixed at arbitrary values.

Let $T:=\\{1,\ldots,k\\}$ and denote by $x_{T}$ the coordinates of $x$
contained in $T$, and by $x_{\sim T}:=x_{T^{C}}$ the coordinates of $x$ that
are not contained in $T$ and hence do not appear in the monomial $M_{T}$.
Similarly, we denote by $|w|_{T},|w|_{\sim T}$ the coordinates of $|w|$ that
appear (respectively do not appear) in set $T$. We proceed,

$\displaystyle\mathbb{E}_{|w|,|b|}\langle M_{T},\sigma\rangle$
$\displaystyle=\mathbb{E}_{x,|w|,|b|}\left[M_{T}(x)\cdot\sigma\left(\sum_{i\in[n]}w_{i}x_{i}+b\right)\right]$
(68)
$\displaystyle=\mathbb{E}_{|w|_{T},x_{T},|b|}\left[M_{T}(x)\cdot\mathbb{E}_{|w|_{\sim
T},x_{\sim T}}\sigma\left(\sum_{i\in[n]}w_{i}x_{i}+b\right)\right]$ (69)

Observe that $\sum_{i\not\in T}w_{i}x_{i}\sim\mathcal{N}(0,\frac{n-k}{n})$,
and denote
$\Sigma_{n}(z):=\Sigma_{1-\frac{k}{n}}(z)=\mathbb{E}_{Y\sim\mathcal{N}(0,\frac{n-k}{n})}[\sigma(z+Y)]$.
Moreover, let $G:=\sum_{i\in T}w_{i}x_{i}+b$. Then,

$\displaystyle\mathbb{E}_{|w|,|b|}\langle M_{T},\sigma\rangle$
$\displaystyle=\mathbb{E}_{|w|_{T},|b|,x_{T}}\left[M_{T}(x)\Sigma_{n}\left(G\right)\right].$
(70)

Since, by condition i) in Lemma 1, function $\Sigma_{n}$ is $C^{\infty}$ and
therefore $C^{P}$, we apply Taylor‘s theorem with Lagrange remainder and write

$\displaystyle\Sigma_{n}(z)=\sum_{\nu=0}^{P}a_{\nu,n}z^{\nu}+R_{P,n}(z),$ (71)

where $a_{\nu,n}=\frac{\Sigma^{(\nu)}_{n}(0)}{\nu!}$ and

$\displaystyle
R_{P,n}(z)=\frac{\Sigma_{n}^{(P+1)}(\xi_{z})}{(P+1)!}z^{P+1}\qquad\text{ for
some }|\xi_{z}|\leq|z|.$ (72)

Plugging this in (70), we get

$\displaystyle\mathbb{E}_{|w|,|b|}\langle
M_{T},\sigma\rangle=\sum_{\nu=0}^{P}a_{\nu,n}\mathbb{E}_{|w|_{T},|b|,x_{T}}\big{[}M_{T}(x)G^{\nu}\big{]}+\mathbb{E}_{|w|_{T},|b|,x_{T}}\big{[}M_{T}(x)R_{P,n}\left(G\right)\big{]}.$
(73)

The following two propositions give the asymptotic characterization of the
first and second term in (73).

######  Proposition 4.

$\displaystyle\sum_{\nu=0}^{P}a_{\nu,n}\mathbb{E}_{|w|_{T},|b|,x_{T}}\big{[}M_{T}(x)G^{\nu}\big{]}=C(P)(-1)^{C^{\prime}(\tau_{T},\operatorname{sgn}(b))}n^{-P/2}+O(n^{-P/2-1/2})\;.$
(74)

where $C(P)\neq 0$ and
$C^{\prime}(\tau_{T},\operatorname{sgn}(b))\in\mathbb{Z}$ are constants that
do not depend on $n$.

######  Proposition 5.

$\displaystyle\mathbb{E}_{|w|_{T},|b|,x_{T}}\big{[}M_{T}(x)R_{P,n}\left(G\right)\big{]}=O(n^{-P/2-1/2}).$
(75)

Before proving Propositions 4 and 5, let us see how Lemma 2 follows from them.
But this is clear: substituting into (73), we have

$\displaystyle\left(\mathbb{E}_{|w|,|b|}\langle
M_{T},\sigma\rangle\right)^{2}=C(P)^{2}n^{-P}+O(n^{-P-1/2})=\Omega(n^{-P})\;,$
(76)

where the claimed bound does not depend on $\tau$ nor on
$\operatorname{sgn}(b)$.

####  A.2.1 Proof of Proposition 4

The main step for proving Proposition 4 is the computation of $\langle
M_{T},G^{\nu}\rangle$, for $\nu\leq P$. This is summarized in the following
formula.

######  Lemma 3.

We have:

$\displaystyle\mathbb{E}_{|w|_{T},|b|,x_{T}}M_{T}(x)G^{\nu}=\begin{cases}0&\text{if
}\nu<k\vspace{0.5em}\\\
C(\nu)(-1)^{C^{\prime}(\tau_{T},\operatorname{sgn}(b))}n^{-\nu/2}&\text{if
}\nu\geq k\;,\end{cases}$ (77)

where $C(\nu)>0$.

Let us first see how to finish the proof once Lemma 3 is established. Recall
that $a_{\nu,n}=\frac{\Sigma^{(\nu)}_{1-k/n}(0)}{\nu!}$ and let
$a_{\nu}:=\frac{\Sigma^{(\nu)}(0)}{\nu!}$. We are considering a sum with $P+1$
terms, so let
$s_{\nu}:=a_{\nu,n}\mathbb{E}_{|w|_{T},|b|,x_{T}}\big{[}M_{T}(x)G^{\nu}\big{]}$.
Accordingly, our objective is to show that

$\displaystyle\sum_{\nu=0}^{P}s_{\nu}=C(P)(-1)^{C^{\prime}(\tau_{T},\operatorname{sgn}(b))}n^{-P/2}+O(n^{-P/2-1/2})\;.$
(78)

We do that by considering the terms $s_{\nu}$ one by one. For $\nu<k$, from
(77) we immediately have $s_{\nu}=0$.

For $k\leq\nu<P$, by Definition 4 recall that the only possible case is
$P=k+1$ and $\Sigma^{(k)}(0)=0$. Then, applying condition iii) from Lemma 1,

$\displaystyle|a_{\nu,n}|$
$\displaystyle=\left|\frac{\Sigma_{1-k/n}^{(\nu)}(0)-\Sigma^{(\nu)}(0)}{\nu!}\right|=O(n^{-1})\;,$
(79)

which together with (77) gives $|s_{v}|=O(n^{-P/2-1/2})$.

Finally, for $\nu=P$, by assumption we have $a_{P}\neq 0$. Then, by condition
iii), we have $|a_{P,n}-a_{P}|=O(1/n)$ and (77) gives us the correct form for
$s_{P}$ and the whole expression.

All that is left is the proof of Lemma 3.

###### Proof of Lemma 3.

The proof proceeds by using the linearity of expectation and independence and
expanding the formula for $G^{\nu}$. Recall that we assumed wlog that
$T=\\{1,\ldots,k\\}$ and let $z_{i}:=w_{i}x_{i}$ for $i\leq k$ and
$z_{k+1}:=b$:

$\displaystyle\mathbb{E}_{|w|_{T},|b|,x_{T}}M_{T}(x)G^{\nu}$
$\displaystyle=\mathbb{E}_{|w|_{T},|b|,x_{T}}\left(\prod_{i=1}^{k}x_{i}\right)\left(\sum_{i=1}^{k}w_{i}x_{i}+b\right)^{\nu}$
(80)
$\displaystyle=\sum_{I=(i_{1},\ldots,i_{\nu})\in[k+1]^{\nu}}\mathbb{E}_{|w|_{T},|b|,x_{T}}\left(\prod_{i=1}^{k}x_{i}\right)\left(\prod_{i\in
I}z_{i}\right)\;.$ (81)

Let us focus on a single term of the sum in (81) for
$I=(i_{1},\ldots,i_{\nu})\in[k+1]^{\nu}$. For $j=1,\ldots,k+1$, let
$\alpha_{j}=\alpha_{j}(I):=|\\{m:i_{m}=j\\}|$. Accordingly, we can rewrite a
term from (81) as

$\displaystyle\mathbb{E}_{|w|_{T},|b|,x_{T}}$
$\displaystyle\left(\prod_{i=1}^{k}x_{i}\right)\left(\prod_{i\in
I}z_{i}\right)$ (82)
$\displaystyle=\mathbb{E}_{|w|_{T},|b|,x_{T}}\left(\prod_{i=1}^{k}w_{i}^{\alpha_{i}}x_{i}^{\alpha_{i}+1}\right)b^{\alpha_{k+1}}$
(83)
$\displaystyle=\left(\prod_{i=1}^{k}\tau_{i}^{\alpha_{i}}\right)\operatorname{sgn}(b)^{\alpha_{k+1}}\left(\prod_{i=1}^{k}\mathbb{E}_{|w|_{i}}\big{[}|w|_{i}^{\alpha_{i}}\big{]}\cdot\mathbb{E}_{x_{i}}\big{[}x_{i}^{\alpha_{i}+1}\big{]}\right)\mathbb{E}_{|b|}\big{[}|b|^{\alpha_{k+1}}\big{]}\;.$
(84)

Since $\mathbb{E}[x_{i}^{\alpha_{i}+1}]=0$ if $\alpha_{i}$ is even, for a term
in (84) to be non-zero it is necessary that $\alpha_{i}$ is odd for every
$1\leq i\leq k$. Consequently, since $\sum_{i=1}^{k+1}\alpha_{i}=\nu$, in any
non-zero term the parity of $\alpha_{k+1}$ is equal to the parity of $\nu-k$.
Therefore, every non-zero term is of the form

$\displaystyle\mathbb{E}_{|w|_{T},|b|,x_{T}}\left(\prod_{i=1}^{k}x_{i}\right)\left(\prod_{i\in
I}z_{i}\right)$
$\displaystyle=\left(\prod_{i=1}^{k}\tau_{i}\right)\operatorname{sgn}(b)^{\mathds{1}[\nu-k\text{
odd}]}\cdot\left(\prod_{i=1}^{k}\mathbb{E}_{|w|_{i}}\big{[}|w_{i}|^{\alpha_{i}}\big{]}\right)\mathbb{E}_{|b|}\big{[}|b|^{\alpha_{k+1}}\big{]}$
(85)
$\displaystyle=(-1)^{C^{\prime}(\tau_{T},\operatorname{sgn}(b))}\cdot\left(\prod_{i=1}^{k}\mathbb{E}_{|w|_{i}}\big{[}|w_{i}|^{\alpha_{i}}\big{]}\right)\mathbb{E}_{|b|}\big{[}|b|^{\alpha_{k+1}}\big{]}\;.$
(86)

We now establish the first case from (77). If $\nu<k$, then since
$\nu=\sum_{i=1}^{k+1}\alpha_{i}$ at least one of $\alpha_{i}$, $1\leq i\leq k$
must be zero, and therefore even. Consequently, each term in (81) is zero and
it follows that $\mathbb{E}_{|w|_{T},|b|,x_{T}}M_{T}(x)G^{\nu}=0$.

On the other hand, for $\nu\geq k$, there exists a non-zero term, for example
taking $\alpha_{1}=\ldots=\alpha_{k}=1$ and $\alpha_{k+1}=\nu-k$. Take any
such term arising from $I\in[k+1]^{\nu}$. Since
$w_{i},b\sim\mathcal{N}(0,1/n)$, we have
$\mathbb{E}_{|w|_{i}}\big{[}|w_{i}|^{j}\big{]},E_{|b|}\big{[}|b|^{j}\big{]}=C_{j}\cdot
n^{-j/2}$ for some $C_{j}>0$ for every fixed $j$. Substituting in (86) and
using $\nu=\sum_{i=1}^{k+1}\alpha_{i}$, we get

$\displaystyle\mathbb{E}_{|w|_{T},|b|,x_{T}}\left(\prod_{i=1}^{k}x_{i}\right)\left(\prod_{i\in
I}z_{i}\right)=(-1)^{C^{\prime}(\tau_{T},\operatorname{sgn}(b))}C_{I}n^{-\nu/2}$
(87)

for some $C_{I}>0$. Therefore,
$C(\nu)(-1)^{C^{\prime}(\tau_{T},\operatorname{sgn}(b))}n^{-\nu/2}$ with
$C(\nu)>0$ follows since it is a sum of at most $(k+1)^{\nu}$ positive terms.
∎

####  A.2.2 Proof of Proposition 5

Let $D$ be a positive constant. We apply the decomposition

$\displaystyle\Big{|}\mathbb{E}_{|w|_{T},|b|,x_{T}}\left[M_{T}(x)R_{P,n}(G)\right]\Big{|}$
$\displaystyle\leq\mathbb{E}_{|w|_{T},|b|,x_{T}}\Big{[}\big{|}R_{P,n}(G)\big{|}\cdot\mathds{1}(|G|\leq
D)\Big{]}$ (88)
$\displaystyle\qquad\qquad+\mathbb{E}_{|w|_{T},|b|,x_{T}}\Big{[}\big{|}R_{P,n}(G)\big{|}\cdot\mathds{1}(|G|>D)\Big{]}$
(89)

The proposition follows from Lemmas 4 and 5 applied to an arbitrary value of
$D$, eg., $D=1$.

######  Lemma 4.

For any $D>0$,

$\displaystyle\mathbb{E}_{|w|_{T},|b|,x_{T}}\Big{[}\big{|}R_{P,n}(G)\big{|}\cdot\mathds{1}(|G|\leq
D)\Big{]}=O\left(n^{-\frac{P+1}{2}}\right).$ (90)

###### Proof.

Let us observe that for a fixed $b$, $G\sim\mathcal{N}(b,\frac{k}{n})$, thus

$\displaystyle\mathbb{E}_{|w|_{T},x_{T}}\left[|R_{P,n}(G)|\mathds{1}(|G|\leq
D)\right]=\mathbb{E}_{y\sim\mathcal{N}(b,\frac{k}{n})}\left[|R_{P,n}(y)|\mathds{1}(|y|\leq
D)\right].$ (91)

Recall that $R_{P,n}(x)=\frac{\Sigma_{n}^{(P+1)}(\xi_{x})}{(P+1)!}x^{P+1}$ for
some $|\xi_{x}|\leq|x|$. Thus,

$\displaystyle\mathbb{E}_{y\sim\mathcal{N}(b,\frac{k}{n})}\left[|R_{P,n}(y)|\mathds{1}(|y|\leq
D)\right]\leq\sup_{|y|\leq
D}\frac{|\Sigma_{n}^{(P+1)}(y)|}{(P+1)!}\cdot\mathbb{E}_{y\sim\mathcal{N}(b,\frac{k}{n})}|y|^{P+1}.$
(92)

On the one hand, assuming that $n\geq 2k$, we have $\Sigma_{n}=\Sigma_{v}$ for
some $1/2\leq v\leq 1$, and thus using the common polynomial bound in property
ii) $\sup_{|y|\leq D}|\Sigma_{n}^{(P+1)}(y)|\leq M_{D}$, where the constant
$M_{D}$ does not depend on $n$. On the other hand,

$\displaystyle\mathbb{E}_{y\sim\mathcal{N}(b,\frac{k}{n})}|y|^{P+1}$
$\displaystyle=n^{-\frac{P+1}{2}}\cdot\mathbb{E}_{y}\big{|}\sqrt{n}\cdot
y|^{P+1}$ (93) $\displaystyle\leq n^{-\frac{P+1}{2}}\cdot
2^{P+1}\cdot\left(|\sqrt{n}b|^{P+1}+\mathbb{E}_{z\sim\mathcal{N}(0,k)}|z|^{P+1}\right)$
(94) $\displaystyle=n^{-\frac{P+1}{2}}\cdot
2^{P+1}\cdot\left(|\sqrt{n}b|^{P+1}+\frac{(2k)^{\frac{P+1}{2}}\Gamma(\frac{P+2}{2})}{\sqrt{\pi}}\right),$
(95)

where in the last equation we plugged the (P+1)-th central moment of the
Gaussian distribution (see, eg., [Win12]). Since $|\sqrt{n}b|$ is also
distributed like an absolute value of $\mathcal{N}(0,1)$, taking the
expectation over $|b|$, we get that for fixed $P,k$,

$\displaystyle\mathbb{E}_{|w|_{T},|b|,x_{T}}\Big{[}\big{|}R_{P,n}(G)\big{|}\cdot\mathds{1}(|G|\leq
D)\Big{]}=O\left(n^{-\frac{P+1}{2}}\right).$ (96)

∎

######  Lemma 5.

For any constant $D>0$, there exist $C_{1},C_{2}>0$ such that

$\displaystyle\mathbb{E}_{|w|_{T},|b|,x_{T}}\Big{[}\big{|}R_{P,n}(G)\big{|}\cdot\mathds{1}(|G|>D)\Big{]}\leq
C_{1}\exp(-C_{2}n).$ (97)

###### Proof.

By Cauchy-Schwartz inequality,

$\displaystyle\mathbb{E}_{|w|_{T},|b|,x_{T}}\left[|R_{P,n}(G)|\mathds{1}(|G|>D)\right]$
$\displaystyle\overset{(C.S.)}{\leq}\mathbb{E}_{|w|_{T},|b|,x_{T}}[R_{P,n}(G)^{2}]^{1/2}\cdot\mathop{\rm
Pr}\nolimits_{|w|_{T},|b|,x_{T}}[|G|>D]^{1/2}\;.$ (98)

For the first term, we use the universal polynomial bound from property ii):

$\displaystyle\Big{|}\mathbb{E}_{|w|_{T},|b|,x_{T}}[R_{P,n}(G)^{2}]\Big{|}$
$\displaystyle=\mathbb{E}_{|w|_{T},|b|,x_{T}}\left[\left(\frac{\sup_{|y|\leq|G|}\Sigma_{n}^{(P+1)}(y)}{(P+1)!}|G|^{P+1}\right)^{2}\right]$
(99)
$\displaystyle\leq\mathbb{E}_{|w|_{T},|b|,x_{T}}\left[\left(\frac{\sup_{|y|\leq|G|}Cy^{2\ell}+C}{(P+1)!}|G|^{P+1}\right)^{2}\right]$
(100)
$\displaystyle=\mathbb{E}_{|w|_{T},|b|,x_{T}}\left[\left(\frac{CG^{2\ell}+C}{(P+1)!}|G|^{P+1}\right)^{2}\right]=O_{n}(1)\;,$
(101)

using a similar reasoning as in Lemma 4.

On the other hand, writing $G=G^{\prime}+|b|$, we have

$\displaystyle\mathop{\rm Pr}\nolimits_{|w|_{T},|b|,x_{T}}[|G|>D]$
$\displaystyle\leq\mathop{\rm Pr}\nolimits_{|b|}[|b|>D/2]+\mathop{\rm
Pr}\nolimits_{|w|_{T},x_{T}}[|G^{\prime}|>D/2]$ (102) $\displaystyle\leq
2\mathop{\rm Pr}\nolimits_{y\sim\mathcal{N}(0,1/n)}[|y|>D/2]\leq
4\exp(-D^{2}n/8)\;.$ (103)

We get desired bound putting together (99) and (103). ∎

##  Appendix B Expressivity of Common Activation Functions

In this section we show that ReLU and sign are expressive. It is clear that
both of these functions are polynomially bounded, so we only need to analyze
their Hermite expansions for condition b) in Definition 4. In both cases we do
it by writing a closed form for $\Sigma^{(k)}(0)$.

######  Proposition 6.

$\operatorname{ReLU}(x):=\max\\{0,x\\}$ is expressive.

###### Proof.

We will see that in the case $\sigma=\operatorname{ReLU}$ we have
$\Sigma(z)=\frac{z}{2}+\frac{z}{2}\operatorname{erf}(z)+\frac{1}{2\sqrt{\pi}}\exp(-z^{2})$.
Indeed,

$\displaystyle\Sigma(z)$
$\displaystyle=\int_{-\infty}^{\infty}\mathds{1}(z+y\geq
0)(z+y)\phi(y)\,\mathrm{d}y=\int_{-z}^{\infty}(z+y)\phi(y)\,\mathrm{d}y=z\Phi(z)+\phi(z)$
(104)
$\displaystyle=\frac{z}{2}+\frac{z\operatorname{erf}(z/\sqrt{2})}{2}+\phi(z)\;.$
(105)

Using well-known Taylor expansions of $\operatorname{erf}$ and $\phi$, this
results in

$\displaystyle\Sigma^{(k)}(0)=\begin{cases}\frac{1}{2}&\text{if }k=1\;,\\\
\frac{(-1)^{k/2+1}}{\sqrt{2\pi}2^{k/2}(k-1)(k/2)!}&\text{if $k$ is even},\\\
0&\text{otherwise.}\end{cases}$ (106)

In particular, $\Sigma^{(k)}(0)\neq 0$ for every even $k$ and ReLU is
expressive. ∎

######  Proposition 7.

The sign function $\operatorname{sgn}(x)$ is expressive.

###### Proof.

In this case, similarly, we have

$\displaystyle\Sigma(z)$
$\displaystyle=-\int_{-\infty}^{-z}\phi(z)\,\mathrm{d}z+\int_{-z}^{\infty}\phi(z)\,\mathrm{d}z=2\Phi(z)-1=\operatorname{erf}(z/\sqrt{2})\;,$
(107)

which can be seen to have the expansion

$\displaystyle\Sigma^{(k)}(0)=\begin{cases}\frac{2}{\sqrt{\pi}}\cdot\frac{(-1)^{(k-1)/2}}{2^{k/2}\left(\frac{k-1}{2}\right)!k}&\text{if
$k$ is odd,}\\\ 0&\text{otherwise.}\end{cases}$ (108)

Again, the sign function is expressive since $\Sigma^{(k)}\neq 0$ for every
odd $k$. ∎

##  Appendix C Proof of Proposition 2

Using the definition of INAL and the Fourier expansion of $f$, we get

$\displaystyle\operatorname{INAL}(f,\sigma)$
$\displaystyle=\mathbb{E}_{w,b}\left[\langle f,\sigma\rangle^{2}\right]$ (109)
$\displaystyle=\mathbb{E}_{w,b}\left[\left(\sum_{T\in[n]}\hat{f}(T)\langle
M_{T},\sigma\rangle\right)^{2}\right]$ (110)
$\displaystyle=\mathbb{E}_{w,b}\left[\sum_{T}\hat{f}(T)^{2}\langle
M_{T},\sigma\rangle^{2}+\sum_{S\neq T}\hat{f}(S)\hat{f}(T)\langle
M_{T},\sigma\rangle\langle M_{S},\sigma\rangle\right].$ (111)

We show that the second term of (111) is zero. Let $S,T$ be two distinct sets.
Without loss of generality, assume that $|S|\geq|T|$, and let $i$ be such that
$i\in S$ but $i\not\in T$ (such $i$ must exist since $S\neq T$). Fix $w$ and
$b$ and decompose $w$ into $w_{\sim i},|w_{i}|,\operatorname{sgn}(w_{i})$
where $w_{\sim i}$ denotes the vector of weights, excluding coordinate $i$. By
applying the change of variable $\operatorname{sgn}(w_{i})x_{i}\mapsto y_{i}$
and noticing that $x_{i}$ has the same distribution of $y_{i}$, we then get

$\displaystyle\langle M_{S},\sigma\rangle$
$\displaystyle=\mathbb{E}_{x}[M_{S}(x)\cdot\sigma(x_{i}\operatorname{sgn}(w_{i})|w_{i}|+\sum_{j\neq
i}x_{j}w_{j}+b)]$ (112)
$\displaystyle=\operatorname{sgn}(w_{i})\cdot\mathbb{E}_{x_{\sim
i},y_{i}}[M_{S_{\sim i}}(x)\cdot y_{i}\cdot\sigma(y_{i}|w_{i}|+\sum_{j\neq
i}x_{j}w_{j}+b)]$ (113) $\displaystyle:=\operatorname{sgn}(w_{i})\cdot E_{S},$
(114)

where $E_{S}$ does not depend on $\operatorname{sgn}(w_{i})$. On the other
hand,

$\displaystyle\langle M_{T},\sigma\rangle$
$\displaystyle=\mathbb{E}_{x}[M_{T}(x)\cdot\sigma(x_{i}\operatorname{sgn}(w_{i})|w_{i}|+\sum_{j\neq
i}x_{j}w_{j}+b)]$ (115) $\displaystyle=\mathbb{E}_{x_{\sim
i},y_{i}}[M_{T}(x)\cdot\sigma(y_{i}|w_{i}|+\sum_{j\neq i}x_{j}w_{j}+b)],$
(116)

which means that $\langle M_{T},\sigma\rangle$ does not depend on
$\operatorname{sgn}(w_{i})$. Thus, we get

$\displaystyle\mathbb{E}_{w,b}\left[\langle M_{T},\sigma\rangle\langle
M_{S},\sigma\rangle\right]=\mathbb{E}_{w,b}\left[\operatorname{sgn}(w_{i})\cdot\langle
M_{T},\sigma\rangle\cdot E_{S}\right]=0.$ (117)

Hence,

$\displaystyle\operatorname{INAL}(f,\sigma)$
$\displaystyle=\sum_{T}\hat{f}(T)^{2}\mathbb{E}_{w,b}\left[\langle
M_{T},\sigma\rangle^{2}\right]$ (118)
$\displaystyle=\sum_{T}\hat{f}(T)^{2}\operatorname{INAL}(M_{T},\sigma).$ (119)

##  Appendix D Proof of Corollary 2

Indeed, by Proposition 2 for any $f:\\{\pm 1\\}^{n}\to\mathbb{R}$ and $k$ it
holds

$\displaystyle\operatorname{INAL}(f,\sigma)$
$\displaystyle=\sum_{T}\hat{f}(T)^{2}\operatorname{INAL}(M_{T},\sigma)\geq
W^{k}(f)\operatorname{INAL}(M_{k},\sigma)\;.$ (120)

Accordingly, if $\operatorname{INAL}(M_{k},\sigma)=\Omega(n^{-k_{0}})$, we
have

$\displaystyle W^{k}(f_{n})\leq\operatorname{INAL}(f_{n},\sigma)\cdot
O(n^{k_{0}})\;,$ (121)

and then, under our assumptions, also

$\displaystyle W^{\leq k}(f_{n})\leq\operatorname{INAL}(f_{n},\sigma)\cdot
O(n^{k_{0}})\;.$ (122)

For the ’’in particular‘‘ statement, let $(f_{n})$ be a function family with
negligible $\operatorname{INAL}(f_{n},\sigma)$ for a correlating $\sigma$. Let
$k\in\mathbb{N}$. Since $\sigma$ is correlating, the assumption
$\operatorname{INAL}(M_{k^{\prime}},\sigma)=\Omega(n^{-k_{0}})$ for
$k^{\prime}=0,\ldots,k$ holds. Therefore, (122) also holds and $W^{\leq k}(f)$
is negligible. Since $k$ was arbitrary, the function family $(f_{n})$ is high-
degree.

##  Appendix E Details and Proof of Corollary 1

Corollary 1 states a hardness results for learning on _fully connected neural
networks with iid initialization_. This is a more specific definition than the
one we gave for a neural network in Section 2. Let us state it precisely,
following the treatment in [AS20b].

######  Definition 10.

For the purposes of Corollary 1, a neural network on $n$ inputs consists of a
differentiable activation function $\sigma:\mathbb{R}\to\mathbb{R}$, a
threshold function $f:\mathbb{R}\to\\{\pm 1\\}$ and a weighted, directed graph
with a vertex set labeled with
$\\{1,x_{1},\ldots,x_{n},v_{1},\ldots,v_{m},v_{\mathrm{out}}\\}$. The vertices
labeled with $x_{1},\ldots,x_{n}$ are called the input vertices, the vertex
labeled with $1$ is the constant vertex and $v_{\mathrm{out}}$ is the output
vertex.

We assume that the graph does not contain loops, the constant and input
vertices do not have any incoming edges, the output vertex does not have
outgoing edges and for the remaining vertices there are no edges
$(v_{i},v_{j})$ for $i>j$. Each vertex (a neuron) has an associated function
(the output of the neuron) from $\mathbb{R}^{n}$ to $\mathbb{R}$ which is
defined recursively as follows: The output of the constant vertex is $y_{1}=1$
and the output of the input vertex is (abusing notation) $y_{x_{i}}=x_{i}$.
The output of any other vertex $v_{i}$ is given by
$y_{v_{i}}=\sigma(\sum_{v:(v,v_{i})\in E(G)}w_{v,v_{i}}y_{v})$. Finally, the
output of the whole network is given by $f(y_{v_{\mathrm{out}}})$.

We say that the neural network is _fully connected_ if every vertex that has
an incoming edge from an input vertex has incoming edges from all input
vertices.

Note that our definition of ’’fully connected network‘‘ covers any feed-
forward architecture that consists of a number of fully connected hidden
layers stacked on top of each other.

Let us restate Theorem 3 from [AS20b] with the bound555Since we are discussing
GD, we are applying their bound with infinite sample size $m=\infty$. from
their Corrolary 1 applied to the junk flow term JFT:

######  Theorem 4 ([AS20b]).

Let $P_{\mathcal{F}}$ be a distribution on Boolean functions $f:\\{\pm
1\\}^{n}\to\\{\pm 1\\}$. Consider any neural network as defined in Definition
10 with $E$ edges. Assume that a function $f$ is chosen from $P_{\mathcal{F}}$
and then $T$ steps of noisy GD with learning rate $\gamma$, overflow range $A$
and noise level $\tau$ are run on the initial network using function $f$ and
uniform input distribution $\mathcal{U}^{n}$.

Then, in expectation over the initial choice of $f$, the training noise, and a
fresh sample $x\sim\mathcal{U}^{n}$, the trained neural network
$\operatorname{NN}^{(T)}$ satisfies

$\displaystyle\Pr\big{[}\operatorname{NN}^{(T)}(x)=f(x)\big{]}$
$\displaystyle\leq\frac{1}{2}+\frac{\gamma
T\sqrt{E}A}{\tau}\cdot\operatorname{CP}(P_{\mathcal{F}},\mathcal{U}^{n})^{1/4}\;.$
(123)

Finally, we need to discuss the fact that Corollary 1 applies for any fully
connected neural network _with iid initialization_. What we mean by this is
that the initial neural network has a fixed activation $\sigma$, threshold
function $f$ and graph (vertices and edges), but the weights on edges are not
fixed. Instead, they are chosen randomly iid from any fixed probability
distribution. More precisely, we can make a weaker assumption that the weights
on all edges that are outgoing from the input vertices are chosen666 Even more
precisely, we can assume only that the distribution of these weights is
symmetric under permutations of input vertices $x_{1},\ldots,x_{n}$. iid from
a fixed distribution and all the other weights have arbitrary fixed values.

We can now proceed to prove Corollary 1.

###  E.1 Proof of Corollary 1

Let a randomly initialized, fully connected neural network $\operatorname{NN}$
be trained in the following way. First, a function $\overline{f_{n}}\circ\pi$
is chosen uniformly at random from the orbit of $\overline{f_{n}}$. Then, a
noisy GD algorithm is run with the parameters stated: $T$ steps, learning rate
$\gamma$, overflow range $A$ and noise level $\tau$. Finally, a fresh sample
$x\sim\mathcal{U}^{N}$ is presented to the trained neural network. Then,
Theorem 4 says that

$\displaystyle\Pr\big{[}\operatorname{NN}^{(T)}(x)=(\overline{f_{n}}\circ\pi)(x)\big{]}\leq\frac{1}{2}+\frac{\gamma
T\sqrt{E}A}{\tau}\cdot\operatorname{CP}(\operatorname{orb}(\overline{f_{n}}),\mathcal{U}^{N})^{1/4}\;.$
(124)

Since we can apply Theorem 4 to the class of all orbits of
$-\overline{f_{n}}$, which has the same cross-predictability, the same upper
bound also holds for
$\Pr[\operatorname{NN}^{(T)}(x)\neq(\overline{f_{n}}\circ\pi)(x)]$.
Consequently, we have the expectation bound

$\displaystyle\Big{|}\mathbb{E}\langle\operatorname{NN}^{(T)},\overline{f_{n}}\circ\pi\rangle\Big{|}\leq\frac{2\gamma
T\sqrt{E}A}{\tau}\cdot\operatorname{CP}(\operatorname{orb}(\overline{f_{n}}),\mathcal{U}^{N})^{1/4}\;.$
(125)

Recall that the neural network is fully connected and the weights on the edges
outgoing from the input vertices are iid. The expectation in (125) is an
average of conditional expectations for different initial choices of
permutation $\pi$. Consider the action induced by $\pi$ on the weights
outgoing from the input vertices. By properties of GD, it follows that each
conditional expectation over $\pi$ contributes equally to the left-hand side
of (125). It follows that the same bound holds also for the single function
$\overline{f_{n}}$:

$\displaystyle\left|\mathbb{E}_{\operatorname{NN}^{(T)}}\langle\operatorname{NN}^{(T)},\overline{f_{n}}\rangle\right|\leq\frac{2\gamma
T\sqrt{E}A}{\tau}\operatorname{CP}(\operatorname{orb}(\overline{f_{n}}),\mathcal{U}^{N})^{1/4}\;.$
(126)

Accordingly, if $\operatorname{INAL}(f_{n},\sigma)$ is negligible, then, by
Theorem 2,
$\operatorname{CP}(\operatorname{orb}(\overline{f_{n}}),\mathcal{U}^{N})$ is
negligible and the right-hand side of (126) remains negligible for any
polynomial bounds on $\gamma$, $T$, $E$, $A$ and $\tau$, as claimed.

For the more precise statement, if
$\operatorname{INAL}(f_{n},\sigma)=O(n^{-c})$, then again by Theorem 2 it
holds
$\operatorname{CP}(\operatorname{orb}(\overline{f_{n}}),\mathcal{U}^{N})=O(n^{-\frac{\epsilon}{1+\epsilon}(c-1)})$
and we get the bound of $O\left(\frac{\gamma T\sqrt{E}A}{\tau}\cdot
n^{-\frac{\epsilon}{4(1+\epsilon)}(c-1)}\right)$ on the right-hand side of
(126). ∎