of samples (or sample indices) to calculate the stochastic gradient. We denote by $\calF_t^b$ the filtration of information before calculating the stochastic gradient in the $t$-th iteration, i.e. $\calF_t^b \triangleq \sth{w_0,\calB_0^b, \ldots, \calB_{t-1}^b}$.

Linear Regression {#subsec:linearRegression}
-----------------

In this subsection, we discuss the dynamics of SGD applied in linear regression. Given data points $(x_1, y_1), \cdots, (x_n, y_n)$, where $x_i \in \mathbb{R}^{p}$ and $y_i \in \mathbb{R}$, we define the loss function to be $$\label{eq:empiricalLoss}
        L(w) = \frac{1}{n} \sum_{i=1}^n L_i(w) = \frac{1}{n} \sum_{i=1}^n \frac{1}{2} \pth{w^\transp x_i - y_i}^2,$$ where $w \in \mathbb{R}^{p}$ are the model parameters. We consider minimizing by mini-batch SGD. Note that the bias term in the general linear regression models is omitted, however, adding the bias term does not change the result of this section. Formally, we first choose a mini-batch size $b$ and initial weights $w_0$. In each iteration $t$, we sample $\calB_t^b$, a subset of $[n]$ with cardinality $b$, and update the parameters by $$w_{t+1}^b = w_t^b - \alpha_t g_t^b,$$ where $g_t^b = \frac{1}{b} \sum_{i\in \calB_t^b} \grad L_i\pth{w_t^b}.$ We first show the relationship between the variance of stochastic gradient $g_t^b$ and the full gradient $\grad L\pth{w_t^b}$ and sample-wise gradient $\grad L_i\pth{w_t^b}, i\in[n]$, derived by considering all 