The Expected Loss of Preconditioned Langevin Dynamics Reveals the Hessian Rank

Amitay Bar, Rotem Mulayoff, Tomer Michaeli, Ronen Talmon

Abstract

Understanding the geometric complexity of the loss landscape in deep neural networks is crucial for analyzing generalization and optimization. A key metric for this complexity is the rank of the Hessian matrix, which represents the number of "effective" parameters. However, computing the Hessian rank for modern architectures is computationally prohibitive. This paper introduces a novel approach using Preconditioned Langevin Dynamics (LD). We demonstrate that by balancing the optimizer's preconditioning matrix with its noise covariance, the steady-state expected loss directly reveals the Hessian rank. Our proposed estimator is computationally efficient, requiring only standard gradients, and significantly outperforms existing spectral density estimation methods in both accuracy and speed.

Introduction

In the study of deep learning, the Hessian matrix—the matrix of second-order partial derivatives of the loss function—serves as a fundamental tool for understanding model behavior. Its eigenvalues characterize the "sharpness" of minima, which is often linked to generalization performance. Specifically, the Hessian rank, or the number of non-zero eigenvalues, acts as a proxy for the "effective" dimensionality of the learned function.

Despite its theoretical importance, the Hessian is notoriously difficult to work with in practice. For a network with $N$ parameters, the Hessian is an $N \times N$ matrix. With modern models reaching billions of parameters, even storing the matrix is impossible. Current state-of-the-art methods for rank estimation, such as those by Ubaru & Saad, rely on stochastic Lanczos quadrature or Hessian-vector products. These methods are often computationally expensive, sensitive to hyperparameter tuning, and can struggle with the "noisy" spectral distributions found in real-world neural networks.

Methodology: The Geometry of Noise

The core contribution of this work is the discovery of a "magic" relationship between optimization noise and landscape geometry. The authors focus on Preconditioned Langevin Dynamics (LD), a stochastic optimization framework where weight updates are augmented with controlled noise and a preconditioning matrix $G$.

Quadratic Approximation and the OU Process

Near a local minimum, the loss landscape can be locally approximated as a quadratic bowl. Under this assumption, the optimization dynamics follow an Ornstein–Uhlenbeck (OU) process. This mathematical framework allows for the derivation of a closed-form expression for the expected loss over time.

The Rank-Revealing Condition

The researchers found that if the preconditioning matrix $G$ and the noise covariance $\Sigma$ are chosen such that their product is a scaled identity matrix ($\Sigma G = \sigma^2 I$), the steady-state expected loss $\mathbb{E}[L]$ becomes remarkably simple: $$\mathbb{E}[L] \approx \frac{\sigma^2}{2} \text{rank}(H)$$ where $H$ is the Hessian at the minimum. This implies that the total "height" the weights reach as they are "shaken" by the optimizer's noise is directly proportional to the number of directions in which the loss bowl curves.

Figure 1: The convergence of empirical loss to the theoretical steady-state value predicted by Theorem 1 and Proposition 1.

Algorithm 1: A Practical Estimator

Based on this theory, the authors propose a simple two-step algorithm:

  1. Train the model to a stationary point using standard optimizers.
  2. "Shake" the weights using Preconditioned LD with the condition $\Sigma G = \sigma^2 I$ and measure the average increase in loss. This approach is highly efficient because it only requires standard backpropagation to compute gradients, making it roughly twice as fast per iteration as methods requiring Hessian-vector products.

Experimental Validation

The proposed estimator was validated across synthetic and real-world scenarios.

Linear Neural Networks

To establish a ground truth, the authors used linear networks where the true Hessian rank is analytically known. They tested architectures ranging from 320 to over 327,000 parameters. As shown in Figure 2, the proposed method ("Ours") tracks the true rank with exceptional precision across multiple orders of magnitude, significantly outperforming the Ubaru & Saad (U&S) baseline.

Figure 2: Hessian rank estimation accuracy. Our method shows near-perfect alignment with the true rank across various scales, while the baseline exhibits significant deviation.

Real-World Architectures: DnCNN

The method was further tested on a Denoising Convolutional Neural Network (DnCNN) trained on the MNIST dataset. In this non-linear setting, the estimator captured over 98.5% of the Hessian's spectral energy. It provided a stable rank estimate of 133, whereas the baseline struggled with the low-magnitude eigenvalues typical of real networks, yielding a much lower and less plausible estimate of 34.

Discussion and Key Insights

The most profound takeaway is that the steady-state loss is not merely a measure of error, but a physical probe of the model's complexity. This "Loss as a Probe" perspective suggests that the noise inherent in stochastic gradient descent (SGD) naturally interacts with the geometry of the loss landscape.

Furthermore, the specific condition $\Sigma G = \sigma^2 I$ links the optimization process to Riemannian Langevin Dynamics on a flat manifold. This suggests that the rank is most clearly revealed when the optimizer "respects" the underlying geometry of the parameter space. This also provides a theoretical explanation for why "simpler" models (those with lower Hessian rank) are naturally more robust to optimization noise: they have fewer "curved" directions for the noise to push the weights up the loss bowl.

Limitations and Future Work

While powerful, the method relies on a local quadratic approximation. While this holds well near minima, its behavior in highly non-convex regions far from stationary points remains a subject for future study. Additionally, while the method is more robust than previous approaches, users must still carefully select the noise scale $\sigma^2$ to ensure the weights stay within the "quadratic bowl" while remaining large enough for measurable loss changes. Future research may extend this "noise-probing" technique to estimate the rank of arbitrary symmetric matrices in general numerical linear algebra.

Summary updated

Abstract

Langevin dynamics (LD) is widely used for sampling from distributions and for optimization. In this work, we derive a closed-form expression for the expected loss of preconditioned LD near stationary points of the objective function. We use the fact that at the vicinity of such points, LD reduces to an Ornstein–Uhlenbeck process, which is amenable to convenient mathematical treatment. Our analysis reveals that when the preconditioning matrix satisfies a particular relation with respect to the noise covariance, LD's expected loss becomes proportional to the rank of the objective's Hessian. We illustrate the applicability of this result in the context of neural networks, where the Hessian rank has been shown to capture the complexity of the predictor function but is usually computationally hard to probe. Finally, we use our analysis to compare SGD-like and Adam-like preconditioners and identify the regimes under which each of them leads to a lower expected loss.
BibTeX
@inproceedings{bar2024expected,
  author = {Amitay Bar and Rotem Mulayoff and Tomer Michaeli and Ronen Talmon},
  title = {{The Expected Loss of Preconditioned Langevin Dynamics Reveals the Hessian Rank}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2024},
  doi = {10.1609/aaai.v38i18.30014},
}
Figure