Last iterate convergence in no-regret learning: constrained min-max optimization for convex-concave landscapes

Despite the rich literature on no-regret learning, most of the known results have the feature that min-max equilibrium is shown to be attained only by the time average. This means that the trajectory of a no-regret learning method $(\mathbf{x}^{t},\mathbf{y}^{t})$ has the property that ${1\over t}\sum_{\tau\leq t}{\mathbf{x}^{\tau}}^{\top}A\mathbf{y}^{\tau}$ converges to the equilibrium of (1), as $t\rightarrow\infty$. Unfortunately that does not mean that the last iterate $(\mathbf{x}^{t},\mathbf{y}^{t})$ converges to an equilibrium, it commonly diverges or cycles. One such example is the well-known Multiplicative Weights Update Algorithm, the time average of which is known to converge to an equilibrium, but the actual trajectory cycles towards the boundary of the simplex ([3]). This is even true for the vanilla Gradient Descent/Ascent, where one can show for even bilinear landscapes (unconstrained case) last iterate fails to converge [6].

Motivated by the training of Generative Adversarial Networks (GANs), the last couple of years researchers have focused on designing and analyzing procedures that exhibit last iterate convergence (or pointwise convergence) for zero-sum games. This is crucial for training GANs, the landscapes of which are typically non-convex non-concave and averaging now as before does not give much guarantees (e.g., note that Jensen’s inequality is not applicable anymore). In [6, 10] the authors show that a variant of Gradient Descent/Ascent, called Optimistic Gradient Descent/Ascent has last iterate convergence for the case of bilinear functions $\mathbf{x}^{\top}A\mathbf{y}$ where $\mathbf{x}\in\mathbb{R}^{n}$ and $\mathbf{y}\in\mathbb{R}^{m}$ (this is called the unconstrained case, since there are no restrictions on the vectors). Later on, [8] generalized the above result with simplex constraints, where the online method that the authors analyzed was Optimistic Multiplicative Weights Update. In [11], it is shown that Mirror Descent with extra gradient computation converges pointwise for a class of zero-sum games that includes the convex-concave setting (with arbitrary constraints), though their algorithm does not fit in the online no-regret framework since it uses information twice about the payoffs before it iterates. Last but not least there have appeared other works that show pointwise convergence for other settings (see [13, 7] and [1] and references therein) to stationary points (but not local equilibrium solutions).

In this paper, we focus on the min-max optimization problem

$\displaystyle\min_{\mathbf{x}\in\Delta_{n}}\max_{\mathbf{y}\in\Delta_{m}}f(\mathbf{x},\mathbf{y}),$

(3)

where $f$ is a convex-concave function (convex in $\mathbf{x}$, concave in $\mathbf{y}$). We analyze the no-regret online algorithm Optimistic Multiplicative Weights Update (OMWU). OMWU is an instantiation of the Optimistic Follow the Regularized Leader (OFTRL) method with entropy as a regularizer (for both players, see Preliminaries section for the definition of OMWU).

We prove that OMWU exhibits local last iterate convergence, generalizing the result of [8] and proving an open question of [15] (for convex-concave games). Formally, our main theorem is stated below:

Moreover, we complement our theoretical findings with experimental analysis of the procedure. The experiments on KL-divergence indicate that the results should hold globally.

We present the structure of the paper and a brief technical overview.

Section 2 provides necessary definitions, the explicit form of OMWU derived from OFTRL with entropy regularizer, and some existing results on dynamical systems.

Section 3 is the main technical part, i.e, the computation and spectral analysis of the Jacobian matrix of OMWU dynamics. The stability analysis, the understanding of the local behavior and the local convergence guarantees of OMWU rely on the spectral analysis of the computed Jacobian matrix. The techniques for bilinear games (as in [8]) are no longer valid in convex-concave games. Allow us to explain the differences from [8]. In general, one cannot expect a trivial generalization from linear to non-linear scenarios. The properties of bilinear games are fundamentally different from that of convex-concave games, and this makes the analysis much more challenging in the latter. The key result of spectral analysis in [8] is in a lemma (Lemma B.6) which states that a skew symmetric²²2$A$ is skew symmetric if $A^{\top}=-A$. has imaginary eigenvalues. Skew symmetric matrices appear since in bilinear cases there are terms that are linear in $\mathbf{x}$ and linear in $\mathbf{y}$ but no higher order terms in $\mathbf{x}$ or $\mathbf{y}$. However, the skew symmetry has no place in the case of convex-concave landscapes and the Jacobian matrix of OMWU is far more complicated. One key technique to overcome the lack of skew symmetry is the use of Ky Fan inequality [12] which states that the sequence of the eigenvalues of $\frac{1}{2}(W+W^{\top})$ majorizes the real part of the sequence of the eigenvalues of W for any square matrix W (see Lemma 3.1).

Section 4 focuses on numerical experiments to understand how the problem size and the choice of learning rate affect the performance of our algorithm. We observe that our algorithm is able to achieve global convergence invariant to the choice of learning rate, random initialization or problem size. As comparison, the latest popularized (projected) optimistic gradient descent ascent is much more sensitivity to the choice of hyperparameter. Due to space constraint, the detailed calculation of the Jacobian matrix (general form and at fixed point) of OMWU are left in Appendix.

From Von Neumann’s minimax theorem, one can conclude that the problem $\min_{\mathbf{x}\in\Delta_{n}}\max_{\mathbf{y}\in\Delta}f(\mathbf{x},\mathbf{y})$ has always an equilibrium $(\mathbf{x}^{*},\mathbf{y}^{*})$ with $f(\mathbf{x}^{*},\mathbf{y}^{*})$ be unique. Moreover from KKT conditions (as long as $f$ is twice differentiable), such an equilibrium must satisfy the following ($\mathbf{x}^{*}$ is a local minimum for fixed $\mathbf{y}=\mathbf{y}^{*}$ and $\mathbf{y}^{*}$ is a local maximum for fixed $\mathbf{x}=\mathbf{x}^{*}$):

The equations of Optimistic Follow-the-Regularized-Leader (OFTRL) applied to a problem
$\min_{\mathbf{x}\in\mathcal{X}}\max_{\mathbf{y}\in\mathcal{Y}}f(\mathbf{x},\mathbf{y})$ with regularizers (strongly convex functions) $h_{1}(\mathbf{x}),h_{2}(\mathbf{y})$ (for player $\mathbf{x},\mathbf{y}$ respectively) and $\mathcal{X}\subset\mathbb{R}^{n},\mathcal{Y}\subset\mathbb{R}^{m}$ is given below (see [6]):

	$\displaystyle\mathbf{x}^{t+1}$	$\displaystyle=\mathop{\mathbf{argmin}}_{\mathbf{x}\in\mathcal{X}}\{\eta\sum_{s=1}^{t}\mathbf{x}^{\top}\nabla_{\mathbf{x}}f(\mathbf{x}^{s},\mathbf{y}^{s})+\underbrace{\eta\mathbf{x}^{\top}\nabla_{\mathbf{x}}f(\mathbf{x}^{t},\mathbf{y}^{t})}_{\textrm{optimistic term}}+h_{1}(\mathbf{x})\}$
	$\displaystyle\mathbf{y}^{t+1}$	$\displaystyle=\mathop{\mathbf{argmax}}_{\mathbf{y}\in\mathcal{Y}}\{\eta\sum_{s=1}^{t}\mathbf{y}^{\top}\nabla_{\mathbf{y}}f(\mathbf{x}^{s},\mathbf{y}^{s})+\underbrace{\eta\mathbf{y}^{\top}\nabla_{\mathbf{y}}f(\mathbf{x}^{t},\mathbf{y}^{t})}_{\textrm{optimistic term}}-h_{2}(\mathbf{y})\}.$

$\eta$ is called the stepsize of the online algorithm. OFTRL is uniquely defined if $f$ is convex-concave and domains $\mathcal{X}$ and $\mathcal{Y}$ are convex. For simplex constraints and entropy regularizers, i.e., $h_{1}(\mathbf{x})=\sum_{i}x_{i}\ln x_{i},h_{2}(\mathbf{y})=\sum_{i}y_{i}\ln y_{i}$, we can solve for the explicit form of OFTRL using KKT conditions, the update rule is the Optimistic Multiplicative Weights Update (OMWU) and is described as follows:

	$\displaystyle x_{i}^{t+1}$	$\displaystyle=x_{i}^{t}\frac{e^{-2\eta\frac{\partial f}{\partial x_{i}}(\mathbf{x}^{t},\mathbf{y}^{t})+\eta\frac{\partial f}{\partial x_{i}}(\mathbf{x}^{t-1},\mathbf{y}^{t-1})}}{\sum_{k}x_{k}^{t}e^{-2\eta\frac{\partial f}{\partial x_{k}}(\mathbf{x}^{t},\mathbf{y}^{t})+\eta\frac{\partial f}{\partial x_{k}}(\mathbf{x}^{t-1},\mathbf{y}^{t-1})}}$
		$\displaystyle\text{for all }i\in[n],$
	$\displaystyle y_{i}^{t+1}$	$\displaystyle=y_{i}^{t}\frac{e^{2\eta\frac{\partial f}{\partial y_{i}}(\mathbf{x}^{t},\mathbf{y}^{t})-\eta\frac{\partial f}{\partial y_{i}}(\mathbf{x}^{t-1},\mathbf{y}^{t-1})}}{\sum_{k}y_{k}^{t}e^{2\eta\frac{\partial f}{\partial y_{j}}(\mathbf{x}^{t},\mathbf{y}^{t})-\eta\frac{\partial f}{\partial y_{k}}(\mathbf{x}^{t-1},\mathbf{y}^{t-1})}}$
		$\displaystyle\text{for all }i\in[m].$

We conclude Preliminaries section with some basic facts from dynamical systems.

Note that we will make use of Proposition 2.5 to prove our Theorem 1.1 (by proving that the Jacobian of the update rule of OMWU has spectral radius less than one).

We first express OMWU algorithm as a dynamical system so that we can use Proposition 2.5. The idea (similar to [8]) is to lift the space to consist of four components $(\mathbf{x},\mathbf{y},\mathbf{z},\mathbf{w}$, in such a way we can include the history (current and previous step, see Section 2.2 for the equations). First, we provide the update rule $g:\Delta_{n}\times\Delta_{m}\times\Delta_{n}\times\Delta_{m}\to\Delta_{n}\times\Delta_{m}\times\Delta_{n}\times\Delta_{m}$ of the lifted dynamical system and is given by

$$g(\mathbf{x},\mathbf{y},\mathbf{z},\mathbf{w})=(g_{1},g_{2},g_{3},g_{4})$$

where $g_{i}=g_{i}(\mathbf{x},\mathbf{y},\mathbf{z},\mathbf{w})$ for $i\in[4]$ are defined as follows:

	$\displaystyle g_{1,i}(\mathbf{x},\mathbf{y},\mathbf{z},\mathbf{w})$	$\displaystyle=x_{i}\frac{e^{-2\eta\frac{\partial f}{\partial x_{i}}(\mathbf{x},\mathbf{y})+\eta\frac{\partial f}{\partial z_{i}}(\mathbf{z},\mathbf{w})}}{\sum_{k}x_{k}e^{-2\eta\frac{\partial f}{\partial x_{k}}(\mathbf{x},\mathbf{y})+\eta\frac{\partial f}{\partial z_{k}}(\mathbf{z},\mathbf{w})}},i\in[n]$		(5)
	$\displaystyle g_{2,i}(\mathbf{x},\mathbf{y},\mathbf{z},\mathbf{w})$	$\displaystyle=y_{i}\frac{e^{2\eta\frac{\partial f}{\partial y_{i}}(\mathbf{x},\mathbf{y})-\eta\frac{\partial f}{\partial w_{i}}(\mathbf{z},\mathbf{w})}}{\sum_{k}y_{k}e^{2\eta\frac{\partial f}{\partial y_{k}}(\mathbf{x},\mathbf{y})-\eta\frac{\partial f}{\partial w_{k}}(\mathbf{z},\mathbf{w})}},i\in[m]$		(6)
	$\displaystyle g_{3}(\mathbf{x},\mathbf{y},\mathbf{z},\mathbf{w})$	$\displaystyle=\mathbf{x}\ \ \ \text{or}\ \ g_{3,i}(\mathbf{x},\mathbf{y},\mathbf{z},\mathbf{w})=x_{i},\ i\in[n]$		(7)
	$\displaystyle g_{4}(\mathbf{x},\mathbf{y},\mathbf{z},\mathbf{w})$	$\displaystyle=\mathbf{y}\ \ \ \text{or}\ \ g_{4,i}(\mathbf{x},\mathbf{y},\mathbf{z},\mathbf{w})=y_{i},\ i\in[m].$		(8)

Then the dynamical system of OMWU can be written in compact form as

$$(\mathbf{x}_{t+1},\mathbf{y}_{t+1},\mathbf{x}_{t},\mathbf{y}_{t})=g(\mathbf{x}_{t},\mathbf{y}_{t},\mathbf{x}_{t-1},\mathbf{y}_{t-1}).$$

In what follows, we will perform spectral analysis on the Jacobian of the function $g$, computed at the fixed point $(\mathbf{x}^{*},\mathbf{y}^{*})$. Since $g$ has been lifted, the fixed point we analyze is $(\mathbf{x}^{*},\mathbf{y}^{*},\mathbf{x}^{*},\mathbf{y}^{*})$ (see Remark 2.4). By showing that the spectral radius is less than one, our Theorem 1.1 follows by Proposition 2.5. The computations of the Jacobian of $g$ are deferred to the supplementary material.

Let $(\mathbf{x}^{*},\mathbf{y}^{*})$ be the equilibrium of min-max problem (2). Assume $i\notin\textrm{Supp}(\mathbf{x}^{*})$, i.e., $x_{i}^{*}=0$ then (see equations at the supplementary material, section A)

$$\frac{\partial g_{1,i}}{\partial x_{i}}(\mathbf{x}^{*},\mathbf{y}^{*},\mathbf{x}^{*},\mathbf{y}^{*})=\frac{e^{-\eta\frac{\partial f}{\partial x_{i}}(\mathbf{x}^{*},\mathbf{y}^{*})}}{\sum_{t=1}^{n}x^{*}_{t}e^{-\eta\frac{\partial f}{\partial x_{t}}(\mathbf{x}^{*},\mathbf{y}^{*})}}$$

and all other partial derivatives of $g_{1,i}$ are zero, thus $\frac{e^{-\eta\frac{\partial f}{\partial x_{i}}(\mathbf{x}^{*},\mathbf{y}^{*})}}{\sum_{t=1}^{n}x^{*}_{t}e^{-\eta\frac{\partial f}{\partial x_{t}}(\mathbf{x}^{*},\mathbf{y}^{*})}}$ is an eigenvalue of the Jacobian computed at $(\mathbf{x}^{*},\mathbf{y}^{*},\mathbf{x}^{*},\mathbf{y}^{*})$. This is true because the row of the Jacobian that corresponds to $g_{1,i}$ has zeros everywhere but the diagonal entry. Moreover because of the degeneracy assumption of KKT conditions (see Remark 2.2), it holds that

$$\frac{e^{-\eta\frac{\partial f}{\partial x_{i}}(\mathbf{x}^{*},\mathbf{y}^{*})}}{\sum_{t=1}^{n}x^{*}_{t}e^{-\eta\frac{\partial f}{\partial x_{t}}(\mathbf{x}^{*},\mathbf{y}^{*})}}<1.$$

Similarly, it holds for $j\notin\textrm{Supp}(\mathbf{y}^{*})$ that

$$\frac{\partial g_{2,j}}{\partial y_{j}}(\mathbf{x}^{*},\mathbf{y}^{*},\mathbf{x}^{*},\mathbf{y}^{*})=\frac{e^{\eta\frac{\partial f}{\partial y_{j}}(\mathbf{x}^{*},\mathbf{y}^{*})}}{\sum_{t=1}^{m}y^{*}_{t}e^{\eta\frac{\partial f}{\partial y_{t}}(\mathbf{x}^{*},\mathbf{y}^{*})}}<1$$

(again by Remark 2.2) and all other partial derivatives of $g_{2,j}$ are zero, therefore $\frac{e^{\eta\frac{\partial f}{\partial y_{j}}(\mathbf{x}^{*},\mathbf{y}^{*})}}{\sum_{t=1}^{m}y^{*}_{t}e^{\eta\frac{\partial f}{\partial y_{t}}(\mathbf{x}^{*},\mathbf{y}^{*})}}$ is an eigenvalue of the Jacobian computed at $(\mathbf{x}^{*},\mathbf{y}^{*},\mathbf{x}^{*},\mathbf{y}^{*})$.

We focus on the submatrix of the Jacobian of $g$ computed at $(\mathbf{x}^{*},\mathbf{y}^{*},\mathbf{x}^{*},\mathbf{y}^{*})$ that corresponds to the non-zero probabilities of $\mathbf{x}^{*}$ and $\mathbf{y}^{*}$. We denote $D_{\mathbf{x}^{*}}$ to be the diagonal matrix of size $\left|\text{Supp}(\mathbf{x}^{*})\right|\times\left|\text{Supp}(\mathbf{x}^{*})\right|$ that has on the diagonal the nonzero entries of $\mathbf{x}^{*}$ and similarly we define $D_{\mathbf{y}^{*}}$ of size $\left|\text{Supp}(\mathbf{y}^{*})\right|\times\left|\text{Supp}(\mathbf{y}^{*})\right|$. For convenience, let us denote $k_{x}:=\left|\text{Supp}(\mathbf{x}^{*})\right|$ and $k_{y}:=\left|\text{Supp}(\mathbf{y}^{*})\right|$. The Jacobian submatrix is the following

$$J=\left[\begin{array}[]{cccc}A_{11}&A_{12}&A_{13}&A_{14}\\ A_{21}&A_{22}&A_{23}&A_{24}\\ \mathbf{I}_{k_{x}\times k_{x}}&\mathbf{0}_{k_{x}\times k_{y}}&\mathbf{0}_{k_{x}\times k_{x}}&\mathbf{0}_{k_{x}\times k_{y}}\\ \mathbf{0}_{k_{y}\times k_{x}}&\mathbf{I}_{k_{y}\times k_{y}}&\mathbf{0}_{k_{y}\times k_{x}}&\mathbf{0}_{k_{y}\times k_{y}}\end{array}\right]$$

where

$\displaystyle\begin{split}A_{11}&=\mathbf{I}_{k_{x}\times k_{x}}-D_{\mathbf{x}^{*}}\mathbf{1}_{k_{x}}\mathbf{1}_{k_{x}}^{\top}-2\eta D_{\mathbf{x}^{*}}(\mathbf{I}_{k_{x}\times k_{x}}-\mathbf{1}_{k_{x}}\mathbf{x}^{*\top})\nabla_{\mathbf{x}\mathbf{x}}^{2}f\\ A_{12}&=-2\eta D_{\mathbf{x}^{*}}(\mathbf{I}_{k_{x}\times k_{x}}-\mathbf{1}_{k_{x}}\mathbf{x}^{*\top})\nabla_{\mathbf{x}\mathbf{y}}^{2}f\\ A_{13}&=\eta D_{\mathbf{x}^{*}}(\mathbf{I}_{k_{x}\times k_{x}}-\mathbf{1}_{k_{x}}\mathbf{x}^{*\top})\nabla_{\mathbf{x}\mathbf{x}}^{2}f\\ A_{14}&=\eta D_{\mathbf{x}^{*}}(\mathbf{I}_{k_{x}\times k_{x}}-\mathbf{1}_{k_{x}}\mathbf{x}^{*\top})\nabla_{\mathbf{x}\mathbf{y}}^{2}f\\ A_{21}&=2\eta D_{\mathbf{y}^{*}}(\mathbf{I}_{k_{y}\times k_{y}}-\mathbf{1}_{k_{y}}\mathbf{y}^{*\top})\nabla_{\mathbf{y}\mathbf{x}}^{2}f\\ A_{22}&=\mathbf{I}_{k_{y}\times k_{y}}-D_{\mathbf{y}^{*}}\mathbf{1}_{k_{y}}\mathbf{1}_{k_{y}}^{\top}+2\eta D_{\mathbf{y}^{*}}(\mathbf{I}_{k_{y}\times k_{y}}-\mathbf{1}_{k_{y}}\mathbf{y}^{*\top})\nabla_{\mathbf{y}\mathbf{y}}^{2}f\\ A_{23}&=-\eta D_{\mathbf{y}^{*}}(\mathbf{I}_{k_{y}\times k_{y}}-\mathbf{1}_{k_{y}}\mathbf{y}^{*\top})\nabla_{\mathbf{y}\mathbf{x}}^{2}f\\ A_{24}&=-\eta D_{\mathbf{y}^{*}}(\mathbf{I}_{k_{y}\times k_{y}}-\mathbf{1}_{k_{y}}\mathbf{y}^{*\top})\nabla_{\mathbf{y}\mathbf{y}}^{2}f.\\ \end{split}$

(9)

We note that $\mathbf{I},\mathbf{0}$ capture the identity matrix and the all zeros matrix respectively (the appropriate size is indicated as a subscript). The vectors $(\mathbf{1}_{k_{x}},\mathbf{0}_{k_{y}},\mathbf{0}_{k_{x}},\mathbf{0}_{k_{y}})$ and $(\mathbf{0}_{k_{x}},\mathbf{1}_{k_{y}},\mathbf{0}_{k_{x}},\mathbf{0}_{k_{y}})$ are left eigenvectors with eigenvalue zero for the above matrix. Hence, any right eigenvector $(\mathbf{v_{x}},\mathbf{v_{y}},\mathbf{v_{z}},\mathbf{v_{w}})$ should satisfy the conditions $\mathbf{1}^{\top}\mathbf{v_{x}}=0$ and $\mathbf{1}^{\top}\mathbf{v_{y}}=0$. Thus, every non-zero eigenvalue of the above matrix is also a non-zero eigenvalue of the matrix below:

$$J_{\text{new}}=\left[\begin{array}[]{cccc}B_{11}&A_{12}&A_{13}&A_{14}\\ A_{21}&B_{22}&A_{23}&A_{24}\\ \mathbf{I}_{k_{x}\times k_{x}}&\mathbf{0}_{k_{x}\times k_{y}}&\mathbf{0}_{k_{x}\times k_{x}}&\mathbf{0}_{k_{x}\times k_{y}}\\ \mathbf{0}_{k_{y}\times k_{x}}&\mathbf{I}_{k_{y}\times k_{y}}&\mathbf{0}_{k_{y}\times k_{x}}&\mathbf{0}_{k_{y}\times k_{y}}\end{array}\right]$$

where

$$B_{11}=\mathbf{I}_{k_{x}\times k_{x}}-2\eta D_{\mathbf{x}^{*}}(\mathbf{I}_{k_{x}\times k_{x}}-\mathbf{1}_{k_{x}}\mathbf{x}^{*\top})\nabla_{\mathbf{x}\mathbf{x}}^{2}f,$$

$$B_{22}=\mathbf{I}_{k_{y}\times k_{y}}+2\eta D_{\mathbf{y}^{*}}(\mathbf{I}_{k_{y}\times k_{y}}-\mathbf{1}_{k_{y}}\mathbf{y}^{*\top})\nabla_{\mathbf{y}\mathbf{y}}^{2}f.$$

The characteristic polynomial of $J_{\text{new}}$ is obtained by finding $\det(J_{\text{new}}-\lambda\mathbf{I})$. One can perform row/column operations on $J_{\text{new}}$ to calculate this determinant, which gives us the following relation:

$$\det(J_{\text{new}}-\lambda\mathbf{I}_{2k_{x}\times 2k_{y}})=\left(1-2\lambda\right)^{(k_{x}+k_{y})}q\left(\frac{\lambda(\lambda-1)}{2\lambda-1}\right)$$

where $q(\lambda)$ is the characteristic polynomial of the following matrix

$$J_{\text{small}}=\left[\begin{array}[]{cccc}B_{11}-\mathbf{I}_{k_{x}\times k_{x}}&A_{12}\\ A_{21}&B_{22}-\mathbf{I}_{k_{y}\times k_{y}},\end{array}\right]$$

and $B_{11},B_{12},A_{12},A_{21}$ are the aforementioned sub-matrices. Notice that $J_{\text{small}}$ can be written as

$$J_{\text{small}}=2\eta\left[\begin{array}[]{cc}-(D_{\mathbf{x}^{*}}-\mathbf{x}^{*}\mathbf{x}^{*\top})&\mathbf{0}_{k_{x}\times k_{y}}\\ \mathbf{0}_{k_{y}\times k_{x}}&(D_{\mathbf{y}^{*}}-\mathbf{y}^{*}\mathbf{y}^{*\top})\end{array}\right]H$$

where,

$$H=\left[\begin{array}[]{cc}\nabla_{\mathbf{x}\mathbf{x}}^{2}f&\nabla_{\mathbf{x}\mathbf{y}}^{2}f\\ \nabla_{\mathbf{y}\mathbf{x}}^{2}f&\nabla_{\mathbf{y}\mathbf{y}}^{2}f\end{array}\right]$$

Notice here that $H$ is the Hessian matrix evaluated at the fixed point $(\mathbf{x}^{*},\mathbf{y}^{*})$, and is the appropriate sub-matrix restricted to the support of $\left|\text{Supp}(\mathbf{y}^{*})\right|$ and $\left|\text{Supp}(\mathbf{x}^{*})\right|$. Although, the Hessian matrix is symmetric, we would like to work with the following representation of $J_{\text{small}}$:

$$J_{\text{small}}=2\eta\left[\begin{array}[]{cc}(D_{\mathbf{x}^{*}}-\mathbf{x}^{*}\mathbf{x}^{*\top})&\mathbf{0}_{k_{x}\times k_{y}}\\ \mathbf{0}_{k_{y}\times k_{x}}&(D_{\mathbf{y}^{*}}-\mathbf{y}^{*}\mathbf{y}^{*\top})\end{array}\right]H^{-}$$

where,

$$H^{-}=\left[\begin{array}[]{cc}-\nabla_{\mathbf{x}\mathbf{x}}^{2}f&-\nabla_{\mathbf{x}\mathbf{y}}^{2}f\\ \nabla_{\mathbf{y}\mathbf{x}}^{2}f&\nabla_{\mathbf{y}\mathbf{y}}^{2}f\end{array}\right]$$

Let us denote any non-zero eigenvalue of $J_{\text{small}}$ by $\epsilon$ which may be a complex number. Thus $\epsilon$ is where $q(\cdot)$ vanishes and hence the eigenvalue of $J_{\text{new}}$ must satisfy the relation

$$\frac{\lambda(\lambda-1)}{2\lambda-1}=\epsilon$$

We are to now show that the magnitude of any eigenvalue of $J_{\text{new}}$ is strictly less than 1, i.e, $\left|\lambda\right|<1$. Trivially, $\lambda=\frac{1}{2}$ satisfies the above condition. Thus we need to show that the magnitude of $\lambda$ where $q(\cdot)$ vanishes is strictly less than 1. The remainder of the proof proceeds by showing the following two lemmas:

We first can see that $\eta$ which is the learning rate multiplies any eigenvalue and we may assume that whilst $\eta$ is positive, it may be chosen to be sufficiently small and hence the magnitude of any eigenvalue $\left|\epsilon\right|\downarrow 0$.