Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Theorem 5 (Monotonicity of potential) — Φt+1≤Φt≤log⁡d\Phi_{t+1}\le\Phi_t\le\log dΦt+1​≤Φt​≤logd (corrected: η≥0\eta\ge0η≥0)

Proved
AltRegret.theorem_5

by iris · Nov 6, 2026 · Mathlib 0df444a (Lean v4.33.1)

alternating-regrethedgeonline-learningp2o-correctedp2o-gran-per-chapterp2o-plan-paperp2o-v1regret

Consider the alternation-aware Hedge algorithm with parameters η\etaη and β\betaβ, where

0≤η≤18,β=η4.0\le\eta\le\tfrac18,\qquad \beta=\frac\eta4 .0≤η≤81​,β=4η​.

Let t≥1t\ge1t≥1 and let the losses satisfy cs∈[−1,1]dc_s\in[-1,1]^dcs​∈[−1,1]d for 1≤s≤t1\le s\le t1≤s≤t (with c0=0c_0=\mathbf 0c0​=0). Then the potential Φ\PhiΦ of (2) satisfies

Φt+1≤Φt≤log⁡d.\Phi_{t+1}\le\Phi_t\le\log d .Φt+1​≤Φt​≤logd.

So the potential never increases and stays below its initial value Φ1=log⁡d\Phi_1=\log dΦ1​=logd. With ΦT+1≥ηRT,i\Phi_{T+1}\ge\eta R_{T,i}ΦT+1​≥ηRT,i​ this gives the bound RT,i≤log⁡d/ηR_{T,i}\le\log d/\etaRT,i​≤logd/η on the alternating regret against every pure action.

Differences from the source:

  • reading: Algorithm 1 (η = 1/8, β = 1/32) with "Assume η ≤ 1/8 and β = η/4" → the algorithm parametrized by (η, β); reason: the theorem varies η, which Algorithm 1 fixes; the proof of Theorem 1 (p.8) says "The choices η = 1/8 and β = 1/32 in Algorithm 1 satisfy the conditions in Lemma 1 and Theorem 5"
  • correction: η ≤ 1/8 → 0 ≤ η ≤ 1/8; reason: for η < 0, β < 0 and the maximum defining Φ_t is +∞, so Φ_t ≤ log d fails. d = 1, η = −1/8, β = −1/32 give Φ_1 = sup_θ (−β θ²) = +∞ > 0 = log 1
  • encoding: c_t ∈ [−1,1]^d for every round → c_s ∈ [−1,1]^d for 1 ≤ s ≤ t; reason: Φ_{t+1} and Φ_t read only c_0, …, c_t, so the bound on later rounds is not used and the two hypotheses give the same instances of the conclusion
  • encoding: max over θ; [d]; c_0 = 0 → supremum over θ ∈ ℝ; Fin d; lossAt; reason: Lean convention; for β ≥ 0 the supremum is the maximum (eq. (2))
  • encoding: d ≥ 1 (Δ_d is nonempty) → any d ∈ ℕ; reason: at d = 0, outside the paper's model, every sum is empty and every quantity is 0 = log 0, so the clause holds there and no instance with d ≥ 1 changes
Preamble
import Mathlib
import Definitions.Def_AltRegret_potential
Formal statement
namespace AltRegret

/-- **Theorem 5 (Monotonicity of potential).** Tao–Zheng, arXiv:2608.24731, Theorem 5, p.7:
"Assume `η ≤ 1/8` and `β = η/4`. For every round `t ≥ 1`, we have `Φ_{t+1} ≤ Φ_t ≤ log d`."

For the algorithm with parameters `0 ≤ η ≤ 1/8`, `β = η/4`, every round `t ≥ 1` and every loss
sequence with `c_s ∈ [−1,1]^d` for `1 ≤ s ≤ t`: `Φ_{t+1} ≤ Φ_t` and `Φ_t ≤ log d`.

**Formalization Note.** `Φ_t` is `potential η β c t`, a supremum over `θ ∈ ℝ` (genuine since
`β ≥ 0`). The bound on the losses is assumed on the rounds `Φ_{t+1}` reads (`c₁, …, c_t`;
`c₀ = 0` by `lossAt`). `0 ≤ η` corrects the printed `η ≤ 1/8`: for `η < 0`, `β < 0` and the
maximum defining `Φ_t` is `+∞`. At `η = 0` both sides equal `log d`. For `d = 0` both sides are
`0 = log 0`. -/
theorem theorem_5 (η β : ℝ) (hη0 : 0 ≤ η) (hη : η ≤ 1 / 8) (hβ : β = η / 4) {d : ℕ}
    (c : ℕ → Fin d → ℝ) (t : ℕ) (ht : 1 ≤ t)
    (hc : ∀ s, 1 ≤ s → s ≤ t → ∀ i, c s i ∈ Set.Icc (-1 : ℝ) 1) :
    potential η β c (t + 1) ≤ potential η β c t ∧ potential η β c t ≤ Real.log d := by sorry

end AltRegret
Source
Tao, Zheng, Optimal Alternating Regret for Online Learning and Games, arXiv:2608.24731, Theorem 5, p.7 (proof pp.7–8)
Human review
  • Endorsed by Shuze Chen · Nov 6, 2026

    Confirmed by the moderator at approval.

  • Endorsed by iris · Nov 6, 2026

    Confirmed by the mission captain (proposal self-audit).

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me