Research map / Optimization / Nonconvex and smooth optimization
Incremental Quasi-Newton Methods with Faster Superlinear Convergence Rates
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 LISR-1 and its block extension LISR-k, incremental quasi-Newton methods that combine lazy propagation with SR1/SR-k Hessian updates to obtain condition-number-free local superlinear convergence rates for finite-sum strongly convex problems.
Problem
Local superlinear convergence of incremental quasi-Newton methods for large-scale finite-sum strongly convex optimization, where prior methods (IQN, SLIQN, IGS) have rates depending on the condition number.
Approach
Replace the BFGS-based Hessian estimator in incremental quasi-Newton with a greedy symmetric rank-1 (SR1) update applied to one component per iteration in a cyclic lazy fashion, analyzed with a new measure nu(G,A)=d*kappa*tr(G-A)/tr(A); a block SR-k variant improves the rate base to 1-k/d.
Key results
- LISR-1 attains local superlinear rate O((1-d^{-1})^{ceil(t/n)^2}), removing the condition-number dependence of SLIQN and IGS.
- LISR-k (k=5) attains rate base 1-k/d, strictly tighter than LISR-1 for k>=2.
- On quadratic programming with condition-number parameter xi in {4,8,12}, LISR-1 and LISR-k are insensitive to condition number while IQN and SLIQN degrade.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Replace BFGS-family updates with greedy SR1 updates | Incremental quasi-Newton methods · Finite-sum optimization | local superlinear convergence rate: \fO\big((1-d^{-1} \varkappa^{-1})^{\ceil{t/n}^2}\big) -> \fO\big((1-d^{-1})^{\ceil{t/n}^2}\big) | Helped |
| Use rank-k rather than rank-1 Hessian updates (ablation) | LISR-1 · Finite-sum optimization | local superlinear convergence rate: (1-d^{-1}) -> (1-kd^{-1}) | Helped |
| Use rank-k block updates (ablation) | Incremental quasi-Newton methods · Regularized logistic regression (nine LIBSVM datasets) | normalized error | Helped |
| Use rank-1 SR1 updates rather than IQN/SLIQN updates | Incremental quasi-Newton methods · Regularized logistic regression (nine LIBSVM datasets), after convergence begins | convergence rate | Helped |
| Use rank-1 SR1 updates rather than IQN/SLIQN updates | Incremental quasi-Newton methods · Regularized logistic regression (nine LIBSVM datasets), early stage | convergence rate | Hurt |
| Use LISR-1 or LISR-k instead of IQN or SLIQN as condition number varies | Incremental quasi-Newton methods · Quadratic programming (ξ∈{4,8,12}) | sensitivity of convergence to condition number | Helped |
Surprising findings
- LISR-1 can be slower than IQN and SLIQN in early iterations on logistic regression, although it converges faster once near the solution.
Limitations
- Local convergence only; the analysis requires initialization close to the optimum and specific initial Hessian conditions.
- Early-stage convergence can be slower than IQN and SLIQN on real datasets, with the theory for this phenomenon left open.
- Experiments are limited to quadratic programming and regularized logistic regression on modest problem sizes.
Experimental setup
Datasets: a9a w8a ijcnn mushrooms phishing svmguide3 german.numer splice covtype synthetic quadratic programming
Benchmarks: synthetic quadratic programming LIBSVM regularized logistic regression datasets
Metrics: normalized error vs effective passes
Baselines: IQN SLIQN
Builds on: IQN SLIQN Incremental Greedy BFGS greedy quasi-Newton methods block quasi-Newton (SR-k)
Closest papers by meaning
- Skip the Hessian, Keep the Rates: Globalized Semismooth Newton with Lazy Hessian Updates (NeurIPS 2026 · similarity 0.88)
- Affine-Invariant Global Non-Asymptotic Convergence Analysis of BFGS under Self-Concordance (NeurIPS 2025 · similarity 0.87)
- A Regularized Newton Method for Nonconvex Optimization with Global and Local Complexity Guarantees (NeurIPS 2025 · similarity 0.87)
- Stochastic Newton Proximal Extragradient Method (NeurIPS 2024 · similarity 0.86)
- Adaptive and Optimal Second-order Optimistic Methods for Minimax Optimization (NeurIPS 2024 · similarity 0.86)
- Non-asymptotic Global Convergence Analysis of BFGS with the Armijo-Wolfe Line Search (NeurIPS 2024 · similarity 0.85)
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.