A related property holds for “components along $n$”:

######  Proposition 4.3.3.

If random $\bm{Z}\in\mathbb{R}^{k}$ has all moments, then
$\mathrm{iid}^{r}(\bm{Z})$ is moment-bounded for all $r\geq 0$.

Moment-boundedness is closed under applications of polynomially bounded
functions: in short,

  * •

$\psi(\bm{x})$ is moment-bounded if $\bm{x}$ is, and

  * •

more generally, $\psi(\bm{x}^{1};\cdots;\bm{x}^{r})$ is moment-bounded if
$\bm{x}^{1},\ldots,\bm{x}^{r}$ are.

We make this formal in the following

######  Proposition 4.3.4.

Consider moment-bounded multi-tensors
$\bm{x}^{t}\in\mathcal{S}_{\mathrm{b}}^{s_{t}}\otimes\mathcal{V}_{t}$ for each
$t=1,\ldots,r$. Let
$\psi(-;\cdots;-):\mathcal{V}_{1}\oplus\cdots\oplus\mathcal{V}_{r}\to\mathcal{V}^{\prime}$
be polynomially bounded. Then $\psi(\bm{x}^{1};\cdots;\bm{x}^{r})$ is moment-
bounded as well:
$\psi(\bm{x}^{1};\cdots;\bm{x}^{r})\in\mathcal{S}_{\mathrm{b}}^{\sum_{t}s_{t}}\otimes{\cal
V}^{\prime}$.

For example, for $r=1$, when we take $\psi:\mathbb{R}^{2}\to\mathbb{R}$ as the
sum and product functions, we have that $\mathcal{S}_{\mathrm{b}}^{s}$ is
closed under entrywise sum and product. Similarly, when we take
$\psi:\mathbb{R}^{k\times l+l\times m}\to\mathbb{R}^{k\times m}$ to be the
matrix multiplication function (multiplying matrices of sizes $k\times l$ and
$l\times m$ to get one of size $k\times m$), we derive the closure of
$\mathcal{S}_{\mathrm{b}}^{s}\otimes\mathbb{R}^{k\times k}$ under matrix
multiplication (after setting $l=m=k$).

###### Proof.

By polynomially-boundedness of $\psi$, for any $q>0$, there are $C,p$ such
that, for any $\bm{z}^{t}\in\mathcal{V}_{t},t=1,\ldots,r$, we have

$\|\psi(\bm{z}^{1};\cdots;\bm{z}^{r})\|_{q}^{q}\leq
C(1+\|\bm{z}^{1}\|_{p}^{p}+\cdots+\|\bm{z}^{r}\|_{p}^{p}).$

Therefore, for ${\bm{\beta}}\in[n]^{s}$,

$\displaystyle\left\langle\|\psi(\bm{x}_{{\bm{\alpha}}_{1}}^{1};\cdots;\bm{x}_{{\bm{\alpha}}_{r}}^{r})\|_{q}^{q}\right\rangle_{{\bm{\alpha}}_{1}\cdots{\bm{\alpha}}_{r}}$
$\displaystyle\leq
C\left\langle(1+\|\bm{x}_{{\bm{\alpha}}_{1}}^{1}\|_{p}^{p}+\cdots+\|\bm{x}_{{\bm{\alpha}}_{r}}^{r}\|_{p}^{p})\right\rangle_{{\bm{\alpha}}_{1}\cdots{\bm{\alpha}}_{r}}$
$\displaystyle=C\left(1+\left\langle\|\bm{x}_{{\bm{\alpha}}}^{1}\|_{p}^{p}\right\rangle_{{\bm{\alpha}}}+\cdots+\left\langle\|\bm{x}_{{\bm{\alpha}}}^{r}\|_{p}^{p}\right\rangle_{{\bm{\alpha}}}\right).$

But, for each $t\in[r]$, since $\bm{x}^{t}$ is moment-bounded, we have
$n^{-\epsilon}\left\langle\|\bm{x}_{{\bm{\alpha}}}^{t}\|_{p}^{p}\right\rangle_{{\bm{\alpha}}}\xrightarrow{\mathrm{\mathrm{a.s.}}}0$
for any $\epsilon>0$. Therefore,

$n^{-\epsilon}\left\langle\|\psi(\bm{x}_{{\bm{\alpha}}_{1}}^{1};\cdots;\bm{x}_{{\bm{\alpha}}_{r}}^{r})\|_{q}^{q}\right\rangle_{{\bm{\alpha}}_{1}\cdots{\bm{\alpha}}_{r}}\leq
n^{-\epsilon}C\left(1+\left\langle\|\bm{x}_{{\bm{\alpha}}}^{1}\|_{p}^{p}\right\rangle_{{\bm{\alpha}}}+\cdots+\left\langle\|\bm{x}_{{\bm{\alpha}}}^{r}\|_{p}^{p}\right\rangle_{{\bm{\alpha}}}\right)\xrightarrow{\mathrm{\mathrm{a.s.}}}0$

as well. Since $q$ and $\epsilon$ are arbitrary in this argument, this shows
$\psi(\bm{x}^{1};\cdots;\bm{x}^{r})$ is moment-bounded. ∎

####  4.3.2 Vanishing Multi-Tensors

A mentioned above, a notion of “vanishing” will play a central role in what
follows:

######  Definition 4.3.5.

We say a multi-tensors $\bm{x}$ is _entrywise vanishing_ , or just _vanishing_
for short, if

$\left\langle\|\bm{x}_{{\bm{\alpha}}}\|^{2}\right\rangle_{{\bm{\alpha}}}=\tilde{O}(n^{-1}),$

with $\tilde{O}$ from 1.2.5. We write $\mathcal{S}_{0}^{s}\otimes\mathcal{V}$
for the space of such multi-tensors.__4 44We emphasize that “vanishing” is a
shorthand for “entrywise-vanishing” and _not_ interpreted as “normwise-
vanishing”. For example, an entrywise-vanishing vector can still have
$\Omega(1)$ norm, such as the vector with entries $n^{-1/2}$; a random
Gaussian matrix with iid $\mathcal{N}(0,1/n)$ entries will have $\Theta(1)$
operator norm almost surely as $n\to\infty$. But since we will never talk
about “normwise-vanishing,” for our purposes it will not cause confusion to
abbreviate “entrywise-vanishing” to just “vanishing.”

Unpacking the big-O notation, $\bm{x}$ is vanishing iff, for every
$\epsilon>0$,

$n^{1-\epsilon}\cdot\left\langle\|\bm{x}_{{\bm{\alpha}}}\|^{2}\right\rangle_{{\bm{\alpha}}}\xrightarrow{\mathrm{\mathrm{a.s.}}}0,\quad\text{as}\quad
n\to\infty.$

At first, using the same intuition as above, one may think of vanishing
tensors as those whose entries have typical size $O(1/\sqrt{n})$.

But notice that “vanishing” is defined only via $L^{2}$ norm, while “moment-
bounded” is defined via every $L^{p}$ norm. This is an important technical
distinction. The primary purpose of this distinction is that when $x$ is an
$n$-vector and $W$ is an iid matrix with (for example) $\mathcal{N}(0,1/n)$
entries,

$Wx$ is vanishing if $x$ is; see 4.3.14.

This is because of the well-known almost sure operator-norm bounds [38, 48] on
such iid matrices $W$. If we defined “vanishing” based on other $L^{p}$ norm
as well, then we cannot make the same statement as it will be much more
difficult to control the $L^{p}$ norm of $Wx$.

As a result of this difference in the definitions, “vanishing” implies
“moment-bounded” _only for scalars and vectors_ (i.e.,
$\mathcal{S}_{0}^{s}\subseteq\mathcal{S}_{\mathrm{b}}^{s}$ only for $s=0,1$);
see Lemma 4.3.7 below. For example, consider the $n$-matrix $x$ with all-zero
entries except the value $\sqrt{n}$ in its top left corner. It is vanishing
(because
$\left\langle|x_{{\bm{\alpha}}}|^{2}\right\rangle_{{\bm{\alpha}}}=\Theta(1/n)$)
but not moment-bounded (e.g.,
$\left\langle|x_{{\bm{\alpha}}}|^{8}\right\rangle_{{\bm{\alpha}}}=\Theta(n^{2})$).
The takeaway here is that while moment-bounded tensors can be thought of as
“every entry is $O(1)$”, vanishing tensors can have a small number of entries
that explode with $n$, as long as the quadratic mean of the entries has size
$O(\nicefrac{{1}}{{\sqrt{n}}})$.

We summarize these intuitions succinctly as follows (because they are
important to understand sooner than later):

moment-bounded $\displaystyle\approx\text{dense entries all of size $O(1)$}$
vanishing $\displaystyle\approx\text{potentially sparse entries,
$O(\nicefrac{{1}}{{\sqrt{n}}})$ in quadratic mean}.$

##### Basic Properties

Like for moment-boundedness, the “vanishing” property is reducible to
components, which makes proofs a bit simpler.

######  Proposition 4.3.6.

$\bm{x}=(x^{1},\ldots,x^{k})$ is vanishing iff each of its components
$x^{1},\ldots,x^{k}$ is vanishing.

As mentioned above, $\mathcal{S}_{0}^{s}\subseteq\mathcal{S}_{\mathrm{b}}^{s}$
only for $s=0,1$.

######  Lemma 4.3.7.

Let $\bm{x}\in\mathcal{S}_{0}^{s}\otimes\mathcal{V}$ for Euclidean space
$\mathcal{V}$. Whenever $s=0,1$ or else $p<\frac{2s}{s-1}$, we have

$\left\langle\|\bm{x}_{{\bm{\alpha}}}\|_{p}^{p}\right\rangle_{{\bm{\alpha}}}\xrightarrow{\mathrm{\mathrm{a.s.}}}0.$

Consequently,
$\mathcal{S}_{0}^{s}\otimes\mathcal{V}\subseteq\mathcal{S}_{\mathrm{b}}^{s}\otimes\mathcal{V}$
for $s=0,1$. i.e., all vanishing multi-scalars and multi-vectors are moment-
bounded. But this is false for $s\geq 2$.

###### Proof.

For clarity, we prove the claim for $x\in\mathcal{S}_{0}^{s}$; the
generalization to $\bm{x}\in\mathcal{S}_{0}^{s}\otimes\mathcal{V}$ follows
from this case componentwise.

By $L^{p}$ norm inequalities, for all $p\geq 2$,

$\|x(n)\|_{p}\leq\|x(n)\|_{2}$

so

$\|x(n)\|_{p}^{p}/n^{s}\leq\|x(n)\|_{2}^{p}/n^{s}=K{}^{p/2}$

where

$K\mathrel{\raisebox{-1.29167pt}{$\mathbin{\overset{\text{{def}}}{=}}$}}\|x(n)\|_{2}^{2}/n^{s\cdot\frac{2}{p}}.$

When $s=0$ or 1 or when $p<\frac{2s}{s-1}$, we have $s\cdot\frac{2}{p}>s-1$,
so that, for any sufficiently small $\delta>0$,

$K<n^{1-\delta}\cdot\|x(n)\|_{2}^{2}/n^{s}\quad\text{for all $n$}.$

But since $x$ is vanishing, the RHS goes to 0 almost surely, and therefore so
does $K$. We thus have

$\|x(n)\|_{p}^{p}/n^{s}=\left\langle\|\bm{x}_{{\bm{\alpha}}}\|_{p}^{p}\right\rangle_{{\bm{\alpha}}}=K^{p/2}\xrightarrow{\mathrm{\mathrm{a.s.}}}0$

as desired. ∎

The following yields a sufficient condition for vanishing that is often easier
to show than directly showing vanishing itself. Roughly speaking, it says an
$n$-tensor is vanishing if every entry looks like $O(1/\sqrt{n})$ as measured
by every power mean expectation.

######  Proposition 4.3.8.

Suppose $v\in\mathcal{S}_{\mathrm{b}}^{s}$. If there exist constants
$C_{p,\varepsilon}$ for all $\varepsilon>0$ and all integers $p\geq 1$ such
that we have the following inequality

$n^{-s}\operatorname*{\mathbb{E}}\|v\|_{2p}^{2p}=\operatorname*{\mathbb{E}}\left\langle
v_{\alpha}^{2p}\right\rangle_{\alpha}\leq C_{p,\varepsilon}n^{-p+\varepsilon}$

for all $p,\varepsilon$ and $n$, then $v$ is vanishing.

###### Proof.

WLOG we assume $s=1$, since the general case follows by unrolling $v$ into a
(giant) vector.

To show $v$ is vanshing, we need to show
$n^{-\epsilon}\|v\|^{2}\xrightarrow{\mathrm{\mathrm{a.s.}}}0$ for any
$\epsilon>0$. By LABEL:{lemma:momentBoundASConvergence}, we just need to show
that for some $q,\gamma>0$, we have
$\operatorname*{\mathbb{E}}(n^{-\epsilon}\|v\|^{2})^{q}=O(n^{-1-\gamma})$. But
$\|v\|\leq n^{1/2-1/2q}\|v\|_{2q}$ for all $q\geq 1$. Thus, for any $q\geq 1$,

$\operatorname*{\mathbb{E}}(n^{-\epsilon}\|v\|^{2})^{q}\leq n^{-\epsilon
q}\operatorname*{\mathbb{E}}n^{q-1}\|v\|_{2q}^{2q}\leq n^{q-\epsilon
q}C_{q,\varepsilon}n^{-q+\varepsilon}=n^{\varepsilon-\epsilon
q}C_{q,\varepsilon}.$

Whence we can take any small $\varepsilon>0$ and $q>(1+\varepsilon)/\epsilon$
to have
$\operatorname*{\mathbb{E}}(n^{-\epsilon}\|v\|^{2})^{q}=O(n^{-1-\gamma})$, as
desired. ∎

####  4.3.3 Equivalence Modulo Vanishing Multi-Tensors

######  Definition 4.3.9.

Let $\bm{x},\bm{y}$ be multi-tensors of the same shape. We say _$\bm{x}$ is
equivalent to $\bm{y}$, written_ $\bm{x}\equiv\bm{y}$, if $\bm{x}-\bm{y}$ is
vanishing.

Since our writing convention suppresses $n$, this notation may be ambiguous:
To disambiguate, the equivalence $\bm{x}\equiv\bm{y}$ is a notion between
multi-tensors as sequences, i.e., it should be read as
$\\{\bm{x}(n)\\}_{n}\equiv\\{\bm{y}(n)\\}_{n}$, NOT as a sequence of
equivalences $\bm{x}(n)\equiv\bm{y}(n)$, one for each $n$.

The $\bm{x},\bm{y}$ here will all have $\Theta(1)$-sized entries in our
applications. By the discussion above regarding vanishing multi-tensors,
$\bm{x}\equiv\bm{y}$ just means that $\bm{x}$ and $\bm{y}$ have roughly the
same entries. But note that, as vectors, matrices, or tensors, $\bm{x}$ can
definitely differ from $\bm{y}$ nontrivially in norm, because e.g., a
vanishing vector can have $\Theta(1)$ norm.

We first note a trivial but useful property.

######  Proposition 4.3.10.

$(x^{1},\ldots,x^{k})\equiv(y^{1},\ldots,y^{k})$ iff $x^{1}\equiv
y^{1},\ldots$, and $x^{k}\equiv y^{k}$.

Equivalence is preserved under most operations, as summarized below:

  1. 1.

“smooth” mapping $\phi$: (4.3.11 and 4.3.12)

    1. (a)

For example, if $\bm{x}\equiv\bm{y}$ are both moment-bounded, then
$\phi(\bm{x})\equiv\phi(\bm{y})$. This holds more generally for “smooth”
nonlinear outer products.

  2. 2.

averaging over $[n]$: (Lemma 4.3.13)

    1. (a)

If $\bm{x}\equiv\bm{y}$, then
$\langle\bm{x}_{{\bm{\alpha}}{\bm{\beta}}}\rangle_{{\bm{\beta}}}\equiv\langle\bm{y}_{{\bm{\alpha}}{\bm{\beta}}}\rangle_{{\bm{\beta}}}$

  3. 3.

multiplication by operator-norm-bounded matrices: (4.3.14)

    1. (a)

If $x\equiv y$ are $n$-vectors and $W$ is an $n$-matrix that almost surely has
bounded operator norm, then $Wx\equiv Wy$. This holds in particular for $W$
having iid, zero-mean entries of size $\Theta(1/\sqrt{n})$.

##### Preservation under Nonlinear Outer Products

######  Proposition 4.3.11.

Consider multi-tensors
$\bm{x}^{t},\bm{y}^{t}\in\mathcal{S}_{\mathrm{b}}^{s_{t}}\otimes\mathcal{V}_{t}$
for each $t=1,\ldots,r$ and a function
$\psi(-;\cdots;-):\mathcal{V}_{1}\oplus\cdots\oplus\mathcal{V}_{t}\to\mathcal{V}^{\prime}$.
If $\psi$ is pseudo-Lipschitz and $\bm{x}^{t}\equiv\bm{y}^{t}$ for all $t$,
then

$\psi(\bm{x}^{1};\cdots;\bm{x}^{r})\equiv\psi(\bm{y}^{1};\cdots;\bm{y}^{r}).$

###### Proof.

Note that this holds for the semicolon product (i.e., when $\psi$ is identity
and $\mathcal{V}^{\prime}=\mathcal{V}_{1}\oplus\cdots\oplus\mathcal{V}_{t}$):
If we shorthand
$\bm{\Delta}=(\bm{x}^{1};\cdots;\bm{x}^{r})-(\bm{y}^{1};\cdots;\bm{y}^{r})$,
then

$\bm{\Delta}_{{\bm{\beta}}_{1}\cdots{\bm{\beta}}_{r}}=(\bm{x}_{{\bm{\beta}}_{1}}^{1}-\bm{y}_{{\bm{\beta}}_{1}}^{1},\ldots,\bm{x}_{{\bm{\beta}}_{r}}^{r}-\bm{y}_{{\bm{\beta}}_{r}}^{r})\in\mathcal{V}^{\prime}$

so that, with ${\bm{\alpha}}=({\bm{\beta}}_{1},\ldots,{\bm{\beta}}_{r})$,

$\displaystyle\left\langle\|\bm{\Delta}_{{\bm{\alpha}}}\|^{2}\right\rangle_{{\bm{\alpha}}}$
$\displaystyle=\left\langle\|\bm{x}_{{\bm{\beta}}_{1}}^{1}-\bm{y}_{{\bm{\beta}}_{1}}^{1}\|^{2}+\cdots+\|\bm{x}_{{\bm{\beta}}_{r}}^{r}-\bm{y}_{{\bm{\beta}}_{r}}^{r}\|^{2}\right\rangle_{{\bm{\beta}}_{1}\cdots{\bm{\beta}}_{r}}$
$\displaystyle=\left\langle\|\bm{x}_{{\bm{\beta}}}^{1}-\bm{y}_{{\bm{\beta}}}^{1}\|^{2}\right\rangle_{{\bm{\beta}}}+\cdots+\left\langle\|\bm{x}_{{\bm{\beta}}}^{r}-\bm{y}_{{\bm{\beta}}}^{r}\|^{2}\right\rangle_{{\bm{\beta}}}.$

Then since $\bm{x}^{1}-\bm{y}^{1},\ldots,\bm{x}^{r}-\bm{y}^{r}$ are all
vanishing, so is $\bm{\Delta}$. Thus, we get
$(\bm{x}^{1};\cdots;\bm{x}^{r})\equiv(\bm{y}^{1};\cdots;\bm{y}^{r})$.

By Eq. 4.1, this means, for proving 4.3.11, it suffices to show
$\psi(\bm{x})\equiv\psi(\bm{y})$ when
$\psi:\mathcal{V}\to\mathcal{V}^{\prime}$ and
$\bm{x},\bm{y}\in\mathcal{S}_{\mathrm{b}}^{s}\otimes\mathcal{V}$ with
$\bm{x}\equiv\bm{y}$, where $\mathcal{V},\mathcal{V}^{\prime}$ are arbitrary
Euclidean spaces. WLOG, assume $\mathcal{V}=\mathbb{R}^{k}$ for some integer
$k\geq 0$. We can further assume $\mathcal{V}^{\prime}$ to be $\mathbb{R}$,
because the general case follows componentwise from this. We proceed as
follows.

By the definition of pseudo-Lipschitz, we have

$\displaystyle|\psi(\bm{x}_{{\bm{\beta}}})-\psi(\bm{y}_{{\bm{\beta}}})|$
$\displaystyle\leq
C\|\bm{x}_{{\bm{\beta}}}-\bm{y}_{{\bm{\beta}}}\|u_{{\bm{\beta}}}$
$\displaystyle\text{where}\quad u_{{\bm{\beta}}}$
$\displaystyle\mathrel{\raisebox{-1.29167pt}{$\mathbin{\overset{\text{{def}}}{=}}$}}1+\|\bm{x}_{{\bm{\beta}}}\|_{p}^{p}+\|\bm{y}_{{\bm{\beta}}}\|_{p}^{p}$

for some constants $C,p>0$. By 4.3.4, $(u_{{\bm{\beta}}})_{{\bm{\beta}}}$ form
a moment-bounded tensor $u\in\mathcal{S}_{\mathrm{b}}^{s}$. Thus

$\left\langle|\psi(\bm{x}_{{\bm{\beta}}})-\psi(\bm{y}_{{\bm{\beta}}})|^{2}\right\rangle_{{\bm{\beta}}}\leq
C\left\langle\|\bm{x}_{{\bm{\beta}}}-\bm{y}_{{\bm{\beta}}}\|^{2}u_{{\bm{\beta}}}^{2}\right\rangle_{{\bm{\beta}}}=C\sum_{i=1}^{k}\left\langle(x_{{\bm{\beta}}}^{i}-y_{{\bm{\beta}}}^{i})^{2}u_{{\bm{\beta}}}^{2}\right\rangle_{{\bm{\beta}}}.$

Now fix $i$ and let $v=x^{i}-y^{i}$. By assumption, $v$ is vanishing. We will
show $n^{1-\epsilon}\left\langle
v_{{\bm{\beta}}}^{2}u_{{\bm{\beta}}}^{2}\right\rangle_{{\bm{\beta}}}\xrightarrow{\mathrm{\mathrm{a.s.}}}0$
for any $\epsilon>0$, for any $i$. By the above inequality, this will prove
the desired result. Below, we shall abbreivate
$\langle\bullet_{{\bm{\beta}}}\rangle_{{\bm{\beta}}}$ as just
$\langle\bullet\rangle$.

By Holder’s inequality, for any $q,r>2$ such that $\frac{2}{q}+\frac{2}{r}=1$,
we have

$\left\langle v^{2}u^{2}\right\rangle\leq\left\langle
v^{q}\right\rangle^{2/q}\left\langle u^{r}\right\rangle^{2/r}.$

For any $\epsilon>0$, we shall choose $q$ (and consequently $r$ by the
relation $\frac{2}{q}+\frac{2}{r}=1$) barely larger than 2 such that

$\displaystyle n^{1-\epsilon/2}\left\langle v^{q}\right\rangle^{2/q}$
$\displaystyle\xrightarrow{\mathrm{\mathrm{a.s.}}}0$ (4.2) $\displaystyle
n^{-\epsilon/2}\left\langle u^{r}\right\rangle^{2/r}$
$\displaystyle\xrightarrow{\mathrm{\mathrm{a.s.}}}0$ (4.3)

from which follows $n^{1-\epsilon}\left\langle v^{2}u^{2}\right\rangle$ as we
wanted. Now, Eq. 4.3 holds for any $\epsilon>0$ and $r>0$ because $u$ is
moment-bounded.

For Eq. 4.2, notice 555Here, the definition of “vanishing” in terms of L2 norm
becomes critical, and if we were to define “vanishing” using general Lp norm,
then the proof wouldn’t go through.

$\left\langle v^{q}\right\rangle^{2/q}=n^{-2s/q}\|v\|_{q}^{2}\leq
n^{-2s/q}\|v\|_{2}^{2}=n^{s(1-2/q)}\left\langle v^{2}\right\rangle$

by standard $L^{p}$ norm inequality. We shall choose $q$ just slightly above
$2$ so that $s(1-2/q)<\epsilon/2$. Then $1-\epsilon/2+s(1-2/q)<1-\delta$ for
some positive $\delta>0$ and hence

$n^{1-\epsilon/2}\left\langle v^{q}\right\rangle^{2/q}\leq
n^{1-\epsilon/2+s(1-2/q)}\left\langle
v^{2}\right\rangle<n^{1-\delta}\left\langle
v^{2}\right\rangle\xrightarrow{\mathrm{\mathrm{a.s.}}}0$

where the convergence to 0 is because $v$ is vanishing. ∎

While most nonlinearities we encounter will be pseudo-Lipschitz (globally),
occasionally we need to work with the functions that are only locally
Lipschitz around some point (for example, the matrix inverse function is
locally Lipschitz around a nonsingular matrix). Equivalence to deterministic
constant is preserved under locally Lipschitz mapping:

######  Proposition 4.3.12.

Consider moment-bounded multi-scalar
$\bm{\theta}\in\mathcal{S}_{\mathrm{b}}^{0}\otimes\mathcal{V}$ such that
$\bm{\theta}\equiv\mathring{\bm{\theta}}$ for some deterministic
$\mathring{\bm{\theta}}\in\mathcal{V}$.666Recall this means the random
sequence $\bm{\theta}$ is equivalent to the sequence that equals
$\mathring{\bm{\theta}}$ identically; c.f. 4.2.4. Let
$\psi:\mathcal{V}\to\mathcal{V}^{\prime}$ be locally Lipschitz at
$\mathring{\bm{\theta}}$. Then

$\psi(\bm{\theta})\equiv\psi(\mathring{\bm{\theta}}).$

###### Proof.

WLOG assume $\mathcal{V}=\mathbb{R}^{k}$. Let $U$ be the open neighborhood of
$\mathring{\bm{\theta}}$ in $\mathbb{R}^{k}$ such that $\psi$ is Lipschitz on
$U$ with Lipschitz constant $L$. Almost surely, $\bm{\theta}\in U$ as
$n\to\infty$ because $\bm{\theta}\equiv\mathring{\bm{\theta}}$. Therefore,
almost surely, $\|\psi(\bm{\theta})-\psi(\mathring{\bm{\theta}})\|\leq
L\|\bm{\theta}-\mathring{\bm{\theta}}\|$ as $n\to\infty$. Since
$\bm{\theta}-\mathring{\bm{\theta}}$ is vanishing, we have
$\psi(\bm{\theta})-\psi(\mathring{\bm{\theta}})$ is vanishing as well. ∎

##### Preservation under Averaging

######  Lemma 4.3.13.

Suppose $\bm{x},\bm{y}\in\mathcal{S}_{\mathrm{b}}^{s}\otimes\mathcal{V}$ are
equivalent. With ${\bm{\beta}}$ denoting any subset of indices, let
$\left\langle\bm{x}_{\bullet{\bm{\beta}}}\right\rangle_{{\bm{\beta}}}$ be the
multi-tensor $\bm{x}^{\prime}$ with entries
$\bm{x}^{\prime}_{{\bm{\alpha}}}=\left\langle\bm{x}_{{\bm{\alpha}}{\bm{\beta}}}\right\rangle_{{\bm{\beta}}}$.
Then

1)
$\left\langle\bm{x}_{\bullet{\bm{\beta}}}\right\rangle_{{\bm{\beta}}},\left\langle\bm{y}_{\bullet{\bm{\beta}}}\right\rangle_{{\bm{\beta}}}$
are both moment-bounded;

2) we have

$\left\langle\bm{x}_{\bullet{\bm{\beta}}}\right\rangle_{{\bm{\beta}}}\equiv\left\langle\bm{y}_{\bullet{\bm{\beta}}}\right\rangle_{{\bm{\beta}}}.$

###### Proof.

Note 1) follows easily from Jensen’s inequality. So we shall focus on 2) in
the remainder.

We first make a few simplifications: 1) We assume ${\bm{\beta}}$ is just the
single last index and use the unbolded font $\beta$ instead. The general case
follows from the obvious induction. 2) WLOG we can assume
$\mathcal{V}=\mathbb{R}$ because the general case follows componentwise from
this. We then use unbolded font $x,y$ instead of $\bm{x},\bm{y}$. 3) By
linearity of $\equiv$, it suffices to prove this for $y\equiv 0$ (i.e., $x$
and $y$ are both vanishing).

Let ${\bm{\beta}}^{\prime}=(\beta_{1},\ldots,\beta_{s-1})\in[n]^{s-1}$ denote
the first $s-1$ indices. Then, by power-mean inequality, for every
${\bm{\beta}}^{\prime}$,

$\left\langle
x_{{\bm{\beta}}^{\prime}\beta}\right\rangle_{\beta}^{2}\leq\left\langle
x_{{\bm{\beta}}^{\prime}\beta}^{2}\right\rangle_{\beta}.$

Therefore,

$\left\|\left\langle
x_{\bullet\beta}\right\rangle_{\beta}\right\|^{2}=\sum_{{\bm{\beta}}^{\prime}}\left\langle
x_{{\bm{\beta}}^{\prime}\beta}\right\rangle_{\beta}^{2}\leq
n^{s-1}\left\langle x_{{\bm{\beta}}}^{2}\right\rangle_{{\bm{\beta}}}$

where ${\bm{\beta}}$ ranges over all $[n]^{s}$. Then

$n^{1-\epsilon}\cdot\left\|\left\langle
x_{\bullet\beta}\right\rangle_{\beta}\right\|^{2}/n^{s-1}\leq
n^{1-\epsilon}\left\langle
x_{{\bm{\beta}}}^{2}\right\rangle_{{\bm{\beta}}}\xrightarrow{\mathrm{\mathrm{a.s.}}}0$

where the almost sure convergence is because $x$ is vanishing. Thus we have
$\left\langle x_{\bullet\beta}\right\rangle_{\beta}$ is vanishing, as well. ∎

##### Preservation under Matrix Multiplication

######  Proposition 4.3.14.

Given $n$-vectors $x,y\in\mathcal{S}_{\mathrm{b}}^{1}$ with $x\equiv y$ and an
$n$-matrix $W\in\mathcal{S}_{\mathrm{b}}^{2}$ with almost surely bounded
operator norm, we have

$Wx\equiv Wy,$

no matter how $W$ is correlated with $x$ and $y$.

In particular, this applies when $W(n)=\frac{1}{\sqrt{n}}\mathrm{iid}_{n\times
n}(Z)$ where $Z$ is a sub-Gaussian random variable with zero mean and unit
variance.777We expect this operator norm bound to hold more generally for $Z$
that is zero-mean, unit variance, and has finite fourth moment, due to [48].
But this result assumes the matrices $W(n),n\geq 1$, are upper left blocks of
an infinite iid matrix. It should be possible to relax this assumption in
[48], but since this is not crucial here, we will just leave this task to
future works for which this is more critical.

###### Proof.

The first statement is trivial since the definition of “vanishing” only
depends on $L^{2}$ norm. The second statement follows from well-known operator
norm bounds on iid matrices with sub-Gaussian entries. ∎

####  4.3.4 Distributional Equivalence (aka Dequivalence)

We will also need the distributional version of equivalence. In the simplest
case, we have the following definition.

######  Definition 4.3.15.

For any multi-tensor $\bm{x},\bm{y}$ of the same shape, we say $\bm{x}$ and
$\bm{y}$ are _distributionally equivalent, or dequivalent_ , written

$\bm{x}\overset{\mathrm{d}}{\equiv}\bm{y},$

if there exist multi-tensors $\hat{\bm{x}},\hat{\bm{y}}$ with
$\hat{\bm{x}}\equiv\bm{x}$ and $\hat{\bm{y}}\equiv\bm{y}$ such that
$\hat{\bm{x}}\overset{\mathrm{d}}{=}\hat{\bm{y}}$.

Like for equivalence, $\bm{x}\overset{\mathrm{d}}{\equiv}\bm{y}$ is a notion
between multi-tensors as sequences, i.e., it should be read as
$\\{\bm{x}(n)\\}_{n}\overset{\mathrm{d}}{\equiv}\\{\bm{y}(n)\\}_{n}$, NOT as a
sequence of equivalences $\bm{x}(n)\overset{\mathrm{d}}{\equiv}\bm{y}(n)$, one
for each $n$.

However, note that, contrary to equality, distributional equality in general
is not reducible componentwise:
$(x^{1},x^{2})\overset{\mathrm{d}}{=}(y^{1},y^{2})$ is usually stronger than
the conjunction of $x^{1}\overset{\mathrm{d}}{=}y^{1}$ and
$x^{2}\overset{\mathrm{d}}{=}y^{2}$. Thus, we need to define a more general
notion of distributional equivalence of list of objects.

######  Definition 4.3.16.

Suppose we have two lists of multi-tensors $\bm{x}^{1},\ldots,\bm{x}^{r}$ and
$\bm{y}^{1},\ldots,\bm{y}^{r}$, such that $x^{t}$ and $\bm{y}^{t}$ have the
same shape for every $t$, but their shapes can vary with $t$. We say
$\left(\bm{x}^{1},\ldots,\bm{x}^{r}\right)$ and
$\left(\bm{y}^{1},\ldots,\bm{y}^{r}\right)$ are _distributionally equivalent,_
written

$\left(\bm{x}^{1},\ldots,\bm{x}^{r}\right)\overset{\mathrm{d}}{\equiv}\left(\bm{y}^{1},\ldots,\bm{y}^{r}\right),$

if there exist $\hat{\bm{x}}^{t}\equiv\bm{x}^{t}$,
$\hat{\bm{y}}^{t}\equiv\bm{y}^{t}$ for all $t\in[r]$ such that
$(\hat{\bm{x}}^{1},\ldots,\hat{\bm{x}}^{r})\overset{\mathrm{d}}{=}(\hat{\bm{y}}^{1},\ldots,\hat{\bm{y}}^{r})$.

This definition is especially necessary for reasoning about the Gaussian
conditioning trick inside the induction proof of the Master Theorem.

Finally, we note that, while 4.3.16 seems to be strictly more general than
4.3.15, in fact they are logically equivalent:

$\left(\bm{x}^{1},\ldots,\bm{x}^{r}\right)\overset{\mathrm{d}}{\equiv}\left(\bm{y}^{1},\ldots,\bm{y}^{r}\right)\iff\left(\bm{x}^{1};\cdots;\bm{x}^{r}\right)\overset{\mathrm{d}}{\equiv}\left(\bm{y}^{1};\cdots;\bm{y}^{r}\right)$
(4.4)

where the RHS uses 4.3.15 on semicolon products.888When $\bm{x}^{t}$ all have
the same number of $n$-dimensions, then
$\left(\bm{x}^{1},\ldots,\bm{x}^{r}\right)\overset{\mathrm{d}}{\equiv}\left(\bm{y}^{1},\ldots,\bm{y}^{r}\right)$
can be interpreted as distributional equivalence ala 4.3.15 of two multi-
tensors fromed from concatenation. But in general $\bm{x}^{t}$ have different
number of $n$-dimensions for different $t$, where the semicolon product still
applies. Nevertheless, we explicitly formulated 4.3.16 as it is more
transparent.

As discussed above,
$(\bm{z},\bm{x})\overset{\mathrm{d}}{\equiv}(\bm{z}^{\prime},\bm{y})$ is
strictly stronger than the conjunction of
$\bm{z}\overset{\mathrm{d}}{\equiv}\bm{z}^{\prime}$ and
$\bm{x}\overset{\mathrm{d}}{\equiv}y$. However, they are logically equivalent
if we replace $\bm{x}\overset{\mathrm{d}}{\equiv}y$ with the _conditional
dequivalence $\bm{x}\overset{\mathrm{d}}{\equiv}_{R}\bm{y}$, _as defined
below, where $R$ is the relation
$\bm{z}\overset{\mathrm{d}}{\equiv}\bm{z}^{\prime}$.

######  Definition 4.3.17 (Conditional distributional equivalence).

The expression $R:\bm{z}\overset{\mathrm{d}}{\equiv}\bm{z}^{\prime}$ means “we
give the relation $\bm{z}\overset{\mathrm{d}}{\equiv}\bm{z}^{\prime}$ the name
$R$.” In this case, we define $\bm{x}\overset{\mathrm{d}}{\equiv}_{R}\bm{y}$
to mean $(\bm{z},\bm{x})\overset{\mathrm{d}}{\equiv}(\bm{z}^{\prime},\bm{y})$.
This is called a _conditional dequivalence_.

More generally, if
$R:\bm{z}\overset{\mathrm{d}}{\equiv}_{R^{\prime}}\bm{z}^{\prime}$ is itself a
conditional equivalence, we recursively define
$\bm{x}\overset{\mathrm{d}}{\equiv}_{R}\bm{y}$ to mean
$(\bm{z},\bm{x})\overset{\mathrm{d}}{\equiv}_{R^{\prime}}(\bm{z}^{\prime},\bm{y})$.
Finally, when $R=\emptyset$ is the empty relation (equivalence of nothing to
nothing), we define $\bm{x}\overset{\mathrm{d}}{\equiv}_{R}\bm{y}$ as just the
unconditional dequivalence $\bm{x}\overset{\mathrm{d}}{\equiv}\bm{y}$.

For example, we may recursively write
$R_{0}:\bm{x}_{0}\overset{\mathrm{d}}{\equiv}\bm{y}_{0}$ and
$R_{i}:\bm{x}_{i}\overset{\mathrm{d}}{\equiv}_{R_{i-1}}\bm{y}_{i}$. Then the
conditional dequivalence $R_{i}$ can be unpacked into
$(\bm{x}_{0},\ldots,\bm{x}_{i})\overset{\mathrm{d}}{\equiv}(\bm{y}_{0},\ldots,\bm{y}_{i})$.

##### Wasserstein Distance Interpretation

For two multi-tensors $\bm{x},\bm{y}$ of the same shape, thought of as
sequences $\\{\bm{x}(n)\\}_{n},\\{\bm{y}(n)\\}_{n}$, we may form a new
sequence $W_{2}(\bm{x},\bm{y})$ of their Wasserstein distances
$\\{W_{2}(\mathcal{D}_{\bm{x}(n)},\mathcal{D}_{\bm{y}(n)})\\}_{n}$, where
$W_{2}$’s underlying metric for each $n$ is the scaled Euclidean distance
$d(\mathbf{x},\mathbf{y})=\sqrt{\langle\|\mathbf{x}_{\bm{\alpha}}-\mathbf{y}_{\bm{\alpha}}\|^{2}\rangle_{\bm{\alpha}}},$
and $\mathcal{D}_{\bm{x}(n)},\mathcal{D}_{\bm{y}(n)}$ denote the measures of
$\bm{x}(n),\bm{y}(n)$. Then,

$\text{morally,}\quad\bm{x}\overset{\mathrm{d}}{\equiv}\bm{y}\iff
W_{2}(\bm{x},\bm{y})=\tilde{O}(n^{-1/2}).$

This is not exactly rigorous because Wasserstein distance is defined using
_expected movement_ while equivalence is defined using an _almost sure_ notion
of “vanishing.” This is a technical issue that can be sidestepped if one were
to define $\tilde{O}$ using convergence of expectations rather than almost
sure. Since we will not actually use this Wasserstein distance interpretation
in this work, we will not attempt to make this more formal. This connection is
purely to aid the reader’s intuitive understanding.

##### Basic Properties

Conditional dequivalence naturally inherits the basic properties of
equivalence. Consider any conditional dequivalence named $R$. In summary,
conditional dequivalence is preserved under:

  1. 1.

“smooth” mapping $\phi$: (4.3.18)

    1. (a)

For example, if $R^{\prime}:\bm{x}\overset{\mathrm{d}}{\equiv}_{R}\bm{y}$ are
all moment-bounded, then
$\phi(\bm{x})\overset{\mathrm{d}}{\equiv}_{R^{\prime}}\phi(\bm{y})$. This
holds more generally for “smooth” nonlinear outer products.

  2. 2.

averaging over $[n]$: (Lemma 4.3.19)

    1. (a)

If $R^{\prime}:\bm{x}\overset{\mathrm{d}}{\equiv}_{R}\bm{y}$, then
$\langle\bm{x}_{\bullet{\bm{\beta}}}\rangle_{{\bm{\beta}}}\overset{\mathrm{d}}{\equiv}_{R^{\prime}}\langle\bm{y}_{\bullet{\bm{\beta}}}\rangle_{{\bm{\beta}}}$.

  3. 3.

multiplication by operator-normed-bounded matrices: (4.3.20)

    1. (a)

If $x,y$ are $n$-vectors with $R^{\prime}:x\overset{\mathrm{d}}{\equiv}_{R}y$
and $W$ is an $n$-matrix that almost surely has bounded operator norm, then
$Wx\equiv_{R^{\prime}}Wy$. This holds in particular for $W$ having iid, zero-
mean entries of size $\Theta(1/\sqrt{n})$.

The formal statements are as follows. The proofs are all trivial given the
corresponding statements in Section 4.3.3.

######  Proposition 4.3.18.

Consider multi-tensors
$\bm{x}^{t},\bm{y}^{t}\in\mathcal{S}_{\mathrm{b}}^{s_{t}}\otimes\mathcal{V}_{t}$
for each $t=1,\ldots,r$ and a function
$\psi(-;\cdots;-):\mathcal{V}_{1}\oplus\cdots\oplus\mathcal{V}_{t}\to\mathcal{V}^{\prime}$.
Let $R$ be any dequivalence. If $\psi$ is pseudo-Lipschitz and
$R^{\prime}:(\bm{x}^{1},\ldots,\bm{x}^{r})\overset{\mathrm{d}}{\equiv}_{R}(\bm{y}^{1},\ldots,\bm{y}^{r})$,
then

$\psi(\bm{x}^{1};\cdots;\bm{x}^{r})\overset{\mathrm{d}}{\equiv}_{R^{\prime}}\psi(\bm{y}^{1};\cdots;\bm{y}^{r}).$

######  Lemma 4.3.19.

Suppose $\bm{x},\bm{y}\in\mathcal{S}_{\mathrm{b}}^{s}\otimes\mathcal{V}$
satisfy $R^{\prime}:\bm{x}\overset{\mathrm{d}}{\equiv}_{R}\bm{y}$ for some
dequivalence $R$. Then, with ${\bm{\beta}}$ denoting any subset of indices,

$\left\langle\bm{x}_{\bullet{\bm{\beta}}}\right\rangle_{{\bm{\beta}}}\overset{\mathrm{d}}{\equiv}_{R^{\prime}}\left\langle\bm{y}_{\bullet{\bm{\beta}}}\right\rangle_{{\bm{\beta}}},$

where $\left\langle\bm{x}_{\bullet{\bm{\beta}}}\right\rangle_{{\bm{\beta}}}$
is the multi-tensor $\bm{x}^{\prime}$ with entries
$\bm{x}^{\prime}_{{\bm{\alpha}}}=\left\langle\bm{x}_{{\bm{\alpha}}{\bm{\beta}}}\right\rangle_{{\bm{\beta}}}$,
and likewise for
$\left\langle\bm{y}_{\bullet{\bm{\beta}}}\right\rangle_{{\bm{\beta}}}$.

######  Proposition 4.3.20.

Given an $n$-matrix $W\in\mathcal{S}_{\mathrm{b}}^{2}$ with almost surely
bounded operator norm and $n$-vectors $x,y\in\mathcal{S}_{\mathrm{b}}^{1}$
with
$R:x\overset{\mathrm{d}}{\equiv}_{W}y$,999$x\overset{\mathrm{d}}{\equiv}_{W}y$
means dequivalence conditional on the trivial equivalence
$W\overset{\mathrm{d}}{\equiv}W$. we have

$Wx\overset{\mathrm{d}}{\equiv}_{R}Wy.$

In particular, this applies when $W(n)=\frac{1}{\sqrt{n}}\mathrm{iid}_{n\times
n}(Z)$ where $Z$ is a random variable with zero mean, unit variance, and
finite fourth moment.

###  4.4 Getting Equivalence From Distributional Equivalence

Here we discuss several situations, in order of easy to hard, that allow us to
“upgrade” dequivalence to equivalence. The most important result (Lemma 4.4.5)
in this section reads roughly as follows: If $\bm{x}$ is iid along the
$n$-dimensions, then
$\langle\phi(\bm{x};\bm{x}_{\beta_{1}};\cdots;\bm{x}_{\beta_{r}})\rangle_{{\bm{\beta}}}\equiv\langle\phi(\bm{x};\bm{x}_{\beta_{1}}^{\mathord{\ThisStyle{\LMpt\kern
1.0pt\LMpt\framebox{$\SavedStyle 1$}\kern
1.0pt\LMpt}}};\cdots;\bm{x}_{\beta_{r}}^{\mathord{\ThisStyle{\LMpt\kern
1.0pt\LMpt\framebox{$\SavedStyle r$}\kern
1.0pt\LMpt}}})\rangle_{{\bm{\beta}}}$ (where, recall, for each $i$,
$\bm{x}^{\mathord{\ThisStyle{\LMpt\kern 1.0pt\LMpt\framebox{$\SavedStyle
i$}\kern 1.0pt\LMpt}}}$ is an iid copy of $\bm{x}$, such that
$\bm{x},\bm{x}^{\mathord{\ThisStyle{\LMpt\kern
1.0pt\LMpt\framebox{$\SavedStyle 1$}\kern
1.0pt\LMpt}}},\ldots,\bm{x}^{\mathord{\ThisStyle{\LMpt\kern
1.0pt\LMpt\framebox{$\SavedStyle r$}\kern 1.0pt\LMpt}}}$ are mutually
independent).

###### Trivial Conversion

Sometimes, we can directly convert $\overset{\mathrm{d}}{\equiv}$ to $\equiv$:

######  Proposition 4.4.1.

If $\bm{x}\overset{\mathrm{d}}{\equiv}\bm{y}$ and, for each $n$, $\bm{y}(n)$
is deterministic, then $\bm{x}\equiv\bm{y}$.

###### Proof.

This just follows from that fact that, for any random vectors $\bm{X}$ and
$\bm{Y}$, if $\bm{X}\overset{\mathrm{d}}{=}\bm{Y}$ and $\bm{Y}$ is
deterministic, then $\bm{X}\overset{\text{a.s.}}{=}\bm{Y}$. ∎

###### Easy Conversion

In other times, two objects formed from dequivalent ingredients are actually
(absolutely) equivalent. This happens typically when we are averaging over
many iid things, essentially because of the Law of Large Numbers. The most
basic example is:

######  Lemma 4.4.2.

Let $Z\in\mathbb{R}$ be a random variable for whom moments of every order
exists. Then, as elements of $\mathcal{S}_{\mathrm{b}}^{0}$,

$\left\langle\mathrm{iid}(Z)_{\alpha}\right\rangle_{\alpha}\equiv\operatorname*{\mathbb{E}}Z.$

Here $\mathrm{iid}(Z)$ is only well-defined up to distributional equality, so
what we mean here is: whenever $z\overset{\mathrm{d}}{\equiv}\mathrm{iid}(Z)$,
we have $\left\langle
z_{\alpha}\right\rangle_{\alpha}\equiv\operatorname*{\mathbb{E}}Z.$ In other
words, if
$z\overset{\mathrm{d}}{\equiv}z^{\prime}\overset{\mathrm{d}}{\equiv}\mathrm{iid}(Z)$,
then we in fact have $\langle z_{\alpha}\rangle_{\alpha}\equiv\langle
z^{\prime}_{\alpha}\rangle_{\alpha}$, not just $\overset{\mathrm{d}}{\equiv}$
as from Lemma 4.3.19.

###### Proof.

WLOG assume $\operatorname*{\mathbb{E}}Z=0$. Then because $Z$ has moments of
every order, by Lemma 4.1.3,
$Y\mathrel{\raisebox{-1.29167pt}{$\mathbin{\overset{\text{{def}}}{=}}$}}\frac{1}{\sqrt{n}}\sum_{\alpha}\mathrm{iid}(Z)_{\alpha}$
has moments of every order $p$ bounded by some constant $C_{p}$ independent of
$n$. To show
$\left\langle\mathrm{iid}(Z)_{\alpha}\right\rangle_{\alpha}=\frac{1}{\sqrt{n}}Y$
is vanishing, we need to show that for every $\epsilon>0$,
$n^{1-\epsilon}\left\langle\mathrm{iid}(Z)_{\alpha}\right\rangle_{\alpha}^{2}=n^{-\epsilon}Y^{2}\xrightarrow{\mathrm{\mathrm{a.s.}}}0$.
But $\operatorname*{\mathbb{E}}|n^{-\epsilon}Y^{2}|^{p}\leq C_{2p}n^{-\epsilon
p}$ for every $p>0$. In particular, taking $p>1/\epsilon$, we can apply Lemma
4.1.2 to get the desired result. ∎

For example, we will frequently use the following corollary of this:

######  Lemma 4.4.3.

If $\bm{x}\in\mathcal{S}_{\mathrm{b}}^{1}\otimes\mathbb{R}^{k}$ and
$\bm{y}\in\mathcal{S}_{\mathrm{b}}^{1}\otimes\mathbb{R}^{l}$ satisfy
$(\bm{x},\bm{y})\overset{\mathrm{d}}{\equiv}\mathrm{iid}(\bm{X},\bm{Y})$ for
random vectors $\bm{X}\in\mathbb{R}^{k},\bm{Y}\in\mathbb{R}^{l}$ with finite
joint moments of every order, then

$\frac{1}{n}\bm{x}^{\top}\bm{y}\equiv\operatorname*{\mathbb{E}}\bm{X}\bm{Y}^{\top}\in\mathbb{R}^{k\times
l}.$

In other words, the RHS has entries $\operatorname*{\mathbb{E}}X^{i}Y^{j}$ for
each $i\in[k],j\in[l]$.

###### Proof.

The $(i,j)$th entry of $\frac{1}{n}\bm{x}^{\top}\bm{y}$ is just $\langle
x_{\alpha}^{i}y_{\alpha}^{j}\rangle_{\alpha}\overset{\mathrm{d}}{\equiv}\langle\mathrm{iid}(X^{i}Y^{j})_{\alpha}\rangle_{\alpha}$
which is equivalent to $\operatorname*{\mathbb{E}}X^{i}Y^{j}$ by Lemma 4.4.2.
Then we can upgrade this to equivalence by 4.4.1:
$(\frac{1}{n}\bm{x}^{\top}\bm{y})^{ij}\equiv\operatorname*{\mathbb{E}}X^{i}Y^{j}$,
as desired. ∎

###### Medium Conversion

For our main theorem involving nonlinear outer products, we need the following
(much stronger) generalization of Lemma 4.4.2, which roughly says
$\langle\psi(\bm{x};\mathrm{iid}(\bm{Z})_{\alpha})\rangle_{\alpha}\equiv\operatorname*{\mathbb{E}}_{\bm{Z}}\psi(\bm{x};\bm{Z})$
in the simplest case.

######  Lemma 4.4.4.

Let $\bm{x}\in\mathcal{S}_{\mathrm{b}}^{s_{0}}\otimes\mathcal{V}_{0}$ be
moment-bounded. For each $t=1,\ldots,r$, let $\bm{Z}^{t}\in\mathcal{V}_{t}$ be
a (fixed-dimensional) random vector whose moments exist for all orders. Assume
$\bm{Z}^{1},\ldots,\bm{Z}^{r}$ are all mutually independent. For each $t$,
define $s_{t}\geq 1$ and
$\bm{z}^{t}\in\mathcal{S}^{s_{t}}\otimes\mathcal{V}_{t}$ such that
$\bm{z}^{t}\overset{\mathrm{d}}{=}\mathrm{iid}^{s_{t}}(\bm{Z}^{t})$. Assume
$\bm{x},\bm{z}^{1},\ldots,\bm{z}^{r}$ are mutually independent. Let
$\psi:\mathcal{V}_{0}\oplus\cdots\oplus\mathcal{V}_{r}\to\mathcal{V}^{\prime}$
be a pseudo-Lipschitz function. Then, with ${\bm{\beta}}_{t}\in[n]^{s_{t}}$
and ${\bm{\beta}}={\bm{\beta}}_{1}\cdots{\bm{\beta}}_{r}$,

$\left\langle\psi(\bm{x};\bm{z}_{{\bm{\beta}}_{1}}^{1};\cdots;\bm{z}_{{\bm{\beta}}_{r}}^{r})\right\rangle_{{\bm{\beta}}}\equiv\Psi(\bm{x})\in\mathcal{S}_{\mathrm{b}}^{s_{0}}\otimes\mathcal{V}^{\prime}$

where

$\Psi:\mathcal{V}_{0}\to\mathcal{V}^{\prime},\quad\Psi(\xi)\mathrel{\raisebox{-1.29167pt}{$\mathbin{\overset{\text{{def}}}{=}}$}}\operatorname*{\mathbb{E}}\psi(\xi;\bm{Z}^{1};\cdots;\bm{Z}^{r}),$

where the expectation is taken over $\bm{Z}^{1},\ldots,\bm{Z}^{r}$.

As discussed above, this implies

$\left\langle\psi(\bm{x};\bm{z}_{{\bm{\beta}}_{1}}^{1};\cdots;\bm{z}_{{\bm{\beta}}_{r}}^{r})\right\rangle_{{\bm{\beta}}}\equiv\left\langle\psi(\bm{x};\bm{z}_{{\bm{\beta}}_{1}}^{1\mathord{\ThisStyle{\LMpt\kern
1.0pt\LMpt\framebox{$\SavedStyle 1$}\kern
1.0pt\LMpt}}};\cdots;\bm{z}_{{\bm{\beta}}_{r}}^{r\mathord{\ThisStyle{\LMpt\kern
1.0pt\LMpt\framebox{$\SavedStyle 1$}\kern
1.0pt\LMpt}}})\right\rangle_{{\bm{\beta}}},$ (4.5)

which is an upgrade over the $\overset{\mathrm{d}}{\equiv}$ from Lemma 4.3.19.

###### Proof.

WLOG assume $\mathcal{V}^{\prime}=\mathbb{R}$ since the general case follows
from this componentwise. Furthermore, we will assume $r=1$ because the general
case follows from this by induction. Let

$\bar{\psi}(\xi;\zeta^{1})\mathrel{\raisebox{-1.29167pt}{$\mathbin{\overset{\text{{def}}}{=}}$}}\psi(\xi;\zeta^{1})-\Psi(\xi).$

Then for any $\xi$, $\bar{\psi}(\xi;\bm{Z}^{1})$ has mean zero (over the
randomness of $\bm{Z}^{1}$). Let

$y\mathrel{\raisebox{-1.29167pt}{$\mathbin{\overset{\text{{def}}}{=}}$}}\left\langle\bar{\psi}(\bm{x};\bm{z}_{{\bm{\beta}}_{1}}^{1})\right\rangle_{{\bm{\beta}}_{1}}\in\mathcal{S}_{\mathrm{b}}^{s_{0}}.$

We want to show $y$ is vanishing.

Notationally, we have usually written $\bm{x}$ when we really mean
$\bm{x}(n)$, the $n$th element of $\bm{x}$ as sequence of tensors. This is not
ambiguous typically, but here we do want to talk about both semantics.
Therefore, in this proof, we will be explicit: for emphasis, we write
$\bm{x}[1,\infty)=\\{x(n)\\}_{n=1}^{\infty}$ for the sequence interpretation
and still write just “$\bm{x}$” for the $n$th element of it (with dependence
on $n$ suppressed as usual).

Now, we will prove $y$ is vanishing by showing that, with probability 1 on the
distribution of $\bm{x}[1,\infty)$, $y$ is vanishing conditioned on
$\bm{x}[1,\infty)$.

By Lemma 4.1.3 applied to
$\bar{\psi}(\bm{x}_{{\bm{\alpha}}};\bm{z}_{{\bm{\beta}}_{1}}^{1})$ with fixed
${\bm{\alpha}}$ (using the independence of $\bm{z}^{1}$ from $\bm{x}$), we
have

$\operatorname*{\mathbb{E}}[y_{{\bm{\alpha}}}^{2p}|\bm{x}_{{\bm{\alpha}}}]\leq
D_{p}(\bm{x}_{{\bm{\alpha}}})n^{-ps_{1}}\leq
D_{p}(\bm{x}_{{\bm{\alpha}}})n^{-p}$

for some polynomially-bounded function $D_{p}:\mathcal{V}_{0}\to\mathbb{R}$
independent of ${\bm{\alpha}}$. (More specifically,
$D_{p}(\bm{x}_{{\bm{\alpha}}})$ is a polynomial in the moments of the random
variable $\psi(\bm{x}_{{\bm{\alpha}}};\bm{Z}^{1})$ conditioned on
$\bm{x}_{{\bm{\alpha}}}$, which are themselves polynomially bounded functions
of $\bm{x}_{{\bm{\alpha}}}$). Here we used the assumption that $s_{1}\geq 1$
in the 2nd inequality. Then

$\operatorname*{\mathbb{E}}\left[\left\langle
y_{{\bm{\alpha}}}^{2p}\right\rangle_{{\bm{\alpha}}}\mid\bm{x}\right]=\left\langle\operatorname*{\mathbb{E}}[y_{{\bm{\alpha}}}^{2p}|\bm{x}_{{\bm{\alpha}}}]\right\rangle_{{\bm{\alpha}}}\leq
n^{-p}\left\langle
D_{p}(\bm{x}_{{\bm{\alpha}}})\right\rangle_{{\bm{\alpha}}}.$

Because $\bm{x}$ is moment-bounded, so is $\left\langle
D_{p}(\bm{x}_{{\bm{\alpha}}})\right\rangle_{{\bm{\alpha}}}\in\mathcal{S}^{0}$,
so that, for every $\varepsilon>0$,

$n^{-\varepsilon}\left\langle
D_{p}(\bm{x}_{{\bm{\alpha}}})\right\rangle_{{\bm{\alpha}}}\xrightarrow{\mathrm{\mathrm{a.s.}}}0.$

Thus, for almost every sequence $\bm{x}[1,\infty)$,

$n^{-\varepsilon}\left\langle
D_{p}(\bm{x}_{{\bm{\alpha}}})\right\rangle_{{\bm{\alpha}}}\leq
C_{p,\varepsilon}(\bm{x}[1,\infty))\quad\text{for all $n$}$

for some constant $C_{p,\varepsilon}(\bm{x}[1,\infty))$ dependent on the whole
sequence $\bm{x}[1,\infty)$. Then

$n^{-\varepsilon}\operatorname*{\mathbb{E}}\left[\left\langle
y_{{\bm{\alpha}}}^{2p}\right\rangle_{{\bm{\alpha}}}\mid\bm{x}[1,\infty)\right]\leq
C_{p,\varepsilon}(\bm{x}[1,\infty))n^{-p}\quad\text{for all $n$}$

satisfying 4.3.8, implying $y$ is vanishing conditioned on $\bm{x}[1,\infty)$.
Since this argument holds for every $\bm{x}[1,\infty)$ and every
$\varepsilon>0$, we have the desired result. ∎

###### Advanced Conversion

In the most advanced case, we need Eq. 4.5 to hold even when the $\bm{x}$ and
$\bm{z}^{i}$ are strongly correlated. This will turn out to be the most
important case, since it forms the induction base for our main theorem.

######  Lemma 4.4.5 (IID Equivalence).

Let $\bm{X}\in\mathbb{R}^{k}$ be a random vector whose moments exist for all
orders. Let $\bm{x}\in\mathcal{S}_{\mathrm{b}}^{1}\otimes\mathbb{R}^{k}$
satisfy $\bm{x}\overset{\mathrm{d}}{\equiv}\mathrm{iid}(\bm{X})$. Let
$\bm{c}\in\mathcal{S}_{\mathrm{b}}^{0}\otimes\mathbb{R}^{l}$ be such that
$\bm{c}\equiv\mathring{\bm{c}}$ for some deterministic
$\mathring{\bm{c}}\in\mathbb{R}^{l}$.

Let $\psi:(\oplus^{s+r}\mathbb{R}^{k})\oplus\mathbb{R}^{l}\to\mathbb{R}$ be
pseudo-Lipschitz. Then, with
${\bm{\beta}}=(\beta_{1},\ldots,\beta_{r})$,101010The iid copies
$\bm{x}^{\mathord{\ThisStyle{\LMpt\kern 1.0pt\LMpt\framebox{$\SavedStyle
1$}\kern 1.0pt\LMpt}}},\ldots,\bm{x}^{\mathord{\ThisStyle{\LMpt\kern
1.0pt\LMpt\framebox{$\SavedStyle r$}\kern 1.0pt\LMpt}}}$ are only well-defined
up to distributional equality, so Eq. 4.6 should be read as: for _any_
instantiation of $\bm{x}^{\mathord{\ThisStyle{\LMpt\kern
1.0pt\LMpt\framebox{$\SavedStyle 1$}\kern
1.0pt\LMpt}}},\ldots,\bm{x}^{\mathord{\ThisStyle{\LMpt\kern
1.0pt\LMpt\framebox{$\SavedStyle r$}\kern 1.0pt\LMpt}}}$, the equivalence
holds.

$\langle\psi(\bm{x};\cdots;\bm{x};\bm{x}_{\beta_{1}};\cdots;\bm{x}_{\beta_{r}};\bm{c})\rangle_{{\bm{\beta}}}\equiv\langle\psi(\bm{x};\cdots;\bm{x};\bm{x}_{\beta_{1}}^{\mathord{\ThisStyle{\LMpt\kern
1.0pt\LMpt\framebox{$\SavedStyle 1$}\kern
1.0pt\LMpt}}};\cdots;\bm{x}_{\beta_{r}}^{\mathord{\ThisStyle{\LMpt\kern
1.0pt\LMpt\framebox{$\SavedStyle r$}\kern
1.0pt\LMpt}}};\mathring{\bm{c}})\rangle_{{\bm{\beta}}}$ (4.6)

as elements of $\mathcal{S}_{\mathrm{b}}^{s}$ (where, recalling 4.2.5,
$\bm{x}^{\mathord{\ThisStyle{\LMpt\kern 1.0pt\LMpt\framebox{$\SavedStyle
1$}\kern 1.0pt\LMpt}}},\ldots,\bm{x}^{\mathord{\ThisStyle{\LMpt\kern
1.0pt\LMpt\framebox{$\SavedStyle r$}\kern 1.0pt\LMpt}}}$ are iid copies of
$\mathrm{iid}(\bm{X})$, independent from $\bm{x}$).

We in fact don’t need to assume $\mathring{c}$ is deterministic, but doing so
simplifies the proof.

We remind the reader the notations in Eq. 4.6. To be very explicit, if $s=1$
and
$T=\langle\psi(\bm{x};\bm{x}_{\beta_{1}};\cdots;\bm{x}_{\beta_{r}};\bm{c})\rangle_{{\bm{\beta}}}\in\mathcal{S}_{\mathrm{b}}^{1}$,
then each entry $T_{\alpha}$ is

$T_{\alpha}=\frac{1}{n^{r}}\sum_{\beta_{1},\ldots,\beta_{r}}\psi(x_{\alpha}^{1},\ldots,x_{\alpha}^{k}\
;\ x_{\beta_{1}}^{1},\ldots,x_{\beta_{1}}^{k}\ ;\ \cdots\ ;\
x_{\beta_{r}}^{1},\ldots,x_{\beta_{r}}^{k}\ ;\ c^{1},\ldots,c^{l}).$ (4.7)

Likewise for
$\langle\psi(\bm{x};\bm{x}_{\beta_{1}}^{\mathord{\ThisStyle{\LMpt\kern
1.0pt\LMpt\framebox{$\SavedStyle 1$}\kern
1.0pt\LMpt}}};\cdots;\bm{x}_{\beta_{r}}^{\mathord{\ThisStyle{\LMpt\kern
1.0pt\LMpt\framebox{$\SavedStyle r$}\kern
1.0pt\LMpt}}};\mathring{\bm{c}})\rangle_{{\bm{\beta}}}$.

Intuitively, when all the $\beta_{1},\ldots,\beta_{r}$ are distinct, then
$\bm{x}_{\beta_{1}},\ldots,\bm{x}_{\beta_{r}}$ are roughly independent as
well, but this is obviously not the case when $\beta_{1},\ldots,\beta_{r}$ are
not distinct. However, among all possible values of the tuple
$(\beta_{1},\ldots,\beta_{r})$, the nondistinct ones constitute a minority,
vanishing with $n$. Therefore, we hope to say that they contribute vanishingly
to the sum Eq. 4.7 so as to establish Eq. 4.6.

By combining with Lemma 4.4.4, we get

######  Lemma 4.4.6.

In the same scenario as Lemma 4.4.5, if $s=1$, then

$\langle\psi(\bm{x};\bm{x}_{\beta_{1}};\cdots;\bm{x}_{\beta_{r}};\bm{c})\rangle_{{\bm{\beta}}}\equiv\Psi(\bm{x})$

where

$\Psi:\mathbb{R}^{k}\to\mathbb{R},\quad\Psi(\mathbf{x})\mathrel{\raisebox{-1.29167pt}{$\mathbin{\overset{\text{{def}}}{=}}$}}\operatorname*{\mathbb{E}}_{\mathord{\ThisStyle{\LMpt\kern
1.0pt\LMpt\framebox{$\SavedStyle 1$}\kern
1.0pt\LMpt}},\ldots,\mathord{\ThisStyle{\LMpt\kern
1.0pt\LMpt\framebox{$\SavedStyle r$}\kern
1.0pt\LMpt}}}\psi(\mathbf{x};\bm{X}^{\mathord{\ThisStyle{\LMpt\kern
1.0pt\LMpt\framebox{$\SavedStyle 1$}\kern
1.0pt\LMpt}}};\cdots;\bm{X}^{\mathord{\ThisStyle{\LMpt\kern
1.0pt\LMpt\framebox{$\SavedStyle r$}\kern
1.0pt\LMpt}}};\mathring{\bm{c}}),\forall\mathbf{x}\in\mathbb{R}^{k},$

(with the expectation taken over $\bm{X}^{\mathord{\ThisStyle{\LMpt\kern
1.0pt\LMpt\framebox{$\SavedStyle 1$}\kern
1.0pt\LMpt}}};\cdots;\bm{X}^{\mathord{\ThisStyle{\LMpt\kern
1.0pt\LMpt\framebox{$\SavedStyle r$}\kern 1.0pt\LMpt}}}$).

####  4.4.1 Proof of Lemma 4.4.5

##### Preliminary Reduction and Setup

We assume in the proof that $s=1$, as the general case is a straightforward
modification.

WLOG, we can assume $\bm{x}$ is an iid copy of $\mathrm{iid}(\bm{X})$ by
4.3.11. Applying 4.3.11 again to $\bm{c}$, we see

$\psi(\bm{x};\bm{x};\cdots;\bm{x};\bm{c})\equiv\psi(\bm{x};\bm{x};\cdots;\bm{x};\mathring{\bm{c}}).$

So we can assume WLOG $\bm{c}=\mathring{c}$ and furthermore just absorb it
into $\psi$ since $\mathring{\bm{c}}$ is deterministic. It remains to show

$\langle\psi(\bm{x};\bm{x}_{\beta_{1}};\cdots;\bm{x}_{\beta_{r}})\rangle_{{\bm{\beta}}}\equiv\langle\psi(\bm{x};\bm{x}_{\beta_{1}}^{\mathord{\ThisStyle{\LMpt\kern
1.0pt\LMpt\framebox{$\SavedStyle 1$}\kern
1.0pt\LMpt}}};\cdots;\bm{x}_{\beta_{r}}^{\mathord{\ThisStyle{\LMpt\kern
1.0pt\LMpt\framebox{$\SavedStyle r$}\kern
1.0pt\LMpt}}})\rangle_{{\bm{\beta}}}.$

Let $\Delta\in\mathcal{S}_{\mathrm{b}}^{r+1}$ be the tensor

$\Delta_{\alpha{\bm{\beta}}}=\Delta_{\alpha\beta_{1}\cdots\beta_{r}}=\psi(\bm{x}_{\alpha};\bm{x}_{\beta_{1}};\cdots;\bm{x}_{\beta_{r}})-\psi(\bm{x}_{\alpha};\bm{x}_{\beta_{1}}^{\mathord{\ThisStyle{\LMpt\kern
1.0pt\LMpt\framebox{$\SavedStyle 1$}\kern
1.0pt\LMpt}}};\cdots;\bm{x}_{\beta_{r}}^{\mathord{\ThisStyle{\LMpt\kern
1.0pt\LMpt\framebox{$\SavedStyle r$}\kern 1.0pt\LMpt}}}).$

Note the following properties of $\Delta$:

######  Proposition 4.4.7.

1) If $\alpha$ does not appear in ${\bm{\beta}}$ and all indices in
${\bm{\beta}}$ are distinct, then
$\operatorname*{\mathbb{E}}\Delta_{\alpha{\bm{\beta}}}=0$. 2) If
${\bm{\beta}}^{\prime}$ is another multi-index with the same property and that
furthermore does not intersect ${\bm{\beta}}$, then
$\Delta_{\alpha{\bm{\beta}}}$ and $\Delta_{\alpha{\bm{\beta}}^{\prime}}$ are
independent conditioned on $\bm{x}_{\alpha}$.

Then our goal is to show
$\left\langle\Delta_{\bullet{\bm{\beta}}}\right\rangle_{{\bm{\beta}}}\in\mathcal{S}_{\mathrm{b}}^{1}$
is vanishing, i.e., for any $\epsilon>0$,

$n^{1-\epsilon}\left\langle\left\langle\Delta_{\alpha{\bm{\beta}}}\right\rangle_{{\bm{\beta}}}^{2}\right\rangle_{\alpha}\xrightarrow{\mathrm{\mathrm{a.s.}}}0.$

By 4.3.8, we just need to show there exist constants $C_{p}$ for all integers
$p\geq 1$ such that

$\operatorname*{\mathbb{E}}\left\langle\left\langle\Delta_{\alpha{\bm{\beta}}}\right\rangle_{{\bm{\beta}}}^{2p}\right\rangle_{\alpha}\leq
C_{p}n^{-p}$ (4.8)

for all $n$ and $p$.

Fix $n$ and $p$. Below, we shall bound each
$\left\langle\Delta_{\alpha{\bm{\beta}}}\right\rangle_{{\bm{\beta}}}^{2p}$
individually. By symmetry in $\alpha$, we WLOG fix $\alpha=n$. Let
$n^{\prime}$ be the largest multiple of $r$ smaller than $n$.

##### The Core Insight

We succinctly overview the core insight here, with more explanation below.
There are 3 steps of reasoning:

1\. For large $n$, $\sum_{{\bm{\beta}}}\Delta_{\alpha{\bm{\beta}}}$ is
dominated by the subset sum
$\sum_{{\bm{\beta}}\in\Gamma}\Delta_{\alpha{\bm{\beta}}}$ where
$\Gamma\subseteq[n^{\prime}]^{r}$ consists of all ${\bm{\beta}}$ that do not
contain repeating indices (i.e., $\beta_{1},\ldots,\beta_{r}$ are all
distinct). (Note such ${\bm{\beta}}$ does not contain $\alpha$ either since
$\alpha=n>n^{\prime}$ by assumption).

2\. But by Ordered Baranyai’s Theorem (4.1.6), there is a partition of
$\Gamma$ into perfect matchings $\Gamma_{1},\Gamma_{2},\ldots$ i.e., such that
each $\Gamma_{i}$ consists of multi-indices
$\Gamma_{i}=\\{{\bm{\beta}}^{1},\ldots,{\bm{\beta}}^{n^{\prime}/r}\\}$ and
${\bm{\beta}}^{1},\ldots,{\bm{\beta}}^{n^{\prime}/r}$ partition $[n^{\prime}]$
(i.e., each $\beta\in[n^{\prime}]$ appear in exactly one of
${\bm{\beta}}^{j}$). For example, if $n^{\prime}=4$ and $r=2$, then
$\Gamma=\\{(1,2),(1,3),(1,4),(2,3),(2,4),(3,4)\\}\cup\\{\text{mirror
image}\\}$. This is partitioned into the perfect matchings
$\\{(1,2),(3,4)\\}\sqcup\\{(1,3),(2,4)\\}\sqcup\\{(1,4),(2,3)\\}$ along with
their mirror images. Back to the general case, we thus have

$\sum_{{\bm{\beta}}\in\Gamma}\Delta_{\alpha{\bm{\beta}}}=\sum_{i}\sum_{{\bm{\beta}}\in\Gamma_{i}}\Delta_{\alpha{\bm{\beta}}}.$
(4.9)

3\. But, conditioned on $\bm{x}_{\alpha}$, each
$\sum_{{\bm{\beta}}\in\Gamma_{i}}\Delta_{\alpha{\bm{\beta}}}$ is a sum of
independent, mean-zero random variables by 4.4.7. Therefore it has typical
size $O(\sqrt{n^{\prime}/r})$ which is just $O(\sqrt{n})$ because $r$ is
constant. As a result, the whole sum Eq. 4.9 is of order $n^{r-1/2}$ so that

$n^{-r}\sum_{{\bm{\beta}}\in\Gamma}\Delta_{\alpha{\bm{\beta}}}=O(n^{-1/2}).$

This will be formalized as moment bounds

$\operatorname*{\mathbb{E}}\left\langle\Delta_{\alpha{\bm{\beta}}}\right\rangle_{{\bm{\beta}}}^{2p}\leq
C_{p}n^{-p}$

from which Eq. 4.8 would follow.

Of the 3 steps above, only 1 and 3 need further explanation. We do so below.

##### Filling in the Details

###### 1\. Sum Decomposition

Let $R_{1}$ be the set of ${\bm{\beta}}$ that contains at least one of
$n^{\prime}+1,\ldots,n$. Let $R_{2}$ be the set of ${\bm{\beta}}$ that
contains repeating indices. Then the complement of $\Gamma$ in $[n]^{r}$ is a
subset of $R_{1}\cup R_{2}$.

Now note that $|R_{1}\cup R_{2}|=\Theta(n^{r-1})$ (where the hidden constant
can depend on $r$ since $r=\Theta(1)$). Furthermore, because $\bm{X}$ (the
distribution of $\bm{x}$ and $\bm{y}$’s $\alpha$-slices) has all moments and
$\psi$ is pseudo-Lipschitz and thus polynomially bounded, there exist
constants $D_{q}$ for every $q\geq 1$ such that for all $\alpha,{\bm{\beta}}$,
we have $\operatorname*{\mathbb{E}}|\Delta_{\alpha{\bm{\beta}}}|^{q}\leq
D_{q}=O(1)$. Therefore, we have

$\operatorname*{\mathbb{E}}(\sum_{{\bm{\beta}}\not\in\Gamma}\Delta_{\alpha{\bm{\beta}}})^{2p}\leq|R_{1}\cup
R_{2}|^{2p-1}\operatorname*{\mathbb{E}}\sum_{{\bm{\beta}}\not\in\Gamma}\Delta_{\alpha{\bm{\beta}}}^{2p}=O(n^{(r-1)(2p-1)+(r-1)})=O(n^{(r-1)2p}).$

Thus, after multiplying by $(n^{-r})^{2p}$, we get

$\operatorname*{\mathbb{E}}\left\langle\Delta_{\alpha{\bm{\beta}}}\mathbb{I}_{{\bm{\beta}}\not\in\Gamma}\right\rangle_{{\bm{\beta}}}^{2p}=O(n^{-2p}).$

Consequently,

$\displaystyle\operatorname*{\mathbb{E}}\left\langle\Delta_{\alpha{\bm{\beta}}}\right\rangle_{{\bm{\beta}}}^{2p}$
$\displaystyle=\operatorname*{\mathbb{E}}\left\langle\Delta_{\alpha{\bm{\beta}}}\mathbb{I}_{{\bm{\beta}}\in\Gamma}+\Delta_{\alpha{\bm{\beta}}}\mathbb{I}_{{\bm{\beta}}\not\in\Gamma}\right\rangle_{{\bm{\beta}}}^{2p}$
$\displaystyle\leq
C\operatorname*{\mathbb{E}}\left\langle\Delta_{\alpha{\bm{\beta}}}\mathbb{I}_{{\bm{\beta}}\in\Gamma}\right\rangle_{{\bm{\beta}}}^{2p}+C\operatorname*{\mathbb{E}}\left\langle\Delta_{\alpha{\bm{\beta}}}\mathbb{I}_{{\bm{\beta}}\not\in\Gamma}\right\rangle_{{\bm{\beta}}}^{2p}$
$\displaystyle\leq
C\operatorname*{\mathbb{E}}\left\langle\Delta_{\alpha{\bm{\beta}}}\mathbb{I}_{{\bm{\beta}}\in\Gamma}\right\rangle_{{\bm{\beta}}}^{2p}+O(n^{-2p})$

where $C=2^{2p-1}$ (by Lemma 4.1.1). Thus, to show Eq. 4.8, it suffices to
show

$\operatorname*{\mathbb{E}}\left\langle\Delta_{\alpha{\bm{\beta}}}\mathbb{I}_{{\bm{\beta}}\in\Gamma}\right\rangle_{{\bm{\beta}}}^{2p}\leq
C_{p}n^{-p}$

(for a different set of constants $C_{p}$).

###### 3\. Bounding Moments

Let $\left\langle-\right\rangle_{{\bm{\beta}}\in\Gamma}$ denote average over
${\bm{\beta}}\in\Gamma$. Recall that, by Ordered Baranyai’s Theorem, we have
partitioned $\Gamma$ into $\Gamma_{1},\Gamma_{2},\ldots$ where each
$\Gamma_{i}$ consists of multi-indices
$\Gamma_{i}=\\{{\bm{\beta}}^{1},\ldots,{\bm{\beta}}^{n^{\prime}/r}\\}$ such
that ${\bm{\beta}}^{1},\ldots,{\bm{\beta}}^{n^{\prime}/r}$ partition
$[n^{\prime}]$. Consequently, for each $i$,
$\\{\Delta_{\alpha{\bm{\beta}}}:{\bm{\beta}}\in\Gamma_{i}\\}$ is mutually
independent conditioned on $\bm{x}_{\alpha}$. We first deduce

$\operatorname*{\mathbb{E}}\left\langle\Delta_{\alpha{\bm{\beta}}}\mathbb{I}_{{\bm{\beta}}\in\Gamma}\right\rangle_{{\bm{\beta}}}^{2p}\leq\operatorname*{\mathbb{E}}\left\langle\Delta_{\alpha{\bm{\beta}}}\right\rangle_{{\bm{\beta}}\in\Gamma}^{2p}=\operatorname*{\mathbb{E}}\left\langle\left\langle\Delta_{\alpha{\bm{\beta}}}\right\rangle_{{\bm{\beta}}\in\Gamma_{i}}\right\rangle_{i}^{2p}\leq\left\langle\operatorname*{\mathbb{E}}\left\langle\Delta_{\alpha{\bm{\beta}}}\right\rangle_{{\bm{\beta}}\in\Gamma_{i}}^{2p}\right\rangle_{i}$

where the equality follows from Eq. 4.9 and the last inequality follows from
power-mean inequality. Again, conditioned on $\bm{x}_{\alpha}$, each
$\left\langle\Delta_{\alpha{\bm{\beta}}}\right\rangle_{{\bm{\beta}}\in\Gamma_{i}}$
is a mean of independent, mean-zero random variables by 4.4.7. But by Lemma
4.1.3, there are real polynomially bounded functions $F_{p}$ of
$\bm{x}_{\alpha}$ for each integer $p$ such that
$\operatorname*{\mathbb{E}}\left[\left\langle\Delta_{\alpha{\bm{\beta}}}\right\rangle_{{\bm{\beta}}\in\Gamma_{i}}^{2p}\mid\bm{x}_{{\bm{\alpha}}}\right]<F_{p}(\bm{x}_{\alpha})(n^{\prime}/r)^{-p}$
simultaneously for every $i$. 111111Specifically, if $H_{\alpha}$ is the
random variable distributed identically as
$\Delta_{\alpha{\bm{\beta}}},{\bm{\beta}}\in\Gamma$ (which have the same
distribution for any ${\bm{\beta}}\in\Gamma$), then by Lemma 4.1.3, $F_{p}$ is
a polynomial in the moments of $H_{\alpha}$ conditioned on
$\bm{x}_{\alpha},$and these moments are themself polynomially bounded in
$\bm{x}_{\alpha}$ because $\psi$ is polynomially bounded. Therefore,
altogether,

$\operatorname*{\mathbb{E}}\left\langle\Delta_{\alpha{\bm{\beta}}}\mathbb{I}_{{\bm{\beta}}\in\Gamma}\right\rangle_{{\bm{\beta}}}^{2p}\leq
C_{p}n^{-p}$

where
$C_{p}=2^{p}r^{p}\operatorname*{\mathbb{E}}F_{p}(\bm{x}_{\alpha})=2^{p}r^{p}\operatorname*{\mathbb{E}}F_{p}(\bm{X})$
(which is finite because $\bm{X}$ has all moments, and where
$2^{p}\geq(n/n^{\prime})^{p}$ is there as a loose conversion factor from
$n^{\prime}$ to $n$).

###  4.5 Matrix Pseudo-Inverse

######  Lemma 4.5.1.

Suppose121212i.e., $\Lambda(n)$ is a random $k\times k$ matrix for each $n$;
c.f. 4.2.2 $\Lambda\in\mathcal{S}_{\mathrm{b}}^{0}\otimes\mathbb{R}^{k\times
k}$ such that $\Lambda\equiv\mathring{\Lambda}$ for a deterministic
$\mathring{\Lambda}\in\mathbb{R}^{k\times k}$.131313Recall this means the
random sequence $\Lambda$ is equivalent to the sequence that equals
$\mathring{\Lambda}$ identically; c.f. 4.2.4. If $\mathring{\Lambda}$ is full
rank, then

$\Lambda^{+}\equiv\mathring{\Lambda}^{-1}$

as well.

###### Proof.

Apply 4.3.12 to $\psi$ being the matrix pseudo-inverse function, which is
locally Lipschitz at any full rank matrix. ∎

Earlier we defined spaces like $\mathcal{S}^{1}\otimes\mathbb{R}^{k}$ which
roughly contains sequences (in $n$) of $n\times k$ matrices. Likewise, we can
define $\mathbb{R}^{k}\otimes\mathcal{S}^{1}$ which contain the transposes of
$\mathcal{S}^{1}\otimes\mathbb{R}^{k}$, i.e., $k\times n$ matrices.

######  Lemma 4.5.2.

Suppose $\bm{X}\in\mathbb{R}^{k}$ is a random vector and
$\bm{x}\overset{\mathrm{d}}{\equiv}\mathrm{iid}(\bm{X})\in\mathcal{S}_{\mathrm{b}}^{1}\otimes\mathbb{R}^{k}$.141414i.e.,
$X$ is a sequence of random $\mathbb{R}^{n\times k}$ matrices,
distributionally equivalent to $\mathrm{iid}(\bm{X})$; c.f. 4.2.2 If $\bm{X}$
has moments of all orders and its covariance
$\Lambda\mathrel{\raisebox{-1.29167pt}{$\mathbin{\overset{\text{{def}}}{=}}$}}\operatorname*{\mathbb{E}}\bm{X}\bm{X}^{\top}\in\mathbb{R}^{k\times
k}$ (which is deterministic, independent of $n$) is full rank, then as
elements of $\mathcal{S}_{\mathrm{b}}^{1}\otimes\mathbb{R}^{k}$,151515Recall,
as discussed in 4.2.2, $\mathcal{S}_{\mathrm{b}}^{1}\otimes\mathbb{R}^{k}$
means sequence in $n$ of moment-bounded $n\times k$ matrices.

$n\bm{x}^{+\top}\equiv\bm{x}\Lambda^{-1}\overset{\mathrm{d}}{\equiv}n\
\mathrm{iid}(\bm{X})^{+\top}\overset{\mathrm{d}}{\equiv}\mathrm{iid}(\bm{X})\Lambda^{-1}.$
(4.10)

Here $n\bm{x}^{+\top}$ is the sequence $n\mapsto n\bm{x}(n)^{+\top}$, and
likewise for $n\ \mathrm{iid}(\bm{X})^{+\top}$; $\bm{x}\Lambda^{-1}$ at index
$n$ is the matrix multiplication between $\bm{x}(n)$ (shape $n\times k$) and
$\Lambda^{-1}$ (shape $k\times k$).

Note that $n\bm{x}^{+\top}$ is the correct scaling with $n$ so that this
matrix has $\Theta(1)$ sized entries (it is elucidating to consider the
example when $k=1$ and $\bm{x}$ is just an $n$-vector).

###### Proof.

Let $\tilde{\bm{x}}$ be an instance of $\mathrm{iid}(\bm{X})$ such that
$\bm{x}\equiv\tilde{\bm{x}}$.

By standard pseudo-inverse facts (Section 4.1.1),
$n\bm{x}^{+}=(\frac{1}{n}\bm{x}^{\top}\bm{x})^{+}\bm{x}^{\top}.$ By Lemma
4.3.13,
$\frac{1}{n}\bm{x}^{\top}\bm{x}\equiv\frac{1}{n}\tilde{\bm{x}}^{\top}\tilde{\bm{x}}$.
By Lemma 4.4.2,
$\frac{1}{n}\tilde{\bm{x}}^{\top}\tilde{\bm{x}}\equiv\operatorname*{\mathbb{E}}\bm{X}\bm{X}^{\top}=\Lambda$.
By Lemma 4.5.1 and the nonsingularity of $\Lambda$, we have

$\left(\frac{1}{n}\bm{x}^{\top}\bm{x}\right)^{+}\equiv\Lambda^{-1}.$ (4.11)

Therefore, since equivalence is preserved under matrix multiplication (which
is certainly pseudo-Lipschitz; see 4.3.11), we have

$n\bm{x}^{+\top}=\bm{x}(\frac{1}{n}\bm{x}^{\top}\bm{x})^{+}\equiv\bm{x}\Lambda^{-1}\overset{\mathrm{d}}{\equiv}\tilde{\bm{x}}\Lambda^{-1}\overset{\mathrm{d}}{=}\mathrm{iid}(\bm{X})\Lambda^{-1}$

as desired.161616Technically, we need to check that $\Lambda^{-1}$ and
$\tilde{\bm{x}}^{\top}$ are both moment-bounded for 4.3.11 to apply. But this
check passes trivially. ∎

######  Lemma 4.5.3.

In the setting of Lemma 4.5.2, suppose there is additionally
$\bm{y}\in\mathcal{S}_{\mathrm{b}}^{1}\otimes\mathbb{R}^{l}$ such that
$(\bm{x},\bm{y})\overset{\mathrm{d}}{\equiv}\mathrm{iid}(\bm{X},\bm{Y})$ (as
sequences in
$\mathcal{S}_{\mathrm{b}}^{1}\otimes(\mathbb{R}^{k}\oplus\mathbb{R}^{l})$) for
some (fixed wrt $n$) random vector $\bm{Y}\in\mathbb{R}^{l}$. Then, as
elements of $\mathcal{S}_{\mathrm{b}}^{0}\otimes\mathbb{R}^{k\times l}$,
171717Recall $\mathcal{S}_{\mathrm{b}}^{0}\otimes\mathbb{R}^{k\times l}$ means
sequence in $n$ of moment-bounded $k\times l$ matrices; c.f. 4.2.2

$\bm{x}^{+}\bm{y}\equiv\Lambda^{-1}\Gamma$ (4.12)

where $\Gamma\in\mathbb{R}^{k\times l}$ is the deterministic matrix with
entries
$\Gamma^{ij}\mathrel{\raisebox{-1.29167pt}{$\mathbin{\overset{\text{{def}}}{=}}$}}\operatorname*{\mathbb{E}}X^{i}Y^{j}$.181818Note
the RHS is just a deterministic $\mathbb{R}^{k\times l}$ matrix, representing
the constant sequence as in 4.2.4.

###### Proof.

let $(\tilde{\bm{x}},\tilde{\bm{y}})$ be an instance of
$\mathrm{iid}(\bm{X},\bm{Y})$ such that
$(\bm{x},\bm{y})\equiv(\tilde{\bm{x}},\tilde{\bm{y}})$. Then by standard
pseudo-inverse facts (Section 4.1.1),

$\bm{x}^{+}\bm{y}=(\frac{1}{n}\bm{x}^{\top}\bm{x})^{-1}(\frac{1}{n}\bm{x}^{\top}\bm{y})\equiv\Lambda^{-1}(\frac{1}{n}\tilde{\bm{x}}^{\top}\tilde{\bm{y}})\equiv\Lambda^{-1}\Gamma$

where the first equivalence follows from Eq. 4.11 and 4.3.11, and the last
equivalence follows from Lemma 4.4.2. ∎

###  4.6 Uniformized Tensor Programs

Here, we “uniformize” different variations of Tensor Programs, in the sense
that we squash all the different instructions into a single step. This allows
us to streamline the induction in our proofs.

####  4.6.1 Uniformized $\textsc{Netsor}\top$

Given initial matrices $A^{1},\ldots,A^{L}\in\bm{\mathbb{\mathbb{R}}}^{n\times
n}$ and initial vectors
$g^{1},\ldots,g^{M_{0}}\in\bm{\mathbb{\mathbb{R}}}^{n}$, consider the
following iteration for $i=M_{0}+1,\ldots,M$ that generates new vectors
$g^{M_{0}+1},\ldots,g^{M}\in\bm{\mathbb{\mathbb{R}}}^{n}$:

$g_{\alpha}^{i}\leftarrow\sum_{\beta=1}^{n}W_{\alpha\beta}^{i}x_{\beta}^{i},\quad\text{where
}x_{\alpha}^{i}=\phi^{i}(g_{\alpha}^{1},\ldots,g_{\alpha}^{i-1}).$ (4.13)

Here each $\phi^{i}$ is a chosen scalar function with $(i-1)$ arguments and
$W^{i}$ is an $n\times n$ matrix. Each matrix $W^{i}$ equals to either some
matrix $A^{j}$ of the program or its transpose $A^{j\top}$. The matrices
$W^{i}$ for different $i$ can possibly be the same. Thus each program is
entirely determined by the data
$\\{A^{j}\\}_{j=1}^{L}\cup\\{g^{i}\\}_{i=1}^{M_{0}}\cup\\{\phi^{i}\\}_{i=M_{0}+1}^{M}$
along with the correspondence between $W^{i}$ and $A^{j}$ or $A^{j\top}$.

This type of program is obviously a subset of $\textsc{Netsor}\top$ ([44]) but
it’s also easy to see that they have the same expressive power.

####  4.6.2 Uniformized $\textsc{Ne}{\otimes}\textsc{or}\top$

Now extend the previous formulation to include additionally initial scalars
$c^{1},\ldots,c^{M_{0}}\in\mathbb{R}$ and extend Eq. 4.13 to produce both a
new vector $g^{i}$ and a new scalar $c^{i}$ at each step $i=M_{0}+1,\ldots,M$:

$\displaystyle g_{\alpha}^{i}$
$\displaystyle\leftarrow\sum_{\beta=1}^{n}W_{\alpha\beta}^{i}x_{\beta}^{i},\quad
c^{i}\leftarrow\frac{1}{n}\sum_{\beta=1}^{n}x_{\beta}^{i},$ (4.14)
$\displaystyle\text{where }x_{\alpha}^{i}$
$\displaystyle=\frac{1}{n^{i}}\sum_{{\bm{\beta}}}\phi^{i}(\bm{g}_{\alpha};\bm{g}_{\beta};\cdots;\bm{g}_{\beta_{i}};\bm{c})$
(4.15)
$\displaystyle=\langle\phi^{i}(\bm{g}_{\alpha};\bm{g}_{\beta_{1}};\cdots;\bm{g}_{\beta_{i}};\bm{c})\rangle_{{\bm{\beta}}}$
(4.16)

where
$\phi^{i}:\underbrace{\mathbb{R}^{i-1}\oplus\cdots\oplus\mathbb{R}^{i-1}}_{i+2}\to\mathbb{R}$,
each ${\bm{\beta}}=(\beta_{1},\ldots,\beta_{i})$ ranges over all tuples in
$[n]^{i}$, and
$\bm{g}=(g^{1},\ldots,g^{i-1}),\bm{c}=(\bm{c}^{1},\ldots,\bm{c}^{i-1})$ at
iteration $i$.

Here we are tying together the tensor order of $\phi^{i}$ with the iteration
index $i$, to simplify the formulation. But note that $\phi^{i}$ can always
ignore all but the first block of inputs, for example, to replicate Eq. 4.13.
By the same reasoning as Section 4.6.1, this formulation of
$\textsc{Ne}{\otimes}\textsc{or}\top$ is equivalent to 2.6.1.

####  4.6.3 Setup and Constructions

Below, we typically consider the following setup for both uniformized
$\textsc{Netsor}\top$ and uniformized $\textsc{Ne}{\otimes}\textsc{or}\top$.
It is essentially the same as 2.6.3 except that the initial scalars need to
converge at the rate of $\tilde{O}(n^{-1/2})$. This is needed to prove the
vectorwise convergence results below.

######  Setup 4.6.1.

Assume

  1. 1.

Every entry of every $A^{l}$ is sampled iid from $\mathcal{N}(0,1/n)$.

  2. 2.

Every entry of every initial vector $g^{i}$ is sampled iid from
$\mathcal{N}(0,1)$.

  3. 3.

Each initial scalar $c^{i}$ is $\tilde{O}(n^{-1/2})$.

  4. 4.

All nonlinearities $\phi^{i}$ are pseudo-Lipschitz.

In addition, since both uniformized $\textsc{Netsor}\top$ and uniformized
$\textsc{Ne}{\otimes}\textsc{or}\top$ are subsets of the
$\textsc{Ne}{\otimes}\textsc{or}\top$ language, the construction of kets in
2.6.5 make sense for both of them. Finally, in the context of $n\to\infty$, we
think of the program’s objects as sequences in $n$, i.e.,
$A^{j}\in\mathcal{S}^{2}$, $g^{i}\in\mathcal{S}^{1}$,
$c^{i}\in\mathcal{S}^{0}$.

###  4.7 $\textsc{Netsor}\top$ Master Theorem, Vectorwise Convergence

######  Definition 4.7.1.

Consider a Tensor Program (of any variation). Let $x^{1},\ldots,x^{k}$ be the
set of all vectors in the program. Then we define
$(\mathring{x}^{1},\ldots,\mathring{x}^{k})$ as
$\mathrm{iid}(\hstretch{0.7}{\talloblong}x^{1}\rangle,\ldots,\hstretch{0.7}{\talloblong}x^{k}\rangle)$,
i.e., each $\alpha$-slice
$(\mathring{x}_{\alpha}^{1},\ldots,\mathring{x}_{\alpha}^{k})$ is an iid
sample from
$(\hstretch{0.7}{\talloblong}x^{1}\rangle,\ldots,\hstretch{0.7}{\talloblong}x^{k}\rangle)$.191919Note
that $(\mathring{x}^{1},\ldots,\mathring{x}^{k})$ is only well defined up to
distributional equality, and thus it only makes sense to talk about them up to
distributional equality or coarser notions like (conditional) dequivalence,
but not up to equivalence.

Both $\mathring{x}$ and $\hstretch{0.7}{\talloblong}x\rangle$ are “limits” of
a vector $x$ in some sense, but $\mathring{x}$ always has the same shape as
$x$ (same for $\mathring{\theta}$ for scalar $\theta$) while
$\hstretch{0.7}{\talloblong}x\rangle$ collapses the $n$-dimension. In this and
the next section, we aim to show that
$x\overset{\mathrm{d}}{\equiv}\mathring{x}$ in different kinds of Tensor
Programs. This essentially means that $x$ and $\mathring{x}$, random vectors
with larger and larger dimensions, become closer and closer in distribution as
$n\to\infty$ (see Section 4.3.4) — hence the _vectorwise convergence_ in the
section title.

######  Theorem 4.7.2.

Consider a $\textsc{Netsor}\top$ program in 4.6.1. Consider any collection of
vectors $y^{1},\ldots,y^{k}$ in the program. Then they are moment-bounded and

$(y^{1},\ldots
y^{k})\overset{\mathrm{d}}{\equiv}(\mathring{y}^{1},\ldots\mathring{y}^{k}).$

In other words, $(y^{1},\ldots y^{k})$ is distributed like $n$ iid copies of
$(\hstretch{0.7}{\talloblong}y^{1}\rangle,\ldots\hstretch{0.7}{\talloblong}y^{k}\rangle)$,
modulo vanishing vectors. This is a stronger result than [44], at the cost of
assuming faster convergence of initial scalars in 4.6.1.

######  Remark 4.7.3.

Let us comment that, in this proof, we do not use the property that
equivalence is preserved under iid matrix multiplication 4.3.14 (this property
is a crucial reason underlying the definition of “vanishing”), because of
$\textsc{Netsor}\top$’s rank stability property. This however will be crucial
in Section 4.8 to prove the analogous result for
$\textsc{Ne}{\otimes}\textsc{or}\top$.

We recall some terminology from prior works.

######  Definition 4.7.4.

A vector is called a G-var if it is an initial vector or generated by MatMul.

####  4.7.1 Proof Setup

[44] | Here
---|---
$x^{i}$ | $g^{i}$
$y^{i}$ | $x^{i}$
$u^{j}$ | $h^{j}$
$v^{j}$ | $y^{j}$
$h$ | $x$
$g$ | $g$
$\Upsilon$ | $\bm{x}^{\top}\bm{x}/n$
$\mathring{\Upsilon}$ | $\langle\bm{x}\hstretch{0.7}{\talloblong}\bm{x}\rangle$
$\Lambda$ | $\bm{y}^{\top}\bm{y}/n$
$\mathring{\Lambda}$ | $\langle\bm{y}\hstretch{0.7}{\talloblong}\bm{y}\rangle$
$\Gamma$ | $\bm{h}^{\top}\bm{x}/n$
$\mathring{\Gamma}$ | $\langle\bm{h}\hstretch{0.7}{\talloblong}\bm{x}\rangle$
$\gamma$ | $\bm{x}^{\top}x/n$
$\mathring{\gamma}$ | $\langle\bm{x}\hstretch{0.7}{\talloblong}x\rangle$
$\delta$ | $\bm{h}^{\top}x/n$
$\mathring{\delta}$ | $\langle\bm{h}\hstretch{0.7}{\talloblong}x\rangle$
Table 4.1: Notation mapping between [44] and here. We improved the notation to
be more intuitive, leveraging our new bra-ket notation.

We will nontrivially leverage parts of the Master Theorem proof in [44]. Our
notation differs from there (hopefully improved for first time readers), but a
mapping is provided in Table 4.1. By 4.3.18, it suffices to show this for all
G-vars of the program, since other vectors are pseudo-Lipschitz images of
G-vars. We furthermore WLOG assume the formulation in Eq. 4.13 and proceed to
show this for vectors $g^{1},\ldots,g^{M}$ (all G-vars in the program).

By the $\textsc{Netsor}\top$ Master Theorem [44], we know that the matrices
$(\frac{1}{n}g^{i\top}g^{j})_{i,j=1}^{M}$ and
$(\frac{1}{n}x^{i\top}x^{j})_{i,j=1}^{M}$ converge almost surely to
deterministic matrices $\Omega\in\mathbb{R}^{M\times M}$ and
$\Xi\in\mathbb{R}^{M\times M}$. By rank stability [44, sec L.5], WLOG, we can
assume

######  Assumption 4.7.5.

WLOG, we assume $\Omega$ and $\Xi$ are both full rank.

Indeed, [44, sec L.5] says that $\Xi$ (resp. $\Omega$) is singular iff there
are linear dependencies (with constant coefficients) between $x^{i}$s (resp.
$g^{i}$s), which we can get rid of by rewriting the program in the obvious
way.202020Rank stability is a highly nontrivial but technical result of [44].
While seemingly small, it allows us to drastically simplify the proof because
we do not have to think about “corner cases” where the rank of a matrix drops
suddenly in the limit, which can lead to all kinds of pathological behaviors.
Readers interested in full rigor should consult [44] for the proof of this
result.

We induct on $i$, starting from the base case $i=M_{0}$.

###### Base Case: $i=M_{0}.$

This holds by 4.6.1 that the initial vectors are sampled iid.

###### Inductive Step

Here we assume the dequivalence

$R:(g^{1},\ldots,g^{i})\overset{\mathrm{d}}{\equiv}(\mathring{g}^{1},\ldots,\mathring{g}^{i})$
(4.17)

as well as their moment-boundedness and we shall show

$g^{i+1}\overset{\mathrm{d}}{\equiv}_{R}\mathring{g}^{i+1},$

and their moment-boundedness, where the conditional dequivalence can be
unpacked into

$(g^{1},\ldots,g^{i},g^{i+1})\overset{\mathrm{d}}{\equiv}(\mathring{g}^{1},\ldots,\mathring{g}^{i},\mathring{g}^{i+1}).$
(4.18)

For brevity, write
$g\mathrel{\raisebox{-1.29167pt}{$\mathbin{\overset{\text{{def}}}{=}}$}}g^{i+1},x\mathrel{\raisebox{-1.29167pt}{$\mathbin{\overset{\text{{def}}}{=}}$}}x^{i+1},W\mathrel{\raisebox{-1.29167pt}{$\mathbin{\overset{\text{{def}}}{=}}$}}W^{i+1}$
so that in this notation, by Eq. 4.13, $g=Wx$.

We apply Gaussian conditioning trick to obtain

$\displaystyle(g^{1},\ldots,g^{i},g)$
$\displaystyle\overset{\mathrm{d}}{=}(g^{1},\ldots,g^{i},\omega+\sigma\Pi^{\perp}z)$
(4.19)

where $\omega\in\mathcal{S}^{1},\Pi^{\perp}\in\mathcal{S}^{2}$ and
$\sigma\in\mathcal{S}^{0}$ are functions of $g^{1},\ldots,g^{i}$, and
$z\in\mathcal{S}^{1},z\overset{\mathrm{d}}{=}\mathrm{iid}(\mathcal{N}(0,1))$
is a fresh iid standard Gaussian vector, independent from everything else.

####  4.7.2 Proof Plan

Below, we will give the exact formulas for $\omega,\Pi^{\perp},\sigma$ and we
will show that

  1. 1.

there is a pseudo-Lipschitz function $\psi:\mathbb{R}^{i}\to\mathbb{R}$ such
that $\omega\equiv\psi(g^{1},\ldots,g^{i})$,212121with $\psi$ applied
coordinatewise as usual

  2. 2.

there is a deterministic $\mathring{\sigma}\in\mathbb{R}$ such that
$\sigma\equiv\mathring{\sigma}$, and

  3. 3.

$\Pi^{\perp}z\equiv z$.

These claims already imply that $g$ is moment-bounded. Furthermore, applying
Eq. 4.17 and 4.3.18 to Eq. 4.19, the above claims imply

$(g^{1},\ldots,g^{i},g)\overset{\mathrm{d}}{\equiv}(\mathring{g}^{1},\ldots,\mathring{g}^{i},\psi(\mathring{g}^{1},\ldots,\mathring{g}^{i})+\mathring{\sigma}z)$

Using the exact formulas below, by the same calculations of [44], the RHS can
be shown to be
$\overset{\mathrm{d}}{=}(\mathring{g}^{1},\ldots,\mathring{g}^{i},\mathring{g}^{i+1})$,
yielding Eq. 4.18 as desired.222222In particular, we do not change any of the
formulas for the large $n$ limit in our induction; we only “upgrade the mode
of convergence” to (distributional) equivalence. So it is easy to verify this
claim.

####  4.7.3 Exact Formulas

###### Preliminary Definitions

We define the following objects.

  * •

Let $J$ (resp. $J^{\prime}$) be the set of indices $j\leq i$ such that
$W^{j}=W^{i+1}$ (resp. $W^{j}=W^{i+1\top}$), so that $g^{j}=Wx^{j}$ (resp.
$g^{j}=W^{\top}x^{j}$) by construction.

  * •

Let $\bm{g}\in\mathcal{S}^{1}\otimes\mathbb{R}^{J}$ (resp.
$\bm{x}\in\mathcal{S}^{1}\otimes\mathbb{R}^{J}$) be the matrix with column
vectors $g^{j}$ (resp. $x^{j}$) for all $j\in J$, so that $\bm{g}=W\bm{x}$.
(Note $\bm{g}$ is a distinct object from and does not contain $g=g^{i+1}$;
likewise for $\bm{x}$ and $x=x^{i+1}$)

  * •

Likewise, let $\bm{h}\in\mathcal{S}^{1}\otimes\mathbb{R}^{J^{\prime}}$ (resp.
$\bm{y}\in\mathcal{S}^{1}\otimes\mathbb{R}^{J^{\prime}}$) be the matrix with
column vectors $g^{j}$ (resp. $x^{j}$) for all $j\in J^{\prime}$, so that
$\bm{h}=W^{\top}\bm{y}$.

###### Exact Formulas

Then, by the same calculations as in [44], $\omega,\Pi^{\perp},\sigma$ have
the following exact formulas:

$\displaystyle\omega$
$\displaystyle=(\bm{g}\bm{x}^{+}+\bm{y}^{+\top}\bm{h}^{\top}-\bm{y}^{+\top}\bm{h}^{\top}\bm{x}\bm{x}^{+})x$
(4.20)

and

$\displaystyle\sigma$
$\displaystyle=\sqrt{\frac{\|\Pi_{\bm{x}}^{\perp}x\|^{2}}{n}}$ (4.21)
$\displaystyle\text{with }\Pi_{\bm{x}}^{\perp}$
$\displaystyle\mathrel{\raisebox{-1.29167pt}{$\mathbin{\overset{\text{{def}}}{=}}$}}I-\bm{x}\bm{x}^{+}$

and

$\Pi^{\perp}\mathrel{\raisebox{-1.29167pt}{$\mathbin{\overset{\text{{def}}}{=}}$}}I-\bm{y}\bm{y}^{+}.$
(4.22)

###### Further Constructions

Now we further define $\mathring{\bm{g}}$ to be the matrix with column vectors
$\mathring{g}^{j}$ for all $j\in J$; likewise we define
$\mathring{\bm{x}},\mathring{\bm{h}},\mathring{\bm{y}}$. By induction
hypothesis (Eq. 4.17), we have

$(\bm{g},\bm{x},\bm{h},\bm{y})\overset{\mathrm{d}}{\equiv}_{R}(\mathring{\bm{g}},\mathring{\bm{x}},\mathring{\bm{h}},\mathring{\bm{y}})$
(4.23)

because of 4.3.18 (as this relation is a pseudo-Lipschitz image of Eq. 4.17).

Now note

$\mathcal{S}^{0}\otimes\mathbb{R}^{J\times
J}\ni\frac{1}{n}\bm{x}^{\top}\bm{x}\equiv\langle\bm{x}\hstretch{0.7}{\talloblong}\bm{x}\rangle\in\mathbb{R}^{J\times
J}$

by Eq. 4.23 and Lemma 4.4.3, where the RHS is a deterministic object
independent of $n$. Likewise,

$\mathcal{S}^{0}\otimes\mathbb{R}^{J^{\prime}\times
J^{\prime}}\ni\frac{1}{n}\bm{y}^{\top}\bm{y}\equiv\langle\bm{y}\hstretch{0.7}{\talloblong}\bm{y}\rangle\in\mathbb{R}^{J^{\prime}\times
J^{\prime}}.$

But both $\langle\bm{x}\hstretch{0.7}{\talloblong}\bm{x}\rangle$ and
$\langle\bm{y}\hstretch{0.7}{\talloblong}\bm{y}\rangle$ are principal
submatrices of $\Xi$ by construction, so by Sylvester’s Criterion and 4.7.5,

$\langle\bm{x}\hstretch{0.7}{\talloblong}\bm{x}\rangle\text{ and
}\langle\bm{y}\hstretch{0.7}{\talloblong}\bm{y}\rangle\text{ are
nonsingular.}$ (4.24)

The significance of this is that now we can use Lemma 4.5.3 on $\bm{x}$ and
$\bm{y}$.

####  4.7.4 Showing 3)

Using Eq. 4.22 and Lemma 4.5.3, we have

$\Pi^{\perp}z=z-\bm{y}\bm{y}^{+}z\equiv
z-\bm{y}\langle\bm{y}\hstretch{0.7}{\talloblong}\bm{y}\rangle^{-1}\langle\bm{y}\hstretch{0.7}{\talloblong}z\rangle$

But $\hstretch{0.7}{\talloblong}z\rangle$ is independent from
$\hstretch{0.7}{\talloblong}\bm{y}\rangle$ (because $z$ is independent from
$\bm{y}$ by construction) and is distributed as $\mathcal{N}(0,1)$, so the
$\langle\bm{y}\hstretch{0.7}{\talloblong}z\rangle$ vanishes. In conclusion,

$\Pi^{\perp}z\equiv z$

as desired. This shows 3).

####  4.7.5 Showing 2)

Writing out the definition of $\sigma^{2}$ (Eq. 4.21), we see

$\displaystyle\sigma^{2}$
$\displaystyle=\frac{\|\Pi_{\bm{x}}^{\perp}x\|^{2}}{n}=\frac{1}{n}x^{\top}x-(\frac{1}{n}x^{\top}\bm{x})(\bm{x}^{+}x)$
$\displaystyle\equiv\frac{1}{n}x^{\top}x-(\frac{1}{n}x^{\top}\bm{x})\langle\bm{x}\hstretch{0.7}{\talloblong}\bm{x}\rangle^{-1}\langle\bm{x}\hstretch{0.7}{\talloblong}x\rangle$
$\displaystyle\equiv\langle x\hstretch{0.7}{\talloblong}x\rangle-\langle
x\hstretch{0.7}{\talloblong}\bm{x}\rangle\langle\bm{x}\hstretch{0.7}{\talloblong}\bm{x}\rangle^{-1}\langle\bm{x}\hstretch{0.7}{\talloblong}x\rangle\mathrel{\raisebox{-1.29167pt}{$\mathbin{\overset{\text{{def}}}{=}}$}}\mathring{\sigma}^{2}$

where the second line follows by Lemma 4.5.3, and the third line follows by
Eq. 4.23 and Lemma 4.4.3.

Note that $\mathring{\sigma}^{2}$ is deterministic. By 4.7.5,
$\mathring{\sigma}^{2}>0$ (because $\mathring{\sigma}$ is a $1\times 1$ Schur
complement of $\Xi$). Then the square root function is locally Lipschitz
around $\mathring{\sigma}^{2}$. So by 4.3.12, we get

$\sigma\equiv\mathring{\sigma}.$

####  4.7.6 Showing 1)

Finally, we can apply the same strategy to show $\omega=Ex$ is equivalent to a
linear combination of $\mathring{\bm{g}}$ and $\mathring{\bm{y}}$ with
deterministic coefficients, albeit with slightly more calculations.

By Eq. 4.20, we can decompose

$\displaystyle\omega$
$\displaystyle=(\bm{g}\bm{x}^{+}+\bm{y}^{+\top}\bm{h}^{\top}-\bm{y}^{+\top}\bm{h}^{\top}\bm{x}\bm{x}^{+})x$
$\displaystyle=A+B-C$

where

$A\mathrel{\raisebox{-1.29167pt}{$\mathbin{\overset{\text{{def}}}{=}}$}}\bm{g}\bm{x}^{+}x,\quad
B\mathrel{\raisebox{-1.29167pt}{$\mathbin{\overset{\text{{def}}}{=}}$}}\bm{y}(\frac{1}{n}\bm{y}^{\top}\bm{y})^{+}(\frac{1}{n}\bm{h}^{\top}x),\quad
C\mathrel{\raisebox{-1.29167pt}{$\mathbin{\overset{\text{{def}}}{=}}$}}\bm{y}(\frac{1}{n}\bm{y}^{\top}\bm{y})^{+}(\frac{1}{n}\bm{h}^{\top}\bm{x})(\bm{x}^{+}x).$

Then the same deduction as before (involving Lemma 4.4.3 and Lemma 4.5.3)
shows

$A\equiv\bm{g}\langle\bm{x}\hstretch{0.7}{\talloblong}\bm{x}\rangle^{-1}\langle\bm{x}\hstretch{0.7}{\talloblong}x\rangle,\quad
B\equiv\bm{y}\langle\bm{y}\hstretch{0.7}{\talloblong}\bm{y}\rangle^{-1}\langle\bm{h}\hstretch{0.7}{\talloblong}x\rangle,\quad
C\equiv\bm{y}\langle\bm{y}\hstretch{0.7}{\talloblong}\bm{y}\rangle^{-1}\langle\bm{h}\hstretch{0.7}{\talloblong}\bm{x}\rangle\langle\bm{x}\hstretch{0.7}{\talloblong}\bm{x}\rangle^{-1}\langle\bm{x}\hstretch{0.7}{\talloblong}x\rangle$

Thus, $A,B,C$, and thus $\omega$ are clearly equivalent to linear combinations
of (the columns of) $\bm{g}$ and $\bm{y}$. Consequently, $\omega$ is also a
pseudo-Lipschitz image of $g^{1},\ldots,g^{i}$ because $\bm{y}$ is. This
proves 1).

###  4.8 $\textsc{Ne}{\otimes}\textsc{or}\top$ Master Theorem, Vectorwise
Convergence

######  Definition 4.8.1 (Integrated Program).

Given an uniformized $\textsc{Ne}{\otimes}\textsc{or}\top$ program $\pi$ (Eq.
4.14), we construct a parallel _uniformized $\textsc{Netsor}\top$ program
$\underline{\pi}$_, called the _integrated program_ , as follows.
$\underline{\pi}$’s vectors will be denoted with an underline
$\underline{g}^{1},\ldots,\underline{g}^{M}$ (which will turn out to be
equivalent to their counterparts without underlines).

  * •

The initial matrices of $\pi$ and $\underline{\pi}$ are identical and using
the same symbols $A^{1},\ldots,A^{L}$.

  * •

The initial vectors $\underline{g}^{1},\ldots,\underline{g}^{M_{0}}$ are the
same as those of the original program $g^{1},\ldots,g^{M_{0}}$.

  * •

new vectors $\underline{g}^{i}$ for $i=M_{0}+1,\ldots,M$ are generated
iteratively as follows: For each such $i$, define
$\underline{\phi}^{i}:\mathbb{R}^{i-1}\to\mathbb{R}$ by

$\underline{\phi}^{i}(\mathbf{x})\mathrel{\raisebox{-1.29167pt}{$\mathbin{\overset{\text{{def}}}{=}}$}}\operatorname*{\mathbb{E}}_{\mathord{\ThisStyle{\LMpt\kern
1.0pt\LMpt\framebox{$\SavedStyle 1$}\kern
1.0pt\LMpt}}\ldots\mathord{\ThisStyle{\LMpt\kern
1.0pt\LMpt\framebox{$\SavedStyle i$}\kern
1.0pt\LMpt}}}\phi^{i}(\mathbf{x};\hstretch{0.7}{\talloblong}\underline{\bm{g}}\rangle^{\mathord{\ThisStyle{\LMpt\kern
1.0pt\LMpt\framebox{$\SavedStyle 1$}\kern
1.0pt\LMpt}}};\ldots;\hstretch{0.7}{\talloblong}\underline{\bm{g}}\rangle^{\mathord{\ThisStyle{\LMpt\kern
1.0pt\LMpt\framebox{$\SavedStyle i$}\kern 1.0pt\LMpt}}};\mathring{\bm{c}})$

for any $\mathbf{x}\in\mathbb{R}^{i-1}$, where $\underline{\bm{g}}$ denotes
$(\underline{g}^{1},\ldots,\underline{g}^{i-1})$, $\bm{c}$ denotes
$(c^{1},\ldots,c^{i-1})$, and $\phi^{i}$ is from Eq. 4.16. Then
$\underline{g}^{i}$ is generated as

$\displaystyle\underline{g}_{\alpha}^{i}$
$\displaystyle\leftarrow\sum_{\beta=1}^{n}W_{\alpha\beta}^{i}\underline{x}_{\beta}^{i},\quad\text{where}\quad\underline{x}_{\alpha}^{i}=\underline{\phi}^{i}\left(\underline{\bm{g}}_{\alpha}\right).$

Note all scalars $c^{i}$ of $\pi$ are replaced by their deterministic limits
$\mathring{c}^{i}\in\mathbb{R}$ as constructed in 2.6.5 and absorbed into the
nonlinearities $\underline{\phi}^{i}$.

The name _integrated program_ refers to the intuition that we are replacing
the averaging
$\langle\phi^{i}(\bm{g}_{\alpha};\bm{g}_{\beta_{1}};\cdots;\bm{g}_{\beta_{i}};\bm{c})\rangle_{{\bm{\beta}}}$
with integration $\operatorname*{\mathbb{E}}_{\mathord{\ThisStyle{\LMpt\kern
1.0pt\LMpt\framebox{$\SavedStyle 1$}\kern
1.0pt\LMpt}}\ldots\mathord{\ThisStyle{\LMpt\kern
1.0pt\LMpt\framebox{$\SavedStyle i$}\kern
1.0pt\LMpt}}}\phi^{i}(\bm{g}_{\alpha};\hstretch{0.7}{\talloblong}\bm{g}\rangle^{\mathord{\ThisStyle{\LMpt\kern
1.0pt\LMpt\framebox{$\SavedStyle 1$}\kern
1.0pt\LMpt}}};\cdots;\hstretch{0.7}{\talloblong}\bm{g}\rangle^{\mathord{\ThisStyle{\LMpt\kern
1.0pt\LMpt\framebox{$\SavedStyle i$}\kern 1.0pt\LMpt}}};\mathring{\bm{c}})$.

######  Lemma 4.8.2.

Consider a uniformized $\textsc{Ne}{\otimes}\textsc{or}\top$ program $\pi$ in
4.6.1 and its integrated $\textsc{Netsor}\top$ program $\underline{\pi}$ as
constructed above. Then for
$\underline{\bm{g}}=(\underline{g}^{1},\ldots,\underline{g}^{M})$, we have
$\hstretch{0.7}{\talloblong}\bm{g}\rangle\overset{\mathrm{d}}{=}\hstretch{0.7}{\talloblong}\underline{\bm{g}}\rangle$
(as random vectors in $\mathbb{R}^{M}$) and

$\bm{g}\equiv\underline{\bm{g}}\overset{\mathrm{d}}{\equiv}\mathring{\underline{\bm{g}}}\overset{\mathrm{d}}{\equiv}\mathring{\bm{g}}.$

In particular, this implies that for (non-uniformized)
$\textsc{Ne}{\otimes}\textsc{or}\top$ programs,
$\bm{x}\overset{\mathrm{d}}{\equiv}\mathring{\bm{x}}$ for $\bm{x}$ being the
collection of all vectors, i.e., we have the vectorwise convergent version of
the Master Theorem, a strengthening of the 2nd half of 2.6.10 (which assumes
initial scalars are $\tilde{O}(n^{-1/2})$).

Before we prove this, let us remark that Lemma 4.8.2 automatically tells us
that identities of kets, such as [44, Lemma L.3], that hold for
$\textsc{Netsor}\top$ programs automatically hold for
$\textsc{Ne}{\otimes}\textsc{or}\top$ programs:

######  Lemma 4.8.3 ([44, Lemma L.3]).

For any vectors $x,y$ and matrix $W$ in a
$\textsc{Ne}{\otimes}\textsc{or}\top$ program, the following identities hold.

$\displaystyle\langle x\hstretch{0.7}{\talloblong}Wy\rangle$
$\displaystyle=\langle W^{\top}x\hstretch{0.7}{\talloblong}y\rangle$
$\displaystyle\langle
x\hstretch{0.7}{\talloblong}Wy\hat{\rangle\mkern-3.0mu}\mkern 3.0mu$
$\displaystyle=\mkern
3.0mu\dot{\mkern-3.0mu\langle}W^{\top}x\hstretch{0.7}{\talloblong}y\rangle$

###### Proof of Lemma 4.8.2.

The distributional equality
$\hstretch{0.7}{\talloblong}\bm{g}\rangle\overset{\mathrm{d}}{=}\hstretch{0.7}{\talloblong}\underline{\bm{g}}\rangle$
follows straightforwardly from the definition of these random vectors. Thus we
also have
$\mathring{\bm{g}}\overset{\mathrm{d}}{=}\mathring{\underline{\bm{g}}}$ (since
they are just iid samples of $\hstretch{0.7}{\talloblong}\bm{g}\rangle$ and
$\hstretch{0.7}{\talloblong}\underline{\bm{g}}\rangle$). We also have from
4.7.2 that
$\underline{\bm{g}}\overset{\mathrm{d}}{\equiv}\mathring{\underline{\bm{g}}}$.
So it remains to prove that $\bm{g}\equiv\underline{\bm{g}}$.

We will induct on $i$ to show that
$(g^{1},\ldots,g^{i})\equiv(\underline{g}^{1},\ldots,\underline{g}^{i})$. Note
that, by 4.3.11, this implies
$(x^{1},\ldots,x^{i+1})\equiv(\underline{x}^{1},\ldots,\underline{x}^{i+1})$,
and by Lemma 4.3.13, this also implies
$(c^{1},\ldots,c^{i+1})\equiv(\mathring{c}^{1},\ldots,\mathring{c}^{i+1})$.

The base case of $i=M_{0}$ is trivial since both programs share their initial
vectors.

Assuming the induction hypothesis for $i$ (i.e.,
$(g^{1},\ldots,g^{i})\equiv(\underline{g}^{1},\ldots,\underline{g}^{i})$), we
shall prove it’s also true for $i+1$: i.e., we need to show
$g^{i+1}\equiv\underline{g}^{i+1}$ in addition.

For brevity, write $\phi=\phi^{i+1}$,
$\underline{\phi}=\underline{\phi}^{i+1},W=W^{i+1}$, $x=x^{i+1}$. Let $\bm{g}$
denote $(g^{1},\ldots,g^{i})$; likewise for $\underline{\bm{g}}$. Let $\bm{c}$
denote $(c^{1},\ldots,c^{i})$ and $\mathring{\bm{c}}$ denote
$(\mathring{c}^{1},\ldots,\mathring{c}^{i})$. Then since
$\bm{g}\equiv\underline{\bm{g}}$ and $\bm{c}\equiv\mathring{\bm{c}}$ by IH, we
have by 4.3.11 that

$\phi(\bm{g};\ldots;\bm{g};\bm{c})\equiv\phi(\underline{\bm{g}};\ldots;\underline{\bm{g}};\mathring{\bm{c}})\in\mathcal{S}_{\mathrm{b}}^{i+2}.$

Finally, by Lemma 4.4.6, we get

$\langle\phi(\underline{\bm{g}};\underline{\bm{g}}_{\beta_{1}};\ldots;\underline{\bm{g}}_{\beta_{i}};\mathring{\bm{c}})\rangle_{{\bm{\beta}}}\equiv\operatorname*{\mathbb{E}}_{\mathord{\ThisStyle{\LMpt\kern
1.0pt\LMpt\framebox{$\SavedStyle 1$}\kern
1.0pt\LMpt}}\ldots\mathord{\ThisStyle{\LMpt\kern
1.0pt\LMpt\framebox{$\SavedStyle i$}\kern
1.0pt\LMpt}}}\phi(\underline{\bm{g}};\hstretch{0.7}{\talloblong}\underline{\bm{g}}\rangle^{\mathord{\ThisStyle{\LMpt\kern
1.0pt\LMpt\framebox{$\SavedStyle 1$}\kern
1.0pt\LMpt}}};\ldots;\hstretch{0.7}{\talloblong}\underline{\bm{g}}\rangle^{\mathord{\ThisStyle{\LMpt\kern
1.0pt\LMpt\framebox{$\SavedStyle i$}\kern
1.0pt\LMpt}}};\mathring{\bm{c}})=\underline{\phi}^{i+1}(\underline{\bm{g}};\mathring{\bm{c}})=\underline{x}.$

So, altogether,

$x=\langle\phi(\bm{g};\bm{g}_{\beta_{1}};\ldots;\bm{g}_{\beta_{i}};\bm{c})\rangle_{{\bm{\beta}}}\equiv\underline{x}.$

Finally, by 4.3.14, we arrive at

$g^{i+1}=Wx\equiv W\underline{x}=\underline{g}^{i+1}$

as desired. ∎

######  Remark 4.8.4.

In this proof, the preservation of equivalence under iid matrix multiplication
4.3.14 (proved using off-the-shelf operator norm tail bounds) is crucial. It
allowed us to circumvent a complex (and probably ill-fated) Gaussian
conditioning argument inside a larger, more involved induction loop. This
preservation property is a key factor behind the 4.3.5 of “vanishing.” The
slight downside to this is that initial scalars need to be
$\tilde{O}(n^{-1/2})$ (to get the equivalence going in the first place), but
that is satisfied most of the time in practice.

###  4.9 Proof of $\textsc{Ne}{\otimes}\textsc{or}\top$ Master Theorem 2.6.10

With Lemma 4.8.2, the only things left to prove are: 1) We can weaken the
requirement that the initial scalars are $\tilde{O}(n^{-1/2})$ (1.2.5) to just
that they converge to 0 almost surely; in turn the conclusion needs to be
weakened as well to almost sure convergence instead of the stronger
$\tilde{O}(n^{-1/2})$ convergence. 2) We can swap the Gaussian setup 2.6.3
with the non-Gaussian setup 2.6.4 and not only still obtain all of the above
results but also show all scalars converge in $L^{p}$ as well, for all
$p\in[1,\infty)$.

####  4.9.1 Relaxing Initial Scalar Requirement

This will follow from the “uniformly locally Lipschitz” property of
$\textsc{Ne}{\otimes}\textsc{or}\top$ programs: For any scalar $\theta$ in a
program, we can treat $\theta$ as a random function $\theta_{n}(\bm{c})$ of
initial scalars $\bm{c}$ (with randomness coming from sampling of initial
matrices and vectors) for any finite $n$. Then for any $\bm{c}$, there is a
neighborhood of $\bm{c}$ and a constant $L>0$ such that $\theta_{n}$ is almost
surely Lipschitz for all $n$ on that neighborhood with Lipschitz constant $L$.

This property in particular implies that $\theta_{n}$ is equicontinuous over
$n$ almost surely, and thus how fast or slow $\bm{c}_{n}$ converges to
$\mathring{\bm{c}}$ does not affect the limit
$\lim_{n\to\infty}\theta_{n}(\bm{c}_{n})$.

This “uniformly locally Lipschitz” property can be shown by proving a sub-
Weibull232323i.e., the probability of deviating $t$ away from the limit is
bounded by a function of the form $\exp(-C(nt)^{\alpha})$ for some power
$\alpha>0$ (usually $<1$). tail bound on the convergence of any scalar in a
program, and then performing a chaining argument [37]. The full details will
be given in a future paper.242424Note that only the Dynamical Dichotomy
Theorem (i.e., classification of abcd-parametrizations) needs to deal with
initial scalars that converge slower than $\tilde{O}(n^{-1/2})$. In
particular, the NT and $\mu$-limits only need the version of the Master
Theorem with $\tilde{O}(n^{-1/2})$ initial scalars.

####  4.9.2 Proof of Non-Gaussian $\textsc{Ne}{\otimes}\textsc{or}\top$ Master
Theorem

The non-Gaussian $\textsc{Netsor}\top$ Master Theorem ([12]) states that,
under 2.6.4, the scalars of the program converge almost surely and in $L^{p}$
for every $p\in[1,\infty)$. Our goal here is to adapt its proof to the more
general $\textsc{Ne}{\otimes}\textsc{or}\top$ case.

The overarching proof strategy of the non-Gaussian $\textsc{Netsor}\top$
Master Theorem was to smoothly interpolate between the non-Gaussian program
and the Gaussian program (c.f. [12, Defn 5.1]) and to show that for large
enough $n$, the scalars of the program do not change much along this
interpolation. In fact, the total change along this interpolation is
$\tilde{O}(n^{-1/2})$ (see the last chain of equation/inequalities before [12,
Sec 5.1]). So if we can adapt all of the reasoning to
$\textsc{Ne}{\otimes}\textsc{or}\top$, then we can obtain the
$\tilde{O}(n^{-1/2})$ convergence in 2.6.10 as well under 2.6.4.

The key technical insight enabling all of this is a bound on the moments of
mixed derivatives of a non-Gaussian program’s scalars and vectors against the
program’s matrices.

To obtain the non-Gaussian $\textsc{Ne}{\otimes}\textsc{or}\top$ Master
Theorem, the main task is to generalize this key technical insight, with which
the interpolation trick carries over to our case easily. This is done in
Lemmas 4.9.2 and LABEL:{lemma:dc_bound} below, which are useful in their own
right beyond this context. The full proof of the non-Gaussian Master Theorem
can be then be straightforwardly adapted from [12].

######  Setup 4.9.1.

Consider 2.6.4, but allow the variances of matrix entries to differ from
$n^{-1}$ but still bounded above by $\nu_{2}n^{-1}$ for some $\nu_{2}>0$
common to all matrix entries.

Below, we invoke the notion of _oblivious constants_ from [12, Defn I.1]. This
is a technical notion needed to finish the proof of the the non-Gaussian
Master Theorem, but the first time readers can ignore the comments on
oblivious constants.

######  Lemma 4.9.2 (Expected Smoothness of Vectors).

Consider a $\textsc{Ne}{\otimes}\textsc{or}\top$ program under 4.9.1. Then,
for any polynomially smooth $\psi:\mathbb{R}^{rM+M}\to\mathbb{R}$, any $p\geq
1$, and any multiset $\mathcal{P}$ of the program’s matrix entries
$\\{W_{\alpha\beta}\\}_{\alpha,\beta,W\in\mathcal{W}}$,

$\sup_{{\bm{\alpha}}\in[n]^{r}}\operatorname*{\mathbb{E}}\left|\partial^{\mathcal{P}}\psi(\bm{g}_{\alpha_{1}};\cdots;\bm{g}_{\alpha_{r}};\bm{c})\right|^{p}=O(1)\quad\text{as
$n\to\infty$.}$ (4.25)

where constant in the big-O is $(p,\mathcal{P})$-oblivious wrt $\psi$ and the
program.

This generalizes [12, Lemma I.3] to $\textsc{Ne}{\otimes}\textsc{or}\top$.

###### Proof.

In the original proof in [12, Sec I], replace $\phi(x^{1},\ldots,x^{k})$ with
$\phi(x^{1};\cdots;x^{k})$ everywhere. As the original proof essentially
factors through arguments about the “supremum” over all indices
$\alpha\in[n]$, it can be adapted straightforwardly to the “supremum” over all
multi-indices ${\bm{\alpha}}\in[n]^{r}$. ∎

######  Lemma 4.9.3 (Expected Smoothness of Scalars).

Consider a program in 4.9.1. Then for any $p\geq 1$, any _nonempty_ multiset
$\mathcal{P}$ of the program’s matrix entries
$\\{W_{\alpha\beta}\\}_{\alpha,\beta,W\in\mathcal{W}}$,, and any scalar $c$ of
the program,

$\operatorname*{\mathbb{E}}\left|\partial^{\mathcal{P}}c\right|^{p}=O(n^{-p})\quad\text{as
$n\to\infty$.}$ (4.26)

Furthermore, the constant in the big-O is $(p,\mathcal{P})$-oblivious wrt the
program.

This generalizes [12, Lemma J.6] to $\textsc{Ne}{\otimes}\textsc{or}\top$.

###### Proof.

Construct the backpropagation program (2.9.14), which is another
$\textsc{Ne}{\otimes}\textsc{or}\top$ program. Then proceed as in the proof of
[12, Lemma J.6]. ∎

##  Chapter 5 Experiments

###  5.1 Numerical Verification

We perform numerical experiments to validate our theory. It is intractable to
compute the exact infinite-width limits for general $\bm{Q}$, since the
expectations required to evaluate the infinite-width dynamics in both limits
do not admit an analytical solution (even for the Neural Tangent Limit). We
thus employ Monte Carlo simulations to approximate these expectations.

We test LABEL:{thm:NT_MLP_memoryful} and 2.7.3 by training ReLU MLPs ($L=4$
for NTP and $L=2$ for $\mu$P) on $\mathbb{R}^{10}$ Gaussian inputs and a unit
output. We use the standard L2 loss function, regressing to random targets. We
train networks with different widths using the Adam optimizer with a learning
rate of $\eta=0.2$ and $\epsilon=10^{-4}$, using 100 training samples and
conducting 10 trials for each width. To account for varying initial outputs
and loss derivatives per weight initialization, we subtract the initialized
network output from the output for each sample, ensuring that the output is
zero at initialization for all inputs.

We approximate the infinite-width training dynamics by estimating the
expectations in 2.4.4 and 2.7.3 using Monte Carlo simulations. As the initial
loss derivatives are deterministic with zero outputs, the infinite-width
dynamics can be estimated without actually constructing a network. To compare
the finite and infinite width neural networks’ evolution, we assess the output
on random inputs at each iteration. Our results are summarized in Fig. 5.1 and
Fig. 5.2. As anticipated, the training dynamics converge to the infinite-width
dynamics as the width increases.

|  |
---|---|---
|  |
|  |
|  |
(a) | (b) | (c)
Figure 5.1: Adam training dynamics of finite and infinite-width networks in NTP. We train networks of widths 64 (a), 512 (b), 7000 (c), and track the outputs for 4 random inputs (one per row) at each iteration as the network trains. We compute the output distribution over 10 independent runs for each network, and compare with the infinite-width dynamics (black curve). As the width grows, the network function converges to that of the infinite-width dynamics captured in 2.4.9. |  |
---|---|---
|  |
|  |
|  |
(a) | (b) | (c)
Figure 5.2: Adam training dynamics of finite and infinite-width networks in
$\mu$P. We train networks of widths 64 (a), 512 (b), 7000 (c), and track the
outputs for 4 random inputs (one per row) at each iteration as the network
trains. We compute the output distribution over 10 independent runs for each
network, and compare with the infinite-width dynamics (black curve). As the
width grows, the network function converges to that of the infinite-width
dynamics captured in 2.7.3.

### Acknowledgements

In alphabetical order, we would like to thank Jeremy Bernstein, Nikhil Ghosh,
Dror Ironi, Ariel Landau, Sadhika Malladi, Jamie Simon, and Josh Susskind for
providing insightful comments and discussion.

## References

  * Alemohammad et al. [2021] Sina Alemohammad, Zichao Wang, Randall Balestriero, and Richard Baraniuk.  The recurrent neural tangent kernel.  _ArXiv_ , abs/2006.10246, 2021.
  * Allen-Zhu et al. [2019] Zeyuan Allen-Zhu, Yuanzhi Li, and Zhao Song.  A convergence theory for deep learning via over-parameterization.  _ArXiv_ , abs/1811.03962, 2019.
  * Arora et al. [2019] Sanjeev Arora, S. Du, Wei Hu, Zhiyuan Li, R. Salakhutdinov, and Ruosong Wang.  On exact computation with an infinitely wide neural net.  In _NeurIPS_ , 2019.
  * Bernstein et al. [2018] Jeremy Bernstein, Yu-Xiang Wang, Kamyar Azizzadenesheli, and Anima Anandkumar.  signSGD: Compressed Optimisation for Non-Convex Problems, February 2018.  URL https://arxiv.org/abs/1802.04434v3.
  * Bernstein et al. [2021] Jeremy Bernstein, Arash Vahdat, Yisong Yue, and Ming-Yu Liu.  On the distance between two neural networks and the stability of learning.  _arXiv:2002.03432 [cs, math, stat]_ , January 2021.  URL http://arxiv.org/abs/2002.03432.
  * Carbonnelle & De Vleeschouwer [2019] Simon Carbonnelle and Christophe De Vleeschouwer.  Layer rotation: a surprisingly powerful indicator of generalization in deep networks?  _arXiv:1806.01603 [cs, stat]_ , July 2019.  URL http://arxiv.org/abs/1806.01603.
  * Chizat & Bach [2018] Lénaïc Chizat and Francis R. Bach.  On the global convergence of gradient descent for over-parameterized models using optimal transport.  In _NeurIPS_ , 2018.
  * Chizat et al. [2019] Lénaïc Chizat, Edouard Oyallon, and Francis R. Bach.  On lazy training in differentiable programming.  In _NeurIPS_ , 2019.
  * Dozat [2016] Timothy Dozat.  Incorporating nesterov momentum into adam.  2016\.
  * Du et al. [2019] Simon Shaolei Du, Kangcheng Hou, Barnabás Póczos, Ruslan Salakhutdinov, Ruosong Wang, and Keyulu Xu.  Graph neural tangent kernel: Fusing graph neural networks with graph kernels.  _ArXiv_ , abs/1905.13192, 2019.
  * Duchi et al. [2010] John C. Duchi, Elad Hazan, and Yoram Singer.  Adaptive subgradient methods for online learning and stochastic optimization.  In _J. Mach. Learn. Res._ , 2010.
  * Golikov & Yang [2022] Eugene Golikov and Greg Yang.  Non-Gaussian Tensor Programs.  October 2022.  URL https://openreview.net/forum?id=AcHUIG2wA8-.
  * Hanin & Nica [2020] Boris Hanin and Mihai Nica.  Finite depth and width corrections to the neural tangent kernel.  _ArXiv_ , abs/1909.05989, 2020.
  * Hinton & Neal [1995] Geoffrey E. Hinton and R. Neal.  Bayesian learning for neural networks.  1995\.
  * Hron et al. [2020] Jiri Hron, Yasaman Bahri, Jascha Narain Sohl-Dickstein, and Roman Novak.  Infinite attention: Nngp and ntk for deep attention networks.  In _ICML_ , 2020.
  * Huang & Yau [2020] Jiaoyang Huang and H. T. Yau.  Dynamics of deep neural networks and neural tangent hierarchy.  _ArXiv_ , abs/1909.08156, 2020.
  * Huang et al. [2020] Xiaoshan Huang, Felipe Pérez, Jimmy Ba, and Maksims Volkovs.  Improving transformer optimization through better initialization.  In _ICML_ , 2020.
  * Jacot et al. [2018] Arthur Jacot, Franck Gabriel, and Clément Hongler.  Neural tangent kernel: convergence and generalization in neural networks (invited paper).  _Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing_ , 2018.
  * Kingma & Ba [2015] Diederik P. Kingma and Jimmy Ba.  Adam: A method for stochastic optimization.  _CoRR_ , abs/1412.6980, 2015.
  * Lee et al. [2018] Jaehoon Lee, Y. Bahri, Roman Novak, S. Schoenholz, Jeffrey Pennington, and Jascha Sohl-Dickstein.  Deep neural networks as gaussian processes.  _ArXiv_ , abs/1711.00165, 2018.
  * Lee et al. [2019] Jaehoon Lee, Lechao Xiao, Samuel S. Schoenholz, Yasaman Bahri, Jascha Sohl-Dickstein, and Jeffrey Pennington.  Wide neural networks of any depth evolve as linear models under gradient descent.  _ArXiv_ , abs/1902.06720, 2019.
  * Littwin et al. [2020a] Etai Littwin, T. Galanti, and L. Wolf.  On random kernels of residual architectures.  _arXiv: Learning_ , 2020a.
  * Littwin et al. [2020b] Etai Littwin, Tomer Galanti, Lior Wolf, and Greg Yang.  On infinite-width hypernetworks.  _arXiv: Learning_ , 2020b.
  * Littwin et al. [2021] Etai Littwin, Omid Saremi, Shuangfei Zhai, Vimal Thilak, Hanlin Goh, Joshua M. Susskind, and Greg Yang.  Implicit Acceleration and Feature Learning in Infinitely Wide Neural Networks with Bottlenecks, July 2021.  URL http://arxiv.org/abs/2107.00364.  arXiv:2107.00364 [cs].
  * Liu et al. [2020] Liyuan Liu, Xiaodong Liu, Jianfeng Gao, Weizhu Chen, and Jiawei Han.  Understanding the difficulty of training transformers.  _ArXiv_ , abs/2004.08249, 2020.
  * Liu et al. [2021] Yang Liu, Jeremy Bernstein, Markus Meister, and Yisong Yue.  Learning by Turning: Neural Architecture Aware Optimisation.  _arXiv:2102.07227 [cs]_ , September 2021.  URL http://arxiv.org/abs/2102.07227.
  * Loshchilov & Hutter [2017] Ilya Loshchilov and Frank Hutter.  Decoupled weight decay regularization.  In _International Conference on Learning Representations_ , 2017.
  * Malladi et al. [2022] Sadhika Malladi, Alexander Wettig, Dingli Yu, Danqi Chen, and Sanjeev Arora.  A Kernel-Based View of Language Model Fine-Tuning, October 2022.  URL https://arxiv.org/abs/2210.05643v3.
  * Matthews et al. [2018] A. Matthews, M. Rowland, J. Hron, R. Turner, and Zoubin Ghahramani.  Gaussian process behaviour in wide deep neural networks.  _ArXiv_ , abs/1804.11271, 2018.
  * Mei et al. [2018a] Song Mei, Andrea Montanari, and Phan-Minh Nguyen.  A mean field view of the landscape of two-layer neural networks.  _Proceedings of the National Academy of Sciences of the United States of America_ , 115:E7665 – E7671, 2018a.
  * Mei et al. [2018b] Song Mei, Andrea Montanari, and Phan-Minh Nguyen.  A mean field view of the landscape of two-layer neural networks.  _Proceedings of the National Academy of Sciences of the United States of America_ , 115:E7665 – E7671, 2018b.
  * Nguyen & Pham [2020] Phan-Minh Nguyen and Huy-Tuan Pham.  A rigorous framework for the mean field limit of multilayer neural networks.  _ArXiv_ , abs/2001.11443, 2020.
  * Novak et al. [2019] Roman Novak, L. Xiao, Y. Bahri, Jaehoon Lee, Greg Yang, J. Hron, D. Abolafia, Jeffrey Pennington, and Jascha Sohl-Dickstein.  Bayesian deep convolutional networks with many channels are gaussian processes.  In _ICLR_ , 2019.
  * Rotskoff & Vanden-Eijnden [2018] Grant M. Rotskoff and Eric Vanden-Eijnden.  Neural networks as interacting particle systems: Asymptotic convexity of the loss landscape and universal scaling of the approximation error.  _ArXiv_ , abs/1805.00915, 2018.
  * Shazeer & Stern [2018] Noam Shazeer and Mitchell Stern.  Adafactor: Adaptive Learning Rates with Sublinear Memory Cost.  April 2018.  URL https://arxiv.org/abs/1804.04235v1.
  * Sirignano & Spiliopoulos [2020] Justin A. Sirignano and Konstantinos Spiliopoulos.  Mean field analysis of neural networks: A law of large numbers.  _SIAM J. Appl. Math._ , 80:725–752, 2020.
  * Talagrand [2014] Michel Talagrand.  _Upper and lower bounds for stochastic processes: modern methods and classical problems_.  Number 3. Folge, volume 60 in Ergebnisse der Mathematik und ihrer Grenzgebiete : a series of modern surveys in mathematics. Springer, Heidelberg ; New York, 2014.  ISBN 978-3-642-54074-5.  OCLC: ocn873529598.
  * Tao [2012] Terence Tao.  Topics in random matrix theory.  _Graduate studies in Mathematics_ , 132, 2012.
  * Vaswani et al. [2017] Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N. Gomez, L. Kaiser, and Illia Polosukhin.  Attention is all you need.  _ArXiv_ , abs/1706.03762, 2017.
  * Yaida [2022] Sho Yaida.  Meta-Principled Family of Hyperparameter Scaling Strategies.  Technical Report arXiv:2210.04909, arXiv, October 2022.  URL http://arxiv.org/abs/2210.04909.  arXiv:2210.04909 [hep-th, stat] type: article.
  * Yang [2019a] Greg Yang.  Tensor programs i: Wide feedforward or recurrent neural networks of any architecture are gaussian processes.  _ArXiv_ , abs/1910.12478, 2019a.
  * Yang [2019b] Greg Yang.  Scaling Limits of Wide Neural Networks with Weight Sharing: Gaussian Process Behavior, Gradient Independence, and Neural Tangent Kernel Derivation.  _arXiv:1902.04760 [cond-mat, physics:math-ph, stat]_ , February 2019b.
  * Yang [2020a] Greg Yang.  Tensor programs ii: Neural tangent kernel for any architecture.  _ArXiv_ , abs/2006.14548, 2020a.
  * Yang [2020b] Greg Yang.  Tensor programs iii: Neural matrix laws.  _ArXiv_ , abs/2009.10685, 2020b.
  * Yang & Hu [2020] Greg Yang and Edward J. Hu.  Feature learning in infinite-width neural networks.  _ArXiv_ , abs/2011.14522, 2020.
  * Yang & Littwin [2021] Greg Yang and Etai Littwin.  Tensor programs iib: Architectural universality of neural tangent kernel training dynamics.  _ArXiv_ , abs/2105.03703, 2021.
  * Yang et al. [2022] Greg Yang, Edward J. Hu, Igor Babuschkin, Szymon Sidor, Xiaodong Liu, David Farhi, Nick Ryder, Jakub Pachocki, Weizhu Chen, and Jianfeng Gao.  Tensor Programs V: Tuning Large Neural Networks via Zero-Shot Hyperparameter Transfer.  _arXiv:2203.03466 [cond-mat]_ , March 2022.  URL http://arxiv.org/abs/2203.03466.  arXiv: 2203.03466.
  * Yin et al. [1988] Y. Q. Yin, Z. D. Bai, and P. R. Krishnaiah.  On the limit of the largest eigenvalue of the large dimensional sample covariance matrix.  _Probability Theory and Related Fields_ , 78(4):509–521, August 1988.  ISSN 0178-8051, 1432-2064.  doi: 10.1007/BF00353874.  URL https://link.springer.com/10.1007/BF00353874.
  * You et al. [2017] Yang You, Igor Gitman, and Boris Ginsburg.  Large Batch Training of Convolutional Networks.  _arXiv:1708.03888 [cs]_ , September 2017.  URL http://arxiv.org/abs/1708.03888.
  * You et al. [2020] Yang You, Jing Li, Sashank Reddi, Jonathan Hseu, Sanjiv Kumar, Srinadh Bhojanapalli, Xiaodan Song, James Demmel, Kurt Keutzer, and Cho-Jui Hsieh.  Large Batch Optimization for Deep Learning: Training BERT in 76 minutes.  _arXiv:1904.00962 [cs, stat]_ , January 2020.  URL http://arxiv.org/abs/1904.00962.
  * Zhang et al. [2019] J. Zhang, Sai Praneeth Karimireddy, Andreas Veit, Seungyeon Kim, Sashank J. Reddi, Surinder Kumar, and Suvrit Sra.  Why adam beats sgd for attention models.  _ArXiv_ , abs/1912.03194, 2019.
  * Zhou et al. [2018] Zhiming Zhou, Qingru Zhang, Guansong Lu, Hongwei Wang, Weinan Zhang, and Yong Yu.  Adaptive learning rate methods.  2018\.