Armijo acceptance with decoupled LM damping
Implementation & benchmark of arXiv:2608.25524 — Adaptive Hybrid Subspace Levenberg Marquardt Algorithm with Adequacy Monitor for Large Scale Least Squares Problems
Source paper: Adaptive Hybrid Subspace Levenberg Marquardt Algorithm with Adequacy Monitor for Large Scale Least Squares Problems arXiv:2608.25524 ⓘ · analyzed Aug 29, 2026
AI-generated research hypothesis, automatically tested. Not peer-reviewed.
Idea description
Use one projected LM direction and let Armijo backtracking decide the accepted step length, instead of repeatedly resolving the damped system whenever a trial step is rejected. Independently update the damping parameter from the ratio of actual to predicted reduction, preserving the trust-region-like adaptivity of LM while reducing expensive curvature solves.
Formulas
Mathematical statement
Let F(theta)=1/2||r(theta)||_2^2, g=∇F(theta), H=J^TJ, and p be a direction obtained from one projected LM solve. The quadratic model is m(p)=F(theta)+g^Tp+1/2 p^THp, so the predicted reduction is Pred=-g^Tp-1/2 p^THp. For a trial step alpha p, the actual reduction is Act(alpha)=F(theta)-F(theta+alpha p), and the reduction ratio is rho(alpha)=Act(alpha)/Pred. Armijo acceptance chooses the largest alpha from {1,beta,beta^2,...}, with 0<beta<1, satisfying F(theta+alpha p)<=F(theta)+c alpha g^Tp for 0<c<1/2. Crucially, alpha is selected without changing lambda or recomputing p. After acceptance, update lambda only from rho, for example lambda<-gamma_up lambda when rho<rho_low, lambda<-lambda/gamma_down when rho>rho_high, and leave it unchanged otherwise. The mathematical benefit is that line-search globalization and curvature regularization are separate control loops: rejected lengths do not trigger repeated linear solves.
Implementation notes
1. Integration point: modify the optimizer step after any subspace, diagonal, or Krylov LM direction has been computed. This can be used independently of the hybrid basis, but the intended integration is with the projected solve (U^THU+lambda I)z=-U^Tg. 2. Pseudocode: at iteration t, compute F(theta), g, and one damped direction p. Compute Pred=max(epsilon, -g dot p - 0.5 p dot H p), where Hp is obtained either from the already available projected curvature or one additional JVP/VJP. Set alpha=1. While F(theta+alpha*p)>F(theta)+c*alpha*(g dot p) and alpha>alpha_min, replace alpha by beta*alpha. If no acceptable alpha exists, skip the update and increase lambda. Otherwise set theta_new=theta+alpha*p, compute Act=F(theta)-F(theta_new), rho=Act/Pred, and update lambda using rho_low, rho_high, gamma_up, and gamma_down. Do not recompute p during backtracking. 3. Computed from the math: Armijo acceptance, the model-prediction term, and rho. Estimated empirically: F on each trial minibatch; to reduce noise, use the same minibatch for all trial evaluations or maintain an exponential moving average of Act and Pred. Use c=1e-4, beta=0.5, alpha_min=1/32, rho_low=0.25, rho_high=0.75, gamma_up=4, and gamma_down=2. 4. First cheap experiment: compare this policy against conventional LM that changes lambda and resolves the projected system after every rejected trial, using the same 2-layer MLP and regression dataset. Record wall-clock time, number of curvature products, rejected trials, accepted loss decrease, and final MSE. The expected signal is similar or better loss per accepted iteration with substantially fewer projected solves, especially when minibatch curvature makes full-step acceptance unreliable.
Verification
Stage 1 · Toy mechanism gate: Passed ✓
Stage 2 · Mechanism transferred to benchmark: Not tested
Stage 2 · Practical benchmark result: Not run
Methodology: Toy-system gate first; the benchmark stage runs only after a pass. How verification works
Stage 1 — Mechanism check agent confidence 8/10
Built a NumPy nonlinear least-squares benchmark comparing decoupled Armijo LM against conventional LM that increases damping and re-solves after rejected full steps. The quadratic-model and reduction-ratio identities passed at approximately 1e-15 error. Across five seeds, the idea used 35 solves every run versus 42.6 baseline solves on average (17.6% fewer), and mean final loss was lower (0.1181 versus 0.1426), but it won on final loss only 2/5 runs and was generally not faster because Armijo backtracking added function evaluations.
- Agent confidence
- 8/10
- Baseline
- 5-seed mean final loss 0.1426035; mean 42.6 LM solves; mean rejected trials 7.6; representative runtime 1.067 s
- Idea
- 5-seed mean final loss 0.1181096; exactly 35 LM solves; mean rejected trials 12.6; representative runtime 0.977 s; lower loss in 2/5 seeds
Limitations: Tiny full-batch NumPy MLP regression only; identity projection was used rather than a reduced subspace; no minibatch noise, JVP/VJP implementation, FLOP-normalized benchmark, or larger neural network was tested. Runtime measurements are noisy and the baseline/idea use different numbers of objective evaluations.
How to run: python3 experiment.py
Verdict computed by deterministic test code from paired-seed statistics — not by the language model.
Artifacts
- experiment.py 4.6 KB View Raw
- report.md 1.4 KB View