Lemma 2 — ∇(f∘g) is Lipschitz with constant L_g² L_∇f + L_f L_∇g
ProvedNestedSA.NASA.lemma_2compositional-optimizationp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1smoothness
Let and satisfy Assumption 2: both are continuously differentiable, and , , , are Lipschitz with constants , , , . Then the gradient of is Lipschitz continuous: for all ,
This supplies the smoothness constant used in the descent step of the merit-function analysis.
Formalization Note The paper's proof starts from ; since Assumption 2 is global, the statement is made on all of .
Preamble
import Mathlib import Definitions.Def_NestedSA_NASA_Basic import Definitions.Def_NestedSA_NASA_Model
Formal statement
namespace NestedSA.NASA
/-- Lemma 2 (p. 9): under Assumption 2 the gradient of `F = f ∘ g` is Lipschitz continuous on all of `ℝⁿ` with
constant `L_∇F = L_g² L_∇f + L_f L_∇g`. -/
theorem lemma_2 {n m : ℕ} (f : EuclideanSpace ℝ (Fin m) → ℝ)
(g : EuclideanSpace ℝ (Fin n) → EuclideanSpace ℝ (Fin m)) (Lf Lg Ldf Ldg : ℝ)
(hA2 : Assumption2 f g Lf Lg Ldf Ldg) (x x' : EuclideanSpace ℝ (Fin n)) :
‖gradF f g x - gradF f g x'‖ ≤ LgradF Lf Lg Ldf Ldg * ‖x - 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. 9, Lemma 2
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.