Proposition 1 — SAG with :
ProvedSAG.SmallStep.proposition_1Let , , be convex and differentiable with gradients that are Lipschitz continuous with constant , . Assume that the average is strongly convex with constant , meaning that is convex, and let be the minimizer of . Put .
Run the SAG iterations with the constant step size from and the zero table for all , with indices independent and uniform on . Then for every ,
This is the first main result of the paper: an incremental method that evaluates a single component gradient per iteration converges linearly in expectation for strongly convex finite sums, unlike stochastic gradient methods, whose rate is sublinear.
Formalization Note is EuclideanSpace ℝ (Fin p) and the indices are Fin n. The expectation is SAGA.Convex.expectIdx n k, the uniform average over all index sequences in , i.e. the law of i.i.d. uniform indices; the expectation is over the algorithm's randomness only. is a minimizer of (∀ x, g x* ≤ g x); its uniqueness is a consequence. Each is convex as assumed in §A.1 (p. 13) and needed by the proof's co-coercivity step. The run is SAG.SmallStep.runFrom with step from . No restriction is assumed (it follows when ).
import Mathlib import Definitions.Def_SAGA_Convex_finiteSum import Definitions.Def_SAGA_Convex_sagaRun import Definitions.Def_SAG_SmallStep_run
namespace SAG.SmallStep
/-- Proposition 1 (Le Roux–Schmidt–Bach, arXiv:1202.6258v4, p. 5). With the constant step size
`α = 1/(2nL)` and the table initialized to `y⁰ = 0`, the SAG iterates satisfy, for `k ≥ 1`,
`E‖xᵏ − x*‖² ≤ (1 − μ/(8Ln))ᵏ [3‖x⁰ − x*‖² + 9σ²/(4L²)]`, where `σ² = (1/n) ∑ᵢ ‖f'ᵢ(x*)‖²` and the
expectation is over `k` i.i.d. uniform indices. -/
theorem proposition_1 {p n : ℕ} (hn : 0 < n)
(f : Fin n → EuclideanSpace ℝ (Fin p) → ℝ)
(f' : Fin n → EuclideanSpace ℝ (Fin p) → EuclideanSpace ℝ (Fin p)) (L μ : ℝ)
(hL : 0 < L) (hμ : 0 < μ)
(hgrad : ∀ i x, HasGradientAt (f i) (f' i x) x)
(hconv : ∀ i, ConvexOn ℝ Set.univ (f i))
(hlip : ∀ i x y, ‖f' i x - f' i y‖ ≤ L * ‖x - y‖)
(hsc : ConvexOn ℝ Set.univ (fun x => SAGA.Convex.fAvg f x - μ / 2 * ‖x‖ ^ 2))
(xstar : EuclideanSpace ℝ (Fin p))
(hmin : ∀ x, SAGA.Convex.fAvg f xstar ≤ SAGA.Convex.fAvg f x)
(x0 : EuclideanSpace ℝ (Fin p)) (k : ℕ) (hk : 1 ≤ k) :
SAGA.Convex.expectIdx n k
(fun js => ‖(runFrom f' (1 / (2 * (n : ℝ) * L)) (fun _ => 0, x0) js).2 - xstar‖ ^ 2)
≤ (1 - μ / (8 * L * (n : ℝ))) ^ k
* (3 * ‖x0 - xstar‖ ^ 2 + 9 * ((1 / (n : ℝ)) * ∑ i, ‖f' i xstar‖ ^ 2) / (4 * L ^ 2)) := by sorry
end SAG.SmallStep
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.