Proposition 2.2(ii) (2.13), p. 234 — ε(z^N) ≤ (Θ(z₀) + Σε_t)/Σγ_t for the relaxed CPM
ProvedProxMethodVI.Rate.prop2_2_ii_ergodic_boundLet be a nonempty convex compact subset of a finite-dimensional normed space , let be monotone on , and let be continuously differentiable on and -strongly convex in the sense of (2.2). Consider a run of the relaxed conceptual prox-method: , and for every , , , and
Let and . Then
This is the convergence guarantee of the conceptual prox-method. Its quantity is the standard accuracy measure of an approximate weak solution of the variational inequality, and the basic implementation of §3 is analysed by verifying (2.11) with .
Formalization Note. The bound on is stated as for every , which is equivalent to the maximum being at most the bound. Only monotonicity of is assumed; the Lipschitz half of (2.1) is not used by the proof. The hypothesis "the relaxed algorithm does not terminate in the course of steps" is replaced by runs that never terminate, since (2.8) is not modelled. makes .
import Mathlib import Definitions.Def_ProxMethodVI_Rate_Setting
namespace ProxMethodVI.Rate
theorem prop2_2_ii_ergodic_bound {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[ℝ] ℝ) (hmono : IsMonotoneOnWRT Z F)
(γ ε : ℕ → ℝ) (z w : ℕ → E) (hrun : IsRelaxedRun Z F ω ω' γ ε z w)
(N : ℕ) (hN : 1 ≤ N) (u : E) (hu : u ∈ Z) :
F u (ergodicAvg γ w N - u)
≤ (theta Z ω ω' (z 0) + ∑ t ∈ Finset.Icc 1 N, ε t) / ∑ t ∈ Finset.Icc 1 N, γ t := by sorry
end ProxMethodVI.Rate
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.