ExampleConstruction: AI-generatedVerification: AI-generatedPipeline-generated

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.

A projected gradient step on an interval

Example

Assume Countable Choice for the nondegenerate projection step. For $K = [0, 1] \subset R$ , let $P_{K} (z)$ be the point in $K$ minimizing $∣ z - v ∣$ . Then $P_{K} (z) = 0$ for $z < 0$ , $P_{K} (z) = z$ for $0 \leq z \leq 1$ , and $P_{K} (z) = 1$ for $z > 1$ . In one OGD round take $D = 1$ , $G = 2$ , $x_{1} = 1 / 4$ , and $f_{1} (x) = 2 x$ with supplied subgradient $g_{1} = 2$ . Then $η_{1} = 1 / 2$ , the unprojected point is $y_{2} = - 3 / 4$ , and the projected point is $x_{2} = 0$ . The number line places the trial point to the left of the thick segment $K$ and marks its nearest point at the left endpoint.

Example references

Projected online gradient descent: the step-size and projected update.

The Axiom of Countable Choice ( ${A C}_{ω}$ ): Countable Choice for the nondegenerate projection branch.

Intervals of $R$ : the nine order-convex forms, nondegeneracy, and length: the closed interval $[0, 1]$ is nonempty when its endpoints are ordered.

The metric topology: a set is open when every one of its points has a ball around it inside the set; closed means open complement: closedness in the real Euclidean metric.

A convex subset of $R^{m}$ contains every line segment between two of its points: convexity of the decision set.

Subgradients and the subdifferential of a convex function: the supporting-inequality meaning of the supplied vector $g_{1}$ .

The Euclidean inner product $⟨ x, y ⟩ = \sum_{k < n} x_{k} y_{k}$ on $R^{n}$ : the norm used for the diameter and gradient bounds.

Metric projection onto a closed convex set satisfies the variational inequality: the criterion used to verify the interval projection.

Facts & Assumptions

Given: $K = [0, 1]$ , $f_{1} (x) = 2 x$ , $x_{1} = 1 / 4$ , $D = 1$ , and $G = 2$ .

[A1]

The Axiom of Countable Choice ( ${A C}_{ω}$ ): the nondegenerate OGD update uses Countable Choice through the metric-projection existence theorem.

[F1]

Intervals of $R$ : the nine order-convex forms, nondegeneracy, and length: $[0, 1] = {x \in R : 0 \leq x \leq 1}$ .

[F2]

The metric topology: a set is open when every one of its points has a ball around it inside the set; closed means open complement: a set is closed when its complement is open, and an open set contains a ball around each of its points.

[F3]

A convex subset of $R^{m}$ contains every line segment between two of its points: a set is convex when it contains every convex combination of two of its points.

[F4]

Metric projection onto a closed convex set satisfies the variational inequality: $p = P_{K} (z)$ if and only if $⟨ z - p, v - p ⟩ \leq 0$ for every $v \in K$ .

[F5]

Subgradients and the subdifferential of a convex function: $g$ is a subgradient at $x$ if $f (v) \geq f (x) + ⟨ g, v - x ⟩$ for every point $v$ of the convex domain.

[F6]

Projected online gradient descent: when $D, G > 0$ , $η_{t} = D / (G \sqrt{t})$ and $x_{t + 1} = P_{K} (x_{t} - η_{t} g_{t})$ .

[F7]

The Euclidean inner product $⟨ x, y ⟩ = \sum_{k < n} x_{k} y_{k}$ on $R^{n}$ : on $R$ , $∥ g ∥_{2} = ∣ g ∣$ .

[F8]

Projection onto a nonempty closed convex set: under Countable Choice, the metric projection onto $K$ exists and is unique.

Verification

1.1F1F2F3givenalgebra

The interval $[0, 1]$ is nonempty because $0 \in K$ . For $u, v \in K$ and $λ \in [0, 1]$ , $0 \leq (1 - λ) u + λ v \leq (1 - λ) + λ = 1$ , so [F3] makes $K$ convex. Its complement is $(- \infty, 0) \cup (1, \infty)$ . If $z < 0$ , the ball of radius $- z / 2$ about $z$ lies in $(- \infty, 0)$ ; if $z > 1$ , the ball of radius $(z - 1) / 2$ about $z$ lies in $(1, \infty)$ . Thus the complement is open by [F2], so $K$ is closed. Also $∣ u - v ∣ \leq 1$ for $u, v \in K$ , with equality at the endpoints, so its diameter is $1$ .

1.2A1F1F4F8cases

By [A1] and [F8], the projection exists uniquely. If $z < 0$ , then for every $v \in [0, 1]$ , $(z - 0) (v - 0) \leq 0$ , so [F4] and uniqueness give $P_{K} (z) = 0$ . If $0 \leq z \leq 1$ , then $z \in K$ and its distance to itself is zero, so $P_{K} (z) = z$ . If $z > 1$ , then $(z - 1) (v - 1) \leq 0$ for every $v \in [0, 1]$ , and [F4] and uniqueness give $P_{K} (z) = 1$ . These cases prove the stated projection formula.

2.1F5F6F7givenstep 1.2algebra∎

For every $v \in R$ , $f_{1} (v) = 2 v = f_{1} (x_{1}) + 2 (v - x_{1})$ , so [F5] makes $g_{1} = 2$ a valid subgradient and [F7] gives $∥ g_{1} ∥_{2} = 2 = G$ . Hence [F6] gives $η_{1} = 1 / 2$ and $y_{2} = x_{1} - η_{1} g_{1} = 1 / 4 - 1 = - 3 / 4$ . By step 1.2, $x_{2} = P_{K} (y_{2}) = 0$ .

Depends on

Used by

Nothing in the library uses this result yet.

Dependency tree · two levels

54 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

Elad Hazan, Introduction to Online Convex Optimization, second edition (standard reference, not scraped)
Tengyu Ma, Lecture Notes for Machine Learning Theory, Chapter 11 (standard reference, not scraped)