Theorem 2.4(b) — two-phase RSG finds an (ε, Λ)-solution
ProvedGhadimiLan.TwoPhase.theorem_2_4_bcomplexitynonconvex-optimizationp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1probabilitystochastic-approximation
Consider the two-phase RSG method of Theorem 2.4. Let and , and set
The selected candidate is an -solution:
The algorithm uses at most stochastic first-order oracle calls: runs of at most calls, followed by estimates for each candidate.
Formalization Note The call count follows from the modeled loops and is stated in prose rather than through a separate call-counting semantics. The logarithm in (2.24) is read in base two; the printed proof's does not follow from a natural logarithm. The model has , since otherwise (2.13) and (2.26) yield a zero step or zero sample size in Lean.
Preamble
import Mathlib import Definitions.Def_GhadimiLan_TwoPhase_Model open MeasureTheory ProbabilityTheory
Formal statement
namespace GhadimiLan.TwoPhase
/-- Theorem 2.4(b), Eqs. (2.24)–(2.27), p. 12. The logarithm in (2.24)
is read in base two, as required by the paper's final 2⁻ˢ bound. -/
theorem theorem_2_4_b {n S N T : ℕ} {Ω Ξ : Type*}
[MeasurableSpace Ω] [MeasurableSpace Ξ]
(μ : Measure Ω) [IsProbabilityMeasure μ]
(P : Problem n Ξ) (A : System (S := S) (N := N) (T := T) P μ)
(ε Λ : ℝ) (hε : 0 < ε) (hΛ0 : 0 < Λ) (hΛ1 : Λ < 1)
(hS : S = Nat.ceil (Real.logb 2 (2 / Λ)))
(hN : N = Nat.ceil (max (32 * P.L ^ 2 * Df P ^ 2 / ε)
((32 * P.L * (P.Dt + Df P ^ 2 / P.Dt) * P.σ / ε) ^ 2)))
(hT : T = Nat.ceil (24 * ((S : ℝ) + 1) * P.σ ^ 2 / (Λ * ε))) :
ENNReal.ofReal (1 - Λ) ≤
μ {ω | ‖P.g (chosen A ω)‖ ^ 2 ≤ ε} := by sorry
end GhadimiLan.TwoPhase
Source
Ghadimi & Lan, arXiv:1309.5549v1, Theorem 2.4(b), Eqs. (2.24)–(2.27), p. 12
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.