math.NAAug 26, 2026

Adaptive Hybrid Subspace Levenberg Marquardt Algorithm with Adequacy Monitor for Large Scale Least Squares Problems

Authors: M. Duc Hoang, Timothy J. Lewis

Organizations: Department of Mathematics, University of California, Davis, Davis, CA, USA

Read PDF
Ask AI
Cite

Copy citation

DOINot available for this paper

Abstract

The Levenberg-Marquardt (LM) algorithm is the most widely used method for solving nonlinear least-squares problems, as it combines the robustness of steepest descent with the fast local convergence of the Gauss-Newton method. However, its computational cost can become prohibitive for large-scale problems because each iteration requires solving a large damped linear system, and conventional step acceptance strategies may require repeated solves as the damping parameter is adjusted. Despite this computational challenge, many large-scale least-squares problems exhibit effective low-dimensional structure, with only a small number of parameter-space directions strongly informed by the data. We propose an adaptive hybrid subspace Levenberg-Marquardt (HSLM) algorithm that constructs a low-dimensional subspace from complementary sources of gradient, memory, Krylov-subspace, and randomized curvature information and computes a spectrally damped LM step within this subspace. A distinguishing feature of the method is a deterministic adequacy monitor that quantifies how much descent information is captured by the reduced space and adaptively enriches the subspace when necessary. Step acceptance is decoupled from damping adjustment: Armijo backtracking determines the accepted step length, while the ratio of actual to predicted reduction is used solely to update the damping parameter, thereby avoiding repeated damped-system solves during step acceptance. For the HSLM algorithm, we establish global convergence to stationarity and prove local linear and superlinear convergence. Numerical experiments on neural-network training problems show that HSLM achieves convergence behavior comparable to classical and Krylov subspace LM (KSLM) while substantially reducing per-iteration computational cost, with increasing advantages observed as the parameter dimension grows.

Figures & tables

NetworkArchitectureTrainable ParametersTraining data size
17→35→20→17\rightarrow 35\rightarrow 20\rightarrow 1102110000
27→60→25→17\rightarrow 60\rightarrow 25\rightarrow 1203120000
37→80→40→17\rightarrow 80\rightarrow 40\rightarrow 1392140000
Table 1: Neural network configurations with increasing model complexity and training data size. Network architecture is reported as the number of neurons in the input layer, the two hidden layers, and the output layer, respectively.
Figure 1: Training results for five representative runs of network 3 for nonlinear function approximation. A1-A2. Levenberg–Marquardt algorithm. B1-B2. Krylov subspace Levenberg–Marquardt algorithm. C1-C2. Hybrid subspace Levenberg–Marquardt algorithm. The gray dashed line indicates the variance of the added noise, σ2≈0.622\sigma^{2}\approx 0.622 . These results indicate that HSLM achieves convergence behavior comparable to the classical LM and Krylov-subspace LM algorithms.
 Classical LMKrylov Subspace LMHSLM
 IterationTime / Iteration (s)IterationTime / Iteration (s)IterationTime / Iteration (s)
Network 141.70.49241.10.26252.70.131
Network 241.62.36739.41.73836.90.615
Network 334.915.83036.513.08235.43.665
Table 2: Comparison in Computational Performance of Neural Network Training Algorithms
Appendix figures & tables6 assets

Supplementary material from the paper’s appendix.

Appendix

SettingKrylov LMHybrid reduced-subspace LM
Initial Krylov directionsUp to maximum—
Initial random probes—0.01n0.01n
Krylov directions per expansion—0.02n0.02n
Random probes per expansion—0.01n0.01n
Adequacy threshold—ηmin⁡=0.99\eta_{\min}=0.99
Lanczos tolerance10−510^{-5}10−510^{-5}
Appendix
Table 3: Numerical settings used for the Krylov and adaptive hybrid reduced-subspace LM methods.
Figure 5
Figure 6
Figure 7
Figure 8
 Classical LMKrylov Subspace LMHSLM
 IterationTime / Iteration (s)IterationTime / Iteration (s)IterationTime / Iteration (s)
Network 143.91.04445.30.94149.80.464
Network 238.23.23537.13.79037.11.221
Network 334.915.83036.513.08235.43.665
Appendix
Table 4: Comparison between algorithms for neural-network training
More in this topic

Nonconvex Optimization

Nonconvex optimization develops methods for problems whose objectives or constraints can have multiple local optima, saddle points, or nonsmooth structure.

See all 147 papers

Explore similar work

CardsList

  1. Subspace Levenberg Marquardt Algorithms in Training Neural Networks

    Sep 1, 2026M. Duc HoangNeural Network OptimizationKrylov Subspace Methods

    Department of Mathematics, University of California, Davis, Davis, CA, USA

  2. Hybrid Joint-Selective Optimization: Reduced-Space Levenberg-Marquardt Refinement of Low-Dimensional Parameters of Interest

    Sep 29, 2026Muhammad Luthfi Shahab, Gabriella Alfa Indahsari, Imam Mukhlash +1Parameter EstimationSecond-Order Optimization

    Department of Mathematics, Institut Teknologi Sepuluh Nopember, Surabaya, 60111, Indonesia · Department of Mathematics, Khalifa University of Science & Technology, Abu Dhabi, PO Box 127788, United Arab Emirates

  3. Higher-Order Geometric Updates for Levenberg-Marquardt Method via Riemann Normal Coordinates

    Jul 8, 2026Jianing Liu, Dong H. ZhangGauss-Newton OptimizationRiemannian Optimization

    State Key Laboratory of Chemical Reaction Dynamics and Department of Chemical Physics, University of Science and Technology of China, Hefei, 230026, China · State Key Laboratory of Chemical Reaction Dynamics, Dalian Institute of Chemical Physics, Chinese Academy of Sciences, Dalian, 116023, China. · University of Chinese Academy of Sciences, Beijing, 100049, China +1