Stochastic gradients

Four examples occupy a table, and their gradients at the current setting are 1, 3, 5 and 7. The average is 4, and that average is the gradient of the objective over the table, because the table's loss is the average of the four rows' losses. Consult one example and you obtain 1 or 7. These four rows happen to point the same way as their average, so only the length is wrong; replace the last gradient with −7 and the average is still 0.5, while the fourth row alone points uphill.

On a table with a million rows the complete gradient requires a pass over everything, and one iteration is all it purchases. A minibatch is a small random sample from the table, and its average gradient is a stochastic gradient [S:43:107-107]. The sample is random, so the direction is random as well. On average it indicates the correct direction: the expected arrow — the average over every sample the scheme could draw — equals the complete gradient, and an estimate with that property is unbiased [S:46:24-24]. !A 250-step run on a synthetic table of 100 rows, with step 0.1. Left: one example per step wanders inside a band of half-width about 0.21 around the table mean 1.034; twenty examples per step narrows the band to about 0.05; the full batch settles on the mean without noise. Right: the equilibrium standard deviation falls as $1/\sqrt{b}$ at steps 0.1 and 0.4 for batches 1 to 20; at 100 every row is used and the sampling noise is zero. The paths are a seeded simulation of the section's model, not measurements. Status: synthetic.

When each iteration observes only one example, two consequences follow. The iteration is inexpensive, because it reads a few rows instead of all of them, and the iteration is noisy, because the sample average differs from the true average. The noise does not cancel within one iteration; it cancels across iterations, which is why the procedure remains effective.

The magnitude of the noise is determined by the batch. Write b for the number of examples in the batch and σ² for the variance of one example's gradient around the table average, the average squared deviation from that average. Independent samples are draws that do not influence one another. The average of b independent samples has variance σ²/b, so a batch of four possesses a quarter of the variance of a batch of one. That identity is the entire reason batch size matters [S:46:31-31].

Why is the average of the per-example gradients the gradient of the table objective? Because the table objective is the average of the per-example objectives, and the derivative of a sum equals the sum of the derivatives. Averaging is linear, so it commutes with differentiation: divide the sum of the four gradients by four and you have the gradient of the average loss. With the four gradients 1, 3, 5 and 7, the table gradient is (1 + 3 + 5 + 7)/4 = 4, and no additional measurement is required beyond the four the batch already performed.

The cost accounting is equally direct. A complete pass over a million rows supplies one exact iteration. A batch of a hundred rows supplies one noisy iteration for one ten-thousandth of the work, and its variance is smaller than a single row's by a factor of one hundred. The exchange is not gratuitous; it deliberately trades accuracy per iteration for the number of iterations you can afford. The next section conducts the exchange over an entire run.

Worked example: the four gradients 1, 3, 5 and 7 have average 4. Their deviations are −3, −1, 1 and 3, and the average of the squared deviations is (9 + 1 + 1 + 9)/4 = 5. So σ² = 5. A batch of two has variance 5/2 = 2.5, and a batch of four has 5/4 = 1.25. Four times the work purchases a quarter of the variance.

The second consequence is where the trajectory halts. With a fixed step, the noise continually injects error as rapidly as the step removes it, and the two balance at a noise floor. The gap settles at a ball around the minimum instead of reaching it [S:46:26-26]. After that point, additional iterations do not assist: the noise in the gradient prevents further progress [S:46:27-27].

The ball is not a failure of the machine. It is the honest conclusion of a run with a constant step, and its radius moves with the step and the batch. Halving the step halves the guaranteed gap; doubling the batch halves the variance and so halves the gap. Because strong convexity ties the gap to the squared distance, the radius — the typical distance from the minimiser — falls by √2 for each of those halvings, not by 2 [S:46:27-28].

The account rests on assumptions. An estimate is unbiased for the scheme that produced it; sample rows with unequal probabilities or clip a gradient — cap each of its entries at a fixed size — and the expected arrow is no longer the complete gradient. The variance bound is an assumption as well, and not every objective satisfies it. And the ball can be larger than the accuracy you require, in which case a constant step never delivers the answer no matter how long it proceeds.

The formal statement. Let the table hold $n$ rows, let $f_i$ be the loss on row $i$, and let the table loss be $F(\theta )=\frac{1}{n}{\sum }_{i=1}^n{f}_i(\theta )$. Draw a batch $B$ of size $b$ and form $\bar{g}=\frac{1}{b}{\sum }_{i\in B}\nabla f_i(\theta )$. If each row is drawn uniformly and independently, then

$$\mathbb{E}[\bar{g}]=\nabla F(\theta ),\mathrm{Var}(\bar{g})=\frac{{\sigma }^2}{b},$$

where ${\sigma }^2$ is the variance of one row's gradient around the table average [S:46:31-31]. The display says that the batch average is right on average, and that its spread shrinks in proportion to the batch size. The hypotheses are uniform sampling, independence, and a finite variance. Unbiasedness needs the first two; the variance identity needs all three.

The derivation. Averaging is linear and differentiation is linear, so the gradient of an average is the average of the gradients. For the variance, write $\bar{g}-\nabla F=\frac{1}{b}{\sum }_{i\in B}(\nabla f_i-\nabla F)$. The $b$ terms are independent and each has mean zero, so the variance of the sum is the sum of the variances. Dividing by $b^2$ leaves ${\sigma }^2/b$. The core's four gradients $1,3,5,7$ check the first identity: their average is $4$, and $4$ is the gradient of the table loss.

The edge case. The identity assumes independence, and independence assumes draws with replacement. A run that reads rows without replacement has a smaller variance, because the draws are negatively correlated: taking one row out changes the average of the rest. At a batch equal to the whole table the variance is zero, which is the core's own remark that a full pass gives one exact step. So the core's figure of $1.25$ describes drawing four times from the four rows with replacement. Read the same four rows once each and the variance is zero. The formula is right for the run it describes and wrong for the other one.

The noise floor. The precise version comes from the stochastic descent lemma. Under $L$-smoothness, $m$-strong convexity and a variance no larger than ${\sigma }^2$, a fixed step $\bar{\eta }\le 1/L$ gives

$$\mathbb{E}[F({\theta }_t)-F({\theta }^{\ast })]\le \frac{\bar{\eta }L{\sigma }^2}{2m}+{\left(1-\bar{\eta }m\right)}^{t-1}[F({\theta }_0)-F({\theta }^{\ast })].$$

The display says that the gap falls geometrically to a floor and then stops [S:46:26-26]. Halving the step halves the floor, and halving the variance does the same. The core's ball is that floor read as a distance: strong convexity gives $\frac{m}{2}\Vert \theta -{\theta }^{\ast }{\Vert }^2\le F(\theta )-F({\theta }^{\ast })$, so the radius is at most $\sqrt{2\mathrm{floor}/m}$. Halving the step or the variance therefore halves the floor and shrinks the radius by $\sqrt{2}$, not by $2$.

What the core hid. The core treated the batch as the only source of noise and the table as the truth. The formal version separates three objects: the risk over the world, the table average, and the batch average. Unbiasedness relates the third to the second, and nothing in the argument relates the second to the first. A batch gradient is an honest estimate of the table gradient and says nothing about a row the table does not contain.

Original sources. Stochastic approximation begins with Robbins and Monro in 1951 [S:82:136-136], and Prince gives the same date for stochastic gradient descent [S:74:105-105]. Bottou, Curtis and Nocedal state the unbiasedness condition and the variance bound that the analysis needs [S:46:24-24], and they record the variance reduction from a batch as a factor of $1/b$ [S:46:31-31]. Bubeck derives the same factor for a batch of $m$ draws [S:43:107-107].

An open question. A batch lowers the variance and raises the cost per step, and the field has not settled when the trade pays. Bottou and coauthors say that the theoretical benefit of mini-batching can appear ambiguous [S:46:30-30]. Bubeck shows that a batch helps only while its size stays below a threshold that grows with the number of oracle calls [S:43:107-107]. Evidence that would settle a proposal: a sweep of batch sizes at a fixed budget, total wall-clock to a fixed gap, the same hardware, and several seeds.

A frontier result. Variance reduction turns the sublinear rate into a linear one. The first methods of this family, SAG and SDCA, need $O((n+\kappa )\log (1/ϵ))$ gradient computations for a linear rate, which beats the sublinear count of plain stochastic gradient descent [S:43:108-108]. Here $n$ is the number of training examples, the number of summands in the table loss, and $\kappa =L/m$ is the condition number; the source writes $m$ for the count of summands, which this chapter has already used for the smallest curvature. SVRG reaches a linear rate with a more transparent mechanism. It keeps a snapshot of the parameters, computes the full gradient there once per epoch, and forms its direction from two stochastic gradients and that snapshot gradient [S:63:327-327]. The centring removes most of the noise without removing the cheap step, and the snapshot costs one full pass per epoch.

What to read next. Read Bottou sections 4.1 to 4.3 for the assumptions and the two lemmas [S:46:23-24]. Read Bubeck sections 6.2 and 6.3 for the batch algebra and SVRG [S:43:107-108]. Read Murphy sections 8.4.4 and 8.4.5 for averaging and variance reduction [S:63:327-327]. Then read Zhao section 6.4 for stochastic approximation as root finding [S:82:136-136].