0x00 Preface

This article analyzes mini-batch SGD, following the Euclidean norm and stochastic gradient definitions from Part 11, and comparing them with the deterministic gradient descent from Part 22.

Let $\mathcal F_t$ denote the history before the $t$-th sampling round, using a fixed step size to update $w_{t+1}=w_t-\eta g_t$. $g_t$ is the average of $b$ new sample gradients, assuming

$$ \mathbb E[g_t\mid\mathcal F_t]=\nabla f(w_t),\qquad \mathbb E[\|g_t-\nabla f(w_t)\|^2\mid\mathcal F_t]\le\frac{\sigma^2}{b}. $$

Here $\sigma^2$ is the upper bound on the variance of single-sample noise; the reduction by a factor of $1/b$ relies on conditionally independent noise within the batch or zero cross-covariance.

One-step Descent

$L$-smoothness yields

$$ f(w_{t+1})\le f(w_t)-\eta\langle\nabla f(w_t),g_t\rangle +\frac{L\eta^2}{2}\|g_t\|^2. $$

First, take the expectation conditioned on $\mathcal F_t$, where $w_t$ is fixed:

$$ \mathbb E[f(w_{t+1})\mid\mathcal F_t] \le f(w_t)-\eta\left(1-\frac{L\eta}{2}\right)\|\nabla f(w_t)\|^2 +\frac{L\eta^2\sigma^2}{2b}. $$

Next, take the expectation over the history. If $0<\eta\le1/L$, we obtain the subsequent recursive relation shared by all:

$$ \mathbb E[f(w_{t+1})]\le\mathbb E[f(w_t)] -\frac\eta2\mathbb E\|\nabla f(w_t)\|^2 +\frac{L\eta^2\sigma^2}{2b}. $$

One cannot treat the random $f(w_t)$ or gradient as deterministic quantities in formulas involving unconditional expectations.

0x01 Smooth and Strongly Convex with Mini-batch SGD

defination

If $f$ is $L$-smooth, $\mu$-strongly convex, and an optimal solution exists, define
$$ \mathcal E_t=\mathbb E[f(w_t)]-f^*,\quad q=1-\eta\mu,\quad C_b=\frac{\eta L\sigma^2}{2\mu b}. $$
For $0<\eta\le1/L$, we have
$$ \mathcal E_T\le q^T\mathcal E_0+C_b(1-q^T) =C_b+q^T(\mathcal E_0-C_b). $$

Proof: By the PL condition $\Vert\nabla f(w_t)\Vert^2\ge2\mu(f(w_t)-f^{\ast})$, a single step of descent becomes

$$ \mathcal E_{t+1}\le(1-\eta\mu)\mathcal E_t+\frac{L\eta^2\sigma^2}{2b}. $$

Since $0\le q<1$, expanding the recursion and summing the geometric series yields

$$ \mathcal E_T\le q^T\mathcal E_0 +\frac{L\eta^2\sigma^2}{2b}\sum_{s=0}^{T-1}q^s =q^T\mathcal E_0+C_b(1-q^T). $$

What Does the Bound Guarantee?

Under a fixed step size, the transient term in the bound decreases at a geometric rate, but typically only guarantees $\limsup_T\mathcal E_T\le C_b$. This is an upper bound on the error, not the actual error the algorithm necessarily achieves, nor a guarantee of linear convergence to the exact optimal solution.

If $0<q<1$ and $\mathcal E_0>\epsilon>C_b$, the required number of iterations is

$$ T\ge\left\lceil \frac{\log((\mathcal E_0-C_b)/(\epsilon-C_b))}{-\log q} \right\rceil. $$

If $\epsilon\le C_b$, this upper bound cannot guarantee reaching the target. One can reduce the step size, increase the batch size, or use a decaying step size scheme with applicable conditions. When $\sigma^2=0$, the results of deterministic GD are recovered; when $q=0$, directly use the recursion without calculating $\log0$.

0x02 Smooth Non-convex with Mini-batch SGD

defination

Assume $f$ is $L$-smooth and has a finite lower bound $f_{\inf}$, and the stochastic gradients satisfy the above conditions. For $0<\eta\le1/L$ and $T\ge1$,
$$ \frac1T\sum_{t=0}^{T-1}\mathbb E\|\nabla f(w_t)\|^2 \le\frac{2(f(w_0)-f_{\inf})}{\eta T}+\frac{L\eta\sigma^2}{b}, $$
Here we assume the starting point $w_0$ is deterministic; for a random starting point, replace $f(w_0)$ with its expectation.

Proof: Summing the one-step descent from $t=0$ to $T-1$ yields

$$ \frac\eta2\sum_{t=0}^{T-1}\mathbb E\|\nabla f(w_t)\|^2 \le f(w_0)-\mathbb E[f(w_T)]+\frac{TL\eta^2\sigma^2}{2b}. $$

Using $f(w_T)\ge f_{\inf}$, then dividing by $\eta T/2$ gives the conclusion. This summation starts from $w_0$, so the telescoping endpoints are $f(w_0)$ and $f(w_T)$.

Step Size and Output

If $R$ are independent and uniformly distributed over $\lbrace 0,\ldots,T-1\rbrace$, the expected squared gradient of the random output $w_R$ equals the above average. This conclusion cannot be directly converted into a guarantee for the final point $w_T$, nor does it guarantee reaching the global optimum.

Denote $A=f(w_0)-f_{\inf}>0$. When $\sigma^2>0$, choose for a given run length $T$

$$ \eta=\min\left\{\frac1L,\sqrt{\frac{2Ab}{L\sigma^2T}}\right\}. $$

When the second term does not exceed $1/L$, the bound on the average squared gradient is

$$ 2\sqrt{\frac{2AL\sigma^2}{bT}}. $$

This is a fixed step size chosen based on a predetermined run length, not replacing the current index with $T$ at every step. It demonstrates the $O(1/\sqrt{bT})$ behavior within the corresponding range; the step size upper limit constrains this scaling. Without noise, taking $\eta=1/L$ yields $2LA/T$.

Reference

Sources: 3 4.

  1. Part 1 ↩︎

  2. Part 2 ↩︎

  3. Bottou, L., Curtis, F. E. and Nocedal, J., Optimization Methods for Large-Scale Machine Learning, Section 4, especially Theorems 4.6 and 4.8. ↩︎

  4. Joshi, G., Optimization Algorithms for Distributed Machine Learning, Springer. ↩︎