ExampleConstruction: AI-generatedVerification: 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.

Exact and Armijo rates on an anisotropic quadratic

Example

For $f (u, v) = \frac{1}{2} u^{2} + 2 v^{2}$ , the exact-gradient step has an explicit nontrivial line minimizer, and Armijo backtracking shows the accepted-step bound in a finite calculation.

Facts & Assumptions

Given: $f (u, v) = \frac{1}{2} u^{2} + 2 v^{2}$ on $R^{2}$ , initial point $x_{0} = (1, 1)$ , exact gradient line search, and Armijo parameters $a = \frac{1}{4}$ , $b = \frac{1}{2}$ .

[F1]

Exact gradient line search has a global objective-gap contraction: under compact sublevel and $m I ⪯ H_{f} ⪯ M I$ , an exact negative-gradient line-search step contracts the objective gap by at least the factor $1 - m / M$ .

[F2]

Armijo gradient descent has an explicit global linear rate: with $0 < a < 1 / 2$ and $0 < b < 1$ , the accepted step is at least $\min {1, 2 b (1 - a) / M}$ and the objective-gap factor is $1 - 2 a m \min {1, 2 b (1 - a) / M}$ .

[F3]

Gradient descent: backtracking tests $t = 1, b, b^{2}, \dots$ and accepts when $f (x - t \nabla f (x)) \leq f (x) - a t ∥ \nabla f (x) ∥_{2}^{2}$ .

[F4]

Heine-Borel in $R^{n}$ : with the Euclidean metric a subset of $R^{n}$ is compact if and only if it is closed and bounded, and the proof by bisection uses no choice principle; the same holds on the real line: in Euclidean space, a closed and bounded set is compact.

Verification

1.1F4given

The Hessian is $diag (1, 4)$ , so $m = 1$ and $M = 4$ ; $x^{*} = (0, 0)$ is the unique minimizer and $f (x_{0}) = 5 / 2$ . The sublevel set is closed by continuity and bounded because $\frac{1}{2} u^{2} \leq 5 / 2$ and $2 v^{2} \leq 5 / 2$ on it; it is compact by [F4]. The gradient at $x_{0}$ is $(1, 4)$ .

1.2F1givenalgebra

Along the negative-gradient ray, $ϕ (t) = \frac{1}{2} (1 - t)^{2} + 2 (1 - 4 t)^{2}$ and $ϕ^{'} (t) = 65 t - 17$ , so the unique minimizer is $t_{*} = 17 / 65$ . It gives $x_{+} = (48 / 65, - 3 / 65)$ and $f (x_{+}) = 234 / 845$ . The theorem [F1] bounds the gap by $(1 - 1 / 4) (5 / 2) = 15 / 8$ , and $234 / 845 < 15 / 8$ .

1.3F3givenalgebra

For Armijo, the first trial $t = 1$ has candidate $(0, - 3)$ with value $18$ and threshold $5 / 2 - 17 / 4 = - 7 / 4$ , so it fails. The second trial $t = 1 / 2$ has candidate $(1 / 2, - 1)$ with value $17 / 8$ and threshold $3 / 8$ , so it fails. At $t = 1 / 4$ , the candidate is $(3 / 4, 0)$ with value $9 / 32 < 23 / 16$ , the Armijo threshold; hence [F3] accepts $t = 1 / 4$ .

2.1F1F2step 1.3algebra∎

Here $τ = \min {1, 2 b (1 - a) / M} = 3 / 16$ , so [F2] gives the gap factor $1 - 2 a m τ = 29 / 32$ . The actual new gap $9 / 32$ is below $(29 / 32) (5 / 2) = 145 / 64$ . The exact and Armijo calculations concern objective gaps; neither calculation supplies an iterate-error bound.

Depends on

Used by

Nothing in the library uses this result yet.

Dependency tree · two levels

48 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.