Lemma 29 —
ProvedNonconvexSaddle.PSGD.lemma_29nonconvex-optimizationp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1saddle-points
Let and define
Then (1) for every , and (2) for every with .
is, up to the factor , the standard deviation of the perturbation term along ; the lemma says it grows like .
Formalization Note The page allows ; at the paper's is , while Lean's would make part (1) false for , so is required. Lemmas 30 and 31 apply the lemma with .
Preamble
import Mathlib import Definitions.Def_NonconvexSaddle_PSGD_Setting open MeasureTheory ProbabilityTheory open scoped RealInnerProductSpace
Formal statement
namespace NonconvexSaddle.PSGD
/-- Lemma 29 (arXiv:1902.04811v2, App. B.3, p. 26), with `a = ηγ ∈ (0, 1]`:
(1) `α(t) ≤ β(t)` for every `t ∈ ℕ`, and (2) `α(t) ≥ β(t)/√3` for `t ≥ ln 2/(ηγ)`. -/
theorem lemma_29 (a : ℝ) (ha : 0 < a) (ha1 : a ≤ 1) :
(∀ t : ℕ, alphaL a t ≤ betaL a t) ∧
∀ t : ℕ, Real.log 2 / a ≤ (t : ℝ) → betaL a t / Real.sqrt 3 ≤ alphaL a t := by sorry
end NonconvexSaddle.PSGD
Source
Jin, Netrapalli, Ge, Kakade, Jordan, On Nonconvex Optimization for Machine Learning: Gradients, Stochasticity, and Saddle Points, arXiv:1902.04811v2, p. 26, Lemma 29
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.