Theorem 1, p. 7 — SAG with α = 1/(16L): E[g(x̄ᵏ)] − g(x*) ≤ (32n/k)C₀, and E[g(xᵏ)] − g(x*) ≤ (1 − min{μ/16L, 1/8n})ᵏC₀ if g is μ-strongly convex
ProvedSAGFiniteSum.Rate.theorem_1Let , , be convex and differentiable with gradients that are Lipschitz continuous with constant , , and let be a minimizer of . Put and .
Run the stochastic average gradient (SAG) method with the constant step size from : at iteration an index is drawn uniformly from , independently of the past, the table entry is replaced by , and . Let . Then for every ,
where
- if the table is initialized with , then ;
- if it is initialized with , then .
Further, if is -strongly convex for some (that is, is convex), then for each of the two initializations, with its ,
This is the main result of the paper: SAG, which evaluates one component gradient per iteration, attains the rate of full gradient descent in the convex case and a linear rate in the strongly convex case, with constants that make it faster than both stochastic and deterministic gradient methods for large .
Formalization Note is EuclideanSpace ℝ (Fin p) and indices are Fin n. The expectation over the algorithm's randomness is SAGA.Convex.expectIdx n k, the uniform average over all index sequences; the data are deterministic. The four claims (two initializations, two rates) are stated as one conjunction; strong convexity is a hypothesis of the last two only. The theorem covers every , including , where SAG is gradient descent and the page's proof does not apply (it assumes ).
import Mathlib import Definitions.Def_SAGFiniteSum_Rate_Model open scoped RealInnerProductSpace
namespace SAGFiniteSum.Rate
/-- Theorem 1 (Schmidt, Le Roux & Bach, arXiv:1309.2388v2, p. 7). SAG with the constant step
size `α = 1/(16L)`, for `k ≥ 1`, from `(y⁰, x⁰)` with `y⁰ = 0` or `y⁰ᵢ = f'ᵢ(x⁰) − g'(x⁰)`:
`E[g(x̄ᵏ)] − g(x*) ≤ (32n/k) C₀`, and if `g` is `μ`-strongly convex,
`E[g(xᵏ)] − g(x*) ≤ (1 − min{μ/(16L), 1/(8n)})ᵏ C₀`, with the `C₀` of each initialization. -/
theorem theorem_1 {p n : ℕ} (f : Fin n → EuclideanSpace ℝ (Fin p) → ℝ)
(f' : Fin n → EuclideanSpace ℝ (Fin p) → EuclideanSpace ℝ (Fin p)) (L : ℝ)
(xstar : EuclideanSpace ℝ (Fin p)) (hA : SAGAssumptions f f' L xstar)
(x0 : EuclideanSpace ℝ (Fin p)) (k : ℕ) (hk : 1 ≤ k) :
(SAGA.Convex.expectIdx n k
(fun js => SAGA.Convex.fAvg f (avgIter f' (1 / (16 * L)) (zeroTable, x0) js))
- SAGA.Convex.fAvg f xstar
≤ 32 * (n : ℝ) / (k : ℝ) * C0zero f f' L xstar x0)
∧ (SAGA.Convex.expectIdx n k
(fun js => SAGA.Convex.fAvg f (avgIter f' (1 / (16 * L)) (centeredTable f' x0, x0) js))
- SAGA.Convex.fAvg f xstar
≤ 32 * (n : ℝ) / (k : ℝ) * C0centered f L xstar x0)
∧ (∀ μ : ℝ, 0 < μ →
ConvexOn ℝ Set.univ (fun x => SAGA.Convex.fAvg f x - μ / 2 * ‖x‖ ^ 2) →
(SAGA.Convex.expectIdx n k
(fun js => SAGA.Convex.fAvg f (sagIter f' (1 / (16 * L)) (zeroTable, x0) js k).2)
- SAGA.Convex.fAvg f xstar
≤ (1 - min (μ / (16 * L)) (1 / (8 * (n : ℝ)))) ^ k * C0zero f f' L xstar x0)
∧ (SAGA.Convex.expectIdx n k
(fun js => SAGA.Convex.fAvg f
(sagIter f' (1 / (16 * L)) (centeredTable f' x0, x0) js k).2)
- SAGA.Convex.fAvg f xstar
≤ (1 - min (μ / (16 * L)) (1 / (8 * (n : ℝ)))) ^ k * C0centered f L xstar x0)) := by sorry
end SAGFiniteSum.Rate
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.