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

Replacing one full loss vector changes a later action kernel

Example

Let $k = 2$ , $T = 3$ , and $η > 0$ . Compare the all-zero loss sequence with the sequence whose second loss vector is $(1, 0)$ and whose first and third vectors are zero. These two fixed inputs differ by replacement of one complete time-step vector. For both inputs the first- and second-round action kernels are uniform on ${1, 2}$ . At round three the all-zero input has weights $(1, 1)$ and probabilities $(1 / 2, 1 / 2)$ , while the replaced input has weights $(e^{- η}, 1)$ and probabilities $(1 / (1 + e^{η}), e^{η} / (1 + e^{η}))$ . In particular, the event that the third action is $1$ has probability ratio $(1 + e^{η}) / 2$ between the all-zero and replaced inputs.

Example references

Full-information exponential-weight procedure

Per-round replacement privacy guarantee

Dwork and Roth, The Algorithmic Foundations of Differential Privacy, Chapter 11 §11.2: full text.

Facts & Assumptions

Given: Two-action, three-round loss sequences, with $η > 0$ and all loss vectors in $[0, 1]^{2}$ .

[F1]

The algorithm initializes both weights at one, draws from their normalized values, and after each round multiplies action $j$ 's weight by $\exp (- η ℓ_{t} (j))$ . Randomized weighted majority with full information

[F2]

Replacing one whole vector at one time step is the adjacency relation used for the online privacy theorem; for every common prior history the action kernel satisfies ordered $(2 η, 0)$ event inequalities. Private online learning regret under composition

Verification

Given: The two loss sequences in the Example and [F1]–[F2].

1.1givenF1F2

The sequences agree at rounds one and three and differ only at round two, where $(0, 0)$ is replaced by $(1, 0)$ , so they are adjacent by [F2]. Both start with weights $(1, 1)$ , and the common first loss vector $(0, 0)$ leaves those weights unchanged; hence the first- and second-round kernels are uniform.

2.1F1step 1.1algebra

After the second loss vector, the all-zero input still has weights $(1, 1)$ , while the replaced input has weights $(e^{- η}, 1)$ . Dividing by their normalizers yields $(1 / 2, 1 / 2)$ and $(e^{- η} / (1 + e^{- η}), 1 / (1 + e^{- η})) = (1 / (1 + e^{η}), e^{η} / (1 + e^{η}))$ .

3.1F2step 2.1algebra∎

For the event ${1}$ at round three, the all-zero probability divided by the replaced-input probability is $(1 / 2) / (1 / (1 + e^{η})) = (1 + e^{η}) / 2$ . Thus the third-round kernels differ, while their ordered ratios remain covered by the theorem's $(2 η, 0)$ bound from [F2]; this calculation makes no claim that a transcript-level privacy bound fails.

Depends on

Used by

Nothing in the library uses this result yet.

Dependency tree · two levels

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