Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Equation (2) — the maximum defining Φt\Phi_tΦt​ is attained at θt\theta_tθt​, and Φ1=log⁡d\Phi_1=\log dΦ1​=logd

Proved
AltRegret.eq_2

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

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

Consider the alternation-aware Hedge algorithm with parameters η∈R\eta\in\mathbb Rη∈R and β≥0\beta\ge0β≥0, any loss sequence (with c0=0c_0=\mathbf 0c0​=0) and any round t≥1t\ge1t≥1. Let Rt−1R_{t-1}Rt−1​ be the alternating regret vector and

Gt(θ)=log⁡∑i=1dexp⁡ ⁣[ηRt−1,i−β(ct−1,i−θ)2],Φt=sup⁡θ∈RGt(θ).G_t(\theta)=\log\sum_{i=1}^{d}\exp\!\big[\eta R_{t-1,i}-\beta(c_{t-1,i}-\theta)^2\big],\qquad \Phi_t=\sup_{\theta\in\mathbb R}G_t(\theta).Gt​(θ)=logi=1∑d​exp[ηRt−1,i​−β(ct−1,i​−θ)2],Φt​=θ∈Rsup​Gt​(θ).

Then:

  1. Gt(θ)≤Gt(θt)G_t(\theta)\le G_t(\theta_t)Gt​(θ)≤Gt​(θt​) for every θ∈R\theta\in\mathbb Rθ∈R, where θt\theta_tθt​ is the algorithm's centering scalar;
  2. Φt=Gt(θt)\Phi_t=G_t(\theta_t)Φt​=Gt​(θt​), i.e.
Φt=max⁡θ∈Rlog⁡∑i=1dexp⁡ ⁣[ηRt−1,i−β(ct−1,i−θ)2]=log⁡∑i=1dexp⁡ ⁣[ηRt−1,i−β(ct−1,i−θt)2];\Phi_t=\max_{\theta\in\mathbb R}\log\sum_{i=1}^{d}\exp\!\big[\eta R_{t-1,i}-\beta(c_{t-1,i}-\theta)^2\big]=\log\sum_{i=1}^{d}\exp\!\big[\eta R_{t-1,i}-\beta(c_{t-1,i}-\theta_t)^2\big];Φt​=θ∈Rmax​logi=1∑d​exp[ηRt−1,i​−β(ct−1,i​−θ)2]=logi=1∑d​exp[ηRt−1,i​−β(ct−1,i​−θt​)2];
  1. Φ1=log⁡d\Phi_1=\log dΦ1​=logd.

The identity lets the analysis evaluate the potential at the algorithm's own θt\theta_tθt​, and the initial value log⁡d\log dlogd is where the final bound 8log⁡d8\log d8logd comes from.

Differences from the source:

  • generalization: Algorithm 1 (η = 1/8, β = 1/32), under Lemma 1's assumptions β < 1/2 and c_{t−1} ∈ [−1,1]^d → any real η, any β ≥ 0, no bound on the losses; reason: for β ≥ 0 the objective of line 3 attains its maximum and differs from G_t by the constant η Σ_{s<t}(c_{s−1}+c_s)ᵀx_s, so the algorithm's θ_t (any maximizer) maximizes G_t; the statement specializes to the paper's (η, β) = (1/8, 1/32) with bounded losses
  • encoding: max over θ ∈ ℝ → supremum over θ ∈ ℝ, with clause 1 stating that it is attained at θ_t; reason: Lean convention; for β ≥ 0 the set of values is bounded above, so the supremum is the paper's maximum
  • encoding: [d], c_0 = 0 → Fin d, losses read through lossAt; reason: Lean convention; same instances
  • 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

/-- **Equation (2) and `Φ₁ = log d`.** Tao–Zheng, arXiv:2608.24731, §2.2, p.7, Eq. (2):
"`Φ_t := max_{θ∈ℝ} log(∑_{i=1}^d exp[ηR_{t−1,i} − β(c_{t−1,i} − θ)²]) =
log(∑_{i=1}^d exp[ηR_{t−1,i} − β(c_{t−1,i} − θ_t)²])`. The equality holds by definition of `θ_t`
in Algorithm 1 and the fact that constant terms do not affect the maximizer. Initially,
`Φ₁ = log d`."

For the algorithm with parameters `(η, β)`, any `η` and any `β ≥ 0`, any loss sequence and any
round `t ≥ 1`:
1. the algorithm's `θ_t` maximizes `θ ↦ log ∑_i exp(ηR_{t−1,i} − β(c_{t−1,i} − θ)²)` over `ℝ`;
2. `Φ_t` (a supremum over `ℝ`) equals the value at `θ_t`, so the supremum is a maximum;
3. `Φ₁ = log d`.

**Formalization Note.** `Φ_t` is `⨆ θ : ℝ`. The algorithm is parametrized by `(η, β)`;
Algorithm 1 is `η = 1/8`, `β = 1/32`. The statement needs only `β ≥ 0` (then the θ-objective of
line 3 attains its maximum and the algorithm's `θ_t` is a maximizer), not Lemma 1's `β < 1/2` or a
bound on the losses; it specializes to the paper's setting. For `β < 0` and `d ≥ 1` no maximum
exists. For `d = 0` every quantity is `0 = log 0`. `c₀ = 0` via `lossAt`; natural logarithm. -/
theorem eq_2 {d : ℕ} (η β : ℝ) (hβ : 0 ≤ β) (c : ℕ → Fin d → ℝ) (t : ℕ) (ht : 1 ≤ t) :
    (∀ θ : ℝ, potentialObjective η β c t θ ≤ potentialObjective η β c t (theta η β c t)) ∧
    potential η β c t = potentialObjective η β c t (theta η β c t) ∧
    potential η β c 1 = Real.log d := by sorry

end AltRegret
Source
Tao, Zheng, Optimal Alternating Regret for Online Learning and Games, arXiv:2608.24731, §2.2, p.7, Eq. (2) and "Initially, Φ1 = log d."
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