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

• URL: http://arxiv.org/abs/2608.25524v1
• Date: Wed, 26 Aug 2026 08:33:33 GMT
• Title: Adaptive Hybrid Subspace Levenberg Marquardt Algorithm with Adequacy Monitor for Large Scale Least Squares Problems
• Abstract summary: The Levenberg-Marquardt (LM) algorithm is the most widely used method for solving nonlinear least-squares problems.<n>We propose an adaptive hybrid subspace Levenberg-Marquardt (HSLM) algorithm that constructs a low-dimensional subspace.<n>HSLM achieves convergence behavior comparable to classical and Krylov subspace LM (KSLM) while substantially reducing per-itarity computational cost.
• Score: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• 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.

Related papers

• Sufficient Dimesion Reduction via Generalized Stein's Lemma [2.791614311130759]
  We propose an SDR framework based on the generalized Stein's lemma.<n>The proposed method does not rely on the linearity condition, avoids matrix inversion, and can leverage unlabeled data.<n>We demonstrate that the proposed methods consistently outperform existing approaches across a variety of settings.
  arXiv  Detail & Related papers  (2026-08-15T08:46:45Z)
• Higher-Order Geometric Updates for Levenberg-Marquardt Method via Riemann Normal Coordinates [1.7812378608633406]
  least-squares optimization is central to regression, physics-informed neural networks, and other machine-learning tasks.<n>RNC-LM improves convergence and robustness in curved valleys and rank-deficient problems.<n>It achieves a 34-fold speedup over standard LM on a large-scale machine-learning potential-energy-surface fitting task.
  arXiv  Detail & Related papers  (2026-07-08T16:39:03Z)
• A Convex Quasilinearization Method for Solving Nonlinear PDEs with Physics-Informed Neural Networks [0.0]
  We present a numerical method for the forward solution of nonlinear partial differential equations (PDEs)<n>The method, LiL-Q, is assessed on seven benchmarks, including systems (planestrain elasticity and the incompressible Navier-Stokes equations in two and three dimensions) and steady flow with heterogeneous permeability.
  arXiv  Detail & Related papers  (2026-06-16T17:09:59Z)
• High-Dimensional Change-Point Detection via Angular Kernel Statistics [9.486498387993718]
  We study change-point detection for high-dimensional data in regimes where inference must be performed from small batches of observations.<n>Our primary focus is the high-dimensional, low sample size (HDLSS) regime, where the sequence length is fixed while the ambient dimension diverges.<n>We propose a dimension-averaged angular kernel scan framework for detecting marginal distributional shifts.
  arXiv  Detail & Related papers  (2026-05-25T13:45:38Z)
• Pack only the essentials: Adaptive dictionary learning for kernel ridge regression [69.32538992633842]
  One of the major limits of kernel ridge regression (KRR) is that storing and manipulating the kernel matrix K_n for n samples requires O(n2) space.<n>INK-Estimate is an algorithm that processes the dataset incrementally and updates RLS, effective dimension, and Nystrom approximations on-the-fly.<n>In this paper we introduce SQUEAK, a new algorithm that builds on INK-Estimate but uses unnormalized RLS.
  arXiv  Detail & Related papers  (2026-04-24T09:22:09Z)
• Deep Learning for Subspace Regression [42.94349364701736]
  A practical way to apply such a scheme is to compute subspaces for a selected set of parameters in the computationally demanding offline stage.<n>For realistic problems the space of parameters is high dimensional, which renders classical strategies infeasible or unreliable.<n>We propose to relax the problem to regression, introduce several loss functions suitable for subspace data, and use a neural network as an approximation to high-dimensional target function.
  arXiv  Detail & Related papers  (2025-09-27T10:56:03Z)
• Constrained Optimization via Exact Augmented Lagrangian and Randomized Iterative Sketching [55.28394191394675]
  We develop an adaptive inexact Newton method for equality-constrained nonlinear, nonIBS optimization problems. We demonstrate the superior performance of our method on benchmark nonlinear problems, constrained logistic regression with data from LVM, and a PDE-constrained problem.
  arXiv  Detail & Related papers  (2023-05-28T06:33:37Z)
• Decomposed Diffusion Sampler for Accelerating Large-Scale Inverse Problems [64.29491112653905]
  We propose a novel and efficient diffusion sampling strategy that synergistically combines the diffusion sampling and Krylov subspace methods. Specifically, we prove that if tangent space at a denoised sample by Tweedie's formula forms a Krylov subspace, then the CG with the denoised data ensures the data consistency update to remain in the tangent space. Our proposed method achieves more than 80 times faster inference time than the previous state-of-the-art method.
  arXiv  Detail & Related papers  (2023-03-10T07:42:49Z)
• Gaussian process regression and conditional Karhunen-Lo\'{e}ve models for data assimilation in inverse problems [68.8204255655161]
  We present a model inversion algorithm, CKLEMAP, for data assimilation and parameter estimation in partial differential equation models. The CKLEMAP method provides better scalability compared to the standard MAP method.
  arXiv  Detail & Related papers  (2023-01-26T18:14:12Z)
• Covariance-Free Sparse Bayesian Learning [62.24008859844098]
  We introduce a new SBL inference algorithm that avoids explicit inversions of the covariance matrix. Our method can be up to thousands of times faster than existing baselines. We showcase how our new algorithm enables SBL to tractably tackle high-dimensional signal recovery problems.
  arXiv  Detail & Related papers  (2021-05-21T16:20:07Z)
• Pushing the Envelope of Rotation Averaging for Visual SLAM [69.7375052440794]
  We propose a novel optimization backbone for visual SLAM systems. We leverage averaging to improve the accuracy, efficiency and robustness of conventional monocular SLAM systems. Our approach can exhibit up to 10x faster with comparable accuracy against the state-art on public benchmarks.
  arXiv  Detail & Related papers  (2020-11-02T18:02:26Z)
• Effective Dimension Adaptive Sketching Methods for Faster Regularized Least-Squares Optimization [56.05635751529922]
  We propose a new randomized algorithm for solving L2-regularized least-squares problems based on sketching. We consider two of the most popular random embeddings, namely, Gaussian embeddings and the Subsampled Randomized Hadamard Transform (SRHT)
  arXiv  Detail & Related papers  (2020-06-10T15:00:09Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.