(35), p. 347 — (1 + μA_k)D_h(x, x^k) = D_{ψ_k}(x, x^k) ≤ ψ_k(x) − ψ*_k
ProvedRelSmoothFOM.DualAvg.eq_35Let be a convex subset of a finite-dimensional real inner-product space , let be convex on and differentiable at every point of , and let . Let be a run of the dual averaging scheme (Algorithm 2) with models and . Then for every and every ,
The equality holds because is an affine function plus , so the two have the same Bregman distance; the inequality is the first-order optimality condition of for over . It is the step that turns the minimisation in Algorithm 2 into the growth estimate for .
Formalization Note is the Bregman distance (7) of the function , with its Fréchet derivative at ; is differentiable there because is. No relative smoothness or relative strong convexity is assumed: neither is used.
import Mathlib import Definitions.Def_RelSmoothFOM_DualAvg_Setting
namespace RelSmoothFOM.DualAvg
/-- (35), proof of Theorem 3.2, p. 347: along a run of Algorithm 2, for every `k` and `u ∈ Q`,
`(1 + μA_k) D_h(u, x^k) = D_{ψ_k}(u, x^k) ≤ ψ_k(u) − ψ*_k`, where `ψ_k = daModel f h L μ x k`
and `ψ*_k = ψ_k(x^k)`. -/
theorem eq_35
{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)
(x : ℕ → E) (hrun : IsDualAveragingRun Q f h L μ x) :
∀ k : ℕ, ∀ u ∈ Q,
(1 + μ * daSum L μ k) * bregman h u (x k) = bregman (daModel f h L μ x k) u (x k) ∧
bregman (daModel f h L μ x k) u (x k) ≤
daModel f h L μ x k u - daModel f h L μ x k (x k) := by sorry
end RelSmoothFOM.DualAvg
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.