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

Randomized weighted majority with full information

Definition

Let $k, T$ be positive integers, let $η > 0$ , and let $[k] = {1, \dots, k}$ . The input also supplies a full-information loss process: before the round- $t$ action draw, its vector $ℓ_{t} \in [0, 1]^{k}$ is fixed using only the previous transcript and any external randomness, and the vector is revealed after the draw. Put $H_{t} = ([k] \times [0, 1]^{k})^{t - 1}$ , with $H_{1} = {()}$ , and give $H_{t}$ its power-set sigma-algebra; these histories have finite length but need not be finite sets. Initialize $w_{1, j} = 1$ for each $j \in [k]$ . At round $t$ , given $h_{t - 1} = ((a_{s}, ℓ_{s}))_{s < t}$ , compute $p_{t, j} = \frac{w_{t, j}}{\sum_{r = 1}^{k} w_{t, r}} .$ Draw $a_{t} = j$ with probability $p_{t, j}$ , observe the entire vector $ℓ_{t}$ , and update $w_{t + 1, j} = w_{t, j} \exp (- η ℓ_{t} (j))$ . Equivalently, the conditional action kernel is $K_{t} (h_{t - 1}, A) = \sum_{j \in A} p_{t, j}$ for each $A \subseteq [k]$ . The action draw uses fresh randomness independent of the loss process, so its conditional law given the past and the already fixed current loss vector is $K_{t}$ . Return the action transcript $(a_{1}, \dots, a_{T})$ .

Definition references

The real exponential function

Probability measures on finite action spaces

Probability kernels for the conditional action laws

Cynthia Dwork and Aaron Roth, The Algorithmic Foundations of Differential Privacy, Algorithm 15, printed pp. 223–224, and Algorithm 16, printed pp. 224–225: full text.

Facts & Assumptions

Given: Positive integers $k, T$ , an update parameter $η > 0$ , and full-information loss vectors in $[0, 1]^{k}$ .

[F1]

The real exponential is finite at every real input and is strictly positive there. The real exponential function and the number $e$ by a power series, The exponential is positive and satisfies $\exp (- x) = 1 / \exp (x)$

[F2]

A measurable space is a set equipped with a sigma-algebra; a power-set sigma-algebra makes every subset measurable. Measurable spaces and measurable sets

[F3]

A probability measure has total mass one. Probability measures and probability spaces

[F4]

A probability kernel has probability-measure sections and measurable event evaluations. Measure kernel and probability kernel

Verification

Given: The hypotheses and procedure in the Definition.

1.1givenF1constructinduction

By induction on $t$ , each $w_{t, j}$ is finite and strictly positive: this holds initially since $w_{1, j} = 1$ , and each update multiplies such a weight by the finite positive number $\exp (- η ℓ_{t} (j))$ from [F1]. Since $[k]$ is finite and nonempty, $Z_{t} : = \sum_{r = 1}^{k} w_{t, r}$ is finite and strictly positive, so every $p_{t, j}$ is defined and nonnegative.

2.1F2F3F4step 1.1algebra∎

The finite sum of the action probabilities is $\sum_{j = 1}^{k} p_{t, j} = Z_{t} / Z_{t} = 1$ . For each history $h$ , define $μ_{t}^{h} (A) = \sum_{j \in A} p_{t, j} (h)$ for $A \subseteq [k]$ . This is countably additive because a pairwise disjoint family of subsets of the finite set $[k]$ has only finitely many nonempty members, and $μ_{t}^{h} ([k]) = 1$ . For each event $A$ , the map $h \mapsto μ_{t}^{h} (A)$ is measurable since $H_{t}$ has its power-set sigma-algebra. Hence $K_{t}$ is a probability kernel by [F3] and [F4].

Source notes

This is the full-information finite-action procedure. Its regret and privacy claims are proved separately; this definition alone makes no regret or privacy assertion.

Depends on

Used by

Dependency tree · two levels

17 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

Cynthia Dwork and Aaron Roth, The Algorithmic Foundations of Differential Privacy, Chapter 11 §11.2 (standard reference, not scraped)