Lewis–Overton conjecture on initialization-independent BFGS trial rates
For each admissible tilt parameter , consider every nonterminating execution of BFGS applied to the one-dimensional tilted absolute-value objective using the Lewis–Overton Armijo–Wolfe line search. The Lewis–Overton conjecture asserts that there exists a rate , depending only on , such that every such execution has the same sharp trial-normalized convergence rate: . In particular, this rate is independent of the initialization.
References
Primary source
Additional references
Progress summary
A September 2026 paper claims to disprove the conjecture by constructing two different long-run behaviors for the same one-dimensional optimization problem.
The Lewis–Overton conjecture predicts that BFGS with Armijo–Wolfe line searches has an asymptotic trial rate independent of initialization. The latest paper claims this universality fails for a tilted absolute-value model.
September 9, 2026 claimed counterexample
The paper Initialization-dependent BFGS trial rates for tilted absolute values claims that, for every tilt in an explicit interval, there are two nonterminating Armijo–Wolfe executions with distinct sharp rates. This would refute the conjecture for the specified one-dimensional problem and line search, but the claim has not been independently verified.
Current status (as of September 2026): The conjecture is claimed to be disproved for the specified one-dimensional model, but the counterexample remains unverified.
Sources
- arxiv.org
- people.orie.cornell.edu
- cs.nyu.edu
- coral.ise.lehigh.edu
- scholar.google.com
- semanticscholar.org
- researchgate.net
- deepmind.google
- activeloop.ai
- ar5iv.labs.arxiv.org
- arxiv.org
- ar5iv.labs.arxiv.org
- arxiv.org
- ar5iv.labs.arxiv.org
- quantamagazine.org
- quantamagazine.org
- mathstodon.xyz
- mathstodon.xyz
Solutions 0
No solutions have been posted yet.