$-K^{(02)}({\bm{w}}_{0},{\bm{w}})[{\bm{z}},{\bm{z}}]>\rho\left\|{\bm{z}}\right\|_{2}^{2}$
and $\left\|K^{(02)}({\bm{w}}_{0},{\bm{w}})\right\|_{{\bm{w}}}\leq B$. Let
$\eta$ be a smooth function. If $\eta({\bm{w}}_{0})=a$,
$\nabla\eta({\bm{w}}_{0})=0$ and
$\left\|a\operatorname{D}_{2}\eta({\bm{w}})-K^{(02)}({\bm{w}}_{0},{\bm{w}})\right\|_{\bm{w}}\leq\tau$
for all $\delta({\bm{w}},{\bm{w}}_{0})\leq r$ with $\tau<\rho/2$, then we have
$|\eta({\bm{w}})|\leq 1-((\rho-2\tau)/2)\delta({\bm{w}},{\bm{w}}_{0})^{2}$ for
all $\delta({\bm{w}},{\bm{w}}_{0})\leq r$.

We now are ready to proof the main result in this section Lemma F.1 that shows
the non-degenerate dual certificate exists. Roughly speaking, following the
same proof as in Poon et al. (2023), we can show that
${\bm{\alpha}}\approx\operatorname{sign}({\bm{a}}_{*})$ and
${\bm{\alpha}}_{2}\approx{\bm{0}}$ and therefore we can transfer the non-
degeneracy of kernel $K$ to the dual certificate $\eta$ with Lemma G.3. See
F.1

###### Proof.

Note that
${\bm{\Upsilon}}={\bm{S}}{\bm{D}}\widetilde{{\bm{\Upsilon}}}{\bm{D}}{\bm{S}}$,
where

$\displaystyle{\bm{D}}=\begin{pmatrix}{\bm{I}}_{m_{*}}&&&\\\
&{\bm{P}}_{{\bm{w}}_{1}^{*}}\\\ &&\ddots&\\\
&&&{\bm{P}}_{{\bm{w}}_{m_{*}}^{*}}\\\
\end{pmatrix},\quad{\bm{S}}=\begin{pmatrix}{\bm{I}}_{m_{*}}&&&\\\
&(Z_{\sigma^{\prime}}/Z_{\sigma}){\bm{I}}_{m_{*}}\\\ &&\ddots&\\\
&&&(Z_{\sigma^{\prime}}/Z_{\sigma}){\bm{I}}_{m_{*}}\\\ \end{pmatrix}$

are block diagonal matrices,
$\widetilde{{\bm{\Upsilon}}}=\mathbb{E}_{\bm{x}}[\widetilde{{\bm{\gamma}}}({\bm{x}})\widetilde{{\bm{\gamma}}}({\bm{x}})^{\top}]\in\mathbb{R}^{m_{*}(d+1)\times
m_{*}(d+1)}$,

$\displaystyle\widetilde{{\bm{\gamma}}}({\bm{x}})=(\overline{\sigma_{\geq\ell}}({\bm{w}}_{1}^{*\top}{\bm{x}}),\ldots,\overline{\sigma_{\geq\ell}}({\bm{w}}_{m_{*}}^{*\top}{\bm{x}}),(Z_{\sigma}/Z_{\sigma^{\prime}})\overline{\sigma_{\geq\ell}}^{\prime}({\bm{w}}_{1}^{*\top}{\bm{x}}){\bm{x}}^{\top},\ldots,(Z_{\sigma}/Z_{\sigma^{\prime}})\overline{\sigma_{\geq\ell}}^{\prime}({\bm{w}}_{m_{*}}^{*\top}{\bm{x}}){\bm{x}}^{\top})^{\top}\in\mathbb{R}^{m_{*}(d+1)},$

$Z_{\sigma^{\prime}}=\sqrt{\sum_{k\geq\ell}\hat{\sigma}_{k}^{2}k}=\Theta(\ell^{-1/4})$
is the normalizing factor so that the diagonal of
$\widetilde{{\bm{\Upsilon}}}$ are all 1.

Thus, to solve (10), it is sufficient to solve the following: denote
$\widetilde{{\bm{K}}}={\bm{D}}\widetilde{{\bm{\Upsilon}}}{\bm{D}}$

$\displaystyle\widetilde{{\bm{K}}}\begin{pmatrix}\widetilde{{\bm{\alpha}}}_{1}\\\
\widetilde{{\bm{\alpha}}}_{2}\end{pmatrix}={\bm{b}},$ (11)

and let ${\bm{\alpha}}_{1}=\widetilde{{\bm{\alpha}}}_{1}$,
${\bm{\alpha}}_{2,i}=(Z_{\sigma}/Z_{\sigma^{\prime}})\widetilde{{\bm{\alpha}}}_{2,i}$
to get the solution of (10).

In the following, we are going to first show that
$\widetilde{{\bm{K}}}\approx{\bm{D}}{\bm{D}}$ because all the off-diagonal
terms of $\widetilde{{\bm{\Upsilon}}}$ are small due to Lemma G.1 (iii) (we
can choose $h$ to be small enough, and we will choose it later). Specifically,
we have

$\displaystyle\left\|\widetilde{{\bm{K}}}-{\bm{D}}{\bm{D}}\right\|_{2}=\sup_{\left\|{\bm{z}}\right\|_{2}=1}|{\bm{z}}^{\top}(\widetilde{{\bm{K}}}-{\bm{D}}{\bm{D}}){\bm{z}}|$
$\displaystyle=$
$\displaystyle\sup_{\left\|{\bm{z}}\right\|_{2}=1}\left|\sum_{i,j}z_{1,i}K({\bm{w}}_{i}^{*},{\bm{w}}_{j}^{*})z_{1,j}+2(Z_{\sigma}/Z_{\sigma^{\prime}})\sum_{i,j}z_{1,i}\nabla_{1}K({\bm{w}}_{i}^{*},{\bm{w}}_{j}^{*})^{\top}{\bm{z}}_{2,j}\right.$
$\displaystyle+\left.(Z_{\sigma}/Z_{\sigma^{\prime}})^{2}\sum_{i,j}{\bm{z}}_{2,i}^{\top}\nabla_{1}\nabla_{2}K({\bm{w}}_{i}^{*},{\bm{w}}_{j}^{*})^{\top}{\bm{z}}_{2,j}\right|$
$\displaystyle\leq$
$\displaystyle\sum_{i,j}|K({\bm{w}}_{i}^{*},{\bm{w}}_{j}^{*})|+\Theta(\ell^{-1/2})\left\|K^{(10)}({\bm{w}}_{i}^{*},{\bm{w}}_{j}^{*})\right\|_{{\bm{w}}_{i}^{*}}+\Theta(\ell^{-1})\left\|K^{(11)}({\bm{w}}_{i}^{*},{\bm{w}}_{j}^{*})\right\|_{{\bm{w}}_{i}^{*},{\bm{w}}_{j}^{*}}\leq
2h,$

where ${\bm{z}}=({\bm{z}}_{1}^{\top},{\bm{z}}_{2}^{\top})^{\top}$,
${\bm{z}}_{1}=({\bm{z}}_{1,1},\ldots,{\bm{z}}_{1,m_{*}})^{\top}$ and
${\bm{z}}_{2}=({\bm{z}}_{2,1}^{\top},\ldots,{\bm{z}}_{2,m_{*}}^{\top})^{\top}$
has the same block structure as $({\bm{\alpha}}_{1},{\bm{\alpha}}_{2})$ and we
use Lemma G.1 and Lemma G.2 in the last line.

Note that ${\bm{D}}{\bm{D}}$ has exactly $m_{*}d$ eigenvalues of 1 and $m_{*}$
eigenvalues of 0, and $\widetilde{{\bm{K}}}$ also has $m_{*}$ eigenvalues of
0. By Weyl’s inequality, we know $|\gamma_{i}-1|\leq 2h$ where
$\widetilde{{\bm{K}}}=\sum_{i\in[m_{*}d]}\gamma_{i}{\bm{v}}_{i}{\bm{v}}_{i}^{\top}$
is its eigendecomposition. Here ${\bm{v}}_{i}^{\top}{\bm{v}}_{\perp}=0$ for
all ${\bm{v}}_{\perp}\in
V_{\perp}=\operatorname{span}\\{({\bm{0}},{\bm{w}}_{1}^{*},{\bm{0}},\ldots,{\bm{0}})^{\top},\ldots({\bm{0}},\ldots,{\bm{0}},{\bm{w}}_{m_{*}}^{*})^{\top}\\}$
in the null space of ${\bm{D}}$. Since ${\bm{b}}^{\top}{\bm{v}}_{\perp}=0$ for
all ${\bm{v}}_{\perp}\in V_{\perp}$, we have

$\displaystyle\begin{pmatrix}\widetilde{{\bm{\alpha}}}_{1}\\\
\widetilde{{\bm{\alpha}}}_{2}\end{pmatrix}=$
$\displaystyle\widetilde{{\bm{K}}}^{\dagger}{\bm{b}}=\sum_{i\in[m_{*}d]}\gamma_{i}^{-1}{\bm{v}}_{i}{\bm{v}}_{i}^{\top}{\bm{b}}=\sum_{i\in[m_{*}d]}(\gamma_{i}^{-1}-1){\bm{v}}_{i}{\bm{v}}_{i}^{\top}{\bm{b}}+\sum_{i\in[m_{*}d]}{\bm{v}}_{i}{\bm{v}}_{i}^{\top}{\bm{b}}$
$\displaystyle=$
$\displaystyle\sum_{i\in[m_{*}d]}(\gamma_{i}^{-1}-1){\bm{v}}_{i}{\bm{v}}_{i}^{\top}{\bm{b}}+{\bm{b}}.$

Therefore,

$\displaystyle\left\|\begin{pmatrix}\widetilde{{\bm{\alpha}}}_{1}\\\
\widetilde{{\bm{\alpha}}}_{2}\end{pmatrix}-{\bm{b}}\right\|_{2}\leq\left\|\sum_{i\in[m_{*}d]}(\gamma_{i}^{-1}-1){\bm{v}}_{i}{\bm{v}}_{i}^{\top}{\bm{b}}\right\|_{2}\leq\max_{i}|\gamma_{i}^{-1}-1|\sqrt{m_{*}}=O(h\sqrt{m_{*}})=:h^{\prime}.$

This implies
$\left\|{\bm{\alpha}}_{1}-\operatorname{sign}({\bm{a}}_{*})\right\|_{\infty}=\left\|\widetilde{{\bm{\alpha}}}_{1}-\operatorname{sign}({\bm{a}}_{*})\right\|_{\infty}\leq
h^{\prime}$,
$\left\|{\bm{\alpha}}_{1}\right\|_{\infty}=\left\|\widetilde{{\bm{\alpha}}}_{1}\right\|_{\infty}\leq
1+h^{\prime}$ and
$\left\|{\bm{\alpha}}_{2}\right\|_{2}=(Z_{\sigma}/Z_{\sigma^{\prime}})\left\|\widetilde{{\bm{\alpha}}}_{2,i}\right\|_{2}\leq\Theta(h^{\prime}\ell^{-1/2})$.

Now, given the ${\bm{\alpha}}_{1}$, ${\bm{\alpha}}_{2}$, we can show the
corresponding $\eta$ is non-degenerate. Choosing $h=O(m_{*}^{-1/2})$ and
$\ell=\Theta(\Delta^{-2}\log(m_{*}/\Delta))$ so that the condition in Lemma
G.1 holds.

Consider ${\bm{w}}\in{\mathcal{T}}_{i}$, when
$\delta({\bm{w}},{\bm{w}}_{i}^{*})\geq r=\Theta(\ell^{-1/2})$, using Lemma G.1
and Lemma G.2 we have

$\displaystyle|\eta({\bm{w}})|=$
$\displaystyle\left|\sum_{j\in[m_{*}]}\alpha_{1,j}K({\bm{w}}_{j}^{*},{\bm{w}})+\sum_{j\in[m_{*}]}{\bm{\alpha}}_{2,j}^{\top}\nabla_{1}K({\bm{w}}_{j}^{*},{\bm{w}})\right|$
$\displaystyle\leq$
$\displaystyle\sum_{j\in[m_{*}]}|\alpha_{1,j}||K({\bm{w}}_{j}^{*},{\bm{w}})|+\sum_{j\in[m_{*}]}\left\|{\bm{\alpha}}_{2,j}\right\|_{{\bm{w}}_{j}^{*}}\left\|\nabla_{1}K({\bm{w}}_{j}^{*},{\bm{w}})\right\|_{{\bm{w}}_{j}^{*}}$
$\displaystyle\leq$
$\displaystyle(1+h^{\prime})(1-\rho_{1}+h)+\Theta(h^{\prime}\ell^{-1/2})(B_{10}+h)\leq
1-\rho_{1}/2\leq 1-\Theta(\rho_{1})\delta({\bm{w}},{\bm{w}}_{i}^{*})^{2},$

where we choose $h=O(m_{*}^{-1/2})$ to be small enough.

When $\delta({\bm{w}},{\bm{w}}_{i}^{*})\leq r=\Theta(\ell^{-1/2})$, again
using Lemma G.1 and Lemma G.2 we have

$\displaystyle\left\|a_{i}^{*}\operatorname{D}_{2}\eta({\bm{w}})-K^{(02)}({\bm{w}}_{i}^{*},{\bm{w}})\right\|_{{\bm{w}}}$
$\displaystyle\leq$
$\displaystyle\left\|\alpha_{1,i}K^{(02)}({\bm{w}}_{i}^{*},{\bm{w}})-K^{(02)}({\bm{w}}_{i}^{*},{\bm{w}})\right\|_{\bm{w}}+\sum_{j\neq
i}\left\|\alpha_{1,j}K^{(02)}({\bm{w}}_{j}^{*},{\bm{w}})\right\|_{\bm{w}}+\sum_{j\in[m_{*}]}\left\|{\bm{\alpha}}_{2,j}\right\|_{{\bm{w}}_{j}^{*}}\left\|K^{(12)}({\bm{w}}_{j}^{*},{\bm{w}})\right\|_{{\bm{w}}_{j}^{*},{\bm{w}}}$
$\displaystyle\leq$ $\displaystyle
h^{\prime}B_{02}+(1+h^{\prime})h+\Theta(h^{\prime}\ell^{-1/2})(B_{21}+h)\leq\rho_{2}/16,$

where again due to our choice of small $h$. Using Lemma G.3 we know that
$|\eta({\bm{w}})|\leq 1-(\rho_{2}/4)\delta({\bm{w}},{\bm{w}}_{i}^{*})^{2}$.

Combine the above two cases, we have $|\eta({\bm{w}})|\leq
1-\Theta(1)\delta({\bm{w}},{\bm{w}}_{i}^{*})^{2}$ and
$\eta({\bm{w}})=\mathbb{E}_{\bm{x}}[p({\bm{x}})\sigma({\bm{w}}^{\top}{\bm{x}})]$
with

$p({\bm{x}})=\frac{1}{Z_{\sigma}^{2}}\left(\sum_{j\in[m_{*}]}\alpha_{1,j}\sigma_{\geq\ell}({\bm{w}}_{j}^{*\top}{\bm{x}})+\sum_{j\in[m_{*}]}{\bm{\alpha}}_{2,j}^{\top}({\bm{I}}-{\bm{w}}_{i}^{*}{\bm{w}}_{i}^{*\top}){\bm{x}}\sigma_{\geq\ell}^{\prime}({\bm{w}}_{i}^{*\top}{\bm{x}})\right).$

We have
$\left\|p\right\|=O(\ell^{3/4}m_{*}+m_{*}h^{\prime}\ell^{-1/2}\ell^{5/4})=\widetilde{O}(\Delta^{-3/2}m_{*})$.
∎

##  Appendix H Proofs in Section F

In this section, we give the omitted proofs in Section F.

###  H.1 Omitted proofs in Section F.1

We give the proofs for these results that characterize the structure of ideal
loss solution.

The following proof follows from the definition of non-degenerate dual
certificate $\eta$. See F.2

###### Proof.

We show the results one by one.

##### Part (i)(ii)

We have

$\displaystyle|\langle\eta,\mu\rangle|\leq$
$\displaystyle\int_{{\mathbb{S}}^{d-1}}|\eta({\bm{w}})|\,\mathrm{d}|\mu|({\bm{w}})=\sum_{i\in[m_{*}]}\int_{{\mathcal{T}}_{i}}|\eta({\bm{w}})|\,\mathrm{d}|\mu|({\bm{w}})\leq|\mu|_{1}-\rho_{\eta}\sum_{i\in[m_{*}]}\int_{{\mathcal{T}}_{i}}\delta({\bm{w}},{\bm{w}}_{i}^{*})^{2}\,\mathrm{d}|\mu|({\bm{w}}).$

where the last inequality follows the property of non-degenerate dual
certificate (Definition 1). The other part then follows directly by the
definition of $\mu^{*}$.

##### Part (iii)

We have

$\displaystyle\langle\eta,\mu-\mu^{*}\rangle=$
$\displaystyle\int_{{\mathbb{S}}^{d-1}}\eta({\bm{w}})\,\mathrm{d}(\mu-\mu^{*})({\bm{w}})=\int_{{\mathbb{S}}^{d-1}}\mathbb{E}_{\bm{x}}[p({\bm{x}})\sigma_{\geq
2}({\bm{w}}^{\top}{\bm{x}})]\,\mathrm{d}(\mu-\mu^{*})({\bm{w}})$
$\displaystyle=$
$\displaystyle\mathbb{E}_{\bm{x}}\left[p({\bm{x}})\int_{{\mathbb{S}}^{d-1}}\sigma_{\geq
2}({\bm{w}}^{\top}{\bm{x}})\,\mathrm{d}(\mu-\mu^{*})({\bm{w}})\right]$
$\displaystyle=$
$\displaystyle\mathbb{E}_{\bm{x}}[p({\bm{x}})(f_{\mu}({\bm{x}})-f_{\mu^{*}}({\bm{x}}))].$

Note that $L(\mu)=\left\|f_{\mu}-f_{\mu^{*}}\right\|_{2}^{2}$, this leads to
$|\langle\eta,\mu-\mu^{*}\rangle|\leq\left\|p\right\|_{2}\sqrt{L(\mu)}$. ∎

Given the above lemma and the optimality of $\mu_{\lambda}^{*}$, we are able
to characterize the structure of $\mu_{\lambda}^{*}$ as below: norm is
bounded, square loss is small and far-away neurons are small. See F.3

###### Proof.

We show the results one by one.

##### Part (i)

Due to the optimality of $\mu_{\lambda}^{*}$, we have

$\displaystyle
L(\mu_{\lambda}^{*})+\lambda|\mu_{\lambda}^{*}|_{1}=L_{\lambda}(\mu_{\lambda}^{*})\leq
L_{\lambda}(\mu^{*})=L(\mu^{*})+\lambda|\mu^{*}|_{1}.$

Rearranging the terms, we have

$\displaystyle\lambda|\mu_{\lambda}^{*}|_{1}-\lambda|\mu^{*}|_{1}\leq
L(\mu^{*})-L(\mu_{\lambda}^{*})=-L(\mu_{\lambda}^{*})\leq 0.$

For the lower bound, with Lemma F.2 we have

$\displaystyle
0\leq|\mu_{\lambda}^{*}|_{1}-|\mu^{*}|_{1}-\langle\eta,\mu_{\lambda}^{*}-\mu^{*}\rangle\leq|\mu_{\lambda}^{*}|_{1}-|\mu^{*}|_{1}+\left\|p\right\|_{2}\sqrt{L(\mu_{\lambda}^{*})}.$

Using part (ii) we get the desired lower bound.

##### Part (ii)

We first have the following inequality due to the optimality of
$\mu_{\lambda}^{*}$ and adding
$\lambda\langle\eta,\mu_{\lambda}^{*}-\mu^{*}\rangle$ on both side:

$\displaystyle
L(\mu_{\lambda}^{*})+\underbrace{\lambda(|\mu_{\lambda}^{*}|_{1}-|\mu^{*}|_{1})-\lambda\langle\eta,\mu_{\lambda}^{*}-\mu^{*}\rangle}_{(I)}\leq
L(\mu^{*})-\lambda\langle\eta,\mu_{\lambda}^{*}-\mu^{*}\rangle.$

For $(I)$, we have

$\displaystyle(I)=\lambda(|\mu_{\lambda}^{*}|_{1}-\langle\eta,\mu_{\lambda}^{*}\rangle)+\lambda(\langle\eta,\mu^{*}\rangle-|\mu^{*}|_{1})\geq
0,$

where we use Lemma F.2 in the last inequality.

Therefore, the above inequality leads to

$\displaystyle L(\mu_{\lambda}^{*})\leq
L(\mu^{*})-\lambda\langle\eta,\mu_{\lambda}^{*}-\mu^{*}\rangle\leq\lambda\left\|p\right\|_{2}\sqrt{L(\mu_{\lambda}^{*})},$

where we again use Lemma F.2. This further leads to
$L(\mu_{\lambda}^{*})\leq\lambda^{2}\left\|p\right\|_{2}^{2}$.

##### Part (iii)

Using part (i) we have

$\displaystyle|\mu_{\lambda}^{*}|_{1}-|\mu^{*}|_{1}-\langle\eta,\mu_{\lambda}^{*}-\mu^{*}\rangle\leq-\langle\eta,\mu_{\lambda}^{*}-\mu^{*}\rangle.$

With Lemma F.2, LHS and RHS become

$\displaystyle\operatorname{LHS}=$
$\displaystyle|\mu_{\lambda}^{*}|_{1}-\langle\eta,\mu_{\lambda}^{*}\rangle\geq\rho_{\eta}\sum_{i\in[m_{*}]}\int_{{\mathcal{T}}_{i}}\delta({\bm{w}},{\bm{w}}_{i}^{*})^{2}\,\mathrm{d}|\mu_{\lambda}^{*}|({\bm{w}})$
$\displaystyle\operatorname{RHS}\leq$
$\displaystyle\left\|p\right\|_{2}\sqrt{L(\mu_{\lambda}^{*})}.$

Then using part (ii) we have the desired result. ∎

We are now ready to characterize the approximated solution by comparing $\mu$
and $\mu_{\lambda}^{*}$. See F.4

###### Proof.

We show the results one by one.

##### Part (i)

By the definition of the optimality gap $\zeta$ and adding
$-\lambda\langle\eta,\mu-\mu^{*}\rangle$ on both side, we have

$\displaystyle
L(\mu)+\lambda(|\mu|_{1}-|\mu_{\lambda}^{*}|_{1})-\lambda\langle\eta,\mu-\mu^{*}\rangle\leq
L(\mu_{\lambda}^{*})+\zeta-\lambda\langle\eta,\mu-\mu^{*}\rangle.$

Note that on LHS,

$\displaystyle\lambda(|\mu|_{1}-|\mu_{\lambda}^{*}|_{1})-\lambda\langle\eta,\mu-\mu^{*}\rangle=\lambda(|\mu|_{1}-\langle\eta,\mu\rangle)+\lambda(|\mu^{*}|_{1}-|\mu_{\lambda}^{*}|_{1})\geq
0,$

where we use Lemma F.2 and Lemma F.3.

Therefore, with Lemma F.2 and Lemma F.3 we get

$\displaystyle L(\mu)\leq
L(\mu_{\lambda}^{*})+\zeta-\lambda\langle\eta,\mu-\mu^{*}\rangle\leq\lambda^{2}\left\|p\right\|_{2}^{2}+\zeta+\lambda\left\|p\right\|_{2}\sqrt{L(\mu)}.$

Solving the above inequality on $L(\mu)$ gives $L(\mu)\leq
5\lambda^{2}\left\|p\right\|_{2}^{2}+4\zeta$.

##### Part (ii)

Again from the definition of the optimality gap $\zeta$, we have

$\displaystyle\lambda|\mu|_{1}\leq
L(\mu_{\lambda}^{*})+\lambda|\mu_{\lambda}^{*}|_{1}+\zeta-L(\mu)\leq\lambda^{2}\left\|p\right\|_{2}^{2}+\lambda|\mu^{*}|_{1}+\zeta,$

where we use Lemma F.3. Thus,
$|\mu|_{1}\leq\lambda\left\|p\right\|_{2}^{2}+|\mu^{*}|_{1}+\zeta/\lambda\leq
3|\mu^{*}|_{1}$. ∎

The lemma below shows that far-away neurons are still small even for the
approximated solution. Intutively, we use the non-degenerate dual certificate
to certify the gap between $\mu$ and $\mu_{\lambda}^{*}$ and give a bound for
it. See F.5

###### Proof.

By the definition of the optimality gap $\zeta$, we have

$\displaystyle
L(\mu)+\lambda|\mu|_{1}=L(\mu_{\lambda}^{*})+\lambda|\mu_{\lambda}^{*}|_{1}+\zeta.$

Rearranging the terms and adding $-\langle\eta,\mu-\mu^{*}\rangle$ on both
side, we get

$\displaystyle|\mu|_{1}-|\mu_{\lambda}^{*}|_{1}-\langle\eta,\mu-\mu^{*}\rangle=\frac{1}{\lambda}(L(\mu_{\lambda}^{*})-L(\mu)+\zeta)-\langle\eta,\mu-\mu^{*}\rangle.$

For LHS, with Lemma F.2 and Lemma F.3 we have

$\displaystyle\operatorname{LHS}=|\mu|_{1}-\langle\eta,\mu\rangle-|\mu_{\lambda}^{*}|_{1}+|\mu^{*}|_{1}\geq\rho_{\eta}\sum_{i\in[m_{*}]}\int_{{\mathcal{T}}_{i}}\delta({\bm{w}},{\bm{w}}_{i}^{*})^{2}\,\mathrm{d}|\mu|({\bm{w}}).$

For RHS, with Lemma F.2 and Lemma F.3 we have

$\displaystyle\operatorname{RHS}\leq\frac{1}{\lambda}(\lambda^{2}\left\|p\right\|_{2}^{2}-L(\mu)+\zeta)+\left\|p\right\|_{2}\sqrt{L(\mu)}=\frac{\zeta}{\lambda}+\lambda\left\|p\right\|_{2}^{2}-\frac{L(\mu)}{\lambda}+\left\|p\right\|_{2}\sqrt{L(\mu)}.$

When $L(\mu)\geq\lambda^{2}\left\|p\right\|_{2}^{2}$, we have
$\operatorname{RHS}\leq\zeta/\lambda+\lambda\left\|p\right\|_{2}^{2}$. When
$L(\mu)\leq\lambda^{2}\left\|p\right\|_{2}^{2}$, we have
$\operatorname{RHS}\leq\zeta/\lambda+2\lambda\left\|p\right\|_{2}^{2}$. Thus,
in summary
$\operatorname{RHS}\leq\zeta/\lambda+2\lambda\left\|p\right\|_{2}^{2}$.

Combine the bounds on LHS and RHS we have

$\displaystyle\rho_{\eta}\sum_{i\in[m_{*}]}\int_{{\mathcal{T}}_{i}}\delta({\bm{w}},{\bm{w}}_{i}^{*})^{2}\,\mathrm{d}|\mu|({\bm{w}})\leq\zeta/\lambda+2\lambda\left\|p\right\|_{2}^{2}.$

∎

The following lemma shows that every teacher neuron must have at least one
close-by student neuron within angle $O_{*}(\zeta^{1/3})$. This generalize and
greatly simplify the previous results Lemma 9 in Zhou et al. (2021). In
particular, we design a new test function using the Hermite expansion to
achieve this. See F.6

###### Proof.

Assume towards contradiction that there exists some $i\in[m_{*}]$ with some
$\delta_{close}\geq\widetilde{\Omega}\left((\frac{L(\mu)}{a_{\min}^{2}})^{1/(4c_{\sigma}-2)}\right)$
with large enough hidden constant such that
$\mu({\mathcal{T}}_{i}(\delta))\operatorname{sign}(a_{i}^{*})\leq|a_{i}^{*}|/2$.
For simplicity, we will use $\delta$ for $\delta_{close}$ in the following.

Let $g(x)=\sum_{\ell\leq
k<2\ell}\operatorname{sign}(a_{i}^{*})\operatorname{sign}(\hat{\sigma}_{k})h_{k}({\bm{w}}_{i}^{*\top}{\bm{x}})$
be a test function, where $h_{k}(x)$ is the $k$-th normalized probabilistic
Hermite polynomial and $\ell$ will be chosen later.

Denote $R({\bm{x}})=f_{\mu}({\bm{x}})-f_{\mu^{*}}({\bm{x}})$ so that
$\left\|R\right\|_{2}^{2}=L(\mu)$. We have

$\displaystyle\sqrt{L(\mu)}\left\|g\right\|_{2}\geq$
$\displaystyle\langle-R,g\rangle$ $\displaystyle=$
$\displaystyle\mathbb{E}_{\bm{x}}\left[\left(a_{i}^{*}\sigma({\bm{w}}_{i}^{*\top}{\bm{x}})-\int_{{\mathcal{T}}_{i}(\delta)}\sigma({\bm{w}}^{\top}{\bm{x}})\,\mathrm{d}\mu({\bm{w}})\right)g({\bm{x}})\right]$
$\displaystyle+\mathbb{E}_{\bm{x}}\left[\left(\sum_{j\neq
i}a_{j}^{*}\sigma({\bm{w}}_{j}^{*\top}{\bm{x}})-\int_{{\mathbb{S}}^{d-1}\setminus{\mathcal{T}}_{i}(\delta)}\sigma({\bm{w}}^{\top}{\bm{x}})\,\mathrm{d}\mu({\bm{w}})\right)g({\bm{x}})\right].$

Recall the Hermite expansion of $\sigma(x)=\sum_{k\geq
0}\hat{\sigma}_{k}h_{k}(x)$ and its property in Claim A.1. For the first term,
it becomes

$\displaystyle\sum_{\ell\leq
k<2\ell}\left(|a_{i}^{*}||\hat{\sigma}_{k}|-\int_{{\mathcal{T}}_{i}(\delta)}|\hat{\sigma}_{k}|\operatorname{sign}(a_{i}^{*})({\bm{w}}^{\top}{\bm{w}}_{i}^{*})^{k}\,\mathrm{d}\mu({\bm{w}})\right)\geq\frac{1}{2}|a_{i}^{*}|\sum_{\ell\leq
k<2\ell}|\hat{\sigma}_{k}|.$

For the second term, it becomes

$\displaystyle\sum_{\ell\leq k<2\ell}\left(\sum_{j\neq
i}a_{j}^{*}|\hat{\sigma}_{k}|\operatorname{sign}(a_{i}^{*})({\bm{w}}_{j}^{*\top}{\bm{w}}_{i}^{*})^{k}-\int_{{\mathbb{S}}^{d-1}\setminus{\mathcal{T}}_{i}(\delta)}|\hat{\sigma}_{k}|\operatorname{sign}(a_{i}^{*})({\bm{w}}^{\top}{\bm{w}}_{i}^{*})^{k}\,\mathrm{d}\mu({\bm{w}})\right)$
$\displaystyle\leq$
$\displaystyle(\left\|{\bm{a}}^{*}\right\|_{1}+|\mu|_{1})\sum_{\ell\leq k\leq
2\ell}|\hat{\sigma}_{k}|\max_{\angle({\bm{w}},{\bm{w}}_{i}^{*})\geq\delta}({\bm{w}}^{\top}{\bm{w}}_{i}^{*})^{k}$
$\displaystyle\leq$
$\displaystyle(\left\|{\bm{a}}^{*}\right\|_{1}+|\mu|_{1})\sum_{\ell\leq
k<2\ell}|\hat{\sigma}_{k}|(1-\delta^{2}/5)^{\ell}$ $\displaystyle\leq$
$\displaystyle
4\left\|{\bm{a}}^{*}\right\|_{1}(1-\delta^{2}/5)^{\ell}\sum_{\ell\leq
k<2\ell}|\hat{\sigma}_{k}|\leq\frac{1}{4}|a_{i}^{*}|\sum_{\ell\leq
k<2\ell}|\hat{\sigma}_{k}|,$

where (i) in the third line we use $\cos\delta\leq 1-\delta^{2}/5$ for
$\delta\in[0,\pi/2]$ and (ii) in the last line we use Lemma F.4 and choose
$\ell=\lceil(5/\delta^{2})\log(16\left\|{\bm{a}}^{*}\right\|_{1}/|a_{i}^{*}|)\rceil$.

Thus, given $|\hat{\sigma}_{k}|=\Theta(k^{-c_{\sigma}})$ we have

$\displaystyle\sqrt{L(\mu)}\sqrt{\ell}=\sqrt{L(\mu)}\left\|g\right\|_{2}\geq\frac{1}{4}|a_{i}^{*}|\sum_{\ell\leq
k<2\ell}|\hat{\sigma}_{k}|=\frac{1}{4}|a_{i}^{*}|\sum_{\ell\leq
k<2\ell}\Theta(k^{-c_{\sigma}})=|a_{i}^{*}|\Theta(\ell^{1-c_{\sigma}}).$

With the choice of $\ell=\widetilde{\Theta}(1/\delta^{2})$, we have
$\delta=\widetilde{O}\left(\left(\frac{L(\mu)}{|a_{i}^{*}|^{2}}\right)^{1/(4c_{\sigma}-2)}\right)$.
Since
$\delta\geq\widetilde{\Omega}\left((\frac{L(\mu)}{a_{\min}^{2}})^{1/(4c_{\sigma}-2)}\right)$
with a large enough hidden constant, we know this is a contradiction.

As a corollary, with Lemma F.4 that
$L(\mu)=4\zeta+5\lambda^{2}\left\|p\right\|_{2}^{2}$, we have
$\delta\geq\widetilde{\Omega}\left((\frac{4\zeta+5\lambda^{2}\left\|p\right\|_{2}^{2}}{a_{\min}^{2}})^{1/(4c_{\sigma}-2)}\right)$.

For the activation $\sigma$ is ReLU or absolute function, by Lemma A.1 we know
$c_{\sigma}=5/4$, which gives the desired result. ∎

The lemma below bounds $R_{2}$ using the fact that it is spiky (has small non-
zero support). See F.8

###### Proof.

Using the same calculation as in Lemma 12 in Zhou et al. (2021), we have

$\displaystyle\left\|R_{2}\right\|_{2}^{2}\leq$ $\displaystyle
O(m_{*})\sum_{i\in[m_{*}]}\left(\sum_{j\in{\mathcal{T}}_{i}}|a_{j}|\left\|{\bm{w}}_{j}\right\|_{2}\right)^{1/2}\left(\sum_{j\in{\mathcal{T}}_{i}}|a_{j}|\left\|{\bm{w}}_{j}\right\|_{2}\delta_{j}^{2}\right)^{3/2}$

With Lemma F.4 and Lemma F.5, we have
$\left\|R_{2}\right\|_{2}^{2}=O(m_{*}^{2}|\mu^{*}|^{1/2}(\zeta/\lambda+\lambda)^{3/2})$.
∎

The following lemma bounds $R_{3}$. In fact, in the view of expressing the
loss as a sum of tensor decomposition problem, $R_{3}$ corresponds to the 0-th
order term in the expansion. It would become small when high-order terms
become small, as shown in the proof below. See F.9

###### Proof.

As shown in Ge et al. (2018); Li et al. (2020), we can write the loss $L(\mu)$
as sum of tensor decomposition problem (recall
$\left\|{\bm{w}}_{i}^{*}\right\|_{2}=1$):

$\displaystyle L(\mu)=\sum_{k\geq
0}\hat{\sigma}_{k}^{2}\left\|\int_{{\bm{w}}\in{\mathbb{S}}^{d-1}}{\bm{w}}^{\otimes
k}\,\mathrm{d}\mu({\bm{w}})-\sum_{i\in[m_{*}]}a_{i}^{*}\left\|{\bm{w}}_{i}^{*}\right\|_{2}{\bm{w}}_{i}^{*\otimes
k}\right\|_{F}^{2}.$

Thus, we know for any $k\geq 1$,

$\displaystyle\left\|\int_{{\bm{w}}\in{\mathbb{S}}^{d-1}}{\bm{w}}^{\otimes
k}\,\mathrm{d}\mu({\bm{w}})-\sum_{i\in[m_{*}]}a_{i}^{*}\left\|{\bm{w}}_{i}^{*}\right\|_{2}{\bm{w}}_{i}^{*\otimes
k}\right\|_{F}^{2}\leq L(\mu)/\hat{\sigma}_{k}^{2}.$

Given any ${\bm{w}}_{j}^{*}$ and even $k$, we have

$\displaystyle\left\|\int_{{\bm{w}}\in{\mathbb{S}}^{d-1}}{\bm{w}}^{\otimes
k}\,\mathrm{d}\mu({\bm{w}})-\sum_{i\in[m_{*}]}a_{i}^{*}\left\|{\bm{w}}_{i}^{*}\right\|_{2}{\bm{w}}_{i}^{*\otimes
k}\right\|_{F}$ $\displaystyle\geq$
$\displaystyle\left|\left\langle\sum_{i\in[m_{*}]}a_{i}^{*}\left\|{\bm{w}}_{i}^{*}\right\|_{2}{\bm{w}}_{i}^{*\otimes
k}-\int_{{\bm{w}}\in{\mathbb{S}}^{d-1}}{\bm{w}}^{\otimes
k}\,\mathrm{d}\mu({\bm{w}}),{\bm{w}}_{j}^{*\otimes k}\right\rangle\right|$
$\displaystyle\geq$
$\displaystyle\left|a_{j}^{*}\left\|{\bm{w}}_{j}^{*}\right\|_{2}-\int_{{\mathcal{T}}_{j}}\langle{\bm{w}},{\bm{w}}_{j}^{*}\rangle^{k}\,\mathrm{d}\mu({\bm{w}})\right|-\left|\sum_{i\neq
j}a_{i}^{*}\left\|{\bm{w}}_{i}^{*}\right\|_{2}\langle{\bm{w}}_{i}^{*},{\bm{w}}_{j}^{*}\rangle^{k}-\int_{{\mathbb{S}}^{d-1}\setminus{\mathcal{T}}_{j}}\langle{\bm{w}},{\bm{w}}_{j}^{*}\rangle^{k}\,\mathrm{d}\mu({\bm{w}})\right|$
$\displaystyle\geq$
$\displaystyle\left|a_{j}^{*}\left\|{\bm{w}}_{j}^{*}\right\|_{2}-\int_{{\mathcal{T}}_{j}}\,\mathrm{d}\mu({\bm{w}})\right|-\left|\int_{{\mathcal{T}}_{j}}\,\mathrm{d}\mu({\bm{w}})-\int_{{\mathcal{T}}_{j}}\langle{\bm{w}},{\bm{w}}_{j}^{*}\rangle^{k}\,\mathrm{d}\mu({\bm{w}})\right|$
$\displaystyle-\left|\sum_{i\neq
j}a_{i}^{*}\left\|{\bm{w}}_{i}^{*}\right\|_{2}\langle{\bm{w}}_{i}^{*},{\bm{w}}_{j}^{*}\rangle^{k}-\int_{{\mathbb{S}}^{d-1}\setminus{\mathcal{T}}_{j}}\langle{\bm{w}},{\bm{w}}_{j}^{*}\rangle^{k}\,\mathrm{d}\mu({\bm{w}})\right|$

We show the last 2 terms are small.

For the second term on RHS, we have

$\displaystyle\left|\int_{{\mathcal{T}}_{j}}\,\mathrm{d}\mu({\bm{w}})-\int_{{\mathcal{T}}_{j}}\langle{\bm{w}},{\bm{w}}_{j}^{*}\rangle^{k}\,\mathrm{d}\mu({\bm{w}})\right|\leq$
$\displaystyle\int_{{\mathcal{T}}_{j}}\left(1-\langle{\bm{w}},{\bm{w}}_{j}^{*}\rangle^{k}\right)\,\mathrm{d}|\mu|({\bm{w}})\stackrel{{\scriptstyle(\text{a})}}{{\leq}}\int_{{\mathcal{T}}_{j}}1-(1-\delta({\bm{w}},{\bm{w}}_{j}^{*})^{2}/2)^{k}\,\mathrm{d}|\mu|({\bm{w}})$
$\displaystyle\stackrel{{\scriptstyle(\text{b})}}{{\leq}}$
$\displaystyle\int_{{\mathcal{T}}_{j},\delta({\bm{w}},{\bm{w}}_{j}^{*})^{2}\leq
1}O(k)\cdot\delta({\bm{w}},{\bm{w}}_{j}^{*})^{2}\,\mathrm{d}|\mu|({\bm{w}})+\int_{{\mathcal{T}}_{j},\delta({\bm{w}},{\bm{w}}_{j}^{*})^{2}>1}\,\mathrm{d}|\mu|({\bm{w}})$
$\displaystyle\leq$ $\displaystyle
O(k)\int_{{\mathcal{T}}_{j}}\delta({\bm{w}},{\bm{w}}_{j}^{*})^{2}\,\mathrm{d}|\mu|({\bm{w}}),$

where (a) $\cos\delta\geq 1-\delta^{2}/2$ for $\delta\in[0,\pi/2]$; (b)
$(1-x)^{k}\geq 1-kx$ for $x\in[0,1]$.

For the third term on RHS, we have

$\displaystyle\left|\sum_{i\neq
j}a_{i}^{*}\left\|{\bm{w}}_{i}^{*}\right\|_{2}\langle{\bm{w}}_{i}^{*},{\bm{w}}_{j}^{*}\rangle^{k}-\int_{{\mathbb{S}}^{d-1}\setminus{\mathcal{T}}_{j}}\langle{\bm{w}},{\bm{w}}_{j}^{*}\rangle^{k}\,\mathrm{d}\mu({\bm{w}})\right|\leq$
$\displaystyle(\left\|{\bm{a}}_{*}\right\|_{1}+|\mu|_{1})\max_{\angle({\bm{w}},{\bm{w}}_{j}^{*})\geq\Delta/2}({\bm{w}}^{\top}{\bm{w}}_{j}^{*})^{k}$
$\displaystyle\stackrel{{\scriptstyle(\text{a})}}{{\leq}}$
$\displaystyle(\left\|{\bm{a}}_{*}\right\|_{1}+|\mu|_{1})(1-\Delta^{2}/10)^{k}\stackrel{{\scriptstyle(\text{b})}}{{\leq}}O(\zeta),$

where (a) $\cos\delta\leq 1-\delta^{2}/5$ for $\delta\in[0,\pi/2]$; (b) we
choose $k=\Theta((1/\Delta^{2})\log(\zeta/\left\|{\bm{a}}_{*}\right\|_{1}))$
and Lemma F.4.

Therefore, we have

$\displaystyle\left\|\int_{{\bm{w}}\in{\mathbb{S}}^{d-1}}{\bm{w}}^{\otimes
k}\mu({\bm{w}})-\sum_{i\in[m_{*}]}a_{i}^{*}\left\|{\bm{w}}_{i}^{*}\right\|_{2}{\bm{w}}_{i}^{*\otimes
k}\right\|_{F}$ $\displaystyle\geq$
$\displaystyle\left|a_{j}^{*}\left\|{\bm{w}}_{j}^{*}\right\|_{2}-\int_{{\mathcal{T}}_{j}}\mu({\bm{w}})\right|-O(k)\int_{{\mathcal{T}}_{j}}\delta({\bm{w}},{\bm{w}}_{j}^{*})^{2}|\mu|({\bm{w}})-O(\zeta).$

This implies that

$\displaystyle m_{*}\sqrt{L(\mu)}/\hat{\sigma}_{k}\geq$
$\displaystyle\sum_{j\in[m_{*}]}\left|a_{j}^{*}\left\|{\bm{w}}_{j}^{*}\right\|_{2}-\int_{{\mathcal{T}}_{j}}\mu({\bm{w}})\right|-O(k)\sum_{j\in[m_{*}]}\int_{{\mathcal{T}}_{j}}\delta({\bm{w}},{\bm{w}}_{j}^{*})^{2}|\mu|({\bm{w}})-O(m_{*}\zeta)$
$\displaystyle\geq$
$\displaystyle\left|\sum_{i\in[m_{*}]}a_{i}^{*}\left\|{\bm{w}}_{i}^{*}\right\|_{2}-\int_{{\mathbb{S}}^{d-1}}\mu({\bm{w}})\right|-\widetilde{O}_{*}(\zeta/\lambda+\lambda)-O(m_{*}\zeta),$

where we use Lemma F.5. Rearranging the terms and recalling
$L(\mu)=O_{*}(\zeta+\lambda^{2})$ from Lemma F.4, we get the bound.

∎

The following lemma gives the bound on the average neuron to its corresponding
teacher neuron. It follows directly from the residual decomposition and
previous lemmas that characterize $R_{1},R_{2},R_{3}$ respectively. See F.10

###### Proof.

With the relation of residual decomposition, Lemma F.7, Lemma F.8 and Lemma
F.9, we have for any $i\in[m_{*}]$

$\displaystyle\Omega(\Delta^{3/2}/m_{*}^{3/2})\left(\sum_{i\in[m_{*}]}\left\|\sum_{j\in{\mathcal{T}}_{i}}a_{j}{\bm{w}}_{j}-{\bm{w}}_{i}^{*}\right\|_{2}^{2}\right)^{1/2}\leq\left\|R_{1}\right\|_{2}\leq\left\|R\right\|_{2}+\left\|R_{2}\right\|_{2}+\left\|R_{3}\right\|_{2}$
$\displaystyle=$ $\displaystyle
O_{*}((\zeta+\lambda^{2})^{1/2}+(\zeta/\lambda+\lambda)^{3/4})+\widetilde{O}_{*}((\zeta+\lambda^{2})^{1/2}+(\zeta/\lambda+\lambda)+\zeta).$

Rearranging the terms, we get the result. ∎

###  H.2 Omitted proofs in Section F.2

In this section, we give the omitted proofs in Section F.2. The key
observation used in the proofs is that balancing the norm and setting
$\alpha,{\bm{\beta}}$ perfectly to their target values only decrease the
optimality gap. See F.11

###### Proof.

Recall in Claim B.1 we have

$\displaystyle
L({\bm{\theta}})=|\alpha-\hat{\alpha}|^{2}+\left\|{\bm{\beta}}-\hat{{\bm{\beta}}}\right\|_{2}^{2}+\sum_{k\geq
2}\hat{\sigma}_{k}^{2}\left\|\sum_{i\in[m]}a_{i}\left\|{\bm{w}}_{i}\right\|_{2}\overline{{\bm{w}}}_{i}^{\otimes
k}-\sum_{i\in[m_{*}]}a_{i}^{*}\left\|{\bm{w}}_{i}^{*}\right\|_{2}{\bm{w}}_{i}^{*\otimes
k}\right\|_{F}^{2}.$

Note that
$|a_{i}|\left\|{\bm{w}}_{i}\right\|_{2}=|a_{bal,i}|\left\|{\bm{w}}_{bal,i}\right\|_{2}$
so that
$L({\bm{\theta}})=L({\bm{\theta}}_{bal})+|\alpha-\hat{\alpha}|^{2}+\left\|{\bm{\beta}}-\hat{{\bm{\beta}}}\right\|_{2}^{2}$.
We then have

$\displaystyle L_{\lambda}({\bm{\theta}})-L_{\lambda}({\bm{\theta}}_{bal})=$
$\displaystyle|\alpha-\hat{\alpha}|^{2}+\left\|{\bm{\beta}}-\hat{{\bm{\beta}}}\right\|_{2}^{2}+\frac{\lambda}{2}\left\|{\bm{a}}\right\|_{2}^{2}+\frac{\lambda}{2}\left\|{\bm{W}}\right\|_{2}^{2}-\frac{\lambda}{2}\left\|{\bm{a}}_{bal}\right\|_{2}^{2}-\frac{\lambda}{2}\left\|{\bm{W}}_{bal}\right\|_{2}^{2}$
$\displaystyle=$
$\displaystyle|\alpha-\hat{\alpha}|^{2}+\left\|{\bm{\beta}}-\hat{{\bm{\beta}}}\right\|_{2}^{2}+\frac{\lambda}{2}\sum_{i\in[m]}(|a_{i}|-\left\|{\bm{w}}_{i}\right\|_{2})^{2}.$

Therefore, we have the optimality gap
$\zeta=L_{\lambda}({\bm{\theta}})-L_{\lambda}(\mu_{\lambda}^{*})\geq
L_{\lambda}({\bm{\theta}}_{bal})-L_{\lambda}(\mu_{\lambda}^{*})=\zeta_{bal}$.
Note that ${\bm{\theta}}_{bal}$ corresponds to a network that has perfect
balanced norms and fitted $\alpha,{\bm{\beta}}$, thus all results in Lemma
F.4, Lemma F.5, Lemma F.6, Lemma F.7, Lemma F.8, Lemma F.9 and Lemma F.10 hold
for ${\bm{\theta}}_{bal}$. Since $\zeta\geq\zeta_{bal}$,
$|a_{i}|\left\|{\bm{w}}_{i}\right\|_{2}=|a_{bal,i}|\left\|{\bm{w}}_{bal,i}\right\|_{2}$
and $L({\bm{\theta}})=L({\bm{\theta}}_{bal})+O(\zeta)$, we can easily check
that all of them also hold for ${\bm{\theta}}$. For the bound on $R_{3}$, note
that

$\displaystyle\left\|R_{3}\right\|_{2}$
$\displaystyle\leq\frac{1}{\sqrt{2\pi}}\left|\sum_{i\in[m_{*}]}a_{i}^{*}\left\|{\bm{w}}_{i}^{*}\right\|_{2}-\sum_{i\in[m]}a_{i}\left\|{\bm{w}}_{i}\right\|_{2}\right|+|\alpha-\hat{\alpha}|+\left\|{\bm{\beta}}-\hat{{\bm{\beta}}}\right\|_{2}$

so that the same bound still hold for $R_{3}$. ∎

See F.12

###### Proof.

We have

$\displaystyle\frac{\lambda}{2}\left\|{\bm{a}}\right\|_{2}^{2}+\frac{\lambda}{2}\left\|{\bm{W}}\right\|_{F}^{2}=\zeta+L(\mu_{\lambda}^{*})+\lambda|\mu_{\lambda}^{*}|_{1}-L({\bm{\theta}})\leq\zeta+\lambda^{2}\left\|p\right\|_{2}^{2}+\lambda|\mu_{\lambda}^{*}|_{1},$

where we use Lemma F.3. Rearranging the terms, we get the result by noting
that $|\mu_{\lambda}^{*}|_{1}\leq\left\|{\bm{a}}_{*}\right\|_{1}$. ∎

###  H.3 Omitted proofs in Section F.3

In this section, we give the omitted proofs in Section F.3. We will consider
them case by case.

The lemma below says that one can always decrease the loss if norms are not
balanced. See F.15

###### Proof.

We have

$\displaystyle\sum_{i\in[m]}\left|\langle\nabla_{a_{j}}L_{\lambda},-a_{j}\rangle+\langle\nabla_{{\bm{w}}_{j}}L_{\lambda},{\bm{w}}_{j}\rangle\right|$
$\displaystyle=$
$\displaystyle\sum_{i\in[m]}\left|-2\mathbb{E}_{\bm{x}}[(f({\bm{x}})-f_{*}({\bm{x}}))a_{j}\sigma({\bm{w}}_{j}^{\top}{\bm{x}})]-\lambda
a_{j}^{2}+2\mathbb{E}_{\bm{x}}[(f({\bm{x}})-f_{*}({\bm{x}}))a_{j}\sigma({\bm{w}}_{j}^{\top}{\bm{x}})]+\lambda\left\|{\bm{w}}_{i}\right\|_{2}^{2}\right|$
$\displaystyle=$
$\displaystyle\lambda\sum_{i\in[m]}\left|a_{i}^{2}-\left\|{\bm{w}}_{i}\right\|_{2}^{2}\right|$

Note that
$|a_{i}|+\left\|{\bm{w}}_{i}\right\|_{2}\geq||a_{i}|-\left\|{\bm{w}}_{i}\right\|_{2}|$,
we get the result. ∎

The following lemma shows that one can always decrease the loss if there are
close-by neurons that cancels with others. Intuitively, reducing such norm
cancellation decrease the regularization term while keeping the square loss
term, which decreasing the total loss as a whole. See F.16

###### Proof.

Denote $R({\bm{x}})=f({\bm{x}})-\widetilde{f}_{*}({\bm{x}})$. We have

$\displaystyle\sum_{s\in\\{+,-\\}}\sum_{j\in
T_{i,s}(\delta_{\operatorname{sign}})}\left\langle\nabla_{a_{j}}L_{\lambda},\frac{a_{j}}{\sum_{j\in
T_{i,s}(\delta_{\operatorname{sign}})}|a_{j}|\left\|{\bm{w}}_{j}\right\|_{2}}\right\rangle+\left\langle\nabla_{{\bm{w}}_{j}}L_{\lambda},\frac{{\bm{w}}_{j}}{\sum_{j\in
T_{i,s}(\delta_{\operatorname{sign}})}|a_{j}|\left\|{\bm{w}}_{j}\right\|_{2}}\right\rangle$
$\displaystyle=$ $\displaystyle\sum_{s\in\\{+,-\\}}\sum_{j\in
T_{i,s}(\delta_{\operatorname{sign}})}\frac{a_{j}\left\|{\bm{w}}_{j}\right\|_{2}}{\sum_{j\in
T_{i,s}(\delta_{\operatorname{sign}})}|a_{j}|\left\|{\bm{w}}_{j}\right\|_{2}}\cdot
2\mathbb{E}_{\bm{x}}[R({\bm{x}})\sigma(\overline{{\bm{w}}}_{j}^{\top}{\bm{x}})]+\frac{\lambda
a_{j}^{2}}{\sum_{j\in
T_{i,s}(\delta_{\operatorname{sign}})}|a_{j}|\left\|{\bm{w}}_{j}\right\|_{2}}$
$\displaystyle+\sum_{s\in\\{+,-\\}}\sum_{j\in
T_{i,s}(\delta_{\operatorname{sign}})}\frac{a_{j}\left\|{\bm{w}}_{j}\right\|_{2}}{\sum_{j\in
T_{i,s}(\delta_{\operatorname{sign}})}|a_{j}|\left\|{\bm{w}}_{j}\right\|_{2}}\cdot
2\mathbb{E}_{\bm{x}}[R({\bm{x}})\sigma(\overline{{\bm{w}}}_{j}^{\top}{\bm{x}})]+\frac{\lambda\left\|{\bm{w}}_{j}\right\|_{2}^{2}}{\sum_{j\in
T_{i,s}(\delta_{\operatorname{sign}})}|a_{j}|\left\|{\bm{w}}_{j}\right\|_{2}}$

We split the above into two terms (depending on square loss or
regularization). WLOG, assume $\operatorname{sign}(a_{i}^{*})=1$. For the
first term that depends on gradient on square loss,

$\displaystyle(I)=$ $\displaystyle 4\sum_{s\in\\{+,-\\}}\sum_{j\in
T_{i,s}(\delta_{\operatorname{sign}})}\frac{a_{j}\left\|{\bm{w}}_{j}\right\|_{2}}{\sum_{j\in
T_{i,s}(\delta_{\operatorname{sign}})}|a_{j}|\left\|{\bm{w}}_{j}\right\|_{2}}\cdot\mathbb{E}_{\bm{x}}[R({\bm{x}})\sigma(\overline{{\bm{w}}}_{j}^{\top}{\bm{x}})]$
$\displaystyle=$ $\displaystyle 4\sum_{j\in
T_{i,+}(\delta_{\operatorname{sign}})}\frac{|a_{j}|\left\|{\bm{w}}_{j}\right\|_{2}}{\sum_{j\in
T_{i,+}(\delta_{\operatorname{sign}})}|a_{j}|\left\|{\bm{w}}_{j}\right\|_{2}}\mathbb{E}_{\bm{x}}[R({\bm{x}})\sigma(\overline{{\bm{w}}}_{j}^{\top}{\bm{x}})]$
$\displaystyle-4\sum_{j\in
T_{i,-}(\delta_{\operatorname{sign}})}\frac{|a_{j}|\left\|{\bm{w}}_{j}\right\|_{2}}{\sum_{j\in
T_{i,-}(\delta_{\operatorname{sign}})}|a_{j}|\left\|{\bm{w}}_{j}\right\|_{2}}\mathbb{E}_{\bm{x}}[R({\bm{x}})\sigma(\overline{{\bm{w}}}_{j}^{\top}{\bm{x}})]$
$\displaystyle=$ $\displaystyle 4\sum_{j\in
T_{i,+}(\delta_{\operatorname{sign}})}\frac{|a_{j}|\left\|{\bm{w}}_{j}\right\|_{2}}{\sum_{j\in
T_{i,+}(\delta_{\operatorname{sign}})}|a_{j}|\left\|{\bm{w}}_{j}\right\|_{2}}\mathbb{E}_{\bm{x}}[R({\bm{x}})(\sigma(\overline{{\bm{w}}}_{j}^{\top}{\bm{x}})-\sigma(\overline{{\bm{w}}}_{i}^{*\top}{\bm{x}}))]$
$\displaystyle-4\sum_{j\in
T_{i,-}(\delta_{\operatorname{sign}})}\frac{|a_{j}|\left\|{\bm{w}}_{j}\right\|_{2}}{\sum_{j\in
T_{i,-}(\delta_{\operatorname{sign}})}|a_{j}|\left\|{\bm{w}}_{j}\right\|_{2}}\mathbb{E}_{\bm{x}}[R({\bm{x}})(\sigma(\overline{{\bm{w}}}_{j}^{\top}{\bm{x}})-\sigma(\overline{{\bm{w}}}_{i}^{*\top}{\bm{x}}))]$

Since $\overline{{\bm{w}}}_{j}$ is $\delta_{\operatorname{sign}}$-close to
${\bm{w}}_{i}^{*}$ and $\left\|R\right\|_{2}^{2}=L({\bm{\theta}})$, we have

$\displaystyle|(I)|\leq
O(\delta_{\operatorname{sign}})\left\|R\right\|_{2}=O_{*}(\delta_{\operatorname{sign}}\zeta^{1/2}),$

where we use Lemma F.11 that $L({\bm{\theta}})=O_{*}(\zeta)$.

For the second term that depends on regularization, we have

$\displaystyle(II)=$ $\displaystyle\lambda\sum_{s\in\\{+,-\\}}\frac{\sum_{j\in
T_{i,s}(\delta_{\operatorname{sign}})}a_{j}^{2}+\left\|{\bm{w}}_{j}\right\|_{2}^{2}}{\sum_{j\in
T_{i,s}(\delta_{\operatorname{sign}})}|a_{j}|\left\|{\bm{w}}_{j}\right\|_{2}}\geq
2\lambda+2\lambda=4\lambda.$

Therefore, when $(I)\leq 2\lambda$, i.e.,
$\delta_{\operatorname{sign}}=O_{*}(\lambda/\zeta^{1/2})$, we have

$\displaystyle\sum_{s\in\\{+,-\\}}\sum_{j\in
T_{i,s}(\delta_{\operatorname{sign}})}\left\langle\nabla_{a_{j}}L_{\lambda},\frac{\operatorname{sign}(a_{j})|a_{j}|}{\sum_{j\in
T_{i,s}(\delta_{\operatorname{sign}})}|a_{j}|\left\|{\bm{w}}_{j}\right\|_{2}}\right\rangle+\left\langle\nabla_{{\bm{w}}_{j}}L_{\lambda},\frac{{\bm{w}}_{j}}{\sum_{j\in
T_{i,s}(\delta_{\operatorname{sign}})}|a_{j}|\left\|{\bm{w}}_{j}\right\|_{2}}\right\rangle$
$\displaystyle\geq$
$\displaystyle\frac{\lambda}{2}\sum_{s\in\\{+,-\\}}\frac{\sum_{j\in
T_{i,s}(\delta_{\operatorname{sign}})}a_{j}^{2}+\left\|{\bm{w}}_{j}\right\|_{2}^{2}}{\sum_{j\in
T_{i,s}(\delta_{\operatorname{sign}})}|a_{j}|\left\|{\bm{w}}_{j}\right\|_{2}}.$

We compute a upper bound for LHS. Note that

$\displaystyle\sum_{s\in\\{+,-\\}}\sum_{j\in
T_{i,s}(\delta_{\operatorname{sign}})}\left\langle\nabla_{a_{j}}L_{\lambda},\frac{a_{j}}{\sum_{j\in
T_{i,s}(\delta_{\operatorname{sign}})}|a_{j}|\left\|{\bm{w}}_{j}\right\|_{2}}\right\rangle+\left\langle\nabla_{{\bm{w}}_{j}}L_{\lambda},\frac{{\bm{w}}_{j}}{\sum_{j\in
T_{i,s}(\delta_{\operatorname{sign}})}|a_{j}|\left\|{\bm{w}}_{j}\right\|_{2}}\right\rangle$
$\displaystyle\leq$ $\displaystyle\sqrt{\sum_{s\in\\{+,-\\}}\sum_{j\in
T_{i,s}(\delta_{\operatorname{sign}})}(\nabla_{a_{j}}L_{\lambda})^{2}+\left\|\nabla_{{\bm{w}}_{j}}L_{\lambda}\right\|_{2}^{2}}\sqrt{\sum_{s\in\\{+,-\\}}\sum_{j\in
T_{i,s}(\delta_{\operatorname{sign}})}\frac{a_{j}^{2}+\left\|{\bm{w}}_{j}\right\|_{2}^{2}}{(\sum_{j\in
T_{i,s}(\delta_{\operatorname{sign}})}|a_{j}|\left\|{\bm{w}}_{j}\right\|_{2})^{2}}}$
$\displaystyle\leq$
$\displaystyle\sqrt{\left\|\nabla_{{\bm{a}}}L_{\lambda}\right\|_{2}^{2}+\left\|\nabla_{{\bm{W}}}L_{\lambda}\right\|_{F}^{2}}\sqrt{\sum_{s\in\\{+,-\\}}\frac{\sum_{j\in
T_{i,s}(\delta_{\operatorname{sign}})}a_{j}^{2}+\left\|{\bm{w}}_{j}\right\|_{2}^{2}}{(\sum_{j\in
T_{i,s}(\delta_{\operatorname{sign}})}|a_{j}|\left\|{\bm{w}}_{j}\right\|_{2})^{2}}}$
$\displaystyle\leq$
$\displaystyle\sqrt{\left\|\nabla_{{\bm{a}}}L_{\lambda}\right\|_{2}^{2}+\left\|\nabla_{{\bm{W}}}L_{\lambda}\right\|_{F}^{2}}\sqrt{\sum_{s\in\\{+,-\\}}\frac{\sum_{j\in
T_{i,s}(\delta_{\operatorname{sign}})}a_{j}^{2}+\left\|{\bm{w}}_{j}\right\|_{2}^{2}}{\sum_{j\in
T_{i,s}(\delta_{\operatorname{sign}})}|a_{j}|\left\|{\bm{w}}_{j}\right\|_{2}}}\frac{1}{\sqrt{\sum_{j\in
T_{i,-}(\delta_{\operatorname{sign}})}|a_{j}|\left\|{\bm{w}}_{j}\right\|_{2}}},$

where the last line we use Lemma F.6: $\sum_{j\in
T_{i,-}(\delta_{\operatorname{sign}})}|a_{j}|\left\|{\bm{w}}_{j}\right\|_{2}<\sum_{j\in
T_{i,+}(\delta_{\operatorname{sign}})}|a_{j}|\left\|{\bm{w}}_{j}\right\|_{2}$
because $\mu(T_{i}(\delta))=\sum_{j\in
T_{i}(\delta_{\operatorname{sign}})}a_{j}\left\|{\bm{w}}_{j}\right\|_{2}>0$.

Combine with the above descent direction, we have

$\displaystyle\sqrt{\left\|\nabla_{{\bm{a}}}L_{\lambda}\right\|_{2}^{2}+\left\|\nabla_{{\bm{W}}}L_{\lambda}\right\|_{F}^{2}}\sqrt{\sum_{s\in\\{+,-\\}}\frac{\sum_{j\in
T_{i,s}(\delta_{\operatorname{sign}})}a_{j}^{2}+\left\|{\bm{w}}_{j}\right\|_{2}^{2}}{\sum_{j\in
T_{i,s}(\delta_{\operatorname{sign}})}|a_{j}|\left\|{\bm{w}}_{j}\right\|_{2}}}\frac{1}{\sqrt{\sum_{j\in
T_{i,-}(\delta_{\operatorname{sign}})}|a_{j}|\left\|{\bm{w}}_{j}\right\|_{2}}}$
$\displaystyle\geq$
$\displaystyle\frac{\lambda}{2}\sum_{s\in\\{+,-\\}}\frac{\sum_{j\in
T_{i,s}(\delta_{\operatorname{sign}})}a_{j}^{2}+\left\|{\bm{w}}_{j}\right\|_{2}^{2}}{\sum_{j\in
T_{i,s}(\delta_{\operatorname{sign}})}|a_{j}|\left\|{\bm{w}}_{j}\right\|_{2}},$

which implies

$\displaystyle\left\|\nabla_{{\bm{a}}}L_{\lambda}\right\|_{2}^{2}+\left\|\nabla_{{\bm{W}}}L_{\lambda}\right\|_{F}^{2}\geq$
$\displaystyle\lambda^{2}\sum_{j\in
T_{i,-}(\delta_{\operatorname{sign}})}|a_{j}|\left\|{\bm{w}}_{j}\right\|_{2}$

∎

The lemma below shows that when all previous cases are not hold, then there is
a descent direction that move all close-by neurons towards their corresponding
teacher neuron. The proof relies on calculations that generalize Lemma 8 in
Zhou et al. (2021). See F.17

###### Proof.

Recall residual $R({\bm{x}})=f({\bm{x}})-\widetilde{f}_{*}({\bm{x}})$. We have

$\displaystyle(\alpha+\alpha_{*})\nabla_{\alpha}L_{\lambda}+\langle\nabla_{\bm{\beta}}L_{\lambda},{\bm{\beta}}+{\bm{\beta}}_{*}\rangle+\sum_{i\in[m_{*}]}\sum_{j\in{\mathcal{T}}_{i}}\langle\nabla_{{\bm{w}}_{i}}L_{\lambda},{\bm{w}}_{j}-q_{ij}{\bm{w}}_{i}^{*}\rangle$
$\displaystyle\stackrel{{\scriptstyle(\text{a})}}{{=}}$ $\displaystyle
2\mathbb{E}_{\bm{x}}[R({\bm{x}})(\alpha+\alpha_{*})]+2\mathbb{E}_{\bm{x}}[R({\bm{x}})({\bm{\beta}}+{\bm{\beta}}_{*})^{\top}{\bm{x}}]$
$\displaystyle+2\sum_{i\in[m_{*}]}\sum_{j\in{\mathcal{T}}_{i}}\mathbb{E}_{\bm{x}}[R({\bm{x}})a_{j}\sigma({\bm{w}}_{j}^{\top}{\bm{x}})]-2\sum_{i\in[m_{*}]}\sum_{j\in{\mathcal{T}}_{i}}\mathbb{E}_{\bm{x}}[R({\bm{x}})a_{j}q_{ij}\sigma({\bm{w}}_{i}^{*\top}{\bm{x}})]$
$\displaystyle+2\sum_{i\in[m_{*}]}\sum_{j\in{\mathcal{T}}_{i}}\mathbb{E}_{\bm{x}}[R({\bm{x}})a_{j}q_{ij}{\bm{w}}_{i}^{*\top}{\bm{x}}(\sigma^{\prime}({\bm{w}}_{i}^{*\top}{\bm{x}})-\sigma^{\prime}({\bm{w}}_{i}^{\top}{\bm{x}}))]$
$\displaystyle+\lambda\sum_{i\in[m]}\left\|{\bm{w}}_{j}\right\|_{2}^{2}-\lambda\sum_{i\in[m_{*}]}\sum_{j\in{\mathcal{T}}_{i}}q_{ij}{\bm{w}}_{j}^{\top}{\bm{w}}_{i}^{*}$
$\displaystyle\stackrel{{\scriptstyle(\text{b})}}{{=}}$ $\displaystyle
2\left\|R\right\|_{2}^{2}+\lambda\left\|{\bm{W}}\right\|_{F}^{2}-\lambda\sum_{i\in[m_{*}]}\sum_{j\in{\mathcal{T}}_{i}}q_{ij}{\bm{w}}_{j}^{\top}{\bm{w}}_{i}^{*}$
$\displaystyle+2\sum_{i\in[m_{*}]}\sum_{j\in{\mathcal{T}}_{i}}\mathbb{E}_{\bm{x}}[R({\bm{x}})a_{j}q_{ij}{\bm{w}}_{i}^{*\top}{\bm{x}}(\sigma^{\prime}({\bm{w}}_{i}^{*\top}{\bm{x}})-\sigma^{\prime}({\bm{w}}_{j}^{\top}{\bm{x}}))]$
$\displaystyle\stackrel{{\scriptstyle(\text{c})}}{{\geq}}$ $\displaystyle
L_{\lambda}(\mu_{\lambda}^{*})+\zeta+\frac{\lambda}{2}(\left\|{\bm{W}}\right\|_{F}^{2}-\left\|{\bm{a}}\right\|_{2}^{2})-\lambda\sum_{i\in[m_{*}]}\sum_{j\in{\mathcal{T}}_{i}}q_{ij}\left\|{\bm{w}}_{j}\right\|_{2}$
$\displaystyle+2\sum_{i\in[m_{*}]}\sum_{j\in{\mathcal{T}}_{i}}\mathbb{E}_{\bm{x}}[R({\bm{x}})a_{j}q_{ij}{\bm{w}}_{i}^{*\top}{\bm{x}}(\sigma^{\prime}({\bm{w}}_{i}^{*\top}{\bm{x}})-\sigma^{\prime}({\bm{w}}_{j}^{\top}{\bm{x}}))],$
(12)

where (a) we plug in the gradient expression and add and minus the term
$2\sum_{i\in[m_{*}]}\sum_{j\in{\mathcal{T}}_{i}}\mathbb{E}_{\bm{x}}[R({\bm{x}})a_{j}q_{ij}\sigma({\bm{w}}_{i}^{*\top}{\bm{x}})]$;
(b) rearranging the terms; (c) using
$L_{\lambda}({\bm{\theta}})=\left\|R\right\|_{2}^{2}+(\lambda/2)\left\|{\bm{W}}\right\|_{F}^{2}+(\lambda/2)\left\|{\bm{a}}\right\|_{2}^{2}=L_{\lambda}(\mu_{\lambda}^{*})+\zeta$.

For the first line on RHS of (H.3), we have

$\displaystyle
L_{\lambda}(\mu_{\lambda}^{*})+\zeta+\frac{\lambda}{2}(\left\|{\bm{W}}\right\|_{F}^{2}-\left\|{\bm{a}}\right\|_{2}^{2})-\lambda\sum_{i\in[m_{*}]}\sum_{j\in{\mathcal{T}}_{i}}q_{ij}\left\|{\bm{w}}_{j}\right\|_{2}$
$\displaystyle\stackrel{{\scriptstyle(\text{a})}}{{\geq}}$
$\displaystyle\zeta/2+L(\mu_{\lambda}^{*})+\lambda|\mu_{\lambda}^{*}|-\lambda\sum_{i\in[m_{*}]}\sum_{j\in{\mathcal{T}}_{i}}q_{ij}\left\|{\bm{w}}_{j}\right\|_{2}$
$\displaystyle\stackrel{{\scriptstyle(\text{b})}}{{\geq}}$
$\displaystyle\zeta/2+\lambda|\mu_{\lambda}^{*}|-\lambda\left\|{\bm{a}}_{*}\right\|_{1}+\lambda\sum_{i\in[m_{*}]}\sum_{j\in{\mathcal{T}}_{i}}q_{ij}(|a_{j}|-\left\|{\bm{w}}_{j}\right\|_{2})$
$\displaystyle\stackrel{{\scriptstyle(\text{c})}}{{\geq}}$
$\displaystyle\zeta/2-O_{*}(\lambda^{2})-\lambda\left(\sum_{i\in[m_{*}]}\sum_{j\in{\mathcal{T}}_{i}}q_{ij}^{2}\right)^{1/2}\left(\sum_{i\in[m]}(|a_{j}|-\left\|{\bm{w}}_{j}\right\|_{2})^{2}\right)^{1/2}\stackrel{{\scriptstyle(\text{d})}}{{\geq}}\zeta/4,$

where (a) due to assumption that norms are balanced; (b) we ignore
$L(\mu_{\lambda}^{*})$ and add and minus
$\lambda\left\|{\bm{a}}_{*}\right\|_{1}$; (c) due to Lemma F.3; (d) due to
assumption that norms are balanced and the choice of $q_{ij}$.

In the following, we will lower bound the last term of (H.3) to show it is no
smaller than $-\zeta/8$ so that we get the desired lower bound. Recall the
residual decomposition (8) that
$R({\bm{x}})=R_{1}({\bm{x}})+R_{2}({\bm{x}})+R_{3}({\bm{x}})$, we have

$\displaystyle\sum_{i\in[m_{*}]}\sum_{j\in{\mathcal{T}}_{i}}\mathbb{E}_{\bm{x}}[R({\bm{x}})a_{j}q_{ij}{\bm{w}}_{i}^{*\top}{\bm{x}}(\sigma^{\prime}({\bm{w}}_{j}^{\top}{\bm{x}})-\sigma^{\prime}({\bm{w}}_{i}^{*\top}{\bm{x}}))]$
$\displaystyle=$
$\displaystyle\underbrace{\sum_{i\in[m_{*}]}\sum_{j\in{\mathcal{T}}_{i}}\mathbb{E}_{\bm{x}}[R_{1}({\bm{x}})a_{j}q_{ij}{\bm{w}}_{i}^{*\top}{\bm{x}}(\sigma^{\prime}({\bm{w}}_{i}^{*\top}{\bm{x}})-\sigma^{\prime}({\bm{w}}_{j}^{\top}{\bm{x}}))]}_{(I)}$
$\displaystyle+\underbrace{\sum_{i\in[m_{*}]}\sum_{j\in{\mathcal{T}}_{i}}\mathbb{E}_{\bm{x}}[R_{2}({\bm{x}})a_{j}q_{ij}{\bm{w}}_{i}^{*\top}{\bm{x}}(\sigma^{\prime}({\bm{w}}_{i}^{*\top}{\bm{x}})-\sigma^{\prime}({\bm{w}}_{j}^{\top}{\bm{x}}))]}_{(II)}$
$\displaystyle+\underbrace{\sum_{i\in[m_{*}]}\sum_{j\in{\mathcal{T}}_{i}}\mathbb{E}_{\bm{x}}[R_{3}({\bm{x}})a_{j}q_{ij}{\bm{w}}_{i}^{*\top}{\bm{x}}(\sigma^{\prime}({\bm{w}}_{i}^{*\top}{\bm{x}})-\sigma^{\prime}({\bm{w}}_{j}^{\top}{\bm{x}}))]}_{(III)}$

##### Bound (I)

For (I), recall
$R_{1}({\bm{x}})=(1/2)\sum_{i\in[m_{*}]}{\bm{v}}_{i}^{\top}{\bm{x}}\operatorname{sign}({\bm{w}}_{i}^{*\top}{\bm{x}})$,
where
${\bm{v}}_{i}=\sum_{j\in{\mathcal{T}}_{i}}a_{j}{\bm{w}}_{j}-{\bm{w}}_{i}^{*}$
is the difference between average neuron and corresponding ground-truth and
$(\sum_{i\in[m_{*}]}\left\|{\bm{v}}_{i}\right\|_{2}^{2})^{1/2}=O_{*}((\zeta/\lambda)^{3/4})$
from Lemma F.10 and Lemma F.11. We have

$\displaystyle\sum_{i\in[m_{*}]}\sum_{j\in{\mathcal{T}}_{i}}\mathbb{E}_{\bm{x}}[R_{1}({\bm{x}})a_{j}q_{ij}{\bm{w}}_{i}^{*\top}{\bm{x}}(\sigma^{\prime}({\bm{w}}_{i}^{*\top}{\bm{x}})-\sigma^{\prime}({\bm{w}}_{j}^{\top}{\bm{x}}))]$
$\displaystyle\stackrel{{\scriptstyle(\text{a})}}{{\geq}}$
$\displaystyle-\frac{1}{2}\sum_{i\in[m_{*}]}\sum_{j\in{\mathcal{T}}_{i}}\sum_{k\in[m_{*}]}\mathbb{E}_{\bm{x}}[|{\bm{v}}_{k}^{\top}{\bm{x}}||a_{j}q_{ij}||{\bm{w}}_{i}^{*\top}{\bm{x}}|\mathbbm{1}_{\operatorname{sign}({\bm{w}}_{j}^{\top}{\bm{x}})\neq\operatorname{sign}({\bm{w}}_{i}^{*\top}{\bm{x}})}]$
$\displaystyle\stackrel{{\scriptstyle(\text{b})}}{{=}}$
$\displaystyle-\frac{1}{2}\sum_{i\in[m_{*}]}\sum_{j\in{\mathcal{T}}_{i}}\sum_{k\in[m_{*}]}|a_{j}q_{ij}|\left\|{\bm{v}}_{k}\right\|_{2}\mathbb{E}_{\widetilde{{\bm{x}}}}[|\overline{{\bm{v}}}_{k}^{\top}\widetilde{{\bm{x}}}||{\bm{w}}_{i}^{*\top}\widetilde{{\bm{x}}}|\mathbbm{1}_{\operatorname{sign}({\bm{w}}_{j}^{\top}\widetilde{{\bm{x}}})\neq\operatorname{sign}({\bm{w}}_{i}^{*\top}\widetilde{{\bm{x}}})}]$
$\displaystyle\stackrel{{\scriptstyle(\text{c})}}{{\geq}}$
$\displaystyle-\frac{1}{2}\sum_{i\in[m_{*}]}\sum_{j\in{\mathcal{T}}_{i}}\sum_{k\in[m_{*}]}|a_{j}q_{ij}|\left\|{\bm{v}}_{k}\right\|_{2}\delta_{j}\mathbb{E}_{\widetilde{{\bm{x}}}}[\left\|\widetilde{{\bm{x}}}\right\|_{2}^{2}\mathbbm{1}_{\operatorname{sign}({\bm{w}}_{j}^{\top}\widetilde{{\bm{x}}})\neq\operatorname{sign}({\bm{w}}_{i}^{*\top}\widetilde{{\bm{x}}})}]$
$\displaystyle\stackrel{{\scriptstyle(\text{d})}}{{\geq}}$
$\displaystyle-\frac{1}{2}\sum_{i\in[m_{*}]}\sum_{j\in{\mathcal{T}}_{i}}\sum_{k\in[m_{*}]}|a_{j}q_{ij}|\left\|{\bm{v}}_{k}\right\|_{2}\Theta(\delta_{j}^{2})$
$\displaystyle\stackrel{{\scriptstyle(\text{e})}}{{\geq}}$
$\displaystyle-\Theta_{*}((\zeta/\lambda)^{3/4}\delta_{close}^{2})\sum_{i\in[m_{*}]}\sum_{j\in{\mathcal{T}}_{i}}|a_{j}q_{ij}|=-\Theta_{*}((\zeta/\lambda)^{3/4}\delta_{close}^{2}),$

where in (a) we plug in the definition of $R_{1}$ and using the fact that
${\bm{w}}_{i}^{*\top}{\bm{x}}(\sigma^{\prime}({\bm{w}}_{i}^{*\top}{\bm{x}})-\sigma^{\prime}({\bm{w}}_{j}^{\top}{\bm{x}}))=|{\bm{w}}_{i}^{*\top}{\bm{x}}|\mathbbm{1}_{\operatorname{sign}({\bm{w}}_{j}^{\top}{\bm{x}})\neq\operatorname{sign}({\bm{w}}_{i}^{*\top}{\bm{x}})}$;
(b) $\widetilde{{\bm{x}}}$ is a 3-dimensional Gaussian since the expectation
only depends on ${\bm{v}}_{k},{\bm{w}}_{i}^{*},{\bm{w}}_{j}$; (c)
$|{\bm{w}}_{i}^{*\top}\widetilde{{\bm{x}}}|\leq\delta_{j}\left\|\widetilde{{\bm{x}}}\right\|_{2}$
when
$\operatorname{sign}({\bm{w}}_{j}^{\top}\widetilde{{\bm{x}}})\neq\operatorname{sign}({\bm{w}}_{i}^{*\top}\widetilde{{\bm{x}}})$;
(d) a direct calculation bound as Lemma H.2; (e) definition of $q_{ij}$.

##### Bound (II)

For (II), recall

$R_{2}({\bm{x}})=\frac{1}{2}\sum_{i\in[m_{*}]}\sum_{j\in{\mathcal{T}}_{i}}a_{j}{\bm{w}}_{j}^{\top}{\bm{x}}(\operatorname{sign}({\bm{w}}_{j}^{\top}{\bm{x}})-\operatorname{sign}({\bm{w}}_{i}^{*\top}{\bm{x}}))=\sum_{i\in[m_{*}]}\sum_{j\in{\mathcal{T}}_{i}}a_{j}|{\bm{w}}_{j}^{\top}{\bm{x}}|\mathbbm{1}_{\operatorname{sign}({\bm{w}}_{j}^{\top}{\bm{x}})\neq\operatorname{sign}({\bm{w}}_{i}^{*\top}{\bm{x}}))}.$

For each term in (II) with $j\in{\mathcal{T}}_{i}$, we can split it into two
terms that corresponding to ${\mathcal{T}}_{i}$ and other
${\mathcal{T}}_{k}$’s.

$\displaystyle\mathbb{E}_{\bm{x}}[R_{2}({\bm{x}})a_{j}q_{ij}{\bm{w}}_{i}^{*\top}{\bm{x}}(\sigma^{\prime}({\bm{w}}_{i}^{*\top}{\bm{x}})-\sigma^{\prime}({\bm{w}}_{j}^{\top}{\bm{x}}))]$
$\displaystyle=$
$\displaystyle\sum_{k\in[m_{*}]}\sum_{\ell\in{\mathcal{T}}_{k}}\mathbb{E}_{\bm{x}}[a_{\ell}|{\bm{w}}_{\ell}^{\top}{\bm{x}}|\mathbbm{1}_{\operatorname{sign}({\bm{w}}_{\ell}^{\top}{\bm{x}})\neq\operatorname{sign}({\bm{w}}_{k}^{*\top}{\bm{x}})}\cdot
a_{j}q_{ij}{\bm{w}}_{i}^{*\top}{\bm{x}}(\sigma^{\prime}({\bm{w}}_{i}^{*\top}{\bm{x}})-\sigma^{\prime}({\bm{w}}_{j}^{\top}{\bm{x}})]$
$\displaystyle=$
$\displaystyle\sum_{k\in[m_{*}]}\sum_{\ell\in{\mathcal{T}}_{k}}a_{\ell}a_{j}q_{ij}\mathbb{E}_{\bm{x}}[|{\bm{w}}_{\ell}^{\top}{\bm{x}}|\mathbbm{1}_{\operatorname{sign}({\bm{w}}_{\ell}^{\top}{\bm{x}})\neq\operatorname{sign}({\bm{w}}_{k}^{*\top}{\bm{x}})}\cdot|{\bm{w}}_{i}^{*\top}{\bm{x}}|\mathbbm{1}_{\operatorname{sign}({\bm{w}}_{i}^{*\top}{\bm{x}})\neq\operatorname{sign}({\bm{w}}_{j}^{\top}{\bm{x}})}]$
$\displaystyle=$
$\displaystyle\underbrace{\sum_{\ell\in{\mathcal{T}}_{i}}a_{\ell}a_{j}q_{ij}\mathbb{E}_{\bm{x}}[|{\bm{w}}_{\ell}^{\top}{\bm{x}}||{\bm{w}}_{i}^{*\top}{\bm{x}}|\mathbbm{1}_{\operatorname{sign}({\bm{w}}_{\ell}^{\top}{\bm{x}})\neq\operatorname{sign}({\bm{w}}_{i}^{*\top}{\bm{x}})}\cdot\mathbbm{1}_{\operatorname{sign}({\bm{w}}_{i}^{*\top}{\bm{x}})\neq\operatorname{sign}({\bm{w}}_{j}^{\top}{\bm{x}})}]}_{(II.i)}$
$\displaystyle+\underbrace{\sum_{k\neq
i}\sum_{\ell\in{\mathcal{T}}_{k}}a_{\ell}a_{j}q_{ij}\mathbb{E}_{\bm{x}}[|{\bm{w}}_{\ell}^{\top}{\bm{x}}||{\bm{w}}_{i}^{*\top}{\bm{x}}|\mathbbm{1}_{\operatorname{sign}({\bm{w}}_{\ell}^{\top}{\bm{x}})\neq\operatorname{sign}({\bm{w}}_{k}^{*\top}{\bm{x}})}\cdot\mathbbm{1}_{\operatorname{sign}({\bm{w}}_{i}^{*\top}{\bm{x}})\neq\operatorname{sign}({\bm{w}}_{j}^{\top}{\bm{x}})}]}_{(II.ii)}.$
(13)

For (II.i), we further split neurons into
${\mathcal{T}}_{i}(\delta_{\operatorname{sign}})$ and others:

$\displaystyle(II.i)=$
$\displaystyle\sum_{\ell\in{\mathcal{T}}_{i}(\delta_{\operatorname{sign}})}a_{\ell}a_{j}q_{ij}\mathbb{E}_{\bm{x}}[|{\bm{w}}_{\ell}^{\top}{\bm{x}}||{\bm{w}}_{i}^{*\top}{\bm{x}}|\mathbbm{1}_{\operatorname{sign}({\bm{w}}_{\ell}^{\top}{\bm{x}})\neq\operatorname{sign}({\bm{w}}_{i}^{*\top}{\bm{x}})}\cdot\mathbbm{1}_{\operatorname{sign}({\bm{w}}_{i}^{*\top}{\bm{x}})\neq\operatorname{sign}({\bm{w}}_{j}^{\top}{\bm{x}})}]$
$\displaystyle+\sum_{\ell\in{\mathcal{T}}_{i}\setminus{\mathcal{T}}_{i}(\delta_{\operatorname{sign}})}a_{\ell}a_{j}q_{ij}\mathbb{E}_{\bm{x}}[|{\bm{w}}_{\ell}^{\top}{\bm{x}}||{\bm{w}}_{i}^{*\top}{\bm{x}}|\mathbbm{1}_{\operatorname{sign}({\bm{w}}_{\ell}^{\top}{\bm{x}})\neq\operatorname{sign}({\bm{w}}_{i}^{*\top}{\bm{x}})}\cdot\mathbbm{1}_{\operatorname{sign}({\bm{w}}_{i}^{*\top}{\bm{x}})\neq\operatorname{sign}({\bm{w}}_{j}^{\top}{\bm{x}})}]$
(14)

Consider the first line of (H.3), from the choice of $q_{ij}$ we know
$a_{j}q_{ij}a_{i}^{*}\geq 0$. For
$\ell\in{\mathcal{T}}_{i,+}(\delta_{\operatorname{sign}})$, we know
$\operatorname{sign}(a_{\ell})=\operatorname{sign}(a_{i}^{*})$, which implies
$a_{\ell}a_{j}q_{ij}\geq 0$ for these terms. We thus only need to deal with
neurons in $T_{i,-}(\delta_{\operatorname{sign}})$, we have the first line is
bounded as

$\displaystyle\sum_{\ell\in{\mathcal{T}}_{i}(\delta_{\operatorname{sign}})}a_{\ell}a_{j}q_{ij}\mathbb{E}_{\bm{x}}[|{\bm{w}}_{\ell}^{\top}{\bm{x}}||{\bm{w}}_{i}^{*\top}{\bm{x}}|\mathbbm{1}_{\operatorname{sign}({\bm{w}}_{\ell}^{\top}{\bm{x}})\neq\operatorname{sign}({\bm{w}}_{i}^{*\top}{\bm{x}})}\cdot\mathbbm{1}_{\operatorname{sign}({\bm{w}}_{i}^{*\top}{\bm{x}})\neq\operatorname{sign}({\bm{w}}_{j}^{\top}{\bm{x}})}]$
$\displaystyle\geq$
$\displaystyle\sum_{\ell\in{\mathcal{T}}_{i,-}(\delta_{\operatorname{sign}})}a_{\ell}a_{j}q_{ij}\mathbb{E}_{\bm{x}}[|{\bm{w}}_{\ell}^{\top}{\bm{x}}||{\bm{w}}_{i}^{*\top}{\bm{x}}|\mathbbm{1}_{\operatorname{sign}({\bm{w}}_{\ell}^{\top}{\bm{x}})\neq\operatorname{sign}({\bm{w}}_{i}^{*\top}{\bm{x}})}\cdot\mathbbm{1}_{\operatorname{sign}({\bm{w}}_{i}^{*\top}{\bm{x}})\neq\operatorname{sign}({\bm{w}}_{j}^{\top}{\bm{x}})}]$
$\displaystyle\stackrel{{\scriptstyle(\text{a})}}{{\geq}}$
$\displaystyle-|a_{j}q_{ij}|\sum_{\ell\in{\mathcal{T}}_{i,-}(\delta_{\operatorname{sign}})}|a_{\ell}|\left\|{\bm{w}}_{\ell}\right\|_{2}\mathbb{E}_{\bm{x}}[|\overline{{\bm{w}}}_{\ell}^{\top}\widetilde{{\bm{x}}}||{\bm{w}}_{i}^{*\top}\widetilde{{\bm{x}}}|\mathbbm{1}_{\operatorname{sign}({\bm{w}}_{\ell}^{\top}\widetilde{{\bm{x}}})\neq\operatorname{sign}({\bm{w}}_{i}^{*\top}\widetilde{{\bm{x}}})}\cdot\mathbbm{1}_{\operatorname{sign}({\bm{w}}_{i}^{*\top}\widetilde{{\bm{x}}})\neq\operatorname{sign}({\bm{w}}_{j}^{\top}\widetilde{{\bm{x}}})}]$
$\displaystyle\stackrel{{\scriptstyle(\text{b})}}{{\geq}}$
$\displaystyle-|a_{j}q_{ij}|\sum_{\ell\in{\mathcal{T}}_{i,-}(\delta_{\operatorname{sign}})}|a_{\ell}|\left\|{\bm{w}}_{\ell}\right\|_{2}\delta_{\ell}\delta_{j}\mathbb{E}_{\bm{x}}[\left\|\widetilde{{\bm{x}}}\right\|_{2}^{2}\mathbbm{1}_{\operatorname{sign}({\bm{w}}_{\ell}^{\top}\widetilde{{\bm{x}}})\neq\operatorname{sign}({\bm{w}}_{i}^{*\top}\widetilde{{\bm{x}}})}\cdot\mathbbm{1}_{\operatorname{sign}({\bm{w}}_{i}^{*\top}\widetilde{{\bm{x}}})\neq\operatorname{sign}({\bm{w}}_{j}^{\top}\widetilde{{\bm{x}}})}]$
$\displaystyle\stackrel{{\scriptstyle(\text{c})}}{{\geq}}$
$\displaystyle-|a_{j}q_{ij}|\sum_{\ell\in{\mathcal{T}}_{i,-}(\delta_{\operatorname{sign}})}|a_{\ell}|\left\|{\bm{w}}_{\ell}\right\|_{2}O(\delta_{\ell}\delta_{j}^{2})$
$\displaystyle\stackrel{{\scriptstyle(\text{d})}}{{\geq}}$
$\displaystyle-|a_{j}q_{ij}|O(\tau\delta_{\operatorname{sign}}\delta_{close}^{2}),$

where (a) $\widetilde{{\bm{x}}}$ is a 3-dimensional Gaussian since the
expectation only depends on ${\bm{w}}_{\ell},{\bm{w}}_{j},{\bm{w}}_{i}^{*}$;
(b)
$|\overline{{\bm{w}}}_{\ell}^{\top}\widetilde{{\bm{x}}}|\leq\delta_{\ell}\left\|\widetilde{{\bm{x}}}\right\|_{2}$
when
$\operatorname{sign}({\bm{w}}_{i}^{*\top}\widetilde{{\bm{x}}})\neq\operatorname{sign}({\bm{w}}_{\ell}^{\top}\widetilde{{\bm{x}}})$
and
$|{\bm{w}}_{i}^{*\top}\widetilde{{\bm{x}}}|\leq\delta_{j}\left\|\widetilde{{\bm{x}}}\right\|_{2}$
when
$\operatorname{sign}({\bm{w}}_{i}^{*\top}\widetilde{{\bm{x}}})\neq\operatorname{sign}({\bm{w}}_{j}^{\top}\widetilde{{\bm{x}}})$;
(c) a direct calculation as in Lemma H.2; (d) assumption that norm
cancellation is small.

For the second term of (H.3), similar as above, we have

$\displaystyle
2\sum_{\ell\in{\mathcal{T}}_{i}\setminus{\mathcal{T}}_{i}(\delta_{\operatorname{sign}})}a_{\ell}a_{j}q_{ij}\mathbb{E}_{\bm{x}}[|{\bm{w}}_{\ell}^{\top}{\bm{x}}||{\bm{w}}_{i}^{*\top}{\bm{x}}|\mathbbm{1}_{\operatorname{sign}({\bm{w}}_{\ell}^{\top}{\bm{x}})\neq\operatorname{sign}({\bm{w}}_{i}^{*\top}{\bm{x}})}\cdot\mathbbm{1}_{\operatorname{sign}({\bm{w}}_{i}^{*\top}{\bm{x}})\neq\operatorname{sign}({\bm{w}}_{j}^{\top}{\bm{x}})}]$
$\displaystyle\stackrel{{\scriptstyle(\text{a})}}{{\geq}}$
$\displaystyle-2|a_{j}q_{ij}|\sum_{\ell\in{\mathcal{T}}_{i}\setminus{\mathcal{T}}_{i}(\delta_{\operatorname{sign}})}|a_{\ell}|\left\|{\bm{w}}_{\ell}\right\|_{2}\mathbb{E}_{\widetilde{{\bm{x}}}}[|\overline{{\bm{w}}}_{\ell}^{\top}\widetilde{{\bm{x}}}||{\bm{w}}_{i}^{*\top}\widetilde{{\bm{x}}}|\mathbbm{1}_{\operatorname{sign}({\bm{w}}_{\ell}^{\top}\widetilde{{\bm{x}}})\neq\operatorname{sign}({\bm{w}}_{i}^{*\top}\widetilde{{\bm{x}}})}\cdot\mathbbm{1}_{\operatorname{sign}({\bm{w}}_{i}^{*\top}\widetilde{{\bm{x}}})\neq\operatorname{sign}({\bm{w}}_{j}^{\top}\widetilde{{\bm{x}}})}]$
$\displaystyle\stackrel{{\scriptstyle(\text{b})}}{{\geq}}$
$\displaystyle-2|a_{j}q_{ij}|\sum_{\ell\in{\mathcal{T}}_{i}\setminus{\mathcal{T}}_{i}(\delta_{\operatorname{sign}})}|a_{\ell}|\left\|{\bm{w}}_{\ell}\right\|_{2}\delta_{\ell}\delta_{j}\mathbb{E}_{\widetilde{{\bm{x}}}}[\left\|\widetilde{{\bm{x}}}\right\|_{2}^{2}\mathbbm{1}_{\operatorname{sign}({\bm{w}}_{i}^{*\top}\widetilde{{\bm{x}}})\neq\operatorname{sign}({\bm{w}}_{j}^{\top}\widetilde{{\bm{x}}})}]$
$\displaystyle\stackrel{{\scriptstyle(\text{c})}}{{\geq}}$
$\displaystyle-2|a_{j}q_{ij}|O(\delta_{j}^{2})\sum_{\ell\in{\mathcal{T}}_{i}\setminus{\mathcal{T}}_{i}(\delta_{\operatorname{sign}})}|a_{\ell}|\left\|{\bm{w}}_{\ell}\right\|_{2}\delta_{\ell}$
$\displaystyle\stackrel{{\scriptstyle(\text{d})}}{{\geq}}$
$\displaystyle-2|a_{j}q_{ij}|O_{*}(\delta_{close}^{2}\zeta\lambda^{-1}\delta_{\operatorname{sign}}^{-1}),$

where (a) $\widetilde{{\bm{x}}}$ is 3-dimensional Gaussian vector since the
expectation only depends on ${\bm{w}}_{\ell},{\bm{w}}_{j},{\bm{w}}_{i}^{*}$;
(b)
$|\overline{{\bm{w}}}_{\ell}^{\top}\widetilde{{\bm{x}}}|\leq\delta_{\ell}\left\|\widetilde{{\bm{x}}}\right\|_{2}$
when
$\operatorname{sign}({\bm{w}}_{i}^{*\top}\widetilde{{\bm{x}}})\neq\operatorname{sign}({\bm{w}}_{\ell}^{\top}\widetilde{{\bm{x}}})$
and
$|{\bm{w}}_{i}^{*\top}\widetilde{{\bm{x}}}|\leq\delta_{j}\left\|\widetilde{{\bm{x}}}\right\|_{2}$
when
$\operatorname{sign}({\bm{w}}_{i}^{*\top}\widetilde{{\bm{x}}})\neq\operatorname{sign}({\bm{w}}_{j}^{\top}\widetilde{{\bm{x}}})$;
(c) a direct calculation as in Lemma H.2; (d) choice of $q_{ij}$ and Lemma F.5
and Lemma F.11 that far-away neurons are small.

Thus, for (II.i) we have

$\displaystyle(II.i)\geq-2|a_{j}q_{ij}|O_{*}(\tau\delta_{\operatorname{sign}}\delta_{close}^{2}+\delta_{close}^{2}\zeta\lambda^{-1}\delta_{\operatorname{sign}}^{-1}).$

For (II.ii), we have

$\displaystyle|(II.ii)|\leq$ $\displaystyle 2\sum_{k\neq
i}\sum_{\ell\in{\mathcal{T}}_{k}}|a_{\ell}||a_{j}q_{ij}|\mathbb{E}_{\bm{x}}[|{\bm{w}}_{\ell}^{\top}{\bm{x}}||{\bm{w}}_{i}^{*\top}{\bm{x}}|\mathbbm{1}_{\operatorname{sign}({\bm{w}}_{\ell}^{\top}{\bm{x}})\neq\operatorname{sign}({\bm{w}}_{k}^{*\top}{\bm{x}})}\cdot\mathbbm{1}_{\operatorname{sign}({\bm{w}}_{i}^{*\top}{\bm{x}})\neq\operatorname{sign}({\bm{w}}_{j}^{\top}{\bm{x}})}]$
$\displaystyle\stackrel{{\scriptstyle(\text{a})}}{{\leq}}$ $\displaystyle
2\sum_{k\neq
i}\sum_{\ell\in{\mathcal{T}}_{k}}|a_{\ell}||a_{j}q_{ij}|\left\|{\bm{w}}_{\ell}\right\|_{2}\delta_{\ell}\delta_{j}\mathbb{E}_{\widetilde{{\bm{x}}}}[\left\|\widetilde{{\bm{x}}}\right\|_{2}^{2}\mathbbm{1}_{\operatorname{sign}({\bm{w}}_{\ell}^{\top}\widetilde{{\bm{x}}})\neq\operatorname{sign}({\bm{w}}_{k}^{*\top}\widetilde{{\bm{x}}})}\cdot\mathbbm{1}_{\operatorname{sign}({\bm{w}}_{i}^{*\top}\widetilde{{\bm{x}}})\neq\operatorname{sign}({\bm{w}}_{j}^{\top}\widetilde{{\bm{x}}})}]$
$\displaystyle\stackrel{{\scriptstyle(\text{b})}}{{\leq}}$ $\displaystyle
2\sum_{k\neq
i}\sum_{\ell\in{\mathcal{T}}_{k}}|a_{\ell}||a_{j}q_{ij}|\left\|{\bm{w}}_{\ell}\right\|_{2}\delta_{\ell}\delta_{j}\mathbb{E}_{\widetilde{{\bm{x}}}}[\left\|\widetilde{{\bm{x}}}\right\|_{2}^{2}\mathbbm{1}_{|{\bm{w}}_{k}^{*\top}\widetilde{{\bm{x}}}|\leq\delta_{\ell}\left\|\widetilde{{\bm{x}}}\right\|_{2}}\cdot\mathbbm{1}_{|{\bm{w}}_{i}^{*\top}\widetilde{{\bm{x}}}|\leq\delta_{j}\left\|\widetilde{{\bm{x}}}\right\|_{2}}]$
$\displaystyle\stackrel{{\scriptstyle(\text{c})}}{{\leq}}$ $\displaystyle
2|a_{j}q_{ij}|\delta_{j}\sum_{k\neq
i}\sum_{\ell\in{\mathcal{T}}_{k}}|a_{\ell}|\left\|{\bm{w}}_{\ell}\right\|_{2}\delta_{\ell}\cdot
O(\delta_{\ell}\delta_{j}/\Delta)$
$\displaystyle\stackrel{{\scriptstyle(\text{d})}}{{=}}$ $\displaystyle
2|a_{j}q_{ij}|O_{*}(\delta_{close}^{2}\zeta\lambda^{-1}\Delta^{-1}),$

where (a)(b) $\widetilde{{\bm{x}}}$ is a 4-dimensional Gaussian vector,
$|\overline{{\bm{w}}}_{\ell}^{\top}\widetilde{{\bm{x}}}|\leq\delta_{\ell}\left\|\widetilde{{\bm{x}}}\right\|_{2}$
when
$\operatorname{sign}({\bm{w}}_{i}^{*\top}\widetilde{{\bm{x}}})\neq\operatorname{sign}({\bm{w}}_{\ell}^{\top}\widetilde{{\bm{x}}})$
and
$|{\bm{w}}_{i}^{*\top}\widetilde{{\bm{x}}}|\leq\delta_{j}\left\|\widetilde{{\bm{x}}}\right\|_{2}$
when
$\operatorname{sign}({\bm{w}}_{i}^{*\top}\widetilde{{\bm{x}}})\neq\operatorname{sign}({\bm{w}}_{j}^{\top}\widetilde{{\bm{x}}})$;
(c) by Lemma H.1; (d) choice of $q_{ij}$ and Lemma F.5 and Lemma F.11 that
far-away neurons are small.

Combine (II.i) (II.ii), we have for (H.3)

$\displaystyle\mathbb{E}_{\bm{x}}[R_{2}({\bm{x}})a_{j}q_{ij}{\bm{w}}_{i}^{*\top}{\bm{x}}(\sigma^{\prime}({\bm{w}}_{i}^{*\top}{\bm{x}})-\sigma^{\prime}({\bm{w}}_{j}^{\top}{\bm{x}}))]\geq-2|a_{j}q_{ij}|O(\tau\delta_{\operatorname{sign}}\delta_{close}^{2}+\delta_{close}^{2}\zeta\lambda^{-1}\delta_{\operatorname{sign}}^{-1}).$

This further gives the lower bound on (II):

$\displaystyle\sum_{i\in[m_{*}]}\sum_{j\in{\mathcal{T}}_{i}}\mathbb{E}_{\bm{x}}[R_{2}({\bm{x}})a_{j}q_{ij}{\bm{w}}_{i}^{*\top}{\bm{x}}(\sigma^{\prime}({\bm{w}}_{i}^{*\top}{\bm{x}})-\sigma^{\prime}({\bm{w}}_{j}^{\top}{\bm{x}}))]$
$\displaystyle\geq$
$\displaystyle-2\sum_{i\in[m_{*}]}\sum_{j\in{\mathcal{T}}_{i}}|a_{j}q_{ij}|O(\tau\delta_{\operatorname{sign}}\delta_{close}^{2}+\delta_{close}^{2}\zeta\lambda^{-1}\delta_{\operatorname{sign}}^{-1})$
$\displaystyle=$ $\displaystyle-
O_{*}(\tau\delta_{\operatorname{sign}}\delta_{close}^{2}+\delta_{close}^{2}\zeta\lambda^{-1}\delta_{\operatorname{sign}}^{-1})$

##### Bound (III)

For (III), recall
$R_{3}({\bm{x}})=\frac{1}{\sqrt{2\pi}}\left(\sum_{i\in[m_{*}]}a_{i}^{*}\left\|{\bm{w}}_{i}^{*}\right\|_{2}-\sum_{i\in[m]}a_{i}\left\|{\bm{w}}_{i}\right\|_{2}\right)+\alpha-\hat{\alpha}+({\bm{\beta}}-\hat{{\bm{\beta}}})^{\top}{\bm{x}}$.
We have

$\displaystyle\sum_{i\in[m_{*}]}\sum_{j\in{\mathcal{T}}_{i}}\mathbb{E}_{\bm{x}}[R_{3}({\bm{x}})a_{j}q_{ij}{\bm{w}}_{i}^{*\top}{\bm{x}}(\sigma^{\prime}({\bm{w}}_{i}^{*\top}{\bm{x}})-\sigma^{\prime}({\bm{w}}_{j}^{\top}{\bm{x}}))]$
$\displaystyle\stackrel{{\scriptstyle(\text{a})}}{{\geq}}$ $\displaystyle-
O_{*}(\zeta/\lambda)\sum_{i\in[m_{*}]}\sum_{j\in{\mathcal{T}}_{i}}|a_{j}q_{ij}|\mathbb{E}_{\bm{x}}[|{\bm{w}}_{i}^{*\top}{\bm{x}}|\mathbbm{1}_{\operatorname{sign}({\bm{w}}_{j}^{\top}{\bm{x}})\neq\operatorname{sign}({\bm{w}}_{i}^{*\top}{\bm{x}})}]$
$\displaystyle-\sum_{i\in[m_{*}]}\sum_{j\in{\mathcal{T}}_{i}}|a_{j}q_{ij}|\mathbb{E}_{\bm{x}}[|({\bm{\beta}}-\hat{{\bm{\beta}}})^{\top}{\bm{x}}||{\bm{w}}_{i}^{*\top}{\bm{x}}|\mathbbm{1}_{\operatorname{sign}({\bm{w}}_{j}^{\top}{\bm{x}})\neq\operatorname{sign}({\bm{w}}_{i}^{*\top}{\bm{x}})}]$
$\displaystyle\stackrel{{\scriptstyle(\text{b})}}{{\geq}}$ $\displaystyle-
O_{*}(\zeta/\lambda)\sum_{i\in[m_{*}]}\sum_{j\in{\mathcal{T}}_{i}}|a_{j}q_{ij}|O(\delta_{j}^{2})$
$\displaystyle-O(\zeta^{1/2})\sum_{i\in[m_{*}]}\sum_{j\in{\mathcal{T}}_{i}}|a_{j}q_{ij}|\delta_{j}\mathbb{E}_{\bm{x}}[\left\|\widetilde{{\bm{x}}}\right\|_{2}^{2}\mathbbm{1}_{\operatorname{sign}({\bm{w}}_{j}^{\top}\widetilde{{\bm{x}}})\neq\operatorname{sign}({\bm{w}}_{i}^{*\top}\widetilde{{\bm{x}}})}]$
$\displaystyle\stackrel{{\scriptstyle(\text{c})}}{{\geq}}$ $\displaystyle-
O_{*}(\zeta/\lambda)\sum_{i\in[m_{*}]}\sum_{j\in{\mathcal{T}}_{i}}|a_{j}q_{ij}|O(\delta_{j}^{2})$
$\displaystyle\stackrel{{\scriptstyle(\text{d})}}{{\geq}}$ $\displaystyle-
O_{*}(\delta_{close}^{2}\zeta/\lambda),$

where (a) plugging in the expression of $R_{3}$ and using Lemma F.9 and Lemma
F.11; (b) using Lemma H.3 and the fact that $\widetilde{{\bm{x}}}$ is a
3-dimensional Gaussian vector and
$|{\bm{w}}_{i}^{*\top}\widetilde{{\bm{x}}}|\leq\delta_{j}\left\|\widetilde{{\bm{x}}}\right\|_{2}$
when
$\operatorname{sign}({\bm{w}}_{i}^{*\top}\widetilde{{\bm{x}}})\neq\operatorname{sign}({\bm{w}}_{j}^{\top}\widetilde{{\bm{x}}})$;
(c) Lemma H.2; (d) choice of $q_{ij}$.

##### Combine all bounds

Combine (I) (II) (III) we now get the last term of (H.3)

$\displaystyle\sum_{i\in[m_{*}]}\sum_{j\in{\mathcal{T}}_{i}}\mathbb{E}_{\bm{x}}[R({\bm{x}})a_{j}q_{ij}{\bm{w}}_{i}^{*\top}{\bm{x}}(\sigma^{\prime}({\bm{w}}_{j}^{\top}{\bm{x}})-\sigma^{\prime}({\bm{w}}_{i}^{*\top}{\bm{x}}))]\geq-
O_{*}((\zeta/\lambda)^{3/4}\delta_{close}^{2}+\tau\delta_{\operatorname{sign}}\delta_{close}^{2}+\delta_{close}^{2}\zeta\lambda^{-1}\delta_{\operatorname{sign}}^{-1})$

From Lemma F.6 we can choose $\delta_{close}=O_{*}(\zeta^{1/3})$ and from
Lemma F.16 we can choose
$\delta_{\operatorname{sign}}=\Theta_{*}(\lambda/\zeta^{1/2})$. Also with
$\tau=O(\zeta^{5/6}/\lambda)$, we finally get

$\displaystyle\sum_{i\in[m_{*}]}\sum_{j\in{\mathcal{T}}_{i}}\mathbb{E}_{\bm{x}}[R({\bm{x}})a_{j}q_{ij}{\bm{w}}_{i}^{*\top}{\bm{x}}(\sigma^{\prime}({\bm{w}}_{j}^{\top}{\bm{x}})-\sigma^{\prime}({\bm{w}}_{i}^{*\top}{\bm{x}}))]\geq\zeta/8,$

as long as
$\zeta=O(\lambda^{9/5}/\operatorname{poly}(r,m_{*},\Delta,\left\|{\bm{a}}_{*}\right\|_{1},a_{\min}))$
with small enough hidden constant.

Thus, we eventually get the lower bound of (H.3)

$\displaystyle(\alpha+\alpha_{*})\nabla_{\alpha}L_{\lambda}+\langle\nabla_{\bm{\beta}}L_{\lambda},{\bm{\beta}}+{\bm{\beta}}_{*}\rangle+\sum_{i\in[m_{*}]}\sum_{j\in{\mathcal{T}}_{i}}\langle\nabla_{{\bm{w}}_{i}}L_{\lambda},{\bm{w}}_{j}-q_{ij}{\bm{w}}_{i}^{*}\rangle\geq\zeta/4-\zeta/8=\zeta/8.$

∎

###  H.4 Technical Lemma

In this section, we collect several technical lemmas that are useful in the
proof.

######  Lemma H.1.

Consider ${\bm{\alpha}},{\bm{\beta}}\in\mathbb{R}^{4}$ with
$\phi=\angle({\bm{\alpha}},{\bm{\beta}})\in[0,\pi]$ and
$\left\|{\bm{\alpha}}\right\|_{2}=\left\|{\bm{\beta}}\right\|_{2}=1$ and
${\bm{x}}\sim N({\bm{0}},{\bm{I}})$. Then, for any
$0<\delta_{1},\delta_{2}\leq\phi$ we have

$\displaystyle\mathbb{E}_{\bm{x}}[\left\|{\bm{x}}\right\|_{2}^{2}\mathbbm{1}_{|{\bm{\alpha}}^{\top}{\bm{x}}|\leq\delta_{1}\left\|{\bm{x}}\right\|_{2},|{\bm{\beta}}^{\top}{\bm{x}}|\leq\delta_{2}\left\|{\bm{x}}\right\|_{2}}]=O(\delta_{1}\delta_{2}/\sin\phi).$

###### Proof.

We first consider the case when at least one of $\delta_{1},\delta_{2}\geq
c\phi$ for a fixed small enough constant. WLOG, suppose $\delta_{2}\geq
c\phi$. In this case, it suffices to show a bound $O(\delta_{1})$. We have

$\displaystyle\mathbb{E}_{\bm{x}}[\left\|{\bm{x}}\right\|_{2}^{2}\mathbbm{1}_{|{\bm{\alpha}}^{\top}{\bm{x}}|\leq\delta_{1}\left\|{\bm{x}}\right\|_{2},|{\bm{\beta}}^{\top}{\bm{x}}|\leq\delta_{2}\left\|{\bm{x}}\right\|_{2}}]\leq\mathbb{E}_{\bm{x}}[\left\|{\bm{x}}\right\|_{2}^{2}\mathbbm{1}_{|{\bm{\alpha}}^{\top}{\bm{x}}|\leq\delta_{1}\left\|{\bm{x}}\right\|_{2}}]=O(\delta_{1}).$

Then, we focus on the case when $\delta_{1},\delta_{2}\leq c\phi$ for a fixed
small enough constant. WLOG, assume ${\bm{\alpha}}=(1,0,0,0)^{\top}$,
${\bm{\beta}}=(\cos\phi,\sin\phi,0,0)$ and $\phi\in[0,\pi/2]$. Then we have

$\displaystyle\mathbb{E}_{\bm{x}}[\left\|{\bm{x}}\right\|_{2}^{2}\mathbbm{1}_{|{\bm{\alpha}}^{\top}{\bm{x}}|\leq\delta_{1}\left\|{\bm{x}}\right\|_{2},|{\bm{\beta}}^{\top}{\bm{x}}|\leq\delta_{2}\left\|{\bm{x}}\right\|_{2}}]$
$\displaystyle=$
$\displaystyle\frac{1}{(2\pi)^{2}}\int_{0}^{\infty}r^{5}e^{-r^{2}/2}\,\mathrm{d}r$
$\displaystyle\int_{0\leq\theta_{1}\leq\pi,|\cos\theta_{1}|\leq\delta_{1}}\sin^{2}\theta_{1}\int_{0\leq\theta_{2}\leq\pi,|\cos\theta_{1}\cos\phi+\sin\theta_{1}\cos\theta_{2}\sin\phi|\leq\delta_{2}}\sin\theta_{2}\,\mathrm{d}\theta_{2}\,\mathrm{d}\theta_{1}\int_{0}^{2\pi}1\,\mathrm{d}\theta_{3}$
$\displaystyle\ =$ $\displaystyle
O(1)\cdot\int_{0\leq\theta_{1}\leq\pi,|\cos\theta_{1}|\leq\delta_{1}}\sin^{2}\theta_{1}\int_{0\leq\theta_{2}\leq\pi,\frac{-\delta_{2}-\cos\theta_{1}\cos\phi}{\sin\theta_{1}\sin\phi}\leq\cos\theta_{2}\leq\frac{\delta_{2}-\cos\theta_{1}\cos\phi}{\sin\theta_{1}\sin\phi}}\sin\theta_{2}\,\mathrm{d}\theta_{2}\,\mathrm{d}\theta_{1}$
$\displaystyle=$
$\displaystyle\int_{0\leq\theta_{1}\leq\pi,|\cos\theta_{1}|\leq\delta_{1}}\sin^{2}\theta_{1}\cdot
O\left(\frac{\delta_{2}}{\sin\theta_{1}\sin\phi}\right)\,\mathrm{d}\theta_{1}$
$\displaystyle=$ $\displaystyle
O\left(\frac{\delta_{1}\delta_{2}}{\sin\phi}\right).$

∎

######  Lemma H.2 (Lemma C.9 in Zhou et al. (2021)).

Consider ${\bm{\alpha}},{\bm{\beta}}\in\mathbb{R}^{3}$ with
$\angle({\bm{\alpha}},{\bm{\beta}})=\phi$ and
${\bm{\alpha}}^{\top}{\bm{\beta}}\geq 0$. We have

$\displaystyle\mathbb{E}_{\bm{x}}[\left\|{\bm{x}}\right\|^{2}\mathbbm{1}_{\operatorname{sign}({\bm{\alpha}}^{\top}{\bm{x}})\neq\operatorname{sign}({\bm{\beta}}^{\top}{\bm{x}})}]=O(\phi).$

######  Lemma H.3.

Consider ${\bm{\alpha}},{\bm{\beta}}\in\mathbb{R}^{d}$ with
$\angle({\bm{\alpha}},{\bm{\beta}})=\phi$,
$\left\|{\bm{\alpha}}\right\|_{2}=\left\|{\bm{\beta}}\right\|_{2}=1$ and
${\bm{\alpha}}^{\top}{\bm{\beta}}\geq 0$. We have

$\displaystyle\mathbb{E}_{\bm{x}}[|{\bm{\alpha}}^{\top}{\bm{x}}|\mathbbm{1}_{\operatorname{sign}({\bm{\alpha}}^{\top}{\bm{x}})\neq\operatorname{sign}({\bm{\beta}}^{\top}{\bm{x}})}]=O(\phi^{2}).$

###### Proof.

It suffices to consider
${\bm{\alpha}},{\bm{\beta}},{\bm{x}}\in\mathbb{R}^{2}$. WLOG, assume
${\bm{\alpha}}=(1,0)^{\top}$ and ${\bm{\beta}}=(\cos\phi,\sin\phi)^{\top}$ We
have

$\displaystyle\mathbb{E}_{\bm{x}}[|{\bm{\alpha}}^{\top}{\bm{x}}|\mathbbm{1}_{\operatorname{sign}({\bm{\alpha}}^{\top}{\bm{x}})\neq\operatorname{sign}({\bm{\beta}}^{\top}{\bm{x}})}]=$
$\displaystyle\frac{1}{2\pi}\int_{0}^{\infty}re^{-r^{2}/2}\,\mathrm{d}r\int_{0}^{2\pi}\cos\theta\mathbbm{1}_{\operatorname{sign}(\cos\theta)\neq\operatorname{sign}(\cos(\theta-\phi))}\,\mathrm{d}\theta$
$\displaystyle=$ $\displaystyle O(\phi^{2}).$

∎

######  Lemma H.4.

Under Lemma 4.4, let

$\displaystyle
q_{ij}=\left\\{\begin{array}[]{ll}\frac{a_{j}a_{i}^{*}}{\sum_{j\in
T_{i,+}(\delta_{close})}a_{j}^{2}}&\text{, if $j\in
T_{i,+}(\delta_{close})$}\\\ 0&\text{, otherwise}\end{array}\right.$

If
$\sum_{i\in[m_{*}]}\left|a_{i}^{2}-\left\|{\bm{w}}_{i}\right\|_{2}^{2}\right|\leq
a_{\min}/2$, then
$\sum_{i\in[m_{*}]}\sum_{j\in{\mathcal{T}}_{i}}q_{ij}^{2}=O(\left\|{\bm{a}}_{*}\right\|_{1})$.

###### Proof.

We have

$\displaystyle\sum_{i\in[m_{*}]}\sum_{j\in{\mathcal{T}}_{i}}q_{ij}^{2}=\sum_{i\in[m_{*}]}\sum_{j\in{\mathcal{T}}_{i,+}(\delta_{close})}\frac{a_{j}^{2}a_{i}^{*2}}{(\sum_{j\in
T_{i,+}(\delta_{close})}a_{j}^{2})^{2}}=\sum_{i\in[m_{*}]}\frac{a_{i}^{*2}}{\sum_{j\in
T_{i,+}(\delta_{close})}a_{j}^{2}}.$

In the following, we aim to lower bound $\sum_{j\in
T_{i,+}(\delta_{close})}a_{j}^{2}$. Given $\sum_{j\in
T_{i,+}(\delta_{close})}|a_{j}^{2}-\left\|{\bm{w}}_{j}\right\|_{2}^{2}|\leq|a_{i}^{*}|/2$,
we have

$\displaystyle 2\sum_{j\in T_{i,+}(\delta_{close})}a_{j}^{2}\geq\sum_{j\in
T_{i,+}(\delta_{close})}a_{j}^{2}+\left\|{\bm{w}}_{j}\right\|_{2}^{2}-|a_{i}^{*}|/2\geq
2\sum_{j\in
T_{i,+}(\delta_{close})}|a_{j}|\left\|{\bm{w}}_{j}\right\|_{2}-|a_{i}^{*}|/2\geq|a_{i}^{*}|/2,$

where the last inequality is due to Lemma F.6: $\sum_{j\in
T_{i,+}(\delta_{close})}|a_{j}|\left\|{\bm{w}}_{j}\right\|_{2}\geq|\sum_{j\in{\mathcal{T}}_{i}(\delta_{close})}a_{j}\left\|{\bm{w}}_{j}\right\|_{2}|\geq|a_{i}^{*}|/2$.
Thus, we have
$\sum_{i\in[m_{*}]}\sum_{j\in{\mathcal{T}}_{i}}q_{ij}^{2}=O(\left\|{\bm{a}}_{*}\right\|_{1})$.
∎

##  Appendix I Proofs in Section G (non-degenerate dual certificate)

In this section, we give the omitted proofs in Section G. The proofs are
mostly direct computations with the properties of Hermite polynomials in Claim
A.1.

See G.1

###### Proof.

With the property of Hermite polynomials in Claim A.1, we have

$\displaystyle K({\bm{w}},{\bm{u}})=$
$\displaystyle\mathbb{E}_{\bm{x}}[\overline{\sigma_{\geq\ell}}(\overline{{\bm{w}}}^{\top}{\bm{x}})\overline{\sigma_{\geq\ell}}(\overline{{\bm{u}}}^{\top}{\bm{x}})]=\frac{1}{Z_{\sigma}^{2}}\sum_{k\geq\ell}\hat{\sigma}^{2}_{k}\cos^{k}\theta,$
(15) $\displaystyle K^{(10)}({\bm{w}},{\bm{u}})=$
$\displaystyle\frac{1}{Z_{\sigma}^{2}}\sum_{k\geq\ell}\hat{\sigma}^{2}_{k}k\cos^{k-1}\theta\frac{1}{\left\|{\bm{w}}\right\|_{2}}({\bm{I}}-\overline{{\bm{w}}}\overline{{\bm{w}}}^{\top})\overline{{\bm{u}}},$
$\displaystyle K^{(11)}({\bm{w}},{\bm{u}})=$
$\displaystyle\frac{1}{Z_{\sigma}^{2}}\sum_{k\geq\ell}\hat{\sigma}_{k}^{2}k(k-1)\cos^{k-2}\theta\frac{1}{\left\|{\bm{w}}\right\|_{2}\left\|{\bm{u}}\right\|_{2}}({\bm{I}}-\overline{{\bm{w}}}\overline{{\bm{w}}}^{\top})\overline{{\bm{u}}}\overline{{\bm{w}}}^{\top}({\bm{I}}-\overline{{\bm{u}}}\overline{{\bm{u}}}^{\top})$
$\displaystyle+\frac{1}{Z_{\sigma}^{2}}\sum_{k\geq\ell}\hat{\sigma}_{k}^{2}k\cos^{k-1}\theta\frac{1}{\left\|{\bm{w}}\right\|_{2}\left\|{\bm{u}}\right\|_{2}}({\bm{I}}-\overline{{\bm{w}}}\overline{{\bm{w}}}^{\top})({\bm{I}}-\overline{{\bm{u}}}\overline{{\bm{u}}}^{\top})$
$\displaystyle K^{(20)}({\bm{w}},{\bm{u}})=$
$\displaystyle\frac{1}{Z_{\sigma}^{2}}\sum_{k\geq\ell}\hat{\sigma}_{k}^{2}k(k-1)\cos^{k-2}\theta\frac{1}{\left\|{\bm{w}}\right\|_{2}^{2}}({\bm{I}}-\overline{{\bm{w}}}\overline{{\bm{w}}}^{\top})\overline{{\bm{u}}}\overline{{\bm{u}}}^{\top}({\bm{I}}-\overline{{\bm{w}}}\overline{{\bm{w}}}^{\top})$
$\displaystyle-\frac{1}{Z_{\sigma}^{2}}\sum_{k\geq\ell}\hat{\sigma}_{k}^{2}k\cos^{k-1}\theta\frac{1}{\left\|{\bm{w}}\right\|_{2}^{2}}\overline{{\bm{w}}}^{\top}\overline{{\bm{u}}}({\bm{I}}-\overline{{\bm{w}}}\overline{{\bm{w}}}^{\top})$
$\displaystyle K^{(21)}({\bm{w}},{\bm{u}})_{i}=$
$\displaystyle\partial_{u_{i}}K^{(20)}({\bm{w}},{\bm{u}})$ $\displaystyle=$
$\displaystyle\frac{1}{Z_{\sigma}^{2}}\sum_{k\geq\ell}\hat{\sigma}_{k}^{2}k(k-1)(k-2)\cos^{k-3}\theta\frac{1}{\left\|{\bm{w}}\right\|_{2}^{2}\left\|{\bm{u}}\right\|_{2}}{\bm{e}}_{i}^{\top}({\bm{I}}-\overline{{\bm{u}}}\overline{{\bm{u}}}^{\top})\overline{{\bm{w}}}\cdot({\bm{I}}-\overline{{\bm{w}}}\overline{{\bm{w}}}^{\top})\overline{{\bm{u}}}\overline{{\bm{u}}}^{\top}({\bm{I}}-\overline{{\bm{w}}}\overline{{\bm{w}}}^{\top})$
$\displaystyle+\frac{1}{Z_{\sigma}^{2}}\sum_{k\geq\ell}\hat{\sigma}_{k}^{2}k(k-1)\cos^{k-2}\theta\frac{1}{\left\|{\bm{w}}\right\|_{2}^{2}\left\|{\bm{u}}\right\|_{2}}({\bm{I}}-\overline{{\bm{w}}}\overline{{\bm{w}}}^{\top})\left(({\bm{I}}-\overline{{\bm{u}}}\overline{{\bm{u}}}^{\top}){\bm{e}}_{i}\overline{{\bm{u}}}^{\top}+\overline{{\bm{u}}}{\bm{e}}_{i}^{\top}({\bm{I}}-\overline{{\bm{u}}}\overline{{\bm{u}}}^{\top})\right)({\bm{I}}-\overline{{\bm{w}}}\overline{{\bm{w}}}^{\top})$
$\displaystyle-\frac{1}{Z_{\sigma}^{2}}\sum_{k\geq\ell}\hat{\sigma}_{k}^{2}k(k-1)\cos^{k-2}\theta\frac{1}{\left\|{\bm{w}}\right\|_{2}^{2}\left\|{\bm{u}}\right\|_{2}}{\bm{e}}_{i}^{\top}({\bm{I}}-\overline{{\bm{u}}}\overline{{\bm{u}}}^{\top})\overline{{\bm{w}}}\cdot\overline{{\bm{w}}}^{\top}\overline{{\bm{u}}}({\bm{I}}-\overline{{\bm{w}}}\overline{{\bm{w}}}^{\top})$
$\displaystyle-\frac{1}{Z_{\sigma}^{2}}\sum_{k\geq\ell}\hat{\sigma}_{k}^{2}k\cos^{k-1}\theta\frac{1}{\left\|{\bm{w}}\right\|_{2}^{2}}\overline{{\bm{w}}}^{\top}({\bm{I}}-\overline{{\bm{u}}}\overline{{\bm{u}}}^{\top}){\bm{e}}_{i}({\bm{I}}-\overline{{\bm{w}}}\overline{{\bm{w}}}^{\top}),$

where $\theta=\arccos(\overline{{\bm{w}}}^{\top}\overline{{\bm{u}}})$.

##### Part (i)

Given that $r=\Theta(1/\sqrt{\ell})$ with a small enough hidden constant, we
know for $\delta({\bm{w}},{\bm{u}})\geq r$

$\displaystyle
K({\bm{w}},{\bm{u}})=\frac{1}{Z_{\sigma}^{2}}\sum_{k\geq\ell}\hat{\sigma}^{2}_{k}\cos^{k}\theta\leq\frac{1}{Z_{\sigma}^{2}}\sum_{k\geq\ell}\hat{\sigma}^{2}_{k}\cdot(1-r^{2}/5)^{\ell}=c<1,$

where $c$ is a constant less than 1. Thus, $\rho_{1}=\Theta(1)$.

##### Part (ii)

For tangent vector ${\bm{z}}$ that ${\bm{z}}^{\top}{\bm{w}}=0$, we have
($\left\|{\bm{w}}\right\|_{2}=\left\|{\bm{u}}\right\|_{2}=1$,
$\delta({\bm{w}},{\bm{u}})\leq r$)

$\displaystyle K^{(20)}({\bm{w}},{\bm{u}})[{\bm{z}},{\bm{z}}]=$
$\displaystyle\frac{1}{Z_{\sigma}^{2}}\sum_{k\geq\ell}\hat{\sigma}_{k}^{2}k(k-1)\cos^{k-2}\theta\cdot(\overline{{\bm{u}}}^{\top}{\bm{z}})^{2}-\frac{1}{Z_{\sigma}^{2}}\sum_{k\geq\ell}\hat{\sigma}_{k}^{2}k\cos^{k-1}\theta\cdot\overline{{\bm{w}}}^{\top}\overline{{\bm{u}}}\left\|{\bm{z}}\right\|_{2}^{2}$
$\displaystyle=$
$\displaystyle\frac{\left\|{\bm{z}}\right\|_{2}^{2}}{Z_{\sigma}^{2}}\left(\sum_{k\geq\ell}\hat{\sigma}_{k}^{2}k(k-1)\cos^{k-2}\theta\cdot(\overline{{\bm{u}}}^{\top}\overline{{\bm{z}}})^{2}-\sum_{k\geq\ell}\hat{\sigma}_{k}^{2}k\cos^{k-1}\theta\cdot\overline{{\bm{w}}}^{\top}\overline{{\bm{u}}}\right)$
$\displaystyle\leq$
$\displaystyle\frac{\left\|{\bm{z}}\right\|_{2}^{2}}{Z_{\sigma}^{2}}\left(\sum_{k\geq\ell}\hat{\sigma}_{k}^{2}k(k-1)\cos^{k-2}\theta\sin^{2}\theta-\sum_{\ell\leq
k\leq 2\ell}\hat{\sigma}_{k}^{2}k\cos^{k}\theta\right).$

For the first term, we have

$\displaystyle\sum_{k\geq\ell}\hat{\sigma}_{k}^{2}k(k-1)\cos^{k-2}\theta\sin^{2}\theta$
$\displaystyle\leq$ $\displaystyle\sum_{k\geq
1/r^{2}}\hat{\sigma}_{k}^{2}k(k-1)\cdot\Theta(1/k)+\sum_{\ell\leq k\leq
1/r^{2}}\Theta(k^{-1/2})r^{2}$ $\displaystyle\leq$ $\displaystyle\sum_{k\geq
1/r^{2}}\Theta(k^{-3/2})+\Theta(r)=\Theta(r),$

where we use Lemma I.1 and $\hat{\sigma}_{k}^{2}=\Theta(k^{-5/2})$ in Lemma
A.1.

For the second term, we have

$\displaystyle\sum_{\ell\leq k\leq
2\ell}\hat{\sigma}_{k}^{2}k\cos^{k}\theta\geq\Theta(\ell^{-1/2})(1-r^{2})^{2\ell}.$

Given that $r=\Theta(1/\sqrt{\ell})$ with a small enough hidden constant, we
know

$\displaystyle
K^{(20)}({\bm{w}},{\bm{u}})[{\bm{z}},{\bm{z}}]\leq-\frac{\left\|{\bm{z}}\right\|_{2}^{2}}{Z_{\sigma}^{2}}\Theta(\ell^{-1/2})=-\Theta(\ell)\left\|{\bm{z}}\right\|_{2}^{2},$

since $Z_{\sigma}^{2}=\Theta(\ell^{-3/2})$.

##### Part (iii)

Recall that $\delta({\bm{w}}_{i}^{*},{\bm{w}}_{j}^{*})\geq\Delta$ for $i\neq
j$. It suffices to bound $\left\|K^{(ij)}({\bm{w}},{\bm{u}})\right\|_{2}\leq
h/m_{*}^{2}$ for $\theta=\delta({\bm{w}},{\bm{u}})\geq\Delta$. Given that
$\ell\geq\Theta(\Delta^{-2}\log(m_{*}\ell/h\Delta))$ with large enough hidden
constant, from (15) we have for
$\left\|{\bm{w}}\right\|=\left\|{\bm{u}}\right\|=1$

$\displaystyle K({\bm{w}},{\bm{u}})\leq$
$\displaystyle\frac{1}{Z_{\sigma}^{2}}\sum_{k\geq\ell}\hat{\sigma}^{2}_{k}(1-\Delta^{2}/5)^{\ell}\leq
h/m_{*}^{2},$
$\displaystyle\left\|K^{(10)}({\bm{w}},{\bm{u}})\right\|_{\bm{w}}\leq$
$\displaystyle\frac{1}{Z_{\sigma}^{2}}\sum_{k\geq\ell}\hat{\sigma}^{2}_{k}k\cos^{k-1}\theta\sin\theta\leq\Theta(\ell)(1-\Delta^{2}/5)^{\ell-1}\leq
h/m_{*}^{2},$
$\displaystyle\left\|K^{(11)}({\bm{w}},{\bm{u}})\right\|_{{\bm{w}},{\bm{u}}}=$
$\displaystyle\frac{1}{Z_{\sigma}^{2}}\sup_{\begin{subarray}{c}{\bm{z}}_{1}^{\top}{\bm{w}}={\bm{z}}_{2}^{\top}{\bm{u}}=0,\\\
\left\|{\bm{z}}_{1}\right\|_{2}=\left\|{\bm{z}}_{2}\right\|_{2}=1\end{subarray}}\sum_{k\geq\ell}\hat{\sigma}_{k}^{2}k(k-1)\cos^{k-2}\theta\overline{{\bm{u}}}^{\top}{\bm{z}}_{1}\cdot\overline{{\bm{w}}}^{\top}{\bm{z}}_{2}+\sum_{k\geq\ell}\hat{\sigma}_{k}^{2}k\cos^{k-1}\theta{\bm{z}}_{1}^{\top}{\bm{z}}_{2}$
$\displaystyle\leq$
$\displaystyle\frac{1}{Z_{\sigma}^{2}}\sum_{k\geq\ell}\hat{\sigma}_{k}^{2}k(k-1)\cos^{k-2}\theta\sin^{2}\theta+\frac{1}{Z_{\sigma}^{2}}\sum_{k\geq\ell}\hat{\sigma}_{k}^{2}k\cos^{k-1}\theta$
$\displaystyle\leq$
$\displaystyle\Theta(\ell^{3/2})\sum_{k\geq\ell}\Theta(k^{-1/2})(1-\Delta^{2}/5)^{k-2}+\Theta(\ell)(1-\Delta^{2}/5)^{\ell-1}\leq
h/m_{*}^{2},$

$\displaystyle\left\|K^{(20)}({\bm{w}},{\bm{u}})\right\|_{\bm{w}}=$
$\displaystyle\frac{1}{Z_{\sigma}^{2}}\sup_{\begin{subarray}{c}{\bm{z}}_{1}^{\top}{\bm{w}}={\bm{z}}_{2}^{\top}{\bm{w}}=0,\\\
\left\|{\bm{z}}_{1}\right\|_{2}=\left\|{\bm{z}}_{2}\right\|_{2}=1\end{subarray}}\sum_{k\geq\ell}\hat{\sigma}_{k}^{2}k(k-1)\cos^{k-2}\theta\cdot\overline{{\bm{u}}}^{\top}{\bm{z}}_{1}\cdot\overline{{\bm{u}}}^{\top}{\bm{z}}_{2}-\sum_{k\geq\ell}\hat{\sigma}_{k}^{2}k\cos^{k-1}\theta\cdot\overline{{\bm{w}}}^{\top}\overline{{\bm{u}}}\cdot{\bm{z}}_{1}^{\top}{\bm{z}}_{2}$
$\displaystyle\leq$
$\displaystyle\frac{1}{Z_{\sigma}^{2}}\sum_{k\geq\ell}\hat{\sigma}_{k}^{2}k(k-1)\cos^{k-2}\theta\sin^{2}\theta+\frac{1}{Z_{\sigma}^{2}}\sum_{k\geq\ell}\hat{\sigma}_{k}^{2}k\cos^{k-1}\theta$
$\displaystyle\leq$
$\displaystyle\Theta(\ell^{3/2})\sum_{k\geq\ell}\Theta(k^{-1/2})(1-\Delta^{2}/5)^{k-2}+\Theta(\ell)(1-\Delta^{2}/5)^{\ell-1}\leq
h/m_{*}^{2},$

$\displaystyle\left\|K^{(21)}({\bm{w}},{\bm{u}})\right\|_{{\bm{w}},{\bm{u}}}$
$\displaystyle=$
$\displaystyle\sup_{\begin{subarray}{c}{\bm{z}}_{1}^{\top}{\bm{w}}={\bm{z}}_{2}^{\top}{\bm{w}}={\bm{q}}^{\top}{\bm{u}}=0,\\\
\left\|{\bm{z}}_{1}\right\|_{2}=\left\|{\bm{z}}_{2}\right\|_{2}=\left\|{\bm{q}}\right\|_{2}=1\end{subarray}}\frac{1}{Z_{\sigma}^{2}}\sum_{k\geq\ell}\hat{\sigma}_{k}^{2}k(k-1)(k-2)\cos^{k-3}\theta\sum_{i}q_{i}{\bm{e}}_{i}^{\top}({\bm{I}}-\overline{{\bm{u}}}\overline{{\bm{u}}}^{\top})\overline{{\bm{w}}}\cdot\overline{{\bm{u}}}^{\top}{\bm{z}}_{1}\cdot\overline{{\bm{u}}}^{\top}{\bm{z}}_{2}$
$\displaystyle+\frac{1}{Z_{\sigma}^{2}}\sum_{k\geq\ell}\hat{\sigma}_{k}^{2}k(k-1)\cos^{k-2}\theta\left(\sum_{i}q_{i}{\bm{z}}_{1}^{\top}({\bm{I}}-\overline{{\bm{u}}}\overline{{\bm{u}}}^{\top}){\bm{e}}_{i}\cdot\overline{{\bm{u}}}^{\top}{\bm{z}}_{2}+\sum_{i}q_{i}{\bm{z}}_{2}^{\top}({\bm{I}}-\overline{{\bm{u}}}\overline{{\bm{u}}}^{\top}){\bm{e}}_{i}\cdot\overline{{\bm{u}}}^{\top}{\bm{z}}_{1}\right)$
$\displaystyle-\frac{1}{Z_{\sigma}^{2}}\sum_{k\geq\ell}\hat{\sigma}_{k}^{2}k(k-1)\cos^{k-2}\theta\sum_{i}q_{i}{\bm{e}}_{i}^{\top}({\bm{I}}-\overline{{\bm{u}}}\overline{{\bm{u}}}^{\top})\overline{{\bm{w}}}\cdot\overline{{\bm{w}}}^{\top}\overline{{\bm{u}}}\cdot{\bm{z}}_{1}^{\top}{\bm{z}}_{2}$
$\displaystyle-\frac{1}{Z_{\sigma}^{2}}\sum_{k\geq\ell}\hat{\sigma}_{k}^{2}k\cos^{k-1}\theta\sum_{i}q_{i}\overline{{\bm{w}}}^{\top}({\bm{I}}-\overline{{\bm{u}}}\overline{{\bm{u}}}^{\top}){\bm{e}}_{i}\cdot{\bm{z}}_{1}^{\top}{\bm{z}}_{2}$
$\displaystyle\leq$
$\displaystyle\frac{1}{Z_{\sigma}^{2}}\sum_{k\geq\ell}\hat{\sigma}_{k}^{2}k(k-1)(k-2)\cos^{k-3}\theta\sin^{3}\theta+\frac{2}{Z_{\sigma}^{2}}\sum_{k\geq\ell}\hat{\sigma}_{k}^{2}k(k-1)\cos^{k-2}\theta\sin\theta+\frac{1}{Z_{\sigma}^{2}}\sum_{k\geq\ell}\hat{\sigma}_{k}^{2}k\cos^{k-1}\theta\sin\theta$
$\displaystyle\stackrel{{\scriptstyle(\text{a})}}{{\leq}}$ $\displaystyle
h/m_{*}^{2},$

where we use $\hat{\sigma}_{k}^{2}=\Theta(k^{-5/2})$ in Lemma A.1 and (a) the
last two terms bound similarly as in $K^{(20)}$ and first term
$\frac{1}{Z_{\sigma}^{2}}\sum_{k\geq\ell}\hat{\sigma}_{k}^{2}k(k-1)(k-2)\cos^{k-3}\theta\sin^{3}\theta\leq\Theta(\ell^{3/2})\sum_{k\geq\ell}\Theta(k^{1/2})(1-\Delta^{2}/5)^{k}\leq
h/3m_{*}^{2}$. ∎

See G.2

###### Proof.

We compute $B_{ij}$ one by one from (15) (see part (iii) proof in Lemma G.1).
Using Lemma I.1 we have

$\displaystyle B_{00}=$
$\displaystyle\sup_{{\bm{w}},{\bm{u}}}\left|\frac{1}{Z_{\sigma}^{2}}\sum_{k\geq\ell}\hat{\sigma}^{2}_{k}\cos^{k}\theta\right|\leq
1,$ $\displaystyle B_{10}\leq$
$\displaystyle\frac{1}{Z_{\sigma}^{2}}\sum_{k\geq\ell}\hat{\sigma}^{2}_{k}k\cos^{k-1}\theta\sin\theta\leq\Theta(\ell^{3/2})\sum_{k\geq\ell}\Theta(k^{-5/2})k\frac{1}{\sqrt{k}}=O(\ell^{1/2}),$
$\displaystyle B_{11}\leq$
$\displaystyle\frac{1}{Z_{\sigma}^{2}}\sum_{k\geq\ell}\hat{\sigma}_{k}^{2}k(k-1)\cos^{k-2}\theta\sin^{2}\theta+\frac{1}{Z_{\sigma}^{2}}\sum_{k\geq\ell}\hat{\sigma}_{k}^{2}k\cos^{k-1}\theta$
$\displaystyle\leq$
$\displaystyle\Theta(\ell^{3/2})\sum_{k\geq\ell}\Theta(k^{-5/2})k^{2}\frac{1}{k}+\Theta(\ell^{3/2})\sum_{k\geq\ell}\Theta(k^{-5/2})k=O(\ell),$

$\displaystyle B_{20}\leq$
$\displaystyle\frac{1}{Z_{\sigma}^{2}}\sum_{k\geq\ell}\hat{\sigma}_{k}^{2}k(k-1)\cos^{k-2}\theta\sin^{2}\theta+\frac{1}{Z_{\sigma}^{2}}\sum_{k\geq\ell}\hat{\sigma}_{k}^{2}k\cos^{k}\theta$
$\displaystyle\leq$
$\displaystyle\Theta(\ell^{3/2})\sum_{k\geq\ell}\Theta(k^{-5/2})k^{2}\frac{1}{k}+\Theta(\ell^{3/2})\sum_{k\geq\ell}\Theta(k^{-5/2})k=O(\ell),$
$\displaystyle B_{21}\leq$
$\displaystyle\frac{1}{Z_{\sigma}^{2}}\sum_{k\geq\ell}\hat{\sigma}_{k}^{2}k(k-1)(k-2)\cos^{k-3}\theta\sin^{3}\theta+\frac{2}{Z_{\sigma}^{2}}\sum_{k\geq\ell}\hat{\sigma}_{k}^{2}k(k-1)\cos^{k-1}\theta\sin\theta+\frac{1}{Z_{\sigma}^{2}}\sum_{k\geq\ell}\hat{\sigma}_{k}^{2}k\cos^{k-1}\theta\sin\theta$
$\displaystyle\leq$
$\displaystyle\Theta(\ell^{3/2})\sum_{k\geq\ell}\Theta(k^{1/2})(1-\theta^{2}/5)^{k-3}\theta^{3}+\Theta(\ell^{3/2})\sum_{k\geq\ell}\Theta(k^{-1/2})(1-\theta^{2}/5)^{k-1}\theta$

For first term above
$\sum_{k\geq\ell}\Theta(k^{1/2})(1-\theta^{2}/5)^{k-3}\theta^{3}$, using Lemma
I.2 we have

$\displaystyle\sum_{k\geq\ell}\Theta(k^{1/2})(1-\theta^{2}/5)^{k-3}\theta^{3}\leq$
$\displaystyle\sum_{k\geq\ell}\Theta(\frac{1}{\sqrt{\ln(1/(1-\theta^{2}))}})(1-\theta^{2}/5)^{k/2-3}\theta^{3}$
$\displaystyle\leq$
$\displaystyle\sum_{k\geq\ell}\Theta(\theta^{2})(1-\theta^{2}/5)^{k/2-3}=\Theta(\theta^{2})\frac{(1-\theta^{2}/5)^{\ell}}{\theta^{2}}=O(1).$

For second term above
$\sum_{k\geq\ell}\Theta(k^{-1/2})(1-\theta^{2}/5)^{k-1}\theta$ we have

$\displaystyle\sum_{k\geq\ell}\Theta(k^{-1/2})(1-\theta^{2}/5)^{k-1}\theta\leq\Theta(\theta)\int_{\ell}^{\infty}x^{-1/2}(1-\theta^{2}/5)^{x}\leq\Theta(\theta)\Theta(\frac{1}{\sqrt{\ln(1/(1-\theta^{2}))}})=O(1).$

Therefore, we have $B_{21}=O(\ell^{3/2})$. ∎

###  I.1 Technical lemma

We collect few lemma here used in the proof. They mostly rely on direct
calculations.

######  Lemma I.1.

For large enough integer $k$, we have

$\max|\cos^{k}\theta\sin\theta|\leq\Theta(1/\sqrt{k}),$
$\max|\cos^{k}\theta\sin^{2}\theta|\leq\Theta(1/k),$
$\max|\cos^{k}\theta\sin^{3}\theta|=\Theta(1/k^{3/2}).$

###### Proof.

We only compute the first one $\max|\cos^{k}\theta\sin\theta|=1/\sqrt{k}$.
Others are similar.

We compute the gradient of $f(\theta)=\cos^{k}\theta\sin\theta$ and get
$f^{\prime}(\theta)=\cos^{k-1}\theta(\cos^{2}\theta-k\sin^{2}\theta)$. We only
need to consider $\theta\in[0,2\pi]$. So the maximum is achieved either at
boundary $\theta=0,\pi$ or $f^{\prime}(\theta)=0$. Then one can verify that
the bound is true. ∎

######  Lemma I.2.

For $\beta<1$ and $k>0$, we have
$k^{1/2}\beta^{k/2}\leq\frac{1}{\sqrt{2\ln(2/\beta)}}$.

###### Proof.

Let $f(k)=k^{1/2}\beta^{k/2}$. We have
$f^{\prime}(k)=\frac{1}{2}k^{-1/2}\beta^{k/2}+k^{1/2}\beta^{k/2}\ln(\beta/2)$.
Set $f^{\prime}(k_{0})=0$ we have $k_{0}=\frac{1}{2\ln(2/\beta)}$. It is easy
to see $\max f(k)=f(k_{0})\leq\frac{1}{\sqrt{2\ln(2/\beta)}}$. ∎