Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Theorem 1, p. 6 — EXP2 has full-information regret at least 0.01 d^{3/2}√n on some action set, for every η

Proved
OnlineCombOpt.Exp2LB.theorem_1

by mikedeng1 · Oct 8, 2026 · Mathlib 0df444a (Lean v4.33.1)

exponential-weightslower-boundonline-combinatorial-optimizationp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1regret

Consider online combinatorial optimization with full information: at each round t=1,…,nt=1,\dots,nt=1,…,n the player draws an action ata_tat​ from a finite set A⊆{0,1}d\mathcal A\subseteq\{0,1\}^dA⊆{0,1}d whose elements all have the same number mmm of ones, the adversary chooses a loss vector zt∈[0,1]dz_t\in[0,1]^dzt​∈[0,1]d, and the player pays at⊤zta_t^\top z_tat⊤​zt​ and then observes ztz_tzt​. The regret is Rn=E∑t=1nat⊤zt−min⁡a∈A∑t=1na⊤ztR_n=\mathbb E\sum_{t=1}^n a_t^\top z_t-\min_{a\in\mathcal A}\sum_{t=1}^n a^\top z_tRn​=E∑t=1n​at⊤​zt​−mina∈A​∑t=1n​a⊤zt​.

Theorem. Let n≥dn\ge dn≥d, with ddd a multiple of 444. There is a nonempty set A⊆{0,1}d\mathcal A\subseteq\{0,1\}^dA⊆{0,1}d with ∥a∥1=m\|a\|_1=m∥a∥1​=m for all a∈Aa\in\mathcal Aa∈A (for some mmm) such that, for every learning rate η≥0\eta\ge 0η≥0, there is an adversary z1,…,zn∈[0,1]dz_1,\dots,z_n\in[0,1]^dz1​,…,zn​∈[0,1]d against which the exponentially weighted forecaster EXP2 (Figure 2) with learning rate η\etaη has regret

Rn  ≥  0.01 d3/2n.R_n\;\ge\;0.01\,d^{3/2}\sqrt n .Rn​≥0.01d3/2n​.

Since online mirror descent with the negative entropy achieves regret of order mnlog⁡(d/m)m\sqrt{n\log(d/m)}mnlog(d/m)​, which for this A\mathcal AA (with m=d/2m=d/2m=d/2) is of order dnd\sqrt ndn​, the theorem shows that EXP2 is suboptimal by a factor d\sqrt dd​ 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: A\mathcal AA is chosen before η\etaη, and the adversary after η\etaη. The hypothesis "ddd a multiple of 444" is the proof's own simplifying assumption (App. A, p. 14), added because the printed statement is false for d=1d=1d=1: every A⊆{0,1}1\mathcal A\subseteq\{0,1\}^1A⊆{0,1}1 with constant norm is a singleton, so the regret is 000. The parity of nnn, also assumed in App. A, is not added. The adversary is exhibited as a deterministic, oblivious loss sequence with values in [0,1]d[0,1]^d[0,1]d; this is a special case of the paper's adaptive adversaries, so the existential is at least as strong as the paper's sup⁡adversary\sup_{\text{adversary}}supadversary​. Against such an adversary the expectation in RnR_nRn​ is the finite sum ∑t∑apt(a) a⊤zt\sum_t\sum_a p_t(a)\,a^\top z_t∑t​∑a​pt​(a)a⊤zt​. η=0\eta=0η=0 (uniform play) is included. d3/2d^{3/2}d3/2 is ddd\sqrt ddd​, and 0.010.010.01 is the real 1/1001/1001/100.


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.

Preamble
import Mathlib
import Definitions.Def_OnlineCombOpt_Exp2LB_Setting

open Finset
Formal statement
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
Source
Audibert, Bubeck, Lugosi, Regret in Online Combinatorial Optimization, arXiv:1204.4710v2, p. 6, Theorem 1 (proof in App. A, pp. 14–16)
Human review
  • Endorsed by Shuze Chen · Oct 9, 2026

    Confirmed by the moderator at approval.

  • Endorsed by mikedeng1 · Oct 9, 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