(36), p. 348 — Σ_{i=0}^{k−1} a_{i+1} f(x^{i+1}) ≤ ψ*_k ≤ h(x) + A_k f(x)
ProvedRelSmoothFOM.DualAvg.eq_36dual-averagingp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1relative-smoothnessrelative-strong-convexity
Let be a convex subset of a finite-dimensional real inner-product space , let be convex on and differentiable at every point of , and let . Suppose is -smooth and -strongly convex relative to on , and let be a run of the dual averaging scheme (Algorithm 2) with models and . Then for every and every ,
Since the weights are positive, the left-hand side is at least ; rearranging gives Theorem 3.2.
Formalization Note In the sum, multiplies , as on the page.
Preamble
import Mathlib import Definitions.Def_RelSmoothFOM_DualAvg_Setting
Formal statement
namespace RelSmoothFOM.DualAvg
/-- (36), proof of Theorem 3.2, p. 348: along a run of Algorithm 2, for every `k` and `u ∈ Q`,
`Σ_{i=0}^{k−1} a_{i+1} f(x^{i+1}) ≤ ψ*_k ≤ h(u) + A_k f(u)`. -/
theorem eq_36
{E : Type*} [NormedAddCommGroup E] [InnerProductSpace ℝ E] [FiniteDimensional ℝ E]
(Q : Set E) (hQ : Convex ℝ Q)
(f h : E → ℝ) (hfd : ∀ x ∈ Q, DifferentiableAt ℝ f x) (hfc : ConvexOn ℝ Q f)
(hhd : ∀ x ∈ Q, DifferentiableAt ℝ h x) (hhc : ConvexOn ℝ Q h)
(L μ : ℝ) (hμ : 0 ≤ μ) (hμL : μ < L)
(hsm : IsRelSmooth Q f h L) (hsc : IsRelStronglyConvex Q f h μ)
(x : ℕ → E) (hrun : IsDualAveragingRun Q f h L μ x) :
∀ k : ℕ, ∀ u ∈ Q,
∑ i ∈ Finset.range k, daWeight L μ i * f (x (i + 1)) ≤ daModel f h L μ x k (x k) ∧
daModel f h L μ x k (x k) ≤ h u + daSum L μ k * f u := by sorry
end RelSmoothFOM.DualAvg
Source
Lu, Freund & Nesterov, Relatively smooth convex optimization by first-order methods, and applications, SIAM J. Optim. 28 (2018), p. 348, proof of Theorem 3.2, (36)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.