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, we frequently need to optimize the parameters $\theta$ of a probability distribution $q_\theta$. This is a core component of tasks such as Maximum Likelihood Estimation (MLE) and Variational Inference (VI). Standard Gradient Descent (GD) treats the parameter space as a flat, Euclidean plane. However, probability distributions naturally reside on a curved manifold. Natural Gradient Descent (NGD) accounts for this geometry using the Fisher Information Matrix (FIM), which often leads to significantly faster convergence.

Despite its advantages, NGD is often computationally prohibitive. For many distributions, such as the Skew-Normal or Negative Binomial, the FIM can be expensive to invert ($O(m^3)$), analytically intractable, or even singular. This paper introduces Surrogate Natural Gradient Descent (SNGD), a method designed to bring the power of natural gradients to these challenging distributions without the heavy computational cost.

Methodology: Surrogate Natural Gradient Descent

The fundamental idea behind SNGD is to reframe the optimization problem. Instead of optimizing the target parameters $\theta$ directly, the authors introduce a surrogate distribution $\tilde{q}$ with parameters $\tilde{\theta}$.

Reparameterization and the Exponential Family

The method defines a differentiable mapping $\theta = g(\tilde{\theta})$, allowing the objective function to be rewritten in terms of the surrogate parameters. The authors specifically advocate for surrogates from the Exponential Family (EF), such as Gaussian or Gamma distributions. EFs possess a unique property: the natural gradient with respect to their "natural parameters" is simply the standard gradient with respect to their "mean parameters."

By exploiting this property, SNGD computes natural gradient updates without ever explicitly instantiating or inverting a Fisher matrix. This bypasses the $O(m^3)$ bottleneck and avoids the need for complex, model-specific derivations. For cases where the surrogate cannot fully represent the target distribution, auxiliary parameters $\lambda$ are used and updated via standard gradient descent.

Experimental Results

The authors validated SNGD across several diverse benchmarks, including particle physics data (UCI MiniBooNE), forest cover data (UCI Covertype), and financial returns (FTSE 100).

Convergence and Accuracy

SNGD consistently outperforms standard optimization baselines. In MLE tasks for count data, SNGD reaches the optimum faster than standard NGD, GD, and BFGS.

SNGD performance on count data MLE. The left panel shows SNGD converging faster than GD, NGD, and BFGS. The right panel shows the resulting Gamma PDF fit to the data.

As seen in Figure 4, SNGD not only converges more quickly but also produces a high-quality fit. Interestingly, SNGD can sometimes outperform "exact" NGD, suggesting that the surrogate's geometry may be more favorable for the optimization landscape than the target's own geometry.

Scalability in High Dimensions

A key strength of SNGD is its scalability. In high-dimensional tasks where exact NGD is computationally impossible due to matrix inversion costs, SNGD remains efficient.

SNGD vs Adam comparison. In this high-dimensional task, SNGD converges to a lower negative log-likelihood significantly faster than the Adam optimizer.

Figure 2 demonstrates that SNGD provides a substantial improvement over Adam, a widely used optimizer in deep learning. SNGD reaches a lower negative log-likelihood in fewer iterations, highlighting its effectiveness in complex parameter spaces.

Discussion and Conclusion

SNGD offers a powerful and easy-to-implement alternative for optimizing probability distributions. By leveraging surrogate geometries, it expands the applicability of natural gradients to a wider range of models.

Key Insights: * Geometry over Identity: The surrogate does not need to match the target distribution perfectly; it only needs to provide a beneficial local geometry. * Ease of Use: The method is simple to implement using standard automatic differentiation software. * Efficiency: It avoids the $O(m^3)$ cost of Fisher matrix inversion, making it suitable for high-dimensional problems.

While the choice of surrogate currently requires some intuition, SNGD represents a significant step forward in making geometric optimization accessible for a broad class of statistical models.

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