Proof of Theorem 3.2, pp. 347–348 — ψ*_{k+1} ≥ ψ*_k + a_{k+1} f(x^{k+1})
ProvedRelSmoothFOM.DualAvg.psi_star_stepdual-averagingfirst-order-methodsp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1relative-smoothness
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 relative to on , and let be a run of the dual averaging scheme (Algorithm 2) with models and . Then for every ,
Summed over , this recursion gives the lower half of (36), .
Formalization Note Relative strong convexity is not needed and is not assumed.
Preamble
import Mathlib import Definitions.Def_RelSmoothFOM_DualAvg_Setting
Formal statement
namespace RelSmoothFOM.DualAvg
/-- Proof of Theorem 3.2, pp. 347–348: along a run of Algorithm 2, for every `k`,
`ψ*_{k+1} ≥ ψ*_k + a_{k+1} f(x^{k+1})`, where `ψ*_k = ψ_k(x^k)`. -/
theorem psi_star_step
{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)
(x : ℕ → E) (hrun : IsDualAveragingRun Q f h L μ x) :
∀ k : ℕ, daModel f h L μ x (k + 1) (x (k + 1)) ≥
daModel f h L μ x k (x k) + daWeight L μ k * f (x (k + 1)) := by sorry
end RelSmoothFOM.DualAvg
Source
Lu, Freund & Nesterov, Relatively smooth convex optimization by first-order methods, and applications, SIAM J. Optim. 28 (2018), pp. 347–348, proof of Theorem 3.2, display preceding (36)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.