Lemma 2.1 (2.5), p. 232 — H_u(P_z(ξ)) − H_u(z) ≤ ⟨ξ, u − P_z(ξ)⟩ + [ω(z) + ⟨ω′(z), P_z(ξ) − z⟩ − ω(P_z(ξ))], and the bracket is ≤ 0
ProvedProxMethodVI.Rate.lemma2_1_prox_ineqbregmanmirror-proxp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1prox-method
Let be a nonempty convex compact subset of a finite-dimensional normed space , and let be continuously differentiable on and -strongly convex in the sense of (2.2). Let be the Legendre transform of , let , and let be the prox-mapping. Let , let be a dual vector, and let . Then for every ,
and the bracket satisfies
This is the basic one-step inequality of the prox-method. plays the role of a potential, and summing (2.5) along a run gives the ergodic error bound of Proposition 2.2.
Formalization Note. "" is the relation that minimizes over . Dual vectors are continuous linear functionals and is ; this is equivalent to the paper's inner-product setting.
Preamble
import Mathlib import Definitions.Def_ProxMethodVI_Rate_Setting
Formal statement
namespace ProxMethodVI.Rate
theorem lemma2_1_prox_ineq {E : Type*} [NormedAddCommGroup E] [NormedSpace ℝ E] [FiniteDimensional ℝ E]
(Z : Set E) (hZc : Convex ℝ Z) (hZk : IsCompact Z) (hZne : Z.Nonempty)
(ω : E → ℝ) (ω' : E → E →L[ℝ] ℝ) (α : ℝ) (hω : IsStrongDGF Z ω ω' α)
(z : E) (hz : z ∈ Z) (ξ : E →L[ℝ] ℝ) (v : E) (hv : IsProxPt Z ω ω' z ξ v)
(u : E) (hu : u ∈ Z) :
Hfun Z ω ω' u v - Hfun Z ω ω' u z ≤ ξ (u - v) + (ω z + ω' z (v - z) - ω v) ∧
ω z + ω' z (v - z) - ω v ≤ 0 := by sorry
end ProxMethodVI.Rate
Source
Nemirovski, Prox-Method with Rate of Convergence O(1/t), SIAM J. Optim. 15(1) (2004), p. 232, Lemma 2.1, (2.5)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.