Source-linked AI summary
Improvements to the Levenberg-Marquardt algorithm for nonlinear least-squares minimization
Mark K. Transtrum, James P. Sethna
TL;DR
Nonlinear least-squares fitting can be slow in narrow canyons and unreliable from poor initial guesses. The paper modifies Levenberg–Marquardt with geodesic acceleration, controlled uphill steps, and Broyden Jacobian updates, then compares these variants across difficult test problems. Geodesic acceleration generally improves success, fit quality, and speed, while the bold acceptance criterion and Broyden update can accelerate convergence at greater risk of becoming lost.
Problem
Levenberg–Marquardt can converge slowly in narrow canyons or fail from distant initial guesses, especially on large problems with many parameters.
Method
The paper improves Levenberg–Marquardt with geodesic acceleration, controlled uphill-step acceptance, and rank-deficient Broyden updates to the Jacobian.
Results
Geodesic acceleration tends to improve success, fit quality, and speed, whereas bold acceptance and Broyden updates can speed convergence but increase the chance of becoming lost.
Takeaways & Limitations
The most effective variant depends on whether fit quality or convergence speed matters more, so implementations should let users adapt algorithm parameters to each problem.
Takeaways & Limitations
Accepting uphill moves has no convergence guarantee and can reduce success rate and fit quality from difficult starting points.
Abstract
from arXiv · showhide
When minimizing a nonlinear least-squares function, the Levenberg-Marquardt algorithm can suffer from a slow convergence, particularly when it must navigate a narrow canyon en route to a best fit. On the other hand, when the least-squares function is very flat, the algorithm may easily become lost in parameter space. We introduce several improvements to the Levenberg-Marquardt algorithm in order to improve both its convergence speed and robustness to initial parameter guesses. We update the usual step to include a geodesic acceleration correction term, explore a systematic way of accepting uphill steps that may increase the residual sum of squares due to Umrigar and Nightingale, and employ the Broyden method to update the Jacobian matrix. We test these changes by comparing their performance on a number of test problems with standard implementations of the algorithm. We suggest that these two particular challenges, slow convergence and robustness to initial guesses, are complimentary problems. Schemes that improve convergence speed often make the algorithm less robust to the initial guess, and vice versa. We provide an open source implementation of our improvements that allow the user to adjust the algorithm parameters to suit particular needs.
1. Introduction
Nonlinear least-squares fitting is difficult because Gauss–Newton methods can fail from poor initial guesses and converge slowly through narrow cost-surface canyons. Levenberg–Marquardt addresses these challenges by damping the update, while the paper investigates further improvements.
- Problem: Nonlinear least-squares minimization seeks parameter values that minimize a sum-of-squares cost function.In data fitting, residuals measure weighted deviations between model predictions and observations; the cost corresponds to the negative log-likelihood under Gaussian errors.
- Problem: Gauss–Newton can take uncontrolled steps from poor initial guesses because J^T J is often ill-conditioned, with eigenvalues spanning six orders of magnitude or more.Far from the best fit, its direction can be nearly orthogonal to the direction the algorithm should take.
- Method: Levenberg–Marquardt damps J^T J to interpolate between gradient descent for avoiding evaporation and Gauss–Newton for rapid local convergence.A large damping parameter produces a small gradient-direction step, while a small parameter near a solution enables Gauss–Newton convergence.
- Problem: Sloppy models create plateaus where parameter changes barely affect model behavior, causing parameter evaporation and poor fits at infinite parameter values.These plateau solutions can be fixed points of the cost while remaining unsatisfactory for fitting and interpretation.
- Problem: Narrow canyons can make fitting sluggish, with aspect ratios greater than 1000 : 1 requiring very small steps along the trough.The challenges of avoiding evaporation and accelerating canyon traversal often conflict: methods that improve one can worsen the other.
- Method: The paper evaluates geodesic acceleration, controlled uphill-step acceptance, and Jacobian updates on standard and large test problems using diverse starting points.The tests use Minpack-2, NIST reference datasets, and several larger problems; broad starting-point distributions make smaller problems comparably difficult.
2. The Levenberg-Marquardt algorithm
The Levenberg-Marquardt algorithm combines damped gradient-like steps with Gauss-Newton convergence, but its performance depends on damping, scaling, and stopping choices. The paper modifies these components to improve speed and stability across different fitting problems.
- Basic algorithm: The algorithm iteratively updates the function and Jacobian, scaling matrix, damping parameter, proposed step, acceptance decision, and stopping checks.These five stages define the basic implementation described in the paper.
- Proposed improvements: The paper modifies the parameter step with geodesic acceleration, changes step acceptance, and updates the Jacobian to improve algorithm speed and stability.These changes target the algorithm's main modifiable components beyond damping selection.
- Choosing the damping parameter: Because step size decreases monotonically with λ, increasing damping produces smaller descent steps and makes the method a trust-region algorithm.The damping parameter can be adjusted directly or indirectly by first selecting an acceptable step size.
- Choosing the damping parameter: No λ-selection method consistently outperforms the others; performance depends strongly on the test problem, with direct and indirect methods each favored in different cases.Indirect methods perform relatively well on problems B and C, whereas direct methods can be more efficient where λ must change substantially.
- Damping matrix: A minimum damping value provides a compromise that preserves canyon-tracking efficiency while improving robustness to parameter evaporation.The authors report that this choice is both robust to parameter evaporation and efficient at finding good fits.
- Convergence criteria: The Bates-Watts convergence criterion uses the angle between the residual vector and tangent plane, but it can misdiagnose convergence when narrow model-manifold boundaries cause parameter evaporation.The criterion stops when cos φ falls below a threshold such as 10^-2 or 10^-3, yet cos φ may remain large at an evaporated-parameter best fit.
3. Geodesic Acceleration
The paper augments the Levenberg-Marquardt step with a geodesic acceleration correction based on directional curvature, improving progress through narrow canyons while controlling overly large corrections on flat plateaus.
- Geodesic acceleration: The geodesic acceleration adds higher-order corrections to the usual Levenberg-Marquardt step.The correction is derived by expanding the nonlinear residuals beyond their local linearization.
- Geodesic acceleration: The correction uses only the directional second derivative along the first-order step, avoiding the cost of calculating the full second-derivative array.A finite-difference estimate requires only one additional residual evaluation.
- Geodesic acceleration: Approximating the canyon path with a parabola lets the algorithm follow a winding canyon toward the best fit more accurately.The geodesic acceleration indicates the direction in which the canyon curves.
- Geodesic acceleration: The acceptance condition requires the correction terms to decrease in magnitude; α = 0.75 is usually effective, while α = 0.1 helps difficult problems.This condition treats the proposed step as a convergent truncated perturbation series and limits uncontrolled motion.
- Geodesic acceleration: With the acceptance condition, geodesic acceleration avoids large, untrusted plateau steps and can improve convergence behavior.In the illustrated plateau problem, smaller steps ultimately reach the best fit, whereas standard Levenberg-Marquardt becomes stuck.
- Performance: Geodesic acceleration improved fit quality and success rate while sometimes requiring 70 fewer Jacobian evaluations on average.Using a smaller α could improve results further, but at the cost of more Jacobian evaluations.
4. Uphill steps
The paper allows selected uphill steps to improve progress through narrow canyons and avoid poor local minima, but the resulting speed gains can reduce stability and success rates.
- Acceptance criterion: The modified criterion always accepts downhill moves but conditionally accepts uphill moves based on the proposed velocity’s direction.Acceptance increases as the angle between the proposed velocity and the relevant direction becomes more acute.
- Motivation: Uphill moves provide more possible progress when a narrow canyon contains only a small sliver of downhill steps.Allowing such moves can prevent the optimization from following the valley floor too closely.
- Results: Allowing uphill moves often reaches minima in fewer optimization steps and finds better minima in systems with multiple minima.The optimization can avoid becoming trapped in potholes along the valley floor.
- Results: Bold acceptance can speed up performance by as much as a factor of 30, but success rates often decrease.The speed gain varies across problems and is accompanied by less constrained steps.
- Trade-off: The speed-stability trade-off can be mitigated with geodesic acceleration and a smaller α, though slower convergence results.The paper describes this trade-off as inherent to the problem.
- Scope: Accepting uphill moves is most useful when the algorithm can find a canyon but becomes sluggish en route to the best fit.It is not expected to help when the main difficulty is finding a canyon in the first place.
5. Updating the Jacobian Matrix
The paper reduces Jacobian evaluations with Broyden rank-1 updates, while monitoring approximation quality and periodically recomputing the full Jacobian. This can greatly accelerate convergence but makes the algorithm more likely to get lost.
- Broyden updates: Broyden’s method evaluates the Jacobian initially, then estimates subsequent Jacobians with a rank-1 update from residual and parameter changes.The update can eliminate Jacobian evaluation at every step in principle.
- Broyden updates: After repeated updates degrade the Jacobian approximation, the algorithm recomputes the full Jacobian, typically after one or two rejected steps.Poor approximations can produce inaccurate gradient directions.
- Rank-2 updates: Geodesic acceleration supplies two function evaluations per iteration, enabling an optional rank-2 Jacobian update.The update uses separate rank-1 updates associated with velocity and acceleration steps.
- Performance and limitations: When successful, Broyden updates dramatically reduce Jacobian evaluations, but approximate Jacobians also lower success rates and fit quality by distorting the gradient direction.The rank-2 variant provides little performance gain in practice because velocity and acceleration are often nearly collinear.
- Performance and limitations: The authors recommend Jacobian updating when becoming lost is unlikely or full Jacobian evaluations are prohibitively expensive.They suggest that more sophisticated reevaluation criteria could improve robustness.
6. Conclusion
The conclusion frames nonlinear least-squares fitting as a trade-off between avoiding flat plateaus and traversing narrow canyons. The proposed improvements generally enhance speed or robustness, but their best combination depends on the problem and user priorities.
- Conclusion: Nonlinear least-squares algorithms can become lost on broad plateaus or converge slowly while following narrow canyons toward the best fit.The paper modifies Levenberg-Marquardt to address both difficulties.
- Conclusion: Geodesic acceleration adds a second-order residual correction at minimal additional cost and tends to improve robustness to initial conditions, success rates, fit quality, and speed.The derivation assumes small extrinsic curvature of the model graph.
- Conclusion: Controlled uphill acceptance can greatly speed canyon traversal, while Broyden Jacobian updates reduce computational cost but increase the tendency to become lost.The paper presents these effects as problem-dependent trade-offs.
- Conclusion: Geodesic acceleration generally improves success, fit quality, and speed, whereas uphill acceptance and Broyden updates can be faster but less robust on difficult starts.The most effective variation depends on the problem and whether fit quality or convergence speed matters more.
- Conclusion: The open-source FORTRAN implementation lets users switch improvements on or off and choose among damping-parameter update schemes.This flexibility supports adapting the fitting process to individual models.
Appendix A. Test Problems
The evaluation uses 17 nonlinear least-squares problems from Minpack-2, NIST, prior work, and the authors’ research. Broadly distributed starting points make these mostly small or moderate problems more challenging and expose variation in algorithm performance.
- Test set: The benchmark contains 17 test problems labeled A-Q, drawn from Minpack-2, NIST reference datasets, prior work, and the authors’ research.The problems are summarized in the appendix for comparison with other algorithms.
- Initialization: Starting points are sampled from Gaussian distributions around suggested starts, with widths adjusted until standard algorithms show noticeable performance variation.The study deliberately avoids using standard starting points.
- Problem diversity: The suite spans small fitting problems and larger models, including 130-parameter collocation, 134-parameter coating, 48-parameter systems biology, 32-parameter avalanche, and 81-parameter neural-network problems.These examples range from ordinary data fitting to constrained, differential-equation, and machine-learning formulations.
- Failure modes: Some problems expose specific failure modes, including difficulty far from the minimum, lost t-dependence for large θ3, local minima, and a local minimizer at infinity.For the thermistor problem, a small α in the geodesic-acceleration acceptance criterion helps move toward smaller θ3.
- Additional test cases: The appendix also includes a 27-parameter, 2002-residual variational-wave-function problem and provides the initial-parameter ensembles for further comparisons.The neural-network formulation adds a weak quadratic prior to help avoid parameter evaporation.
Appendix B.1. Measuring Success
The appendix evaluates algorithms using success rate, fit quality, and Jacobian-evaluation efficiency. These measures distinguish claiming convergence, reaching a good fit, and doing so with limited computational effort.
- Success rate: Success rate is the fraction of attempts claiming to find a minimum under the common convergence criterion.It indicates how well an algorithm avoids becoming lost in parameter space and generally finds a minimum within the iteration limit.
- Fit quality: The quality factor compares the final cost C_final with the best known cost C_best and approaches one for the best fit while being exponentially suppressed for poorer fits.For many test problems, it is effectively zero or one because one minimum is much better than the others.
- Computational efficiency: Jacobian evaluations measure convergence efficiency because Jacobian computation often dominates runtime, especially when finite differences are used for many parameters.The benchmark plots the inverse average number of Jacobian evaluations so larger values are preferable.
- Reported comparisons: Figures B.6 and B.7 compare direct and indirect methods across the 17 problems using average success rate and average quality factor, respectively.The quality-factor figure uses the measure defined in Eq. (B.1).
Appendix B.2. Comparison of Standard Methods
The tested schemes for selecting λ show problem-dependent performance: no algorithm consistently outperforms the others, although indirect and direct methods each appear advantageous for some problem classes.
- No algorithm consistently outperforms all others across the test problems.
- An algorithm’s relative success depends strongly on the specific problem.
- Indirect methods collectively outperform direct methods for some problem classes, while direct methods perform better for others.
Appendix B.3. Comparison of methods with acceleration
Geodesic acceleration generally improves algorithm performance across success, fit quality, and speed, with the largest gains in reducing Jacobian evaluations.
- Geodesic acceleration generally improves success, fit quality, and speed across the tested methods.The passage reports only a few exceptions.
- Speedups in Jacobian evaluations reach 70-fold, with most improvements between 2-fold and 10-fold.
Appendix B.4. Comparison of methods with bold acceptance
The bold acceptance variant is evaluated alone and in combination with geodesic acceleration, using a modified criterion that permits selected uphill steps.
- Bold acceptance uses Eq. (22) with b = 2 and is denoted by appending B to the algorithm name.
- The combined geodesic-acceleration and bold-acceptance variant is denoted AB.
Appendix B.5. Comparison of methods with rank-deficient updates
The appendix evaluates rank-deficient Jacobian updates, including Broyden’s rank-1 update and a rank-2 variant combined with geodesic acceleration and bold acceptance.
- Methods with rank-1 updates after accepted steps are evaluated, with Broyden’s update denoted by C.
- A rank-2 update variant combines geodesic acceleration with bold acceptance.