(31) — the descent inequality for an L_φ-smooth objective along θ − αg
ProvedCertDRO.SGD.eq_31descent-lemmap2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1smoothness
Let be differentiable with -Lipschitz gradient, . Then for every and every ,
In the proof of Theorem 2 this is applied with , and , so that the left side is ; it is the progress guarantee of one step of Algorithm 1.
Formalization Note The statement is deterministic and holds for any stepsize; the paper's displayed chain of equalities after the first inequality is algebra.
Preamble
import Definitions.Def_CertDRO_SGD_model
Formal statement
namespace CertDRO.SGD
/-- (31), §B.3, p. 40: for a differentiable `F` on `ℝ^d` with `L_φ`-Lipschitz gradient, the step
`θ⁺ = θ − α g` satisfies
`F(θ⁺) ≤ F(θ) − α(1 − ½ L_φ α)‖∇F(θ)‖² + α(1 − L_φ α)⟨∇F(θ), ∇F(θ) − g⟩ + (L_φ α²/2)‖g − ∇F(θ)‖²`. -/
theorem eq_31 {d : ℕ} (F : Param d → ℝ) (Lφ : ℝ) (hF : Differentiable ℝ F)
(hL : ∀ θ θ', ‖gradient F θ - gradient F θ'‖ ≤ Lφ * ‖θ - θ'‖)
(θ g : Param d) (α : ℝ) :
F (θ - α • g) ≤ F θ - α * (1 - 1 / 2 * Lφ * α) * ‖gradient F θ‖ ^ 2
+ α * (1 - Lφ * α) * inner ℝ (gradient F θ) (gradient F θ - g)
+ Lφ * α ^ 2 / 2 * ‖g - 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, (31)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.