# Finite Sample Identification of Wide Shallow Neural Networks with Biases

Massimo Fornasier1, Timo Klock2, Marco Mondelli3, , Michael Rauchensteiner4
Marco Mondelli was partially supported by the 2019 Lopez-Loreta prize.

(1Department of Mathematics, Technical University of Munich,
Bolzmannstraße 3, 85748, Garching, Germany,
Email<EMAIL_ADDRESS>
2Deeptech Consulting, Oslo, Norway
Email<EMAIL_ADDRESS>
3Institute of Science and Technology Austria (ISTA),
Am Campus 1, 3400 Klosterneuburg
Email<EMAIL_ADDRESS>
4Department of Mathematics, Technical University of Munich,
Bolzmannstraße 3, 85748, Garching, Germany,
Email<EMAIL_ADDRESS>
)

###### Abstract

Artificial neural networks are functions depending on a finite number of
parameters typically encoded as weights and biases. The identification of the
parameters of the network from finite samples of input-output pairs is often
referred to as the _teacher-student model_ , and this model has represented a
popular framework for understanding training and generalization. Even if the
problem is NP-complete in the worst case, a rapidly growing literature – after
adding suitable distributional assumptions – has established finite sample
identification of two-layer networks with a number of neurons
$m=\mathcal{O}(D)$, $D$ being the input dimension. For the range $D<m<D^{2}$
the problem becomes harder, and truly little is known for networks
parametrized by biases as well. This paper fills the gap by providing
constructive methods and theoretical guarantees of finite sample
identification for such wider shallow networks with biases. Our approach is
based on a two-step pipeline: first, we recover the direction of the weights,
by exploiting second order information; next, we identify the signs by
suitable algebraic evaluations, and we recover the biases by empirical risk
minimization via gradient descent. Numerical results demonstrate the
effectiveness of our approach.

##  1 Introduction

Training a neural network is an NP-complete [31, 10] and non-convex
optimization problem which exhibits spurious and disconnected local minima [6,
49, 65]. However, highly over-parameterized networks are routinely trained to
zero loss and generalize well over unseen data [67]. In an effort to
understand these puzzling phenomena, a line of work has focused on the
implicit bias of gradient descent methods [4, 5, 7, 38, 39, 55, 63]. Another
popular framework to characterize training and generalization is the so-called
teacher-student model [12, 57, 50, 34, 18, 19, 51, 52, 68, 26, 25, 23, 24, 30,
35, 36, 69]. Here, the training data of a so-called student network are
assumed to be realizable by an unknown teacher network, which interpolates
them. This model is justified by the wide literature – both classical and more
recent – on memorization capacity [16, 44, 28, 37, 13, 66, 60, 11], which
shows that generic data can be realized by slightly over-parametrized
networks. Furthermore, it has also been proved that, in certain settings,
small generalization errors necessarily require identification of the
parameters [36]. This leads to the fundamental question of understanding when
the minimization of the empirical error simultaneously promotes the
identification of the teacher parameters and consequently the perfect
generalization beyond training data.

Existing results mostly focus on the identification of the weights of shallow
(i.e., two-layer) networks with a number of neurons $m$ scaling linearly in
the input dimension $D$ (see the related work discussed below). There is also
evidence of the average-case hardness of the regime $D^{3/2}<m<D^{2}$, as
weight identification can be reduced to tensor decomposition [36]. Let us also
highlight that, even if the role of biases is often neglected, most of the
known universal approximation results would not hold without biases 111If the
activation is odd, then it evaluates to $0$ in $0$ and one can only represent
functions which are $0$ in $0$..

##### Main contributions.

In this paper, we give theoretical guarantees on the recovery of both weights
and biases from finite samples in the regime $D<m<D^{2}$, under rather mild
assumptions on the smoothness of the activation function, incoherence of the
weights, and boundedness of the biases. More specifically, the teacher network
is given by

$\displaystyle
f:\mathbb{R}^{D}\to\mathbb{R},\quad{f}(x):=\sum_{j=1}^{m}g(\langle
w_{j},x\rangle+\tau_{j}),$ (1)

where $w_{1},\ldots,w_{m}$ are unit-norm weights and
$\tau_{1},\ldots,\tau_{m}$ are bounded biases. We propose a two-step parameter
recovery pipeline that decouples the learning of the weights from the recovery
of the remaining network parameters. In the first step, we use second order
information to recover the weights $w_{1},\ldots,w_{m}$ up to signs. The
method (cf. Section 3) comes with provable guarantees of recovery up to
$m\log^{2}(m)=O(D^{2})$ weights, provided that _(i)_ the weights are
sufficiently incoherent, and _(ii)_ second order derivatives of $f$ carry
_enough information_. Our approach is based on the observation that
$\nabla^{2}f(x)=\sum_{j=1}^{m}g^{(2)}(\langle
w_{j},x\rangle+\tau_{j})w_{j}\otimes w_{j}\in{\cal
W}=\operatorname{span}\\{w_{1}\otimes w_{1},\dots,w_{m}\otimes w_{m}\\}$ and,
hence, multiple samples of independent Hessians allow to compute an
approximating subspace $\widehat{\mathcal{W}}\approx{\cal W}$. The
construction of such a subspace is based exclusively on second order
information and differs from the tensor approach in [30], which uses higher
order tensor decomposition. The identification of the weights is then
performed by projected gradient ascent, the so-called subspace power method
[22, 33, 32], seeking for solutions of

$\displaystyle\max_{u\in\mathbb{S}^{D-1}}\left\lVert
P_{\widehat{\mathcal{W}}}(u\otimes
u)\right\rVert^{2}_{F}\approx\max_{u\in\mathbb{S}^{D-1}}\left\lVert P_{{\cal
W}}(u\otimes u)\right\rVert^{2}_{F}.$ (2)

In the second step (cf. Section 4), we show how to identify the signs by
suitable algebraic evaluations and the biases by empirical risk minimization
via gradient descent. For this part, we give a suitable initialization of the
algorithm and provide convergence guarantees to the ground-truth biases. The
convergence proof is based on a linearization argument inspired by the neural
tangent kernel (NTK) approach. However, delicate technical adaptations are
needed, in order to _(i)_ ensure that biases do not compromise the well-
posedness of the linearized system, and _(ii)_ control the effect on the
gradient descent iteration of the errors accumulated in the weight
identification step. The theoretical findings of this paper can be summarized
in the following informal statement.

######  Theorem 1 (Informal).

Let $f$ be the shallow network (1) with $D$ inputs and $m$ neurons such that
$m\log^{2}m=O(D^{2})$. Then, for sufficiently large $D$, there exists a
constructive algorithm recovering all weights and shifts of the network with
high probability from $O(Dm^{2}\log^{2}m)$ network queries.

A few comments on the complexity are in order. For $m=\mathcal{O}(D)$, the
proposed pipeline has polynomial complexity in $D,m$. For $D<m<D^{2}$, while
the pipeline is still guaranteed to converge globally, our findings clarify
precisely how the hardness of the problem consists in distinguishing local
maximizers of (2). This fine geometrical description is novel, and it could
pave the way towards a more refined understanding of the hardness of the
network identification problem. In fact, our numerical experiments (cf.
Section 5) consistently show that the network recovery remains surprisingly
successful with low complexity up to the information-theoretic upper
bound222This information-theoretic upper bound holds for all methods employing
order-2 tensors. In fact, for $m\approx D^{2}/2$,
$\operatorname{span}\\{w_{1}\otimes w_{1},\dots,w_{m}\otimes w_{m}\\}$
coincides with the space of all symmetric matrices, making it impossible to
distinguish $w_{j}\otimes w_{j}$ from any other rank-1 matrix. $m\approx
D^{2}/2$.

##### Related work.

A line of work spanning three decades has considered network identification
under the assumption of being able to access exactly _all_ possible input-
output pairs (shallow networks in [56, 1], fully-connected deep networks in
[21] and, most recently, deep networks without clone nodes and piecewise
$C^{1}$ activations with bounded-variation derivative in [61]). However, as a
neural network remains fully determined by a finite number of parameters, it
is not at all expected to generically require an infinite amount of training
samples. This has motivated the rapidly growing literature on the teacher-
student model. A popular setup is to minimize the population risk by assuming
a Gaussian distribution of the weights: a two-layer ReLU network with a single
neuron is considered in [57], a single convolutional filter in [18, 12],
multiple convolutional filters with no overlap in [19], and residual networks
in [34]. Gradient descent methods have also been widely studied: [51]
considers a single ReLU unit; [52] provide a global convergence result for
shallow networks with quadratic activations and a local convergence result for
more general activations; and gradient descent is combined with an
initialization based on tensor decomposition in [69, 68, 26]. A local
convergence analysis for student networks containing at least as many neurons
as the teacher network is provided by [70]. Let us highlight that these
results neglect the role of biases, and the convergence guarantees are either
local or, when global, require a number of neurons $m=\mathcal{O}(D)$.
Inspired by papers dating back to the 1990s [14, 43, 15], the works [50, 25,
24, 30, 35, 36, 69] have explored the connection between differentiation of
shallow networks and symmetric tensor decompositions. Once the weights have
been identified, the computation of biases has also been considered by direct
estimation [25] for $m\leq D$, or by Fourier methods [30] for mildy
overparametrized network. These results, however, do not offer rigorous
guarantees for the regime $D<m<D^{2}$. Finally, a line of work from
statistical physics, which started with [47, 46, 48, 9, 45] and recently
culminated with [27], has characterized the dynamics of one-pass stochastic
gradient descent via a set of ordinary differential equations, thus providing
insights on the generalization behavior.

##### Technical tools and innovations.

_Weight identification:_ Instead of considering higher order tensor
decompositions (and, hence, higher order differentiation of the network) as
done by [30], here we follow the strategy of [25], which exploits the
information coming from the Hessians. However, while [25] require the weights
to be linearly independent (and, thus, $m\leq D$), we tackle the challenging
overcomplete case $m>D$. Furthermore, for the identification of the weights we
use (2), namely a robust non-linear program over vectors, which is
significantly less computationally expensive than the minimum rank selection
of [25]. Our analysis improves upon [22] by allowing to go beyond a linear
scaling between $m$ and $D$, and it takes advantage of the new insights
provided by [32] on the subspace power method.

_Shift identification:_ Differently from [25, 30], we set up an empirical risk
minimization problem, and we solve it via gradient descent. Our proof of
convergence is based on certain kernel matrices, which are reminiscent of
those appearing in the neural tangent kernel (NTK) theory [29]. The NTK
perspective has been used to prove global convergence of gradient descent for
shallow [20, 42, 54, 64, 37, 53] and deep neural networks [2, 17, 71, 72, 41,
40, 11]. The technical innovations of our paper with respect to this line of
work are as follows. First, we exchange the role between input variable $x$
and weights: we consider the Jacobian of the network with respect to its input
$x$, and not to its parameters. This allows us to keep fixed the size of the
network and to analyze the NTK spectrum for large input samples. Second, we
extend the NTK theory to handle networks with biases. Finally, as the accuracy
of the linearization argument depends on the errors accumulated in the weight
identification step, we carry out a delicate perturbation analysis.

##### Notation.

Given two vectors $u$ and $v$, let $u\otimes v$ be their Kronecker product and
$u\odot v$ their element-wise product. Given a vector $u$, let $\left\lVert
u\right\rVert_{2}$ be its $\ell_{2}$ norm and $\operatorname{diag}(v)$ the
diagonal matrix with $v$ on diagonal. Given a matrix $A$, let $\left\lVert
A\right\rVert$ be its operator norm, $\left\lVert A\right\rVert_{F}$ its
Frobenius norm, and $\left\lVert A\right\rVert_{F\to
F}=\sup_{\|X\|_{F}=1}\left\lVert AX\right\rVert_{F}$. Let
$\operatorname{Sym}(\mathbb{R}^{d\times d})$ be the space of symmetric
matrices in $\mathbb{R}^{d\times d}$, ${\cal C}^{n}(\mathbb{R})$ the space of
functions in $\mathbb{R}$ with $n$ continuous derivatives,
$\textrm{Uni}(\mathbb{S}^{D-1})$ the uniform distribution on the
$D$-dimensional sphere $\mathbb{S}^{D-1}$, and $\operatorname{Id}_{p}$ the
identity matrix in $\mathbb{R}^{p\times p}$. Given a function $g$, let
$g^{(n)}$ be its $n$-th derivative. Given a vector $v$ and a permutation
$\pi$, let $v_{\pi}$ be the vector obtained by permuting the entries of $v$
according to $\pi$.

##  2 Network model and main result

We consider the parameter recovery of a planted shallow neural network
$f:\mathbb{R}^{D}\to\mathbb{R}$ of the form (1). We assume that the weights
are drawn uniformly at random from the sphere, i.e.,
$w_{1},\ldots,w_{m}\sim_{\rm i.i.d.}\textrm{Uni}(\mathbb{S}^{D-1})$, and the
shifts are contained in a given interval, i.e.,
$\tau_{1},\ldots,\tau_{m}\in[-\tau_{\infty},+\tau_{\infty}]$. We also make the
following assumptions on the activation function $g$ and on the Hessians of
$f$.

  1. (M1)

$g\in{\cal C}^{3}(\mathbb{R})$ and

$\displaystyle\kappa$ $\displaystyle:=\max_{n\in[3]}\left\lVert
g^{(n)}\right\rVert_{\infty}<\infty.$ (3)

Furthermore, $g^{(2)}$ is strictly monotonic on
$(-\tau_{\infty},+{\tau}_{\infty})$, $g^{(1)}$ is strictly positive or
negative on $(-\tau_{\infty},+{\tau}_{\infty})$ and there exists
$s\in\\{-1,+1\\}$ such that for all $\tau\in[-\tau_{\infty},+{\tau}_{\infty}]$
we have

$\displaystyle
s=\operatorname{sgn}\left(\int_{\mathbb{R}}g^{(1)}(t+\tau)\exp(-t^{2}/2)dt\right).$

  2. (M2)

$g^{(1)}$ is not a polynomial of degree 3 or less and
$\int_{\mathbb{R}}g(t)^{2}\exp(-t^{2}/2)dt<\infty$.

  3. (M3)

The Hessians of $f$ have sufficient information for weight recovery, i.e.,

$\displaystyle\lambda_{m}\left(\mathbb{E}_{X\sim{\cal
N}(0,\operatorname{Id})}[\operatorname{vec}(\nabla^{2}f(X))^{\otimes
2}]\right)\geq\alpha>0.$ (4)

The size of the interval $[-\tau_{\infty},+\tau_{\infty}]$ does not depend on
$m$ or $D$, but only on $g$ via (M1). This assumption is satisfied by common
activations, such as $g(x)=\tanh(x)$ for ${\tau}_{\infty}\approx 0.6$ and the
sigmoid $g(x)=1/(1+\exp(-x))$ for ${\tau}_{\infty}\approx 1.5$. Condition (M3)
guarantees that combining Hessians of $f$ at sufficiently many generic inputs
provides enough information to recover all individual weights. A potential way
to show that (4) holds is as follows. First, note that
$\nabla^{2}f(x)=\sum^{m}_{k=1}g^{(2)}(w_{k}^{\top}x+\tau_{k})w_{k}\otimes
w_{k}\in\operatorname{span}\\{w_{1}\otimes w_{1},\dots,w_{m}\otimes w_{m}\\}$.
Hence, by exploiting the incoherence of
$w_{1},\dots,w_{m}\sim\operatorname{Uni}(\mathbb{S}^{D-1})$, one could relate
the smallest eigenvalue in (4) to that of the matrix with entries
$(\mathbb{E}_{X\sim{\cal N}(0,\operatorname{Id})}[g^{(2)}(\langle
w_{k},X\rangle+\tau_{k})g^{(2)}(\langle
w_{\ell},X\rangle+\tau_{\ell})])_{k,\ell}.$ This last quantity may then be
bounded using the tools developed in Section 4.2. Making these passages
rigorous is beyond the scope of this work, and we leave it as an open
question. We also highlight that assumption (M3) is common in the related
literature [23, 25, 22, 3].

We also assume the ability to evaluate the network $f$ and to approximate its
derivatives.

  1. (G1)

We can query the teacher network ${f}$ and the activation $g$ at any point
without noise, and the number of neurons $m$ is known.

  2. (G2)

We assume access to a numerical differentiation method, denoted by
$\Delta^{n}[\cdot]$, that computes the derivatives for $n=1,2,3$ up to an
accuracy $\epsilon>0$. To be more precise, we require that the derivatives of
$g$ with respect to a vector input $x\in\mathbb{R}^{D}$ fulfill

$\displaystyle\left\lVert\nabla^{n}g(w^{\top}x)-\Delta^{n}[g(w^{\top}x)]\right\rVert_{F}\leq
C_{\Delta}\left\lVert w^{\otimes n}\right\rVert_{F}\epsilon,$ (5)

where $C_{\Delta}$ is a universal constant only depending on the activation
through $\kappa$ (see (3)). Furthermore, for any $b,t_{0}\in\mathbb{R}$ the
derivatives of $t\mapsto g(b\,t)$ can be approximated as

$\displaystyle\left|{\left.\frac{d^{n}}{dt^{n}}g(b\cdot
t)\right|_{t=t_{0}}-\Delta^{n}[g(b\cdot)](t_{0})}\right|\leq
C_{\Delta}b^{n+2}\epsilon.$ (6)

We also assume that the numerical differentiation method is linear, i.e.,

$\displaystyle\Delta^{n}[a\cdot g+h]=a\cdot\Delta^{n}[g]+\Delta^{n}[h],$ (7)

for any functions $g,h$ and scalar $a\in\mathbb{R}$. Finally, the numerical
differentiation algorithm requires a number of queries equal to the dimension
of the approximated derivative, i.e., $\mathcal{O}(1)$ for partial derivatives
and $\mathcal{O}(D^{n})$ for $n$-th order derivative tensors.

We note that all the properties in (G2) are fulfilled by a standard central
finite difference scheme. Our proposed algorithm for the recovery of the
parameters of the planted model (1) is based on a two-step procedure. In the
first step, we learn the weight vectors (up to a sign) from the space spanned
by Hessian approximations of $f$ (cf. Section 3). Recovering the weights
provides access to vectors ${\hat{w}}_{k}$, which satisfy
$s_{k}{\hat{w}}_{k}\approx w_{k}$ for some signs
$s_{1},\ldots,s_{m}\in\\{-1,1\\}$. In the second step, we identify the signs
$s=(s_{1},\ldots,s_{m})$ and shifts $\tau=(\tau_{1},\dots,\tau_{m})$ (cf.
Section 4). We begin by finding $s$ and an initialization of the shifts
$\hat{\tau}\approx\tau$ by a linearization through higher order (numerical)
differentiation along the previously computed weight approximations. The shift
approximation $\hat{\tau}$ is then refined by empirical risk minimization.
More precisely, we consider the parametrization

$\displaystyle\hat{f}(x,\hat{\tau}):=\sum_{k=1}^{m}g(s_{k}\langle{\hat{w}}_{k},x\rangle+{\hat{\tau}}_{k}),$
(8)

which is fit against the planted model $f(x)$ defined in (1) by minimizing the
least squares objective

$\displaystyle
J(\hat{\tau})=\frac{1}{2N_{\text{train}}}\sum^{N_{\text{train}}}_{i=1}\Big{(}f(x_{i})-\hat{f}(x_{i},{\hat{\tau}})\Big{)}^{2}$
(9)

via gradient descent, where $x_{1},\ldots,x_{N_{\text{train}}}\sim_{\rm
i.i.d.}{\cal N}(0,\operatorname{Id}_{D})$. Provided that the activation
function satisfies (M1)-(M2) , we show that gradient descent is guaranteed to
converge locally to the ground truth shifts up to an error depending only on
the accuracy of the initial weight estimates $\hat{w}_{k}\approx\pm w_{k}$.
The combination of these two steps leads to Algorithm 1 and to our main
result, stated below. Its proof is deferred to Section D of the supplementary
materials, and it follows as a combination of Theorem 3, Proposition 1, and
Theorem 4 (discussed in the rest of the paper).

Input: Teacher neural network $f$ defined in (1) with known number of neurons
$m$, numerical differentiation method $\Delta^{n}[\cdot]$ with accuracy
$\epsilon$, number of Hessian locations $N_{h}$ and gradient descent samples
$N_{\text{train}}$, number of steps for refinement via gradient descent
$N_{\text{GD}}$.

1 Compute weights ${\widehat{W}}=[{\hat{w}}_{1}|\dots|{\hat{w}}_{m}]$ by PCA
of Hessians followed by iterations of the subspace power method (cf. Algorithm
2 in the supplementary materials, and discussion in Section 3);

2 Find signs $\hat{s}$ and initial shifts $\hat{\tau}\in\mathbb{R}^{m}$ by
linearization through higher order differentiation along approximated weight
vectors (cf. Algorithm 3 in the supplementary materials, and discussion in
Section 4.1);

3 Set ${\widehat{W}}\leftarrow{\widehat{W}}\operatorname{diag}(\hat{s})$ and
construct a student network $\hat{f}$ as in (8) with parameters
${\widehat{W}},{\hat{\tau}}$;

4 Draw samples $x_{1},\dots,x_{N_{\text{train}}}\sim{\cal
N}(0,\operatorname{Id}_{D})$ and refine the shifts of $\hat{f}$ by minimizing
$J({\hat{\tau}})$ (cf. (9)) via gradient descent for $N_{\text{GD}}$ steps
(cf. Section 4.2). Denote by ${\hat{\tau}}^{[N_{\text{GD}}]}$ the final
iterate.

Output: Weights ${\widehat{W}}$ and final shifts
${\hat{\tau}}^{[N_{\text{GD}}]}$ of $\hat{f}$.

Algorithm 1 Network reconstruction

######  Theorem 2 (Main result on network reconstruction).

Consider the teacher network $f$ defined in (1), where
$w_{1},\dots,w_{m}\sim\textrm{Uni}(\mathbb{S}^{D-1})$ and
${\tau}_{1},\ldots,{\tau}_{m}\in[-\tau_{\infty},\tau_{\infty}]$. Assume $g$
satisfies (M1) \- (M2) and $f$ satisfies the learnability condition (M3) for
some $\alpha>0$. Assume we run Algorithm 1 with $N_{h}>t(m+m^{2}\log(m)/D)$
for some $t\geq 1$ and $N_{\text{train}}>m\sqrt{D}$. Then, there exists
$D_{0}\in\mathbb{N}$ and a constant $C>0$ only depending on $g$ and
${\tau}_{\infty}$ such that the following holds with probability at least
$1-m^{-1}-2D^{2}\exp\left(-\min\\{\alpha,1\\}t/C\right)-Cm^{2}\exp(-\sqrt{D}/C)$:
If $m\geq D\geq D_{0}$, $Cm\log^{2}m\leq D^{2}$, and the numerical
differentiation accuracy $\epsilon$ satisfies

$\displaystyle\epsilon\leq\frac{D^{1/2}\min\\{1,\alpha^{1/2}\\}}{Cm^{9/2}\log(m)^{3/2}},$
(10)

then Algorithm 1 returns weights and shifts
$({\widehat{W}}=[{\hat{w}}_{1}|\dots|{\hat{w}}_{m}],{\hat{\tau}}^{[N_{GD}]})$
that fulfill

$\displaystyle\max_{k\in[m]}\|{\hat{w}}_{\pi(k)}-{w}_{k}\|_{2}$
$\displaystyle\leq C(m/\alpha)^{1/4}\epsilon^{1/2},$ (11)
$\displaystyle\|{\hat{\tau}}^{[N_{GD}]}_{\pi}-{\tau}\|_{2}$ $\displaystyle\leq
C\left(\frac{m^{7/4}D^{1/4}\epsilon^{1/2}}{\alpha^{1/4}N_{\text{train}}^{1/2}}+\frac{\xi^{N_{GD}}}{m^{1/2}}+\Delta_{W,1}\right),$
(12)

for some permutation $\pi$ and some constant $\xi\in[0,1)$ where

$\displaystyle\Delta_{W,1}$
$\displaystyle:=\frac{m^{1/2}\log(m)^{3/4}}{D^{1/4}}\cdot\left(\|{\widehat{W}}-W\|_{F}+\frac{\Delta_{W,O}^{1/2}}{D^{1/2}}+\left\|\sum^{m}_{k=1}w_{k}-{\hat{w}}_{k}\right\|_{2}\right),$
(13) $\displaystyle\Delta_{W,O}$ $\displaystyle:=\sum^{m}_{k\neq
k^{\prime}}\left|\langle
w_{k}-{\hat{w}}_{k},w_{k^{\prime}}-{\hat{w}}_{k^{\prime}}\rangle\right|.$ (14)

By choosing an appropriate numerical accuracy $\epsilon$, (10) is satisfied
and the error on the weights in (11) can be made arbitrarily small. The error
on the shifts in (12) depends on three terms. The first term scales with
$\sqrt{\epsilon/N_{\text{train}}}$, hence it is controlled by taking a large
number of training samples. The second term vanishes exponentially with the
number of gradient steps $N_{GD}$. Thus, for large enough $N_{\text{train}}$
and $N_{GD}$, the dominant factor is $\Delta_{W,1}$. This last term decreases
with the weight approximation error, i.e., if ${\widehat{W}}=W$, then
$\Delta_{W,1}=0$. In fact, $\Delta_{W,1}$ scales with $\epsilon^{1/2}$, hence
it can be reduced by improving the numerical accuracy.

It is natural to compare the residual error term $\Delta_{W,1}$ _after
gradient descent_ with the error on the shifts _before gradient descent_ ,
i.e., at initialization as given by Proposition 1 (cf. (22)). If we assume
randomness on the weight errors (with variance matching the upper bound in
(11)), i.e.,
${\hat{w}}_{\pi(k)}-{w}_{k}\sim_{i.i.d.}\mathcal{N}(0,(m/\alpha)^{(1/2)}\epsilon/D\cdot\operatorname{Id}_{D})$
then, up to poly-logarithmic factors, $\Delta_{W,1}$ scales as

$\frac{\epsilon^{1/2}}{\alpha^{1/4}}\left(\frac{m^{5/4}}{D^{1/4}}+\frac{m^{7/4}}{D}\right).$
(15)

This last quantity is provably smaller than the error (22) at initialization,
see the discussion after Proposition 1. In the worst case, when all weight
errors are aligned, $\Delta_{W,1}$ is dominated by
$\left\|\sum^{m}_{k=1}w_{k}-{\hat{w}}_{k}\right\|_{2}=\mathcal{O}(m^{5/4}\alpha^{-1/4}\epsilon^{1/2})$,
which would not lead to a provable improvement over (22). However, in Section
5, we numerically observe that this type of error accumulation does not occur:
the term $\left\|\sum^{m}_{k=1}w_{k}-{\hat{w}}_{k}\right\|_{2}$ is negligible
and $\Delta_{W,1}$ is significantly smaller than (22), see Figure 2 and the
related discussion.

##  3 Identification of the weights

######  Definition 1 (RIP).

Let $W\in\mathbb{R}^{D\times m}$, $1\leq p\leq m$ be an integer, and
$\delta\in(0,1)$. We say that $W$ is $(p,\delta)$-RIP if every $D\times p$
submatrix $W_{p}$ of $W$ satisfies
$\|W_{p}^{\top}W_{p}-\operatorname{Id}_{p}\|_{2}\leq\delta$.

######  Definition 2 (Properties of isotropic random weights).

Let $W:=[w_{1}|\ldots|w_{m}]$ and $(G_{n})_{k\ell}:=\langle
w_{k},w_{\ell}\rangle^{n}$. We define the following incoherence properties:

  1. (A1)

There exists $c_{1}>0$, depending only on $\delta$, such that $W$ is $(\lceil
c_{1}D/\log(m)\rceil,\delta)$-RIP.

  2. (A2)

There exists $c_{2}>0$, independent of $m,D$, so that $\max_{i\neq j}\langle
w_{i},w_{j}\rangle^{2}\leq c_{2}\log(m)/D$.

  3. (A3)

There exists $c_{3}>0$, independent of $m,D$, so that $\left\lVert
G_{n}^{-1}\right\rVert\leq c_{3}$, for all $n\geq 2$.

If the number of weights $m$ is $o(D^{2})$, weights drawn from the uniform
spherical distribution fulfill (A1) \- (A3) with high probability. This
follows from a result due to [32] (cf. Proposition 2 in the supplementary
materials). We are going to use the properties of Definition 2 throughout our
analysis.

The weight recovery consists of two steps. First, we leverage the fact that
approximated Hessians of the network expose the weights according to

$\displaystyle\Delta^{2}f(x)\approx\nabla^{2}f(x)=\sum^{m}_{k=1}g^{(2)}(\langle
w_{k},x\rangle+{\tau}_{k})w_{k}\otimes w_{k},$

such that independent sampling of Hessian locations eventually spans
(approximately) the space

$\displaystyle\widehat{\mathcal{W}}\approx{\cal
W}:=\operatorname{span}\left\\{w_{1}\otimes w_{1},\dots,w_{m}\otimes
w_{m}\right\\},$ (16)

with $\widehat{\mathcal{W}},{\cal
W}\subset\operatorname{Sym}(\mathbb{R}^{D\times D})$. This holds w.h.p. for
Hessian locations $x_{1},\dots,x_{N_{h}}$ drawn as standard Gaussians as a
consequence of (M3), provided $N_{h}$ is sufficiently large. The resulting
approximation error $\left\lVert P_{{\cal
W}}-P_{\widehat{\mathcal{W}}}\right\rVert_{F\rightarrow F}$ can be controlled
by the accuracy of the numerical differentiation $\epsilon$, see Lemma 1 in
the supplementary materials.

Next, the weights are uniquely identified (up to a sign) as the $2m$ local
maximizers of the program (2), which belong to a certain level set
$\\{u\in\mathbb{S}^{D-1}|\left\lVert P_{\widehat{\mathcal{W}}}(u\otimes
u)\right\rVert_{F}^{2}\geq\beta\\}$ of the underlying objective. This follows
as a special case from the theory within [33, 22, 32]. More specifically, [33]
study the problem in the unperturbed case, [22] extend the subspace power
method to the perturbed objective but their analysis is limited to $m<2D$, and
finally [32] go for $2$-tensor decompositions up to $m=o(D^{2})$ for the
perturbed objective. Then, the local maximizers of (2) are computed via a
projected gradient ascent algorithm that iterates

$\displaystyle u_{j+1}=P_{\mathbb{S}^{D-1}}(u_{j}+2\gamma
P_{\widehat{\mathcal{W}}}((u_{j})^{\otimes 2})u_{j}),$ (17)

where $\gamma$ is the step-size and
$P_{\mathbb{S}^{D-1}}/P_{\widehat{\mathcal{W}}}$ denote the projections on
$\mathbb{S}^{D-1}/\widehat{\mathcal{W}}$. The iteration (17) starts from a
random initialization $u_{0}\in\mathbb{S}^{D-1}$, and it was introduced by
[33] as a subspace power method (SPM). By iterating (17) until convergence
repeatedly from independent starting points, one can collect all $m$ local
maximizers of (2) and thereby learn (approximately) all weights up to sign.
Assuming the retrieval of every local maximizer is equally likely, the average
number of repetitions needed to recover all local maximizers follows from the
analysis of the coupon collection problem and grows like $\Theta(m\log m)$
(see also [24]). The theorem below provides a bound on the uniform
approximation error for the weights. Its proof, as well as the description of
Algorithm 2 summarizing the overall procedure of weight identification, is
deferred to Section A of the supplementary materials.

######  Theorem 3 (Weight recovery).

Consider the teacher network $f$ defined in (1), where
$w_{1},\dots,w_{m}\sim\textrm{Uni}(\mathbb{S}^{D-1})$ and
${\tau}_{1},\ldots,{\tau}_{m}\in[-\tau_{\infty},\tau_{\infty}]$. Assume $g$
satisfies (M1) \- (M2) and $f$ satisfies the learnability condition (M3) for
some $\alpha>0$. Then, there exists $D_{0}\in\mathbb{N}$ and a constant $C>0$
depending only on $g,{\tau}_{\infty}$, such that, for all $D\geq D_{0}$ and
$Cm\log^{2}m\leq D^{2}$, the following holds with probability at least
$1-m^{-1}-D^{2}\exp\left(-\min\\{\alpha,1\\}t/C\right)-C\exp(-\sqrt{m}/C)$:
(i) The weights $w_{1},\ldots,w_{m}$ fulfill (A1) \- (A3), and (ii) if we run
Algorithm 2 with numerical differentiation accuracy
$\epsilon\leq\frac{\sqrt{\alpha}}{C\sqrt{m}}$ and using
$N_{h}>t(m+m^{2}\log(m)/D)$ Hessian locations for some $t\geq 1$, we obtain a
set of approximated weights ${\cal U}\subset\mathbb{S}^{D-1}$ such that, for
all ${\hat{w}}\in{\cal U}$, there exists a $k\in[m]$ and a sign
$s\in\left\\{-1,+1\right\\}$ for which

$\displaystyle\left\lVert w_{k}-s{\hat{w}}_{k}\right\rVert_{2}\leq
C(m/\alpha)^{1/4}\epsilon^{1/2}.$ (18)

##  4 Identification of the signs and shifts

By leveraging the fact that differentiation exposes the weights of the network
as components of the tensor
$\nabla^{n}f(x)=\sum^{m}_{k=1}g^{(n)}(x^{\top}w_{k}+{\tau}_{k})w_{k}^{\otimes
n}$ for $n=2$, Theorem 3 gives that ${\hat{w}}_{k}\approx{s}_{k}{w}_{k}$ for
some signs ${s}_{k}\in\\{-1,+1\\}$. In this section, we show how to recover
the remaining parameters (shifts and signs) for a given set of ground truth
weights $\\{w_{1},\dots,w_{m}\\}\subset\mathbb{S}^{D-1}$ which are
sufficiently incoherent and approximated by
$\\{{\hat{w}}_{1},\dots,{\hat{w}}_{m}\\}\subset\mathbb{S}^{D-1}$ up to a sign.
This recovery can be broken down into two steps. First, we find the correct
signs and good initial shifts (cf. Section 4.1); once the parameters are
known, a student network can be initialized from these starting values.
Second, the shifts of the student network are refined by empirical risk
minimization via gradient descent (cf. Section 4.2).

###  4.1 Parameter initialization

Our initialization strategy is centered around the recovery of the quantities
$\mathcal{C}_{2}=(\mathcal{C}_{2,1},\ldots,\mathcal{C}_{2,m})$ and
$\mathcal{C}_{3}=(\mathcal{C}_{3,1},\ldots,\mathcal{C}_{3,m})$, where

$\displaystyle\mathcal{C}_{n,k}:=s_{k}^{n}g^{(n)}({\tau}_{k}),\quad\text{ for
}k\in[m],\quad n\in\\{2,3\\}.$ (19)

If $g$ satisfies (M1), then $g^{(3)}$ does not change sign on the interval
$(-\tau_{\infty},\tau_{\infty})$ due to the monotonicity of $g^{(2)}$. Hence,
we can infer the sign $s_{k}$ from $\mathcal{C}_{3,k}$. Furthermore, as
$g^{(2)}$ is monotone on $[-\tau_{\infty},\tau_{\infty}]$, it admits an
inverse, which allows for the recovery of $\tau_{k}$ from $\mathcal{C}_{2,k}$.
To learn $\mathcal{C}_{2},\mathcal{C}_{3}$, we rely on numerical
approximations of the quantities $\langle\nabla^{n}f(x),{\hat{w}}_{k}^{\otimes
n}\rangle$, namely, the directional derivatives of the network $f$ along the
approximated weights. We consider the following linear system representation
of the directional derivatives. Computing the derivative for $x=0$ reveals

$\displaystyle\langle\nabla^{n}f(0),{\hat{w}}_{\ell}^{\otimes
n}\rangle=\sum^{m}_{k=1}s_{k}^{n}g^{(n)}(\tau_{k})\langle
s_{k}w_{k},{\hat{w}}_{\ell}\rangle^{n}.$

Denote by $\tilde{G}_{n}\in\mathbb{R}^{m\times m}$ the matrix with entries
$(\tilde{G}_{n})_{\ell,k}={\langle{\hat{w}}_{\ell},s_{k}w_{k}\rangle}^{n}$.
Then, we have

$\displaystyle\tilde{G}_{n}\cdot\mathcal{C}_{n}=\begin{bmatrix}\langle\nabla^{n}f(0),{\hat{w}}_{1}^{\otimes
n}\rangle\\\ \vdots\\\ \langle\nabla^{n}f(0),{\hat{w}}_{m}^{\otimes
n}\rangle\end{bmatrix}:=T_{n}.$ (20)

In (20), $T_{n}$ is a vector containing all directional derivatives of $f$
evaluated at $0$ along the recovered weights
${\hat{w}}_{1},\dots,{\hat{w}}_{m}$. These directional derivatives can be
approximated from only $\mathcal{O}(n)$ evaluations of the network by
numerical differentiation (cf. (G2)), which allows us to compute
$\tilde{T}_{n}\approx T_{n}$. Provided the weight approximations are
sufficiently accurate and incoherent in the sense of Definition 2, the matrix
$\tilde{G}_{n}$ is invertible and can be estimated by
$(\widehat{G}_{n})_{\ell,k}:=\langle{\hat{w}}_{\ell},{\hat{w}}_{k}\rangle^{n}$.
Therefore, we obtain
$\mathcal{C}_{n}\approx\tilde{G}_{n}^{-1}\tilde{T}_{n}\approx\widehat{G}_{n}^{-1}\tilde{T}_{n}$.
This strategy is summarized in Algorithm 3 detailed in supplementary
materials, and the robustness analysis of Proposition 1 makes all the
approximations rigorous. This procedure could be carried out for any order of
directional derivatives, allowing us to benefit from the higher incoherence of
$\langle w_{k}^{\otimes n},w_{\ell}^{\otimes n}\rangle=\langle
w_{k},w_{\ell}\rangle^{n}$. However, for the sake of simplicity and to be more
aligned with our network model, we combine only the second and third order
directional derivatives.

######  Proposition 1 (Parameter initialization).

Consider the teacher network $f$ defined in (1), where the weights
$\\{w_{k}\in\mathbb{S}^{D-1},\,k\in[m]\\}$ satisfy (A2) \- (A3) with constants
$c_{2},c_{3}$ and the activation $g$ satisfies (M1). Then, there exist
constants $C>0$ only depending on $g,c_{2},c_{3},{\tau}_{\infty}$ and
$D_{0}\in\mathbb{N}$, such that, for $m\geq D\geq D_{0},m\log^{2}m\leq D^{2}$,
the following holds. Given
${\hat{w}}_{1},\dots,{\hat{w}}_{m}\in\mathbb{S}^{D-1}$ such that

$\displaystyle\delta_{\max}$
$\displaystyle:=\max_{k\in[m]}\min_{s\in\\{-1,1\\}}\left\lVert
w_{k}-s{\hat{w}}_{k}\right\rVert_{2}\leq\frac{D^{1/2}}{Cm\sqrt{\log m}},$ (21)

Algorithm 3 returns a set of shifts $\hat{\tau}$ such that

$\displaystyle\left\lVert\hat{\tau}-{\tau}\right\rVert_{2}\leq
C\sqrt{m}\epsilon+Cm^{3/2}\left(\frac{\log m}{D}\right)^{3/4}\delta_{\max},$
(22)

where $\epsilon>0$ is the accuracy of the numerical differentiation method.
Furthermore, once the RHS of (22) is smaller than $1$ and
$\epsilon\leq(Cm)^{-1}$, the signs returned by Algorithm 3 are identical to
the ground truth signs.

The proof is postponed to Section B of the supplementary materials. By Theorem
3, we have that $\delta_{\max}$ scales as $(m/\alpha)^{1/4}\epsilon^{1/2}$.
Thus, by taking a suitably small $\epsilon$, (21) is satisfied and, after
omitting poly-logarithmic factors, the dominant term in (22) scales as

$\frac{\epsilon^{1/2}}{\alpha^{1/4}}\frac{m^{7/4}}{D^{3/4}}.$ (23)

By comparing (15) and (23) and recalling that $m$ scales at least linearly in
$D$, it is clear that gradient descent improves upon its initialization, under
a random model for the weight errors. This improvement is also evident if we
evaluate $\Delta_{W,1}$ on the _actual_ weights errors coming from the
proposed algorithmic pipeline (cf. Figure 2).

###  4.2 Local convergence of gradient descent

So far, we have obtained weight approximations ${\widehat{W}}\approx W$ and
shift approximations ${\hat{\tau}}\approx\tau$ of the shallow teacher network
$f$ defined in (1). These parameters $({\widehat{W}},{\hat{\tau}})$ allow us
to define the neural network $\hat{f}$ in (8) and, depending on the accuracy
of the previous steps, we would expect already a strong similarity between
realizations of $\hat{f}$ and $f$. In this section, we explore to what degree
the approximation $\hat{f}$ can further be improved by tuning the shifts
${\hat{\tau}}$ in a teacher-student setting. Assume
$x_{1},\dots,x_{N_{\text{train}}}$ generic inputs and access to
${N_{\text{train}}}$ input-output pairs
$(x_{i},y_{i})_{i\in[N_{\text{train}}]}=(x_{i},f(x_{i}))_{i\in[N_{\text{train}}]}$
of the network $f$. Based on the initial network configuration of $\hat{f}$,
we seek to learn the shifts $\tau$ attributed to ${f}$ by minimizing the
least-squares objective (9) via the gradient descent scheme

$\displaystyle{\hat{\tau}}^{(n+1)}={\hat{\tau}}^{(n)}-\gamma\nabla
J({\hat{\tau}}^{(n)}).$ (24)

Here, $\gamma>0$ represent the step-size of the gradient updates. For the case
${\widehat{W}}=W$, we show that w.h.p. the gradient descent iteration (24)
produces a sequence $(\tau^{(n)})_{n\in\mathbb{N}}$ that converges linearly to
$\tau$ provided that
$\|{\hat{\tau}}^{(0)}-{\tau}\|_{2}=\mathcal{O}(m^{-1/2})$. In the perturbed
case where ${\widehat{W}}\approx W$, we provide an analysis that estimates the
error of the shifts w.r.t. _(i)_ the Frobenius error
$\|{\widehat{W}}-W\|_{F}$, _(ii)_ the alignment between the individual weight
errors $\Delta_{W,O}$ (cf. (14)), and _(iii)_
$\|\sum^{m}_{k=1}w_{k}-{\hat{w}}_{k}\|_{2}$. More precisely, for sufficiently
many training samples $N_{\text{train}}$, the gradient descent iteration will
settle within distance $\Delta_{W,1}$ of the optimal solution.

######  Theorem 4 (Local convergence).

Consider the teacher network $f$ defined in (1), with shifts
${\tau}_{1},\dots,{\tau}_{m}\in[-\tau_{\infty},+\tau_{\infty}]$ and weights
$w_{1},\dots,w_{m}\sim\textrm{Uni}(\mathbb{S}^{D-1})$ that are incoherent
according to Definition 2. Assume $g$ satisfies (M1)-(M2), and consider the
least-squares objective $J$ in (9) constructed with ${N_{\text{train}}}\geq m$
network evaluations $y_{1},\dots,y_{N_{\text{train}}}$ of ${f}$, where
$y_{i}={f}(X_{i})$ and $X_{1},\dots,X_{N_{\text{train}}}\sim{\cal
N}(0,\operatorname{Id}_{D})$. Let $\hat{f}$ be parameterized by
${\widehat{W}}$ and ${\hat{\tau}}$, as in (8). Then, there exists a constant
$C>0$ depending only on $g,\tau_{\infty}$ and $D_{0}>0$ such that the
following holds with probability at least
$1-m\exp(-{N_{\text{train}}}/Cm)-2m^{2}\exp\left(-t/C\right)$ for $t>0$:
Assume $Cm\log^{2}m\leq D^{2},m\geq D\geq D_{0}$ and

$\displaystyle\left\lVert\tau-{{\hat{\tau}}}\right\rVert_{2}+\Delta_{W}\leq\frac{1}{C\sqrt{m}},$
(25)

where
$\Delta_{W}=\Delta_{W,1}+\left(\frac{m^{3}\delta_{\max}^{2}t}{{N_{\text{train}}}}\right)^{1/2}$
and $\Delta_{W,1}$ is given by (13). Then, the gradient descent iteration (24)
with sufficiently small step-size $\gamma>0$ started from
${\hat{\tau}}^{(0)}={\hat{\tau}}$ satisfies

$\displaystyle\|{\hat{\tau}}^{(n)}-{\tau}\|_{2}\leq
2\xi^{n}\|{\hat{\tau}}^{(0)}-{\tau}\|_{2}+C(1-\xi^{n})\Delta_{W}.$ (26)

Note that (25) can always be satisfied within our framework as all factors
depend on $\epsilon$ which can be chosen freely. The proof of Theorem is in
Section C of the supplementary materials. The idea is to express $J$ as a
quadratic form
$J({\hat{\tau}})=({\hat{\tau}}-\tau)^{\top}A({\hat{\tau}})({\hat{\tau}}-\tau)$,
where $A({\hat{\tau}})$ denotes the Jacobian obtained by taking derivatives
w.r.t. the input features. Then, we linearize around the true solution by
replacing $A({\hat{\tau}})$ with $A(\tau)$. Analyzing the idealized objective
$({\hat{\tau}}-\tau)^{\top}A(\tau)({\hat{\tau}}-\tau)$ requires to guarantee
the well-posedness of $A(\tau)$, which we prove by using techniques from the
NTK literature adapted to our setting (Section C.1). The error due to the
replacement of $A({\hat{\tau}})$ with $A(\tau)$ depends on the error in the
weight approximation, and we control it via a delicate argument exploiting
Hermite expansions and the incoherence of the weights (Section C.2).

##  5 Numerical results

We corroborate our theoretical results by testing the pipeline of Algorithm 1,
in order to identify parameters of shallow networks of the type
${f}(x)=\sum^{m}_{k=1}\tanh({w}_{k}^{\top}x+{\tau}_{k})$. As assumed in the
theory, the weights are given by
$w_{1},\dots,w_{m}\sim_{\text{i.i.d.}}\textrm{Uni}(\mathbb{S}^{D-1})$, the
shifts are sampled according to
$\tau_{1},\dots,\tau_{m}\sim_{\text{i.i.d.}}\operatorname{Uni}(-0.5,0.5)$ and
the activation satisfies (M1)-(M2). The number of neurons $m$ depends on the
input dimension $D$ according to the rule
$m=\lceil\frac{2}{5}D^{\beta}\rceil$, where the exponent $1/2\leq\beta\leq 2$
is referred to as the _order of neurons_. The accuracy is evaluated via the
following metrics: _(i)_ the uniform error (of the approximating network),
computed as $E_{\infty}=m^{-1}\max_{i}|f(x_{i})-\hat{f}(x_{i})|$ on a set of
$10^{6}$ unseen Gaussian inputs, _(ii)_ the worst weight approximation, i.e.,
$\max_{k\in[m]}\min_{s\in\\{-1,1\\}}\|{w}_{k}-s{\hat{w}}_{k}\|_{2}$, and
_(iii)_ the error of the shift approximation, i.e.,
$m^{-1/2}\|{\tau}-{\hat{\tau}}\|_{2}$. The scaling $m^{-1}$ of $E_{\infty}$
normalizes for the fact that the range of $f(x)$ grows with $m$ according to
our network model (1). All experiments were performed using one NVIDIA Tesla®
P100 16GB/GPU in a NVIDIA DGX-1.

##### Baseline.

As a baseline for our pipeline, we first try to identify the network
parameters in a standard teacher-student setup. The teacher network is fit by
empirical risk minimization via SGD applied to a student network of identical
architecture. Using 8 minutes of training time with Tensorflow and the
hardware as stated above ($N_{\text{train}}=\frac{5}{2}m\cdot D^{2}$ teacher
evaluations, mini-batch size of 64 and learning rate $0.005$), we obtain the
uniform error depicted in the top row on the left in Figure 1. These results
are averaged over four repetitions. The experiment shows that SGD manages to
identify the network parameters and achieve a low uniform error as long as the
number of neurons $m$ is small, in particular much smaller than a quadratic
scaling such as $m=\lceil\frac{2}{5}D^{2}\rceil$. Furthermore, the results
worsen for growing dimension $D$ despite higher incoherence of the network
weights, possibly due to the fixed training time and learning rate. In an
attempt to improve these results, we additionally run SGD for 50 minutes and
several different learning rates, fixing the case $D=50$. The results, shown
in the top row on the right in Figure 1, indicate an improvement of SGD for
certain hyperparameter combinations, yet we were not able to find a suitable
tuning for $D=50,m=1000$. For this experiment, we choose
$\tau_{1},\dots,\tau_{m}\sim_{\text{i.i.d.}}\mathcal{N}(0,0.05)$, thus the
ground-truth shifts are closer to the initialization (set at $0$) than if they
are uniform in $[-0.5,0.5]$, which should facilitate the task of the SGD
algorithm.

Figure 1:  Performance of parameter identification of shallow networks with
$\tanh$ activations, $m$ neurons and input size $D$ via SGD for shifts
$\tau_{k}\sim\mathcal{N}(0,0.05)$ (top row), our pipeline for shifts
$\tau_{k}\sim\operatorname{Uni}(-0.5,0.5)$ (bottom row).

##### Recovery pipeline.

We now discuss the results of our recovery pipeline in Algorithm 1 to identify
shallow networks with $\tanh$ activation. For the weight recovery, we use
$N_{h}=\lceil\log(D)m\rceil$ Hessian approximations, which are computed via
central finite differences with step-size $\epsilon_{\text{FD}}=0.01$ and are
anchored at evaluations $x_{1},\dots,x_{N_{h}}\sim_{\text{i.i.d.}}{\cal
N}(0,\operatorname{Id}_{D})$. Then, we run $R=5m\log(m)$ SPM iterations (17)
in parallel for $10^{3}$ steps with step-size $\gamma=2$. The initial shifts
computed by the parameter initialization are finalized via (stochastic)
gradient descent as described in Section 4. We use $N_{\text{train}}=m\cdot
D^{2}$ samples, learning rate $\gamma=10^{-3}$ and batch size $64$. The
training input points are drawn from a standard Gaussian distribution. The
refinement of the shifts (by gradient descent) is timed out after $180$
seconds, or once we reach a training error below $10^{-8}$.

The results of our pipeline in the bottom row of Figure 1 demonstrate
successful recovery of all weights and shifts consistently over $10$
repetitions, and for all combinations of $m,D$. For $\beta=2$ (or
$m=\lceil\frac{2}{5}D^{2}\rceil$) the performance of the weight recovery is
worse for small $D$. The causes of this effect may be two-fold: the weights do
not yet behave statistically as in the average case scenario for larger $D$;
and the gap between $m=\frac{2}{5}D^{2}$ and the theoretical limit for weight
recovery, $m=D(D-1)/2$, decreases in $D$. Moreover, we emphasize that the time
spent for the weight recovery (which includes the time necessary to
approximate all Hessian matrices by numerical differentiation) is in the order
of seconds, reaching a maximum of $112s$ for $D=50,\beta=2$. The overall
runtime of the pipeline is below 5 minutes over all individual runs.

Figure 2:  Comparison between the guaranteed accuracy of the shift
initialization (red), the term $\Delta_{W,1}$ (dashed red) and the sum of
residual errors $\|\sum^{m}_{k=1}w_{k}-{\hat{w}}_{k}\|_{2}$ (blue) for weights
approximated by our pipeline and $D=50$.

##### Improvement of the shifts by GD.

In Figure 2, we compare the error bound (22) on the initial shifts with
$\Delta_{W,1}$ (cf. (13)), where for simplicity the constants $C$ are taken to
be $1$ in both statements. The results are averaged over $10$ realizations.
The plot shows that _(i)_ the sum of the residuals
$\|\sum^{m}_{k=1}w_{k}-{\hat{w}}_{k}\|_{2}$ in blue has only a negligible
contribution to $\Delta_{W,1}$, and hence _(ii)_ by settling within distance
$\Delta_{W,1}$ of the true shifts, GD will improve over the initialization.

##  6 Concluding remarks

In this paper, we give an algorithm with provable guarantees for the finite
sample identification of shallow networks _with biases_ , where the number of
neurons $m$ is roughly $\mathcal{O}(D^{2})$. By doing so, we improve upon
previous work [25, 30], which neglects the role of biases and is limited to
$m=\mathcal{O}(D)$. Let us finally mention that [23, 22] have provided partial
results on finite sample identification of deep networks. Thus, giving a
complete pipeline for the deep case, which keeps into full consideration also
the important role of biases, is an interesting future direction.

##  Appendix A Proofs: Weight recovery

Algorithm 2 summarizes the first step of the reconstruction pipeline which is
the weight recovery. For more details on the exact procedure we refer to
Section 3. This section is concerned with the proof of Theorem 3, which
provides a uniform bound on the approximation error associated with the weight
recovery. Additionally, we characterize the incoherence of the resulting
approximated weights in terms of the numerical accuracy. A large part of the
proofs in this section will operate under the assumptions that vectors, which
are drawn uniformly from a high-dimensional sphere, are well separated. To
make this more concrete, we rely on a result due to [32] which allows the
application of the deterministic incoherence properties (A1) -(A3) stated in
Definition 2 to the ground truth weights
$w_{1},\dots,w_{m}\in\mathbb{S}^{D-1}$ which are modeled by a uniform
spherical distribution according to our network model (cf. Section 2).

######  Proposition 2 ([32, Prop. 13]).

Let $w_{1},\dots,w_{m}$ be drawn independently from
$\textrm{Uni}(\mathbb{S}^{D-1})$. If $m=o(D^{2})$, then, for any arbitrary
constant $\delta\in(0,1)$, there exist constants $C>0$ and
$D_{0}\in\mathbb{N}$ depending only on $\delta$ such that for all $D\geq
D_{0}$, and with probability at least

$\displaystyle 1-m^{-1}-2\exp(-C\delta^{2}D)-C\left(\frac{e\cdot
D}{\sqrt{m}}\right)^{-C\sqrt{m}}$ (27)

conditions (A1) \- (A3) hold with constants $c_{2},c_{3}<C$.

Input: Shallow neural network $f$, number of neurons $m$, number of Hessian
locations $N_{h}$, stepsize $\gamma>0$, $\beta$ threshold for rejection of
spurious local maximizers

1 Draw independent samples $x_{1},\dots,x_{N}\sim{\cal
N}(0,\operatorname{Id})$.

2 Construct the matrix
$\displaystyle\widehat{M}:=\begin{bmatrix}\operatorname{vec}(\Delta^{2}{f}(x_{1}))&\dots&\operatorname{vec}(\Delta^{2}{f}(x_{N}))\end{bmatrix}\in\mathbb{R}^{D^{2}\times
N_{h}}.$

3 Denote by $\mathcal{P}_{\widehat{\mathcal{W}}}$ the orthogonal projection
onto the $m$-th left singular subspace of $\widehat{M}$.

4 Define $P_{\widehat{\mathcal{W}}}$ as the orth. proj. in matrix space
corresponding to $\mathcal{P}_{\widehat{\mathcal{W}}}$

5 Set ${\cal U}\leftarrow\emptyset$

6 while  _$|{\cal U}| <m$_ do

7 Sample $u_{0}\sim\textrm{Unif}(\mathbb{S}^{D-1})$

8 Iterate projected gradient ascent  $u\leftarrow
P_{\mathbb{S}^{D-1}}(u+2\gamma P_{\widehat{\mathcal{W}}}((u)^{\otimes 2})u)$
until convergence, and denote the vector of the final iteration by $\hat{u}$.

9 if  _$\left\lVert P_{\widehat{\mathcal{W}}}(\hat{u}^{\otimes
2})\right\rVert_{F}^{2} >\beta$_ then

10 if  _$\hat{u}\not\in{{\cal U}}$ and $-\hat{u}\not\in{{\cal U}}$_ then

11 ${\cal U}\leftarrow{\cal U}\cup\\{\hat{u}\\}$

12

13 end if

14

15 end if

16

17 end while

Output: ${\cal U}$

Algorithm 2 Weight recovery

##### Proof Sketch of Theorem 3

The proof of Theorem 3 relies on two individual auxiliary statements. First, a
subspace approximation bound covered in Lemma 1, that controls the error
$\left\lVert P_{{\cal W}}-P_{\widehat{\mathcal{W}}}\right\rVert_{F\rightarrow
F}$. Recall that $\widehat{\mathcal{W}}$ is constructed to approximate the
matrix space

$\displaystyle{\cal W}=\operatorname{span}\\{w_{1}\otimes w_{1},\dots
w_{m}\otimes w_{m}\\}\subset\operatorname{Sym}(\mathbb{R}^{D\times D})$

from which individual weights can be identified as the rank-1 spanning
elements. It is noteworthy that the proof of Lemma 1 as well as Algorithm 2
make use of the following convention: We associated every matrix subspace with
a classical vector space induced by vectorization. The vectorization of a
matrix is denoted by the operator $\operatorname{vec}(\cdot)$ whose output
applied to a matrix $X\in\mathbb{R}^{a\times b}$ is the vector in
$\mathbb{R}^{a\cdot b}$ containing the columns of $X$ stacked on top of other,
i.e.

$\displaystyle\operatorname{vec}\left(\begin{bmatrix}\vline&&\vline\\\
x_{1}&\dots&x_{b}\\\ \vline&&\vline\\\
\end{bmatrix}\right)=\begin{pmatrix}x_{1}\\\ \vdots\\\ x_{b}\end{pmatrix}.$

This allows us to associate a space like ${\cal
W}\subset\operatorname{Sym}(\mathbb{R}^{D\times D})$ with the space

$\displaystyle\operatorname{span}\\{\operatorname{vec}(w_{1}\otimes
w_{1}),\dots,\operatorname{vec}(w_{m}\otimes w_{m})\\}\mathbb{R}^{D^{2}}.$

######  Lemma 1.

Consider the teacher network $f$ defined in (1). Assume the activation $g$
satisfies (M1) \- (M2) and $f$ satisfies the learnability condition (M3) for
some $\alpha>0$. Furthermore assume that the network weights
$w_{1},\dots,w_{m}\in\mathbb{S}^{D-1}$ fulfill (A2) of Definition 2 with
constant $c_{2}$. Let $P_{\cal W}$ be the orthogonal approximation onto ${\cal
W}=\operatorname{span}\\{w_{1}\otimes w_{1},\dots w_{m}\otimes w_{m}\\}$ and
let $P_{\widehat{\mathcal{W}}}$ be constructed as described in Algorithm 2.
Then there exists a constant $C>0$ depending only on $g$ and $c_{2}$, such
that for numerical diff. accuracy $\epsilon<\frac{\sqrt{\alpha}}{C\sqrt{m}}$
and $N_{h}>t(m+m^{2}\log(m)/D)$ for some $t\geq 1$ we have

$\displaystyle\left\lVert P_{{\cal
W}}-P_{\widehat{\mathcal{W}}}\right\rVert_{F\rightarrow F}\leq
C\sqrt{m/\alpha}\cdot\epsilon,$ (28)

with probability at least $1-D^{2}\exp\left(-\frac{t\alpha}{C}\right)$.

###### Proof.

Consider $X_{1},\dots,X_{N_{h}}$ independent copies of a standard Gaussian,
i.e. $X_{i}\sim{\cal N}(0,\operatorname{Id}_{D})$. Denote by
$\mathcal{P}_{\cal W}\in\mathbb{R}^{D^{2}\times D^{2}}$ the orthogonal
projection matrix onto
$\operatorname{span}\left\\{\operatorname{vec}({w}_{k}\otimes{w}_{k})\,|\,i=1,\ldots,m\right\\}$
and by $M$ the matrix with columns given by the exact vectorized Hessians at
the inputs $X_{1},\ldots,X_{N_{h}}$, i.e.

$\displaystyle
M:=\begin{bmatrix}\operatorname{vec}(\nabla^{2}f(X_{1}))&\dots&\operatorname{vec}(\nabla^{2}f(X_{N_{h}}))\end{bmatrix}\in\mathbb{R}^{D^{2}\times
N_{h}}.$ (29)

We associate the matrix subspaces ${\cal W}$ and $\widehat{\cal W}$ with their
corresponding $D^{2}$-dimensional vector subspaces described by the orthogonal
projection matrices $\mathcal{P}_{{\cal
W}},\mathcal{P}_{\widehat{\mathcal{W}}}$, respectively. Note that

$\displaystyle\left\lVert P_{{\cal
W}}-P_{\widehat{\mathcal{W}}}\right\rVert_{F\rightarrow F}$
$\displaystyle=\sup_{\left\lVert M\right\rVert_{F}=1}\left\lVert P_{{\cal
W}}(M)-P_{\widehat{\mathcal{W}}}(M)\right\rVert_{F}=\left\lVert\mathcal{P}_{{\cal
W}}-\mathcal{P}_{\widehat{\mathcal{W}}}\right\rVert$

with $\|\cdot\|$ describing the ordinary spectral normal in
$\mathbb{R}^{D^{2}}$. Hence, to prove the result, we can rely on the well-
known Wedin bound, see for instance [25, 23, 22, 32], giving

$\displaystyle\left\lVert P_{{\cal
W}}-P_{\widehat{\mathcal{W}}}\right\rVert_{F\rightarrow
F}=\left\lVert\mathcal{P}_{{\cal
W}}-\mathcal{P}_{\widehat{\mathcal{W}}}\right\rVert\leq\frac{\|M-\widehat{M}\|_{F}}{\sigma_{m}(\widehat{M})},$
(30)

for as long as $\sigma_{m}(\widehat{M})>0$. We continue to provide separate
bounds for the numerator and denominator of (30). For the numerator we obtain

$\displaystyle\|M-\widehat{M}\|_{F}$
$\displaystyle\leq\sqrt{N_{h}}\max_{i\in[N_{h}]}\left\lVert\nabla^{2}{f}(X_{i})-\Delta^{2}{f}(X_{i})\right\rVert_{F}$
$\displaystyle\leq\sqrt{N_{h}m}\max_{\begin{subarray}{c}i\in[N_{h}]\\\
k\in[m]\end{subarray}}\left\lVert\nabla^{2}g(w_{k}^{\top}X_{i}+{\tau}_{k})-\Delta^{2}g({w}_{k}^{\top}X_{i}+{\tau}_{k})\right\rVert_{F}$
$\displaystyle\leq\max_{k\in[m]}C_{\Delta}\sqrt{N_{h}m}\left\lVert{w}_{k}\otimes{w}_{k}\right\rVert_{F}\epsilon=C_{\Delta}\sqrt{N_{h}m}\epsilon,$

where we used the linearity of $\Delta^{2},\nabla^{2}$ in the second step and
our assumptions on the numerical differentiation method (G2) in the last line
which gives rise to the constant $C_{\Delta}$ that only depends on $g$. For
the denominator in (30) we use Weyl’s inequality [62] which leads to the lower
bound

$\displaystyle\sigma_{m}(\widehat{M})\geq\sigma_{m}(M)-\|M-\widehat{M}\|\geq\sigma_{m}(M)-\|M-\widehat{M}\|_{F}\geq\sigma_{m}(M)-C_{\Delta}\sqrt{N_{h}m}\epsilon.$
(31)

Lastly, we need to control $\sigma_{m}(M)$ by a concentration argument in
combination with the learnability assumption (M3) of Section 2. We first
express $\sigma_{m}(M)$ as sum of independent matrices:

$\displaystyle\sigma_{m}(M)^{2}=\sigma_{m}(MM^{\top})=\sigma_{m}\left(\sum^{N_{h}}_{i=1}\operatorname{vec}(\nabla^{2}f(X_{i}))\otimes\operatorname{vec}(\nabla^{2}f(X_{i}))\right).$
(32)

Denote
$A_{i}=\operatorname{vec}(\nabla^{2}{f}(X_{i}))\otimes\operatorname{vec}(\nabla^{2}{f}(X_{i}))$.
By (M3) we know that

$\displaystyle\sigma_{m}\left(\sum^{N_{h}}_{i=1}\mathbb{E}A_{i}\right)=N_{h}\alpha>0.$

We will make use of the matrix Chernoff (see [58] Corollary 5.2 and the
following remark) which states that

$\displaystyle\mathbb{P}\left(\sigma_{m}\left(\sum^{N_{h}}_{i=1}A_{i}\right)\leq(1-s)\sigma_{m}\left(\sum^{N_{h}}_{i=1}\mathbb{E}A_{i}\right)\right)\leq
D^{2}\exp\left(-(1-s)^{2}\sigma_{m}\left(\sum^{N_{h}}_{i=1}\mathbb{E}A_{i}\right)/2K\right)$
(33)

for $s\in[0,1]$ and $K=\max_{i\in[N_{h}]}\left\lVert A_{i}\right\rVert_{2}$.
The norm of $A_{i}$ can be bound uniformly over all $x\in\mathbb{R}^{D}$ by

$\displaystyle\left\lVert\operatorname{vec}(\nabla^{2}f(X_{i}))\otimes\operatorname{vec}(\nabla^{2}{f}(X_{i}))\right\rVert_{2}$
$\displaystyle\leq\sup_{x\in\mathbb{R}^{D}}\left\lVert\operatorname{vec}(\nabla^{2}{f}(x))\right\rVert^{2}_{2}=\sup_{x\in\mathbb{R}^{D}}\left\lVert\nabla^{2}{f}(x)\right\rVert^{2}_{F}$
$\displaystyle=\sup_{x\in\mathbb{R}^{D}}\left\lVert\sum^{m}_{k=1}g^{(2)}({w}_{k}^{\top}x+{\tau}_{k}){w}_{k}\otimes{w}_{k}\right\rVert_{F}^{2}$
$\displaystyle=\sup_{x\in\mathbb{R}^{D}}\sum^{m}_{k,\ell=1}g^{(2)}({w}_{k}^{\top}x+{\tau}_{k})g^{(2)}({w}_{\ell}^{\top}x+{\tau}_{\ell})\langle{w}_{k},{w}_{\ell}\rangle^{2}$
$\displaystyle\leq\kappa^{2}\sum^{m}_{k,\ell=1}\langle{w}_{k},{w}_{\ell}\rangle^{2}\leq\kappa^{2}(m+c_{2}m(m-1)\log
m/D).$

The last inequality follows by the incoherence assumption (A2) from the
initial statement. Combining this with (33) for $s=1/2$ together with the
bound on the spectrum of the expectation yields

$\displaystyle\mathbb{P}\left(\sigma_{m}\left(\sum^{N_{h}}_{i=1}A_{i}\right)\geq\frac{1}{2}N_{h}\alpha\right)\geq
1-D^{2}\exp\left(-\frac{N_{h}D\alpha}{8\kappa^{2}(Dm+c_{2}m^{2}\log
m)}\right).$ (34)

Conditioning on this event, and assuming
$\epsilon<\sqrt{\alpha/8C^{2}_{\Delta}m}$ the initial subspace bound now holds
as

$\displaystyle\left\lVert P_{{\cal
W}}-P_{\widehat{\mathcal{W}}}\right\rVert_{F\rightarrow F}$
$\displaystyle\leq\frac{\left\lVert
M-\widehat{M}\right\rVert_{2}}{\sigma_{m}(\widehat{M})}\leq\frac{C_{\Delta}\sqrt{N_{h}m}\epsilon}{\sqrt{\frac{1}{2}N_{h}\alpha}-C_{\Delta}\sqrt{N_{h}m}\epsilon}=\frac{C_{\Delta}\sqrt{m}\cdot\epsilon}{\sqrt{\frac{\alpha}{2}}-C_{\Delta}\sqrt{m}\cdot\epsilon}$
(35)
$\displaystyle\leq\frac{\sqrt{2}C_{\Delta}\sqrt{m}\cdot\epsilon}{\sqrt{{\alpha}}}$
(36)

with said probability. The final result follows by applying the bound on
$\epsilon$ onto the denominator. More precisely, we need that $C>2C_{\Delta}$
to fulfill (35) and $C>8\kappa^{2}\max\\{1,c_{2}\\}$ which implies

$\displaystyle
1-D^{2}\exp\left(-\frac{N_{h}D\alpha}{8\kappa^{2}(Dm+c_{2}m^{2}\log
m)}\right)\leq 1-D^{2}\exp\left(-t\alpha/C\right),$

due to our assumption that $N_{h}>t(m+m^{2}\log(m)/D)$. ∎

The second part of Algorithm 2 performs projected gradient ascent to find the
local maximizers of

$\displaystyle u\mapsto\left\lVert P_{\widehat{\mathcal{W}}}(u\otimes
u)\right\rVert^{2}_{F},u\in\mathbb{S}^{D-1}.$ (37)

The landscape for this functional, for $m=o(D^{2})$, has been recently
analyzed (in particular the properties of its local maximizers) in [32] for
the general problem of symmetric tensor decomposition. We now provide one of
their main statements adopted to the matrix scenario.

######  Theorem 5 ([32, Theorem 16]).

Let $m,D\in\mathbb{N}$ such that $m\log^{2}(m)\leq D^{2}$. Assume
${w}_{1},\dots,{w}_{m}$ satisfy (A1) \- (A3) of Definition 2 for some
$\delta,c_{1},c_{2},c_{3}>0$. Then there exists $\delta_{0}$, depending only
on $c_{2},c_{3}$ and $D_{0},\Delta_{0},C$ which depend additionally on
$c_{1}$, such that if $\delta<\delta_{0},D>D_{0}$ and $\left\lVert P_{{\cal
W}}-P_{\widehat{\mathcal{W}}}\right\rVert_{F\rightarrow F}\leq\Delta_{0}$, the
program (37) has exactly $2m$ second-order critical points in the superlevel
set

$\displaystyle\left\\{x\in\mathbb{S}^{D-1}\middle|\,\left\lVert
P_{\widehat{\mathcal{W}}}(x\otimes x)\right\rVert^{2}_{F}\geq
Cm\log^{2}(m)/D^{2}+5\left\lVert P_{{\cal
W}}-P_{\widehat{\mathcal{W}}}\right\rVert_{F\rightarrow F}\right\\}.$ (38)

Each of these critical points is a strict local maximizer for
$\operatorname{argmax}_{u\in\mathbb{S}^{D-1}}\left\lVert
P_{\widehat{\mathcal{W}}}(u\otimes u)\right\rVert^{2}_{F}$. Furthermore, for
each such point $x^{*}$, there exists a unique $k\in[m]$ such that

$\displaystyle\min_{s\in\\{-1,1\\}}\left\lVert
x^{*}-sw_{k}\right\rVert_{2}\leq\sqrt{\left\lVert P_{{\cal
W}}-P_{\widehat{\mathcal{W}}}\right\rVert_{F\rightarrow F}}.$ (39)

This establishes that the local maximizers of (37) that belong to the
superlevel set (38) will be close to one of the weights $w_{1},\dots,w_{m}$ up
to sign. The projected gradient ascent iteration in Algorithm 2 converges
monotonically to one of the constrained stationary points of (37) as shown in
[33, Theorem 5.1]. We are now ready to prove the main result on the weight
recovery which relies on the lemma above, Proposition 2, and the machinery
developed in [32] represented by Theorem 5.

###### Proof of Theorem 3.

The weights ${w}_{1},\dots,{w}_{m}$ of $f$ are drawn uniformly from the unit
sphere. By Proposition 2, and for any $\delta_{0}\in(0,1)$, there exists
$D_{1}\in\mathbb{N},C_{1}>0$ depending only on $\delta_{0}$ such that for all
$D\geq D_{1}$ this set of weights fulfills conditions (A1) \- (A3) of
Definition 2 with constants $c_{2},c_{3}<C_{1}$ and with probability at least

$1-m^{-1}-2\exp(-C_{1}\delta_{0}^{2}D)-C_{1}\left(\frac{e\cdot
D}{\sqrt{m}}\right)^{-C_{1}\sqrt{m}}.$

We condition on this event and denote it by $E_{1}$ for the remaining part of
the proof. Now, due to the incoherence of the weights and according to our
initial assumption which includes $N_{h}>t(m+m^{2}\log(m)/D)$, the conditions
of Lemma 1 are met which provides an error bound for the subspace which is
constructed in the first part of Algorithm 2, such that

$\displaystyle\left\lVert P_{{\cal
W}}-P_{\widehat{\mathcal{W}}}\right\rVert_{F\rightarrow F}\leq
C_{2}\sqrt{m/\alpha}\cdot\epsilon,$ (40)

with probability at least $1-D^{2}\exp\left(-t\alpha/C_{2}\right)$ for a
constant $C_{2}$ only depending on $g$. Denote the event that this subspace
bound holds by $E_{2}$ and assume it occurs, which only depends on the number
of Hessians $N_{h}$ in relationship to $D,m$. Note that $\delta_{0}$ can be
freely chosen in $(0,1)$. By Theorem 5 there exist constants
$D_{2},\Delta_{0},C_{3}$, such that for $D\geq D_{2}$ and $\left\lVert
P_{{\cal W}}-P_{\widehat{\mathcal{W}}}\right\rVert_{F\rightarrow
F}\leq\Delta_{0}$, the local maximizers of the program
$\operatorname{argmax}_{u\in\mathbb{S}^{D-1}}\left\lVert
P_{\widehat{\mathcal{W}}}(u\otimes u)\right\rVert^{2}_{F}$ fulfill

$\displaystyle\min_{s\in\\{-1,1\\}}\left\lVert
x^{*}-s{w}_{k}\right\rVert_{2}\leq\sqrt{\left\lVert P_{{\cal
W}}-P_{\widehat{\mathcal{W}}}\right\rVert_{F\rightarrow
F}}\leq\sqrt{C_{2}\sqrt{m/\alpha}\cdot\epsilon},$ (41)

as long as they belong to the level set

$\displaystyle\left\\{x\in\mathbb{S}^{D-1}\middle|\,\left\lVert
P_{\widehat{\mathcal{W}}}(x\otimes x)\right\rVert^{2}_{F}\geq
C_{3}m\log^{2}(m)/D^{2}+5C_{2}\sqrt{m/\alpha}\cdot\epsilon\right\\}.$

By iterating projected gradient ascent until convergence, every vector
$\hat{u}$ will be one of the these local maximizers. Also note that by
construction all vectors returned by Algorithm 2 must have unit norm, hence
${\cal U}\subset\mathbb{S}^{D-1}$. We need to make sure that level set is not
empty, which is guaranteed for $C_{3}m\log^{2}(m)/D^{2}\leq\frac{1}{4}$ and
$\epsilon\leq\frac{\alpha^{1/2}}{20C_{2}\sqrt{m}}$ which leads to the
threshold

$\displaystyle
C_{3}m\log^{2}(m)/D^{2}+5C_{2}\sqrt{m/\alpha}\cdot\epsilon\leq\frac{1}{4}+\frac{1}{4}=\frac{1}{2}.$
(42)

Therefore, only considering local maximizers that fulfill $\left\lVert
P_{\widehat{\mathcal{W}}}(x\otimes x)\right\rVert^{2}_{F}\geq 1/2$ will
guarantee that all local maximizers are of the kind which satisfies (41).
Before we conclude, there are still some points that need to be addressed. To
achieve the bound (41) we had to assume that $\left\lVert P_{{\cal
W}}-P_{\widehat{\mathcal{W}}}\right\rVert_{F\rightarrow F}\leq\Delta_{0}$.
This is true due to (40) given the accuracy satisfies
$\epsilon\leq\frac{\Delta_{0}\alpha^{1/2}}{C_{3}m^{1/2}}$ which is clearly
realizable by our initial assumptions on $\epsilon$, since $\Delta_{0}$ is
independent of $m,D$. Hence, by further unifying also the constants
$C_{1},C_{2},C_{3},D_{1},D_{2}$, we showed that there exists constants
$C>0,D_{0}\in\mathbb{N}$ such that for $D\geq D_{0}$ and $Cm\log^{2}m\leq
D^{2}$ all vectors $u\in{\cal U}$ returned by Algorithm 2 ran with num.
accuracy $\epsilon\leq\frac{\sqrt{\alpha}}{C\sqrt{m}}$ will fulfill the
uniform error bound,

$\displaystyle\min_{s\in\\{-1,1\\}}\left\lVert
x^{*}-s\bar{w}_{k}\right\rVert_{2}\leq C(m/\alpha)^{1/4}\epsilon^{1/2},$ (43)

and this result holds with the combined probability

$\displaystyle
1-D^{2}\exp\left(-t\alpha/C\right)-m^{-1}-2\exp(-D/C)-C\left(\frac{e\cdot
D}{\sqrt{m}}\right)^{-\sqrt{m}/C}.$ (44)

∎

The following short result does show a useful property of the spectrum of
higher order Grammians which will prove useful for the upcoming part about
parameter initialization.

######  Lemma 2 (Higher order Hadamard products).

In the setting of Definition 2 we have
$\lambda_{\min}(G_{2+\widetilde{n}})\geq\lambda_{\min}(G_{2})$ and thus in
particular $\left\lVert G_{2+\widetilde{n}}^{-1}\right\rVert_{2}\leq c_{3}$
for all $\widetilde{n}\in\mathbb{N}_{\geq 0}$ as well.

###### Proof.

For each $n\in\mathbb{N}$ the matrix $G_{n}$ is a Grammian of the tensors
$\\{w_{1}^{\otimes n},\ldots,w_{m}^{\otimes n}\\}$ and as such it is a
positive semidefinite matrix. Since $\lambda_{\min}(A\odot
B)\geq\min_{i}a_{ii}\lambda_{\min}(B)$ for any pair of positive semidefinite
matrices $A,B$, see [8, Theorem 3], we thus have

$\displaystyle\lambda_{\min}(G_{2+\widetilde{n}})=\lambda_{\min}(G_{2}\odot
G_{\widetilde{n}})\geq\lambda_{\min}(G_{2})\min_{i}\langle
w_{i},w_{i}\rangle^{\widetilde{n}}=\lambda_{\min}(G_{2}).$

∎

Let us conclude this section with an important auxiliary result. As said
before we generally operate in a setting where the ground truth weight are
sufficiently incoherent and fulfill (A1) \- (A3) of Definition 2. It is clear
that these properties translate to accurate approximations of the ground truth
weights. The following result makes this explicit alongside with a few other
minor technical results which will be used throughout the remaining proofs.

######  Lemma 3 (Incoherence of approximated Weights).

Assume the ground truth weights $\\{w_{k}\in\mathbb{S}^{D-1}|k\in[m]\\}$
fulfill (A1) \- (A3) of Definition 2 with constants $c_{2},c_{3}$ and that
$D\leq m$. Then there exists a constant $C>0$ only depending on $c_{2},c_{3}$
such that for approximations $\\{{\hat{w}}_{k}\in\mathbb{S}^{D-1}|k\in[m]\\}$
which satisfy the error bound

$\displaystyle\max_{k\in[m]}\min_{s\in\\{-1,1\\}}\left\lVert
s{\hat{w}}_{k}-{w}_{k}\right\rVert_{2}=\delta_{\max}\leq\frac{1}{C}\frac{D^{1/2}}{m\sqrt{\log
m}}$ (45)

condition (A2) \- (A3) of Definition 2 holds with constants $2c_{2},2c_{3}$.
Furthermore, denote $\tilde{G}_{n}\in\mathbb{R}^{m\times m}$ the matrix with
entries $\tilde{G}_{n,\ell
k}=\langle{\hat{w}}_{\ell},{s}_{k}{w}_{k}\rangle^{n}$, where $s_{k}$ are the
ground truth signs. Then there exists $D_{0}$ such that for $m\geq D\geq
D_{0}$, $n=2,3$ the following holds true:

  1. (i)

For all $k\neq\ell$ we have
$\langle{\hat{w}}_{k},s_{\ell}w_{\ell}\rangle^{2}\leq 2c_{2}\log(m)/D$

  2. (ii)

$\tilde{G}_{n}$ is invertible and $\|\tilde{G}_{n}^{-1}\|\leq 3c_{2}$

  3. (iii)

Denote by $\tilde{G}_{n}\in\mathbb{R}^{m\times m}$ the matrix with entries
$\tilde{G}_{n,\ell k}=\langle{\hat{w}}_{\ell},{s}_{k}{w}_{k}\rangle^{n}$, then

$\displaystyle\left\lVert\tilde{G}_{n}-\widehat{G}_{n}\right\rVert\leq
Cm\left(\frac{\log m}{D}\right)^{(2n-1)/4}\delta_{\max}.$ (46)

###### Proof.

W.l.o.g. we can assume that $C$ is choosen such that

$\displaystyle\max_{k\in[m]}\min_{s\in\\{-1,1\\}}\left\lVert
s{\hat{w}}_{k}-w_{k}\right\rVert_{2}=\delta_{\max}\leq\min\left\\{\frac{1}{8}\left(\frac{c_{2}\log
m}{D}\right)^{1/2},\frac{D^{1/2}}{8c_{3}m\sqrt{2c_{2}\log m}}\right\\}$ (47)

holds. We start by showing (A2) for the approximated weights. Pick any
$k,\ell\in[m],k\neq\ell$. A first observation is that we can disregard the
sign that appears in (45) since
$\langle{\hat{w}}_{k},{\hat{w}}_{\ell}\rangle^{2}=\langle-{\hat{w}}_{k},{\hat{w}}_{\ell}\rangle^{2}$
. So w.l.o.g. assume that both signs are correct and therefore
$\left\lVert{\hat{w}}_{k}-w_{k}\right\rVert_{2}\leq\delta_{\max}$ and
$\left\lVert{\hat{w}}_{\ell}-{w}_{\ell}\right\rVert_{2}\leq\delta_{\max}$.
Then

$\displaystyle\langle{\hat{w}}_{k},{\hat{w}}_{\ell}\rangle^{2}$
$\displaystyle\leq\left(\left|{\langle{w}_{k},{w}_{\ell}\rangle}\right|+\left|{\langle{\hat{w}}_{k}-{w}_{k},{w}_{\ell}\rangle}\right|+\left|{\langle{w}_{k},{\hat{w}}_{\ell}-w_{\ell}\rangle}\right|+\left|{\langle{\hat{w}}_{k}-w_{k},{\hat{w}}_{\ell}-{w}_{\ell}\rangle}\right|\right)^{2}$
(48)
$\displaystyle\leq\left(\left|{\langle{w}_{k},{w}_{\ell}\rangle}\right|+2\delta_{\max}+\delta_{\max}^{2}\right)^{2}\leq\left|{\langle
w_{k},w_{\ell}\rangle}\right|^{2}+6\delta_{\max}\left|{\langle
w_{k},w_{\ell}\rangle}\right|+9\delta_{\max}^{2}$
$\displaystyle\leq\frac{c_{2}\log m}{D}+6\left(\frac{c_{2}\log
m}{D}\right)^{1/2}\delta_{\max}+9\delta_{\max}^{2}$
$\displaystyle\leq\frac{c_{2}\log m}{D}+\frac{48+9}{64}\frac{c_{2}\log
m}{D}\leq\frac{2c_{2}\log m}{D},$

which proves that (A2) is fulfilled by the approximated weights for a constant
$2c_{2}$. Moving on to (A3), we need to bound the minimal eigenvalue of
$\widehat{G}_{n}=({\widehat{W}}^{\top}{\widehat{W}})^{\odot n}$ from below.
Assuming $\widehat{G}_{2}$ is invertible, we know by Lemma 2 that

$\displaystyle\|\widehat{G}_{n}^{-1}\|\leq\|\widehat{G}_{2}^{-1}\|\quad\text{
for all }\quad n\geq 2.$

Thus, it is sufficient to show that (A3) holds for the approximated weigths
for $n=2$. Denote $G_{2}=(W^{\top}W)^{\odot 2}$. Clearly
$G_{2},\widehat{G}_{2}$ are symmetric, and since (A3) holds for the ground
truth weights we know that the minimal eigenvalue of $G_{2}$ can be bounded by
a constant $\left|{\sigma_{m}({G}_{2})}\right|\geq c_{3}^{-1}$. Hence, by
Weyl’s inequality we have

$\displaystyle\left|{\sigma_{m}(\widehat{G}_{2})}\right|\geq
c_{3}^{-1}-\left\lVert\widehat{G}_{2}-{G}_{2}\right\rVert.$ (49)

Our goal is to find an upper bound the spectral norm on the right hand side,.
Note that the diagonal of both matrices is identical due to the fact that all
columns of ${\widehat{W}}$ and ${W}$ have unit norm, so we focus on the off
diagonal exclusively. Via Gershgorin’s circle theorem we attain

$\displaystyle\left\lVert\widehat{G}_{n}-{G}_{n}\right\rVert$
$\displaystyle\leq\max_{k\in[m]}\sum^{m}_{\begin{subarray}{c}\ell=1\\\
\ell\neq
k\end{subarray}}\left|{\langle{\hat{w}}_{k},{\hat{w}}_{\ell}\rangle^{2}-\langle
w_{k},w_{\ell}\rangle^{2}}\right|$
$\displaystyle=\max_{k\in[m]}\sum^{m}_{\begin{subarray}{c}\ell=1\\\ \ell\neq
k\end{subarray}}\left|{\langle
s_{k}{\hat{w}}_{k},s_{\ell}{\hat{w}}_{\ell}\rangle^{2}-\langle
w_{k},w_{\ell}\rangle^{2}}\right|$
$\displaystyle\leq\max_{k\in[m]}\sum^{m}_{\begin{subarray}{c}\ell=1\\\
\ell\neq k\end{subarray}}\left|{\langle
s_{k}{\hat{w}}_{k},s_{\ell}{\hat{w}}_{\ell}\rangle+\langle
w_{k},w_{\ell}\rangle}\right|\left|{\langle
s_{k}{\hat{w}}_{k},s_{\ell}{\hat{w}}_{\ell}\rangle-\langle
w_{k},w_{\ell}\rangle}\right|$ $\displaystyle\leq 2\left(\frac{2c_{2}\log
m}{D}\right)^{1/2}\max_{k\in[m]}\sum^{m}_{\begin{subarray}{c}\ell=1\\\
\ell\neq k\end{subarray}}\left|{\langle
s_{k}{\hat{w}}_{k}-w_{k},s_{\ell}{\hat{w}}_{\ell}\rangle-\langle
w_{k},s_{\ell}{\hat{w}}_{\ell}-w_{\ell}\rangle}\right|$ $\displaystyle\leq
4\left(\frac{2c_{2}\log
m}{D}\right)^{1/2}m\cdot\delta_{\max}\leq\frac{1}{2c_{3}},$

where we used the fact that (A2) holds for the ground truth weights and
approximated weights in the penultimate inequality followed by the uniform
bound in (45) at the end. We conclude with Weyl’s inequality which yields

$\displaystyle\left|{\sigma_{m}(\widehat{G}_{2}^{-1})}\right|\leq\left|{\sigma_{1}(\widehat{G}_{2})}\right|^{-1}\leq
2c_{3}.$ (50)

Hence, the approximated weights fulfill (A3) with constant $2c_{3}$ for $n=2$
which extends to $n\geq 2$ by Lemma 2. Let us now proof $(i)-(iii)$. The first
statement follows directly from our proof of (A2) for the approximated
weights, since for any $k\neq\ell$ we have

$\displaystyle\langle{\hat{w}}_{k},s_{\ell}{w}_{\ell}\rangle^{2}\leq\left(\left|{\langle
w_{\ell},w_{k}\rangle}\right|+\left|{\langle{\hat{w}}_{\ell}-{w}_{\ell},{w}_{k}\rangle}\right|\right)^{2}\leq\left(\left|{\langle{w}_{\ell},{w}_{k}\rangle}\right|+\delta_{\max}\right)^{2}\leq\frac{2c_{2}\log
m}{D},$

follows by the chain of inequalities started in (48). To show $(iii)$ we first
split the difference $\tilde{G}_{n}-\widehat{G}_{n}=D_{n}+O_{n}$ into a
diagonal part $D_{n}$ and an off-diagonal part $O_{n}$. We have
$\|\tilde{G}_{n}-\widehat{G}_{n}\|\leq\|D_{n}\|+\|O_{n}\|$ and start by
controlling $\|O_{n}\|$ via Gershgorin’s circle theorem:

$\displaystyle\|O_{n}\|$
$\displaystyle\leq\max_{\ell\in[m]}\sum^{m}_{\begin{subarray}{c}k=1\\\
k\neq\ell\end{subarray}}\left|{\langle{\hat{w}}_{k},{\hat{w}}_{\ell}\rangle^{n}-\langle{\hat{w}}_{k},s_{\ell}w_{\ell}\rangle^{n}}\right|$
$\displaystyle\leq\max_{\ell\in[m]}\sum^{m}_{\begin{subarray}{c}k=1\\\
k\neq\ell\end{subarray}}\left|{\langle{\hat{w}}_{k},{\hat{w}}_{\ell}\rangle-\langle{\hat{w}}_{k},s_{\ell}w_{\ell}\rangle}\right|\left|{\sum^{n}_{i=1}\langle{\hat{w}}_{k},{\hat{w}}_{\ell}\rangle^{n-i}\langle{\hat{w}}_{k},s_{\ell}w_{\ell}\rangle^{i-1}}\right|$
$\displaystyle\leq n\left(\frac{2c_{2}\log
m}{D}\right)^{(n-1)/2}\max_{\ell\in[m]}\sum^{m}_{\begin{subarray}{c}k=1\\\
k\neq\ell\end{subarray}}\left|{\langle{\hat{w}}_{k},{\hat{w}}_{\ell}-s_{\ell}w_{\ell}\rangle}\right|.$

From here we can slightly improve over Cauchy-Schwarz, and instead use that

$\displaystyle\sum^{m}_{\begin{subarray}{c}k=1\\\
k\neq\ell\end{subarray}}\left|{\langle{\hat{w}}_{k},{\hat{w}}_{\ell}-s_{\ell}w_{\ell}\rangle}\right|\leq\sqrt{m-1}\sqrt{\sum^{m}_{\begin{subarray}{c}k=1\\\
k\neq\ell\end{subarray}}\langle{\hat{w}}_{k},{\hat{w}}_{\ell}-s_{\ell}w_{\ell}\rangle^{2}}\leq\sqrt{m}\left\lVert{\widehat{W}}\right\rVert\delta_{\max}.$

Using
$\|{\widehat{W}}\|=\|{\widehat{W}}^{\top}{\widehat{W}}\|^{1/2}\leq\left(1+m\left(\frac{2c_{2}\log
m}{D}\right)^{1/2}\right)^{1/2}$ we arrive at the following bound for the off-
diagonal terms:

$\displaystyle\|O_{n}\|$ $\displaystyle\leq n\left(\frac{2c_{2}\log
m}{D}\right)^{(n-1)/2}\sqrt{m}\left(1+m\left(\frac{2c_{2}\log
m}{D}\right)^{1/2}\right)^{1/2}\delta_{\max}$ $\displaystyle\leq
Cnm\left(\frac{\log m}{D}\right)^{(n-1)/2}\left(\frac{\log
m}{D}\right)^{1/4}\delta_{\max}\leq Cnm\left(\frac{\log
m}{D}\right)^{(2n-1)/4}\delta_{\max},$

where $C>0$ is an absolute constant only depending on $c_{2}$ and $m\geq D$
was used in the second inequality. For the diagonal part we receive

$\displaystyle\|D_{n}\|=\left|1-\max_{\ell\in[m]}\left|{\langle{\hat{w}}_{\ell},{w}_{\ell}\rangle}\right|^{n}\right|\leq\left|{1-(1-\delta_{\max}^{2}/2)^{n}}\right|.$

Hence, we attain overall

$\displaystyle\left\lVert\tilde{G}_{n}-\widehat{G}_{n}\right\rVert$
$\displaystyle\leq\left|{1-(1-\delta_{\max}^{2}/2)^{n}}\right|+Cnm\left(\frac{\log
m}{D}\right)^{(2n-1)/4}\delta_{\max}.$

For $n=2,3$ and some constant $C_{1}>0$ depending only on $c_{2}$ this can be
further simplified using the bound on $\delta_{\max}$ as

$\displaystyle\left\lVert\tilde{G}_{n}-\widehat{G}_{n}\right\rVert$
$\displaystyle\leq\delta_{\max}^{2}+Cnm\left(\frac{\log
m}{D}\right)^{(2n-1)/4}\delta_{\max}$ $\displaystyle\leq
C_{1}m\left(\frac{\log m}{D}\right)^{(2n-1)/4}\delta_{\max},$

which confirms (iii). To prove (ii) we need to show that
$\left\lVert\tilde{G}_{n}-\widehat{G}_{n}\right\rVert\leq c_{4}/2$ from which
the rest follows as before by Weyl’s inequality. We can reuse (iii) in
combination with 45 obtaining

$\displaystyle\left\lVert\tilde{G}_{n}-\widehat{G}_{n}\right\rVert\leq
C_{1}m\left(\frac{\log m}{D}\right)^{(2n-1)/4}\delta_{\max}\leq
C_{2}\left(\frac{\log m}{D}\right)^{1/4}$

for some constant $C_{2}$. Hence (ii) is true for $D\geq D_{0}$ sufficiently
large. ∎

##  Appendix B Proofs: Parameter initialization

Input: Approximated weights ${\widehat{W}}$, numerical differentiation schema
$\Delta^{n}[\cdot]$ with accuracy $\epsilon>0$, interval on which $g^{(2)}$ is
monotonic $[-\tau_{\infty},+\tau_{\infty}]$

1 Set $\widehat{G}_{2}\leftarrow({\widehat{W}}^{\top}{\widehat{W}})^{\odot
2}$,$\widehat{G}_{3}\leftarrow({\widehat{W}}^{\top}{\widehat{W}})^{\odot 3}$

2 for  _$k=1,\ldots,m$_ do

3 Compute directional derivative approximations
$\tilde{T}_{2,k}=\Delta^{2}[f(\cdot{\hat{w}}_{k})](0),\tilde{T}_{3,k}=\Delta^{3}[f(\cdot{\hat{w}}_{k})](0)$

4 end for

5Set $\tilde{\mathcal{C}}_{2}\leftarrow\widehat{G}_{2}^{-1}\tilde{T}_{2}$,
$\tilde{\mathcal{C}}_{3}\leftarrow\widehat{G}_{3}^{-1}\tilde{T}_{3}$

6 for  _$k=1,\dots,m$_ do

7 $\displaystyle\tilde{\tau}_{k}$
$\displaystyle\leftarrow{\begin{cases}{(g^{(2)})}^{-1}(\tilde{\mathcal{C}}_{2,k}),&\text{if
}{(g^{(2)})}^{-1}\text{ is defined for }\tilde{\mathcal{C}}_{2,k},\\\
\operatorname{argmin}_{t\in[-{\tau}_{\infty},\tau_{\infty}]}\left|{g^{(2)}(t)-\tilde{\mathcal{C}}_{2,k}}\right|&\text{else},\end{cases}}$
(51) $\displaystyle\tilde{s}_{k}$
$\displaystyle\leftarrow\operatorname{sign}\Big{(}\tilde{\mathcal{C}}_{3,k}\cdot
g^{(3)}(0)\Big{)},$ (52)

8 end for

Output: $\tilde{\tau},\tilde{s}$

Algorithm 3 Parameter Initialization

In this section we proof Proposition 1, which asses the quality of shifts
computed by Algorithm 3. These initial shifts will later be used as an
initialization for gradient descent (cf. Section C).

##### Proof Sketch of Proposition 1

As discussed in Section 4.1, goal of Algorithm 3 is to recover the vectors

$\displaystyle\mathcal{C}_{2}=g^{(2)}(\tau),\quad\text{and}\quad\mathcal{C}_{3}=s\odot
g^{(3)}(\tau).$

This recovery is only possible up to a approximations
$\tilde{\mathcal{C}}_{2},\tilde{\mathcal{C}}_{3}$ due to perturbations
accumulated in the weight recovery and errors caused by the numerical
approximation of derivatives. The proof begins with an auxiliary statement,
namely Lemma 4, that develops an upper bound on
$\|\mathcal{C}_{n}-\tilde{\mathcal{C}}_{n}\|_{2}$ ($n=2,3$) assuming that the
weight recovery achieved a certain level of accuracy. The proof of Proposition
1 will then utilize the properties of the activation function ((M1)-(M2)) to
show that the shifts $\tau$ can be approximated by using the components of
$\tilde{\mathcal{C}}_{2}\approx g^{(2)}(\tau)$, whereas the signs of the
original weights are revealed by $\tilde{\mathcal{C}}_{3}\approx s\odot
g^{(3)}(\tau)$.

######  Lemma 4.

Denote by $\mathcal{\tilde{C}}_{n}$ the coefficient vectors computed by
Algorithm 3 for an input network ${f}$ with ground truth weights
$\\{w_{k}\in\mathbb{S}^{D-1}|k\in[m]\\}$ which fulfill (A2) \- (A3) of
Definition 2 with constants $c_{2},c_{3}$ and activation $g$ that fulfills
(M1). Then there exist constants $C>0$ only depending on $g,c_{2},c_{3}$ and
$D_{0}\in\mathbb{N}$, such that for $m\geq D\geq D_{0},m\log^{2}m\leq D^{2}$,
$n=2,3$ and provided approximations
$\\{{\hat{w}}_{k}\in\mathbb{S}^{D-1}|k\in[m]\\}$ to the ground truth weights
such that

$\displaystyle\max_{k\in[m]}\min_{s\in\\{-1,1\\}}\left\lVert
s{\hat{w}}_{k}-w_{k}\right\rVert_{2}=\delta_{\max}\leq\frac{1}{C}\frac{D^{1/2}}{m\sqrt{\log
m}},$ (53)

we have

$\displaystyle\left\lVert\tilde{\mathcal{C}}_{n}-{s}^{n}\odot
g^{(n)}({\tau})\right\rVert_{2}\leq C\sqrt{m}\epsilon+Cm^{3/2}\left(\frac{\log
m}{D}\right)^{(2n-1)/4}\delta_{\max},$ (54)

where $s$ is the vector storing the true signs that are implied by (53).

###### Proof of Lemma 4.

Denote as in Algorithm 3
$\tilde{T}_{n,k}=\Delta^{n}[f(\cdot{\hat{w}}_{k})](0)$ and
$T_{n,k}=\langle\nabla^{n}{f}(0),{\hat{w}}_{k}^{\otimes n}\rangle$. By their
definition and the linearity of $\nabla^{n},\Delta^{n}$ we have

$\displaystyle\left\lVert T_{n}-\tilde{T}_{n}\right\rVert_{\infty}$
$\displaystyle=\sup_{k\in[m]}\left|{\langle\nabla^{n}f(0),{\hat{w}}_{k}^{\otimes
n}\rangle-\Delta^{n}_{\epsilon}[f({\hat{w}}_{k}\cdot)](0)}\right|$ (55)
$\displaystyle\leq\sup_{k\in[m]}\sum^{m}_{\ell=1}\left|{\left.\frac{\partial^{n}}{\partial
t^{n}}g(\langle{\hat{w}}_{k},w_{\ell}\rangle
t+{\tau}_{\ell})\right|_{t=0}-\Delta^{n}[g(\langle{\hat{w}}_{k},w_{\ell}\rangle\cdot+{\tau}_{\ell})](0)}\right|$
(56) $\displaystyle\leq
C_{\Delta}\epsilon\sup_{k\in[m]}\sum^{m}_{\ell=1}\left|{\langle{\hat{w}}_{k},{w}_{\ell}\rangle}\right|^{n+2}\leq
C_{\Delta}\epsilon\left(1+m\left(\frac{2c_{2}\log
m}{D}\right)^{\frac{n+2}{2}}\right),$ (57)

where we used the second point of (G2) in the last line followed by the
incoherence of the apx. weights (A2) established in Lemma 3. Making use of
$D^{2}\geq m\log^{2}m$, this simplifies to

$\displaystyle\left\lVert T_{n}-\tilde{T}_{n}\right\rVert_{\infty}\leq
C_{1}\cdot\epsilon$

with constant $C_{1}=(1+4c_{2}^{2})C_{\Delta}$ for $n=2,3$. Coming back to our
initial objective, we can express $s^{n}\odot g^{(n)}({\tau})$ as the product
${s}^{n}\odot g^{(n)}({\tau})=T_{n}\tilde{G}_{n}$ where $\tilde{G}_{n}$
describes the matrix with entries given by
$(\tilde{G}_{n})_{k\ell}=\langle{\hat{w}}_{k},{s}_{\ell}{w}_{\ell}\rangle^{n}$.
Note that Algorithm 3 constructs
$\tilde{\mathcal{C}}_{n}=\widehat{G}_{n}^{-1}\tilde{T}_{n}$, where
$(\widehat{G}_{n})_{k\ell}=\langle{\hat{w}}_{k},{{\hat{w}}}_{\ell}\rangle^{n}$.
We can reduce our main statement (54) into separate bounds

$\displaystyle\left\lVert\tilde{\mathcal{C}}_{n}-{s}^{n}\odot
g^{(n)}({\tau})\right\rVert_{2}$
$\displaystyle=\left\lVert\widehat{G}_{n}^{-1}\tilde{T}_{n}-\tilde{G}_{n}^{-1}T_{n}\right\rVert_{2}$
(58)
$\displaystyle\leq\left\lVert\widehat{G}_{n}^{-1}(T_{n}-\tilde{T}_{n})\right\rVert_{2}+\left\lVert(\widehat{G}_{n}^{-1}-\tilde{G}_{n}^{-1})T_{n}\right\rVert_{2}$
(59)
$\displaystyle\leq\sqrt{m}\left\lVert\widehat{G}_{n}^{-1}\right\rVert\left\lVert
T_{n}-\tilde{T}_{n}\right\rVert_{\infty}+\left\lVert(\widehat{G}_{n}^{-1}-\tilde{G}_{n}^{-1})T_{n}\right\rVert_{2}$
(60) $\displaystyle\leq
C_{1}\sqrt{m}\cdot\epsilon+\left\lVert(\widehat{G}_{n}^{-1}-\tilde{G}_{n}^{-1})T_{n}\right\rVert_{2}$
(61)

To bound
$\left\lVert(\widehat{G}_{n}^{-1}-\tilde{G}^{-1}_{n})T_{n}\right\rVert_{2}$ we
first decompose according to

$\displaystyle\left\lVert(\widehat{G}_{n}^{-1}-\tilde{G}^{-1}_{n})T_{n}\right\rVert_{2}=\left\lVert\widehat{G}_{n}^{-1}(\widehat{G}_{n}-\tilde{G}_{n})\tilde{G}^{-1}_{n}T_{n}\right\rVert_{2}=\left\lVert\widehat{G}_{n}^{-1}(\widehat{G}_{n}-\tilde{G}_{n})({s}^{n}\odot
g^{(n)}({\tau}))\right\rVert_{2}.$ (62)

By invoking Definition (A3) again we continue with

$\displaystyle\left\lVert\widehat{G}_{n}^{-1}(\widehat{G}_{n}-\tilde{G}_{n})({s}^{n}\odot
g^{(n)}({\tau}))\right\rVert_{2}\leq
2c_{3}\left\lVert\widehat{G}_{n}-\tilde{G}_{n}\right\rVert\left\lVert{s}^{n}\odot
g^{(n)}({\tau})\right\rVert_{2}\leq
2c_{3}\kappa\sqrt{m}\left\lVert\widehat{G}_{n}-\tilde{G}_{n}\right\rVert,$
(63)

where we used $\left\lVert g^{(n)}\right\rVert_{\infty}\leq\kappa$. The
statement then follows by using inequality (iii) of Lemma 3 onto
$\left\lVert\widehat{G}_{n}-\tilde{G}_{n}\right\rVert$ and unifying the
involved constants. ∎

We are now ready to prove the main result for the parameter initialization.

###### Proof of Proposition 1.

First note that due the assumptions made, we can freely apply the results of
Lemma 3 and Lemma 4. As a consequence the approximated weights considered in
the statement of Proposition 1 fulfill (A2)-(A3) of Definition 2 with
constants derived from the ground truth weights as described in Lemma 3. We
continue with the remark that (M1) guarantees the existence of the inverse
function ${g^{(2)}}^{-1}$ on $[-{\tau}_{\infty},{\tau}_{\infty}]$ and here we
can disregard the signs such that

$\displaystyle{g^{(2)}}^{-1}({s}^{2}\odot
g^{(2)}({\tau}))={g^{(2)}}^{-1}\left(1\odot g^{(2)}(\tau)\right)={\tau}$ (64)

While ${s}^{2}\odot g^{(2)}({\tau})$ is not directly available,
$\tilde{\mathcal{C}}_{2}$ serves as an approximation
$\tilde{\mathcal{C}}_{2}\approx{s}^{2}\odot g^{(2)}({\tau})$. Fix any
$k\in[m]$, and assume that

$\displaystyle\tilde{\mathcal{C}}_{2,k}\in\left[\min_{t\in[-\tau_{\infty},+\tau_{\infty}]}g^{(2)}(t),\max_{t\in[-\tau_{\infty},+\tau_{\infty}]}g^{(2)}(t)\right],$
(65)

then by the mean value theorem

$\displaystyle{{\hat{\tau}}}_{k}$
$\displaystyle={g^{(2)}}^{-1}(\tilde{\mathcal{C}}_{2,k})={g^{(2)}}^{-1}\left(g^{(2)}(\tau_{k})+\tilde{\mathcal{C}}_{2,k}-g^{(2)}(\tau_{k})\right)$
$\displaystyle={g^{(2)}}^{-1}\left(g^{(2)}(\tau_{k})\right)+\left(\tilde{\mathcal{C}}_{2,k}-g^{(2)}(\tau_{k})\right)({g^{(2)}}^{-1})^{\prime}(\xi_{k})$
$\displaystyle={\tau}_{k}+\left(\tilde{\mathcal{C}}_{2,k}-g^{(2)}(\tau_{k})\right)\frac{1}{g^{(3)}\left({g^{(2)}}^{-1}(\xi_{k})\right)}$

for some
$\xi_{k}\in\left[\min_{t\in[-\tau_{\infty},+\tau_{\infty}]}g^{(2)}(t),\max_{t\in[-\tau_{\infty},+\tau_{\infty}]}g^{(2)}(t)\right]$.
Since $g^{(2)}$ is strictly monotonic on $[-{\tau}_{\infty},{\tau}_{\infty}]$
and differentiable we have

$\displaystyle\theta:=\max_{t\in[-{\tau}_{\infty},{\tau}_{\infty}]}\left|{g^{(3)}(t)}\right|>0.$

Hence, we can bound
$\left|{\frac{1}{g^{(3)}\left({g^{(2)}}^{-1}(\xi_{k})\right)}}\right|\leq\theta^{-1}$
from the outgoing assumption (M1). Applying Lemma 4 to bound $\left\lVert
g^{(2)}(\tau)-\tilde{\mathcal{C}}_{2}\right\rVert_{2}$ therefore yields

$\displaystyle\left\lVert\hat{\tau}-{\tau}\right\rVert_{2}\leq\theta^{-1}\left(C\sqrt{m}\epsilon+Cm^{3/2}\left(\frac{\log
m}{D}\right)^{3/4}\delta_{\max}\right)$ (66)

Now assume there is a $k\in[m]$ such that $\tilde{\mathcal{C}}_{2,k}$ does not
satisfy (65). By the monotonicity we also know that the maximal and minimal
value of $g^{(2)}$ are found exactly on $\pm\tau_{\infty}$. If
$\tilde{\mathcal{C}}_{2,k}$ does not lie in the image of $g^{(2)}$ on
$[-\tau_{\infty},+\tau_{\infty}]$ it has to exceed one of those. We can assume
w.l.o.g. that
$\tilde{\mathcal{C}}_{2,k}>\max_{t\in[-\tau_{\infty},+\tau_{\infty}]}g^{(2)}(t)=g^{(2)}(\tau_{\infty})$.
Then

$\displaystyle\left|{g^{(2)}(\tau_{\infty})-g^{(2)}({\tau}_{k})}\right|<\left|{\tilde{\mathcal{C}}_{2,k}-g^{(2)}({\tau}_{k})}\right|,$

which shows that $g^{(2)}(\tau_{\infty})$ is simply a better estimate of
$g^{(2)}({\tau}_{k})$ than $\tilde{\mathcal{C}}_{2,k}$, and ${g^{(2)}}^{-1}$
is also defined for $g^{(2)}(\tau_{\infty})$. Hence, the same error bound as
above holds for all $k\in[m]$. The expression in (52) yields the correct sign
if
$\operatorname{sign}(\tilde{\mathcal{C}}_{3,k})=\operatorname{sign}({s}_{k}^{(3)})\cdot\operatorname{sign}(g^{(3)}({\tau}_{k}))=\operatorname{sign}({s}_{k})\cdot\operatorname{sign}(g^{(3)}({\tau}_{k}))$.
This is the case if

$\displaystyle\left|{{s}_{k}^{(3)}\cdot
g^{(3)}({\tau}_{k})}\right|>\left|{s_{k}^{(3)}\cdot
g^{(3)}({\tau}_{k})-\tilde{\mathcal{C}}_{3,k}}\right|.$ (67)

By our outgoing assumption $\left|{s_{k}^{(3)}\cdot
g^{(3)}({\tau}_{k})}\right|\geq\theta$ and together with Lemma 4 applied to
the right hand side of the inequality above we get that the signs are correct
as long as

$\displaystyle\theta>\left(C\sqrt{m}\epsilon+Cm^{3/2}\left(\frac{\log
m}{D}\right)^{5/4}\delta_{\max}\right).$ (68)

Assume now that the RHS of (22) is smaller than $1$ and
$\epsilon\leq(Cm)^{-1}$, this implies in particular

$Cm^{3/2}\left(\frac{\log m}{D}\right)^{3/4}\delta_{\max}<1.$

We can estimate the right hand side of (68) from above by

$\displaystyle C\sqrt{m}\epsilon+Cm^{3/2}\left(\frac{\log
m}{D}\right)^{5/4}\delta_{\max}\leq\frac{1}{m^{1/2}}+\left(\frac{\log
m}{D}\right)^{2/4},$

which clearly is smaller than any constant for $D$ large enough, and therefore
the signs will be correct for $D_{0}$ chosen accordingly since (67) is
fulfilled. ∎

##  Appendix C Proof of Theorem 4

Let us shortly recall the setting of Theorem 4. We consider the identification
of the parameters ${W},{\tau}$ attributed to a shallow neural network
$f(\cdot,{W},{\tau})$ which falls into the class of networks described in
Section 2. By means of Algorithms 2 -3, we can find weight approximations
${\widehat{W}}\approx W$ and shift approximations ${\hat{\tau}}\approx\tau$ of
$f$. The parameters $({\widehat{W}},{\hat{\tau}})$ give rise to a neural
network $\hat{f}(\cdot,{\widehat{W}},{\hat{\tau}})$ which is architecturally
identical to ${f}$, and, depending on the accuracy of the previous algorithmic
steps, we would already expect some agreement in terms of $\hat{f}\approx f$.
Given network evaluations
$y_{1}=f(x_{1}),\dots,y_{N_{\text{train}}}=f(x_{N_{\text{train}}})$ of ${f}$,
we consider further improvement of the approximated shifts ${\hat{\tau}}$ by
empirical risk minimization of the objective

$\displaystyle
J({\hat{\tau}})=\frac{1}{2{N_{\text{train}}}}\sum^{{N_{\text{train}}}}_{i=1}\left(\hat{f}(x_{i},{\hat{\tau}})-y_{i}\right)^{2},$
(69)

via gradient descent given by

$\displaystyle{\hat{\tau}}^{(n+1)}={\hat{\tau}}^{(n)}-\gamma\nabla
J({\hat{\tau}}^{(n)}).$ (70)

In Theorem 4, we prove a local convergence result with the guarantee that, for
sufficiently large $N_{\text{train}}$, $\|{\hat{\tau}}^{(n)}-{\tau}\|_{2}$ is
roughly

$\displaystyle\|{\hat{\tau}}^{(n)}-{\tau}\|_{2}\lesssim\frac{m^{1/2}\log(m)^{3/4}}{D^{1/4}}\left(\|{\widehat{W}}-W\|_{F}+\frac{\Delta_{W,O}^{1/2}}{D^{1/2}}+\left\|\sum^{m}_{k=1}w_{k}-{\hat{w}}_{k}\right\|_{2}\right).$

where

$\Delta_{W,O}=\sum^{m}_{k\neq
k^{\prime}}\left|\langle{\hat{w}}_{k}-w_{k},{\hat{w}}_{k^{\prime}}-w_{k^{\prime}}\rangle\right|.$

##### Proof sketch.

For the proof, we rely on an idealized loss given by a quadratic functional in
${\hat{\tau}}$:

$\displaystyle
J_{*}({\hat{\tau}})=({\hat{\tau}}-\tau)^{\top}A({\hat{\tau}}-\tau),$ (71)

with

$\displaystyle
A:=\frac{1}{2{N_{\text{train}}}}\sum^{N_{\text{train}}}_{i=1}\nabla\hat{f}(x_{i},{\tau})\nabla\hat{f}(x_{i},{\tau})^{\top}.$
(72)

The proof can then be broken down into two steps. First, in Lemma 8, it is
shown that $J_{*}$ is strictly convex by estimating a lower bound on the
minimal eigenvalue $\lambda_{m}(A)$ of $A$. The proof relies on techniques
from the NTK literature to first control the spectrum of
$\mathbb{E}_{X_{1},\ldots,X_{N_{\text{train}}}\sim{\cal
N}(0,\operatorname{Id}_{D})}[A]$ by leveraging (M2) and the incoherence of
${\hat{w}}_{1},\dots,{\hat{w}}_{m}$. In particular, Lemma 8 implies that
minimizing $J_{*}$ via the gradient descent iteration given by

$\displaystyle{\hat{\tau}}_{*}^{(n+1)}={\hat{\tau}}_{*}^{(n)}-\gamma\nabla
J_{*}({\hat{\tau}}_{*}^{(n)})={\hat{\tau}}_{*}^{(n)}-\gamma
A({\hat{\tau}}_{*}^{(n)}-\tau)$ (73)

with step-sizes $\gamma\leq 1/\|A\|$ does necessarily converge to the global
minimum attained at ${\hat{\tau}}_{*}=\tau$. As a second step, we control the
perturbation between the iterations
${\hat{\tau}}^{(n)},{\hat{\tau}}_{*}^{(n)}$, when starting them from an
identical vector ${\hat{\tau}}^{(0)}={\hat{\tau}}_{*}^{(0)}$. In particular,
in Lemma 14 it is shown that the difference
$\|{\hat{\tau}}^{(n)}-{\hat{\tau}}_{*}^{(n)}\|_{2}$ adheres to

$\displaystyle\|{\hat{\tau}}^{(n)}-{\hat{\tau}}_{*}^{(n)}\|_{2}\leq\xi^{n}\|{\hat{\tau}}^{(0)}-{\tau}\|_{2}+\left(1-\xi^{n}\right)\Delta_{W},$

provided ${\hat{\tau}}^{(0)}$ is sufficiently close to the optimal solution
$\tau$, and where $\Delta_{W}$ is an error term which satisfies $\Delta_{W}\to
0$ as $\|{\widehat{W}}-{W}\|_{F}\to 0$ and $\xi\in[0,1)$. By the triangle
inequality, we then bound the distance of the original gradient descent
iteration (70) to $\tau$ via

$\displaystyle\|{\hat{\tau}}^{(n)}-\tau\|_{2}$
$\displaystyle\leq\|{\hat{\tau}}^{(n)}-{\hat{\tau}}_{*}^{(n)}\|_{2}+\|{\hat{\tau}}_{*}^{(n)}-\tau\|_{2}$
$\displaystyle\leq\xi^{n}\|{\hat{\tau}}^{(0)}-{\tau}\|_{2}+\left(1-\xi^{n}\right)\Delta_{W}+(1-\gamma\lambda_{m}(A))^{n}\|{\hat{\tau}}_{*}^{(0)}-\tau\|_{2}\to\Delta_{W},$

for $n\to\infty$. Hence, we establish that the iteration ${\hat{\tau}}^{(n)}$
settles in an area around the optimal shifts $\tau$ that is determined by the
initial and irreparable error present in the weight approximation
${\widehat{W}}$ of ${W}$.

##### Organisation of this section.

Subsection C.1 is dedicated to analyze the matrix $A$ in (72) in expectation
(over $x_{i}$’s) and proves the well-posedness. Subsection C.2 analyzes the
perturbation between gradient descent on the idealized objective $J_{*}$ and
the true objective $J$. Subsection C.3 concludes the proof by combining the
well-posedness and the perturbation analysis.

###  C.1 Well-posedness of the idealized objective in expectation

We begin this section with a short primer on Hermitian expansions, a technical
tool which is commonly used in the NTK literature. Afterwards, we prove the
well-posedness of $A$ in (72) in expectation.

####  C.1.1 A primer on Hermitian expansions

The Hermitian polynomials form an orthonormal basis of the $L_{2}$ space,
weighted by the Gaussian kernel $w_{G}$, which we denote as
$L_{2}(\mathbb{R},w_{G})$. The $r$-th Hermitian polynomial is defined as

$\displaystyle
h_{r}(y):=\frac{1}{\sqrt{r!}}(-1)^{r}\exp\Big{(}\frac{y^{2}}{2}\Big{)}\frac{d^{r}}{dy^{r}}\exp\Big{(}\frac{-y^{2}}{2}\Big{)}.$

Any function $h\in L_{2}(\mathbb{R},w_{G})$ can be expanded as
$h\equiv\sum_{r}\mu_{r}(h)h_{r}$ with Hermitian coefficients $\mu_{r}(h)$ as

$\displaystyle\mu_{r}(h):=\int h(y)h_{r}(y)w_{G}(y)dy.$

As per Assumption (M1) the first three derivatives of $g$ are bounded, hence
$\max_{k\in[3]}\|g_{\tau}^{(k)}\|_{\infty}<\infty$ for any
$\tau\in\mathbb{R}$. It is easy to check that this implies that these
functions lie within $L_{2}(\mathbb{R},w_{G})$.

######  Lemma 5.

Assume $h$ is bounded, then $h\in L_{2}(\mathbb{R},\omega_{G})$ and

$\displaystyle\sum_{r\geq 0}\mu_{r}(h)^{2}\leq\sqrt{2\pi}\|h\|_{\infty}^{2}$

###### Proof.

$\displaystyle\int_{\mathbb{R}}h(t)^{2}\exp(-t^{2}/2)dt\leq\sqrt{2\pi}\|h\|_{\infty}^{2}<\infty.$

The second statement follows from the fact that $L_{2}(\mathbb{R},\omega_{G})$
is a Hilbert space and the hermite polynomials form an orthonormal system
within that space. ∎

We further assume in (M2) that $g^{(1)}$ is not a polynomial of degree three
or less, implying that also $g^{(1)}_{\tau}$ is not a polynomial of degree
three or less. Since $h_{0},h_{1},h_{2},h_{3}$ form a basis for the space of
affine functions, this implies
$g^{(1)}_{\tau}\not\in\textrm{Span}(h_{0},h_{1},h_{2},h_{3})$. In particular,
$\mu_{r}(g^{(1)}_{\tau})\neq 0$ for some $r\geq 4$ and any
$\tau\in\mathbb{R}$. In the following, we denote

$\omega:=\min_{\tau\in[-{\tau}_{\infty},{\tau}_{\infty}]}\sum_{r\geq
4}\mu_{r}(g^{(1)}(\cdot+\tau))^{2}>0,$

which depends only on the activation function $g^{(1)}$ and the shift bound
$\tau_{\infty}$. Lastly, a useful property of Hermitian expansions and the
Hermitian basis is the following identity.

######  Lemma 6 ([41, Lemma D.2]).

For two unit norm vectors $x,y\in\mathbb{R}^{D}$ and every $k,\ell\geq 0$ we
have

$\displaystyle\mathbb{E}_{X\sim\mathcal{N}(0,\operatorname{Id}_{D})}\left[h_{k}(v^{\top}X)h_{\ell}(u^{\top}X)\right]=\delta_{k\ell}\langle
u,v\rangle^{k},$

where $\delta_{k\ell}=1$ if $k=\ell$ and 0 otherwise.

####  C.1.2 Well-posedness in expectation

The central object of study in this section is the matrix

$\displaystyle E:=\mathbb{E}_{X_{1},\ldots,X_{N_{\text{train}}}\sim{\cal
N}(0,\operatorname{Id}_{D})}[A].$ (74)

We prove its well-posedness in Lemma 8. The proof relies on the observation
that $E$ is actually equal to a sum of positive semidefinite Grammian matrices
as shown in Lemma 7.

######  Lemma 7.

Assume that (M1) holds, and let $E$ be defined as in (74). Then, we have

$\displaystyle E=\frac{1}{2}\sum_{r=0}^{\infty}T_{r}T_{r}^{\top},\quad\textrm{
where
}T_{r}:=\left[\begin{array}[]{c}\mu_{r}(g^{(1)}_{\tau_{1}})\operatorname{vec}({\hat{w}}_{1}^{\otimes
r})\\\ \vdots\\\
\mu_{r}(g^{(1)}_{\tau_{m}})\operatorname{vec}({\hat{w}}_{m}^{\otimes r})\\\
\end{array}\right]\in\mathbb{R}^{m\times D^{r}}.$

In particular, we have
$E\succcurlyeq\frac{1}{2}\sum_{r\in\mathcal{R}}T_{r}T_{r}^{\top}$ for any
subset $\mathcal{R}\subseteq\mathbb{N}_{\geq 1}$, where $A\succcurlyeq B$
means $A-B$ is positive semidefinite.

###### Proof.

The matrix $A$ can be written as

$\displaystyle A_{k\ell}$
$\displaystyle=\frac{1}{2{N_{\text{train}}}}\sum_{i=1}^{{N_{\text{train}}}}g^{(1)}({\hat{w}}_{k}^{\top}X_{i}+\tau_{k})g^{(1)}({\hat{w}}_{\ell}^{\top}X_{i}+{\tau}_{\ell})$

and the corresponding expectation reads

$\displaystyle E_{k\ell}=\frac{1}{2}\mathbb{E}_{X\sim{\cal
N}(0,\operatorname{Id}_{D})}\left[g^{(1)}_{{\tau}_{k}}({\hat{w}}_{k}^{\top}X)g^{(1)}_{{\tau}_{\ell}}({\hat{w}}_{\ell}^{\top}X)\right].$

Now, note that $g^{(1)}_{\tau}=g^{(1)}(\cdot+\tau)\in L_{2}(\mathbb{R},w_{H})$
for any $\tau\in\mathbb{R}$ by (M1) and Lemma 5. Hence, $g^{(1)}_{\tau}$ has a
Hermitian expansion and we can write

$\displaystyle E_{k\ell}=\frac{1}{2}\mathbb{E}_{X\sim{\cal
N}(0,\operatorname{Id}_{D})}$
$\displaystyle\left[\Bigg{(}\sum_{r=0}^{\infty}\mu_{r}(g^{(1)}_{{\tau}_{k}})h_{r}({\hat{w}}_{k}^{\top}X)\Bigg{)}\left(\sum_{r=0}^{\infty}\mu_{r}(g^{(1)}_{{\tau}_{\ell}})h_{r}({\hat{w}}_{\ell}^{\top}X)\right)\right].$

Using now Lemma 6 to express expectations of scalar products of Hermite
polynomials, we obtain

$\displaystyle E_{k\ell}$
$\displaystyle=\frac{1}{2}\sum_{r=0}^{\infty}\mu_{r}(g^{(1)}_{{\tau}_{k}})\mu_{r}(g^{(1)}_{{\tau}_{\ell}})\langle{\hat{w}}_{k},{\hat{w}}_{\ell}\rangle^{r},$

which can equivalently be written as
$\frac{1}{2}\sum_{r=0}^{\infty}T_{r}T_{r}^{\top}$. The second part of the
statement follows from the fact that each individual matrix
$T_{r}T_{r}^{\top}$ is a positive semidefinite Grammian matrix. ∎

######  Lemma 8.

Let $E$ be defined as in (74) and assume that the approximated weights satisfy
$\|{\hat{w}}_{k}\|_{2}=1$ and (A2) for some universal constant $c_{2}$.
Furthermore, assume the activation function adheres to (M2). Then, we have

$\displaystyle\lambda_{m}(E)\geq\omega-C(m-1)\left(\frac{\log
m}{D}\right)^{2},$ (75)

where $\omega$ and $C$ are constants depending only on $g$ and
$\tau_{\infty}$. Specifically, we have

$\displaystyle\omega$
$\displaystyle=\frac{1}{2}\min_{\tau\in[-\bar{\tau}_{\infty},\bar{\tau}_{\infty}]}\sum_{r\geq
4}\left(\mu_{r}(g^{(1)}(\cdot+\tau))\right)^{2},$ $\displaystyle C$
$\displaystyle=\frac{1}{2}c_{2}^{2}\max_{\tau,\widetilde{\tau}\in[-\tau_{\infty},\tau_{\infty}]}\sum_{r\geq
4}\left|{\mu_{r}(g^{(1)}_{\tau})\mu_{r}(g^{(1)}_{\widetilde{\tau}})}\right|.$

###### Proof of Lemma 8.

To simplify the notation, we introduce the shorthand
$\mu_{r,k}:=\mu_{r}(g^{(1)}_{{\tau}_{k}})$. By Lemma 7 we have
$E\succcurlyeq\frac{1}{2}\sum_{r\geq 4}T_{r}T_{r}^{\top}$, so we concentrate
on the expression on the right hand side. As
$\left\lVert{{\hat{w}}}_{k}\right\rVert_{2}=1$ for all $k\in[m]$, we first
note that we can rewrite $\frac{1}{2}\sum_{r\geq 4}T_{r}T_{r}^{\top}$ as
$\frac{1}{2}\sum_{r\geq 4}T_{r}T_{r}^{\top}=D_{4}+O_{4}$, where the matrix
$D_{4}$ is given by

$\displaystyle D_{4}$
$\displaystyle:=\frac{1}{2}\operatorname{Diag}\Big{(}\sum_{r\geq
4}\mu_{r,1}^{2},\ldots,\sum_{r\geq 4}\mu_{r,m}^{2}\Big{)}$

and the remainder $O_{4}$ equals $\frac{1}{2}\sum_{r\in 4}T_{r}T_{r}^{\top}$
with its diagonal set to $0$. To show (75), we compute a lower eigenvalue
bound for $D_{4}$ and an upper eigenvalue bound for $O_{4}$ independently, and
then complete the argument with Weyl’s eigenvalue perturbation bound [62]. The
smallest eigenvalue of $D_{4}$ can be read from the diagonal and is given by

$\displaystyle\lambda_{\min}(D_{4})=\frac{1}{2}\min_{k\in[m]}\sum_{r\geq
4}\mu_{r,k}^{2}\geq\omega>0.$

For the spectral norm of $O_{4}$ we use $L_{1}/L_{\infty}$-Cauchy-Schwarz
inequalities and $\left\lVert{\hat{w}}_{k}\right\rVert_{2}=1$ for all
$k\in[m]$. Specifically, for any unit norm vector $u$ we have

$\displaystyle u^{\top}O_{4}u$
$\displaystyle=\frac{1}{2}\sum_{k=1}^{m}\sum_{\ell\neq
k}u_{k}u_{\ell}\sum_{r\geq
4}\mu_{r,k}\mu_{r,\ell}\langle{\hat{w}}_{k},{\hat{w}}_{\ell}\rangle^{r}$
$\displaystyle\leq\frac{1}{2}\sum_{k=1}^{m}\sum_{\ell\neq
k}\left|{u_{k}}\right|\left|{u_{\ell}}\right|\sum_{r\geq
4}\left|{\mu_{r,k}\mu_{r,\ell}}\right|\left|{\langle{\hat{w}}_{k},{\hat{w}}_{\ell}\rangle}\right|^{r}.$

By dragging out the maximum of the sums over Hermitian coefficients, we
further bound

$\displaystyle
u^{\top}O_{4}u\leq\Big{(}\frac{1}{2}\max_{\tau,\widetilde{\tau}\in[-\tau_{\infty},\tau_{\infty}]}\sum_{r\geq
4}\left|{\mu_{r}(g^{(1)}_{\tau})\mu_{r}(g^{(1)}_{\widetilde{\tau}})}\right|\Big{)}\sum_{k=1}^{m}\sum_{\ell\neq
k}\left|{u_{k}}\right|\left|{u_{\ell}}\right|\left|{\langle{\hat{w}}_{k},{\hat{w}}_{\ell}\rangle}\right|^{4}.$

The trailing factor is, for all unit norm $u$, bounded by the spectral norm of
the matrix

$(\widehat{O}_{4})_{ij}:=\begin{cases}0,&\textrm{ if }i=j,\\\
\left|{\langle{\hat{w}}_{i},{\hat{w}}_{j}\rangle}\right|^{4},&\textrm{ else
}.\end{cases}$ (76)

Therefore we have $u^{\top}O_{4}u\leq C_{g,\tau_{\infty}}\|\widehat{O}_{4}\|$
for all unit norm $u$, and with the constant $C_{g,\tau_{\infty}}$ given as

$C_{g,\tau_{\infty}}=\frac{1}{2}\max_{\tau,\widetilde{\tau}\in[-\tau_{\infty},\tau_{\infty}]}\sum_{r\geq
4}\left|{\mu_{r}(g^{(1)}_{\tau})\mu_{r}(g^{(1)}_{\widetilde{\tau}})}\right|,$

and only dependent on $g$ and the shift bound $\tau_{\infty}$. By Gershgorin’s
circle theorem we further have

$\displaystyle\|\widehat{O}_{4}\|\leq\max_{k\in[m]}\sum_{\ell\neq
k}^{m}|(\widehat{O}_{4})_{k\ell}|\leq(m-1)\left(\frac{c_{2}\log
m}{D}\right)^{2},$

where we used the fact that ${\hat{w}}_{1},\ldots,{\hat{w}}_{m}$ satisfy (A2).
∎

###  C.2 Controlling the perturbation from the idealized GD iteration

This section is concerned with the divergence between the two gradient descent
iterations in (70) and (73). We start with a number of auxiliary results that
control certain series involving the Hermite coefficients of the activation
and its derivatives. These technical statements are needed to control the
perturbation in the GD iteration that is caused by the weight approximation.
The bounds enable Lemma 13 which provides an upper bound for the difference
between the gradients $\nabla J({\hat{\tau}}),\nabla J_{*}({\hat{\tau}})$,
defined in (69), (71), respectively, w.r.t. the accuracy of the estimated
weights and shift initializations.

####  C.2.1 Controlling perturbation from weigths

The first part of this section is concerned with estimating a series that
contains elements

$\displaystyle S_{r,\ell}$
$\displaystyle:=\sum^{m}_{k=1}\mu_{r}(g_{\tau_{k}})\mu_{r}(g^{(1)}_{{\hat{\tau}}_{\ell}})\left(\langle{\hat{w}}_{k},{\hat{w}}_{\ell}\rangle^{r}-\langle
w_{k},{\hat{w}}_{\ell}\rangle^{r}\right),$ (77)

where $\mu_{r}(g_{\tau_{k}}),\mu_{r}(g^{(1)}_{{\hat{\tau}}_{\ell}})$
correspond to the $k$-th and $\ell$-th Hermite coefficient of the function
$g_{\tau_{k}}(\cdot)=g(\cdot+\tau_{k})$,
$g_{{\hat{\tau}}_{\ell}}^{\prime}(\cdot)=g^{(1)}(\cdot+{\hat{\tau}}_{\ell})$,
respectively. These coefficients are assumed to be uniformy bounded for all
$r\geq 0$ which is a consequence of (M2) and Lemma 5. The following results
pave the way for perturbation bound w.r.t. estimated weights and we use the
following shorthands to keep the expressions more compact:

$\displaystyle\Delta_{W,F}$ $\displaystyle=\|{\widehat{W}}-W\|_{F},$ (78)
$\displaystyle\Delta_{W,O}$ $\displaystyle=\sum^{m}_{k\neq
k^{\prime}}\left|\langle{\hat{w}}_{k}-w_{k},{\hat{w}}_{k^{\prime}}-w_{k}^{\prime}\rangle\right|.$
(79)

######  Lemma 9.

Consider weights and approximated weights
$(w_{k})_{k\in[m]},({\hat{w}}_{k})_{k\in[m]}$ of unit norm as before that both
fulfill (A2) and (i) in Lemma 3, as well shifts
$(\tau_{k})_{k\in[m]},({\hat{\tau}}_{k})_{k\in[m]}$ within
$[-\tau_{\infty},\tau_{\infty}]$ for some $\tau_{\infty}<\infty$. Let
$S_{r,\ell}$ be defined as in (77) and assume that $g$ fulfills the assumption
(M1) \- (M2). Then, there exists a constant $C>0$ such that, for $m\geq D$,

$\displaystyle\sum^{m}_{\ell=1}S_{r,\ell}^{2}$ $\displaystyle\leq
Cr^{2}\max_{k,\ell\in[m]}\mu_{r}(g^{(1)}_{{\hat{\tau}}_{\ell}})^{2}\mu_{r}(g_{\tau_{k}})^{2}{\left(1+m\left(\frac{\log
m}{D}\right)^{r/2}\right)}$
$\displaystyle\cdot\left[\Delta_{W,F}^{2}+\left(\frac{\log
m}{D}\right)^{(r-1)/2}\Delta_{W,O}\right].$

Furthermore, for any fixed $R\geq 2$ we have

$\displaystyle\sum_{r=2}^{R}2^{r}\sum^{m}_{\ell=1}S_{r,\ell}^{2}\leq\frac{Cm\log
m}{D}\left(\Delta_{W,F}^{2}+\left(\frac{\log
m}{D}\right)^{1/2}\Delta_{W,O}\right),$

where the constant $C>0$ additionally depends on $R$.

###### Proof of Lemma 9.

Throughout this proof we use the convention that, for any vector, we have
$v^{\otimes 0}=1$, $1\otimes 1=1$ and $v\otimes 1=1\otimes v=v$, which will be
relevant for the case $r=1$. We start with a chain of equalities that uses
elementary properties of the Frobenius inner product:

$\displaystyle\sum^{m}_{\ell=1}S_{r,\ell}^{2}=$
$\displaystyle\sum^{m}_{\ell=1}\left[\sum^{m}_{k=1}\mu_{r}(g_{\tau_{k}})\mu_{r}(g^{(1)}_{{\hat{\tau}}_{\ell}})\left(\langle{\hat{w}}_{k},{\hat{w}}_{\ell}\rangle^{r}-\langle
w_{k},{\hat{w}}_{\ell}\rangle^{r}\right)\right]^{2}$ $\displaystyle=$
$\displaystyle\sum^{m}_{\ell=1}\left[\sum^{m}_{k=1}\mu_{r}(g_{\tau_{k}})\mu_{r}(g^{(1)}_{{\hat{\tau}}_{\ell}})\langle{\hat{w}}_{k}-w_{k},{\hat{w}}_{\ell}\rangle\left(\sum^{r}_{i=1}\langle{\hat{w}}_{k},{\hat{w}}_{\ell}\rangle^{r-i}\langle
w_{k},{\hat{w}}_{\ell}\rangle^{i-1}\right)\right]^{2}$ $\displaystyle=$
$\displaystyle\sum^{m}_{\ell=1}\left[\sum^{m}_{k=1}\mu_{r}(g_{\tau_{k}})\mu_{r}(g^{(1)}_{{\hat{\tau}}_{\ell}})\langle{\hat{w}}_{k}-w_{k},{\hat{w}}_{\ell}\rangle\left\langle\sum^{r}_{i=1}{\hat{w}}_{k}^{\otimes(r-i)}\otimes
w_{k}^{\otimes(i-1)},{\hat{w}}_{\ell}^{\otimes r-1}\right\rangle\right]^{2}$
$\displaystyle=$
$\displaystyle\sum^{m}_{\ell=1}\left[\sum^{m}_{k=1}\mu_{r}(g_{\tau_{k}})\mu_{r}(g^{(1)}_{{\hat{\tau}}_{\ell}})\left\langle({\hat{w}}_{k}-w_{k})\otimes\sum^{r}_{i=1}\left({\hat{w}}_{k}^{\otimes(r-i)}\otimes
w_{k}^{\otimes(i-1)}\right),{\hat{w}}_{\ell}^{\otimes
r}\right\rangle\right]^{2}$ $\displaystyle=$
$\displaystyle\sum^{m}_{\ell=1}\left[\mu_{r}(g^{(1)}_{{\hat{\tau}}_{\ell}})\left\langle\sum^{m}_{k=1}\mu_{r}(g_{\tau_{k}})({\hat{w}}_{k}-w_{k})\otimes\sum^{r}_{i=1}\left({\hat{w}}_{k}^{\otimes(r-i)}\otimes
w_{k}^{\otimes(i-1)}\right),{\hat{w}}_{\ell}^{\otimes
r}\right\rangle\right]^{2}$ $\displaystyle=$
$\displaystyle\sum^{m}_{\ell=1}\mu_{r}(g^{(1)}_{{\hat{\tau}}_{\ell}})^{2}\left\langle\sum^{m}_{k=1}\mu_{r}(g_{\tau_{k}})({\hat{w}}_{k}-w_{k})\otimes\sum^{r}_{i=1}\left({\hat{w}}_{k}^{\otimes(r-i)}\otimes
w_{k}^{\otimes(i-1)}\right),{\hat{w}}_{\ell}^{\otimes r}\right\rangle^{2}.$

At this stage, we separate the coefficients depending on $\ell$ such that

$\displaystyle\sum^{m}_{\ell=1}\left[\sum^{m}_{k=1}\mu_{r}(g_{\tau_{k}})\mu_{r}(g^{(1)}_{{\hat{\tau}}_{\ell}})\left(\langle{\hat{w}}_{k},{\hat{w}}_{\ell}\rangle^{r}-\langle
w_{k},{\hat{w}}_{\ell}\rangle^{r}\right)\right]^{2}$ $\displaystyle\leq$
$\displaystyle\max_{\ell\in[m]}\mu_{r}(g^{(1)}_{{\hat{\tau}}_{\ell}})^{2}\sum^{m}_{\ell=1}\left\langle\sum^{m}_{k=1}\mu_{r}(g_{\tau_{k}})({\hat{w}}_{k}-w_{k})\otimes\sum^{r}_{i=1}\left({\hat{w}}_{k}^{\otimes(r-i)}\otimes
w_{k}^{\otimes(i-1)}\right),{\hat{w}}_{\ell}^{\otimes r}\right\rangle^{2}.$

Now, note that the set of tensors $({\hat{w}}_{\ell}^{\otimes
r})_{\ell\in[m]}$ forms a frame whose upper frame constant is bounded by the
upper spectrum of the Grammian
$(\widehat{G}_{r})_{ij}=\langle{\hat{w}}_{i},{\hat{w}}_{j}\rangle^{r}$, see
also Lemma 16. Due to Lemma 17 which relies on Gershgorin’s circle theorem we
know there exists an absolute constant $C>0$ such that for $D$ sufficiently
large the operator norm of $\widehat{G}_{r}$ obeys

$\displaystyle\|\widehat{G}_{r}\|\leq C{\left(1+m\left(\frac{\log
m}{D}\right)^{r/2}\right)}.$

As a consequence, we get

$\displaystyle\max_{\ell\in[m]}\mu_{r}(g^{(1)}_{{\hat{\tau}}_{\ell}})^{2}\sum^{m}_{\ell=1}\left\langle\sum^{m}_{k=1}\mu_{r}(g_{\tau_{k}})({\hat{w}}_{k}-w_{k})\otimes\sum^{r}_{i=1}\left({\hat{w}}_{k}^{\otimes(r-i)}\otimes
w_{k}^{\otimes(i-1)}\right),{\hat{w}}_{\ell}^{\otimes r}\right\rangle^{2}$
$\displaystyle\leq$
$\displaystyle\,\max_{\ell\in[m]}\mu_{r}(g^{(1)}_{{\hat{\tau}}_{\ell}})^{2}\|\widehat{G}_{r}\|\left\|\sum^{m}_{k=1}\mu_{r}(g_{\tau_{k}})({\hat{w}}_{k}-w_{k})\otimes\sum^{r}_{i=1}\left({\hat{w}}_{k}^{\otimes(r-i)}\otimes
w_{k}^{\otimes(i-1)}\right)\right\|_{F}^{2}$ $\displaystyle\leq$
$\displaystyle\,C\max_{\ell\in[m]}\mu_{r}(g^{(1)}_{{\hat{\tau}}_{\ell}})^{2}{\left(1+m\left(\frac{\log
m}{D}\right)^{r/2}\right)}\left\|\sum^{m}_{k=1}\mu_{r}(g_{\tau_{k}})({\hat{w}}_{k}-w_{k})\otimes\sum^{r}_{i=1}\left({\hat{w}}_{k}^{\otimes(r-i)}\otimes
w_{k}^{\otimes(i-1)}\right)\right\|_{F}^{2}.$ (80)

Denote now $\Delta_{k,r}:=\mu_{r}(g_{\tau_{k}})({\hat{w}}_{k}-w_{k})$ and
$T_{k,r}:=\sum^{r}_{i=1}\left({\hat{w}}_{k}^{\otimes(r-i)}\otimes
w_{k}^{\otimes(i-1)}\right)$, then

$\displaystyle\left\|\sum^{m}_{k=1}\mu_{r}(g_{\tau_{k}})({\hat{w}}_{k}-w_{k})\otimes\sum^{r}_{i=1}\left({\hat{w}}_{k}^{\otimes(r-i)}\otimes
w_{k}^{\otimes(i-1)}\right)\right\|_{F}^{2}$ $\displaystyle=$
$\displaystyle\sum^{m}_{k,k^{\prime}=1}\langle\Delta_{k,r}\otimes
T_{k,r},\Delta_{k^{\prime},r}\otimes
T_{k^{\prime},r}\rangle=\sum^{m}_{k,k^{\prime}=1}\langle\Delta_{k,r},\Delta_{k^{\prime},r}\rangle\langle
T_{k,r},T_{k^{\prime},r}\rangle$ $\displaystyle=$
$\displaystyle\,\sum^{m}_{k=1}\|\Delta_{k,r}\|_{2}^{2}\|T_{k,r}\|_{F}^{2}+\sum^{m}_{k\neq
k^{\prime}}\langle\Delta_{k,r},\Delta_{k^{\prime},r}\rangle\langle
T_{k,r},T_{k^{\prime},r}\rangle.$ (81)

Using $\|w_{k}\|_{2}=\|{\hat{w}}_{k}\|_{2}=1$ we get

$\displaystyle\|T_{k,r}\|_{F}\leq\sum^{r}_{i=1}\|{\hat{w}}_{k}^{\otimes(r-i)}\otimes
w_{k}^{\otimes(i-1)}\|_{F}\leq\sum^{r}_{i=1}\|{\hat{w}}_{k}\|_{2}^{r-i}\|w_{k}\|_{2}^{i-1}=r,$

such that the left part of (81) can be estimated by

$\begin{split}\sum^{m}_{k=1}\|\Delta_{k,r}\|_{2}^{2}\|T_{k,r}\|_{F}^{2}&\leq
r^{2}\max_{k\in[m]}\mu_{r}(g_{\tau_{k}})^{2}\sum^{m}_{k=1}\|{\hat{w}}_{k}-w_{k}\|_{2}^{2}\\\
&=r^{2}\max_{k\in[m]}\mu_{r}(g_{\tau_{k}})^{2}\|{\widehat{W}}-W\|_{F}^{2}.\end{split}$
(82)

To bound the right part of (81) first note that, for $k\neq k^{\prime}$,

$\displaystyle\langle T_{k,r},T_{k^{\prime},r}\rangle$
$\displaystyle=\sum^{r}_{i,i^{\prime}=1}\left\langle{\hat{w}}_{k}^{\otimes(r-i)}\otimes
w_{k}^{\otimes(i-1)},{\hat{w}}_{k^{\prime}}^{\otimes(r-i^{\prime})}\otimes
w_{k^{\prime}}^{\otimes(i^{\prime}-1)}\right\rangle$ $\displaystyle\leq
C\sum^{r}_{i,i^{\prime}=1}\left(\frac{\log
m}{D}\right)^{(r-1)/2}=Cr^{2}\left(\frac{\log m}{D}\right)^{(r-1)/2},$

for some absolute constant $C$, which follows from the pairwise incoherence
(A2) as well as point (i) of Lemma 3. Therefore, the right part of (81) is
bounded by

$\begin{split}\sum^{m}_{k\neq
k^{\prime}}\langle\Delta_{k,r},\Delta_{k^{\prime},r}\rangle\langle
T_{k,r},T_{k^{\prime},r}\rangle&\leq Cr^{2}\left(\frac{\log
m}{D}\right)^{(r-1)/2}\sum^{m}_{k\neq
k^{\prime}}\left|\langle\Delta_{k,r},\Delta_{k^{\prime},r}\rangle\right|\\\
&\leq Cr^{2}\left(\frac{\log
m}{D}\right)^{(r-1)/2}\max_{k\in[m]}\mu_{r}(g_{\tau_{k}})^{2}\sum^{m}_{k\neq
k^{\prime}}\left|\langle{\hat{w}}_{k}-w_{k},{\hat{w}}_{k^{\prime}}-w_{k}^{\prime}\rangle\right|.\end{split}$
(83)

Plugging in (82) and (83) into (81) yields

$\displaystyle\left\|\sum^{m}_{k=1}\mu_{r}(g_{\tau_{k}})({\hat{w}}_{k}-w_{k})\otimes\sum^{r}_{i=1}\left({\hat{w}}_{k}^{\otimes(r-i)}\otimes
w_{k}^{\otimes(i-1)}\right)\right\|_{F}^{2}$ (84) $\displaystyle\leq$
$\displaystyle\,Cr^{2}\max_{k\in[m]}\mu_{r}(g_{\tau_{k}})^{2}\left[\|{\widehat{W}}-W\|_{F}^{2}+\left(\frac{\log
m}{D}\right)^{(r-1)/2}\sum^{m}_{k\neq
k^{\prime}}\left|\langle{\hat{w}}_{k}-w_{k},{\hat{w}}_{k^{\prime}}-w_{k}^{\prime}\rangle\right|\right].$
(85)

Combining this with (80) yields the desired first statement

$\displaystyle\sum^{m}_{\ell=1}S_{r,\ell}^{2}$ $\displaystyle\leq
Cr^{2}\max_{k,\ell\in[m]}\mu_{r}(g^{(1)}_{{\hat{\tau}}_{\ell}})^{2}\mu_{r}(g_{\tau_{k}})^{2}{\left(1+m\left(\frac{\log
m}{D}\right)^{r/2}\right)}$
$\displaystyle\cdot\left[\Delta_{W,F}^{2}+\left(\frac{\log
m}{D}\right)^{(r-1)/2}\Delta_{W,O}\right].$

For the second statement, note that $\max_{k\in[m]}\mu_{r}(g_{\tau_{k}})^{2}$
is bounded due to (M2) and
$\max_{\ell\in[m]}\mu_{r}(g^{(1)}_{{\hat{\tau}}_{\ell}})^{2}$ is bounded
according to Lemma 5. Hence it follows that

$\displaystyle\sum_{r=2}^{R}2^{r}\sum^{m}_{\ell=1}S_{r,\ell}^{2}$
$\displaystyle\leq\sum_{r=2}^{R}2^{r}Cr^{2}{\left(1+m\left(\frac{\log
m}{D}\right)^{r/2}\right)}\left[\Delta_{W,F}^{2}+\left(\frac{\log
m}{D}\right)^{(r-1)/2}\Delta_{W,O}\right]$
$\displaystyle\leq{\left(1+m\left(\frac{\log
m}{D}\right)\right)}\left(\Delta_{W,F}^{2}+\left(\frac{\log
m}{D}\right)^{1/2}\Delta_{W,O}\right)\sum_{r=1}^{R}2^{r}Cr^{2}.$

The second statement follows from the upper bound above by adjusting the
constant $C$ due to $\sum_{r=1}^{R}2^{r}Cr^{2}<\infty$ for fixed $R$ and using
$(m\log m)/D>1$. ∎

######  Lemma 10.

Consider weights and approximated weights
$(w_{k})_{k\in[m]},({\hat{w}}_{k})_{k\in[m]}$ of unit norm as before that both
fulfill (A2) and (i) in Lemma 3, as well shifts
$(\tau_{k})_{k\in[m]},({\hat{\tau}}_{k})_{k\in[m]}$ within
$[-\tau_{\infty},\tau_{\infty}]$ for some $\tau_{\infty}<\infty$. Let
$S_{r,\ell}$ be defined as in (77) and assume that $g$ fulfills the assumption
(M1) \- (M2). Then, there exists a constant $C>0$ such that for $m\geq D$

$\displaystyle\sum^{m}_{\ell=1}S_{1,\ell}^{2}\leq Cm\left(\frac{\log
m}{D}\right)^{1/2}\left\|\sum^{m}_{k=1}w_{k}-{\hat{w}}_{k}\right\|_{2}^{2}.$

###### Proof.

According to the proof of Lemma 9, in particular (80), we can bound

$\displaystyle\sum^{m}_{\ell=1}S_{1,\ell}^{2}\leq Cm\left(\frac{\log
m}{D}\right)^{1/2}\left\|\sum^{m}_{k=1}\mu_{1}(g_{\tau_{k}})(w_{k}-{\hat{w}}_{k})\right\|_{2}^{2},$

for some constant $C>0$. Since $\mu_{1}(g_{\tau_{k}})$ is bounded for all
$k\in[m]$, what remains is to show that the Hermite coefficients do not change
signs. Note that the first Hermite polynomial is given by $h_{1}(u)=u$.
According to the definition of the Hermite coefficients we have

$\displaystyle\mu_{1}(g_{\tau_{k}})$
$\displaystyle=\int_{\mathbb{R}}ug(u+\tau_{k})e^{-u^{2}/2}du=\left[-g(u+\tau_{k})e^{-u^{2}/2}\right]_{-\infty}^{\infty}+\int_{\mathbb{R}}g^{(1)}(u+\tau_{k})e^{-u^{2}/2}du$
$\displaystyle=\int_{\mathbb{R}}g^{(1)}(u+\tau_{k})e^{-u^{2}/2}du.$

Now note that $g^{(1)}(u+\tau_{k})$ will always have the same sign since
$g^{(2)}$ is monotonic due to (M1). Therefore
$\mu_{1}(g_{\tau_{1}}),\dots,\mu_{1}(g_{\tau_{m}})$ must all be either
positive or negative, from which the proof follows directly. ∎

######  Lemma 11.

Assume that $g$ fulfills the assumption (M1)-(M2) and that the shifts
$(\tau_{k})_{k\in[m]},({\hat{\tau}}_{k})_{k\in[m]}$ are within
$[-\tau_{\infty},\tau_{\infty}]$. Then, for $R\geq 4$, we have

$\displaystyle\sum_{r\geq
R}r|\max_{k,\ell\in[m]}\mu_{r}(g_{\tau_{k}})\mu_{r}(g^{(1)}_{{\hat{\tau}}_{\ell}})|<\infty.$
(86)

###### Proof.

By applying Lemma 15 (whose condition is met due to (M1) \- (M2)), we
immediately get that, for all $r\geq R$,

$\displaystyle\mu_{r}(g_{\tau_{k}})\mu_{r}(g^{(1)}_{{\hat{\tau}}_{\ell}})$
$\displaystyle=\left(3!\binom{r}{r-3}\right)^{-1/2}\mu_{r-3}(g^{(3)}_{\tau_{k}})\cdot\left(2!\binom{r}{r-2}\right)^{-1/2}\mu_{r-2}(g^{(3)}_{{\hat{\tau}}_{\ell}})$
$\displaystyle=\left((r-2)(r-1)^{2}r^{2}\right)^{-1/2}\mu_{r-3}(g^{(3)}_{\tau_{k}})\mu_{r-2}(g^{(3)}_{{\hat{\tau}}_{\ell}}).$

Plugging this into (86) yields

$\displaystyle\sum_{r\geq
R}r|\max_{k,\ell\in[m]}\mu_{r}(g_{\tau_{k}})\mu_{r}(g^{(1)}_{{\hat{\tau}}_{\ell}})|$
$\displaystyle\leq\sum_{r\geq
R}\frac{1}{\sqrt{r-2}(r-1)}\max_{k,\ell\in[m]}\mu_{r-3}(g^{(3)}_{\tau_{k}})\mu_{r-2}(g^{(3)}_{{\hat{\tau}}_{\ell}})$
$\displaystyle\leq\sum_{r\geq
R-3}\max_{k\in[m]}\frac{1}{r^{3/2}}\mu_{r}(g^{(3)}_{\tau_{k}})^{2}+\sum_{r\geq
R-2}\max_{\ell\in[m]}\frac{1}{r^{3/2}}\mu_{r}(g^{(3)}_{{\hat{\tau}}_{\ell}})^{2},$

where the second line follows by applying Cauchy-Schwarz. Using assumption
(M1), according to Lemma 5, then gives
$\max_{\tau\in[-\tau_{\infty},\tau_{\infty}]}\mu_{r}(g^{(3)}_{\tau})^{2}\leq
C$ for all $r\geq 0$ and some constant $C>0$. Therefore we can conclude with

$\displaystyle\sum_{r\geq
R}r|\max_{k,\ell\in[m]}\mu_{r}(g_{\tau_{k}})\mu_{r}(g^{(1)}_{{\hat{\tau}}_{\ell}})|\leq
2C\sum_{r\geq 1}\frac{1}{r^{3/2}}\leq 6C<\infty.$

∎

######  Lemma 12.

Consider weights and approximated weights
$(w_{k})_{k\in[m]},({\hat{w}}_{k})_{k\in[m]}$ of unit norm as before that both
fulfill (A2) and (i) in Lemma 3, as well as shifts
$(\tau_{k})_{k\in[m]},({\hat{\tau}}_{k})_{k\in[m]}$ within
$[-\tau_{\infty},\tau_{\infty}]$ for some $\tau_{\infty}<\infty$. Let
$S_{r,\ell}$ be defined as in (77), and assume that $g$ fulfills the
assumption (M1). Then, there exists a constant $C>0$ such that for $R\geq 9$
we have

$\displaystyle\sum^{m}_{\ell=1}\left(\sum_{r\geq R}S_{r,\ell}\right)^{2}\leq
C\sqrt{m}\Delta_{W,F}^{2}.$

###### Proof.

We start by applying the Cauchy product to the squared series

$\displaystyle\sum^{m}_{\ell=1}\left(\sum_{r\geq R}S_{r,\ell}\right)^{2}$
$\displaystyle=\sum^{m}_{\ell=1}\left(\sum_{r\geq
0}\sum^{r}_{s=0}S_{r+R-s,\ell}S_{s+R,\ell}\right)$ $\displaystyle=\sum_{r\geq
0}\sum^{r}_{s=0}\sum^{m}_{\ell=1}S_{r+R-s,\ell}S_{s+R,\ell}$
$\displaystyle\leq\sqrt{m}\sum_{r\geq
0}\sum^{r}_{s=0}\left(\sum^{m}_{\ell=1}S_{r+R-s,\ell}^{2}S_{s+R,\ell}^{2}\right)^{1/2}.$

The inner sum is now controlled by a sequence of inequalities similar to Lemma
9. Again we denote $\Delta_{k,r}:=\mu_{r}(g_{\tau_{k}})({\hat{w}}_{k}-w_{k})$
and $T_{k,r}:=\sum^{r}_{i=1}\left({\hat{w}}_{k}^{\otimes(r-i)}\otimes
w_{k}^{\otimes(i-1)}\right)$, then by applying the same chain of inequality as
in the beginning of the proof of Lemma 9 we receive

$\displaystyle\sum^{m}_{\ell=1}S_{r+R-s,\ell}^{2}S_{s+R,\ell}^{2}$
$\displaystyle=\sum^{m}_{\ell=1}\mu_{r+R-s}(g^{(1)}_{{\hat{\tau}}_{\ell}})^{2}\mu_{s+R}(g^{(1)}_{{\hat{\tau}}_{\ell}})^{2}$
$\displaystyle\cdot\left\langle\sum^{m}_{k=1}\Delta_{k,r+R-s}\otimes
T_{k,r+R-s},{\hat{w}}_{\ell}^{\otimes
r+R-s}\right\rangle^{2}\left\langle\sum^{m}_{k=1}\Delta_{k,s+R}\otimes
T_{k,s+R},{\hat{w}}_{\ell}^{\otimes s+R}\right\rangle^{2}$
$\displaystyle=\sum^{m}_{\ell=1}\mu_{r+R-s}(g^{(1)}_{{\hat{\tau}}_{\ell}})^{2}\mu_{s+R}(g^{(1)}_{{\hat{\tau}}_{\ell}})^{2}$
$\displaystyle\cdot\left\langle\left(\sum^{m}_{k=1}\Delta_{k,r+R-s}\otimes
T_{k,r+R-s}\right)\otimes\left(\sum^{m}_{k=1}\Delta_{k,s+R}\otimes
T_{k,s+R}\right),{\hat{w}}_{\ell}^{\otimes r+2R}\right\rangle^{2}.$

As before we now invoke the frame like condition described in Lemma 16 to
attain a bound depending on the upper spectrum of the Grammian
$(\widehat{G}_{r+2R})_{ij}=\langle{\hat{w}}_{i},{\hat{w}}_{j}\rangle^{r+2R}$.
More precisely, by using the shorthand

$\displaystyle\mu^{\prime}_{r,s}:=\max_{\ell\in[m]}\mu_{r+R-s}(g^{(1)}_{{\hat{\tau}}_{\ell}})^{2}\mu_{s+R}(g^{(1)}_{{\hat{\tau}}_{\ell}})^{2}$
(87)

we then have

$\displaystyle\sum^{m}_{\ell=1}S_{r+R-s,\ell}^{2}S_{s+R,\ell}^{2}$
$\displaystyle\leq\mu^{\prime}_{r,s}\|\widehat{G}_{r+2R}\|\left\|\left(\sum^{m}_{k=1}\Delta_{k,r+R-s}\otimes
T_{k,r+R-s}\right)\otimes\left(\sum^{m}_{k=1}\Delta_{k,s+R}\otimes
T_{k,s+R}\right)\right\|_{F}^{2}$ (88)
$\displaystyle\leq\mu^{\prime}_{r,s}\|\widehat{G}_{r+2R}\|\left\|\sum^{m}_{k=1}\Delta_{k,r+R-s}\otimes
T_{k,r+R-s}\right\|_{F}^{2}\left\|\sum^{m}_{k=1}\Delta_{k,s+R}\otimes
T_{k,s+R}\right\|_{F}^{2}.$ (89)

The two Frobenius norms can now be estimated as in Lemma 9, more precisely
(85), where we also use the shorthands $\Delta_{W,F},\Delta_{W,O}$ defined in
(78) - (79) as well as

$\displaystyle\mu_{r,s}:=\max_{k\in[m]}\mu_{r+R-s}(g_{\tau_{k}})^{2}\max_{k\in[m]}\mu_{s+R}(g_{\tau_{k}})^{2}.$

This gives for some absolute constant $C>0$

$\displaystyle\mu^{\prime}_{r,s}\|\widehat{G}_{r+2R}\|$
$\displaystyle\left\|\sum^{m}_{k=1}\Delta_{k,r+R-s}\otimes
T_{k,r+R-s}\right\|_{F}^{2}\left\|\sum^{m}_{k=1}\Delta_{k,s+R}\otimes
T_{k,s+R}\right\|_{F}^{2}$ $\displaystyle\leq
C\mu^{\prime}_{r,s}\mu_{r,s}\|\widehat{G}_{r+2R}\|(r+R-s)^{2}(s+R)^{2}$
$\displaystyle\cdot\left(\Delta_{W,F}^{2}+\left(\frac{\log
m}{D}\right)^{(r+R-s-1)/2}\Delta_{W,O}\right)\left(\Delta_{W,F}^{2}+\left(\frac{\log
m}{D}\right)^{(s+R-1)/2}\Delta_{W,O}\right)$ $\displaystyle\leq
C\mu^{\prime}_{r,s}\mu_{r,s}\|\widehat{G}_{r+2R}\|(r+R-s)^{2}(s+R)^{2}\left(\Delta_{W,F}^{2}+\left(\frac{\log
m}{D}\right)^{(R-1)/2}\Delta_{W,O}\right)^{2}.$

Next we identify the dominant factors and simplify. Due to Lemma 17 we have
for some constant $C>0$ that

$\displaystyle\|\widehat{G}_{r+2R}\|\leq C\left(1+m\left(\frac{\log
m}{D}\right)^{(r+2R)/2}\right)\leq C\left(1+m\left(\frac{\log
m}{D}\right)^{9}\right).$

where the last stop follows since $R\geq 9$ and due to $m(\log m)^{2}\leq
D^{2}$ this can be further simplified to $\|\widehat{G}_{r+2R}\|\leq C$.
Similarly, we have

$\displaystyle\left(\frac{\log m}{D}\right)^{(R-1)/2}\Delta_{W,O}$
$\displaystyle=\left(\frac{\log m}{D}\right)^{(R-1)/2}\sum^{m}_{k\neq
k^{\prime}}\left|\langle{\hat{w}}_{k}-w_{k},{\hat{w}}_{k^{\prime}}-w_{k}^{\prime}\rangle\right|$
$\displaystyle\leq\left(\frac{\log
m}{D}\right)^{4}m^{2}\delta_{\max}^{2}\leq\delta_{\max}^{2}\leq\Delta_{W,F}^{2}$

and therefore we get

$\displaystyle\|\widehat{G}_{r+2R}\|\left(\Delta_{W,F}^{2}+\left(\frac{\log
m}{D}\right)^{(R-1)/2}\Delta_{W,O}\right)^{2}\leq C\Delta_{W,F}^{4}$

for some absolute constant $C>0$. Plugging these into (89) results in

$\displaystyle\sum^{m}_{\ell=1}S_{r+R-s,\ell}^{2}S_{s+R,\ell}^{2}\leq
C\mu^{\prime}_{r,s}\mu_{r,s}(r+R-s)^{2}(s+R)^{2}\Delta_{W,F}^{4}.$

Hence, we have

$\displaystyle\sum^{m}_{\ell=1}\left(\sum_{r\geq R}S_{r,\ell}\right)^{2}$
$\displaystyle\leq\sqrt{m}\sum_{r\geq
0}\sum^{r}_{s=0}\left(\sum^{m}_{\ell=1}S_{r+R-s,\ell}^{2}S_{s+R,\ell}^{2}\right)^{1/2}$
$\displaystyle\leq C\Delta_{W,F}^{2}\sqrt{m}\sum_{r\geq
0}\sum^{r}_{s=0}\sqrt{|\mu^{\prime}_{r,s}\mu_{r,s}|}(r+R-s)(s+R)$
$\displaystyle\leq C\Delta_{W,F}^{2}\sqrt{m}\left(\sum_{r\geq
R}r|\max_{k,\ell}\mu_{r}(g_{\tau_{k}})\mu_{r}(g^{(1)}_{{\hat{\tau}}_{\ell}})|\right)^{2}.$

The result then follows by applying Lemma 11 onto the series in the last line
followed by a unification of the constants. ∎

Now, we are finally able to formalize the key lemma of this section. Recall
that

$\displaystyle\Delta_{W,F}$ $\displaystyle:=\|{\widehat{W}}-W\|_{F}$
$\displaystyle\Delta_{W,O}$ $\displaystyle:=\sum^{m}_{k\neq
k^{\prime}}\left|\langle{\hat{w}}_{k}-w_{k},{\hat{w}}_{k^{\prime}}-w_{k^{\prime}}\rangle\right|,$
$\displaystyle\Delta_{W,S}$
$\displaystyle:=\left\|\sum^{m}_{k=1}w_{k}-{\hat{w}}_{k}\right\|_{2}.$

######  Lemma 13.

Consider a shallow neural network $f$ with unit norm weights described by
${W}$, shifts ${\tau}_{1},\dots,{\tau}_{m}\in[-\tau_{\infty},\tau_{\infty}]$
stored in $\tau$ and an activation function $g$ that adheres to (M1) with
$D\leq m$. Furthermore, consider $J,J_{*}$ given by (69), (71) constructed
with ${N_{\text{train}}}\geq m$ network evaluations
$y_{1},\dots,y_{N_{\text{train}}}$ of ${f}$ where $y_{i}={f}(X_{i})$ and
$X_{1},\dots,X_{N}\sim{\cal N}(0,\operatorname{Id}_{D})$. Denote by $\hat{f}$
an approximation to ${f}$ constructed from parameters
${\widehat{W}}=[{\hat{w}}_{1}|\dots|{\hat{w}}_{m}],{\hat{\tau}}$ as described
above with $\|{\hat{w}}_{k}\|=1$ for all $k\in[m]$. Then, there exists an
absolute constant $C>0$ and $D_{0}$ such that, for dimension $D\geq D_{0}$,
the difference between the gradients of $J$ and of the idealized objective
$J_{*}$ obeys

$\displaystyle\left\lVert\nabla J({\hat{\tau}})-\nabla
J_{*}({\hat{\tau}})\right\rVert_{2}\leq
2\kappa^{2}\sqrt{m}\left\lVert{\hat{\tau}}-\tau\right\rVert^{2}_{2}+C\Delta_{W,1}+\left(\frac{m^{3}\delta_{\max}^{2}t}{{N_{\text{train}}}}\right)^{1/2}$
(90)

for $t>0$ with probability at least
$1-2m^{2}\exp\left(-\frac{t}{C\kappa^{4}}\right)$ and where

$\displaystyle\Delta_{W,1}\leq\frac{m^{1/2}\log(m)^{3/4}}{D^{1/4}}\left[\|{\widehat{W}}-W\|_{F}+\frac{\Delta_{W,O}^{1/2}}{D^{1/2}}+\left\|\sum^{m}_{k=1}w_{k}-{\hat{w}}_{k}\right\|_{2}\right].$

###### Proof of Lemma 13.

Recall that

$\displaystyle
J({\hat{\tau}})=\frac{1}{2{N_{\text{train}}}}\sum_{i=1}^{N_{\text{train}}}\Big{(}\hat{f}(X_{i},{\hat{\tau}})-{f}(X_{i},\tau)\Big{)}^{2}.$

By chain rule we compute the gradient of $J$ w.r.t. ${\hat{\tau}}$ as

$\displaystyle\nabla J({\hat{\tau}})$
$\displaystyle=\frac{1}{{N_{\text{train}}}}\sum_{i=1}^{N_{\text{train}}}\left(\hat{f}(X_{i},{\hat{\tau}})-{f}(X_{i},\tau)\right)\nabla\hat{f}(X_{i},{\hat{\tau}}).$

Adding
$0=(\hat{f}(X_{i},{\tau})-\hat{f}(X_{i},{\tau}))\nabla\hat{f}(X_{i},{\hat{\tau}})$
to $J({\hat{\tau}})$ and applying the triangle inequality to $\nabla J-\nabla
J_{*}$ allows us to separate the error caused by the weight approximation

$\displaystyle\Big{\|}\nabla J({\hat{\tau}})$ $\displaystyle-\nabla
J_{*}({\hat{\tau}})\Big{\|}_{2}$ $\displaystyle\leq$
$\displaystyle\,\Big{\|}\frac{1}{{N_{\text{train}}}}\Big{(}\sum_{i=1}^{N_{\text{train}}}(\hat{f}(X_{i},{\hat{\tau}})-\hat{f}(X_{i},{\tau}))\nabla\hat{f}(X_{i},{\hat{\tau}})-\nabla\hat{f}(X_{i},{\tau})\nabla\hat{f}(X_{i},{\tau})^{\top}({\hat{\tau}}-{\tau})\Big{)}\Big{\|}_{2}$
(91)
$\displaystyle+\Big{\|}\frac{1}{{N_{\text{train}}}}\sum^{N_{\text{train}}}_{i=1}\left(\hat{f}(X_{i},{\tau})-{f}(X_{i},{\tau})\right)\nabla\hat{f}(X_{i},{\hat{\tau}})\Big{\|}_{2}.$
(92)

To bound the first term in (91) denote
$h(\lambda)=(1-\lambda){\hat{\tau}}+\lambda{\tau}$, then we have

$\displaystyle\hat{f}(X_{i},{\hat{\tau}})-\hat{f}(X_{i},{\tau})$
$\displaystyle=\sum^{m}_{k=1}g({\hat{w}}_{k}^{\top}X_{i}+\tau_{k})-g({\hat{w}}_{k}^{\top}X_{i}+{\hat{\tau}}_{k})$
$\displaystyle=\sum^{m}_{k=1}g({\hat{w}}_{k}^{\top}X_{i}+h(1)_{k})-g({\hat{w}}_{k}^{\top}X_{i}+h(0)_{k})$
$\displaystyle=\sum^{m}_{k=1}\int^{h(1)_{k}}_{h(0)_{k}}g^{(1)}({\hat{w}}_{k}^{\top}X_{i}+u)du$
$\displaystyle=\sum^{m}_{k=1}\int^{1}_{0}g^{(1)}({\hat{w}}_{k}^{\top}X_{i}+h(\lambda)_{k})h^{\prime}(\lambda)_{k}d\lambda$
$\displaystyle=\sum^{m}_{k=1}\int^{1}_{0}g^{(1)}({\hat{w}}_{k}^{\top}X_{i}+h(\lambda)_{k})d\lambda(\tau_{k}-{\hat{\tau}}_{k}).$

Therefore, we can bound (91) as follows:

$\displaystyle\,\Big{\|}\frac{1}{{N_{\text{train}}}}\Big{(}\sum_{i=1}^{N_{\text{train}}}(\hat{f}(X_{i},{\hat{\tau}})-\hat{f}(X_{i},{\tau}))\nabla\hat{f}(X_{i},{\hat{\tau}})-\nabla\hat{f}(X_{i},{\tau})\nabla\hat{f}(X_{i},{\tau})^{\top}({\hat{\tau}}-{\tau})\Big{)}\Big{\|}_{2}$
$\displaystyle\leq$
$\displaystyle\,\Big{\|}\frac{1}{{N_{\text{train}}}}\Big{(}\sum_{i=1}^{N_{\text{train}}}\nabla\hat{f}(X_{i},{\hat{\tau}})\Big{(}\int^{1}_{0}\nabla\hat{f}(X_{i},h(\lambda))d\lambda\Big{)}^{\top}-\nabla\hat{f}(X_{i},{\tau})\nabla\hat{f}(X_{i},{\tau})^{\top}\Big{)}\Big{\|}\left\lVert({\hat{\tau}}-{\tau})\right\rVert_{2}.$

Let us fix ${\hat{\tau}},{\tau}$ for now and write the last line in terms of
matrices $\hat{F},{F},F^{*}\in\mathbb{R}^{{N_{\text{train}}}\times m}$, where
the $i$-th row of these matrices is given by
$\nabla\hat{f}(X_{i},{\hat{\tau}}),\nabla\hat{f}(X_{i},{\tau})$ and
$\int^{1}_{0}\nabla\hat{f}(X_{i},h(\lambda))d\lambda$, respectively. We obtain

$\displaystyle\Big{\|}\frac{1}{{N_{\text{train}}}}\Big{(}\sum_{i=1}^{N_{\text{train}}}\nabla\hat{f}(X_{i},{\hat{\tau}})\Big{(}\int^{1}_{0}\nabla\hat{f}(X_{i},h(\lambda))d\lambda\Big{)}^{\top}-\nabla\hat{f}(X_{i},{\tau})\nabla\hat{f}(X_{i},{\tau})^{\top}\Big{)}\Big{\|}\left\lVert({\hat{\tau}}-{\tau})\right\rVert_{2}$
$\displaystyle\leq$
$\displaystyle\frac{1}{{N_{\text{train}}}}\|\hat{F}^{\top}F^{*}-{F}^{\top}{F}\|\,\|{\hat{\tau}}-{\tau}\|_{2}$
$\displaystyle\leq$
$\displaystyle\frac{1}{{N_{\text{train}}}}\Big{(}\|\hat{F}-{F}\|\|F^{*}\|+\|{F}\|\|{F}-F^{*}\|\Big{)}\left\lVert{\hat{\tau}}-{\tau}\right\rVert_{2}.$
(93)

A simultaneous upper bound for $\|\hat{F}-{F}\|$ and $\|{F}-F^{*}\|$ can be
established with elementary matrix arithmetic and the Lipschitz continuity of
$g^{(1)}$:

$\displaystyle\|\hat{F}-{F}\|$
$\displaystyle\leq\|\hat{F}-{F}\|_{F}=\Big{[}\sum^{N_{\text{train}}}_{i=1}\sum^{m}_{k=1}(g^{(1)}(\langle{\hat{w}}_{k},X_{i}\rangle+{\hat{\tau}}_{k})-g^{(1)}(\langle{\hat{w}}_{k},X_{i}\rangle+\tau_{k}))^{2}\Big{]}^{\frac{1}{2}}$
$\displaystyle\leq\left\lVert