\section{Rates without a condition modulus}
\subsection{Slow Rates}

From \Cref{eq:operator_norm_bound_movement}, we have that for any $t,s$,
\begin{align*}
\|\matY_s (z_{t}-z_{t-1})\|_2 &\le \eta \sqrt{\|\matY_s \Lambda_t^{-1/2}\|_{\op}^2 \| \nabla_t\|_{\Lambda_{t}^{\shortminus 1}}^2} \le \frac{\eta}{\lambda} \|\matY_s\|_{\op}\sqrt{ \| \nabla_t\|_{\Lambda_{t}^{\shortminus 1}}^2} \le \frac{\eta \radY^2}{\lambda}\sqrt{ \| \nabla_t\|_{\Lambda_{t}^{\shortminus  1}}^2},
\end{align*}
where we crudely bound $\|\matY_s \Lambda_t^{-1/2}\|_{\op}^2 = \|\matY_s \Lambda_t^{-1}\matY_s\|_{\op} \le \frac{1}{\lambda}\|\matY_s\|_{\op}^2$, as $\Lambda_t \succeq \lambda I$.  Therefore, 
\begin{align*}
	\normaltext{(movement cost)} &\le h \Leff \radG \sum_{s=1-h}^T \sum_{i=1}^{h-1} \|\matY_{s}(\matz_{s+i+1} - \matz_{s+i})\|_2 \cdot \I_{1 \le s+i \le t-1}\\
	&\le \frac{h \eta \radY^2 \Leff \radG}{\lambda}\sum_{s=1-h}^T \sum_{i=1}^{h-1} \sqrt{ \| \nabla_{s+i}\|_{\Lambda_{s+i}^{\shortminus 1}}^2} \cdot \I_{1 \le s+i \le t-1}\\
	&\le \frac{h^2 \eta \radY^2 \Leff \radG}{\lambda}\sum_{s=1}^T  \sqrt{ \| \nabla_{t}\|_{\Lambda_{t}^{\shortminus 1}}^2}.
	\end{align*}
	Now, by Cauchy-Schwartz, followed by \Cref{eq:X_move_contrib}, we bound
	\begin{align*}
	\sum_{t=1}^T  \sqrt{ \| \nabla_{t}\|_{\Lambda_{t}^{1/2}}^2} \le \sqrt{T} \cdot \frac{\eta }{2} \sum_{s=1}^T   \| \nabla_{t}\|_{\Lambda_{t}^{1/2}}^2 \le  d \Leff^2 \sqrt{T}\log\left(1 + \frac{T\radH^2}{\lambda}\right).
	\end{align*}
	Therefore,

\subsection{Fast Rates for Semi-Stochastic Sequences}

\begin{definition} We say that $(\matH_t)$ is a $(\kappa,\gamma)$-semi stochastic sequence if, for all $1 \le s \le t \le T$,
\begin{align*}
\sum_{i = s}^t \matH_t^\top \matH_t \succeq \kappa I - \gamma.
\end{align*}
\end{definition}
{"config": "arxiv", "file": "2006.05910/body/body_slow.tex"}