The theory of neural networks is a huge and quickly growing field. Here we only give a brief summary of the work most closely related to ours.

Convergence results for neural networks with random inputs. Assuming the input data points are sampled from a Gaussian distribution is often done for proving convergence results Zhong et al. (2017b); Li and Yuan (2017); Zhong et al. (2017a); Ge et al. (2018); Bakshi et al. (2019); Chen et al. (2020). A more closely related work is the work of Daniely (2020) who introduced the coupled initialization technique, and showed that $\widetilde{O}(n/d)$ hidden neurons can memorize all but an $\epsilon$ fraction of $n$ random binary labels of points uniformly distributed on the sphere. Similar results were obtained for random vertices of a unit hypercube and for random orthonormal basis vectors. In contrast to our work, this reference uses stochastic gradient descent, where the nice assumption on the input distribution gives rise to the $1/d$ factor; however, this reference achieves only an approximate memorization. We note that full memorization of all input points is needed to achieve our goal of an error arbitrarily close to zero, and $\Omega(n)$ neurons are needed for worst case inputs. Similarly, though not necessarily relying on random inputs, Bubeck et al. (2020) shows that for well-dispersed inputs, the neural tangent kernel (with ReLU network) can memorize the input data with $\widetilde{O}(n/d)$ neurons. However, their training algorithm is neither a gradient descent nor a stochastic gradient descent algorithm, and also their network consists of complex weights rather than real weights. One motivation of our work is to analyze standard algorithms such as gradient descent. In this work, we do not make any input distribution assumptions; therefore, these works are incomparable to ours. In particular, random data sets are often well-dispersed inputs that allow smaller width and tighter concentration, but are hardly realistic. In contrast, we conduct worst case analyses to cover all possible inputs, which might not be well-dispersed in practice.

Convergence results of neural networks in the under-parameterized setting. When considering classification with cross-entropy (logistic) loss, the analogue of the minimum eigenvalue parameter of the kernel matrix is the maximum separation margin $\gamma$ (see Assumption  3.1 for a formal definition) in the RKHS of the NTK. Previous separability assumptions on an infinite-width two-layer ReLU network in Cao and Gu (2019b, a) and on smooth target functions in Allen-Zhu et al. (2019a) led to polynomial dependencies between the width $m$ and the number $n$ of input points. The work of Nitanda et al. (2019) relies on the NTK separation mentioned above and improved the dependence, but was still polynomial.

A recent work of Ji and Telgarsky (2020) gives the first convergence result based on an NTK analysis where the direct dependence on $n$, i.e., the number of points, is only poly-logarithmic. Specifically, they show that as long as the width of the neural network is polynomially larger than $1/\gamma$ and $\log n$, then gradient descent can achieve zero training loss.

Convergence results for neural networks in the over-parameterized setting. There is a body of work studying convergence results of over-parameterized neural networks Li and Liang (2018); Du et al. (2019c); Allen-Zhu et al. (2019c, b); Du et al. (2019b); Allen-Zhu et al. (2019a); Song and Yang (2019); Arora et al. (2019b, a); Cao and Gu (2019b); Zou and Gu (2019); Du et al. (2019a); Lee et al. (2020); Huang and Yau (2020); Chen and Xu (2020); Brand et al. (2021); Li et al. (2021); Song et al. (2021). One line of work explicitly works on the neural tangent kernel Jacot et al. (2018) with kernel matrix $K$. This line of work shows that as long as the width of the neural network is polynomially larger than $n/\lambda_{\min}(K)$, then one can achieve zero training error. Another line of work instead assumes that the input data points are not too “collinear”, where this is formalized by the parameter $\delta=\min_{i\neq j}\{\|x_{i}-x_{j}\|_{2},\|x_{i}+x_{j}\|_{2}\}$²²2This is also sometimes called the separability of data points. Li and Liang (2018); Oymak and Soltanolkotabi (2020). These works show that as long as the width of the neural network is polynomially larger than $1/\delta$ and $n$, then one can train the neural network to achieve zero training error. The work of Song and Yang (2019) shows that the over-parameterization $m=\Omega(\lambda^{-4}n^{4})$ suffices for the same regime we consider³³3Although the title of Song and Yang (2019) is quadratic, $n^{2}$ is only achieved when the finite sample kernel matrix deviates from its limit in norm only by a constant $\alpha$ w.h.p., and the inputs are well-dispersed with constant $\theta$, i.e., $|\langle x_{i},x_{j}\rangle|\leq\theta/\sqrt{n}$ for all $i\neq j$. In general, Song and Yang (2019) only achieve a bound of $n^{4}$. . Additional work claims that even a linear dependence is possible, though it is in a different setting. E.g., Kawaguchi and Huang (2019) show that for any neural network with nearly linear width, there exists a trainable data set. Although their width is small, this work does not provide a general convergence result. Similarly, Zhang et al. (2021) use a coupled LeCun initialization scheme that also forces the output at initalization to be $0$. This is shown to improve the width bounds for shallow networks below $n$ neurons. However, their convergence analysis is local and restricted to cases where it remains unclear how to find globally optimal or even approximate solutions. We instead focus on cases where gradient descent provably optimizes up to arbitrary small error, for which we give a lower bound of $\Omega(n)$.

Other than considering over-parameterization in first-order optimization algorithms, such as gradient descent, Brand et al. (2021) show convergence results via second-order optimization, such as Newton’s method. Their running time also relies on $m=\Omega(\lambda^{-4}n^{4})$, which is the state-of-the-art width for first-order methods Song and Yang (2019), and it was noted that any improvement to $m$ would yield an improved running time bound.

Our work presented in this paper continues and improves those lines of research on understanding two-layer ReLU networks.

In this work, we mainly focus on two different types of loss functions. The binary cross-entropy (logistic) loss and the squared loss. These loss functions are arguably the most well-studied for binary classification and for regression tasks with low numerical error, respectively.

We are given a set of $n$ input data points and corresponding labels, denoted by

$\displaystyle\{(x_{1},y_{1}),\ldots,(x_{n},y_{n})\}\subset\mathbb{R}^{d}\times\mathbb{R}.$

We make a standard normalization assumption, as in Du et al. (2019c); Song and Yang (2019); Ji and Telgarsky (2020). In the case of logistic loss, the labels are restricted to $y_{i}\in\{-1,+1\}$. In the case of squared loss, the labels are $|y_{i}|=O(1)$. In both cases, as in prior work and for simplicity, we assume that $\|x_{i}\|_{2}=1$⁶⁶6 We adopt the assumption for a concise presentation, but we note it can be resolved by weaker constant bounds $0<\mathrm{lb}\leq\|x_{i}\|\leq\mathrm{ub}$, introducing a constant $\mathrm{ub}/\mathrm{lb}$ factor, cf. Du et al. (2019c), or otherwise the data can be rescaled and padded with an additional coordinate to ensure $\|x_{i}\|=1$, cf. Allen-Zhu et al. (2019a). , $\forall i\in[n]$. We also define the output function on input $x_{i}$ to be $f_{i}(W)=f(W,x_{i},a)$. At time $t$, let $u(W(t))=(u_{1}(W(t)),\ldots,u_{n}(W(t)))\in\mathbb{R}^{n}$ be the prediction vector, where each $u_{i}(W(t))$ is defined to be

$\displaystyle u_{i}(W(t))=f(W(t),x_{i},a).$

(3)

For simplicity, we use $u(t)$ to denote $u(W(t))$ in later discussion.

We consider the objective function $L$:

$\displaystyle L(W)=\sum_{i=1}^{n}\ell(y_{i},u_{i}(W))$

where the individual logistic loss is defined as $\ell(v_{1},v_{2})=\ln(1+\exp(-v_{1}v_{2}))$, and the individual squared loss is given by $\ell(v_{1},v_{2})=\frac{1}{2}(v_{1}-v_{2})^{2}$.

For logistic loss, we can compute the gradient⁵⁵footnotemark: 5 of $L$ in terms of $w_{r}\in\mathbb{R}^{d}$

$\displaystyle\frac{\partial L(W)}{\partial w_{r}}=\sum_{i=1}^{n}\frac{-\exp(-y_{i}f(W,x_{i},a))}{1+\exp(-y_{i}f(W,x_{i},a))}y_{i}a_{r}x_{i}{\bf 1}_{w_{r}^{\top}x_{i}\geq 0}$

(4)

For squared loss, we can compute the gradient⁵⁵footnotemark: 5  of $L$ in terms of $w_{r}\in\mathbb{R}^{d}$

$\displaystyle\frac{\partial L(W)}{\partial w_{r}}=\sum_{i=1}^{n}(f(W,x_{i},a)-y_{i})a_{r}x_{i}{\bf 1}_{w_{r}^{\top}x_{i}\geq 0}.$

(5)

We apply gradient descent to optimize the weight matrix $W$ with the following standard update rule,

$\displaystyle W(t+1)=W(t)-\eta\frac{\partial L(W(t))}{\partial W(t)},$

(6)

where $0<\eta\leq 1$ determines the step size.

In our analysis, we assume that $W$ consists of $m_{0}$ blocks of Gaussian vectors, where in each block, there are $B$ identical copies of the same Gaussian vector. Thus, we have $m=m_{0}\cdot B$. Ultimately we show it already suffices to set $m_{0}=m/2$ and $B=2$. We use $w_{r,b}$ to denote the $b$-th row of the $r$-th block, where $b\in[B]$ and $r\in[m_{0}]$. When there is no confusion, we also use $w_{r}$ to denote the $r$-th row of $W$, $r\in[m]$.

The work of Ji and Telgarsky (2020) shows that we can bound the actual logistic loss averaged over $T$ gradient descent iterations $W_{t},t\in[T]$ using any reference parameterization $\overline{W}$ in the following NTK bound:

$\displaystyle\frac{1}{T}\sum_{t=1}^{T}L(W_{t})\leq\frac{1}{T}\|W_{0}-\overline{W}\|_{F}^{2}+\frac{2}{T}\sum_{t=1}^{T}L^{(t)}(\overline{W}),$

(7)

where $L^{(t)}(\overline{W}):=\sum_{i=1}^{n}\ell\left(y_{i},\langle\nabla f_{i}(W_{t}),\overline{W}\rangle\right)$. It seems very natural to choose $\overline{W}=W_{0}+\rho\overline{U}$ where $\overline{U}$ is a reasonably good separator for the NTK points with bounded norm $\|\overline{U}\|_{F}\leq 1$, meaning that for all $i$ it holds that $y_{i}\langle\nabla f_{i}(W_{0}),\overline{U}\rangle=\Omega(\gamma)$. It thus has the same margin as in the infinite case up to constants. This already implies that the first term of Eq. (7) is sufficiently small when we choose roughly $T=\rho^{2}/\epsilon$ iterations. Now, in order to bound the second term, Ji and Telgarsky (2020) propose to show $L^{(t)}(\overline{W})\leq\epsilon$ for every $t\leq T$, which is implied if for each index $i\in[n]$ we have that

$\displaystyle y_{i}\langle$

$\displaystyle\nabla f_{i}(W_{t}),\overline{W}\rangle=y_{i}\langle\nabla f_{i}(W_{0}),W_{0}\rangle+y_{i}\langle\nabla f_{i}(W_{t})-\nabla f_{i}(W_{0}),W_{0}\rangle+\rho y_{i}\langle\nabla f_{i}(W_{t}),\overline{U}\rangle$

is sufficiently large. Here, we can leverage the coupled initialization scheme (Def. 2.1) to prove Theorem 3.1: bounding the first term for random Gaussian parameters, this results in roughly the value $\sqrt{\log n}$, but now since for each Gaussian vector there is another identical Gaussian with opposite signs, those simply cancel and we have $y_{i}\langle\nabla f_{i}(W_{0}),W_{0}\rangle=0$ in the initial state.

To bound the second term, the previous analysis Ji and Telgarsky (2020) relied on a proper scaling with respect to the parameters $m,\rho,$ and $\gamma$, where the requirement that $m\geq\rho^{2}/\gamma^{6}$ led to a bound of roughly $m\geq\gamma^{-8}\log n$. Using the coupled initialization, however, the terms again cancel in such a way that the scaling does not matter, and in particular does not need to be balanced among the variables. Another crucial insight is that the gradient is entirely independent of the scale of the parameter vectors in $W_{0}$. This implies $\nabla f_{i}(W_{t})=\nabla f_{i}(W_{0})$ and thus $y_{i}\langle\nabla f_{i}(W_{t})-\nabla f_{i}(W_{0}),W_{0}\rangle=0$ again, notably without any implications for the width of the neural network!

Indeed, the only place in the analysis where the width is constrained by roughly $m\geq\gamma^{-2}\log n$ occurs when bounding the contribution of the third term by $\rho y_{i}\langle\nabla f_{i}(W_{t}),\overline{U}\rangle=\rho y_{i}\langle\nabla f_{i}(W_{0}),\overline{U}\rangle=\Omega(\rho\gamma)$. This is done exactly as in Ji and Telgarsky (2020) by a Hoeffding bound to relate the separation margin of the finite subsample to the separation margin of the infinite width case, i.e.,

$\displaystyle y_{i}\frac{1}{m}$

$\displaystyle\sum\limits_{j=1}^{m}\langle\overline{v}(z_{j}),x_{i}\rangle\mathbf{1}[\langle z_{j},x_{i}\rangle>0]\approx y_{i}\int\langle\overline{v}(z),x_{i}\rangle\mathbf{1}[\langle z,x_{i}\rangle>0]~{}\mathsf{d}\mu_{N}(z)\geq\gamma$

(8)

followed by a union bound over all $n$ input points.

The special and natural choice of $\overline{U}$ such that $\overline{u}_{j}=a_{j}\overline{v}(z_{j})/\sqrt{m}$ yields Eq. (8) above, where notably the LHS equals the RHS in expectation. We will discuss this particular choice again in our lower bounds section 4.2.

Our assumption on the separation margin is formally defined in Section C where we also give several examples and useful lemmas to bound $\gamma$. Our lower bounds in Section D are based on the following hard instance in $2$ dimensions. The points are equally spaced and with alternating labels on the unit circle.

Formally, let $n$ be divisible by $4$. We define the alternating points on the circle data set to be $X=\{x_{k}:=\left(\cos\left(\frac{2k\pi}{n}\right),\sin\left(\frac{2k\pi}{n}\right)\right)\mid k\in[n]\}\subset\mathbb{R}^{2}$, and we put $y_{k}=(-1)^{k}$ for each $k\in[n]$.

A natural choice for $\overline{v}$ would send any $z\in\mathbb{R}^{d}$ to its closest point in our data set $X$, multiplied by its label. However, applying Lemma C.2 gives us the following improved mapping, which is even optimal by Lemma C.5: note that for any $z\in\mathbb{R}^{d}$ that is not collinear with any input point, there exists a unique $i_{z}$ such that $z\in{\rm Cone}(\{x_{i_{z}},x_{i_{z}+1}\})$. Instead of mapping to the closest input point, in what follows, we map to a point that is nearly orthogonal to $z$,

$\displaystyle r_{z}:=\frac{x_{i_{z}}y_{i_{z}}+x_{i_{z}+1}y_{i_{z}+1}}{\|x_{i_{z}}-x_{i_{z}+1}\|_{2}}.$

More precisely we define $\overline{v}:\mathbb{R}^{d}\rightarrow\mathbb{R}^{d}$ by

$$\overline{v}(z)=\begin{cases}0&\text{, if }\exists x_{i}\in X,\tau\geq 0:z=\tau x_{i}\\ (-1)^{n/4+1}r_{z}&\text{, otherwise}.\end{cases}$$

See Fig. 1 for an illustration. We show in Lemma D.2 that $\gamma_{\overline{v}}=\gamma(X,Y)=\Omega(n^{-1})$ and consequently $n=\Omega(\gamma^{-1})$. Now we can derive our lower bounds under increasingly stronger assumptions as follows:

For the first unconditional bound, Theorem 3.2, we map the input points on the unit circle by contraction to the unit $\ell_{1}$ ball and note that by doing so, the labels remain in alternating order. Next we note that the output function $f$ of our network restricted to the $\ell_{1}$ ball is a piecewise linear function of $x$ and thus its gradient $\frac{\partial f}{\partial x}$ can only change in the vertices of the ball or where $x$ is orthogonal to one of the parameter vectors $w_{s}$, i.e., at most $O(m)$ times. Now consider any triple of consecutive points. Since they have alternating labels, the gradient needs to change at least once for each triple. Consequently $m=\Omega(n)=\Omega(\gamma^{-1})$, improving the $\Omega(\gamma^{-1/2})$ conditional lower bound in Ji and Telgarsky (2020). We remark that since the argument only depends on the output function but not on the loss function, Lemma D.4 yields an $m=\Omega(n)$ lower bound for any loss function, in particular also for squared loss.

Now consider any argument that relies on an NTK analysis, where the fist step is to show that for our choice of the width $m$, we have separability at initialization; this is how the argument in Ji and Telgarsky (2020) proceeds. Formally, assume that there exists $W\in\mathbb{R}^{m\times d}$ such that for all $i\in[n]$, we have $y_{i}\langle\nabla f_{i}(W_{0}),W\rangle>0$. This condition enables us to show an improved lower bound, Theorem 3.3, as follows. Partition our data set into tuples, each consisting of four consecutive points. Now consider the event that there exists a point $x_{i}$ such that all parameter vectors $w_{s}$ satisfy

$\displaystyle\mathbf{1}[\langle x_{i},w_{s}\rangle>0]$

$\displaystyle=\mathbf{1}[\langle x_{i+1},w_{s}\rangle>0]=\mathbf{1}[\langle x_{i+2},w_{s}\rangle>0]=\mathbf{1}[\langle x_{i+3},w_{s}\rangle>0],$

which implies that at least one of the points in $\{x_{i},x_{i+2},x_{i+3},x_{i+4}\}$ is misclassified. To avoid this, it means that our initialization necessarily needs to include, for each $i$ divisible by $4$, a vector $w_{s}$ that hits the areas orthogonal to the cones separating two points out of the quadruple. There are $O(n)$ quadruples to hit, each succeeding with probability $\Omega(n^{-1})$ with respect to the Gaussian measure. This is exactly the coupon collector’s problem, where the coupons are the quadruples, and it is known Erdős and Rényi (1961) that $m=\Omega(n\log n)=\Omega(\gamma^{-1}\log n)$ are necessary to collect all $O(n)$ items with constant probability, which yields our improved lower bound for this style of analysis. One thus needs a different approach beyond NTK to break this barrier, cf. Ji and Telgarsky (2020).

For the upper bound, Theorem 3.1, we further note that the existence of an NTK separator $W$ as above is not sufficient, i.e., we need to construct a separator $\overline{U}$ satisfying the separability condition. Moreover, to achieve a reasonable bound in terms of the margin parameter $\gamma^{-1}$ we also need that $\overline{U}$ achieves a separation margin of $\Omega(\gamma)$. To do so, it seems natural to construct $\overline{U}$ such that $\overline{u}_{j}=a_{j}\overline{v}(w_{j})/\sqrt{m}$ for all $j\in[m]$. Indeed, this is the most natural choice because the resulting separation margin in the finite case is exactly the empirical mean estimator for the infinite case and thus standard concentration bounds (Hoeffing’s bound) yield the necessary proximity of the margins between the two cases, cf. Eq. (8). Let us assume we fix this choice of $\overline{U}$. This condition enables us to prove a quadratic lower bound, Lemma 3.4, which shows that our analysis of the upper bound is actually tight: for our alternating points on a circle example, the summands have high variance, and therefore Hoeffding’s bound is tight by a matching lower bound Feller (1943). Consequently, $m=\Omega(\gamma^{2}\log n)$, and one would need a different definition of $\overline{U}$ and a non-standard estimation of $\gamma$ to break this barrier.

Finally, we conjecture that the quadratic upper bound is actually tight in general. Specifically, we conjecture the following: take $n=1/\gamma^{2}$ random points on the sphere in $\Theta(\log(1/\gamma))$ dimensions and assign random labels $y_{i}\in\{-1,1\}$. Then the NTK margin is $\Omega(\gamma)$.

If the conjecture is true, we obtain an $\Omega(1/\gamma^{2})$ lower bound for $m$, up to logarithmic factors.⁷⁷7This might be confusing, since we argued before that such data is particularly mild for the squared loss function. This may be due to the different loss functions, but regardless, it does not contradict the $\widetilde{O}(n/d)$ bound of Daniely (2020) for the same data distribution in the squared loss regime, since $n/d=\Theta(1/(\gamma^{2}\log(1/\gamma)))$. Indeed, we can round the weights to the nearest vectors in a net of size $\operatorname{poly}(1/\gamma)^{O(\log(1/\gamma))}$, which only changes $\gamma$ by a constant factor. Then, if we could classify with zero error, we would encode $n=1/\gamma^{2}$ random labels using $m\log^{O(1)}(1/\gamma)$ bits, which implies $m\geq\Omega(1/(\gamma^{2}\log^{O(1)}(1/\gamma)))$. We note that Ji and Telgarsky (2020) gave an $O(1/\sqrt{n})$ upper bound for the margin of any data with random labels, but we would need a matching $\Omega(1/\sqrt{n})$ lower bound for this instance in order for this argument to work.

The high level intuition of our proof of Theorem 3.6 is to recursively prove the following: (1) the weight matrix does not change much, and (2) given that the weight matrix does not change much, the prediction error, measured by the squared loss, decays exponentially.

Given (1) we prove (2) as follows. The intuition is that the kernel matrix does not change much, since the weights do not change much, and it is close to the initial value of the kernel matrix, which is in turn close to the NTK matrix, involving the entire Gaussian distribution rather than our finite sample. The NTK matrix has a lower bound on its minimum eigenvalue by Assumption 3.3. Thus, the prediction loss decays exponentially.

Given (2) we prove (1) as follows. Since the prediction error decays exponentially, one can show that the change in weights is upper bounded by the prediction loss, and thus the change in weights also decays exponentially and the total change is small.

First, we show a concentration lemma for initialization:

Second, we can show a perturbation bound for random weights.

Next, we have the following lemma (see Section I for a formal proof) stating that the weights should not change too much. Note that the lemma is a variation of Corollary 4.1 in Du et al. (2019c).

Next, we calculate the difference of predictions between two consecutive iterations, analogous to the $\frac{\mathsf{d}u_{i}(t)}{\mathsf{d}t}$ term in Fact H.1. For each $i\in[n]$, we have

$\displaystyle u_{i}(t+1)-u_{i}(t)=\sum_{r=1}^{m}$

$\displaystyle a_{r}\cdot\left(\phi(w_{r}(t+1)^{\top}x_{i})-\,\phi(w_{r}(t)^{\top}x_{i})\right)=\sum_{r=1}^{m}a_{r}\cdot z_{i,r}.$

where

$\displaystyle z_{i,r}:=\phi\left(\Big{(}w_{r}(t)-\eta\frac{\partial L(W(t))}{\partial w_{r}(t)}\Big{)}^{\top}x_{i}\right)-\phi(w_{r}(t)^{\top}x_{i}).$

Here we divide the right hand side into two parts. First, $v_{1,i}$ represents the terms for which the pattern does not change, while $v_{2,i}$ represents the terms for which the pattern may change. For each $i\in[n]$, we define the set $S_{i}\subset[m]$ as

$\displaystyle S_{i}:=~{}\{r\in[m]:\forall w\in\mathbb{R}^{d}$

$\displaystyle\text{ s.t. }\|w-w_{r}(0)\|_{2}\leq R,\text{ and }\mathbf{1}_{w_{r}(0)^{\top}x_{i}\geq 0}=\mathbf{1}_{w^{\top}x_{i}\geq 0}\}.$

Then we define $v_{1,i}$ and $v_{2,i}$ as follows

$\displaystyle v_{1,i}:=\sum_{r\in S_{i}}a_{r}z_{i,r},\qquad v_{2,i}:=\sum_{r\in\overline{S}_{i}}a_{r}z_{i,r}.$

Define $H$ and $H^{\bot}\in\mathbb{R}^{n\times n}$ as

	$\displaystyle H(t)_{i,j}:=$	$\displaystyle~{}\frac{1}{m}\sum_{r=1}^{m}x_{i}^{\top}x_{j}{\bf 1}_{w_{r}(t)^{\top}x_{i}\geq 0,w_{r}(t)^{\top}x_{j}\geq 0},$		(9)
	$\displaystyle H(t)^{\bot}_{i,j}:=$	$\displaystyle~{}\frac{1}{m}\sum_{r\in\overline{S}_{i}}x_{i}^{\top}x_{j}{\bf 1}_{w_{r}(t)^{\top}x_{i}\geq 0,w_{r}(t)^{\top}x_{j}\geq 0},$		(10)

and

	$\displaystyle C_{1}:=-2\eta(y-u(t))^{\top}H(t)(y-u(t)),\qquad C_{2}:=+2\eta(y-u(t))^{\top}H(t)^{\bot}(y-u(t)),$
	$\displaystyle C_{3}:=-2(y-u(t))^{\top}v_{2},\qquad\qquad\qquad\qquad\!C_{4}:=\|u(t+1)-u(t)\|_{2}^{2}.$

Then we have that (see Section I for a formal proof)