gradient_descent_optimization

Gradient Descent and Variants

Definition

Gradient descent is a first-order iterative optimization algorithm that minimizes an objective function by repeatedly moving in the direction of steepest descent (negative gradient).

Intuition

Imagine standing on a hilly terrain in fog. You can only feel the slope under your feet. Gradient descent says: always step in the direction that goes most steeply downhill. The step size (learning rate) controls how far you stride each step — too large and you overshoot; too small and you take forever to converge.

Formal Description

Batch Gradient Descent

Given $f(\mathbf{\theta })=\frac{1}{n}{\sum }_{i=1}^n\ell (\mathbf{\theta };x_i)$, update:

$${\mathbf{\theta }}_{t+1}={\mathbf{\theta }}_t-\eta {\nabla }_{\mathbf{\theta }}f({\mathbf{\theta }}_t)$$

$\eta >0$ is the learning rate. Computes gradient over the full dataset — expensive for large $n$.

Stochastic Gradient Descent (SGD)

In the classical definition, uses one randomly sampled example per update:

$${\mathbf{\theta }}_{t+1}={\mathbf{\theta }}_t-\eta {\nabla }_{\mathbf{\theta }}\ell ({\mathbf{\theta }}_t;x_i)$$

This is an unbiased but noisy estimate of the full gradient; the noise can help escape saddle points and some shallow minima.

Complexity per iteration: $O(d)$ for single-example SGD vs $O(nd)$ for batch gradient descent, where $d$ is the parameter dimension and $n$ is the dataset size.

Note on terminology: In modern practice, “SGD” often refers to mini-batch SGD (see below). True single-example SGD is rarely used because it cannot leverage GPU parallelism effectively.

Mini-batch SGD (standard in deep learning): average gradient over a batch of $B$ examples:

$${\mathbf{\theta }}_{t+1}={\mathbf{\theta }}_t-\frac{\eta }{B}\sum _{i\in \mathcal{B}}\nabla \ell ({\mathbf{\theta }}_t;x_i)$$

Typical batch size: 32–512. GPU parallelism makes mini-batch efficient.

Convergence Rate

For $L$-smooth, $m$-strongly convex $f$ with fixed $\eta \le 1/L$:

$$f({\mathbf{\theta }}_T)-f({\mathbf{\theta }}^{\ast })\le {\left(1-\frac{m}{L}\right)}^T(f({\mathbf{\theta }}_0)-f({\mathbf{\theta }}^{\ast }))$$

Linear convergence — the condition number $\kappa =L/m$ governs speed.

For convex (not strongly convex): $O(1/T)$ convergence.

Momentum

Accumulates an exponential moving average of gradients to dampen oscillations:

$${\mathbf{v}}_{t+1}=\beta {\mathbf{v}}_t+(1-\beta )\nabla f({\mathbf{\theta }}_t)$$ $${\mathbf{\theta }}_{t+1}={\mathbf{\theta }}_t-\eta {\mathbf{v}}_{t+1}$$

Typical $\beta =0.9$. Nesterov momentum evaluates the gradient at the “lookahead” point ${\mathbf{\theta }}_t-\beta {\mathbf{v}}_t$, improving convergence rate to $O(1/T^2)$ for convex problems.

RMSProp

Divides the learning rate by a running average of squared gradients, adapting per-parameter:

$${\mathbf{s}}_{t+1}=\rho {\mathbf{s}}_t+(1-\rho )\nabla f\odot \nabla f$$ $${\mathbf{\theta }}_{t+1}={\mathbf{\theta }}_t-\frac{\eta }{\sqrt{{\mathbf{s}}_{t+1}}+ϵ}\nabla f$$

Effective in non-stationary settings; reduces the learning rate for frequently updated parameters.

Adam (Adaptive Moment Estimation)

Combines momentum (first moment) and RMSProp (second moment) with bias correction:

$${\mathbf{m}}_{t+1}={\beta }_1{\mathbf{m}}_t+(1-{\beta }_1)\nabla f$$ $${\mathbf{v}}_{t+1}={\beta }_2{\mathbf{v}}_t+(1-{\beta }_2)\nabla f\odot \nabla f$$ $$\hat{\mathbf{m}}={\mathbf{m}}_{t+1}/(1-{\beta }_1^{t+1}),\hat{\mathbf{v}}={\mathbf{v}}_{t+1}/(1-{\beta }_2^{t+1})$$ $${\mathbf{\theta }}_{t+1}={\mathbf{\theta }}_t-\frac{\eta }{\sqrt{\hat{\mathbf{v}}}+ϵ}\hat{\mathbf{m}}$$

Defaults: ${\beta }_1=0.9$, ${\beta }_2=0.999$, $ϵ=10^{-8}$, $\eta =10^{-3}$.

AdamW: decouples weight decay from the gradient update (correct form):

$${\mathbf{\theta }}_{t+1}={\mathbf{\theta }}_t-\frac{\eta }{\sqrt{\hat{\mathbf{v}}}+ϵ}\hat{\mathbf{m}}-\eta \lambda {\mathbf{\theta }}_t$$

Learning Rate Schedules

Schedule	Description
Step decay	Multiply by $\gamma <1$ every $k$ epochs
Cosine annealing	${\eta }_t={\eta }_{\min }+\frac{1}{2}({\eta }_{\max }-{\eta }_{\min })(1+\cos (\pi t/T))$
Warmup	Linear ramp from 0 to ${\eta }_{\max }$ over first $T_w$ steps
Cyclic LR (CLR)	Oscillate between ${\eta }_{\min }$ and ${\eta }_{\max }$

Warmup + cosine decay is standard for transformer training.

Challenges in Non-Convex Optimization

• Saddle points: gradient is zero but not a minimum; second-order methods or noise escape these.
• Vanishing/exploding gradients: deep networks can have exponentially small/large gradients; mitigated by normalisation, residual connections, gradient clipping.
• Learning rate sensitivity: too large diverges, too small converges slowly; use learning rate finders.

Applications

• Training any differentiable model: linear regression, logistic regression, neural networks
• Specific optimizer choice matters: Adam is default for deep learning; SGD with momentum can generalise better for image models (via implicit regularisation from noise)

Trade-offs

Optimizer	Pros	Cons
SGD (+ momentum)	Good generalisation, well-studied theory	Sensitive to LR, slow on ill-conditioned problems
Adam	Fast convergence, robust to LR	Can generalise worse than SGD for image models; weight decay must use AdamW
RMSProp	Good for RNNs	No bias correction

Links

• Convex Optimization
• Lagrangian and Constrained Optimization
• Partial Derivatives
• Gradient Descent (DL Theory)
• Optimization Algorithms (Modeling)