Proposition 2 — for n ≥ 8L/μ, SAG with α = 1/(2nμ) after an SG pass satisfies E[g(xᵏ) − g(x*)] ≤ C(1 − 1/(8n))ᵏ for k ≥ n
ProvedSAG.LargeStep.proposition_2Throughout, () are convex and differentiable with -Lipschitz gradients , the average is -strongly convex ( is convex, ), minimizes , and .
Assume . Consider the run in which the first iterations use stochastic gradient from with step sizes , SAG is then initialized with the average of the stochastic gradient iterates and with all set to zero, and the subsequent SAG iterations use step size ; all indices are independent and uniform on . Then for every
The paper explains: "We state this result for because we assume that the first iterations of the algorithm use an SG method and that we initialize the subsequent SAG iterations with the average of the iterates, which leads to an rate. In contrast, using the SAG iterations from the beginning gives the same rate but with a constant proportional to . Note that this bound is obtained when initializing all to zero after the SG phase."
When , each pass through the data thus reduces the expected suboptimality by the factor , independently of and .
Formalization Note The run is hybrid (see its definition for the index bookkeeping: indices are drawn, the stochastic gradient phase uses the first , index is unused, SAG uses the last ). The expectation is the uniform average over all index sequences.
import Mathlib import Definitions.Def_SAGA_Convex_finiteSum import Definitions.Def_SAGA_Convex_sagaRun import Definitions.Def_SAG_LargeStep_setting import Definitions.Def_SAG_LargeStep_hybrid
namespace SAG.LargeStep
/-- Proposition 2, p. 6: if `n ≥ 8L/μ`, the run of `hybrid` (one pass of stochastic gradient
with `γ_j = 1/(2L + μj/2)`, average of its iterates, table reset to `0`, then SAG with
`α = 1/(2nμ)`) satisfies, for `k ≥ n`, `E[g(xᵏ) − g(x*)] ≤ C (1 − 1/(8n))ᵏ` with
`C = 16L/(3n)‖x⁰ − x*‖² + 4σ²/(3nμ)(8 log(1 + μn/(4L)) + 1)`. -/
theorem proposition_2 {p n : ℕ} (f : Fin n → EuclideanSpace ℝ (Fin p) → ℝ)
(f' : Fin n → EuclideanSpace ℝ (Fin p) → EuclideanSpace ℝ (Fin p)) (L μ : ℝ)
(xstar : EuclideanSpace ℝ (Fin p)) (h : Assumptions f f' L μ xstar)
(hn : 8 * L / μ ≤ (n : ℝ)) (x0 : EuclideanSpace ℝ (Fin p)) (k : ℕ) (hk : n ≤ k) :
SAGA.Convex.expectIdx n k (fun js =>
SAGA.Convex.fAvg f (hybrid f' L μ x0 js) - SAGA.Convex.fAvg f xstar)
≤ (16 * L / (3 * (n : ℝ)) * ‖x0 - xstar‖ ^ 2
+ 4 * sigmaSq f' xstar / (3 * (n : ℝ) * μ)
* (8 * Real.log (1 + μ * (n : ℝ) / (4 * L)) + 1))
* (1 - 1 / (8 * (n : ℝ))) ^ k := by sorry
end SAG.LargeStep
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.