LemmaStatement: Literature-sourcedProof: AI-generatedPipeline-generated

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.

Retraction trust-region ratios are accurate at small radii

Statement

Let $M$ be a finite-dimensional real Stiefel or Grassmann manifold, or a complex Grassmannian, with its real Frobenius metric. Regard every tangent space as real, let $x \in M$ , and let $g = grad f (x) \neq 0$ . Choose a first-order retraction $R$ and write ${\hat{f}}_{x} (s) = f (R_{x} (s))$ on the tangent (or horizontal) space, equipped with its real Frobenius inner product. Suppose $\nabla {\hat{f}}_{x}$ is $L_{R}$ -Lipschitz on the ball $∥ s ∥ \leq Δ$ for $Δ > 0$ , and let $m_{x} (s) = f (x) + ⟨ g, s ⟩ + \frac{1}{2} ⟨ s, B_{x} s ⟩$ with $B_{x}$ self-adjoint and real-linear. Define its induced operator norm by $∥ B_{x} ∥_{o p} : = \sup_{s \neq 0} \frac{∥ B_{x} s ∥}{∥ s ∥},$ and assume $∥ B_{x} ∥_{o p} \leq M_{B}$ . Let $p_{C}$ be the negative-gradient Cauchy step, and let a feasible trial $p$ satisfy $m_{x} (0) - m_{x} (p) \geq θ_{C} [m_{x} (0) - m_{x} (p_{C})]$ for $0 < θ_{C} \leq 1$ . With a zero denominator interpreted as $+ \infty$ , if $Δ \leq ∥ g ∥ / (2 M_{B})$ , then its predicted decrease $P$ is positive and $∣ ρ - 1 ∣ \leq \frac{2 (L_{R} + M_{B}) Δ}{θ_{C} ∥ g ∥}, ρ = \frac{f (x) - f (R_{x} (p))}{P} .$ Consequently, for $0 < η_{2} < 1$ , if $Δ \leq \min {\frac{∥ g ∥}{2 M_{B}}, \frac{θ_{C} (1 - η_{2}) ∥ g ∥}{2 (L_{R} + M_{B})}},$ then $ρ \geq η_{2}$ . If $L_{R} + M_{B} = 0$ , the ratio equals $1$ .

Facts & Assumptions

Given: The $C^{2}$ pullback, gradient Lipschitz bound, self-adjoint model operator and norm bound, Cauchy-fraction condition, and small-radius safeguard in the Statement.

[F1]

A first-order real Stiefel/Grassmann or complex Grassmann retraction satisfies $D R_{x} (0) [s] = s$ (The QR and polar maps are first-order Stiefel and Grassmann retractions, The complex Grassmann polar map is a first-order retraction).

[F2]

The Riemannian trust-region step is feasible, has predicted decrease at least $θ_{C}$ times Cauchy decrease, and uses the Cauchy step when $Δ \leq ∥ g ∥ / (2 M_{B})$ (Finite-budget Riemannian trust-region method).

[F3]

The negative-gradient Cauchy step is the segment minimizer with the formula stated in The Cauchy step for a quadratic trust-region model.

[F4]

In orthonormal real coordinates on the finite-dimensional tangent or horizontal space, the operator $B_{x}$ has a symmetric matrix with Euclidean induced norm $∥ B_{x} ∥_{o p}$ , so the Cauchy decrease estimate gives at least $\frac{1}{2} ∥ g ∥ \min {Δ, ∥ g ∥ / ∥ B_{x} ∥_{o p}}$ , with the zero-operator convention (The Cauchy step gives a quantitative model decrease).

[F5]

The matrix norm is compatible with the vector norm and the Euclidean inner product satisfies Cauchy–Schwarz (Induced matrix norms are compatible with matrix-vector multiplication, submultiplicative, and satisfy ||I|| = 1, Cauchy-Schwarz $∣ ⟨ x, y ⟩ ∣ \leq ∥ x ∥_{2} ∥ y ∥_{2}$ with its equality case, the triangle inequality for $∥ \cdot ∥_{2}$ , the parallelogram law and polarisation).

[F6]

A scalar function continuous on a closed interval and differentiable in its interior has an interior point where its derivative is the endpoint slope (The mean value theorem, as the case $g (x) = x$ of Cauchy's: for $f$ continuous on $[a, b]$ with $a < b$ and differentiable on $(a, b)$ there is $c \in (a, b)$ with $f (b) - f (a) = f^{'} (c) (b - a)$ ).

Proof

technique · lower-bound the model decrease and compare pullback actual decrease with its quadratic model

1.1F3F5givencasesalgebra

Write $a = ∥ g ∥ > 0$ and $c = ⟨ g, B_{x} g ⟩$ . The operator norm bound and Cauchy–Schwarz in [F5] give $c \leq ∣ c ∣ \leq a ∥ B_{x} g ∥ \leq M_{B} a^{2}$ . If $c \leq 0$ , [F3] gives a boundary Cauchy step. If $c > 0$ , then $M_{B} > 0$ , the unconstrained segment minimizer has length $a^{3} / c \geq a / M_{B}$ , and $Δ \leq a / (2 M_{B})$ forces the constrained minimizer to the boundary. Thus $∥ p_{C} ∥ = Δ$ in both branches, including $M_{B} = 0$ .

2.1F2F4givenstep 1.1choosealgebra

Choose orthonormal real coordinates on the finite-dimensional tangent or horizontal space. In these coordinates [F4] applies, and $∥ B_{x} ∥_{2} = ∥ B_{x} ∥_{o p}$ . Since $∥ B_{x} ∥_{o p} \leq M_{B}$ and step 1.1 gives $∥ p_{C} ∥ = Δ$ , the Cauchy decrease is at least $\frac{1}{2} a Δ$ . The trial condition and [F2] therefore give $P = m_{x} (0) - m_{x} (p) \geq \frac{1}{2} θ_{C} a Δ > 0$ . This verifies that $ρ$ is defined.

3.1F1F2F5F6givenstep 2.1algebra∎

Put $ϕ (t) = {\hat{f}}_{x} (t p)$ and $h (t) = ϕ (t) - ϕ (0) - t ϕ^{'} (0)$ . By [F1], $ϕ^{'} (0) = ⟨ g, p ⟩$ . Lipschitz continuity and [F5] give $∣ h^{'} (t) ∣ \leq L_{R} t ∥ p ∥^{2} \leq L_{R} ∥ p ∥^{2}$ for $0 \leq t \leq 1$ . Apply [F6] on $[0, 1]$ to obtain $∣ h (1) ∣ \leq L_{R} ∥ p ∥^{2}$ . The quadratic model contributes at most $\frac{1}{2} M_{B} ∥ p ∥^{2}$ beyond the linear term, so $∣ f (x) - f (R_{x} (p)) - P ∣ \leq (L_{R} + M_{B}) ∥ p ∥^{2} .$ Since $∥ p ∥ \leq Δ$ , step 2.1 gives $∣ ρ - 1 ∣ \leq \frac{(L_{R} + M_{B}) Δ^{2}}{θ_{C} a Δ / 2} = \frac{2 (L_{R} + M_{B}) Δ}{θ_{C} a} .$ If $L_{R} + M_{B} = 0$ , the numerator error is zero and $ρ = 1$ . Otherwise the stated radius threshold makes $∣ ρ - 1 ∣ \leq 1 - η_{2}$ , hence $ρ \geq η_{2}$ .

Depends on

Used by

Riemannian trust regions reach an epsilon-gradient iterate Theorem

Dependency tree · two levels

42 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

P.-A. Absil, R. Mahony, and R. Sepulchre, Optimization Algorithms on Matrix Manifolds, Chapter 7 (2008) (standard reference, not scraped)
Nicolas Boumal, P.-A. Absil, and Coralia Cartis, Global rates of convergence for nonconvex optimization on manifolds (2018), arXiv v2 (standard reference, not scraped)
Nicolas Boumal, An Introduction to Optimization on Smooth Manifolds (2023 prepublication) (standard reference, not scraped)