TheoremStatement: AI-adaptedProof: AI-generatedPipeline-generated

How statement and proof provenance work

The first chip identifies the source of the statement or construction; the second identifies the source of its local proof or verification.

Literature-sourced: the exact statement appears in a cited source; only wording and notation differ.
AI-adapted: a semantically identical restatement of literature-sourced material, modulo indexing, notation, and boundary cases adopted by the library.
AI-generated: a genuinely novel statement formulated by AI, with no source for the claim itself.

These labels describe origin, not correctness: citations and verification chips remain separate evidence.

SAGA constant-step linear contraction with a memory-capped factor

Statement

Assume AC. Let $n, d \geq 1$ and let $f_{i} : R^{d} \to R$ be convex, continuously differentiable, with $L$ -Lipschitz gradients for a common $L > 0$ . Set $F = n^{- 1} \sum_{i} f_{i}$ , assume $F$ is $μ$ -strongly convex for $μ > 0$ , and let $x^{*}$ satisfy $\nabla F (x^{*}) = 0$ . Run Finite-sum SAGA from deterministic $x_{0}$ with its standard initialized table and independent uniform component draws. For any constant $0 < η \leq 1 / (10 L)$ , define $V_{k} = ∥ x_{k} - x^{*} ∥_{2}^{2}, S_{k} = \frac{1}{n} \sum_{i} ∥ α_{i}^{k} - \nabla f_{i} (x^{*}) ∥_{2}^{2}, L_{k} = V_{k} + 7 η^{2} n S_{k},$ $δ = \min {μ η, 1 / (7 n)}, q = 1 - δ .$ Then $0 < δ < 1$ , and for every $k \geq 0$ , $E [L_{k + 1} ∣ F_{k}] \leq q L_{k}, E [L_{k}] \leq q^{k} L_{0}, E [F (x_{k}) - F (x^{*})] \leq \frac{L}{2} q^{k} L_{0} .$ In particular $η = 1 / (10 L)$ is allowed independently of $n$ , with $δ = \min {μ / (10 L), 1 / (7 n)}$ . When additionally $μ η \leq 1 / (7 n)$ the factor is $1 - μ η$ ; no such faster factor is asserted without that condition. These are expectation bounds for the exact SAGA recurrence, not almost-sure convergence or finite-oracle success claims.

Facts & Assumptions

Given: The functions, $x^{*}$ , SAGA initialization and independent uniform sampling in this Statement, with AC for conditional-expectation classes. Finite-time moments exist because for each finite $k$ the algorithm has finitely many index histories and each gradient evaluation is finite.

[F1]

Finite-sum SAGA: $x_{k + 1} = x_{k} - η v_{k}$ , then the sampled table entry is replaced by $\nabla f_{I_{k}} (x_{k})$ using the pre-update iterate.

[F2]

SAGA conditional estimator, variance, and table recurrence: conditionally on the history, $E [v_{k} ∣ F_{k}] = \nabla F (x_{k})$ , $E [∥ v_{k} ∥_{2}^{2} ∣ F_{k}] \leq 6 L (F (x_{k}) - F (x^{*})) + 6 S_{k}$ , and $E [S_{k + 1} ∣ F_{k}] \leq (1 - 1 / n) S_{k} + (2 L / n) (F (x_{k}) - F (x^{*}))$ .

[F3]

Gradient of a finite sum is the finite sum of gradients: $\nabla F (w) = n^{- 1} \sum_{i} \nabla f_{i} (w)$ .

[F4]

Descent inequality for a Lipschitz gradient: each $f_{i}$ satisfies its $L$ -smooth upper descent inequality.

[F5]

Strong convexity makes a differentiable gradient strongly monotone: $F (y) \geq F (x) + ⟨ \nabla F (x), y - x ⟩ + (μ / 2) ∥ y - x ∥_{2}^{2}$ .

[F6]

The Euclidean inner product $⟨ x, y ⟩ = \sum_{k < n} x_{k} y_{k}$ on $R^{n}$ : the Euclidean inner product is bilinear and $∥ z ∥_{2}^{2} = ⟨ z, z ⟩$ .

[F7]

Lipschitz map, $α$ -Hölder map for rational $0 < α \leq 1$ , and contraction: an $L$ -Lipschitz gradient satisfies $∥ \nabla f_{i} (x) - \nabla f_{i} (y) ∥_{2} \leq L ∥ x - y ∥_{2}$ .

[F8]

Cauchy-Schwarz $∣ ⟨ x, y ⟩ ∣ \leq ∥ x ∥_{2} ∥ y ∥_{2}$ with its equality case, the triangle inequality for $∥ \cdot ∥_{2}$ , the parallelogram law and polarisation: $∣ ⟨ z, w ⟩ ∣ \leq ∥ z ∥_{2} ∥ w ∥_{2}$ ; applying Cauchy–Schwarz to the finite vector of component norms bounds an average by its root-mean-square norm.

[F9]

Basic algebra and order properties of conditional expectation: conditional expectation preserves order and $E [E [X ∣ F_{k}]] = E [X]$ for integrable $X$ .

[F10]

Finite sums and finite products, by recursion: the finite average is the recursively defined finite sum scaled by $1 / n$ .

[F11]

Laws of finite sums and finite products: finite sums are additive, obey scaling, and are monotone termwise.

[A1]

The Axiom of Choice: AC is assumed by the conditional-expectation interface [F2].

Proof

1.1F3F4F5F11givenalgebra

Put $Δ_{k} = F (x_{k}) - F (x^{*})$ and $e_{k} = x_{k} - x^{*}$ . By [F5] at $x_{k}$ with $y = x^{*}$ , $⟨ \nabla F (x_{k}), e_{k} ⟩ \geq Δ_{k} + (μ / 2) V_{k}$ . By [F5] at $x^{*}$ , $Δ_{k} \geq (μ / 2) V_{k} \geq 0$ . Averaging [F4] at $x^{*}$ and using [F3], [F11] and $\nabla F (x^{*}) = 0$ also gives $Δ_{k} \leq (L / 2) V_{k}$ .

1.2F3F5F7F8F10F11givenalgebra

The average gradient is $L$ -Lipschitz: by [F3], [F7], [F8], [F10] and [F11], $∥ \nabla F (x) - \nabla F (y) ∥_{2}^{2} \leq n^{- 1} \sum_{i} ∥ \nabla f_{i} (x) - \nabla f_{i} (y) ∥_{2}^{2} \leq L^{2} ∥ x - y ∥_{2}^{2}$ . The strong-monotonicity consequence of [F5] and Cauchy–Schwarz [F8] imply $μ \leq L$ , since $d \geq 1$ allows $x \neq y$ . Thus $0 < μ η \leq 1 / 10$ and $0 < δ \leq 1 / (7 n) \leq 1 / 7 < 1$ .

2.1A1F1F2F6step 1.1givenalgebra

Expand [F1] and condition on the current history. Unbiasedness and the second-moment bound in [F2], followed by the gap-retaining inner-product estimate in step 1.1, give $E [V_{k + 1} ∣ F_{k}] \leq V_{k} - 2 η ⟨ \nabla F (x_{k}), e_{k} ⟩ + η^{2} (6 L Δ_{k} + 6 S_{k}) \leq (1 - μ η) V_{k} + (- 2 η + 6 L η^{2}) Δ_{k} + 6 η^{2} S_{k}$ . Finite-time moments exist as stated in the Given paragraph, so all conditional quantities are integrable.

3.1A1F2step 1.1step 2.1givenalgebra

Multiply the table recurrence in [F2] by $7 η^{2} n$ and add step 2.1. This yields $E [L_{k + 1} ∣ F_{k}] \leq (1 - μ η) V_{k} + (- 2 η + 20 L η^{2}) Δ_{k} + (7 n - 1) η^{2} S_{k}$ . Since $η \leq 1 / (10 L)$ , the gap coefficient is nonpositive; since $Δ_{k} \geq 0$ , it can be dropped.

4.1step 1.2step 3.1givenalgebra

By definition $δ \leq μ η$ and $δ \leq 1 / (7 n)$ . Hence $(1 - μ η) V_{k} \leq (1 - δ) V_{k}$ and $(7 n - 1) η^{2} S_{k} = 7 η^{2} n (1 - 1 / (7 n)) S_{k} \leq 7 η^{2} n (1 - δ) S_{k}$ . Apply these two inequalities to step 3.1 to obtain $E [L_{k + 1} ∣ F_{k}] \leq q L_{k}$ . The positivity from step 1.2 gives $q \in (0, 1)$ .

5.1A1F9F11step 1.1step 4.1giveninductionalgebra∎

Apply the tower property and order preservation in [F9] to step 4.1. Induction gives $E [L_{k}] \leq q^{k} L_{0}$ , beginning with equality at $k = 0$ . Step 1.1 and $V_{k} \leq L_{k}$ give the objective bound after taking expectations. Substituting $η = 1 / (10 L)$ gives the advertised constant-step factor; if $μ η \leq 1 / (7 n)$ , the minimum defining $δ$ is $μ η$ .

Remarks

The expectation estimate is not a total-runtime guarantee and does not bound the cost of an individual component-gradient evaluation. At $η = 1 / (10 L)$ , $1 / δ = \max {10 L / μ, 7 n}$ describes the geometric-rate scale; it is not a total runtime bound.

The separate memory-scaled theorem and the standard-initialization counterexample remain unchanged. The counterexample refutes omitting the memory cap from the faster factor, not the present capped rate. This local proof retains the gap term supplied by strong convexity instead of discarding it before combining iterate and table recurrences.

Depends on

Used by

Nothing in the library uses this result yet.

Dependency tree · two levels

70 results within two dependency steps of this one, each drawn at its shortest distance from it. An arrow runs from a result to what uses it, so the chart reads left to right and ends at this result, which carries a heavier outline. Every node is a link to that result. Click elsewhere on the chart to enlarge it.

Sources

Aaron Defazio, Francis Bach, and Simon Lacoste-Julien, SAGA: A Fast Incremental Gradient Method With Support for Non-Strongly Convex Composite Objectives, NeurIPS 2014 (standard reference, not scraped)
Robert M. Gower and Alexandre Gramfort, Optimization for Data Science: Stochastic Variance Reduced Gradient Methods, complete lecture-note deck (standard reference, not scraped)