PaperlayerView exact revision on arXiv

Source-linked AI summary

Initialization-dependent BFGS trial rates for tilted absolute values

Qiuyu Chen

arXiv:2609.09872v1math.NAcs.NAmath.OC

TL;DR

Lewis and Overton conjectured that every nonterminating run on the one-dimensional tilted absolute value has a trial-normalized rate determined by tilt, not initialization. We reduce the line-search dynamics to a scale-free state and construct periodic executions with different exact rates, disproving that assertion.

  • Problem

    Lewis and Overton conjectured that every nonterminating run's trial-normalized rate depends only on tilt u, not initialization.

    Source: §1 · p. 1

  • Method

    The paper reduces accepted-step dynamics to (sign x, t*) and constructs two periodic state cycles under the specified Armijo–Wolfe search.

    Source: §1 · p. 1, §2 · p. 2, §4 · p. 7

  • Results

    For every u in I, two nonterminating executions have different exact trial-normalized R-linear factors, refuting initialization independence.

    Source: §1 · p. 2, §4 · p. 7

  • Takeaways & Limitations

    Initialization can determine asymptotic trial-normalized behavior even in this one-dimensional tilted-absolute-value model.

    Source: §1 · p. 2

    The analysis sets c1=0 and allows weak Wolfe parameters c2 in (0, 1).

    Source: §2 · p. 2

Abstract

from arXiv · show

Lewis and Overton conjectured in 2008 that, for BFGS applied to the one-dimensional tilted absolute value with their Armijo--Wolfe line search, every nonterminating execution converges at a trial-normalized rate determined only by the tilt parameter and independent of the initial data. We prove that this initialization-independent rate assertion is false. In fact, for every tilt parameter in an explicit open interval, we construct two nonterminating executions with different sharp trial-normalized convergence rates. The proof reduces the line search to a scale-free state consisting of the iterate sign and the zero-crossing stepsize, and verifies two periodic state cycles by elementary rational inequalities. This yields an explicit family of counterexamples and shows that the asymptotic trial-normalized behavior of nonsmooth BFGS can depend essentially on the initialization even for this canonical one-dimensional model.

1 Introduction

Lewis and Overton conjectured that, for fixed tilt, every initialization either terminates or has the same trial-normalized convergence rate [4, Conjecture 4.1]. This paper constructs periodic nonterminating executions with different rates, disproving that initialization-independent assertion.

1 Introduction

  • Prior work studied nonsmooth BFGS behavior through examples, convergence results, and analyses of success and failure mechanisms [2].The paper situates its model among low-dimensional examples amenable to exact analysis.Source: §1 · p. 1
  • The conjecture asserted that each fixed tilt u determines the rate independently of the initial point, measured by line-search trials [4, Conjecture 4.1].Lewis and Overton normalized the numerical rate by function trials rather than accepted iterations.Source: §1 · p. 1
  • Two initializations generate periodic line-search dynamics up to scale, with the full state contracting by a fixed factor each period.The scale-free state returns exactly after one period.Source: §1 · p. 1
  • For every u in I, two nonterminating executions have different exact trial-normalized rates, disproving initialization independence.For rational u in I, both executions also have rational initial states, trial points, and contraction factors.Source: §1 · pp. 1–2

2 Trial-normalized rate and scale-free dynamics

The section defines convergence rates using a trial clock and reduces the one-dimensional line search to a scale-free state. It derives the acceptance and update rules that govern that state.

2 Trial-normalized rate and scale-free dynamics

  • The exact R-linear factor under a trial clock is characterized by the infimal admissible factor for the sequence indexed by cumulative trial counts.The rate definition distinguishes trial-indexed values from accepted-function-value indexing.Source: §2 · p. 2
  • The analysis sets the Armijo parameter c1 to 0 and allows any weak Wolfe parameter c2 in (0, 1).The ordinary gradient is specified away from the origin.Source: §2 · p. 2
  • The acceptance interval depends on the sign of x and is independent of the weak Wolfe parameter c2.Trials before the zero crossing fail weak Wolfe; trials beyond it satisfy weak Wolfe within the sign-dependent Armijo bound.Source: §2 · p. 3
  • After an accepted nonzero trial, the secant update determines the new inverse-Hessian approximation and the iterate crosses to the opposite sign.With λ = t/t*, the accepted-step map gives the updated state in terms of the zero-crossing stepsize.Source: §2 · p. 3
  • The pair (sign x, t*) is a complete scale-free state for accepted-step dynamics.Positive rescaling of (x, H) leaves t* and line-search comparisons unchanged.Source: §2 · p. 3

3 Two parameterized periodic families

For every parameter in the stated interval, the section constructs two nonterminating periodic executions of the line search. Their different cycle lengths and contraction factors yield distinct trial-normalized rates.

3 Two parameterized periodic families

  • The parameter window’s endpoint comparisons reduce to positivity conditions involving P(u) and Q(u), with the remaining quadratic shown positive throughout the interval.The proof uses the monotonicity of P and Q on I and a negative discriminant for the quadratic.Source: §3 · pp. 4, 6
  • For every u in I, two nonterminating executions repeat cycles of five and four trials, with full states multiplied by qA(u) and qB(u), respectively.The theorem starts from the normalized states specified in (20).Source: §3 · p. 5
  • The strict line-search comparisons keep every trial point away from zero, allowing scale equivariance to propagate each cycle indefinitely.The resulting trial-value sequences obey the cycle contraction relations, and their asymptotic rates follow from the repeated scaling.Source: §3 · pp. 5–6
  • For every rational u in I, both executions have rational initial states, trial points, and contraction factors, giving infinitely many explicit pairs with different rates..Source: §3 · p. 6

4 Consequence for the Lewis–Overton conjecture

For every parameter in the interval, two initializations produce different exact trial-normalized rates, disproving the initialization-independent rate assertion. The construction traces this dependence to distinct periodic line-search words in a scale-free state.

4 Consequence for the Lewis–Overton conjecture

  • For every u in I, two nonterminating initializations have unequal exact R-linear factors when measured by line-search trials.The factors are the infimal R-linear factors under that trial clock.Source: §4 · p. 7
  • The two executions use the same objective and line-search parameters, so their unequal rates contradict the conjectured rate depending only on u.The paper identifies this as falsifying Lewis and Overton’s Conjecture 4.1.Source: §4 · p. 7
  • Distinct periodic words in the scale-free state (sign x, t*) carry distinct contractions per trial; the reduction also makes other words amenable to finite calculations.The line search is doubling–bisection, and the calculations use explicit rational maps.Source: §4 · p. 7
Loading 2609.09872v1…