Lemma 7.7, pp. 102–103 — proximal regularizers
ProvedModernOnlineLearning.FTRL.lemma_7_7ftrlonline-learningp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-bookp2o-v1proximal-regularization
Let be nonempty, closed and convex. Suppose is closed, subdifferentiable and -strongly convex on , with . Let be an FTRL minimizer that also minimizes on . Then has a unique minimizer . For every ,
The proximal condition evaluates the regularizer change at the current iterate and provides a second stability bound for FTRL.
Formalization Note The existence assertion is explicit. The book's nonempty subdifferential hypothesis is represented before universally quantifying over its elements.
Preamble
import Mathlib import Definitions.Def_ModernOnlineLearning_FTRL_Defs set_option autoImplicit false
Formal statement
namespace ModernOnlineLearning.FTRL
/-- Orabona, Lemma 7.7, pp. 102–103: the proximal-regularizer stability chain. -/
theorem lemma_7_7
{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)
(hFnextClosed : IsClosedFunctionOn V (F ψ ℓ (t + 1)))
(hFnextSubdiff : IsSubdifferentiableOn V (F ψ ℓ (t + 1)))
(hFnextStrong : StrongConvexOn V lam (F ψ ℓ (t + 1)))
(x : E) (hx : IsMinimizerOn V (F ψ ℓ t) x)
(hprox : IsMinimizerOn V (fun z => ψ (t + 1) z - ψ t z) x) :
(∃! y : E, IsMinimizerOn V (F ψ ℓ (t + 1)) y) ∧
∀ y : E, 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 x - ψ (t + 1) x ∧
g (x - y) - lam / 2 * ‖x - y‖ ^ 2 + ψ t x - ψ (t + 1) x ≤
‖g‖ ^ 2 / (2 * lam) + ψ t x - ψ (t + 1) x := by sorry
end ModernOnlineLearning.FTRL
Source
Orabona, arXiv:1912.13213v10, Lemma 7.7, pp. 102–103
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.