Theorem 2 — nonconvex SGD on the robust surrogate: (1/T)Σ E‖∇F(θᵗ)‖² − 4L_θz²ε/(γ − L_zz) ≤ 4σ√(L_φΔ_F/T)
ProvedCertDRO.SGD.theorem_2Let be nonempty, convex and closed; let the cost satisfy Assumption A and the loss satisfy Assumption B, both with the Euclidean norm, and let . Let and
where is a probability distribution with and each is -integrable. Suppose:
- is bounded below and satisfies ;
- and for every ;
- and the inner maximization is solved by a jointly measurable -approximate oracle ;
- and .
Run Algorithm 1 from for steps with i.i.d. samples and constant stepsize , i.e. . Then
This is the paper's computational guarantee: stochastic gradient descent with an approximate adversary reaches an approximate stationary point of the Wasserstein penalty objective at the rate of smooth nonconvex optimization, up to an additive bias proportional to the accuracy of the inner maximization.
Formalization Note The inequality is stated in with the -term moved to the right-hand side, which is equivalent because all terms are finite and nonnegative; the expectations are lower Lebesgue integrals over , so a non-integrable integrand is never read as . Hypotheses implicit in the paper and made explicit: (the paper writes but divides by ), convex and closed, and (needed for a positive stepsize), , , bounded below, integrability of , and measurability of the oracle. The cost is not assumed differentiable.
Retired 2026-10-27: a Lean-vs-paper fidelity audit found this statement weaker than, or narrower than, the cited result. A corrected statement will be resubmitted.
import Definitions.Def_CertDRO_SGD_model
namespace CertDRO.SGD
open MeasureTheory
/-- Theorem 2 (Convergence of Nonconvex SGD), p. 6. Let Assumptions A and B hold with the ℓ²-norm,
`Θ = ℝ^d`, `γ > Lzz`, and let `F(θ) = E_{P₀}[φ_γ(θ; Z)]`. Let `Δ_F ≥ F(θ⁰) − inf_θ F(θ)`, assume
`E‖∇F(θ) − ∇_θ φ_γ(θ, Z)‖² ≤ σ²` for all `θ`, and run Algorithm 1 with an `ε`-approximate maximization
oracle and constant stepsize `α = √(Δ_F / (L_φ T σ²))`, `L_φ = Lθθ + Lθz Lzθ / (γ − Lzz)`. If
`T ≥ L_φ Δ_F / σ²`, then
`(1/T) Σ_{t=0}^{T−1} E‖∇F(θ^t)‖² − (4 Lθz² / (γ − Lzz)) ε ≤ 4σ √(L_φ Δ_F / T)`
(stated with the `ε`-term moved to the right-hand side, in `ℝ≥0∞`). -/
theorem theorem_2 {d m : ℕ} (Z : Set (Data m)) (c : Data m → Data m → ℝ)
(ℓ : Param d → Data m → ℝ) (gθ : Param d → Data m → Param d) (gz : Param d → Data m → Data m)
(Lθθ Lzz Lθz Lzθ γ : ℝ)
(hS : Standing Z c ℓ gθ gz Lθθ Lzz Lθz Lzθ γ)
(P₀ : Measure (Data m)) [IsProbabilityMeasure P₀] (hP₀ : P₀ Zᶜ = 0)
(hint : ∀ θ, Integrable (fun z => robustSurrogate Z ℓ c γ θ z) P₀)
(ε : ℝ) (hε : 0 ≤ ε) (zhat : Param d → Data m → Data m)
(hzhat : IsOracle Z ℓ c γ ε zhat) (hzhat_meas : Measurable (Function.uncurry zhat))
(σ : ℝ) (hσ : 0 < σ)
(hvar : ∀ θ, ∫⁻ z, ENNReal.ofReal (‖gradient (robustObjective Z ℓ c γ P₀) θ -
gradient (fun θ' => robustSurrogate Z ℓ c γ θ' z) θ‖ ^ 2) ∂P₀ ≤ ENNReal.ofReal (σ ^ 2))
(θ₀ : Param d) (ΔF : ℝ) (hΔF_pos : 0 < ΔF)
(hbdd : BddBelow (Set.range (robustObjective Z ℓ c γ P₀)))
(hΔF : robustObjective Z ℓ c γ P₀ θ₀ - ⨅ θ, robustObjective Z ℓ c γ P₀ θ ≤ ΔF)
(T : ℕ) (hT : 0 < T) (hTL : Lphi Lθθ Lzz Lθz Lzθ γ * ΔF / σ ^ 2 ≤ T) :
(T : ENNReal)⁻¹ * ∑ t ∈ Finset.range T,
∫⁻ ω, ENNReal.ofReal (‖gradient (robustObjective Z ℓ c γ P₀)
(run gθ zhat (Real.sqrt (ΔF / (Lphi Lθθ Lzz Lθz Lzθ γ * T * σ ^ 2))) θ₀ ω t)‖ ^ 2)
∂(Measure.pi fun _ : Fin T => P₀) ≤
ENNReal.ofReal (4 * Lθz ^ 2 / (γ - Lzz) * ε
+ 4 * σ * Real.sqrt (Lphi Lθθ Lzz Lθz Lzθ γ * ΔF / T)) := by sorry
end CertDRO.SGD
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.