Gradient Descent for Deep Learning

Consider a deep network parameterized by a vector $\theta \in \mathbb{R}^p$ (all weights and biases flattened together). Given a training set $\{(x^{(i)}, y^{(i)})\}_{i=1}^n$, define the empirical loss

where $f_\theta$ is the network's forward function and $\ell$ is a per-example loss such as cross-entropy or squared error. Training means finding $\theta^\star$ that minimizes $L$. Because $L$ is a smooth (almost everywhere differentiable) function of $\theta$, and $p$ is enormous, we cannot solve $\nabla_\theta L(\theta) = 0$ in closed form; instead we search iteratively.

Full-batch gradient descent is the iterative rule

where $\eta > 0$ is the learning rate (step size) and $\nabla_\theta L(\theta_t)$ is the gradient of the entire dataset's average loss, evaluated at the current parameters. The word "full-batch" specifically means every one of the $n$ training examples contributes to the gradient at every single step — as opposed to stochastic or mini-batch variants, which use a random subset. The gradient itself is computed efficiently via Backpropagation, which applies the chain rule layer-by-layer through the Computational Graph of the network. The key conceptual object is the gradient vector $\nabla_\theta L(\theta)$: a vector with one entry per parameter, each entry being the partial derivative $\partial L / \partial \theta_j$. This vector, by a basic fact of multivariable calculus, points in the direction of steepest increase of $L$ at $\theta$. Moving in the opposite direction — hence the minus sign — is therefore the direction of steepest decrease, at least locally. The learning rate $\eta$ controls how far we trust this local linear approximation before recomputing it.

The algorithm alternates two phases at every iteration: (1) a forward-and-backward pass over the whole dataset to compute the exact gradient, and (2) a parameter update using that gradient. This repeats until some stopping criterion — a fixed iteration budget, a small gradient norm, or a validation-loss plateau — is met. ``` ALGORITHM FullBatchGradientDescent Input: theta_0 : initial parameter vector (e.g., random init) D = {(x_i,y_i)} : full training set, i = 1..n eta : learning rate T : maximum number of iterations tol : gradient-norm stopping tolerance theta <- theta_0 for t = 1 to T:

# --- Forward pass: compute predictions and loss for ALL n examples --- total_loss <- 0 for i = 1 to n: y_hat_i <- forward(theta, x_i) total_loss <- total_loss + loss(y_hat_i, y_i) total_loss <- total_loss / n

# --- Backward pass: accumulate gradient over ALL n examples --- grad <- zero_vector(size(theta)) for i = 1 to n: grad_i <- backprop(theta, x_i, y_i) # dL_i/d theta via chain rule grad <- grad + grad_i grad <- grad / n

# --- Stopping check --- if norm(grad) < tol: break

# --- Parameter update: the actual gradient-descent step --- theta <- theta - eta * grad return theta ``` Two implementation details matter. First, the loop `for i = 1 to n` for the backward pass is, in practice, vectorized: frameworks compute the gradient over the whole batch as one tensor operation rather than a Python-level loop, but the mathematical content — averaging per-example gradients — is identical. Second, the per-example gradients `grad_i` are computed by a single application of reverse-mode automatic differentiation (backpropagation) per example, reusing intermediate activations from the forward pass; this is what keeps the cost linear rather than quadratic in the network depth. The following diagram shows the computational loop as a state machine: the two big phases (accumulate gradient over the full dataset, then take one step) followed by a stopping check.

Time complexity. Let $n$ be the number of training examples, $p$ the number of parameters, and assume a forward pass through the network costs $O(p)$ floating-point operations per example (true for standard feedforward and convolutional architectures, where compute is dominated by matrix multiplications whose total size scales with the parameter count). Backpropagation for one example costs the same order as the forward pass, $O(p)$, since reverse-mode automatic differentiation performs one extra pass of comparable cost to the forward pass — a classical and important fact, since naively computing $p$ separate directional derivatives would cost $O(p^2)$. Therefore:

• One full-batch gradient computation costs $O(n \cdot p)$.
• Over $T$ iterations, full-batch gradient descent costs $O(T \cdot n \cdot p)$.

This is the honest cost: to take even one single parameter-update step, you must touch every training example. This is the central tradeoff that motivates Mini-Batch Gradient Descent and Stochastic Gradient Descent — they approximate $\nabla_\theta L(\theta)$ using a subset of size $m \ll n$, reducing per-step cost to $O(m \cdot p)$ at the price of noisier gradient estimates.

Space complexity. Training requires storing:

• the parameters $\theta$: $O(p)$,
• the gradient accumulator: $O(p)$,
• all intermediate activations needed by backpropagation for the current batch: $O(n \cdot h)$ where $h$ is the total width of hidden layers, since full-batch descent must forward-propagate the entire dataset before it can backpropagate.

This last term is often the true bottleneck in practice — it is why full-batch gradient descent is rarely used at scale for deep networks: keeping every activation for every training example in memory simultaneously is infeasible once $n$ is large (this is precisely why mini-batching exists, quite apart from any statistical benefit of noise).

Correctness argument. Why does subtracting the gradient decrease the loss? Consider a first-order Taylor expansion of $L$ around $\theta_t$ for a small step $\Delta\theta$:

We want to choose $\Delta\theta$ (subject to a bound on its size, since the approximation is only locally valid) to make the right-hand side as negative as possible. Among all vectors $\Delta\theta$ of fixed norm $r$, the inner product $\nabla L(\theta_t)^\top \Delta\theta$ is minimized (most negative) when $\Delta\theta$ points exactly opposite to $\nabla L(\theta_t)$ — a direct consequence of the Cauchy–Schwarz inequality, since

with equality exactly when $\Delta\theta = -c\,\nabla L(\theta_t)$ for $c>0$. Choosing $\Delta\theta = -\eta \nabla L(\theta_t)$ realizes this optimal direction. Substituting back,

which is strictly less than $L(\theta_t)$ whenever $\nabla L(\theta_t) \ne 0$ and $\eta$ is small enough that the linear approximation is trustworthy. This gives a descent guarantee: each step decreases the loss, provided $\eta$ is chosen appropriately. Making this rigorous (rather than just "approximately") requires an assumption on the smoothness of $L$. If $L$ is $\beta$-smooth (its gradient is $\beta$-Lipschitz — a standard, mild assumption for the loss surfaces induced by common activations and losses on bounded domains), then a classical descent lemma gives

Choosing $\eta < 2/\beta$ (in practice $\eta \le 1/\beta$) makes the coefficient of $\|\nabla L(\theta_t)\|^2$ strictly positive, guaranteeing monotonic decrease at every step until a stationary point ($\nabla L(\theta_t) = 0$) is reached. Since deep-network losses are non-convex, this argument only guarantees convergence to a stationary point — a local minimum, saddle point, or (in pathological cases) a local maximum — not the global minimum. This is the honest tradeoff: gradient descent's correctness guarantee is about local improvement, not global optimality, and in practice saddle points and flat regions are the dominant obstacle in high-dimensional non-convex loss landscapes, not local minima being globally suboptimal (empirically, most local minima found by gradient descent in deep nets are of comparable quality).

To make the mechanics completely concrete, consider a tiny network: a single linear neuron with no bias, predicting $\hat{y} = \theta x$, trained with squared error on three data points. This is small enough to trace by hand, yet non-trivial (asymmetric, non-zero-centered data) so no error can hide. Dataset: $(x_1,y_1)=(1,2)$, $(x_2,y_2)=(2,3)$, $(x_3,y_3)=(3,5)$. Loss: $L(\theta) = \frac{1}{3}\sum_{i=1}^3 (\theta x_i - y_i)^2$. Gradient: $\dfrac{dL}{d\theta} = \dfrac{2}{3}\sum_{i=1}^3 x_i(\theta x_i - y_i)$. Let $\eta = 0.05$ and $\theta_0 = 0$.

Notice the loss is falling each step (residuals shrink in magnitude) and the gradient magnitude is shrinking ($15.33 \to 8.38 \to 4.27 \to 2.28$), exactly as predicted by the descent lemma: as $\theta_t$ approaches the least-squares optimum, $\nabla L(\theta_t) \to 0$. The exact least-squares solution here is $\theta^\star = \frac{\sum x_iy_i}{\sum x_i^2} = \frac{2+6+15}{1+4+9}=\frac{23}{14}\approx 1.643$, and the iterates $0 \to 0.767 \to 1.186 \to 1.399 \to 1.513$ are visibly converging toward it geometrically. This single-parameter trace scales conceptually to a full deep network: the same update rule, applied to a $p$-dimensional $\theta$ using gradients from backpropagation, drives every weight toward a stationary point of the loss.

The method traces back to 19th-century numerical analysis, long before neural networks existed, and was repurposed by 20th-century optimization and machine-learning researchers into the workhorse of deep learning.

Every major deep learning framework — PyTorch, TensorFlow, JAX — implements gradient descent and its stochastic/mini-batch descendants as the core `optimizer.step()` primitive that all training loops call. Large-scale systems such as image classifiers, large language models, recommendation engines, and reinforcement learning agents are all trained by variants of this same update rule, layered with momentum, adaptive scaling, weight decay, and learning-rate schedules. Understanding the plain full-batch rule is the prerequisite for understanding why these more sophisticated optimizers were invented: each addresses a specific weakness (noise, curvature, scale, cost) of the basic gradient-descent step described here. It also underlies numerical methods far beyond deep learning, including classical regression, matrix factorization, and physics-based simulation, wherever a smooth objective must be minimized over continuous parameters.

Ask the tutor: How do momentum and adaptive learning rates (like Adam) modify this basic gradient descent update, and why do they train deep networks faster in practice?