Research map / Optimization / Nonconvex and smooth optimization
An Enhanced Levenberg--Marquardt Method via Gram Reduction
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes Gram-Reduced Levenberg–Marquardt (GRLM), which refreshes the Jacobian Gram matrix only every m iterations, giving a line-search-free globally convergent LM method with local superlinear convergence and lower total flop cost.
Problem
Solving systems of nonlinear equations F(x)=0 (equivalently nonlinear least squares) with methods that are both globally convergent and locally superlinear while being computationally cheap; existing global LM methods cost O(d^3 eps^-2) or worse and need line search or trust-region subproblems.
Approach
Reuse the Gram matrix J(x)^T J(x) computed at a snapshot point for m consecutive iterations (lazy Gram matrix), with the regularization lambda_t = sqrt(c||J^T F||) as in adaptive LM, yielding a line-search-free LM scheme whose total cost is O(d^3 eps^-1 + d^2 eps^-2) flops.
Key results
- GRLM (m=50/100) requires fewer Jacobian-vector products and less CPU time than GD and LM across H-equation (N=100,200,300) and logistic regression benchmarks.
- Global complexity improves from O(d^3 eps^-2.5 log(1/eps)) (Mishchenko 2023) to O(d^3 eps^-1 + d^2 eps^-2) flops under the cubic-growth assumption.
- Local superlinear convergence is proved under a non-degenerate Jacobian at the solution, with rate depending on ||x_t - x*||.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Reuse the Gram matrix for m iterations instead of recomputing it every iteration | GRLM · Nonlinear equations, ϵ-stationary point | computation cost: O(d3ϵ−2) -> O(d3ϵ−1 + d2ϵ−2) | Helped |
| Use GRLM instead of gradient descent or LM | GRLM · Chandrasekhar H-equation (N = 100, N = 200, and N = 300) | Jacobian-vector products and CPU time | Helped |
| Use GRLM instead of gradient descent or LM | GRLM · Non-convex regularized logistic regression (a1a, w1a, and splice) | Jacobian-vector products and CPU time | Helped |
| Vary the Gram-matrix reuse interval m among 1, 50, 100, and 500 (ablation) | GRLM · Chandrasekhar H-equation (N = 100, N = 200, and N = 300) | iteration count | Mixed |
| Set m = 1, removing Gram-matrix reuse across iterations (ablation) | GRLM · Nonlinear equations, ϵ-stationary point | computation cost: O(d3ϵ−1 + d2ϵ−2) -> O(d3ϵ−2.5) | Hurt |
Surprising findings
- Smaller snapshot interval m gives fewer iterations but higher per-iteration cost, so the best m trades iteration count against Gram-matrix computation.
Limitations
- Requires Lipschitz Jacobian and cubic-growth assumptions for global guarantees.
- Experiments are small-scale (N up to 300, d up to 300) on a single PC.
- Parameter c and snapshot interval m must be chosen (tuned from grids in experiments); the method is not parameter-free.
Experimental setup
Datasets: Chandrasekhar H-equation (synthetic, N=100/200/300) LIBSVM a1a LIBSVM w1a LIBSVM splice
Benchmarks: Chandrasekhar H-equation non-convex regularized logistic regression on a1a, w1a, splice
Metrics: number of Jacobian-vector products CPU time norm of J(x)^T F(x) (gradient norm)
Baselines: Gradient descent Levenberg-Marquardt with gradient regularization (Mishchenko 2023)
Builds on: Levenberg-Marquardt method Mishchenko (2023) adaptive LM regularized Newton with lazy Hessians (Doikov et al. 2023) Shamanskii method
Closest papers by meaning
- Block Broyden's Methods for Solving Nonlinear Equations (NeurIPS 2023 · similarity 0.84)
- Skip the Hessian, Keep the Rates: Globalized Semismooth Newton with Lazy Hessian Updates (NeurIPS 2026 · similarity 0.83)
- A Regularized Newton Method for Nonconvex Optimization with Global and Local Complexity Guarantees (NeurIPS 2025 · similarity 0.82)
- Exploring Jacobian Inexactness in Second-Order Methods for Variational Inequalities: Lower Bounds, Optimal Algorithms and Quasi-Newton Approximations (NeurIPS 2024 · similarity 0.82)
- Iterative Methods via Locally Evolving Set Process (NeurIPS 2024 · similarity 0.81)
- Non-asymptotic Global Convergence Analysis of BFGS with the Armijo-Wolfe Line Search (NeurIPS 2024 · similarity 0.81)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.