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.

Hedge with two experts over two rounds

Example

Take two experts and two rounds, use learning rate $ϵ = \log 2$ , and fix the full-information loss vectors in advance as $ℓ_{1} = (0, 1)$ and $ℓ_{2} = (1, 0)$ . Hedge starts from $W_{1} = (1, 1)$ , so $x_{1} = (1 / 2, 1 / 2)$ ; after the first vector it has $W_{2} = (1, 1 / 2)$ and $x_{2} = (2 / 3, 1 / 3)$ . The expected sampled loss is $1 / 2 + 2 / 3 = 7 / 6$ . Each fixed expert has total loss $1$ , so the expected static regret is $1 / 6$ .

Example references

Hedge: the weight update and normalized sampling distribution.

Adversary and feedback models: full-information loss vectors fixed before learner randomization.

Static, dynamic, interval, and strongly adaptive regret: expected static regret against the best fixed expert.

The natural logarithm as the inverse of the exponential function: $\log 2$ is the exponent whose exponential is $2$ .

Expectation of a nonnegative or integrable random variable: bounded measurable losses have finite expectations.

Facts & Assumptions

Given: The two fixed loss vectors and the Hedge learning rate in the Example.

[F1]

Hedge: $W_{1} (i) = 1$ , $x_{t} (i) = W_{t} (i) / \sum_{j} W_{t} (j)$ , and $W_{t + 1} (i) = W_{t} (i) \exp (- ϵ ℓ_{t} (i))$ .

[F2]

Adversary and feedback models: the complete loss vector is revealed after the choice, and the sequence is fixed before randomization.

[F3]

Static, dynamic, interval, and strongly adaptive regret: expected static regret is the expectation of sampled cumulative loss minus the best fixed expert's cumulative loss.

[F4]

The expectation of an indicator is the probability of the event and Linearity, monotonicity, and the modulus bound for expectation: a finite categorical draw has expected loss equal to its probability-weighted sum, and finite sums commute with expectation.

[F5]

The natural logarithm as the inverse of the exponential function and The exponential is positive and satisfies $\exp (- x) = 1 / \exp (x)$ : $\exp (\log 2) = 2$ and $\exp (- \log 2) = 1 / 2$ .

[F6]

Expectation of a nonnegative or integrable random variable: expectation is defined for nonnegative or integrable random variables.

[F7]

Online decision protocol: the learner chooses using only its previous history and does not observe the current loss before its choice.

Verification

1.1F1F2F5F7algebra

The learner chooses before round-one feedback by [F7]; the displayed loss vectors are fixed in advance by [F2]. Initially $x_{1} = (1 / 2, 1 / 2)$ . By [F5], the round-one update multiplies expert 2's weight by $1 / 2$ and expert 1's by $1$ , giving $W_{2} = (1, 1 / 2)$ and $x_{2} = (2 / 3, 1 / 3)$ .

2.1F1F2F4F6step 1.1algebra

The mixed losses are $\sum_{i} x_{1} (i) ℓ_{1} (i) = 1 / 2$ and $\sum_{i} x_{2} (i) ℓ_{2} (i) = 2 / 3$ . By [F2], [F4], [F6], and the algorithm's measurable sampling in [F1], these are the expected sampled losses, so the expected cumulative loss is $7 / 6$ .

3.1F3F6step 2.1algebra∎

Expert 1's total loss is $0 + 1 = 1$ , and expert 2's is $1 + 0 = 1$ . Hence the best fixed expert has loss $1$ and [F3] gives expected static regret $7 / 6 - 1 = 1 / 6$ ; the finite losses are integrable by [F6].

Depends on

Used by

Nothing in the library uses this result yet.

Dependency tree · two levels

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