Eq. (42) — the pathwise descent inequality
ProvedPrefixVR.eq_42finite-sum-optimizationnonconvex-optimizationp2o-gran-per-chapterp2o-plan-paperp2o-strengthenedp2o-v1variance-reduction
Let be -smooth: differentiable, with for all . For every and every , with and ,
Applied to , of Algorithm 1 (, ), this is the per-step inequality behind Theorems 1 and 2.
Formalization Note -smoothness is the published IsBetaSmooth f G Lf with gradient map (which includes ).
Differences from the source:
- generalization: x = x_t, v = v_t of a run of Algorithm 1, η > 0, L_f > 0 → every x, v ∈ ℝᵈ, every real η, every L_f ≥ 0; reason: the inequality is deterministic; the source's case is an instance
- encoding: f is L_f-smooth → IsBetaSmooth f G Lf; reason: published definition: gradient G everywhere, Lf-Lipschitz
Preamble
import Mathlib import Definitions.Def_ConvexOptAlg_SmoothGD_Defs
Formal statement
namespace PrefixVR
/-- **The pathwise descent inequality (42).** Jiang, Wang, Yang, Li, Zhang (manuscript, sha256
ed33106a…), App. C, Eq. (42), p.15: by `L_f`-smoothness and `x_{t+1} − x_t = −ηv_t`, with
`e_t = v_t − ∇f(x_t)`,
`f(x_{t+1}) ≤ f(x_t) − (η/2)‖∇f(x_t)‖² − (η/2)(1 − L_f η)‖v_t‖² + (η/2)‖e_t‖²`.
Stated for every `L_f`-smooth `f` (gradient map `G`), every point `x`, every direction `v` and
every real `η`, with `x⁺ = x − ηv`.
**Formalization Note.** `L_f`-smoothness is the published `ConvexOptAlg.SmoothGD.IsBetaSmooth f G Lf`
(`f` has gradient `G x` at every `x`, `G` is `Lf`-Lipschitz, `Lf ≥ 0`). -/
theorem eq_42 {d : ℕ} (f : EuclideanSpace ℝ (Fin d) → ℝ)
(G : EuclideanSpace ℝ (Fin d) → EuclideanSpace ℝ (Fin d)) (Lf : ℝ)
(hf : ConvexOptAlg.SmoothGD.IsBetaSmooth f G Lf) (x v : EuclideanSpace ℝ (Fin d)) (η : ℝ) :
f (x - η • v) ≤ f x - η / 2 * ‖G x‖ ^ 2 - η / 2 * (1 - Lf * η) * ‖v‖ ^ 2
+ η / 2 * ‖v - G x‖ ^ 2 := by sorry
end PrefixVR
Source
Jiang, Wang, Yang, Li, Zhang, Memory-efficient Finite-sum Optimization without Full Gradient Refreshes (manuscript, sha256 ed33106a…), App. C, Eq. (42), p.15 (PDF p.15)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.