(3.29) — V(x,z) ≤ max(1,β²)‖d‖² + ‖z − ∇F(x)‖²
ProvedNestedSA.NASA.eq_3_29p2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1stationarity-measure
Let be closed and convex, , , , , and . Then the optimality measure (2.10) satisfies
Applied at the iterates, this reduces a bound on to bounds on the step and on the gradient-tracking error .
Preamble
import Mathlib import Definitions.Def_SpectralProjGrad_Shared_IsProjOnto import Definitions.Def_NestedSA_NASA_Basic
Formal statement
namespace NestedSA.NASA
/-- (3.29) (p. 13): for a closed convex `X` with Euclidean projection `P`, every `x ∈ X`, every `z` and every
`β > 0`, `V(x, z) ≤ max(1, β²) ‖d‖² + ‖z − ∇F(x)‖²` with `d = ȳ(x, z, β) − x` and `F = f ∘ g`. -/
theorem eq_3_29 {n m : ℕ} (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)
(f : EuclideanSpace ℝ (Fin m) → ℝ) (g : EuclideanSpace ℝ (Fin n) → EuclideanSpace ℝ (Fin m))
(x : EuclideanSpace ℝ (Fin n)) (hx : x ∈ X) (z : EuclideanSpace ℝ (Fin n)) (β : ℝ) (hβ : 0 < β) :
V P f g x z ≤ max 1 (β ^ 2) * ‖ybar P x z β - x‖ ^ 2 + ‖z - gradF f g x‖ ^ 2 := by sorry
end NestedSA.NASA
Source
Ghadimi, Ruszczyński, Wang, A Single Time-Scale Stochastic Approximation Method for Nested Stochastic Optimization, arXiv:1812.01094v2, §3, (3.29), p. 13
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.