LemmaStatement: Literature-sourcedProof: AI-adaptedPipeline-generatedprecheck passjudge pass (gpt-6-luna)

How statement and proof provenance work

The first chip identifies the source of the statement or construction; the second identifies the source of its local proof or verification.

Literature-sourced: the exact statement appears in a cited source; only wording and notation differ.
AI-adapted: a semantically identical restatement of literature-sourced material, modulo indexing, notation, and boundary cases adopted by the library.
AI-generated: a genuinely novel statement formulated by AI, with no source for the claim itself.

These labels describe origin, not correctness: citations and verification chips remain separate evidence.

Fixed-memory L-Bfgs curvature and scale bounds imply uniform spectral bounds

Statement

Fix $n, m \geq 1$ , constants $0 < a \leq b < \infty$ , $C > 0$ , and $0 < γ_{\min} \leq γ_{\max} < \infty$ . Suppose every stored pair in a limited-memory BFGS state satisfies $a ∥ s_{i} ∥_{2}^{2} \leq s_{i}^{T} y_{i} \leq b ∥ s_{i} ∥_{2}^{2}, \frac{∥ y_{i} ∥_{2}^{2}}{s_{i}^{T} y_{i}} \leq C,$ and each base scale satisfies $γ_{\min} \leq γ \leq γ_{\max}$ . Then the implicit SPD matrix $H_{k}$ represented by the two-loop recursion of Limited-memory Bfgs two-loop recursion with curvature filtering has uniform bounds $\underline{λ} I ⪯ H_{k} ⪯ \overline{λ} I, T : = \frac{n}{γ_{\min}} + m C, r : = \min {1, a / T}, D : = γ_{\max}^{} r^{m}, \underline{λ} : = \frac{1}{T}, \overline{λ} : = \frac{T^{n - 1}}{D} .$ Here $A ⪯ B$ means $z^{T} A z \leq z^{T} B z$ for all $z$ . If the stored list is nonempty, the usual scale $(s_{l a s t}^{T} y_{l a s t}) / ∥ y_{l a s t} ∥_{2}^{2}$ lies in $[1 / C, b / a^{2}]$ .

Facts & Assumptions

Given: $n, m, a, b, C, γ_{\min}, γ_{\max}$ , the stored-pair bounds, and the L-BFGS state in the Statement.

[F1]

The L-Bfgs two-loop recursion equals the stored inverse updates and costs linear memory work: the implicit matrix is obtained by at most $m$ sequential inverse BFGS updates from $H_{0} = γ I$ .

[F2]

Bfgs updates preserve the secant equations, symmetry, and positive definiteness: each positive-curvature inverse update preserves positive definiteness and is reciprocal to its Hessian update.

[F3]

Bfgs trace and determinant identities give a matrix potential inequality: for $B = H^{- 1}$ , one update adds at most $∥ y ∥_{2}^{2} / (s^{T} y)$ to $tr (B)$ and multiplies $\det (B)$ by $(s^{T} y) / (s^{T} B s)$ .

[F4]

In an orthonormal basis, self-adjoint means conjugate-transpose symmetry and normal means commuting with the conjugate transpose and Real spectral theorem: a self-adjoint endomorphism of a finite-dimensional real inner product space has an orthonormal eigenbasis: a real symmetric matrix represents a self-adjoint endomorphism of Euclidean $R^{n}$ and has an orthonormal eigenbasis. If the matrix is SPD, each eigenvalue is positive by evaluating its quadratic form on a unit eigenvector.

[F5]

Limited-memory Bfgs two-loop recursion with curvature filtering: the scale from the newest pair is $(s_{l a s t}^{T} y_{l a s t}) / (y_{l a s t}^{T} y_{l a s t})$ .

[F6]

The basis-independent characteristic polynomial $χ_{T}$ of an endomorphism of a finite-dimensional space, including $χ_{T} = 1$ in dimension zero, For $A \in M_{n} (F)$ , the characteristic polynomial is $χ_{A} (x) = \det (x I_{n} - A)$ when $n \geq 1$ , with $χ_{A} (x) = 1$ for the unique $0 \times 0$ matrix, and The determinant of a triangular matrix is the product of its diagonal entries: in an eigenbasis with diagonal matrix $D = diag (λ_{1}, \dots, λ_{n})$ , $χ_{B_{k}} (t) = \det (t I - D) = \prod_{i} (t - λ_{i})$ . If $χ_{T} (x) = \prod_{i < n} (x - λ_{i})$ in $F [x]$ , then $tr (T) = \sum_{i < n} λ_{i}$ : trace is the sum of the eigenvalues counted with algebraic multiplicity and If $χ_{T} (x) = \prod_{i < n} (x - λ_{i})$ in $F [x]$ , then $\det (T) = \prod_{i < n} λ_{i}$ : determinant is the product of the eigenvalues counted with algebraic multiplicity then give the trace and determinant as $\sum_{i} λ_{i}$ and $\prod_{i} λ_{i}$ ; The basis-independent trace of an endomorphism of a finite-dimensional vector space and The determinant of an endomorphism of a finite-dimensional vector space: its matrix determinant in an ordered basis in positive dimension, and $1$ on the zero space identify these with the represented matrix's trace and determinant. The triangular-determinant rule also gives $\det (γ^{- 1} I) = γ^{- n}$ .

Proof

Given: $n, m, a, b, C, γ_{\min}, γ_{\max}$ , the stored-pair bounds, and the L-BFGS state in the Statement.

[F1] The L-Bfgs two-loop recursion equals the stored inverse updates and costs linear memory work: the implicit matrix is obtained by at most $m$ sequential inverse BFGS updates from $H_{0} = γ I$ .

[F2] Bfgs updates preserve the secant equations, symmetry, and positive definiteness: each positive-curvature inverse update preserves positive definiteness and is reciprocal to its Hessian update.

[F3] Bfgs trace and determinant identities give a matrix potential inequality: for $B = H^{- 1}$ , one update adds at most $∥ y ∥_{2}^{2} / (s^{T} y)$ to $tr (B)$ and multiplies $\det (B)$ by $(s^{T} y) / (s^{T} B s)$ .

[F4] In an orthonormal basis, self-adjoint means conjugate-transpose symmetry and normal means commuting with the conjugate transpose and Real spectral theorem: a self-adjoint endomorphism of a finite-dimensional real inner product space has an orthonormal eigenbasis: a real symmetric matrix represents a self-adjoint endomorphism of Euclidean $R^{n}$ and has an orthonormal eigenbasis. If the matrix is SPD, each eigenvalue is positive by evaluating its quadratic form on a unit eigenvector.

[F5] Limited-memory Bfgs two-loop recursion with curvature filtering: the scale from the newest pair is $(s_{l a s t}^{T} y_{l a s t}) / (y_{l a s t}^{T} y_{l a s t})$ .

[F6] The basis-independent characteristic polynomial $χ_{T}$ of an endomorphism of a finite-dimensional space, including $χ_{T} = 1$ in dimension zero, For $A \in M_{n} (F)$ , the characteristic polynomial is $χ_{A} (x) = \det (x I_{n} - A)$ when $n \geq 1$ , with $χ_{A} (x) = 1$ for the unique $0 \times 0$ matrix, and The determinant of a triangular matrix is the product of its diagonal entries: in an eigenbasis with diagonal matrix $D = diag (λ_{1}, \dots, λ_{n})$ , $χ_{B_{k}} (t) = \det (t I - D) = \prod_{i} (t - λ_{i})$ . If $χ_{T} (x) = \prod_{i < n} (x - λ_{i})$ in $F [x]$ , then $tr (T) = \sum_{i < n} λ_{i}$ : trace is the sum of the eigenvalues counted with algebraic multiplicity and If $χ_{T} (x) = \prod_{i < n} (x - λ_{i})$ in $F [x]$ , then $\det (T) = \prod_{i < n} λ_{i}$ : determinant is the product of the eigenvalues counted with algebraic multiplicity then give the trace and determinant as $\sum_{i} λ_{i}$ and $\prod_{i} λ_{i}$ ; The basis-independent trace of an endomorphism of a finite-dimensional vector space and The determinant of an endomorphism of a finite-dimensional vector space: its matrix determinant in an ordered basis in positive dimension, and $1$ on the zero space identify these with the represented matrix's trace and determinant. The triangular-determinant rule also gives $\det (γ^{- 1} I) = γ^{- n}$ .

1.1givenF1F2F3algebra

Let $B_{k} : = H_{k}^{- 1}$ . By [F1] and [F2], this is an SPD matrix obtained from $B_{0} = γ^{- 1} I$ by at most $m$ direct BFGS updates. Its initial trace satisfies $tr (B_{0}) = n / γ \leq n / γ_{\min}$ . Each update adds at most $C$ to trace by [F3] and the pair bound. Hence $tr (B_{k}) \leq T$ .

2.1givenF3F4F6step 1.1algebra

By [F4], choose an orthonormal eigenbasis for $B_{k}$ and let its positive eigenvalues be $λ_{1}, \dots, λ_{n}$ . In this basis the characteristic polynomial factors as $\prod_{i} (t - λ_{i})$ , so [F6] gives $tr (B_{k}) = \sum_{i} λ_{i}$ and $\det (B_{k}) = \prod_{i} λ_{i}$ . By step 1.1 each $λ_{i} \leq T$ , and expanding $s$ in this orthonormal basis gives $s^{T} B_{k} s \leq T ∥ s ∥_{2}^{2}$ . The determinant ratio in [F3] and the lower pair bound therefore give $\frac{\det (B_{k + 1})}{\det (B_{k})} = \frac{s^{T} y}{s^{T} B_{k} s} \geq \frac{a}{T} \geq r .$ Since $0 < r \leq 1$ and there are at most $m$ updates, while $\det (B_{0}) = γ^{- n} \geq γ_{\max}^{}$ , it follows that $\det (B_{k}) \geq D$ .

3.1F4F6step 2.1algebra

Let $λ_{\min} (B_{k})$ be the smallest eigenvalue. By step 2.1, $\det (B_{k})$ is the product of the $n$ positive eigenvalues, and the other $n - 1$ eigenvalues are at most $T$ . Thus $λ_{\min} (B_{k}) \geq D / T^{n - 1}$ , while every eigenvalue is at most $T$ . The eigenvalues of $H_{k} = B_{k}^{- 1}$ are the reciprocals, so they lie in $[1 / T, T^{n - 1} / D]$ . The spectral theorem translates these bounds into the asserted quadratic-form inequalities.

4.1givenF5algebra∎

If the stored list is nonempty, take its newest pair. For the standard scale, [F5] and the upper curvature bound give $γ = (s^{T} y) / ∥ y ∥_{2}^{2} \leq b ∥ s ∥_{2}^{2} / ∥ y ∥_{2}^{2}$ . By Cauchy–Schwarz and the lower curvature bound, $∥ s ∥_{2} ∥ y ∥_{2} \geq s^{T} y \geq a ∥ s ∥_{2}^{2}$ , so $∥ y ∥_{2} \geq a ∥ s ∥_{2}$ and $γ \leq b / a^{2}$ . The other pair bound gives $∥ y ∥_{2}^{2} / (s^{T} y) \leq C$ , hence $γ \geq 1 / C$ .

Depends on

Used by

Fixed-memory L-Bfgs converges linearly under uniform curvature and scale bounds Theorem

Dependency tree · two levels

39 results within two dependency steps of this one, each drawn at its shortest distance from it. An arrow runs from a result to what uses it, so the chart reads left to right and ends at this result, which carries a heavier outline. Every node is a link to that result. Click elsewhere on the chart to enlarge it.

Sources

Dong C. Liu and Jorge Nocedal, On the limited memory BFGS method for large scale optimization (standard reference, not scraped)
Jorge Nocedal and Stephen J. Wright, Numerical Optimization, 2nd ed. (standard reference, not scraped)