$\displaystyle:=\sum_{i=1}^{n}\eta_{i}^{3}\exp\left(-2\sum_{j=i+1}^{n}\eta_{j}\left(\lambda_{1}-\lambda_{2}\right)\right)$
$\displaystyle=\left(\frac{\alpha}{\lambda_{1}-\lambda_{2}}\right)^{3}\sum_{i=1}^{n}\frac{1}{\left(\beta+i\right)^{3}}\left(\frac{i+\beta+1}{n+\beta+1}\right)^{2\alpha}$
$\displaystyle\leq\left(\frac{\alpha}{\lambda_{1}-\lambda_{2}}\right)^{3}\left(\frac{\beta+1}{\beta}\right)^{3}\sum_{i=1}^{n}\frac{1}{\left(\beta+i+1\right)^{3}}\left(\frac{i+\beta+1}{n+\beta+1}\right)^{2\alpha}$
$\displaystyle=\left(\frac{\alpha}{\lambda_{1}-\lambda_{2}}\right)^{3}\left(\frac{\beta+1}{\beta}\right)^{3}\sum_{i=1}^{n}\frac{1}{\left(\beta+i+1\right)^{2}}\left(\frac{i+\beta+1}{n+\beta+1}\right)^{2\alpha}$
$\displaystyle\leq
2\left(\frac{\alpha}{\lambda_{1}-\lambda_{2}}\right)^{3}\frac{1}{\left(n+\beta+1\right)^{2\alpha}}\sum_{i=1}^{n}\left(i+\beta+1\right)^{2\alpha-3}$
$\displaystyle\leq\frac{1}{\alpha-1}\left(\frac{\alpha}{\lambda_{1}-\lambda_{2}}\right)^{3}\frac{1}{\left(n+\beta+2\right)^{2}}\left(\frac{n+\beta+2}{n+\beta+1}\right)^{2\alpha}\text{
using }\ref{ineq:sum_exponentials_upper_bound}$
$\displaystyle=\frac{1}{\alpha-1}\left(\frac{\alpha}{\lambda_{1}-\lambda_{2}}\right)^{3}\frac{1}{\left(n+\beta+2\right)^{2}}\left(1+\frac{1}{n+\beta+1}\right)^{2\alpha}$
(53)

Using 45, we have

$\displaystyle\frac{\alpha}{n+\beta+1}=\eta_{n}\left(\lambda_{1}-\lambda_{2}\right)\leq\eta_{n}\lambda_{1}\leq\eta_{n}k_{n}\lambda_{1}\leq\epsilon\leq
0.1$ (54)

Therefore, using [17]

$\displaystyle\left(1+\frac{1}{n+\beta+1}\right)^{2\alpha}\stackrel{{\scriptstyle(i)}}{{\leq}}\frac{1}{1-\frac{2\alpha}{n+\beta+1}}\stackrel{{\scriptstyle(ii)}}{{\leq}}1+\frac{4\alpha}{n+\beta+1}\leq
1+4\epsilon$ (55)

where $(i)$ follows since $\frac{2\alpha}{n+\beta+1}<1$ by 54 and $(ii)$
follows since $\frac{1}{1-x}\leq 1+2x\text{ for }x\in[0,\frac{1}{2}]$.

Using 55 with 52, we have

$\displaystyle T_{3}$
$\displaystyle\leq\frac{2}{2\alpha-1}\left(\frac{\alpha}{\lambda_{1}-\lambda_{2}}\right)^{2}\frac{1}{\left(n+\beta+2\right)}\left(1+\frac{4\alpha}{n+\beta+1}\right)$
$\displaystyle\leq\frac{2\left(1+4\epsilon\right)}{2\alpha-1}\left(\frac{\alpha}{\lambda_{1}-\lambda_{2}}\right)^{2}\frac{1}{\left(n+\beta+2\right)}$
(56)

Using 55 with 53, we have

$\displaystyle T_{4}$
$\displaystyle\leq\frac{1+4\epsilon}{\alpha-1}\left(\frac{\alpha}{\lambda_{1}-\lambda_{2}}\right)^{3}\frac{1}{\left(n+\beta+2\right)^{2}}$
(57)

Let

$\displaystyle
C_{1}:=\frac{2\left(1+10\epsilon\right)\alpha^{2}}{2\alpha-1},C_{2}:=\frac{24\left(1+10\epsilon\right)\alpha^{3}}{\left(\alpha-1\right)},$

Putting together 56, 57 in 51 and using the definition of $k_{i}$ in 43 we
have

$\displaystyle\left(1+5\epsilon\right)\mathcal{V}^{\prime}T_{3}$
$\displaystyle\leq\frac{2\left(1+5\epsilon\right)\left(1+4\epsilon\right)}{2\alpha-1}\left(\frac{\alpha}{\lambda_{1}-\lambda_{2}}\right)^{2}\frac{\mathcal{V}^{\prime}}{\left(n+\beta+2\right)}$
$\displaystyle\leq\frac{2\left(1+10\epsilon\right)\alpha^{2}}{2\alpha-1}\frac{\mathcal{V}^{\prime}}{\left(\lambda_{1}-\lambda_{2}\right)^{2}}\frac{1}{n}\text{
since }\epsilon\leq 0.05$

and similarly,

$\displaystyle
24\left(1+5\epsilon\right)\mathcal{M}\left(\mathcal{M}+\lambda_{1}\right)^{2}k_{n}^{2}T_{4}$
$\displaystyle\leq\frac{24\left(1+5\epsilon\right)\left(1+4\epsilon\right)\alpha^{3}}{\alpha-1}\frac{\mathcal{M}\left(\mathcal{M}+\lambda_{1}\right)^{2}}{\left(\lambda_{1}-\lambda_{2}\right)^{3}}\frac{k_{n}^{2}}{n^{2}}$

Therefore from 51, we have

$\displaystyle\sum_{i=1}^{n}\left(\mathcal{V}^{\prime}+\xi_{k,i}\right)\eta_{i-k_{i}}^{2}\exp\left(-\sum_{j=i+1}^{n}2\eta_{j}\left(\lambda_{1}-\lambda_{2}\right)\right)\leq
C_{1}\frac{\mathcal{V}^{\prime}}{\left(\lambda_{1}-\lambda_{2}\right)^{2}}\frac{1}{n}+C_{2}\frac{\mathcal{M}\left(\mathcal{M}+\lambda_{1}\right)^{2}}{\left(\lambda_{1}-\lambda_{2}\right)^{3}}\frac{k_{n}^{2}}{n^{2}}$

Hence proved. ∎

##  Appendix S.4 Proofs : Convergence Analysis of Oja’s Algorithm for
Markovian Data

In this section, we present proofs of Theorems 2, 3, 4 and 5. We state
versions of these theorems that are valid under more general conditions on the
step sizes. Specifically, for the following, we only require a sequence of
non-increasing step-sizes which satisfy, for $\epsilon:=\frac{1}{100},\forall
i\in[n]$ -

  1. 1.

$\eta_{i}k_{i}\left(\mathcal{M}+\lambda_{1}\right)\leq\epsilon$

  2. 2.

$\eta_{i}\leq\eta_{i-k_{i}}\leq\left(1+2\epsilon\right)\eta_{i}\leq 2\eta_{i}$
(slow-decay)

The version of these theorems stated in the manuscript are obtained by
plugging in the step-sizes as
$\eta_{i}:=\frac{\alpha}{\left(\lambda_{1}-\lambda_{2}\right)\left(\beta+i\right)}$
for the values of $\alpha,\beta$ provided in Lemma S.12. Before starting with
the proofs, we define the following scalar variables -

$\displaystyle r$
$\displaystyle:=2\left(1+\epsilon\right)k_{n}\eta_{n}\left(\mathcal{M}+\lambda_{1}\right),\qquad\zeta_{k,t}:=40k_{t+1}\left(\mathcal{M}+\lambda_{1}\right)^{2}$
$\displaystyle\psi_{k,t}$
$\displaystyle:=6\mathcal{M}\left[1+3k_{t+1}^{2}\left(\mathcal{M}+\lambda_{1}\right)^{2}\right],\qquad\xi_{k,t}:=\eta_{t-k_{t}}\psi_{k,t}$
$\displaystyle\mathcal{V}^{\prime}$
$\displaystyle:=\frac{1+\left(3+4\epsilon\right)|\lambda_{2}\left(P\right)|}{1-\left|\lambda_{2}\left(P\right)\right|}\mathcal{V},\
\
\qquad\qquad\overline{\mathcal{V}_{k,t}}:=\mathcal{V}^{\prime}+\lambda_{1}^{2}+\xi_{k,t}$
(58)

######  Theorem 2.

(General Version)

$\displaystyle\mathbb{E}\left[v_{1}^{T}B_{n,1}B_{n,1}^{T}v_{1}\right]\leq\left(1+r\right)^{2}\exp\left(\sum_{t=1}^{n-k_{n}}\left(2\eta_{t}\lambda_{1}+\eta_{t}^{2}\left(\mathcal{V}^{\prime}+\lambda_{1}^{2}+\xi_{k,t}\right)\right)\right)$

where $B_{j,i}$ is defined in 12.

###### Proof.

Define
$\alpha_{n,t}:=\mathbb{E}\left[\operatorname{Tr}\left(v_{1}^{T}B_{n,t}B_{n,t}^{T}v_{1}\right)\right]=\mathbb{E}\left[v_{1}^{T}B_{n,t}B_{n,t}^{T}v_{1}\right],i\leq
t\leq n$. Then, we have

$\displaystyle v_{1}^{T}B_{n,t}B_{n,t}^{T}v_{1}$
$\displaystyle=v_{1}^{T}B_{n,t+1}(I+\eta_{t}\Sigma)^{2}B_{n,t+1}^{T}v_{1}\;+\;2\eta_{t}\underbrace{\left(v_{1}^{T}B_{n,t+1}(I+\eta_{t}\Sigma)(A_{t}-\Sigma)B_{n,t+1}^{T}v_{1}\right)}_{P_{n,t}}$
$\displaystyle+\;\eta_{t}^{2}\underbrace{\left(v_{1}^{T}B_{n,t+1}(A_{t}-\Sigma)^{2}B_{n,t+1}^{T}v_{1}\right)}_{Q_{n,t}}$
(59) $\displaystyle\leq
v_{1}^{T}B_{j,t+1}B_{j,t+1}^{T}v_{1}((1+\eta_{t}\lambda_{1})^{2})+\eta_{t}^{2}Q_{n,t}+2\eta_{t}P_{n,t}$

Using Lemma S.8 with $U=v_{1},G=\left(I+\eta_{t}\Sigma\right),\gamma=1$ and
noting that $\mathbb{E}_{\pi}\left[A_{t}-\Sigma\right]=0$, along with
observing that $\alpha_{n,t+k_{t+1}}\leq\alpha_{n,t+k_{t}}$ from Lemma S.3, we
have

$\displaystyle\left|\mathbb{E}\left[P_{n,t}\right]\right|$
$\displaystyle\leq\eta_{t+1}\left(1+\eta_{t}\lambda_{1}\right)\left(\frac{2\mathcal{V}\left|\lambda_{2}\left(P\right)\right|}{1-\left|\lambda_{2}\left(P\right)\right|}+\eta_{t+1}\mathcal{M}\left(2+16\epsilon+\left(2+\left(1+\epsilon\right)^{2}\right)k_{t+1}^{2}\left(\mathcal{M}+\lambda_{1}\right)^{2}\right)\right)\alpha_{n,t+k_{{t}}}$

We note that $\forall i,\;k_{i}\geq 1$, therefore, using the assumption in
S.4, $1+\eta_{t}\lambda_{1}\leq
1+\eta_{t}k_{t}\left(\mathcal{M}+\lambda_{1}\right)\leq 1+\epsilon$.

Next, using Lemma S.9 with $U=v_{1},G=I,\gamma=1$ and noting that
$\left\|\mathbb{E}_{\pi}\left[\left(A_{t}-\Sigma\right)^{2}\right]\right\|_{2}\leq\mathcal{V}$
along with observing that $\alpha_{n,t+k_{t+1}}\leq\alpha_{n,t+k_{t}}$ using
Lemma S.3, we have

$\displaystyle\left|\mathbb{E}\left[Q_{n,t}\right]\right|$
$\displaystyle\leq\left(\mathcal{V}+\eta_{t+1}\mathcal{M}^{2}\left(2\eta_{t+1}+\left(1+\epsilon\right)\left(2+\epsilon\left(1+\epsilon\right)\right)k_{t+1}\left(\mathcal{M}+\lambda_{1}\right)\right)\right)\alpha_{n,t+k_{{t}}}$
$\displaystyle\leq\left(\mathcal{V}+2\epsilon\eta_{t+1}\mathcal{M}+\eta_{t+1}\mathcal{M}^{2}\left(\left(1+\epsilon\right)\left(2+\epsilon\left(1+\epsilon\right)\right)k_{t+1}\left(\mathcal{M}+\lambda_{1}\right)\right)\right)\alpha_{n,t+k_{{t}}}$

where in the last line, we used
$\eta_{t+1}\mathcal{M}\leq\eta_{t+1}\left(\mathcal{M}+\lambda_{1}\right)\leq\eta_{t+1}k_{t+1}\left(\mathcal{M}+\lambda_{1}\right)\leq\epsilon$.

Then from 59 for $n-k_{t}\geq t\geq 1$,

$\displaystyle\alpha_{n,t}$
$\displaystyle\leq\left(1+\eta_{t}\lambda_{1}\right)^{2}\alpha_{n,t+1}+\left(\frac{1+\left(3+4\epsilon\right)|\lambda_{2}\left(P\right)|}{1-\left|\lambda_{2}\left(P\right)\right|}\right)\mathcal{V}\eta_{t}^{2}\alpha_{n,t+k_{t}}+C_{k,t}\eta_{t}^{3}\alpha_{n,t+k_{t}}$
(60)

where $C_{k,t}$ is defined as

$\displaystyle C_{k,t}$
$\displaystyle:=\mathcal{M}\left[4\left(1+\epsilon\right)\left(1+8\epsilon\right)+2\epsilon+k_{t+1}\left(\mathcal{M}+\lambda_{1}\right)\left(\left(1+\epsilon\right)\left(2+\epsilon\left(1+\epsilon\right)\right)\mathcal{M}+2\left(2+\left(1+\epsilon\right)^{2}\right)k_{t+1}\left(\mathcal{M}+\lambda_{1}\right)\right)\right]$
$\displaystyle\stackrel{{\scriptstyle\left(i\right)}}{{\leq}}\mathcal{M}\left[4\left(1+\epsilon\right)\left(1+8\epsilon\right)+2\epsilon+\left(\left(1+\epsilon\right)\left(2+\epsilon\left(1+\epsilon\right)\right)+2\left(2+\left(1+\epsilon\right)^{2}\right)\right)k_{t+1}^{2}\left(\mathcal{M}+\lambda_{1}\right)^{2}\right]$
$\displaystyle=\mathcal{M}\left[4+38\epsilon+32\epsilon^{2}+\left(6+2\epsilon+\left(1+\epsilon\right)^{2}\left(1+2\epsilon\right)\right)k_{t+1}^{2}\left(\mathcal{M}+\lambda_{1}\right)^{2}\right]$

where in $\left(i\right)$ we used $\mathcal{M}\leq
k_{t+1}\left(\mathcal{M}+\lambda_{1}\right)$.

Then recalling the definition of $\xi_{k,t}$ in S.4, and noting that
$\alpha_{n,t+k_{t}}\leq\alpha_{n,t+1}$ using Lemma S.3 we have from 60,

$\displaystyle\alpha_{n,t}$
$\displaystyle\leq\left(1+\eta_{t}\lambda_{1}\right)^{2}\alpha_{n,t+1}+\left(\left(\frac{1+\left(3+4\epsilon\right)|\lambda_{2}\left(P\right)|}{1-\left|\lambda_{2}\left(P\right)\right|}\right)\mathcal{V}+\xi_{k,t}\right)\eta_{t}^{2}\alpha_{n,t+k_{t}}$
$\displaystyle=\left(1+2\eta_{t}\lambda_{1}+\eta_{t}^{2}\left(\left(\frac{1+\left(3+4\epsilon\right)|\lambda_{2}\left(P\right)|}{1-\left|\lambda_{2}\left(P\right)\right|}\right)\mathcal{V}+\lambda_{1}^{2}+\xi_{k,t}\right)\right)\alpha_{n,t+1}$

Therefore using this recursion, we have,

$\displaystyle\alpha_{n,1}$
$\displaystyle\leq\alpha_{n,n-k_{n}+1}\exp\left(2\lambda_{1}\sum_{t=1}^{n-k_{n}}\eta_{t}+\sum_{t=1}^{n-k_{n}}\eta_{t}^{2}\left(\left(\frac{1+\left(3+4\epsilon\right)|\lambda_{2}\left(P\right)|}{1-\left|\lambda_{2}\left(P\right)\right|}\right)\mathcal{V}+\lambda_{1}^{2}+\xi_{k,t}\right)\right)$

Let $B_{n,n-k_{n}+1}=I+R^{\prime}$, where $\|R^{\prime}\|\leq r$ a.s.

$\displaystyle\alpha_{n,n-k_{n}+1}$
$\displaystyle=\mathbb{E}\left[v_{1}^{T}B_{n,n-k_{n}+1}B_{n,n-k_{n}+1}^{T}v_{1}\right]$
$\displaystyle=\mathbb{E}\left[v_{1}^{T}v_{1}\right]+\mathbb{E}\left[v_{1}^{T}(R^{\prime}+R^{\prime
T})v_{1}\right]+\mathbb{E}\left[v_{1}^{T}R^{\prime}R^{\prime T}v_{1}\right]$
$\displaystyle\leq 1+2r+r^{2}$

Using Lemma 2 we have

$\displaystyle r$
$\displaystyle\leq\left(1+\epsilon\right)k_{n}\eta_{n-k_{n}+1}\left(\mathcal{M}+\lambda_{1}\right)$
$\displaystyle\leq\left(1+\epsilon\right)k_{n}\eta_{n-k_{n}}\left(\mathcal{M}+\lambda_{1}\right)$
$\displaystyle\leq
2\left(1+\epsilon\right)k_{n}\eta_{n}\left(\mathcal{M}+\lambda_{1}\right)\;\;\text{since
}\eta_{n-k_{n}}\leq 2\eta_{n}$

Therefore,

$\displaystyle\alpha_{n,1}$
$\displaystyle\leq\left(1+2r+r^{2}\right)\exp\left(2\lambda_{1}\sum_{t=1}^{n-k_{n}}\eta_{t}+\sum_{t=1}^{n-k_{n}}\eta_{t}^{2}\left(\left(\frac{1+\left(3+4\epsilon\right)|\lambda_{2}\left(P\right)|}{1-\left|\lambda_{2}\left(P\right)\right|}\right)\mathcal{V}+\lambda_{1}^{2}+\xi_{k,t}\right)\right)$

Hence proved. ∎

######  Theorem 3.

(General Version) Let $u:=\min\left\\{i:i\in[n],i-k_{i}\geq 0\right\\}$. Then,

$\displaystyle\mathbb{E}\left[\operatorname{Tr}\left(V_{\perp}^{T}B_{n}B_{n}^{T}V_{\perp}\right)\right]$
$\displaystyle\leq\left(1+5\epsilon\right)\exp\left(\sum_{i=u+1}^{n}2\eta_{i}\lambda_{2}+\left(\mathcal{V}^{\prime}+\lambda_{1}^{2}+\xi_{k,i}\right)\eta_{i-k_{i}}^{2}\right)$
$\displaystyle\qquad\times\left(d+\sum_{i=u+1}^{n}\left(\mathcal{V}^{\prime}+\xi_{k,i}\right)C_{k,i}^{\prime}\eta_{i-k_{i}}^{2}\exp\left(\sum_{j=u+1}^{i}2\eta_{j}\left(\lambda_{1}-\lambda_{2}\right)\right)\right)$

where
$C_{k,t}^{\prime}:=\exp\left(2\lambda_{1}\sum_{j=1}^{u}\left(\eta_{j}-\eta_{t-u+j}\right)+\sum_{j=1}^{t-u}\eta_{j}^{2}\left(\overline{\mathcal{V}_{k,j}}-\overline{\mathcal{V}_{k,j+u}}\right)\right)$
and $B_{t}$ is defined in 2.

###### Proof.

For $t\leq n$, let

$\displaystyle\alpha_{t}:=\alpha_{t,1}=\mathbb{E}\left[v_{1}^{T}B_{t}B_{t}^{T}v_{1}\right]=\mathbb{E}\left[\operatorname{Tr}\left(v_{1}^{T}B_{t}B_{t}^{T}v_{1}\right)\right],\;\text{as
defined in Theorem }\ref{theorem:v1upperbound}$
$\displaystyle\beta_{t}:=\mathbb{E}\left[\operatorname{Tr}\left(V_{\perp}^{T}B_{t}B_{t}^{T}V_{\perp}\right)\right]$

Note that $\alpha_{t}+\beta_{t}=\operatorname{Tr}\left(B_{t}B_{t}^{T}\right)$
by definition. Then,

$\displaystyle\operatorname{Tr}\left(B_{t}B_{t}^{T}V_{\perp}V_{\perp}^{T}\right)$
$\displaystyle=\operatorname{Tr}\left(B_{t-1}B_{t-1}^{T}(I+\eta_{t}\Sigma)V_{\perp}V_{\perp}^{T}(I+\eta_{t}\Sigma)\right)+\eta_{t}\operatorname{Tr}\left(B_{t-1}^{T}(I+\eta_{t}\Sigma)V_{\perp}V_{\perp}^{T}(A_{t}-\Sigma)B_{t-1}\right)$
$\displaystyle\;\;\;\;\;\;\;\;+\eta_{t}\operatorname{Tr}\left(B_{t-1}^{T}(A_{t}-\Sigma)V_{\perp}V_{\perp}^{T}(I+\eta_{t}\Sigma)B_{t-1}\right)+\eta_{t}^{2}\operatorname{Tr}\left(B_{t-1}B_{t-1}^{T}(A_{t}-\Sigma)V_{\perp}V_{\perp}^{T}(A_{t}-\Sigma)\right)$
$\displaystyle\leq(1+\eta_{t}\lambda_{2})^{2}\operatorname{Tr}\left(B_{t-1}B_{t-1}^{T}V_{\perp}V_{\perp}^{T}\right)+2\eta_{t}\underbrace{\operatorname{Tr}\left(B_{t-1}B_{t-1}^{T}(I+\eta_{t}\Sigma)V_{\perp}V_{\perp}^{T}(A_{t}-\Sigma)\right)}_{P_{t}}$
$\displaystyle\;\;\;\;\;\;\;\;+\eta_{t}^{2}\underbrace{\operatorname{Tr}\left(B_{t-1}B_{t-1}^{T}(A_{t}-\Sigma)V_{\perp}V_{\perp}^{T}(A_{t}-\Sigma)\right)}_{Q_{t}}$

Let $B_{t-1}=\left(I+R\right)B_{t-k_{t}}$ with $\|R\|_{2}\leq r$. Using Lemma
S.10 with
$G=\left(I+\eta_{t}\Sigma\right)V_{\perp}V_{\perp}^{T}=V_{\perp}(I+\eta_{t}\Lambda_{\perp})V_{\perp}^{T},\gamma=1$,
where $\Lambda_{\perp}$ is a $d-1\times d-1$ diagonal matrix of eigenvalues
$\lambda_{2},\dots,\lambda_{d}$ of $\Sigma$, and noting that
$\left\|V_{\perp}V_{\perp}^{T}\right\|_{2}=1$,

$\displaystyle\mathbb{E}\left[P_{t}\right]$
$\displaystyle\leq\left(1+\eta_{t}\lambda_{1}\right)\eta_{t-k_{t}}\left(\frac{2\mathcal{V}\left|\lambda_{2}\left(P\right)\right|}{1-\left|\lambda_{2}\left(P\right)\right|}+\eta_{t-k_{t}}\mathcal{M}\left(2\left(1+8\epsilon\right)+\left(2+\left(1+\epsilon\right)^{2}\right)k_{t}^{2}\left(\mathcal{M}+\lambda_{1}\right)^{2}\right)\right)\left(\alpha_{t-k_{t}}+\beta_{t-k_{t}}\right)$
$\displaystyle\leq\left(1+\epsilon\right)\eta_{t-k_{t}}\left(\frac{2\mathcal{V}\left|\lambda_{2}\left(P\right)\right|}{1-\left|\lambda_{2}\left(P\right)\right|}+\eta_{t-k_{t}}\mathcal{M}\left(2\left(1+8\epsilon\right)+\left(2+\left(1+\epsilon\right)^{2}\right)k_{t}^{2}\left(\mathcal{M}+\lambda_{1}\right)^{2}\right)\right)\left(\alpha_{t-k_{t}}+\beta_{t-k_{t}}\right)$

where in the last line, we used
$\eta_{t}\lambda_{1}\leq\eta_{t}k_{t}\left(\mathcal{M}+\lambda_{1}\right)\leq\epsilon$.

Using Lemma S.11 with $U=V_{\perp}V_{\perp}^{T},\gamma=1$,

$\displaystyle\mathbb{E}\left[Q_{t}\right]$
$\displaystyle\leq\left(\mathcal{V}+\eta_{t-k_{t}+1}\mathcal{M}^{2}\left(2\eta_{t}+2\left(1+\epsilon\right)\left(1+\epsilon\left(1+\epsilon\right)\right)k_{t}\left(\mathcal{M}+\lambda_{1}\right)\right)\right)\left(\alpha_{t-k_{t}}+\beta_{t-k_{t}}\right)$
$\displaystyle\stackrel{{\scriptstyle(i)}}{{\leq}}\left(\mathcal{V}+2\epsilon\eta_{t}\mathcal{M}+2\eta_{t-k_{t}+1}\mathcal{M}^{2}\left(\left(1+\epsilon\right)\left(1+\epsilon\left(1+\epsilon\right)\right)k_{t}\left(\mathcal{M}+\lambda_{1}\right)\right)\right)\left(\alpha_{t-k_{t}}+\beta_{t-k_{t}}\right)$
$\displaystyle\stackrel{{\scriptstyle(ii)}}{{\leq}}\left(\mathcal{V}+2\epsilon\eta_{t}\mathcal{M}+2\eta_{t-k_{t}+1}\mathcal{M}\left(\left(1+\epsilon\right)\left(1+\epsilon\left(1+\epsilon\right)\right)k_{t}^{2}\left(\mathcal{M}+\lambda_{1}\right)^{2}\right)\right)\left(\alpha_{t-k_{t}}+\beta_{t-k_{t}}\right)$

where in $(i)$ we used $\forall
i,\;\eta_{i}\mathcal{M}\leq\eta_{i}k_{i}\left(\mathcal{M}+\lambda_{1}\right)\leq\epsilon$
and in $(ii)$ we used $\mathcal{M}\leq
k_{t}\left(\mathcal{M}+\lambda_{1}\right)$. Putting everything together, we
have,

$\displaystyle\mathbb{E}\left[\operatorname{Tr}\left(B_{t}B_{t}^{T}V_{\perp}V_{\perp}^{T}\right)\right]$
$\displaystyle\;\;\leq\left(1+\eta_{t}\lambda_{2}\right)^{2}\beta_{t-1}$
$\displaystyle\;\;\;\;\;\;\;\;+2\left(1+\epsilon\right)\eta_{t}\eta_{t-k_{t}}\left(\frac{2\mathcal{V}\left|\lambda_{2}\left(P\right)\right|}{1-\left|\lambda_{2}\left(P\right)\right|}+\eta_{t-k_{t}}\mathcal{M}\left(2\left(1+8\epsilon\right)+\left(2+\left(1+\epsilon\right)^{2}\right)k_{t}^{2}\left(\mathcal{M}+\lambda_{1}\right)^{2}\right)\right)\left(\alpha_{t-k_{t}}+\beta_{t-k_{t}}\right)$
$\displaystyle\;\;\;\;\;\;\;\;\;+\eta_{t}^{2}\left(\mathcal{V}+2\epsilon\eta_{t}\mathcal{M}+2\eta_{t-k_{t}+1}\mathcal{M}\left(\left(1+\epsilon\right)\left(1+\epsilon\left(1+\epsilon\right)\right)k_{t}^{2}\left(\mathcal{M}+\lambda_{1}\right)^{2}\right)\right)\left(\alpha_{t-k_{t}}+\beta_{t-k_{t}}\right)$
$\displaystyle\;\;\leq\left(1+\eta_{t}\lambda_{2}\right)^{2}\beta_{t-1}$
$\displaystyle\;\;\;\;\;\;\;\;+2\left(1+\epsilon\right)\eta_{t-k_{t}}^{2}\left(\frac{2\mathcal{V}\left|\lambda_{2}\left(P\right)\right|}{1-\left|\lambda_{2}\left(P\right)\right|}+\eta_{t-k_{t}}\mathcal{M}\left(2\left(1+8\epsilon\right)+\left(2+\left(1+\epsilon\right)^{2}\right)k_{t}^{2}\left(\mathcal{M}+\lambda_{1}\right)^{2}\right)\right)\left(\alpha_{t-k_{t}}+\beta_{t-k_{t}}\right)$
$\displaystyle\;\;\;\;\;\;\;\;\;+\eta_{t-k_{t}}^{2}\left(\mathcal{V}+2\epsilon\eta_{t}\mathcal{M}+2\eta_{t-k_{t}+1}\mathcal{M}\left(\left(1+\epsilon\right)\left(1+\epsilon\left(1+\epsilon\right)\right)k_{t}^{2}\left(\mathcal{M}+\lambda_{1}\right)^{2}\right)\right)\left(\alpha_{t-k_{t}}+\beta_{t-k_{t}}\right)$
$\displaystyle\;\;\leq\left(1+\eta_{t}\lambda_{2}\right)^{2}\beta_{t-1}+\eta_{t-k_{t}}^{2}\left(\left(\frac{1+\left(3+4\epsilon\right)|\lambda_{2}\left(P\right)|}{1-\left|\lambda_{2}\left(P\right)\right|}\right)\mathcal{V}+\xi_{k,t}\right)\left(\alpha_{t-k_{t}}+\beta_{t-k_{t}}\right)$

where $\xi_{k,t}$ is as defined in S.4. Therefore using Lemma S.4,

$\displaystyle\mathbb{E}\left[\operatorname{Tr}\left(B_{t}B_{t}^{T}V_{\perp}V_{\perp}^{T}\right)\right]$
$\displaystyle\leq\left(1+2\eta_{t}\lambda_{2}+\eta_{t-k_{t}}^{2}\left(\left(\frac{1+\left(3+4\epsilon\right)|\lambda_{2}\left(P\right)|}{1-\left|\lambda_{2}\left(P\right)\right|}\right)\mathcal{V}+\lambda_{2}^{2}+\xi_{k,t}\right)\right)\beta_{t-1}$
$\displaystyle+\eta_{t-k_{t}}^{2}\left(\left(\frac{1+\left(3+4\epsilon\right)|\lambda_{2}\left(P\right)|}{1-\left|\lambda_{2}\left(P\right)\right|}\right)\mathcal{V}+\xi_{k,t}\right)\alpha_{t-1}$
(61)

Let
$\chi_{\epsilon}:=1+4\epsilon\left(1+\epsilon\right)\left(1+\epsilon+\epsilon^{2}\right)\leq
1.05$. From Theorem 2 denoting

$\displaystyle
r_{k,t}:=1+4\left(1+\epsilon\right)\eta_{t-1}k_{t-1}\left(\mathcal{M}+\lambda_{1}\right)+4\left(1+c\right)^{2}\eta_{t-1}^{2}k_{t-1}^{2}\left(\mathcal{M}+\lambda_{1}\right)^{2}\leq
1+4\epsilon\left(1+\epsilon\right)\left(1+\epsilon+\epsilon^{2}\right)=\chi_{\epsilon},$
(62)

we have,

$\displaystyle\alpha_{t-1}\leq
r_{k,t}\exp\left(2\lambda_{1}\sum_{i=1}^{t-k_{t}-1}\eta_{t}+\sum_{i=1}^{t-k_{t}-1}\eta_{i}^{2}\left(\left(\frac{1+\left(3+4\epsilon\right)|\lambda_{2}\left(P\right)|}{1-\left|\lambda_{2}\left(P\right)\right|}\right)\mathcal{V}+\lambda_{1}^{2}+\xi_{k,i}\right)\right)$

Now, we note the definition of $\overline{\mathcal{V}_{k,t}}$ and
$\mathcal{V}^{\prime}$ as mentioned in S.4 -

$\displaystyle\overline{\mathcal{V}_{k,t}}$
$\displaystyle:=\left(\frac{1+\left(3+4\epsilon\right)|\lambda_{2}\left(P\right)|}{1-\left|\lambda_{2}\left(P\right)\right|}\right)\mathcal{V}+\lambda_{1}^{2}+\xi_{k,t}$
$\displaystyle=\mathcal{V}^{\prime}+\lambda_{1}^{2}+\xi_{k,t}$

Therefore using 61,

$\displaystyle\beta_{t}$
$\displaystyle\leq\left(1+2\eta_{t}\lambda_{2}+\eta_{t-k_{t}}^{2}\overline{\mathcal{V}_{k,t}}\right)\beta_{t-1}+\eta_{t-k_{t}}^{2}r_{k,t}\left(\mathcal{V}^{\prime}+\xi_{k,t}\right)\exp\left(2\lambda_{1}\sum_{i=1}^{t-k_{t}-1}\eta_{i}+\sum_{i=1}^{t-k_{t}-1}\eta_{i}^{2}\overline{\mathcal{V}_{k,i}}\right)$

Recursing on the above inequality for $u<t\leq n$ where
$u=\min\left\\{i:i\in[n],i-k_{i}\geq 0\right\\}$, we have,

$\displaystyle\beta_{n}$
$\displaystyle\leq\beta_{u}\exp\left(2\sum_{i=u+1}^{n}\eta_{i}\lambda_{2}+\sum_{i=u+1}^{n}\overline{\mathcal{V}_{k,i}}\eta_{i-k_{i}}^{2}\right)$
$\displaystyle\;\;\;\;\;\;+\sum_{i=u+1}^{n}r_{k,i}\left(\mathcal{V}^{\prime}+\xi_{k,i}\right)\eta_{i-k_{i}}^{2}\exp\left(\sum_{j=i+1}^{n}\left(2\eta_{j}\lambda_{2}+\overline{\mathcal{V}_{k,j}}\eta_{j-k_{j}}^{2}\right)\right)\exp\left(\sum_{j=1}^{i-k_{i}}2\eta_{j}\lambda_{1}+\overline{\mathcal{V}_{k,j}}\eta_{j}^{2}\right)$
$\displaystyle\leq\exp\left(\sum_{i=u+1}^{n}2\eta_{i}\lambda_{2}+\overline{\mathcal{V}_{k,i}}\eta_{i-k_{i}}^{2}\right)$
$\displaystyle\;\;\;\;\;\;\times\left(\beta_{u}+\sum_{i=u+1}^{n}r_{k,i}\left(\mathcal{V}^{\prime}+\xi_{k,i}\right)\eta_{i-k_{i}}^{2}\exp\left(\sum_{j=1}^{i-k_{i}}(2\eta_{j}\lambda_{1}+\overline{\mathcal{V}_{k,j}}\eta_{j}^{2})-\sum_{j=u+1}^{i}\left(2\eta_{j}\lambda_{2}+\overline{\mathcal{V}_{k,j}}\eta_{j-k_{j}}^{2}\right)\right)\right)$

Now, since $k_{i},k_{j}\geq k_{u}=u$, therefore, we have

$\displaystyle\beta_{n}$
$\displaystyle\leq\exp\left(\sum_{i=u+1}^{n}2\eta_{i}\lambda_{2}+\overline{\mathcal{V}_{k,i}}\eta_{i-k_{i}}^{2}\right)\times$
$\displaystyle\;\;\;\;\;\;\;\left(\beta_{u}+\sum_{i=u+1}^{n}r_{k,i}\left(\mathcal{V}^{\prime}+\xi_{k,i}\right)\eta_{i-k_{i}}^{2}\exp\left(\sum_{j=1}^{i-u}(2\eta_{j}\lambda_{1}+\overline{\mathcal{V}_{k,j}}\eta_{j}^{2})-\sum_{j=u+1}^{i}\left(2\eta_{j}\lambda_{2}+\overline{\mathcal{V}_{k,j}}\eta_{j-u}^{2}\right)\right)\right)$

Recall that
$C_{k,i}^{\prime}:=\exp\left(2\lambda_{1}\sum_{j=1}^{u}\left(\eta_{j}-\eta_{i-u+j}\right)+\sum_{j=1}^{i-u}\eta_{j}^{2}\left(\overline{\mathcal{V}_{k,j}}-\overline{\mathcal{V}_{k,j+u}}\right)\right)$
as defined in S.4. Therefore,

$\displaystyle\beta_{n}$
$\displaystyle\leq\exp\left(\sum_{i=u+1}^{n}2\eta_{i}\lambda_{2}+\overline{\mathcal{V}_{k,i}}\eta_{i-k_{i}}^{2}\right)\times$
$\displaystyle\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\left(\beta_{u}+\sum_{i=u+1}^{n}r_{k,i}\left(\mathcal{V}^{\prime}+\xi_{k,i}\right)C_{k,i}^{\prime}\eta_{i-k_{i}}^{2}\exp\left(\sum_{j=u+1}^{i}2\eta_{j}\left(\lambda_{1}-\lambda_{2}\right)\right)\right)$

Let $B_{u}=I+R^{\prime}$ with $\|R^{\prime}\|\leq r^{\prime}$ a.s. Using Lemma
2 we have

$\displaystyle r^{\prime}$
$\displaystyle\leq\left(1+\epsilon\right)k_{u}\eta_{1}\left(\mathcal{M}+\lambda_{1}\right)$
$\displaystyle\leq\left(1+\epsilon\right)k_{u}\eta_{0}\left(\mathcal{M}+\lambda_{1}\right)$
$\displaystyle\leq
2\left(1+\epsilon\right)k_{u}\eta_{u}\left(\mathcal{M}+\lambda_{1}\right)\;\;\text{since
}\eta_{0}=\eta_{u-k_{u}}\leq 2\eta_{u}$
$\displaystyle<2\epsilon\left(1+\epsilon\right)$

Therefore,

$\displaystyle\beta_{u}$
$\displaystyle=\mathbb{E}\left[\operatorname{Tr}\left(V_{\perp}^{T}B_{u}B_{u}^{T}V_{\perp}\right)\right]$
$\displaystyle=\mathbb{E}\left[\operatorname{Tr}\left(V_{\perp}^{T}V_{\perp}\right)\right]+\mathbb{E}\left[\operatorname{Tr}\left(V_{\perp}^{T}(R^{\prime}+R^{\prime
T})V_{\perp}\right)\right]+\mathbb{E}\left[\operatorname{Tr}\left(V_{\perp}^{T}R^{\prime}R^{\prime
T}V_{\perp}\right)\right]$ $\displaystyle\leq d\left(1+2r^{\prime}+r^{\prime
2}\right)$ $\displaystyle\leq
d\left(1+4\epsilon\left(1+\epsilon\right)+4\epsilon^{2}\left(1+\epsilon\right)^{2}\right)$
$\displaystyle=d\left(1+4\epsilon\left(1+\epsilon\right)\left(1+\epsilon+\epsilon^{2}\right)\right)$
$\displaystyle=\chi_{\epsilon}d$

The proof follows by noting that $r_{k,t}\leq\chi_{\epsilon}$ as shown in 62.
∎

######  Theorem 4.

(General Version)

$\displaystyle\mathbb{E}\left[v_{1}^{T}B_{n,1}B_{n,1}^{T}v_{1}\right]\geq\left(1-t\right)\exp\left(\sum_{i=1}^{n-k_{n}}2\eta_{i}\lambda_{1}-\sum_{i=1}^{n-k_{n}}4\eta_{i}^{2}\lambda_{1}^{2}\right)$

where
$t:=2r+s,s:=3\left(1+r\right)^{2}\exp\left(2\lambda_{1}^{2}\sum_{i=1}^{n}\eta_{i}^{2}\right)\sum_{t=1}^{n-k_{n}}W_{k,t}\eta_{t}^{2}\exp\left(\sum_{i=t+1}^{n-k_{n}}\eta_{i}^{2}\right),W_{k,t}:=\mathcal{V}^{\prime}+\xi_{k,t}$
and $B_{j,i}$ has been defined in 12.

###### Proof.

We will start will expanding the quantity of interest using Eq 59.

$\displaystyle\alpha_{n,t}=\mathbb{E}\left[v_{1}^{T}B_{n,t}B_{n,t}^{T}v_{1}\right]\geq\mathbb{E}\left[v_{1}^{T}B_{n,t+1}\left(I+\eta_{t}\Sigma\right)^{2}B_{n,t+1}^{T}v_{1}+2\eta_{t}P_{n,t}\right]$
(63)

where $P_{n,t}$ has been defined in Theorem 2. Let’s define

$\displaystyle\mathcal{S}_{t}:=\prod_{i=t}^{1}\left(I+\eta_{i}\Sigma\right)\prod_{i=1}^{t}\left(I+\eta_{i}\Sigma\right),\;\mathcal{S}_{0}=I\;\text{
and }$
$\displaystyle\delta_{n,t}:=\mathbb{E}\left[v_{1}^{T}B_{n,t+1}\mathcal{S}_{t}B_{n,t+1}^{T}v_{1}\right]$

Note that $\delta_{n,0}=\alpha_{n,1}$. First we bound $\delta_{n,n-k_{n}}$.
Let $B_{n,n-k_{n}}=I+R^{\prime}$. By Lemma 2 along with the slow-decay
assumption on the step-sizes, we know that $\|R^{\prime}\|_{2}\leq
r:=2\left(1+\epsilon\right)\eta_{n}k_{n}\left(\mathcal{M}+\lambda_{1}\right)$
a.s. Then,

$\displaystyle\delta_{n,n-k_{n}}-\prod_{i=1}^{n-k_{n}}\left(1+\eta_{i}\lambda_{1}\right)^{2}\geq-2\left|E[v_{1}^{T}R^{\prime}\mathcal{S}_{n-k_{n}}v_{1}]\right|\geq-2r\prod_{i=1}^{n-k_{n}}(1+\eta_{i}\lambda_{1})^{2}$

Therefore,

$\displaystyle\delta_{n,n-k_{n}}$
$\displaystyle\geq\prod_{i=1}^{n-k_{n}}\left(1+\eta_{i}\lambda_{1}\right)^{2}(1-2r)$
$\displaystyle=(1-2r)\left\|\mathcal{S}_{n-k_{n}}\right\|_{2}$ (64)

Now using 63, we have

$\displaystyle\delta_{n,t-1}$
$\displaystyle\geq\delta_{n,t}+2\eta_{t}\mathbb{E}\left[\underbrace{v_{1}^{T}B_{n,t+1}\left(I+\eta_{t}\Sigma\right)\mathcal{S}_{t-1}\left(A_{t}-\Sigma\right)B_{n,t+1}^{T}v_{1}}_{U_{t}}\right]$

First, observe that $\mathcal{S}_{t-1}=U\Lambda U^{T}$, where $U$ denotes a
matrix of eigenvectors of $\Sigma$, and $\Lambda$ is a PSD diagonal matrix.
Since $I+\eta_{t}\Sigma=U\Lambda^{\prime}U^{T}$ for some other PSD diagonal
matrix $\Lambda^{\prime}$, the product will also be PSD.

By using Lemma S.8 with
$U=v_{1},G=\left(I+\eta_{t}\Sigma\right)\mathcal{S}_{t-1},\gamma=1$ and noting
that $\mathbb{E}_{\pi}\left[A_{t}-\Sigma\right]=0$, we have

$\displaystyle\left|\mathbb{E}\left[U_{t}\right]\right|$
$\displaystyle\leq\left(1+\eta_{t}\lambda_{1}\right)\eta_{t+1}\left\|\mathcal{S}_{t-1}\right\|_{2}\left(\frac{2\mathcal{V}\left|\lambda_{2}\left(P\right)\right|}{1-\left|\lambda_{2}\left(P\right)\right|}+\eta_{t+1}\mathcal{M}\left(2\left(1+8\epsilon\right)+\left(2+\left(1+\epsilon\right)^{2}\right)k_{t+1}^{2}\left(\mathcal{M}+\lambda_{1}\right)^{2}\right)\right)\alpha_{n,t+k_{t+1}}$
$\displaystyle\leq\left(1+\epsilon\right)\eta_{t+1}\left\|\mathcal{S}_{t-1}\right\|_{2}W_{k,t}\alpha_{n,t+1}$

where $W_{k,t}=\mathcal{V}^{\prime}+\xi_{k,t}$. Therefore,

$\displaystyle\delta_{n,t-1}$
$\displaystyle\geq\delta_{n,t}-2\left(1+\epsilon\right)W_{k,t}\eta_{t}^{2}\alpha_{n,t+1}\left\|\mathcal{S}_{t-1}\right\|_{2}\text{
for $t\leq n-k_{n}$}$

Let

$\displaystyle\mathcal{V}^{\prime}:=\left(\frac{1+\left(3+4\epsilon\right)|\lambda_{2}\left(P\right)|}{1-\left|\lambda_{2}\left(P\right)\right|}\right)\mathcal{V}$

as defined in S.4. Unwinding the recursion for $t\leq n-k_{n}$, we have,

$\displaystyle\delta_{n,0}$
$\displaystyle\geq\delta_{n,n-k_{n}}-2\left(1+\epsilon\right)\sum_{t=1}^{n-k_{n}}W_{k,t}\eta_{t}^{2}\alpha_{n,t+1}\left\|\mathcal{S}_{t-1}\right\|_{2}$
$\displaystyle\geq(1-2r)\left\|\mathcal{S}_{n-k_{n}}\right\|_{2}-2\left(1+\epsilon\right)\left(1+r\right)^{2}\sum_{t=1}^{n-k_{n}}W_{k,t}\eta_{t}^{2}\exp\left(2\lambda_{1}\sum_{i=t+1}^{n-k_{n}}\eta_{i}+\sum_{i=t+1}^{n-k_{n}}\eta_{i}^{2}\left(\mathcal{V}^{\prime}+\lambda_{1}^{2}+C_{k,i}\right)\right)\left\|\mathcal{S}_{t-1}\right\|_{2}$

where second step followed from Theorem 2 and 64.

Using the inequalities $\forall x\in\mathbb{R},\;1+x\leq e^{x}$ and $\forall
x\in\mathbb{R},\;x\geq 0,1+x\geq e^{x-x^{2}}$, $\forall t$ we have,

$\displaystyle\left\|\mathcal{S}_{t}\right\|_{2}=\prod_{i=1}^{t}(1+\eta_{i}\lambda_{1})^{2}\leq\exp\left(2\lambda_{1}\sum_{i=1}^{t}\eta_{i}\right)\text{,
and }$
$\displaystyle\left\|\mathcal{S}_{t}\right\|_{2}=\prod_{i=1}^{t}(1+\eta_{i}\lambda_{1})^{2}\geq\exp\left(2\lambda_{1}\sum_{i=1}^{t}\eta_{i}-4\lambda_{1}^{2}\sum_{i=1}^{t}\eta_{i}^{2}\right)$

Therefore denoting
$\theta_{\epsilon}:=2\left(1+\epsilon\right)\exp\left(2\lambda_{1}^{2}\sum_{i=1}^{n}\eta_{i}^{2}\right)$,
we have

$\displaystyle\delta_{n,0}$
$\displaystyle\geq\exp\left(2\lambda_{1}\sum_{i=1}^{n-k_{n}}\eta_{i}-4\lambda_{1}^{2}\sum_{i=1}^{n-k_{n}}\eta_{i}^{2}\right)\left[\left(1-2r\right)-\theta_{\epsilon}\left(1+r\right)^{2}\sum_{t=1}^{n-k_{n}}W_{k,t}\eta_{t}^{2}\exp\left(\sum_{i=t+1}^{n-k_{n}}\eta_{i}^{2}\left(\mathcal{V}^{\prime}+\lambda_{1}^{2}+C_{k,i}\right)\right)\right]$
$\displaystyle\geq\exp\left(2\lambda_{1}\sum_{i=1}^{n-k_{n}}\eta_{i}-4\lambda_{1}^{2}\sum_{i=1}^{n-k_{n}}\eta_{i}^{2}\right)\left[\left(1-2r\right)-\theta_{\epsilon}\left(1+r\right)^{2}\sum_{t=1}^{n-k_{n}}W_{k,t}\eta_{t}^{2}\exp\left(\sum_{i=t+1}^{n-k_{n}}\eta_{i}^{2}\left(\mathcal{V}^{\prime}+\lambda_{1}^{2}+C_{k,i}\right)\right)\right]$
$\displaystyle\geq\exp\left(2\lambda_{1}\sum_{i=1}^{n-k_{n}}\eta_{i}-4\lambda_{1}^{2}\sum_{i=1}^{n-k_{n}}\eta_{i}^{2}\right)\left[1-\left(2r+\theta_{\epsilon}\left(1+r\right)^{2}\sum_{t=1}^{n-k_{n}}W_{k,t}\eta_{t}^{2}\exp\left(\sum_{i=t+1}^{n-k_{n}}\eta_{i}^{2}\overline{\mathcal{V}_{k,i}}\right)\right)\right]$

where $\overline{\mathcal{V}_{k,i}}$ is defined in S.4. Hence proved. ∎

######  Theorem 5.

(General Version)

$\displaystyle\mathbb{E}\left[\left(v_{1}^{T}B_{n,1}B_{n,1}^{T}v_{1}\right)^{2}\right]\leq\left(1+r\right)^{4}\exp\left(\sum_{i=1}^{n-k_{n}}4\eta_{i}\lambda_{1}+\sum_{i=1}^{n-k_{n}}\eta_{i}^{2}\zeta_{k,i}\right)$

where $B_{j,i}$ has been defined in 12.

###### Proof.

Define $Q_{n,t}:=v_{1}^{T}B_{n,t+1}(A_{t}-\Sigma)^{2}B_{n,t+1}^{T}v_{1}$, and
$P_{n,t}:=v_{1}^{T}B_{n,t+1}(I+\eta_{t}\Sigma)(A_{t}-\Sigma)B_{n,t+1}^{T}v_{1}$.
Using 59, we have, for $n\geq t\geq 1$,

$\displaystyle 0\leq v_{1}^{T}B_{n,t}B_{n,t}^{T}v_{1}$
$\displaystyle=v_{1}^{T}B_{n,t+1}(I+\eta_{t}\Sigma)^{2}B_{n,t+1}^{T}v_{1}+\eta_{t}^{2}Q_{n,t}+2\eta_{t}P_{n,t}$
$\displaystyle\leq
v_{1}^{T}B_{j,t+1}B_{j,t+1}^{T}v_{1}(1+\eta_{t}\lambda_{1})^{2}+\eta_{t}^{2}\mathcal{M}^{2}\left(v_{1}^{T}B_{n,t+1}B_{n,t+1}^{T}v_{1}\right)+2\eta_{t}P_{n,t}$
$\displaystyle\leq
v_{1}^{T}B_{j,t+1}B_{j,t+1}^{T}v_{1}\underbrace{\left((1+\eta_{t}\lambda_{1})^{2}+\eta_{t}^{2}\mathcal{M}^{2}\right)}_{c_{t}}+2\eta_{t}P_{n,t}$

Thus, we have -

$\displaystyle\kappa_{n,t}:=\mathbb{E}\left[(v_{1}^{T}B_{n,t}B_{n,t}^{T}v_{1})^{2}\right]$
$\displaystyle\leq\mathbb{E}\left[\left(c_{t}v_{1}^{T}B_{n,t+1}B_{n,t+1}^{T}v_{1}+2\eta_{t}P_{n,t}\right)^{2}\right]$
$\displaystyle\leq
c_{t}^{2}\kappa_{n,t+1}+4\eta_{t}^{2}\mathbb{E}\left[P_{n,t}^{2}\right]+4c_{t}\eta_{t}\mathbb{E}\left[\left(v_{1}^{T}B_{n,t+1}B_{n,t+1}^{T}v_{1}\right)P_{n,t}\right]$
(65)

Note that,

$\displaystyle\mathbb{E}\left[P_{n,t}^{2}\right]$
$\displaystyle\leq\mathbb{E}\left[\left(v_{1}^{T}B_{n,t+1}(I+\eta_{t}\Sigma)(A_{t}-\Sigma)B_{n,t+1}^{T}v_{1}\right)^{2}\right]$
$\displaystyle\leq(1+\eta_{t}\lambda_{1})^{2}\mathcal{M}^{2}\mathbb{E}\left[\left(v_{1}^{T}B_{n,t+1}B_{n,t+1}^{T}v_{1}\right)^{2}\right]$
$\displaystyle=(1+\eta_{t}\lambda_{1})^{2}\mathcal{M}^{2}\kappa_{n,t+1}$

Now we work on the cross-term. For the convenience of notation, let’s denote
$k:=k_{t+1}$ unless otherwise specified. Let
$B_{n,t+1}=B_{n,t+k}\left(I+R\right)$ with,

$\displaystyle\|R\|_{2}\leq(1+c)\eta_{t+1}k(\mathcal{M}+\lambda_{1})=:r_{t}\leq\epsilon\left(1+\epsilon\right)$

Using Lemma 2, we have

$\displaystyle|\underbrace{v_{1}^{T}B_{n,t+1}B_{n,t+1}^{T}v_{1}-v_{1}^{T}B_{n,t+k}B_{n,t+k}^{T}v_{1}}_{Y_{1}}|$
$\displaystyle=|v_{1}^{T}B_{n,t+k}(R+R^{T}+RR^{T})B_{n,t+k}^{T}v_{1}|$
$\displaystyle\leq|v_{1}^{T}B_{n,t+k}B_{n,t+k}^{T}v_{1}|\left(2r_{t}+r_{t}^{2}\right)$
(66)

We will also bound

$\displaystyle|\underbrace{v_{1}^{T}B_{n,t+1}(I+\eta_{t}\Sigma)(A_{t}-\Sigma)B_{n,t+1}^{T}v_{1}-v_{1}^{T}B_{n,t+k}(I+\eta_{t}\Sigma)(A_{t}-\Sigma)B_{n,t+k}^{T}v_{1}}_{Y_{2}}|$
$\displaystyle\;\;\;\;=|v_{1}^{T}B_{n,t+k}R(I+\eta_{t}\Sigma)(A_{t}-\Sigma)(I+R^{T})B_{n,t+k}^{T}v_{1}+v_{1}^{T}B_{n,t+k}(I+\eta_{t}\Sigma)(A_{t}-\Sigma)R^{T}B_{n,t+k}^{T}v_{1}|$
$\displaystyle\;\;\;\;\leq(2r_{t}+r_{t}^{2})\left(1+\eta_{t}\lambda_{1}\right)\mathcal{M}|v_{1}^{T}B_{n,t+k}B_{n,t+k}^{T}v_{1}|$
(67)

So, now we have:

$\displaystyle\mathbb{E}\left[\left(v_{1}^{T}B_{n,t+1}B_{n,t+1}^{T}v_{1}P_{n,t}\right)\right]$
$\displaystyle=\mathbb{E}\left[(v_{1}^{T}B_{n,t+1}B_{n,t+1}^{T}v_{1})(v_{1}^{T}B_{n,t+1}(I+\eta_{t}\Sigma)(A_{t}-\Sigma)B_{n,t+1}^{T}v_{1})\right]$
$\displaystyle=\mathbb{E}\left[(Y_{1}+v_{1}^{T}B_{n,t+k}B_{n,t+k}^{T}v_{1})(Y_{2}+v_{1}^{T}B_{n,t+k}(I+\eta_{t}\Sigma)(A_{t}-\Sigma)B_{n,t+k}^{T}v_{1})\right]$
$\displaystyle=\underbrace{\mathbb{E}\left[Y_{1}Y_{2}\right]}_{T_{1}}+\underbrace{\mathbb{E}\left[Y_{1}v_{1}^{T}B_{n,t+k}(I+\eta_{t}\Sigma)(A_{t}-\Sigma)B_{n,t+k}^{T}v_{1}\right]}_{T_{2}}+\underbrace{\mathbb{E}\left[Y_{2}v_{1}^{T}B_{n,t+k}B_{n,t+k}^{T}v_{1}\right]}_{T_{3}}$
$\displaystyle\;\;+\underbrace{\mathbb{E}\left[(v_{1}^{T}B_{n,t+k}B_{n,t+k}^{T}v_{1})(v_{1}^{T}B_{n,t+k}(I+\eta_{t}\Sigma)(A_{t}-\Sigma)B_{n,t+k}^{T}v_{1})\right]}_{T_{4}}$

Lets start with the last term, $T_{4}$. Using Lemma S.3 we have,

$\displaystyle|T_{4}|$
$\displaystyle\leq\left|\mathbb{E}\left[(v_{1}^{T}B_{n,t+k}B_{n,t+k}^{T}v_{1})(v_{1}^{T}B_{n,t+k}(I+\eta_{t}\Sigma)\mathbb{E}\left[(A_{t}-\Sigma)|s_{t+k}\right]B_{n,t+k}^{T}v_{1})\right]\right|$
$\displaystyle\leq
2(1+\eta_{t}\lambda_{1})\mathcal{M}d_{\text{mix}}\left(k\right)\kappa_{n,t+k}$
$\displaystyle\leq
2\eta_{t+1}^{2}(1+\eta_{t}\lambda_{1})\mathcal{M}\kappa_{n,t+k}$
$\displaystyle\leq
2\eta_{t+1}^{2}(1+\eta_{t}\lambda_{1})\mathcal{M}\kappa_{n,t+1}$

Using Eqs S.4 and S.4 the first three terms can be bounded as:

$\displaystyle|T_{1}|\leq\mathbb{E}\left[|Y_{1}Y_{2}|\right]$
$\displaystyle\leq\left(2r_{t}+r_{t}^{2}\right)^{2}\left(1+\eta_{t}\lambda_{1}\right)\mathcal{M}\kappa_{n,t+k}$
$\displaystyle\leq\left(2r_{t}+r_{t}^{2}\right)^{2}\left(1+\eta_{t}\lambda_{1}\right)\mathcal{M}\kappa_{n,t+1}\text{
using Lemma }\ref{lemma:inner_product_monotonicity}$
$\displaystyle=\left(2+r_{t}\right)^{2}r_{t}^{2}\left(1+\eta_{t}\lambda_{1}\right)\mathcal{M}\kappa_{n,t+1}$
$\displaystyle\leq\left(1+\epsilon\right)^{2}\left(2+\epsilon\left(1+\epsilon\right)\right)^{2}\left(1+\eta_{t}\lambda_{1}\right)\eta_{t+1}^{2}k_{t+1}^{2}\mathcal{M}\left(\mathcal{M}+\lambda_{1}\right)^{2}\kappa_{n,t+1}$
$\displaystyle\leq\left(1+\epsilon\right)^{3}\left(2+\epsilon+\epsilon^{2}\right)^{2}\eta_{t+1}^{2}k_{t+1}^{2}\mathcal{M}\left(\mathcal{M}+\lambda_{1}\right)^{2}\kappa_{n,t+1}\text{
since }\eta_{t}\lambda_{1}\leq\epsilon$
$\displaystyle|T_{2}|\leq\mathbb{E}\left[|Y_{1}v_{1}^{T}B_{n,t+k}(I+\eta_{t}\Sigma)(A_{t}-\Sigma)B_{n,t+k}^{T}v_{1}|\right]$
$\displaystyle\leq\left(2+r_{t}\right)r_{t}\left(1+\eta_{t}\lambda_{1}\right)\mathcal{M}\kappa_{n,t+k}$
$\displaystyle\leq\left(2+r_{t}\right)r_{t}\left(1+\eta_{t}\lambda_{1}\right)\mathcal{M}\kappa_{n,t+1}\text{
using Lemma }\ref{lemma:inner_product_monotonicity}$
$\displaystyle\leq\left(2+\epsilon+\epsilon^{2}\right)\left(1+\epsilon\right)\left(1+\eta_{t}\lambda_{1}\right)\eta_{t+1}k_{t+1}\left(\mathcal{M}+\lambda_{1}\right)\mathcal{M}\kappa_{n,t+1}$
$\displaystyle\leq\left(1+\epsilon\right)^{2}\left(2+\epsilon+\epsilon^{2}\right)\eta_{t+1}k_{t+1}\mathcal{M}\left(\mathcal{M}+\lambda_{1}\right)\kappa_{n,t+1}$

and similarly,

$\displaystyle|T_{3}|\leq\mathbb{E}\left[Y_{2}v_{1}^{T}B_{n,t+k}B_{n,t+k}^{T}v_{1}\right]$
$\displaystyle\leq
r_{t}\left(2+r_{t}\right)\left(1+\eta_{t}\lambda_{1}\right)\mathcal{M}\kappa_{n,t+k}$
$\displaystyle\leq\left(1+\epsilon\right)\left(2+\epsilon+\epsilon^{2}\right)\left(1+\eta_{t}\lambda_{1}\right)\eta_{t+1}k_{t+1}\mathcal{M}\left(\mathcal{M}+\lambda_{1}\right)\kappa_{n,t+k}$
$\displaystyle\leq\left(1+\epsilon\right)^{2}\left(2+\epsilon+\epsilon^{2}\right)\eta_{t+1}k_{t+1}\mathcal{M}\left(\mathcal{M}+\lambda_{1}\right)\kappa_{n,t+k}$
$\displaystyle\leq\left(1+\epsilon\right)^{2}\left(2+\epsilon+\epsilon^{2}\right)\eta_{t+1}k_{t+1}\mathcal{M}\left(\mathcal{M}+\lambda_{1}\right)\kappa_{n,t+1}\text{
using Lemma }\ref{lemma:inner_product_monotonicity}$

Note that

$\displaystyle c_{t}$
$\displaystyle:=(1+\eta_{t}\lambda_{1})^{2}+\eta_{t}^{2}\mathcal{M}^{2}\leq
1+2\epsilon+2\epsilon^{2}\text{, and }$ $\displaystyle c_{t}^{2}$
$\displaystyle=\left(1+2\eta_{t}\lambda_{1}+\eta_{t}^{2}\left(\mathcal{M}^{2}+\lambda_{1}^{2}\right)\right)^{2}$
$\displaystyle=1+4\eta_{t}^{2}\lambda_{1}^{2}+\eta_{t}^{4}\left(\mathcal{M}^{2}+\lambda_{1}^{2}\right)^{2}+4\eta_{t}\lambda_{1}+4\eta_{t}^{3}\lambda_{1}\left(\mathcal{M}^{2}+\lambda_{1}^{2}\right)+2\eta_{t}^{2}\left(\mathcal{M}^{2}+\lambda_{1}^{2}\right)$
$\displaystyle\leq
1+4\eta_{t}\lambda_{1}+\eta_{t}^{2}\left(2\mathcal{M}^{2}+6\lambda_{1}^{2}+\epsilon\mathcal{M}+\epsilon\lambda_{1}\right)+4\eta_{t}^{3}\lambda_{1}\left(\mathcal{M}^{2}+\lambda_{1}^{2}\right)$
$\displaystyle\leq
1+4\eta_{t}\lambda_{1}+6\eta_{t}^{2}\left(\mathcal{M}+\lambda_{1}\right)^{2}+4\eta_{t}^{3}\lambda_{1}\left(\mathcal{M}+\lambda_{1}\right)^{2}$

Define

$\displaystyle\phi_{\epsilon}$
$\displaystyle:=\left(1+\epsilon\right)\left(2+\epsilon+\epsilon^{2}\right)$
$\displaystyle\omega_{\epsilon}$ $\displaystyle:=1+2\epsilon+2\epsilon^{2}$
$\displaystyle\zeta_{k,t}$
$\displaystyle:=\left(10+8\left(1+\epsilon\right)+4\left(1+2\epsilon\right)\phi_{\epsilon}\right)\phi_{\epsilon}c_{t}k_{t+1}\left(\mathcal{M}+\lambda_{1}\right)^{2}$

Putting everything together in Eq 65, for $t\leq n-k_{t+1}$ we have,

$\displaystyle\frac{\kappa_{n,t}}{\kappa_{n,t+1}}$ $\displaystyle\leq
c_{t}^{2}+4\eta_{t}^{2}\left(1+\eta_{t}\lambda_{1}\right)^{2}\mathcal{M}^{2}+4\left(1+\epsilon\right)c_{t}\eta_{t}\mathcal{M}\left(2\phi_{\epsilon}\eta_{t+1}k_{t+1}\left(\mathcal{M}+\lambda_{1}\right)+\left(2+\phi_{\epsilon}^{2}k_{t+1}^{2}\left(\mathcal{M}+\lambda_{1}\right)^{2}\right)\eta_{t+1}^{2}\right)$
$\displaystyle\leq
c_{t}^{2}+4\eta_{t}^{2}\left(1+\eta_{t}\lambda_{1}\right)^{2}\mathcal{M}^{2}+4\left(1+\epsilon\right)c_{t}\eta_{t}\mathcal{M}\left(2\phi_{\epsilon}\eta_{t}k_{t+1}\left(\mathcal{M}+\lambda_{1}\right)+\left(2+\phi_{\epsilon}^{2}k_{t+1}^{2}\left(\mathcal{M}+\lambda_{1}\right)^{2}\right)\eta_{t}^{2}\right)$
$\displaystyle=c_{t}^{2}+4\eta_{t}^{2}\left[\mathcal{M}^{2}+2\phi_{\epsilon}\left(1+\epsilon\right)c_{t}\mathcal{M}\left(\mathcal{M}+\lambda_{1}\right)k_{t+1}\right]+4\eta_{t}^{3}\left[\left(1+2\epsilon\right)\lambda_{1}+\left(1+\epsilon\right)c_{t}\mathcal{M}\left(2+\phi_{\epsilon}^{2}k_{t+1}^{2}\left(\mathcal{M}+\lambda_{1}\right)^{2}\right)\right]$
$\displaystyle\leq
c_{t}^{2}+4\eta_{t}^{2}\left[2+2\phi_{\epsilon}\left(1+\epsilon\right)c_{t}k_{t+1}\right]\mathcal{M}\left(\mathcal{M}+\lambda_{1}\right)+4\left(1+2\epsilon\right)\eta_{t}^{3}\left[\lambda_{1}+c_{t}\mathcal{M}\left(2+\phi_{\epsilon}^{2}k_{t+1}^{2}\left(\mathcal{M}+\lambda_{1}\right)^{2}\right)\right]$
$\displaystyle\leq
1+4\eta_{t}\lambda_{1}+\eta_{t}^{2}\left[10+8\phi_{\epsilon}\left(2+\epsilon\right)c_{t}k_{t+1}\right]\left(\mathcal{M}+\lambda_{1}\right)^{2}+4\left(1+2\epsilon\right)\eta_{t}^{3}\left[\lambda_{1}+2c_{t}\mathcal{M}+c_{t}\phi_{\epsilon}^{2}k_{t+1}^{2}\left(\mathcal{M}+\lambda_{1}\right)^{3}\right]$
$\displaystyle\leq\exp\left(4\eta_{t}\lambda_{1}+\eta_{t}^{2}\left(10+8\phi_{\epsilon}\left(1+\epsilon\right)c_{t}k_{t+1}\right)\left(\mathcal{M}+\lambda_{1}\right)^{2}+4\left(1+2\epsilon\right)\eta_{t}^{3}\left(\lambda_{1}+c_{t}\mathcal{M}+2c_{t}\phi_{\epsilon}^{2}k_{t+1}^{2}\left(\mathcal{M}+\lambda_{1}\right)^{3}\right)\right)$
$\displaystyle\leq\exp\left(4\eta_{t}\lambda_{1}+\eta_{t}^{2}\left(10+8\phi_{\epsilon}\left(1+\epsilon\right)c_{t}k_{t+1}\right)\left(\mathcal{M}+\lambda_{1}\right)^{2}+4\epsilon\left(1+2\epsilon\right)\eta_{t}^{2}\left(2c_{t}+c_{t}\phi_{\epsilon}^{2}k_{t+1}\left(\mathcal{M}+\lambda_{1}\right)^{2}\right)\right)$
$\displaystyle\leq\exp\left(4\eta_{t}\lambda_{1}+\eta_{t}^{2}\left(8\epsilon\left(1+2\epsilon\right)\omega_{\epsilon}+\left(10+\left(8\left(1+\epsilon\right)+4\epsilon\left(1+2\epsilon\right)\phi_{\epsilon}\right)\phi_{\epsilon}\omega_{\epsilon}k_{t+1}\right)\left(\mathcal{M}+\lambda_{1}\right)^{2}\right)\right)$
$\displaystyle\leq\exp\left(4\eta_{t}\lambda_{1}+\eta_{t}^{2}\left(1+\left(10+20k_{t+1}\right)\left(\mathcal{M}+\lambda_{1}\right)^{2}\right)\right)$
$\displaystyle\leq\exp\left(4\eta_{t}\lambda_{1}+\eta_{t}^{2}\left(1+\left(10+20k_{t+1}\right)\left(\mathcal{M}+\lambda_{1}\right)^{2}\right)\right)$
$\displaystyle\leq\exp\left(4\eta_{t}\lambda_{1}+40\eta_{t}^{2}k_{t+1}\left(\mathcal{M}+\lambda_{1}\right)^{2}\right)\text{
since }\left(\mathcal{M}+\lambda_{1}\right),k_{t+1}\geq 1$

Recall our definition of $k:=k_{t+1}$. We can use the above recursion for
$1\leq t\leq n-k_{t+1}$. We note that $t=n-k_{n}$ satisfies the conditions.
Therefore,

$\displaystyle\kappa_{n,1}$
$\displaystyle\leq\exp\left(\sum_{i=1}^{n-k_{n}}4\eta_{i}\lambda_{1}+\sum_{i=1}^{n-k_{n}}\eta_{i}^{2}\zeta_{k,i}\right)\kappa_{n,n-k_{n}+1}$

Let $B_{n,n-k_{n}+1}=I+R^{\prime}$, with $\|R^{\prime}\|_{2}\leq r$ a.s.

$\displaystyle\kappa_{n,n-k_{n}+1}$
$\displaystyle=\mathbb{E}\left[\left(v_{1}^{T}B_{n,n-k_{n}+1}B_{n,n-k_{n}+1}^{T}v_{1}\right)^{2}\right]$
$\displaystyle=\mathbb{E}\left[\left(v_{1}^{T}v_{1}+v_{1}^{T}(R^{\prime}+R^{\prime
T})v_{1}+v_{1}^{T}R^{\prime}R^{\prime T}v_{1}\right)^{2}\right]$
$\displaystyle\leq\left(1+2r+r^{2}\right)^{2}\mathbb{E}\left[\left(v_{1}^{T}v_{1}\right)^{2}\right]$

Using Lemma 2, we have

$\displaystyle r$
$\displaystyle\leq\left(1+\epsilon\right)k_{n+1}\eta_{n-k_{n+1}}\left(\mathcal{M}+\lambda_{1}\right)$
$\displaystyle\leq\left(1+\epsilon\right)k_{n}\eta_{n-k_{n}}\left(\mathcal{M}+\lambda_{1}\right)$
$\displaystyle\leq
2\left(1+\epsilon\right)k_{n}\eta_{n}\left(\mathcal{M}+\lambda_{1}\right)\;\;\text{since
}\eta_{n-k_{n}}\leq 2\eta_{n}$

which completes our proof. ∎

##  Appendix S.5 Main Results : Details and Proofs

###  S.5.1 Proof of Theorem 1

######  Lemma S.13.

This lemma proves conditions required later in the proof. Let the step-sizes
be set according to Lemma S.12 and $m:=200$. Define

$\displaystyle
r:=2\left(1+\epsilon\right)\eta_{n}k_{n}\left(\mathcal{M}+\lambda_{1}\right),$
$\displaystyle
s:=3(1+r)^{2}\sum_{t=1}^{n-k_{n}-1}W_{k,t}\eta_{t}^{2}\exp\left(\sum_{i=t+1}^{n-k_{n}-1}\overline{\mathcal{V}_{k,i}}\eta_{i}^{2}\right)$

where $W_{k,t}$ is defined in Theorem 4, $\overline{\mathcal{V}_{k,i}}$ is
defined in S.4 and $\alpha,\beta,f\left(.\right),\delta$ are defined in Lemma
S.12. Then for sufficiently large number of samples $n$, such that

$\displaystyle\frac{n}{\ln\left(f\left(n\right)\right)}>\frac{\beta}{\ln\left(f\left(0\right)\right)}$

we have

  1. 1.

$2r+s\leq\frac{1}{2}$ (72)

  2. 2.

$r=2\left(1+\epsilon\right)\eta_{n}k_{n}\left(\mathcal{M}+\lambda_{1}\right)<\frac{1}{50}\frac{\delta/m}{1+\delta/m}$
(75)

###### Proof.

For (1), using Lemma S.12-(3), we note that

$\displaystyle s$ $\displaystyle\leq
3(1+r)^{2}\sum_{t=1}^{n-k_{n}-1}W_{k,t}\eta_{t}^{2}\exp\left(\sum_{i=t+1}^{n-k_{n}-1}\overline{\mathcal{V}_{k,i}}\eta_{i}^{2}\right)$
$\displaystyle\leq
3(1+r)^{2}\sum_{t=1}^{n-k_{n}-1}W_{k,t}\eta_{t}^{2}\left(1+\frac{\delta}{m}\right)$
$\displaystyle\leq\frac{3(1+r)^{2}}{100}\left(1+\frac{\delta}{m}\right)\ln\left(1+\frac{\delta}{m}\right)$
(68) $\displaystyle\leq\frac{3(1+r)^{2}\ln\left(2\right)}{50}\text{ since
}\frac{\delta}{m}<1$

Therefore,

$\displaystyle 2r+s$ $\displaystyle\leq 2r+\frac{3\left(1+r\right)^{2}}{25}$
$\displaystyle=\frac{3}{25}+\frac{56}{25}r+\frac{3}{25}r^{2}$ (69)

Setting $\frac{3}{25}+\frac{56}{25}r+\frac{3}{25}r^{2}\leq\frac{1}{2}$, we
have,

$\displaystyle\;\;\;\;\;\;\;\;\frac{3}{25}+\frac{56}{25}r+\frac{3}{25}r^{2}\leq\frac{1}{2}$
$\displaystyle\implies 6r^{2}+112r-19\leq 0$

which holds for $r\in\left[0,\frac{1}{10}\right]$.

For $\left(2\right)$, using Lemma S.12 and substituting the value of
$k_{i}:=\tau_{\text{mix}}\left(\eta_{i}^{2}\right)\leq\frac{2\tau_{\text{mix}}}{\ln\left(2\right)}\ln\left(\frac{1}{\eta_{i}^{2}}\right)$
for $\eta_{i}<1$, we note that

$\displaystyle r$
$\displaystyle\leq\frac{8\left(1+\epsilon\right)\tau_{\text{mix}}\left(\mathcal{M}+\lambda_{1}\right)}{\ln\left(2\right)}\frac{\alpha}{\left(\lambda_{1}-\lambda_{2}\right)\left(\beta+n\right)}\ln\left(\frac{\left(\lambda_{1}-\lambda_{2}\right)\left(\beta+n\right)}{\alpha}\right)$
$\displaystyle=\frac{8\left(1+\epsilon\right)\tau_{\text{mix}}\left(\mathcal{M}+\lambda_{1}\right)}{\ln\left(2\right)}\frac{\ln\left(\frac{\left(\lambda_{1}-\lambda_{2}\right)\left(\beta+n\right)}{\alpha}\right)}{\frac{\left(\lambda_{1}-\lambda_{2}\right)\left(\beta+n\right)}{\alpha}}$
$\displaystyle=\frac{8\left(1+\epsilon\right)\tau_{\text{mix}}\left(\mathcal{M}+\lambda_{1}\right)}{\ln\left(2\right)}\frac{\ln\left(f\left(n\right)\right)}{f\left(n\right)}$

Therefore (2) holds for sufficiently large $n$, i.e,

$\displaystyle\;\;\;\;\;\;\;\;\;\;\frac{f\left(n\right)}{\ln\left(f\left(n\right)\right)}\geq\frac{400\left(1+\frac{\delta}{m}\right)\left(1+\epsilon\right)\tau_{\text{mix}}\left(\mathcal{M}+\lambda_{1}\right)}{\ln\left(2\right)\frac{\delta}{m}}$

This is satisfied if

$\displaystyle\frac{n}{\ln\left(f\left(n\right)\right)}\geq\frac{400\tau_{\text{mix}}\left(1+\frac{\delta}{m}\right)\left(1+\epsilon\right)}{\ln\left(2\right)}\frac{\left(\mathcal{M}+\lambda_{1}\right)\alpha}{\left(\lambda_{1}-\lambda_{2}\right)\frac{\delta}{m}}$
(70)

From Lemma S.12, we have

$\displaystyle\frac{\beta}{\ln\left(f\left(0\right)\right)}$
$\displaystyle\geq\frac{600\tau_{\text{mix}}\left(1+2\epsilon\right)^{2}\left(\mathcal{M}+\lambda_{1}\right)^{2}\alpha^{2}}{\left(\lambda_{1}-\lambda_{2}\right)^{2}\ln\left(1+\frac{\delta}{m}\right)}\stackrel{{\scriptstyle\left(i\right)}}{{\geq}}\frac{400\tau_{\text{mix}}\left(1+\frac{\delta}{m}\right)\left(1+\epsilon\right)}{\ln\left(2\right)}\frac{\left(\mathcal{M}+\lambda_{1}\right)\alpha}{\left(\lambda_{1}-\lambda_{2}\right)\frac{\delta}{m}}$

where $\left(i\right)$ follows since
$\frac{\mathcal{M}+\lambda_{1}}{\lambda_{1}-\lambda_{2}}>1,\alpha>2$ and
$\ln\left(1+x\right)\leq x\;\forall x$. Therefore,
$\frac{n}{\ln\left(f\left(n\right)\right)}>\frac{\beta}{\ln\left(f\left(0\right)\right)}$
suffices. Further, we note that (2) implies (1) for m = 200, $\delta\leq 1$.
Therefore, the condition on $n$ is sufficient for both results. Hence proved.
∎

######  Lemma S.14.

Let

$\displaystyle u$ $\displaystyle:=\min\left\\{i:i\in[n],i-k_{i}\geq
0\right\\}$

where $k_{i}$ is defined in Lemma S.12. Then,

$\displaystyle u\leq\lfloor\beta\rfloor\leq\beta$

###### Proof.

Using the definition of $k_{i}$ mentioned in Lemma S.12, we have

$\displaystyle k_{i}:=\tau_{\text{mix}}\left(\eta_{i}^{2}\right)$
$\displaystyle\leq\frac{2\tau_{\text{mix}}}{\ln\left(2\right)}\ln\left(\frac{1}{\eta_{i}^{2}}\right)$
$\displaystyle=\frac{4\tau_{\text{mix}}}{\ln\left(2\right)}\ln\left(\frac{\left(\lambda_{1}-\lambda_{2}\right)\left(\beta+i\right)}{\alpha}\right)$

Therefore,

$\displaystyle\lfloor\beta\rfloor-k_{\lfloor\beta\rfloor}$
$\displaystyle\geq\lfloor\beta\rfloor-\frac{4\tau_{\text{mix}}}{\ln\left(2\right)}\ln\left(\frac{\beta+\lfloor\beta\rfloor}{\frac{\alpha}{\lambda_{1}-\lambda_{2}}}\right)$
$\displaystyle\geq\frac{\beta}{2}-\frac{4\tau_{\text{mix}}}{\ln\left(2\right)}\ln\left(\frac{2\beta}{\frac{\alpha}{\lambda_{1}-\lambda_{2}}}\right)\text{
since }\beta>1$
$\displaystyle=\beta\left[\frac{1}{2}-\frac{4\tau_{\text{mix}}}{\ln\left(2\right)}\frac{\ln\left(2f\left(0\right)\right)}{\beta}\right],\text{
where }f\left(.\right)\text{ is defined in Lemma
}\ref{lemma:learning_rate_schedule}$

Now, from Lemma S.12, we know that $f\left(0\right)>e$. Therefore,
$\ln\left(2f\left(0\right)\right)\leq 2\ln\left(f\left(0\right)\right)$. Then,

$\displaystyle\lfloor\beta\rfloor-k_{\lfloor\beta\rfloor}$
$\displaystyle\geq\beta\left[\frac{1}{2}-\frac{8\tau_{\text{mix}}}{\ln\left(2\right)}\frac{\ln\left(f\left(0\right)\right)}{\beta}\right]$

Again, from the conditions in Lemma S.12, we know that

$\displaystyle\frac{\ln\left(f\left(0\right)\right)}{\beta}\leq\frac{\epsilon}{6\tau_{\text{mix}}}\frac{\lambda_{1}-\lambda_{2}}{\left(\mathcal{M}+\lambda_{1}\right)\alpha}\leq\frac{1}{120\tau_{\text{mix}}}\text{
since }\alpha>2,\frac{\lambda_{1}-\lambda_{2}}{\mathcal{M}+\lambda_{1}}\leq
1,\epsilon\leq\frac{1}{100}$

Therefore,

$\displaystyle\lfloor\beta\rfloor-
k_{\lfloor\beta\rfloor}\geq\beta\left(\frac{1}{2}-\frac{8}{120\ln\left(2\right)}\right)\geq
0$

Hence proved. ∎

####  S.5.1.1 Numerator

Using Theorem 3 and Markov’s Inequality, we have with probability atleast
$\left(1-\delta\right)$

$\displaystyle\operatorname{Tr}\left(V_{\perp}^{T}B_{n}B_{n}^{T}V_{\perp}\right)\leq$
$\displaystyle\;\;\;\;1.05\frac{\exp\left(\sum_{i=u+1}^{n}2\eta_{i}\lambda_{2}+\overline{\mathcal{V}_{k,i}}\eta_{i-k_{i}}^{2}\right)}{\delta}\left(d+\sum_{i=u+1}^{n}\left(\mathcal{V}^{\prime}+\xi_{k,i}\right)C_{k,i}^{\prime}\eta_{i-k_{i}}^{2}\exp\left(\sum_{j=u+1}^{i}2\eta_{j}\left(\lambda_{1}-\lambda_{2}\right)\right)\right)$

####  S.5.1.2 Denominator

Using Chebyshev’s Inequality we have, with probability atleast
$\left(1-\delta\right)$

$\displaystyle v_{1}^{T}B_{n}B_{n}^{T}v_{1}$
$\displaystyle\geq\mathbb{E}\left[v_{1}^{T}B_{n}B_{n}^{T}v_{1}\right]\left(1-\sqrt{\frac{1}{\delta}}\sqrt{\frac{\mathbb{E}\left[\left(v_{1}^{T}B_{n}B_{n}^{T}v_{1}\right)^{2}\right]}{\mathbb{E}\left[v_{1}^{T}B_{n}B_{n}^{T}v_{1}\right]^{2}}-1}\right)$
(71)

Let
$r:=2\left(1+\epsilon\right)\eta_{n}k_{n}\left(\mathcal{M}+\lambda_{1}\right)\leq\frac{1}{10}$.
Using Theorem 3, we have

$\displaystyle\mathbb{E}\left[\left(v_{1}^{T}B_{n}B_{n}^{T}v_{1}\right)^{2}\right]\leq\left(1+r\right)^{4}\exp\left(\sum_{i=1}^{n-k_{n}}4\eta_{i}\lambda_{1}+\sum_{i=1}^{n-k_{n}}\eta_{i}^{2}\zeta_{k,t}\right)$

Using Theorem 4, we have

$\displaystyle\mathbb{E}\left[v_{1}^{T}B_{n,1}B_{n,1}^{T}v_{1}\right]\geq\exp\left(2\lambda_{1}\sum_{i=1}^{n-k_{n}}\eta_{i}-4\lambda_{1}^{2}\sum_{i=1}^{n-k_{n}}\eta_{i}^{2}\right)\left[1-\left(2r+3\left(1+r\right)^{2}\sum_{t=1}^{n-k_{n}}W_{k,t}\eta_{t}^{2}\exp\left(\sum_{i=t+1}^{n-k_{n}}\eta_{i}^{2}\overline{\mathcal{V}_{k,i}}\right)\right)\right]$

Let

$\displaystyle
s:=3\left(1+r\right)^{2}\sum_{t=1}^{n-k_{n}}W_{k,t}\eta_{t}^{2}\exp\left(\sum_{i=t+1}^{n-k_{n}}\eta_{i}^{2}\overline{\mathcal{V}_{k,i}}\right)$

Then,

$\displaystyle\frac{\mathbb{E}\left[\left(v_{1}^{T}B_{n}B_{n}^{T}v_{1}\right)^{2}\right]}{\mathbb{E}\left[v_{1}^{T}B_{n}B_{n}^{T}v_{1}\right]^{2}}$
$\displaystyle\leq\frac{\left(1+r\right)^{4}}{\left(1-2r-s\right)^{2}}\exp\left(\sum_{i=1}^{n-k_{n}}\eta_{i}^{2}\left(\zeta_{k,i}+4\lambda_{1}^{2}\right)\right)$

By Lemma S.13, we have that

$\displaystyle 2r+s\leq\frac{1}{2}.$ (72)

Then, using

$\displaystyle\frac{1}{\left(1-x\right)^{2}}\leq 1+6x\text{ for
}x\in\left[0,\frac{1}{2}\right]\text{ and, }\left(1+x\right)^{4}\leq
1+5x\text{ for }x\in\left[0,\frac{1}{10}\right]$

we have,

$\displaystyle\frac{\mathbb{E}\left[\left(v_{1}^{T}B_{n}B_{n}^{T}v_{1}\right)^{2}\right]}{\mathbb{E}\left[v_{1}^{T}B_{n}B_{n}^{T}v_{1}\right]^{2}}$
$\displaystyle\leq\left(1+5r\right)\left(1+12r+6s\right)\exp\left(\sum_{i=1}^{n-k_{n}}\eta_{i}^{2}\left(\zeta_{k,i}+4\lambda_{1}^{2}\right)\right)$
$\displaystyle\leq\left(1+17r+6s+60r^{2}+30rs\right)\exp\left(\sum_{i=1}^{n-k_{n}}\eta_{i}^{2}\left(\zeta_{k,i}+4\lambda_{1}^{2}\right)\right)$
$\displaystyle\leq\left(1+22r+12s\right)\exp\left(\sum_{i=1}^{n-k_{n}}\eta_{i}^{2}\left(\zeta_{k,i}+4\lambda_{1}^{2}\right)\right)\text{
since }r\leq\frac{1}{10}$

By Lemma S.12-(3), we have that

$\displaystyle\exp\left(\sum_{i=1}^{n-k_{n}}\eta_{i}^{2}\left(\zeta_{k,i}+4\lambda_{1}^{2}\right)\right)\leq
1+\frac{\delta}{m}$ (73)

By 68, we have that

$\displaystyle 12s$
$\displaystyle\leq\frac{48(1+r)^{2}}{100}\left(1+\frac{\delta}{m}\right)^{2}\ln\left(1+\frac{\delta}{m}\right)$
$\displaystyle\leq\frac{3}{5}\left(1+\frac{\delta}{m}\right)^{2}\ln\left(1+\frac{\delta}{m}\right)\text{
since }r\leq\frac{1}{10}$ (74)

By Lemma S.13, we have that

$\displaystyle
r=2\left(1+\epsilon\right)\eta_{n}k_{n}\left(\mathcal{M}+\lambda_{1}\right)<\frac{1}{50}\frac{\delta/m}{1+\delta/m}$
(75)

Then,

$\displaystyle\frac{\mathbb{E}\left[\left(v_{1}^{T}B_{n}B_{n}^{T}v_{1}\right)^{2}\right]}{\mathbb{E}\left[v_{1}^{T}B_{n}B_{n}^{T}v_{1}\right]^{2}}$
$\displaystyle\leq\left(1+22r+12s\right)\left(1+\frac{\delta}{m}\right)$
$\displaystyle=1+\frac{\delta}{m}+22r\left(1+\frac{\delta}{m}\right)+12s\left(1+\frac{\delta}{m}\right)$
$\displaystyle\leq
1+\frac{\delta}{m}+\frac{22}{50}\frac{\delta}{m}+\frac{3}{5}\left(1+\frac{\delta}{m}\right)^{3}\ln\left(1+\frac{\delta}{m}\right)$
$\displaystyle\leq
1+\frac{\delta}{m}+\frac{22}{50}\frac{\delta}{m}+\frac{7}{10}\ln\left(1+\frac{\delta}{m}\right)\text{
since }\delta\leq 1,m=200$ $\displaystyle\leq
1+\frac{\delta}{m}+\frac{22}{50}\frac{\delta}{m}+\frac{7}{10}\frac{\delta}{m}\text{
since }\forall x,\;\ln\left(1+x\right)\leq x$ $\displaystyle\leq
1+3\frac{\delta}{m}$

Then setting $m=200$, from 71 we have

$\displaystyle v_{1}^{T}B_{n}B_{n}^{T}v_{1}$
$\displaystyle\geq\exp\left(\sum_{i=1}^{n-k_{n}}2\eta_{i}\lambda_{1}-4\eta_{i}^{2}\lambda_{1}^{2}\right)\left(1-2r-s\right)\left(1-\sqrt{\frac{1}{\delta}}\sqrt{\frac{3\delta}{m}}\right)$
$\displaystyle\geq\exp\left(\sum_{i=1}^{n-k_{n}}2\eta_{i}\lambda_{1}-4\eta_{i}^{2}\lambda_{1}^{2}\right)\left(1-\frac{1}{25}\frac{\delta/m}{1+\delta/m}-\frac{1}{20}\left(1+\frac{\delta}{m}\right)^{2}\ln\left(1+\frac{\delta}{m}\right)\right)\left(1-\sqrt{\frac{3}{m}}\right)\text{
using }\ref{eq:epsilon_delta_bound_1},\ref{assumption:r_delta_condition}$
$\displaystyle\geq\frac{5}{6}\exp\left(\sum_{i=1}^{n-k_{n}}2\eta_{i}\lambda_{1}-4\eta_{i}^{2}\lambda_{1}^{2}\right)\text{
since }\delta\leq 1\text{ and }m=200$

####  S.5.1.3 Fraction

Now that we have established this result let’s calculate the fraction. Let the
step-sizes be set according to Lemma S.12. Define

$\displaystyle\mathcal{S}:=\exp\left(\sum_{i=u+1}^{n}\overline{\mathcal{V}_{k,i}}\eta_{i-k_{i}}^{2}+\sum_{i=1}^{n-k_{n}}4\lambda_{1}^{2}\eta_{i}^{2}\right)$
$\displaystyle
Q_{u}:=\exp\left(2\lambda_{1}\left(\sum_{j=1}^{u}\eta_{j}-\sum_{j=n-k_{n}+1}^{n}\eta_{j}\right)\right)$
$\displaystyle\mathcal{R}_{k,t}:=\frac{\exp\left(\sum_{j=1}^{t-u}\eta_{j}^{2}\left(\overline{\mathcal{V}_{k,j}}-\overline{\mathcal{V}_{k,j+u}}\right)\right)\exp\left(2\lambda_{1}\sum_{j=n-k_{n}+1}^{n}\eta_{j}\right)}{\exp\left(2\lambda_{1}\sum_{j=1}^{u}\eta_{t-u+j}\right)}$

Then, recall that

$\displaystyle u$ $\displaystyle:=\min\left\\{i:i\in[n],i-k_{i}\geq
0\right\\}$ $\displaystyle\xi_{k,t}$
$\displaystyle:=6\eta_{t-k_{t}}\mathcal{M}\left[1+3k_{t+1}^{2}\left(\mathcal{M}+\lambda_{1}\right)^{2}\right]$
$\displaystyle\mathcal{V}^{\prime}$
$\displaystyle:=\left(\frac{1+\left(3+4\epsilon\right)|\lambda_{2}\left(P\right)|}{1-\left|\lambda_{2}\left(P\right)\right|}\right)\mathcal{V}$
$\displaystyle\overline{\mathcal{V}_{k,t}}$
$\displaystyle:=\mathcal{V}^{\prime}+\lambda_{1}^{2}+\xi_{k,t}$ $\displaystyle
C_{k,t}^{\prime}$
$\displaystyle:=\exp\left(2\lambda_{1}\sum_{j=1}^{u}\left(\eta_{j}-\eta_{t-u+j}\right)+\sum_{j=1}^{t-u}\eta_{j}^{2}\left(\overline{\mathcal{V}_{k,j}}-\overline{\mathcal{V}_{k,j+u}}\right)\right)=Q_{u}\mathcal{R}_{k,t}$

Therefore,

$\displaystyle\frac{\operatorname{Tr}\left(V_{\perp}^{T}B_{n}B_{n}^{T}V_{\perp}\right)}{v_{1}^{T}B_{n}B_{n}^{T}v_{1}}$
$\displaystyle\leq\frac{1.3}{\delta}\frac{\exp\left(\sum_{i=u+1}^{n}2\eta_{i}\lambda_{2}+\overline{\mathcal{V}_{k,i}}\eta_{i-k_{i}}^{2}\right)}{\exp\left(\sum_{i=1}^{n-k_{n}}2\eta_{i}\lambda_{1}-4\eta_{i}^{2}\lambda_{1}^{2}\right)}\left(d+\sum_{i=u+1}^{n}\left(\mathcal{V}^{\prime}+\xi_{k,i}\right)C_{k,i}^{\prime}\eta_{i-k_{i}}^{2}\exp\left(\sum_{j=u+1}^{i}2\eta_{j}\left(\lambda_{1}-\lambda_{2}\right)\right)\right)$
$\displaystyle\leq\frac{1.3}{\delta}\frac{\mathcal{S}}{Q_{u}}\exp\left(\sum_{i=u+1}^{n}2\eta_{i}\left(\lambda_{2}-\lambda_{1}\right)\right)\left(d+\sum_{i=u+1}^{n}\left(\mathcal{V}^{\prime}+\xi_{k,i}\right)C_{k,i}^{\prime}\eta_{i-k_{i}}^{2}\exp\left(\sum_{j=u+1}^{i}2\eta_{j}\left(\lambda_{1}-\lambda_{2}\right)\right)\right)$
$\displaystyle\leq\frac{1.3}{\delta}\mathcal{S}\left(\underbrace{\frac{d\exp\left(\sum_{i=u+1}^{n}2\eta_{i}\left(\lambda_{2}-\lambda_{1}\right)\right)}{Q_{u}}}_{X_{1}}+\underbrace{\sum_{i=u+1}^{n}\left(\mathcal{V}^{\prime}+\xi_{k,i}\right)\mathcal{R}_{k,i}\eta_{i-k_{i}}^{2}\exp\left(-\sum_{j=i+1}^{n}2\eta_{j}\left(\lambda_{1}-\lambda_{2}\right)\right)}_{X_{2}}\right)$
(76)

For $X_{1}$, we have

$\displaystyle X_{1}$
$\displaystyle\leq\frac{d\exp\left(\sum_{i=u+1}^{n}2\eta_{i}\left(\lambda_{2}-\lambda_{1}\right)\right)}{Q_{u}}$
$\displaystyle=\frac{d\exp\left(\sum_{i=u+1}^{n}2\eta_{i}\left(\lambda_{2}-\lambda_{1}\right)\right)}{\exp\left(2\lambda_{1}\left(\sum_{j=1}^{u}\eta_{j}-\sum_{j=n-k_{n}+1}^{n}\eta_{j}\right)\right)}$
$\displaystyle\leq\frac{d\exp\left(\sum_{i=u+1}^{n}2\eta_{i}\left(\lambda_{2}-\lambda_{1}\right)\right)}{\exp\left(-2\lambda_{1}\left(\sum_{j=n-k_{n}+1}^{n}\eta_{j}\right)\right)}$
$\displaystyle\leq
d\exp\left(\sum_{i=u+1}^{n}2\eta_{i}\left(\lambda_{2}-\lambda_{1}\right)\right)\exp\left(2\lambda_{1}\left(\sum_{j=n-k_{n}+1}^{n}\eta_{j}\right)\right)$

Note that

$\displaystyle\exp\left(2\lambda_{1}\sum_{j=n-k_{n}+1}^{n}\eta_{j}\right)$
$\displaystyle\leq\exp\left(2\left(1+2\epsilon\right)\lambda_{1}k_{n}\eta_{n-k_{n}+1}\right)\text{
using monotonicity of }\eta_{i}$
$\displaystyle\leq\exp\left(4\left(1+2\epsilon\right)\lambda_{1}k_{n}\eta_{n}\right)\text{
using slow-decay of }\eta_{i}$ $\displaystyle\leq 1+2\frac{\delta}{m}\text{
using Lemma }\ref{lemma:additional_assumptions}\text{ along with }e^{x}\leq
1+x+x^{2}\text{ for }x\in\left(0,1\right)$

Therefore, using 40

$\displaystyle X_{1}$ $\displaystyle\leq
d\left(1+\frac{2\delta}{m}\right)\left(\frac{\beta+u}{n}\right)^{2\alpha}$

Next, for $X_{2}$, we first have

$\displaystyle\mathcal{R}_{k,t}$
$\displaystyle:=\frac{\exp\left(\sum_{j=1}^{t-u}\eta_{j}^{2}\left(\overline{\mathcal{V}_{k,j}}-\overline{\mathcal{V}_{k,j+u}}\right)\right)\exp\left(2\lambda_{1}\sum_{j=n-k_{n}+1}^{n}\eta_{j}\right)}{\exp\left(2\lambda_{1}\sum_{j=1}^{u}\eta_{t-u+j}\right)}$
$\displaystyle\leq\exp\left(\sum_{j=1}^{t-u}\eta_{j}^{2}\overline{\mathcal{V}_{k,j}}\right)\exp\left(2\lambda_{1}\sum_{j=n-k_{n}+1}^{n}\eta_{j}\right)$
$\displaystyle\leq\left(1+\frac{2\delta}{m}\right)^{2}\text{ using Lemmas
}\ref{lemma:learning_rate_schedule}-(3),\ref{lemma:additional_assumptions}\text{
and }e^{x}\leq 1+x+x^{2}\text{ for }x\in\left(0,1\right)$

Now, using S.12-(4) we have,

$\displaystyle\sum_{i=1}^{n}\overline{\mathcal{V}_{k,i}}\eta_{i-k_{i}}^{2}\exp\left(-\sum_{j=i+1}^{n}2\eta_{j}\left(\lambda_{1}-\lambda_{2}\right)\right)\leq$
$\displaystyle\;\;\left(\frac{2\left(1+10\epsilon\right)\alpha^{2}}{2\alpha-1}\right)\frac{\mathcal{V}^{\prime}}{\left(\lambda_{1}-\lambda_{2}\right)^{2}}\frac{1}{n}+\left(\frac{800\left(1+10\epsilon\right)\alpha^{3}}{\left(\alpha-1\right)}\right)\frac{\mathcal{M}\left(\mathcal{M}+\lambda_{1}\right)^{2}\tau_{\text{mix}}^{2}}{\left(\lambda_{1}-\lambda_{2}\right)^{3}}\frac{\ln^{2}\left(\frac{\left(\beta+n\right)\left(\lambda_{1}-\lambda_{2}\right)}{\alpha}\right)}{n^{2}}$

Then,

$\displaystyle X_{2}$
$\displaystyle\leq\left(1+\frac{2\delta}{m}\right)^{2}\left[\underbrace{\left(\frac{2\left(1+10\epsilon\right)\alpha^{2}}{2\alpha-1}\right)}_{C_{1}}\frac{\mathcal{V}^{\prime}}{\left(\lambda_{1}-\lambda_{2}\right)^{2}}\frac{1}{n}+\underbrace{\left(\frac{24\left(1+10\epsilon\right)\alpha^{3}}{\left(\alpha-1\right)}\right)}_{C_{2}}\frac{\mathcal{M}\left(\mathcal{M}+\lambda_{1}\right)^{2}}{\left(\lambda_{1}-\lambda_{2}\right)^{3}}\frac{k_{n}^{2}}{n^{2}}\right]$

Therefore substituting in 76,

$\displaystyle\frac{\operatorname{Tr}\left(V_{\perp}^{T}B_{n}B_{n}^{T}V_{\perp}\right)}{v_{1}^{T}B_{n}B_{n}^{T}v_{1}}\leq\frac{1.3\mathcal{S}}{\delta}\left(1+\frac{2\delta}{m}\right)^{2}\left[d\left(\frac{\beta+u}{n}\right)^{2\alpha}+\frac{C_{1}\mathcal{V}^{\prime}}{\left(\lambda_{1}-\lambda_{2}\right)^{2}}\frac{1}{n}+\frac{C_{2}\mathcal{M}\left(\mathcal{M}+\lambda_{1}\right)^{2}}{\left(\lambda_{1}-\lambda_{2}\right)^{3}}\frac{k_{n}^{2}}{n^{2}}\right]$
(77)

###### Proof of Theorem 1.

To complete our proof, we bound $\mathcal{S}$ to simplify 77. We note that
under the learning rate schedule presented in Lemma S.12-(3),

$\displaystyle\mathcal{S}$ $\displaystyle\leq\left(1+\frac{\delta}{m}\right)$

Therefore,

$\displaystyle\frac{\operatorname{Tr}\left(V_{\perp}^{T}B_{n}B_{n}^{T}V_{\perp}\right)}{v_{1}^{T}B_{n}B_{n}^{T}v_{1}}$
$\displaystyle\leq\frac{1.3}{\delta}\left(1+\frac{2\delta}{m}\right)^{3}\left[d\left(\frac{\beta+u}{n}\right)^{2\alpha}+\frac{C_{1}\mathcal{V}^{\prime}}{\left(\lambda_{1}-\lambda_{2}\right)^{2}}\frac{1}{n}+\frac{C_{2}\mathcal{M}\left(\mathcal{M}+\lambda_{1}\right)^{2}}{\left(\lambda_{1}-\lambda_{2}\right)^{3}}\frac{k_{n}^{2}}{n^{2}}\right]$
$\displaystyle\leq\frac{1.4}{\delta}\left[d\left(\frac{\beta+u}{n}\right)^{2\alpha}+\frac{C_{1}\mathcal{V}^{\prime}}{\left(\lambda_{1}-\lambda_{2}\right)^{2}}\frac{1}{n}+\frac{C_{2}\mathcal{M}\left(\mathcal{M}+\lambda_{1}\right)^{2}}{\left(\lambda_{1}-\lambda_{2}\right)^{3}}\frac{k_{n}^{2}}{n^{2}}\right]$

Using lemma S.14, we have that $u\leq\beta$. Then, using Lemma 3.1 from [14]
completes our proof. ∎

###  S.5.2 Proof of Corollary 1

###### Proof of Corollary 1.

We note that the downsampled data stream can be considered to be drawn from a
Markov chain with transition kernel $P^{k}\left(.,.\right)$ since each data-
point is $k$ steps away from the previous one. For sufficiently large $k$,
this implies that the mixing time of this chain is $\Theta\left(1\right)$.

Therefore, as noted in the theorem statement, we plug in the modified
parameters in the bound proved for Theorem 1.

Next, we note that for the transition kernel $P^{k}\left(.,.\right)$, the
second-largest absolute eigenvalue is given as
$\left|\lambda_{2}\left(P\right)\right|^{k}$. Therefore, for
$k:=\tau_{\text{mix}}\left(\gamma\eta_{n}^{2}\right)\leq\frac{2\tau_{\text{mix}}}{\ln\left(2\right)}\ln\left(\frac{1}{\gamma\eta_{n}^{2}}\right)\leq
C\frac{1}{1-\left|\lambda_{2}\left(P\right)\right|}\ln\left(n\right),C>1$,
using standard bounds on mixing times for reversible Markov chains (see for
example, [19]). Consider the function $f\left(x\right):=x^{\frac{1}{1-x}}$ for
$x\in\left(0,1\right)$. Then,

$\displaystyle f^{\prime}\left(x\right)$
$\displaystyle=f\left(x\right)\left(\frac{1-x-x\ln\left(x\right)}{x\left(1-x\right)^{2}}\right)>0$

Therefore, $f\left(x\right)<\lim_{x\rightarrow
1}f\left(x\right)=\frac{1}{e}<1$. which implies
$\left|\lambda_{2}\left(P\right)\right|^{k}\stackrel{{\scriptstyle(i)}}{{\leq}}\left(\frac{1}{e}\right)^{C\ln\left(n\right)}<\frac{1}{e}$.
Here $(i)$ follows if $C>1,n>3$, which is true. Therefore,

$\displaystyle\mathcal{V}^{\prime}:=\left(\frac{1+\left(3+4\epsilon\right)|\lambda_{2}\left(P\right)|^{k}}{1-\left|\lambda_{2}\left(P\right)\right|^{k}}\right)\mathcal{V}\leq
5\mathcal{V}$

This also implies that mixing time for the new Markov chain for sub-sampled
data is $\Theta\left(1\right)$. The bound then follows by substituting $n$ to
be
$\frac{n}{k}=n_{k}=\Theta\left(\frac{n}{C\tau_{\text{mix}}\ln\left(n\right)}\right)$
and setting the $\tau_{\text{mix}}$ in the original expression of Theorem 1 to
a constant. ∎


* [CM23] Fabio Cavalletti and Andrea Mondino.  Optimal transport in lorentzian synthetic spaces, synthetic timelike ricci curvature lower bounds and applications, 2023.
  * [CRHK17] William J. Cunningham, David Rideout, James Halverson, and Dmitri Krioukov.  Exact geodesic distances in FLRW spacetimes.  Phys. Rev. D, 96:103538, 2017.
  * [Har82] S. Harris.  A triangle comparison theorem for lorentz manifolds.  Indiana Math. J., 31:298–308, 1982.
  * [Ket14] Christian Ketterer.  Cones over metric measure spaces and the maximal diameter theorem, 2014\.
  * [KS19] Michael Kunzinger and Clemens Sämann.  Lorentzian length spaces, 2019.
  * [LLS21] Christian Lange, Alexander Lytchak, and Clemens Sämann.  Lorentz meets Lipschitz.  Adv. Theor. Math. Phys., 25(8):2141–2170, 2021.
  * [Mye41] Sumner B Myers.  Riemannian manifolds with positive mean curvature.  1941\.
  * [O’n83] Barrett O’neill.  Semi-Riemannian geometry with applications to relativity.  Academic press, 1983.
  * [Sä15] Clemens Sämann.  Global hyperbolicity for spacetimes with continuous metrics.  Annales Henri Poincaré, 17(6):1429–1455, jul 2015.
  * [Tre11] Jan-Hendrik Treude.  Ricci curvature comparison in Riemannian and Lorentzian geometry.  PhD thesis, Universität Freiburg, 2011.