Lemma 7.1, p. 100 — exact FTRL regret identity
ProvedModernOnlineLearning.FTRL.lemma_7_1ftrlonline-learningp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-bookp2o-v1regret
Let be closed and nonempty, and let minimize over for rounds . For every comparator in the ambient space,
The identity separates comparator regularization from the changes in successive regularized objectives and is the algebraic starting point for FTRL regret bounds.
Formalization Note is the book's because the first-round objective is . Losses are real-valued. The book's final sentence, that does not change the first iterates, follows directly from the run definition and is not included in the Lean equality.
Preamble
import Mathlib import Definitions.Def_ModernOnlineLearning_FTRL_Defs set_option autoImplicit false
Formal statement
namespace ModernOnlineLearning.FTRL
/-- Orabona, Lemma 7.1, p. 100: the exact FTRL regret identity. -/
theorem lemma_7_1
{E : Type*} [NormedAddCommGroup E] [NormedSpace ℝ E]
(V : Set E) (hVclosed : IsClosed V) (hVnonempty : V.Nonempty)
(ψ ℓ : ℕ → E → ℝ) (x : ℕ → E) (T : ℕ)
(hRun : IsFTRLRunUpTo V ψ ℓ x T) (u : E) :
(∑ t ∈ Finset.Icc 1 T, (ℓ t (x t) - ℓ t u)) =
ψ (T + 1) u - ψ 1 (x 1) +
(∑ t ∈ Finset.Icc 1 T,
(F ψ ℓ t (x t) - F ψ ℓ (t + 1) (x (t + 1)) + ℓ t (x t))) +
F ψ ℓ (T + 1) (x (T + 1)) - F ψ ℓ (T + 1) u := by sorry
end ModernOnlineLearning.FTRL
Source
Orabona, arXiv:1912.13213v10, Lemma 7.1, p. 100
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.