Gradient Descent · Projects · Amittai Siavava

Regression models fit to a labeled dataset with no closed-form solver in play: the parameters start arbitrary and gradient descent moves them toward the values that minimize the loss. The point of the exercise is the optimizer itself — deriving the gradient of the loss and stepping against it.

For parameters $w$ and a loss $J (w)$ averaged over the training set, gradient descent repeatedly steps opposite the gradient:

w \leftarrow w - η \nabla_{w} J (w),

where the learning rate $η$ sets the step size. The gradient points uphill, so its negation is the direction of steepest local decrease. For a convex loss the iteration reaches the global minimum; otherwise it settles into a local one.

Take squared-error loss over $m$ examples, and write the per-example residual $r_{i} = w \cdot x_{i} - y_{i}$ :

J (w) = \frac{1}{2 m} i = 1 \sum m r_{i}^{2} .

Each residual depends on the weights through $\partial r_{i} / \partial w = x_{i}$ , so the chain rule differentiates one term as $\frac{1}{2} \partial_{w} r_{i}^{2} = r_{i} x_{i}$ . Averaging over the examples gives the gradient the update uses:

\nabla_{w} J = \frac{1}{m} i = 1 \sum m (w \cdot x_{i} - y_{i}) x_{i} .

It is the average of each example's error scaled by its features, so the step pushes weights toward reducing the largest residuals first.

How quickly descent converges depends on the shape of that bowl. The loss here is a quadratic bowl, and its contours are ellipses whose axes are the eigenvectors of the Hessian $\frac{1}{m} X^{⊤} X$ . When the features are on similar scales the bowl is round and descent heads almost straight for the minimum. When one direction is much steeper than another the bowl is a narrow valley, and the gradient, perpendicular to each contour, points mostly across the valley rather than down it, so the path zigzags.

Elliptical loss contours with the minimum at the center. On elongated, ill-conditioned contours the negative gradient points across the valley, so gradient descent zigzags in toward the minimum.

The step size interacts with that shape. Convergence on a quadratic needs $η < 2/ L$ , where $L$ is the largest curvature; above it the iteration overshoots and diverges. The number of steps to converge grows with the condition number $κ = L / μ$ , the ratio of the largest to the smallest curvature, which is exactly how elongated the ellipses are. Too small an $η$ is always safe but crawls.

Algorithm:

\textsc{Gradient-Descent}(X, y, \eta)

— batch parameter fit

1
input: features $X$ , targets $y$ , learning rate $\eta$
2
initialize $\mathbf{w}$ to zeros
3
repeat
4
$\mathbf{g} \gets \nabla_{\mathbf{w}} J(\mathbf{w})$ over all examples
5
$\mathbf{w} \gets \mathbf{w} - \eta \, \mathbf{g}$
6
until $J(\mathbf{w})$ stops decreasing
7
return $\mathbf{w}$

Standardizing the features first shrinks $κ$ toward $1$ , so no single dimension dominates the step and one learning rate suits them all. Stochastic and minibatch variants estimate the gradient from a subset each step, trading a noisier direction for far more updates per pass over the data. Training stops when the loss flattens.

References

Project repository
Reference notes: Numerical Optimization and Gradient Descent
Reference notes: Learning from Examples

╌╌ END ╌╌