Lemma 1 — the unit-step projected displacement is at most max(1,β) times the β-step one
ProvedNestedSA.NASA.lemma_1convex-analysisp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1projection
Let be closed and convex, the Euclidean projection onto , and the solution of subproblem (2.5). For every , every and every ,
The lemma compares the step of the subproblem at an arbitrary regularization with the unit-regularization step that enters the optimality measure ; it is what turns a bound on the algorithm's steps into a bound on .
Preamble
import Mathlib import Definitions.Def_SpectralProjGrad_Shared_IsProjOnto import Definitions.Def_NestedSA_NASA_Basic
Formal statement
namespace NestedSA.NASA
/-- Lemma 1, (2.11) (p. 7): for a closed convex `X ⊆ ℝⁿ` with Euclidean projection `P`, every `x ∈ X`, every
`z ∈ ℝⁿ` and every `β > 0`, `‖ȳ(x, z, 1) − x‖ ≤ max(1, β) ‖ȳ(x, z, β) − x‖`, where `ȳ(x, z, β) = Π_X(x − β⁻¹z)`. -/
theorem lemma_1 {n : ℕ} (X : Set (EuclideanSpace ℝ (Fin n))) (hX_cl : IsClosed X) (hX_cvx : Convex ℝ X)
(P : EuclideanSpace ℝ (Fin n) → EuclideanSpace ℝ (Fin n))
(hP : SpectralProjGrad.Shared.IsProjOnto X P)
(x : EuclideanSpace ℝ (Fin n)) (hx : x ∈ X) (z : EuclideanSpace ℝ (Fin n)) (β : ℝ) (hβ : 0 < β) :
‖ybar P x z 1 - x‖ ≤ max 1 β * ‖ybar P x z β - x‖ := by sorry
end NestedSA.NASA
Source
Ghadimi, Ruszczyński, Wang, A Single Time-Scale Stochastic Approximation Method for Nested Stochastic Optimization, arXiv:1812.01094v2, p. 7, Lemma 1, (2.11)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.