Alphabeta Math
TheoremStatement: 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.

Summable certified prox errors preserve an O(1/k) best-iterate bound

Statement

Under the inexact proximal-gradient model of Certified inexact proximal-gradient and FISTA updates, suppose F=f+g has a minimizer x∗ and let ηk≥0 be the certified errors. Then for every N≥1, min⁡1≤k≤N(F(xk)−F(x∗))≤L∥x0−x∗∥22/2+∑k=1NηkN. If ∑k=1∞ηk<∞, then F(xk)−F(x∗)→0. This gives a best-iterate bound; no last-iterate O(1/k) rate is asserted.

Facts & Assumptions

Given: The certified inexact proximal-gradient sequence, its nonnegative errors and a minimizer.

[F1]

Certified inexact proximal-gradient and FISTA updates: at step k, yk=xk−1 and the point xk has certificate error ηk≥0.

[F2]

One-step estimate for a certified inexact proximal call: with z=x∗, F(x∗)≥F(xk)+L2∥xk−xk−1∥22+L⟨xk−1−x∗,xk−xk−1⟩−ηk.

Proof

1.1F1F2givenalgebra

By [F1], yk=xk−1 at each proximal-gradient call. Put dk=xk−xk−1. The norm identity and [F2] give F(xk)−F(x∗)≤L2(∥xk−1−x∗∥22−∥xk−x∗∥22)+ηk. Summing from 1 to N telescopes the squared distances and yields ∑k=1N(F(xk)−F(x∗))≤L∥x0−x∗∥22/2+∑k=1Nηk. The minimum of N real numbers is at most their average, proving the finite-N bound.

2.1givenstep 1.1contradictionalgebra∎

Each gap is nonnegative because x∗ minimizes F. If the error series is summable, step 1.1 bounds the partial sums of the nonnegative gaps uniformly by L∥x0−x∗∥22/2+∑k≥1ηk. A nonnegative sequence with bounded partial sums has terms tending to zero: otherwise some ε>0 would be exceeded infinitely often and the partial sums would be unbounded.

Depends on

Used by

Nothing in the library uses this result yet.

Dependency tree · two levels

9 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