Geodesic acceleration and the small-curvature approximation for\n nonlinear least squares

Mark K. Transtrum, James P. SethnaarXiv 2012 · DOI · arXiv

Introduction

In scientific computing, fitting complex models to experimental data typically involves minimizing a sum-of-squares cost function. The Levenberg-Marquardt (LM) algorithm has long been the industry standard for these nonlinear least squares problems. However, LM frequently encounters performance bottlenecks in regions of parameter space characterized by "narrow, winding canyons," where the algorithm may exhibit slow, oscillatory behavior and require excessive Jacobian evaluations.

While previous research suggested that "geodesic acceleration"—a second-order correction term—could mitigate these issues, the method was often couched in the abstract language of differential geometry. This paper provides a rigorous theoretical foundation for geodesic acceleration, deriving it through a straightforward perturbation expansion and proving its global convergence within a standard optimization framework.

The Small-Curvature Approximation

The traditional justification for the Gauss-Newton method (and by extension, LM) is the "small-residual approximation," which assumes the model fits the data nearly perfectly at the minimum. The authors propose a more robust alternative: the small-curvature approximation.

This approximation posits that the model manifold is relatively flat, meaning the extrinsic curvature is small. Unlike the small-residual assumption, the small-curvature approximation:

  1. Is Data-Independent: It depends only on the model structure, not the specific data being fit.
  2. Is Robust to Poor Fits: It remains valid even when the best-fit residuals are large.
  3. Is Globally Applicable: It applies throughout the entire optimization process, not just in the region near the global minimum.

This insight provides a much broader justification for why LM is effective across a wide range of physical models, even those with poor fits, and identifies the geometric conditions under which the algorithm excels.

Deriving Geodesic Acceleration

The authors extend the standard LM step by incorporating a second-order term. Instead of a simple linear step $\delta\theta_1$, the proposed step is defined as:

$$\delta\theta = \delta\theta_1 + \delta\theta_2$$

Where:

  • $\delta\theta_1$ (Geodesic Velocity): This represents the standard Levenberg-Marquardt step.
  • $\delta\theta_2$ (Geodesic Acceleration): This is the new correction term, calculated using the directional second derivative of the residuals.

Crucially, calculating the full Hessian (the matrix of second derivatives) is computationally prohibitive for large-scale models. However, geodesic acceleration only requires a directional second derivative. This can be estimated with just one additional evaluation of the residuals—a negligible cost compared to the $N$ evaluations typically required for a Jacobian. This makes geodesic acceleration a "computational bargain," providing second-order convergence benefits for the price of a single function evaluation.

Convergence and Stability

A primary contribution of this work is the adaptation of standard trust-region convergence proofs to include geodesic acceleration. The authors demonstrate that the modified algorithm is globally convergent, meaning it is guaranteed to find a local minimum (a point where the gradient is zero) under standard assumptions.

To ensure stability, the algorithm includes a specific check: if the acceleration term $\delta\theta_2$ becomes too large relative to the velocity term $\delta\theta_1$, the step is constrained. This prevents the algorithm from flying off into unphysical parameter regions when the small-curvature approximation momentarily fails. In practice, a stability parameter (typically $\alpha \approx 0.75$) is used to maintain this balance.

Conclusion

By bridging the gap between high-level information geometry and practical optimization, this paper elevates geodesic acceleration from a heuristic tweak to a mathematically sound extension of the Levenberg-Marquardt algorithm. The introduction of the small-curvature approximation explains the success of these methods on a deeper level, offering a path toward more efficient and robust model fitting in fields as diverse as physics, systems biology, and engineering. For researchers dealing with "sloppy" models or difficult convergence, this second-order boost offers a way to turn a zig-zagging crawl into a smooth glide toward the minimum.

Summary updated

Abstract

It has been shown numerically that the performance of the Levenberg-Marquardt\nalgorithm can be improved by including a second order correction known as the\ngeodesic acceleration. In this paper we give the method a more sound\ntheoretical foundation by deriving the geodesic acceleration correction without\nusing differential geometry and showing that the traditional convergence proofs\ncan be adapted to incorporate geodesic acceleration. Unlike other methods which\ninclude second derivative information, the geodesic acceleration does not\nattempt to improve the Gauss-Newton approximate Hessian, but rather is an\nextension of the small-residual approximation to cubic order. In deriving\ngeodesic acceleration, we note that the small-residual approximation is\ncomplemented by a small-curvature approximation. This latter approximation\nprovides a much broader justification for the Gauss-Newton approximate Hessian\nand Levenberg-Marquardt algorithm. In particular, it is justifiable even if the\nbest fit residuals are large, is dependent only on the model and not on the\ndata being fit, and is applicable for the entire course of the algorithm and\nnot just the region near the minimum.\n
BibTeX
@misc{transtrum2012geodesic,
  author = {Mark K. Transtrum and James P. Sethna},
  title = {{Geodesic acceleration and the small-curvature approximation for\textbackslash\{\}n nonlinear least squares}},
  year = {2012},
  eprint = {1207.4999},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1207.4999},
}
Figure