ExampleConstruction: AI-generatedVerification: AI-generatedPipeline-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.

A changing comparator separates static and dynamic regret

Example

Let $K = [0, 1]$ with norm $∣ \cdot ∣$ , horizon $T = 3$ , losses $f_{1} (x) = x$ , $f_{2} (x) = 1 - x$ , and $f_{3} (x) = x$ , and learner choices $x_{1} = x_{2} = x_{3} = 1 / 2$ . The realized static regret is $1 / 2$ . For the changing comparator $u_{1} = 0, u_{2} = 1, u_{3} = 0$ , the dynamic regret is $3 / 2$ and the path length is $3$ . The maximum static regret over all nonempty contiguous intervals is $1 / 2$ .

Example references

Online decision protocol: the horizon, actions, and round losses form a finite-horizon online protocol.

Static, dynamic, interval, and strongly adaptive regret: static, dynamic, path-length, interval, and adaptive regret conventions.

Elad Hazan, Introduction to Online Convex Optimization, second edition: §§10.1–10.2, PDF pp. 190–193.

Facts & Assumptions

Given: $K = [0, 1]$ , $T = 3$ , $f_{1} (x) = x$ , $f_{2} (x) = 1 - x$ , $f_{3} (x) = x$ , learner choices $x_{t} = 1 / 2$ , and comparator sequence $(0, 1, 0)$ .

[F1]

An online protocol fixes the horizon and action set; each learner choice uses only earlier revealed history and available private randomness and is made before its current loss is observed. The environment may fix each loss before the choice or select it afterward, as specified by its model (Online decision protocol).

[F2]

Static regret compares with one fixed minimizer; dynamic regret compares with a supplied sequence; path length is $1 + \sum_{t < T} ∥ u_{t} - u_{t + 1} ∥$ ; interval regret minimizes cumulative loss over one comparator on that interval (Static, dynamic, interval, and strongly adaptive regret).

Verification

1.1givenF1F2algebra

The learner's losses are $1 / 2, 1 / 2, 1 / 2$ , so their sum is $3 / 2$ . For any fixed $u \in [0, 1]$ , the cumulative loss is $u + (1 - u) + u = 1 + u$ , whose minimum is $1$ at $u = 0$ . Thus static regret is $3 / 2 - 1 = 1 / 2$ .

1.2givenF2algebra

The comparator losses are $f_{1} (0) = 0$ , $f_{2} (1) = 0$ , and $f_{3} (0) = 0$ , so its total loss is zero and dynamic regret is $3 / 2$ . Its path length is $1 + ∣ 0 - 1 ∣ + ∣ 1 - 0 ∣ = 3$ .

2.1givenF2algebra∎

The singleton interval regrets are $1 / 2$ on each of $[1, 1]$ , $[2, 2]$ , and $[3, 3]$ , because each learner loss is $1 / 2$ and each corresponding linear loss has minimum $0$ . On $[1, 2]$ and $[2, 3]$ , the cumulative loss is identically $1$ , as $f_{1} + f_{2} = 1$ and $f_{2} + f_{3} = 1$ , so both regrets are zero. On $[1, 3]$ , the cumulative loss is $1 + x$ , its minimum is $1$ , and the learner incurs $3 / 2$ , so its regret is $1 / 2$ . The maximum over these six nonempty contiguous intervals is therefore $1 / 2$ .

Depends on

Used by

Nothing in the library uses this result yet.

Dependency tree · two levels

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