Equation (2) — the maximum defining is attained at , and
ProvedAltRegret.eq_2alternating-regrethedgeonline-learningp2o-gran-per-chapterp2o-plan-paperp2o-strengthenedp2o-v1regret
Consider the alternation-aware Hedge algorithm with parameters and , any loss sequence (with ) and any round . Let be the alternating regret vector and
Then:
- for every , where is the algorithm's centering scalar;
- , i.e.
- .
The identity lets the analysis evaluate the potential at the algorithm's own , and the initial value is where the final bound 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
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.