Comparison of Numerical Solvers for Differential Equations for Holonomic Gradient Method in Statistics

Nobuki Takayama, Takaharu Yaguchi, Yi Zhang

Introduction

The Holonomic Gradient Method (HGM) has emerged as a powerful framework in statistics for evaluating complex normalizing constants. By identifying a system of linear ordinary differential equations (ODEs) that a target integral satisfies, HGM transforms a difficult integration problem into a numerical initial value problem. However, a significant challenge arises in "unstable HGM problems," where the desired statistical function is not the dominant solution of the ODE system. In such scenarios, standard numerical solvers often fail as microscopic errors trigger the exponential growth of "fake" dominant solutions. This paper evaluates various numerical strategies to overcome these instabilities.

Numerical Approaches

The study compares several classes of solvers across different computational environments (Julia, Mathematica, Risa/Asir):

  1. Standard Local Solvers: Explicit and Implicit Runge-Kutta (RK/IRK) and multi-step methods.
  2. Spectral Methods: Approximation using Chebyshev polynomials via packages like ApproxFun and chebfun.
  3. The Defusing Method (Filter Method): A heuristic algorithm that identifies "exploding" eigenvalues in the system's transition matrix and projects the initial value vector onto a subspace that excludes these growth components.
  4. Sparse Interpolation/Extrapolation: Global methods that treat the ODE as a generalized boundary value problem, minimizing a residual loss function across a set of data points using basis functions derived from the ODE’s local asymptotic expansion.

The Challenge of Numerical Instability

The primary obstacle in HGM is the "dominance trap." If the target function decays while an alternative solution to the same ODE grows, standard step-by-step solvers like RK45 inevitably diverge. This is clearly demonstrated using the Airy function ($Ai(t)$) benchmark.

Table 1: Rapid error accumulation in standard Runge-Kutta solvers for the Airy function benchmark.

As shown in Table 1, standard Runge-Kutta methods produce catastrophic errors as the parameter $t$ increases. By the time $t$ reaches 70, the error magnitudes grow from $10^{-31}$ to $10^{-30}$ in just 10 steps, quickly overwhelming the true value of the function and rendering the results useless for statistical inference.

Specialized Solutions and Results

To mitigate these issues, the authors demonstrate the efficacy of global and heuristic methods over traditional local solvers.

The Defusing Method

The defusing method acts as a stabilizer by periodically correcting the solution vector to ensure it remains within the subspace of the desired non-dominant solution.

Figure 1: The Airy differential equation solved via the defusing method, successfully avoiding numerical blow-up.

As illustrated in Figure 1, this approach allows for a stable numerical representation of the Airy function over a wide domain, preventing the typical divergence seen in local solvers. While effective, the authors note that this remains a heuristic approach requiring further theoretical refinement for rigorous error bounding.

Sparse Interpolation and High-Rank Problems

For high-rank problems, such as calculating the Euler characteristic of random manifolds (a rank 11 ODE), sparse interpolation methods proved superior. By utilizing basis functions that mimic known asymptotic behavior, these methods can achieve high accuracy even with noisy input data. For example, in MIMO WiFi outage probability calculations ($H_n^k$), Sparse Interpolation Method B achieved a relative error of $10^{-12}$ despite significant random noise in the input data.

Conclusion

The choice of numerical solver is critical for the success of the Holonomic Gradient Method in statistics. While standard solvers are sufficient for dominant solutions, unstable problems require global approaches or specialized filtering techniques like defusing. The study highlights that implicit methods and global optimization strategies offer significantly wider valid intervals for solving the complex ODEs found in modern statistical applications.

Summary updated

Abstract

Definite integrals with parameters of holonomic functions satisfy holonomic systems of linear partial differential equations. When we restrict parameters to a one dimensional curve, the system becomes a linear ordinary differential equation (ODE) with respect to a curve in the parameter space. We can evaluate the integral by solving the linear ODE numerically. This approach to evaluate numerically definite integrals is called the holonomic gradient method (HGM) and it is useful to evaluate several normalizing constants in statistics. We will discuss and compare methods to solve linear ODE's to evaluate normalizing constants.
BibTeX
@misc{takayama2021comparison,
  author = {Nobuki Takayama and Takaharu Yaguchi and Yi Zhang},
  title = {{Comparison of Numerical Solvers for Differential Equations for Holonomic Gradient Method in Statistics}},
  year = {2021},
  eprint = {2111.10947},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2111.10947},
}
Figure