TheoremStatement: Literature-sourcedProof: AI-adaptedPipeline-generatedprecheck pass

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.

Strong convexity gives linear proximal-gradient and restarted-FISTA rates

Statement

Assume the exact algorithm hypotheses of Proximal-gradient, FISTA, and fixed-period restarted FISTA, that $F = f + g$ is $μ$ -strongly convex for $μ > 0$ under Strong convexity for an extended-real objective, that a minimizer $x_{*}$ exists, and that $F (x_{0}) < + \infty$ . For each mode, let $(x_{k})_{k \geq 0}$ denote the sequence whose finite prefixes are its executions with arbitrary finite budgets, using the same initial point and, for restart, the same period. Exact proximal points are unique, so these prefixes agree whenever their budgets overlap. A run with budget $N$ satisfies the bounds below for $0 \leq k \leq N$ and $0 \leq j m \leq N$ , respectively. Exact proximal gradient satisfies $F (x_{k}) - F (x_{*}) \leq q^{k} (F (x_{0}) - F (x_{*})), q = \frac{1}{1 + μ / (4 L)} < 1.$ For fixed-period restarted FISTA with $m = ⌈ \sqrt{8 L / μ} ⌉$ updates per full block, the restart-point gaps obey $F (x_{j m}) - F (x_{*}) \leq 2^{- j} (F (x_{0}) - F (x_{*})), j \geq 0.$

Facts & Assumptions

Given: The exact algorithms, $μ$ -strongly convex objective, minimizer and finite starting objective in the Statement.

[F1]

Strong convexity for an extended-real objective: for finite-domain points, $F ((1 - θ) x + θ y) \leq (1 - θ) F (x) + θ F (y) - (μ / 2) θ (1 - θ) ∥ x - y ∥_{2}^{2}$ .

[F2]

Existence, resolvent characterization, and firm nonexpansiveness of the proximal map: an exact step $x^{+} = T_{L} (x)$ has $p = L (x - x^{+}) - \nabla f (x) \in \partial g (x^{+})$ .

[F3]

Differentiable convex functions are characterized by the gradient inequality: $\nabla f (x^{+}) \in \partial f (x^{+})$ and convexity gives the gradient lower bound.

[F4]

One-step proximal-gradient estimate: at a finite iterate $x$ with $z = x$ , exact proximal gradient gives $F (x) \geq F (x^{+}) + L ∥ x^{+} - x ∥_{2}^{2} / 2$ ; both objective values are finite.

[F5]

FISTA has an O(1/k^2) objective bound: $m$ exact FISTA updates from a point $w$ have gap at most $2 L ∥ w - x_{*} ∥_{2}^{2} / (m + 1)^{2}$ .

[F6]

Subdifferentials of proper extended-real convex functions: $r \in \partial F (x)$ means $F (z) \geq F (x) + ⟨ r, z - x ⟩$ for every $z$ .

[F7]

Cauchy-Schwarz $∣ ⟨ x, y ⟩ ∣ \leq ∥ x ∥_{2} ∥ y ∥_{2}$ with its equality case, the triangle inequality for $∥ \cdot ∥_{2}$ , the parallelogram law and polarisation: the Euclidean norm satisfies $∥ a + b ∥_{2} \leq ∥ a ∥_{2} + ∥ b ∥_{2}$ .

Proof

1.1F1F6givenalgebra

If $r \in \partial F (x)$ and $z \in dom F$ , [F6] gives the subgradient lower bound at $(1 - θ) x + θ z$ , while [F1] gives the strong-convexity upper bound there. Combine them, divide by $θ > 0$ , and let $θ ↓ 0$ . This gives $F (z) \geq F (x) + ⟨ r, z - x ⟩ + \frac{μ}{2} ∥ z - x ∥_{2}^{2} .$ Taking $z = x_{*}$ and maximizing the right-hand upper bound $⟨ r, x - x_{*} ⟩ - (μ / 2) ∥ x - x_{*} ∥^{2}$ by completing the square yields $F (x) - F (x_{*}) \leq ∥ r ∥_{2}^{2} / (2 μ)$ .

1.2F1givenalgebra

Strong convexity and minimality imply $F (w) - F (x_{*}) \geq (μ / 2) ∥ w - x_{*} ∥_{2}^{2}$ for every finite $w$ : apply [F1] to $(x_{*}, w)$ , use $F (x_{*}) \leq F ((1 - θ) x_{*} + θ w)$ , divide by $θ$ , and let $θ ↓ 0$ .

2.1F2F3F6F7step 1.1givenalgebra

For an exact step $x^{+} = T_{L} (x)$ , [F2] gives $p = L (x - x^{+}) - \nabla f (x) \in \partial g (x^{+})$ . Adding the gradient inequality [F3] shows $r = p + \nabla f (x^{+}) \in \partial F (x^{+})$ by [F6]. If $d = x^{+} - x$ , [F7] and Lipschitz continuity give $∥ r ∥_{2} \leq L ∥ d ∥_{2} + L ∥ d ∥_{2} = 2 L ∥ d ∥_{2}$ . Step 1.1 therefore yields $F (x^{+}) - F (x_{*}) \leq (2 L^{2} / μ) ∥ d ∥_{2}^{2}$ .

3.1F4step 2.1giveninductionalgebra

By [F4], $F (x) - F (x^{+}) \geq (L / 2) ∥ d ∥_{2}^{2}$ . Combining with step 2.1 gives $F (x) - F (x_{*}) \geq (1 + μ / (4 L)) (F (x^{+}) - F (x_{*}))$ . Apply this at every proximal-gradient step and induct to obtain the stated factor $q^{k}$ .

4.1F5step 1.2giveninductionalgebra∎

Apply [F5] to one FISTA block starting at a restart point $w$ . Step 1.2 gives $∥ w - x_{*} ∥_{2}^{2} \leq 2 (F (w) - F (x_{*})) / μ$ , so the block-end gap is at most $4 L (F (w) - F (x_{*})) / (μ (m + 1)^{2})$ . Since $m + 1 \geq \sqrt{8 L / μ}$ , this factor is at most $1 / 2$ . Each completed restart starts the next block at its last iterate; induction over blocks proves the stated restart-point bound.

Depends on

Used by

Nothing in the library uses this result yet.

Dependency tree · two levels

43 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

Amir Beck, First-Order Methods in Optimization, SIAM, 2017, §§10.6–10.7 (standard reference, not scraped)
Mark Schmidt, Nicolas Le Roux, and Francis Bach, Convergence Rates of Inexact Proximal-Gradient Methods for Convex Optimization, Proposition 3 and Appendix §6.3 (standard reference, not scraped)