TheoremStatement: Literature-sourcedProof: AI-adaptedPipeline-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.

Projected online gradient descent has static regret at most three-halves of DG square-root T

Statement

Let $d, T \geq 1$ be integers, let $K \subseteq R^{d}$ be nonempty, closed, and convex, and let $D, G \geq 0$ be finite bounds such that $∥ u - v ∥_{2} \leq D$ for all $u, v \in K$ and $∥ g_{t} ∥_{2} \leq G$ for every round. Supply $x_{1} \in K$ . On each round, either $f_{t}$ is differentiable and convex on an open convex neighborhood of $K$ and $g_{t} = \nabla f_{t} (x_{t})$ , or $f_{t} : C_{t} \to R$ is convex on a convex set $C_{t} \supseteq K$ and a vector $g_{t} \in \partial f_{t} (x_{t})$ is supplied with $f_{t} (u) \geq f_{t} (x_{t}) + ⟨ g_{t}, u - x_{t} ⟩$ explicitly required for every $u \in K$ ; here $\partial f_{t} (x_{t})$ is the set of vectors satisfying that supporting inequality for every point of $C_{t}$ . Run projected online gradient descent with $η_{t} = D / (G \sqrt{t})$ when $D, G > 0$ , and with the no-op branch $x_{t + 1} = x_{t}$ if $D = 0$ or $G = 0$ . Assume the Axiom of Countable Choice only when $D, G > 0$ . For every realization satisfying these hypotheses and every $u \in K$ , $\sum_{t = 1}^{T} (f_{t} (x_{t}) - f_{t} (u)) \leq \frac{3}{2} D G \sqrt{T} .$ If $D = 0$ or $G = 0$ , this sum is nonpositive. Whenever the finite-horizon loss sum attains a finite minimum on $K$ , the static regret, defined as $\sum_{t = 1}^{T} f_{t} (x_{t}) - \min_{u \in K} \sum_{t = 1}^{T} f_{t} (u)$ , is therefore at most $\frac{3}{2} D G \sqrt{T}$ .

Statement references

Projected online gradient descent: the projected update and its degenerate branches.

Static, dynamic, interval, and strongly adaptive regret: static regret uses a finite attained minimum.

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: open neighborhoods and closed subsets are understood in the Euclidean metric topology.

A convex subset of $R^{m}$ contains every line segment between two of its points: convex sets contain the segment between any two points.

Convex and strictly convex functions on Euclidean convex sets: convexity of a real-valued function on its domain.

The Jacobian matrix of partial derivatives and the gradient in the scalar-valued case: the gradient is the vector of scalar partial derivatives in Euclidean coordinates.

Subgradients and the subdifferential of a convex function: the subdifferential consists of vectors satisfying the supporting inequality on the function's domain.

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

Projection onto a nonempty closed convex set: a nonempty closed convex subset of a real Hilbert space has a unique nearest point under Countable Choice.

Metric projection onto a closed convex set satisfies the variational inequality: the metric projection satisfies the Euclidean variational inequality.

The metric projection onto a closed convex set is nonexpansive: the metric projection is continuous.

Differentiable convex functions are characterized by the gradient inequality: the smooth branch satisfies the comparator inequality.

Facts & Assumptions

Given: The dimensions, horizon, decision set, diameter and gradient bounds in the Statement; the initial point and one of the stated smooth or subgradient branches on each round.

[A1]

The Axiom of Countable Choice ( ${A C}_{ω}$ ): for $D, G > 0$ , Countable Choice is assumed for the existence theorem for nearest points.

[F1]

The Euclidean inner product $⟨ x, y ⟩ = \sum_{k < n} x_{k} y_{k}$ on $R^{n}$ , $R$ and $R^{n}$ for $n \geq 1$ with the Euclidean metric are complete, componentwise from the Cauchy criterion in $R$ , and Hilbert space: with the standard dot product and induced norm, $R^{d}$ is a real Hilbert space for $d \geq 1$ .

[F2]

Projection onto a nonempty closed convex set: under Countable Choice, for each $y \in R^{d}$ there is a unique $P_{K} (y) \in K$ minimizing $∥ y - z ∥_{2}$ over $z \in K$ .

[F3]

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

[F4]

The metric projection onto a closed convex set is nonexpansive: $∥ P_{K} (y) - P_{K} (z) ∥_{2} \leq ∥ y - z ∥_{2}$ , so $P_{K}$ is continuous.

[F5]

Differentiable convex functions are characterized by the gradient inequality: for a differentiable convex function on an open convex domain, $f_{t} (u) \geq f_{t} (x_{t}) + ⟨ \nabla f_{t} (x_{t}), u - x_{t} ⟩$ .

[F6]

Subgradients and the subdifferential of a convex function: $g_{t} \in \partial f_{t} (x_{t})$ gives the supporting inequality on the convex domain, and the Statement explicitly requires it for every $u \in K$ .

[F7]

Static, dynamic, interval, and strongly adaptive regret: static regret uses the finite-horizon minimum only when it is finite and attained.

[F8]

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; open sets contain a ball around each of their points.

[F9]

A convex subset of $R^{m}$ contains every line segment between two of its points and Convex and strictly convex functions on Euclidean convex sets: $K$ and the stated loss domains are convex.

[F10]

The Jacobian matrix of partial derivatives and the gradient in the scalar-valued case: $\nabla f_{t} (x_{t})$ denotes the standard vector of partial derivatives.

[F11]

Projected online gradient descent: for random inputs, $R^{d}$ and $K$ have their Euclidean and relative Borel $σ$ -algebras, and $x_{1}$ and every direction $g_{t}$ , whether supplied or computed as a smooth gradient, are measurable random elements of those spaces.

Proof

1.1givenF1F5F6algebra

If $D = 0$ , the diameter condition and nonemptiness make $K$ a singleton, so $x_{t} = u$ and every loss difference is zero. If $G = 0$ , then $g_{t} = 0$ by the positive-definite Euclidean norm in [F1], and [F5] or [F6] gives $f_{t} (x_{t}) - f_{t} (u) \leq 0$ on each round; the sum is nonpositive. These branches use no projection and no choice axiom. Hence assume $D, G > 0$ .

1.2A1F1F2F4F8F11givenalgebra

By [A1], [F1], [F2], and the closedness of $K$ in the metric topology [F8], the nondegenerate algorithm has a unique projection at every update. For random inputs, [F11] gives $K$ and $R^{d}$ their relative and Euclidean Borel $σ$ -algebras; the inclusion $K ↪ R^{d}$ and vector update are continuous, and [F4] makes $P_{K}$ continuous. Therefore their composition preserves measurability of each iterate.

2.1F1F3step 1.2givenalgebra

Fix $u \in K$ , put $a_{t} = ∥ x_{t} - u ∥_{2}^{2}$ , $y_{t + 1} = x_{t} - η_{t} g_{t}$ , and $x_{t + 1} = P_{K} (y_{t + 1})$ . By [F3], $⟨ y_{t + 1} - x_{t + 1}, u - x_{t + 1} ⟩ \leq 0$ , whence $∥ y_{t + 1} - u ∥_{2}^{2} - ∥ x_{t + 1} - u ∥_{2}^{2} = ∥ y_{t + 1} - x_{t + 1} ∥_{2}^{2} + 2 ⟨ y_{t + 1} - x_{t + 1}, x_{t + 1} - u ⟩ \geq 0$ . Expanding $y_{t + 1}$ therefore gives $a_{t + 1} \leq a_{t} - 2 η_{t} ⟨ g_{t}, x_{t} - u ⟩ + η_{t}^{2} ∥ g_{t} ∥_{2}^{2}$ .

3.1F5F6F9F10givenstep 2.1algebra

The stated domains are convex by [F9], and [F10] identifies the smooth-branch vector $g_{t}$ with the gradient in Euclidean coordinates. Thus in the smooth branch [F5] gives $f_{t} (x_{t}) - f_{t} (u) \leq ⟨ g_{t}, x_{t} - u ⟩$ ; in the nonsmooth branch the same inequality is an explicit hypothesis in the Statement and follows from [F6]. Rearranging step 2.1 and using $∥ g_{t} ∥_{2} \leq G$ yields $f_{t} (x_{t}) - f_{t} (u) \leq (a_{t} - a_{t + 1}) / (2 η_{t}) + η_{t} G^{2} / 2$ .

4.1givenstep 3.1algebra

Since $x_{t}, u \in K$ , the diameter hypothesis gives $0 \leq a_{t} \leq D^{2}$ for every $t$ , while $a_{T + 1} \geq 0$ . Also $1 / η_{t} = G \sqrt{t} / D$ is nondecreasing because $D, G > 0$ . Summing step 3.1 gives $\sum_{t = 1}^{T} (f_{t} (x_{t}) - f_{t} (u)) \leq D^{2} / (2 η_{T}) + (G^{2} / 2) \sum_{t = 1}^{T} η_{t}$ . The exact telescoping identity is $\sum_{t = 1}^{T} (a_{t} - a_{t + 1}) / η_{t} = a_{1} / η_{1} + \sum_{t = 2}^{T} a_{t} (1 / η_{t} - 1 / η_{t - 1}) - a_{T + 1} / η_{T}$ . Every coefficient $1 / η_{t} - 1 / η_{t - 1}$ is nonnegative, so $a_{t} \leq D^{2}$ and $a_{T + 1} \geq 0$ bound this by $D^{2} (1 / η_{1} + \sum_{t = 2}^{T} (1 / η_{t} - 1 / η_{t - 1})) = D^{2} / η_{T}$ .

5.1givenstep 4.1algebra

With $η_{t} = D / (G \sqrt{t})$ , the first term in step 4.1 is $D G \sqrt{T} / 2$ . For every integer $t \geq 1$ , $1 / \sqrt{t} \leq 2 (\sqrt{t} - \sqrt{t - 1})$ because $\sqrt{t} + \sqrt{t - 1} \leq 2 \sqrt{t}$ ; summing telescopically gives $\sum_{t = 1}^{T} 1 / \sqrt{t} \leq 2 \sqrt{T}$ . Thus the second term is at most $D G \sqrt{T}$ , proving the pointwise comparator bound.

6.1F7step 5.1algebra∎

If the finite-horizon loss sum attains a finite minimum at $u^{⋆} \in K$ , substitute $u^{⋆}$ into the bound just proved. The left side becomes the static regret of [F7], giving the stated static-regret consequence.

Depends on

Used by

The projected OGD bound does not cover infeasible comparators Counterexample

Dependency tree · two levels

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