Lemma 3.1 (3.7.a), p. 238 — ‖w − z₊‖ ≤ α⁻¹γ‖ξ − η‖_*
ProvedProxMethodVI.Rate.lemma3_1_a_prox_lipschitzbregmanmirror-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 a nonempty set be convex and closed, let , let be dual vectors and let . Consider the points
Then
This is part (a) of Lemma 3.1, the key lemma of the two-step analysis. It is used in (3.7.d) to bound the inner-product term.
Formalization Note. and are any minimizers of the two problems (3.6). The lemma's "for all " binds nothing in part (a) and is omitted. is the operator norm.
Preamble
import Mathlib import Definitions.Def_ProxMethodVI_Rate_Setting
Formal statement
namespace ProxMethodVI.Rate
theorem lemma3_1_a_prox_lipschitz {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 ω ω' α)
(U : Set E) (hUZ : U ⊆ Z) (hUne : U.Nonempty) (hUc : Convex ℝ U) (hUcl : IsClosed U)
(z : E) (hz : z ∈ Z) (ξ η : E →L[ℝ] ℝ) (γ : ℝ) (hγ : 0 < γ)
(w : E) (hw : IsProxPt U ω ω' z (γ • ξ) w)
(zp : E) (hzp : IsProxPt U ω ω' z (γ • η) zp) :
‖w - zp‖ ≤ α⁻¹ * γ * ‖ξ - η‖ := by sorry
end ProxMethodVI.Rate
Source
Nemirovski, Prox-Method with Rate of Convergence O(1/t), SIAM J. Optim. 15(1) (2004), pp. 237–238, Lemma 3.1, (3.6), (3.7.a)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.