Feedforward and Recurrent Neural Networks Backward Propagation and Hessian in Matrix Form

Maxim Naumov

Abstract

In this paper, we focus on the linear algebra theory behind feedforward (FNN) and recurrent (RNN) neural networks. We review backward propagation, including backward propagation through time (BPTT). Also, we obtain a new exact expression for the Hessian, which represents second-order effects. We show that for $t$ time steps, the weight gradient can be expressed as a rank-$t$ matrix, while the weight Hessian is a sum of $t^2$ Kronecker products of rank-1 and $W^T AW$ matrices, for some matrix $A$ and weight matrix $W$. Also, we show that for a mini-batch of size $r$, the weight update can be expressed as a rank-$rt$ matrix. Finally, we briefly comment on the eigenvalues of the Hessian matrix.

Most modern deep learning relies on first-order optimization methods like Stochastic Gradient Descent (SGD) or Adam. These methods utilize the gradient—the first derivative of the loss—to update model weights. However, first-order methods are inherently "blind" to the curvature of the loss landscape. Second-order methods, which leverage the Hessian (the second derivative), can navigate complex landscapes much more efficiently.

Despite their potential, second-order methods are rarely used because the Hessian is computationally gargantuan: for a model with $W$ weights, the Hessian is a $W \times W$ matrix. This paper addresses this challenge by providing a rigorous linear algebra treatment of neural network training, deriving exact matrix-form expressions for both gradients and Hessians. The core insight is that these derivatives possess elegant, low-rank structures that could pave the way for more efficient second-order optimization.

Theoretical Framework: Matrix Representation

The foundation of this analysis is the representation of neural network layers in compact matrix form. For a single layer, the transformation of inputs $\mathbf{x}$ to outputs $\mathbf{z}$ is defined by a weight matrix $W$, a bias vector $\mathbf{b}$, and an activation function $f$.

Matrix representation of a single neural network layer.

By establishing this notation, the author, Maxim Naumov, uses multivariable calculus to derive closed-form expressions for derivatives across multi-layer architectures.

Backpropagation and Low-Rank Gradients

The paper re-derives standard backpropagation (BP) and Backpropagation Through Time (BPTT) using matrix notation. A key finding is the specific rank of weight updates. For a single data point in a feedforward network, the weight gradient is a rank-1 matrix (an outer product of two vectors). In the context of an RNN operating over $t$ time steps, the gradient becomes a rank-$t$ matrix.

Signal propagation through a multi-layer feedforward neural network.

This low-rank nature implies that the "information" added to weights during a single training step is confined to a very low-dimensional subspace relative to the total number of parameters. For a mini-batch of size $r$, the update is shown to be a rank-$rt$ matrix.

The Exact Hessian and Kronecker Structure

The primary novelty of the work is the derivation of an exact expression for the weight Hessian. Naumov demonstrates that the Hessian can be expressed using Kronecker products, which effectively inflate small matrices into large block matrices. For FNNs, the Hessian is expressed as:

$$H_w = (C \circ F + D) \otimes (zz^T)$$

This formula is significant because it separates the contribution of layer inputs ($zz^T$) from the error propagation terms ($C, F, D$). Furthermore, the paper shows that the eigenvalues of a massive $mn \times mn$ Hessian are directly related to the eigenvalues of a much smaller $m \times m$ matrix. This dimensionality reduction suggests that one can understand local curvature or model stability without decomposing the entire Hessian.

Implications for Optimization

While calculating the full Hessian for modern large-scale models remains computationally expensive, these structural insights offer a path forward. By exploiting the Kronecker and low-rank structures identified here, researchers may develop "quasi-second-order" algorithms that offer the stability of Newton methods with the feasibility of first-order methods. Additionally, the paper provides concrete bounds for RNN Hessian eigenvalues, offering a theoretical lens through which to analyze the vanishing and exploding gradient problems.

Summary updated

Abstract

In this paper we focus on the linear algebra theory behind feedforward (FNN) and recurrent (RNN) neural networks. We review backward propagation, including backward propagation through time (BPTT). Also, we obtain a new exact expression for Hessian, which represents second order effects. We show that for $t$ time steps the weight gradient can be expressed as a rank-$t$ matrix, while the weight Hessian is as a sum of $t^{2}$ Kronecker products of rank-$1$ and $W^{T}AW$ matrices, for some matrix $A$ and weight matrix $W$. Also, we show that for a mini-batch of size $r$, the weight update can be expressed as a rank-$rt$ matrix. Finally, we briefly comment on the eigenvalues of the Hessian matrix.
BibTeX
@misc{naumov2017feedforward,
  author = {Maxim Naumov},
  title = {{Feedforward and Recurrent Neural Networks Backward Propagation and Hessian in Matrix Form}},
  year = {2017},
  eprint = {1709.06080},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1709.06080},
}
Figure