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

M. Duc Hoang; Timothy J. Lewis

Source-linked AI summary

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

M. Duc Hoang, Timothy J. Lewis

arXiv:2608.25524v1Aug 26, 2026math.NAcs.LGmath.OC

TL;DR

Large-scale LM can require expensive damped-system solves, while existing reduced-space methods may not deterministically maintain adequate descent information. HSLM combines complementary subspace sources with adequacy monitoring, curvature-adaptive reduced damping, and decoupled acceptance and damping updates; theory and neural-network experiments report convergence comparable to full-space LM at lower linear-algebra cost as dimension increases.

Problem
Large-scale LM is costly, and existing subspace methods may lack deterministic mechanisms for maintaining adequate descent information as local geometry changes.
Method
HSLM adaptively combines gradient, memory, Krylov, and randomized curvature information, monitors projected-gradient adequacy, and uses reduced curvature-adaptive damping with decoupled step acceptance.
Results
HSLM preserves convergence behavior comparable to full-space LM while substantially reducing linear-algebra cost as parameter dimension increases.
Takeaways & Limitations
Adaptive hybrid subspace construction retains favorable LM convergence properties while improving computational efficiency for large-scale problems.
Takeaways & Limitations
The adequacy monitor ensures gradient capture but does not directly guarantee curvature capture.

Abstract

from arXiv · show

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.

1 INTRODUCTION

Large-scale nonlinear least-squares problems make full-space LM expensive, despite low-dimensional structure that can support reduced-space methods. HSLM addresses adequacy and efficiency through adaptive hybrid subspaces, deterministic monitoring, decoupled step acceptance, and convergence guarantees.

Full-space LM becomes computationally expensive in high-dimensional problems because each iteration solves large Jacobian- or Hessian-related linear systems.
Many inverse problems constrain only a relatively small parameter-space subspace, motivating reduced-space and low-rank LM variants.
Existing subspace methods may lack deterministic mechanisms for maintaining adequate descent and curvature information as optimization progresses.
HSLM combines gradient, previous-step, curvature-probe, and related subspace information to construct a compact adaptive subspace.
A projected-gradient adequacy monitor enriches the subspace when needed, while Armijo backtracking handles acceptance and reduction ratios update damping without repeated solves.
The analysis establishes global convergence to stationarity and local linear and superlinear convergence, with neural-network experiments comparing HSLM against classical and Krylov subspace LM.

2 BACKGROUND AND NOTATION

The background formulates nonlinear least-squares optimization through residuals and Jacobians, then motivates LM damping as a robustness improvement over Gauss–Newton.

Nonlinear least-squares problems represent an objective through a residual vector r(x), which is linearized using its Jacobian at each iteration.
The Gauss–Newton Hessian approximation is H(xk) ≈ J(xk)⊤J(xk), and Gauss–Newton has second-order local convergence under small residuals and full-rank Jacobians.
Gauss–Newton may fail with an ill-conditioned Jacobian or a distant initial guess, motivating Levenberg–Marquardt damping for greater robustness.
LM adjusts damping downward after effective residual reduction and upward after insufficient reduction, interpolating between Gauss–Newton and steepest descent.

3 HYBRID SUBSPACE LEVENBERG MARQUART ALGORITHM

HSLM adaptively builds and monitors a low-dimensional hybrid subspace, solves a curvature-adaptively damped reduced LM problem, and separates step acceptance from damping updates.

Subspace construction: HSLM constructs an adaptive subspace from gradient, recent optimization history, Krylov/Lanczos directions, and randomized curvature probes.
Adequacy monitoring: The deterministic adequacy monitor measures projected-gradient energy and enriches the basis until a prescribed threshold is satisfied.
Reduced LM system: The reduced Jacobian and its singular value decomposition define a low-dimensional LM system whose search direction is mapped back to the original parameter space.
Curvature-adaptive damping: Curvature-dependent diagonal damping assigns stronger regularization to larger-singular-value directions while keeping damping positive and weaker along flatter directions.
Step acceptance and damping updates: Armijo backtracking determines the accepted step length, while the gain ratio updates damping, avoiding repeated damped-system solves during acceptance.

4 CONVERGENCE ANALYSIS

The analysis establishes convergence of HSLM by combining adaptive-subspace adequacy, reduced-system conditioning, and Armijo line search. Under stronger local approximation conditions, the method achieves linear or superlinear convergence.

Lipschitz gradient continuity guarantees sufficiently small step lengths satisfy Armijo decrease, allowing backtracking to terminate.
The deterministic adequacy condition ensures the reduced subspace retains a uniformly positive fraction of full-gradient information.
For µk > 0, regularization makes the reduced matrix symmetric positive definite, so the reduced LM step exists uniquely.
Under adequacy, the reduced LM step is a strict descent direction whenever the full gradient is nonzero.
Under Assumptions 1–4, every infinite iterate sequence has a subsequence whose gradient norm converges to zero.
With eventually accepted full steps, bounded combined approximation errors yield local linear convergence, while vanishing errors yield superlinear convergence.
The local theorem specifies linear convergence when θk remains below one and superlinear convergence when θk tends to zero.

5 NUMERICAL EXPERIMENTS

Experiments train feedforward neural networks on a scalable nonlinear function-approximation benchmark and compare LM, KSLM, and HSLM. HSLM attains comparable errors and convergence while reducing per-iteration cost, increasingly so for larger networks.

Experimental setup: The experiments compare classical LM, Krylov-subspace LM, and HSLM across network and dataset sizes using errors, convergence, and computational cost.
Experimental setup: The benchmark uses a two-hidden-layer MLP with hyperbolic-tangent hidden activations and a linear output layer.
Experimental setup: Neural-network problem dimension increases systematically through three architectures and training-set sizes while preserving the same approximation objective.
Experimental setup: The maximum subspace dimension for KSLM and HSLM is limited to 10% of the parameter dimension.
Results: All three algorithms achieve similar final training errors approaching the added-noise variance, indicating approximation to approximately the noise level.
Results: HSLM reduces average execution time per iteration relative to classical LM by approximately 3.7, 3.8, and 4.3 factors across the networks.
Results: Relative to Krylov-subspace LM, HSLM achieves speedups of approximately 2.0, 2.8, and 3.6 for Networks 1, 2, and 3.
Results: The adequacy monitor generally enables substantially smaller subspaces than KSLM while satisfying the projected-gradient adequacy criterion.

6 DISCUSSION

HSLM combines complementary subspace directions with adaptive dimension control and a deterministic adequacy monitor, while separating step acceptance from damping updates. Experiments indicate comparable convergence to full-space LM with lower parameter-dependent linear-algebra cost, especially as dimension grows.

Adaptive hybrid construction: HSLM combines gradient, memory, Krylov/Lanczos, and randomized curvature directions in an adaptive hybrid subspace.The framework allows problem-dependent candidate directions while retaining convergence guarantees for general hybrid constructions.
Adequacy monitoring: The adequacy monitor controls subspace enrichment by measuring whether the reduced space captures a prescribed fraction of gradient information.It does not directly assess whether all curvature directions relevant to an effective LM step are captured.
Step acceptance and damping: Armijo backtracking selects the step length, while the gain ratio updates damping, avoiding repeated damped-system solves during step acceptance.The predicted reduction remains positive for accepted Armijo step lengths and is evaluated in reduced coordinates.
Scope and limitations: Performance depends on the quality and diversity of candidate directions, and other problems may require different problem-specific directions.The present hybrid construction combines gradient, memory, Krylov/Lanczos, and randomized curvature information to address this dependence.
Computational scaling: At fixed training-set size, HSLM becomes increasingly advantageous as parameter dimension grows, reducing parameter-dependent linear-algebra costs.The experiments do not examine increasing training-set size, where Jacobian evaluations and matrix-vector products are expected to become more important.
Scope and limitations: The numerical study is limited to neural-network regression, leaving mini-batch, matrix-free, larger-training-set, and inverse-problem applications for future work.These settings may involve different Jacobian and curvature structures.
Overall outcome: Overall, HSLM preserves convergence behavior comparable to full-space LM while substantially reducing linear-algebra cost as parameter dimension increases.The results support retaining favorable LM-type properties while improving computational efficiency for large-scale problems.

A.1 Krylov-Subspace Levenberg–Marquardt Method

The methods construct reduced LM steps from Krylov and hybrid candidate subspaces, using implicit Gauss–Newton products, orthogonalization, and adaptive enrichment. Backtracking handles step lengths while reduced-system reuse lowers rejected-iteration cost.

Krylov-subspace construction: The Krylov basis starts with the normalized gradient and is generated by the Lanczos process using implicit Gauss–Newton matrix–vector products.The products avoid explicitly forming the Gauss–Newton matrix.
Krylov-subspace construction: The Krylov subspace is capped at dmax = ⌊0.1n⌋ or terminated when the Lanczos residual satisfies β_j ≤ 10^-5.
Reduced LM solve: The reduced LM system is solved in Krylov coordinates, and the full-space step is recovered as s_k = Q_k z_k.If a trial step is rejected, the previously computed Krylov basis is retained while only the reduced system is updated.
Hybrid subspace construction: HSLM combines Lanczos directions, random curvature probes, and recent accepted steps, then removes dependent directions through thin QR factorization.Its initial candidate subspace includes ⌊0.01n⌋ random curvature probes and s_{k−1}.
Adaptive enrichment: The adequacy monitor measures the fraction of squared gradient norm captured by the reduced basis and enriches it with additional Lanczos directions and random probes when needed.The target adequacy threshold is η_sub ≥ 0.99, with a maximum dimension of ⌊0.1n⌋.
Step control: Armijo backtracking starts with t_k = 1 and evaluates at most ten trial step lengths, an implementation safeguard outside the convergence theorem.The stated termination conditions are objective reduction below 0.005 or 10000 iterations.

B TRAINING AND VALIDATION RESULTS FOR NETWORK 1 & 2

Experiments on Networks 1 and 2 compare classical LM, Krylov-subspace LM, and HSLM under the same initial guess. The five representative training results show comparable convergence behavior across the three algorithms.

Experimental comparison: Five representative training results from Networks 1 and 2 use the same initial guess to compare LM, KSLM, and HSLM.

C ADAPTIVE SUBSPACE DIMENSION SELECTION USING DETERMINISTIC ADEQUACY MONITOR

HSLM selects its reduced-space dimension adaptively during optimization rather than fixing it at 10% of the parameter dimension. The adequacy monitor triggers enrichment when projected gradient information is insufficient, while generally maintaining adequacy with a smaller subspace.

Adaptive dimension comparison: The experiments compare subspace dimensions selected by KSLM and HSLM across iterations for three neural networks of increasing complexity.Upper panels show representative optimization runs, while lower panels show the corresponding projected-gradient quantity.
Adequacy monitoring: HSLM enriches its subspace when the adequacy criterion fails during optimization.
Adaptive dimension comparison: KSLM uses a fixed subspace equal to 10% of the parameter dimension, whereas HSLM dynamically adjusts its dimension.
Adaptive dimension comparison: HSLM generally satisfies the adequacy criterion using a substantially smaller subspace than KSLM.

D INFLUENCE OF CANDIDATE BASIS SOURCES IN SUBSPACE CONSTRUCTION ON ALGORITHM PERFORMANCE

The candidate-source experiments compare randomized curvature information alone, curvature plus the gradient direction, and full HSLM construction. Adding structured directions improves convergence behavior, with full HSLM producing the strongest reported performance among the variants.

Compared basis constructions: The experiments compare randomized Hessian/Gauss–Newton probes alone, probes plus the gradient direction, and HSLM across representative Network 3 runs.
Structured directions: Randomized curvature directions alone may omit important descent information, while adding the gradient direction produces more reliable convergence toward a local optimum.The reduction in training and validation error remains slow for the gradient-augmented variant.
Full hybrid construction: HSLM reaches the lowest training and validation errors more rapidly and consistently across five representative runs.
Full hybrid construction: Augmenting randomized curvature information with additional structured directions improves convergence behavior, with full HSLM strongest among the three variants.

E COMPUTATIONAL EFFICIENCY OF HSLM IN INCREASING PARAMETER DIMENSION AT FIXED TRAINING-SET SIZE

The experiments compare HSLM with classical and hybrid Krylov-subspace LM on noisy, overparameterized neural networks. All methods reach similar final training errors, while HSLM reduces execution time and scales more effectively as network size increases.

Experimental setup: The evaluation compares HSLM with hybrid Krylov-subspace and classical Levenberg–Marquardt algorithms on overparameterized feedforward neural networks.The setup uses 40,000 training samples with additive Gaussian noise at 5% of the target-signal standard deviation.
Experimental setup: Average iterations and execution time per iteration are summarized over 50 independent trials in Table 4.
Accuracy: All three algorithms achieve similar final training errors, approximately equal to the variance of the additive noise.The results indicate that the remaining error is primarily due to irreducible noise.
Computational efficiency: HSLM exhibits comparable convergence behavior while scaling more effectively as network size increases.
Computational efficiency: Relative to classical LM, HSLM reduces execution time by approximately factors of 2.3, 2.6, and 4.3 for Networks 1, 2, and 3, respectively.