(2.15), proof of Proposition 2.2, p. 235 — ⟨γ_tF(w_t), w_t − u⟩ ≤ H_u(z_{t−1}) − H_u(z_t) + ε_t
ProvedProxMethodVI.Rate.eq2_15_one_stepLet be a nonempty convex compact subset of a finite-dimensional normed space , let be continuously differentiable on and -strongly convex in the sense of (2.2), and let be as in (2.3). Consider a run , of the relaxed conceptual prox-method with stepsizes and tolerances : , , , and condition (2.11) holds at every step . Then for every step and every ,
This one-step estimate telescopes over to give (2.16) and then the ergodic bound (2.13).
Formalization Note. No property of is used, so is an arbitrary map (the section's standing assumption (2.1) is dropped here, which is a generalization). In Lean the step of the paper is the index t + 1, t : ℕ. The termination test (2.8) is not part of the run.
import Mathlib import Definitions.Def_ProxMethodVI_Rate_Setting
namespace ProxMethodVI.Rate
theorem eq2_15_one_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[ℝ] ℝ) (γ ε : ℕ → ℝ) (z w : ℕ → E)
(hrun : IsRelaxedRun Z F ω ω' γ ε z w) (t : ℕ) (u : E) (hu : u ∈ Z) :
γ (t + 1) * F (w (t + 1)) (w (t + 1) - u)
≤ Hfun Z ω ω' u (z t) - Hfun Z ω ω' u (z (t + 1)) + ε (t + 1) := by sorry
end ProxMethodVI.Rate
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.