\begin{IEEEproof}
For ease of notation, let $\lambda_X^{(k)}=\frac{\bar{\lambda}_X^{(k)}}{f}$ and $\lambda_Y^{(k)}=\frac{\bar{\lambda}_Y^{(k)}}{p}$ for all $k \geq 1$. First, we show that the first iteration of the KGL algorithm yields a fast statistical convergence rate of $O_P\left( \sqrt{\frac{(p+f)\log M}{n}} \right)$ by appropriately adjusting the regularization parameters. Second, we show that the second iteration maintains the same convergence rate as the first. Finally, we consider the second iteration as the base case and fix the regularization parameters to $\lambda_X \asymp \lambda_Y  \asymp \left( \frac{1}{\sqrt{p}} + \frac{1}{\sqrt{f}} \right) \sqrt{\frac{\log M}{n}}$ and use induction to show that the same fast rate holds for all subsequent iterations.

%Let us first establish some asymptotic notation. For random matrices $\bX_1$ and $\bX_2$ of same order:
%\begin{equation*}
%	\bX_1 \cong \bX_2 \Longrightarrow \nn\bX_1-\bX_2\nn_F = o_p\left( \sqrt{\frac{M_{p,f}^2 \log(M_{p,f})}{n}} \right)
%\end{equation*}
%as $p,f,n\to\infty$.


By Assumption 2, Lemma \ref{lemma: large_dev_optimal} yields
\begin{equation} \label{tilde_B_0_rate}
	|\tilde{\bB}^0|_\infty = O_P\left( \sqrt{\frac{\log M}{np}} \right)
\end{equation}
where $\tilde{\bB}^0=\hat{\bB}(\bA_{init})-\bB_*$.

From Proposition \ref{prop: Glasso_optimal_rate}, we obtain optimal Frobenius rate norms using (\ref{tilde_B_0_rate}):
\begin{equation} \label{Y_Frob_error}
	\nn \bY_1-\bY_* \nn_F = O_P\left( \sqrt{\frac{f\log M}{np}} \right)
\end{equation}
where we also used $s_{Y_0}=O(f)$ and $\bY_1:=\bB_1^{-1}$.

Let $\check{\bB}^0:=\bB_1 - \bB_*$. % this is the double tilde notation in the notes
Then, from the dual program (\ref{dualY}) and the triangle inequality, we have
\begin{align}
	|\check{\bB}^0|_\infty &\leq |\bB_1-\hat{\bB}(\bA_{init})|_\infty + |\tilde{\bB}^0|_\infty \nonumber \\
		&\leq \lambda_Y^{(1)} + |\tilde{\bB}^0|_\infty = O_P\left( \sqrt{\frac{\log M}{np}} \right) \label{check_B_0_rate}
\end{align}

Let $\grave{\bA}^1:=\hat{\bA}(\bB_1) - \bA_*$. Then, after some algebra,
\begin{align}
	\vec(\grave{\bA}^1) %&= \frac{1}{f} \hat{\bR}_A \vec((\bB_*+\check{\bB}^0)^{-1}) - \vec(\bA_*) \nonumber \\
		%&= \frac{1}{f} \hat{\bR}_A \vec(\bB_*^{-1} - \bB_*^{-1} \check{\bB}^0 \bB_*^{-1} + \bDelta_B) - \vec(\bA_*) \nonumber \\
		&= \vec(\hat{\bA}(\bB_*)-\bA_*) - \frac{\tr(\bB_*^{-1} \check{\bB}^0)}{f} \vec(\bA_*) \nonumber \\
		&\quad + \vec(\bDelta_B^+) \label{grave_A_1}
\end{align}
where $\bDelta_B = \sum_{k=2}^\infty (-\bB_*^{-1} \check{\bB}^0)^k \bB_*^{-1}$ and 
\begin{equation} \label{bDelta_B_plus}
	\vec(\bDelta_B^+) = \frac{1}{f}\hat{\bR}_A \vec(\bDelta_B) - \frac{1}{f} \tilde{\bR}_A (\bB_*^{-T}\otimes \bB_*^{-1}) \vec(\check{\bB}^0)
\end{equation}
Next, we show $\bDelta_B^+$ is asymptotically negligible. From (\ref{bDelta_B_plus}):
\begin{align}
	&|\bDelta_B^+|_\infty \leq \nn \bDelta_B^+ \nn_F \leq \frac{1}{f} \nn \hat{\bR}_A\nn_2 \nn \bDelta_B\nn_F + \frac{1}{f} \nn \tilde{\bR}_A \nn_2 \nn\bB_*^{-1}\nn_2^2 \nn \check{\bB}^0\nn_F \nonumber \\
		%&\leq O_P\left( \frac{\sqrt{pf}}{f} (\sqrt{f} \frac{f^2\log f}{np}) + \frac{1}{f} (pf \sqrt{\frac{\log(pf)}{n}}) \sqrt{\frac{f^2\log(f)}{np}} \right) \nonumber \\
		&= O_P\left( \frac{(f^2 p^{-1/2}+p^{1/2}f) \log M}{n} \right) \label{bDelta_B_plus_bound_linfty}
\end{align}
From (\ref{grave_A_1}), applying the triangle inequality and using (\ref{check_B_0_rate}), $s_{Y_0}=O(f)$, (\ref{bDelta_B_plus_bound_linfty}), we have:
\begin{align}
	|\grave{\bA}^1|_\infty %&\leq |\hat{\bA}(\bB_*)-\bA_*|_\infty + \frac{|\tr(\bB_*^{-1} \check{\bB}^0)|}{f} |\bA_*|_\infty + |\bDelta_B^+|_\infty \nonumber \\
		&\leq |\hat{\bA}(\bB_*)-\bA_*|_\infty + \frac{|\check{\bB}^0|_\infty |\bB_*^{-1}|_1}{f} |\bA_*|_\infty + |\bDelta_B^+|_\infty \nonumber \\
		%&=O_P \Big( \sqrt{\frac{\log(p)}{nf}} + \sqrt{\frac{\log(f)}{np}} \nonumber \\
		%&\qquad + \frac{(f^2 p^{-1/2}+p^{1/2}f) \log M}{n} \Big) \nonumber \\
		&=O_P\left( \left( \frac{1}{\sqrt{p}} + \frac{1}{\sqrt{f}} \right) \sqrt{\frac{\log M}{n}} \right) \label{grave_A_1_bound}
\end{align}
where we used Assumption 1, Lemma \ref{lemma: large_dev_optimal} and the growth assumption. This type of asymptotic inequality will be abbreviated as $\lesssim$ in the sequel.

From Proposition \ref{prop: Glasso_optimal_rate}, we obtain optimal Frobenius rate using (\ref{grave_A_1_bound}):
\begin{equation} \label{X_Frob_error}
	\nn \bX_1-\bX_* \nn_F = O_P\left( \sqrt{ \frac{p\log M}{nf}} + \sqrt{\frac{\log M}{n}} \right)
\end{equation}
where we used $s_{X_0}=O(p)$ and $\bX_1:=\bG(\hat{\bA}(\bB_1), \lambda_X^{(1)})$, $\bX_*:=\bA_*^{-1}$.

Finally, using (\ref{Y_Frob_error}) and (\ref{X_Frob_error}), we obtain the optimal Frobenius total error:
\begin{align}
	& \nn \bTheta_{KGL}(1)-\bTheta_0 \nn_F \leq \nn \bY_1-\bY_*\nn_F \sqrt{p} \nn \bX_*\nn_2  \nonumber \\
		&\quad + \nn \bX_1-\bX_*\nn_F \sqrt{f} \nn \bY_*\nn_2 + \nn \bY_1-\bY_*\nn_F \nn \bX_1-\bX_*\nn_F \label{total_error} \\
		&=O_P\left( \sqrt{\frac{p\log M}{n}} + \sqrt{\frac{f\log M}{n}} \right) \nonumber
\end{align}
where we used the fact that $p \log M=o(n)$ and $f\log M=o(n)$ in the last step. Note that $\nn \bTheta_{KGL}(1)-\bTheta_0 \nn_F^2 = O_P\left( \frac{p\log M}{n} + \frac{f\log M}{n} + \sqrt{\frac{p\log M}{n}} \sqrt{\frac{f\log M}{n}} \right)$. As $p,f,n\to\infty$, the last term becomes negligible. This concludes the first part of the proof.

Next, define the error quantities:
\begin{align*}
	\check{\bA}^1 &= \bA_1 - \bA_* \\
	\grave{\bB}^2 &= \hat{\bB}(\bA_1) - \bB_* \\
	\check{\bB}^1 &= \bB_2 - \bB_* \\
	\grave{\bA}^2 &= \hat{\bA}(\bB_2) - \bA_*
\end{align*}
where $\bA_1 := \bX_1^{-1}$.

Continuing to propagate the statistics into the second KGL iteration, we obtain the base case:
\begin{align}
	|\check{\bA}^1|_\infty &= O_P\left( \left( \frac{1}{\sqrt{p}} + \frac{1}{\sqrt{f}} \right) \sqrt{\frac{\log M}{n}} \right) \label{eq_base_case_1} \\
	|\grave{\bB}^2|_\infty &= O_P\left( \left( \frac{1}{\sqrt{p}} + \frac{1}{\sqrt{f}} \right) \sqrt{\frac{\log M}{n}} \right) \label{eq_base_case_2} \\
	|\check{\bB}^1|_\infty &= O_P\left( \left( \frac{1}{\sqrt{p}} + \frac{1}{\sqrt{f}} \right) \sqrt{\frac{\log M}{n}} \right) \label{eq_base_case_3} \\
	|\grave{\bA}^2|_\infty &= O_P\left( \left( \frac{1}{\sqrt{p}} + \frac{1}{\sqrt{f}} \right) \sqrt{\frac{\log M}{n}} \right) \label{eq_base_case_4}
\end{align}
Eq. (\ref{eq_base_case_1}) follows from $\lambda_X^{(1)}\asymp \left( \frac{1}{\sqrt{p}} + \frac{1}{\sqrt{f}} \right) \sqrt{\frac{\log M}{n}}$ and using (\ref{grave_A_1_bound}) in:
\begin{align*}
	|\check{\bA}^1|_\infty &\leq |\bA_1 - \hat{\bA}(\bB_1)|_\infty + |\hat{\bA}(\bB_1)-\bA_*|_\infty \\
		&\leq \lambda_X^{(1)} + |\grave{\bA}^1|_\infty
\end{align*}

Using similar techniques as before, we can write:
\begin{equation}
	\vec(\grave{\bB}^2) = \vec(\hat{\bB}(\bA_*)-\bB_*) - \frac{\tr(\bA_*^{-1} \check{\bA}^1)}{p} + \vec(\bDelta_A^+) \label{grave_B_2}
\end{equation}
where $\bDelta_A = \sum_{k=2}^\infty (-\bA_*^{-1}\check{\bA}^1)^k \bA_*^{-1}$ and
\begin{equation*}
	\vec(\bDelta_A^+) = \frac{1}{p}\hat{\bR}_B \vec(\bDelta_A) - \frac{1}{p}\tilde{\bR}_B(\bA_*^{-T}\otimes \bA_*^{-1}) \vec(\check{\bA}^1)
\end{equation*}
Using (\ref{eq_base_case_1}) and $\nn \check{\bA}^1 \nn_F^2 \leq p^2 |\check{\bA}^1|_\infty^2$, it follows that
\begin{equation} \label{bound_Delta_A_Frob}
	\nn \bDelta_A \nn_F = O_P\left(\sqrt{p} \left\{ \frac{(p^2 f^{-1}+p) \log M}{n} \right\} \right)
\end{equation}
where we used $\nn \bDelta_A \nn_F \leq \sqrt{p} \nn\bDelta_A \nn_2$.

Using (\ref{grave_B_2}) and (\ref{bound_Delta_A_Frob}), we obtain:
\begin{align}
	& |\bDelta_A^+|_\infty\leq  \nn \bDelta_A^+ \nn_F \leq \frac{1}{p} \nn \hat{\bR}_B \nn_2 \nn \bDelta_A \nn_F + \frac{1}{p} \nn \tilde{\bR}_B\nn_2 \nn \bA_*^{-1}\nn_2^2 \nn \check{\bA}^1 \nn_F \nonumber \\
	 %&\leq O_P\Big( \frac{\sqrt{pf}}{p} \left(\sqrt{p} \frac{p^2f^{-1} \log(p)+p\log(f)}{n} \right)  \\
	 %&\quad + \frac{1}{p} \left(pf \sqrt{\frac{\log(pf)}{n}}\right) (\sqrt{\frac{p^2\log(p)}{nf}}+\sqrt{\frac{p\log(f)}{n}}) \Big) \\
	 &\leq O_P\left( \frac{(p^2 f^{-1/2}+p\sqrt{f}+\sqrt{p}f) \log M}{n} \right) \label{weaker_sufficient_condition}
\end{align}
As a result, $\bDelta_A^+$ is asymptotically negligible as $p,f,n\to\infty$ and:
\begin{align}
	|\grave{\bB}^2|_\infty %&\leq |\hat{\bB}(\bA_*)-\bB_*|_\infty + \frac{|\tr(\bA_*^{-1} \check{\bA}^1)|}{p} |\bB_*|_\infty + |\bDelta_A^+|_\infty \nonumber \\
		&\leq |\hat{\bB}(\bA_*)-\bB_*|_\infty + |\check{\bA}^1|_\infty \frac{|\bA_*^{-1}|_1}{p} |\bB_*|_\infty + |\bDelta_A^+|_\infty \nonumber \\
		%&= O_P \Big( \sqrt{\frac{\log(f)}{np}} + \sqrt{\frac{\log(p)}{nf}} \nonumber \\
		%&\qquad + \frac{(p^2 f^{-1/2}+p\sqrt{f}+\sqrt{f}p+\sqrt{p}f)\log M }{n} \Big) \nonumber \\
		&= O_P\left( \left( \frac{1}{\sqrt{p}} + \frac{1}{\sqrt{f}} \right) \sqrt{\frac{\log M}{n}} \right) \label{grave_B_2_bound_linfty}
\end{align}
where we used Lemma \ref{lemma: large_dev_optimal}, (\ref{eq_base_case_1}), Assumption 1, and the bounded growth assumption. Thus, Eq. (\ref{eq_base_case_2}) follows.

Eq. (\ref{eq_base_case_3}) similarly follows from using $\lambda_Y^{(2)}\asymp (\frac{1}{\sqrt{p}}+\frac{1}{\sqrt{f}}) \sqrt{\frac{\log M}{n}} $ and (\ref{eq_base_case_2}) in:
\begin{align*}
	|\check{\bB}^1|_\infty &\leq |\bB_2 - \hat{\bB}(\bA_1)|_\infty + |\hat{\bB}(\bA_1)-\bB_*|_\infty \\
		&\leq \lambda_Y^{(2)} + |\grave{\bB}^2|_\infty
\end{align*}
Eq. (\ref{eq_base_case_4}) follows from using Lemma \ref{lemma: large_dev_optimal}, (\ref{eq_base_case_3}), Assumption 1 and the bounded growth assumption in:
\begin{align*}
	|\grave{\bA}^2|_\infty &\lesssim |\hat{\bA}(\bB_*)-\bA_*|_\infty + |\check{\bB}^1|_\infty \frac{|\bB_*^{-1}|_1}{f} |\bA_*|_\infty
\end{align*}

From (\ref{eq_base_case_2}), $s_{Y_0}=O(f)$, $\bY_2 = \bG(\hat{\bB}(\bA_1),\lambda_Y^{(2)})$, we have:
\begin{equation*}
	\nn \bY_2 - \bY_* \nn_F = O_P\left( \sqrt{\frac{f\log M}{np}} + \sqrt{\frac{\log M}{n}} \right)
\end{equation*}
Similarly, from (\ref{eq_base_case_4}), $s_{X_0}=O(p)$, $\bX_2 = \bG(\hat{\bA}(\bB_2),\lambda_X^{(2)})$, we have:
\begin{equation*}
	\nn \bX_2 - \bX_* \nn_F = O_P\left( \sqrt{\frac{p\log M}{nf}} + \sqrt{\frac{\log M}{n}} \right)
\end{equation*}

Finally, we consider Eq. (\ref{eq_base_case_1})-(\ref{eq_base_case_4}) as the base case and a simple induction finishes the proof (see \cite{TsiligkaridisTSP} for more details).

%Define the intermediate error quantities for $k\geq 2$:
%\begin{align*}
%	\check{\bA}^{k-1} &= \bA_{k-1} - \bA_* \\
%	\grave{\bB}^k &= \hat{\bB}(\bA_{k-1}) - \bB_* \\
%	\check{\bB}^{k-1} &= \bB_k - \bB_* \\
%	\grave{\bA}^k &= \hat{\bA}(\bB_k) - \bA_* 
%\end{align*}
%According to the above arguments, $|\check{\bA}^{k-1}|_\infty=O_P(\sqrt{\frac{\log(f)}{np}} + \sqrt{\frac{\log(p)}{nf}})$ implies $|\grave{\bA}^k|_\infty =O_P(\sqrt{\frac{\log(f)}{np}} + \sqrt{\frac{\log(p)}{nf}})$. Assume $|\grave{\bA}^k|_\infty = O_P(\sqrt{\frac{\log(f)}{np}} + \sqrt{\frac{\log(p)}{nf}})$ for some $k\geq 2$. To finish the proof, it suffices to show this implies $|\grave{\bA}^{k+1}|_\infty = O_P(\sqrt{\frac{\log(f)}{np}} + \sqrt{\frac{\log(p)}{nf}})$.
%
%Then, continuing as before, we have:
%\begin{align}
%	|\check{\bA}^k|_\infty &\leq |\bA_* - \hat{\bA}(\bB_k)|_\infty + |\hat{\bA}(\bB_k) - \bA_*|_\infty \nonumber \\
%		&\leq \lambda_X^{(k)} + |\grave{\bA}^k|_\infty \nonumber \\
%		&=O_P\left( \sqrt{\frac{\log(f)}{np}} + \sqrt{\frac{\log(p)}{nf}} \right) \label{check_A_k}
%\end{align}
%Using (\ref{check_A_k}), we obtain:
%\begin{align}
%	|\grave{\bB}^{k+1}|_\infty &\lesssim |\hat{\bB}(\bA_*)-\bB_*|_\infty + |\check{\bA}^k|_\infty \frac{|\bA_*^{-1}|_1}{p} |\bB_*|_\infty \nonumber \\
%		&=O_P\left( \sqrt{\frac{\log(f)}{np}} + \sqrt{\frac{\log(p)}{nf}} \right) \label{grave_B_kplus1}
%\end{align}
%Repeating this argument, we have:
%\begin{align}
%	|\check{\bB}^k|_\infty &\leq |\bB_{k+1} - \hat{\bB}(\bA_k)|_\infty + |\hat{\bB}(\bA_k)-\bB_*|_\infty \nonumber \\
%		&\leq \lambda_Y^{(k+1)} + |\grave{\bB}^{k+1}|_\infty \nonumber \\
%		&=O_P\left( \sqrt{\frac{\log(f)}{np}} + \sqrt{\frac{\log(p)}{nf}} \right) \label{check_B_k}
%\end{align}
%Using (\ref{check_B_k}), we obtain:
%\begin{align}
%	|\grave{\bA}^{k+1}|_\infty &\lesssim |\hat{\bA}(\bB_*)-\bA_*|_\infty + |\check{\bB}^k|_\infty \frac{|\bB_*^{-1}|_1}{f} |\bA_*|_\infty \\
%		&=O_P\left( \sqrt{\frac{\log(f)}{np}} + \sqrt{\frac{\log(p)}{nf}} \right)
%\end{align}
%
%We thus conclude that $|\check{\bA}^{k-1}|_\infty, |\grave{\bB}^k|_\infty, |\check{\bB}^{k-1}|_\infty, |\grave{\bA}^k|_\infty$ all have the same rate $O_P\left( \sqrt{\frac{\log(f)}{np}} + \sqrt{\frac{\log(p)}{nf}} \right)$ for $k\geq 2$. This implies that for $k\geq 2$, since $s_{Y_0}=O(f)$, $\bY_k = \bG(\hat{\bB}(\bA_{k-1}),\lambda_Y^{(k)})$, we have:
%\begin{equation*}
%	\nn \bY_k - \bY_* \nn_F = O_P\left( \sqrt{\frac{f\log(f)}{np}} + \sqrt{\frac{\log(p)}{n}} \right)
%\end{equation*}
%and since $s_{X_0}=O(p)$, $\bX_k = \bG(\hat{\bA}(\bB_k),\lambda_X^{(k)})$, we have:
%\begin{equation*}
%	\nn \bX_k - \bX_* \nn_F = O_P\left( \sqrt{\frac{p\log(p)}{nf}} + \sqrt{\frac{\log(f)}{n}} \right)
%\end{equation*}
%The triangle inequality concludes the proof (see (\ref{total_error})).


\end{IEEEproof}
