Hamiltonian Monte Carlo on ReLU Neural Networks is Inefficient

Vu C. Dinh, Lam Si Tung Ho, Cuong V. Nguyen

TL;DR

While Hamiltonian Monte Carlo (HMC) is a powerful tool for Bayesian Neural Network inference, this paper proves it is fundamentally inefficient when paired with ReLU activation functions. The non-differentiability of ReLU causes the standard leapfrog integrator to incur significantly higher errors—$\Omega(\epsilon)$ instead of the classical $O(\epsilon^3)$—leading to high rejection rates and a massive computational slowdown compared to smooth, analytical networks.

What Problem Does This Paper Address?

Bayesian Neural Networks (BNNs) are prized for their ability to provide uncertainty estimates, but training them requires sampling from complex, high-dimensional posterior distributions. Hamiltonian Monte Carlo (HMC) is the "gold standard" for this task because it uses gradient information to navigate the parameter space efficiently.

However, HMC’s efficiency relies on the target distribution being smooth. Most modern neural networks use the Rectified Linear Unit (ReLU) activation function, which has a sharp "kink" at zero where it isn't differentiable. Researchers often assume this doesn't matter because the non-differentiable points occupy a "set of measure zero" in the parameter space. This paper challenges that assumption, showing that these tiny points of non-smoothness have a outsized, negative impact on HMC's performance.

Methods

The authors combine rigorous theoretical analysis with empirical simulations to dissect HMC's behavior on ReLU networks.

  1. Theoretical Error Analysis: They analyze the "leapfrog integrator," the numerical engine of HMC. They prove that when a particle's path crosses a surface of non-differentiability (i.e., a neuron switching between active and inactive), the local error in the Hamiltonian jumps from the expected $O(\epsilon^3)$ to a much larger $\Omega(\epsilon)$.
  2. Correctness Proof: Interestingly, they first prove that HMC on ReLU networks is still mathematically correct (it samples from the right distribution) as long as the derivatives are defined consistently, such as through standard backpropagation. The issue is purely one of computational efficiency.
  3. Optimal Tuning Derivation: They derive new scaling laws for HMC on non-smooth targets. For smooth targets, the optimal acceptance rate is famously $0.651$. The authors show that for ReLU-like targets, this drops to approximately $0.45$, and the step size $\epsilon$ must scale more aggressively with the dimension $d$ (specifically $d^{-1/2}$ instead of $d^{-1/4}$).

Datasets

The authors validated their findings using two primary setups:

  • Synthetic Dataset: 100 data points generated from a noisy cosine function ($y \sim \mathcal{N}(\cos(2x), 0.1^2)$). This allowed for controlled testing of hyper-parameters like step size and dimensionality.
  • UTKFace Dataset: A real-world image regression task where the model predicts a person's age from their face. The authors used a subset of male Asian faces to compare the efficiency of Sigmoid, ReLU, and Leaky ReLU networks.

Key Insights and Ideas

  • The "Measure Zero" Fallacy: In optimization (like SGD), non-differentiable points are often negligible. In HMC, they are catastrophic. Because HMC trajectories are long, they are almost guaranteed to hit these "kinks," causing the integrator to "stumble" and the proposal to be rejected.
  • Error Accumulation: The jump in local error ($\Omega(\epsilon)$) means that as you increase the number of leapfrog steps ($L$) to explore further, the errors accumulate so quickly that the acceptance rate eventually crashes to zero.
  • Smoothness Wins: Analytical activation functions like Sigmoid do not suffer from this "stumbling" effect. Their acceptance rates remain stable even as the trajectory length increases, making them far more efficient for Bayesian inference.

Key Results

The experiments clearly demonstrate the efficiency gap:

  • Acceptance Rate Decay: As shown in Figure 1, the acceptance rate for Sigmoid networks remains high and stable. In contrast, ReLU and Leaky ReLU networks see their acceptance rates plummet as the step size or the number of steps increases.
Figure 1: Acceptance rates of HMC with respect to the number of leapfrog steps L (left) and step size ϵ (right) on BNNs with different activation functions. The decay in acceptance rates of sigmoid networks is much more moderate than those of ReLU-based networks.
  • Efficiency Gap: On the synthetic dataset, HMC for Sigmoid networks was found to be more than 4 times more efficient than for ReLU counterparts at their respective optimal settings.
  • Real-World Performance: On the UTKFace dataset, Sigmoid networks achieved significantly higher average acceptance rates ($\sim 0.54$) compared to ReLU ($\sim 0.22$) and Leaky ReLU ($\sim 0.17$). While all networks eventually reached similar error rates (MSE) when tuned perfectly, the ReLU-based networks required much more computational effort to get there.
Efficiency vs. Acceptance Rate

Limitations and Future Work

  • I.I.D. Assumption: The theoretical tuning guidelines (like the $0.45$ optimal acceptance rate) were derived assuming independent and identically distributed (i.i.d.) target components. Real neural network parameters have complex dependencies, which might shift these values.
  • Architectural Scope: This study focused on feed-forward networks. The authors suggest that future work should examine other non-smooth components, such as max-pooling layers in Convolutional Neural Networks (CNNs).
  • Geometric Characterization: A deeper understanding of how the number of "boundary crossings" scales with network depth versus width could provide even better guidelines for practitioners choosing architectures for Bayesian deep learning.

Summary updated

Abstract

We analyze the error rates of the Hamiltonian Monte Carlo algorithm with leapfrog integrator for Bayesian neural network inference. We show that due to the non-differentiability of activation functions in the ReLU family, leapfrog HMC for networks with these activation functions has a large local error rate of $Ω(ε)$ rather than the classical error rate of $O(ε^3)$. This leads to a higher rejection rate of the proposals, making the method inefficient. We then verify our theoretical findings through empirical simulations as well as experiments on a real-world dataset that highlight the inefficiency of HMC inference on ReLU-based neural networks compared to analytical networks.
BibTeX
@inproceedings{dinh2024hamiltonian,
  author = {Vu C. Dinh and Lam Si Tung Ho and Cuong V. Nguyen},
  title = {{Hamiltonian Monte Carlo on ReLU Neural Networks is Inefficient}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2024},
  url = {https://openreview.net/forum?id=aBmiyi7iA7},
}
Figure