Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

§6.6, p. 81 — Exponentiated Gradient regret on the simplex

Proved
ModernOnlineLearning.ToX.eg_regret_6_6

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

exponentiated-gradientonline-learningp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-bookp2o-v1regret

Let d,T≥1d,T\ge1d,T≥1 and η>0\eta>0η>0. Run Exponentiated Gradient from the uniform point on Δd−1\Delta^{d-1}Δd−1 against losses ℓt\ell_tℓt​, choosing a subgradient gtg_tgt​ at each prediction xtx_txt​. Then for every fixed u∈Δd−1u\in\Delta^{d-1}u∈Δd−1,

∑t=1T(ℓt(xt)−ℓt(u))≤ln⁡dη+η2∑t=1T∥gt∥∞2.\sum_{t=1}^T\bigl(\ell_t(x_t)-\ell_t(u)\bigr) \le\frac{\ln d}{\eta}+\frac\eta2\sum_{t=1}^T\|g_t\|_\infty^2.t=1∑T​(ℓt​(xt​)−ℓt​(u))≤ηlnd​+2η​t=1∑T​∥gt​∥∞2​.

This is the regret estimate used with Theorem 16.4 to obtain the finite-class bound in Corollary 16.7.

Formalization Note Losses are represented by real-valued functions and the chosen subgradient satisfies the subgradient inequality for every comparator in the simplex. This records exactly the part of the book's extended-valued subgradient condition used by the regret estimate. The infinity norm is the maximum coordinate absolute value. The run predicate explicitly fixes the uniform initial point and the update rule of Algorithm 6.2.

Preamble
import Mathlib
import Definitions.Def_ModernOnlineLearning_ToX_Algorithms
Formal statement
namespace ModernOnlineLearning.ToX

/-- The unnumbered EG regret display of §6.6, p. 81.
`IsEGRun` is Algorithm 6.2, p. 80; each `g t` is a subgradient of
the round's loss at `x t`. -/
theorem eg_regret_6_6 {d T : ℕ} [NeZero d] (hT : 1 ≤ T)
    (η : ℝ) (g x : ℕ → Fin d → ℝ)
    (loss : ℕ → (Fin d → ℝ) → ℝ)
    (hRun : IsEGRun T η g x)
    (hsub : ∀ t ∈ Finset.Icc 1 T, ∀ y ∈ simplex d,
      loss t (x t) + pairing (g t) (y - x t) ≤ loss t y) :
    ∀ u ∈ simplex d,
      (∑ t ∈ Finset.Icc 1 T, (loss t (x t) - loss t u)) ≤
        Real.log (d : ℝ) / η +
          η / 2 * ∑ t ∈ Finset.Icc 1 T,
            (Finset.univ.sup' Finset.univ_nonempty
              (fun i : Fin d => |g t i|)) ^ 2 := by sorry

end ModernOnlineLearning.ToX
Source
Orabona, arXiv:1912.13213v10, §6.6, p. 81, first display after Lemma 6.33; Algorithm 6.2, p. 80
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