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.

The proximal-gradient method has an O(1/k) objective bound

Statement

Under the exact proximal-gradient hypotheses of Proximal-gradient, FISTA, and fixed-period restarted FISTA, suppose F=f+g has a minimizer x∗. From any x0∈Rn, the iterates xk=TL(xk−1) satisfy 0≤F(xk)−F(x∗)≤L∥x0−x∗∥222k(k≥1).

Facts & Assumptions

Given: The exact proximal-gradient iteration and minimizer in the Statement.

[F1]

Proximal-gradient, FISTA, and fixed-period restarted FISTA: xk=TL(xk−1) and every proximal output lies in dom⁡g.

[F2]

One-step proximal-gradient estimate: for z=x∗, F(x∗)≥F(xk)+(L/2)∥xk−xk−1∥22+L⟨xk−1−x∗,xk−xk−1⟩. Here F(x∗) and F(xk) are finite, so the equivalent finite-gap form may be used in the proof.

[F3]

A finite continuous convex summand preserves proper closed convexity: F is convex, so F(xk)≥F(x∗).

Proof

1.1F2givenalgebra

Put dk=xk−xk−1. The identity 2⟨xk−1−x∗,dk⟩=∥xk−x∗∥22−∥xk−1−x∗∥22−∥dk∥22 and [F2] yield F(xk)−F(x∗)≤(L/2)(∥xk−1−x∗∥22−∥xk−x∗∥22). Summing from 1 to k gives ∑j=1k(F(xj)−F(x∗))≤L∥x0−x∗∥22/2.

2.1F1F2F3step 1.1givenalgebra∎

For every j≥2, apply the one-step estimate with comparison point z=xj−1; this point has finite F by [F1]. The cross term is zero, so F(xj−1)−F(xj)≥(L/2)∥xj−xj−1∥22≥0. Hence the gaps for x1,x2,… are nonincreasing. Their sum bound in step 1.1 implies k(F(xk)−F(x∗))≤∑j=1k(F(xj)−F(x∗))≤L∥x0−x∗∥22/2. Nonnegativity is [F3].

Depends on

Used by

Nothing in the library uses this result yet.

Dependency tree · two levels

13 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