针对大规模非线性最小二乘问题,提出高效降维的LM算法,降低计算开销。
Adaptive Hybrid Subspace Levenberg Marquardt Algorithm with Adequacy Monitor for Large Scale Least Squares Problems

- 构建融合梯度、记忆、克里洛夫子空间与随机曲率信息的低维子空间
- 通过谱化阻尼步在子空间内求解,每轮迭代成本显著降低
- 自适应充分性监控器动态扩展子空间,适合高维神经网络训练
Levenberg-Marquardt (LM) 算法是求解非线性最小二乘问题最常用的方法,兼具梯度下降的鲁棒性与高斯-牛顿法的快速局部收敛性。然而,其在大规模问题中计算成本过高,因每轮需求解大型阻尼线性系统,且传统步长接受策略常需重复求解以调整阻尼参数。尽管如此,许多大规模最小二乘问题具有有效低维结构:仅有少量参数方向被数据强约束。本文提出自适应混合子空间 LM(HSLM)算法,从梯度、记忆、克里洛夫子空间和随机曲率信息中构建低维子空间,并在该子空间内计算谱化阻尼的 LM 步。方法的关键特征是确定性充分性监控器,可量化降维空间捕获的下降信息,并在必要时自适应扩充子空间。步长接受与阻尼调整解耦:Armijo 回溯决定接受步长,而实际与预测下降比仅用于更新阻尼参数,避免步长接受过程中的重复求解。理论证明了 HSLM 全局收敛至驻点,并具备局部线性和超线性收敛性。数值实验表明,该算法在神经网络训练任务中,收敛行为与经典 LM 及克里洛夫子空间 LM(KSLM)相当,但每轮迭代成本大幅降低,且随参数维度增加优势愈发明显。
原文摘要 · Abstract (English)
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.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。