\\
M_{t'}(\theta)& := &-\mathbb E_{\theta_0,t'}[\nabla^2_\theta \log p_{\theta,t'}(j|S_{t'})]  \nonumber  \\
& =  &\mathbb E_{\theta_0,t'}[v_{t'j}v_{t'j}^\top] - \{\mathbb E_{\theta_0,t'}v_{t'j}\}\{\mathbb E_{\theta,t'}v_{t'j}\}^\top
- \{\mathbb E_{\theta,t'}v_{t'j}\} \{\mathbb E_{\theta_0,t'}v_{t'j}\}^\top  +  \{\mathbb E_{\theta,t'}v_{t'j}\}\{\mathbb E_{\theta,t'}v_{t'j}\}^\top \nonumber\end{aligned}$$ where $\mathbb E_{\theta,t'}$ denotes the expectation evaluated under the law $j\sim p_{\theta,t'}(\cdot|S_{t'})$; that is, $p_{\theta,t'}(j|S_{t'}) =\exp\{v_{t'j}^\top\theta\}/(1+\sum_{k\in S_{t'}}\exp\{v_{t'j}^\top\theta\})$ for $j\in S_{t'}$ and $p_{\theta,t'}(j|S_{t'})=0$ for $j\notin S_{t'}$.

Suppose $\tau\leq 1/\sqrt{8\rho \nu^2K^2}$. Then there exists a universal constant $C>0$ such that with probability $1-O(T^{-1})$ the following holds uniformly over all $t=T_0,\cdots,T-1$: $$({\widehat}\theta_t-\theta_0)^\top I_t(\theta_0)({\widehat}\theta_t-\theta_0) \leq C\cdot d\log(\rho\nu TK).$$ \[lem:mle\]

For $\theta=\theta_0$, the expression of $M_{t'}(\theta)$ can be simplified as $M_{t'}(\theta_0) = \mathbb E_{\theta_0,t'}[v_{t'j}v_{t'j}^\top] - \{\mathbb E_{\theta_0,t'}v_{t'j}\}\{\mathbb E_{\theta_0,t'}v_{t'j}\}^\top$.

The complete proof of Lemma \[lem:mle\] is given in the supplementary material, and here we provide some high-level ideas behind our proof.

Our proof is inspired by the classical convergence rate analysis of M-estimators [@van1998asymptotic Sec. 5.8]. The main technical challenge is to provide *finite-sample* analysis of several components in the proof of [@van1998asymptotic Sec. 5.8].

In particular, for any $\theta\in\mathbb R^d$, consider $$F_{t}(\theta) := \sum_{t'\leq t}f_{t'}(\theta)\;\;\;\;\text{where}\;\;
f_{t'}(\theta) := \mathbb E_{\theta_0,t'}\left[\log\frac{p_{\theta,t'}(j|S_{t'})}{p_{\theta_0,t'}(j|S_{t'})}\right] = \sum_{j\in S_{t'}\cup\{0\}} p_{\theta_0,t'}(j|S_{t'})\log\frac{p_{\theta,t'}(j|S_{t'})}{p_{\theta_0,t'}(j|S_{t'})}$$ and its “sample” version $${\widehat}F_t(\theta) := \sum_{t'\leq t} {\widehat}f_{t'}(\theta)\;\;\;\;\text{where}\;\;
{\widehat}f_{t'}(\theta) := \log\frac{p_{\theta,t'}(i_{t'}|S_{t'})}{p_{\theta_0,t'}(i_{t'}|S_{t'})}.$$

It is easy to verify by definition that $F_t({\widehat}\theta_{t})\geq F_t(\theta_0)=0$ and ${\widehat}F_t({\widehat}\theta_{t})\leq  {\widehat}{F}_t(\theta_0)=0$, 