§4.2.1 — gradient of , the bound , and convexity
ProvedForecastAggLearn.barL_gradient_convexforecast-aggregationonline-learningp2o-gran-per-chapterp2o-plan-paperp2o-v1probability
Let , and , and let be the loss (4). For every :
- the gradient of at is
- ;
- the Hessian is positive semidefinite;
- is convex on .
These are the hypotheses of online gradient descent (Lemma 1): convex losses whose gradients are bounded by .
Formalization Note The Hessian is the second Fréchet derivative, and positive semidefiniteness is for all .
Differences from the source:
- encoding: ∇²L̄_t(h) is positive semidefinite → fderiv ℝ (fderiv ℝ L̄) h v v ≥ 0 for all v; reason: the Hessian's quadratic form is the second Fréchet derivative on the diagonal
Preamble
import Mathlib import Definitions.Def_ForecastAggLearn_barL
Formal statement
namespace ForecastAggLearn
/-- **Gradient, gradient bound and convexity of `L̄_t`.**
Babichenko, Garber, arXiv:1802.07107v1, §4.2.1, p.18: "the gradient vector of L̄_t(h) is given by
∇L̄_t(h) = (1 − ω_t) z̃_t − exp(−h · z̃_t − µ̃_t)/(1 + exp(−h · z̃_t − µ̃_t)) z̃_t. Note also that for all
t ∈ [T], h ∈ ℝⁿ, since ω_t ∈ {0, 1}, we have that ‖∇L̄_t(h)‖ ≤ ‖z̃_t‖. Finally, [...] the Hessian
matrix of L̄_t(h), i.e., ∇²L̄_t(h), is positive semidefinite and hence, for all t ∈ [T], L̄_t(h) is
a convex function."
**Formalization Note.** On `EuclideanSpace ℝ (Fin n)`; `1 − ω_t` is `if ω then 0 else 1`. The
Hessian quadratic form is `v ↦ D²L̄_t(h)(v, v)`, the second Fréchet derivative. -/
theorem barL_gradient_convex {n : ℕ} (z : EuclideanSpace ℝ (Fin n)) (μt : ℝ) (ω : Bool) :
(∀ h, HasGradientAt (barL z μt ω)
((if ω then (0 : ℝ) else 1) • z -
(Real.exp (-(inner ℝ h z) - μt) / (1 + Real.exp (-(inner ℝ h z) - μt))) • z) h) ∧
(∀ h, ‖(if ω then (0 : ℝ) else 1) • z -
(Real.exp (-(inner ℝ h z) - μt) / (1 + Real.exp (-(inner ℝ h z) - μt))) • z‖ ≤ ‖z‖) ∧
(∀ h v, 0 ≤ fderiv ℝ (fderiv ℝ (barL z μt ω)) h v v) ∧
ConvexOn ℝ Set.univ (barL z μt ω) := by sorry
end ForecastAggLearn
Source
Babichenko, Garber, Learning of Optimal Forecast Aggregation in Partial Evidence Environments, arXiv:1802.07107v1, §4.2.1, p.18
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.