TITLE: Sum $\sum_{n=1}^\infty\frac{n+2}{n(n+1)2^{n+1}}$
QUESTION [1 upvotes]: I'm given the series
$$\sum_{n=1}^\infty\frac{n+2}{n(n+1)2^{n+1}}$$
I've tried splitting up the fractions to use the telescoping effect, but no terms seem to cancel out. Can someone help me out?

REPLY [2 votes]: The given expression can be written as
$$\frac{n+2}{n(n+1)2^{n+1}} = \frac{1}{n2^n} - \frac{1}{(n+1)2^{n+1}}$$ which is the desired telescopic sum

REPLY [1 votes]: Hint
Let $$\dfrac{n+2}{n(n+1)2^{n+1}}=f(n+1)-f(n)$$
where $f(m)=\dfrac{a_0+a_1m+a_2m^2+\cdots}{m2^m}$
$$\dfrac{n+2}{n(n+1)2^{n+1}}= \dfrac{n(a_0+a_1(n+1)+a_2(n+1)^2+\cdots)-2(n+1)(a_0+a_1n+a_2n^2+\cdots)}{n(n+1)2^{n+1}} $$
$$\implies n+2=n(a_0+a_1(n+1)+a_2(n+1)^2+\cdots)-2(n+1)(a_0+a_1n+a_2n^2+\cdots)$$
Compare the coefficients of $n^2$ and above to find $a_r=0\forall r\ge1$
$$\implies n+2=na_0-2(n+1)a_0=-2a_0-na_0$$
$$\implies a_0=-1$$


TITLE: Union of all possible intersections of sets
QUESTION [0 upvotes]: Suppose there are three points $x_1,x_2,x_3$, and they can be ranked in any order. For each order, e.g., $(x_1,x_2,x_3)$, each pair of points have a set, for example, regarding to this order, the sets are $S_{12},S_{13},S_{23}$. If we change the order of points, the resulting sets should be different, for example, if the order is $(x_3,x_2,x_1)$, the resulting sets are $\bar{S_{12}},\bar{S_{13}},\bar{S_{23}}$, where $S_{12}$ and $\bar{S_{12}}$ are complement to each other.
My question is, if for every order, a solution region is the intersection of sets. Then does the union region of all possible order is the whole space? For example, there are 3! orders and the corresponding solution region are:
$(x_1,x_2,x_3)$: $A_1 = S_{12}\cap S_{13} \cap S_{23}$
$(x_1,x_3,x_2)$: $A_2 = S_{12}\cap S_{13} \cap \bar{S_{23}}$
$(x_2,x_1,x_3)$: $A_3 = \bar{S_{12}}\cap S_{13} \cap S_{23}$
$(x_2,x_3,x_1)$: $A_4 = \bar{S_{12}}\cap \bar{S_{13}} \cap S_{23}$
$(x_3,x_1,x_2)$: $A_5 = S_{12}\cap \bar{S_{13}} \cap \bar{S_{23}}$
$(x_3,x_2,x_1)$: $A_6 = \bar{S_{12}}\cap \bar{S_{13}} \cap \bar{S_{23}}$
REVISED: Also, for each order, there is a transitivity property, for example, if the order is $(x_1,x_2,x_3)$, then $(S_{12}\cup S_{23}) \supseteq S_{13} \supseteq (S_{12}\cap S_{23})$ must holds. There might be some order whose solution region is empty. My problem is try to show the union of solution region for every possible order is an entire space.
Does the union of all these solution regions (for all possible orders), say $(A_1 \cup A_2 \cup A_3 \cup A_4 \cup A_5 \cup A_6)$ is the whole space (say $D$?) what if the number of points are $n$? I think it is true, but not easy to prove it. Hope somebody gives some clues. Thanks.

REPLY [1 votes]: I think what you are asking is this:
Suppose you have an ambient set $D$ and an ordered index list $\langle 1, 2, 3\rangle$. You assign to each pair of different indices $\langle i, j\rangle$ $(i\neq j \in \{1,2,3\})$ a subset $S_{i,j}\subseteq D$ which respects parity in the sense that $S_{i,j}$ and $S_{j,i}$ are complements of each other in $D$.
Then for any permutation $\langle i, j, k\rangle$ of $\langle 1, 2, 3\rangle$, you define the set
$$A_{i,j,k} \equiv S_{i,j} \cap S_{j,k} \cap S_{i,k}.$$
There are 6 such sets $A_{i,j,k}$ corresponding to the 3! permutations of $\langle 1, 2, 3\rangle$. Your question is whether the union over all six $A_{i,j,k}$ is necessarily equal to $D$.
I claim that the union of the $A_{i,j,k}$ is equal to $D$ if and only if the cyclic permutations $S_{1,2}, S_{2,3}, S_{3,1}$ have empty intersection and their union is $D$.

Let $A$ refer to the union of all six $A_{i,j,k}$.
Let us start by grouping the six results into pairs. Note that by the properties of union and intersection,
$$\begin{align*}A_{1,2,3} \cup A_{1,3,2} &= S_{1,2}\cap S_{1,3}\cap(S_{2,3} \cup S_{3,2})\\&= S_{1,2} \cap S_{1,3} \cap D\\ &= S_{1,2} \cap S_{1,3}\end{align*}$$
And similarly
$$\begin{align*}A_{2,1,3} \cup A_{2,3,1} &= S_{2,1} \cap S_{2,3}\\
A_{3,2,1} \cup A_{3,1,2} &= S_{3,2} \cap S_{3,1}.\\
\end{align*}$$
Hence
$$A = (S_{1,2}\cap S_{1,3})\cup (S_{2,1} \cap S_{2,3}) \cup (S_{3,2}\cap S_{3,1})$$
To expose the complementarity here, we can put $P \equiv S_{1,2}$, $Q\equiv S_{2,3}$, $R\equiv S_{3,1}$. Then
$$A = (P \cap R^C) \cup (Q \cap P^C) \cup (R \cap Q^C) $$
In which case, union/intersection laws (or drawing a Venn diagram) reveals that $A = D$ if and only if $P\cap Q\cap R = \varnothing$ and also $P\cup Q\cup R = D$.
(Intuitively, this is because none of the terms above intersects $P\cap Q\cap R$, because each term intersects the complement of one of them.)

I am not sure what this transitivity property means. I interpret it as meaning that for all permutations $\langle i,j,k\rangle$ of $\{1,2,3\}$ we must have $S_{i,j} = S_{i,k}\cap S_{k,j}$.
Using the fact that $S_{i,j} = S_{j,i}^C$ and DeMorgan's laws, you can prove that this means that $S_{i,k} = S_{k,j}$ for all permutations $\langle i,k,j\rangle$. Indeed,
$$\begin{align*}
S_{i,j} &= S_{j,i}^C\\
(S_{i,k}\cap S_{k,j}) &= (S_{j,k} \cap S_{k,i})^C\\
S_{i,k} \cap S_{k,j} &= S_{k,j} \cup S_{i,k}
\end{align*}$$
and the only time the intersection of two sets is equal to their union is if the two sets are the same.
Hence
$S_{i,j} = S_{j,k} = S_{k,i}$ for all permutations $\langle i,j,k\rangle$ of $\{1,2,3\}$.
In our specific case, let us define $S_+ = S_{1,2} = S_{2,3} = S_{3,1}$ and $S_- = S_{3,2} = S_{2,1} = S_{1,3}$. The sets $S_+$ and $S_-$ are requred to be complements, and we have that for all $\langle i,j,k\rangle$,
$$S_{i,j,k} = S_+ \text{ or } S_- \text{ or }\varnothing$$
The first case occurs when the indices are a cyclic permutation of $\langle 1, 2, 3\rangle$ and the second case occurs when the indices are a cyclic permutation of $\langle 3,2,1\rangle$, and the empty case occurs every other time.
Hence $$A \supseteq A_{1,2,3} \cup A_{3,2,1} = A_+ \cup A_- = D$$.

This argument straightforwardly generalizes to $n>3$: by the transitivity and complentarity properties, we must have that there is a set $A$ such that
$$S_{i,j} = \begin{cases}A &\text{if }i < j\\ A^C & \text{if }j<i\end{cases}$$
Consequently, $S_{1,2,3,\ldots,n} = A$ and $S_{n,n-1,\ldots,1} = A^C$, so their union is $D$— the entire space.


TITLE: Proof about L(U,V). Is this reasoning correct?
QUESTION [1 upvotes]: If $U\cong U'$ and $V\cong V'$ then $L(U,V)\cong L(U',V')$
Proof:
Since $U\cong U'$ and $V\cong V'$ then $$dim_{\mathbb{K}}U=dim_{\mathbb{K}}U'=m$$ and $$dim_{\mathbb{K}}V=dim_{\mathbb{K}}V'=n.$$ Due to the above, it is necessary $$dim_{\mathbb{K}}L(U,V)=mn=dim_{\mathbb{K}}L(U',V')$$ then $$L(U,V)\cong L(U',V')$$
Is this reasoning correct? If not, any suggestions?

REPLY [2 votes]: I assume $\mathbb{K}$ is a field and $U,U',V,V'$ are $\mathbb{K}$-vector spaces. In this case, your reasoning is exactly right, as dimension clasasifies finite-dimensional vector spaces up to ismorphism. Moreover, if you have explicit isomorphisms $\varphi \colon U \to U'$ and $\psi \colon V \to V'$, you can build an explicit isomorphism $\Theta \colon L(U,V) \to L(U',V')$ by $\Theta(f) = \psi \circ f \circ \varphi^{-1}$, for $f \in L(U,V)$.


TITLE: Proving that each compact operator is bounded
QUESTION [0 upvotes]: I'm trying to prove that each compact operator is bounded, from the definition:

On the internet I find solutions for this problem, but they always start from a different definition. I would be glad if someone could help me, in finding a proof for this property from this specific definition. Any hints are welcome!

REPLY [5 votes]: Hint: If operator $A$ is not bounded, there is a bounded sequence $u_n$ such that
$\|A u_n\| \to \infty$.  How can this contain a convergent subsequence?


TITLE: $a_n+a_{n+1} \to \alpha$ and $a_n+a_{n+2} \to \beta$ then $\alpha=\beta$ and $a_n \to \alpha/2$
QUESTION [0 upvotes]: Show that if $a_n+a_{n+1} \to \alpha$ and $a_n+a_{n+2} \to \beta$ then
$\alpha=\beta$ and $a_n \to \alpha/2$.

My textbook denotes $\alpha_n=a_n+a_{n+1}$ and $\beta_n=a_n+a_{n+2}$, notices that $a_n=\frac{1}{2}(\alpha_n+\beta_n-\alpha_{n+1})$ and concludes the proof.
However, I did not see that and I've done something longer using the definition of limit. Can someone check if my work is correct too, please?
My work: let $\epsilon>0$. From the hypotheses on the limits, there exist $N_1,N_2 \in \mathbb{N}$ such that $n \ge N_1$ implies $-\epsilon/2<a_n+a_{n+1}-\alpha<\epsilon/2$ and $n \ge N_2$ implies $-\epsilon/2<a_n+a_{n+2}-\beta<\epsilon/2 \iff -\epsilon/2<-a_n-a_{n+2}+\beta<\epsilon/2$. So, if $n\ge \max\{N_1,N_2\}$, adding the inequalities it is $|a_{n+1}-a_{n+2}-(\alpha-\beta)|<\epsilon$; since this holds for any $\epsilon>0$, it is $|a_{n+1}-a_{n+2}-(\alpha-\beta)|<\epsilon$ and so $a_{n+1}-a_{n+2}\to \alpha-\beta$.
So, using all the three limits definition with $\epsilon/3$, if $n$ is greater than the maximum among the three indexes of these limits hypotheses it is
$$|\alpha-\beta|=|a_n-a_n+a_{n+1}-a_{n+1}+a_{n+2}-a_{n+2}+\alpha-\beta|$$
$$\le|a_n+a_{n+1}-\alpha|+|a_n+a_{n+2}-\beta|+|a_{n+1}-a_{n+2}|<\epsilon/3+\epsilon/3+\epsilon/3=\epsilon$$
Hence $\alpha=\beta$ because $\epsilon>0$ is arbitrary.
To show that $a_n \to \alpha/2$, I noticed that since $n+1>n$ the hypothesis $a_n+a_{n+1} \to \alpha$ works with $n+1$ in place of $n$ as well; that is, $a_{n+1}+a_{n+2} \to \alpha$ as well. Hence, using that $\alpha=\beta$, if $n$ is greater than the maximum index among the indexes of the limits hypotheses used with $2\epsilon/3$ it is:
$$|a_n-\alpha/2|=\frac{1}{2}|2a_n-\alpha|=\frac{1}{2}|a_n+a_n+a_{n+1}-a_{n+1}+a_{n+2}-a_{n+2}-\alpha+\beta-\beta|$$
$$\le \frac{1}{2}(|a_n+a_{n+1}-\alpha|+|a_n+a_{n+2}-\beta|+|a_{n+1}+a_{n+2}-\alpha|)$$
$$\le \frac{1}{2}\left(\frac{2}{3}\epsilon+\frac{2}{3}\epsilon+\frac{2}{3}\epsilon\right)=\epsilon$$
That is $a_n \to \alpha/2$ because $\epsilon>0$ is arbitrary.
Is this correct? In particular, I am not sure when I add the inequalities and when I say that $a_{n+1}+a_{n+2} \to \alpha$ as well.

REPLY [1 votes]: Your proof of the second part is correct, that $a_n\to\alpha/2$ given that $\alpha=\beta$. However your proof that $\alpha=\beta$ is suspect - you invoke the inequality: $$|a_{n+1}-a_{n+2}|\lt\varepsilon/3$$But this is simply false a priori (it is in fact true for large $n$, but only once you have already shown $a_n$ is convergent - it is illegal proof to suppose this inequality beforehand). You have $|a_{n+1}-a_{n+2}-(\alpha-\beta)|\lt\varepsilon/3$ for large $n$, but you cannot forget about the $(\alpha-\beta)$ term.
Adding inequalities is ok (if you're careful...) by the triangle inequality, don't worry, and $a_n+a_{n+1}\to\alpha$ is equivalent to $a_{n+1}+a_{n+2}\to\alpha$ since "for all $n\ge N$" also allows "for all $n+1\ge N+1$"...
To show that $\alpha=\beta$ and complete your proof without error, note that $(a_n+a_{n+1})+(a_{n+2}+a_{n+3})\to2\alpha$ but this is the same as $(a_n+a_{n+2})+(a_{n+1}+a_{n+3})\to2\beta$ hence $\alpha=\beta$.


TITLE: Determine the equation of the line the portion of which, intercepted by the axes, is divided by the point $(-5,4)$ in the ratio of $1:2$.
QUESTION [0 upvotes]: Determine the equation of the line the portion of which, intercepted by the axes, is divided by the point $(-5,4)$ in the ratio of $1:2$.
My Attempt:
Let the equation of straight line be
$$ax+by+c=0$$
It passes through the point $(-5,4)$.
$$-5a+4b+c=0$$

REPLY [0 votes]: HINT: make the Ansatz $$y=mx+n$$  since $P(-5,4)$ is situated on the line we have
$$y=m(x+5)+4$$ and the intersection Point withe the $x$ axes is $$P_x(-5-\frac{4}{m};0)$$ and the y-axes  $$P_y(0;5m+4)$$
Now must $$\frac{P_xP}{PP_y}=\frac{1}{2}$$ can you finish?


text:
\section{Algorithmic modifications}\label{app:algmod}

In this appendix we study modifications of GDN and CN, including adding momentum, using total gradients, and generalization to general sum games. We perform asymptotic analysis \citep{polyak87book} for simplicity but general non-asymptotic analysis is also possible if we perform similar proofs as in Theorem \ref{thm:GDN_app}.

\subsection{GDN with momentum}

Notice that in GDN \eqref{eq:gdn}, the minimizer still takes a gradient descent step. Therefore, we can accelerate it using Polyak's momentum \citep{Polyak64}.

Our Theorem~\ref{thm:gdnm} shows that after adding momentum, one can accelerate the convergence rate of GDN in Theorem~\ref{thm:GDN} to $1 - 2/(\sqrt{\kappa}+ 1)$.

We call the following algorithm as GD-Newton with (Polyak's) momentum:
\be
&&\xv_{t+1} = \xv_t - \a \n_\xv f(\xv_t, \yv_t) + \b (\xv_t - \xv_{t-1}),\\
&&\yv_{t+1} = \yv_t - (\yyv^{-1} \cdot \n_\yv) f(\tilde{\xv}_{t + 1}, \yv_t),
\en
where $\tilde{\xv}_{t + 1} = \xv_t$ if it is simultaneous update and $\tilde{\xv}_{t + 1} = \xv_{t+1}$ if it is alternating update.

\begin{theoremEnd}[end, restate]{thm}\label{thm:gdnm}
At a {\slmm} $(\xv^*,\yv^*)$, denote $\lambda_1$ and $\lambda_n$ as the largest and the smallest eigenvalues of $\dxxv f(\xv^*,\yv^*)$. Given $\a = 4/(\sqrt{\lambda_1} + \sqrt{\lambda_n})^2$ and $\b = ((\sqrt{\kappa} - 1)/(\sqrt{\kappa} + 1))^2$, alternating GD-Newton with momentum can achieve a local convergence rate $1 - 2/(\sqrt{\kappa} + 1)$, with $\kappa := \lambda_1/\lambda_n$.
\end{theoremEnd}

\begin{proof}
In this proof we use $\xxv f, \xyv f, \yxv f, \yyv f$ to denote second-order derivatives at the local minimax point $(\xv^*, \yv^*)$. For simultaneous GD-Newton with momentum, we use state augmentation $(\xv_t, \yv_t) \to (\xv_t, \yv_t, \xv_{t-1}, \yv_{t-1})$ and compute the corresponding Jacobian as:
\be
\begin{bmatrix}
(\beta + 1)\Iv - \alpha \xxv f & -\alpha \xyv f & -\beta\Iv & \zero \\
-(\yyv^{-1}\cdot\yxv) f & \zero & \zero & \zero \\
\Iv & \zero & \zero & \zero \\
\zero & \Iv & \zero & \zero
\end{bmatrix}.
\en
With \citet[Theorem 2.3]{zhang2019convergence} we have that for alternating GDN with momentum, the characteristic polynomial of the Jacobian is:
\be
\mu^2 - (\b + 1) \mu + \a \mu \lambda_i + \b = 0,
\en
with $\lambda_i \in \Sp(\dxxv f(\xv^*,\yv^*))$. This is equivalent to the characteristic polynomial of the process ($\wv_t \in \R^n$):
\be
\wv_{t+1} = \wv_t - \alpha \dxxv f(\xv^*, \yv^*) \cdot \wv_t + \beta (\wv_t - \wv_{t-1}).
\en
From \citet[Theorem 1, p.~65]{polyak87book} we can obtain the fastest convergence rate among all choices of $\alpha, \beta$.
\end{proof}
\subsection{The effect of total derivative}\label{app:tgd}
In this subsection we discuss the effect of using total derivatives instead of partial derivatives in the update of $\xv$, in Newton-type methods. The effect of using total derivatives is to keep the same convergence rate while we can replace the alternating updates with simultaneous ones. Also, for general sum games it is necessary to use the total derivative in the update of $\xv$ (\Cref{app:gen_sum}).

\subsubsection{TGD-Newton}\label{app:tgdn}

It is possible to combine TGD with Newton, the continuous version of such method has appeared in \cite{evtushenko1974iterative}.
\be\label{eq:tgdn}
\xv_{t+1} = \xv_t -\a  \TD_\xv f(\xv_t, \yv_t), \, \yv_{t+1} = \yv_t -  [(\yyv^{-1} \cdot \n_\yv) f](\xv_{t}, \yv_t). \en
The Jacobian of TGD-Newton at a \slmm is:
\be\label{eq:jnewton_tgd}
\Jv_{\rm Newton} = \begin{bmatrix}
\Iv - \a \TD_{\xv\xv} f & \zero \\
-(\yyv^{-1}\cdot\yxv) f & \zero
\end{bmatrix}.
\en
The convergence rate is the same as GD-Newton, with simultaneous or alternating updates.

\subsubsection{Complete Newton}\label{app:tgd_cn}

If we replace the partial derivative with total derivative in \eqref{eq:newton}, we obtain:
\be
\label{eq:newton_tdg}
\xv_{t+1} = \xv_t - [(\TD_{\xv\xv}^{-1} \cdot\TD_\xv) f](\xv_t, \yv_t), \,
\yv_{t+1} = \yv_t - [(\yyv^{-1} \cdot \n_\yv) f](\xv_{t}, \yv_t).
\en
The Jacobian can be evaluated as:
\be
\begin{bmatrix}
\zero & \zero \\
-(\yyv^{-1} \cdot\yxv) f & \zero
\end{bmatrix},
\en
which implies super-linear convergence. Combining with \Cref{app:tgdn} we can see that if the update of $\yv$ is Newton, the usage of the total derivative with simultaneous updates is equivalent to using the partial derivative with alternating updates.

\subsection{Alternating vs. simultaneous GDN}\label{app:alt_vs_simul}

In this subsection, we compare simultaneous GDN with alternating GDN in cases where $\a$ is small, as often required in experiments due to stochastic noise. In fact, simultaneous GD-Newton can converge even faster than alternating GD-Newton. Let us make clear of the definitions first. In fact, the algorithm we proposed in \eqref{eq:gdn} is using alternating update, whereas its simultaneous version is:
\be
\label{eq:gdn_s}
\xv_{t+1} = \xv_t - \a \n_\xv f(\xv_t, \yv_t), \, \yv_{t+1} = \yv_t - (\n_{\yv\yv}^{-1} \cdot \n_\yv) f(\xv_{t}, \yv_t).
\en

More detailed discussion can be found in \citet{zhang2019convergence}.

\begin{theoremEnd}[end, restate]{thm}
Suppose at a strict local minimax point $(\xv^*, \yv^*)$, $[\xxv f, (\xyv \cdot \yyv^{-1} \cdot \yxv) f]=\zero$.\footnote{The commutator of two matrices $A, B$ is defined such that $[A, B] := AB - BA$.} Then there exist an orthogonal matrix $\Qv$ s.t.~$\xxv = \Qv \diag\{u_1, \dots, u_n\} \Qv^\top$ and $-(\xyv \cdot\yyv^{-1} \cdot\yxv) f= \Qv \diag\{v_1, \dots, v_n\} \Qv^\top$. If for any $i$, $0 < \a v_i < 1$ and $ \a u_i < 1 - \a v_i - \sqrt{\a v_i}$, then simultaneous GD-Newton always converges faster than alternating GD-Newton near the local minimax point $(\xv^*, \yv^*)$.
\end{theoremEnd}

\begin{proof}
The two characteristic polynomials for simultaneous and alternating methods are separately:
\be
\l^2 - (1 - \a u_i) \l + \a v_i = 0, \, \l(\l -1 + \a u_i + \a v_i) = 0, \, \forall \, i.
\en
We require that $\a v_i + \a u_i < 1$ for all $i$. In order for the simultaneous method to converge faster, suffices to have:
\be
\left|\frac{1}{2}(1 -\a u_i \pm \sqrt{(1 - \a u_i)^2 - 4 \a v_i})\right| < 1 - \a u_i - \a v_i,
\en
if $(1 -\a u_i)^2 \geq 4\a v_i$ and
\be
\sqrt{\a v_i} < 1 - \a u_i - \a v_i,
\en
if $(1 -\a u_i)^2 < 4\a v_i$. Solving the two cases above gives
\be
0 < \a v_i < 1, \, \a u_i  < 1 - \a v_i - \sqrt{\a v_i}.
\en
\end{proof}
When $\a$ is small enough, the condition for $\a$ is always satisfied. Specifically, if $\xxv = \zero$, $u_i = 0$ for all $i$, and we have:
\begin{cor}
Suppose at a strict local minimax point  $(\xv^*, \yv^*)$, $\xxv f = \zero$, $\yyv f \cl \zero$ and $0 < \a v_{1} < (3-\sqrt{5})/2$ for $v_{\max} = \l_{1}(-(\xyv \cdot\yyv^{-1}\cdot\yxv) f)$, then simultaneous GD-Newton always converges faster than alternating GD-Newton near $(\xv^*, \yv^*)$.
\end{cor}

\begin{proof}
Solving $1 - \a v_i - \sqrt{\a v_i} > 0$ and $0 < \a v_i < 1$ gives $0 < \a v_i < (3 - \sqrt{5})/{2}$.
\end{proof}

The condition $\xxv f = \zero$, $\yyv f \cl \zero$ is often satisfied in GANs, see Example~\ref{eg:gan}.

\subsection{General sum games}\label{app:gen_sum}

GD-Newton could naturally be generalized to two-player general sum games \citep{fiez2019convergence}, by which we mean to minimize:
\be
\of(\xv) = \max_{\yv \in \Y^*(\xv)} f(\xv, \yv), \, \mbox{ where }\Y^*(\xv) = \argmin_{\yv\in \Y} g(\xv, \yv).
\en
We use $\n_\yv g(\xv, \yv) = \zero$ as an implicit function that determines the best response $r(\xv)$. It is unique when $\yyv g(\xv, \yv)\cg \zero$. It leads to the definition of a strict local Stackelberg equilibrium $(\xv, \yv) := (\xv, r(\xv))$ (\cite{fiez2019convergence}):
\be
&&\n_\yv g(\xv, \yv) = \zero, \, \TD_\xv f(\xv, r(\xv)) = \zero, \\
&& \yyv g(\xv, \yv)\cg \zero, \, \TD_{\xv\xv} f(\xv, r(\xv)) \cg \zero.
\en
Using implicit function theorem we obtain that:
\be\label{eq:gen_td1}
\TD_\xv f := \n_\xv f - (\xyv \cdot \yyv^{-1})g\cdot \n_\yv f,
\en
and (see also \citet{wang2019solving}),
\be\label{eq:gen_td2}
\TD_{\xv\xv} f &:=& \xxv f -\xyv f \cdot (\xyv \cdot \yyv^{-1})g - \n_\xv [(\xyv \cdot\yyv^{-1})g\cdot \n_\yv f] + \tr &+& \n_\yv [(\xyv \cdot\yyv^{-1})g\cdot \n_\yv f] (\yyv^{-1}\cdot\yxv) g,
\en
where both sides in \eqref{eq:gen_td1} and \eqref{eq:gen_td2} are applied on $(\xv, r(\xv))$. In the zero-sum case, $g= -f$. Hence \eqref{eq:gen_td1} and \eqref{eq:gen_td2} reduce to \eqref{eq:TD1} and \eqref{eq:TD2} respectively. These functions induce GD-Newton for general sum games naturally:
\be
&& \xv_{t+1} = \xv_t - \a_\La \TD_\xv f(\xv_t, \yv_t), \, \yv_{t+1} = \yv_t - [(\yyv^{-1}\cdot\n_\yv)g](\xv_{t+1}, \yv_t).
\en
Let us first compute the Jacobian of the simultaneous version of GDN near a strict local Stackelberg equilibrium, where $\yv_{t+1} = \yv_t - [(\yyv^{-1}\cdot\n_\yv)g](\xv_{t}, \yv_t)$:
\be\label{eq:jnewton}
\Jv_{\rm GDN} = \begin{bmatrix}
\Iv - \a_\La (\xxv f - \n_\xv [(\xyv\cdot \yyv^{-1})g\cdot \n_\yv f] ) & -\a_\La\xyv f +  \a_\La \n_\yv [(\xyv\cdot \yyv^{-1})g\cdot \n_\yv f] \\
-(\yyv^{-1}\cdot\yxv)g  & \zero
\end{bmatrix}.
\en
Computing the spectrum and using \citet[Theorem 2.3]{zhang2019convergence} we have:
\begin{theoremEnd}[end, restate]{thm}\label{thm:gdn_2}
Near a \slmm, GDN can achieve linear convergence $\max_i |1 - \a_\La \l_i|$ with $\l_i \in \Sp(\TD_{\xv\xv}f)$. With $\a_\La = 2/(\l_1 + \l_n)$, GDN can achieve a local convergence rate $1 - 2/(\kappa + 1)$, with $\kappa := \l_1/\l_n$, and $\l_1$ ($\l_n$) the largest (smallest) eigenvalue of $\TD_{\xv\xv}f$.
\end{theoremEnd}

\begin{proof}

The characteristic equation for simultaneous GDN is:
\be
\det\left(\l ((\l - 1)\Iv \!+\! \a_\La  (\xxv f - \n_\xv [(\xyv\cdot \yyv^{-1})g\cdot \n_\yv f] )) \!-\!  \a_\La (\xyv f \!-\! \n_\yv [(\xyv\cdot \yyv^{-1})g\cdot \n_\yv f]) \cdot ( \yyv^{-1}\cdot\yxv )g \right) = 0.
\en
For alternating updates, using \citet[Theorem 2.3]{zhang2019convergence}, we take $ (\yyv^{-1} \cdot \yxv) g\to \l (\yyv^{-1}\cdot \yxv) g$ in \eqref{eq:jnewton}, and the characteristic equation becomes:
\be
\det(\l ((\l - 1)\Iv + \a_\La \dxxv f)) = 0,
\en
where $\dxxv f$ is defined in \eqref{eq:gen_td2}. which reduces to $\l = 0$ or
\be
\det((\l - 1)\Iv + \a_\La \dxxv f) = 0.
\en

So, for any strict local minimax point, alternating GD-Newton converges for small enough $\a_\La$, and the convergence rate of $\|\zv_t - \zv^*\|$ is:
\be\label{eq:sp_ra_gdn}
\rho(\Jv_{\rm GDN}) = \max_i |1 - \a_\La \l_i|,
\en

From \eqref{eq:sp_ra_gdn} it suffices to solve the following minimization problem:
\be
\min_{\a_\La > 0} \max_i |1 - \a_\La \l_i|.
\en
$\max_i |1 - \a_\La \l_i|$ is a piece-wise linear function and it is minimized at the point where $\a_\La \l_1 - 1 = 1 - \a_\La \l_n$. Solving it gives $\a_\La = 2/(\l_1 + \l_n)$ and the local convergence rate $1 - 2/(\kappa_{\La} + 1)$, with $\kappa_{\La} := \l_1/\l_n$.
\end{proof}

config: arxiv