Gradient Descent & the LMS Rule¶
When the closed form is too expensive, you walk to the bottom of the loss bowl instead of jumping there. This page covers gradient descent and its three flavors, the self-correcting LMS (Widrow-Hoff) update that every flavor is built from, and the convexity argument (the Hessian and positive semi-definiteness) that guarantees the walk reaches the global minimum.
Rapid Recall
Gradient descent steps against the gradient, which points uphill, with the learning rate setting stride length. The only difference between batch, stochastic, and mini-batch is how many samples estimate the gradient before each step: all of them, one, or 32 to 256. The per-example update is the LMS rule, error times feature, which is self-correcting and only adjusts the features that drove the prediction. Linear regression's loss is exactly quadratic, so its Hessian \(2X^\top X\) is constant and positive semi-definite, which makes the loss convex and any stationary point the global minimum.
§1 Gradient descent and its three flavors¶
Instead of jumping to the bottom of the bowl, walk there. The gradient \(\nabla_{\mathbf w}L\) points uphill (steepest increase), so step against it:
\(\eta\) is the learning rate (stride length). Too small → crawls forever. Too large → oversteps the valley and bounces / diverges.
Foggy hillside. You are on a hill in fog (no closed form visible), but you can feel the slope at your feet. Step in the steepest downhill direction, reassess, repeat. \(\eta\) is your stride; too big and you leap clear over the valley onto the far slope.
The gradient for linear regression (vectorized)¶
With error vector \(\mathbf e = X\mathbf w - \mathbf y\):
In words: the gradient for feature \(j\) is the average of (prediction error × that feature's value). Setting it to zero recovers the Normal Equation — so GD and the closed form chase the same point; GD just crawls there. Because the loss is convex, GD with a sane \(\eta\) is guaranteed to reach the global minimum.
The three flavors: same algorithm, one dial¶
The only thing that changes is how many samples are used to estimate the gradient before each step:
| Flavor | Samples / step | Character |
|---|---|---|
| Batch (\(B=n\)) | all \(n\) | True gradient, smooth path, but one step touches the whole dataset. 1 update / epoch. |
| Stochastic (SGD) (\(B=1\)) | one random | Cheap, noisy, zig-zags; buzzes around the minimum (decay \(\eta\) to settle). \(n\) updates / epoch. |
| Mini-batch (\(1\!<\!B\!<\!n\)) | 32–256 | Best of both; GPU-friendly matrix multiply. The practical default. \(n/B\) updates / epoch. |
One epoch = one full pass over the data. Note: PyTorch's optim.SGD is really mini-batch — define all three precisely by \(B\) in an interview.
§2 The LMS / Widrow-Hoff rule¶
Per-example cost \(J(\theta)=\tfrac12(h_\theta(x)-y)^2\) with \(h_\theta(x)=\theta^\top x\). Chain rule (the 2 and \(\tfrac12\) cancel; \(\partial h/\partial\theta_j = x_j\)):
The gradient for weight \(j\) is the prediction error times the \(j\)-th feature. Plugging into the GD step gives the LMS / Widrow-Hoff update:
Why it is intuitive
The update is self-correcting and proportional to error: near-right prediction → tiny step; badly wrong → big step; the sign auto-handles direction; and it is scaled by \(x_j\) so only the feature that actually drove the prediction gets corrected. This single-example atom is what Batch GD (sum over all \(m\)) and SGD (one at a time) are built from.
Cricket. A batsman adjusting after each ball: misjudge the length badly, big technical correction; almost middled it, leave technique alone; and only adjust the part of your game that was involved (no point fixing pull-shot footwork after misjudging a cover drive).
§3 Convexity, the Hessian and positive semi-definite¶
From \(\nabla_{\mathbf w}L = -2X^\top\mathbf y + 2X^\top X\mathbf w\), differentiate again:
The Hessian is constant — the loss is exactly quadratic, so curvature is identical everywhere (a true paraboloid). Convexity ⇔ \(X^\top X\) is positive semi-definite (PSD).
PSD proof. For any vector \(\mathbf z\): \(\;\mathbf{z}^\top (X^\top X) \mathbf{z} = (X\mathbf{z})^\top (X\mathbf{z}) = \|X\mathbf{z}\|^2 \geq 0.\) A squared length is never negative — which is the definition of PSD. Hence \(H = 2X^\top X \succeq 0\), the loss is convex, and any stationary point is a global minimum.
What PSD actually means¶
- Matrix version of "non-negative": just as \(a\ge 0\) means \(az^2\ge0\) (upward parabola), PSD means \(\mathbf z^\top A\mathbf z\ge0\) — the quadratic surface opens upward in every direction. That's why "Hessian PSD ⇔ convex."
- Eigenvalue view: PSD ⇔ all eigenvalues \(\ge 0\) (the curvatures along the principal axes). A negative eigenvalue = a downhill direction = a saddle.
- PD vs PSD: strictly positive (PD, unique minimum) iff \(X\) has full column rank. Collinear features make some \(X\mathbf z = 0\) → a flat trough → \(X^\top X\) singular → the closed form breaks. This is exactly what Ridge's \(+\lambda I\) fixes.
Interview questions¶
Q1: What actually differs between batch, stochastic, and mini-batch gradient descent?
Only the number of samples used to estimate the gradient before each step. Batch uses all n for the true gradient and a smooth path but one update per epoch; SGD uses one random sample, which is cheap and noisy and buzzes around the minimum; mini-batch uses 32 to 256, the GPU-friendly default. PyTorch's optim.SGD is actually mini-batch, so define each precisely by the batch size B.
Q2: How does the learning rate affect convergence? The learning rate is the stride length applied against the gradient. Too small and the descent crawls and takes forever; too large and it oversteps the valley, bounces, or diverges. For SGD you typically decay the learning rate over time so the iterate settles into the minimum rather than buzzing around it.
Q3: Why is linear regression guaranteed to find the global minimum? Its loss is exactly quadratic, so the Hessian \(2X^\top X\) is constant and positive semi-definite, since \(\mathbf z^\top X^\top X\mathbf z=\|X\mathbf z\|^2\ge0\). A positive semi-definite Hessian means the surface opens upward in every direction, so the loss is convex and any point where the gradient is zero is the global minimum. Gradient descent with a sane learning rate therefore converges to it.
Q4: What does the LMS update tell you intuitively? The per-weight gradient is the prediction error times that feature's value, so the update is proportional to how wrong you were and scaled by the feature that drove the prediction. A near-correct prediction barely moves the weights, a badly wrong one moves them a lot, and the sign handles direction automatically. Batch GD sums this atom over all examples and SGD applies it one at a time.