Gradient descent

Gradient descent minimizes a differentiable function through successive steps opposite to the gradient:

where is the learning rate at iteration .

The idea: the gradient points toward steepest ascent; subtracting moves locally toward a minimum.

Intuition

Imagine a ball rolling on a surface: at each step, read the local slope ( ) and move in the steepest descent direction. Step too large: overshoot and divergence. Step too small: very slow convergence. On a convex smooth function, a good choice of guarantees convergence to the global minimum (see Convex optimization). On a non-convex function (neural networks), you often land at a local minimum or saddle — hence initialization and variants (momentum, Adam).

Learning rate

Strategy	Formula / idea	Usage
Fixed step	constant	Simple; requires manual tuning
Decay	or	SGD convergence guarantees under assumptions
Line search	Choose minimizing	Costly but adaptive; Newton uses similar logic
Schedule (warmup, cosine)	planned over epochs	Standard in deep learning

For an -smooth convex function, a constant step guarantees convergence. In practice, is rarely known: test values (log-scale: , , …) or use an adaptive optimizer.

Variants

Method	Idea	Benefit
Batch (GD)	Gradient over the full dataset	Stable but slow on large data
SGD	Gradient on one example (or mini-batch)	Fast; noise helps escape local minima
Mini-batch	Gradient on a subset of size	Standard compromise; GPU-parallelizable
Momentum	, then	Accelerates along consistent directions; dampens oscillation
Adam / RMSProp	Per-coordinate adaptive step (moving averages of gradient and variance)	Little tuning; default in tabular DL and neural nets

Convergence

If is convex and -smooth, gradient descent with satisfies:

convergence — linear in iteration count for accuracy, not exponential. For faster convergence near the optimum, see Newton and quasi-Newton (coming soon).

If is -strongly convex (), the rate becomes linear (geometric):

The condition number governs speed: the larger it is, the slower the convergence.

Key hyperparameters

Parameter	Role	Main effect
`learning_rate` ()	Step size	Too large → divergence; too small → slowness
`batch_size`	Mini-batch size	Large → stable gradient; small → noise and generalization
`momentum` ()	Gradient inertia	Typically 0.9; accelerates in narrow valleys
`max_iter` / epochs	Number of iterations	Pair with early stopping to avoid overfitting
`tolerance`	Stop threshold on or loss gain	Useful when loss plateaus

Applications

Linear regression: OLS has a closed form, but gradient descent remains useful for large or streaming.
Ridge / lasso regularization: iterative minimization when or is very large.
Machine learning: training linear models, neural networks (via backprop + SGD/Adam).
Calibration: fit model parameters by minimizing a loss on historical data.

Gradient descent is the baseline algorithm in Derivatives, gradient, and Hessian; Convex optimization explains why, on a convex problem, this procedure targets the right optimum.

Limits and pitfalls

Situation	Issue	Approach
Non-convex function	Local minima, saddle points	Multi-start, momentum, learning rate schedule
Poor conditioning	Narrow elongated valleys	Feature scaling, Adam, preconditioning
Plateaus	far from optimum	ReLU/sigmoid in DL; momentum or Adam
Non-smooth objective	(lasso)	Subgradient, proximal gradient (ISTA)
Cost per iteration	Full batch too slow	Mini-batch SGD; closed form sometimes preferable (OLS)