Theorem 3.2 a), (3.16), p. 17 — the RSGF method bounds (1/L)E‖∇f(x_R)‖² for nonconvex f
ProvedGhadimiLan.RSGF.theorem_3_2_aConsider the stochastic program (3.1), where . Assume:
- almost surely, with ;
- Assumption A1 for , with variance bound ;
- Assumption A3;
- is bounded below.
Run the randomized stochastic gradient free (RSGF) method (3.12)–(3.13) from . It uses smoothing parameter , iteration limit , and stepsizes with . At each step it draws a fresh sample and a fresh standard Gaussian direction , all mutually independent. Its output is , where the random index is independent of the samples and has probability mass function
Then is integrable and
where (2.5), and the expectation is over , and .
This is the main convergence guarantee of the paper for nonconvex stochastic optimization with zeroth-order (function value) information only. With constant stepsizes it gives the complexity of Corollary 3.3.
Formalization Note is EuclideanSpace ℝ (Fin n), and the constants use the same . The smoothing parameter is μs, and μ is the probability measure. The value is the infimum of (IsGLB), and is written out as . The following are disclosed additions that make the paper's implicit setting explicit:
- the samples are measurable and mutually independent, and is independent of them;
- is jointly measurable and , are integrable;
- the stepsizes are positive.
The integrability of is part of the conclusion.
import Mathlib import Definitions.Def_GhadimiLan_RSGF_Model import Definitions.Def_GhadimiLan_RSGF_Method open MeasureTheory ProbabilityTheory
namespace GhadimiLan.RSGF
/-- Theorem 3.2 a), Eq. (3.16) (Ghadimi & Lan, arXiv:1309.5549v1, pp. 16–17). Under the standing
assumptions of §3 (A1 for `G = ∇_x F`, A3, `F(·, ξ) ∈ C^{1,1}_L` a.s.), with `f = objective P F`
bounded below with infimum `fstar`, stepsizes `0 < γ_k < 1/[2(n+4)L]`, smoothing parameter
`μs > 0` (the paper's `µ`; `μ` is the probability measure) and the random output index `R` with
the pmf (3.15), drawn independently of the samples, the RSGF output satisfies
`(1/L) E‖∇f(x_R)‖² ≤ [D_f² + 2µ²(n+4)(1 + L(n+4)² Σ(γ_k/4 + Lγ_k²)) + 2(n+4)σ² Σγ_k²] / Σ[γ_k − 2L(n+4)γ_k²]`
with `D_f² = 2(f(x_1) − f*)/L` (2.5). The integrability of `‖∇f(x_R)‖²` is part of the claim. -/
theorem theorem_3_2_a {n : ℕ} {Ω Ξ : Type*} [MeasurableSpace Ω] [MeasurableSpace Ξ]
(μ : Measure Ω) [IsProbabilityMeasure μ] (P : Measure Ξ) [IsProbabilityMeasure P]
(F : EuclideanSpace ℝ (Fin n) → Ξ → ℝ) (L σ μs : ℝ) (hL : 0 < L) (hσ : 0 ≤ σ) (hμs : 0 < μs)
(hF : SZOAssumptions P F L σ)
(fstar : ℝ) (hfstar : IsGLB (Set.range (objective P F)) fstar)
(N : ℕ) (hN : 1 ≤ N) (γ : ℕ → ℝ)
(hγ : ∀ k ∈ Finset.Icc 1 N, 0 < γ k ∧ γ k < 1 / (2 * ((n : ℝ) + 4) * L))
(ξ : ℕ → Ω → Ξ) (u : ℕ → Ω → EuclideanSpace ℝ (Fin n)) (hs : IsSZOSampling μ P ξ u)
(x1 : EuclideanSpace ℝ (Fin n)) (x : ℕ → Ω → EuclideanSpace ℝ (Fin n))
(hx : IsRSGFRun F μs γ x1 ξ u x)
(R : Ω → ℕ) (hR : IsOutputIndex μ ξ u N (rsgfPMF L n γ N) R) :
Integrable (fun ω => ‖gradient (objective P F) (x (R ω) ω)‖ ^ 2) μ ∧
1 / L * ∫ ω, ‖gradient (objective P F) (x (R ω) ω)‖ ^ 2 ∂μ ≤
1 / (∑ k ∈ Finset.Icc 1 N, (γ k - 2 * L * ((n : ℝ) + 4) * γ k ^ 2)) *
(2 * (objective P F x1 - fstar) / L
+ 2 * μs ^ 2 * ((n : ℝ) + 4) *
(1 + L * ((n : ℝ) + 4) ^ 2 * ∑ k ∈ Finset.Icc 1 N, (γ k / 4 + L * γ k ^ 2))
+ 2 * ((n : ℝ) + 4) * σ ^ 2 * ∑ k ∈ Finset.Icc 1 N, γ k ^ 2) := by sorry
end GhadimiLan.RSGF
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.