possible choices of the mini-batch $\calB_t^b$. Readers should note that Lemma \[lemma:1\] actually holds for all models with $L_2$-loss, not merely linear regression (since in the proof we do not need to know the explicit form of $L_i(w)$).

\[lemma:1\] Let $c_b \triangleq \frac{n-b}{b(n-1)} \ge 0$. For any matrix $A \in \mathbb{R}^{p\times p}$ we have [$$\begin{aligned}
            \condvar{}{Ag_t^b}{\calF_t^b} &= \condexp{}{\norm{Ag_t^b}^2}{\calF_t^b} - \norm{A\grad L\pth{w_t^b}}^2 \\
            &= c_b \left(\frac{1}{n}\sum_{i=1}^n\norm{A\grad L_i\pth{w_t^b}}^2 - \norm{A\grad L\pth{w_t^b}}^2\right).
        \end{aligned}$$]{}

Lemma \[lemma:1\] provides a bridge to connect the norm and variance of $g_t^b$ with sample-wise gradients $\grad L_i\pth{w_t^b}, i\in [n]$. Therefore, if we can further discover the properties of $\grad L_i\pth{w_t^b}, i\in [n]$, we are able to calculate the variance of $g_t^b$. Lemma \[lemma:3\] addresses this problem by showing the relationship between any linear combination of $\grad L_i\pth{w_t^b}$ and $\grad L_i\pth{w_{t-1}^b}$.

\[lemma:3\] For any set of square matrices $\sth{A_1, \cdots, A_n} \in \mathbb{R}^{p \times p}$, if we denote $A = \sum_{i=1}^n A_i x_i x_i^\transp$, then we have [$$\begin{aligned}
                & \condexp{}{\norm{\sum_{i=1}^{n}  A_i \grad L_i  \pth{w_{t+1}^b}}^2}{\calF_0}  =
                \condexp{}{\norm{\sum_{i=1}^{n} B_i \grad L_i\pth{w_{t}^b}}^2}{\calF_0} \\
                &+ \frac{\alpha_t^2 c_b}{n^2} \sum_{k=1}^n \sum_{l=1}^n\condexp{}{\norm{\sum_{i=1}^{n} B_i^{kl} \grad L_i\pth{w_{t}^b}}^2}{\calF_0}.
            \end{aligned}$$]{} Here $B_i = A_i - \frac{\alpha_t}{n} A $; $B_i^{kl} = A$ if $i=k, i\neq l$, $B_i^{kl} = A$ if $i=l, i\neq 