# Efficient anti-symmetrization of a neural network layer by taming the sign
problem

Nilin Abrahamsen  Corresponding author<EMAIL_ADDRESS>Department of
Mathematics, University of California, Berkeley  The Simons Institute for the
Theory of Computing  Lin Lin<EMAIL_ADDRESS>Department of
Mathematics, University of California, Berkeley  Lawrence Berkeley National
Laboratory

###### Abstract

Explicit antisymmetrization of a neural network is a potential candidate for a
universal function approximator for generic antisymmetric functions, which are
ubiquitous in quantum physics. However, this procedure is a priori factorially
costly to implement, making it impractical for large numbers of particles. The
strategy also suffers from a sign problem. Namely, due to near-exact
cancellation of positive and negative contributions, the magnitude of the
antisymmetrized function may be significantly smaller than before
antisymmetrization. We show that the anti-symmetric projection of a two-layer
neural network can be evaluated efficiently, opening the door to using a
generic antisymmetric layer as a building block in anti-symmetric neural
network Ansatzes. This approximation is effective when the sign problem is
controlled, and we show that this property depends crucially the choice of
activation function under standard Xavier/He initialization methods. As a
consequence, using a smooth activation function requires re-scaling of the
neural network weights compared to standard initializations.

Fermions, Sign problem, Neural quantum states,

##  1 Introduction

Simulation of quantum chemistry from first principles depends on the accurate
modeling of _fermionic_ system comprised of the electrons. The Pauli exclusion
principle dictates that fermionic wavefunctions must be antisymmetric with
respect to particle exchange. This antisymmetry poses challenges; for
instance, as the number of fermions increases, the effective parameterization
of such wavefunctions becomes exceedingly complex for many systems. The
antisymmetry condition also results in near-exact cancellation between
positive and negative contributions when computing observables. This leads to
the so-called fermionic sign problem (FSP), which was originally discovered in
quantum Monte Carlo (QMC) simulations [1, 2, 3].

Over the last decade, the scientific community has witnessed a surge in the
development of methods employing neural networks (NNs) as universal function
approximators. This surge is due to advancements in software tools, hardware
capabilities, and algorithmic improvements. These developments have had a
significant impact on the modeling of fermionic systems [4, 5, 6, 7, 8, 9].

However, constructing a universal NN representation for antisymmetric
functions that does not suffer from the curse of dimensionality is still an
open question. In the absence of symmetry constraints, even a simple structure
such as a two-layer NN can act as a universal function approximator. In
theory, one could explicitly antisymmetrize such a two-layer NN to
parameterize universal antisymmetric functions. Such an explicitly
antisymmetrized NN structure has been recently studied in QMC calculations,
which can yield effectively the exact ground state energy for small atoms and
molecules [9]. However, the computational cost of this antisymmetrization
procedure appears _a priori_ to grow factorially with the system size.

In this paper we give a procedure to _efficiently_ evaluate the explicit anti-
symmetrization of a two-layer neural network using a quadrature procedure.
This is surprising due to the factorially many terms in the definition of the
anti-symmetrization. For this statement to be meaningful we require that the
sign problem is controlled, meaning that the anti-symmetrization does not make
the original function vanish due to cancellations. We demonstrate that with
the standard Xavier/He initialization, the sign problem is controlled when the
activation function in the neural network is _rough_. Examples of a rough
(resp. smooth) activation function in the ReLU (resp. sigmoid). Alternatively,
this statement implies that to avoid the sign problem with the sigmoid
activation, the weights in the first layer need to be asymptotically larger
than the standard Xavier/He initializations.

Among all activation functions, the exponential activation function (real or
complex) plays a special role in our analysis. This is because
antisymmetrizing a two-layer NN with an exponential activation function gives
rise to a determinant (called a Slater determinant), which can be evaluated in
polynomial time. By exploring the Fourier representation of a (rough)
activation function, we can approximately express the explicitly
antisymmetrized two-layer NN as a linear combination of polynomially (with
respect to the system size and inverse precision) many Slater determinants.
This overcomes the factorial scaling barrier, and gives rise to a polynomial-
time algorithm for approximate evaluation of antisymmetrized two-layer neural
networks (Theorem 3.7).

###  1.1 Related work

The representation of anti-symmetric functions is extensively studied in
physics, where a widely used class of Ansatzes for anti-symmetric functions
takes the form of a sum of Slater determinants. Slater determinants can span a
dense subset of the anti-symmetric space but the representation is very
inefficient. Indeed, even in the case of a finite single-particle state space
$|\Omega|=O(n)$ we would require $\binom{|\Omega|}{n}$ Slater determinants to
span the anti-symmetric space. [10] finds certain anti-symmetric functions
that cannot be efficiently approximated using a simple sum of Slater
determinants, but can be effectively expressed using a more complex Ansatz
called the Slater-Jastrow form.

In the machine learning literature there is a rich body of works related to
permutation-invariant data, i.e., when the input data is a set [11, 12, 13,
14]. But the literature on _anti_ -symmetrized neural networks is sparse. [15]
gave approximation bounds for the class of anti-symmetric functions in the
Barron space, which can be viewed as the set of functions that can be
expressed as infinite two-layer neural networks.

##  2 Problem setting

The wave function $\psi(x_{1},\ldots,x_{n})$ of a system of $n$
_indistinguishable particles_ in a $d$-dimensional space ($d=1,2,3$) satisfies
permutation symmetry of $|\psi|$ under interchange of the $n$ inputs
$x_{i}\in\mathbb{R}^{d}$. _Fermions_ are indistinguishable particles which
satisfy the Pauli exclusion principle and correspond to an _antisymmetric_
wave function $\psi$. For a permutation $\pi\in S_{n}$ with sign $(-1)^{\pi}$,
we have $\pi(\psi)=(-1)^{\pi}\psi$ where we have defined
$\pi(\psi):\mathbb{R}^{nd}\mapsto\mathbb{C}$ by
$\pi(\psi)(x):=\psi(x_{\pi(1)},\ldots,x_{\pi(n)})$ for $x\in\mathbb{R}^{nd}$.
For any $f:\mathbb{R}^{nd}\to\mathbb{C}$ we can define its explicit
antisymmetrization

$\mathcal{A}f=\frac{1}{\sqrt{n!}}\sum_{\pi\in S_{n}}(-1)^{\pi}\pi(f).$ (1)

As will be shown later, the prefactor $1/\sqrt{n!}$ is the natural scaling in
the antisymmetrization process.

A function defined on $\mathbb{R}^{d}$ is called a single-particle function.
Let $\rho$ be a fast-decaying probability density on $\mathbb{R}^{d}$ and let
$\rho_{n}=\rho^{\otimes n}$ be a product of single-particle densities. For
simplicity of analytic computation, we may take $\rho$ to be the density of
the standard Gaussian $\mathcal{N}(0,I_{d})$ (called a Gaussian envelope). We
represent an $n$-particle fermionic wave function as

$\psi=\sqrt{\rho_{n}}\odot\mathcal{A}f=\mathcal{A}(\sqrt{\rho_{n}}\odot f),$
(2)

where $\odot$ denotes multiplication of function values. The wave function
should be normalized as $\|\psi\|^{2}=1$, where $\|\cdot\|$ is the
$L^{2}$-norm on $\mathbb{R}^{nd}$. Eq. 2 implies
$\|\psi\|=\|\mathcal{A}f\|_{\rho}$ where $\|\cdot\|_{\rho}$ is the norm
induced by the inner product $\langle
f|g\rangle_{\rho}=\int\bar{f}(x)g(x)d\rho_{n}(x)$.

If $f=f_{1}\otimes\cdots\otimes f_{n}$ is a product of single-particle
functions, then so is $\phi=\phi_{1}\otimes\cdots\otimes\phi_{n}$ where
$\phi_{i}=\sqrt{\rho}\odot f_{i}$. In this case $\psi(x)=(\mathcal{A}\phi)(x)$
is a determinant (called the Slater determinant) denoted by
$\phi_{1}\wedge\cdots\wedge\phi_{n}$ and defined by
$(\phi_{1}\wedge\cdots\wedge\phi_{n})(x_{1},\ldots,x_{n})=\frac{1}{\sqrt{n!}}\det[(\phi_{i}(x_{j}))_{ij}]$.
The normalization in Eq. (1) is such that if $\phi_{i}$ are orthonormal
functions on $L^{2}(\mathbb{R}^{d})$ then $\psi$ is normalized by Pythagoras’
theorem, $\|\psi\|=\|\mathcal{A}f\|_{\rho}=1$.

By letting $f$ range over a universal class of functions on $\mathbb{R}^{nd}$
we obtain a universal class of antisymmetric functions
$\psi=\sqrt{\rho_{n}}\odot\mathcal{A}f$ which are not in general normalized.
However, this approach has two important drawbacks _a priori_ :

  1. 1.

The procedure of normalizing $\psi$ becomes numerically unstable if
cancellations in (1) cause the magnitudes of $\mathcal{A}f$ to be too small
compared to $f$. This can be viewed as a manifestation of the fermionic sign
problem in this setting.

  2. 2.

The sum (1) has $n!$ terms, making it in general intractable to evaluate the
sum for all but small values of $n$.

aaaaa

Figure 1: Log-plot of $\mathbb{E}[\|\mathcal{A}f\|_{\rho}^{2}]$ as a function
of $n$ for different activation functions $\tau$: $\exp$ (magenta), $\tanh$
(red), ReLU (blue), and Heaviside step function (green). The weights are
sampled from the Xavier initialization (Definition 3.4) with $d=3$, $m=nd$.
Shaded areas represent $90\%$ confidence regions. Values for $n\leq 12$ are
computed by direct antisymmetrization, and dotted lines on the right are
computed from (15).

We consider the case when $f$ is given by a two-layer NN

$f_{W,a,b}(x)=\sum_{k=1}^{m}a_{k}\tau(w^{(k)}\cdot x+b_{k}),$ (3)

where $\tau:\mathbb{R}\to\mathbb{R}$ is some activation function,
$w^{(k)}\in\mathbb{R}^{nd}$, and $b_{k},a_{k}\in\mathbb{R}$ for each
$k=1,\ldots,m$.

To illustrate the sign problem, Fig. 1 shows the magnitude
$\|\mathcal{A}f\|_{\rho}^{2}$ for four activation functions $\exp$, $\tanh$,
ReLU ($\tau_{\mathrm{ReLU}}(y)=\max\\{0,y\\}$), and the Heaviside step
function ($\tau_{\mathrm{HS}}(y)=1_{y>0}$). As the system size $n$ increases,
the norm decreases with respect to $n$ for all activation functions. However,
the decay rate depends on the smoothness of the activation function. The
deterioration of the sign problem is much more severe for smooth activation
functions ($\exp$, $\tanh$) than for rough activation functions (ReLU,
Heaviside). We aim to quantify this effect and investigate more precisely how
the magnitude of $\mathcal{A}\tau_{w}$ depends on $\tau$.

##  3 Main results

We state our results in terms of the Fourier transform $\widehat{\tau}$ of the
activation function. A typical activation function does not have finite
integral over $\mathbb{R}$, so its Fourier transform is not defined as a
convergent integral but rather in the sense of _tempered distributions_ [16].
We will not need the precise definition of $\widehat{\tau}$ but only that it
satisfies the _Fourier inversion formula_ in the sense that for
$0<\epsilon<1$,

$\tau(y)=\frac{1}{\sqrt{2\pi}}\int_{|\theta|>\epsilon}\widehat{\tau}(\theta)e^{i\theta
y}d\theta+p(y)+C_{\epsilon}+O_{\epsilon\to 0}(\epsilon g(y)),$ (4)

where $p$ is a polynomial of bounded degree and $g$ is bounded by a
polynomial. In particular we will be able to take $p,C_{\epsilon}\equiv 0$,
$g(y)=|y|$ for $\tau=\tanh$ and $p(y)=y/2$,
$C_{\epsilon}=\frac{1}{\pi\epsilon}$, $g(y)=y^{2}$ for
$\tau=\operatorname{ReLU}$. The integral in (4) converges for these activation
functions since
$\int_{|\theta|>\epsilon}|\widehat{\tau}(\theta)|d\theta<\infty$:

Figure 2: Fourier transforms of different activation functions.  $\tau(y)$ | $\widehat{\tau}(\theta)$ | Fourier tail decay $K$
---|---|---
$\operatorname{ReLU}(y)$ | $\frac{-1}{\sqrt{2\pi}\cdot\theta^{2}}+\sqrt{\tfrac{\pi}{2}}i\delta^{\prime}(\theta)$ |  $3$ (rough)
$\tanh(y)$ | $\frac{-i\sqrt{\pi/2}}{\sinh(\pi\theta/2)}$ |  $\infty$ (smooth)

Consider the decomposition the an activation function into low- and high-
frequency parts as follows:

######  Definition 3.1.

For $\tau:\mathbb{R}\to\mathbb{C}$ define its _high-pass_
${\tau}^{\mathrm{HP}(t)}$ at threshold $t>0$ by

${\tau}^{\mathrm{HP}(t)}(y)=\frac{1}{\sqrt{2\pi}}\int_{|\theta|>t}\widehat{\tau}(\theta)e^{i\theta
y}d\theta.$ (5)

Define its _low-pass_ as the remainder
${\tau}^{\mathrm{LP}(t)}=\tau-{\tau}^{\mathrm{HP}(t)}$.

Eq. 4 says that ${\tau}^{\mathrm{LP}(\epsilon)}=p+C_{\epsilon}+O(\epsilon g)$
as $\epsilon\to 0$.

######  Definition 3.2.

For an activation function $\tau$ define its frequency tail
$\mathfrak{T}_{\widehat{\tau}}:(0,\infty)\to[0,\infty)$ by

$\mathfrak{T}_{\widehat{\tau}}(t)=\int_{|\theta|\geq
t}|\widehat{\tau}(\theta)|^{2}d\theta.$ (6)

We define the _tail decay_ $K\geq 0$ of $\widehat{\tau}$ as the largest $K$
such that $\mathfrak{T}_{\widehat{\tau}}(t)=O(t^{-K})$ as $t\to\infty$. More
precisely,
$K=\limsup_{t\to\infty}\frac{-\log\mathfrak{T}_{\widehat{\tau}}(t)}{\log t}$.

######  Definition 3.3 (Smooth and rough activation functions).

  1. 1.

A function $\tau:\mathbb{R}\to\mathbb{C}$ is _smooth_ if its Fourier transform
$\widehat{\tau}$ has tail decay $\infty$, i.e., if
$\mathfrak{T}_{\widehat{\tau}}(t)=t^{-\omega(1)}$ decays faster than
polynomially as $t\to\infty$. In particular, any activation function with
$\widehat{\tau}(\theta)=\theta^{-\omega(1)}$ is smooth.

  2. 2.

$\tau$ is _rough_ if there exists $k>1$ and non-zero constants
$z_{+},z_{-}\in\mathbb{C}$ such that
$\widehat{\tau}(\theta)=z_{+}\Theta(|\theta|^{-k})$ 111Here $\Theta(b_{t})$ is
to be understood as non-negative by definition. More generally we use the
standard $O(\cdot)$-notation: Write $a_{t}=O(b_{t})$ and
$b_{t}=\Omega(|a_{t}|)$ if $|a_{t}|\leq Cb_{t}$ for all $t$ and some constant
$C>0$. Write $\tilde{b}_{t}=\Theta(b_{t})$ if $\tilde{b}_{t}=O(b_{t})$ and
$\tilde{b}_{t}=\Omega(b_{t})$. Write $a_{t}=\tilde{O}(b_{t})$ if
$a_{t}=O(b_{t}|\log b_{t}|^{O(1)})$. Write $a_{t}=o(b_{t})$ and
$b_{t}=\omega(|a_{t}|)$ if $|a_{t}|=\epsilon_{t}b_{t}$ for some $\epsilon_{t}$
that converges to $0$. as $\theta\to\infty$ and
$\widehat{\tau}(\theta)=z_{-}\Theta(|\theta|^{-k})$ as $\theta\to-\infty$. In
this case $\tau$ has Fourier tail decay $K=2k-1$.

Our results below for rough activation functions hold for a more general
definition of roughness which allows the Fourier transform to have varying
phase. We give this definition of _generalized rough_ activation functions in
Appendix C.

We consider the two-layer network (3) with randomly initialized weights using
two standard initialization strategies. It is typical to initialize the biases
to zero.

######  Definition 3.4.

We say that $f_{W,a}(x)=\sum_{k=1}^{m}a_{k}\tau(w^{(k)}\cdot x)$ is chosen
with the _Xavier initialization_ or _He initialization_ if the $mnd+m$ weights
$W=(w^{(k)}_{ij}),a=(a_{i})$ are chosen independently from
$a_{k}\sim\mathcal{N}(0,\tilde{c}/m)$ for each $k=1,\ldots,m$, and
$w^{(k)}_{ij}\sim\mathcal{N}(0,\tilde{c}/(nd))$ for $k=1,\ldots,m$,
$i=1,\ldots,n$, and $j=1,\ldots,d$. Here $\tilde{c}=1$ corresponds to the
Xavier initialization and $\tilde{c}=2$ to the He initialization.

######  Theorem 3.5 (Upper bound, sign problem deteriorates super-polynomially
for smooth activation functions).

Let $f_{W,a}:\mathbb{R}^{nd}\to\mathbb{C}$ be given by a two-layer neural
network (3) with activation function $\tau$ and let
$\rho=\mathcal{N}(0,I_{nd})$ be the Gaussian envelope function. If $\tau$ is
smooth and $f_{W,a}$ is sampled from the Xavier or He initializations, then
with probability $1-o(1)$ over $W$,
$\mathbb{E}_{a|W}[\|\mathcal{A}f_{W,a}\|_{\mathcal{N}}^{2}]=n^{-\omega(1)}$.

Given an activation function $\tau:\mathbb{R}\to\mathbb{C}$ and weight vector
$w\in\mathbb{R}^{nd}$ define $\tau_{w}:\mathbb{R}^{nd}\to\mathbb{C}$ by
$\tau_{w}(x)=\tau(w\cdot x)$. Let $\ell_{w}={\tau}^{\mathrm{LP}(t)}_{w}$ be
the low-passed part of the activation function. The upper bound of
$\|\mathcal{A}f\|_{\mathcal{N}}^{2}$ relies on the fact that the norm of the
antisymmetrized function $\|\mathcal{A}\ell_{w}\|_{\mathcal{N}}^{2}$ decreases
exponentially with respect to $n$ when $t=O(\sqrt{n/\log n})$ (Lemma 6.9). The
high-passed part can be directly controlled by the tail decay of the
activation function.

######  Theorem 3.6 (Lower bound, sign problem deteriorates at most
polynomially for rough activation functions).

Let $f_{W,a}:\mathbb{R}^{nd}\to\mathbb{C}$ be given by a two-layer neural
network (3) with activation function $\tau$ and weights sampled from the
Xavier or He initialization, and let $\rho=\mathcal{N}(0,I_{nd})$ be the
Gaussian envelope. If $\tau$ is rough or generalized rough with tail decay
$K$, then with probability $1-o(1)$ over $W$,
$\mathbb{E}_{a|W}[\|\mathcal{A}f_{W,a}\|_{\mathcal{N}}^{2}]=\tilde{\Omega}(n^{-(1+2/d)K})$
where $\tilde{\Omega}$ denotes a lower bound up to $\log$-factors. In
particular the magnitude of the antisymmetrized NN decays no faster than
polynomially in $n$.

To prove Theorem 3.6 we show that for the high-passed part
$h={\tau}^{\mathrm{HP}(T)}$ at sufficiently large threshold, the norm of the
antisymmetized function $\|\mathcal{A}h_{w}\|_{\mathcal{N}}^{2}$ can be
approximated by the norm $\|h_{w}\|_{\mathcal{N}}^{2}$ before
antisymmetrization (Lemma 6.2). The lower bound with polynomial scaling in $n$
can also be viewed as evidence that the prefactor $1/\sqrt{n!}$ in Eq. 1 is
the appropriate scaling.

We then show that when $f$ is given by a two-layer NN with a rough activation
function, $\mathcal{A}f$ can be computed efficiently to any inverse-polynomial
precision relative to $\sqrt{\mathbb{E}[\|\mathcal{A}f\|_{\mathcal{N}}^{2}]}$:

######  Theorem 3.7 (Deterministic polynomial time algorithm for approximate
evaluation of explicitly antisymmetrized two-layer neural network).

Let $f_{W,a}:\mathbb{R}^{nd}\to\mathbb{C}$ be given by a two-layer neural
network as in Theorem 3.6 with a rough or generalized rough activation
function, and let $\epsilon=n^{-O(1)}$. There exists a deterministic
polynomial-time algorithm $(W,a,b,x)\mapsto S_{W,a,b}(x)$ whose output is
exactly antisymmetric in $x$ and such that with probability $1-o(1)$ over $W$,

$\mathbb{E}_{a|W}[\|S_{W,a,0}-\mathcal{A}f_{W,a}\|_{\mathcal{N}}^{2}]\leq\epsilon\>\mathbb{E}_{a|W}[\|\mathcal{A}f_{W,a}\|_{\mathcal{N}}^{2}].$

We consider the examples of activation functions in Fig. 2. $\tanh$ is smooth,
so $\|\mathcal{A}f\|_{\mathcal{N}}^{2}$ decays super-polynomially with $n$
with the $\tanh$ or sigmoid activation function. The ReLU activation is rough
with tail decay $3$. By Theorem 3.6, $\|\mathcal{A}f\|_{\mathcal{N}}^{2}$ is
of order $\tilde{\Omega}(n^{-(3+6/d)})$ with the ReLU activation function. By
Theorem 3.7 there exists an efficient algorithm to compute the output of $f$
with inverse polynomial relative error when the activation function is chosen
to be ReLU.

The approximation algorithm in theorem 3.7 involves the approximate evaluation
of an integral over frequencies $\theta$.

######  Remark 3.8.

In the setting of the standard Xavier/He initializations, Theorems 3.5-3.7
show that a rough activation function is required to avoid the sign problem.
On the other hand it is still desirable to use smooth activation functions to
obtain a smooth wavefunction. In the context of a smooth activation function,
our results show that an initialization should be used in which the weights in
the first layer are larger than those on the typical Xavier/He
initializations. This re-scaling of the first layer need only be by an
algebraic222This is because the re-scaling factor can be chosen as the
frequency threshold used to prove theorem 3.6. factor $r=n^{O(1)}$. In this
setting the approximation algorithm of theorem 3.7 is unchanged except that
the infra-red truncation $t$ of the integral is replaced by $t/r$.

Using the smooth activation function $\tanh$ as an example, the modification
in remark 3.8 is equivalent to replacing $\tanh$ with $y\mapsto\tanh(ry)$
where $r$ grows with $n$.

##  4 Reduction and generic weights

We now present an outline of the proofs of the main theorems. Additional
details follow in sections A-9.1. We first reduce estimates of the magnitude
of $\mathcal{A}f$ to estimates on the magnitude of $\mathcal{A}\tau_{w}$.

######  Lemma 4.1.

For $f_{W,a}(x)$ given by the network (3) with the He initialization
(Definition 3.4),
$\mathbb{E}[\|\mathcal{A}f_{W,a}\|_{\rho}^{2}\>|W]=\frac{\tilde{c}}{m}\sum_{k=1}^{m}\|\mathcal{A}\tau_{w^{(k)}}\|_{\rho}^{2}$.
In particular,

$\mathbb{E}[\|\mathcal{A}f_{W,a}\|_{\rho}^{2}]=\tilde{c}\>\mathbb{E}[\|\mathcal{A}\tau_{w}\|_{\rho}^{2}],\qquad
w\sim\mathcal{N}(0,\frac{\tilde{c}}{nd}I_{nd})$ (7)

does not depend on $m$.

######  Proof 4.2.

Expand
$\|\mathcal{A}f_{W,a}\|_{\rho}^{2}=\sum_{k,l=1}^{m}a_{k}a_{l}\langle\mathcal{A}\tau_{w^{(k)}}|\mathcal{A}\tau_{w^{(l)}}\rangle_{\rho}$.
The $a_{k}\sim\mathcal{N}(0,\tilde{c}/m)$’s are independent so
$\mathbb{E}[a_{k}a_{l}]=\delta_{kl}\tilde{c}/m$, and

$\mathbb{E}[\|\mathcal{A}f_{W,a}\|_{\rho}^{2}\>|\>W]=\frac{\tilde{c}}{m}\sum_{k,l=1}^{m}\delta_{kl}\mathbb{E}[\langle\mathcal{A}\tau_{w^{(k)}}|\mathcal{A}\tau_{w^{(l)}}\rangle_{\rho}]=\frac{\tilde{c}}{m}\sum_{k=1}^{m}\|\mathcal{A}\tau_{w^{(k)}}\|_{\rho}^{2}.$
(8)

Taking the expectation over $W$ yields
$\mathbb{E}_{W,a}[\|\mathcal{A}f_{W,a}\|_{\rho}^{2}]=\tilde{c}\>\mathbb{E}[\|\mathcal{A}\tau_{v}\|_{\rho}^{2}]$.

The next definition characterizes the weights of the first layer with high
probability under the Xavier/He initializations.

######  Definition 4.3.

Fix a constant $C>1$. We say that $w\in\mathbb{R}^{nd}$ is _typical_ if
$\tilde{c}/2\leq\|w\|^{2}\leq 2\tilde{c}$ and
$\|w\|_{\infty}:=\max_{ij}|w_{ij}|\leq C\sqrt{\frac{\log(nd)}{nd}}$.

In particular a typical $w$ has $\|w\|=\Theta(1)$. We view $d$ as a constant,
so $\|w\|_{\infty}=O(\sqrt{(\log n)/n})$ for typical $w$. For lower bounds we
need an additional property of $w=w^{(k)}$ sampled from the Xavier/He
initializations, namely that the $w_{i}\in\mathbb{R}^{d}$ are sufficiently
separated. To see why this is needed, take the example where $w_{i}=w_{j}$ for
some $i\neq j$ which would imply $\mathcal{A}\tau_{w}\equiv 0$. We formalize
the separation property using the following quantity:

######  Definition 4.4.

For $w\in\mathbb{R}^{nd}$ write $\delta_{w}=\frac{1}{2}\min_{1\leq i<j\leq
n}\|w_{i}\pm w_{j}\|$ where the minimum is over both choices of sign $\pm$.

We then define weights with _typical_ separation:

######  Definition 4.5.

Fix a function $\delta(n)=o(n^{-(1/2+2/d)})$ as $n\to\infty$ (for concreteness
we let $\delta(n)=n^{-(1/2+2/d)}/\sqrt{\log n}$). We say that $v$ has typical
separation if $\delta_{v}\geq\delta(n)$. We say that $W\in\mathbb{R}^{m\times
nd}$ is _typical_ if each $w^{(k)}$ is typical and at least half the $w^{(k)}$
have typical separation.

In Appendix A we show that He/Xavier initialized weights generically have
typical separation:

######  Lemma 4.6.

Let $d$ be constant, let $m=O(n^{C^{\prime}})$ for some constant $C^{\prime}$,
and let $f$ be sampled as in Definition 3.4. Then $W$ is typical with
probability $1-o(1)$ for some constant $C$ in Definition 4.3 depending on
$C^{\prime}$. For such $W$,

$\frac{\tilde{c}}{2}\inf_{w\in
S^{\prime}}\|\mathcal{A}\tau_{w}\|_{\rho}^{2}\leq\mathbb{E}_{a|W}[\|\mathcal{A}f\|_{\rho}^{2}]\leq\tilde{c}\sup_{w\in
S}\|\mathcal{A}\tau_{w}\|_{\rho}^{2},$ (9)

where $S$ is the set of typical $w\in\mathbb{R}^{nd}$ and $S^{\prime}\subset
S$ is the set of typical $w$ which have typical separation.

##  5 Overlap kernel induced by Fourier decomposition

Consider the case when the activation function is a complex exponential
function. Let “$\operatorname{expression}([\mathbf{x}])$” denote the function
$x\mapsto\operatorname{expression}(x)$. Then
$e^{iw\cdot[\mathbf{x}]}=\otimes_{i=1}^{n}e^{iw_{i}\cdot[\mathbf{x}]_{i}}$ is
a product of single-particle functions, so antisymmetrizing it yields a Slater
determinant,

$\mathcal{A}(e^{iw\cdot[\mathbf{x}]})=\mathcal{A}(\otimes_{i=1}^{n}e^{iw_{i}\cdot[\mathbf{x}]_{i}})=\wedge_{i=1}^{n}e^{iw_{i}\cdot[\mathbf{x}]_{i}},$
(10)

where the RHS is defined as
$\frac{1}{\sqrt{n!}}\det((e^{iw_{i}\cdot[\mathbf{x}]_{j}})_{ij})$. The overlap
between two Slater determinants is the determinant of the _overlap matrix_
[17], meaning that

$\langle\mathcal{A}e^{iv\cdot[\mathbf{x}]}|\mathcal{A}e^{iw\cdot[\mathbf{x}]}\rangle_{\rho}=\langle\wedge_{i}e^{iv_{i}\cdot[\mathbf{x}]}|\wedge
e^{iw_{i}\cdot[\mathbf{x}]}\rangle_{\rho}=\det B^{(v,w)},$ (11)

where $B^{(v,w)}\in\mathbb{R}^{n\times n}$ is given by $B^{(v,w)}_{ij}=\langle
e^{iv_{i}\cdot[\mathbf{x}]}|e^{iw_{j}\cdot[\mathbf{x}]}\rangle_{\rho}$. We can
evaluate this as

$B^{(v,w)}_{ij}=\mathbb{E}_{X\sim\rho}[e^{-i(v_{i}-w_{j})\cdot
X}]=\mathfrak{F}{\rho}(v_{i}-w_{j}).$ (12)

Here we have defined the _un-normalized_ Fourier transform $\mathfrak{F}{}$
(also denoted by $\mathfrak{F}_{d}{}$) on $\mathbb{R}^{d}$ by
$\mathfrak{F}{\rho}(v)=\int_{\mathbb{R}^{d}}e^{-iv\cdot x}d\rho(x)$. In
particular $\mathfrak{F}{\rho}(0)=1$, and
$\mathfrak{F}{\rho}=(2\pi)^{d/2}\widehat{\rho}$.

By the Fourier inversion formula (4) we have the identity of functions on
$\mathbb{R}^{nd}$

$\tau_{w}(x)=\frac{1}{\sqrt{2\pi}}\int_{|\theta|>\epsilon}\widehat{\tau}(\theta)e^{i\theta
w\cdot x}d\theta+p(w\cdot x)+C_{\epsilon}+O(\epsilon g(w\cdot x)),$ (13)

We use the fact that low-degree polynomials vanish upon antisymmetrization:

######  Lemma 5.1 ([15] lemma 7).

If $f:\mathbb{R}^{nd}\to\mathbb{C}$ is a polynomial of degree $\deg f\leq
n-2$, then $\mathcal{A}f\equiv 0$. In particular $\mathcal{A}\tau_{w}\equiv 0$
if $\tau$ is an activation function which is a polynomial of degree
$\deg\tau\leq n-2$.

We antisymmetrize (13) and apply Lemma 5.1 which yields that for $n\geq\deg
p+2$,

$\mathcal{A}\tau_{w}=\lim_{\epsilon\to
0}\mathcal{A}{\tau}^{\mathrm{HP}(\epsilon)}=\lim_{\epsilon\to
0}\frac{1}{\sqrt{2\pi}}\int_{|\theta|>\epsilon}\widehat{\tau}(\theta)\mathcal{A}(e^{i\theta
w\cdot[\mathbf{x}]})d\theta,$ (14)

where convergence is in the $\mathcal{L}^{2}(\mathbb{R}^{nd};\rho_{n})$-norm.

######  Definition 5.2 (Overlap kernel).

Define
$\operatorname{D}_{\rho}:\mathbb{R}^{nd}\times\mathbb{R}^{nd}\to\mathbb{C}$ by
$\operatorname{D}_{\rho}(v,w)=\det B^{(v,w)}$, where
$B^{(v,w)}\in\mathbb{C}^{n\times n}$ is given by (12). Given a vector of
weights $w\in\mathbb{R}^{nd}$ define
$D_{\rho}^{(w)}:\mathbb{R}^{2}\to\mathbb{C}$ by
$D_{\rho}^{(w)}(\theta,\tilde{\theta})=\operatorname{D}_{\rho}(\theta
w,\tilde{\theta}w)$.

Note that $D_{\rho}^{(w)}$ depends on the envelope function. Eq. (11) shows
that $D_{\rho}^{(w)}(\theta,\tilde{\theta})=\langle\mathcal{A}e^{i\theta
w\cdot[\mathbf{x}]}|\mathcal{A}e^{i\tilde{\theta}w\cdot[\mathbf{x}]}\rangle_{\rho}$.
The expansion (14) then yields Lemma 5.3:

######  Lemma 5.3.

If
$\iint_{\mathbb{R}^{2}}|\widehat{\tau}(\theta)\widehat{\tau}(\tilde{\theta})D_{\rho}^{(w)}(\theta,\tilde{\theta})|d\theta
d\tilde{\theta}<\infty$, then

$\|\mathcal{A}\tau_{w}\|_{\rho}^{2}=\frac{1}{2\pi}\iint_{\mathbb{R}^{2}}\overline{\widehat{\tau}(\theta)}{\widehat{\tau}(\tilde{\theta})}D_{\rho}^{(w)}(\theta,\tilde{\theta})d\theta
d\tilde{\theta}.$ (15)

##  6 Properties of the overlap kernel

On the diagonal $v=w$ we have $0\leq\operatorname{D}_{\rho}(w,w)\leq 1$.
Indeed, $B_{ij}^{(w,w)}$ is the Gram matrix of vectors
$\mathcal{A}e^{iw_{i}\cdot[\mathbf{x}]}\in\mathcal{L}^{2}(\mathbb{R}^{d};\rho)$
so it satisfies
$\det(B^{(w,w)})\leq\prod_{i}B_{ii}^{(w,w)}=(\mathfrak{F}_{d}{\rho}(0))^{n}=1$
by Hadamard’s theorem for positive semidefinite matrices.
$\operatorname{D}_{\rho}(v,w)$ is a positive semidefinite kernel because it is
a (infinite) Gram matrix of vectors
$\mathcal{A}e^{iw\cdot[\mathbf{x}]}\in\mathcal{L}^{2}(\mathbb{R}^{nd};\rho_{n})$.
In particular,
$|\operatorname{D}_{\rho}(v,w)|^{2}\leq\operatorname{D}_{\rho}(v,v)\operatorname{D}_{\rho}(w,w)\leq
1$ for all $v,w\in\mathbb{R}^{nd}$. Specializing these observations to
$D_{\rho}^{(w)}$ yields $0\leq D_{\rho}^{(w)}(\theta,\theta)\leq 1$ on the
diagonal and $|D_{\rho}^{(w)}(\theta,\tilde{\theta})|^{2}\leq 1$ everywhere.

To approximate the behavior of $D_{\rho}^{(w)}$ at large $\theta$ and
$\tilde{\theta}$ we define a probability distribution $\rho_{w}$ on
$\mathbb{R}$.

######  Definition 6.1.

For any $w\in\mathbb{R}^{nd}$, let $\rho_{w}$ on $\mathbb{R}$ be the
distribution of $w\cdot X$ where $X\sim\rho_{n}$.

We expect $\mathcal{A}e^{i\theta v\cdot[\mathbf{x}]}$ to be roughly orthogonal
to $\mathcal{A}e^{i\tilde{\theta}v\cdot[\mathbf{x}]}$ when the frequencies
$\theta$ and $\tilde{\theta}$ are sufficiently different. We therefore expect
$D_{\rho}^{(w)}(\theta,\tilde{\theta})=\langle\mathcal{A}e^{i\theta
w\cdot[\mathbf{x}]}|\mathcal{A}e^{i\tilde{\theta}w\cdot[\mathbf{x}]}\rangle_{\rho}$
to vanish away from the diagonal $\tilde{\theta}=\theta$. Moreover, when
$\theta$ is large we expect the $n!$ terms in (1) to be roughly orthogonal, so
by Pythagoras’ theorem and considering the normalization factor $1/\sqrt{n!}$
we expect $D_{\rho}^{(w)}(\theta,\theta)=\|\mathcal{A}e^{i\theta
w\cdot[\mathbf{x}]}\|_{\rho}^{2}\approx\|e^{i\theta
w\cdot[\mathbf{x}]}\|_{\rho}^{2}=1$ for large $\theta$. We formalize this idea
by approximating $D_{\rho}^{(w)}(\theta,\tilde{\theta})$ with a convolution
kernel $\mathfrak{F}{\rho_{v}}(\theta-\tilde{\theta})$ when
$\max\\{|\theta|,|\tilde{\theta}|\\}\geq T$ for sufficiently large $T>0$. We
then apply the convolution theorem to obtain

######  Lemma 6.2.

Let $h={\tau}^{\mathrm{HP}(T)}$ be the high-passed activation function at
threshold $T>1$. Then,

$\|\mathcal{A}h_{w}\|_{\rho}^{2}=\|h_{w}\|_{\rho}^{2}+\varepsilon(T),$ (16)

with the error term
$|\varepsilon(T)|=O(n!\delta_{w}^{-2}\int_{\delta_{w}T}^{\infty}\epsilon_{\rho}(t)tdt)$,
$\epsilon_{\rho}(\theta)=\sup\\{|\mathfrak{F}{\rho}(y)|:y\in\mathbb{R}^{d},\|y\|\geq\theta\\}$.

Lemma 6.2 states that at sufficiently large threshold $T$ the magnitude of the
antisymmetrization of the high-passed activation function is approximately the
magnitude before antisymmetrization.

The $\delta_{w}$ in the error term was defined in Definition 4.4. The fast
decay of $\epsilon_{\rho}(\theta)$ compensates for the growth of the factor
$n!$ in (16), making the approximation meaningful at polynomially large $T$.

Figure 3:  Heatmap of $\mathbb{E}_{w}D_{\rho}^{(w)}(\theta,\tilde{\theta})$
where $w\sim\mathcal{N}(0,\frac{2}{nd}I_{nd})$ for $d=3$ and $n=2$. Positive
values are blue and negative values red.

###  6.1 Proof of Lemma 6.2

######  Lemma 6.3.

Let $\delta_{w}=\frac{1}{2}\min_{i\neq j}\|w_{i}\pm w_{j}\|$ and let
$\rho_{w}$ be as in Definition 6.1. Then,

$\displaystyle\begin{split}|D_{\rho}^{(w)}(\theta,\tilde{\theta})-\mathfrak{F}{\rho_{w}}(\theta-\tilde{\theta})|\leq
n!\>\epsilon_{\rho}\big{(}\delta_{w}\theta_{\operatorname{max}}\big{)},\end{split}$
(17)

where $\theta_{\operatorname{max}}=\max\\{|\theta|,|\tilde{\theta}|\\}$ and
$\epsilon_{\rho}(\theta)=\sup\\{|\mathfrak{F}_{d}{\rho}(y)|:y\in\mathbb{R}^{d},\|y\|\geq\theta\\}$.
$\mathfrak{F}{\rho_{w}}$ can be expressed in terms of the $nd$-dimensional
Fourier transform as
$\mathfrak{F}{\rho_{w}}(\theta)=\mathfrak{F}_{nd}{\rho_{n}}(\theta w)$.

######  Proof 6.4.

By definition we have

$D_{\rho}^{(w)}(\theta,\tilde{\theta})=\det(\mathfrak{F}_{d}{\rho}(\theta
w_{i}-\tilde{\theta}w_{j})_{ij})=\sum_{\pi\in
S_{n}}(-1)^{\pi}\mathfrak{F}_{nd}{\rho_{n}}(\theta w-\tilde{\theta}\pi(w)).$

The $\pi=1$ term equals

$\mathfrak{F}_{nd}{\rho_{n}}((\theta-\tilde{\theta})w)=\mathfrak{F}{\rho_{w}}(\theta-\tilde{\theta}).$
(18)

To verify the identity (18) and the claim at the end of the lemma, write

$\mathfrak{F}_{nd}{\rho_{n}}(\theta w)=\mathbb{E}_{X\sim\rho_{n}}[e^{-i(\theta
w)\cdot X}]=\mathbb{E}_{X\sim\rho_{n}}[e^{-i\theta(w\cdot
X)}]=\mathbb{E}_{y\sim\rho_{w}}[e^{-i\theta
y}]=\mathfrak{F}{\rho_{w}}(\theta).$

The difference on the LHS of (17) is exactly $\varepsilon=\sum_{\pi\neq
1}(-1)^{\pi}\mathfrak{F}_{nd}{\rho_{n}}(\theta w-\tilde{\theta}\pi(w))$. Apply
the triangle inequality and use the fact that
$\|\epsilon_{\rho}\|_{\infty}=\|\mathfrak{F}_{nd}{\rho_{n}}\|_{\infty}\leq 1$
because $\rho$ is a probability distribution to obtain

$\displaystyle\begin{split}|\varepsilon|&\leq n!\max_{\pi\neq
1}|\mathfrak{F}_{nd}{\rho_{n}}(\theta w-\tilde{\theta}\pi(w))|\\\ &\leq
n!\>\max_{\pi\neq 1}\prod_{i=1}^{n}\epsilon_{\rho}\big{(}\|\theta
w_{i}-\tilde{\theta}\pi(w)_{i}\|\big{)}\\\ &\leq n!\>\max_{\pi\neq
1}\min_{i}\epsilon_{\rho}\big{(}\|\theta
w_{i}-\tilde{\theta}\pi(w)_{i}\|\big{)}\leq
n!\>\epsilon_{\rho}(|\theta|\tilde{\delta}(w)),\end{split}$ (19)

where

$\displaystyle\tilde{\delta}(v)$
$\displaystyle=\min_{\tilde{\theta}}\min_{\pi\neq
1}\max_{i}\|v_{i}-\tilde{\theta}\pi(v)_{i}\|.$ (20)

We show that $\tilde{\delta}_{w}\geq\delta_{w}$ in Lemma 6.5. The result
follows from symmetry in $\theta$ and $\tilde{\theta}$.

######  Lemma 6.5.

Let $\tilde{\delta}_{w}:=\min_{\tilde{\theta}\in\mathbb{R}}\min_{\pi\neq
1}\max_{i}\|w_{i}-\tilde{\theta}\pi(w)_{i}\|$ Then
$\tilde{\delta}_{w}\geq\delta_{w}$.

######  Proof 6.6.

Let $\tilde{\theta}$ and $\sigma=\pi^{-1}\neq 1$ be arbitrary. We need to show
that $\|w_{i}-\tilde{\theta}w_{\sigma(i)}\|\geq\delta_{w}$ for some $i$.

Since $\sigma\neq 1$ there exists $i$ such that $\sigma(i)\neq i$, therefore
$\|w_{i}-sw_{\sigma(i)}\|\geq 2\delta_{w}$ for $s=\pm 1$. If
$\|w_{i}-\tilde{\theta}w_{\sigma(i)}\|\geq\delta_{w}$ then we have found $i$
and we are done. Otherwise, let $s=\operatorname{sign}\tilde{\theta}$. Then,

$\displaystyle\begin{split}2\delta_{w}\leq\|w_{i}-sw_{\sigma(i)}\|&\leq\|w_{i}-\tilde{\theta}w_{\sigma(i)}\|+\|\tilde{\theta}w_{\sigma(i)}-sw_{\sigma(i)}\|\\\
&=\|w_{i}-\tilde{\theta}w_{\sigma(i)}\|+|\tilde{\theta}-s|\cdot\|w_{\sigma(i)}\|\\\
&<\delta_{w}+|\tilde{\theta}-s|\max_{j}\|w_{j}\|.\end{split}$ (21)

Rearranging (21) we yields

$|\tilde{\theta}-s|R>\delta_{w},\qquad R=\max_{j}\|w\|_{j}.$ (22)

Pick $j$ such that $\|w_{j}\|=R$. If $|\tilde{\theta}|\geq 1$ then (22) says
$(|\tilde{\theta}|-1)R>\delta_{w}$. Let $i=\pi(j)$ so that $\sigma(i)=j$ and
$\|w_{\sigma(i)}\|=R$. Then,

$\|w_{i}-\tilde{\theta}w_{\sigma(i)}\|\geq\|\tilde{\theta}w_{\sigma(i)}\|-\|w_{i}\|=|\tilde{\theta}|R-\|w_{i}\|\geq(|\tilde{\theta}|-1)R\geq\delta_{w}.$

If instead $|\tilde{\theta}|<1$ then (22) says
$(1-|\tilde{\theta}|)R>\delta_{w}$. We then use

$\|w_{j}-\tilde{\theta}w_{\sigma(j)}\|\geq\|w_{j}\|-\|\tilde{\theta}w_{\sigma(j)}\|=R-\|\tilde{\theta}w_{\sigma(j)}\|\geq(1-|\tilde{\theta}|)R\geq\delta_{w}.$

######  Proof 6.7 (Proof of Lemma 6.2).

By (15) we have
$\|\mathcal{A}h_{w}\|_{\rho}^{2}=\frac{1}{2\pi}\iint_{|\theta|,|\tilde{\theta}|\geq
T}D_{\rho}^{(w)}(\theta,\tilde{\theta})\overline{\widehat{\tau}(\theta)}\widehat{\tau}(\tilde{\theta})d\theta
d\tilde{\theta}$. Apply Lemma 6.3 to approximate
$D_{\rho}^{(w)}(\theta,\tilde{\theta})$ by
$\mathfrak{F}{\rho_{w}}(\theta-\tilde{\theta})$. Recall that
$\widehat{h}=\widehat{\tau}\odot 1_{\mathbb{R}\backslash[-T,T]}$. The
resulting approximation is, by the convolution theorem and Plancherel’s
identity,

$\displaystyle\begin{split}\frac{1}{2\pi}\iint\mathfrak{F}{\rho_{w}}(\theta-\tilde{\theta})\overline{\widehat{h}(\theta)}\widehat{h}(\tilde{\theta})d\theta
d\tilde{\theta}.=&\frac{1}{2\pi}\int\overline{\widehat{h}(\theta)}\Big{(}\mathfrak{F}{\rho_{w}}*\widehat{h}\Big{)}(\theta)d\theta.\\\
=&\int|h(y)|^{2}\rho_{w}(y)dy.=\mathbb{E}_{X\sim\rho_{n}}[|h(w\cdot
X)|^{2}]=\|h_{w}\|_{\rho}^{2}.\end{split}$ (23)

$\widehat{\tau}$ is bounded on $\mathbb{R}\backslash[-T,T]$ by assumption. The
error of the approximation is then bounded by a constant times

$\displaystyle\iint_{|\theta|,|\tilde{\theta}|\geq
T}|D_{\rho}^{(w)}(\theta,\tilde{\theta})-\mathfrak{F}{\rho_{w}}(\theta-\tilde{\theta})|d\theta
d\tilde{\theta}\leq
8\int_{T}^{\infty}\int_{T}^{\theta}n!\epsilon_{\rho}\big{(}\delta_{w}\theta\big{)}d\tilde{\theta}d\theta\leq
8n!\int_{T}^{\infty}\epsilon_{\rho}\big{(}\delta_{w}\theta\big{)}\>\theta
d\theta.$

The error bound follows by substituting $t=\delta_{w}\theta$.

###  6.2 Upper bound for Gaussian envelopes

Lemma 6.2 explains the behavior of $D_{\rho}^{(w)}(\theta,\tilde{\theta})$ at
large $\theta$. We now establish that it vanishes for small $\theta$. When the
envelope is the standard Gaussian $\rho=\mathcal{N}$, the overlap kernel takes
the following form:

$\operatorname{D}_{\mathcal{N}}(v,w)=e^{-\frac{\|v\|^{2}+\|w\|^{2}}{2}}\det\big{(}(e^{v_{i}\cdot
w_{j}})_{ij}\big{)}.$ (24)

An upper bound on $\operatorname{D}_{\mathcal{N}}$ was obtained in [15,
Proposition 11]:

######  Proposition 6.8.

Let $\nu=2\sqrt{d\|v\|_{\infty}\|w\|_{\infty}}$. Then, $\det((e^{v_{i}\cdot
w_{j}})_{ij})\leq(\nu/2)^{pn}$ for $\nu\leq 1$, where $p$ is any integer such
that $\binom{p+d-1}{d}\leq n/2$ and $p!\geq 4n^{2}$.

The proof of proposition 6.8 is recalled from [15] in section B. It works by
decomposing $(e^{v_{i}\cdot w_{j}})_{ij}=\sum_{k=0}^{\infty}Q_{k}$ and
bounding the ranks and operator norms of the terms $Q_{k}$. For
$L=\sum_{k=1}^{p-1}\operatorname{rank}Q_{k}$, the $L$-th eigenvalue is then
bounded as the tail sum $\sum_{k=p}^{\infty}\|Q_{k}\|$. Taking the product of
the eigenvalues yields the bound on (24).

Combining proposition 6.8 with the triangle inequality yields:

######  Lemma 6.9.

Let $\ell={\tau}^{\mathrm{LP}(t)}$ be the low-pass at threshold
$t=(2\sqrt{d}\|w\|_{\infty})^{-1}$. If $w$ is typical then
$t=\Omega(\sqrt{n/\log n})$ and
$\|\mathcal{A}\ell_{w}\|_{\mathcal{N}}=O(2^{-\Omega(n^{1+1/d})})$.

##  7 Proof of Theorem 3.5

We specialize the quantities of Lemma 6.2 to the case of a Gaussian envelope.
For the Gaussian envelope $\rho=\mathcal{N}(0,I_{d})$ we have
$\mathfrak{F}_{d}{\rho}(v)=e^{-\|v\|^{2}/2}$,
$\mathfrak{F}{\rho_{w}}(\theta)=e^{-\|w\|^{2}\theta^{2}/2}$, and
$\epsilon_{\rho}(\theta)=e^{-\theta^{2}/2}$. The integral in the error term of
Lemma 6.2 becomes
$\int_{\delta_{w}T}^{\infty}e^{-t^{2}/2}tdt=e^{-(\delta_{w}T)^{2}/2}$, so we
get the approximation

$\|\mathcal{A}h_{w}\|_{\mathcal{N}}^{2}=\|h_{w}\|_{\mathcal{N}}^{2}+O(\delta_{w}^{-2}e^{-\delta_{w}^{2}T^{2}/2+n\log
n}).$ (25)

We have the two following expressions for $D_{\mathcal{N}}^{(w)}$.

$\displaystyle D_{\mathcal{N}}^{(w)}(\theta,\tilde{\theta})$
$\displaystyle=\det[(e^{-\frac{1}{2}\|\theta
w_{i}-\tilde{\theta}w_{j}\|^{2}})_{ij}]=e^{-\frac{\theta^{2}+\tilde{\theta}^{2}}{2}\|w\|^{2}}\det[(e^{\theta\tilde{\theta}w_{i}\cdot
w_{j}})_{ij}].$ (26)

It follows from (26) that $D_{\mathcal{N}}^{(w)}(\theta,\tilde{\theta})$ can
be determined from its values on the diagonal and anti-diagonal
$\tilde{\theta}=\pm\theta$. More precisely we have (27),

$D_{\mathcal{N}}^{(w)}(\theta,\tilde{\theta})=e^{-\frac{\|w\|^{2}}{2}(|\theta|-|\tilde{\theta}|)^{2}}D_{\mathcal{N}}^{(w)}(\theta_{\operatorname{g.m.}},\pm\theta_{\operatorname{g.m.}}),$
(27)

where the geometric mean
$\theta_{\operatorname{g.m.}}={|\theta\tilde{\theta}|}^{1/2}$ and $\pm$ is the
sign of $\theta\tilde{\theta}$. To show (27) apply the rightmost expression of
(26) on both sides and note that the determinants are equal. In particular we
have that $D_{\mathcal{N}}^{(w)}$ decays away from the diagonal and anti-
diagonal,

$|D_{\mathcal{N}}^{(w)}(\theta,\tilde{\theta})|\leq
e^{-\frac{\|w\|^{2}}{2}(|\theta|-|\tilde{\theta}|)^{2}}.$ (28)

The bound (28) gives concentration around the diagonal everywhere and not only
for large $\theta,\tilde{\theta}$ as Lemma 6.3. Integrating (28) yields:

######  Lemma 7.1.

Let $h={\tau}^{\mathrm{HP}(t)}$ be the high-passed activation function at
$t>1$. Then,
$\|\mathcal{A}h_{w}\|_{\mathcal{N}}^{2}\leq\frac{4}{\sqrt{2\pi}\|w\|}\mathfrak{T}_{\widehat{\tau}}(t)$.
So $\|\mathcal{A}h_{w}\|_{\mathcal{N}}^{2}=O(t^{-K})$ for typical $w$.

######  Proof 7.2.

Write the LHS as a double integral over $|\theta|,|\tilde{\theta}|\geq t$ as
in (15). By (28),

$\displaystyle\frac{1}{2\pi}\iint_{\tilde{\theta}>\theta>t}D_{\mathcal{N}}^{(w)}(\theta,\tilde{\theta})|\widehat{\tau}(\theta)\widehat{\tau}(\tilde{\theta})|d\theta
d\tilde{\theta}$
$\displaystyle=\frac{1}{2\pi}\int_{0}^{\infty}e^{-\frac{\|w\|^{2}s^{2}}{2}}\int_{t}^{\infty}|\widehat{\tau}(\theta)\widehat{\tau}(s+\theta)|d\theta
ds$ (29)
$\displaystyle\leq\frac{1}{2\pi}\int_{0}^{\infty}e^{-\frac{\|w\|^{2}s^{2}}{2}}ds\int_{t}^{\infty}|\widehat{\tau}(\theta)|^{2}d\theta$
(30)
$\displaystyle=\frac{1}{2\sqrt{2\pi}\|w\|}\int_{t}^{\infty}|\widehat{\tau}(\theta)|^{2}d\theta,$
(31)

where (30) follows from Cauchy-Schwartz. The same bound holds for each of $8$
regions in the $\theta,\tilde{\theta}$-plane.

For typical $w$ choose threshold $t=\Omega(\sqrt{n/\log n})$ as in Lemma 6.9
and decompose $\mathcal{A}\tau_{w}=\mathcal{A}\ell_{w}+\mathcal{A}h_{w}$.
Apply Lemma 6.9 and Lemma 7.1 to obtain the following corollary, which implies
Theorem 3.5.

######  Corollary 7.3.

If $\tau$ has frequency tail decay $K<\infty$ then
$\|\mathcal{A}\tau_{w}\|_{\mathcal{N}}^{2}=\tilde{O}(n^{-K/2})$ for typical
$w$. If $\tau$ is smooth ($K=\infty$), then
$\|\mathcal{A}\tau_{w}\|_{\mathcal{N}}^{2}=n^{-\omega(1)}$ for typical $w$.

##  8 Proof of Theorem 3.6

For the Gaussian envelope function we get a more explicit form of the error
term in Lemma 6.2. To prove the lower bound we pick an appropriate $T$ based
on this expression and decompose $\tau$ into $\ell={\tau}^{\mathrm{LP}(T)}$
and $h={\tau}^{\mathrm{HP}(T)}$. We then expand
$\|\mathcal{A}\ell+\mathcal{A}h\|_{\mathcal{N}}^{2}$ and use that
$\|\mathcal{A}\ell\|_{\mathcal{N}}^{2}\geq 0$ to get
$\|\mathcal{A}\tau_{w}\|_{\mathcal{N}}^{2}\geq\|\mathcal{A}h_{w}\|_{\mathcal{N}}^{2}-2|\langle\mathcal{A}\ell_{w}|\mathcal{A}h_{w}\rangle_{\mathcal{N}}|$.
The result follows by bounding
$|\langle\mathcal{A}\ell_{w}|\mathcal{A}h_{w}\rangle_{\mathcal{N}}|$ and
applying Lemma 6.2 to lower-bound $\|\mathcal{A}h_{w}\|_{\mathcal{N}}$.

######  Lemma 8.1.

For activation functions satisfying Item 1 of Definition C.1 we have that

$\|\mathcal{A}\tau_{w}\|_{\mathcal{N}}^{2}\geq\|h^{(T)}_{w}\|_{\mathcal{N}}^{2}-O(e^{-n\log
n})+o(\mathfrak{T}_{\widehat{\tau}}(T)).$ (32)

for $T=\frac{2}{\delta_{v}}(\sqrt{n\log n+\log(1/\delta_{v})})$ and typical
$w$.

######  Proof 8.2.

Let $\ell^{(T)}={\tau}^{\mathrm{LP}(T)}$ and
$h^{(T)}={\tau}^{\mathrm{HP}(T)}$. As discussed above we have the lower bound

$\|\mathcal{A}\tau_{w}\|_{\mathcal{N}}^{2}\geq\|\mathcal{A}h^{(T)}_{w}\|_{\mathcal{N}}^{2}-2|\langle\mathcal{A}\ell^{(T)}_{w}|\mathcal{A}h^{(T)}\rangle_{\mathcal{N}}|\geq\|h^{(T)}_{w}\|_{\mathcal{N}}^{2}-e^{-n\log
n}-2|\langle\mathcal{A}\ell^{(T)}_{w}|\mathcal{A}h^{(T)}_{w}\rangle_{\mathcal{N}}|,$
(33)

We further divide the low-frequency part into $|\theta|$ in $[0,1]$,
$[1,T/2]$, and $[T/2,T]$. We write $\alpha^{(t,T)}=h^{(t)}-h^{(T)}$. Then,

$|\langle\mathcal{A}\ell^{(T)}_{w}|\mathcal{A}h^{(T)}_{w}\rangle_{\mathcal{N}}|\leq\|\mathcal{A}\ell^{(1)}_{w}\|_{\mathcal{N}}\|\mathcal{A}h^{(T)}_{w}\|_{\mathcal{N}}+|\langle\mathcal{A}\alpha^{(1,T/2)}_{w}|\mathcal{A}h^{(T)}_{w}\rangle_{\mathcal{N}}+\langle\mathcal{A}\alpha^{(T/2,T)}_{w}|\mathcal{A}h^{(T)}_{w}\rangle_{\mathcal{N}}|.$
(34)

By applying the polarization identity to (15) we obtain the overlap between
the antisymmetrization with different activation functions, so by the bound
(28) on $D_{\mathcal{N}}^{(w)}(\theta,\tilde{\theta})$,

$\displaystyle|\langle\mathcal{A}\alpha^{(T/2,T)}_{w}|\mathcal{A}h^{(T)}_{w}\rangle_{\mathcal{N}}|$
$\displaystyle\leq\frac{(\sup_{|\theta|\geq
T/2}|\widehat{\tau}(\theta)|)^{2}}{2\pi}\int_{T/2<|\theta|<T}\int_{T<|\tilde{\theta}|}e^{-\frac{\|w\|^{2}}{2}(|\tilde{\theta}|-|\theta|)^{2}}d\tilde{\theta}d\theta$
(35) $\displaystyle\leq\frac{4(\sup_{|\theta|\geq
T/2}|\widehat{\tau}(\theta)|)^{2}}{2\pi}\int_{T/2<\theta<T}\int_{T-\theta}^{\infty}e^{-\frac{\|w\|^{2}}{2}t^{2}}dtd\theta$
(36) $\displaystyle=\frac{4(\sup_{|\theta|\geq
T/2}|\widehat{\tau}(\theta)|)^{2}}{2\pi}\int_{0}^{\infty}\min\\{t,T/2\\}e^{-\frac{\|w\|^{2}}{2}t^{2}}dt$
(37) $\displaystyle\leq\frac{4\sup_{|\theta|\geq
T/2}|\widehat{\tau}(\theta)|^{2}}{2\pi}\int_{0}^{\infty}te^{-\frac{\|w\|^{2}t^{2}}{2}}dt$
(38) $\displaystyle=\frac{2\sup_{|\theta|\geq
T/2}|\widehat{\tau}(\theta)|^{2}}{\pi\|w\|^{2}},$ (39)

where in (38) the factor $4$ comes from the choice of signs of
$\theta,\tilde{\theta}$, and we have substituted $t=\tilde{\theta}-\theta$. We
apply Item 1 of Definition C.1 to obtain that

$|\langle\mathcal{A}\alpha^{(T/2,T)}_{w}|\mathcal{A}h^{(T)}_{w}\rangle_{\mathcal{N}}|=o(\mathfrak{T}_{\widehat{\tau}}(T)/\|w\|^{2}).$
(40)

For the first term on the RHS of (34) we have for $T$ sufficiently large (so
that $|\widehat{\tau}(\theta)\widehat{\tau}(\tilde{\theta})|\leq 2\pi$ for
$|\theta|>1$ and $|\tilde{\theta}|>T$),

$\displaystyle\begin{split}|\langle\mathcal{A}\alpha^{(1,T/2)}_{w}|\mathcal{A}h^{(T)}_{w}\rangle_{\mathcal{N}}|&\leq\int_{1<|\theta|<T/2}\int_{T<|\tilde{\theta}|}e^{-\frac{\|w\|^{2}}{2}(|\tilde{\theta}|-|\theta|)^{2}}d\tilde{\theta}d\theta\\\
&\leq\frac{T}{2}\int_{T/2}^{\infty}e^{-\frac{\|w\|^{2}t^{2}}{2}}dt\\\
&\leq\frac{e^{-\frac{\|w\|^{2}T^{2}}{8}}}{\|w\|^{2}}.\end{split}$ (41)

By (40) and (41),
$|\langle\alpha^{(1,T/2)}_{w}|h^{(T)}_{w}\rangle_{\mathcal{N}}+\langle\alpha^{(T/2,T)}_{w}|h^{(T)}_{w}\rangle_{\mathcal{N}}|=O(e^{-\Omega(T^{2})})+o(\mathfrak{T}_{\widehat{\tau}}(T))$
for typical $w$. Finally, for typical $w$ we have $t>1$ in Lemma 6.9 and
$\|h^{(T)}_{w}\|_{\mathcal{N}}=O(t^{-K})=O(1)$ by Lemma 7.1, so
$\|\ell^{(1)}_{w}\|_{\mathcal{N}}\|h^{(T)}_{w}\|_{\mathcal{N}}=O(\|\ell^{(t)}_{w}\|_{\mathcal{N}})=2^{-\Omega(n^{1+1/d})}$.
The claim follows by substituting back into (33) and (34).

######  Proof 8.3 (Proof of Theorem 3.6).

By Lemma 4.6 it suffices to show the claim for $f=\tau_{w}$ where $w$ is
typical and has typical separation.

By the convolution theorem (23) and the expression
$\mathfrak{F}{\rho_{v}}(\theta)=e^{-\|v\|^{2}\theta^{2}/2}$ for the Gaussian
case we have

$\|h^{(T)}_{w}\|_{\mathcal{N}}^{2}=\frac{1}{2\pi}\iint_{|\theta|,|\tilde{\theta}|>T}e^{-\|w\|^{2}(\theta-\tilde{\theta})^{2}/2}\overline{\widehat{\tau}(\theta)}\widehat{\tau}(\tilde{\theta})d\theta
d\tilde{\theta}.$ (42)

We bound the contribution of the first quadrant to (42) from below. The same
argument holds for the third quadrant ($\theta,\tilde{\theta}<-T$). Let
$\sigma=1/\|w\|$. Then,

$\displaystyle\begin{split}\iint_{\theta,\tilde{\theta}>T}e^{-\|w\|^{2}(\theta-\tilde{\theta})^{2}/2}\overline{\widehat{\tau}(\theta)}\widehat{\tau}(\tilde{\theta})d\theta
d\tilde{\theta}&=2\operatorname{Re}\int_{T}^{\infty}\overline{\widehat{\tau}(\theta)}\int_{\theta}^{\infty}e^{-\|w\|^{2}(\tilde{\theta}-\theta)^{2}/2}\widehat{\tau}(\tilde{\theta})d\tilde{\theta}d\theta\\\
&=2\operatorname{Re}\int_{T}^{\infty}\overline{\widehat{\tau}(\theta)}\int_{\theta}^{\infty}e^{-\frac{(\tilde{\theta}-\theta)^{2}}{2\sigma^{2}}}\widehat{\tau}(\tilde{\theta})d\tilde{\theta}d\theta\\\
&=\sqrt{2\pi}\sigma\int_{T}^{\infty}\operatorname{Re}\Big{(}\overline{\widehat{\tau}(\theta)}\mathbb{E}[\widehat{\tau}(\theta+|Y|)]\Big{)}d\theta,\end{split}$
(43)

where $Y\sim\mathcal{N}(0,\sigma^{2})$. To obtain a lower bound on the
integrand we write

$\overline{\widehat{\tau}(\theta)}\cdot\mathbb{E}[\widehat{\tau}(\theta+|Y|)]=\|\widehat{\tau}(\theta)\|^{2}\cdot\frac{\mathbb{E}[\widehat{\tau}(\theta+|Y|)]}{\widehat{\tau}(\theta)}.$
(44)

So from Item 2 of Definition C.1 we then have a lower bound

$\operatorname{Re}\Big{(}\overline{\widehat{\tau}(\theta)}\cdot\mathbb{E}[\widehat{\tau}(\theta+|Y|)]\Big{)}=\|\widehat{\tau}(\theta)\|^{2}\operatorname{Re}\Big{(}\frac{\mathbb{E}[\widehat{\tau}(\theta+|Y|)]}{\widehat{\tau}(\theta)}\Big{)}=\Omega(|\widehat{\tau}(\theta)|^{2}),$
(45)

when $1/2\leq\sigma\leq 2$, i.e., when $1/4\leq\|w\|^{2}\leq 4$. This holds
because $w$ is typical (and because $1/2\leq\tilde{c}\leq 2$). For typical $w$
(42) and (45) then show that

$\displaystyle\begin{split}\iint_{\theta,\tilde{\theta}>T}e^{-\|w\|^{2}(\theta-\tilde{\theta})^{2}/2}\overline{\widehat{\tau}(\theta)}\widehat{\tau}(\tilde{\theta})d\theta
d\tilde{\theta}&=\Omega\Big{(}\int_{T}^{\infty}|\widehat{\tau}(\theta)|^{2}d\theta\Big{)}=\Omega(\mathfrak{T}_{\widehat{\tau}}(T)),\end{split}$
(46)

and the same lower bound holds for the integral over
$\theta,\tilde{\theta}<T$. Finally we bound the second quadrant
$\theta<-T,\tilde{\theta}>t$ (the fourth quadrant $\theta>T,\tilde{\theta}<-T$
is analogous) by writing

$\displaystyle\begin{split}\Big{|}\iint_{\theta<-T,\tilde{\theta}>T}e^{-\|w\|^{2}(\theta-\tilde{\theta})^{2}/2}\overline{\widehat{\tau}(\theta)}\widehat{\tau}(\tilde{\theta})d\theta
d\tilde{\theta}\Big{|}&=o\Big{(}\iint_{\theta<-T,\tilde{\theta}>T}e^{-\|w\|^{2}(\tilde{\theta}-\theta)^{2}/2}d\theta
d\tilde{\theta}\Big{)}\\\
&=o\Big{(}\int_{2T}^{\infty}te^{-\|w\|^{2}t^{2}/2}dt\Big{)}\\\
&=o(e^{-2\|w\|^{2}T^{2}}/\|w\|^{2})=o(e^{-T^{2}}),\end{split}$ (47)

where the last expression os for typical $w$. The identity (42), the lower
bound for the diagonal part (46), and the bound on the magnitude of the off-
diagonal part (47) show that
$\|h^{(T)}_{w}\|_{\mathcal{N}}^{2}=\Omega(\mathfrak{T}_{\widehat{\tau}}(T))=\Omega(T^{-K})$.
For typical $w$ with typical separation we have that $\delta_{w}\geq
n^{-(1/2+2/d)}/\sqrt{\log n}$ and $T\sim 2n^{1+2/d}\log n$, so
$\|h^{(T)}_{w}\|_{\mathcal{N}}^{2}=\tilde{\Omega}(n^{-(1+2/d)})$.

##  9 Efficient algorithm

Recall (10) which gives the antisymmetrization with an exponential activation
function as a determinant,
$\mathcal{A}(e^{iw\cdot[\mathbf{x}]})=\frac{1}{\sqrt{n!}}\det((e^{iw_{i}\cdot[\mathbf{x}]_{j}})_{ij})$.
Let $\ell^{(t)}={\tau}^{\mathrm{LP}(t)}$ and $h^{(T)}={\tau}^{\mathrm{HP}(T)}$
be the low-pass and high-pass of $\tau$ at thresholds $t<T$. We approximate
$\mathcal{A}\tau_{w}$ by removing the low-passed and high-passed components:
Apply (14) to ${\tau}^{\mathrm{HP}(t)}-{\tau}^{\mathrm{HP}(T)}$ to obtain
$\mathcal{A}\tau_{w}(x)=\alpha_{w}+\mathcal{A}\ell^{(t)}_{w}+\mathcal{A}h^{(T)}_{w}$,
where

$\displaystyle\alpha_{w}(x)$ $\displaystyle=\frac{1}{\sqrt{2\pi
n!}}\int_{[-T,T]\backslash[-t,t]}\widehat{\tau}(\theta)\det((e^{i\theta
w_{i}\cdot x_{j}})_{ij})d\theta.$ (48)

The integrand can be computed at a single $\theta$ in time $O(n^{3})$. Apply
Lemma 6.9 and Lemma 7.1 (with a different choice of threshold for the high-
pass) to bound the truncation error.

######  Lemma 9.1 (Truncation error bound).

Suppose $\widehat{\tau}$ has tail decay $K$. Let
$t=\max\\{\frac{1}{2\sqrt{d}\|w\|_{\infty}},1\\}$ and, given $\epsilon>0$, let
$T=\epsilon^{-1/K}$. Then
$\|\mathcal{A}\tau_{w}-\alpha_{w}\|_{\mathcal{N}}^{2}=O(2^{-\Omega(n^{1+1/d})}+\epsilon)$
for typical $w$.

We approximate $\alpha_{w}(x)$ by a sum $S_{w}(x)=\frac{1}{\sqrt{2\pi
n!}}\sum_{p=\pm 1,\ldots,\pm N}c_{p}\det((e^{i\theta_{p}w_{i}\cdot
x_{j}})_{ij})$, where $\theta_{1},\ldots,\theta_{N}$ are a discretization of
$[t,T]$.

###  9.1 Discretization error bound

Let $t=\Omega(1)$ and let $t=t_{0}<t_{1}<\cdots<t_{N}=T$ be evenly spaced and
for each $p=1,\ldots,N$ write

$I_{-p}=[-t_{p},-t_{p-1}],\qquad I_{p}=[t_{p-1},t_{p}].$

For $p=\pm 1,\ldots,\pm N$, let $\theta_{p}\in I_{p}$ and define

$c_{p}:=\int_{I_{p}}\widehat{\tau}(\theta)d\theta.$

For these evenly spaced $\theta_{p}$ and coefficients $c_{p}$, define
$\|\partial_{\theta}D_{\mathcal{N}}^{(w)}\|_{\infty}:=\sup_{\theta,\tilde{\theta}}|\frac{\partial}{\partial\tilde{\theta}}D_{\mathcal{N}}^{(w)}(\theta,\tilde{\theta})|$.
We then have

######  Lemma 9.2.

$\|S_{w}-\alpha_{w}\|_{\mathcal{N}}^{2}\leq\frac{2}{\pi}\frac{T}{N}\|\partial_{\theta}D_{\mathcal{N}}^{(w)}\|_{\infty}\big{(}\int_{t\leq|\theta|\leq
T}|\widehat{\tau}(\theta)|\big{)}^{2}=O(\frac{T}{N}\|\partial_{\theta}D_{\mathcal{N}}^{(w)}\|_{\infty})$.

######  Proof 9.3.

$S_{w}$ is exactly the antisymmetrization $\mathcal{A}s_{w}$ where

$s(t)=\frac{1}{\sqrt{2\pi}}\sum_{\pm q=1}^{N}c_{q}e^{i\theta_{q}t}.$

Passing from the truncated activation to its discretization incurs the error

$\|S_{w}-\tilde{\alpha}_{w}\|_{\mathcal{N}}^{2}=\|\mathcal{A}(s-\tau_{\operatorname{trc}})_{w}\|_{\mathcal{N}}^{2}=\frac{1}{2\pi}\iint_{\mathbb{R}^{2}}D_{\mathcal{N}}^{(w)}(\theta,\tilde{\theta})d\bar{\mu}(\theta)d\mu(\tilde{\theta}),$
(49)

where
$\tau_{\operatorname{trc}}=\tau-{\tau}^{\mathrm{LP}(1)}-{\tau}^{\mathrm{HP}(T)}$,
and $\mu$ is the complex-valued measure

$\mu(\theta)=\sum_{q}c_{q}\delta(\theta-\theta_{q})-(\widehat{\tau}(\theta)d\theta).$

For each square $S_{pq}=I_{p}\times I_{q}$,

$\displaystyle\begin{split}&\iint_{S_{pq}}D_{\mathcal{N}}^{(w)}(\theta,\tilde{\theta})d\bar{\mu}(\theta)d\mu(\tilde{\theta})\\\\[20.00003pt]
=&\overline{c_{p}}c_{q}D_{\mathcal{N}}^{(w)}(\theta_{p},\theta_{q})+\iint_{S_{pq}}D_{\mathcal{N}}^{(w)}(\theta,\tilde{\theta})\overline{\widehat{\tau}(\theta)}\widehat{\tau}(\tilde{\theta})d\theta
d\tilde{\theta}\\\
&-\overline{c_{p}}\int_{I_{q}}D_{\mathcal{N}}^{(w)}(\theta_{p},\tilde{\theta})\widehat{\tau}(\tilde{\theta})d\theta-
c_{q}\int_{I_{p}}D_{\mathcal{N}}^{(w)}(\theta,\theta_{q})\overline{\widehat{\tau}(\theta)}d\theta\\\\[20.00003pt]
=&\iint_{S_{pq}}\Big{[}D_{\mathcal{N}}^{(w)}(\theta_{p},\theta_{q})+D_{\mathcal{N}}^{(w)}(\theta,\tilde{\theta})-D_{\mathcal{N}}^{(w)}(\theta_{p},\tilde{\theta})-D_{\mathcal{N}}^{(w)}(\theta,\theta_{q})\Big{]}\>\overline{\widehat{\tau}(\theta)}\widehat{\tau}(\tilde{\theta})d\theta
d\tilde{\theta}\\\\[20.00003pt] \leq&\iint_{S_{pq}}\Big{[}2\max
D_{\mathcal{N}}^{(w)}(I_{p},I_{q})-2\min
D_{\mathcal{N}}^{(w)}(I_{p},I_{q})\Big{]}\>|\widehat{\tau}(\theta)\widehat{\tau}(\tilde{\theta})|d\theta
d\tilde{\theta}\\\\[20.00003pt]
=&2(\operatorname{diam}D_{\mathcal{N}}^{(w)}(I_{p},I_{q}))\int_{I_{p}}|\widehat{\tau}(\theta)|d\theta\int_{I_{q}}|\widehat{\tau}(\tilde{\theta})|d\tilde{\theta},\end{split}$
(50)

where $\operatorname{diam}(D_{\mathcal{N}}^{(w)}(I_{p},I_{q}))$ is the
diameter of the set
$D(I_{p},I_{q})=\\{D_{\mathcal{N}}^{(w)}(\theta,\tilde{\theta})\>|\>(\theta,\tilde{\theta})\in
I_{p}\times I_{q}\\}$. Let $\|\partial
D_{\mathcal{N}}^{(w)}\|_{\infty}=\sup_{\theta,\tilde{\theta}}\max\\{|\frac{\partial}{\partial\theta}D_{\mathcal{N}}^{(w)}(\theta,\tilde{\theta})|,|\frac{\partial}{\partial\tilde{\theta}}D_{\mathcal{N}}^{(w)}(\theta,\tilde{\theta})|\\}$
and let $t_{0}=1,\ldots,t_{N}=T$ be evenly spaced so that $|I_{p}|\leq T/N$.
Then by (50),

$\displaystyle\iint_{S_{pq}}D_{\mathcal{N}}^{(w)}(\theta,\tilde{\theta})d\mu(\theta)d\mu(\tilde{\theta})\leq$
$\displaystyle\frac{4T}{N}\|\partial
D_{\mathcal{N}}^{(w)}\|_{\infty}\int_{I_{p}}|\widehat{\tau}(\theta)|d\theta\int_{I_{q}}|\widehat{\tau}(\tilde{\theta})|d\tilde{\theta}.$
(51)

Summing over $p,q$ and applying (49) we get

$\|S_{w}-\tilde{\alpha}_{w}\|_{\mathcal{N}}^{2}\leq\frac{2}{\pi}\frac{T}{N}\|\partial
D_{\mathcal{N}}^{(w)}\|_{\infty}\Big{(}\int_{t\leq|\theta|\leq
T}|\widehat{\tau}(\theta)|\Big{)}^{2}.$

######  Lemma 9.4.

Let $B^{(v,w)}_{ij}=\mathfrak{F}{\rho}(v_{i}-w_{j})$ as in Definition 5.2.
Then, $|\frac{\partial}{\partial B_{ij}}\det B|\leq 1$ at any $B=B^{(v,w)}$.

######  Proof 9.5.

$\frac{\partial}{\partial B_{ij}}\det B=(-1)^{i+j}m^{B}_{i,j}$ where
$m^{B}_{i,j}$ is the $i,j$th minor of $B$. But $m^{B}_{ij}=\det
B^{(\tilde{v},\tilde{w})}$ where $\tilde{v}=(v_{i^{\prime}})_{i^{\prime}\neq
i}$ and $\tilde{w}=(w_{j^{\prime}})_{j^{\prime}\neq j}$, and $|\det
B^{(\tilde{v},\tilde{w})}|=|\operatorname{D}_{\mathcal{N}}(\tilde{v},\tilde{w})|\leq
1$ by the properties mentioned in Section 6.1.

######  Corollary 9.6.

$|\frac{\partial}{\partial\theta}D_{\mathcal{N}}^{(w)}(\theta,\tilde{\theta})|\leq
n^{3/2}\|w\|/\sqrt{e}$.

######  Proof 9.7.

By the chain rule,

$\frac{\partial}{\partial\theta}D_{\mathcal{N}}^{(w)}(\theta,\tilde{\theta})=\sum_{ij}\frac{\partial
B_{ij}(\theta w,\tilde{\theta}w)}{\partial\theta}\frac{\partial\det
B}{\partial B_{ij}},$

where

$\Big{|}\frac{\partial B_{ij}(\theta
w,\tilde{\theta}w)}{\partial\theta}\Big{|}=|w_{i}\cdot(\nabla\mathfrak{F}_{d}{\rho})(\theta
w_{i}-\tilde{\theta}w_{j})|\leq\|w_{i}\|\cdot\|\nabla\mathfrak{F}_{d}{\rho}\|_{\infty}$

Lemma 9.4 and the triangle inequality then imply that

$\Big{|}\frac{\partial}{\partial\theta}D_{\mathcal{N}}^{(w)}(\theta,\tilde{\theta})\Big{|}\leq
n\|\nabla\mathfrak{F}_{d}{\rho}\|_{\infty}\sum_{i}\|w_{i}\|\leq
n^{3/2}\|\nabla\mathfrak{F}_{d}{\rho}\|_{\infty}\|w\|,$

where the last inequality is by Cauchy-Schwarz. For
$\rho=\mathcal{N}(0,I_{d})$ we have
$\mathfrak{F}_{d}{\mathcal{N}}(w)=e^{-\|w\|^{2}/2}$ and
$\|\nabla\mathfrak{F}_{d}{\mathcal{N}}\|_{\infty}=1/\sqrt{e}$.

In the presence of bias terms $b_{k}$ in (3) we can efficiently compute an
approximation $S_{w,b}$ to the function
$\mathcal{A}\tau(w^{(k)}\cdot[\mathbf{x}]+b_{k})$ with the same error bound.
Indeed, the bias term results in a shift of the activation function which
corresponds to multiplying the Fourier transform by an oscillating phase.
Since the upper bounds do not depend on the phase of the Fourier transform,
the same truncation error bound applies. Theorem 3.5 holds for arbitrary bias
terms for the same reason.

######  Proof 9.8 (Proof of Theorem 3.7).

Because $\tau$ is rough we have
$\mathbb{E}[\|\mathcal{A}f\|_{\mathcal{N}}|W]=n^{-O(1)}$ with probability
$1-o(1)$. Given target relative error $\epsilon=n^{-O(1)}$ it suffices to
achieve absolute error
$\epsilon^{\prime}=\epsilon\cdot\mathbb{E}[\|\mathcal{A}f\|_{\mathcal{N}}|W]=n^{-O(1)}$.
$\|S_{w}-\mathcal{A}\tau_{w}\|_{\mathcal{N}}^{2}=O(\epsilon^{\prime}+n^{O(1)}\|\partial_{\theta}D_{\mathcal{N}}^{(w)}\|_{\infty}/N)$
by Lemma 9.1 and Lemma 9.2. Corollary 9.6 shows that
$\|\partial_{\theta}D_{\mathcal{N}}^{(w)}\|_{\infty}=n^{O(1)}$, so
$\|S_{w}-\mathcal{A}\tau_{w}\|_{\mathcal{N}}^{2}=O(\epsilon^{\prime}+n^{O(1)}/N)$.
It then suffices to pick $N=n^{O(1)}$. Let
$S_{W,a,b}=\sum_{k=1}^{m}a_{k}S_{w^{(k)},b_{k}}$ and apply Lemma 4.1 to the
difference $f_{W,a,b}-S_{W,a,b}$ to extend the termwise error bound to the sum
(3). The computational cost of evaluating $S_{w}(x)$ is $O(n^{3}N)$.

###  9.2 Numerical demonstration of Theorem 3.7

We numerically demonstrate Theorem 3.7 by approximating the anti-
symmetrization of a single neuron with the ReLU activation function (Figures 4
and 5). We compare the approximation $S_{w}$ given by Theorem 3.7 with the
explicit anti-symmetrization $\mathcal{A}\tau_{w}$. We use 100 sample points
$x\sim\mathcal{N}(0,I)$ to estimate the norm of the anti-symmetrized function
and the distance between the true anti-symmetrization and its efficient
approximation. In our implementation we used Gauss-Legendre quadrature to
estimate the integral in (48).

Figure 4:  Approximation error in Theorem 3.7 for a single ReLU neuron as a
function of the ultraviolet truncation $T$. Values plotted are
$T=100,200,500,1000,2000,5000$. Here, $n=8$ and $d=3$. Here, the number of
quadrature points $N=10^{4}$ and the infra-red cutoff $t=0.1$ is kept
constant.

Figure 5:  The approximation error of Theorem 3.7 as in Figure 4, except the
number of quadrature points $N$ is chosen to grow with the ultraviolet cutoff
$T$ (specifically, we take $N=T$).

The cubic convergence with $T$ observed in Figures 4 and 5 is in accordance
with our theory, because the anti-symmetrization operator $\mathcal{A}$ is
approximately an isometry for highly oscillating functions, i.e., in the
within the ultraviolet part. By Plancherel’s equality we can approximate the
squared error introduced by the tail truncation as the squared $L^{2}$ norm of
the truncated tail, which is of order
$\int_{|\theta|>T}|\hat{\tau}(\theta)|^{2}d\theta\propto\int_{|\theta|>T}|\theta|^{-4}\propto
T^{-3}$ when $\tau$ is the ReLU activation.

##  10 Empirical generalization to multi-layer networks

It is natural to ask whether the advantage of rough activation functions
against cancellations remains as the depth of the neural network grows. We
consider networks of depth $L=3,4,5$ and compare
$\|\mathcal{A}f\|_{\mathcal{N}}^{2}$ between two choices of activation
functions: The smooth $\tanh$ and the rough _normalized double ReLU_ (DReLU)
$\tau_{\kappa}(y)=\kappa\max\\{-1,\min\\{1,y\\}\\}$ where $\kappa\approx
0.875$ is chosen such that
$\mathbb{E}[|\tau_{\kappa}(Z)|^{2}]=\mathbb{E}[|\tanh(Z)|^{2}]$ for standard-
Gaussian $Z\sim\mathcal{N}(0,1)$.

aaaaa

Figure 6: Log-scale comparison between
$\mathbb{E}[\|\mathcal{A}f\|_{\mathcal{N}}^{2}]$ for smooth and rough
activation functions (tanh vs normalized DReLU) for antisymmetrized neural
networks of different depths. Shaded areas show $90\%$ confidence regions.

We take $d=3$, let all layers have width $m=3n$, and instantiate NNs from the
Xavier initialization (independent Gaussian weights with variance $1/m$ where
$m$ is the number of neurons in the preceding layer). Fig. 6 shows that the
rough activation function maintains its advantage for networks with more
layers.

Figure 7: Tanh and the normalized DReLU.

##  11 Conclusion

Using the Fourier representation of the activation function, we observe that a
rough activation function is necessary to tame the near-exact cancellations
when antisymmetrizing two-layer NNs initialized with the standard
initializations. Equivalently, an architecture based on a smooth activation
function would require an initialization of the weights in the first layer
distinct from the standard Xavier/He initializations to avoid the sign problem
in the antisymmetric setting. The Fourier perspective also provides a
polynomial-time algorithm for approximately evaluating explicitly
antisymmetrized two-layer NNs. It may be possible that explicitly
antisymmetrized two-layer NNs provides a path towards universal approximation
of a class of antisymmetric functions without suffering from curse of
dimensionality. Our work also raises intriguing open questions about how the
cancellations and efficient algorithms generalize to antisymmetrized multi-
layer NNs as well as to the training regime.

## Acknowledgment

This work was partially supported by the NSF Quantum Leap Challenge Institute
(QLCI) program through grant number OMA-2016245 (N.A.), by the U.S. Department
of Energy, Office of Science, Office of Advanced Scientific Computing Research
and Office of Basic Energy Sciences, Scientific Discovery through Advanced
Computing (SciDAC) program, and by the Applied Mathematics Program of the US
Department of Energy (DOE) Office of Advanced Scientific Computing Research
under contract number DE-AC02-05CH1123 (L.L.). L.L. is a Simons Investigator.
The authors thank Jeffmin Lin and Lexing Ying for helpful discussions.

## References

  * [1] Sandro Sorella, S Baroni, Roberto Car, and M Parrinello.  A novel technique for the simulation of interacting fermion systems.  EPL, 8(7):663, 1989.
  * [2] EY Loh Jr, JE Gubernatis, RT Scalettar, SR White, DJ Scalapino, and RL Sugar.  Sign problem in the numerical simulation of many-electron systems.  Phys. Rev. B, 41(13):9301, 1990.
  * [3] D. M. Ceperley.  Fermion nodes.  J. Stat. Phys., 63(5-6):1237–1267, 1991.
  * [4] Di Luo and Bryan K. Clark.  Backflow transformations via neural networks for quantum many-body wave functions.  Phys. Rev. Lett., 122:226401, 2019.
  * [5] Jiequn Han, Linfeng Zhang, and Weinan E.  Solving many-electron Schrödinger equation using deep neural networks.  J. Comput. Phys., 399:108929, 2019.
  * [6] Jan Hermann, Zeno Schatzle, and Frank Noe.  Deep neural network solution of the electronic schrödinger equation.  Nature Chem., 12:891–897, 2020.
  * [7] David Pfau, James S. Spencer, Alexander G. D. G. Matthews, and W. M. C. Foulkes.  Ab initio solution of the many–electron schrödinger equation with deep neural networks.  Phys. Rev. Research, 2:033429, 2020.
  * [8] James Stokes, Javier Robledo Moreno, Eftychios A. Pnevmatikakis, and Giuseppe Carleo.  Phases of two-dimensional spinless lattice fermions with first-quantized deep neural-network quantum states.  Phys. Rev. B, 102:205122, 2020.
  * [9] Jeffmin Lin, Gil Goldshlager, and Lin Lin.  Explicitly antisymmetrized neural network layers for variational Monte Carlo simulation.  arXiv:2112.03491, 2021.
  * [10] Aaron Zweig and Joan Bruna.  Towards Antisymmetric Neural Ansatz Separation, December 2022\.  arXiv:2208.03264 [cs].
  * [11] Manzil Zaheer, Satwik Kottur, Siamak Ravanbakhsh, Barnabas Poczos, Russ R Salakhutdinov, and Alexander J Smola.  Deep Sets.  In I. Guyon, U. Von Luxburg, S. Bengio, H. Wallach, R. Fergus, S. Vishwanathan, and R. Garnett, editors, Advances in Neural Information Processing Systems, volume 30. Curran Associates, Inc., 2017\.
  * [12] Adam Santoro, David Raposo, David G Barrett, Mateusz Malinowski, Razvan Pascanu, Peter Battaglia, and Timothy Lillicrap.  A simple neural network module for relational reasoning.  page 10.
  * [13] Dmitry Yarotsky.  Universal Approximations of Invariant Maps by Neural Networks.  Constructive Approximation, 55(1):407–474, February 2022.
  * [14] Aaron Zweig and Joan Bruna.  A Functional Perspective on Learning Symmetric Functions with Neural Networks.  page 10.
  * [15] Nilin Abrahamsen and Lin Lin.  Anti-symmetric barron functions and their approximation with sums of determinants, 2023.
  * [16] M. Reed and B. Simon.  I: Functional Analysis.  Methods of Modern Mathematical Physics. Elsevier Science, 1981.
  * [17] Per-Olov Löwdin.  Quantum theory of many-particle systems. i. physical interpretations by means of density matrices, natural spin-orbitals, and convergence problems in the method of configurational interaction.  Phys. Rev., 97:1474–1489, Mar 1955.

##  Appendix A Lower-bounding the typical separation

######  Lemma A.1.

For $w\sim\mathcal{N}(0,\frac{2}{nd}I_{nd})$ sampled from the He
initialization, where $|B_{d}|$ is the volume of the unit ball in
$\mathbb{R}^{d}$. For constant $d$ this is $O(n^{2+d/2}\delta^{d})$.

######  Proof A.2.

If $w_{i}$ are sampled independently from a distribution $\mathcal{W}$ on
$\mathbb{R}^{d}$, then

$\displaystyle\begin{split}\prob(\delta_{w}<\delta)&\leq\sum_{i<j}\prob(\frac{1}{2}\|w_{i}-w_{j}\|<\delta)+\prob(\frac{1}{2}\|w_{i}+w_{j}\|<\delta)\\\
&\leq\sum_{i<j}\max_{w^{\prime}\in\mathbb{R}^{d}}\prob(\|w_{i}-w_{j}\|<2\delta\>|\>w_{j}=w^{\prime})+\max_{w^{\prime}\in\mathbb{R}^{d}}\prob(\|w_{i}+w_{j}\|<2\delta\>|\>w_{j}=w^{\prime})\\\
&\leq 2\binom{n}{2}(2\delta)^{d}|B_{d}|\|\mathcal{W}\|_{\infty},\end{split}$
(53)

where $\|\mathcal{W}\|_{\infty}$ is the supremum of the density. For the He
initialization $w_{i}\sim\mathcal{N}(0,\frac{2}{nd}I_{d})$ we have
$\|\mathcal{W}\|_{\infty}=(2\pi\cdot\frac{\tilde{c}}{nd})^{-d/2}=(\frac{2\tilde{c}\pi}{nd})^{-d/2}$.

For fixed $d$, $v=w^{(k)}$ satisfies that . Then with probability $1-o(1)$,
$v$ has _typical separation_ as defined in Definition 4.5.

######  Proof A.3 (Proof of Lemma 4.6).

Recall that by definition, $W$ is typical if each $w^{(k)}$ is typical and at
least half the $w^{(k)}$ have typical separation. The distribution of
$\frac{nd}{\tilde{c}}\|w^{(k)}\|^{2}\sim\chi^{2}(nd)$ implies that for each
$k=1,\ldots,m$, and since $\mathbb{E}[\|w^{(k)}\|^{2}]=\tilde{c}$. By a union
bound we have $\tilde{c}/2\leq\|w^{(k)}\|^{2}\leq 2\tilde{c}$ for all
$k=1,\ldots,m$ with probability $1-2m2^{-\Omega(nd)}$. Furthermore,
$w^{(k)}_{ij}\sim\mathcal{N}(0,\frac{\tilde{c}}{nd})$ and a union bound imply
that

Given any $C^{\prime\prime}>0$ we may let
$t=2\sqrt{C^{\prime}+C^{\prime\prime}+1}\sqrt{\frac{\log(nd)}{nd}}$ and obtain
that $\|w^{(k)}\|_{\infty}\leq t$ for all $k$ with probability at least
$1-n^{-C^{\prime\prime}}$. This shows that each $w$ is typical with
probability $1-1/n$ for appropriate $C$ in Definition 4.3.

If for each fixed $k$ then the probability that $\delta(w^{(k)}\geq\delta)$
for at least half the $k=1,\ldots,m$ also converges to $1$. Eq. (9) follows
from Lemma 4.1.

##  Appendix B Bound on complex-exponential overlap kernel for the Gaussian
envelope

In this section we recall the proof of the bound on a determinant of
exponentials given in [15].

######  Lemma B.1.

Let $v=(v_{1},\ldots,v_{n})^{T}\in\mathbb{R}^{n\times d}$ and
$w=(w_{1},\ldots,w_{n})^{T}\in\mathbb{R}^{n\times d}$. Then $(e^{v_{i}\cdot
w_{j}})_{ij}=\sum_{k=0}^{\infty}Q_{k}$ where

$\operatorname{rank}Q_{k}\leq\binom{k+d-1}{d-1},\qquad\|Q_{k}\|\leq\frac{n(\|v\|_{\infty}\|w\|_{\infty}d)^{k}}{k!}.$
(54)

######  Proof B.2.

Let $(c_{1},\ldots,c_{d})$ and $(\tilde{c}_{1},\dots,\tilde{c}_{d})$ be the
columns of $v$ and $w$ and let $\odot$ denote elementwise operations.

$(e^{v_{i}\cdot
w_{j}})_{ij}=e^{\odot\sum_{i=1}^{d}c_{i}\tilde{c}_{i}^{T}}=\odot_{i=1}^{d}e^{\odot
c_{i}\tilde{c}_{i}^{T}}.$ (55)

We first consider each factor $e^{\odot c_{i}\tilde{c}_{i}^{T}}$ separately.
Elementwise multiplication of rank-one matrices given as outer products
corresponds to elementwise multiplication of the vectors,
$ab^{T}\odot\tilde{a}\tilde{b}^{T}=(a\odot\tilde{a})(b\odot\tilde{b})^{T}$.
Therefore, applying the Taylor expansion entrywise,

$e^{\odot c\tilde{c}^{T}}=\sum_{k=0}^{\infty}\frac{(c\tilde{c}^{T})^{\odot
k}}{k!}=\sum_{k=0}^{\infty}\frac{(c^{\odot k})(\tilde{c}^{\odot k})^{T}}{k!},$
(56)

where $c=c_{i}$, $\tilde{c}=\tilde{c}_{i}$ are column vectors. Apply (56) to
each factor of (55),

$\displaystyle\odot_{i=1}^{d}e^{\odot c_{i}\tilde{c}_{i}^{T}}$
$\displaystyle=\sum_{k_{1},\ldots,k_{d}=0}^{\infty}\frac{(\odot_{i=1}^{d}c_{i}^{\odot
k_{i}})(\odot_{i=1}^{d}\tilde{c}_{i}^{\odot
k_{i}})^{T}}{\prod_{i=1}^{d}k_{i}!}.$ (57)
$\displaystyle=\sum_{k=0}^{\infty}\sum_{k_{1}+\ldots+k_{d}=k}^{\infty}\frac{1}{k!}\binom{k}{k_{1},\ldots,k_{d}}(\odot_{i=1}^{d}c_{i}^{\odot
k_{i}})(\odot_{i=1}^{d}\tilde{c}_{i}^{\odot k_{i}})^{T}$ (58)

Let $Q_{k}$ be the innermost sum of (58). We estimate the maximum over the
entries,

$\|Q_{k}\|_{\operatorname{max}}\leq\frac{\|v\|_{\infty}^{k}\|w\|_{\infty}^{k}}{k!}\sum_{k_{1}+\ldots+k_{d}=k}^{\infty}\binom{k}{k_{1},\ldots,k_{d}}=\frac{\|v\|_{\infty}^{k}\|w\|_{\infty}^{k}d^{k}}{k!}$

and apply the inequality $\|Q_{k}\|\leq n\|Q_{k}\|_{\operatorname{max}}$.

######  Lemma B.3.

Let $\lambda_{0}\geq\lambda_{1}\geq\ldots$ be the absolute values of the
eigenvalues of $(e^{v_{i}\cdot w_{j}})_{ij}$ and let
$\mu=\|v\|_{\infty}\|w\|_{\infty}d$. Then $\lambda_{0}\leq ne^{\mu}$, and for
$\mu\leq 1/2$,

$\lambda_{L}\leq\frac{2n}{p!}\mu^{p},\qquad L=\binom{p+d-1}{d},$ (59)

where the case $p=0$ of (59) holds with the interpretation
$L=\binom{d-1}{d}=0$, $\lambda_{0}\leq ne^{1/2}\leq 2n$.

######  Proof B.4.

From the identity

$\binom{p+d-1}{d}=1+d+\binom{d+1}{d-1}+\cdots+\binom{p+d-2}{d-1},$

there are

$1+d+\binom{d+1}{d-1}+\cdots+\binom{p+d-2}{d-1}\geq\operatorname{rank}Q_{0}+\cdots+\operatorname{rank}Q_{p-1}$

eigenvalues in front of $\lambda_{L}$ where $L=\binom{p+d-1}{d}$, and we have
used Lemma B.1. By the min-max principle,

$\lambda_{L}\leq\left\|\sum_{k=p}^{\infty}Q_{k}\right\|\leq
n\sum_{k=p}^{\infty}\frac{\mu^{k}}{k!}=\frac{n}{p!}\sum_{k=p}^{\infty}\mu^{k}=\frac{n}{p!}\frac{\mu^{p}}{1-\mu}\leq\frac{2n}{p!}\mu^{p}.$

######  Proof B.5 (Proof of proposition 6.8).

By Lemma B.3 and the assumptions on $p$ we have $\lambda_{\lfloor
n/2\rfloor}\leq\frac{2n}{p!}\mu^{p}\leq\frac{\mu^{p}}{2n}$ and
$\lambda_{0}\leq 2n$ where $\mu=d\|v\|_{\infty}\|w\|_{\infty}$, so it follows
that $|\det((e^{v_{i}\cdot
w_{j}})_{ij})|\leq\lambda_{0}^{n/2}\lambda_{n/2}^{n/2}\leq(\mu^{p})^{n/2}=(\nu/2)^{pn}$.

Apply the bound to $\operatorname{D}_{\mathcal{N}}(\theta w,\theta w)$ with
$p=\Theta(n^{1/d})$ to get that for $\theta\leq
t:=(2\sqrt{d}\|w\|_{\infty})^{-1}$,

$D_{\mathcal{N}}^{(w)}(\theta,\theta)=(\tfrac{1}{2}\theta/t)^{\Omega(n^{1+1/d})}.$
(60)

Eq. (14) implies the _triangle inequality_
$\|\mathcal{A}\tau_{w}\|_{\rho}\leq\frac{1}{\sqrt{2\pi}}\int_{-\infty}^{\infty}|\widehat{\tau}(\theta)|\sqrt{D_{\mathcal{N}}^{(w)}(\theta,\theta)}d\theta$
because $\sqrt{D_{\rho}^{(w)}(\theta,\theta)}=\|\mathcal{A}e^{i\theta
w\cdot[\mathbf{x}]}\|_{\rho}$ by definition. Apply this triangle inequality to
the low-pass part and bound the integrand using (60) to cancel the pole of
$|\widehat{\tau}|$ at $0$. We then obtain lemma 6.9

See 6.9

######  Proof B.6.

The lower bound on $t$ follows directly from its definition and the definition
of $w$ being typical.

Bound $D_{\mathcal{N}}^{(w)}$ as in (60) and write
$|\widehat{\tau}(\theta)|=O(|\theta|^{-r}+1)$. The triangle inequality yields
$\|{\tau}^{\mathrm{LP}(t)}\|_{\mathcal{N}}=O(2^{-pn/2}\int_{-t}^{t}(|\theta|/t)^{pn/2}(|\theta|^{-r}+1)d\theta)=O(2^{-pn/2}t(t^{-r}+1))$
where $p=\Omega(n^{1/d})$. Here we have cancelled the pole $|\theta|^{-r}$ by
writing
$(|\theta|/t)^{pn/2}|\theta|^{-r}\leq(|\theta|/t)^{r}|\theta|^{-r}=t^{-r}$ so
that the integrand is bounded by $t^{-r}+1$.

##  Appendix C Generalized definition of roughness

######  Definition C.1 (Generalized rough activation functions).

$\tau:\mathbb{R}\to\mathbb{C}$ is _generalized rough_ if its Fourier transform
$\widehat{\tau}$ has tail decay $K<\infty$, i.e., if
$\mathfrak{T}_{\widehat{\tau}}(t)=t^{-O(1)}$, and if additionally,

  1. 1.

$|\widehat{\tau}(\theta)|^{2}/\mathfrak{T}_{\widehat{\tau}}(\theta)\to 0$ as
$\theta\to\infty$.

  2. 2.

There exists $\gamma>0$ such that for $1/2\leq\sigma\leq 2$ and all
$\theta\in\mathbb{R}\backslash[-1,1]$ where $\widehat{\tau}(\theta)\neq 0$,

$\operatorname{Re}\Big{(}\frac{\mathbb{E}[\>\widehat{\tau}(\theta\pm|Z|)\>]}{\widehat{\tau}(\theta)}\Big{)}\geq\gamma,$
(61)

where $Z\sim\mathcal{N}(0,\sigma^{2})$. Here, “$\pm$” is taken the sign of
$\theta$, and $\operatorname{Re}$ is the real part of a complex number.

The assumptions of Item 1 and Item 2 prevent activation functions with
excessive negative correlations between nearby frequencies. The constraint on
the standard deviation $1/2\leq\sigma\leq 2$ is related to the Xavier / He
initialization in Definition 3.4.

##  Appendix D The Fourier inversion formula holds for ReLU and tanh

We include the derivation (see [15]) to verify Eq. 4 which asserts that
${\tau}^{\mathrm{LP}(\epsilon)}=p+C_{\epsilon}+O(\epsilon g)$ where $p$ is a
low-degree polynomial and $g$ is bounded by a polynomial. Here we have defined
${\tau}^{\mathrm{LP}(\epsilon)}=\tau-{\tau}^{\mathrm{HP}(\epsilon)}$.

  1. 1.

$\tau=\operatorname{ReLU}$: We first evaluate the high-pass part

${\tau}^{\mathrm{HP}(\epsilon)}(y)=|y|/2-\frac{\cos(\epsilon
y)}{\pi\epsilon}-\frac{y\operatorname{Si}(\epsilon y)}{\pi},$

where $\operatorname{Si}(y)=\int_{0}^{y}\frac{\sin s}{s}ds$. Since
$\operatorname{ReLU}(y)=|y|/2+y/2$,

$\displaystyle{\tau}^{\mathrm{LP}(\epsilon)}(y)$
$\displaystyle=y/2+\frac{\cos(\epsilon
y)}{\pi\epsilon}+\frac{y\operatorname{Si}(\epsilon y)}{\pi}.$ (62)

Write ${\tau}^{\mathrm{LP}(\epsilon)}=p+C_{\epsilon}+\varepsilon$ where

$p(y)=y/2,\qquad C_{\epsilon}=\frac{1}{\pi\epsilon}.$

Then the remainder satisfies

$|\varepsilon|\leq|\frac{\cos(\epsilon
y)-1}{\pi\epsilon}|+|\frac{y\operatorname{Si}(\epsilon
y)}{\pi}|\leq\frac{(\epsilon y)^{2}}{2\pi\epsilon}+\frac{y\cdot(\epsilon
y)}{\pi}=\epsilon g(y),\qquad g(y):=\frac{3}{2\pi}y^{2}.$ (63)

  2. 2.

$\tau=\tanh$: We can write the low-pass part as an absolutely convergent
integral as

${\tau}^{\mathrm{LP}(\epsilon)}(y)=\frac{1}{\sqrt{2\pi}}\int_{-\epsilon}^{\epsilon}\frac{-i\sqrt{\pi/2}}{\sinh(\pi\theta/2)}(e^{i\theta
y}-1)d\theta.$

Let $p,C_{\epsilon}\equiv 0$ and bound

$\displaystyle|{\tau}^{\mathrm{LP}(\epsilon)}(y)|\leq$
$\displaystyle\frac{1}{\sqrt{2\pi}}\int_{-\epsilon}^{\epsilon}\frac{\sqrt{\pi/2}}{|\pi\theta/2|}|\theta
y|d\theta=\epsilon g(y),\qquad g(y):=\frac{2}{\pi}|y|.$ (64)