CorollaryStatement: AI-adaptedProof: 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 fixed-step projected subgradient rate is O(1/√N)

Statement

Under the hypotheses of Projected subgradient best-iterate and weighted-average bound, let $R > 0$ and $G > 0$ and choose the constant stepsize $α_{k} = R / (G \sqrt{N})$ for all $k < N$ . Then $\max {\min_{k < N} (f (x_{k}) - f (x^{*})), f ({\overset{ˉ}{x}}_{N}) - f (x^{*})} \leq \frac{R G}{\sqrt{N}} .$ Thus both reported gaps are $O (N^{- 1 / 2})$ with constants $R, G$ fixed. The schedule is not used when $R = 0$ or $G = 0$ ; in those boundary cases the best-iterate gap is zero under the theorem's hypotheses and bounds below.

Facts & Assumptions

Given: The best-iterate and weighted-average bound Projected subgradient best-iterate and weighted-average bound.

[F1]

The bound is $[R^{2} + G^{2} \sum_{k < N} α_{k}^{2}] / (2 \sum_{k < N} α_{k})$ (Projected subgradient best-iterate and weighted-average bound).

[F2]

The Euclidean norm is definite, so $∥ v ∥_{2} = 0$ implies $v = 0$ (Cauchy-Schwarz $∣ ⟨ x, y ⟩ ∣ \leq ∥ x ∥_{2} ∥ y ∥_{2}$ with its equality case, the triangle inequality for $∥ \cdot ∥_{2}$ , the parallelogram law and polarisation).

[F3]

The algorithm's best observed list includes $x_{0}$ , and $g_{0} \in \partial f (x_{0})$ on a successful first call (Projected subgradient method with finite budget, The projected subgradient method returns within its finite budget, Subgradients and the subdifferential of a convex function).

[F4]

For a constant real $a$ , $\sum_{k < N} a = N a$ by the scaling law for finite sums (Laws of finite sums and finite products).

Proof

1.1F1F4givenalgebra

For $R, G > 0$ , [F4] gives $\sum_{k < N} α_{k} = N R / (G \sqrt{N}) = R \sqrt{N} / G$ and $G^{2} \sum_{k < N} α_{k}^{2} = N R^{2} / N = R^{2}$ . Substituting these values into [F1] gives $(2 R^{2}) / (2 R \sqrt{N} / G) = R G / \sqrt{N}$ .

1.2givenF2F3algebra

If $R = 0$ , then $∥ x_{0} - x^{*} ∥_{2} = 0$ and [F2] gives $x_{0} = x^{*}$ ; by [F3] the best observed list includes this optimizer, so its gap is zero.

2.1givenF2F3algebra∎

If $G = 0$ , the successful first call satisfies $∥ g_{0} ∥_{2} \leq 0$ , so [F2] gives $g_{0} = 0$ . Then $g_{0} \in \partial f (x_{0})$ and the subgradient inequality gives $f (y) \geq f (x_{0})$ for every feasible $y$ ; hence $x_{0}$ is a global minimizer and the best-iterate gap is zero. These boundary cases require no zero stepsize.

Depends on

Used by

Nothing in the library uses this result yet.

Dependency tree · two levels

39 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

Sébastien Bubeck, Convex Optimization: Algorithms and Complexity, §3.1 (standard reference, not scraped)
Dimitri Bertsekas, MIT 6.253 Complete Lecture Notes, Lecture 15 (standard reference, not scraped)