Proof of Lemma 4.2, pp. 9–10 — the step rule λ(y, τ) is at least α/L
ProvedProjReflGrad.Adaptive.stepCap_geadaptive-step-sizep2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1variational-inequality
Let be -Lipschitz with and let . Let be the step rule (4.1) for the previous data , , and cap . If and , then for every and every
This is the first claim of the proof of Lemma 4.2, used there to show that satisfies (4.3).
Formalization Note The two hypotheses and are made explicit. The first is the induction hypothesis of the paper's argument ("Then and hence by induction"); the second is the reading of "some large " (Algorithm 4.2, step 1) that this argument needs. Neither is assumed in the goal theorem.
Preamble
import Mathlib import Definitions.Def_ProjReflGrad_Adaptive_Setting
Formal statement
namespace ProjReflGrad.Adaptive
/-- Proof of Lemma 4.2 (Malitsky 2015, pp. 9–10): for an `L`-Lipschitz `F`, `λ(y, τ) ≥ α/L` for all
`y`, `y_{n-1}` and `τ ∈ (0, 1]`, provided `λ_{n-1} ≥ α/L` (the induction hypothesis) and
`λ̄ ≥ α/L` (the reading of "some large `λ̄`" the proof uses). -/
theorem stepCap_ge {H : Type*} [NormedAddCommGroup H] [InnerProductSpace ℝ H] (F : H → H) (L : ℝ) (hL : 0 < L)
(hC3 : ProjReflGrad.Weak.IsLipschitzMap F L) (α lamBar : ℝ) (hα : 0 < α) (yp y : H) (taup lamp tau : ℝ)
(htaup : 0 ≤ taup) (htau : tau ∈ Set.Ioc 0 1) (hlamp : α / L ≤ lamp)
(hbar : α / L ≤ lamBar) :
α / L ≤ stepCap F α lamBar yp taup lamp y tau := by sorry
end ProjReflGrad.Adaptive
Source
Malitsky, Projected Reflected Gradient Methods for Monotone Variational Inequalities, arXiv:1502.04968v1, pp. 9–10, proof of Lemma 4.2
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.