ZeroSARAH and D-ZeroSARAH Variance-Reduced Nonconvex Optimization without Full Gradient Computations
Algorithms AIMech:ZeroSarahAndDZeroSarahVarianceReducedNonconvexOptimizationWithoutFullGradientComputations DRAFT
Aliases: ZeroSARAH, D-ZeroSARAH, Distributed ZeroSARAH, Variance-Reduced Nonconvex Optimization with Zero Full Gradient Computation
A family of single-loop variance-reduced stochastic optimization algorithms for nonconvex finite-sum minimization f(x) = (1/n) sum_{i=1}^n f_i(x) (ZeroSARAH) and partial-participation distributed finite-sum minimization (D-ZeroSARAH) introduced by Li, Hanzely, and Richtárik (2021). ZeroSARAH maintains a historical gradient table {y_i^{k-1}}_{i=1}^n initialized to zero (requiring zero full gradient computations throughout training), samples a mini-batch I_b^k subseteq [n] of size b_k, updates the gradient estimator via v^k = (1/b_k) sum_{i in I_b^k} (nabla f_i(x^k) - nabla f_i(x^{k-1})) + (1 - lambda_k) v^{k-1} + lambda_k ((1/b_k) sum_{i in I_b^k} (nabla f_i(x^{k-1}) - y_i^{k-1}) + (1/n) sum_{j=1}^n y_j^{k-1}), steps x^{k+1} = x^k - eta_k v^k, and refreshes y_i^k = nabla f_i(x^k) for i in I_b^k while keeping y_i^k = y_i^{k-1} for i not in I_b^k.
Identity Notes & Concept Scope
Distinct from classical SARAH, SPIDER, SpiderBoost, and PAGE (which require an initial full gradient computation nabla f(x^0) and/or periodic full-batch checkpoints of cost O(n) every epoch or with probability p_k), and distinct from SAGA (which achieves O(n^{2/3}/epsilon^2) nonconvex gradient complexity rather than O(sqrt(n)/epsilon^2)): ZeroSARAH combines SARAH's recursive difference update with a SAGA-style historical table correction weighted by lambda_k = b_k / (2n) so that E_k[v^k - nabla f(x^k)] = (1 - lambda_k)(v^{k-1} - nabla f(x^{k-1})), never computing any full gradient across all iterations.
Claims & Grounded Evidence
4 Claims
Mechanism
#zerosarah-recursive-table-corrected-estimator-and-bias-decay
ZeroSARAH initializes x^{-1} = x^0, v^{-1} = 0, and y_1^{-1} = ... = y_n^{-1} = 0 without evaluating nabla f(x^0), and at iteration k >= 0 samples a mini-batch I_b^k of size b_k to form v^k = (1/b_k) sum_{i in I_b^k}(nabla f_i(x^k) - nabla f_i(x^{k-1})) + (1 - lambda_k) v^{k-1} + lambda_k ((1/b_k) sum_{i in I_b^k}(nabla f_i(x^{k-1}) - y_i^{k-1}) + (1/n) sum_{j=1}^n y_j^{k-1}); by Lemma 1, the conditional expectation of the estimation error satisfies E_k[v^k - nabla f(x^k)] = (1 - lambda_k)(v^{k-1} - nabla f(x^{k-1})).
Mechanism
#zerosarah-optimal-nonconvex-complexity-with-zero-full-gradients
Under L-smoothness (Assumption 1), setting b_k = sqrt(n), lambda_0 = 1, lambda_k = b_k / (2n) for k >= 1, and step size eta_k = 1 / ((1 + sqrt(8)) L) yields M_{k+1} = 2 / (lambda_{k+1} b_{k+1}) + 8 lambda_{k+1} n^2 / b_{k+1}^3 = 8 and guarantees E[||nabla f(hat{x}^K)||^2] <= epsilon^2 in O(sqrt(n) (L Delta_0 + G_0) / epsilon^2) stochastic gradient computations with zero full gradient evaluations, recovering best-known O(n + sqrt(n) L Delta_0 / epsilon^2) complexity when initialized with y_i^{-1} = nabla f_i(x^0) (Theorem 1, Corollaries 1-2).
Application
#d-zerosarah-distributed-partial-participation-nonconvex-optimization
D-ZeroSARAH (Algorithm 3) extends ZeroSARAH to distributed optimization f(x) = (1/m) sum_{i=1}^m f_i(x) where each client i in [m] holds s local functions f_{i,j}: in each round k, a subset I_{b_1}^k subseteq [m] of b_1 clients is sampled and each active client samples a local mini-batch I_{i,b_2}^k subseteq [s] of size b_2, achieving E[||nabla f(hat{x}^K)||^2] <= epsilon^2 without ever requiring full client participation or full local dataset gradient evaluation (Theorem 2, Corollaries 3-4).
Limitation
#zerosarah-historical-gradient-table-memory-limitation
Maintaining the historical gradient table {y_i^{k-1}}_{i=1}^n requires O(n d) memory in general (reduced to O(n) scalar storage for generalized linear models where nabla f_i(x) scales a fixed feature vector a_i), and the zero-full-gradient complexity bound depends on the initial average squared component gradient norm G_0 = (1/n) sum_{i=1}^n ||nabla f_i(x^0)||^2 when y_i^{-1} is initialized to zero.
⚠️ Curated Limitations & Negative Results
- Requires storing historical component gradients {y_i^{k-1}}_{i=1}^n (O(nd) memory in general, or O(n) scalars for linear predictors).
- When initialized with y_i^{-1} = 0 to avoid any initial full gradient pass, the stochastic gradient complexity includes an additive O(sqrt(n) G_0 / epsilon^2) term proportional to G_0 = (1/n) sum_{i=1}^n ||nabla f_i(x^0)||^2.
Artificial Intelligence Ontology (AIO) Grounding
Mapped AIO Classes
| AIO Target Class | Mapping Relation | Mapping Rationale |
|---|---|---|
AIO:FederatedLearning
Federated Learning
|
related_match | D-ZeroSARAH (Algorithm 3) extends ZeroSARAH to distributed/federated nonconvex optimization across m clients with partial client participation without ever evaluating gradients across all clients or all local data samples simultaneously. |
Evidence Sources & Primary Literature
3 Sources| Source ID | Publication / Document | Type / Access | Reference & Checksum |
|---|---|---|---|
r566-primary-pdf
|
Zhize Li, Slavomír Hanzely, Peter Richtárik
|
primary paper
full_text
|
ID: https://api.openalex.org/works/W3135176055
sha256:3385bfc630e0…
|
r566-arxiv-abs
|
Zhize Li, Slavomír Hanzely, Peter Richtárik
|
primary paper
abstract_only
|
ID: https://arxiv.org/abs/2103.01447
sha256:98c65f118e72…
|
r566-metadata-cr
|
Zhize Li, Slavomír Hanzely, Peter Richtárik
|
primary paper
abstract_only
|
ID: https://api.openalex.org/works/W3135176055
sha256:a81243e29e4d…
|
Ontology & Grounding Topology
Open in interactive network graph →Curation Provenance
Curator: Antigravity
Method: ai_assisted
Model: Gemini
Created: 2026-10-19T10:49:00Z
Updated: 2026-10-19T10:49:00Z
Explore across X-Mech
Related computational & biological Mechs:
Embedding Map
Network Graph
ProteinTraitsMech (ESM-2 pLM)
DUFMech (Domain pLM)
TraitMech
CultureMech
All 14 X-Mech Repositories