Lemma 7.49, p. 131 — stability of regularized linear minimizers
ProvedModernOnlineLearning.FTRL.lemma_7_49ftrlonline-learningp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-bookp2o-v1stability
Let be -strongly convex on a nonempty, closed and convex feasible set , where . For dual vectors and , let minimize over . Then
The lemma controls how much a regularized linear prediction can change when its linear term changes.
Formalization Note The two minimizers are supplied rather than selected by a choice operator. Dual vectors are continuous linear functionals, and their operator norm is .
Preamble
import Mathlib import Definitions.Def_ModernOnlineLearning_FTRL_Defs set_option autoImplicit false
Formal statement
namespace ModernOnlineLearning.FTRL
/-- Orabona, Lemma 7.49, p. 131: sensitivity of a regularized linear minimizer. -/
theorem lemma_7_49
{E : Type*} [NormedAddCommGroup E] [NormedSpace ℝ E]
(V : Set E) (hVclosed : IsClosed V) (hVconvex : Convex ℝ V)
(hVnonempty : V.Nonempty) (ψ : E → ℝ)
(lam : ℝ) (hlam : 0 < lam) (hStrong : StrongConvexOn V lam ψ)
(θ₁ θ₂ : E →L[ℝ] ℝ) (x₁ x₂ : E)
(hx₁ : IsMinimizerOn V (fun z => ψ z + θ₁ z) x₁)
(hx₂ : IsMinimizerOn V (fun z => ψ z + θ₂ z) x₂) :
‖x₁ - x₂‖ ≤ (1 / lam) * ‖θ₁ - θ₂‖ := by sorry
end ModernOnlineLearning.FTRL
Source
Orabona, arXiv:1912.13213v10, Lemma 7.49, p. 131
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.