# Feature Normalization Prevents Collapse of Non-contrastive Learning Dynamics

Han Bao
Kyoto University
<EMAIL_ADDRESS>
###### Abstract

Contrastive learning is a self-supervised representation learning framework,
where two positive views generated through data augmentation are made similar
by an attraction force in a data representation space, while a repulsive force
makes them far from negative examples. Non-contrastive learning, represented
by BYOL and SimSiam, further gets rid of negative examples and improves
computational efficiency. While learned representations may collapse into a
single point due to the lack of the repulsive force at first sight, [35]
revealed through the learning dynamics analysis that the representations can
avoid collapse if data augmentation is sufficiently stronger than
regularization. However, their analysis does not take into account commonly-
used _feature normalization_ , a normalizer before measuring the similarity of
representations, and hence excessively strong regularization may collapse the
dynamics, which is an unnatural behavior under the presence of feature
normalization. Therefore, we extend the previous theory based on the L2 loss
by considering the cosine loss, which involves feature normalization. We show
that the cosine loss induces sixth-order dynamics (while the L2 loss induces a
third-order one), in which a stable equilibrium dynamically emerges even if
there are only collapsed solutions with given initial parameters. Thus, we
offer a new understanding that feature normalization plays an important role
in robustly preventing the dynamics collapse.

##  1 Introduction

Modern machine learning often owes to the success of self-supervised
representation learning, which attempts to capture the underlying data
structure useful for downstream tasks by solving an auxiliary learning task.
Among self-supervised learning, contrastive learning is a popular framework,
in which data augmentation generates two positive views from the original data
and their encoded features are contrasted with background negative samples [8,
37]. In particular, [9] conducted large-scale contrastive learning with 10K+
negative samples to establish comparable downstream classification performance
even to supervised vision learners. The benefit of large-scale negative
samples has been observed both theoretically [27, 3] and empirically [7, 34],
but it is disadvantageous in terms of computational efficiency.

By contrast, non-contrastive learning trains a feature encoder with only
positive views, leveraging additional implementation tricks. The seminal work
[15] proposed BYOL (Bootstrap Your Own Latent) to introduce the momentum
encoder and apply gradient stopping for one encoder branch only. The follow-up
work [7] showed that gradient stopping brings success into non-contrastive
learning via a simplified architecture SimSiam (Simple Siamese representation
learning). Despite their empirical successes, non-contrastive learning lacks
the repulsive force induced by negative samples and learned representations
may trivially collapse to a constant zero with only the attractive force
between positive views. Folklore says that asymmetric architectures between
the two branches are behind the success [42]. [35] first tackled the question
_why non-contrastive learning does not collapse to zero_ , by specifically
studying the learning dynamics of BYOL. They tracked the eigenmodes of the
encoder parameters and found that the eigenmode dynamics have non-trivial
equilibriums unless the regularization is overly strong. To put it
differently, the balance between data augmentation and regularization controls
the existence of non-trivial solutions. However, this analysis dismisses
_feature normalization_ practically added to normalize the encoded positive
views before computing their similarity. As feature normalization blows up
when encoded features approach zero, the analysis of [35] may fail to explain
the behavior of the non-contrastive learning dynamics with strong
regularization. Indeed, our pilot study (Fig. 1) reveals that SimSiam learning
dynamics remains to stabilize with much heavier regularization than the
default strength $\rho=10^{-4}$.

Figure 1:  Linear probing accuracy of SimSiam representations of the CIFAR-10
dataset [23] is indifferent to the weight decay intensity $\rho$. The vertical
axis indicates fine-tuning epochs of the linear classifier. For non-
contrastive pre-training, we used the ResNet-18 model [21] with the initial
learning rate $5\times 10^{-6}$, $500$ epochs, and different weight decay
intensities ($\rho$) indicated in the legends. Other parameters and setup were
inherited from the official implementation [7].

Therefore, we study the non-contrastive learning dynamics with feature
normalization: an encoded feature ${\bm{\Phi}}{\mathbf{x}}$ for an input
${\mathbf{x}}\in{\mathbb{R}}^{d}$ and encoder
${\bm{\Phi}}\in{\mathbb{R}}^{h\times d}$ is normalized as
${\bm{\Phi}}{\mathbf{x}}/\left\lVert{{\bm{\Phi}}{\mathbf{x}}}\right\rVert_{2}$.
The main challenge is that feature normalization yields a highly nonlinear
dynamics because parameter norms appear in the denominator of a loss function.
This is a major reason why the existing studies on non-contrastive learning
confine themselves to the L2-loss dynamics without feature normalization [35,
41, 30, 45, 25, 36]. Our approach is to consider the high-dimensional limit
$d,h\to\infty$, where the feature norm
$\left\lVert{{\bm{\Phi}}{\mathbf{x}}}\right\rVert_{2}$ concentrates around a
constant with proper parameter initialization. In this way, we can analyze the
learning dynamics with feature normalization. Under the setup of synthetic
data, we derive the learning dynamics of encoder parameters (Section 4), and
disentangle it into the eigenmode dynamics with further assumptions (Section
5.1). The eigenmode dynamics is sixth-order, and we find that a stable
equilibrium emerges even if there is no stable equilibrium with the initial
parametrization and regularization strength (Section 5.2). This dynamics
behavior is in contrast to the third-order dynamics of [35], compared in
Section 5.3. We further observe the above findings in numerical simulation
(Section 5.4). Overall, we demonstrate how feature normalization prevents
representation collapse using a synthetic model. We believe that our
techniques open a new direction to understanding self-supervised
representation learning.

##  2 Related work

Recent advances in contrastive learning can be attributed to the InfoNCE loss
[37], which can be regarded as a multi-sample mutual information estimator
between the two views [28, 31]. [9] showed that large-scale contrastive
representation learning can potentially perform comparably to supervised
vision learners. This empirical success owes to a huge number of negative
samples, forming a repulsive force in contrastive learning. Follow-up studies
confirmed that larger negative samples are generally beneficial for downstream
performance [7, 34], and the phenomenon has been verified through theoretical
analysis of the downstream classification error [27, 46, 3, 1], whereas larger
negative samples require heavier computation.

Non-contrastive learning is yet another stream of contrastive learning,
without requiring any negative samples. Although it may fail due to lack of
the repulsive force, additional tricks in architectures assist the learned
representation avoiding a trivial solution. BYOL [15] is the initial attempt
by introducing the momentum encoder and gradient stopping to make two encoder
branches asymmetric. Later, SimSiam [7] revealed that gradient stopping is
dominant. Both BYOL and SimSiam emphasize the importance of asymmetric
architectures. Other recent approaches to non-contrastive learning are to
conduct representation learning and clustering iteratively (e.g., SwAV [10]
and TCR [24]), to impose regularization on the representation covariance
matrix (e.g., Barlow Twins [48], Whitening MSE [13], and VICReg [5]), and to
leverage knowledge distillation (e.g., DINO [11]). While these methods
empirically succeed, theoretical understanding of the mechanism of non-
contrastive learning still falls behind. In particular, we need to answer
_why_ the non-contrastive dynamics does not collapse without the repulsive
force, and _what_ the non-contrastive dynamics learns. For the latter
question, recent studies revealed that it implicitly learns a subspace [41],
sparse signals [44], a permutation matrix over latent variables [30], and a
low-pass filter of parameter spectra [49]. Besides, contrastive supervision is
theoretically useful for downstream classification under a simplified setup
[4, 6].

Why does non-contrastive dynamics remain stable? The seminal work [35]
analyzed the BYOL/SimSiam dynamics with a two-layer network and found that
data augmentation behaves as a repulsive force to prevent eigenmodes of
network parameters from collapsing if augmentation is sufficiently stronger
than regularization. We closely follow this analysis to delineate that feature
normalization serves as another repulsive force and regularization may not
destroy the dynamics. Our focus is to understand how a non-trivial equilibrium
emerges in self-supervised learning dynamics, whereas several prior studies
investigated when and how fast general gradient descent dynamics with weight
normalization converges [12, 47]. Further, [45] analyzed the SimSiam dynamics
with a trainable prediction head to reveal the conditions preventing
representation collapse. [36] investigated the same phenomenon in a
reinforcement learning setup. While we have less understanding of other non-
contrastive dynamics, [25] showed that some non-contrastive dynamics including
VICReg may cause dimensional collapse.

##  3 Model and loss functions

#### Notations.

The $n$-dimensional Euclidean space and hypersphere are denoted by
${\mathbb{R}}^{n}$ and ${\mathbb{S}}^{n-1}$, respectively. The L2, Frobenius,
and spectral norms are denoted by $\left\lVert{\cdot}\right\rVert_{2}$,
$\left\lVert{\cdot}\right\rVert_{\mathrm{F}}$, and
$\left\lVert{\cdot}\right\rVert$, respectively. The $n\times n$ identity
matrix is denoted by ${\mathbf{I}}_{n}$, or by ${\mathbf{I}}$ whenever clear
from the context. For two vectors
${\mathbf{u}},{\mathbf{v}}\in{\mathbb{R}}^{n}$,
$\left\langle{{\mathbf{u}}},{{\mathbf{v}}}\right\rangle={\mathbf{u}}^{\top}{\mathbf{v}}$
denotes the inner product. For two matrices
${\mathbf{A}},{\mathbf{B}}\in{\mathbb{R}}^{n_{1}\times n_{2}}$,
$\left\langle{{\mathbf{A}}},{{\mathbf{B}}}\right\rangle_{\mathrm{F}}=\sum_{i,j}A_{i,j}B_{i,j}$
denotes the Frobenius inner product. For a time-dependent matrix
${\mathbf{A}}$ (such as network parameters), we make the time dependency
explicitly by ${\mathbf{A}}(t)$ if necessary. The Moore–Penrose inverse of a
matrix ${\mathbf{A}}$ is denoted by ${{{\mathbf{A}}}^{\dagger}}$. The set of
$n\times n$ symmetric matrices is denoted by
${\mathbb{S}\mathrm{ym}}_{n}\coloneqq\left\\{{{\mathbf{A}}\in{\mathbb{R}}^{n\times
n}|{\mathbf{A}}={\mathbf{A}}^{\top}}\right\\}$. The upper and lower asymptotic
orders are denoted by ${\mathcal{O}}(\cdot)$ and $\Omega(\cdot)$,
respectively. The little-o and little-$\omega$ are denoted in the same way.
The stochastic orders of boundedness and convergence indexed by $h$ are
denoted by ${{\mathcal{O}}_{{\mathbb{P}}}}(\cdot)$ and
${o_{{\mathbb{P}}}}(\cdot)$, respectively.

#### Model.

In this work, we focus on the SimSiam model [7] as a non-contrastive learner
and consider the following two-layer linear network, following the analysis of
[35]. We first sample a $d$-dimensional input feature
${\mathbf{x}}_{0}\sim{\mathcal{D}}$ as an anchor and apply a data augmentation
to obtain two views
${\mathbf{x}},{\mathbf{x}}^{\prime}\sim{\mathcal{D}}^{\mathrm{aug}}_{{\mathbf{x}}_{0}}$,
where ${\mathcal{D}}^{\mathrm{aug}}_{{\mathbf{x}}_{0}}$ is the augmentation
distribution. While affine transforms or random maskings of input images are
common as data augmentation [9, 17], we assume the isotropic Gaussian
augmentation distribution
${\mathcal{D}}^{\mathrm{aug}}_{{\mathbf{x}}_{0}}={\mathcal{N}}({\mathbf{x}}_{0},\sigma^{2}{\mathbf{I}})$
to simplify and let $\sigma^{2}$ represent the augmentation intensity. For the
input distribution, we suppose the multivariate Gaussian
${\mathcal{D}}={\mathcal{N}}({\mathbf{0}},{\bm{\Sigma}})$ to devote ourselves
to understanding dynamics, as in [32, 35].

Our neural network encoder consists of two linear layers without biases:
representation net ${\bm{\Phi}}\in{\mathbb{R}}^{h\times d}$ and projection
head ${\mathbf{W}}\in{\mathbb{R}}^{h\times h}$ as the first and second layers,
respectively, where $h$ is the representation dimension. For the two views
${\mathbf{x}},{\mathbf{x}}^{\prime}$, we obtain _online_ representation
${\bm{\Phi}}{\mathbf{x}}\in{\mathbb{R}}^{h}$ and _target_ representation
${\bm{\Phi}}{\mathbf{x}}^{\prime}\in{\mathbb{R}}^{h}$, and predict the target
from the online representation by
${\mathbf{W}}{\bm{\Phi}}{\mathbf{x}}\in{\mathbb{R}}^{h}$. Here, we use the
same representation parameters ${\bm{\Phi}}$ for both views without the
exponential moving average [15] as this ablation reportedly works comparably
in SimSiam [7].

#### Loss functions.

BYOL/SimSiam introduce _asymmetry_ of the two branches with the stop gradient
operator, denoted by ${\mathrm{StopGrad}}(\cdot)$, where parameters are
regarded as constants during backpropagation [7]. [35] used the following _L2
loss_ to describe non-contrastive dynamics:

${{{\mathcal{L}}}_{\mathrm{sq}}}({\bm{\Phi}},{\mathbf{W}})\coloneqq\frac{1}{2}\operatorname*{{\mathbb{E}}}_{{\mathbf{x}}_{0}}\operatorname*{{\mathbb{E}}}_{{\mathbf{x}},{\mathbf{x}}^{\prime}\mid{\mathbf{x}}_{0}}[\left\lVert{{\mathbf{W}}{\bm{\Phi}}{\mathbf{x}}-{\mathrm{StopGrad}}({\bm{\Phi}}{\mathbf{x}}^{\prime})}\right\rVert_{2}^{2}],$
(1)

where the expectations are taken over
${\mathbf{x}},{\mathbf{x}}^{\prime}\sim{\mathcal{D}}^{\mathrm{aug}}_{{\mathbf{x}}_{0}}$
and ${\mathbf{x}}_{0}\sim{\mathcal{D}}$. Thanks to the simple closed-form
solution, the L2 loss has been used in most of the existing analyses of self-
supervised learning dynamics [41, 36, 49].

We instead focus on the following _cosine loss_ to take feature normalization
into account, which is a key factor in the success of contrastive
representation learning [43]:

${{{\mathcal{L}}}_{\mathrm{cos}}}({\bm{\Phi}},{\mathbf{W}})\coloneqq\operatorname*{{\mathbb{E}}}_{{\mathbf{x}}_{0}}\operatorname*{{\mathbb{E}}}_{{\mathbf{x}},{\mathbf{x}}^{\prime}\mid{\mathbf{x}}_{0}}\left[-\frac{\left\langle{{\mathbf{W}}{\bm{\Phi}}{\mathbf{x}}},{{\mathrm{StopGrad}}({\bm{\Phi}}{\mathbf{x}}^{\prime})}\right\rangle}{\left\lVert{{\mathbf{W}}{\bm{\Phi}}{\mathbf{x}}}\right\rVert_{2}\left\lVert{{\mathrm{StopGrad}}({\bm{\Phi}}{\mathbf{x}}^{\prime})}\right\rVert_{2}}\right].$
(2)

Importantly, the cosine loss has been used in most practical implementations
[15, 7], including a reproductive research [18] of simulations in [35].
Subsequently, the weight decay
$R({\bm{\Phi}},{\mathbf{W}})\coloneqq\frac{\rho}{2}(\left\lVert{{\bm{\Phi}}}\right\rVert_{\mathrm{F}}^{2}+\left\lVert{{\mathbf{W}}}\right\rVert_{\mathrm{F}}^{2})$
is added with a regularization strength $\rho>0$.

##  4 Non-contrastive dynamics in thermodynamical limit

Let us focus on the cosine loss and derive its non-contrastive dynamics via
the gradient flow. See Appendix B for the proofs of lemmas provided
subsequently. As the continuous limit of the gradient descent where learning
rates are taken to be infinitesimal [32], we characterize time evolution of
the network parameters by the following simultaneous ordinal differential
equation:

$\dot{\bm{\Phi}}=-\nabla_{\bm{\Phi}}\\{{{{\mathcal{L}}}_{\mathrm{cos}}}({\bm{\Phi}},{\mathbf{W}})+R({\bm{\Phi}},{\mathbf{W}})\\},\quad\dot{\mathbf{W}}=-\nabla_{\mathbf{W}}\\{{{{\mathcal{L}}}_{\mathrm{cos}}}({\bm{\Phi}},{\mathbf{W}})+R({\bm{\Phi}},{\mathbf{W}})\\}.$
(3)

To derive the dynamics, several assumptions are imposed.

######  Assumption 1 (Symmetric projection).

${\mathbf{W}}\in{\mathbb{S}\mathrm{ym}}_{h}$ holds during time evolution.

######  Assumption 2 (Input distribution).

${\mathcal{D}}={\mathcal{N}}({\mathbf{0}},{\mathbf{I}})$ and
${\bm{\Sigma}}={\mathbf{I}}$.

######  Assumption 3 (Thermodynamical limit).

$d,h\to\infty$, and $d/h\to\alpha$ for some $\alpha\in(0,1)$.

######  Assumption 4 (Parameter initialization).

${\bm{\Phi}}$ is initialized with
$\sqrt{d}\cdot{\bm{\Phi}}(0)_{ij}\sim{\mathcal{N}}(0,1)$ for
$i\in[h],j\in[d]$. ${\mathbf{W}}$ is initialized with
$\sqrt{h}\cdot{\mathbf{W}}(0)_{ij}\sim{\mathcal{N}}(0,1)$ for $i,j\in[h]$.

Assumptions 1 and 2 are borrowed from [35] and simplify subsequent analyses.
We empirically verify that the non-contrastive dynamics maintains the symmetry
of ${\mathbf{W}}$ during the training later (Section 5.4). Assumption 3 is a
cornerstone to our analysis: the high-dimensional limit makes Gaussian random
vectors concentrate on a sphere, which leads to a closed-form solution for the
cosine loss dynamics. We suppose that the common hidden unit size $h=512$
(used in SimSiam) is sufficient to bring into the high-dimensional
limit—though the high-dimensional regime of representations would be arguable
with the low-dimensional manifold assumption being in one’s mind. Assumption 4
is a standard initialization scale empirically in the He initialization [20]
and theoretically in the neural tangent kernel regime [22]. This
initialization scale maintains norms of the random matrices ${\bm{\Phi}}$ and
${\mathbf{W}}{\bm{\Phi}}$ without vanishing or exploding under the
thermodynamical limit.

######  Lemma 1.

Parameter matrices ${\mathbf{W}}$ and ${\bm{\Phi}}$ evolve as follows:

$\displaystyle{\mathbf{W}}^{\top}\dot{\mathbf{W}}$
$\displaystyle={\mathbf{H}}-\rho{\mathbf{W}}{\mathbf{W}}^{\top},$ (4)
$\displaystyle\dot{\bm{\Phi}}{\bm{\Phi}}^{\top}{\mathbf{W}}^{\top}$
$\displaystyle={\mathbf{W}}^{\top}{\mathbf{H}}-\rho{\bm{\Phi}}{\bm{\Phi}}^{\top}{\mathbf{W}}^{\top},$

where
${\mathbf{H}}\coloneqq\operatorname*{{\mathbb{E}}}[{\mathbf{z}}^{\prime}{\bm{\omega}}^{\top}-({\bm{\omega}}^{\top}{\mathbf{z}}^{\prime}){\bm{\omega}}{\bm{\omega}}^{\top}]$,
${\mathbf{z}}\coloneqq{\bm{\Phi}}{\mathbf{x}}^{\prime}/\left\lVert{{\bm{\Phi}}{\mathbf{x}}^{\prime}}\right\rVert_{2}$,
and
${\bm{\omega}}\coloneqq{\mathbf{W}}{\bm{\Phi}}{\mathbf{x}}/\left\lVert{{\mathbf{W}}{\bm{\Phi}}{\mathbf{x}}}\right\rVert_{2}$.
The expectation in ${\mathbf{H}}$ is taken over
${\mathbf{x}}_{0},{\mathbf{x}}$, and ${\mathbf{x}}^{\prime}$.

We will analyze Eq. 4 to see when the dynamics stably converges to a non-
trivial solution. To solve it, we need to evaluate ${\mathbf{H}}$ first. This
involves expectations with ${\mathbf{z}}^{\prime}$ and ${\bm{\omega}}$, which
are normalized Gaussian vectors and cannot be straightforwardly evaluated.
Here, we take a step further by considering the thermodynamical limit
(Assumption 3), where norms of Gaussian vectors are concentrated. This regime
allows us to directly evaluate Gaussian random vectors instead of the
normalized ones.

######  Lemma 2.

Under Assumptions 1, 4, 2 and 3, for a fixed ${\mathbf{x}}_{0}$, the norms of
${\bm{\Phi}}{\mathbf{x}}$ and ${\mathbf{W}}{\bm{\Phi}}{\mathbf{x}}$ are
concentrated:

$\displaystyle\left\lVert{\tfrac{1}{\sqrt{h\sigma^{2}}}{\bm{\Phi}}{\mathbf{x}}}\right\rVert_{2}^{2}$
$\displaystyle=\left\lVert{\tfrac{1}{\sqrt{h}}{\bm{\Phi}}}\right\rVert_{\mathrm{F}}^{2}+\left\lVert{\tfrac{1}{\sqrt{h\sigma^{2}}}{\bm{\Phi}}{\mathbf{x}}_{0}}\right\rVert_{2}^{2}+{o_{{\mathbb{P}}}}(1),$
$\displaystyle\left\lVert{\tfrac{1}{\sqrt{h^{2}\sigma^{2}}}{\mathbf{W}}{\bm{\Phi}}{\mathbf{x}}}\right\rVert_{2}^{2}$
$\displaystyle=\left\lVert{\tfrac{1}{\sqrt{h^{2}}}{\mathbf{W}}{\bm{\Phi}}}\right\rVert_{\mathrm{F}}^{2}+\left\lVert{\tfrac{1}{\sqrt{h^{2}\sigma^{2}}}{\mathbf{W}}{\bm{\Phi}}{\mathbf{x}}_{0}}\right\rVert_{2}^{2}+{o_{{\mathbb{P}}}}(1).$

######  Lemma 3.

Under Assumptions 1, 4, 2 and 3, the following concentrations are established:

$\left\lVert{\tfrac{1}{\sqrt{h\sigma^{2}}}{\bm{\Phi}}{\mathbf{x}}_{0}}\right\rVert_{2}=\left\lVert{\tfrac{1}{\sqrt{h\sigma^{2}}}{\bm{\Phi}}}\right\rVert_{\mathrm{F}}+{o_{{\mathbb{P}}}}(1),\qquad\left\lVert{\tfrac{1}{\sqrt{h^{2}\sigma^{2}}}{\mathbf{W}}{\bm{\Phi}}{\mathbf{x}}_{0}}\right\rVert_{2}=\left\lVert{\tfrac{1}{\sqrt{h^{2}\sigma^{2}}}{\mathbf{W}}{\bm{\Phi}}{\mathbf{x}}_{0}}\right\rVert_{\mathrm{F}}+{o_{{\mathbb{P}}}}(1).$

Lemmas 2 and 3 are based on the _Hanson–Wright inequality_ [38, Theorem
6.3.2], a concentration inequality for order-$2$ Gaussian chaos, with an
additional effort to control norms of random matrices ${\mathbf{W}}$ and
${\bm{\Phi}}$. By combining Lemmas 2 and 3, we can express normalizers
$\left\lVert{{\bm{\Phi}}{\mathbf{x}}^{\prime}}\right\rVert_{2}^{-1}$ and
$\left\lVert{{\mathbf{W}}{\bm{\Phi}}{\mathbf{x}}}\right\rVert_{2}^{-1}$ in
${\mathbf{H}}$ into simpler forms, and obtain a concise expression of
${\mathbf{H}}$ consequently.

######  Lemma 4.

Let ${\bm{\Psi}}\coloneqq{\mathbf{W}}{\bm{\Phi}}$. Assume that
$\left\lVert{{\bm{\Phi}}}\right\rVert_{\mathrm{F}}$ and
$\left\lVert{{\bm{\Psi}}}\right\rVert_{\mathrm{F}}$ are bounded away from
zero. Under Assumptions 1, 4, 2 and 3, ${\mathbf{H}}$ can be expressed as
follows:

${\mathbf{H}}=\frac{1}{1+\sigma^{2}}\left\\{\tilde{\bm{\Phi}}\tilde{\bm{\Psi}}^{\top}-2\tilde{\bm{\Psi}}\tilde{\bm{\Phi}}^{\top}\tilde{\bm{\Psi}}\tilde{\bm{\Psi}}^{\top}-\operatorname{\mathrm{tr}}(\tilde{\bm{\Phi}}^{\top}\tilde{\bm{\Psi}})\tilde{\bm{\Psi}}\tilde{\bm{\Psi}}^{\top}\right\\}+{o_{{\mathbb{P}}}}(1),$

where
$\tilde{\bm{\Phi}}\coloneqq{\bm{\Phi}}/\left\lVert{{\bm{\Phi}}}\right\rVert_{\mathrm{F}}$
and
$\tilde{\bm{\Psi}}\coloneqq{\bm{\Psi}}/\left\lVert{{\bm{\Psi}}}\right\rVert_{\mathrm{F}}$.

Subsequently, we analyze the dynamics (4) in detail by leveraging the
expression ${\mathbf{H}}$ in Lemma 4.

##  5 Analysis of non-contrastive dynamics

In the dynamics (4), the main obstacle is the normalizers
$\left\lVert{{\bm{\Phi}}}\right\rVert_{\mathrm{F}}^{-1}$ and
$\left\lVert{{\bm{\Psi}}}\right\rVert_{\mathrm{F}}^{-1}$ in ${\mathbf{H}}$,
which makes the dynamics highly nonlinear and challenging to solve directly.
Instead, we consider the equilibrium state
$\left\lVert{{\bm{\Phi}}}\right\rVert_{\mathrm{F}}\to N_{\Phi}$ and
$\left\lVert{{\bm{\Psi}}}\right\rVert_{\mathrm{F}}\to N_{\Psi}$ with
$N_{\Phi},N_{\Psi}\gg 0$. This regime allows us to focus on the parameter
values ${\mathbf{W}}$ and ${\bm{\Phi}}$ at equilibrium. We impose the next
assumption.

######  Assumption 5 (Norms remain stable).

$\left\lVert{{\bm{\Phi}}}\right\rVert_{\mathrm{F}}\equiv N_{\Phi}$,
$\left\lVert{{\bm{\Psi}}}\right\rVert_{\mathrm{F}}\equiv N_{\Psi}$, and
$\operatorname{\mathrm{tr}}(\tilde{\bm{\Phi}}^{\top}\tilde{\bm{\Psi}})\equiv
N_{\times}$ for $\forall t\geq 0$.

In Section 5.4, we will see that these quantities may not be ill-behaved
during time evolution. Indeed, learning dynamics analysis of weight
normalization often assumes a similar one [40]. We conjecture that this
assumption can be replaced with the local stability as in the previous
convergence analysis of weight-norm dynamics [47]; nevertheless, we choose to
assume the global stability to concentrate on the equilibrium analysis. Under
Assumption 5, ${\mathbf{H}}$ can be expressed as follows:

${\mathbf{H}}=\hat{\mathbf{H}}=\frac{1}{1+\sigma^{2}}\left(\frac{{\mathbf{F}}{\mathbf{W}}}{N_{\Phi}N_{\Psi}}-\frac{2{\mathbf{W}}{\mathbf{F}}{\mathbf{W}}{\mathbf{F}}{\mathbf{W}}}{N_{\Phi}N_{\Psi}^{3}}-\frac{N_{\times}{\mathbf{W}}{\mathbf{F}}{\mathbf{W}}}{N_{\Phi}N_{\Psi}}\right),$
(5)

where ${\mathbf{F}}\coloneqq{\bm{\Phi}}{\bm{\Phi}}^{\top}$ and we drop the
negligible term ${o_{{\mathbb{P}}}}(1)$ for simplicity.

###  5.1 Eigenmode decomposition of dynamics

To analyze the stability of the dynamics (4), we disentangle it into the
eigenmodes. We first show the condition where the eigenspaces of
${\mathbf{W}}$ and ${\mathbf{F}}$ align with each other. Note that two
commuting matrices can be simultaneously diagonalized.

######  Proposition 1.

Suppose ${\mathbf{W}}$ is non-singular. Under the dynamics (4) with
${\mathbf{H}}=\hat{\mathbf{H}}$, the commutator
${\mathbf{L}}(t)\coloneqq[{\mathbf{F}},{\mathbf{W}}]\coloneqq{\mathbf{F}}{\mathbf{W}}-{\mathbf{W}}{\mathbf{F}}$
satisfies
$\frac{\mathrm{d}{{\mathrm{vec}({{\mathbf{L}}(t)})}}}{\mathrm{d}{t}}=-{\mathbf{K}}(t){\mathrm{vec}({{\mathbf{L}}(t)})}$,
where

${\mathbf{K}}(t)\coloneqq
2\frac{{\mathbf{W}}\oplus{\mathbf{W}}{\mathbf{F}}{\mathbf{W}}+{\mathbf{W}}^{2}({\mathbf{F}}{\mathbf{W}}\oplus{\mathbf{I}}_{d})}{(1+\sigma^{2})N_{\Phi}N_{\Psi}^{3}}+\frac{({\mathbf{W}}^{-1})\oplus{\mathbf{F}}-({\mathbf{W}}-N_{\times}{\mathbf{W}}^{2})\oplus{\mathbf{I}}_{d}}{(1+\sigma^{2})N_{\Phi}N_{\Psi}}+3\rho{\mathbf{I}}_{d},$

and
${\mathbf{A}}\oplus{\mathbf{B}}\coloneqq{\mathbf{A}}\otimes{\mathbf{B}}+{\mathbf{B}}\otimes{\mathbf{A}}$
denotes the sum of the two Kronecker products.

If $\inf_{t\geq 0}{\lambda_{\min}({{\mathbf{K}}(t)})}\geq\lambda_{0}>0$ for
some $\lambda_{0}>0$, then
$\left\lVert{{\mathbf{L}}(t)}\right\rVert_{\mathrm{F}}\to 0$ as $t\to\infty$.

Proposition 1 is a variant of [35, Theorem 3] for the dynamics (4).
Consequently, we see that ${\mathbf{W}}$ and ${\mathbf{F}}$ are simultaneously
diagonalizable at the equilibrium
$\left\lVert{{\mathbf{L}}(t)}\right\rVert_{\mathrm{F}}=\left\lVert{[{\mathbf{F}},{\mathbf{W}}]}\right\rVert_{\mathrm{F}}=0$.
We then approximately deal with the dynamics (4).

######  Assumption 6 (Always commutative).

$\left\lVert{[{\mathbf{F}},{\mathbf{W}}]}\right\rVert_{\mathrm{F}}\equiv 0$
for $\forall t\geq 0$.

We verify the validity of the assumption in Section 5.4, where we see that the
commutator remains to be nearly zero.

Let ${\mathbf{U}}$ be the common eigenvectors of ${\mathbf{F}}$ and
${\mathbf{W}}$, then
${\mathbf{W}}={\mathbf{U}}{\bm{\Lambda}}_{W}{\mathbf{U}}^{\top}$ and
${\mathbf{F}}={\mathbf{U}}{\bm{\Lambda}}_{F}{\mathbf{U}}^{\top}$, where
${\bm{\Lambda}}_{W}=\operatorname{\mathrm{diag}}[p_{1},p_{2},\dots,p_{d}]$ and
${\bm{\Lambda}}_{F}=\operatorname{\mathrm{diag}}[s_{1},s_{2},\dots,s_{d}]$. By
extending the discussion of [35, Appendix B.1], we can show that
${\mathbf{U}}$ would not change over time.

######  Proposition 2.

Suppose ${\mathbf{W}}$ is non-singular. Under the dynamics of Eq. 4 with
${\mathbf{H}}=\hat{\mathbf{H}}$, we have $\dot{\mathbf{U}}={\mathbf{O}}$.

With Assumptions 5 and 6 and Proposition 2, we decompose (4) with
${\mathbf{H}}=\hat{\mathbf{H}}$ into the eigenmodes.

$\displaystyle\dot{p}_{j}$
$\displaystyle=-\frac{1}{(1+\sigma^{2})N_{\Phi}N_{\Psi}}\left(\frac{2}{N_{\Psi}^{2}}s_{j}^{2}p_{j}^{2}+N_{\times}s_{j}p_{j}-s_{j}\right)-\rho
p_{j},$ (6) $\displaystyle\dot{s}_{j}$
$\displaystyle=-\frac{2}{(1+\sigma^{2})N_{\Phi}N_{\Psi}}\left(\frac{2}{N_{\Psi}^{2}}s_{j}^{2}p_{j}^{3}+N_{\times}s_{j}p_{j}^{2}-s_{j}p_{j}\right)-2\rho
s_{j}.$

The eigenmode dynamics (6) is far more interpretable than the matrix dynamics
(4) and amenable to further understanding. Subsequently, we analyze the
eigenmode dynamics to investigate the number of equilibrium points and their
stability.

###  5.2 Equilibrium analysis of eigenmode dynamics

We are interested in when the eigenmode dynamics does and does not collapse
depending on augmentation strength $\sigma^{2}$ and regularization $\rho$. For
this purpose, we investigate the equilibrium points of the eigenmode dynamics
(6).

#### Invariant parabola.

By simple algebra, $\dot{s_{j}}-2p_{j}\dot{p_{j}}=-2\rho(s_{j}-p_{j}^{2})$.
Noting that
$\frac{\mathrm{d}{}}{\mathrm{d}{t}}(s_{j}-p_{j}^{2})=\dot{s_{j}}-2p_{j}\dot{p_{j}}$
and integrating both ends, we encounter the following relation:

$s_{j}(t)=p_{j}^{2}(t)+c_{j}\exp(-2\rho t),$ (7)

where $c_{j}\coloneqq s_{j}(0)-p_{j}^{2}(0)$ is the initial condition.
Equation 7 elucidates that the dynamics of $(p_{j}(t),s_{j}(t))$
asymptotically converges to the parabola $s_{j}(t)=p_{j}^{2}(t)$ as
$t\to\infty$ when regularization $\rho>0$ exists. The information of
initialization $c_{j}$ shall be forgotten. Stronger regularization yields
faster convergence to the parabola.

#### Dynamics on invariant parabola.

We now focus on the dynamics on the invariant parabola. Substituting
$s_{j}(t)=p_{j}^{2}(t)$ into $p_{j}$-dynamics in Eq. 6 yields the following
dynamics:

$\dot{p_{j}}=-\frac{2}{(1+\sigma^{2})N_{\Phi}N_{\Psi}^{3}}p_{j}^{6}-\frac{N_{\times}}{(1+\sigma^{2})N_{\Phi}N_{\Psi}}p_{j}^{3}+\frac{1}{(1+\sigma^{2})N_{\Phi}N_{\Psi}}p_{j}^{2}-\rho
p_{j}.$ (8)

Figure 2:  Numerical illustrations of the dynamics Eq. 8 with different values
of $(\rho,N_{\Phi},N_{\Psi})$, where vertical and horizontal axes denote
$p_{j}$ and $\dot{p_{j}}$, respectively. The left two columns are illustrated
for $\rho=0.5$, while right two columns for $\rho=0.1$. Red
$\blacktriangledown$ and green $\blacktriangle$ indicate stable (namely,
$\dot{p_{j}}<0$) and unstable equilibrium (namely, $\dot{p_{j}}>0$) points,
respectively [19]. For other parameters, we chose $N_{\times}=1$ and
$\sigma^{2}=0.1$ for illustration.

We illustrate the dynamics (8) with different parameter values in Fig. 2. This
dynamics always has $p_{j}=0$ as an equilibrium point, and the number of
equilibrium points varies between two and four. Notably, Eq. 8 is a _sixth-
order_ non-linear ODE, whereas the L2 loss dynamics [35, Eq. (16)] induces a
_third-order_ non-linear eigenmode dynamics, as we will recap in Section 5.3.
From Fig. 2, we can classify the dynamics into three regimes (refer to Fig. 3
together):

  * •

(Collapse) When all of $\rho$, $N_{\Phi}$, $N_{\Psi}$ are large, the dynamics
only has two equilibrium points. See the plots with
$(\rho,N_{\Phi},N_{\Psi})\in\left\\{{(0.5,1.0,1.0),(0.5,1.0,0.5),(0.5,0.5,1.0)}\right\\}$.
In this regime, $p_{j}=0$ is the only stable equilibrium, causing the
collapsed dynamics. This regime is brittle because the stable equilibrium
$p_{j}=0$ blows up the normalizers
$\left\lVert{{\bm{\Phi}}}\right\rVert_{\mathrm{F}}^{-1}$ and
$\left\lVert{{\bm{\Psi}}}\right\rVert_{\mathrm{F}}^{-1}$ in the original
cosine loss dynamics. As $p_{j}$ shrinks, the values $N_{\Phi}$ and $N_{\Psi}$
shrink together, too, which brings the dynamics into the next two regimes.

  * •

(Acute) When $\rho$, $N_{\Phi}$, and $N_{\Psi}$ become smaller than those in
Collapse, two new equilibrium points emerge and the number of equilibrium
points is four in total. See the plots with
$(\rho,N_{\Phi},N_{\Psi})\in\left\\{{(0.5,0.5,0.5),(0.5,0.25,1.0),(0.1,1.0,1.0)}\right\\}$.
Let $p_{\blacktriangle}^{(-)}$, $p_{\blacktriangledown}^{(0)}(=0)$,
$p_{\blacktriangle}^{(+)}$, and $p_{\blacktriangledown}^{(+)}$ denote the
equilibrium points from smaller to larger ones, respectively, namely,
$p_{\blacktriangle}^{(-)}<p_{\blacktriangledown}^{(0)}=0<p_{\blacktriangle}^{(+)}<p_{\blacktriangledown}^{(+)}$
(see Fig. 3). Note that
$p_{j}=p_{\blacktriangle}^{(-)},p_{\blacktriangle}^{(+)}$ are unstable and
$p_{j}=p_{\blacktriangledown}^{(0)},p_{\blacktriangledown}^{(+)}$ are stable
[19]. In this regime, the eigenmode initialized larger than
$p_{\blacktriangle}^{(+)}$ converge to non-degenerate point
$p_{\blacktriangledown}^{(+)}$. However, the eigenmode degenerates to
$p_{\blacktriangledown}^{(0)}$ if initialization is in the range
$[p_{\blacktriangle}^{(-)},p_{\blacktriangle}^{(+)}]$ (close to zero), and
diverges if initialization has large negative value
$<p_{\blacktriangle}^{(-)}$. If the eigenmode degenerates, the values
$N_{\Phi}$ and $N_{\Psi}$ further shrink and then the regime enters the final
one; if the eigenmode diverges, $N_{\Phi}$ and $N_{\Psi}$ inflate and the
regime goes back to the previous Collapse.

  * •

(Stable) When $\rho$, $N_{\Phi}$, and $N_{\Psi}$ are further smaller than
those in Acute, the middle two equilibrium points
$p_{\blacktriangledown}^{(0)}$ and $p_{\blacktriangle}^{(+)}$ approaches and
form a saddle point. See the plots with
$(\rho,N_{\Phi},N_{\Psi})\in\left\\{{(0.5,0.25,0.5),(0.1,0.25,1.0),(0.1,0.25,0.5)}\right\\}$.
Denote this saddle point by $p_{\blacklozenge}$. The dynamics has a unstable
equilibrium $p_{\blacktriangle}^{(-)}$, a saddle point $p_{\blacklozenge}$,
and a stable equilibrium $p_{\blacktriangledown}^{(+)}$, from smaller to
larger ones. In this regime, the eigenmode stably converges to the non-
degenerate point $p_{j}=p_{\blacktriangledown}^{(+)}$ unless the
initialization is smaller than $p_{\blacktriangle}^{(-)}$.

(_Remark_ : The two equilibrium $p_{\blacktriangledown}^{(0)}$ and
$p_{\blacktriangle}^{(+)}$ would not coincide exactly at a single saddle point
because the dynamics diverges as $N_{\Phi},N_{\Psi}\to 0$. Nonetheless, the
approximation $p_{\blacktriangledown}^{(0)}\approx p_{\blacktriangle}^{(+)}$
is reasonable with realistic parameters such as
$(\rho,N_{\Phi},N_{\Psi})=(0.1,0.25,0.5)$.)

#### Three regimes prevent degeneration.

Figure 3:  Schema of Collapse, Acute, and Stable regimes of the eigenmode
dynamics Eq. 8. Red $\blacktriangledown$ and green $\blacktriangle$ indicate
stable (namely, $\dot{p_{j}}<0$) and unstable equilibrium (namely,
$\dot{p_{j}}>0$) points, respectively. The black $\blacklozenge$ denotes the
saddle point. Red, gray, and blue backgrounds indicate ranges where the
eigenmode will diverge to $-\infty$, collapse to $0$, and converge to the
stable equilibrium, respectively. As $N_{\Phi}$ and $N_{\Psi}$ become smaller,
the regime shifts in the direction <<Collapse $\to$ Acute $\to$ Stable>>, and
as $N_{\Phi}$ and $N_{\Psi}$ become larger, the regime shifts in the opposite
direction <<Stable $\to$ Acute $\to$ Collapse>>.

We illustrate the relationship among the three regimes in Fig. 3. As we see in
the numerical experiments (Section 5.4), the parameter initialization
(Assumption 4) hardly makes the initial eigenmode smaller than
$p_{\blacktriangle}^{(-)}$: indeed, we conducted a numerical simulation to see
the distribution of the initial eigenmode in Fig. 4, which indicates that the
initial eigenmodes are sufficiently larger than $p_{\blacktriangle}^{(-)}$.
Therefore, the learning dynamics has stable equilibriums and successfully
stabilizes.

Figure 4:  Numerical simulation of eigenvalue distributions of ${\mathbf{W}}$.
In each figure, we generate ${\mathbf{W}}$ and ${\bm{\Phi}}$ by the
initialization of Assumption 4, and illustrate the histogram of eigenmodes of
${\mathbf{W}}$. The vertical line indicates the value of
$p_{\blacktriangle}^{(-)}$, the negative unstable equilibrium point of
$p_{j}$-dynamics (8), computed by the binary search and numerical root
finding. For parameters, we chose $\rho=0.05$, $\sigma^{2}=1.0$, $d=2048$, and
$h\in\left\\{{64,256}\right\\}$.

Importantly, this cosine loss dynamics stabilizes and would not collapse to
zero regardless of the regularization strength $\rho$, which is in stark
contrast to the L2 loss dynamics, as detailed in Section 5.3. This observation
tells us the importance of feature normalization to prevent representation
collapse in non-contrastive self-supervised learning.

###  5.3 Comparison with L2 loss dynamics

Figure 5:  Schema of three eigenmode dynamics in the L2 loss case. Each figure
illustrates the eigenmode corresponding fixed regularization strength $\rho$.
The meaning of each mark ($\blacktriangle,\blacktriangledown,\blacklozenge$)
and background colors can be found in the caption of Fig. 3. The figure
borrows the illustration of [35, Figure 4].

Whereas we mainly focused on the study of the cosine loss dynamics, [35] (and
many earlier studies) engaged in the L2 loss dynamics, which does not entail
feature normalization. Here, we compare the cosine and L2 loss dynamics to see
how feature normalization plays a crucial role.

Let us review the dynamics of [35]. We inherit Assumption 1 (symmetric
projector), Assumption 2 (standard normal input), and Assumption 6
(${\mathbf{F}}$ and ${\mathbf{W}}$ are commutative). Under this setup, [35]
analyzed the non-contrastive dynamics (4) with the L2 loss (1), and revealed
that the eigenmodes of ${\mathbf{W}}$ and ${\mathbf{F}}$ (denoted by $p_{j}$
and $s_{j}$, respectively) asymptotically converges to the invariant parabola
$s_{j}(t)=p_{j}^{2}(t)$ (see Eq. 7), where the $p_{j}$-dynamics reads:

$\dot{p_{j}}=p_{j}^{2}\\{1-(1+\sigma^{2})p_{j}\\}-\rho p_{j}.$ (9)

Compare the L2-loss eigenmode dynamics (9) (third-order) and the cosine-loss
eigenmode dynamics (8) (sixth-order). Note that we omit the exponential moving
average of the online representation in the original BYOL ($\tau=1$) and set
the unite learning rate ratio between the predictor and online nets
($\alpha=1$) in [35] for comparison.

The behaviors of the two dynamics are compared in Fig. 3 (cosine loss) and
Fig. 5 (L2 loss). One of the most important differences is that the cosine
loss dynamics has the regime shift depending on evolution of $N_{\Phi}$,
$N_{\Psi}$, and $N_{\times}$, while the L2 loss dynamics does not have such a
shift. Thus, the L2 loss dynamics and its time evolution are solely determined
by a given regularization strength $\rho$ (see three plots in Fig. 5). That
being said, if the L2 loss dynamics is regularized strongly such that
$\rho>\frac{1}{4(1+\sigma^{2})}$, there is no hope that the eigenmode stably
converges without collapse to zero. On the contrary, a strong regularization
with the cosine loss initially makes the dynamics fall into the Collapse
regime, where no meaningful stable equilibrium exists, but the regime
gradually shifts to Acute as the eigenmode (and the norms $N_{\Phi}$ and
$N_{\Psi}$ accordingly) approaches zero. Such regime shift owes to feature
normalization involved in the cosine loss.

###  5.4 Numerical experiments

Figure 6:  Numerical simulation of the SimSiam model. (Left) Time evolution of
$N_{\Phi}$, $N_{\Psi}$, and $N_{\times}$. They overall remain stable (cf.
Assumption 5). (Center) Asymmetry of the projection head ${\mathbf{W}}$
(measured by the relative error of ${\mathbf{W}}-{\mathbf{W}}^{\top}$) and
non-commutativity of ${\mathbf{F}}$ and ${\mathbf{W}}$ (measured by the
relative error of the commutator $[{\mathbf{F}},{\mathbf{W}}]$). The relative
errors stay close to zero during time evolution (cf. Assumptions 1 and 6).
(Right) The leading eigenmode of the projection head $p_{j}$ (green line),
with background colors illustrating three intervals where $p_{j}$ diverges,
$p_{j}$ collapses, and $p_{j}$ stably converges at each epoch. Each color
corresponds to those in Fig. 3. The vertical black line indicates the shift
from Collapse (epoch < 1700) to Acute (epoch > 1700).

We conducted a simple numerical simulation of the SimSiam model using the
official implementation available at
https://github.com/facebookresearch/simsiam. We tested the linear model setup
shown in Section 3, with linear representation net ${\bm{\Phi}}$ and linear
projection head ${\mathbf{W}}$, and the representation dimension was set to
$h=64$. Data are generated from the $512$-dimensional ($d=512$) standard
multivariate normal (Assumption 2) and data augmentation follows isotropic
Gaussian noise ${\mathcal{D}}_{{\mathbf{x}}_{0}}^{\mathrm{aug}}$, with
variance $\sigma^{2}=1.0$. The learning rate of the momentum SGD was initially
set to $0.05$ and scheduled by the cosine annealing. The regularization
strength was set to $\rho=0.005$. For the other implementation details, we
followed the official implementation.

The results are shown in Fig. 6. We first confirm how Assumption 5 is
reasonable in practice by testing the values of $N_{\Phi}$, $N_{\Psi}$, and
$N_{\times}$ during time evolution. Figure 6 (Left) shows that these three
values, and $N_{\times}$ in particular, overall remain stable, with mild
shrinkage of $N_{\Phi}$ and $N_{\Psi}$. Nevertheless, $N_{\Phi}$ and
$N_{\Psi}$ occasionally have spikes. To take those behaviors into account, the
local norm stability [47] would be useful in future analyses. Next, to confirm
the validity of Assumptions 1 and 6, we plot asymmetry of the projection head
${\mathbf{W}}$ and commutativity of ${\mathbf{F}}$ and ${\mathbf{W}}$ in Fig.
6 (Center), which suggests that the assumptions are reasonable in general.
Lastly, we empirically observe the regime shift in Fig. 6 (Right). The
regularization strength $\rho=0.005$ used in this experiment is rather larger
than the default SimSiam regularization strength $\rho=10^{-4}$, which leads
to the Collapse regime initially (when $\mathrm{epoch}<1700$) but gradually
shifts to the Acute regime (when $\mathrm{epoch}>1700$). Thus, we observed how
the eigenmode escapes from the Collapse regime.

##  6 Conclusion

In this work, we questioned how to describe non-contrastive dynamics without
eigenmode collapse. The existing theory (represented by [35]) leverages the
simplicity of the L2 loss to analytically derive the dynamics of the two-layer
non-contrastive learning. However, the regularization severely affects
eigenmode collapse: with too strong regularization, the dynamics has no way to
escape from eigenmode collapse. This may indicate a drawback of the L2 loss
analysis, though their theoretical model is transparent. Alternatively, we
focused on the cosine loss, which involves feature normalization and derived
the corresponding eigenmode dynamics. Despite that the dynamics may fall into
the Collapse regime for too strong regularization, the shrinkage of the
eigenmodes brings the regime into non-collapse ones. Thus, we witnessed the
importance of feature normalization.

Technically, we leveraged the thermodynamical limit of the feature dimensions,
which allows us to focus on high-dimensional concentrated feature norms. We
believe that a similar device may enhance theoretical models of related
learning problems and architectures, including self-supervised learning based
on covariance regularization such as Barlow Twins [48] and VICReg [5].

This work is limited to the analysis of dynamics stability and refrains to
answer why non-contrastive learning is appealing for many downstream tasks.
While downstream performances of contrastive learning have been theoretically
analyzed through the lens of the learning theoretic viewpoint [33, 27, 46, 3]
and the smoothness of loss landscapes [26], we have far less understanding of
non-contrastive learning for the time being. We hope that understanding the
non-contrastive dynamics paves a road to the analysis of downstream tasks.

## Acknowledgments

HB appreciates Yoshihiro Nagano for providing numerous insights at the initial
phase of this research. A part of the experiments of this research was
conducted using Wisteria/Aquarius in the Information Technology Center, The
University of Tokyo.

## References

  * ADK [22] Pranjal Awasthi, Nishanth Dikkala, and Pritish Kamath.  Do more negative samples necessarily hurt in contrastive learning?  In Proceedings of the 39th International Conference on Machine Learning, pages 1101–1116. PMLR, 2022.
  * Bel [43] Richard Bellman.  The stability of solutions of linear differential equations.  Duke Mathematical Journal, 10(1):643–647, 1943.
  * BNN [22] Han Bao, Yoshihiro Nagano, and Kento Nozawa.  On the surrogate gap between contrastive and supervised losses.  In Proceedings of the 39th International Conference on Machine Learning, pages 1585–1606. PMLR, 2022.
  * BNS [18] Han Bao, Gang Niu, and Masashi Sugiyama.  Classification from pairwise similarity and unlabeled data.  In Proceedings of the 35th International Conference on Machine Learning, pages 452–461. PMLR, 2018.
  * BPL [22] Adrien Bardes, Jean Ponce, and Yann LeCun.  VICReg: Variance-invariance-covariance regularization for self-supervised learning.  In Proceedings of the 11th International Conference on Learning Representations, 2022.
  * BSX+ [22] Han Bao, Takuya Shimada, Liyuan Xu, Issei Sato, and Masashi Sugiyama.  Pairwise supervision can provably elicit a decision boundary.  In Proceedings of the 22nd International Conference on Artificial Intelligence and Statistics, pages 2618–2640. PMLR, 2022.
  * CH [21] Xinlei Chen and Kaiming He.  Exploring simple Siamese representation learning.  In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 15750–15758, 2021.
  * CHL [05] Sumit Chopra, Raia Hadsell, and Yann LeCun.  Learning a similarity metric discriminatively, with application to face verification.  In CVPR, pages 539–546, 2005.
  * CKNH [20] Ting Chen, Simon Kornblith, Mohammad Norouzi, and Geoffrey Hinton.  A simple framework for contrastive learning of visual representations.  In Proceedings of the 37th International Conference on Machine Learning, pages 1597–1607. PMLR, 2020.
  * CMM+ [20] Mathilde Caron, Ishan Misra, Julien Mairal, Priya Goyal, Piotr Bojanowski, and Armand Joulin.  Unsupervised learning of visual features by contrasting cluster assignments.  Advances in Neural Information Processing Systems 33, pages 9912–9924, 2020.
  * CTM+ [21] Mathilde Caron, Hugo Touvron, Ishan Misra, Hervé Jégou, Julien Mairal, Piotr Bojanowski, and Armand Joulin.  Emerging properties in self-supervised vision transformers.  In Proceedings of the IEEE/CVF International Conference on Computer Vision, pages 9650–9660, 2021.
  * DGM [20] Yonatan Dukler, Quanquan Gu, and Guido Montúfar.  Optimization theory for relu neural networks trained with normalization layers.  In Proceedings of the 37th International conference on machine learning, pages 2751–2760. PMLR, 2020.
  * ESSS [21] Aleksandr Ermolov, Aliaksandr Siarohin, Enver Sangineto, and Nicu Sebe.  Whitening for self-supervised representation learning.  In Proceedings of the 38th International Conference on Machine Learning, pages 3015–3024. PMLR, 2021.
  * GBLJ [19] Gauthier Gidel, Francis Bach, and Simon Lacoste-Julien.  Implicit regularization of discrete gradient dynamics in linear neural networks.  Advances in Neural Information Processing Systems 32, pages 3202–3211, 2019.
  * GSA+ [20] Jean-Bastien Grill, Florian Strub, Florent Altché, Corentin Tallec, Pierre Richemond, Elena Buchatskaya, Carl Doersch, Bernardo Avila Pires, Zhaohan Guo, Mohammad Gheshlaghi Azar, Bilal Piot, Koray Kavukcuoglu, Remi Munos, and Valko Michal.  Bootstrap your own latent - a new approach to self-supervised learning.  Advances in Neural Information Processing Systems 33, pages 21271–21284, 2020.
  * HAYWC [19] Botao Hao, Yasin Abbasi-Yadkori, Zheng Wen, and Guang Cheng.  Bootstrapping upper confidence bound.  Advances in Neural Information Processing Systems 32, pages 12123–12133, 2019.
  * HCX+ [22] Kaiming He, Xinlei Chen, Saining Xie, Yanghao Li, Piotr Dollár, and Ross Girshick.  Masked autoencoders are scalable vision learners.  In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 16000–16009, 2022.
  * HMW [22] Tobias Höppe, Agnieszka Miszkurka, and Dennis Bogatov Wilkman.  [re] understanding self-supervised learning dynamics without contrastive pairs.  In ML Reproducibility Challenge 2021 (Fall Edition), 2022.
  * HSD [12] Morris W Hirsch, Stephen Smale, and Robert L Devaney.  Differential Equations, Dynamical Systems, and An Introduction to Chaos.  Academic Press, 2012.
  * HZRS [15] Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun.  Delving deep into rectifiers: Surpassing human-level performance on imagenet classification.  In Proceedings of the IEEE International Conference on Computer Vision, pages 1026–1034, 2015.
  * HZRS [16] Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun.  Deep residual learning for image recognition.  In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 770–778, 2016.
  * JGH [18] Arthur Jacot, Franck Gabriel, and Clément Hongler.  Neural tangent kernel: Convergence and generalization in neural networks.  Advances in Neural Information Processing Systems 31, 31, 2018.
  * Kri [09] Alex Krizhevsky.  Learning multiple layers of features from tiny images.  Technical report, 2009.
  * LCLS [22] Zengyi Li, Yubei Chen, Yann LeCun, and Friedrich T Sommer.  Neural manifold clustering and embedding.  arXiv preprint arXiv:2201.10000, 2022.
  * LLUT [23] Ziyin Liu, Ekdeep Singh Lubana, Masahito Ueda, and Hidenori Tanaka.  What shapes the loss landscape of self supervised learning?  In Proceedings of the 11th International Conference on Learning Representations, 2023.
  * LXLM [23] Hong Liu, Sang Michael Xie, Zhiyuan Li, and Tengyu Ma.  Same pre-training loss, better downstream: Implicit bias matters for language models.  In Proceedings of the 40th International Conference on Machine Learning, pages 22188–22214. PMLR, 2023.
  * NS [21] Kento Nozawa and Issei Sato.  Understanding negative samples in instance discriminative self-supervised representation learning.  Advances in Neural Information Processing Systems 34, pages 5784–5797, 2021.
  * POvdO+ [19] Ben Poole, Sherjil Ozair, Aaron van den Oord, Alex Alemi, and George Tucker.  On variational bounds of mutual information.  In Proceedings of 36th International Coneference on Machine Learning, pages 5171–5180, 2019.
  * PP [12] Kaare Brandt Petersen and Michael Syskind Pedersen.  The matrix cookbook, 2012.
  * PTLR [22] Ashwini Pokle, Jinjin Tian, Yuchen Li, and Andrej Risteski.  Contrasting the landscape of contrastive and non-contrastive learning.  In Proceedings of the 25th International Conference on Artificial Intelligence and Statistics, pages 8592–8618. PMLR, 2022.
  * SE [20] Jiaming Song and Stefano Ermon.  Understanding the limitations of variational mutual information estimators.  In Proceedings of th 9th International Conference on Learning Representations, 2020.
  * SMG [14] Andrew M Saxe, James L McClelland, and Surya Ganguli.  Exact solutions to the nonlinear dynamics of learning in deep linear neural networks.  In Proceedings of the 2nd International Conference on Learning Representations, 2014.
  * SPA+ [19] Nikunj Saunshi, Orestis Plevrakis, Sanjeev Arora, Mikhail Khodak, and Hrishikesh Khandeparkar.  A theoretical analysis of contrastive unsupervised representation learning.  In Proceedings of the 36th International Conference on Machine Learning, pages 5628–5637. PMLR, 2019.
  * TBM+ [22] Nenad Tomasev, Ioana Bica, Brian McWilliams, Lars Buesing, Razvan Pascanu, Charles Blundell, and Jovana Mitrovic.  Pushing the limits of self-supervised ResNets: Can we outperform supervised learning without labels on ImageNet?  arXiv preprint arXiv:2201.05119, 2022.
  * TCG [21] Yuandong Tian, Xinlei Chen, and Surya Ganguli.  Understanding self-supervised learning dynamics without contrastive pairs.  In Proceedings of the 38th International Conference on Machine Learning, pages 10268–10278. PMLR, 2021.
  * TGR+ [23] Yunhao Tang, Zhaohan Daniel Guo, Pierre Harvey Richemond, Bernardo Avila Pires, Yash Chandak, Rémi Munos, Mark Rowland, Mohammad Gheshlaghi Azar, Charline Le Lan, Clare Lyle, et al.  Understanding self-predictive learning for reinforcement learning.  In Proceedings of the 40th International Conference on Machine Learning, pages 33632–33656. PMLR, 2023.
  * vdOLV [18] Aaron van den Oord, Yazhe Li, and Oriol Vinyals.  Representation learning with contrastive predictive coding.  arXiv preprint arXiv:1807.03748, 2018.
  * Ver [18] Roman Vershynin.  High-Dimensional Probability: An Introduction with Applications in Data Science, volume 47.  Cambridge University Press, 2018.
  * VGNA [20] Mariia Vladimirova, Stéphane Girard, Hien Nguyen, and Julyan Arbel.  Sub-weibull distributions: Generalizing sub-gaussian and sub-exponential properties to heavier tailed distributions.  Stat, 9(1):e318, 2020.
  * vL [17] Twan van Laarhoven.  L2 regularization versus batch and weight normalization.  arXiv preprint arXiv:1706.05350, 2017.
  * WCDT [21] Xiang Wang, Xinlei Chen, Simon S Du, and Yuandong Tian.  Towards demystifying representation learning with non-contrastive self-supervision.  arXiv:2110.04947, 2021.
  * WFT+ [22] Xiao Wang, Haoqi Fan, Yuandong Tian, Daisuke Kihara, and Xinlei Chen.  On the importance of asymmetry for siamese representation learning.  In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 16570–16579, 2022.
  * WI [20] Tongzhou Wang and Phillip Isola.  Understanding contrastive representation learning through alignment and uniformity on the hypersphere.  In Proceedings of the 37th International Conference on Machine Learning, pages 9929–9939. PMLR, 2020.
  * WL [21] Zixin Wen and Yuanzhi Li.  Toward understanding the feature learning process of self-supervised contrastive learning.  In Proceedings of the 39th International Conference on Machine Learning, pages 11112–11122. PMLR, 2021.
  * WL [22] Zixin Wen and Yuanzhi Li.  The mechanism of prediction head in non-contrastive self-supervised learning.  Advances in Neural Information Processing Systems 35, pages 24794–24809, 2022.
  * WZW+ [22] Yifei Wang, Qi Zhang, Yisen Wang, Jiansheng Yang, and Zhouchen Lin.  Chaos is a ladder: A new theoretical understanding of contrastive learning via augmentation overlap.  In Proceedings of 11th International Conference on Learning Representations, 2022.
  * WZZS [21] Ruosi Wan, Zhanxing Zhu, Xiangyu Zhang, and Jian Sun.  Spherical motion dynamics: Learning dynamics of normalized neural network using SGD and weight decay.  Advances in Neural Information Processing Systems 34, pages 6380–6391, 2021.
  * ZJM+ [21] Jure Zbontar, Li Jing, Ishan Misra, Yann LeCun, and Stéphane Deny.  Barlow Twins: Self-supervised learning via redundancy reduction.  In Proceedings of the 38th International Conference on Machine Learning, pages 12310–12320. PMLR, 2021.
  * ZWMW [23] Zhijian Zhuo, Yifei Wang, Jinwen Ma, and Yisen Wang.  Towards a unified theoretical understanding of non-contrastive learning via rank differential mechanism.  In Proceedings of the 11th International Conference on Learning Representations, 2023.

Appendix

Feature Normalization Prevents Collapse of Non-contrastive Self-supervised
Learning

##  Appendix A Technical lemmas

###  A.1 Sub-Weibull distributions

In this subsection, we give a brief introduction to _sub-Weibull
distributions_ [16, 39], which is a generalization of seminal sub-Gaussian and
sub-exponential random variables. First, we define sub-Weibull distributions.

######  Definition 1 ([16]).

For $\beta>0$, we define $X$ as a sub-Weibull random variable with the
$\psi_{\beta}$-norm if it entails a bounded $\psi_{\beta}$-norm, defined as
follows:

$\left\lVert{X}\right\rVert_{\psi_{\beta}}\coloneqq\inf\left\\{{C\in(0,\infty)}\mathrel{}\middle|\mathrel{}{\operatorname*{{\mathbb{E}}}[\exp(\left|{X}\right|^{\beta}/C^{\beta})]\leq
2}\right\\}.$

We occasionally call _$\beta$ -sub-Weibull_ to specify the corresponding
$\psi_{\beta}$-norm explicitly. Obviously, $\beta=2$ and $\beta=1$ recover
sub-Gaussian and sub-exponential distributions, respectively. Among equivalent
definitions of sub-Weibull distributions, we often use the following
conditions.

######  Proposition 3 ([39]).

Let $X$ be a sub-Weibull random variable. Then, the following conditions are
equivalent:

  1. 1.

The tails of $X$ satisfy

$\exists K_{1}>0\quad\text{such
that}\quad{\mathbb{P}}\left\\{{|X|\geq\varepsilon}\right\\}\leq
2\exp\left(-(\varepsilon/K_{1})^{\beta}\right)\quad\text{for all
}\varepsilon\geq 0.$

  2. 2.

The moments of $X$ satisfy

$\exists K_{2}>0\quad\text{such
that}\quad\left\lVert{X}\right\rVert_{L^{p}}\coloneqq\\{\operatorname*{{\mathbb{E}}}|X|^{p}\\}^{1/p}\leq
K_{2}p^{1/\beta}\quad\text{for all }p\geq 1.$

  3. 3.

The moment-generating function (MGF) of $|X|^{\beta}$ is bounded at some
point, namely,

$\exists K_{3}>0\quad\text{such
that}\quad\operatorname*{{\mathbb{E}}}\exp\left((|X|/K_{3})^{\beta}\right)\leq
2.$

The parameters $K_{1}$, $K_{2}$, and $K_{3}$ differ from each other by at most
an absolute constant factor.

We are interested in sub-Weibull distributions because they admit a nice
closure property, as shown below.

######  Proposition 4 ([39]).

Let $X$ and $Y$ be $\beta$-sub-Weibull random variables. Then, $XY$ is
$(\beta/2)$-sub-Weibull with
$\left\lVert{XY}\right\rVert_{\psi_{\beta/2}}\leq\left\lVert{X}\right\rVert_{\psi_{\beta}}\left\lVert{Y}\right\rVert_{\psi_{\beta}}$.
In addition, $X+Y$ is $\beta$-sub-Weibull with
$\left\lVert{X+Y}\right\rVert_{\psi_{\beta}}\leq\left\lVert{X}\right\rVert_{\psi_{\beta}}+\left\lVert{Y}\right\rVert_{\psi_{\beta}}$.

Note that Proposition 4 does not require the independence of two random
variables $X$ and $Y$. Lastly, we show a corresponding concentration
inequality for the sum of independent sub-Weibull random variables, which is a
generalization of Hoeffding’s and Bernstein’s inequalities for sub-Gaussian
and sub-exponential random variables, respectively.

######  Proposition 5 ([16]).

Let $X_{1},\dots,X_{N}$ be independent $\beta$-sub-Weibull random variables
with $\left\lVert{X_{i}}\right\rVert_{\psi_{\beta}}\leq K$ for each $i\in[N]$.
Then, there exists an absolute constant $C>0$ only depending on $\beta$ such
that for any $\delta\in(0,e^{-2})$,

$\left|{\sum_{i=1}^{N}X_{i}-\operatorname*{{\mathbb{E}}}\left[\sum_{i=1}^{N}X_{i}\right]}\right|\leq
CK\left(\sqrt{N\log\frac{1}{\delta}}+\left(\log\frac{1}{\delta}\right)^{1/\beta}\right),$

with probability at least $1-\delta$.

For the proofs of these propositions, please refer to the corresponding
references.

We additionally provide technical lemmas for random matrices whose element is
sub-Weibull.

######  Lemma 5.

Let ${\mathbf{G}}\in{\mathbb{R}}^{h\times d}$ be a random matrix with each
element being $\beta$-sub-Weibull such that
$\left\lVert{G_{ij}}\right\rVert_{\psi_{\beta}}={\mathcal{O}}(K(d,h))$ for
some $\beta>0$ and any $(i,j)\in[h]\times[d]$, where $K(d,h)$ may depend on
$d$ and $h$. Then,
$\frac{1}{d^{2}h^{2}}\left\lVert{{\mathbf{G}}^{\top}{\mathbf{G}}}\right\rVert_{\mathrm{F}}^{2}={{\mathcal{O}}_{{\mathbb{P}}}}(K(d,h)/h)$.

###### Proof of Lemma 5.

Let ${\mathbf{G}}_{i}\in{\mathbb{R}}^{h}$ denote the $i$-th column vector of
the matrix ${\mathbf{G}}$. We have the decomposition
$\left\lVert{{\mathbf{G}}^{\top}{\mathbf{G}}}\right\rVert_{\mathrm{F}}^{2}=\sum_{i,j=1}^{d}\left\langle{{\mathbf{G}}_{i}},{{\mathbf{G}}_{j}}\right\rangle^{2}$.
Let us focus on each
$\left\langle{{\mathbf{G}}_{i}},{{\mathbf{G}}_{j}}\right\rangle$ for fixed $i$
and $j$ first. We can decompose into
$\left\langle{{\mathbf{G}}_{i}},{{\mathbf{G}}_{j}}\right\rangle=\sum_{k=1}^{h}G_{ik}G_{jk}$,
which is the sum of $(\beta/2)$-sub-Weibull random variable $G_{ik}G_{jk}$
with
$\left\lVert{G_{ik}G_{jk}}\right\rVert_{\psi_{\beta/2}}={\mathcal{O}}(K(d,h))$
(cf. Proposition 4). By using the closure property under addition (Proposition
4), the sum $\left\langle{{\mathbf{G}}_{i}},{{\mathbf{G}}_{j}}\right\rangle$
is $(\beta/2)$-sub-Weibull again, with
$\left\lVert{\left\langle{{\mathbf{G}}_{i}},{{\mathbf{G}}_{j}}\right\rangle}\right\rVert_{\psi_{\beta/2}}={\mathcal{O}}(hK(d,h))$.

Now, we move back to evaluation of
$\left\lVert{{\mathbf{G}}^{\top}{\mathbf{G}}}\right\rVert_{\mathrm{F}}^{2}=\sum_{i,j=1}^{d}\left\langle{{\mathbf{G}}_{i}},{{\mathbf{G}}_{j}}\right\rangle^{2}$.
By using the closure property under multiplication (Proposition 4),
$\left\langle{{\mathbf{G}}_{i}},{{\mathbf{G}}_{j}}\right\rangle^{2}$ is
$(\beta/4)$-sub-Weibull with
$\left\lVert{\left\langle{{\mathbf{G}}_{i}},{{\mathbf{G}}_{j}}\right\rangle^{2}}\right\rVert_{\psi_{\beta/4}}={\mathcal{O}}(hK(d,h))$.
Then, the closure property under addition implies that
$\sum_{i,j=1}^{d}\left\langle{{\mathbf{G}}_{i}},{{\mathbf{G}}_{j}}\right\rangle^{2}$
is $(\beta/4)$-sub-Weibull, with
$\left\lVert{\sum_{i,j=1}^{d}\left\langle{{\mathbf{G}}_{i}},{{\mathbf{G}}_{j}}\right\rangle^{2}}\right\rVert_{\psi_{\beta/4}}={\mathcal{O}}(d^{2}hK(d,h))$.
Hence, by using the sub-Weibull tails in Proposition 3,

$\left\lVert{{\mathbf{G}}^{\top}{\mathbf{G}}}\right\rVert_{\mathrm{F}}^{2}=\sum_{i,j=1}^{d}\left\langle{{\mathbf{G}}_{i}},{{\mathbf{G}}_{j}}\right\rangle^{2}={{\mathcal{O}}_{{\mathbb{P}}}}(d^{2}hK(d,h)),$

from which we deduce that
$\frac{1}{d^{2}h^{2}}\left\lVert{{\mathbf{G}}^{\top}{\mathbf{G}}}\right\rVert_{\mathrm{F}}^{2}={{\mathcal{O}}_{{\mathbb{P}}}}(K(d,h)/h)$.
∎

######  Lemma 6.

Let ${\mathbf{G}}\in{\mathbb{R}}^{h\times d}$ be a random matrix with each
element being $\beta$-sub-Weibull such that
$\left\lVert{G_{ij}}\right\rVert_{\psi_{\beta}}={\mathcal{O}}(K(d,h))$ for
some $\beta>0$ and any $i,j\in[d]$, where $K(d,h)$ may depend on $d$ and $h$.
Then,
$\left\lVert{{\mathbf{G}}}\right\rVert={{\mathcal{O}}_{{\mathbb{P}}}}((d^{1/\beta}+h^{1/\beta})K(d,h))$.

###### Proof of Lemma 6.

The proof is akin to [38, Theorem 4.4.5], which is a spectral norm deviation
for sub-Gaussian random matrices. We leverage the _$\varepsilon$ -net
argument_: Using [38, Corollary 4.2.13], we can find $\varepsilon$-nets
${\mathcal{M}}_{d}$ of ${\mathbb{S}}^{d-1}$ with
$\left|{{\mathcal{M}}_{d}}\right|\leq 9^{d}$ and ${\mathcal{M}}_{h}$ of
${\mathbb{S}}^{h-1}$ with $\left|{{\mathcal{M}}_{h}}\right|\leq 9^{h}$, and
$\left\lVert{{\mathbf{G}}}\right\rVert\leq
2\max_{{\mathbf{x}}\in{\mathcal{M}}_{d},{\mathbf{y}}\in{\mathcal{M}}_{h}}\left\langle{{\mathbf{G}}{\mathbf{x}}},{{\mathbf{y}}}\right\rangle$.
Hence, it is sufficient to control the quadratic form
$\left\langle{{\mathbf{G}}{\mathbf{x}}},{{\mathbf{y}}}\right\rangle$ for fixed
$({\mathbf{x}},{\mathbf{y}})\in{\mathcal{M}}_{d}\times{\mathcal{M}}_{h}$.

The quadratic form
$\left\langle{{\mathbf{G}}{\mathbf{x}}},{{\mathbf{y}}}\right\rangle=\sum_{i=1}^{d}\sum_{j=1}^{h}G_{ij}x_{i}y_{j}$
is the sum of $\beta$-sub-Weibull random variables. By the closure property
(Proposition 4),

$\left\lVert{\left\langle{{\mathbf{G}}{\mathbf{x}}},{{\mathbf{y}}}\right\rangle}\right\rVert_{\psi_{\beta}}^{2}\leq\sum_{i,j}\left\lVert{G_{ij}x_{i}y_{j}}\right\rVert_{\psi_{\beta}}^{2}\leq{\mathcal{O}}(K(d,h))\cdot\left(\sum_{i=1}^{d}x_{i}^{2}\right)\left(\sum_{j=1}^{h}y_{j}^{2}\right)={\mathcal{O}}(K(d,h)).$

Thus, sub-Weibull tails (Proposition 3) imply
${\mathbb{P}}\left\\{{\left\langle{{\mathbf{G}}{\mathbf{x}}},{{\mathbf{y}}}\right\rangle\geq
u}\right\\}\leq 2\exp(-(u/K_{1})^{\beta})$ with $K_{1}={\mathcal{O}}(K(d,h))$.
The union bound yields

${\mathbb{P}}\left\\{{\max_{{\mathbf{x}}\in{\mathcal{M}}_{d},{\mathbf{y}}\in{\mathcal{M}}_{h}}\left\langle{{\mathbf{G}}{\mathbf{x}}},{{\mathbf{y}}}\right\rangle\geq
u}\right\\}\leq 9^{d+h}\cdot 2\exp(-(u/K_{1})^{\beta})\leq
2\exp(-\delta^{\beta}),$

where the last inequality is a consequence of the choice
$u=CK_{1}(d^{1/\beta}+h^{1/\beta}+\delta)$ with a sufficiently large absolute
constant $C$. Hence,
${\mathbb{P}}\left\\{{\left\lVert{{\mathbf{G}}}\right\rVert\geq
2u}\right\\}\leq 2\exp(-\delta^{\beta})$ holds, namely,
$\left\lVert{{\mathbf{G}}}\right\rVert=2C(d^{1/\beta}+h^{1/\beta}+\delta)\cdot{\mathcal{O}}(K(d,h))$
holds with probability at least $1-2\exp(-\delta^{\beta})$. This completes the
proof. ∎

###  A.2 Integral inequality

In this subsection, we briefly introduce the Grönwall–Bellman inequality [2,
14] to solve functional inequalities represented by integrals. In subsequent
analyses, we heavily use it to control the norm of certain random matrices
during time evolution.

######  Theorem 1 (Grönwall–Bellman inequality).

Let $\beta$ be a non-negative function and $\alpha$ a non-decreasing function.
Let $u$ be a function defined on an interval ${\mathcal{I}}=[0,\infty)$ such
that

$u(t)\leq\alpha(t)+\int_{0}^{t}\beta(s)u(s)\mathrm{d}{s},\quad\forall
t\in{\mathcal{I}}.$

Then, we have

$u(t)\leq\alpha(t)\exp\left(\int_{0}^{t}\beta(s)\mathrm{d}{s}\right),\quad\forall
t\in{\mathcal{I}}.$

###  A.3 Helper lemmas

######  Lemma 7.

Under the initialization of Assumption 4, we have the following results:

  1. 1.

$\frac{1}{h}\left\lVert{{\bm{\Phi}}^{\top}{\bm{\Phi}}(0)}\right\rVert={o_{{\mathbb{P}}}}(1)$.

  2. 2.

$\frac{1}{h^{2}}\left\lVert{{\bm{\Phi}}^{\top}{\mathbf{W}}^{\top}{\mathbf{W}}{\bm{\Phi}}(0)}\right\rVert={o_{{\mathbb{P}}}}(1)$.

###### Proof of Lemma 7.

To prove 1, we note that each element of the random matrix
$\sqrt{d}{\bm{\Phi}}(0)$ is sub-Gaussian (namely, $2$-sub-Weibull) with the
$\psi_{2}$-norm being ${\mathcal{O}}(1)$, by the assumption on the parameter
initialization (Assumption 4). Then, Lemma 6 implies
$d\left\lVert{{\bm{\Phi}}^{\top}{\bm{\Phi}}(0)}\right\rVert=\left\lVert{\sqrt{d}{\bm{\Phi}}(0)}\right\rVert^{2}={{\mathcal{O}}_{{\mathbb{P}}}}(d)$.
Finally, we have
$\frac{1}{h}\left\lVert{{\bm{\Phi}}^{\top}{\bm{\Phi}}(0)}\right\rVert={{\mathcal{O}}_{{\mathbb{P}}}}(1/h)={o_{{\mathbb{P}}}}(1)$.

The identity 2 follows similarly. The $(i,j)$-th element of the random matrix
$\sqrt{dh}{\mathbf{W}}{\bm{\Phi}}(0)$ can be expressed as
$\left\langle{{\mathbf{w}}_{i}},{{\bm{\Phi}}_{j}}\right\rangle$, where
${\mathbf{w}}_{i}$ is the $i$-th row vector of $\sqrt{h}{\mathbf{W}}(0)$ and
${\bm{\Phi}}_{j}$ is the $j$-th column vector of $\sqrt{d}{\bm{\Phi}}(0)$.
Both ${\mathbf{w}}_{i}$ and ${\bm{\Phi}}_{j}$ are $h$-dimensional vectors with
each element being standard normal. Hence,
$\left\langle{{\mathbf{w}}_{i}},{{\bm{\Phi}}_{j}}\right\rangle$ is the sum of
$h$ sub-exponential random variables, being sub-exponential with
$\left\lVert{\left\langle{{\mathbf{w}}_{i}},{{\bm{\Phi}}_{j}}\right\rangle}\right\rVert_{\psi_{1}}={\mathcal{O}}(h)$
(by using Proposition 4). This indicates that each element of
$\sqrt{dh}{\mathbf{W}}{\bm{\Phi}}(0)$ is sub-exponential (namely, $1$-sub-
Weibull). Then, Lemma 6 implies
$dh\left\lVert{{\bm{\Phi}}^{\top}{\mathbf{W}}^{\top}{\mathbf{W}}{\bm{\Phi}}(0)}\right\rVert=\left\lVert{\sqrt{dh}{\mathbf{W}}{\bm{\Phi}}(0)}\right\rVert^{2}={{\mathcal{O}}_{{\mathbb{P}}}}(d^{2})$.
Finally, we have
$\frac{1}{h^{2}}\left\lVert{{\bm{\Phi}}^{\top}{\mathbf{W}}^{\top}{\mathbf{W}}{\bm{\Phi}}(0)}\right\rVert={{\mathcal{O}}_{{\mathbb{P}}}}(1/h^{2})={o_{{\mathbb{P}}}}(1)$.
∎

######  Lemma 8.

Under the initialization of Assumption 4, we have the following results:

  1. 1.

$\frac{1}{h^{2}}\left\lVert{{\bm{\Phi}}^{\top}{\bm{\Phi}}(0)}\right\rVert_{\mathrm{F}}^{2}={o_{{\mathbb{P}}}}(1)$.

  2. 2.

$\frac{1}{h^{2}}\left\lVert{{\bm{\Phi}}^{\top}{\mathbf{W}}^{\top}{\mathbf{W}}{\bm{\Phi}}(0)}\right\rVert_{\mathrm{F}}^{2}={o_{{\mathbb{P}}}}(1)$.

  3. 3.

$\frac{1}{h^{2}}\operatorname{\mathrm{tr}}({\mathbf{W}}^{\top}{\mathbf{W}}(0))^{2}={{\mathcal{O}}_{{\mathbb{P}}}}(1)$.

###### Proof of Lemma 8.

Let us prove 1. Again, each element of the random matrix
$\sqrt{d}{\bm{\Phi}}(0)$ is $2$-sub-Weibull (see the proof of Lemma 7). Thus,
Lemma 5 implies
$\frac{1}{h^{2}}\left\lVert{{\bm{\Phi}}^{\top}{\bm{\Phi}}(0)}\right\rVert_{\mathrm{F}}^{2}=\frac{1}{d^{2}h^{2}}\cdot
d^{2}\left\lVert{{\bm{\Phi}}^{\top}{\bm{\Phi}}(0)}\right\rVert_{\mathrm{F}}^{2}={{\mathcal{O}}_{{\mathbb{P}}}}(1/h)={o_{{\mathbb{P}}}}(1)$.

The identity 2 follows similarly. Again, each element of the random matrix
$\sqrt{dh}{\mathbf{W}}{\bm{\Phi}}(0)$ is $1$-sub-Weibull (see the proof of
Lemma 7) so that $\sqrt{dh}{\mathbf{W}}{\bm{\Phi}}(0)$ satisfies the
assumption of Lemma 5, from which we deduce that

$\displaystyle\frac{1}{h^{2}}\left\lVert{{\bm{\Phi}}^{\top}{\mathbf{W}}^{\top}{\mathbf{W}}{\bm{\Phi}}(0)}\right\rVert_{\mathrm{F}}^{2}$
$\displaystyle=\frac{1}{h^{2}}\cdot\frac{1}{d^{2}h^{2}}\cdot
d^{2}h^{2}\left\lVert{{\bm{\Phi}}^{\top}{\mathbf{W}}^{\top}{\mathbf{W}}{\bm{\Phi}}(0)}\right\rVert_{\mathrm{F}}^{2}$
$\displaystyle=\frac{1}{h^{2}}{{\mathcal{O}}_{{\mathbb{P}}}}(1)$
$\displaystyle={o_{{\mathbb{P}}}}(1).$

To prove 3, we see that
$h\operatorname{\mathrm{tr}}({\mathbf{W}}^{\top}{\mathbf{W}}(0))=h\left\lVert{{\mathbf{W}}(0)}\right\rVert_{\mathrm{F}}^{2}=\sum_{i,j=1}^{h}(\sqrt{h}W(0)_{ij})^{2}$
is the sum of sub-exponential (namely, $1$-sub-Weibull) random variables
$(\sqrt{h}W(0)_{ij})^{2}$ with
$\left\lVert{\sqrt{h}W(0)_{ij}}\right\rVert_{\psi_{1}}={\mathcal{O}}(1)$ for
$i,j\in[h]$. Hence,
$h\operatorname{\mathrm{tr}}({\mathbf{W}}^{\top}{\mathbf{W}}(0))$ is $1$-sub-
Weibull with
$\left\lVert{h\operatorname{\mathrm{tr}}({\mathbf{W}}^{\top}{\mathbf{W}}(0))}\right\rVert_{\psi_{1}}={\mathcal{O}}(h^{2})$
from Proposition 4. By the closure property again,
$h^{2}\operatorname{\mathrm{tr}}({\mathbf{W}}^{\top}{\mathbf{W}}(0))^{2}$ is
$\frac{1}{2}$-sub-Weibull with the corresponding norm being
${\mathcal{O}}(h^{4})$. By using sub-Weibull tails in Proposition 3, we deduce
that
$\left|{h^{2}\operatorname{\mathrm{tr}}({\mathbf{W}}^{\top}{\mathbf{W}}(0))^{2}}\right|={{\mathcal{O}}_{{\mathbb{P}}}}(h^{2})$.
Lastly, we obtain
$\frac{1}{h^{2}}\operatorname{\mathrm{tr}}({\mathbf{W}}^{\top}{\mathbf{W}}(0))^{2}={{\mathcal{O}}_{{\mathbb{P}}}}(1)$.
∎

######  Lemma 9.

Under Assumptions 2 and 4, we have the following consequences:

  1. 1.

$\frac{1}{h^{2}}\left\lVert{{\bm{\Phi}}^{\top}{\bm{\Phi}}(0){\mathbf{x}}_{0}}\right\rVert_{2}^{2}={o_{{\mathbb{P}}}}(1)$.

  2. 2.

$\frac{1}{h^{4}}\left\lVert{{\bm{\Phi}}^{\top}{\mathbf{W}}^{\top}{\mathbf{W}}{\bm{\Phi}}(0){\mathbf{x}}_{0}}\right\rVert_{2}^{2}={o_{{\mathbb{P}}}}(1)$.

###### Proof of Lemma 9.

Assumption 2 implies that
${\mathbf{x}}_{0}\sim{\mathcal{N}}({\mathbf{0}},{\mathbf{I}}_{d})$, from which
we can verify that
$\left\lVert{{\mathbf{x}}_{0}}\right\rVert_{2}^{2}=\sum_{i=1}^{d}x_{0,i}^{2}$
is the sum of $d$ sub-exponential (i.e., $1$-sub-Weibull) random variables and
$\left\lVert{\left\lVert{{\mathbf{x}}_{0}}\right\rVert_{2}^{2}}\right\rVert_{\psi_{1}}={\mathcal{O}}(d)$
(Proposition 4). By sub-Weibull tails (Proposition 3),
$\left\lVert{{\mathbf{x}}_{0}}\right\rVert_{2}^{2}={{\mathcal{O}}_{{\mathbb{P}}}}(d)$
entails.

To prove 1, we confirm that each element of
$h{\bm{\Phi}}^{\top}{\bm{\Phi}}(0)$ is sub-exponential with the
$\psi_{1}$-norm being ${\mathcal{O}}(1)$. To see this, we let
${\bm{\Phi}}_{i}$ denote the $i$-th column vector of $\sqrt{h}{\bm{\Phi}}(0)$.
Assumption 4 indicates that ${\bm{\Phi}}_{i}$ is an $h$-dimensional standard
normal random vector, and
$\operatorname*{{\mathbb{E}}}\left\langle{{\bm{\Phi}}_{i}},{{\bm{\Phi}}_{j}}\right\rangle=h\cdot{\left\llbracket{i=j}\right\rrbracket}$.
Thus, Bernstein’s inequality [38, Corollary 2.8.3] yields
$\left|{\left\langle{{\bm{\Phi}}_{i}},{{\bm{\Phi}}_{j}}\right\rangle-h\cdot{\left\llbracket{i=j}\right\rrbracket}}\right|={{\mathcal{O}}_{{\mathbb{P}}}}(1)$
(for sufficiently large $h$), which indicates that
$h{\bm{\Phi}}^{\top}{\bm{\Phi}}(0)-h{\mathbf{I}}_{d}$ satisfies the assumption
of Lemma 6 with $\beta=1$ and $K(d,h)=1$. Hence, by Lemma 6,

$\left\lVert{h{\bm{\Phi}}^{\top}{\bm{\Phi}}(0)}\right\rVert\leq\left\lVert{h{\bm{\Phi}}^{\top}{\bm{\Phi}}(0)-h{\mathbf{I}}_{d}}\right\rVert+h\left\lVert{{\mathbf{I}}_{d}}\right\rVert={{\mathcal{O}}_{{\mathbb{P}}}}(d)+h.$

Combining this with
$\left\lVert{{\mathbf{x}}_{0}}\right\rVert_{2}^{2}={{\mathcal{O}}_{{\mathbb{P}}}}(d)$,
we obtain the following result:

$\frac{1}{h^{2}}\left\lVert{{\bm{\Phi}}^{\top}{\bm{\Phi}}(0){\mathbf{x}}_{0}}\right\rVert_{2}^{2}\leq\frac{1}{h^{4}}\cdot\left\lVert{h{\bm{\Phi}}^{\top}{\bm{\Phi}}(0)}\right\rVert^{2}\cdot\left\lVert{{\mathbf{x}}_{0}}\right\rVert_{2}^{2}=\frac{1}{h^{4}}\cdot\left\\{{{\mathcal{O}}_{{\mathbb{P}}}}(d)+h\right\\}^{2}\cdot{{\mathcal{O}}_{{\mathbb{P}}}}(d)={{\mathcal{O}}_{{\mathbb{P}}}}(h^{-1}),$

which completes the proof.

To prove 2, we confirm that each element of
$h^{2}{\bm{\Phi}}^{\top}{\mathbf{W}}^{\top}{\mathbf{W}}{\bm{\Phi}}(0)$ is
$\frac{1}{2}$-sub-Weibull with the $\psi_{\frac{1}{2}}$-norm being
${\mathcal{O}}(\sqrt{h})$. To see this, we let ${\bm{\Psi}}_{i}$ denote the
$i$-th column vector of $h{\mathbf{W}}(0){\bm{\Phi}}(0)$ (for $i\in[d]$). The
$k$-th element of ${\bm{\Psi}}_{i}$ (for $k\in[h]$) is
$\Psi_{i}^{(k)}\coloneqq h\sum_{l=1}^{h}W(0)_{kl}\Phi(0)_{li}$, which is sub-
exponential and mean zero from Assumption 4 and
$\left|{\Psi_{i}^{(k)}}\right|=\left|{h\sum_{l=1}^{h}W(0)_{kl}\Phi(0)_{li}}\right|={{\mathcal{O}}_{{\mathbb{P}}}}(1)$
(for sufficiently large $h$) from Bernstein’s inequality. Here, each
$(i,j)$-th element of
$h^{2}{\bm{\Phi}}^{\top}{\mathbf{W}}^{\top}{\mathbf{W}}{\bm{\Phi}}(0)$ is
$\left\langle{{\bm{\Psi}}_{i}},{{\bm{\Psi}}_{j}}\right\rangle=\sum_{k=1}^{h}\Psi_{i}^{(k)}\Psi_{j}^{(k)}$,
which is the sum of $h$ products $\Psi_{i}^{(k)}\Psi_{j}^{(k)}$. Each
$\Psi_{i}^{(k)}\Psi_{j}^{(k)}$ is $\frac{1}{2}$-sub-Weibull because of the
closure property (Proposition 4), and hence the sum
$\left\langle{{\bm{\Psi}}_{i}},{{\bm{\Psi}}_{j}}\right\rangle$ is
$\frac{1}{2}$-sub-Weibull with
$\left\lVert{\left\langle{{\bm{\Psi}}_{i}},{{\bm{\Psi}}_{j}}\right\rangle}\right\rVert_{\psi_{\frac{1}{2}}}={\mathcal{O}}(h)$.
Thus, we see the sub-Weibull property of
$h^{2}{\bm{\Phi}}^{\top}{\mathbf{W}}^{\top}{\mathbf{W}}{\bm{\Phi}}(0)$. Hence,
we can apply Lemma 6 to claim
$\left\lVert{h^{2}{\bm{\Phi}}^{\top}{\mathbf{W}}^{\top}{\mathbf{W}}{\bm{\Phi}}(0)}\right\rVert={{\mathcal{O}}_{{\mathbb{P}}}}(d^{2}h)$.
Combining this with
$\left\lVert{{\mathbf{x}}_{0}}\right\rVert_{2}^{2}={{\mathcal{O}}_{{\mathbb{P}}}}(d)$,
we obtain the desired result:

$\displaystyle\frac{1}{h^{4}}\left\lVert{{\bm{\Phi}}^{\top}{\mathbf{W}}^{\top}{\mathbf{W}}{\bm{\Phi}}(0){\mathbf{x}}_{0}}\right\rVert_{2}^{2}$
$\displaystyle\leq\frac{1}{h^{8}}\cdot\left\lVert{h^{2}{\bm{\Phi}}^{\top}{\mathbf{W}}^{\top}{\mathbf{W}}{\bm{\Phi}}(0)}\right\rVert^{2}\cdot\left\lVert{{\mathbf{x}}_{0}}\right\rVert_{2}^{2}$
$\displaystyle=\frac{1}{h^{8}}\cdot{{\mathcal{O}}_{{\mathbb{P}}}}(d^{4}h^{2})\cdot{{\mathcal{O}}_{{\mathbb{P}}}}(d)$
$\displaystyle={{\mathcal{O}}_{{\mathbb{P}}}}(h^{-1}).$

∎

######  Lemma 10.

For any $t$,
$\left\lVert{{\bm{\Phi}}^{\top}{\bm{\Phi}}(t)}\right\rVert_{\mathrm{F}}\leq(\left\lVert{{\bm{\Phi}}^{\top}{\bm{\Phi}}(0)}\right\rVert_{\mathrm{F}}+4t)\exp(2\rho
t)$.

###### Proof of Lemma 10.

First, we use the fundamental theorem of calculus and the triangular
inequality to decompose as follows:

$\displaystyle\left\lVert{{\bm{\Phi}}^{\top}{\bm{\Phi}}(t)}\right\rVert_{\mathrm{F}}$
$\displaystyle=\left\lVert{{\bm{\Phi}}^{\top}{\bm{\Phi}}(0)+\int_{0}^{t}\left\\{\dot{\bm{\Phi}}^{\top}{\bm{\Phi}}(\tau)+{\bm{\Phi}}^{\top}\dot{\bm{\Phi}}(\tau)\right\\}\mathrm{d}{\tau}}\right\rVert_{\mathrm{F}}$
(10)
$\displaystyle\leq\left\lVert{{\bm{\Phi}}^{\top}{\bm{\Phi}}(0)}\right\rVert_{\mathrm{F}}+\int_{0}^{t}\left\lVert{\dot{\bm{\Phi}}^{\top}{\bm{\Phi}}(\tau)}\right\rVert_{\mathrm{F}}\mathrm{d}{\tau}+\int_{0}^{t}\left\lVert{{\bm{\Phi}}^{\top}\dot{\bm{\Phi}}(\tau)}\right\rVert_{\mathrm{F}}\mathrm{d}{\tau}$
$\displaystyle=\left\lVert{{\bm{\Phi}}^{\top}{\bm{\Phi}}(0)}\right\rVert_{\mathrm{F}}+2\int_{0}^{t}\left\lVert{\dot{\bm{\Phi}}^{\top}{\bm{\Phi}}(\tau)}\right\rVert_{\mathrm{F}}\mathrm{d}{\tau}.$

The term $\dot{\bm{\Phi}}^{\top}{\bm{\Phi}}$ can be evaluated by using the
dynamics derived in Lemma 1 as follows:

$\displaystyle\dot{\bm{\Phi}}^{\top}{\bm{\Phi}}$
$\displaystyle=\left\\{{\mathbf{W}}^{\top}({\mathbf{W}}^{\top}\dot{\mathbf{W}}+\rho{\mathbf{W}}{\mathbf{W}}^{\top}){{({\mathbf{W}}^{\top})}^{\dagger}}{{({\bm{\Phi}}^{\top})}^{\dagger}}-\rho{\bm{\Phi}}{\bm{\Phi}}^{\top}{\mathbf{W}}^{\top}{{({\mathbf{W}}^{\top})}^{\dagger}}{{({\bm{\Phi}}^{\top})}^{\dagger}}\right\\}^{\top}{\bm{\Phi}}$
(11)
$\displaystyle=\left\\{{\mathbf{W}}^{\top}{\mathbf{W}}^{\top}\dot{\mathbf{W}}({{{\mathbf{W}}}^{\dagger}})^{\top}({{{\bm{\Phi}}}^{\dagger}})^{\top}+\rho{\mathbf{W}}^{\top}{\mathbf{W}}({{{\bm{\Phi}}}^{\dagger}})^{\top}-\rho{\bm{\Phi}}\right\\}^{\top}{\bm{\Phi}}$
$\displaystyle={{{\bm{\Phi}}}^{\dagger}}{{{\mathbf{W}}}^{\dagger}}\dot{\mathbf{W}}^{\top}{\mathbf{W}}^{2}{\bm{\Phi}}+\rho{{{\bm{\Phi}}}^{\dagger}}{\mathbf{W}}^{\top}{\mathbf{W}}{\bm{\Phi}}-\rho{\bm{\Phi}}^{\top}{\bm{\Phi}}$
$\displaystyle={{{\bm{\Phi}}}^{\dagger}}{{{\mathbf{W}}}^{\dagger}}\\{\operatorname*{{\mathbb{E}}}[{\mathbf{z}}^{\prime}{\bm{\omega}}^{\top}-({\bm{\omega}}^{\top}{\mathbf{z}}^{\prime}){\bm{\omega}}{\bm{\omega}}^{\top}]-\rho{\mathbf{W}}{\mathbf{W}}^{\top}\\}{\mathbf{W}}{\bm{\Phi}}+\rho{{{\bm{\Phi}}}^{\dagger}}{\mathbf{W}}^{\top}{\mathbf{W}}{\bm{\Phi}}-\rho{\bm{\Phi}}^{\top}{\bm{\Phi}}$
$\displaystyle={{{\bm{\Phi}}}^{\dagger}}{{{\mathbf{W}}}^{\dagger}}\operatorname*{{\mathbb{E}}}[{\mathbf{z}}^{\prime}{\bm{\omega}}^{\top}-({\bm{\omega}}^{\top}{\mathbf{z}}^{\prime}){\bm{\omega}}{\bm{\omega}}^{\top}]{\mathbf{W}}{\bm{\Phi}}-\rho{\bm{\Phi}}^{\top}{\bm{\Phi}},$

whose Frobenius norm shall be bounded from above subsequently:

$\left\lVert{\dot{\bm{\Phi}}^{\top}{\bm{\Phi}}}\right\rVert_{\mathrm{F}}\leq\operatorname*{{\mathbb{E}}}\left\lVert{{{{\bm{\Phi}}}^{\dagger}}{{{\mathbf{W}}}^{\dagger}}({\mathbf{z}}^{\prime}{\bm{\omega}}^{\top}){\mathbf{W}}{\bm{\Phi}}}\right\rVert_{\mathrm{F}}+\operatorname*{{\mathbb{E}}}\left\lVert{{{{\bm{\Phi}}}^{\dagger}}{{{\mathbf{W}}}^{\dagger}}({\bm{\omega}}{\bm{\omega}}^{\top}){\mathbf{W}}{\bm{\Phi}}}\right\rVert_{\mathrm{F}}+\rho\left\lVert{{\bm{\Phi}}^{\top}{\bm{\Phi}}}\right\rVert_{\mathrm{F}}.$

Note that we use $\left|{{\bm{\omega}}^{\top}{\mathbf{z}}^{\prime}}\right|\leq
1$ because ${\bm{\omega}},{\mathbf{z}}^{\prime}\in{\mathbb{S}}^{h-1}$ in this
bound. The norm
$\left\lVert{{{{\bm{\Phi}}}^{\dagger}}{{{\mathbf{W}}}^{\dagger}}({\mathbf{z}}^{\prime}{\bm{\omega}}^{\top}){\mathbf{W}}{\bm{\Phi}}}\right\rVert_{\mathrm{F}}$
is bounded as follows:

$\displaystyle\left\lVert{{{{\bm{\Phi}}}^{\dagger}}{{{\mathbf{W}}}^{\dagger}}({\mathbf{z}}^{\prime}{\bm{\omega}}^{\top}){\mathbf{W}}{\bm{\Phi}}}\right\rVert_{\mathrm{F}}^{2}$
$\displaystyle=\left\langle{{{{\bm{\Phi}}}^{\dagger}}{{{\mathbf{W}}}^{\dagger}}({\mathbf{z}}^{\prime}{\bm{\omega}}^{\top}){\mathbf{W}}{\bm{\Phi}}},{{{{\bm{\Phi}}}^{\dagger}}{{{\mathbf{W}}}^{\dagger}}({\mathbf{z}}^{\prime}{\bm{\omega}}^{\top}){\mathbf{W}}{\bm{\Phi}}}\right\rangle_{\mathrm{F}}$
(12)
$\displaystyle=\operatorname{\mathrm{tr}}({\bm{\Phi}}^{\top}{\mathbf{W}}^{\top}{\bm{\omega}}({\mathbf{z}}^{\prime})^{\top}({{{\mathbf{W}}}^{\dagger}})^{\top}({{{\bm{\Phi}}}^{\dagger}})^{\top}{{{\bm{\Phi}}}^{\dagger}}{{{\mathbf{W}}}^{\dagger}}{\mathbf{z}}^{\prime}{\bm{\omega}}^{\top}{\mathbf{W}}{\bm{\Phi}})$
$\displaystyle\overset{\text{(*)}}{=}\operatorname{\mathrm{tr}}({\bm{\omega}}({\mathbf{z}}^{\prime})^{\top}({{{\mathbf{W}}}^{\dagger}})^{\top}({{{\bm{\Phi}}}^{\dagger}})^{\top}{{{\bm{\Phi}}}^{\dagger}}{{{\mathbf{W}}}^{\dagger}}{\mathbf{z}}^{\prime}{\bm{\omega}}^{\top}{\mathbf{W}}{\bm{\Phi}}{\bm{\Phi}}^{\top}{\mathbf{W}}^{\top})$
$\displaystyle\leq\left|{\operatorname{\mathrm{tr}}({\bm{\omega}}({\mathbf{z}}^{\prime})^{\top})}\right|\cdot\left|{\operatorname{\mathrm{tr}}(({{{\mathbf{W}}}^{\dagger}})^{\top}({{{\bm{\Phi}}}^{\dagger}})^{\top}{{{\bm{\Phi}}}^{\dagger}}{{{\mathbf{W}}}^{\dagger}}{\mathbf{z}}^{\prime}{\bm{\omega}}^{\top}{\mathbf{W}}{\bm{\Phi}}{\bm{\Phi}}^{\top}{\mathbf{W}}^{\top})}\right|$
$\displaystyle\overset{\text{(*)}}{=}\left|{\operatorname{\mathrm{tr}}({\bm{\omega}}({\mathbf{z}}^{\prime})^{\top})}\right|\cdot\left|{\operatorname{\mathrm{tr}}({\mathbf{z}}^{\prime}{\bm{\omega}}^{\top})}\right|$
$\displaystyle=\left\lVert{{\bm{\omega}}}\right\rVert_{2}\left\lVert{{\mathbf{z}}^{\prime}}\right\rVert_{2}\left\lVert{{\mathbf{z}}^{\prime}}\right\rVert_{2}\left\lVert{{\bm{\omega}}}\right\rVert_{2}$
$\displaystyle\leq 1,$

where the cyclic property of the trace
$\operatorname{\mathrm{tr}}({\mathbf{A}}{\mathbf{B}}{\mathbf{C}})=\operatorname{\mathrm{tr}}({\mathbf{B}}{\mathbf{C}}{\mathbf{A}})$
is used at the two identities (*). Because Eq. 12 relies solely on
${\mathbf{z}}^{\prime},{\bm{\omega}}\in{\mathbb{S}}^{h-1}$, the same reasoning
induces the upper bound
$\left\lVert{{{{\bm{\Phi}}}^{\dagger}}{{{\mathbf{W}}}^{\dagger}}({\bm{\omega}}{\bm{\omega}}^{\top}){\mathbf{W}}{\bm{\Phi}}}\right\rVert_{\mathrm{F}}\leq
1$. By plugging everything back to Eq. 10, we obtain the following integral
inequality for the norm
$\left\lVert{{\bm{\Phi}}^{\top}{\bm{\Phi}}(t)}\right\rVert_{\mathrm{F}}$:

$\left\lVert{{\bm{\Phi}}^{\top}{\bm{\Phi}}(t)}\right\rVert_{\mathrm{F}}\leq\left\lVert{{\bm{\Phi}}^{\top}{\bm{\Phi}}(0)}\right\rVert_{\mathrm{F}}+4t+2\rho\int_{0}^{t}\left\lVert{{\bm{\Phi}}^{\top}{\bm{\Phi}}(\tau)}\right\rVert_{\mathrm{F}}\mathrm{d}{\tau}.$
(13)

The form of Eq. 13 satisfies the assumption of the Grönwall–Bellman inequality
(Theorem 1) with which the norm upper bound
$\left\lVert{{\bm{\Phi}}^{\top}{\bm{\Phi}}(t)}\right\rVert_{\mathrm{F}}\leq(\left\lVert{{\bm{\Phi}}^{\top}{\bm{\Phi}}(0)}\right\rVert_{\mathrm{F}}+4t)\exp(2\rho
t)$ is derived. ∎

######  Lemma 11.

For any $t$,
$\left\lVert{{\bm{\Phi}}(t)}\right\rVert\leq\sqrt{(\left\lVert{{\bm{\Phi}}^{\top}{\bm{\Phi}}(0)}\right\rVert+4t)\exp(2\rho
t)}$.

###### Proof of Lemma 11.

We evaluate
$\left\lVert{{\bm{\Phi}}^{\top}{\bm{\Phi}}(t)}\right\rVert=\left\lVert{{\bm{\Phi}}(t)}\right\rVert^{2}$.
By the fundamental theorem of calculus, we obtain the following decomposition:

$\left\lVert{{\bm{\Phi}}^{\top}{\bm{\Phi}}(t)}\right\rVert\leq\left\lVert{{\bm{\Phi}}^{\top}{\bm{\Phi}}(0)}\right\rVert+2\int_{0}^{t}\left\lVert{\dot{\bm{\Phi}}^{\top}{\bm{\Phi}}(\tau)}\right\rVert\mathrm{d}{\tau}.$

By following the same derivation as the proof of Lemma 10, it is not difficult
to see $\left\lVert{\dot{\bm{\Phi}}^{\top}{\bm{\Phi}}}\right\rVert\leq
2+\rho\left\lVert{{\bm{\Phi}}^{\top}{\bm{\Phi}}}\right\rVert$. Then,
$\left\lVert{{\bm{\Phi}}^{\top}{\bm{\Phi}}(t)}\right\rVert\leq\left\lVert{{\bm{\Phi}}^{\top}{\bm{\Phi}}(0)}\right\rVert+4t+2\rho\int_{0}^{t}\left\lVert{{\bm{\Phi}}^{\top}{\bm{\Phi}}(\tau)}\right\rVert\mathrm{d}{\tau}$.
This integral inequality can be solved via Theorem 1, and we have
$\left\lVert{{\bm{\Phi}}^{\top}{\bm{\Phi}}(t)}\right\rVert\leq(\left\lVert{{\bm{\Phi}}^{\top}{\bm{\Phi}}(0)}\right\rVert+4t)\exp(2\rho
t)$. ∎

######  Lemma 12.

For ${\mathbf{W}}\in{\mathbb{S}\mathrm{ym}}_{h}$, for any $t$,
$\operatorname{\mathrm{tr}}({\mathbf{W}}^{\top}{\mathbf{W}}(t))\leq(\operatorname{\mathrm{tr}}({\mathbf{W}}^{\top}{\mathbf{W}}(0))+4t)\exp(2\rho
t)$.

###### Proof of Lemma 12.

By the fundamental theorem of calculus, we obtain the following decomposition:

$\operatorname{\mathrm{tr}}({\mathbf{W}}^{\top}{\mathbf{W}}(t))\leq\operatorname{\mathrm{tr}}({\mathbf{W}}^{\top}{\mathbf{W}}(0))+2\int_{0}^{t}\operatorname{\mathrm{tr}}({\mathbf{W}}^{\top}\dot{\mathbf{W}}(\tau))\mathrm{d}{\tau}.$

By using the dynamics in Lemma 1, we further obtain the bound of
$\operatorname{\mathrm{tr}}({\mathbf{W}}^{\top}\dot{\mathbf{W}})$:

$\displaystyle\operatorname{\mathrm{tr}}({\mathbf{W}}^{\top}\dot{\mathbf{W}})$
$\displaystyle=\operatorname{\mathrm{tr}}\left(\operatorname*{{\mathbb{E}}}[{\mathbf{z}}^{\prime}{\bm{\omega}}^{\top}-({\bm{\omega}}^{\top}{\mathbf{z}}^{\prime}){\bm{\omega}}{\bm{\omega}}^{\top}]-\rho{\mathbf{W}}{\mathbf{W}}^{\top}\right)$
$\displaystyle\leq\operatorname*{{\mathbb{E}}}\operatorname{\mathrm{tr}}({\mathbf{z}}^{\prime}{\bm{\omega}}^{\top})+\operatorname*{{\mathbb{E}}}\operatorname{\mathrm{tr}}({\bm{\omega}}{\bm{\omega}}^{\top})+\rho\operatorname{\mathrm{tr}}({\mathbf{W}}{\mathbf{W}}^{\top})$
$\displaystyle\leq
2+\rho\operatorname{\mathrm{tr}}({\mathbf{W}}^{\top}{\mathbf{W}}),$

where the trace evaluation of rank-$1$ matrices and the symmetry of
${\mathbf{W}}$ are used. Hence, we obtain the following integral inequality:

$\operatorname{\mathrm{tr}}({\mathbf{W}}^{\top}{\mathbf{W}}(t))\leq\operatorname{\mathrm{tr}}({\mathbf{W}}^{\top}{\mathbf{W}}(0))+4t+2\rho\int_{0}^{t}\operatorname{\mathrm{tr}}({\mathbf{W}}^{\top}{\mathbf{W}}(\tau))\mathrm{d}{\tau},$

which is the same form as the integral inequality in Eq. 13, and can be solved
in the same way. ∎

######  Lemma 13.

For any $t$,
$\left\lVert{{\bm{\Phi}}^{\top}{\bm{\Phi}}(t){\mathbf{x}}_{0}}\right\rVert_{2}^{2}\leq(\left\lVert{{\bm{\Phi}}^{\top}{\bm{\Phi}}(0){\mathbf{x}}_{0}}\right\rVert_{2}^{2}+4\left\lVert{{\mathbf{x}}_{0}}\right\rVert_{2}^{2}t)\exp(2\rho
t)$.

###### Proof of Lemma 13.

First, we obtain

$\left\lVert{{\bm{\Phi}}^{\top}{\bm{\Phi}}(t){\mathbf{x}}_{0}}\right\rVert_{2}^{2}\leq\left\lVert{{\bm{\Phi}}^{\top}{\bm{\Phi}}(0){\mathbf{x}}_{0}}\right\rVert_{2}^{2}+\int_{0}^{t}\left\lVert{\dot{\bm{\Phi}}^{\top}{\bm{\Phi}}(\tau){\mathbf{x}}_{0}}\right\rVert_{2}^{2}\mathrm{d}{\tau}+\int_{0}^{t}\left\lVert{{\bm{\Phi}}^{\top}\dot{\bm{\Phi}}(\tau){\mathbf{x}}_{0}}\right\rVert_{2}^{2}\mathrm{d}{\tau},$

which is obtained in the same manner as Eq. 10 (in the proof of Lemma 10). We
substitute the dynamics (Lemma 1), or Eq. 11 in the proof of Lemma 10, and
simplify
$\left\lVert{\dot{\bm{\Phi}}^{\top}{\bm{\Phi}}(\tau){\mathbf{x}}_{0}}\right\rVert_{2}^{2}$
as follows:

$\displaystyle\left\lVert{\dot{\bm{\Phi}}^{\top}{\bm{\Phi}}{\mathbf{x}}_{0}}\right\rVert_{2}^{2}$
$\displaystyle=\left\lVert{{{{\bm{\Phi}}}^{\dagger}}{{{\mathbf{W}}}^{\dagger}}\operatorname*{{\mathbb{E}}}[{\mathbf{z}}^{\prime}{\bm{\omega}}^{\top}-({\bm{\omega}}^{\top}{\mathbf{z}}^{\prime}){\bm{\omega}}{\bm{\omega}}^{\top}]{\mathbf{W}}{\bm{\Phi}}{\mathbf{x}}_{0}-\rho{\bm{\Phi}}^{\top}{\bm{\Phi}}{\mathbf{x}}_{0}}\right\rVert_{2}^{2}$
$\displaystyle\leq\operatorname*{{\mathbb{E}}}\left\lVert{{{{\bm{\Phi}}}^{\dagger}}{{{\mathbf{W}}}^{\dagger}}({\mathbf{z}}^{\prime}{\bm{\omega}}^{\top}){\mathbf{W}}{\bm{\Phi}}{\mathbf{x}}_{0}}\right\rVert_{2}^{2}+\operatorname*{{\mathbb{E}}}\left\lVert{{{{\bm{\Phi}}}^{\dagger}}{{{\mathbf{W}}}^{\dagger}}({\bm{\omega}}{\bm{\omega}}^{\top}){\mathbf{W}}{\bm{\Phi}}{\mathbf{x}}_{0}}\right\rVert_{2}^{2}+\rho\left\lVert{{\bm{\Phi}}^{\top}{\bm{\Phi}}{\mathbf{x}}_{0}}\right\rVert_{2}^{2},$

where $\left|{{\bm{\omega}}^{\top}{\mathbf{z}}^{\prime}}\right|\leq 1$ is
used. The first term is bounded as follows:

$\displaystyle\left\lVert{{{{\bm{\Phi}}}^{\dagger}}{{{\mathbf{W}}}^{\dagger}}({\mathbf{z}}^{\prime}{\bm{\omega}}^{\top}){\mathbf{W}}{\bm{\Phi}}{\mathbf{x}}_{0}}\right\rVert_{2}^{2}$
$\displaystyle=\operatorname{\mathrm{tr}}\left({{{\bm{\Phi}}}^{\dagger}}{{{\mathbf{W}}}^{\dagger}}({\mathbf{z}}^{\prime}{\bm{\omega}}^{\top}){\mathbf{W}}{\bm{\Phi}}{\mathbf{x}}_{0}{\mathbf{x}}_{0}^{\top}{\bm{\Phi}}^{\top}{\mathbf{W}}^{\top}({\bm{\omega}}({\mathbf{z}}^{\prime})^{\top})({{{\mathbf{W}}}^{\dagger}})^{\top}({{{\bm{\Phi}}}^{\dagger}})^{\top}\right)$
$\displaystyle\overset{\text{(*)}}{=}\operatorname{\mathrm{tr}}\left(({\mathbf{z}}^{\prime}{\bm{\omega}}^{\top}){\mathbf{W}}{\bm{\Phi}}{\mathbf{x}}_{0}{\mathbf{x}}_{0}^{\top}{\bm{\Phi}}^{\top}{\mathbf{W}}^{\top}({\bm{\omega}}({\mathbf{z}}^{\prime})^{\top})({{{\mathbf{W}}}^{\dagger}})^{\top}({{{\bm{\Phi}}}^{\dagger}})^{\top}{{{\bm{\Phi}}}^{\dagger}}{{{\mathbf{W}}}^{\dagger}}\right)$
$\displaystyle\overset{(\natural)}{\leq}\left|{\operatorname{\mathrm{tr}}\left({\mathbf{W}}{\bm{\Phi}}{\mathbf{x}}_{0}{\mathbf{x}}_{0}^{\top}{\bm{\Phi}}^{\top}{\mathbf{W}}^{\top}({\bm{\omega}}({\mathbf{z}}^{\prime})^{\top})({{{\mathbf{W}}}^{\dagger}})^{\top}({{{\bm{\Phi}}}^{\dagger}})^{\top}{{{\bm{\Phi}}}^{\dagger}}{{{\mathbf{W}}}^{\dagger}}\right)}\right|$
$\displaystyle\overset{\text{(*)}}{=}\left|{\operatorname{\mathrm{tr}}\left(({\bm{\omega}}({\mathbf{z}}^{\prime})^{\top})({{{\mathbf{W}}}^{\dagger}})^{\top}({{{\bm{\Phi}}}^{\dagger}})^{\top}{{{\bm{\Phi}}}^{\dagger}}{{{\mathbf{W}}}^{\dagger}}{\mathbf{W}}{\bm{\Phi}}{\mathbf{x}}_{0}{\mathbf{x}}_{0}^{\top}{\bm{\Phi}}^{\top}{\mathbf{W}}^{\top}\right)}\right|$
$\displaystyle\overset{(\natural)}{\leq}\left|{\operatorname{\mathrm{tr}}\left(({{{\mathbf{W}}}^{\dagger}})^{\top}({{{\bm{\Phi}}}^{\dagger}})^{\top}{{{\bm{\Phi}}}^{\dagger}}{{{\mathbf{W}}}^{\dagger}}{\mathbf{W}}{\bm{\Phi}}{\mathbf{x}}_{0}{\mathbf{x}}_{0}^{\top}{\bm{\Phi}}^{\top}{\mathbf{W}}^{\top}\right)}\right|$
$\displaystyle\overset{\text{(*)}}{=}\left|{\operatorname{\mathrm{tr}}\left({{{\bm{\Phi}}}^{\dagger}}{{{\mathbf{W}}}^{\dagger}}{\mathbf{W}}{\bm{\Phi}}{\mathbf{x}}_{0}{\mathbf{x}}_{0}^{\top}\right)}\right|$
$\displaystyle\leq\left|{\operatorname{\mathrm{tr}}\left({{{\bm{\Phi}}}^{\dagger}}{{{\mathbf{W}}}^{\dagger}}{\mathbf{W}}{\bm{\Phi}}\right)\cdot\operatorname{\mathrm{tr}}\left({\mathbf{x}}_{0}{\mathbf{x}}_{0}^{\top}\right)}\right|$
$\displaystyle\overset{\text{(*)}}{=}\left|{\operatorname{\mathrm{tr}}\left({\mathbf{x}}_{0}{\mathbf{x}}_{0}^{\top}\right)}\right|$
$\displaystyle=\left\lVert{{\mathbf{x}}_{0}}\right\rVert_{2}^{2},$

where we use the trace cyclic property at (*), and the Cauchy-Schwartz
inequality and the trace property
$\left|{\operatorname{\mathrm{tr}}({\mathbf{z}}{\bm{\omega}}^{\top})}\right|=\left|{{\bm{\omega}}^{\top}{\mathbf{z}}}\right|\leq
1$ for ${\mathbf{z}},{\bm{\omega}}\in{\mathbb{S}}^{h-1}$ at ($\natural$).
Similarly,
$\left\lVert{{{{\bm{\Phi}}}^{\dagger}}{{{\mathbf{W}}}^{\dagger}}({\bm{\omega}}{\bm{\omega}}^{\top}){\mathbf{W}}{\bm{\Phi}}{\mathbf{x}}_{0}}\right\rVert_{2}^{2}\leq\left\lVert{{\mathbf{x}}_{0}}\right\rVert_{2}^{2}$.
Thus, we have
$\left\lVert{\dot{\bm{\Phi}}^{\top}{\bm{\Phi}}{\mathbf{x}}_{0}}\right\rVert_{2}^{2}\leq
2\left\lVert{{\mathbf{x}}_{0}}\right\rVert_{2}^{2}+\rho\left\lVert{{\bm{\Phi}}^{\top}{\bm{\Phi}}{\mathbf{x}}_{0}}\right\rVert_{2}^{2}$.
By doing the same algebra again, we have
$\left\lVert{{\bm{\Phi}}^{\top}\dot{\bm{\Phi}}{\mathbf{x}}_{0}}\right\rVert_{2}^{2}\leq
2\left\lVert{{\mathbf{x}}_{0}}\right\rVert_{2}^{2}+\rho\left\lVert{{\bm{\Phi}}^{\top}{\bm{\Phi}}{\mathbf{x}}_{0}}\right\rVert_{2}^{2}$
as well. By combining them,

$\left\lVert{{\bm{\Phi}}^{\top}{\bm{\Phi}}(t){\mathbf{x}}_{0}}\right\rVert_{2}^{2}\leq\left\lVert{{\bm{\Phi}}^{\top}{\bm{\Phi}}(0){\mathbf{x}}_{0}}\right\rVert_{2}^{2}+4\left\lVert{{\mathbf{x}}_{0}}\right\rVert_{2}^{2}t+2\rho\int_{0}^{t}\left\lVert{{\bm{\Phi}}^{\top}{\bm{\Phi}}(\tau){\mathbf{x}}_{0}}\right\rVert_{2}^{2}\mathrm{d}{\tau}$

holds, to which the Grönwall–Bellman inequality (Theorem 1) can be used, and
we deduce
$\left\lVert{{\bm{\Phi}}^{\top}{\bm{\Phi}}(t){\mathbf{x}}_{0}}\right\rVert_{2}^{2}\leq(\left\lVert{{\bm{\Phi}}^{\top}{\bm{\Phi}}(0){\mathbf{x}}_{0}}\right\rVert_{2}^{2}+4\left\lVert{{\mathbf{x}}_{0}}\right\rVert_{2}^{2}t)\exp(2\rho
t)$. ∎

######  Lemma 14.

For ${\mathbf{W}}\in{\mathbb{S}\mathrm{ym}}_{h}$, for any $t$, the following
bound holds:

$\left\lVert{{\bm{\Phi}}^{\top}{\mathbf{W}}^{\top}{\mathbf{W}}{\bm{\Phi}}(t)}\right\rVert_{\mathrm{F}}\leq\left\\{\left\lVert{{\bm{\Phi}}^{\top}{\mathbf{W}}^{\top}{\mathbf{W}}{\bm{\Phi}}(0)}\right\rVert_{\mathrm{F}}+\frac{16\rho
te^{2\rho t}+(2\rho I_{0}-8)(e^{2\rho t}-1)}{\rho^{2}}\right\\}e^{4\rho t},$

where
$I_{0}\coloneqq\operatorname{\mathrm{tr}}({\mathbf{W}}^{\top}{\mathbf{W}}(0))+\left\lVert{{\bm{\Phi}}^{\top}{\bm{\Phi}}(0)}\right\rVert_{\mathrm{F}}$.

###### Proof of Lemma 14.

By using the fundamental theorem of calculus and the triangular inequality,
the Frobenius norm
$\left\lVert{{\bm{\Phi}}^{\top}{\mathbf{W}}^{\top}{\mathbf{W}}{\bm{\Phi}}(t)}\right\rVert_{\mathrm{F}}$
is bounded:

$\displaystyle\left\lVert{{\bm{\Phi}}^{\top}{\mathbf{W}}^{\top}{\mathbf{W}}{\bm{\Phi}}(t)}\right\rVert_{\mathrm{F}}$
(14)
$\displaystyle\leq\left\lVert{{\bm{\Phi}}^{\top}{\mathbf{W}}^{\top}{\mathbf{W}}{\bm{\Phi}}(0)}\right\rVert_{\mathrm{F}}+2\int_{0}^{t}\left\lVert{\frac{\mathrm{d}{({\mathbf{W}}{\bm{\Phi}})(\tau)}}{\mathrm{d}{\tau}}^{\top}({\mathbf{W}}{\bm{\Phi}})(\tau)}\right\rVert_{\mathrm{F}}\mathrm{d}{\tau}$
$\displaystyle\leq\left\lVert{{\bm{\Phi}}^{\top}{\mathbf{W}}^{\top}{\mathbf{W}}{\bm{\Phi}}(0)}\right\rVert_{\mathrm{F}}+2\underbrace{\int_{0}^{t}\left\lVert{\dot{\bm{\Phi}}^{\top}{\mathbf{W}}^{\top}{\mathbf{W}}{\bm{\Phi}}(\tau)}\right\rVert_{\mathrm{F}}\mathrm{d}{\tau}}_{\text{(A)}}+2\underbrace{\int_{0}^{t}\left\lVert{{\bm{\Phi}}^{\top}\dot{\mathbf{W}}^{\top}{\mathbf{W}}{\bm{\Phi}}(\tau)}\right\rVert_{\mathrm{F}}\mathrm{d}{\tau}}_{\text{(B)}}.$

To bound (A) in Eq. 14, we proceed by plugging the dynamics (Lemma 1) in as
follows:

$\displaystyle\left\lVert{\dot{\bm{\Phi}}^{\top}{\mathbf{W}}^{\top}{\mathbf{W}}{\bm{\Phi}}}\right\rVert_{\mathrm{F}}$
$\displaystyle=\left\lVert{({{{\bm{\Phi}}}^{\dagger}}{{{\mathbf{W}}}^{\dagger}}\operatorname*{{\mathbb{E}}}[{\bm{\omega}}({\mathbf{z}}^{\prime})^{\top}-({\bm{\omega}}^{\top}{\mathbf{z}}^{\prime}){\bm{\omega}}{\bm{\omega}}^{\top}]{\mathbf{W}}-\rho{\bm{\Phi}}^{\top}){\mathbf{W}}^{\top}{\mathbf{W}}{\bm{\Phi}}}\right\rVert_{\mathrm{F}}$
(15)
$\displaystyle\leq\underbrace{\operatorname*{{\mathbb{E}}}\left\lVert{{{{\bm{\Phi}}}^{\dagger}}{{{\mathbf{W}}}^{\dagger}}({\bm{\omega}}({\mathbf{z}}^{\prime})^{\top}){\mathbf{W}}{\mathbf{W}}^{\top}{\mathbf{W}}{\bm{\Phi}}}\right\rVert_{\mathrm{F}}}_{(\clubsuit)}+\underbrace{\operatorname*{{\mathbb{E}}}\left\lVert{{{{\bm{\Phi}}}^{\dagger}}{{{\mathbf{W}}}^{\dagger}}({\bm{\omega}}{\bm{\omega}}^{\top}){\mathbf{W}}{\mathbf{W}}^{\top}{\mathbf{W}}{\bm{\Phi}}}\right\rVert_{\mathrm{F}}}_{(\diamondsuit)}$
$\displaystyle\phantom{\leq}+\rho\left\lVert{{\bm{\Phi}}^{\top}{\mathbf{W}}^{\top}{\mathbf{W}}{\bm{\Phi}}}\right\rVert_{\mathrm{F}}.$

We bound the squared ($\clubsuit$) in Eq. 15 as follows:

$\displaystyle\left\lVert{{{{\bm{\Phi}}}^{\dagger}}{{{\mathbf{W}}}^{\dagger}}({\bm{\omega}}({\mathbf{z}}^{\prime})^{\top}){\mathbf{W}}{\mathbf{W}}^{\top}{\mathbf{W}}{\bm{\Phi}}}\right\rVert_{\mathrm{F}}^{2}$
$\displaystyle=\operatorname{\mathrm{tr}}\left({\bm{\Phi}}^{\top}{\mathbf{W}}^{\top}{\mathbf{W}}{\mathbf{W}}^{\top}({\mathbf{z}}^{\prime}{\bm{\omega}}^{\top})({{{\mathbf{W}}}^{\dagger}})^{\top}({{{\bm{\Phi}}}^{\dagger}})^{\top}\cdot{{{\bm{\Phi}}}^{\dagger}}{{{\mathbf{W}}}^{\dagger}}({\bm{\omega}}({\mathbf{z}}^{\prime})^{\top}){\mathbf{W}}{\mathbf{W}}^{\top}{\mathbf{W}}{\bm{\Phi}}\right)$
$\displaystyle\overset{\text{(*$\natural$)}}{\leq}\left|{\operatorname{\mathrm{tr}}\left(({{{\mathbf{W}}}^{\dagger}})^{\top}({{{\bm{\Phi}}}^{\dagger}})^{\top}{{{\bm{\Phi}}}^{\dagger}}{{{\mathbf{W}}}^{\dagger}}({\bm{\omega}}({\mathbf{z}}^{\prime})^{\top}){\mathbf{W}}{\mathbf{W}}^{\top}{\mathbf{W}}{\bm{\Phi}}\cdot{\bm{\Phi}}^{\top}{\mathbf{W}}^{\top}{\mathbf{W}}{\mathbf{W}}^{\top}\right)}\right|$
$\displaystyle\overset{\text{(*)}}{=}\left|{\operatorname{\mathrm{tr}}\left(({{{\bm{\Phi}}}^{\dagger}})^{\top}{{{\bm{\Phi}}}^{\dagger}}{{{\mathbf{W}}}^{\dagger}}({\bm{\omega}}({\mathbf{z}}^{\prime})^{\top}){\mathbf{W}}{\mathbf{W}}^{\top}{\mathbf{W}}{\bm{\Phi}}{\bm{\Phi}}^{\top}{\mathbf{W}}^{\top}{\mathbf{W}}\right)}\right|$
$\displaystyle\overset{\text{(*$\natural$)}}{\leq}\left|{\operatorname{\mathrm{tr}}\left({\mathbf{W}}{\mathbf{W}}^{\top}{\mathbf{W}}{\bm{\Phi}}{\bm{\Phi}}^{\top}{\mathbf{W}}^{\top}{\mathbf{W}}\cdot({{{\bm{\Phi}}}^{\dagger}})^{\top}{{{\bm{\Phi}}}^{\dagger}}{{{\mathbf{W}}}^{\dagger}}\right)}\right|$
$\displaystyle\overset{\text{(*)}}{=}\left|{\operatorname{\mathrm{tr}}\left({{{\bm{\Phi}}}^{\dagger}}{\mathbf{W}}^{\top}{\mathbf{W}}{\bm{\Phi}}\cdot{\bm{\Phi}}^{\top}{\mathbf{W}}^{\top}{\mathbf{W}}({{{\bm{\Phi}}}^{\dagger}})^{\top}\right)}\right|$
$\displaystyle\leq\left|{\operatorname{\mathrm{tr}}({{{\bm{\Phi}}}^{\dagger}}{\mathbf{W}}^{\top}{\mathbf{W}}{\bm{\Phi}})\cdot\operatorname{\mathrm{tr}}({\bm{\Phi}}^{\top}{\mathbf{W}}^{\top}{\mathbf{W}}({{{\bm{\Phi}}}^{\dagger}})^{\top})}\right|$
$\displaystyle\overset{\text{(*)}}{=}\operatorname{\mathrm{tr}}({\mathbf{W}}^{\top}{\mathbf{W}})^{2},$

where we use the trace cyclic property at (*), and use the trace cyclic
property, the Cauchy-Schwartz inequality, and the trace evaluation of rank-$1$
matrices at (*$\natural$), as we do in the proof of Lemma 13. By using the
same techniques, the squared ($\diamondsuit$) in Eq. 15 can be bounded by
$\operatorname{\mathrm{tr}}({\mathbf{W}}^{\top}{\mathbf{W}})$ as well. Hence,
we obtain the bound of Eq. 15 as
$\left\lVert{\dot{\bm{\Phi}}^{\top}{\mathbf{W}}^{\top}{\mathbf{W}}{\bm{\Phi}}}\right\rVert_{\mathrm{F}}\leq
2\operatorname{\mathrm{tr}}({\mathbf{W}}^{\top}{\mathbf{W}})+\rho\left\lVert{{\bm{\Phi}}^{\top}{\mathbf{W}}^{\top}{\mathbf{W}}{\bm{\Phi}}}\right\rVert_{\mathrm{F}}$.
To bound (B) in Eq. 14, the dynamics (Lemma 1) is plugged in again:

$\displaystyle\left\lVert{{\bm{\Phi}}^{\top}\dot{\mathbf{W}}^{\top}{\mathbf{W}}{\bm{\Phi}}}\right\rVert_{\mathrm{F}}$
$\displaystyle=\left\lVert{{\bm{\Phi}}^{\top}\operatorname*{{\mathbb{E}}}[{\bm{\omega}}({\mathbf{z}}^{\prime})^{\top}-({\bm{\omega}}^{\top}{\mathbf{z}}^{\prime}){\bm{\omega}}{\bm{\omega}}^{\top}]{\bm{\Phi}}-\rho{\bm{\Phi}}^{\top}{\mathbf{W}}{\mathbf{W}}^{\top}{\bm{\Phi}}^{\top}}\right\rVert$
(16)
$\displaystyle\leq\underbrace{\operatorname*{{\mathbb{E}}}\left\lVert{{\bm{\Phi}}^{\top}({\bm{\omega}}({\mathbf{z}}^{\prime})^{\top}){\bm{\Phi}}}\right\rVert_{\mathrm{F}}}_{(\heartsuit)}+\underbrace{\operatorname*{{\mathbb{E}}}\left\lVert{{\bm{\Phi}}^{\top}({\bm{\omega}}{\bm{\omega}}^{\top}){\bm{\Phi}}}\right\rVert_{\mathrm{F}}}_{(\spadesuit)}+\rho\left\lVert{{\bm{\Phi}}^{\top}{\mathbf{W}}{\mathbf{W}}^{\top}{\bm{\Phi}}}\right\rVert_{\mathrm{F}},$

where the squared ($\heartsuit$) is bounded as follows:

$\displaystyle\left\lVert{{\bm{\Phi}}^{\top}({\bm{\omega}}({\mathbf{z}}^{\prime})^{\top}){\bm{\Phi}}}\right\rVert_{\mathrm{F}}^{2}$
$\displaystyle=\operatorname{\mathrm{tr}}\left({\bm{\Phi}}^{\top}({\mathbf{z}}^{\prime}{\bm{\omega}}^{\top}){\bm{\Phi}}\cdot{\bm{\Phi}}^{\top}({\bm{\omega}}({\mathbf{z}}^{\prime})^{\top}){\bm{\Phi}}\right)$
$\displaystyle\overset{(*\natural)}{\leq}\left|{\operatorname{\mathrm{tr}}\left({\bm{\Phi}}{\bm{\Phi}}^{\top}({\bm{\omega}}({\mathbf{z}}^{\prime})^{\top}){\bm{\Phi}}{\bm{\Phi}}^{\top}\right)}\right|$
$\displaystyle\overset{(*\natural)}{\leq}\left|{\operatorname{\mathrm{tr}}\left({\bm{\Phi}}{\bm{\Phi}}^{\top}{\bm{\Phi}}{\bm{\Phi}}^{\top}\right)}\right|$
$\displaystyle=\left\lVert{{\bm{\Phi}}{\bm{\Phi}}^{\top}}\right\rVert_{\mathrm{F}}^{2}$
$\displaystyle=\left\lVert{{\bm{\Phi}}^{\top}{\bm{\Phi}}}\right\rVert_{\mathrm{F}}^{2}.$

The squared ($\spadesuit$) is bounded by
$\left\lVert{{\bm{\Phi}}^{\top}{\bm{\Phi}}}\right\rVert_{\mathrm{F}}$ as well.
Hence, we obtain the bound of Eq. 16 as
$\left\lVert{{\bm{\Phi}}^{\top}\dot{\mathbf{W}}^{\top}{\mathbf{W}}{\bm{\Phi}}}\right\rVert_{\mathrm{F}}\leq
2\left\lVert{{\bm{\Phi}}^{\top}{\bm{\Phi}}}\right\rVert_{\mathrm{F}}+\rho\left\lVert{{\bm{\Phi}}^{\top}{\mathbf{W}}{\mathbf{W}}^{\top}{\bm{\Phi}}}\right\rVert_{\mathrm{F}}$.
Eventually, we obtain the following bound from Eq. 14 (which requires the
symmetry of ${\mathbf{W}}$):

$\displaystyle\left\lVert{{\bm{\Phi}}^{\top}{\mathbf{W}}^{\top}{\mathbf{W}}{\bm{\Phi}}(t)}\right\rVert_{\mathrm{F}}$
$\displaystyle\leq\left\lVert{{\bm{\Phi}}^{\top}{\mathbf{W}}^{\top}{\mathbf{W}}{\bm{\Phi}}(0)}\right\rVert_{\mathrm{F}}+4\int_{0}^{t}\operatorname{\mathrm{tr}}({\mathbf{W}}^{\top}{\mathbf{W}}(\tau))\mathrm{d}{\tau}$
$\displaystyle\phantom{\leq}+4\int_{0}^{t}\left\lVert{{\bm{\Phi}}^{\top}{\bm{\Phi}}(\tau)}\right\rVert_{\mathrm{F}}\mathrm{d}{\tau}+4\int_{0}^{t}\rho\left\lVert{{\bm{\Phi}}^{\top}{\mathbf{W}}^{\top}{\mathbf{W}}{\bm{\Phi}}(\tau)}\right\rVert_{\mathrm{F}}\mathrm{d}{\tau}$
$\displaystyle\leq\left\lVert{{\bm{\Phi}}^{\top}{\mathbf{W}}^{\top}{\mathbf{W}}{\bm{\Phi}}(0)}\right\rVert_{\mathrm{F}}+4\int_{0}^{t}\rho\left\lVert{{\bm{\Phi}}^{\top}{\mathbf{W}}^{\top}{\mathbf{W}}{\bm{\Phi}}(\tau)}\right\rVert_{\mathrm{F}}\mathrm{d}{\tau}$
$\displaystyle\phantom{\leq}+4\int_{0}^{t}\left\\{I_{0}\exp(2\rho\tau)+8\tau\exp(2\rho\tau)\right\\}\mathrm{d}{\tau}$
$\displaystyle\leq\left\lVert{{\bm{\Phi}}^{\top}{\mathbf{W}}^{\top}{\mathbf{W}}{\bm{\Phi}}(0)}\right\rVert_{\mathrm{F}}+4\int_{0}^{t}\rho\left\lVert{{\bm{\Phi}}^{\top}{\mathbf{W}}^{\top}{\mathbf{W}}{\bm{\Phi}}(\tau)}\right\rVert_{\mathrm{F}}\mathrm{d}{\tau}$
$\displaystyle\phantom{\leq}+\frac{16\rho te^{2\rho t}+(2\rho
I_{0}-8)(e^{2\rho t}-1)}{\rho^{2}},$

where Lemmas 10 and 12 are used at the second inequality and integration by
parts is used in the third inequality. This integral inequality can be solved
by the Grönwall–Bellman inequality (Theorem 1), and we can obtain the
conclusion. ∎

######  Lemma 15.

For ${\mathbf{W}}\in{\mathbb{S}\mathrm{ym}}_{h}$, for any $t$, the following
bound holds:

$\left\lVert{{\mathbf{W}}{\bm{\Phi}}(t)}\right\rVert\leq\sqrt{\left\\{\left\lVert{{\bm{\Phi}}^{\top}{\mathbf{W}}^{\top}{\mathbf{W}}{\bm{\Phi}}(0)}\right\rVert+\frac{16\rho
te^{2\rho t}+(2\rho I_{0}-8)(e^{2\rho t}-1)}{\rho^{2}}\right\\}e^{4\rho t}},$

where $I_{0}$ is defined in Lemma 14.

###### Proof of Lemma 15.

We evaluate
$\left\lVert{{\bm{\Phi}}^{\top}{\mathbf{W}}^{\top}{\mathbf{W}}{\bm{\Phi}}(t)}\right\rVert=\left\lVert{{\mathbf{W}}{\bm{\Phi}}(t)}\right\rVert^{2}$.
By the fundamental theorem of calculus, we obtain the following decomposition:

$\left\lVert{{\bm{\Phi}}^{\top}{\mathbf{W}}^{\top}{\mathbf{W}}{\bm{\Phi}}(t)}\right\rVert\leq\left\lVert{{\bm{\Phi}}^{\top}{\mathbf{W}}^{\top}{\mathbf{W}}{\bm{\Phi}}(0)}\right\rVert+2\int_{0}^{t}\left\lVert{\left(\frac{\mathrm{d}{{\mathbf{W}}{\bm{\Phi}}}}{\mathrm{d}{\tau}}\right)^{\top}{\mathbf{W}}{\bm{\Phi}}(\tau)}\right\rVert\mathrm{d}{\tau}.$

By following the same derivation as the proof of Lemma 14, it is not difficult
to see the following upper bound:

$\left\lVert{\left(\frac{\mathrm{d}{{\mathbf{W}}{\bm{\Phi}}}}{\mathrm{d}{\tau}}\right)^{\top}{\mathbf{W}}{\bm{\Phi}}}\right\rVert\leq
2\operatorname{\mathrm{tr}}({\mathbf{W}}^{\top}{\mathbf{W}})+2\left\lVert{{\bm{\Phi}}^{\top}{\bm{\Phi}}}\right\rVert_{\mathrm{F}}+2\rho\left\lVert{{\bm{\Phi}}^{\top}{\mathbf{W}}^{\top}{\mathbf{W}}{\bm{\Phi}}}\right\rVert.$

By plugging the results of Lemmas 10 and 12 into
$\operatorname{\mathrm{tr}}({\mathbf{W}}^{\top}{\mathbf{W}}(\tau))$ and
$\left\lVert{{\bm{\Phi}}^{\top}{\bm{\Phi}}(\tau)}\right\rVert_{\mathrm{F}}$,
we obtain the integral inequality:

$\displaystyle\left\lVert{{\bm{\Phi}}^{\top}{\mathbf{W}}^{\top}{\mathbf{W}}{\bm{\Phi}}(t)}\right\rVert$
$\displaystyle\leq\left\lVert{{\bm{\Phi}}^{\top}{\mathbf{W}}^{\top}{\mathbf{W}}{\bm{\Phi}}(0)}\right\rVert+4\rho\int_{0}^{t}\left\lVert{{\bm{\Phi}}^{\top}{\mathbf{W}}^{\top}{\mathbf{W}}{\bm{\Phi}}(\tau)}\right\rVert\mathrm{d}{\tau}$
$\displaystyle\phantom{\leq}+\frac{16\rho te^{2\rho t}+(2\rho
I_{0}-8)(e^{2\rho t}-1)}{\rho^{2}}.$

This can be solved via Theorem 1. ∎

######  Lemma 16.

For ${\mathbf{W}}\in{\mathbb{S}\mathrm{ym}}_{h}$, for any $t$, the following
bound holds:

$\displaystyle\left\lVert{{\bm{\Phi}}^{\top}{\mathbf{W}}^{\top}{\mathbf{W}}{\bm{\Phi}}(t){\mathbf{x}}_{0}}\right\rVert_{2}^{2}$
$\displaystyle\leq\left\\{\left\lVert{{\bm{\Phi}}^{\top}{\mathbf{W}}^{\top}{\mathbf{W}}{\bm{\Phi}}(0){\mathbf{x}}_{0}}\right\rVert_{2}^{2}+\Xi_{1}\left\lVert{{\mathbf{x}}_{0}}\right\rVert_{2}^{2}+\Xi_{2}\left\lVert{{\bm{\Phi}}^{\top}{\bm{\Phi}}(0){\mathbf{x}}_{0}}\right\rVert_{2}^{2}\right\\}\exp(2\rho
t),$

where

$\displaystyle\Xi_{1}$ $\displaystyle\coloneqq T_{0}^{2}\frac{e^{4\rho
t}-1}{\rho}\\!+\\!2T_{0}\frac{e^{4\rho t}(4\rho
t-1)+1}{\rho^{2}}\\!+\\!2\frac{e^{4\rho t}(8\rho^{2}t^{2}-4\rho
t+1)-1}{\rho^{3}}\\!+\\!4\frac{e^{2\rho t}(2\rho t-1)+1}{\rho^{2}},$
$\displaystyle\Xi_{2}$ $\displaystyle\coloneqq 2\frac{e^{2\rho t}-1}{\rho},$

and
$T_{0}\coloneqq\operatorname{\mathrm{tr}}({\mathbf{W}}^{\top}{\mathbf{W}}(0))$.

###### Proof of Lemma 16.

By using the fundamental theorem of calculus,
$\left\lVert{{\bm{\Phi}}^{\top}{\mathbf{W}}^{\top}{\mathbf{W}}{\bm{\Phi}}(t){\mathbf{x}}_{0}}\right\rVert_{2}^{2}$
is bounded as follows:

$\displaystyle\left\lVert{{\bm{\Phi}}^{\top}{\mathbf{W}}^{\top}{\mathbf{W}}{\bm{\Phi}}(t){\mathbf{x}}_{0}}\right\rVert_{2}^{2}$
(17)
$\displaystyle\leq\left\lVert{{\bm{\Phi}}^{\top}{\mathbf{W}}^{\top}{\mathbf{W}}{\bm{\Phi}}(0){\mathbf{x}}_{0}}\right\rVert_{2}^{2}+2\int_{0}^{t}\left\lVert{\left(\frac{\mathrm{d}{{\mathbf{W}}{\bm{\Phi}}}}{\mathrm{d}{\tau}}\right)^{\top}{\mathbf{W}}{\bm{\Phi}}(\tau){\mathbf{x}}_{0}}\right\rVert_{2}^{2}\mathrm{d}{\tau}$
$\displaystyle\leq\left\lVert{{\bm{\Phi}}^{\top}{\mathbf{W}}^{\top}{\mathbf{W}}{\bm{\Phi}}(0){\mathbf{x}}_{0}}\right\rVert_{2}^{2}$
$\displaystyle\phantom{\leq}+2\underbrace{\int_{0}^{t}\left\lVert{\dot{\bm{\Phi}}^{\top}{\mathbf{W}}^{\top}{\mathbf{W}}{\bm{\Phi}}(\tau){\mathbf{x}}_{0}}\right\rVert_{2}^{2}\mathrm{d}{\tau}}_{\text{(A)}}+2\underbrace{\int_{0}^{t}\left\lVert{{\bm{\Phi}}^{\top}\dot{\mathbf{W}}^{\top}{\mathbf{W}}{\bm{\Phi}}(\tau){\mathbf{x}}_{0}}\right\rVert_{2}^{2}\mathrm{d}{\tau}}_{\text{(B)}}.$

To bound (A) in Eq. 17, we follow almost the same calculation as Eq. 15 in the
proof of Lemma 13 (therefore omitted) and obtain
$\left\lVert{\dot{\bm{\Phi}}^{\top}{\mathbf{W}}^{\top}{\mathbf{W}}{\bm{\Phi}}{\mathbf{x}}_{0}}\right\rVert_{2}^{2}\leq\operatorname{\mathrm{tr}}({\mathbf{W}}^{\top}{\mathbf{W}})^{2}\left\lVert{{\mathbf{x}}_{0}}\right\rVert_{2}^{2}$.
To bound (B) in Eq. 17, we follow almost the same calculation as Eq. 16 in the
proof of Lemma 13 (therefore omitted) and obtain
$\left\lVert{{\bm{\Phi}}^{\top}\dot{\mathbf{W}}^{\top}{\mathbf{W}}{\bm{\Phi}}{\mathbf{x}}_{0}}\right\rVert_{2}^{2}\leq
2\left\lVert{{\bm{\Phi}}^{\top}{\bm{\Phi}}{\mathbf{x}}_{0}}\right\rVert_{2}^{2}+\rho\left\lVert{{\bm{\Phi}}^{\top}{\mathbf{W}}^{\top}{\mathbf{W}}{\bm{\Phi}}{\mathbf{x}}_{0}}\right\rVert_{2}^{2}$.
Here, the symmetry of ${\mathbf{W}}$ is used. By substituting them back into
(A) and (B) in Eq. 17, we obtain the following bound:

$\displaystyle\left\lVert{{\bm{\Phi}}^{\top}{\mathbf{W}}^{\top}{\mathbf{W}}{\bm{\Phi}}(t){\mathbf{x}}_{0}}\right\rVert_{2}^{2}$
$\displaystyle\leq\left\lVert{{\bm{\Phi}}^{\top}{\mathbf{W}}^{\top}{\mathbf{W}}{\bm{\Phi}}(0){\mathbf{x}}_{0}}\right\rVert_{2}^{2}+2\rho\int_{0}^{t}\left\lVert{{\bm{\Phi}}^{\top}{\mathbf{W}}^{\top}{\mathbf{W}}{\bm{\Phi}}(\tau){\mathbf{x}}_{0}}\right\rVert_{2}^{2}\mathrm{d}{\tau}$
$\displaystyle\phantom{\leq}+4\left\lVert{{\mathbf{x}}_{0}}\right\rVert_{2}^{2}\underbrace{\int_{0}^{t}\operatorname{\mathrm{tr}}({\mathbf{W}}^{\top}{\mathbf{W}}(\tau))^{2}\mathrm{d}{\tau}}_{(\clubsuit)}+4\underbrace{\int_{0}^{t}\left\lVert{{\bm{\Phi}}^{\top}{\bm{\Phi}}(\tau){\mathbf{x}}_{0}}\right\rVert_{2}^{2}\mathrm{d}{\tau}}_{(\diamondsuit)}.$

The term ($\clubsuit$) can be evaluated by Lemma 12 and integration by parts
as follows:

$\displaystyle(\clubsuit)$
$\displaystyle\leq\int_{0}^{t}(T_{0}+4\tau)^{2}\exp(4\rho\tau)\mathrm{d}{\tau}$
$\displaystyle=\int_{0}^{t}(T_{0}^{2}+8T_{0}\tau+16\tau^{2})\exp(4\rho\tau)\mathrm{d}{\tau}$
$\displaystyle=T_{0}^{2}\frac{e^{4\rho t}-1}{4\rho}+T_{0}\frac{e^{4\rho
t}(4\rho t-1)+1}{2\rho^{2}}+\frac{e^{4\rho t}(8\rho^{2}t^{2}-4\rho
t+1)-1}{2\rho^{3}},$

The term ($\diamondsuit$) can be evaluated by Lemma 13 and integration by
parts as follows:

$\displaystyle(\diamondsuit)$
$\displaystyle\leq\int_{0}^{t}\left\\{\left\lVert{{\bm{\Phi}}^{\top}{\bm{\Phi}}(0){\mathbf{x}}_{0}}\right\rVert_{2}^{2}+4\left\lVert{{\mathbf{x}}_{0}}\right\rVert_{2}^{2}\tau\right\\}e^{2\rho\tau}\mathrm{d}{\tau}$
$\displaystyle=\left\lVert{{\bm{\Phi}}^{\top}{\bm{\Phi}}(0){\mathbf{x}}_{0}}\right\rVert_{2}^{2}\frac{e^{2\rho
t}-1}{2\rho}+\left\lVert{{\mathbf{x}}_{0}}\right\rVert_{2}^{2}\frac{e^{2\rho
t}(2\rho t-1)+1}{\rho^{2}}.$

Hence, we obtain the following integral inequality:

$\displaystyle\left\lVert{{\bm{\Phi}}^{\top}{\mathbf{W}}^{\top}{\mathbf{W}}{\bm{\Phi}}(t){\mathbf{x}}_{0}}\right\rVert_{2}^{2}$
$\displaystyle\leq\left\lVert{{\bm{\Phi}}^{\top}{\mathbf{W}}^{\top}{\mathbf{W}}{\bm{\Phi}}(0){\mathbf{x}}_{0}}\right\rVert_{2}^{2}+\Xi_{1}\left\lVert{{\mathbf{x}}_{0}}\right\rVert_{2}^{2}+\Xi_{2}\left\lVert{{\bm{\Phi}}^{\top}{\bm{\Phi}}(0){\mathbf{x}}_{0}}\right\rVert_{2}^{2}$
$\displaystyle\phantom{\leq}+2\rho\int_{0}^{t}\left\lVert{{\bm{\Phi}}^{\top}{\mathbf{W}}^{\top}{\mathbf{W}}{\bm{\Phi}}(\tau){\mathbf{x}}_{0}}\right\rVert_{2}^{2}\mathrm{d}{\tau},$

which can be solved by the Grönwall–Bellman inequality (Theorem 1). As a
result, the desired bound on
$\left\lVert{{\bm{\Phi}}^{\top}{\mathbf{W}}^{\top}{\mathbf{W}}{\bm{\Phi}}(t){\mathbf{x}}_{0}}\right\rVert_{2}^{2}$
can be obtained. ∎

##  Appendix B Missing proofs

See 1

###### Proof of Lemma 1.

To derive the ${\mathbf{W}}$-dynamics, we begin with calculating the gradient
$\nabla_{\mathbf{W}}{{{\mathcal{L}}}_{\mathrm{cos}}}$.

$\displaystyle-\nabla_{\mathbf{W}}{{{\mathcal{L}}}_{\mathrm{cos}}}$
$\displaystyle=\operatorname*{{\mathbb{E}}}\left[\frac{1}{\left\lVert{{\bm{\Phi}}{\mathbf{x}}^{\prime}}\right\rVert_{2}}\frac{\left\lVert{{\mathbf{W}}{\bm{\Phi}}{\mathbf{x}}}\right\rVert_{2}\nabla_{\mathbf{W}}({\mathbf{x}}^{\top}{\bm{\Phi}}^{\top}{\mathbf{W}}^{\top}{\bm{\Phi}}{\mathbf{x}}^{\prime})-{\mathbf{x}}^{\top}{\bm{\Phi}}^{\top}{\mathbf{W}}^{\top}{\bm{\Phi}}{\mathbf{x}}^{\prime}\nabla_{\mathbf{W}}\left\lVert{{\mathbf{W}}{\bm{\Phi}}{\mathbf{x}}}\right\rVert_{2}}{\left\lVert{{\mathbf{W}}{\bm{\Phi}}{\mathbf{x}}}\right\rVert_{2}^{2}}\right]$
$\displaystyle=\operatorname*{{\mathbb{E}}}\left[\frac{\nabla_{\mathbf{W}}({\mathbf{x}}^{\top}{\bm{\Phi}}^{\top}{\mathbf{W}}^{\top}{\mathbf{z}}^{\prime})-{\bm{\omega}}^{\top}{\mathbf{z}}^{\prime}\nabla_{\mathbf{W}}\left\lVert{{\mathbf{W}}{\bm{\Phi}}{\mathbf{x}}}\right\rVert_{2}}{\left\lVert{{\mathbf{W}}{\bm{\Phi}}{\mathbf{x}}}\right\rVert_{2}}\right]$
$\displaystyle=\operatorname*{{\mathbb{E}}}\left[\frac{{\mathbf{z}}^{\prime}{\mathbf{x}}^{\top}{\bm{\Phi}}^{\top}-({\bm{\omega}}^{\top}{\mathbf{z}}^{\prime})\frac{{\mathbf{W}}{\bm{\Phi}}{\mathbf{x}}{\mathbf{x}}^{\top}{\bm{\Phi}}^{\top}}{\left\lVert{{\mathbf{W}}{\bm{\Phi}}{\mathbf{x}}}\right\rVert_{2}}}{\left\lVert{{\mathbf{W}}{\bm{\Phi}}{\mathbf{x}}}\right\rVert_{2}}\right]$
$\displaystyle=\operatorname*{{\mathbb{E}}}\left[{\mathbf{z}}^{\prime}\frac{{\mathbf{x}}^{\top}{\bm{\Phi}}^{\top}}{\left\lVert{{\mathbf{W}}{\bm{\Phi}}{\mathbf{x}}}\right\rVert_{2}}-({\bm{\omega}}^{\top}{\mathbf{z}}^{\prime}){\bm{\omega}}\frac{{\mathbf{x}}^{\top}{\bm{\Phi}}^{\top}}{\left\lVert{{\mathbf{W}}{\bm{\Phi}}{\mathbf{x}}}\right\rVert_{2}}\right].$

Here, ${\mathbf{W}}$ follows the dynamics
$\dot{\mathbf{W}}=-\nabla_{\mathbf{W}}{{{\mathcal{L}}}_{\mathrm{cos}}}-\rho{\mathbf{W}}$,
and hence we obtain
$\dot{\mathbf{W}}{\mathbf{W}}^{\top}=\operatorname*{{\mathbb{E}}}[{\mathbf{z}}^{\prime}{\bm{\omega}}^{\top}-({\bm{\omega}}^{\top}{\mathbf{z}}^{\prime}){\bm{\omega}}{\bm{\omega}}^{\top}]-\rho{\mathbf{W}}{\mathbf{W}}^{\top}$.

To derive the ${\bm{\Phi}}$-dynamics, we calculate the gradient
$\nabla_{\bm{\Phi}}{{{\mathcal{L}}}_{\mathrm{cos}}}$.

$\displaystyle-$
$\displaystyle\nabla_{\bm{\Phi}}{{{\mathcal{L}}}_{\mathrm{cos}}}$
$\displaystyle=\operatorname*{{\mathbb{E}}}\left[\frac{1}{\left\lVert{{\bm{\Phi}}{\mathbf{x}}^{\prime}}\right\rVert_{2}}\frac{\left\lVert{{\mathbf{W}}{\bm{\Phi}}{\mathbf{x}}}\right\rVert_{2}\nabla_{\bm{\Phi}}({\mathbf{x}}^{\top}{\bm{\Phi}}^{\top}{\mathbf{W}}^{\top}{\mathrm{StopGrad}}({\bm{\Phi}}){\mathbf{x}}^{\prime})-{\mathbf{x}}^{\top}{\bm{\Phi}}^{\top}{\mathbf{W}}^{\top}{\bm{\Phi}}{\mathbf{x}}^{\prime}\nabla_{\bm{\Phi}}\left\lVert{{\mathbf{W}}{\bm{\Phi}}{\mathbf{x}}}\right\rVert_{2}}{\left\lVert{{\mathbf{W}}{\bm{\Phi}}{\mathbf{x}}}\right\rVert_{2}^{2}}\right]$
$\displaystyle=\operatorname*{{\mathbb{E}}}\left[\frac{1}{\left\lVert{{\bm{\Phi}}{\mathbf{x}}^{\prime}}\right\rVert_{2}}\frac{\left\lVert{{\mathbf{W}}{\bm{\Phi}}{\mathbf{x}}}\right\rVert_{2}{\mathbf{W}}^{\top}{\bm{\Phi}}{\mathbf{x}}^{\prime}{\mathbf{x}}^{\top}-{\mathbf{x}}^{\top}{\bm{\Phi}}^{\top}{\mathbf{W}}^{\top}{\bm{\Phi}}{\mathbf{x}}^{\prime}\frac{{\mathbf{W}}^{\top}{\mathbf{W}}{\bm{\Phi}}{\mathbf{x}}{\mathbf{x}}^{\top}}{\left\lVert{{\mathbf{W}}{\bm{\Phi}}{\mathbf{x}}}\right\rVert_{2}}}{\left\lVert{{\mathbf{W}}{\bm{\Phi}}{\mathbf{x}}}\right\rVert_{2}^{2}}\right]$
$\displaystyle={\mathbf{W}}^{\top}\operatorname*{{\mathbb{E}}}\left[\frac{{\mathbf{z}}^{\prime}{\mathbf{x}}^{\top}-({\bm{\omega}}^{\top}{\mathbf{z}}^{\prime}){\bm{\omega}}{\mathbf{x}}^{\top}}{\left\lVert{{\mathbf{W}}{\bm{\Phi}}{\mathbf{x}}}\right\rVert_{2}}\right],$

from which
$(-\nabla_{\bm{\Phi}}{{{\mathcal{L}}}_{\mathrm{cos}}}){\bm{\Phi}}^{\top}{\mathbf{W}}^{\top}={\mathbf{W}}^{\top}\operatorname*{{\mathbb{E}}}[{\mathbf{z}}^{\prime}{\bm{\omega}}^{\top}-({\bm{\omega}}^{\top}{\mathbf{z}}^{\prime}){\bm{\omega}}{\bm{\omega}}^{\top}]$
follows. Thus, the dynamics
$\dot{\bm{\Phi}}=-\nabla_{\bm{\Phi}}{{{\mathcal{L}}}_{\mathrm{cos}}}-\rho{\bm{\Phi}}$
can be written as
$\dot{\bm{\Phi}}{\bm{\Phi}}^{\top}{\mathbf{W}}^{\top}={\mathbf{W}}^{\top}\operatorname*{{\mathbb{E}}}[{\mathbf{z}}^{\prime}{\bm{\omega}}^{\top}-({\bm{\omega}}^{\top}{\mathbf{z}}^{\prime}){\bm{\omega}}{\bm{\omega}}^{\top}]-\rho{\bm{\Phi}}{\bm{\Phi}}^{\top}{\mathbf{W}}^{\top}$.
∎

See 2

###### Proof of Lemma 2.

We will show concentration of
$\left\lVert{\frac{1}{\sqrt{h\sigma^{2}}}{\bm{\Phi}}{\mathbf{x}}}\right\rVert_{2}^{2}$
and
$\left\lVert{\frac{1}{\sqrt{h^{2}\sigma^{2}}}{\mathbf{W}}{\bm{\Phi}}{\mathbf{x}}}\right\rVert_{2}^{2}$.

#### Concentration of
$\left\lVert{{\bm{\Phi}}{\mathbf{x}}}\right\rVert_{2}^{2}$

: We begin with showing the first concentration.

$\displaystyle\left\lVert{\frac{1}{\sqrt{h\sigma^{2}}}{\bm{\Phi}}{\mathbf{x}}}\right\rVert_{2}^{2}$
$\displaystyle=\left\lVert{\frac{1}{\sqrt{h}}\left({\bm{\Phi}}\frac{{\mathbf{x}}-{\mathbf{x}}_{0}}{\sigma}+{\bm{\Phi}}\frac{{\mathbf{x}}_{0}}{\sigma}\right)}\right\rVert_{2}^{2}$
(18)
$\displaystyle=\underbrace{\left\lVert{\frac{1}{\sqrt{h}}{\bm{\Phi}}\frac{{\mathbf{x}}-{\mathbf{x}}_{0}}{\sigma}}\right\rVert_{2}^{2}}_{\text{(A)}}+2\sigma^{-1}\underbrace{\left\langle{\frac{1}{\sqrt{h}}{\bm{\Phi}}\frac{{\mathbf{x}}-{\mathbf{x}}_{0}}{\sigma}},{\frac{1}{\sqrt{h}}{\bm{\Phi}}{\mathbf{x}}_{0}}\right\rangle}_{\text{(B)}}+\left\lVert{\frac{1}{\sqrt{h}}{\bm{\Phi}}\frac{{\mathbf{x}}_{0}}{\sigma}}\right\rVert_{2}^{2}.$

To deal with (A), which is a Gaussian chaos (namely, a quadratic form with
standard normal vectors), we invoke the Hanson–Wright inequality [38, Theorem
6.3.2]. Note that $\frac{{\mathbf{x}}-{\mathbf{x}}_{0}}{\sigma}$ follows the
standard normal distribution. Then, the following inequality holds with
probability at least $1-\delta$ (over the sampling of ${\mathbf{x}}$):

$\left|{\left\lVert{\frac{1}{\sqrt{h}}{\bm{\Phi}}\frac{{\mathbf{x}}-{\mathbf{x}}_{0}}{\sigma}}\right\rVert_{2}-\left\lVert{\frac{1}{\sqrt{h}}{\bm{\Phi}}}\right\rVert_{\mathrm{F}}}\right|\leq\sqrt{\frac{C_{0}\left\lVert{{\bm{\Phi}}}\right\rVert^{2}\log\frac{2}{\delta}}{h}},$
(19)

where the expectation is taken over
${\mathbf{x}}\sim{\mathcal{N}}({\mathbf{x}}_{0},\sigma^{2}{\mathbf{I}}_{d})$,
and $C_{0}$ is an absolute constant irrelevant to $d$ and $h$. Now, we
evaluate the deviation term and show it vanishes as $d,h\to\infty$. Since the
deviation term contains $\left\lVert{{\bm{\Phi}}}\right\rVert^{2}$ and it
depends on the time $t$, we need to carefully evaluate its order in $d$ and
$h$ along with time evolution. For this purpose, Lemma 11 is used to obtain
$\left\lVert{{\bm{\Phi}}(t)}\right\rVert^{2}\leq(\left\lVert{{\bm{\Phi}}^{\top}{\bm{\Phi}}(0)}\right\rVert+4t)\exp(2\rho
t)$. Lastly, the Gaussian initialization of ${\bm{\Phi}}$ (Assumption 4)
induces
$\frac{1}{h}\left\lVert{{\bm{\Phi}}^{\top}{\bm{\Phi}}(0)}\right\rVert={o_{{\mathbb{P}}}}(1)$
(by Lemma 7). Thus, the deviation term of Eq. 19 is bounded from above as
follows:

$\sqrt{\frac{C_{0}(\left\lVert{{\bm{\Phi}}^{\top}{\bm{\Phi}}(0)}\right\rVert+4t)\exp(2\rho
t)\log\frac{2}{\delta}}{h}}={o_{{\mathbb{P}}}}(1),$

from which we conclude as follows:

$\left\lVert{\frac{1}{\sqrt{h}}{\bm{\Phi}}\frac{{\mathbf{x}}-{\mathbf{x}}_{0}}{\sigma}}\right\rVert_{2}^{2}=\left\lVert{\frac{1}{\sqrt{h}}{\bm{\Phi}}}\right\rVert_{\mathrm{F}}^{2}+{o_{{\mathbb{P}}}}(1).$

Next, we deal with (B) in Eq. 18. The term (B) is equivalent to
$\left\langle{\frac{1}{h}{\bm{\Phi}}^{\top}{\bm{\Phi}}{\mathbf{x}}_{0}},{\frac{{\mathbf{x}}-{\mathbf{x}}_{0}}{\sigma}}\right\rangle$,
which is a linear combination of the standard normal random variables. Its
concentration (to mean $0$) can be established by the general Hoeffding’s
inequality [38, Theorem 2.6.3] as follows: With probability at least
$1-\delta$ (over the sampling of ${\mathbf{x}}$),

$\text{(B)}=\left|{\left\langle{\frac{1}{h}{\bm{\Phi}}^{\top}{\bm{\Phi}}{\mathbf{x}}_{0}},{\frac{{\mathbf{x}}-{\mathbf{x}}_{0}}{\sigma}}\right\rangle}\right|\leq\sqrt{\frac{C_{1}\left\lVert{{\bm{\Phi}}^{\top}{\bm{\Phi}}{\mathbf{x}}_{0}}\right\rVert_{2}^{2}\log\frac{2}{\delta}}{h^{2}}},$
(20)

where $C_{1}$ is an absolute constant irrelevant to $d$ and $h$. We need to
evaluate
$\left\lVert{{\bm{\Phi}}^{\top}{\bm{\Phi}}(t){\mathbf{x}}_{0}}\right\rVert_{2}^{2}$
by noting its time dependency again. For this purpose, Lemma 13 is used to
obtain
$\left\lVert{{\bm{\Phi}}^{\top}{\bm{\Phi}}(t){\mathbf{x}}_{0}}\right\rVert_{2}^{2}\leq(\left\lVert{{\bm{\Phi}}^{\top}{\bm{\Phi}}(0){\mathbf{x}}_{0}}\right\rVert_{2}^{2}+4\left\lVert{{\mathbf{x}}_{0}}\right\rVert_{2}^{2}t)\exp(2\rho
t)$. Here,
$\frac{1}{h^{2}}\left\lVert{{\bm{\Phi}}^{\top}{\bm{\Phi}}(0){\mathbf{x}}_{0}}\right\rVert_{2}^{2}={o_{{\mathbb{P}}}}(1)$
(Lemma 9) holds. In addition,
${\mathbf{x}}_{0}\sim{\mathcal{N}}({\mathbf{0}},{\mathbf{I}})$ (Assumption 2)
indicates that $\left\lVert{{\mathbf{x}}_{0}}\right\rVert_{2}^{2}$ is the sum
of independent zero-mean sub-exponential random variables, from which
Bernstein’s inequality claim
$\left\lVert{{\mathbf{x}}_{0}}\right\rVert_{2}^{2}={{\mathcal{O}}_{{\mathbb{P}}}}(d)$
[38, Corollary 2.8.3]. Plugging them into the upper bound of
$\left\lVert{{\bm{\Phi}}^{\top}{\bm{\Phi}}(t){\mathbf{x}}_{0}}\right\rVert_{2}^{2}$,
we deduce

$\text{(B)}\leq\sqrt{C_{1}\log\frac{2}{\delta}\left(\frac{\left\lVert{{\bm{\Phi}}^{\top}{\bm{\Phi}}(0){\mathbf{x}}_{0}}\right\rVert_{2}^{2}}{h^{2}}+4t\frac{\left\lVert{{\mathbf{x}}_{0}}\right\rVert_{2}^{2}}{h^{2}}\right)e^{2\rho
t}}=\sqrt{{o_{{\mathbb{P}}}}(1)+{{\mathcal{O}}_{{\mathbb{P}}}}(\alpha
h^{-1})}={o_{{\mathbb{P}}}}(1).$

Eventually, the concentration of (A) and (B) is established and the conclusion
follows from Eq. 18.

#### Concentration of
$\left\lVert{{\mathbf{W}}{\bm{\Phi}}{\mathbf{x}}}\right\rVert_{2}^{2}$

: In the same manner as Eq. 18, we have the following decomposition:

$\left\lVert{\frac{1}{\sqrt{h^{2}\sigma^{2}}}{\mathbf{W}}{\bm{\Phi}}{\mathbf{x}}}\right\rVert_{2}^{2}=\left\lVert{\frac{1}{h}{\mathbf{W}}{\bm{\Phi}}\frac{{\mathbf{x}}-{\mathbf{x}}_{0}}{\sigma}}\right\rVert_{2}^{2}+\frac{2}{\sigma}\left\langle{\frac{1}{h}{\mathbf{W}}{\bm{\Phi}}\frac{{\mathbf{x}}-{\mathbf{x}}_{0}}{\sigma}},{\frac{1}{h}{\mathbf{W}}{\bm{\Phi}}{\mathbf{x}}_{0}}\right\rangle+\left\lVert{\frac{1}{h}{\mathbf{W}}{\bm{\Phi}}\frac{{\mathbf{x}}_{0}}{\sigma}}\right\rVert_{2}^{2}.$
(21)

The subsequent analysis follows in a very similar way to the analysis of
$\left\lVert{\frac{1}{\sqrt{h\sigma^{2}}}{\bm{\Phi}}{\mathbf{x}}}\right\rVert_{2}^{2}$.
Indeed, we can obtain the following inequalities (each of them with
probability at least $1-\delta$, respectively):

$\displaystyle\left|{\left\lVert{\frac{1}{h}{\mathbf{W}}{\bm{\Phi}}\frac{{\mathbf{x}}-{\mathbf{x}}_{0}}{\sigma}}\right\rVert_{2}-\left\lVert{\frac{1}{h}{\mathbf{W}}{\bm{\Phi}}}\right\rVert_{\mathrm{F}}}\right|$
$\displaystyle\leq\sqrt{\frac{C_{2}\left\lVert{{\mathbf{W}}{\bm{\Phi}}}\right\rVert^{2}\log\frac{2}{\delta}}{h^{2}}},$
(22)
$\displaystyle\left|{\left\langle{\frac{1}{h}{\mathbf{W}}{\bm{\Phi}}\frac{{\mathbf{x}}-{\mathbf{x}}_{0}}{\sigma}},{\frac{1}{h}{\mathbf{W}}{\bm{\Phi}}{\mathbf{x}}_{0}}\right\rangle}\right|$
$\displaystyle\leq\sqrt{\frac{C_{3}\left\lVert{{\bm{\Phi}}^{\top}{\mathbf{W}}^{\top}{\mathbf{W}}{\bm{\Phi}}{\mathbf{x}}_{0}}\right\rVert_{2}^{2}\log\frac{2}{\delta}}{h^{4}}},$
(23)

where $C_{2}$ and $C_{3}$ are absolute constants (see Eqs. 19 and 20).

To deal with Eq. 22, we control the spectral norm
$\left\lVert{{\mathbf{W}}{\bm{\Phi}}(t)}\right\rVert$ along time evolution by
using Lemma 15, and obtain the following bound:

$\left\lVert{{\mathbf{W}}{\bm{\Phi}}(t)}\right\rVert^{2}\leq\left\\{\left\lVert{{\bm{\Phi}}^{\top}{\mathbf{W}}^{\top}{\mathbf{W}}{\bm{\Phi}}(0)}\right\rVert+\frac{16\rho
te^{2\rho t}+(2\rho I_{0}-8)(e^{2\rho t}-1)}{\rho^{2}}\right\\}e^{4\rho t},$

where
$I_{0}\coloneqq\operatorname{\mathrm{tr}}({\mathbf{W}}^{\top}{\mathbf{W}}(0))+\left\lVert{{\bm{\Phi}}^{\top}{\bm{\Phi}}(0)}\right\rVert_{\mathrm{F}}$.
By plugging this bound back into Eq. 22 and using Lemmas 7 and 8, we obtain

$\left\lVert{\frac{1}{h}{\mathbf{W}}{\bm{\Phi}}\frac{{\mathbf{x}}-{\mathbf{x}}_{0}}{\sigma}}\right\rVert_{2}^{2}=\left\lVert{\frac{1}{h}{\mathbf{W}}{\bm{\Phi}}}\right\rVert_{\mathrm{F}}^{2}+{o_{{\mathbb{P}}}}(1).$

Next, we deal with Eq. 23 by controlling the L2 norm
$\left\lVert{{\bm{\Phi}}^{\top}{\mathbf{W}}^{\top}{\mathbf{W}}{\bm{\Phi}}(t){\mathbf{x}}_{0}}\right\rVert_{2}^{2}$
along time evolution. By using Lemma 16, we obtain the following bound:

$\displaystyle\left\lVert{{\bm{\Phi}}^{\top}{\mathbf{W}}^{\top}{\mathbf{W}}{\bm{\Phi}}(t){\mathbf{x}}_{0}}\right\rVert_{2}^{2}$
$\displaystyle\leq\left\\{\left\lVert{{\bm{\Phi}}^{\top}{\mathbf{W}}^{\top}{\mathbf{W}}{\bm{\Phi}}(0){\mathbf{x}}_{0}}\right\rVert_{2}^{2}+{\mathcal{O}}(\left\lVert{{\bm{\Phi}}^{\top}{\bm{\Phi}}(0){\mathbf{x}}_{0}}\right\rVert_{2}^{2})+\left\lVert{{\mathbf{x}}_{0}}\right\rVert_{2}^{2}{\mathcal{O}}(\operatorname{\mathrm{tr}}({\mathbf{W}}^{\top}{\mathbf{W}}(0))^{2})\right\\}e^{2\rho
t},$

where the order term
${\mathcal{O}}(\operatorname{\mathrm{tr}}({\mathbf{W}}^{\top}{\mathbf{W}}(0))^{2})$
hides the dependency on $t$. We now combine Lemmas 8 and 9 and the consequence
of Bernstein’s inequality
$\left\lVert{{\mathbf{x}}_{0}}\right\rVert_{2}^{2}={{\mathcal{O}}_{{\mathbb{P}}}}(d)$
and substitute them into Eq. 23. Then, we obtain

$\displaystyle\left|{\left\langle{\frac{1}{h}{\mathbf{W}}{\bm{\Phi}}\frac{{\mathbf{x}}-{\mathbf{x}}_{0}}{\sigma}},{\frac{1}{h}{\mathbf{W}}{\bm{\Phi}}{\mathbf{x}}_{0}}\right\rangle}\right|$
$\displaystyle\leq\sqrt{C_{3}^{\prime}\left\\{\frac{\left\lVert{{\bm{\Phi}}^{\top}{\mathbf{W}}^{\top}{\mathbf{W}}{\bm{\Phi}}(0){\mathbf{x}}_{0}}\right\rVert_{2}^{2}}{h^{4}}+\frac{{\mathcal{O}}(\left\lVert{{\bm{\Phi}}^{\top}{\bm{\Phi}}(0){\mathbf{x}}_{0}}\right\rVert_{2}^{2})}{h^{4}}+\frac{\left\lVert{{\mathbf{x}}_{0}}\right\rVert_{2}^{2}{\mathcal{O}}(\operatorname{\mathrm{tr}}({\mathbf{W}}^{\top}{\mathbf{W}}(0))^{2})}{h^{4}}\right\\}}$
$\displaystyle=\sqrt{{o_{{\mathbb{P}}}}(1)+{o_{{\mathbb{P}}}}(1)\cdot
h^{-2}+{{\mathcal{O}}_{{\mathbb{P}}}}(d)\cdot{o_{{\mathbb{P}}}}(1)\cdot
h^{-2}}$ $\displaystyle={o_{{\mathbb{P}}}}(1),$

where $C_{3}^{\prime}\coloneqq C_{3}e^{2\rho t}\log\tfrac{2}{\delta}$.

Hence, the concentration result for
$\left\lVert{\frac{1}{\sqrt{h^{2}\sigma^{2}}}{\mathbf{W}}{\bm{\Phi}}{\mathbf{x}}}\right\rVert_{2}^{2}$
is established by substituting Eqs. 22 and 23 back into Eq. 21. ∎

See 3

###### Proof of Lemma 3.

To establish concentration of
$\left\lVert{{\bm{\Phi}}{\mathbf{x}}_{0}}\right\rVert_{2}$, we invoke the
Hanson–Wright inequality [38, Theorem 6.3.2]: For an absolute constant
$C_{0}$,

$\left|{\left\lVert{\frac{1}{\sqrt{h\sigma^{2}}}{\bm{\Phi}}{\mathbf{x}}_{0}}\right\rVert_{2}-\left\lVert{\frac{1}{\sqrt{h\sigma^{2}}}{\bm{\Phi}}}\right\rVert_{\mathrm{F}}}\right|\leq\sqrt{\frac{C_{0}\left\lVert{{\bm{\Phi}}}\right\rVert^{2}\log\frac{2}{\delta}}{h\sigma^{2}}},$

with probability at least $1-\delta$. Here, we further derive the upper bound
of the right-hand side by Lemma 11:

$\frac{\left\lVert{{\bm{\Phi}}(t)}\right\rVert^{2}}{h}\leq\frac{(\left\lVert{{\bm{\Phi}}^{\top}{\bm{\Phi}}(0)}\right\rVert+4t)\exp(2\rho
t)}{h}={o_{{\mathbb{P}}}}(1),$

where the last identity follows from Lemma 7. Thus, the concentration of
$\left\lVert{{\bm{\Phi}}{\mathbf{x}}_{0}}\right\rVert_{2}$ is shown.

To establish concentration of
$\left\lVert{{\mathbf{W}}{\bm{\Phi}}{\mathbf{x}}_{0}}\right\rVert$, we invoke
the Hanson–Wright inequality again: For an absolute constant $C_{1}$,

$\left|{\left\lVert{\frac{1}{\sqrt{h^{2}\sigma^{2}}}{\mathbf{W}}{\bm{\Phi}}{\mathbf{x}}_{0}}\right\rVert-\left\lVert{\frac{1}{\sqrt{h^{2}\sigma^{2}}}{\mathbf{W}}{\bm{\Phi}}}\right\rVert_{\mathrm{F}}}\right|\leq\sqrt{\frac{C_{1}\left\lVert{{\mathbf{W}}{\bm{\Phi}}}\right\rVert^{2}\log\frac{2}{\delta}}{h^{2}\sigma^{2}}},$

with probability at least $1-\delta$. We can show
$\frac{1}{h^{2}}\left\lVert{{\mathbf{W}}{\bm{\Phi}}(t)}\right\rVert^{2}={o_{{\mathbb{P}}}}(1)$
in the same way as in the proof of Lemma 2. ∎

See 4

###### Proof of Lemma 4.

To evaluate
${\mathbf{H}}=\operatorname*{{\mathbb{E}}}[{\mathbf{z}}^{\prime}{\bm{\omega}}^{\top}-({\bm{\omega}}^{\top}{\mathbf{z}}^{\prime}){\bm{\omega}}{\bm{\omega}}^{\top}]\coloneqq{\mathbf{H}}_{1}-{\mathbf{H}}_{2}$,
where
${\mathbf{H}}_{1}\coloneqq\operatorname*{{\mathbb{E}}}[{\mathbf{z}}^{\prime}{\bm{\omega}}^{\top}]$
and
${\mathbf{H}}_{2}=\operatorname*{{\mathbb{E}}}[({\bm{\omega}}^{\top}{\mathbf{z}}^{\prime}){\bm{\omega}}{\bm{\omega}}^{\top}]$,
we evaluate the normalizers
$\left\lVert{{\bm{\Phi}}{\mathbf{x}}^{\prime}}\right\rVert_{2}^{-1}$ and
$\left\lVert{{\mathbf{W}}{\bm{\Phi}}{\mathbf{x}}}\right\rVert_{2}^{-1}$ first.
By Lemmas 2 and 3,

$\displaystyle\frac{1}{\left\lVert{{\bm{\Phi}}{\mathbf{x}}^{\prime}}\right\rVert_{2}}$
$\displaystyle=\frac{1}{\sqrt{h\sigma^{2}}}\cdot\left\\{\left\lVert{\frac{1}{\sqrt{h}}{\bm{\Phi}}}\right\rVert_{\mathrm{F}}^{2}+\left\lVert{\frac{1}{\sqrt{h\sigma^{2}}}{\bm{\Phi}}}\right\rVert_{\mathrm{F}}^{2}+{o_{{\mathbb{P}}}}(1)\right\\}^{-1/2}$
$\displaystyle=\frac{1}{\sqrt{h\sigma^{2}}}\cdot\frac{1}{\sqrt{1+\sigma^{-2}}\left\lVert{\frac{1}{\sqrt{h}}{\bm{\Phi}}}\right\rVert_{\mathrm{F}}+{o_{{\mathbb{P}}}}(1)}$
$\displaystyle\stackrel{{\scriptstyle(\clubsuit)}}{{=}}\frac{1}{\sqrt{h\sigma^{2}}}\cdot\left\\{\frac{1}{\sqrt{1+\sigma^{-2}}\left\lVert{\frac{1}{\sqrt{h}}{\bm{\Phi}}}\right\rVert_{\mathrm{F}}}+{o_{{\mathbb{P}}}}(1)\right\\}$
$\displaystyle=\frac{1}{\sqrt{1+\sigma^{2}}}\cdot\frac{1}{\left\lVert{{\bm{\Phi}}}\right\rVert_{\mathrm{F}}}+{o_{{\mathbb{P}}}}(1),$

where $(\clubsuit)$ is due to the first-order Taylor expansion
$f(\varepsilon)=\frac{1}{x+\varepsilon}\approx\frac{1}{x}-\frac{\varepsilon}{x^{2}}$
around $\varepsilon=0$. Similarly, we have

$\frac{1}{\left\lVert{{\mathbf{W}}{\bm{\Phi}}{\mathbf{x}}}\right\rVert_{2}}=\frac{1}{\left\lVert{{\bm{\Psi}}{\mathbf{x}}}\right\rVert_{2}}=\frac{1}{\sqrt{1+\sigma^{2}}}\cdot\frac{1}{\left\lVert{{\bm{\Psi}}}\right\rVert_{\mathrm{F}}}+{o_{{\mathbb{P}}}}(1).$

Next, we evaluate ${\mathbf{H}}_{1}$.

$\displaystyle{\mathbf{H}}_{1}$
$\displaystyle=\operatorname*{{\mathbb{E}}}_{{\mathbf{x}}_{0}}\operatorname*{{\mathbb{E}}}_{{\mathbf{x}},{\mathbf{x}}^{\prime}}\left[\frac{{\bm{\Phi}}{\mathbf{x}}^{\prime}}{\left\lVert{{\bm{\Phi}}{\mathbf{x}}^{\prime}}\right\rVert_{2}}\left(\frac{{\bm{\Psi}}{\mathbf{x}}}{\left\lVert{{\bm{\Psi}}{\mathbf{x}}}\right\rVert_{2}}\right)^{\top}\right]$
$\displaystyle=\operatorname*{{\mathbb{E}}}_{{\mathbf{x}}_{0}}\left[\frac{1}{(1+\sigma^{2})\left\lVert{{\bm{\Phi}}}\right\rVert_{\mathrm{F}}\left\lVert{{\bm{\Psi}}}\right\rVert_{\mathrm{F}}}\operatorname*{{\mathbb{E}}}_{{\mathbf{x}},{\mathbf{x}}^{\prime}}[{\bm{\Phi}}{\mathbf{x}}^{\prime}{\mathbf{x}}^{\top}{\bm{\Psi}}^{\top}]\right]+{o_{{\mathbb{P}}}}(1)$
$\displaystyle=\frac{1}{1+\sigma^{2}}\frac{{\bm{\Phi}}}{\left\lVert{{\bm{\Phi}}}\right\rVert_{\mathrm{F}}}\frac{{\bm{\Psi}}^{\top}}{\left\lVert{{\bm{\Psi}}}\right\rVert_{\mathrm{F}}}+{o_{{\mathbb{P}}}}(1),$

where we used
$\operatorname*{{\mathbb{E}}}_{{\mathbf{x}}_{0}}\operatorname*{{\mathbb{E}}}_{{\mathbf{x}},{\mathbf{x}}^{\prime}}[{\mathbf{x}}^{\prime}{\mathbf{x}}^{\top}]=\operatorname*{{\mathbb{E}}}_{{\mathbf{x}}_{0}}[{\mathbf{x}}_{0}{\mathbf{x}}_{0}^{\top}]={\mathbf{I}}_{d}$
at the last identity. We can evaluate ${\mathbf{H}}_{2}$ similarly.

$\displaystyle{\mathbf{H}}_{2}$
$\displaystyle=\operatorname*{{\mathbb{E}}}_{{\mathbf{x}}_{0}}\operatorname*{{\mathbb{E}}}_{{\mathbf{x}},{\mathbf{x}}^{\prime}}\left[\frac{({\mathbf{x}}^{\top}{\bm{\Psi}}^{\top}{\bm{\Phi}}{\mathbf{x}}^{\prime}){\bm{\Psi}}{\mathbf{x}}{\mathbf{x}}^{\top}{\bm{\Psi}}^{\top}}{\left\lVert{{\bm{\Phi}}{\mathbf{x}}^{\prime}}\right\rVert_{2}\left\lVert{{\bm{\Psi}}{\mathbf{x}}}\right\rVert_{2}^{3}}\right]$