LemmaStatement: 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 projected subgradient method returns within its finite budget

Statement

Let $N \geq 1$ be an integer and run Projected subgradient method with finite budget with all stated inputs. Every execution returns after at most $N$ oracle calls. On failure it returns the feasible current iterate and a best observed point if one has been observed, or none otherwise; it does not return a full-horizon average. If all calls succeed, the weighted average is defined and feasible, a best observed iterate exists, and the status is budget-exhausted after exactly $N$ updates.

Facts & Assumptions

Given: A nonempty closed convex feasible set, a finite budget, positive stepsizes, and the oracle/failure rules of Projected subgradient method with finite budget.

[F1]

Every point has a unique nearest-point projection onto a nonempty closed convex set (Every point has a unique nearest point in a nonempty closed Euclidean convex set).

[F2]

A convex combination of feasible points remains feasible (Finite Jensen inequality for convex functions on $R^{n}$ ).

[F3]

A nonempty finite list of real values has a minimum attained at one of its members (Every nonempty finite set of reals has a maximum and a minimum, Maximum and minimum of a set); scanning the list in increasing index order and replacing the record only on a strict decrease yields the least-index minimizer, by induction on the finite list length.

[F4]

A finite sum of nonnegative terms is nonnegative, and a zero sum forces every term to be zero; therefore a nonempty finite sum of strictly positive terms is strictly positive (Laws of finite sums and finite products).

Proof

1.1givenF1induction

Initially $x_{0} \in C$ . At each successful oracle call, if $x_{k} \in C$ , [F1] gives a unique projected point $x_{k + 1} \in C$ . Induction over the successful calls proves feasibility and unique definition of each iterate through at most $N$ calls.

2.1givenF2F3F4step 1.1algebra∎

A failed call returns immediately; if no earlier value was observed, the optional best field is none, and otherwise [F3] supplies a least-index best among the finite observed list. If all calls succeed, $N \geq 1$ and every $α_{k} > 0$ , so $A_{N} = \sum_{k < N} α_{k} > 0$ by [F4]. The weights $α_{k} / A_{N}$ are positive and sum to one by the scaling law for finite sums; [F2] makes the weighted average feasible, and [F3] gives a least-index best observed point. The finite loop completes exactly $N$ updates and returns budget-exhausted.

Depends on

Used by

Cited to discharge well-definedness by Projected subgradient method with finite budget.

Dependency tree · two levels

30 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)