(32) — the one-step bound with the bias δ = g − ∇_θφ_γ separated, for α ≤ 1/L_φ
ProvedCertDRO.SGD.eq_32biased-gradientdescent-lemmap2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1
Let be differentiable with -Lipschitz gradient, , and let with . For all , writing ,
In the proof of Theorem 2, is the exact stochastic gradient and is the bias caused by solving the inner maximization only approximately; the inequality separates a mean-zero term, the bias and the variance.
Formalization Note The paper assumes "in the rest of the proof" (p. 40); this is the hypothesis together with and , which the step needs.
Preamble
import Definitions.Def_CertDRO_SGD_model
Formal statement
namespace CertDRO.SGD
/-- (32), §B.3, p. 40: for a differentiable `F` on `ℝ^d` with `L_φ`-Lipschitz gradient (`L_φ ≥ 0`) and a
stepsize `0 ≤ α ≤ 1/L_φ`, the step `θ⁺ = θ − α g` satisfies, for every vector `u` (in the proof,
`u = ∇_θ φ_γ(θ^t; z^t)`) and with `δ = g − u`,
`F(θ⁺) ≤ F(θ) − (α/2)‖∇F(θ)‖² + α(1 − L_φ α)⟨∇F(θ), ∇F(θ) − u⟩ + (α(1 + L_φ α)/2)‖δ‖²
+ L_φ α² ‖u − ∇F(θ)‖²`. -/
theorem eq_32 {d : ℕ} (F : Param d → ℝ) (Lφ : ℝ) (hF : Differentiable ℝ F)
(hL : ∀ θ θ', ‖gradient F θ - gradient F θ'‖ ≤ Lφ * ‖θ - θ'‖) (hLφ : 0 ≤ Lφ)
(θ g u : Param d) (α : ℝ) (hα : 0 ≤ α) (hαL : Lφ * α ≤ 1) :
F (θ - α • g) ≤ F θ - α / 2 * ‖gradient F θ‖ ^ 2
+ α * (1 - Lφ * α) * inner ℝ (gradient F θ) (gradient F θ - u)
+ α * (1 + Lφ * α) / 2 * ‖g - u‖ ^ 2
+ Lφ * α ^ 2 * ‖u - gradient F θ‖ ^ 2 := by sorry
end CertDRO.SGD
Source
Sinha, Namkoong, Volpi, Duchi, Certifying Some Distributional Robustness with Principled Adversarial Training, arXiv:1710.10571v5, p. 40, §B.3, (32)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.