TITLE: If $x$ is right-continuous with left limits, does $\{t>0:x(t)\ne\lim_{s\to t-}x(s)\}$ admit a minimum?
QUESTION [1 upvotes]: Let $E$ be a normed $\mathbb R$-vector space and $x:[0,\infty)\to E$ be càdlàg with $x(0)=0$. Moreover, let $x(0-):=x(0)$, $$x(t-):=\lim_{s\to t-}x(s)\;\;\;\text{for }t>0$$ and $$\Delta x(t):=x(t)-x(t-)\;\;\;\text{for }t\ge0.$$
Now let $\tau_0:=0$ and $$\tau_n:=\inf\underbrace{\{t>\tau_{n-1}:\Delta x(t)\ne0\}}_{=:\:I_n}\;\;\;\text{for }n\in\mathbb N.$$

Can we show that either $I_n=\emptyset$ or $\tau_n\in I_n$ for all $n\in\mathbb N$?

If $I_n=\emptyset$, then $\tau_n=\infty$. Assume $I_n\ne\emptyset$. Then there is a $t_n\in I_n$. Let $$J:=\{t\in(\tau_{n-1},t_n]:\Delta x(t)\ne0\}.$$ Clearly, $$\tau_n=\inf J\in[\tau_{n-1},t_n].$$ We know that $J$ is countable, but is that sufficient to conclude $\Delta x(\tau_n)\ne0$?

REPLY [1 votes]: Let $E = \mathbb{R}$ and define $x : [0, \infty) \to E$ as
$$x(t) = \begin{cases} 0 & t = 0 \\ \frac{1}{\left\lceil \frac{1}{t} \right\rceil} & t \neq 0 \end{cases}$$
Then $I_n = \left\{ \frac{1}{n} : n \in \mathbb{N} \right\}$ nad $\tau_n = 0$ for each $n$, so $\tau_n \notin I_n$.


TITLE: Improper Integral: $\int_{-\infty}^{\infty}\frac{\log(1+x^4)}{x^4}dx$
QUESTION [3 upvotes]: How can I prove this?

$$\int_{-\infty}^{\infty}\frac{\log(1+x^4)}{x^4}dx=\frac{2\sqrt{2}}{3}\pi$$

REPLY [2 votes]: You can use another way to do calculation. It is much easier. Let
$$ I(\alpha)=\int_{-\infty}^\infty\frac{\log(1+\alpha x^4)}{x^4}dx. $$
Then
$$ I'(\alpha)=\int_{-\infty}^\infty\frac{1}{1+\alpha x^4}dx=\frac{\pi}{\sqrt{2}\sqrt[4]{\alpha}}. $$
So
\begin{eqnarray*}
I(1)&=&\int_0^1\frac{\pi}{\sqrt{2}\sqrt[4]{\alpha}}d\alpha\\
&=&\frac{2\sqrt{2}\pi}{3}.
\end{eqnarray*}


TITLE: Where can I find the old papers of the Math Tripos?
QUESTION [35 upvotes]: Is there a repository on the Internet which has the old question papers of the tripos? I am specifically interested in the papers during the 1890-1910 era, which was the era before the reforms, although I'm also interested in the other, more recent papers.
Most of the problems which I have come across from the pre-reform era are very interesting, and it would be wonderful if the actual full papers are accessible now.
Thanks in advance!

REPLY [14 votes]: There are dozens of books which contain papers and solutions. The exam used to be called the senate-house examination a while ago, hence the titles. 'Tripos' is derived from the way the exam was taken, where you had to sit on a 3-legged wooden stool and "wrangle" - argue through problems orally - with the examiners. ('Riders' are just the first few parts of a problem, which are usually simple book-work questions in order to allow the weaker candidates to gain some points on the exam.)
To name a few:

Cambridge senate-house problems and riders, with solutions, 1875 - Greenhill
Cambridge senate-house problems and riders, with solutions, 1878 - Glaisher
Mathematical problems for Cambridge Mathematical Tripos - Wolstenholme
(I remember seeing a solutions manual to this somewhere, but it might be called something weird like "Key to..." instead of "Solutions to...".)
Cambridge senate-house problems and riders, 1848-1851 - Ferrers
Cambridge senate-house problems and riders, 1843-1851 - Jameson
Cambridge senate-house problems and riders, 1854 - Walton
Cambridge senate-house problems and riders, 1857 - Walton

You can easily discover more by searching "cambridge senate house" on archive.org. Other useful terms include: "cambridge problems and riders", "cambridge senate house solutions", "problems cambridge examinations", "cambridge examples", etc.


text:
\begin{document}
\title{A Note on the Global Convergence of Multilayer Neural Networks in
the Mean Field Regime}
\author{Huy Tuan Pham\thanks{Department of Mathematics, Stanford University.}$\quad$and
Phan-Minh Nguyen\thanks{Department of Electrical Engineering, Stanford University.}
\thanks{The author ordering is randomized.}}
\maketitle
\begin{abstract}
In a recent work, we introduced a rigorous framework to describe the
mean field limit of the gradient-based learning dynamics of multilayer
neural networks, based on the idea of a neuronal embedding. There
we also proved a global convergence guarantee for three-layer (as
well as two-layer) networks using this framework.

In this companion note, we point out that the insights in our previous
work can be readily extended to prove a global convergence guarantee
for multilayer networks of any depths. Unlike our previous three-layer
global convergence guarantee that assumes i.i.d. initializations,
our present result applies to a type of correlated initialization.
This initialization allows to, at any finite training time, propagate
a certain universal approximation property through the depth of the
neural network. To achieve this effect, we introduce a bidirectional
diversity condition.
\end{abstract}

\section{Introduction}

The mean field (MF) regime refers to a newly discovered scaling regime,
in which as the width tends to infinity, the behavior of an appropriately
scaled neural network under training converges to a well-defined and
nonlinear dynamical limit. The MF limit has been investigated for
two-layer networks \cite{mei2018mean,chizat2018,rotskoff2018neural,sirignano2018mean}
as well as multilayer setups \cite{nguyen2019mean,araujo2019mean,sirignano2019mean,nguyen2020rigorous}.

In a recent work \cite{nguyen2020rigorous}, we introduced a framework
to describe the MF limit of multilayer neural networks under training
and proved a connection between a large-width network and its MF limit.
Underlying this framework is the idea of a neuronal embedding that
encapsulates neural networks of arbitrary sizes. Using this framework,
we showed in \cite{nguyen2020rigorous} global convergence guarantees
for two-layer and three-layer neural networks. It is worth noting
that although these global convergence results were proven in the
context of independent and identically distributed (i.i.d.) initializations,
the framework is not restricted to initializations of this type. In
\cite{nguyen2020rigorous}, it was also proven that when there are
more than three layers, i.i.d. initializations (with zero initial
biases) can cause a certain strong simplifying effect, which we believe
to be undesirable in general. This clarifies a phenomenon that was
first discovered in \cite{araujo2019mean}.

The present note complements our previous work \cite{nguyen2020rigorous}.
Our main task here is to show that the approach in \cite{nguyen2020rigorous}
can be readily extended to prove a similar global convergence guarantee
for neural networks of any number of layers. We however do not assume
i.i.d. initializations. Our result applies to a type of correlated
initialization and the analysis crucially relies on the `neuronal
embedding' framework. As such, our result realizes the vision in \cite{nguyen2019mean}
of a MF limit that does not exhibit the aforementioned simplifying
effect. Furthermore our result cannot be established by the formulations
in \cite{araujo2019mean,sirignano2019mean} which are specific to
i.i.d. initializations.

Similar to the global convergence guarantees in \cite{nguyen2020rigorous}
and unlike other works, our result does not rely critically on convexity
and instead emphasizes on certain universal approximation properties
of neural networks. To be precise, the key is a diversity condition,
which is shown to hold at any finite training time. The insight on
diversity first appeared in the work \cite{chizat2018}: in the context
of two-layer networks, it refers to the full support condition of
the first layer's weight in the Euclidean space. Our previous work
\cite{nguyen2020rigorous} partially hinged on the same insight to
analyze three-layer networks. Here our present result defines a new
notion of diversity in the context of general multilayer networks.
Firstly, it is realized in function spaces that are naturally described
by the `neuronal embedding' framework. Secondly, it is bidirectional:
roughly speaking, for intermediate layers, diversity holds in both
the forward and backward passes. The effect of bidirectional diversity
is that a certain universal approximation property, at any finite
training time, is propagated from the first layer to the second last
one.

\paragraph*{Organization.}

We first describe the multilayer setup and the MF limit in Section
\ref{sec:setup} to make the note self-contained. Our main result
of global convergence (Theorem \ref{thm:global-optimum}) is presented
and proven in Section \ref{sec:global_conv}. This result is proven
for the MF limit. Lastly Section \ref{sec:connection} connects the
result to large-width multilayer networks.

Since the emphasis here is on the global convergence result, to keep
the note concise, other results are stated with proofs omitted, since
they can be found or established in a similar manner to \cite{nguyen2020rigorous}.

\paragraph*{Notations.}

We use $K$ to denote a generic constant that may change from line
to line. We use $\left|\cdot\right|$ to denote the absolute value
for a scalar, the Euclidean norm for a vector, and the respective
norm for an element of a Banach space. For an integer $n$, we let
$\left[n\right]=\left\{ 1,...,n\right\} $. We write ${\rm cl}\left(S\right)$
to denote the closure of a set $S$ in a topological space.

\section{Multilayer neural networks and the mean field limit\label{sec:setup}}

\subsection{Multilayer neural network\label{subsec:Three-layer-neural-network}}

We consider the following $L$-layer network:
\begin{align}
\hat{{\bf y}}\left(x;\mathbf{W}\left(k\right)\right) & =\varphi_{L}\left(\mathbf{H}_{L}\left(x,1;\mathbf{W}\left(k\right)\right)\right),\label{eq:three-layer-nn}\\
\mathbf{H}_{i}\left(x,j_{i};\mathbf{W}\left(k\right)\right) & =\frac{1}{n_{i-1}}\sum_{j_{i-1}=1}^{n_{i-1}}{\bf w}_{i}\left(k,j_{i-1},j_{i}\right)\varphi_{i-1}\left({\bf H}_{i-1}\left(x,j_{i-1};\mathbf{W}\left(k\right)\right)\right),\qquad i=L,...,2,\nonumber \\
{\bf H}_{1}\left(x,j_{1};\mathbf{W}\left(k\right)\right) & =\left\langle {\bf w}_{1}\left(k,j_{1}\right),x\right\rangle ,\nonumber
\end{align}
in which $x\in\mathbb{R}^{d}$ is the input, $\mathbf{W}\left(k\right)=\left\{ {\bf w}_{1}\left(k,\cdot\right),{\bf w}_{i}\left(k,\cdot,\cdot\right):\;i=2,...,L\right\} $
is the weight with ${\bf w}_{1}\left(k,j_{1}\right)\in\mathbb{R}^{d}$,
${\bf w}_{i}\left(k,j_{i-1},j_{i}\right)\in\mathbb{R}$, $\varphi_{i}:\;\mathbb{R}\to\mathbb{R}$
is the activation. Here the network has widths $\left\{ n_{i}\right\} _{i\leq L}$
with $n_{L}=1$, and $k\in\mathbb{N}_{\geq0}$ denotes the time, i.e.
we shall let the network evolve in (discrete) time.

We train the network with stochastic gradient descent (SGD) w.r.t.
the loss ${\cal L}:\;\mathbb{R}\times\mathbb{R}\to\mathbb{R}_{\geq0}$.
We assume that at each time $k$, we draw independently a fresh sample
$z\left(k\right)=\left(x\left(k\right),y\left(k\right)\right)\in\mathbb{R}^{d}\times\mathbb{R}$
from a training distribution ${\cal P}$. Given an initialization
$\mathbf{W}\left(0\right)$, we update $\mathbf{W}\left(k\right)$
according to
\begin{align*}
{\bf w}_{i}\left(k+1,j_{i-1},j_{i}\right) & ={\bf w}_{i}\left(k,j_{i-1},j_{i}\right)-\epsilon\ensuremath{\xi}_{i}\left(t\epsilon\right)\Delta_{i}^{\mathbf{w}}\left(z\left(k\right),j_{i-1},j_{i};\mathbf{W}\left(k\right)\right),\qquad i=2,...,L,\\
{\bf w}_{1}\left(k+1,j_{1}\right) & ={\bf w}_{1}\left(k,j_{1}\right)-\epsilon\ensuremath{\xi}_{1}\left(t\epsilon\right)\Delta_{1}^{\mathbf{w}}\left(z\left(k\right),j_{1};\mathbf{W}\left(k\right)\right),
\end{align*}
in which $j_{i}\in\left[n_{i}\right]$, $\epsilon\in\mathbb{R}_{>0}$
is the learning rate, $\xi_{i}:\;\mathbb{R}_{\geq0}\mapsto\mathbb{R}_{\geq0}$
is the learning rate schedule for $\mathbf{w}_{i}$, and for $z=\left(x,y\right)$,
we define
\begin{align*}
\Delta_{L}^{\mathbf{H}}\left(z,1;\mathbf{W}\left(k\right)\right) & =\partial_{2}{\cal L}\left(y,\hat{\mathbf{y}}\left(x;\mathbf{W}\left(k\right)\right)\right)\varphi_{L}'\left(\mathbf{H}_{L}\left(x,1;\mathbf{W}\left(k\right)\right)\right),\\
\Delta_{i-1}^{\mathbf{H}}\left(z,j_{i-1};\mathbf{W}\left(k\right)\right) & =\frac{1}{n_{i}}\sum_{j_{i}=1}^{n_{i}}\Delta_{i}^{\mathbf{H}}\left(z,j_{i};\mathbf{W}\left(k\right)\right){\bf w}_{i}\left(k,j_{i-1},j_{i}\right)\varphi_{i-1}'\left({\bf H}_{i-1}\left(x,j_{i-1};\mathbf{W}\left(k\right)\right)\right),\qquad i=L,...,2,\\
\Delta_{i}^{\mathbf{w}}\left(z,j_{i-1},j_{i};\mathbf{W}\left(k\right)\right) & =\Delta_{i}^{\mathbf{H}}\left(z,j_{i};\mathbf{W}\left(k\right)\right)\varphi_{i-1}\left({\bf H}_{i-1}\left(x,j_{i-1};\mathbf{W}\left(k\right)\right)\right),\qquad i=L,...,2,\\
\Delta_{1}^{\mathbf{w}}\left(z,j_{1};\mathbf{W}\left(k\right)\right) & =\Delta_{1}^{\mathbf{H}}\left(z,j_{1};\mathbf{W}\left(k\right)\right)x.
\end{align*}
In short, for an initialization $\mathbf{W}\left(0\right)$, we obtain
an SGD trajectory $\mathbf{W}\left(k\right)$ of an $L$-layer network
with size $\left\{ n_{i}\right\} _{i\leq L}$.

\subsection{Mean field limit\label{subsec:Mean-field-limit}}

The MF limit is a continuous-time infinite-width analog of the neural
network under training. We first recall from \cite{nguyen2020rigorous}
the concept of a neuronal ensemble. Given a product probability space
$\left(\Omega,P\right)=\prod_{i=1}^{L}\left(\Omega_{i},P_{i}\right)$
with $\Omega_{L}=\left\{ 1\right\} $, we independently sample $C_{i}\sim P_{i}$,
$i=1,...,L$. In the following, we use $\mathbb{E}_{C_{i}}$ to denote
the expectation w.r.t. the random variable $C_{i}\sim P_{i}$ and
$c_{i}$ to denote a dummy variable $c_{i}\in\Omega_{i}$. The space
$\left(\Omega,P\right)$ is called a neuronal ensemble.

Given a neuronal ensemble $\left(\Omega,P\right)$, the MF limit is
described by a time-evolving system with parameter $W\left(t\right)$,
where the time $t\in\mathbb{R}_{\geq0}$ and $W\left(t\right)=\left\{ w_{1}\left(t,\cdot\right),w_{i}\left(t,\cdot,\cdot\right):\;i=2,...,L\right\} $
with $w_{1}:\,\mathbb{R}_{\geq0}\times\Omega_{1}\to\mathbb{R}^{d}$
and $w_{i}:\,\mathbb{R}_{\geq0}\times\Omega_{i-1}\times\Omega_{i}\to\mathbb{R}$.
It entails the quantities:
\begin{align}
\hat{y}\left(x;W\left(t\right)\right) & =\varphi_{L}\left(H_{L}\left(x,1;W\left(t\right)\right)\right),\label{eq:three-layer-nn-1}\\
H_{i}\left(x,c_{i};W\left(t\right)\right) & =\mathbb{E}_{C_{i-1}}\left[w_{i}\left(t,C_{i-1},c_{i}\right)\varphi_{i-1}\left(H_{i-1}\left(x,C_{i-1};W\left(t\right)\right)\right)\right],\qquad i=L,...,2,\nonumber \\
H_{1}\left(x,c_{1};W\left(t\right)\right) & =\left\langle w_{1}\left(t,c_{1}\right),x\right\rangle .\nonumber
\end{align}
The MF limit evolves according to a continuous-time dynamics, described
by a system of ODEs, which we refer to as the MF ODEs. Specifically,
given an initialization $W\left(0\right)=\left\{ w_{1}\left(0,\cdot\right),w_{i}\left(0,\cdot,\cdot\right):\;i=2,...,L\right\} $,
the dynamics solves:
\begin{align*}
\frac{\partial}{\partial t}w_{i}\left(t,c_{i-1},c_{i}\right) & =-\xi_{i}\left(t\right)\mathbb{E}_{Z}\left[\Delta_{i}^{w}\left(Z,c_{i-1},c_{i};W\left(t\right)\right)\right],\qquad i=2,...,L,\\
\frac{\partial}{\partial t}w_{1}\left(t,c_{1}\right) & =-\xi_{1}\left(t\right)\mathbb{E}_{Z}\left[\Delta_{1}^{w}\left(Z,c_{1};W\left(t\right)\right)\right].
\end{align*}
Here $c_{i}\in\Omega_{i}$, $\mathbb{E}_{Z}$ denotes the expectation
w.r.t. the data $Z=\left(X,Y\right)\sim{\cal P}$, and for $z=\left(x,y\right)$,
we define
\begin{align*}
\Delta_{L}^{H}\left(z,1;W\left(t\right)\right) & =\partial_{2}{\cal L}\left(y,\hat{y}\left(x;W\left(t\right)\right)\right)\varphi_{L}'\left(H_{L}\left(x,1;W\left(t\right)\right)\right),\\
\Delta_{i-1}^{H}\left(z,c_{i-1};W\left(t\right)\right) & =\mathbb{E}_{C_{i}}\left[\Delta_{i}^{H}\left(z,C_{i};W\left(t\right)\right)w_{i}\left(t,c_{i-1},C_{i}\right)\varphi_{i-1}'\left(H_{i-1}\left(x,c_{i-1};W\left(t\right)\right)\right)\right],\qquad i=L,...,2,\\
\Delta_{i}^{w}\left(z,c_{i-1},c_{i};W\left(t\right)\right) & =\Delta_{i}^{H}\left(z,c_{i};W\left(t\right)\right)\varphi_{i-1}\left(H_{i-1}\left(x,c_{i-1};W\left(t\right)\right)\right),\qquad i=L,...,2,\\
\Delta_{1}^{w}\left(z,c_{1};W\left(t\right)\right) & =\Delta_{1}^{H}\left(z,c_{1};W\left(t\right)\right)x.
\end{align*}
In short, given a neuronal ensemble $\left(\Omega,P\right)$, for
each initialization $W\left(0\right)$, we have defined a MF limit
$W\left(t\right)$.

\section{Convergence to global optima\label{sec:global_conv}}

\subsection{Main result: global convergence}

To measure the learning quality, we consider the loss averaged over
the data $Z\sim{\cal P}$:
\[
\mathscr{L}\left(F\right)=\mathbb{E}_{Z}\left[{\cal L}\left(Y,\hat{y}\left(X;F\right)\right)\right],
\]
where $F=\left\{ f_{i}:\;i=1,...,L\right\} $ a set of measurable
functions $f_{1}:\;\Omega_{1}\to\mathbb{R}^{d}$, $f_{i}:\;\Omega_{i-1}\times\Omega_{i}\to\mathbb{R}$
for $i=2,...,L$.

We also recall the concept of a neuronal embedding from \cite{nguyen2020rigorous}.
Formally, in the present context, it is a tuple $\left(\Omega,P,\left\{ w_{i}^{0}\right\} _{i\leq L}\right)$,
comprising of a neuronal ensemble $\left(\Omega,P\right)$ and a set
of measurable functions $\left\{ w_{i}^{0}\right\} _{i\leq L}$ in
which $w_{1}^{0}:\;\Omega_{1}\to\mathbb{R}^{d}$ and $w_{i}^{0}:\;\Omega_{i-1}\times\Omega_{i}\to\mathbb{R}$
for $i=2,...,L$. The neuronal embedding connects a finite-width neural
network and its MF limit, via their initializations which are specified
by $\left\{ w_{i}^{0}\right\} _{i\leq L}$. We shall revisit this
connection later in Section \ref{sec:connection}. In the following,
we focus on the analysis of the MF limit.
\begin{assumption}
\label{assump:multilayer}Consider a neuronal embedding $\left(\Omega,P,\left\{ w_{i}^{0}\right\} _{i\leq L}\right)$,
recalling $\Omega=\prod_{i=1}^{L}\Omega_{i}$ and $P=\prod_{i=1}^{L}P_{i}$
with $\Omega_{L}=\left\{ 1\right\} $. Consider the MF limit associated
with the neuronal ensemble $\left(\Omega,P\right)$ with initialization
$W\left(0\right)$ such that $w_{1}\left(0,\cdot\right)=w_{1}^{0}\left(\cdot\right)$
and $w_{i}\left(0,\cdot,\cdot\right)=w_{i}^{0}\left(\cdot,\cdot\right)$.
We make the following assumptions:
\begin{enumerate}
\item Regularity: We assume that
\begin{itemize}
\item $\varphi_{i}$ is $K$-bounded for $1\leq i\leq L-1$, $\varphi_{i}'$
is $K$-bounded and $K$-Lipschitz for $1\leq i\leq L$, and $\varphi_{L}'$
is non-zero everywhere,
\item $\partial_{2}{\cal L}\left(\cdot,\cdot\right)$ is $K$-Lipschitz
in the second variable and $K$-bounded,
\item $\left|X\right|\leq K$ with probability $1$,
\item $\xi_{i}$ is $K$-bounded and $K$-Lipschitz for $1\leq i\leq L$,
\item $\sup_{k\geq1}k^{-1/2}\mathbb{E}\left[\left|w_{1}^{0}\left(C_{1}\right)\right|^{k}\right]^{1/k}\leq K$
and $\sup_{k\geq1}k^{-1/2}\mathbb{E}\left[\left|w_{i}^{0}\left(C_{i-1},C_{i}\right)\right|^{k}\right]^{1/k}\leq K$
for $i=2,...,L$.
\end{itemize}
\item Diversity: The functions $\left\{ w_{i}^{0}\right\} _{i\leq L}$ satisfy
that
\begin{itemize}
\item ${\rm supp}\left(w_{1}^{0}\left(C_{1}\right),w_{2}^{0}\left(C_{1},\cdot\right)\right)=\mathbb{R}^{d}\times L^{2}\left(P_{2}\right)$,
\item ${\rm supp}\left(w_{i}^{0}\left(\cdot,C_{i}\right),w_{i+1}^{0}\left(C_{i},\cdot\right)\right)=L^{2}\left(P_{i-1}\right)\times L^{2}\left(P_{i+1}\right)$
for $i=2,...,L-1$.
\end{itemize}
(Remark: we write $w_{i}^{0}\left(\cdot,C_{i}\right)$ to denote the
random mapping $c_{i-1}\mapsto w_{i}^{0}\left(c_{i-1},C_{i}\right)$,
and similar for $w_{i+1}^{0}\left(C_{i},\cdot\right)$.)
\item Convergence: There exist limits $\left\{ \bar{w}_{i}\right\} _{i\leq L}$
such that as $t\to\infty$,
\begin{align*}
\mathbb{E}\left[\left|w_{i}\left(t,C_{i-1},C_{i}\right)-\bar{w}_{i}\left(C_{i-1},C_{i}\right)\right|\sideset{}{_{j=i+1}^{L}}\prod\left|\bar{w}_{j}\left(C_{j-1},C_{j}\right)\right|\right] & \to0,\quad i=2,...,L,\\
\mathbb{E}\left[\left|w_{1}\left(t,C_{1}\right)-\bar{w}_{1}\left(C_{1}\right)\right|\sideset{}{_{j=2}^{L}}\prod\left|\bar{w}_{j}\left(C_{j-1},C_{j}\right)\right|\right] & \to0,\\
{\rm ess\text{-}sup}\left|\frac{\partial}{\partial t}w_{L}\left(t,C_{L-1},1\right)\right| & \to0.
\end{align*}
(Here we take $\prod_{j=i+1}^{L}=1$ for $i=L$.)
\item Universal approximation: The set $\left\{ \varphi_{1}\left(\left\langle u,\cdot\right\rangle \right):\;u\in\mathbb{R}^{d}\right\} $
has dense span in $L^{2}\left({\cal P}_{X}\right)$ (the space of
square integrable functions w.r.t. the measure ${\cal P}_{X}$, which
is the distribution of the input $X$). Furthermore, for each $i=2,...,L-1$,
$\varphi_{i}$ is non-obstructive in the sense that the set $\left\{ \varphi_{i}\circ f:\;f\in L^{2}\left({\cal P}_{X}\right)\right\} $
has dense span in $L^{2}\left({\cal P}_{X}\right)$.
\end{enumerate}
\end{assumption}

The first assumption can be satisfied for several common setups and
loss functions. The third assumption, similar to \cite{chizat2018,nguyen2020rigorous},
is technical and sets the focus on settings where the MF dynamics
converges with time, although we note it is an assumption on the mode
of convergence only and not on the limits $\left\{ \bar{w}_{i}\right\} _{i\leq L}$.
The fourth assumption is natural and can be satisfied by common activations.
For example, $\varphi_{i}$ can be $\tanh$ for $i=1,...,L-1$. In
general, for a bounded and continuous $\varphi_{i}$ to be non-obstructive,
it suffices that $\varphi_{i}$ is not a constant function. The second
assumption is new: it refers to an initialization scheme that introduces
correlation among the weights. In particular, i.i.d. initializations
do not satisfy this assumption for $L\geq3$.
\begin{thm}
\label{thm:existence}Given any neuronal ensemble $\left(\Omega,P\right)$
and a set of functions $\left\{ w_{i}^{0}\right\} _{i\leq L}$ such
that the regularity assumption listed in Assumption \ref{assump:multilayer}
is satisfied, and given an initialization $W\left(0\right)$ such
that $w_{1}\left(0,\cdot\right)=w_{1}^{0}\left(\cdot\right)$ and
$w_{i}\left(0,\cdot,\cdot\right)=w_{i}^{0}\left(\cdot,\cdot\right)$,
there exists a unique solution $W$ to the MF ODEs on $t\in[0,\infty)$.
\end{thm}

This theorem can be proven in a similar manner to \cite[Theorem 3]{nguyen2020rigorous},
so we will not show the complete proof here. The main focus is on
the global convergence result, which we state next.

\begin{thm}
\label{thm:global-optimum}Consider a neuronal embedding $\left(\Omega,P,\left\{ w_{i}^{0}\right\} _{i\leq L}\right)$
and the MF limit as in Assumption \ref{assump:multilayer}. Assume
$\xi_{L}\left(\cdot\right)=1$. Then:
\begin{itemize}
\item Case 1 (convex loss): If ${\cal L}$ is convex in the second variable,
then $\left\{ \bar{w}_{i}\right\} _{i\leq L}$ is a global minimizer
of $\mathscr{L}$:
\[
\mathscr{L}\left(\left\{ \bar{w}_{i}\right\} _{i\leq L}\right)=\inf_{F}\mathscr{L}\left(F\right)=\inf_{\tilde{y}:\;\mathbb{R}^{d}\to\mathbb{R}}\mathbb{E}_{Z}\left[{\cal L}\left(Y,\tilde{y}\left(X\right)\right)\right].
\]
\item Case 2 (generic non-negative loss): Suppose that $\partial_{2}{\cal L}\left(y,\hat{y}\right)=0$
implies ${\cal L}\left(y,\hat{y}\right)=0$. If $y=y(x)$ is a function
of $x$, then $\mathscr{L}\left(\left\{ \bar{w}_{i}\right\} _{i\leq L}\right)=0$.
\end{itemize}
\end{thm}

The assumptions here are similar to those made in \cite{nguyen2020rigorous}.
We remark on a special difference. In \cite{nguyen2020rigorous},
the diversity assumption refers to a full support condition of the
first layer's weight only. Here our diversity assumptions refers to
a certain full support condition for all layers. At a closer look,
the condition is in the function space and reflects certain \textsl{bidirectional
diversity}. In particular, this assumption implies both $w_{i}^{0}\left(\cdot,C_{i}\right)$
and $w_{i}^{0}\left(C_{i-1},\cdot\right)$ have full supports in $L^{2}\left(P_{i-1}\right)$
and $L^{2}\left(P_{i}\right)$ respectively (which we shall refer
to as \textit{forward diversity} and \textit{backward diversity},
respectively), for $2\leq i\leq L-1$.

The proof proceeds with several insights that have already appeared
in \cite{nguyen2020rigorous}. The novelty of our present analysis
lies in the use of the aforementioned bidirectional diversity. To
clarify the point, let us give a brief high-level idea of the proof.
At time $t$ sufficiently large, we expect to have:
\[
\left|\frac{\partial}{\partial t}w_{L}\left(t,c_{L-1},1\right)\right|=\left|\mathbb{E}_{Z}\left[\partial_{2}{\cal L}\left(Y,\hat{y}\left(X;W\left(t\right)\right)\right)\varphi_{L}'\left(H_{L}\left(X,1;W\left(t\right)\right)\right)\varphi_{L-1}\left(H_{L-1}\left(X,c_{L-1};W\left(t\right)\right)\right)\right]\right|\approx0
\]
for $P_{L-1}$-almost every $c_{L-1}$. If the set of mappings $x\mapsto H_{L-1}\left(x,c_{L-1};W\left(t\right)\right)$,
indexed by $c_{L-1}$, is diverse in the sense that ${\rm supp}\left(H_{L-1}\left(\cdot,C_{L-1};W\left(t\right)\right)\right)=L^{2}\left({\cal P}_{X}\right)$,
then since $\varphi_{L-1}$ is non-obstructive, we obtain
\[
\mathbb{E}_{Z}\left[\partial_{2}{\cal L}\left(Y,\hat{y}\left(X;W\left(t\right)\right)\right)\middle|X=x\right]\varphi_{L}'\left(H_{L}\left(x,1;W\left(t\right)\right)\right)\approx0
\]
and consequently
\[
\mathbb{E}_{Z}\left[\partial_{2}{\cal L}\left(Y,\hat{y}\left(X;W\left(t\right)\right)\right)\middle|X=x\right]\approx0
\]
for ${\cal P}_{X}$-almost every $x$. The desired conclusion then
follows.

Hence the crux of the proof is to show that ${\rm supp}\left(H_{L-1}\left(\cdot,C_{L-1};W\left(t\right)\right)\right)=L^{2}\left({\cal P}_{X}\right)$.
In fact, we show that this holds for any finite time $t\geq0$. This
follows if we can prove the forward diversity property of the weights,
in which $w_{i}\left(t,\cdot,C_{i}\right)$ has full support in $L^{2}\left(P_{i-1}\right)$
for any $t\geq0$ and $2\leq i\leq L-1$, and a similar property for
$w_{1}\left(t,C_{1}\right)$. Interestingly to that end, we actually
show that bidirectional diversity, and hence both forward diversity
and backward diversity, hold at any time $t\geq0$, even though we
only need forward diversity for our purpose.

\subsection{Proof of Theorem \ref{thm:global-optimum}}
\begin{proof}
We divide the proof into several steps.

\paragraph*{Step 1: Diversity of the weights.}

We show that ${\rm supp}\left(w_{1}\left(t,C_{1}\right)\right)=\mathbb{R}^{d}$
and ${\rm supp}\left(w_{i}\left(t,\cdot,C_{i}\right)\right)=L^{2}\left(P_{i-1}\right)$
for $i=2,...,L-1$, for any $t\geq0$. We do so by showing a stronger
statement, that the following bidirectional diversity condition holds
at any finite training time:
\begin{align*}
{\rm supp}\left(w_{1}\left(t,C_{1}\right),w_{2}\left(t,C_{1},\cdot\right)\right) & =\mathbb{R}^{d}\times L^{2}\left(P_{2}\right),\\
{\rm supp}\left(w_{i}\left(t,\cdot,C_{i}\right),w_{i+1}\left(t,C_{i},\cdot\right)\right) & =L^{2}\left(P_{i-1}\right)\times L^{2}\left(P_{i+1}\right),\qquad i=2,...,L-1,
\end{align*}
for any $t\geq0$.

We prove the first statement. Given a MF trajectory $\left(W\left(t\right)\right)_{t\ge0}$
and $u_{1}\in\mathbb{R}^{d}$, $u_{2}\in L^{2}\left(P_{2}\right)$,
we consider the following flow on $\mathbb{R}^{d}\times L^{2}\left(P_{2}\right)$:
\begin{align}
\frac{\partial}{\partial t}a_{2}^{+}\left(t,c_{2};u\right) & =-\xi_{2}(t)\mathbb{E}_{Z}\left[\Delta_{2}^{H}\left(Z,c_{2};W(t)\right)\varphi_{1}\left(\left\langle a_{1}^{+}\left(t;u\right),X\right\rangle \right)\right],\nonumber \\
\frac{\partial}{\partial t}a_{1}^{+}\left(t;u\right) & =-\xi_{1}(t)\mathbb{E}_{Z}\left[\mathbb{E}_{C_{2}}\left[\Delta_{2}^{H}\left(Z,C_{2};W(t)\right)a_{2}^{+}\left(t,C_{2};u\right)\right]\varphi_{1}'\left(\left\langle a_{1}^{+}\left(t;u\right),X\right\rangle \right)X\right],\label{eq:ODE-w}
\end{align}
for $u=\left(u_{1},u_{2}\right)$, with the initialization $a_{1}^{+}\left(0;u\right)=u_{1}$
and $a_{2}^{+}\left(0,c_{2};u\right)=u_{2}\left(c_{2}\right)$. Existence
and uniqueness of $\left(a_{1}^{+},a_{2}^{+}\right)$ follows similarly
to Theorem \ref{thm:existence}. We next prove for all finite $T>0$
and $u^{+}=\left(u_{1}^{+},u_{2}^{+}\right)\in\mathbb{R}^{d}\times L^{2}\left(P_{2}\right)$,
there exists $u^{-}=\left(u_{1}^{-},u_{2}^{-}\right)\in\mathbb{R}^{d}\times L^{2}\left(P_{2}\right)$
such that
\[
a_{1}^{+}\left(T;u^{-}\right)=u_{1}^{+},\qquad a_{2}^{+}\left(T,\cdot;u^{-}\right)=u_{2}^{+}.
\]
We consider the following auxiliary dynamics on $\mathbb{R}^{d}\times L^{2}\left(P_{2}\right)$:
\begin{align}
\frac{\partial}{\partial t}a_{2}^{-}\left(t,c_{2};u\right) & =\xi_{2}(T-t)\mathbb{E}_{Z}\left[\Delta_{2}^{H}\left(Z,c_{2};W(T-t)\right)\varphi_{1}\left(\left\langle a_{1}^{-}\left(t;u\right),X\right\rangle \right)\right],\nonumber \\
\frac{\partial}{\partial t}a_{1}^{-}\left(t;u\right) & =\xi_{1}(T-t)\mathbb{E}_{Z}\left[\mathbb{E}_{C_{2}}\left[\Delta_{2}^{H}\left(Z,C_{2};W(T-t)\right)a_{2}^{-}\left(t,C_{2};u\right)\right]\varphi_{1}'\left(\left\langle a_{1}^{-}\left(t;u\right),X\right\rangle \right)X\right],\label{eq:ODE-a}
\end{align}
initialized at $a_{1}^{-}\left(0;u\right)=u_{1}$ and $a_{2}^{-}\left(0,c_{2};u\right)=u_{2}\left(c_{2}\right)$,
for $u=\left(u_{1},u_{2}\right)\in\mathbb{R}^{d}\times L^{2}\left(P_{2}\right)$.
Existence and uniqueness of $(a_{1}^{-},a_{2}^{-})$ follow similarly
to Theorem \ref{thm:existence}. Observe that the pair
\[
\tilde{a}_{1}^{-}\left(t\right)=a_{1}^{-}\left(T-t;u^{+}\right),\qquad\tilde{a}_{2}^{-}\left(t,c_{2}\right)=a_{2}^{-}\left(T-t,c_{2};u^{+}\right)
\]
solves the system
\begin{align*}
\frac{\partial}{\partial t}\tilde{a}_{2}^{-}\left(t,c_{2}\right) & =-\frac{\partial}{\partial t}a_{2}^{-}\left(T-t,c_{2};u^{+}\right)=-\xi_{2}(t)\mathbb{E}_{Z}\left[\Delta_{2}^{H}\left(Z,c_{2};W(t)\right)\varphi_{1}\left(\left\langle \tilde{a}_{1}^{-}\left(t\right),X\right\rangle \right)\right],\\
\frac{\partial}{\partial t}\tilde{a}_{1}^{-}\left(t\right) & =-\frac{\partial}{\partial t}a_{1}^{-}\left(T-t;u^{+}\right)=-\xi_{1}(t)\mathbb{E}_{Z}\left[\mathbb{E}_{C_{2}}\left[\Delta_{2}^{H}\left(Z,C_{2};W(t)\right)\tilde{a}_{2}^{-}\left(t,C_{2}\right)\right]\varphi_{1}'\left(\left\langle \tilde{a}_{1}^{-}\left(t\right),X\right\rangle \right)X\right],
\end{align*}
initialized at $\tilde{a}_{2}^{-}\left(0,c_{2}\right)=a_{2}^{-}\left(T,c_{2};u^{+}\right)$
and $\tilde{a}_{1}^{-}(0)=a_{1}^{-}\left(T;u^{+}\right)$. Thus, by
uniqueness of the solution to the ODE (\ref{eq:ODE-w}), $(\tilde{a}_{1}^{-},\tilde{a}_{2}^{-})$
forms a solution of the ODE (\ref{eq:ODE-w}) initialized at
\[
\tilde{a}_{1}^{-}(0)=a_{1}^{-}\left(T;u^{+}\right),\qquad\tilde{a}_{2}^{-}\left(0,c_{2}\right)=a_{2}^{-}\left(T,c_{2};u^{+}\right).
\]
In particular, the solution $(\tilde{a}_{1}^{-},\tilde{a}_{2}^{-})$
of the ODE (\ref{eq:ODE-w}) with this initialization satisfies
\[
\tilde{a}_{1}^{-}\left(T\right)=a_{1}^{-}\left(0;u^{+}\right)=u_{1}^{+},\qquad\tilde{a}_{2}^{-}\left(T,\cdot\right)=a_{2}^{-}\left(0,\cdot;u^{+}\right)=u_{2}^{+}.
\]
Let $u_{1}^{-}=a_{1}^{-}\left(T;u^{+}\right)$ and $u_{2}^{-}=a_{2}^{-}\left(T,\cdot;u^{+}\right)$.
Then we have $a_{1}^{+}\left(T;u^{-}\right)=u_{1}^{+}$ and $a_{2}^{+}\left(T,\cdot;u^{-}\right)=u_{2}^{+}$
as desired.

Using this, by continuity of the map $u\mapsto\left(a_{1}^{+}\left(T;u\right),a_{2}^{+}\left(T,\cdot;u\right)\right)$,
for every $\epsilon>0$, there exists a neighborhood $U$ of $u^{-}$
such that for any $u\in U$, $\left|\left(a_{1}^{+}\left(T;u\right),a_{2}^{+}\left(T,\cdot;u\right)\right)-u^{+}\right|\le\epsilon$.
Notice that the MF trajectory $W\left(t\right)$ satisfies
\[
w_{1}\left(t,c_{1}\right)=a_{1}^{+}\left(t;w_{1}\left(0,c_{1}\right),w_{2}\left(0,c_{1},\cdot\right)\right),\qquad w_{2}\left(t,c_{1},\cdot\right)=a_{2}^{+}\left(t,\cdot;w_{1}\left(0,c_{1}\right),w_{2}\left(0,c_{1},\cdot\right)\right).
\]
Then since $\left(w_{1}\left(0,C_{1}\right),w_{2}\left(0,C_{1},\cdot\right)\right)$
has full support in $\mathbb{R}^{d}\times L^{2}\left(P_{2}\right)$,
for any finite $T>0$, we have $\left(w_{1}\left(T,C_{1}\right),w_{2}\left(T,C_{1},\cdot\right)\right)$
has full support in $\mathbb{R}^{d}\times L^{2}\left(P_{2}\right)$,
proving the first statement.

The other statements can be proven similarly by considering the following
pairs of flows on $L^{2}(P_{i-1})\times L^{2}(P_{i+1})$, for $u=\left(u_{1},u_{2}\right)\in L^{2}(P_{i-1})\times L^{2}(P_{i+1})$:
\begin{align*}
\frac{\partial}{\partial t}a_{i}^{+}\left(t,c_{i-1};u\right) & =-\xi_{i}\left(t\right)\mathbb{E}_{Z}\left[\Delta_{i}^{a}\left(Z,a_{i}^{+}\left(t,\cdot;u\right),a_{i+1}^{+}\left(t,\cdot;u\right);W\left(t\right)\right)\varphi_{i-1}\left(H_{i-1}\left(X,c_{i-1};W\left(t\right)\right)\right)\right],\\
\frac{\partial}{\partial t}a_{i+1}^{+}\left(t,c_{i+1};u\right) & =-\xi_{i+1}\left(t\right)\mathbb{E}_{Z}\left[\Delta_{i+1}^{H}\left(Z,c_{i+1};W\left(t\right)\right)\varphi_{i}\left(H_{i}^{a}\left(Z,a_{i}^{+}\left(t,\cdot;u\right);W\left(t\right)\right)\right)\right],
\end{align*}
initialized at $a_{i}^{+}\left(0,c_{i-1};u\right)=u_{1}\left(c_{i-1}\right)$
and $a_{i+1}^{+}\left(0,c_{i+1};u\right)=u_{2}\left(c_{i+1}\right)$,
and
\begin{align*}
\frac{\partial}{\partial t}a_{i}^{-}\left(t,c_{i-1};u\right) & =\xi_{i}\left(T-t\right)\mathbb{E}_{Z}\left[\Delta_{i}^{a}\left(Z,a_{i}^{-}\left(t,\cdot;u\right),a_{i+1}^{-}\left(t,\cdot;u\right);W\left(T-t\right)\right)\varphi_{i-1}\left(H_{i-1}\left(X,c_{i-1};W\left(T-t\right)\right)\right)\right],\\
\frac{\partial}{\partial t}a_{i+1}^{-}\left(t,c_{i+1};u\right) & =\xi_{i+1}\left(T-t\right)\mathbb{E}_{Z}\left[\Delta_{i+1}^{H}\left(Z,c_{i+1};W(T-t)\right)\varphi_{i}\left(H_{i}^{a}\left(Z,a_{i}^{-}\left(t,\cdot;u\right);W\left(T-t\right)\right)\right)\right],
\end{align*}
initialized at $a_{i}^{-}\left(0,c_{i-1};u\right)=u_{1}\left(c_{i-1}\right)$
and $a_{i+1}^{-}\left(0,c_{i+1};u\right)=u_{2}\left(c_{i+1}\right)$,
in which we define:
\begin{align*}
\Delta_{i}^{a}\left(z,f,g;W\left(t\right)\right) & =\mathbb{E}_{C_{i+1}}\left[\Delta_{i+1}^{H}\left(z,C_{i+1};W\left(t\right)\right)g\left(C_{i+1}\right)\varphi_{i}'\left(H_{i}^{a}\left(z,f;W\left(t\right)\right)\right)\right],\\
H_{i}^{a}\left(z,f;W\left(t\right)\right) & =\mathbb{E}_{C_{i-1}}\left[f\left(C_{i-1}\right)\varphi_{i-1}\left(H_{i-1}\left(x,C_{i-1};W\left(t\right)\right)\right)\right],
\end{align*}
for $f\in L^{2}\left(P_{i-1}\right)$ and $g\in L^{2}\left(P_{i+1}\right)$.

\paragraph*{Step 2: Diversity of the pre-activations.}

We show that ${\rm supp}\left(H_{i}\left(\cdot,C_{i};W\left(t\right)\right)\right)=L^{2}\left({\cal P}_{X}\right)$
for any $t\geq0$, for $i=2,...,L-1$ by induction.

Firstly consider the base case $i=2$. Recall that
\[
H_{2}\left(x,c_{2};W\left(t\right)\right)=\mathbb{E}_{C_{1}}\left[w_{2}\left(t,C_{1},c_{2}\right)\varphi_{1}\left(\left\langle w_{1}\left(t,C_{1}\right),x\right\rangle \right)\right]\equiv{\cal H}_{2}\left(t,x,w_{2}\left(t,\cdot,c_{2}\right)\right).
\]
Observe that the set ${\rm cl}\left(\left\{ {\cal H}_{2}\left(t,\cdot,f\right):\;f\in L^{2}\left(P_{1}\right)\right\} \right)$
is a closed linear subspace of $L^{2}\left({\cal P}_{X}\right)$.
Hence this set is equal to $L^{2}\left({\cal P}_{X}\right)$ if it
has dense span in $L^{2}\left({\cal P}_{X}\right)$, which we show
now. Indeed, suppose that for some $g\in L^{2}\left({\cal P}_{X}\right)$
such that $\left|g\right|\neq0$, we have $\mathbb{E}_{Z}\left[g\left(X\right){\cal H}_{2}\left(t,X,f\right)\right]=0$
for all $f\in L^{2}\left(P_{1}\right)$. Equivalently,
\[
\mathbb{E}_{C_{1}}\left[f\left(C_{1}\right)\mathbb{E}_{Z}\left[g\left(X\right)\varphi_{1}\left(\left\langle w_{1}\left(t,C_{1}\right),X\right\rangle \right)\right]\right]=0,
\]
for all $f\in L^{2}\left(P_{1}\right)$. As such, for $P_{1}$-almost
every $c_{1}$,
\[
\mathbb{E}_{Z}\left[g\left(X\right)\varphi_{1}\left(\left\langle w_{1}\left(t,c_{1}\right),X\right\rangle \right)\right]=0.
\]
Since ${\rm supp}\left(w_{1}\left(t,C_{1}\right)\right)=\mathbb{R}^{d}$
and that the mapping $u\mapsto\varphi_{1}\left(\left\langle u,x\right\rangle \right)$
is continuous, by the universal approximation assumption for $\varphi_{1}$,
we then obtain $g(x)=0$ for $P_{X}$-almost every $x$, which is
a contradiction. We have thus proved that ${\rm cl}\left(\left\{ {\cal H}_{2}\left(t,\cdot,f\right):\;f\in L^{2}\left(P_{1}\right)\right\} \right)=L^{2}\left({\cal P}_{X}\right)$.
Note that $f\mapsto{\cal H}_{2}\left(t,x,f\right)$ is continuous,
and ${\rm supp}\left(w_{2}\left(t,\cdot,C_{2}\right)\right)=L^{2}\left(P_{1}\right)$,
we then have ${\rm supp}\left(H_{2}\left(\cdot,C_{2};W\left(t\right)\right)\right)=L^{2}\left({\cal P}_{X}\right)$
as desired.

Now let us assume that ${\rm supp}\left(H_{i-1}\left(\cdot,C_{i-1};W\left(t\right)\right)\right)=L^{2}\left({\cal P}_{X}\right)$
for some $i\geq3$ (the induction hypothesis). We would like to show
${\rm supp}\left(H_{i}\left(\cdot,C_{i};W\left(t\right)\right)\right)=L^{2}\left({\cal P}_{X}\right)$.
This is similar to the base case. In particular, recall that
\[
H_{i}\left(x,c_{i};W\left(t\right)\right)=\mathbb{E}_{C_{i-1}}\left[w_{i}\left(t,C_{i-1},c_{i}\right)\varphi_{i-1}\left(H_{i-1}\left(x,C_{i-1};W\left(t\right)\right)\right)\right]\equiv{\cal H}_{i}\left(t,x,w_{i}\left(t,\cdot,c_{i}\right)\right).
\]
Now suppose that for some $g\in L^{2}\left({\cal P}_{X}\right)$ such
that $\left|g\right|\neq0$, we have $\mathbb{E}_{Z}\left[g\left(X\right){\cal H}_{i}\left(t,X,f\right)\right]=0$
for all $f\in L^{2}\left(P_{i-1}\right)$. Then, for $P_{i-1}$-almost
every $c_{i-1}$,
\[
\mathbb{E}_{Z}\left[g\left(X\right)\varphi_{i-1}\left(H_{i-1}\left(X,c_{i-1};W\left(t\right)\right)\right)\right]=0.
\]
Recall the induction hypothesis ${\rm supp}\left(H_{i-1}\left(\cdot,C_{i-1};W\left(t\right)\right)\right)=L^{2}\left({\cal P}_{X}\right)$.
Since $\varphi_{i-1}$ is non-obstructive and continuous, we obtain
$g(x)=0$ for $P_{X}$-almost every $x$, which is a contradiction.
Therefore the set ${\rm cl}\left(\left\{ {\cal H}_{i}\left(t,\cdot,f\right):\;f\in L^{2}\left(P_{i-1}\right)\right\} \right)$
has dense span in $L^{2}\left({\cal P}_{X}\right)$, and again, this
implies it is equal to $L^{2}\left({\cal P}_{X}\right)$. Since $f\mapsto{\cal H}_{i}\left(t,x,f\right)$
is continuous and ${\rm supp}\left(w_{i}\left(t,\cdot,C_{i}\right)\right)=L^{2}\left(P_{i-1}\right)$,
we have ${\rm supp}\left(H_{i}\left(\cdot,C_{i};W\left(t\right)\right)\right)=L^{2}\left({\cal P}_{X}\right)$.

\paragraph*{Step 3: Concluding.}

Let $\mathbb{E}_{Z}\left[\partial_{2}{\cal L}\left(Y,\hat{y}\left(X;W\left(t\right)\right)\right)\middle|X=x\right]\varphi_{L}'\left(H_{L}\left(x,1;W\left(t\right)\right)\right)={\cal H}\left(x,W\left(t\right)\right)$.
From the last step, we have ${\rm supp}\left(H_{L-1}\left(\cdot,C_{L-1};W\left(t\right)\right)\right)=L^{2}\left({\cal P}_{X}\right)$
for any $t\geq0$. Recall that
\[
\frac{\partial}{\partial t}w_{L}\left(t,c_{L-1},1\right)=-\mathbb{E}_{Z}\left[{\cal H}\left(X,W\left(t\right)\right)\varphi_{L-1}\left(H_{L-1}\left(X,c_{L-1};W\left(t\right)\right)\right)\right].
\]
By the convergence assumption, for any $\epsilon>0$, there exists
$T\left(\epsilon\right)>0$ such that for any $t\geq T\left(\epsilon\right)$,
for $P_{L-1}$-almost every $c_{L-1}$,
\[
\left|\mathbb{E}_{Z}\left[{\cal H}\left(X,W\left(t\right)\right)\varphi_{L-1}\left(H_{L-1}\left(X,c_{L-1};W\left(t\right)\right)\right)\right]\right|\leq\epsilon.
\]
We claim that ${\cal H}\left(x,W\left(t\right)\right)\to{\cal H}\left(x,\left\{ \bar{w}_{i}\right\} _{i\leq L}\right)$
in $L^{1}\left({\cal P}_{X}\right)$ as $t\to\infty$. Assuming this
claim and recalling that $\varphi_{L-1}$ is $K$-bounded by the regularity
assumption, we then have that for some $T'\left(\epsilon\right)\geq T\left(\epsilon\right)$,
for any $t\geq T'\left(\epsilon\right)$,
\begin{align*}
 & {\rm ess\text{-}sup}\left|\mathbb{E}_{Z}\left[{\cal H}\left(X,\left\{ \bar{w}_{i}\right\} _{i\leq L}\right)\varphi_{L-1}\left(H_{L-1}\left(X,C_{L-1};W\left(t\right)\right)\right)\right]\right|\\
 & \leq K\mathbb{E}_{Z}\left[\left|{\cal H}\left(X,\left\{ \bar{w}_{i}\right\} _{i\leq L}\right)-{\cal H}\left(X,W\left(t\right)\right)\right|\right]+{\rm ess\text{-}sup}\left|\mathbb{E}_{Z}\left[{\cal H}\left(X,W\left(t\right)\right)\varphi_{L-1}\left(H_{L-1}\left(X,C_{L-1};W\left(t\right)\right)\right)\right]\right|\\
 & \leq K\epsilon.
\end{align*}
Since ${\rm supp}\left(H_{L-1}\left(\cdot,C_{L-1};W\left(t\right)\right)\right)=L^{2}\left({\cal P}_{X}\right)$
and $\varphi_{L-1}$ is continuous,
\[
\left|\mathbb{E}_{Z}\left[{\cal H}\left(X,\left\{ \bar{w}_{i}\right\} _{i\leq L}\right)f\left(X\right)\right]\right|\leq K\epsilon\qquad\forall f\in S,
\]
for $S=\left\{ \varphi_{L-1}\circ g:\;g\in L^{2}\left({\cal P}_{X}\right)\right\} $.
Since $\epsilon>0$ is arbitrary,
\[
\left|\mathbb{E}_{Z}\left[{\cal H}\left(X,\left\{ \bar{w}_{i}\right\} _{i\leq L}\right)f\left(X\right)\right]\right|=0\qquad\forall f\in S.
\]
Furthermore, since $\varphi_{L-1}$ is non-obstructive, $S$ has dense
span in $L^{2}\left({\cal P}_{X}\right)$. Therefore ${\cal H}\left(x,\left\{ \bar{w}_{i}\right\} _{i\leq L}\right)=0$
for ${\cal P}_{X}$-almost every $x$. Since $\varphi_{L}'$ is non-zero
everywhere,
\[
\mathbb{E}_{Z}\left[\partial_{2}{\cal L}\left(Y,\hat{y}\left(X;\left\{ \bar{w}_{i}\right\} _{i\leq L}\right)\right)\middle|X=x\right]=0
\]
 for ${\cal P}_{X}$-almost every $x$.

In Case 1, due to convexity of ${\cal L}$, for any measurable function
$\tilde{y}$:
\[
{\cal L}\left(y,\tilde{y}\left(x\right)\right)-{\cal L}\left(y,\hat{y}\left(x;\left\{ \bar{w}_{i}\right\} _{i\leq L}\right)\right)\geq\partial_{2}{\cal L}\left(y,\hat{y}\left(x,\left\{ \bar{w}_{i}\right\} _{i\leq L}\right)\right)\left(\tilde{y}\left(x\right)-\hat{y}\left(x,\left\{ \bar{w}_{i}\right\} _{i\leq L}\right)\right).
\]
Taking expectation, we get $\mathbb{E}_{Z}\left[{\cal L}\left(Y,\tilde{y}\left(X\right)\right)\right]\geq\mathscr{L}\left(\left\{ \bar{w}_{i}\right\} _{i\leq L}\right)$.

In Case 2, we have $\partial_{2}{\cal L}\left(y\left(x\right),\hat{y}\left(x;\left\{ \bar{w}_{i}\right\} _{i\leq L}\right)\right)=0$,
and hence ${\cal L}\left(y\left(x\right),\hat{y}\left(x;\left\{ \bar{w}_{i}\right\} _{i\leq L}\right)\right)=0$,
for ${\cal P}_{X}$-almost every $x$, since $y$ is a function of
$x$.

We are left with proving the claim that ${\cal H}(x,W(t))\to{\cal H}\left(x,\{\bar{w}_{i}\}_{i\le L}\right)$
in $L^{1}({\cal P}_{X})$ as $t\to\infty$. For brevity, we denote
\[
\delta_{i}\left(t,x,c_{i}\right)=\left|H_{i}\left(x,c_{i};W\left(t\right)\right)-H_{i}\left(x,c_{i};\left\{ \bar{w}_{i}\right\} _{i\leq L}\right)\right|.
\]
First observe that by the regularity assumption, for $2\leq i\leq L$:
\begin{align*}
\delta_{i}\left(t,x,c_{i}\right) & \leq K\mathbb{E}_{C_{i-1}}\left[\left|w_{i}\left(t,C_{i-1},c_{i}\right)-\bar{w}_{i}\left(C_{i-1},c_{i}\right)\right|+\left|\bar{w}_{i}\left(C_{i-1},c_{i}\right)\right|\delta_{i-1}\left(t,x,C_{i-1}\right)\right],\\
\delta_{1}\left(t,x,c_{1}\right) & \leq K\left|w_{1}\left(t,c_{1}\right)-\bar{w}_{1}\left(c_{1}\right)\right|.
\end{align*}
This thus gives:
\begin{align*}
 & \mathbb{E}_{Z}\left[\left|{\cal H}\left(X,W\left(t\right)\right)-{\cal H}\left(X,\left\{ \bar{w}_{i}\right\} _{i\leq L}\right)\right|\right]\\
 & \leq K\mathbb{E}_{Z}\left[\delta_{L}\left(t,X,1\right)\right]\\
 & \leq K^{L}\sum_{i=2}^{L}\mathbb{E}\left[\left|w_{i}\left(t,C_{i-1},C_{i}\right)-\bar{w}_{i}\left(C_{i-1},C_{i}\right)\right|\sideset{}{_{j=i+1}^{L}}\prod\left|\bar{w}_{j}\left(C_{j-1},C_{j}\right)\right|\right]\\
 & \quad+K^{L}\mathbb{E}\left[\left|w_{1}\left(t,C_{1}\right)-\bar{w}_{1}\left(C_{1}\right)\right|\sideset{}{_{j=2}^{L}}\prod\left|\bar{w}_{j}\left(C_{j-1},C_{j}\right)\right|\right].
\end{align*}
By the convergence assumption, the right-hand side tends to $0$ as
$t\to\infty$. This proves the claim and concludes the proof.
\end{proof}

\section{Connection to large-width neural networks\label{sec:connection}}

Theorem \ref{thm:global-optimum} concerns with the global convergence
of the MF limit. To make the connection with a finite-width neural
network, we recall the neuronal embedding $\left(\Omega,P,\left\{ w_{i}^{0}\right\} _{i\leq L}\right)$,
as well as the following coupling procedure in \cite{nguyen2020rigorous}:
\begin{enumerate}
\item We form the MF limit $W\left(t\right)$ (for $t\in\mathbb{R}_{\geq0}$)
associated with the neuronal ensemble $\left(\Omega,P\right)$ by
setting the initialization $W\left(0\right)$ to $w_{1}\left(0,\cdot\right)=w_{1}^{0}\left(\cdot\right)$,
$w_{i}\left(0,\cdot,\cdot\right)=w_{i}^{0}\left(\cdot,\cdot\right)$
and running the MF ODEs described in Section \ref{subsec:Mean-field-limit}.
\item We independently sample $C_{i}\left(j_{i}\right)\sim P_{i}$ for $i=1,...,L$
and $j_{i}=1,...,n_{i}$. We then form the neural network initialization
$\mathbf{W}\left(0\right)$ with $\mathbf{w}_{1}\left(0,j_{1}\right)=w_{1}^{0}\left(C_{1}\left(j_{1}\right)\right)$
and $\mathbf{w}_{i}\left(0,j_{i-1},j_{i}\right)=w_{i}^{0}\left(C_{i-1}\left(j_{i-1}\right),C_{i}\left(j_{i}\right)\right)$
for $j_{i}\in\left[n_{i}\right]$. We obtain the network's trajectory
$\mathbf{W}\left(k\right)$ for $k\in\mathbb{N}_{\geq0}$ as in Section
\ref{subsec:Three-layer-neural-network}, with the data $z\left(k\right)$
generated independently of $\left\{ C_{i}\left(j_{i}\right)\right\} _{i\leq L}$
and hence $\mathbf{W}\left(0\right)$.
\end{enumerate}
Here in our present context, the neuronal embedding forms the basis
on which the finite-width neural network is realized. Furthermore
the neural network and its MF limit are coupled. One can establish
a result on their connection, showing that the coupled trajectories
are close to each other with high probability, similar to \cite[Theorem 10]{nguyen2020rigorous}.
Together with Theorem \ref{thm:global-optimum}, one can obtain the
following result on the optimization efficiency of the neural network
with SGD:
\begin{cor}
\label{cor:global-optimum-NN}Consider the neural network (\ref{eq:three-layer-nn})
as described by the coupling procedure. Under the same setting as
Theorem \ref{thm:global-optimum}, in Case 1,
\[
\lim_{t\to\infty}\lim_{\left\{ n_{i}\right\} _{i\leq L}}\lim_{\epsilon\to0}\mathbb{E}_{Z}\left[{\cal L}\left(Y,\hat{{\bf y}}\left(X;\mathbf{W}\left(\left\lfloor t/\epsilon\right\rfloor \right)\right)\right)\right]=\inf_{F}\mathscr{L}\left(F\right)=\inf_{\tilde{y}}\mathbb{E}_{Z}\left[{\cal L}\left(Y,\tilde{y}\left(X\right)\right)\right]
\]
in probability, where the limit of the widths is such that $\left(\min\left\{ n_{i}\right\} _{i\leq L-1}\right)^{-1}\log\left(\max\left\{ n_{i}\right\} _{i\leq L}\right)\to0$.
In Case 2, the same holds with the right-hand side being $0$.
\end{cor}

\bibliographystyle{amsalpha}
\bibliography{NN_companion}

\end{document}

config: arxiv


TITLE: Find all solutions to $x^2$ ≡ 1(mod 8)
QUESTION [0 upvotes]: Find all solutions to $x^2$ ≡ 1 in arithmetic modulo 8.
My understanding is that what this is saying is that find the x which multiplicative inverse is equal to itself within modulo 8.
I know that this is the case for certain examples like in modulo 18: the multiplicative inverse of 17 is also 17. But I am not quite sure why.
Any explanation and help with a technique to solve would be appreciated.

REPLY [1 votes]: Well there's always trial an error and the will give you insight.
$1^2 \equiv 1 \mod 8$.
$2^2 \equiv 4; 3^3 \equiv 1 \mod 8; 4^2 \equiv 0 \mod 8; 5^2\equiv 1 \mod 8; 6^2\equiv 4\mod 8; 7^2 \equiv 1\mod 8; 0^2 \equiv 0 \mod 8$
So the answer is $1, 3,5,7$ which seems to be the odd numbers but why would this be?
Well, you can always you the quadratic formula.
$x^2 \equiv 1 \mod 8$
$x^2 - 1 \equiv 0 \mod 8$
$x^2 - 1 -8k = 0$ for some integer $k$
$x = \frac {\pm \sqrt{4(1+8k)}}2 =  \pm \sqrt{1+8k}$
If $k = 0$ then $x = \pm1$ and if $k=1$ and if $k = 1$ then $x =\pm 3$. so that gives us $1,3,5,7$.
But that's still not satisfying because it is still trial and error and who knows if there is any $k> 1$ where $1 +8k$ is a perfect square.
But $x^2 \equiv 1 \mod 8$ means $x^2 -1 = (x-1)(x+1) \equiv 0 \mod 8$. so this is a matter of finding the factors of $0$ and adding and subtracting $1$ from them.
Obiviously lettting one of $x+1; x-1$ being equiv $0$ will yield a solution:  $x\pm 1 \equiv 0\mod 8$ so $x\equiv \mp 1 \mod 8$ will be options so that accounts for $1, 7$.
The non-zero factors are: $m,8k;$ and $2j;4m$.
Or in other words:  $(0,x),(1,0), (2,4),(4,4),(6,4)$.
If $x \pm 1 \equiv 0$ then $x = 1, 7$
If $x\pm 1\equiv 1 \mod 8$ while $x \mp 1 \equiv 0 \mod 8$ means $x\equiv 0,2$ while $x \equiv 1,7$ which is impossible.
If $x \pm 1 \equiv 2$ while $x \mp 1 \equiv 4$ means $x\equiv 1,3$ while $x \equiv 5,3$ so $x = 3$.
$x +1 \equiv 4 \equiv x-1$ is impossible.
And if $x\pm 1\equiv 6\implies x\equiv 5,7$ and $x\mp \equiv 4 \implies x \equiv 5,3$ so $x = 3$.
Hence $x = 1,3,5,7$ and we hopefully have a hint why the odd numbers were the answers (because the factors of $0\mod 8$ are $2,4$ and are equiv to $x\pm 1$) and how to solve in genernal.  (Factor and find the divisors of $0$ and set equal to the factors).


TITLE: Creating a Rotating Partner, Round Robin Schedule
QUESTION [1 upvotes]: First, I'm going to apologize for a lack of proper terminology on this post.  It's been well over a decade since my days in the classroom, so I've regressed back to a simple math layman here.  (As a result, please add any missing/correct any inaccurate tags as needed)
The problem in a nutshell is to come up with a "perfect" rotating-partner/round-robin schedule that will allow for every person to partner with every other participant in the tournament once and play against every other participant in the tournament twice.  The current bounds of the problem are that the number of players in the tournament (n) must be divisible by 4, and the total number of rounds played will be equal to n-1.
Take for example 4 players: the perfect schedule could be represented as follows:
$$\begin{array}{|c|c|c|c|c|c|} \hline
    & T^1 (P^1) & T^1 (P^2) & vs & T^2 (P^1) & T^2 (P^2)\\  \hline
    Round\ 1 & A & B & & C & D\\ \hline
    Round\ 2 & A & C & & B & D\\ \hline
    Round\ 3 & A & D & & C & B\\ \hline
\end{array}$$
Note: $T^1(P^1)$ indicates Team 1 (Player 1)
This solution shows that all players partner with every other player once and play against them twice.
Upon using the brute-force method of identifying the next step, I've also been able to identify what the perfect schedule looks like for 8 players, as follows:
$$\begin{array}{|c|c|c|c|c|c|c|c|c|c|c|} \hline
    & T^1 (P^1) & T^1 (P^2) & v & T^2 (P^1) & T^2 (P^2) & & T^3 (P^1) & T^3 (P^2) & v & T^4 (P^1) & T^4 (P^2)\\ \hline
    Rnd\ 1 & A & B & & C & D & & E & F & & G & H\\ \hline
    Rnd\ 2 & A & C & & E & G & & B & D & & F & H\\ \hline
    Rnd\ 3 & A & D & & H & E & & B & C & & G & F\\ \hline
    Rnd\ 4 & A & E & & B & F & & C & G & & D & H\\ \hline
    Rnd\ 5 & A & F & & D & G & & C & H & & B & E\\ \hline
    Rnd\ 6 & A & G & & B & H & & C & E & & D & F\\ \hline
    Rnd\ 7 & A & H & & C & F & & D & E & & B & G\\ \hline
\end{array}$$
I'm quite confident there is a "perfect" solution for every iteration of this problem (e.g. 12, 16, 20 participants and higher), but as you continue to increase the number of players it becomes significantly less efficient to use the brute force method to identify what these schedules look like.
Has anyone tackled this problem before and come up with an elegant solution as opposed to using the brute force method?  If not, does anyone have any ideas on potential solutions or some methods I can look into to help identify a more efficient solution to solving this problem?

REPLY [2 votes]: There's a generator for this type of tournament here. The site also has a message board where you can ask questions. The site also links to this page where additional info on the underlying algorithms are given.


TITLE: can alpha particles cause perturbation
QUESTION [0 upvotes]: Can alpha particles coming from a matter cause the molecules surrounding that matter to move (cause perturbation)? in these cases:
Air, Water, Oil, Grease
Thank you

REPLY [0 votes]: Alpha particles are absorbed by 10 cm of air and they are the least penetrating of the three types of radioactive decay. Thinking about it, my comment above might have been badly worded, my apologies if it was not as helpful as I intended.
When the alpha particles emerge from the nucleus, they are lighter in mass than air molecules but they are moving relatively quickly. They can lose energy in two ways, either by ionising the air molecules,  which is the most likely method, although the $O_2$ molecule will still move in accordance with the laws of conservation of momentum and energy.
They may have a very  small chance of getting through the screen of 8 electrons surrounding  the oxygen (or 7 in the case of nitrogen)  atom and imparting their momentum  directly to the oxygen nucleus, but I would guess this would be  a very rare event compared to the ionisation process.
Once the alpha particle has lost its momentum, its chance of causing perturbation of a air molecule is pretty much nil.
Here's a picture of the three types of radiation and how much material is needed to stop each of them.

Image source: Cyberphysics


TITLE: Symmetrizing the Canonical Energy-Momentum Tensor
QUESTION [20 upvotes]: The Canonical energy momentum tensor is given by
$$T_{\mu\nu} = \frac{\partial {\cal L}}{\partial (\partial^\mu \phi_s)} \partial_\nu \phi_s - g_{\mu\nu} {\cal L}. $$
A priori, there is no reason to believe that the EM tensor above is symmetric. To symmetrize it we do the following trick.
To any EM tensor we can add the following term without changing its divergence and the conserved charges:
$${\tilde T}_{\mu\nu} = T_{\mu\nu} + \partial^\beta \chi_{\beta\mu\nu}, $$
where $\chi_{\beta\mu\nu} = - \chi_{\mu\beta\nu}$. The antisymmetry of $\chi$ in its $\mu\beta$ indices implies that ${\tilde T}_{\mu\nu}$ is conserved. Also, all the conserved charges stay the same.
Now even though $T_{\mu\nu}$ is not a symmetric tensor, it is possible to choose $\chi_{\beta\mu\nu}$ in such a way so as to make ${\tilde T}_{\mu\nu}$ symmetric. It can be shown that choosing
$$\chi_{\lambda\mu\nu} = - \frac{i}{2}\left[ \frac{\delta {\cal L}}{\delta (\partial^\mu \phi_r) } (I_{\nu\lambda})_{rs} \phi_s +   \frac{\delta {\cal L}}{\delta (\partial^\lambda \phi_r) } (I_{\mu\nu})_{rs} \phi_s + \frac{\delta {\cal L} }{\delta (\partial^\nu \phi_r) } (I_{\mu\lambda})_{rs} \phi_s  \right]$$
makes the new EM tensor symmetric. Here $(I_{\mu\nu})_{rs}$ is the representation of the Lorentz Algebra under which the fields $\phi_s$ transform.
Here's my question - Is it possible to obtain the symmetric EM tensor directly from variational principles by adding a total derivative term to the Lagrangian. In other words, by shifting ${\cal L} \to {\cal L} + \partial_\mu X^\mu$, and choosing $X^\mu$ appropriately, can we exactly get the shift in the EM tensor required, in order to make the canonical EM tensor symmetric?
What I've done so far - It is possible to show that under a shift in the Lagrangian by a total derivative, one shifts the EM tensor by $T_{\mu\nu} \to T_{\mu\nu} + \partial^\lambda \chi_{\lambda\mu\nu}$ where
$$\chi_{\lambda\mu\nu} =   \frac{1}{2} \frac{\delta X_\lambda}{\delta (\partial^\mu \phi_r)}  \partial_\nu \phi_r   -  \frac{1}{2}   \frac{ \delta X_\mu }{\delta (\partial_\lambda \phi_r)}    \partial_\nu \phi_r   +  X_\mu g_{\lambda\nu} -    X_\lambda g_{\mu\nu} \,. $$
What I wish to do next - I now have a differential equation that I wish to solve:
\begin{align}
&\frac{1}{2} \frac{\delta X_\lambda}{\delta (\partial^\mu \phi_r)}  \partial_\nu \phi_r   -  \frac{1}{2}   \frac{ \delta X_\mu }{\delta (\partial_\lambda \phi_r)}    \partial_\nu \phi_r   +  X_\mu g_{\lambda\nu} -    X_\lambda g_{\mu\nu} \\
&~~~~~~= - \frac{i}{2}\left[ \frac{\delta {\cal L}}{\delta (\partial^\mu \phi_r) } (I_{\nu\lambda})_{rs} \phi_s +   \frac{\delta {\cal L}}{\delta (\partial^\lambda \phi_r) } (I_{\mu\nu})_{rs} \phi_s + \frac{\delta {\cal L} }{\delta (\partial^\nu \phi_r) } (I_{\mu\lambda})_{rs} \phi_s  \right] \,.
\end{align}
Any ideas on how to solve this?

REPLY [0 votes]: It is possible to choose a Lagrangian such that the Noether energy momentum tensor is symmetric, namely $${\cal L} = \frac{\epsilon_0}{2} \partial_\mu A_\nu \partial^\mu A^\nu \,.$$ This Lagrangian however differ from the standard one $${\cal L} = \frac{\epsilon_0}{4} F_{\mu\nu} F^{\mu\nu} \,.$$ by the term $${\cal L} = \frac{\epsilon_0}{2} \partial_\mu A_\nu \partial^\nu A^\mu \,.$$ which is not a total derivative.


TITLE: Quadratic roots
QUESTION [0 upvotes]: I've come across the expression $α/β + β/α$ which I've never seen before. I've tried to find out as much as I can about it but I've only found information on the other expressions for quadratic roots $α+β$ and $αβ$ and regular (non maths) sites in russian.
The quadratic in particular this expression is in relation to is $$2x^2 - 3x - 1 = 0$$
A fairly simple quadratic, but I don't know how to use the expression $α/β + β/α$.
Can anyone explain it's use and how to calculate it?

REPLY [2 votes]: Hint:$$\dfrac{\alpha}{\beta} + \dfrac{\beta}{\alpha} = \dfrac{\alpha^2 + \beta^2}{\alpha\beta} = \dfrac{(\alpha + \beta)^2-2\alpha\beta}{\alpha\beta}$$


TITLE: Lipschitz contradiction
QUESTION [1 upvotes]: Assume that $\phi:\mathbb{R}^n\rightarrow \mathbb{R}^n$ is a smooth vector field, and assume that we can find vectors $y_k,x_k$ ($k$ positive integer) such that
$(\phi(x_k)-\phi(y_k),x_k-y_k)\geq k \mid y_k-x_k\mid^2$, where $(,)$ is the usual scalar product.
Why does this condition contradict the fact that $\phi$ is Lipschitz?

REPLY [2 votes]: Recall Cauchy Schwarz which says $(x,y)\leq \|x\| \|y\|$.
Then $$(\phi(x_k)-\phi(y_k),x_k-y_k)\leq \|\phi(x_k)-\phi(y_k)\| \|x_k-y_k\|$$  Since $\phi$ is Lipschitz, there exists a constant $C$ such that $$|\phi(x_k)-\phi(y_k)\|\leq C\|x_k-y_k\|$$ and hence $$(\phi(x_k)-\phi(y_k),x_k-y_k)\leq C|x_k-y_k\|^2.$$  But if we had two sequences, $x_k$, $y_k$ with $$(\phi(x_k)-\phi(y_k),x_k-y_k)\geq k\|y_k-x_k\|^2,$$ we would have to have $C>k$ for every integer $k$ which is impossible.
Hope that helps,
Note:  I assume that your statement is meant to be interpreted as "for every integer $k$ we can find $x_k$, $y_k$ ..." rather than "there exists $k$ with..." since setting $\phi$ equal to $k$ times the identity deals with the second case.


TITLE: Are gluon particles analogous to flux tubes?
QUESTION [0 upvotes]: I've always been told gluons are the force "particles" mediating the strong force. And I've learned that Fluxtubes are what hold quarks together. Are these fluxtubes the "particle" component of gluons?
I can't seem to find an explanation of where the "particle" resides within the gluon field.
I've seen these animations that say the particles "jump" to the higher energy blobs. But then are the particles themselves not what binds quarks together?

REPLY [1 votes]: Gluons are zero mass   elementary point particles in the standard model of particle physics. They are for the strong interaction what the photon is for the electromagnetic interactions.
Electrons and nuclei form atoms held together with the exchange of virtual photons . The attraction of quark to quark or antiquark is similar, but complicated mathematically by the fact that gluons are attracted to gluons, whereas photons are not attracted to photons. So a quark and antiquark forming a hadron, pion for example, exchange what you call "flux tubes", virtual complicated gluon exchanges, forming a flux because of the glue-glue attraction (a pion will decay very fast through the weak interaction, but that is another story).
There is no "particle within the gluon field", and the term "gluon field" belongs to a higher level quantum model, the quantum field theory, a complicated story at this level of the question.


TITLE: No factors of Characteristic Polynomial are the Minimal Polynomial?
QUESTION [0 upvotes]: I'm trying to compute the Jordan canonical form for the matrix
$$ \begin{pmatrix}
9 & 4 & 5    \\
-4 & 0 & -3  \\
-6 & -4 & -2
\end{pmatrix}. $$
My first step was to compute the characteristic polynomial and then, from that, find the minimal polynomial. But finding the minimal polynomial is proving to be somewhat of a challenge for some reason. Observe:
Let $A$ be the given matrix. Then, the characteristic polynomial $\chi_A(x)$ is given by the determinant of $xI - A$. Thus,
$$ \chi_A(x) = x^3 - 7x^2 + 16x - 12 = (x-3)(x-2)^2. $$
So, the minimal polynomial $m_A(x)$ must be either $(x-3)(x-2)$ or $(x-3)(x-2)^2$. But,
$$ (A-3I)(A-2I) =  \begin{pmatrix}
42 & 16 & 25    \\
16 & 6 & 9  \\
36 & 16 & 20
\end{pmatrix} \ne \begin{pmatrix}
0 & 0 & 0    \\
0 & 0 & 0  \\
0 & 0 & 0
\end{pmatrix}. $$
And, similarly,
$$ (A-3I)(A-2I)^2 =  \begin{pmatrix}
294 & 64 & 125    \\
-64 & -12 & -27  \\
-216 & -64 & -80
\end{pmatrix} \ne \begin{pmatrix}
0 & 0 & 0    \\
0 & 0 & 0  \\
0 & 0 & 0
\end{pmatrix}. $$
Does this matrix not have a minimal polynomial, or something? Is such a thing even possible? What am I doing wrong here?

REPLY [1 votes]: I get
\begin{align*}
A-3I &= \pmatrix{
 6&4&5\cr
 -4&-3&-3\cr
 -6&-4&-5\cr
 } \\
A-2I &= \pmatrix{
 7&4&5\cr
 -4&-2&-3\cr
 -6&-4&-4\cr
 } \\
(A-3I)(A-2I) &= \pmatrix{
 -4&-4&-2\cr
 2&2&1\cr
 4&4&2\cr
 } \\
(A-3I)(A-2I)^2 &= \pmatrix{
 0&0&0\cr
 0&0&0\cr
 0&0&0\cr
 }
\end{align*}


TITLE: If a Gaussian measure has density, then its covariance is nondegenerate
QUESTION [1 upvotes]: A Gaussian measure $\mu$ on $\mathbb{R}^{N}$ is said to be Gaussian if its Fourier transform has the form:
$$\hat{\mu}(y) := \int_{\mathbb{R}^{N}}e^{i\langle y,x\rangle}d\mu(x) = e^{i\langle a,y\rangle - \frac{1}{2}\langle Ky,y\rangle}$$
where $a \in \mathbb{R}^{N}$ and $K$ is a nonnegative symmetric matrix. I want to prove that if $\mu$ is Gaussian, then $\mu$ has density if, and only if $K$ is nondegenerate. I already proved that if $K$ is nondegenerate, then $\mu$ has density, but I'm stuck at the converse: if $\mu$ has density, then $K$ needs to be nondegenerate. Any hints, please?

REPLY [4 votes]: The Riemann-Lebesgue lemma tells us that the Fourier transform of an $L^{1}$ function vanishes at infinity.
But if $K$ is not positive definite there is some $y$ for which $\left\langle K y, y\right\rangle\le 0$.
So $\mathcal{F}\mu$ will not be heading to zero in that direction.


TITLE: If $M$ is a convex subset and $f:M\rightarrow F$ is uniformly continuous, prove that $\|f(x)-f(y)\|\leq a \|x-y\|+1$
QUESTION [0 upvotes]: Consider: $E,F$ normed vector spaces, $M\subset E$ a convex subset and $f:M\rightarrow F$ a uniformly continuous function. Prove that there exists $a>0$ such that: $\|f(x)-f(y)\|\leq a \|x-y\|+1$ .

I have only a suspicion of a way to prove this exercise. Since $M$ is convex, for every $a,b\in M$, the set $[a,b] = \{(1-t)a+tb:t\in[0,1]\} \subset M$. By hyphotesis $E$ is a normed vector space, so for any $x,y\in M$ we can take $x'=x/\|x\|$ and $y'=y/\|y\|$. So the set $[y',x']$ is contained in $M$. Also we can note that $\|(1-t)y'+tx'\|=\|t(x'-y')+y'\|\leq t \|x'-y'\|+\|y'\| = t\|x'-y'\|+1. $
This latter equation reminds me of the one that we must prove. But i can't proceed with those observations. Any help would be much appreciated.

REPLY [1 votes]: Suppose that $f$ is uniformly continuous on $M$. This means, that for $\epsilon = 1$, there exists $\delta$ such that $|x - y| < \delta \implies |f(x) -  f(y)| < 1$ for all $x,y \in M$.
Fix $x,y \in M$ and define $z_k = x + k\frac {\delta}{2} \frac{y-x}{||y-x||}$ for $k = 0,1,2,...,N$ where $N = \left\lfloor\frac{2||y-x||}{\delta}\right\rfloor$.
From the convexity of $M$, each $z_k \in M$. Also, $z_0 = x$, $||z_k  - z_{k-1}|| = \frac \delta 2$ and $||y-z_N|| < \frac \delta 2$, which I leave you to see yourself.
Therefore, $$
||f(y) - f(x)|| \leq \sum_{k=1}^N ||f(z_k) - f(z_{k-1})|| + ||f(y) - f(z_N)|| < (N + 1) \leq \frac{2||y-x||}{\delta} + 1
$$
Now, pick $a = \frac 2 \delta$ to conclude the argument. Since $x,y$ were arbitrary, this is true for all $x,y \in M$.


TITLE: Irreducible elements are not associates
QUESTION [2 upvotes]: I would like to know if every irreducible elements in a ring are not associates. I'm asking that because of this part in the page 61 of this book:

Thanks a lot

REPLY [5 votes]: Two primes are associates if one of them is a unit times the other.  For example, in the integers $5$ and $-5$ are associates (as are $p$ and $-p$).  More trivially a prime is always an associate of itself.
You should think of "not associates" as a slightly stronger version of "distinct."


text:
In this section, we prove Theorem~\ref{thm:episodic}.

\paragraph{Notations}

	Let $Q_h^k(x,a),V_{h}^k(x),N_h^k(x,a)$ denote the value of $Q_h(x,a),V_{h}(x)$,and $N_h(x,a)$ right before the $k$-th episode, respectively.

Let $\indict{\cdot}$ denote the indicator function.
Let $\tau_h(x,a,i):=\max\left\{k:N_h^k(x,a)=i-1\right\}$ be the episode $k$ at which $\xahk{h}{k}=(x,a)$ for the $i$-th time. We will abbreviate $\Nxahk{h}{k}$ for $n_h^k$ when no confusion can arise.
$\alpha_t^i$ is defined by the following: $\alpha_t\!=\!\frac{H+1}{H+t}$, $\alpha_t^0\!=\!\prod_{j=1}^{t}\!\left(1\!-\!\alpha_{j}\right)$ and $\alpha_t^i\!=\!\alpha_i\!\prod_{j=i+1}^{t}\!\left(1\!-\!\alpha_{j}\right)\ (i>0)$. Let $\beta_0=0$ and $\beta_t\!=\!4c\sqrt{\!\frac{H^3\iota}{t}}$ for $t\ge1$.

\paragraph{Proof of Theorem~\ref{thm:episodic}}
Our proof starts with the observation that the regret of each episode can be rewritten as the expected sum of sub-optimality gaps for each action:
\begin{align}
&\left(V_1^*-V_1^{\pi^k}\right)\!\left(x_1^k\right)\nonumber\\
=&\ V_1^*\!\left(x_1^k\right)
-Q_1^*\!\left(x_1^k,a_1^k\right)
+\left(Q_1^*-Q_1^{\pi^k}\right)\!\xahk{1}{k}\nonumber\\
=&\ \gaph{1}\left(x_1^k,a_1^k\right)
+\mathbb{E}_{s'\sim \Pxahk{1}{k}}
\left[\left(V_{2}^*-V_{2}^{\pi^k}\right)\!(s')\right]\nonumber\\
=&\ \cdots\ =\expect{\sum_{h=1}^H
	\gaph{h}\!\xahk{h}{k}\Bigg|
	a_h^k=\pi_h^k(x_h^k)}.
\label{eq:episodic-regret-decomp}
\end{align}

In order to bound $\gaph{h}\!\xahk{h}{k}$ by learning error $\left(\!Q_h^k-Q_h^*\right)\!\xahk{h}{k}$, we define the following concentration event.
\begin{definition}[Concentration of Learning Errors]
	\begin{align*}
	\cE_{\mathrm{conc}}&:=\Bigg\{
	\forall (x,\!a,\!h,\!k)\!
	:
	0\le \left(Q_h^k\!-\!Q_h^*\right)\!(x,a)\le\nonumber\\
	&\alpha_{n_h^k}^0 H\!+\!\sum_{i=1}^{n_h^k}\alpha_{n_h^k}^i\!\left(\!V_{\!h+1}^{\!\tau_h(x,a,i)}\!-\!V^*\!\right)\!(\!x_{h+1\!}^{\!\tau_h\!(x,a,i)}\!)\!+\!\beta_{\!n_h^k}\Bigg\} .
\end{align*}
\end{definition}
Intuitively, $\cE_{\mathrm{conc}}$ is the event in which all the learning errors of the value function is both bounded below (by zero) and bounded above.

We now refer to \cite{jin2018qlearning} for the following lemma that

shows $\cE_{\mathrm{conc}}$ happens with high probability
via a concentration argument.
\begin{lemma}[Concentration]
	\label{lemma: conc-event}
	 Event $\cE_{\mathrm{conc}}$ occurs
	w.p. at least $1-\nicefrac{1}{T}$.

\end{lemma}
Lemma~\ref{lemma: conc-event} suggests that Algorithm~\ref{algo:ucb-q} is optimistic on $\cE_{\mathrm{conc}}$. Combining with the greedy choice of actions yields
\begin{align}
V_h^{*}\left(x_h^k\right)\!=\!
Q_h^{*}\left(x_h^k,a^{\!*}\!\right)\!\le\! Q_h^{k}\left(x_h^k,a^{\!*}\!\right) \!\le\! Q_h^{k}\left(x_h^k,a_h^k\right).
\label{ineq:optimistic-bound-on-Vopt}
\end{align}
To bound $\gap_h(x_h^k,a_h^k)$, the following notion introduced in \cite{max2019nonasymptotic} is convenient.
If we define $\clip{x}{\delta}\!:=\!x\cdot\indict{x\ge\delta}$, then Ineq~\eqref{ineq:optimistic-bound-on-Vopt}  suggests that $\gaph{h}\!\xahk{h}{k}$ can be bounded by clipped estimation error:
\begin{align}
\gaph{h}\!\xahk{h}{k}&=\clip{V_h^{*}\!\left(x_h^k\right)-Q_h^*\!\xahk{h}{k}}{\gapmin}\nonumber\\
&\le\clip{\left(Q_h^k-Q_h^*\right)\!\xahk{h}{k}}{\gapmin}.
\label{ineq:gap-bounded-by-learning-error}
\end{align}

Our main technique to get $1/\gapmin$ instead of $1/\gapmin^2$ regret bound is to classify gaps of state-action pairs into different intervals and count them separately.
Note the gap can range from $\gapmin$ to $H$.
Thus, we divide the interval $\left[\gapmin,H\right]$ into $N$ disjoint intervals:
 $\left[\gapmin,2\gapmin\right),\cdots,\left[2^{N-1}\gapmin,2^N\gapmin\right]$, where $N=\left\lceil \log_2\left(\nicefrac{H}{\gapmin}\right)\right\rceil$.

 Lemma~\ref{lemma:count-in-each-layer} below is our main technical lemma which upper bounds the number of steps Algorithm~\ref{algo:ucb-q} chooses a sub-optimal action whose suboptimality is in a certain interval.
\begin{lemma}[Bounded Number of Steps in Each Interval]
	\label{lemma:count-in-each-layer} Under $\cE_{\mathrm{conc}}$, we have
 	for every $n\in\left[N\right]$,

	\begin{align*}
	C^{(n)} &\!:=\!\Bigg|\!\left\{\!(k,h):\ {\left(Q_h^k-Q_h^*\right)\!\xahk{h}{k}\!\in\atop\!\left[2^{n-1}\gapmin,2^n \gapmin\right)}\ \right\}\!\Bigg|\nonumber\\
	&\le\mathcal{O}\left(\frac{H^6SA\iota}{4^n \gapmin^2}
	\right),\qquad\text{where $\iota = \log\left(SAT^2\right)$.}
	\end{align*}
\end{lemma}
Before we give the proof for Lemma~\ref{lemma:count-in-each-layer}, we first show how to use Lemma~\ref{lemma:count-in-each-layer} to prove Theorem~\ref{thm:episodic}.
\paragraph{Proof of Theorem~\ref{thm:episodic}}
	Since the trajectories inside $\cE_{\mathrm{conc}}$ have bounded empirical regret, and
	complementary event $\overline{\cE_{\mathrm{conc}}}$ happens with sufficiently low probability,

	\begin{align}
	&\expect{\regret(K)} =\expect{\sum_{k=1}^K\!\sum_{h=1}^H
		\gaph{h}\!\left(x_h^k,a_h^k\right)}\nonumber\\=\
	&\!\sum_{\text{traj}}\!
	\prob\!\left(\text{traj}\right)\cdot\!
	\sum_{k,h}\!
	\gaph{h}
		\left(\!x_h^k,a_h^k\big|\text{traj}\right)
		\label{tmp0}\\
	{\le}&
	\!\sum_{\text{traj}\in\cE_{\mathrm{conc}}}\!
	\prob\!\left(\text{traj}\right)\!\cdot\!
	\sum_{k,h}\!
	\clip{\!\left(\!Q_h^k\!-\!Q_h^*\!\right)\!
		(\!x_h^k,a_h^k\big|\text{traj}\!)\!}{\gapmin\!}
	\nonumber\\
	&\qquad+
	\sum_{\text{traj}\in\overline{\cE_{\mathrm{conc}}}}\!
	\prob\!\left(\text{traj}\right)\!\cdot\!TH
	\label{tmp1}\\
	{\le}&\prob\!\left(\cE_{\mathrm{conc}}\right)
	\sum_{n=1}^{N} 2^n\gapmin C^{(n)}
	+\prob\!\left(\overline{\cE_{\mathrm{conc}}}\right)\cdot TH
	\label{tmp2}\\
	{\le}&\sum_{n=1}^{N}\!\mathcal{O}\!\left(\frac{H^6SA\iota}{2^n \gapmin}\right)\!+\!H\label{tmp3}\\
	\le&\mathcal{O}\!\left(\!\frac{H^6SA}{\gapmin}
	\log\!\left(\!{SAT}\right)\!\right).\nonumber
	\end{align}
	Above, \eqref{tmp0} follows from the definition of expectation,
	\eqref{tmp1} is because Ineq~(\ref{ineq:gap-bounded-by-learning-error}) suggests that for trajectories inside $\cE_{\mathrm{conc}}$, gaps can be bounded by clipped learning errors; whereas for trajectories outside of $\cE_{\mathrm{conc}}$, sub-optimality gaps never exceed $H$.
	\eqref{tmp2} follows from adding an outer summation for state-action pairs over the $N$ disjoint subintervals, then bounding the estimation error in each subinterval by its maximum value times the number of steps it contains.
	\eqref{tmp3}~comes from a sum of numbers in a geometric progression generated by Lemma~\ref{lemma:count-in-each-layer}, and the fact that $\prob\!\left(\overline{\cE_{\mathrm{conc}}}\right)\le \nicefrac{1}{T}$ from concentration Lemma~\ref{lemma: conc-event}.
	In the final step, we notice that $\iota=\log(SAT^2)=\cO\left(\log(SAT)\right)$.

\qed

\paragraph{Proof of Lemma~\ref{lemma:count-in-each-layer}}
The proof of Lemma~\ref{lemma:count-in-each-layer} relies on a general lemma (Lemma~\ref{lemma:weighed-sum-learning-error}) characterizing a weighted sum of the estimation errors of $Q$-function.
 Then we choose a particular sequence of weights to prove Lemma~\ref{lemma:count-in-each-layer}.
We remark that this general idea has appeared in \cite{jin2018qlearning,dong2019qlearning,zhang2020optimal}.

Formally, we use the following definition.
\begin{definition}[$(C,w)$-Sequence (Definition 3 in \cite{dong2019qlearning})]
	\label{def:c-w-sequence}
	A sequence $\left\{w_{k}\right\}_{\!k\ge1}$ is called a $(C,w)$-sequence if $0\!\le\!w_{k}\!\le\!w$ for all $k$ and $\sum_{k}\!w_{k}\le C$.
\end{definition}

\begin{lemma}[Weighted Sum of Learning Errors]
	\label{lemma:weighed-sum-learning-error}
	On event $\cE_{\mathrm{conc}}$, {for every $h\in[H]$, if $\left\{w_{k}\right\}_{k\in[K]}$ is a $(C,w)$-sequence,
		then:}
	\begin{eqnarray}
	\sum_{k=1}^K \!w_{k}\!
	\left(\!Q_h^k-Q_h^*\!\right)\!(\!x_h^k,a_h^k\!)
	\!\le\! ewS\!AH^2\!+\!10c\sqrt{\!ewS\!AC\!H^5\iota}.\nonumber
	\end{eqnarray}
\end{lemma}

Before presenting the proof of Lemma~\ref{lemma:weighed-sum-learning-error}, we refer the readers to \cite{jin2018qlearning} for Lemma~\ref{lemma:property-lr} below, which summarizes the properties of $\alpha_t^i$ that will be useful in our proof.
\begin{lemma}[Properties of $\alpha_t^i$]
	\label{lemma:property-lr}
	Let $\alpha_t\!=\!\frac{H+1}{H+t}$, $\alpha_t^0\!=\!\prod_{j=1}^{t}\!\left(1\!-\!\alpha_{j}\right)$ and $\alpha_t^i\!=\!\alpha_i\!\prod_{j=i+1}^{t}\!\left(1\!-\!\alpha_{j}\right)$ for $0<i\le t$.
	\begin{enumerate}[(i)]
		\item $\sum_{i=1}^{t}\alpha_t^i=1$ and $\alpha_t^0=0$ for every $t\ge1$, $\sum_{i=1}^{t}\alpha_t^i=0$ and $\alpha_t^0=1$ for $t=0$.
		\item $\sum_{t=i}^{\infty}\alpha_t^i=1+\frac{1}{H}$ for every $i\ge1$.

	\end{enumerate}
\end{lemma}
\paragraph{Proof of Lemma~\ref{lemma:weighed-sum-learning-error}}

We will recursively bound the weighted sum of step $h$ by its next step $(h\!+\!1)$, and unroll $(H\!-\!h\!+\!1)$ times for the desired bound. As suggested by Lemma~\ref{lemma: conc-event}, upper bounds of learning error holds under $\cE_{\mathrm{conc}}$. Thus we have
\begin{align}
&\sum_{k=1}^K w_{k}
\left(Q_h^k-Q_h^*\right)\!\xahk{h}{k}\nonumber\\
\le& \sum_{k=1}^K\! w_{k}
\Big(\! H\!\alpha_{n_h^k}^0\!+\!\beta_{\!n_h^k}\!+\!\sum_{i=1}^{n_h^k}\alpha_{n_h^k\!}^i\!\left(\!V_{\!h+1}^{\!\tau_h\!(s,a,i)}\!-\!V_{h+1}^{\!*}\!\right)\!(\!x_{h+1\!}^{\!\tau_h\!(\!s,a,i\!)\!}\!)\!
\Big)\nonumber\\
= &\sum_{k=1}^K w_{k} H\alpha_{n_h^k}^0+\sum_{k=1}^K w_{k} \beta_{n_h^k}\nonumber\\
&+\sum_{k=1}^K w_k
\sum_{i=1}^{n_h^k}\!\alpha_{n_h^k\!}^i\!\left(\!V_{\!h+1}^{\!\tau_h\!(x_h^k\!,a_h^k,i)}\!-\!V_{h+1}^{\!*}\!\right)\!(x_{h+1\!}^{\!\tau_h\!(\!x_h^k\!,a_h^k,i\!)\!})
\label{ineq:recursion}.
\end{align}
For the first term of \eqref{ineq:recursion}, $n_h^k\!=\!0$ at most once for every state-action pair, and we always have $w_k\!\le\! w$. Thus,
\begin{align}
\sum_{k=1}^K w_{k}H\alpha_{n_h^k}^0=\sum_{k=1}^K w_{k} H\indict{n_h^k=0}\le wSAH.
\label{first term}
\end{align}

The second term of (\ref{ineq:recursion}) can be bounded by the following inequalities with respective reasons listed below:
\begin{align}
\sum_{k=1}^K w_{k} \beta_{n_h^k}&=
\sum_{s,a}\! \sum_{k=1\atop (s_h^k,a_h^k)=(s,a)}^{K}\!w_{k}\beta_{n_h^k}\nonumber\\
&= 4c\sqrt{\!H^3\iota}
\sum_{s,a}\!
\sum_{i=2}^{N_h^{\!K}\!(s,a)}\!
\frac{w_{\!\tau\!(\!s,a,i\!)}}{\sqrt{i-1}}
\label{tmp11}\\
&{\le}
4c\sqrt{\!H^3\iota}
\sum_{s,a}
\sum_{i=1}^{\left\lceil{C_{s,a}}/{w}\right\rceil}
\frac{w}{\sqrt{i}}
\label{tmp12}\\
&{\le}10c\sqrt{H^3\iota}
\sum_{s,a}\sqrt{C_{s,a} w}\label{tmp13}\\
&{\le}10c\sqrt{SACwH^3\iota}.
\label{ineq:beta-sum}
\end{align}

Above, \eqref{tmp11} comes from prior definition $\beta_t\!=\!4c\sqrt{\!\frac{H^3\iota}{t}}$ when $t\ge 1$ and $\beta_0=0$. Note that $\tau_h(x, a, i)$ is the episode where $(x, a)$ is visited for the $i$-th time, so we always have $n_h^{\tau_h(x,a,i)} = i-1$. \eqref{tmp12} follows from a rearrangement inequality with $C_{\!s,a\!}$ defined as $C_{\!s,a\!}:=\sum\nolimits_{i=1}^{n_h^{\!K}\!(\!s,a\!)}\!w_{\tau\!(\!s,a,i\!)}$, where we always keep in mind that $0<w_{\tau\!(\!s,a,i\!)}\le w$. \eqref{tmp13} follows from the integral conversion of $\sum_i{1}/{\sqrt{i}}$, and \eqref{ineq:beta-sum} is true because of Cauchy-Schwartz inequality where
$\sum\nolimits_{\!s,a\!}\!C_{\!s,a\!}\!=\!\sum\nolimits_{k=1}^K w_k\!\le\!C$.

For the third term in Ineq (\ref{ineq:recursion}), we notice that $\Vxhk{h}{k}=\Qxahk{h}{k}$ due to greedy choice of actions and $V_{h}^*\!(x_{h}^k)\ge Q_{h+1}^*\!(x_{h+1}^k,a_{h+1}^k)$ by definition.
Therefore
 $\left(V_{h}^k-V_{h}^*\right)\!(x_{h}^k)\le \left(Q_{h}^k-Q_{h}^*\right)\!(x_{h}^k,a_{h}^k)$.
Note that $\forall\! k\!\in\![K]$, the third term takes into account all the prior episodes $l\!<\!k$ where $\xahk{h}{k}\!=\!\xahk{h}{l}$, indicating that the learning error at step $l$ is only counted by subsequent episodes $k\!>\!l$ when the same $(s,a)$ is visited.
Thus, we exchange the order of summation and obtain
\begin{align}
&\sum_{k=1}^K w_k\sum_{i=1}^{n_h^k}
\alpha_{n_h^k\!}^i\!\left(\!V_{\!h+1}^{\!\tau_h\!(x_h^k,a_h^k,i)}\!-\!V_{h+1}^{\!*}\!\right)\!(x_{h+1\!}^{\!\tau_h\!(\!x_h^k,a_h^k,i\!)\!})\nonumber\\
=&\sum_{l=1}^{K}
\left(V_{\!h+1}^{l}\!-\!V_{h+1}^{\!*}\right)\!(x_{h+1\!}^{l})
\sum_{j= n_h^l+1}^{N_{\!h}^{\!K}\!\xahk{h}{l}}\!
w_{\tau_h\!(x_h^l,a_h^l,j)} \alpha_{j}^{\!n_h^l+1}\nonumber\\
\le&\sum_{l=1}^{K}
\left(\!Q_{\!h\!+\!1}^{l}\!-\!Q_{h\!+\!1}^{*}\!\right)\!(x_{h\!+\!1\!}^{l}, a_{h\!+\!1\!}^{l})
\sum_{j= n_h^l\!+1}^{N_{\!h}^{\!K}\!\xahk{h}{l}}\!
w_{\!\tau_h\!(x_h^l,a_h^l,j\!)}\! \alpha_{j}^{\!n_h^l\!+1}.\nonumber
\end{align}

Then for $l\in[K]$ we
let $\widetilde{w}_l=
\sum\limits_{j= n_h^l+1}^{N_{\!h}^{\!K}\!\xahk{h}{l}}\!
w_{\tau_h\!(x_h^l,a_h^l,j)} \alpha_{j}^{\!n_h^l+1}$ and further simplify the above equation to be
\begin{align}
&\sum_{k=1}^K w_k\sum_{i=1}^{n_h^k}
\alpha_{n_h^k\!}^i\!\left(\!V_{\!h+1}^{\!\tau_h\!(s,a,i)}\!-\!V_{h+1}^{\!*}\!\right)\!(x_{h+1\!}^{\!\tau_h\!(\!s,a,i\!)\!})\nonumber\\
\le&\sum_{l=1}^{K}\widetilde{w}_l
\left(Q_{\!h+1}^{l}\!-\!Q_{h+1}^{\!*}\right)\!(x_{h+1\!}^{l}, a_{h+1\!}^{l}).\label{third term}
\end{align}
Next, we use Lemma~\ref{lemma:property-lr} to verify that $\left\{\widetilde{w}_l\right\}_{l\in[K]}$ is a $\left(C,\left(\!1\!+\!\frac{1}{H}\!\right)\!w\right)$-sequence:
\begin{align}
\widetilde{w}_l&\le w\!\sum_{j= n_h^l\!+\!1}^{N_{\!h}^{\!K}\!\xahk{h}{l}}\alpha_j^{n_h^l\!+\!1}\le w\! \sum_{j\ge n_h^l\!+\!1} \!\alpha_j^{n_h^l\!+\!1}
\!\le\!  \left(\!1\!+\!\frac1H\!\right)\!w,\nonumber\\
\sum_{l=1}^{K}\!\widetilde{w}_{l}

&=\sum_{l=1}^K\sum\limits_{j= n_h^l+1}^{N_{\!h}^{\!K}\!\xahk{h}{l}}\!
w_{\tau_h\!\left(\!x_h^l,a_h^l,j\!\right)} \alpha_{j}^{\!n_h^l+1}\nonumber\\
&=\sum\limits_{k=1}^K\!w_{k}\sum\limits_{t=1}^ {n_h^k}
\alpha_{n_h^k}^t=\sum\limits_{k=1}^K\!w_{k}\le C.
\label{ineq:w_{h+1}}
\end{align}
Plugging the upper bounds of three separate terms in \eqref{first term}, \eqref{ineq:beta-sum} and \eqref{third term} back into Ineq~\eqref{ineq:recursion} gives us
\begin{align}
\sum_{k=1}^K \!w_{k}\!&
\left(\!Q_h^k\!-\!Q_h^*\!\right)\!\xahk{h}{k}
\!\le\! wSAH\!+\!10c\sqrt{SACwH^3\iota}\nonumber\\
&\!+\!\sum_{l=1}^K\!\widetilde{w}_{l}\!
\left(\!Q_{h\!+\!1}^l\!-\!Q_{h\!+\!1}^*\!\right)\!\xahk{h+1}{l},
\end{align}
where the third term is a weighted sum of learning errors of the same format, but taken at level $h+1$. In addition, it has weights $\left\{\!\widetilde{w}_{l}\right\}_{\!l\in[\!K\!]\!}$ being a  $\left(\!C,\left(\!1\!+\!{1}\!/\!{H}\!\right)\!w\!\right)$-sequence. Therefore, the above analysis will also yield
\begin{align}
&\sum_{l=1}^K \!\widetilde{w}_{l}\!
\left(\!Q_{h+1}^l\!-\!Q_{h+1}^*\!\right)\!\xahk{h}{l}
\!\le\! \left(\!1\!+\!\frac{1}{H}\!\right)\!wSAH\!\nonumber\\
&+\!10c\sqrt{SAC\!\left(\!1\!+\!\frac{1}{H}\!\right)\!wH^3\iota}
+
\big[\text{weighted sum at ($h\!+\!2$)}\big].\nonumber
\end{align}
Recursing this argument for $h\!+\!1,h\!+\!2,\!\cdots\!,\!H$ gives us
\begin{align}
&\sum_{k=1}^K \!w_{k,h}\!
\left(\!Q_h^k\!-\!Q_h^*\!\right)\!\xahk{h}{k}\nonumber\\
\le&\sum_{h'=0}^{H-h}\left(\!SAH\left(\!1\!+\!{1}\!/\!{H}\!\right)^{h'\!}\!w\!+\!10c\sqrt{\!SAC\left(\!1\!+\!{1}\!/\!{H}\!\right)^{h'}\!wH^3\iota}\!\right)\nonumber\\
\le& H\left(SAHew\!+\!10c\!\sqrt{SACewH^3\iota}\right).
\end{align}
which is the desired conclusion.

With Lemma~\ref{lemma:weighed-sum-learning-error}, we can easily prove Lemma~\ref{lemma:count-in-each-layer} by choosing a particular $(C,w)$-sequence.
\paragraph{Proof of Lemma~\ref{lemma:count-in-each-layer}}
For every $n\!\in\![N]$, $h\!\in\![H]$, let
\begin{align*}
w_{k}^{\!(\!n\!,h\!)}&:=\indict{\left(\!Q_h^k-Q_h^*\!\right)\!
	(x_h^k,a_h^k)\!\in\!\left[2^{n\!-\!1\!}\gapmin,2^n \gapmin\right) }\!,\\
C^{\!(\!n\!,h\!)}&:=\sum_{k=1}^K w_{k}^{(n,h)}\\
&\!=\!\Bigg|\!\Big\{\!k\!:\!\left(\!Q_h^k-Q_h^*\!\right)\!(\!x_h^k,a_h^k\!)\!\in\!\left[\!2^{n\!-\!1\!}\gapmin,2^{n} \gapmin\!\right)\!\Big\}\!\Bigg|.
\end{align*}
By definition, $\forall h\!\in\![H]$ and $n\!\in\![N]$, $\left\{\!w_{k}^{\!(\!n\!,h\!)\!}\!\right\}_{\!k\in[K]}$ is a $(C^{\!(\!n\!,h\!)} ,1)$-sequence.
Now we consider bounding

$\sum_{k=1}^K\! w_{k}^{\!(\!n\!,h\!)}\!
\left(\!Q_h^k\!-\!Q_h^*\!\right)\!\xahk{h}{k}$ from both sides.
On the one hand, by Lemma~\ref{lemma:weighed-sum-learning-error},
\begin{align*}
&\sum_{k=1}^K\! w_{k}^{\!(\!n\!,h\!)}\!
\left(\!Q_h^k\!-\!Q_h^*\!\right)\!\xahk{h}{k}
\!\le\!
 eS\!A\!H^2\!+\!10c\!\sqrt{\!e\!S\!AC^{\!(\!n\!,h\!)}\!H^5\!\iota}.
\end{align*}
On the other hand, according to the definition of $w_k^{\!(\!n\!,h\!)}$,

\begin{align*}
\sum_{k=1}^K\! w_{k}^{\!(\!n\!,h\!)}
\!\left(\!Q_h^k\!-\!Q_h^*\!\right)\!\xahk{h}{k}
\!\ge\! \left(2^{n-1} \gapmin\right)\!\cdot \!C^{\!(\!n\!,h\!)}.
\end{align*}
Combining these two sides,

we obtain the following inequality of $C^{\!(\!n\!,h\!)}$:
\begin{align}
\left(2^{n-1} \gapmin\right)& C^{\!(\!n\!,h\!)}\le eSAH^2+10c\sqrt{eSAC^{\!(\!n\!,h\!)}H^5\iota}\nonumber\\
\Rightarrow&\  C^{\!(\!n\!,h\!)}\le\mathcal{O}\left(\frac{H^5SA\iota}{4^n \gapmin^2}
\right).\nonumber
\end{align}

Finally, we observe that
\begin{align}
C^{(n)}=\sum_{h=1}^{H}C^{\!(\!n\!,h\!)}
\le\mathcal{O}\left(\frac{H^6SA\iota}{4^n \gapmin^2}\right),\nonumber
\end{align}
which is exactly the statement of Lemma~\ref{lemma:count-in-each-layer}.
\qed