# Convergence of Implicit Gradient Descent for Training Two-Layer Physics-
Informed Neural Networks

Xianliang Xu1, Zhongyi Huang1 and Ye Li2,† 1 Department of Mathematics,
Tsinghua University, Beijing, China.
2 College of Computer Science and Technology/Artificial Intelligence, Nanjing
University of Aeronautics and Astronautics MIIT Key Laboratory of Pattern
Analysis and Machine Intelligence, Nanjing, China.
<EMAIL_ADDRESS>zhongyih<EMAIL_ADDRESS>
† Corresponding author.

∗ This work was partially supported by the NSFC Projects No. 12025104,
11871298, 81930119, 62106103.

##  1\. Abstract

Optimization algorithms is crucial in training physics-informed neural
networks (PINNs), unsuitable methods may lead to poor solutions. Compared to
the common gradient descent algorithm, implicit gradient descent (IGD)
outperforms it in handling some multi-scale problems. In this paper, we
provide convergence analysis for the implicit gradient descent for training
over-parametrized two-layer PINNs. We first demonstrate the positive
definiteness of Gram matrices for general smooth activation functions, like
sigmoidal function, softplus function, tanh function and so on. Then the over-
parameterization allows us to show that the randomly initialized IGD converges
a globally optimal solution at a linear convergence rate. Moreover, due to the
different training dynamics, the learning rate of IGD can be chosen
independent of the sample size and the least eigenvalue of the Gram matrix.

##  2\. Introduction

Partial differential equations (PDEs) play an important role in modeling
phenomenas in various fields, such as biology, physics, engineering. However,
solving high-dimensional PDEs numerically is a long-standing challenge in
scientific computing due to the curse of dimensionality while utilizing the
classic methods, like finite difference, finite volume and so on. In recent
years, neural networks have achieved much milestone breakthroughs in the
fields of computer vision [1], natural language processing [2], and
reinforcement learning [3]. The flexibility, scalability and express power of
neural networks motivate researchers to apply them in solving PDEs
numerically. Among the various approaches proposed to solve PDEs via neural
networks, physics-informed neural network (PINN) is a flexible and popular
framework that incorporates physical knowledge into the architecture of neural
networks to solve forward and inverse problems of PDEs.

Specifically, in PINNs, for PDE in the open bounded domain
$\Omega\subset\mathbb{R}^{d}$ with following form:

$\displaystyle\mathcal{F}(u;\theta)(x)$ $\displaystyle=0,\ x\in\Omega,$ (1)
$\displaystyle\mathcal{B}(u;\theta)(x)$ $\displaystyle=0,\
x\in\partial\Omega,$

where $\theta$ is the parameter of the PDE that could be either a vector or a
vector-valued function, $\mathcal{F}$ and $\mathcal{B}$ are differential
operators on $\Omega$ and $\partial\Omega$ respectively. Then, one can
construct a neural network $u_{w}(x)$ and train it with the following loss
function

$\int_{\Omega}(\mathcal{F}(u_{w};\theta)(x))^{2}dx+\lambda\int_{\partial\Omega}(\mathcal{B}(u_{w};\theta)(y))^{2}dy,$
(2)

where $\lambda$ is a hyperparameter to balance the two terms from interior and
boundary. However, the computation of the integrals can be prohibitively
expensive in high dimension, if using traditional quadrature methods. To
circumvent the curse of dimensionality, we can employ Monte-Carlo sampling to
approximate them using a set of collocation points, which yields the following
empirical loss function

$\frac{|\Omega|}{n_{1}}\sum\limits_{i=1}^{n_{1}}(\mathcal{F}(u_{w};\theta)(x_{i}))^{2}+\frac{\lambda|\partial\Omega|}{n_{2}}\sum\limits_{j=1}^{n_{2}}(\mathcal{B}(u_{w};\theta)(y_{j}))^{2},$
(3)

where $|\Omega|$ and $|\partial\Omega|$ are the measures of $\Omega$ and
$\partial\Omega$ respectively, $\\{x_{i}\\}_{i=1}^{n_{1}}$ and
$\\{y_{j}\\}_{j=1}^{n_{2}}$ are i.i.d. random samples according to the uniform
distribution $U(\Omega)$ on $\Omega$ and $U(\partial\Omega)$ on
$\partial\Omega$, respectively. Thanks to the implementation of automatic
differentiation, the empirical loss function (3) is easily computable and can
be effectively trained using first-order optimization methods such as SGD, as
well as more sophisticated second-order optimizers like L-BFGS.

In fact, the idea of using neural networks to solve PDEs can date back to the
last century [4]. Due to the rapid development of computational power and
algorithems, much attention has been drawn to revisiting the idea and various
methods involving neural networks to solve PDEs have been proposed. As the
most representative approach, PINNs have been applied successfully in varous
domains, including computational physics [5, 6, 7], inverse problem [8, 9, 10]
and quantitative finance [11, 12, 13]. Compared to the classical numerical
methods, PINNs method is mesh-less that can be adapted for solving high-
dimesional PDEs, like Hamilton-Jacobi-Bellman equation [14].

Despite of the remarkable sucess of PINNs for solving various types PDEs, they
may result in poor solutions due to the complex non-convex optimization
problems one needs to solve [15]. Compared to gradient descent, implicit
gradient descent works better in some multi-scale problems, which is shown in
[16] numerically. While the work [16] has offered a convergence analysis for
the IGD in the context of $L^{2}$ regression problems, the convergence of IGD
for PINNs remains an open question. In this paper, we aim to fill this gap.

###  2.1. Contributions

  * •

We prove the positive definiteness of the Gram matrices of PINNs for general
smooth activation functions under mild assumption on the samples. Moreover,
the conclusion can be generalized to various type PDEs.

  * •

For two-layer over-paramterized PINNs, We demenstrate that randomly
initialized IGD converges to a globally optimal solution at a linear
convergence rate. In contrast to the GD, the IGD possesses a different
training dynamic and the learning rate of IGD can be chosen independent of the
sample size and the smallest eigenvalue of the Gram matrix.

  * •

By utilizing the concentration inequality for the sum of independent random
variables that are sub-Weibull of order $\alpha>0$ (see the definition in the
notation), we can deduce that a width $m=\Omega(poly(n,\log(1/\delta)))$ is
sufficient. This is in contrast to the results in [17, 18, 19], where both
gradient descent for $L^{2}$ regression problems or PINNs require a width of
$m=\Omega(poly(n,1/\delta))$.

###  2.2. Related Work

Gradient Descent: It has been shown in [20] that training multilayer fully-
connected neural networks with a smooth activation function via gradient
descent is equivalent to performing a certain kernel method as the width of
every layer goes to infinity. Inspired by the celebrated result, several works
have demonstrated that gradient-based methods like gradient descent can
achieve zero training error despite the objective function is non-convex [20,
17, 18, 21, 22]. For the $L^{2}$ regression problems, [17] showed that for
randomly initialized and over-parametrized two-layer ReLU neural networks,
gradient descent converges to a globally optimal solution at a linear
convergence rate under the setting that no two inputs are parallel. And
similar results have been established in [18] for deep over-parameterized
neural networks with smooth activation functions. Both rely on the observation
that over-parameterization makes weights closed to their initializations for
all iterations, which yields the linear convergence.

PINNs: Various optimization methods are available for PINNs, like L-BFGS [5],
natural gradient descent [23], but none have been accompanied by convergence
analysis. [24] proved the global linear convergence of gradient descent in
training PINNs for second-order linear PDEs, but only focused on the gradient
flow and some assumptions are not verified. The work most relevant to ours is
[19], which derived the rigorous convergence analysis of gradient descent for
two-layer PINNs with $\text{ReLU}^{3}$ activation functions. Compared to [19]
for GD, IGD has a completely different training dynamic, which yields a free
choice for the learning rate and requires a new processing method. Moreover,
the required width of the two-layer neural network in [19] is of order
$poly(1/\delta)$, which is much worser than our result.

###  2.3. Notation

For $x\in\mathbb{R}^{d}$, we denote by $\|x\|_{2}$ the Euclidean norm of $x$.
Let $g:[0,\infty)\rightarrow[0,\infty)$ be a non-decreasing function with
$g(0)=0$. The g-Orlicz norm of a real-valued random variable $X$ is given by

$\|X\|_{g}:=\inf\\{t>0:\mathbb{E}[g\left(\frac{|X|}{t}\right)]\leq 1\\}.$

A random variabel $X$ is said to be sub-Weibull of order $\alpha>0$, denoted
as sub-Weill($\alpha$), if $\|X\|_{\psi_{\alpha}}<\infty$, where

$\psi_{\alpha}(x):=e^{x^{\alpha}}-1,\ for\ x\geq 0.$

Throughout the paper, We use boldface to represent vectors.

##  3\. Preliminaries

In this paper, in order to compare with the convergence analysis of gradient
descent in [19], we focus on the PDE with the same form:

$\displaystyle\frac{\partial u}{\partial
x_{0}}(\bm{x})-\sum\limits_{i=1}^{d}\frac{\partial^{2}u}{\partial
x_{i}^{2}}(\bm{x})=f(\bm{x}),\,\bm{x}\in(0,T)\times\Omega,$ (4) $\displaystyle
u(\bm{x})=g(\bm{x}),\
\bm{x}\in\\{0\\}\times\Omega\cup[0,T]\times\partial\Omega,$

where $\bm{x}=(x_{0},x_{1},\cdots,x_{d})\in\mathbb{R}^{d}$ and $x_{0}\in[0,T]$
is the time variable. In the following, we assume that $\|x\|_{2}\leq 1$ for
$x\in[0,T]\times\bar{\Omega}$ and $f,g$ are bounded continuous functions.

Moreover, we consider a two-layer neural network of the following form.

$u(\bm{x};\bm{w},\bm{a})=\frac{1}{\sqrt{m}}\sum\limits_{r=1}^{m}a_{r}\sigma(\bm{w}_{r}^{T}\bm{x}),$
(5)

where
$\bm{w}=(\bm{w}_{1}^{T},\cdots,\bm{w}_{m}^{T})^{T}\in\mathbb{R}^{m(d+1)}$,
$\bm{a}=(a_{1},\cdots,a_{m})^{T}\in\mathbb{R}^{m}$ and
$\bm{w}_{r}\in\mathbb{R}^{d+1}$ is the weight vector of the first layer,
$a_{r}$ is the output weight and $\sigma(\cdot)$ is the activation function
satisfying the following assumption.

######  Assumption 1.

There exists a constant $c>0$ such that $|\sigma(0)|\leq c$ and for any
$z,z^{{}^{\prime}}\in\mathbb{R}$,

$|\sigma^{(k)}(z)-\sigma^{(k)}(z^{{}^{\prime}})|\leq c|z-z^{{}^{\prime}}|,$
(6)

where $k\in\\{0,1,2,3\\}$. Moreover, $\sigma(\cdot)$ is analytic and is not a
polynomial function.

The assumption is satisfied for some general activation functions, like
softplus function $\sigma(z)=\log(1+e^{z})$, logistic function
$\sigma(z)=1/(1+e^{-z})$, hyperbolic tangent function
$\sigma(z)=(e^{z}-e^{-z})/(e^{z}+e^{-z})$ and so on. Throughout the paper, we
regard all parameters related to the activation functions as constants.

In the framework of PINNs, we focus on the empirical risk minimization
problem. Given training samples $\\{\bm{x}_{p}\\}_{p=1}^{n_{1}}$ and
$\\{\bm{y}_{j}\\}_{j=1}^{n_{2}}$ that are from interior and boundary
respectively, we aim to minimize

$\displaystyle L(\bm{w},\bm{a}):=$ (7)
$\displaystyle\sum\limits_{p=1}^{n_{1}}\frac{1}{2n_{1}}\left(\frac{\partial
u}{\partial
x_{0}}(\bm{x}_{p};\bm{w},\bm{a})-\sum\limits_{i=1}^{d}\frac{\partial^{2}u}{\partial
x_{i}^{2}}(\bm{x}_{p};\bm{w},\bm{a})-f(\bm{x}_{p})\right)^{2}$
$\displaystyle+\sum\limits_{j=1}^{n_{2}}\frac{\lambda}{2n_{2}}\left(u(\bm{y}_{j};\bm{w},\bm{a})-g(\bm{y}_{j})\right)^{2}.$

The gradient descent updates the weights by the following formulations:

$\displaystyle\bm{w}_{r}(k+1)$ $\displaystyle=\bm{w}_{r}(k)-\eta\frac{\partial
L(\bm{w}(k),\bm{a}(k))}{\partial\bm{w}_{r}},$ (8) $\displaystyle a_{r}(k+1)$
$\displaystyle=a_{r}(k)-\eta\frac{\partial L(\bm{w}(k),\bm{a}(k))}{\partial
a_{r}}$

for all $r\in[m]$ and $k\in\mathbb{N}$, where $\eta>0$ is the learning rate.

In contrast, the implicit gradient descent has a different updating procedure
for the weights:

$\displaystyle\bm{w}_{r}(k+1)$ $\displaystyle=\bm{w}_{r}(k)-\eta\frac{\partial
L(\bm{w}(k+1),\bm{a}(k+1))}{\partial\bm{w}_{r}},$ (9) $\displaystyle
a_{r}(k+1)$ $\displaystyle=a_{r}(k)-\eta\frac{\partial
L(\bm{w}(k+1),\bm{a}(k+1))}{\partial a_{r}}.$

In this paper, we consider the initialization that is same as the $L^{2}$
regression problem [2]:

$\bm{w}_{r}(0)\sim\mathcal{N}(0,\bm{I}_{d+1}),\,a_{r}(0)\sim
Unif(\\{-1,1\\}).$ (10)

For simplicity, we fix the second layer and apply implicit gradient descent to
optimize the first layer, i.e., only optimize $\bm{w}$ with

$\bm{w}(k+1)=\bm{w}(k)-\eta\nabla L(\bm{w}(k+1)).$ (11)

Note that the updating rule for $\bm{w}$ is equivalent to that

$\bm{w}(k+1)=\mathop{\arg\min}\limits_{\bm{w}}\frac{1}{2}\|\bm{w}-\bm{w}(k)\|_{2}^{2}+\eta
L(\bm{w}).$ (12)

##  4\. Main Results

In this section, we show initialized IGD converges to the global minimum at a
linear rate. Before presenting the results, we first simplify the notation.
For the residual of interior and boundary, we denote them by $s_{p}(\bm{w})$
and $h_{j}(\bm{w})$ respectively, i.e.,

$s_{p}(\bm{w})=\frac{1}{\sqrt{n_{1}}}(\frac{\partial u}{\partial
x_{0}}(\bm{x}_{p};\bm{w})-\sum\limits_{i=1}^{d}\frac{\partial^{2}u}{\partial
x_{i}^{2}}(\bm{x}_{p};\bm{w})-f(\bm{x}_{p}))$ (13)

and

$h_{j}(\bm{w})=\sqrt{\frac{\lambda}{n_{2}}}(u(\bm{y}_{j};\bm{w})-g(\bm{y}_{j})).$
(14)

Then the empirical loss function can be written as

$L(\bm{w}):=\frac{1}{2}(\|\bm{s}(\bm{w})\|_{2}^{2}+\|\bm{h}(\bm{w})\|_{2}^{2}),$
(15)

where

$\bm{s}(\bm{w})=(s_{1}(\bm{w}),\cdots,s_{n_{1}}(\bm{w}))^{T}\in\mathbb{R}^{n_{1}}$
(16)

and

$\bm{h}(\bm{w})=(h_{1}(\bm{w}),\cdots,h_{n_{2}}(\bm{w}))^{T}\in\mathbb{R}^{n_{2}}.$
(17)

At this time, we have

$\displaystyle\frac{\partial
L(\bm{w})}{\partial\bm{w}_{r}}=\sum\limits_{p=1}^{n_{1}}s_{p}(\bm{w})\frac{\partial
s_{p}(\bm{w})}{\partial\bm{w}_{r}}+\sum\limits_{j=1}^{n_{2}}h_{j}(\bm{w})\frac{\partial
h_{j}(\bm{w})}{\partial\bm{w}_{r}},$ (18)

which can be used to derive the recursive formula in the follwong lemma for
the IGD.

######  Lemma 1.

For the implicit gradient descent, we can deduce that for all
$k\in\mathbb{N}$,

$\displaystyle\begin{bmatrix}\bm{s}(\bm{w}(k+1))\\\
\bm{h}(\bm{w}(k+1))\end{bmatrix}$ (19) $\displaystyle=(\bm{I}+\eta
G(k+1))^{-1}\left(\begin{bmatrix}\bm{s}(\bm{w}(k))\\\
\bm{h}(\bm{w}(k))\end{bmatrix}-\begin{bmatrix}\bm{I}_{1}(k+1)\\\
\bm{I}_{2}(k+1)\end{bmatrix}\right),$

where $G(t)$ is the Gram matrice for the $t$-th ($t\in\mathbb{N}$) iteration,
defined as

$G(t)=\bm{D}(t)^{T}\bm{D}(t)$ (20)

with definition of $\bm{D}(t)$ as

$\left[\frac{\partial s_{1}(\bm{w}(t))}{\partial\bm{w}},\cdots,\frac{\partial
s_{n_{1}}(\bm{w}(t))}{\partial\bm{w}},\frac{\partial
h_{1}(\bm{w}(t))}{\partial\bm{w}},\cdots,\frac{\partial
h_{n_{2}}(\bm{w}(t))}{\partial\bm{w}}\right]$ (21)

and $\bm{I}_{1}(t)$, $\bm{I}_{2}(t)$ are residual terms, the $p$-th ($1\leq
p\leq n_{1}$) component of $\bm{I}_{1}(t)$ is defined as

$\int_{0}^{\eta}\langle\nabla L(\bm{w}(t)),\nabla s_{p}(\bm{w}(t)+\alpha\nabla
L(\bm{w}(t)))-\nabla s_{p}(\bm{w}(t))\rangle d\alpha,$ (22)

the $j$-th ($1\leq j\leq n_{2}$) component of $\bm{I}_{2}(t)$ is defined as

$\int_{0}^{\eta}\langle\nabla L(\bm{w}(t)),\nabla h_{j}(\bm{w}(t)+\alpha\nabla
L(\bm{w}(t)))-\nabla h_{j}(\bm{w}(t))\rangle d\alpha.$ (23)

Lemma 1 implies that the implicit gradient descent has a completely different
dynamic from the gradient descent, which admits the following iterative
formula.

$\begin{bmatrix}\bm{s}(\bm{w}(k+1))\\\
\bm{h}(\bm{w}(k+1))\end{bmatrix}=(I-\eta
G(k))\begin{bmatrix}\bm{s}(\bm{w}(k))\\\
\bm{h}(\bm{w}(k))\end{bmatrix}-\begin{bmatrix}\bm{\chi}(k)\\\
\tilde{\bm{\chi}}(k)\end{bmatrix},$ (24)

where $\bm{\chi}(k)$ and $\tilde{\bm{\chi}}(k)$ are residual terms that are
similar to $\bm{I}_{1}(k)$ and $\bm{I}_{2}(k)$. Thus, it requires a different
approach compared gradient descent.

Similar as the convergence analysis of gradient descent for the $L^{2}$
regression problems, we first prove the positive definiteness of the
expectation of the Gram matrix. Define matrix
$G^{\infty}\in\mathbb{R}^{(n_{1}+n_{2})\times(n_{1}+n_{2})}$ with
$G^{\infty}=\mathbb{E}_{\bm{w}(0)\sim\mathcal{N}(\bm{0},\bm{I})}G(0)$.

######  Lemma 2.

If no two samples in $\\{x_{p}\\}_{p=1}^{n_{1}}\cup\\{y_{j}\\}_{j=1}^{n_{2}}$
are parallel, then $G^{\infty}$ is strictly positive definite for activation
functions that satisfy assumption 1, i.e.,
$\lambda_{0}:=\lambda_{min}(G^{\infty})>0$.

######  Remark 1.

Due to the fact that two points in the high-dimensional space tend to be
parallel, we can consider the neural network with bias. Specifically, we can
replace the sample $\bm{x}$ with $(\bm{x}^{T},1)^{T}$, then the non-parallel
condition in Lemma 2 is equivalent to that no two samples are equal, which is
natural to hold.

Under over-parameterization, we can deduce that at random initialization,
$G(0)$ is closed enough to $G^{\infty}$, thus $G(0)$ has a lower bounded least
eigenvalue with high probability. Recall that in the setting of $L^{2}$
regression problem, the related random variables are all bounded, thus the
Hoeffding’s inequality or Bernstein’s inequality suffice. However, due to the
involvement of derivatives in the framework of PINNs, the random variables are
not bounded anymore. Fortunately, we can show that they are sub-Weibull of
order $\alpha>0$, thus the concentration inequality for the sum of sub-Weibull
variables is avaliable and we defer the detailed proof to the appendix.

######  Lemma 3.

If $m=\Omega(\frac{d^{4}}{\lambda_{0}^{2}}\log(\frac{n_{1}+n_{2}}{\delta}))$,
we have that with probability at least $1-\delta$,
$\|G(0)-G^{\infty}\|_{2}\leq\frac{\lambda_{0}}{4}$ and
$\lambda_{min}(G(0))\geq\frac{3}{4}\lambda_{0}$.

Over-parameterization not only ensures that $G(0)$ is strictly positive
definite, but also that $G(0)$ is stable under small perturbations. Formally,
the following lemma shows that if $\bm{w}$ is closed to the random
initialization $\bm{w}(0)$, the induced Gram matrix $G$ is closed to $G(0)$,
thus $G$ also has a lower bounded least eigenvalue.

######  Lemma 4.

If $\bm{w}_{1}(0),\cdots,\bm{w}_{m}(0)$ are i.i.d. generated from
$\mathcal{N}(0,\bm{I}_{d+1})$, then with probability at least $1-\delta$, the
following holds. For any set of weight vectors
$\bm{w}_{1},\cdots,\bm{w}_{m}\in\mathbb{R}^{d+1}$ that satisfy that for any
$r\in[m]$, $\|\bm{w}_{r}-\bm{w}_{r}(0)\|_{2}\leq R\leq 1$, then the induced
Gram matrix $G\in\mathbb{R}^{(n_{1}+n_{2})\times(n_{1}+n_{2})}$ satisfies

$\|G-G(0)\|_{2}\leq
CR\max\left(d^{2},\frac{d^{2}}{\sqrt{m}}\sqrt{\log(\frac{1}{\delta})},\frac{d^{2}}{m}(\log(\frac{1}{\delta}))^{2}\right)$
(25)

with a universal constant $C$.

With these preparations, in the following, we prove the convergence of IGD by
induction. In the proof, we first show that when $m$ is large enough, the
parameter $\bm{w}$ is closed to the random initialization $\bm{w}(0)$ in all
iterations. Then Lemma 4 implies that the corresponding Gram matrix has a
lower bounded least eigenvalue. Finally, bounding the residual terms in the
recursive formula of Lemma 1 yields the conclusion. Formally, our induction
hypothesis concerns the convergence of the empirical loss and the boundedness
of the weights.

Condition 1: At the $k$-th interation, we have $\|\bm{w}_{r}(k)\|_{2}\leq B$
for all $r\in[m]$ and

$L(k)\leq\left(1+\frac{\eta\lambda_{0}}{2}\right)^{-k}L(0),$ (26)

where $L(k)$ is an abbreviation of $L(\bm{w}(k))$ and $B>1$, is a constant to
be determined.

The assumption of the boundedness of $\|\bm{w}_{r}(k)\|_{2}$ is necessary, as
the derivatives appear in the loss function. Note that
$\|\bm{w}_{r}(k)\|_{2}\leq\|\bm{w}_{r}(k)-\bm{w}_{r}(0)\|_{2}+\|\bm{w}_{r}(0)\|_{2}$,
thus the assumtion holds directly from the facts that $\bm{w}_{r}(k)$ does not
go far away from $\bm{w}_{r}(0)$ under over-parameterization and
$\bm{w}_{r}(0)$ is bounded with high probability for all $r\in[m]$. The
boundedness of the weights and initial value also come from the utilization of
concentration inequality for sub-Weibull random variables and we put the
detailed proofs in Appendix.

######  Lemma 5.

With probability at least $1-\delta$,

$\|\bm{w}_{r}(0)\|_{2}^{2}\leq
C\left(d+\sqrt{d\log(\frac{m}{\delta})}+\log(\frac{m}{\delta})\right)$ (27)

holds for all $r\in[m]$ with a universal constant $C$.

######  Lemma 6.

With probability at least $1-\delta$, we have

$L(0)\leq
C\left(d^{2}\log(\frac{n_{1}+n_{2}}{\delta})+\frac{d^{2}}{m}(\log(\frac{n_{1}+n_{2}}{\delta}))^{2}\right),$
(28)

where $C$ is a universal constant.

From Lemma 5 and the fact that
$\|\bm{w}_{r}(k)\|_{2}\leq\|\bm{w}_{r}(k)-\bm{w}_{r}(0)\|_{2}+\|\bm{w}_{r}(0)\|_{2}$,
we can let

$B=\sqrt{C\left(d+\sqrt{d\log(\frac{m}{\delta})}+\log(\frac{m}{\delta})\right)}+1.$
(29)

With above proparations, we can derive the main conclusion in the induction.

######  Lemma 7.

If condition 1 holds for $k^{{}^{\prime}}=0,\cdots,k$, then we have for every
$r\in[m]$

$\displaystyle\|\bm{w}_{r}(k+1)-\bm{w}_{r}(0)\|_{2}$ (30)
$\displaystyle\leq\frac{C\eta}{\sqrt{m}}(\eta
L(0)+B^{2})\sqrt{L(0)}+\frac{CB^{2}}{\sqrt{m}\lambda_{0}}\sqrt{L(0)}.$

Lemma 7 implies that for large enough $m$, $\bm{w}_{r}(k+1)$ is closed enough
to $\bm{w}_{r}(0)$ for all $r\in[m]$. Therefore, combining the stability
property of the Gram matrix, i.e., Lemma 4, yields the following lemma.

######  Lemma 8.

When $m$ satisfies that

$\displaystyle m\geq$ $\displaystyle
Cd^{8}\left(\log(\frac{n_{1}+n_{2}}{\delta})\right.\max\left\\{d^{2}\log(\frac{n_{1}+n_{2}}{\delta}),\right.$
(31)
$\displaystyle\quad\left.\left.\frac{1}{\lambda_{0}^{2}}(\log(\frac{m}{\delta}))^{2}\right\\}\right),$

we have $\lambda_{min}(G(k+1))\geq\frac{\lambda_{0}}{2}$ under the event in
the Lemma 4, where $C$ is a universal constant. Moreover,
$\|\bm{w}_{r}(k+1)\|_{2}\leq B$ for all $r\in[m]$ under the event in the Lemma
5.

The induction is not yet complete, it remains only to prove that

$L(k+1)\leq\left(1+\frac{\eta\lambda_{0}}{2}\right)^{-(k+1)}L(0),$ (32)

which can be done by bounding the residual terms.

######  Lemma 9.

Under the setting of Lemma 7, we have

$\|\bm{I}_{1}(k+1)\|_{2}\leq\frac{C\eta^{2}\sqrt{n_{1}}B^{6}}{\sqrt{m}}L(k+1)$
(33)

and

$\|\bm{I}_{2}(k+1)\|_{2}\leq\frac{C\eta^{2}\sqrt{n_{2}}}{\sqrt{m}}L(k+1)$ (34)

with a universal constant $C$.

At this time, we arrive at our final conclusion.

######  Theorem 1.

Under the assumption 1 for the activation function and the non-parallel
condition in Lemma 1 for the training samples, we have that with probability
at least $1-\delta$ over the random initialization, the implicit gradient
descent algorithm satisfies that for all $k\in\mathbb{N}$

$L(k)\leq\left(1+\frac{\eta\lambda_{0}}{2}\right)^{-k}L(0),$ (35)

where

$\displaystyle
m=\Omega\left(d^{8}\log(\frac{n_{1}+n_{2}}{\delta})\max\left\\{\eta^{4}d^{2}\log(\frac{n_{1}+n_{2}}{\delta})\right.\right.,$
(36)
$\displaystyle\quad\left.\left.\frac{1}{\lambda_{0}^{2}}(\log(\frac{m}{\delta}))^{2},\frac{\eta^{2}(n_{1}+n_{2})d^{2}(\log(\frac{m}{\delta}))^{6}(\log(\frac{n_{1}+n_{2}}{\delta}))^{2}}{\lambda_{0}^{2}}\right\\}\right).$

######  Remark 2.

The conclusion (15) holds under the intersection of events in the Lemma 3,
Lemma 4, Lemma 5 and Lemma 6, which are independent of the iterations $k$.

##  5\. Conclusion

In this paper, we have demonstrated the convergence of implicit gradient
descent in training two-layer PINNs under suitable over-parameterization and
mild assumption on the training samples. Apart from the class of PDEs we are
considering, the methods in the paper can be naturally extended to a broader
class of PDEs. However, there remains some limitations of this work, for
instance, we do not take into account the error associated with the sub-
optimization problem during the implicit updating process, and the complexity
is also a factor that cannot be ignored.

## Appendix

##  6\. Proof of Lemma 1

###### Proof.

From the updating procedure of implicit gradient descent (IGD), i.e.,
$\bm{w}(k+1)=\bm{w}(k)-\eta\nabla L(\bm{w}(k+1))$, we have

$\displaystyle s_{p}(\bm{w}(k+1))-s_{p}(\bm{w}(k))$
$\displaystyle=s_{p}(\bm{w}(k+1))-s_{p}(\bm{w}(k+1)+\eta\nabla
L(\bm{w}(k+1)))$ $\displaystyle=-\int_{0}^{\eta}\langle\nabla
L(\bm{w}(k+1)),\nabla s_{p}(\bm{w}(k+1)+\alpha\nabla L(\bm{w}(k+1)))\rangle
d\alpha$ $\displaystyle=-\int_{0}^{\eta}\langle\nabla L(\bm{w}(k+1)),\nabla
s_{p}(\bm{w}(k+1))\rangle$ $\displaystyle\quad-\int_{0}^{\eta}\langle\nabla
L(\bm{w}(k+1)),\nabla s_{p}(\bm{w}(k+1)+\alpha\nabla L(\bm{w}(k+1)))-\nabla
s_{p}(\bm{w}(k+1))\rangle d\alpha$ $\displaystyle=-\eta\langle\nabla
L(\bm{w}(k+1)),\nabla s_{p}(\bm{w}(k+1))\rangle$
$\displaystyle\quad-\int_{0}^{\eta}\langle\nabla L(\bm{w}(k+1)),\nabla
s_{p}(\bm{w}(k+1)+\alpha\nabla L(\bm{w}(k+1)))-\nabla
s_{p}(\bm{w}(k+1))\rangle d\alpha$
$\displaystyle:=\bm{I}_{0}^{p}(k+1)-\bm{I}_{1}^{p}(k+1),$

where the second equality follows from the Newton-Leibniz formula.

Similarly, for the residual of the boundary, we have

$\displaystyle h_{j}(\bm{w}(k+1))-h_{j}(\bm{w}(k))$
$\displaystyle=-\eta\langle\nabla L(\bm{w}(k+1)),\nabla
s_{p}(\bm{w}(k+1))\rangle$ $\displaystyle\quad-\int_{0}^{\eta}\langle\nabla
L(\bm{w}(k+1)),\nabla h_{j}(\bm{w}(k+1)+\alpha\nabla L(\bm{w}(k+1)))-\nabla
h_{j}(\bm{w}(k+1))\rangle d\alpha$
$\displaystyle:=\bm{I}_{0}^{n_{1}+j}(k+1)-\bm{I}_{2}^{j}(k+1).$

We denote $\bm{I}_{0}(k+1)$ as the main term, which is
$(\bm{I}_{0}^{1}(k+1),\cdots,\bm{I}_{0}^{n_{1}}(k+1),\bm{I}_{0}^{n_{1}+1}(k+1),\cdots,\bm{I}_{0}^{n_{1}+n_{2}}(k+1))$,
and $\bm{I}_{1}(k+1)$ and $\bm{I}_{2}(k+1)$ as residual terms, which are
$(\bm{I}_{1}^{1}(k+1),\cdots,\bm{I}_{1}^{n_{1}}(k+1))$ and
$(\bm{I}_{2}^{1}(k+1),\cdots,\bm{I}_{2}^{n_{2}}(k+1))$ respectively.

For $\bm{I}_{0}^{p}(k+1),p\in[n_{1}]$, we can derive that

$\displaystyle\bm{I}_{0}^{p}(k+1)$ $\displaystyle=-\eta\langle\nabla
L(\bm{w}(k+1)),\nabla s_{p}(\bm{w}(k+1))\rangle$
$\displaystyle=-\eta\sum\limits_{r=1}^{m}\langle\frac{\partial
L(\bm{w}(k+1))}{\partial\bm{w}_{r}},\frac{\partial
s_{p}(\bm{w}(k+1))}{\partial\bm{w}_{r}}\rangle$
$\displaystyle=-\eta\sum\limits_{r=1}^{m}\langle\sum\limits_{i=1}^{n_{1}}s_{i}(\bm{w}(k+1))\frac{\partial
s_{i}(\bm{w}(k+1))}{\partial\bm{w}_{r}}+\sum\limits_{j=1}^{n_{2}}h_{j}(\bm{w}(k+1))\frac{\partial
h_{j}(\bm{w}(k+1))}{\partial\bm{w}_{r}},\frac{\partial
s_{p}(\bm{w}(k+1))}{\partial\bm{w}_{r}}\rangle$
$\displaystyle=-\eta\sum\limits_{i=1}^{n_{1}}\left(\sum\limits_{r=1}^{m}\langle\frac{\partial
s_{p}(\bm{w}(k+1))}{\partial\bm{w}_{r}},\frac{\partial
s_{i}(\bm{w}(k+1))}{\partial\bm{w}_{r}}\rangle\right)s_{i}(\bm{w}(k+1))-\eta\sum\limits_{j=1}^{n_{2}}\left(\sum\limits_{r=1}^{m}\langle\frac{\partial
s_{p}(\bm{w}(k+1))}{\partial\bm{w}_{r}},\frac{\partial
h_{j}(\bm{w}(k+1))}{\partial\bm{w}_{r}}\rangle\right)h_{j}(\bm{w}(k+1))$
$\displaystyle=-\eta[G(k+1)]_{p}\begin{bmatrix}\bm{s}(\bm{w}(k+1))\\\
\bm{h}(\bm{w}(k+1))\end{bmatrix},$

where $[G(k+1)]_{p}$ denote the $p$-th row of $G(k+1)$.

Similarly, we can deduce that for $j\in[n_{2}]$,

$\bm{I}_{0}^{n_{1}+j}(k+1)=-\eta[G(k+1)]_{n_{1}+j}\begin{bmatrix}\bm{s}(\bm{w}(k+1))\\\
\bm{h}(\bm{w}(k+1))\end{bmatrix}.$

Combining the results for $p\in[n_{1}]$ and $j\in[n_{2}]$ yields

$\bm{I}_{0}(k+1)=-\eta\begin{bmatrix}\bm{s}(\bm{w}(k+1))\\\
\bm{h}(\bm{w}(k+1))\end{bmatrix}.$

Therefore, we have that

$\begin{bmatrix}\bm{s}(\bm{w}(k+1))-\bm{s}(\bm{w}(k))\\\
\bm{h}(\bm{w}(k+1))-\bm{h}(\bm{w}(k))\end{bmatrix}=-\alpha
G(k+1)\begin{bmatrix}\bm{s}(\bm{w}(k+1))\\\
\bm{h}(\bm{w}(k+1))\end{bmatrix}-\begin{bmatrix}\bm{I}_{1}(k+1)\\\
\bm{I}_{2}(k+1)\end{bmatrix}.$

Finally, a simple vector transformation leads to the conclusion

$\begin{bmatrix}\bm{s}(\bm{w}(k+1))\\\
\bm{h}(\bm{w}(k+1))\end{bmatrix}=(\bm{I}+\eta
G(k+1))^{-1}\left(\begin{bmatrix}\bm{s}(\bm{w}(k))\\\
\bm{h}(\bm{w}(k))\end{bmatrix}-\begin{bmatrix}\bm{I}_{1}(k+1)\\\
\bm{I}_{2}(k+1)\end{bmatrix}\right).$ (37)

∎

##  7\. Proof of Lemma 2

###### Proof.

Let

$G(\bm{w})=D^{T}D,\quad D=[\frac{\partial
s_{1}}{\partial\bm{w}},\cdots,\frac{\partial
s_{n_{1}}}{\partial\bm{w}},\frac{\partial
h_{1}}{\partial\bm{w}},\cdots,\frac{\partial h_{n_{2}}}{\partial\bm{w}}],$

then $G^{\infty}=\mathbb{E}_{\bm{w}\sim\mathcal{N}(\bm{0},\bm{I})}G(\bm{w})$.

We denote
$\varphi(\bm{x};\bm{w})=\sigma^{{}^{\prime}}(\bm{w}^{T}\bm{x})w_{0}-\sigma^{{}^{\prime\prime}}(\bm{w}^{T}\bm{x})\|\bm{w}_{1}\|_{2}^{2}$,
where $\bm{w}=(w_{0},\bm{w}_{1}^{T})^{T}$,
$w_{0}\in\mathbb{R},\bm{w}_{1}\in\mathbb{R}^{d}$, then

$\frac{\partial
s_{p}(\bm{w})}{\partial\bm{w}_{r}}=\frac{1}{\sqrt{n}_{1}}\frac{a_{r}}{\sqrt{m}}\frac{\partial\varphi(\bm{x}_{p};\bm{w}_{r})}{\partial\bm{w}_{r}}.$

Similarly, we denote $\psi(\bm{y};\bm{w})=\sigma(\bm{w}^{T}\bm{y})$, then

$\frac{\partial
h_{j}(\bm{w})}{\partial\bm{w}_{r}}=\frac{1}{\sqrt{n}_{2}}\frac{a_{r}}{\sqrt{m}}\frac{\partial\psi(\bm{y}_{j},\bm{w}_{r})}{\partial\bm{w}_{r}}.$

With the notations, we can deduce that

$G_{p,j}^{\infty}=\left\\{\begin{aligned}
\frac{1}{n_{1}}\mathbb{E}_{\bm{w}\sim\mathcal{N}(\bm{0},\bm{I})}\langle\frac{\partial\varphi(\bm{x}_{p};\bm{w})}{\partial\bm{w}},\frac{\partial\varphi(\bm{x}_{j};\bm{w})}{\partial\bm{w}}\rangle&,&1\leq
p\leq n_{1},1\leq j\leq n_{1},\\\
\frac{1}{\sqrt{n_{1}n_{2}}}\mathbb{E}_{\bm{w}\sim\mathcal{N}(\bm{0},\bm{I})}\langle\frac{\partial\varphi(\bm{x}_{p};\bm{w})}{\partial\bm{w}},\frac{\partial\psi(\bm{y}_{j};\bm{w})}{\partial\bm{w}}\rangle&,&1\leq
p\leq n_{1},n_{1}+1\leq j\leq n_{1}+n_{2},\\\
\frac{1}{n_{2}}\mathbb{E}_{\bm{w}\sim\mathcal{N}(\bm{0},\bm{I})}\langle\frac{\partial\psi(\bm{y}_{p};\bm{w})}{\partial\bm{w}},\frac{\partial\psi(\bm{y}_{j};\bm{w})}{\partial\bm{w}}\rangle&,&n_{1}+1\leq
p\leq n_{1}+n_{2},n_{1}+1\leq j\leq n_{1}+n_{2}.\end{aligned}\right.$

The proof of this lemma requires tools from functional analysis. Let
$\mathcal{H}$ be a Hilbert space of integrable $(d+1)$-dimensional vector
fields on $\mathbb{R}^{d+1}$, i.e., $f\in\mathcal{H}$ if
$\mathbb{E}_{\bm{w}\sim\mathcal{N}(\bm{0},\bm{I})}[\|f(\bm{w})\|_{2}^{2}]<\infty$.
The inner product for any two elements $f,g$ in $\mathcal{H}$ is
$\mathbb{E}_{\bm{w}\sim\mathcal{N}(\bm{0},\bm{I})}[\langle
f(\bm{w}),g(\bm{w})\rangle]$. Thus, proving $G^{\infty}$ is strictly positive
definite is equivalent to show
$\frac{\partial\varphi(\bm{x}_{1};\bm{w})}{\partial\bm{w}},\cdots,\frac{\partial\varphi(\bm{x}_{n_{1}};\bm{w})}{\partial\bm{w}},\frac{\partial\psi(\bm{y}_{1};\bm{w})}{\partial\bm{w}},\cdots,\frac{\partial\psi(\bm{y}_{n_{2}};\bm{w})}{\partial\bm{w}}\in\mathcal{H}$
are linearly independent. Suppose that there are
$\alpha_{1},\cdots,\alpha_{n_{1}},\beta_{1},\cdots,\beta_{n_{2}}\in\mathbb{R}$
such that

$\alpha_{1}\frac{\partial\varphi(\bm{x}_{1};\bm{w})}{\partial\bm{w}}+\cdots+\alpha_{n_{1}}\frac{\partial\varphi(\bm{x}_{n_{1}};\bm{w})}{\partial\bm{w}}+\beta_{1}\frac{\partial\psi(\bm{y}_{1};\bm{w})}{\partial\bm{w}}+\cdots+\beta_{n_{2}}\frac{\partial\psi(\bm{y}_{n_{2}};\bm{w})}{\partial\bm{w}}=0\
in\ \mathcal{H}.$

This implies that

$\alpha_{1}\frac{\partial\varphi(\bm{x}_{1};\bm{w})}{\partial\bm{w}}+\cdots+\alpha_{n_{1}}\frac{\partial\varphi(\bm{x}_{n_{1}};\bm{w})}{\partial\bm{w}}+\beta_{1}\frac{\partial\psi(\bm{y}_{1};\bm{w})}{\partial\bm{w}}+\cdots+\beta_{n_{2}}\frac{\partial\psi(\bm{y}_{n_{2}};\bm{w})}{\partial\bm{w}}=0$
(38)

holds for all $\bm{w}\in\mathbb{R}^{d+1}$, as $\sigma$ is smooth.

We first compute the derivatives of $\varphi$ and $\psi$. Differentiating
$\psi(\bm{y};\bm{w})$ $k$ times with respect to $\bm{w}$, we have

$\frac{\partial^{k}\psi(\bm{y};\bm{w})}{\partial\bm{w}^{k}}=\sigma^{(k)}(\bm{w}^{T}\bm{y})\bm{y}^{\otimes(k)},$

where $\otimes$ denote tensor product.

For $\varphi(\bm{x};\bm{w})$, let
$\varphi_{0}(\bm{x};\bm{w})=\sigma^{{}^{\prime}}(\bm{w}^{T}\bm{x})w_{0}$,
$\varphi_{i}(\bm{x};\bm{w})=\sigma^{{}^{\prime\prime}}(\bm{w}^{T}\bm{x})w_{i}^{2}$
for $1\leq i\leq d$, then

$\varphi(\bm{x};\bm{w})=\varphi_{0}(\bm{x};\bm{w})-\sum\limits_{i=1}^{d}\varphi_{i}(\bm{x};\bm{w}).$

Differentiating $\varphi_{0}(\bm{x};\bm{w})$ $k$ times with respect to
$\bm{w}$, we have

$\frac{\partial^{k}\varphi_{0}(\bm{x};\bm{w})}{\partial\bm{w}^{k}}=\sigma^{(k+1)}(\bm{w}^{T}\bm{x})w_{0}\bm{x}^{\otimes(k)}+k\sigma^{(k)}(\bm{w}^{T}\bm{x})\bm{e}_{0}\otimes\bm{x}^{\otimes(k-1)},$

where $\bm{e}_{0}=(1,0,\cdots,0)\in\mathbb{R}^{d+1}$.

Similarly, for $\varphi_{i}(\bm{x};\bm{w})$, $1\leq i\leq d$, we have

$\frac{\partial^{k}\varphi_{i}(\bm{x};\bm{w})}{\partial\bm{w}^{k}}=\sigma^{(k+2)}(\bm{w}^{T}\bm{x})w_{i}^{2}\bm{x}^{\otimes(k)}+C_{k}^{1}\sigma^{(k+1)}(\bm{w}^{T}\bm{x})2w_{i}\bm{e}_{i}\otimes\bm{x}^{\otimes(k-1)}+C_{k}^{2}\sigma^{(k)}(\bm{w}^{T}\bm{x})2\bm{e}_{i}^{\otimes(2)}\otimes\bm{x}^{\otimes(k-2)},$

where $\bm{e}_{i}\in\mathbb{R}^{d+1}$, is a vector where all other components
are $0$, and only the $(i+1)$-th component is $1$.

Combining the results for the derivatives for
$\varphi_{0}(\bm{x};\bm{w}),\cdots,\varphi_{d}(\bm{x};\bm{w})$ yields that

$\displaystyle\frac{\partial^{k}\varphi(\bm{x};\bm{w})}{\partial\bm{w}^{k}}$
$\displaystyle=\frac{\partial^{k}\varphi_{0}(x;\bm{w})}{\partial\bm{w}^{k}}-\sum\limits_{i=1}^{d}\frac{\partial^{k}\varphi_{i}(\bm{x};\bm{w})}{\partial\bm{w}^{k}}$
$\displaystyle=\sigma^{(k+1)}(\bm{w}^{T}\bm{x})w_{0}\bm{x}^{\otimes(k)}+k\sigma^{(k)}(\bm{w}^{T}\bm{x})\bm{e}_{0}\otimes\bm{x}^{\otimes(k-1)}$
$\displaystyle\quad-\sum\limits_{i=1}^{d}\left(\sigma^{(k+2)}(\bm{w}^{T}\bm{x})w_{i}^{2}\bm{x}^{\otimes(k)}+C_{k}^{1}\sigma^{(k+1)}(\bm{w}^{T}\bm{x})2w_{i}\bm{e}_{i}\otimes\bm{x}^{\otimes(k-1)}+C_{k}^{2}\sigma^{(k)}(\bm{w}^{T}\bm{x})2\bm{e}_{i}^{\otimes(2)}\otimes\bm{x}^{\otimes(k-2)}\right).$

Note that when no two points in
$\\{\bm{x}_{1},\cdots,\bm{x}_{n_{1}},\bm{y}_{1},\cdots,\bm{y}_{n_{2}}\\}$ are
parallel,

$\bm{x}_{1}^{\otimes(n_{1}+n_{2}-1)},\cdots,\bm{x}_{n_{1}}^{\otimes(n_{1}+n_{2}-1)},\bm{y}_{1}^{\otimes(n_{1}+n_{2}-1)},\cdots,\bm{y}_{n_{2}}^{\otimes(n_{1}+n_{2}-1)}$

are independent (see Lemma G.6 in [18]). It motivates us to differentiate both
sides in (38) $k-1$ times for $\bm{w}$ with $k=n_{1}+n_{2}+1$, then we have

$\alpha_{1}\frac{\partial^{k}\varphi(\bm{x}_{1};\bm{w})}{\partial\bm{w}^{k}}+\cdots+\alpha_{n_{1}}\frac{\partial^{k}\varphi(\bm{x}_{n_{1}};\bm{w})}{\partial\bm{w}^{k}}+\beta_{1}\frac{\partial^{k}\psi(\bm{y}_{1};\bm{w})}{\partial\bm{w}^{k}}+\cdots+\beta_{n_{2}}\frac{\partial^{k}\psi(\bm{y}_{n_{2}};\bm{w})}{\partial\bm{w}^{k}}=0.$

Since

$\frac{\partial^{(n_{1}+n_{2}+1)}\psi(\bm{y}_{j};\bm{w})}{\partial\bm{w}^{(n_{1}+n_{2}+1)}}=\sigma^{(n_{1}+n_{2}+1)}(\bm{w}^{T}\bm{y}_{j})\bm{y}_{j}^{\otimes(n_{1}+n_{2}+1)},$

we can deduce that for any $j\in[n_{2}]$ and $\bm{w}\in\mathbb{R}^{d+1}$,

$\beta_{j}\sigma^{(n_{1}+n_{2}+1)}(\bm{w}^{T}\bm{y}_{j})\bm{y}_{j}^{\otimes(2)}=0.$

Now, we can choose a $\bm{w}$ such that
$\sigma^{(n_{1}+n_{2}+1)}(\bm{w}^{T}\bm{y}_{j})\neq 0$, thus

$\beta_{j}\sigma^{(n_{1}+n_{2}+1)}(\bm{w}^{T}\bm{y}_{j})\|\bm{y}_{j}\|_{2}^{2}=Trace(\beta_{j}\sigma^{(n_{1}+n_{2}+1)}(\bm{w}^{T}\bm{y}_{j})\bm{y}_{j}^{\otimes(2)})=0,$

which implies $\beta_{j}=0$ and then it holds for all $j\in[n_{2}]$.

Similarly, for $\alpha_{i}$, $i\in[n_{1}]$, we have

$\displaystyle\alpha_{i}[\sigma^{(k+1)}(\bm{w}^{T}\bm{x}_{i})w_{0}\bm{x}_{i}^{\otimes(2)}+k\sigma^{(k)}(\bm{w}^{T}\bm{x}_{i})\bm{e}_{0}\otimes\bm{x}_{i}$
$\displaystyle\quad-\sum\limits_{j=1}^{d}\left(\sigma^{(k+2)}(\bm{w}^{T}\bm{x}_{i})w_{j}^{2}\bm{x}_{i}^{\otimes(2)}+C_{k}^{1}\sigma^{(k+1)}(\bm{w}^{T}\bm{x}_{i})2w_{j}\bm{e}_{j}\otimes\bm{x}_{i}+C_{k}^{2}\sigma^{(k)}(\bm{w}^{T}\bm{x}_{i})2\bm{e}_{j}^{\otimes(2)}\right)]=0.$

For fixed $i$, denote $\bm{x}_{i}=(x_{i0},\bm{x}_{i1}^{T})^{T}$ with
$x_{i0}\in\mathbb{R}$ and $\bm{x}_{i1}\in\mathbb{R}^{d}$. We consider two
cases: (1) $\bm{x}_{i1}\neq 0$; (2) $\bm{x}_{i1}=0$.

In the case(1), we can let $w_{0}=0$, thus for $k=n_{1}+n_{2}+1$,

$\alpha_{i}\left[k\sigma^{(k)}(\bm{w}^{T}\bm{x}_{i})\bm{e}_{0}\otimes\bm{x}_{i}-\sum\limits_{j=1}^{d}\left(\sigma^{(k+2)}(\bm{w}^{T}\bm{x}_{i})w_{j}^{2}\bm{x}_{i}^{\otimes(2)}+C_{k}^{1}\sigma^{(k+1)}(\bm{w}^{T}\bm{x}_{i})2w_{j}\bm{e}_{j}\otimes\bm{x}_{i}+C_{k}^{2}\sigma^{(k)}(\bm{w}^{T}\bm{x}_{i})2\bm{e}_{j}^{\otimes(2)}\right)\right]=0,$

which means the trace is $0$, i.e.,

$\alpha_{i}\left[k\sigma^{(k)}(\bm{w}^{T}\bm{x}_{i})x_{i,0}-\sum\limits_{j=1}^{d}\left(\sigma^{(k+2)}(\bm{w}^{T}\bm{x}_{i})w_{j}^{2}\|\bm{x}_{i}\|_{2}^{2}+C_{k}^{1}\sigma^{(k+1)}(\bm{w}^{T}\bm{x}_{i})2w_{j}\bm{x}_{ij}+C_{k}^{2}\sigma^{(k)}(\bm{w}^{T}\bm{x}_{i})2\right)\right]=0.$

Rearranging yields that

$\alpha_{i}\left[k\sigma^{(k)}(w^{T}\bm{x}_{i})\bm{x}_{i0}-\left(\sigma^{(k+2)}(\bm{w}^{T}\bm{x}_{i})\|w_{1}\|_{2}^{2}\|\bm{x}_{i}\|_{2}^{2}+2C_{k}^{1}\sigma^{(k+1)}(\bm{w}^{T}\bm{x}_{i})w_{1}^{T}\bm{x}_{i1}+2C_{k}^{2}\sigma^{(k)}(\bm{w}^{T}\bm{x}_{i})\right)\right]=0.$

Now, we can set $\bm{w}_{1}^{T}\bm{x}_{i1}=c$ such that $\sigma^{(k+1)}(c)\neq
0$. As $\bm{w}^{T}\bm{x}_{i}=\bm{w_{1}}^{T}\bm{x}_{i1}=c$, we have

$\alpha_{i}\left[k\sigma^{(k)}(c)\bm{x}_{i,0}-\left(\sigma^{(k+2)}(c)\|\bm{w}_{1}\|_{2}^{2}\|\bm{x}_{i}\|_{2}^{2}+2C_{k}^{1}\sigma^{(k+1)}(c)c+2C_{k}^{2}\sigma^{(k)}(c)\right)\right]=0.$

Note that the only variable in above equation is $\bm{w}_{1}$ and in the
hyperplane $\\{\bm{w}_{1}:\bm{w}_{1}^{T}\bm{x}_{i,1}=c\\}$,
$\|\bm{w}_{1}\|_{2}$ can tend to be infinite, thus $\alpha_{i}=0$.

In the case(2), we have that

$\alpha_{i}\left[\sigma^{(k+1)}(\bm{w}^{T}\bm{x}_{i})w_{0}\bm{x}_{i}^{\otimes(2)}+k\sigma^{(k)}(\bm{w}^{T}\bm{x}_{i})\bm{e}_{0}\otimes\bm{x}_{i}\\\
-\sum\limits_{j=1}^{d}C_{k}^{2}\sigma^{(k)}(\bm{w}^{T}\bm{x}_{i})2\bm{e}_{j}^{\otimes(2)}\right]=0.$

From the observation of the $(j,j)$-th component of the matrix with $j\geq 2$,
we have that

$\alpha_{i}(-C_{k}^{2}\sigma^{(k)}(w^{T}\bm{x}_{i})2)=-2\alpha_{i}C_{k}^{2}\sigma^{(k)}(w_{0}\bm{x}_{i0})=0.$

Then, taking a $w_{0}$ such that $\sigma^{(k)}(w_{0}x_{i0})\neq 0$ yields the
conclusion. ∎

For the sake of readability, we present the concentration ineuqality of sum of
independent sub-Weibull random variables before the proof of remaining
conclusions.

Recall that for given random variable $X$, the $\psi_{\alpha}$ norm of $X$ is
given by

$\|X\|_{\psi_{\alpha}}:=\inf\\{t>0:\mathbb{E}[\psi_{\alpha}\left(\frac{|X|}{t}\right)]\leq
1\\},$

where $\psi_{\alpha}(x)=e^{x^{\alpha}}-1$ for $x\geq 0$.

Thus, $\|\cdot\|_{\psi_{\alpha}}$ is a norm for $\alpha\geq 1$ and a quasi-
norm for $0\leq\alpha<1$. Moreover,

$\|X+Y\|_{\psi_{\alpha}}\leq 2(\|X\|_{\psi_{\alpha}}+\|Y\|_{\psi_{\alpha}}).$

In the following, we may frequently use the following conclusion that for
$X\sim\mathcal{N}(0,1)$, we have

$\|X\|_{\psi_{2}}\leq C,\|X^{2}\|_{\psi_{1}}\leq\|X\|_{\psi_{2}}^{2}\leq
C^{2},\|X^{4}\|_{\psi_{\frac{1}{2}}}\leq C^{4},$

where $C$ is a universal constant.

######  Lemma 10 (Theorem 3.1 in [25]).

If $X_{1},\cdots,X_{n}$ are independent mean zero random variables with
$\|X_{i}\|_{\psi_{\alpha}}<\infty$ for all $1\leq i\leq n$ and some
$\alpha>0$, then for any vector $a=(a_{1},\cdots,a_{n})\in\mathbb{R}^{n}$, the
following holds ture:

$P(|\sum\limits_{i=1}^{n}a_{i}X_{i}|\geq
2eC(\alpha)\|b\|_{2}\sqrt{t}+2eL_{n}^{*}(\alpha)t^{1/\alpha}\|b\|_{\beta(\alpha)})\leq
2e^{-t},\ for\ all\ t\geq 0,$

where
$b=(a_{1}\|X_{1}\|_{\psi_{\alpha}},\cdots,a_{n}\|X_{n}\|_{\psi_{\alpha}})\in\mathbb{R}^{n}$,

$C(\alpha):=\max\\{\sqrt{2},2^{1/\alpha}\\}\left\\{\begin{aligned}
\sqrt{8}(2\pi)^{1/4}e^{1/24}(e^{2/e}/\alpha)^{1/\alpha}&,&if\ \alpha<1,\\\
4e+2(\log 2)^{1/\alpha}&,&if\ \alpha\geq 1.\end{aligned}\right.$

and for $\beta(\alpha)=\infty$ when $\alpha\geq 1$ and
$\beta(\alpha)=\alpha/(\alpha-1)$ when $\alpha>1$,

$L_{n}(\alpha):=\frac{4^{1/\alpha}}{\sqrt{2}\|b\|_{2}}\times\left\\{\begin{aligned}
&\|b\|_{\beta(\alpha)},&if\ \alpha<1,\\\
&4e\|b\|_{\beta(\alpha)}/C(\alpha),&if\alpha\geq 1.\end{aligned}\right.$

and $L^{*}_{n}(\alpha)=L_{n}(\alpha)C(\alpha)\|b\|_{2}/\|b\|_{\beta(\alpha)}$.

##  8\. Proof of Lemma 3

###### Proof.

Recall that

$\frac{\partial
s_{p}(\bm{w})}{\partial\bm{w}_{r}}=\frac{a_{r}}{\sqrt{mn_{1}}}(\sigma^{{}^{\prime\prime}}(\bm{w}^{T}x_{p})w_{r0}\bm{x}_{p}+\sigma^{{}^{\prime}}(\bm{w}^{T}\bm{x}_{p})\begin{pmatrix}1\\\
\bm{0}_{d}\end{pmatrix}-\sigma^{{}^{\prime\prime\prime}}(\bm{w}_{r}^{T}\bm{x}_{p})\|\bm{w}_{r1}\|_{2}^{2}\bm{x}_{p}-2\sigma^{{}^{\prime\prime}}(\bm{w}_{r}^{T}\bm{x}_{p})\begin{pmatrix}0\\\
\bm{w}_{r1}\end{pmatrix})$

and

$\frac{\partial
h_{j}(\bm{w})}{\partial\bm{w}_{r}}=\frac{a_{r}\sqrt{\lambda}}{\sqrt{mn_{2}}}\sigma^{{}^{\prime}}(\bm{w}_{r}^{T}\bm{y}_{j})\bm{y}_{j}.$

As $\|G(0)-G^{\infty}\|_{2}\leq\|G(0)-G^{\infty}\|_{F}$, it suffices to bound
each element of $G(0)-G^{\infty}$, which is of the form

$\sum\limits_{r=1}^{m}\langle\frac{\partial
s_{p}(\bm{w})}{\partial\bm{w}_{r}},\frac{\partial
s_{j}(\bm{w})}{\partial\bm{w}_{r}}\rangle-\mathbb{E}_{\bm{w}}\sum\limits_{r=1}^{m}\langle\frac{\partial
s_{p}(\bm{w})}{\partial\bm{w}_{r}},\frac{\partial
s_{j}(\bm{w})}{\partial\bm{w}_{r}}\rangle$ (39)

or

$\sum\limits_{r=1}^{m}\langle\frac{\partial
s_{p}(\bm{w})}{\partial\bm{w}_{r}},\frac{\partial
h_{j}(\bm{w})}{\partial\bm{w}_{r}}\rangle-\mathbb{E}_{\bm{w}}\sum\limits_{r=1}^{m}\langle\frac{\partial
s_{p}(\bm{w})}{\partial\bm{w}_{r}},\frac{\partial
h_{j}(\bm{w})}{\partial\bm{w}_{r}}\rangle$ (40)

or

$\sum\limits_{r=1}^{m}\langle\frac{\partial
h_{p}(\bm{w})}{\partial\bm{w}_{r}},\frac{\partial
h_{j}(\bm{w})}{\partial\bm{w}_{r}}\rangle-\mathbb{E}_{\bm{w}}\sum\limits_{r=1}^{m}\langle\frac{\partial
h_{p}(\bm{w})}{\partial\bm{w}_{r}},\frac{\partial
h_{j}(\bm{w})}{\partial\bm{w}_{r}}\rangle.$ (41)

For the first form (39), let

$Y_{r}(i)=\sigma^{{}^{\prime\prime}}(\bm{w}_{r}(0)^{T}\bm{x}_{i})w_{r0}(0)\bm{x}_{i}+\sigma^{{}^{\prime}}(\bm{w}_{r}(0)^{T}\bm{x}_{i})\begin{pmatrix}1\\\
\bm{0}_{d}\end{pmatrix}-\sigma^{{}^{\prime\prime\prime}}(\bm{w}_{r}(0)^{T}\bm{x}_{i})\|w_{r1}(0)\|_{2}^{2}\bm{x}_{i}-2\sigma^{{}^{\prime\prime}}(\bm{w}_{r}(0)^{T}\bm{x}_{i})\begin{pmatrix}0\\\
\bm{w}_{r1}(0)\end{pmatrix}$

and

$X_{r}(ij)=\langle Y_{r}(i),Y_{r}(j)\rangle,$

then

$\sum\limits_{r=1}^{m}\langle\frac{\partial
s_{p}(\bm{w})}{\partial\bm{w}_{r}},\frac{\partial
s_{j}(\bm{w})}{\partial\bm{w}_{r}}\rangle-\mathbb{E}_{\bm{w}}\sum\limits_{r=1}^{m}\langle\frac{\partial
s_{p}(\bm{w})}{\partial\bm{w}_{r}},\frac{\partial
s_{j}(\bm{w})}{\partial\bm{w}_{r}}\rangle=\frac{1}{n_{1}}\sum\limits_{r=1}^{m}(X_{r}(ij)-\mathbb{E}X_{r}(ij)).$

Note that $|X_{r}(ij)|\lesssim 1+\|\bm{w}_{r}(0)\|_{2}^{4}$, thus

$\|X_{r}(ij)\|_{\psi_{\frac{1}{2}}}\lesssim
1+\left\|\|\bm{w}_{r}(0)\|_{2}^{4}\right\|_{\psi_{\frac{1}{2}}}\lesssim
1+\left\|\|\bm{w}_{r}(0)\|_{2}^{2}\right\|_{\psi_{1}}^{2}\lesssim d^{2}.$

For the centered random variable, the property of $\psi_{\frac{1}{2}}$ quasi-
norm implies that

$\|X_{r}(ij)-\mathbb{E}[X_{r}(ij)]\|_{\psi_{\frac{1}{2}}}\lesssim\|X_{r}(ij)\|_{\psi_{\frac{1}{2}}}+\|\mathbb{E}[X_{r}(ij)]\|_{\psi_{\frac{1}{2}}}\lesssim
d^{2}.$

Therefore, applying Lemma 10 yields that with probability at least $1-\delta$,

$|\sum\limits_{r=1}^{m}\frac{1}{m}(X_{r}(ij)-\mathbb{E}[X_{r}(ij)])|\lesssim\frac{d^{2}}{\sqrt{m}}\sqrt{\log(\frac{1}{\delta})}+\frac{d^{2}}{m}(\log(\frac{1}{\delta}))^{2},$

which means

$|\sum\limits_{r=1}^{m}\langle\frac{\partial
s_{i}(\bm{w})}{\partial\bm{w}_{r}},\frac{\partial
s_{j}(\bm{w})}{\partial\bm{w}_{r}}\rangle-\mathbb{E}_{\bm{w}}\sum\limits_{r=1}^{m}\langle\frac{\partial
s_{i}(\bm{w})}{\partial\bm{w}_{r}},\frac{\partial
s_{j}(\bm{w})}{\partial\bm{w}w_{r}}\rangle|\lesssim\frac{d^{2}}{n_{1}\sqrt{m}}\sqrt{\log(\frac{1}{\delta})}+\frac{d^{2}}{n_{1}m}(\log(\frac{1}{\delta}))^{2}.$

For the second form (40), we only need to apply Lemma 10 for random variables
with finite $\psi_{1}$ norm, which yields that with probability at least
$1-\delta$,

$|\sum\limits_{r=1}^{m}\langle\frac{\partial
s_{i}(\bm{w})}{\partial\bm{w}_{r}},\frac{\partial
h_{j}(\bm{w})}{\partial\bm{w}_{r}}\rangle-\mathbb{E}_{\bm{w}}\sum\limits_{r=1}^{m}\langle\frac{\partial
s_{i}(\bm{w})}{\partial\bm{w}_{r}},\frac{\partial
h_{j}(\bm{w})}{\partial\bm{w}_{r}}\rangle|\lesssim\frac{d}{\sqrt{n_{1}n_{2}}\sqrt{m}}\sqrt{\log(\frac{1}{\delta})}+\frac{d}{\sqrt{n_{1}n_{2}}m}\log(\frac{1}{\delta}).$

Similarly, for the third form (41), applying Lemma 10 for random variables
with finite $\psi_{2}$ norm suffices. Thus, we have that with probability at
least $1-\delta$,

$|\sum\limits_{r=1}^{m}\langle\frac{\partial
h_{i}(\bm{w})}{\partial\bm{w}_{r}},\frac{\partial
h_{j}(\bm{w})}{\partial\bm{w}_{r}}\rangle-\mathbb{E}_{\bm{w}}\sum\limits_{r=1}^{m}\langle\frac{\partial
h_{i}(\bm{w})}{\partial\bm{w}_{r}},\frac{\partial
h_{j}(\bm{w})}{\partial\bm{w}_{r}}\rangle|\lesssim\frac{1}{n_{2}\sqrt{m}}\sqrt{\log(\frac{1}{\delta})}.$

Combining above results for the three forms, we can deduce that with
probability at least $1-\delta$,

$\displaystyle\|G(0)-G^{\infty}\|_{2}^{2}$
$\displaystyle\leq\|G(0)-G^{\infty}\|_{F}^{2}$
$\displaystyle\lesssim\frac{d^{4}}{m}\log(\frac{n_{1}+n_{2}}{\delta})+\frac{d^{4}}{m^{2}}(\log(\frac{n_{1}+n_{2}}{\delta}))^{4}$
$\displaystyle\lesssim\frac{d^{4}}{m}\log(\frac{n_{1}+n_{2}}{\delta}).$

Thus when
$\sqrt{\frac{d^{4}}{m}\log(\frac{n_{1}+n_{2}}{\delta})}\lesssim\frac{\lambda_{0}}{4}$,
i.e.,

$m=\Omega(\frac{d^{4}}{\lambda_{0}^{2}}\log(\frac{n_{1}+n_{2}}{\delta})),$

we have $\lambda_{min}(G(0))\geq\frac{3}{4}\lambda_{0}$.

∎

##  9\. Proof of Lemma 4

###### Proof.

As $\|G-G(0)\|_{2}\leq\|G-G(0)\|_{F}$, it suffices to bound each element of
$|G-G(0)|$.

For $i\in[1,n_{1}]$ and $j\in[1,n_{1}]$, we have

$\displaystyle|G_{ij}-G(0)_{ij}|$
$\displaystyle=|\sum\limits_{r=1}^{m}\langle\frac{\partial
s_{i}(\bm{w})}{\partial\bm{w}_{r}},\frac{\partial
s_{j}(\bm{w})}{\partial\bm{w}_{r}}\rangle-\langle\frac{\partial
s_{i}(\bm{w}(0))}{\partial\bm{w}_{r}},\frac{\partial
s_{j}(\bm{w}(0))}{\partial\bm{w}_{r}}\rangle|$ $\displaystyle\lesssim
R\frac{1}{n_{1}}\frac{1}{m}\sum\limits_{r=1}^{m}(\|\bm{w}_{r}(0)\|_{2}^{4}+\|\bm{w}_{r}(0)\|_{2}^{3}+\|\bm{w}_{r}(0)\|_{2}^{2}+\|\bm{w}_{r}(0)\|_{2}+1)$
$\displaystyle\lesssim
R\frac{1}{n_{1}}\frac{1}{m}\sum\limits_{r=1}^{m}(\|\bm{w}_{r}(0)\|_{2}^{4}+1),$

where the first inequality is due to $R\leq 1$ and the second inequality
follows from the Young’s inequality.

For $i\in[1,n_{1}]$ and $j\in[n_{1}+1,n_{1}+n_{2}]$, we have

$\displaystyle|G_{ij}-G(0)_{ij}|$
$\displaystyle=|\sum\limits_{r=1}^{m}\langle\frac{\partial
s_{i}(\bm{w})}{\partial\bm{w}_{r}},\frac{\partial
h_{j}(\bm{w})}{\partial\bm{w}_{r}}\rangle-\langle\frac{\partial
s_{i}(\bm{w}(0))}{\partial\bm{w}_{r}},\frac{\partial
h_{j}(\bm{w}(0))}{\partial\bm{w}_{r}}\rangle|$ $\displaystyle\lesssim
R\frac{1}{\sqrt{n_{1}n_{2}}}\frac{1}{m}\sum\limits_{r=1}^{m}(\|\bm{w}_{r}(0)\|_{2}^{2}+\|\bm{w}_{r}(0)\|_{2}+1)$
$\displaystyle\lesssim
R\frac{1}{\sqrt{n_{1}n_{2}}}\frac{1}{m}\sum\limits_{r=1}^{m}(\|\bm{w}_{r}(0)\|_{2}^{2}+1).$

For $i\in[n_{1}+1,n_{1}+n_{2}]$ and $j\in[n_{1}+1,n_{1}+n_{2}]$, we have

$\displaystyle|G_{ij}-G(0)_{ij}|$
$\displaystyle=|\sum\limits_{r=1}^{m}\langle\frac{\partial
h_{i}(\bm{w})}{\partial\bm{w}_{r}},\frac{\partial
h_{j}(\bm{w})}{\partial\bm{w}_{r}}\rangle-\langle\frac{\partial
h_{i}(\bm{w}(0))}{\partial\bm{w}_{r}},\frac{\partial
h_{j}(\bm{w}(0))}{\partial\bm{w}_{r}}\rangle|$ $\displaystyle\lesssim
R\frac{1}{n_{2}}\frac{1}{m}.$

Combining above results yields that

$\displaystyle\|G-G(0)\|_{2}^{2}$ $\displaystyle\leq\|G-G(0)\|_{F}^{2}$
$\displaystyle\lesssim
R^{2}+R^{2}\left(\frac{1}{m}\sum\limits_{r=1}^{m}\|\bm{w}_{r}(0)\|_{2}^{4}\right)^{2}+R^{2}\left(\frac{1}{m}\sum\limits_{r=1}^{m}\|\bm{w}_{r}(0)\|_{2}^{2}\right)^{2}.$

For the second term, Lemma 10 implies that with probability at least
$1-\delta$,

$\frac{1}{m}\sum\limits_{r=1}^{m}\|\bm{w}_{r}(0)\|_{2}^{4}\lesssim
d^{2}+\frac{d^{2}}{\sqrt{m}}\sqrt{\log(\frac{1}{\delta})}+\frac{d^{2}}{m}(\log(\frac{1}{\delta}))^{2}.$

Similarly, for the third term, we have that with probability at least
$1-\delta$,

$\frac{1}{m}\sum\limits_{r=1}^{m}\|\bm{w}_{r}(0)\|_{2}^{2}\lesssim
d+\frac{d}{\sqrt{m}}\sqrt{\log(\frac{1}{\delta})}+\frac{d}{m}\log(\frac{1}{\delta}).$

Finally, we can deduce that with probability at least $1-\delta$,

$\|G-G(0)\|_{2}\leq
CR\max\left(d^{2},\frac{d^{2}}{\sqrt{m}}\sqrt{\log(\frac{1}{\delta})},\frac{d^{2}}{m}(\log(\frac{1}{\delta}))^{2}\right),$

where $C$ is a universal constant.

∎

##  10\. Proof of Lemma 5

###### Proof.

From Lemma 10, we can deduce that for fixed $r\in[m]$,

$\|\bm{w}_{r}(0)\|_{2}^{2}\leq
C(d+\sqrt{d\log(\frac{1}{\delta})}+\log(\frac{1}{\delta}))$

holds with probability at least $1-\delta$.

Therefore, the following holds with probability at least $1-\delta$.

$\|\bm{w}_{r}(0)\|_{2}^{2}\leq
C(d+\sqrt{d\log(\frac{m}{\delta})}+\log(\frac{m}{\delta})),\ for\ \forall
r\in[m].$

∎

##  11\. Proof of Lemma 6

###### Proof.

Recall that the initial value of PINN is

$\displaystyle L(0)$
$\displaystyle=\frac{1}{2}\sum\limits_{p=1}^{n_{1}}s_{p}^{2}(\bm{w}(0))+\frac{1}{2}\sum\limits_{j=1}^{n_{2}}h_{j}^{2}(\bm{w}(0))$
$\displaystyle=\frac{1}{2n_{1}}\sum\limits_{p=1}^{n_{1}}(\frac{1}{\sqrt{m}}\sum\limits_{r=1}^{m}a_{r}(0)[\sigma^{{}^{\prime}}(\bm{w}_{r}(0)^{T}\bm{x}_{p})w_{r0}(0)-\sigma^{{}^{\prime\prime}}(\bm{w}_{r}(0)^{T}\bm{x}_{p})\|\bm{w}_{r1}(0)\|_{2}^{2}]-f(\bm{x}_{p}))^{2}$
$\displaystyle\quad+\frac{\lambda}{2n_{2}}\sum\limits_{j=1}^{n_{2}}(\frac{1}{\sqrt{m}}\sum\limits_{r=1}^{m}a_{r}(0)\sigma(\bm{w}_{r}(0)^{T}\bm{y}_{j})-g(\bm{y}_{j}))^{2}$
$\displaystyle\leq\frac{1}{n_{1}}\sum\limits_{p=1}^{n_{1}}(\frac{1}{\sqrt{m}}\sum\limits_{r=1}^{m}a_{r}(0)[\sigma^{{}^{\prime}}(\bm{w}_{r}(0)^{T}\bm{x}_{p})w_{r0}(0)-\sigma^{{}^{\prime\prime}}(\bm{w}_{r}(0)^{T}x_{p})\|\bm{w}_{r1}(0)\|_{2}^{2}])^{2}+(f(\bm{x}_{p}))^{2}$
$\displaystyle\quad+\frac{\lambda}{n_{2}}\sum\limits_{j=1}^{n_{2}}(\frac{1}{\sqrt{m}}\sum\limits_{r=1}^{m}a_{r}(0)\sigma(\bm{w}_{r}(0)^{T}\bm{y}_{j}))^{2}+(g(\bm{y}_{j}))^{2}.$

For the first term, note that
$\mathbb{E}\left(a_{r}(0)[\sigma^{{}^{\prime}}(\bm{w}_{r}(0)^{T}\bm{x}_{p})w_{r0}(0)-\sigma^{{}^{\prime\prime}}(\bm{w}_{r}(0)^{T}\bm{x}_{p})\|\bm{w}_{r1}(0)\|_{2}^{2}]\right)=0$
and

$\displaystyle|a_{r}(0)[\sigma^{{}^{\prime}}(\bm{w}_{r}(0)^{T}\bm{x}_{p})w_{r0}(0)-\sigma^{{}^{\prime\prime}}(\bm{w}_{r}(0)^{T}\bm{x}_{p})\|\bm{w}_{r1}(0)\|_{2}^{2}]|$
$\displaystyle\lesssim|w_{r0}(0)|+\|\bm{w}_{r1}(0)\|_{2}^{2}$
$\displaystyle\lesssim 1+|w_{r0}(0)|^{2}+\|\bm{w}_{r1}(0)\|_{2}^{2}$
$\displaystyle=1+\sum\limits_{i=0}^{d}|w_{ri}(0)|^{2}.$

Therefore,

$\|a_{r}(0)[\sigma^{{}^{\prime}}(\bm{w}_{r}(0)^{T}\bm{x}_{p})w_{r0}(0)-\sigma^{{}^{\prime\prime}}(\bm{w}_{r}(0)^{T}\bm{x}_{p})\|\bm{w}_{r1}(0)\|_{2}^{2}]\|_{\psi_{1}}\leq
Cd.$

Let
$X_{r}=a_{r}(0)[\sigma^{{}^{\prime}}(\bm{w}_{r}(0)^{T}\bm{x}_{p})w_{r0}(0)-\sigma^{{}^{\prime\prime}}(\bm{w}_{r}(0)^{T}\bm{x}_{p})\|\bm{w}_{r1}(0)\|_{2}^{2}]$,
then Lemma 10 implies that with probability at least $1-\delta$,

$|\sum\limits_{r=1}^{m}\frac{1}{\sqrt{m}}X_{r}|\lesssim
d\sqrt{\log(\frac{1}{\delta})}+\frac{d}{\sqrt{m}}\log(\frac{1}{\delta}).$

For the second term

$\frac{1}{\sqrt{m}}\sum\limits_{r=1}^{m}a_{r}(0)\sigma(w_{r}(0)^{T}\bm{y}_{j})=\frac{1}{\sqrt{m}}\sum\limits_{r=1}^{m}a_{r}(0)(\sigma(\bm{w}_{r}(0)^{T}\bm{y}_{j})-\sigma(0))+a_{r}(0)\sigma(0),$

note that
$\mathbb{E}[a_{r}(0)(\sigma(\bm{w}_{r}(0)^{T}\bm{y}_{j})-\sigma(0))]=0$ and

$|a_{r}(0)(\sigma(\bm{w}_{r}(0)^{T}\bm{y}_{j})-\sigma(0))|\lesssim|\bm{w}_{r}(0)^{T}\bm{y}_{j}|,$

thus

$\|a_{r}(0)(\sigma(\bm{w}_{r}(0)^{T}\bm{y}_{j})-\sigma(0))\|_{\psi_{2}}\leq
C,$

as $\bm{w}_{r}(0)^{T}\bm{y}_{j}\sim N(0,\|\bm{y}_{j}\|_{2}^{2})$.

Let $Y_{r}=a_{r}(0)(\sigma(\bm{w}_{r}(0)^{T}\bm{y}_{j})-\sigma(0))$, applying
Lemma 10 yields that with probability at least $1-\delta$,

$|\sum\limits_{r=1}^{m}\frac{1}{\sqrt{m}}Y_{r}|\lesssim\sqrt{\log(\frac{1}{\delta})}+\frac{1}{\sqrt{m}}\log(\frac{1}{\delta}).$

It remains only to handle $\frac{1}{\sqrt{m}}\sum_{r=1}^{m}a_{r}(0)\sigma(0)$,
which is sub-Gaussian. Specifically, for any $\lambda\in\mathbb{R}$, we have

$\displaystyle\mathbb{E}exp\left(\frac{\lambda}{\sqrt{m}}\sum_{r=1}^{m}a_{r}(0)\sigma(0)\right)$
$\displaystyle=\prod_{r=1}^{m}\mathbb{E}exp\left(\frac{\lambda}{\sqrt{m}}a_{r}(0)\sigma(0)\right)$
$\displaystyle\leq\prod_{r=1}^{m}\mathbb{E}exp\left(\frac{\lambda^{2}}{2m}\sigma(0)^{2}\right)$
$\displaystyle=\mathbb{E}exp\left(\frac{\lambda^{2}}{2}\sigma(0)^{2}\right),$

where the first inequality follows from the fact that the Rademacher variable
$a_{r}(0)$ is sub-Gaussian.

Thus with probability at least $1-\delta$,

$|\frac{1}{\sqrt{m}}\sum\limits_{r=1}^{m}a_{r}(0)\sigma(0)|\lesssim\sqrt{\log(\frac{1}{\delta})}.$

Combining all results above yields that

$L(0)\lesssim
d^{2}\log(\frac{n_{1}+n_{2}}{\delta})+\frac{d^{2}}{m}(\log(\frac{n_{1}+n_{2}}{\delta}))^{2}$

holds with probability at least $1-\delta$.

∎

##  12\. Proof of Lemma 7

###### Proof.

Recall that

$\frac{\partial
s_{p}(\bm{w})}{\partial\bm{w}_{r}}=\frac{a_{r}}{\sqrt{mn_{1}}}(\sigma^{{}^{\prime\prime}}(\bm{w}^{T}x_{p})w_{r0}\bm{x}_{p}+\sigma^{{}^{\prime}}(\bm{w}^{T}\bm{x}_{p})\begin{pmatrix}1\\\
\bm{0}_{d}\end{pmatrix}-\sigma^{{}^{\prime\prime\prime}}(\bm{w}_{r}^{T}\bm{x}_{p})\|\bm{w}_{r1}\|_{2}^{2}\bm{x}_{p}-2\sigma^{{}^{\prime\prime}}(\bm{w}_{r}^{T}\bm{x}_{p})\begin{pmatrix}0\\\
\bm{w}_{r1}\end{pmatrix})$

and

$\frac{\partial
h_{j}(\bm{w})}{\partial\bm{w}_{r}}=\frac{a_{r}\sqrt{\lambda}}{\sqrt{mn_{2}}}\sigma^{{}^{\prime}}(\bm{w}_{r}^{T}\bm{y}_{j})\bm{y}_{j}.$

Thus, under the setting that condition 1 holds for
$k^{{}^{\prime}}=0,\cdots,k$, we have that

$\|\frac{\partial
s_{p}(\bm{w}(k^{{}^{\prime}})}{\partial\bm{w}_{r}}\|_{2}\lesssim\frac{B^{2}}{\sqrt{mn_{1}}},\
\|\frac{\partial
h_{j}(\bm{w}(k^{{}^{\prime}}))}{\partial\bm{w}_{r}}\|_{2}\lesssim\frac{1}{\sqrt{mn_{2}}}$

holds for $k^{{}^{\prime}}=0,\cdots,k$.

From the updating rule, i.e.,

$\bm{w}_{r}(t+1)=\bm{w}_{r}(t)-\eta\sum\limits_{p=1}^{n_{1}}s_{p}(\bm{w}(t+1))\frac{\partial
s_{p}(\bm{w}(t+1))}{\partial\bm{w}_{r}}-\eta\sum\limits_{j=1}^{n_{2}}h_{j}(\bm{w}(t+1))\frac{\partial
h_{j}(\bm{w}(t+1))}{\partial\bm{w}_{r}},$

we have that for $t=0,\cdots,k-1$,

$\displaystyle\|\bm{w}_{r}(t+1)-\bm{w}_{r}(t)\|_{2}$
$\displaystyle\leq\eta\|\sum\limits_{p=1}^{n_{1}}s_{p}(\bm{w}(t+1))\frac{\partial
s_{p}(\bm{w}(t+1))}{\partial\bm{w}_{r}}+\sum\limits_{j=1}^{n_{2}}h_{j}(t+1)\frac{\partial
h_{j}(\bm{w}(t+1))}{\partial\bm{w}_{r}}\|_{2}$
$\displaystyle\leq\eta\sum\limits_{p=1}^{n_{1}}|s_{p}(\bm{w}(t+1))|\|\frac{\partial
s_{p}(\bm{w}(t+1))}{\partial\bm{w}_{r}}\|_{2}+\eta\sum\limits_{j=1}^{n_{2}}|h_{j}(\bm{w}(t+1))|\|\frac{\partial
h_{j}(\bm{w}(t+1))}{\partial\bm{w}_{r}}\|_{2}$
$\displaystyle\lesssim\eta\sum\limits_{p=1}^{n_{1}}|s_{p}(\bm{w}(t+1))|\frac{B^{2}}{\sqrt{mn_{1}}}+\eta\sum\limits_{j=1}^{n_{2}}|h_{j}(\bm{w}(t+1))|\frac{1}{\sqrt{mn_{2}}}$
$\displaystyle\leq\eta\frac{B^{2}}{\sqrt{m}}\|\bm{s}(\bm{w}(t+1))\|_{2}+\eta\frac{1}{\sqrt{m}}\|\bm{h}(\bm{w}(t+1))\|_{2}$
$\displaystyle\lesssim\frac{\eta
B^{2}}{\sqrt{m}}\left\|\begin{bmatrix}\bm{s}(\bm{w}(t+1))\\\
\bm{h}(\bm{w}(t+1))\end{bmatrix}\right\|_{2}$ $\displaystyle\leq\frac{\eta
B^{2}}{\sqrt{m}}(1+\frac{\eta\lambda_{0}}{2})^{-\frac{t+1}{2}}\left\|\begin{bmatrix}\bm{s}(0)\\\
\bm{h}(0)\end{bmatrix}\right\|_{2},$

where the second inequality follows from triangle ineuqality, the third
inequality follows from Cauchy’s inequality and the last inequality is due to
the induction.

Summing $t$ from $0$ to $k-1$ yields that

$\displaystyle\|\bm{w}_{r}(k)-\bm{w}_{r}(0)\|_{2}$
$\displaystyle\leq\sum\limits_{t=0}^{k-1}\|\bm{w}_{r}(t+1)-\bm{w}_{r}(t)\|_{2}$
(42) $\displaystyle\leq C\frac{\eta
B^{2}}{\sqrt{m}}\sum\limits_{t=0}^{k-1}(1+\frac{\eta\lambda_{0}}{2})^{-\frac{t+1}{2}}\left\|\begin{bmatrix}\bm{s}(0)\\\
\bm{h}(0)\end{bmatrix}\right\|_{2}$ $\displaystyle\leq C\frac{\eta
B^{2}}{\sqrt{m}}\sum\limits_{t=1}^{\infty}(1+\frac{\eta\lambda_{0}}{2})^{-\frac{t}{2}}\left\|\begin{bmatrix}\bm{s}(0)\\\
\bm{h}(0)\end{bmatrix}\right\|_{2}$ $\displaystyle\leq C\frac{\eta
B^{2}}{\sqrt{m}}\frac{1}{\eta\lambda_{0}}\left\|\begin{bmatrix}\bm{s}(0)\\\
\bm{h}(0)\end{bmatrix}\right\|_{2}$
$\displaystyle\leq\frac{CB^{2}}{\sqrt{m}\lambda_{0}}\left\|\begin{bmatrix}\bm{s}(0)\\\
\bm{h}(0)\end{bmatrix}\right\|_{2},$

where $C$ is a universal constant.

For $t=k$, we can only deduce that

$\displaystyle\|\bm{w}_{r}(k+1)-\bm{w}_{r}(k)\|_{2}$ (43)
$\displaystyle\leq\eta\|\sum\limits_{p=1}^{n_{1}}s_{p}(\bm{w}(k+1))\frac{\partial
s_{p}(\bm{w}(k+1))}{\partial\bm{w}_{r}}+\sum\limits_{j=1}^{n_{2}}h_{j}(\bm{w}(k+1))\frac{\partial
h_{j}(\bm{w}(k+1))}{\partial\bm{w}_{r}}\|_{2}$
$\displaystyle\leq\eta\frac{1}{\sqrt{mn_{1}}}(\|\bm{w}_{r}(k+1)\|_{2}^{2}+1)\sum\limits_{p=1}^{n_{1}}|s_{p}(\bm{w}(k+1))|+\eta\frac{1}{\sqrt{mn_{2}}}\sum\limits_{j=1}^{n_{2}}|h_{j}(\bm{w}(k+1))|$
$\displaystyle\lesssim\eta\frac{1}{\sqrt{m}}(\|\bm{w}_{r}(k+1)\|_{2}^{2}+1)(\|\bm{s}(k+1)\|_{2}+\|\bm{h}(k+1)\|_{2})$
$\displaystyle\lesssim\eta\frac{1}{\sqrt{m}}(\|\bm{w}_{r}(k+1)\|_{2}^{2}+1)\|\begin{bmatrix}\bm{s}(k+1)\\\
\bm{h}(k+1)\end{bmatrix}\|_{2}$
$\displaystyle=\eta\frac{1}{\sqrt{m}}(\|\bm{w}_{r}(k+1)\|_{2}^{2}+1)\sqrt{L(k+1)},$

where the third inequality follows from Cauchy’s inequality.

Fortunately, the implicit updating rule (12) imples that

$\|\bm{w}(k+1)-\bm{w}(k)\|_{2}^{2}\leq 2\eta(L(k)-L(k+1)),$

thus

$\|\bm{w}_{r}(k+1)-\bm{w}_{r}(k)\|_{2}^{2}\leq 2\eta L(k),\ for\ \forall
r\in[m].$ (44)

Plugging (44) into (43) yields that

$\displaystyle\|\bm{w}_{r}(k+1)-\bm{w}_{r}(k)\|_{2}$ (45)
$\displaystyle\lesssim\eta\frac{1}{\sqrt{m}}(\|\bm{w}_{r}(k+1)\|_{2}^{2}+1)\sqrt{L(k+1)}$
$\displaystyle\leq\eta\frac{1}{\sqrt{m}}(2\|\bm{w}_{r}(k+1)-\bm{w}_{r}(k)\|_{2}^{2}+2\|\bm{w}_{r}(k)\|_{2}^{2}+1)\sqrt{L(k+1)}$
$\displaystyle\lesssim\frac{\eta}{\sqrt{m}}(\eta L(k)+B^{2}+1)\sqrt{L(0)}$
$\displaystyle\lesssim\frac{\eta}{\sqrt{m}}(\eta L(0)+B^{2})\sqrt{L(0)}.$

Combining (45) and (42), we have

$\displaystyle\|\bm{w}_{r}(k+1)-\bm{w}_{r}(0)\|_{2}$
$\displaystyle\leq\|\bm{w}_{r}(k+1)-\bm{w}_{r}(k)\|_{2}+\|\bm{w}_{r}(k)-\bm{w}_{r}(0)\|_{2}$
(46) $\displaystyle\leq\frac{C\eta}{\sqrt{m}}(\eta
L(0)+B^{2})\sqrt{L(0)}+\frac{CB^{2}}{\sqrt{m}\lambda_{0}}\sqrt{L(0)},$

with a universal constant $C$. ∎

##  13\. Proof of Lemma 8

###### Proof.

Thans to Lemma 7 that provides an upper bound for
$\|\bm{w}_{r}(k+1)-\bm{w}_{r}(0)\|_{2}$, i.e., (46), then applying Lemma 4
yields that

$\displaystyle\|G(k+1)-G(0)\|_{2}$
$\displaystyle\leq(C\max(d^{2},\frac{d^{2}}{\sqrt{m}}\sqrt{\log(\frac{1}{\delta})},\frac{d^{2}}{m}(\log(\frac{1}{\delta}))^{2}))(\frac{C\eta}{\sqrt{m}}(\eta
L(0)+B^{2})\sqrt{L(0)}+\frac{CB^{2}}{\sqrt{m}\lambda_{0}}\sqrt{L(0)})$
$\displaystyle\leq
Cd^{2}\frac{1}{\sqrt{m}}\sqrt{L(0)}\max(\eta^{2}L(0),\frac{B^{2}}{\lambda_{0}})$
$\displaystyle\leq\frac{\lambda_{0}}{4},$

where the last inequality requires that

$m\geq
Cd^{8}(\log(\frac{n_{1}+n_{2}}{\delta})\max(\eta^{4}d^{2}\log(\frac{n_{1}+n_{2}}{\delta}),\frac{1}{\lambda_{0}^{2}}(\log(\frac{m}{\delta}))^{2})).$
(47)

Thus, $\lambda_{min}(G(k+1))\geq\frac{\lambda_{0}}{2}$.

∎

##  14\. Proof of Lemma 9

###### Proof.

Recall that

$\bm{I}_{1}^{p}(k+1)=\int_{0}^{\eta}\langle\nabla L(\bm{w}(k+1)),\nabla
s_{p}(\bm{w}(k+1)+\alpha\nabla(\bm{w}(k+1)))-\nabla s_{p}(\bm{w}(k+1))\rangle
d\alpha$

and

$\bm{I}_{2}^{j}(k+1)=\int_{0}^{\eta}\langle\nabla L(\bm{w}(k+1)),\nabla
h_{j}(\bm{w}(k+1)+\alpha\nabla L(\bm{w}(k+1)))-\nabla
h_{j}(\bm{w}(k+1))\rangle d\alpha.$

Thus for $\bm{I}_{1}^{p}(k+1)$, we have

$\displaystyle\bm{I}_{1}^{p}(k+1)$
$\displaystyle=\sum\limits_{r=1}^{m}\int_{0}^{\eta}\langle\frac{\partial
L(\bm{w}(k+1))}{\partial\bm{w}_{r}},\frac{\partial
s_{p}(\bm{w}(k+1)+\alpha\frac{\partial
L(\bm{w}(k+1))}{\partial\bm{w}})}{\partial\bm{w}_{r}}-\frac{\partial
s_{p}(\bm{w}(k+1))}{\partial\bm{w}_{r}}\rangle d\alpha.$

Note that

$\frac{\partial
s_{p}(\bm{w})}{\partial\bm{w}_{r}}=\frac{1}{\sqrt{n_{1}}}\frac{a_{r}}{\sqrt{m}}\left[\sigma^{{}^{\prime\prime}}(\bm{w}_{r}^{T}\bm{x}_{p})w_{r0}\bm{x}+\sigma^{{}^{\prime}}(\bm{w}_{r}^{T}\bm{x}_{p})\begin{pmatrix}1\\\
0_{d}\end{pmatrix}-\sigma^{{}^{\prime\prime\prime}}(\bm{w}_{r}^{T}\bm{x}_{p})\|\bm{w}_{r1}\|_{2}^{2}\bm{x}-2\sigma^{{}^{\prime\prime}}(\bm{w}_{r}^{T}\bm{x}_{p})\begin{pmatrix}0\\\
\bm{w}_{r1}\end{pmatrix}\right],$

thus for any $\bm{w}=(\bm{w}_{1},\cdots,\bm{w}_{m})$ and
$\hat{\bm{w}}=(\hat{\bm{w}}_{1},\cdots,\hat{\bm{w}}_{m})$ with
$\|\bm{w}_{r}\|_{2}\leq B,\|\hat{\bm{w}}_{r}\|_{2}\leq B$ for all $r\in[m]$
(as for any $\alpha\in[0,\eta]$, $\bm{w}(k+1)+\alpha\frac{\partial
L(\bm{w}(k+1))}{\partial\bm{w}}$ is a convex combination of $\bm{w}(k)$ and
$\bm{w}(k+1)$, thus the $2$-norm of each component of it is bounded by $B$),
we have

$\displaystyle\|\frac{\partial
s_{p}(\bm{w})}{\partial\bm{w}_{r}}-\frac{\partial
s_{p}(\hat{\bm{w}})}{\partial\bm{w}_{r}}\|_{2}$
$\displaystyle\lesssim\frac{1}{\sqrt{m}}(B^{2}+B+1)\|\bm{w}_{r}-\hat{\bm{w}}_{r}\|_{2}\lesssim\frac{B^{2}}{\sqrt{m}}\|\bm{w}_{r}-\hat{\bm{w}}_{r}\|_{2}.$

With this result, we can deduce that

$\displaystyle|\bm{I}_{1}^{p}(k+1)|$
$\displaystyle=|\sum\limits_{r=1}^{m}\int_{0}^{\eta}\langle\frac{\partial
L(\bm{w}(k+1))}{\partial\bm{w}_{r}},\frac{\partial
s_{p}(\bm{w}(k+1)+\alpha\frac{\partial
L(\bm{w}(k+1))}{\partial\bm{w}})}{\partial\bm{w}_{r}}-\frac{\partial
s_{p}(\bm{w}(k+1))}{\partial\bm{w}_{r}}\rangle d\alpha|$
$\displaystyle\leq\sum\limits_{r=1}^{m}\int_{0}^{\eta}\|\frac{\partial
L(\bm{w}(k+1))}{\partial\bm{w}_{r}}\|_{2}\|\frac{\partial
s_{p}(\bm{w}(k+1)+\alpha\frac{\partial
L(\bm{w}(k+1))}{\partial\bm{w}})}{\partial\bm{w}_{r}}-\frac{\partial
s_{p}(\bm{w}(k+1))}{\partial\bm{w}_{r}}\|_{2}d\alpha$
$\displaystyle\lesssim\frac{B^{2}}{\sqrt{m}}\sum\limits_{r=1}^{m}\int_{0}^{\eta}\|\frac{\partial
L(\bm{w}(k+1))}{\partial\bm{w}_{r}}\|_{2}|\alpha|\|\frac{\partial
L(\bm{w}(k+1))}{\partial\bm{w}_{r}}\|_{2}d\alpha$
$\displaystyle\lesssim\frac{\eta^{2}B^{2}}{\sqrt{m}}\sum\limits_{r=1}^{m}\|\frac{\partial
L(\bm{w}(k+1))}{\partial\bm{w}_{r}}\|_{2}^{2}.$

Recall that

$\frac{\partial
L(\bm{w}(k+1))}{\partial\bm{w}_{r}}=\sum\limits_{p=1}^{n_{1}}s_{p}(k+1)\frac{\partial
s_{p}(k+1)}{\partial\bm{w}_{r}}+\sum\limits_{j=1}^{n_{2}}h_{j}(k+1)\frac{\partial
h_{j}(k+1)}{\partial\bm{w}_{r}}.$

From the estimation of $\|\bm{w}_{r}(t+1)-\bm{w}_{r}(t)\|_{2}$ in the proof of
Lemma 7, we have that

$\|\frac{\partial
L(\bm{w}(k+1))}{\partial\bm{w}_{r}}\|_{2}\lesssim\frac{B^{2}}{\sqrt{m}}\sqrt{L(k+1)}.$

Therefore,

$\displaystyle\|\bm{I}_{1}(k+1)\|_{2}$
$\displaystyle=\sqrt{\sum\limits_{p=1}^{n_{1}}|\bm{I}_{1}^{p}(k+1)|^{2}}$ (48)
$\displaystyle\lesssim\frac{\sqrt{n_{1}}\eta^{2}B^{2}}{\sqrt{m}}\sum\limits_{r=1}^{m}\frac{B^{4}}{m}L(k+1)$
$\displaystyle\lesssim\frac{\eta^{2}\sqrt{n_{1}}B^{6}}{\sqrt{m}}L(k+1).$

Similarly, we can deduce that

$\|\bm{I}_{2}(k+1)\|_{2}\lesssim\frac{\eta^{2}\sqrt{n_{2}}}{\sqrt{m}}L(k+1).$
(49)

∎

##  15\. Proof of Theorem 1

###### Proof.

We first recall the recursive formula of the implicit gradient descent:

$\begin{bmatrix}\bm{s}(\bm{w}(k+1))\\\
\bm{h}(\bm{w}(k+1))\end{bmatrix}=(\bm{I}+\eta
G(k+1))^{-1}\left(\begin{bmatrix}\bm{s}(\bm{w}(k))\\\
\bm{h}(\bm{w}(k))\end{bmatrix}-\begin{bmatrix}\bm{I}_{1}(k+1)\\\
\bm{I}_{2}(k+1)\end{bmatrix}\right).$

Thus,

$\displaystyle\|\begin{bmatrix}\bm{s}(\bm{w}(k+1))\\\
\bm{h}(\bm{w}(k+1))\end{bmatrix}\|_{2}^{2}$ $\displaystyle=\|(\bm{I}+\eta
G(k+1))^{-1}\left(\begin{bmatrix}\bm{s}(\bm{w}(k))\\\
\bm{h}(\bm{w}(k))\end{bmatrix}-\begin{bmatrix}\bm{I}_{1}(k+1)\\\
\bm{I}_{2}(k+1)\end{bmatrix}\right)\|_{2}^{2}$ (50)
$\displaystyle\leq\frac{1}{(1+\frac{\eta\lambda_{0}}{2})^{2}}\left[\|\begin{bmatrix}\bm{s}(\bm{w}(k))\\\
\bm{h}(\bm{w}(k))\end{bmatrix}\|_{2}^{2}-2\langle\begin{bmatrix}\bm{s}(\bm{w}(k))\\\
\bm{h}(\bm{w}(k))\end{bmatrix},\begin{bmatrix}\bm{I}_{1}(k+1)\\\
\bm{I}_{2}(k+1)\end{bmatrix}\rangle+\|\begin{bmatrix}\bm{I}_{1}(k+1)\\\
\bm{I}_{2}(k+1)\end{bmatrix}\|_{2}^{2}\right]$
$\displaystyle\leq\frac{1}{(1+\frac{\eta\lambda_{0}}{2})^{2}}\left[\|\begin{bmatrix}\bm{s}(\bm{w}(k))\\\
\bm{h}(\bm{w}(k))\end{bmatrix}\|_{2}^{2}+2\|\begin{bmatrix}\bm{s}(\bm{w}(k))\\\
\bm{h}(\bm{w}(k))\end{bmatrix}\|_{2}\|\begin{bmatrix}\bm{I}_{1}(k+1)\\\
\bm{I}_{2}(k+1)\end{bmatrix}\|_{2}+\|\begin{bmatrix}\bm{I}_{1}(k+1)\\\
\bm{I}_{2}(k+1)\end{bmatrix}\|_{2}^{2}\right].$

From Lemma 9, combining (48) and (49), we can deduce that

$\left\|\begin{bmatrix}\bm{I}_{1}(k+1)\\\
\bm{I}_{2}(k+1)\end{bmatrix}\right\|_{2}\leq\frac{C\eta^{2}(\sqrt{n_{1}}B^{6}+\sqrt{n_{2}})}{\sqrt{m}}L(k+1)\leq\frac{C\eta^{2}(\sqrt{n_{1}+n_{2}})B^{6}}{\sqrt{m}}L(k+1)\leq\frac{C\eta^{2}(\sqrt{n_{1}+n_{2}})B^{6}}{\sqrt{m}}\sqrt{L(0)L(k+1)}$
(51)

and

$\left\|\begin{bmatrix}\bm{I}_{1}(k+1)\\\
\bm{I}_{2}(k+1)\end{bmatrix}\right\|_{2}^{2}\leq\frac{C^{2}\eta^{4}(\sqrt{n_{1}+n_{2}})^{2}B^{12}}{m}L(k+1)^{2}\leq\frac{C^{2}\eta^{2}(n_{1}+n_{2})B^{12}}{\sqrt{m}}L(k+1)L(0).$
(52)

Plugging (51) and (52) into (50) yields that

$\displaystyle L(k+1)$
$\displaystyle\leq\frac{1}{(1+\frac{\eta\lambda_{0}}{2})^{2}}\left[L(k)+\frac{C\eta^{2}(\sqrt{n_{1}+n_{2}})B^{6}}{\sqrt{m}}\sqrt{L(0)}\sqrt{L(k)}\sqrt{L(k+1)}+\frac{C^{2}\eta^{2}(n_{1}+n_{2})B^{12}}{\sqrt{m}}L(0)L(k+1).\right]$
$\displaystyle\leq\frac{1}{(1+\frac{\eta\lambda_{0}}{2})^{2}}\left[L(k)+\frac{C\eta^{2}(\sqrt{n_{1}+n_{2}})B^{6}}{\sqrt{m}}\sqrt{L(0)}(L(k)+L(k+1))+\frac{C^{2}\eta^{2}(n_{1}+n_{2})B^{12}}{\sqrt{m}}L(0)L(k+1),\right]$

where the first inequality follows from the mean inequality.

Let $f(m)=\frac{C\eta^{2}(\sqrt{n_{1}+n_{2}})B^{6}}{\sqrt{m}}L(0)$, then
simple algebraic transformations leads to that

$\displaystyle L(k+1)$
$\displaystyle\leq\frac{1+f(m)}{(1+\frac{\eta\lambda_{0}}{2})^{2}-f(m)-f^{2}(m)}L(k)$
$\displaystyle\leq\frac{1+\frac{\eta\lambda_{0}}{4}}{(1+\frac{\eta\lambda_{0}}{2})^{2}-\frac{\eta\lambda_{0}}{4}-\frac{\eta^{2}\lambda_{0}^{2}}{16}}L(k)$
$\displaystyle\leq\frac{1+\frac{\eta\lambda_{0}}{4}}{1+\frac{3\eta\lambda_{0}}{4}+\frac{3\eta^{2}\lambda_{0}^{2}}{16}}L(k)$
$\displaystyle\leq\frac{1+\frac{\eta\lambda_{0}}{4}}{1+\frac{3\eta\lambda_{0}}{4}+\frac{\eta^{2}\lambda_{0}^{2}}{8}}L(k)$
$\displaystyle=\frac{1+\frac{\eta\lambda_{0}}{4}}{(1+\frac{\eta\lambda_{0}}{4})(1+\frac{\eta\lambda_{0}}{2})}L(k)$
$\displaystyle=(1+\frac{\eta\lambda_{0}}{2})^{-1}L(k)$
$\displaystyle\leq(1+\frac{\eta\lambda_{0}}{2})^{-(k+1)}L(0),$

where the second inequality is due to that we choose $m$ large enough such
that

$\frac{C\eta^{2}(\sqrt{n_{1}+n_{2}})B^{6}}{\sqrt{m}}L(0)\leq\frac{\eta\lambda_{0}}{4},$

i.e.,

$m=\Omega(\frac{\eta^{2}(n_{1}+n_{2})B^{12}L(0)^{2}}{\lambda_{0}^{2}})=\Omega(\frac{\eta^{2}(n_{1}+n_{2})d^{10}(\log(\frac{m}{\delta}))^{6}(\log(\frac{n_{1}+n_{2}}{\delta}))^{2}}{\lambda_{0}^{2}}).$
(53)

Combining the requirments for $m$, i.e., (47) and (53), we can deduce that

$m=\Omega\left(d^{8}\log(\frac{n_{1}+n_{2}}{\delta})\max\left\\{\eta^{4}d^{2}\log(\frac{n_{1}+n_{2}}{\delta}),\frac{1}{\lambda_{0}^{2}}(\log(\frac{m}{\delta}))^{2},\frac{\eta^{2}(n_{1}+n_{2})d^{2}(\log(\frac{m}{\delta}))^{6}(\log(\frac{n_{1}+n_{2}}{\delta}))^{2}}{\lambda_{0}^{2}}\right\\}\right).$

∎

## References

  * [1] K. He, X. Zhang, S. Ren, and J. Sun, “Deep residual learning for image recognition,” in _Proceedings of the IEEE conference on computer vision and pattern recognition_ , 2016, pp. 770–778.
  * [2] J. Devlin, M.-W. Chang, K. Lee, and K. Toutanova, “Bert: Pre-training of deep bidirectional transformers for language understanding,” _arXiv preprint arXiv:1810.04805_ , 2018.
  * [3] D. Silver, A. Huang, C. J. Maddison, A. Guez, L. Sifre, G. Van Den Driessche, J. Schrittwieser, I. Antonoglou, V. Panneershelvam, M. Lanctot _et al._ , “Mastering the game of go with deep neural networks and tree search,” _nature_ , vol. 529, no. 7587, pp. 484–489, 2016.
  * [4] I. E. Lagaris, A. Likas, and D. I. Fotiadis, “Artificial neural networks for solving ordinary and partial differential equations,” _IEEE transactions on neural networks_ , vol. 9, no. 5, pp. 987–1000, 1998.
  * [5] M. Raissi, P. Perdikaris, and G. E. Karniadakis, “Physics-informed neural networks: A deep learning framework for solving forward and inverse problems involving nonlinear partial differential equations,” _Journal of Computational physics_ , vol. 378, pp. 686–707, 2019.
  * [6] J. Han, A. Jentzen, and W. E, “Solving high-dimensional partial differential equations using deep learning,” _Proceedings of the National Academy of Sciences_ , vol. 115, no. 34, pp. 8505–8510, 2018.
  * [7] D. Lucor, A. Agrawal, and A. Sergent, “Simple computational strategies for more effective physics-informed neural networks modeling of turbulent natural convection,” _Journal of Computational Physics_ , vol. 456, p. 111022, 2022\.
  * [8] D. Gilton, G. Ongie, and R. Willett, “Neumann networks for linear inverse problems in imaging,” _IEEE Transactions on Computational Imaging_ , vol. 6, pp. 328–343, 2019.
  * [9] Y. Fan and L. Ying, “Solving electrical impedance tomography with deep learning,” _Journal of Computational Physics_ , vol. 404, p. 109119, 2020\.
  * [10] L. Lu, R. Pestourie, W. Yao, Z. Wang, F. Verdugo, and S. G. Johnson, “Physics-informed neural networks with hard constraints for inverse design,” _SIAM Journal on Scientific Computing_ , vol. 43, no. 6, pp. B1105–B1132, 2021.
  * [11] M. Germain, H. Pham, X. Warin _et al._ , “Neural networks-based algorithms for stochastic control and pdes in finance,” _arXiv preprint arXiv:2101.08068_ , 2021.
  * [12] J. B. Heaton, N. G. Polson, and J. H. Witte, “Deep learning for finance: deep portfolios,” _Applied Stochastic Models in Business and Industry_ , vol. 33, no. 1, pp. 3–12, 2017.
  * [13] Y. Bai, T. Chaolu, and S. Bilige, “The application of improved physics-informed neural network (ipinn) method in finance,” _Nonlinear Dynamics_ , vol. 107, no. 4, pp. 3655–3667, 2022.
  * [14] J. Sirignano and K. Spiliopoulos, “Dgm: A deep learning algorithm for solving partial differential equations,” _Journal of computational physics_ , vol. 375, pp. 1339–1364, 2018.
  * [15] A. Krishnapriyan, A. Gholami, S. Zhe, R. Kirby, and M. W. Mahoney, “Characterizing possible failure modes in physics-informed neural networks,” _Advances in neural information processing systems_ , vol. 34, pp. 26 548–26 560, 2021.
  * [16] Y. Li, S.-C. Chen, and S.-J. Huang, “Implicit stochastic gradient descent for training physics-informed neural networks,” in _Proceedings of the AAAI Conference on Artificial Intelligence_ , vol. 37, no. 7, 2023, pp. 8692–8700.
  * [17] S. S. Du, X. Zhai, B. Poczos, and A. Singh, “Gradient descent provably optimizes over-parameterized neural networks,” _arXiv preprint arXiv:1810.02054_ , 2018.
  * [18] S. Du, J. Lee, H. Li, L. Wang, and X. Zhai, “Gradient descent finds global minima of deep neural networks,” in _International conference on machine learning_. PMLR, 2019, pp. 1675–1685.
  * [19] Y. Gao, Y. Gu, and M. Ng, “Gradient descent finds the global optima of two-layer physics-informed neural networks,” in _International Conference on Machine Learning_. PMLR, 2023, pp. 10 676–10 707.
  * [20] A. Jacot, F. Gabriel, and C. Hongler, “Neural tangent kernel: Convergence and generalization in neural networks,” _Advances in neural information processing systems_ , vol. 31, 2018.
  * [21] Y. Cao and Q. Gu, “Generalization error bounds of gradient descent for learning over-parameterized deep relu networks,” in _Proceedings of the AAAI Conference on Artificial Intelligence_ , vol. 34, no. 04, 2020, pp. 3349–3356.
  * [22] Z. Allen-Zhu, Y. Li, and Z. Song, “A convergence theory for deep learning via over-parameterization,” in _International conference on machine learning_. PMLR, 2019, pp. 242–252.
  * [23] J. Müller and M. Zeinhofer, “Achieving high accuracy with pinns via energy natural gradient descent,” in _International Conference on Machine Learning_. PMLR, 2023, pp. 25 471–25 485.
  * [24] T. Luo and H. Yang, “Two-layer neural networks for partial differential equations: Optimization and generalization theory,” _arXiv preprint arXiv:2006.15733_ , 2020.
  * [25] A. K. Kuchibhotla and A. Chakrabortty, “Moving beyond sub-gaussianity in high-dimensional statistics: Applications in covariance estimation and linear regression,” _Information and Inference: A Journal of the IMA_ , vol. 11, no. 4, pp. 1389–1456, 2022.


# 2nd Place Solution for MeViS Track in CVPR 2024 PVUW Workshop: Motion
Expression guided Video Segmentation

Bin Cao1,2,3 Yisi Zhang4 Xuanxu Lin2 Xingjian He1 Bo Zhao3 Jing Liu1,2
1Institute of Automation, Chinese Academy of Sciences (CASIA)
2School of Artificial Intelligence, University of Chinese Academy of Sciences
(UCAS)
3Beijing Academy of Artificial Intelligence (BAAI)
4University of Science and Technology Beijing (USTB)
Team: CASIA_IVA Equal contribution. Corresponding author.

###### Abstract

Motion Expression guided Video Segmentation is a challenging task that aims at
segmenting objects in the video based on natural language expressions with
motion descriptions. Unlike the previous referring video object segmentation
(RVOS), this task focuses more on the motion in video content for language-
guided video object segmentation, requiring an enhanced ability to model
longer temporal, motion-oriented vision-language data. In this report, based
on the RVOS methods, we successfully introduce mask information obtained from
the video instance segmentation model as preliminary information for temporal
enhancement and employ SAM for spatial refinement. Finally, our method
achieved a score of 49.92 $\mathcal{J}\&\mathcal{F}$ in the validation phase
and 54.20 $\mathcal{J}\&\mathcal{F}$ in the test phase, securing the final
ranking of 2nd in the MeViS Track at the CVPR 2024 PVUW Challenge.

##  1 Introduction

Referring Video Object Segmentation (ROVS) aims to segment and track the
target object referred by the given language description. This emerging task
has attracted significant attention due to its potential applications in video
editing and human-agent interaction.

Motion Expression-guided Video Segmentation is a challenging task based on the
RVOS task. Given videos and motion-oriented language expressions obtained from
the dataset MeViS [3], an embodied agent is needed to segment the
corresponding described one target or multiple objects in the video. Compared
to the conventional RVOS datasets like Ref-Youtube-VOS [13] and Ref-DAVIS17
[7], MeViS presents more complex expressions that include motion information
rather than merely simple spatial location descriptions. Consequently, MeViS
necessitates that the agent comprehends both temporal and spatial information
within video clips to effectively correlate with motion expressions.
Furthermore, MeViS extends the referring task to include language expressions
that match multiple targets, making MeViS more challenging and reflective of
real-world scenarios.

With the development of deep learning, there are studies dealing with the RVOS
task. For example, some studies [13, 1] try to deal with the task from a per-
frame perspective, they transfer the referring image segmentation methods [5,
10, 4] into video domain, whether through a per-frame mask propagation manner
or based on history memory attention to predict the mask of the current frame.
Most recent methods, e.g. [16, 12, 11, 18, 14, 2], focus on a unified
framework that employs language as queries to segment and track the referred
object simultaneously. By effectively building correlations between
expressions and multi-frame visual features, they achieve promising results
across multiple RVOS benchmarks. Some recent methods, e.g.[17, 15, 9], unify
various kinds of object-level tasks, such as MOT, VIS, RVOS and RES, into a
single framework to present an object-centric foundation model. However, these
methods still encounter the issue of inconsistent predicted results across
multiple frames. While some recent studies on Video Instance Segmentation
(VIS) task[19], which emphasizes segmenting different instances in the given
video, have shown promising results in dealing with prediction inconsistent
problem. Furthermore, the emergence of SAM [8] also provides strong
segmentation tools for refinement.

Figure 1: The overall architecture of our solution. We employ MUTR as our
basic model (Left), which contains a visual/text backbone, transformer-based
encoder and decoder, MTI module, and MTA module. We attempt to introduce
instance masks to improve the consistency of prediction results. We employ an
attention block and a sequential mechanism to aggregate instance information
into a query (Right).

Thanks to the superior performance of DVIS [20] from the VIS task, MUTR [18]
from the RVOS task, and HQ-SAM [6], our method achieves a score of 49.92
$\mathcal{J}\&\mathcal{F}$ in the validation phase and 54.20
$\mathcal{J}\&\mathcal{F}$ in the test phase, securing the final ranking of
2nd in the MeViS Track at the CVPR 2024 PVUW Challenge.

##  2 Method

###  2.1 Overview

The architecture of our model is shown in Figure 1. We employ a DETR-based
model as our basic architecture. To improve the consistency of predicted
results, we attempt to introduce proposal instance masks into the model for
query initialization. After prediction, we employ HQ-SAM to refine prediction
masks by sampling key points as prompts.

###  2.2 Basic Model Architecture

MUTR (Multimodal Unified Temporal transformer for Referring video object
segmentation) was proposed in [18] and has shown superior performance on Ref-
Youtube-VOS and Ref-DAVIS17. MUTR adopts a DETR-like style model. Compared
with other methods, MUTR introduces two core modules, i.e. MTI (Multi-object
Temporal Interaction module), MTA (Multi-scale Temporal Aggregation module).

To conduct multi-modal interaction and fusion, the MTA module consists of
sequential cross-attention blocks, which takes text feature and multi-scale
visual features as input and progressively captures temporal visual
information. After that, the class token of output multi-modal tokens is
repeated to initialize object queries of transformer decoder. Considering that
transformer encoder and decoder process video in a frame-independent manner
without temporal modeling, MTI is designed to perform object-wise interaction.
MTI module contains an encoder and a decoder. MTI encoder conducts temporal
interaction of the same object across frames and MTI decoder is designed to
aggregate information of object queries. MTI encoder takes the output of
transformer decoder as input and performs self-attention for the same object
across multiple frames to conduct temporal interaction. MTI decoder consists
of a cross-attention layer, a self-attention layer, and a FFN layer. In MTI
decoder, a set of video-wise query $\mathcal{Q}$ with random initialization is
adopted to associate objects. MTI decoder takes the output of MTI encoder as
key and value and conducts cross-attention with video-wise query.

Table 1: Ablation Experiment Results on MeViS Validation Set We ablate
multiple design choices, including sampling method, HQ-SAM, and introducing
instance masks for query initialization. In all experiments, we adopt the pre-
trained weights of MUTR as initialization and fine-tune model on MeViS.

Method | Backbone | Sampling Method | Instance Masks | HQ-SAM | $\mathcal{J}\&\mathcal{F}$ | $\mathcal{J}$ | $\mathcal{F}$
---|---|---|---|---|---|---|---
MUTR | Swin-L | Local Sampling | ✗ | ✗ | 48.40 | 44.87 | 51.94
✗ | ✓ | 48.66 | 45.86 | 51.46
Global Sampling | ✗ | ✗ | 49.11 | 45.89 | 52.33
✗ | ✓ | 49.50 | 46.91 | 52.09
Global Sampling | ✓ | ✗ | 49.62 | 46.38 | 52.85
✓ | ✓ | 49.92 | 47.30 | 52.54

###  2.3 Instance Masks for Query Initialization

While MUTR achieves superior performance on RVOS, prediction results from MUTR
still suffer from inconsistency and incompleteness. Meantime, some recent
studies on VIS show promising results to solve this issue. Therefore, we
attempt to introduce instance mask information into a DETR-based model to
improve the consistency and completeness of prediction results.

Specifically, we attempt to introduce instance masks to initialize the video-
wise query $\mathcal{Q}$ in MTI decoder. Thanks to the superior performance of
DVIS on VIS, we employ DVIS for mask generation, which extracts all instance
masks in a video clip as follows:

$m_{i}=\text{DVIS}(\text{I}),\ m_{i}\in\mathbb{R}^{\ T\times H\times W}$ (1)

where $\text{I}\in\mathbb{R}^{\ T\times H\times W\times\text{3}}$ is the input
video clip, $m=\\{m_{i}\\}^{K}_{i=1}$ denotes the set of instance masks, $K$
is the number of instances in a video clip and $T$ is the number of frames of
a video clip.

Next, we utilize a visual encoder to extract multi-scale visual features of
instance masks.

$\mathcal{F}_{i,j}=\text{Visual\\_Backbone}(m_{i}),\
\mathcal{F}_{i,j}\in\mathbb{R}^{\ T\times h_{j}\times w_{j}\times c_{j}}$ (2)

where $c_{j}$ is the channel of $j$ level visual feature. After feature
extraction, we utilize a linear projection layer on multi-scale visual
features to align dimension with video features and perform average pooling
along spatial dimension to obtain instance features as follows:

$\mathcal{F}^{{}^{\prime}}_{i,j}=\text{Pooling}(\text{Proj}(\mathcal{F}_{i,j})),\
\mathcal{F}_{i,j}\in\mathbb{R}^{\ T\times C}$ (3)

where $C$ is the channel of video feature.

For simplicity, we only explain our solution utilizing the single-level visual
feature. To aggregate all instance information into an instance query, we
design an attention block and adapt sequential mechanisms as follows:

$\mathcal{Q}_{i}=\text{Block}(\mathcal{Q}_{i-1},\mathcal{F}^{{}^{\prime}}_{i}),\
1\leq i\leq K$ (4)

where ${Q}_{i}\in\mathbb{R}^{\ N\times C}$ is the instance query and $N$ is
the number of queries. ${Q}_{0}$ is randomly initialized. The designed
attention block consists of a cross-attention layer, a set of self-attention
layers, and FFN layers. After that, we utilize this query with instance
information to replace the randomly initialized video-wise query fed to MTI
decoder.

###  2.4 HQ-SAM for Spatial Refinement

Since SAM has shown its great ability in segmenting objects, it could serve as
a spatial refiner for better results. Specifically, in this report, we adopt
HQ-SAM [6] with ViT-L as our mask refiner. Given the predicted result from
MUTR of each clip, we first determine the coordinates of the bounding box by
selecting the maximum and minimum horizontal and vertical coordinates of the
points along the boundary of the mask. Next, we uniformly sample 10
coordinates within the predicted mask as positive points and 5 coordinates out
of the mask but within the bounding box as negative points. The sampled points
are then fed into the mask decoder of HQ-SAM as prompts to generate the
refined masks.

##  3 Experiments

###  3.1 Dataset and Metrics

Datasets. We fine-tune and evaluate our solution on MeViS, a large-scale
dataset for motion guided video segmentation. It contains 2,006 videos with
28,570 language expressions in total. These videos are divided into 1,662
videos for training, 50 videos for offline evaluation, 140 videos for online
evaluation, and other videos for competition.

Metrics. We adopt standard evaluation metrics for MeViS: region similarity
($\mathcal{J}$), contour accuracy ($\mathcal{F}$), and their average value
($\mathcal{J}\&\mathcal{F}$).

###  3.2 Sampling Method

In the training phase, previous work in RVOS sample frames around a center
point, we named this method local sampling. This method only allows model to
access part of the video. However, motion expression guided video segmentation
requires a video-level representation. Therefore, we attempt to divide the
entire video into a set of segments and sample one frame randomly in each
segment, and aggregate sampling frames to obtain a video clip fed into model.
We refer this approach as global sampling, which enables model to access
frames across the entire video.

###  3.3 Implement Details

We adopt the pre-trained weights of MUTR as initialization and fine-tune model
on MeViS. The number of sampling frames is 5. The model is optimized by AdamW
optimizer. The batch size is 1 and the accumulation step is 2. In post-
process, we employ HQ-SAM with VIT-L backbone utilizing default parameters in
[6].

###  3.4 Ablation Experiments

To validate the effectiveness of introducing instance mask for query
initialization, sampling method and HQ-SAM, we conduct simple ablation
experiments. We adopt the pre-trained weight of MUTR for weight initialization
and fine-tuning model on MeViS. Experiment results are shown in Tab. 1. It is
noted that utilizing HQ-SAM for refinement brings an improvement on
$\mathcal{J}$ while a drop about $\mathcal{F}$. However, utilizing HQ-SAM for
refinement still brings an improvement on $\mathcal{J}\&\mathcal{F}$. Compared
with the previous sampling method, the proposed sampling method brings a
significant improvement about 0.69 $\mathcal{J}\&\mathcal{F}$. After
introducing instance masks for query initialization, the performance improved
from 49.11 $\mathcal{J}\&\mathcal{F}$ to 49.62 $\mathcal{J}\&\mathcal{F}$.
Finally, when we combine all of the above methods, model achieves the best
performance 49.92 $\mathcal{J}\&\mathcal{F}$.

###  3.5 Competition Results

Finally, we submit our best solution and achieve 54.20
$\mathcal{J}\&\mathcal{F}$ ( 50.97 $\mathcal{J}$ and 57.43 $\mathcal{F}$ ) on
test phase, which ranks the 2nd place for MeViS Track in CVPR 2024 PVUW.

## References

  * [1] Miriam Bellver, Carles Ventura, Carina Silberer, Ioannis Kazakos, Jordi Torres, and Xavier Giro-i Nieto.  A closer look at referring expressions for video object segmentation.  Multimedia Tools and Applications, 82(3):4419–4438, 2023.
  * [2] Adam Botach, Evgenii Zheltonozhskii, and Chaim Baskin.  End-to-end referring video object segmentation with multimodal transformers.  In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 4985–4995, 2022.
  * [3] Henghui Ding, Chang Liu, Shuting He, Xudong Jiang, and Chen Change Loy.  Mevis: A large-scale benchmark for video segmentation with motion expressions.  In Proceedings of the IEEE/CVF International Conference on Computer Vision, pages 2694–2703, 2023.
  * [4] Henghui Ding, Chang Liu, Suchen Wang, and Xudong Jiang.  Vision-language transformer and query generation for referring segmentation.  In Proceedings of the IEEE/CVF International Conference on Computer Vision, pages 16321–16330, 2021.
  * [5] Shaofei Huang, Tianrui Hui, Si Liu, Guanbin Li, Yunchao Wei, Jizhong Han, Luoqi Liu, and Bo Li.  Referring image segmentation via cross-modal progressive comprehension.  In Proceedings of the IEEE/CVF conference on computer vision and pattern recognition, pages 10488–10497, 2020.
  * [6] Lei Ke, Mingqiao Ye, Martin Danelljan, Yu-Wing Tai, Chi-Keung Tang, Fisher Yu, et al.  Segment anything in high quality.  Advances in Neural Information Processing Systems, 36, 2024.
  * [7] Anna Khoreva, Anna Rohrbach, and Bernt Schiele.  Video object segmentation with language referring expressions.  In Computer Vision–ACCV 2018: 14th Asian Conference on Computer Vision, Perth, Australia, December 2–6, 2018, Revised Selected Papers, Part IV 14, pages 123–141. Springer, 2019.
  * [8] Alexander Kirillov, Eric Mintun, Nikhila Ravi, Hanzi Mao, Chloe Rolland, Laura Gustafson, Tete Xiao, Spencer Whitehead, Alexander C Berg, Wan-Yen Lo, et al.  Segment anything.  In Proceedings of the IEEE/CVF International Conference on Computer Vision, pages 4015–4026, 2023.
  * [9] Minghan Li, Shuai Li, Xindong Zhang, and Lei Zhang.  Univs: Unified and universal video segmentation with prompts as queries.  arXiv preprint arXiv:2402.18115, 2024.
  * [10] Gen Luo, Yiyi Zhou, Xiaoshuai Sun, Liujuan Cao, Chenglin Wu, Cheng Deng, and Rongrong Ji.  Multi-task collaborative network for joint referring expression comprehension and segmentation.  In Proceedings of the IEEE/CVF Conference on computer vision and pattern recognition, pages 10034–10043, 2020.
  * [11] Zhuoyan Luo, Yicheng Xiao, Yong Liu, Shuyan Li, Yitong Wang, Yansong Tang, Xiu Li, and Yujiu Yang.  Soc: Semantic-assisted object cluster for referring video object segmentation.  Advances in Neural Information Processing Systems, 36, 2024.
  * [12] Bo Miao, Mohammed Bennamoun, Yongsheng Gao, and Ajmal Mian.  Spectrum-guided multi-granularity referring video object segmentation.  In Proceedings of the IEEE/CVF International Conference on Computer Vision, pages 920–930, 2023.
  * [13] Seonguk Seo, Joon-Young Lee, and Bohyung Han.  Urvos: Unified referring video object segmentation network with a large-scale benchmark.  In Computer Vision–ECCV 2020: 16th European Conference, Glasgow, UK, August 23–28, 2020, Proceedings, Part XV 16, pages 208–223. Springer, 2020.
  * [14] Dongming Wu, Tiancai Wang, Yuang Zhang, Xiangyu Zhang, and Jianbing Shen.  Onlinerefer: A simple online baseline for referring video object segmentation.  In Proceedings of the IEEE/CVF International Conference on Computer Vision, pages 2761–2770, 2023.
  * [15] Junfeng Wu, Yi Jiang, Qihao Liu, Zehuan Yuan, Xiang Bai, and Song Bai.  General object foundation model for images and videos at scale.  arXiv preprint arXiv:2312.09158, 2023.
  * [16] Jiannan Wu, Yi Jiang, Peize Sun, Zehuan Yuan, and Ping Luo.  Language as queries for referring video object segmentation.  In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 4974–4984, 2022.
  * [17] Bin Yan, Yi Jiang, Jiannan Wu, Dong Wang, Ping Luo, Zehuan Yuan, and Huchuan Lu.  Universal instance perception as object discovery and retrieval.  In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 15325–15336, 2023.
  * [18] Shilin Yan, Renrui Zhang, Ziyu Guo, Wenchao Chen, Wei Zhang, Hongyang Li, Yu Qiao, Hao Dong, Zhongjiang He, and Peng Gao.  Referred by multi-modality: A unified temporal transformer for video object segmentation.  In Proceedings of the AAAI Conference on Artificial Intelligence, volume 38, pages 6449–6457, 2024.
  * [19] Linjie Yang, Yuchen Fan, and Ning Xu.  Video instance segmentation.  In Proceedings of the IEEE/CVF international conference on computer vision, pages 5188–5197, 2019.
  * [20] Tao Zhang, Xingye Tian, Yu Wu, Shunping Ji, Xuebo Wang, Yuan Zhang, and Pengfei Wan.  Dvis: Decoupled video instance segmentation framework.  In Proceedings of the IEEE/CVF International Conference on Computer Vision, pages 1282–1291, 2023.