Lemma 7.5, p. 101 — existence, uniqueness, and FTRL stability
ProvedModernOnlineLearning.FTRL.lemma_7_5ftrlonline-learningp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-bookp2o-v1strong-convexity
Let be nonempty, closed and convex. Suppose is closed, subdifferentiable and strongly convex on . Then it has a unique minimizer . Suppose also that is closed, subdifferentiable and -strongly convex on , with . For any minimizer of and any subgradient ,
This bounds the change in objective values by the dual norm of a loss subgradient and the change in regularizer.
Formalization Note Existence of is stated by quantifying over any such minimizer; the lemma's existence assertion concerns . Subgradients are full-space continuous linear functionals. The positivity of makes the printed denominator meaningful.
Preamble
import Mathlib import Definitions.Def_ModernOnlineLearning_FTRL_Defs set_option autoImplicit false
Formal statement
namespace ModernOnlineLearning.FTRL
/-- Orabona, Lemma 7.5, p. 101: existence, uniqueness, and the FTRL stability chain. -/
theorem lemma_7_5
{E : Type*} [NormedAddCommGroup E] [NormedSpace ℝ E]
[FiniteDimensional ℝ E]
(V : Set E) (hVclosed : IsClosed V) (hVconvex : Convex ℝ V)
(hVnonempty : V.Nonempty) (ψ ℓ : ℕ → E → ℝ) (t : ℕ) (ht : 1 ≤ t)
(lam : ℝ) (hlam : 0 < lam)
(hFtClosed : IsClosedFunctionOn V (F ψ ℓ t))
(hFtSubdiff : IsSubdifferentiableOn V (F ψ ℓ t))
(hFtStrong : ∃ κ : ℝ, 0 < κ ∧ StrongConvexOn V κ (F ψ ℓ t))
(hFtlClosed : IsClosedFunctionOn V (fun y => F ψ ℓ t y + ℓ t y))
(hFtlSubdiff : IsSubdifferentiableOn V (fun y => F ψ ℓ t y + ℓ t y))
(hFtlStrong : StrongConvexOn V lam (fun y => F ψ ℓ t y + ℓ t y)) :
(∃! z : E, IsMinimizerOn V (F ψ ℓ t) z) ∧
∀ (x y : E), IsMinimizerOn V (F ψ ℓ t) x →
IsMinimizerOn V (F ψ ℓ (t + 1)) y →
(∃ g : E →L[ℝ] ℝ, IsSubgradientAt (ℓ t) x g) →
∀ g : E →L[ℝ] ℝ, IsSubgradientAt (ℓ t) x g →
F ψ ℓ t x - F ψ ℓ (t + 1) y + ℓ t x ≤
g (x - y) - lam / 2 * ‖x - y‖ ^ 2 + ψ t y - ψ (t + 1) y ∧
g (x - y) - lam / 2 * ‖x - y‖ ^ 2 + ψ t y - ψ (t + 1) y ≤
‖g‖ ^ 2 / (2 * lam) + ψ t y - ψ (t + 1) y := by sorry
end ModernOnlineLearning.FTRL
Source
Orabona, arXiv:1912.13213v10, Lemma 7.5, p. 101
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.