Lemma 2 — variance of a prefix difference
ProvedPrefixVR.lemma_2finite-sum-optimizationnonconvex-optimizationp2o-gran-per-chapterp2o-plan-paperp2o-strengthenedp2o-v1variance-reduction
Suppose condition (2) holds with constant . Fix and a nonempty subset of size . Define
If is uniform on , then
Both inequalities are asserted.
This is the variance bound for the prefix reconstruction: a single sampled difference from the already inserted components costs at most , uniformly in the prefix.
Formalization Note over is the average ; is a Finset (Fin n).
Differences from the source:
- generalization: the component gradients ∇fᵢ of differentiable fᵢ, with ∇f their average in (2) → arbitrary maps g i : ℝᵈ → ℝᵈ satisfying (2) with ∇f replaced by the average (1/n)∑ g i; reason: the statement and its proof use only (2); taking g i = ∇fᵢ, whose average is ∇f, gives the source's statement
- encoding: j ∼ Unif(A) and 𝔼_j → the average (1/k)∑_{j∈A}; reason: this is the expectation under the uniform law on A
- encoding: [n] and A ⊆ [n] → Fin n and A : Finset (Fin n); reason: Lean convention
Preamble
import Mathlib import Definitions.Def_PrefixVR_Variation
Formal statement
namespace PrefixVR
/-- **Lemma 2 (variance of a prefix difference).** Jiang, Wang, Yang, Li, Zhang, *Memory-efficient
Finite-sum Optimization without Full Gradient Refreshes* (manuscript, sha256 ed33106a…), Lemma 2,
Eq. (24), p.12: suppose (2) holds; fix `x, y` and a nonempty `A ⊆ [n]` of size `k`; with
`dᵢ = ∇fᵢ(x) − ∇fᵢ(y)` and `d_A = (1/k) ∑_{i∈A} dᵢ`, if `j ∼ Unif(A)` then
`𝔼_j ‖(k/n)(d_j − d_A)‖² ≤ (k/n) δ² ‖x − y‖² ≤ δ² ‖x − y‖²`.
**Formalization Note.** Components are `Fin n`; `g i` stands for `∇fᵢ` and (2) is `Variation g δ`
(with `∇f` the average of the `g i`). `𝔼_j` over `j ∼ Unif(A)` is the average `(1/k) ∑_{j∈A}`. -/
theorem lemma_2 {n d : ℕ}
(g : Fin n → EuclideanSpace ℝ (Fin d) → EuclideanSpace ℝ (Fin d)) (δ : ℝ)
(hvar : Variation g δ) (x y : EuclideanSpace ℝ (Fin d)) (A : Finset (Fin n))
(hA : A.Nonempty) :
(A.card : ℝ)⁻¹ * ∑ j ∈ A,
‖((A.card : ℝ) / n) • ((g j x - g j y) -
(A.card : ℝ)⁻¹ • ∑ i ∈ A, (g i x - g i y))‖ ^ 2
≤ (A.card : ℝ) / n * δ ^ 2 * ‖x - y‖ ^ 2 ∧
(A.card : ℝ) / n * δ ^ 2 * ‖x - y‖ ^ 2 ≤ δ ^ 2 * ‖x - y‖ ^ 2 := by sorry
end PrefixVR
Source
Jiang, Wang, Yang, Li, Zhang, Memory-efficient Finite-sum Optimization without Full Gradient Refreshes (manuscript, sha256 ed33106a…), App. A, Lemma 2, Eq. (24), p.12 (PDF p.12)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.