(34), p. 347 — along the dual averaging scheme, ψ*_k ≤ h(x) + A_k f(x) for every x ∈ Q
ProvedRelSmoothFOM.DualAvg.eq_34dual-averagingfirst-order-methodsp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1relative-strong-convexity
Let be a convex subset of a finite-dimensional real inner-product space , and let be convex on and differentiable at every point of . Let and suppose is -strongly convex relative to on . Let be a run of the dual averaging scheme (Algorithm 2), with models and . Then for every and every ,
This is the upper half of (36): the model's optimal value never exceeds plus times the objective at any feasible point.
Formalization Note For , because minimises over ; for , and is the -center. The relative smoothness condition is not needed and is not assumed.
Preamble
import Mathlib import Definitions.Def_RelSmoothFOM_DualAvg_Setting
Formal statement
namespace RelSmoothFOM.DualAvg
/-- (34), proof of Theorem 3.2, p. 347: along a run of Algorithm 2, for every `k` and every
`u ∈ Q`, `ψ*_k = ψ_k(x^k) ≤ h(u) + A_k f(u)`. -/
theorem eq_34
{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)
(hsc : IsRelStronglyConvex Q f h μ)
(x : ℕ → E) (hrun : IsDualAveragingRun Q f h L μ x) :
∀ k : ℕ, ∀ u ∈ Q, 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. 347, proof of Theorem 3.2, (34)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.