Lemma 3.1 (3.7.d), p. 238 — ε ≤ α⁻¹γ²‖ξ − η‖²_* − (α/2)[‖w − z‖² + ‖w − z₊‖²]
ProvedProxMethodVI.Rate.lemma3_1_dbregmanmirror-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, let , and let be the points (3.6) (minimizers over ). Then
This is part (d) of Lemma 3.1. Together with (3.7.c) it bounds the left-hand side of the test (3.4) at the second inner iteration, and it carries the constant that makes the stepsize work in Theorem 3.2.
Formalization Note. is written out in full. is the operator norm. Strong convexity is assumed only in the monotonicity form (2.2); its function-value form is not a hypothesis.
Preamble
import Mathlib import Definitions.Def_ProxMethodVI_Rate_Setting
Formal statement
namespace ProxMethodVI.Rate
theorem lemma3_1_d {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) + (ω z + ω' z (w - z) + ω' w (zp - w) - ω zp)
≤ α⁻¹ * γ ^ 2 * ‖ξ - η‖ ^ 2 - α / 2 * (‖w - z‖ ^ 2 + ‖w - zp‖ ^ 2) := 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.d)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.