Proof of Theorem 3.2, p. 239 — with γ = α/(√2L), the second inner iterate w_{t,2} always passes (3.4)
ProvedProxMethodVI.Rate.theorem3_2_second_inner_stepLet be a nonempty convex compact subset of a finite-dimensional normed space , let satisfy (2.1) with a constant (Lipschitz from to and monotone on ), and let be continuously differentiable on and -strongly convex in the sense of (2.2). Let as in (3.2). Let , let and . Then
that is, the test (3.4) is met at the second inner iteration .
This is the display of the proof of Theorem 3.2. It is what makes every step of the basic implementation cost at most two evaluations of and two prox problems.
Formalization Note. The statement is unconditional: it does not assume that (3.4) fails at , because the proof's display never uses that failure. It is therefore slightly stronger than the sentence "if (3.4) is not met with , it is met with ". is needed for (3.2) to make sense. Prox points are minimizers over .
import Mathlib import Definitions.Def_ProxMethodVI_Rate_Setting
namespace ProxMethodVI.Rate
theorem theorem3_2_second_inner_step {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 ω ω' α)
(F : E → E →L[ℝ] ℝ) (L : ℝ) (hL : 0 < L) (hLip : IsLipschitzOnWRT Z F L)
(hmono : IsMonotoneOnWRT Z F)
(z : E) (hz : z ∈ Z) (w₁ : E) (hw₁ : IsProxPt Z ω ω' z ((α / (Real.sqrt 2 * L)) • F z) w₁)
(zp : E) (hzp : IsProxPt Z ω ω' z ((α / (Real.sqrt 2 * L)) • F w₁) zp) :
test34 (α / (Real.sqrt 2 * L)) F ω ω' z w₁ zp := by sorry
end ProxMethodVI.Rate
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.