Optimising Distributions with Natural Gradient Surrogates

Jonathan So, Richard E. Turner

Abstract

Natural gradient methods have been used to optimise the parameters of probability distributions in a variety of settings, often resulting in fast-converging procedures. Unfortunately, for many distributions of interest, computing the natural gradient has a number of challenges. In this work we propose a novel technique for tackling such issues, which involves reframing the optimisation as one with respect to the parameters of a surrogate distribution, for which computing the natural gradient is easy. We give several examples of existing methods that can be interpreted as applying this technique, and propose a new method for applying it to a wide variety of problems. Our method expands the set of distributions that can be efficiently targeted with natural gradients. Furthermore, it is fast, easy to understand, simple to implement using standard autodiff software, and does not require lengthy model-specific derivations. We demonstrate our method on maximum likelihood estimation and variational inference tasks.

Introduction

In machine learning and statistics, finding optimal parameters for probability distributions—such as in Maximum Likelihood Estimation (MLE) or Variational Inference (VI)—is a fundamental task. While standard Gradient Descent (GD) is widely used, its performance is highly sensitive to the chosen parameterization. Natural Gradient Descent (NGD) addresses this by navigating the "statistical manifold" rather than the raw parameter space, offering reparameterization invariance and faster convergence.

However, NGD's reliance on the Fisher Information Matrix (FIM) presents significant hurdles: the FIM can be computationally expensive to invert ($O(m^3)$), analytically unavailable, or singular. This paper introduces Surrogate Natural Gradient Descent (SNGD), a method that bypasses these issues by reparameterizing the objective using a "surrogate" distribution where the natural gradient is trivial to compute.

Methodology: Surrogate Natural Gradient Descent

The core of SNGD lies in reparameterizing the target distribution $q_\theta$ via a function $\theta = g(\tilde{\theta})$, where $\tilde{\theta}$ are parameters of a surrogate distribution $\tilde{q}_{\tilde{\theta}}$. By choosing a surrogate from an Exponential Family (EF), the natural gradient with respect to natural parameters becomes a simple standard gradient with respect to dual mean parameters. This "EF trick" allows SNGD to leverage standard automatic differentiation tools to compute natural gradients without ever explicitly forming or inverting a Fisher matrix.

In cases where the surrogate's parameter space does not perfectly align with the target's, auxiliary parameters ($\lambda$) are introduced and optimized using standard methods like Adam in parallel with the surrogate natural gradient steps.

Experimental Evaluation

The authors evaluated SNGD across diverse tasks, including Negative Binomial MLE (Sheep Ticks dataset), density estimation (UCI MiniBooNE), and high-dimensional synthetic data (up to $d=1,000$).

Convergence comparison on MLE tasks and the Gamma surrogate fit for Negative Binomial data.

As shown in Figure 5, SNGD demonstrates superior convergence speed compared to standard GD, NGD, and BFGS. Notably, the method remains effective even when the surrogate and target distributions have different supports, such as using a continuous Gamma distribution as a surrogate for a discrete Negative Binomial distribution.

Comparison of SNGD and Adam performance over many iterations.

In comparisons with Adam (Figure 2), SNGD consistently achieves lower negative log-likelihood values more quickly and maintains greater stability across various learning rates. In high-dimensional settings with over 500,000 parameters, SNGD remains computationally feasible where exact NGD would fail due to the $O(m^3)$ cost of FIM inversion.

Discussion and Insights

A key insight is that the surrogate distribution acts as a local approximation of the target's statistical manifold. SNGD is effective if the surrogate's KL divergence locally mirrors that of the target. Interestingly, SNGD can sometimes outperform "exact" NGD because the use of mean parameters in Exponential Families allows for larger, more stable optimization steps.

The method is highly "autodiff friendly," integrating seamlessly with modern libraries like JAX or PyTorch. This eliminates the need for manual, model-specific derivations of complex Fisher matrices, making advanced optimization accessible for a wider range of models.

Conclusion and Future Work

SNGD provides a robust, scalable, and easy-to-implement alternative to standard natural gradient methods. While it currently requires manual selection of surrogate distributions and mapping functions, future work could focus on automating these choices. Additionally, exploring more complex surrogate manifolds, such as those defined by normalizing flows, could further extend the applicability of this promising technique.

Summary updated

Abstract

Natural gradient methods have been used to optimise the parameters of probability distributions in a variety of settings, often resulting in fast-converging procedures. Unfortunately, for many distributions of interest, computing the natural gradient has a number of challenges. In this work we propose a novel technique for tackling such issues, which involves reframing the optimisation as one with respect to the parameters of a surrogate distribution, for which computing the natural gradient is easy. We give several examples of existing methods that can be interpreted as applying this technique, and propose a new method for applying it to a wide variety of problems. Our method expands the set of distributions that can be efficiently targeted with natural gradients. Furthermore, it is fast, easy to understand, simple to implement using standard autodiff software, and does not require lengthy model-specific derivations. We demonstrate our method on maximum likelihood estimation and variational inference tasks.
BibTeX
@inproceedings{so2024optimising,
  author = {Jonathan So and Richard E. Turner},
  title = {{Optimising Distributions with Natural Gradient Surrogates}},
  booktitle = {International Conference on Artificial Intelligence and Statistics},
  year = {2024},
  url = {https://openreview.net/forum?id=NE1CzhH8p2},
}
Figure