Theorem 1, p. 6 — EXP2 has full-information regret at least 0.01 d^{3/2}√n on some action set, for every η
ProvedOnlineCombOpt.Exp2LB.theorem_1Consider online combinatorial optimization with full information: at each round the player draws an action from a finite set whose elements all have the same number of ones, the adversary chooses a loss vector , and the player pays and then observes . The regret is .
Theorem. Let , with a multiple of . There is a nonempty set with for all (for some ) such that, for every learning rate , there is an adversary against which the exponentially weighted forecaster EXP2 (Figure 2) with learning rate has regret
Since online mirror descent with the negative entropy achieves regret of order , which for this (with ) is of order , the theorem shows that EXP2 is suboptimal by a factor for every choice of its learning rate. It answers a question of Koolen, Warmuth and Kivinen.
Formalization Note The order of quantifiers is the paper's: is chosen before , and the adversary after . The hypothesis " a multiple of " is the proof's own simplifying assumption (App. A, p. 14), added because the printed statement is false for : every with constant norm is a singleton, so the regret is . The parity of , also assumed in App. A, is not added. The adversary is exhibited as a deterministic, oblivious loss sequence with values in ; this is a special case of the paper's adaptive adversaries, so the existential is at least as strong as the paper's . Against such an adversary the expectation in is the finite sum . (uniform play) is included. is , and is the real .
Retired 2026-10-27: a Lean-vs-paper fidelity audit found this statement weaker than, or narrower than, the cited result. A corrected statement will be resubmitted.
import Mathlib import Definitions.Def_OnlineCombOpt_Exp2LB_Setting open Finset
namespace OnlineCombOpt.Exp2LB
/-- Theorem 1 (Audibert, Bubeck, Lugosi, arXiv:1204.4710v2, p. 6): let `n ≥ d` (with `d` a multiple
of 4). There is an action set `A ⊆ {0,1}^d` with constant `‖a‖₁` such that, for every learning rate
`η ≥ 0`, some adversary with losses in `[0,1]^d` forces full-information EXP2 to regret
`R_n ≥ 0.01 d^{3/2} √n`. -/
theorem theorem_1 (n d : ℕ) (hd : 4 ∣ d) (hnd : d ≤ n) :
∃ (A : Finset (Fin d → ℝ)) (m : ℕ), IsBinaryActionSet A m ∧
∀ η : ℝ, 0 ≤ η → ∃ z : ℕ → Fin d → ℝ, (∀ t i, z t i ∈ Set.Icc (0 : ℝ) 1) ∧
(1 : ℝ) / 100 * d * Real.sqrt d * Real.sqrt n ≤ exp2Regret A η z n := by sorry
end OnlineCombOpt.Exp2LB
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.