ZoomNotes for Linear Algebra

Part 10: Learning from Data: Minimize Loss by Gradient Descent

10.1 Learning Function $F(x, v_0)$ : Data $v_0$ and Weights $x$

A neural network is a composition of $L$ layer functions:

v_k = \text{ReLU}(A_k v_{k-1} + b_k) \quad \text{for } k = 1, \dots, L

where:

$v_0$ is the input data
$A_k$ are weight matrices (learnable parameters, collectively called $x$ )
$b_k$ are bias vectors
$v_L$ is the output (prediction)

ReLU (Rectified Linear Unit): The nonlinear activation function:

\text{ReLU}(y) = \max(y, 0)

ReLU is a piecewise linear ramp function, which makes the entire network piecewise linear in the weights and inputs. This is crucial for training: the function $F(x, v_0)$ is piecewise linear.

The Learning Function: $F(x, v_0)$ maps weights $x$ and input $v_0$ to output $v_L$ . The goal is to find weights $x$ that minimize a loss function over the training data.

10.2 Counting Flat Pieces in the Graph of $F$

Because ReLU creates folds (the "crease" where $y=0$ ), the piecewise linear function $F$ divides the input space into many linear regions.

Counting Formula: For $N$ ReLU folds in $\mathbb{R}^p$ :

r(N, p) = \binom{N}{0} + \binom{N}{1} + \cdots + \binom{N}{p}

Recursive Formula:

r(N, p) = r(N-1, p) + r(N-1, p-1)

Growth: The number of regions grows roughly as $r(N,p) \approx c N^p$ , showing that even modest networks can represent highly complex piecewise linear functions.

Example: For $N = 100$ ReLU neurons in $\mathbb{R}^{10}$ , the number of linear regions is approximately $\binom{100}{10} \approx 1.7 \times 10^{13}$ .

10.3 Minimizing the Loss: Stochastic Gradient Descent

Gradient Descent: Iteratively update weights in the direction of steepest descent:

x_{k+1} = x_k - s_k \nabla F(x_k)

where $s_k$ is the learning rate (step size) and $\nabla F(x_k)$ is the gradient of the loss at $x_k$ .

Loss Functions:

Square loss: $L = (y_{\text{pred}} - y_{\text{true}})^2$
Cross-entropy loss: $L = -\sum y_i \log(\hat{y}_i)$ (for classification)

Stochastic Gradient Descent (SGD): Instead of computing the gradient over the entire dataset (which is expensive), use one random sample:

x_{k+1} = x_k - s_k \nabla F_{i_k}(x_k)

where $i_k$ is a randomly chosen index. This is much faster per iteration, and the randomness helps escape local minima.

Minibatch SGD: Average the gradient over a small batch of $B$ random samples:

x_{k+1} = x_k - s_k \cdot \frac{1}{B} \sum_{i \in \text{batch}} \nabla F_i(x_k)

Typical batch sizes: 32, 64, 128, 256. Batches balance gradient accuracy with computational efficiency.

10.4 Slow Convergence with Zigzag: Add Momentum

Standard gradient descent can zigzag when the loss landscape is elongated (high condition number), leading to slow convergence.

Momentum (Heavy Ball Method): Add a fraction of the previous update:

\begin{aligned} z_{k+1} &= \beta z_k + \nabla F(x_k) \\ x_{k+1} &= x_k - s_k z_{k+1} \end{aligned}

The momentum term $\beta z_k$ (typically $\beta \approx 0.9$ ) smooths the trajectory, reducing oscillation and accelerating convergence.

ADAM (Adaptive Moment Estimation): Combines momentum with adaptive learning rates per parameter:

Maintains exponentially decaying averages of past gradients and squared gradients
Adapts the learning rate for each parameter individually
Handles sparse gradients effectively
Typically the default optimizer for deep learning

10.5 Convolutional Neural Nets: CNN in 1D and 2D

Convolutional Neural Networks use shared weights applied via sliding windows, making them shift-invariant (translation equivariant).

1D Convolution: A filter (kernel) $w$ slides over the input, computing dot products at each position:

(f * w)[i] = \sum_{j} f[i+j] \, w[j]

2D Convolution (images): A small kernel (e.g., $3 \times 3$ ) slides across the image, computing the same weighted sum at each patch:

(I * K)[i,j] = \sum_{p,q} I[i+p, j+q] \, K[p,q]

Key properties:

Weight sharing: same filter weights used at every position (dramatically reduces parameters)
Locality: each output pixel only depends on a local neighborhood
Hierarchy: early layers detect edges, later layers detect shapes and objects

Pooling Layers: Reduce spatial dimensions:

Max-pooling: take the maximum value in each $2 \times 2$ (or other size) block
Average-pooling: take the average

Additional components:

Softmax: $\text{softmax}(z)_i = e^{z_i} / \sum_j e^{z_j}$ converts outputs to probabilities
Batch Normalization: rescales and recenters activations at each layer to maintain stable gradients
Residual Networks (ResNet): skip connections $x \to f(x) + x$ allow training very deep networks by mitigating the vanishing gradient problem

10.6 Backpropagation: Chain Rule for $F$

Backpropagation is the algorithm for computing gradients in neural networks. It is the chain rule applied efficiently in reverse mode.

Forward Pass: Compute $v_1, v_2, \dots, v_L$ and the loss $L$ .

Backward Pass (Reverse Mode): Compute gradients layer by layer from output back to input:

\frac{\partial L}{\partial v_{k-1}} = \frac{\partial L}{\partial v_k} \cdot \frac{\partial v_k}{\partial v_{k-1}}

For each layer $v_k = \text{ReLU}(A_k v_{k-1} + b_k)$ , the gradients with respect to $A_k$ and $b_k$ are computed via local derivatives:

\begin{aligned} \frac{\partial L}{\partial A_k} &= \frac{\partial L}{\partial v_k} \cdot v_{k-1}^T \\ \frac{\partial L}{\partial b_k} &= \frac{\partial L}{\partial v_k} \end{aligned}

Why automatic differentiation is efficient: The forward pass costs one function evaluation. The backward pass computes all partial derivatives in roughly the same time as one forward pass -- a vast improvement over $O(n)$ forward passes for $n$ parameters via finite differences.

The key insight: never form the full Jacobian matrix (which would be enormous). Instead, propagate gradient information backward through the computational graph, storing and reusing intermediate results.

Reading Notice