Home / Curated / Algorithms / SCSG (Stochastically Controlled Stochastic Gradient) for Non-Convex Optimization

SCSG (Stochastically Controlled Stochastic Gradient) for Non-Convex Optimization

Algorithms AIMech:ScsgStochasticallyControlledStochasticGradientForNonconvexOptimization DRAFT

Aliases: SCSG, Non-Convex SCSG, Stochastically Controlled Stochastic Gradient

A variance-reduced stochastic optimization algorithm (Lei, Ju, Chen, & Jordan 2017) for smooth non-convex finite-sum and online optimization min_x f(x) = (1/n) sum_{i=1}^n f_i(x) that replaces SVRG's full-dataset outer gradient pass with a subsampled without-replacement batch I_j subset {1, ..., n} of size B_j <= n, sets the anchor gradient g_j = (1/B_j) sum_{i in I_j} nabla f_i(xtilde_{j-1}), draws a geometrically distributed number of inner-loop steps N_j ~ Geom(B_j / (B_j + b_j)) (so E[N_j] = B_j / b_j), performs b_j-minibatch variance-reduced updates v_{k-1}^{(j)} = nabla f_{I'_{k-1}}(x_{k-1}^{(j)}) - nabla f_{I'_{k-1}}(xtilde_{j-1}) + g_j, and sets xtilde_j = x_{N_j}^{(j)}, achieving E||nabla f(xhat)||_2^2 <= varepsilon in O(min{varepsilon^{-5/3}, n^{2/3} varepsilon^{-1}} + min{varepsilon^{-1}, n}) (equivalently O(min{varepsilon_g^{-10/3}, n^{2/3} varepsilon_g^{-2}} + min{varepsilon_g^{-2}, n}) for E||nabla f(xhat)||_2 <= varepsilon_g) stochastic gradient evaluations.

Identity Notes & Concept Scope Distinct from classical SVRG (Johnson & Zhang 2013; Reddi et al. 2016; Allen-Zhu & Hazan 2016), which computes a full n-sample gradient at every outer epoch (incurring an unavoidable O(n + n^{2/3} / varepsilon_g^2) cost even when n >> varepsilon_g^{-2}) and uses a fixed deterministic epoch length m with uniform random iterate selection; from SAGA (Defazio et al. 2014, AIMech:SagaFastIncrementalGradientMethodWithSupportForNonStronglyConvexCompositeObjectives), which stores O(n*d) gradient tables; and from recursive path-integrated estimators (SARAH, SPIDER, SNVRG, STORM, PAGE), which update the gradient estimate incrementally from x_{t-1} rather than from a geometrically terminated epoch anchor xtilde_{j-1}.

Claims & Grounded Evidence

3 Claims

Mechanism #r375-claim-geometric-epoch-telescoping-and-one-epoch-bound

For any sequence {D_k}_{k >= 0} and geometric stopping time N_j ~ Geom(gamma) on {0, 1, 2, ...} with P(N_j = k) = gamma^k (1 - gamma) and gamma = B_j / (B_j + b_j), the exact expectation identity E_{N_j}[D_{N_j} - D_{N_j + 1}] = (1 / E[N_j]) * E_{N_j}[D_0 - D_{N_j}] = (b_j / B_j) * (D_0 - E_{N_j}[D_{N_j}]) (Lemma A.2) telescopes single-step descent directly into an epoch-level bound on the terminal iterate xtilde_j = x_{N_j}^{(j)} without storing intermediate inner-loop iterates: for step size eta_j * L * (B_j / b_j)^{2/3} <= c_0, E||nabla f(xtilde_j)||_2^2 <= (2 / (eta_j * (1 - 2 * eta_j * L))) * (b_j / B_j) * E[f(xtilde_{j-1}) - f(xtilde_j)] + (I(B_j < n) / B_j) * (6 / (1 - 2 * eta_j * L)) * S^2 (Theorem 3.1).

supports Source: Non-convex Finite-Sum Optimization Via SCSG Methods · Locator: Section 3, Theorem 3.1; Appendix A, Lemma A.2; Appendix B, Lemma B.1 and Theorem B.1

Mechanism #r375-claim-sample-size-independent-and-finite-sum-complexity-regimes

Setting step size eta_j = (b_j / B_j)^{2/3} / (6L) and outer batch size B_j = min{n, S^2 / varepsilon} (where varepsilon denotes target squared gradient norm E||nabla f(xhat)||_2^2 <= varepsilon, i.e., varepsilon = varepsilon_g^2) gives total expected stochastic gradient complexity O(B^{-1/3} * L * Delta_f / (varepsilon * b^{1/3}) + B) = O((min{S^2 / varepsilon, n})^{2/3} * (L * Delta_f / (S^2 * b^{1/3})) + min{S^2 / varepsilon, n}) = O(min{varepsilon^{-5/3}, n^{2/3} * varepsilon^{-1}}) (Theorem 3.2, Corollary 3.3, Table 1), strictly dominating both SGD O(varepsilon^{-2}) when varepsilon << 1 and SVRG O(n + n^{2/3} * varepsilon^{-1}) in the practical large-data regime where varepsilon^{-1} < n without ever computing a full pass over all n examples.

supports Source: Non-convex Finite-Sum Optimization Via SCSG Methods · Locator: Section 1, Table 1; Section 3.2, Theorem 3.2, Corollaries 3.1-3.3, Figure 1

Application #r375-claim-polyak-lojasiewicz-and-dnn-warm-start-applications

Under the mu-Polyak-Lojasiewicz condition 1/2 * ||nabla f(x)||_2^2 >= mu * (f(x) - f^*), SCSG achieves E[f(xhat) - f^*] <= varepsilon in O((min{L/mu * (L / (mu * b))^{1/3}, n^{2/3} * L / (mu * b^{1/3})} + min{n, S^2 / (mu * varepsilon)}) * log(1/varepsilon)) gradient evaluations (Theorem 4.3, Table 2); on MNIST 3-layer fully connected and LeNet convolutional neural networks, SCSG with polynomially growing batch sizes B_j propto j^{3/2} outperforms mini-batch SGD from random initialization without needing an SGD warm-start.

supports Source: Non-convex Finite-Sum Optimization Via SCSG Methods · Locator: Section 4, Table 2, Theorem 4.3; Section 5, Experiments, Figures 2-3

⚠️ Curated Limitations & Negative Results

Achieves O(min(varepsilon_g^{-10/3}, n^{2/3} varepsilon_g^{-2})) for E||nabla f(x)||_2 <= varepsilon_g because it anchors inner-loop variance reduction at a fixed epoch reference point xtilde_{j-1}, which is suboptimal by a factor of varepsilon_g^{-1/3} (online) or n^{1/6} (finite-sum) compared to recursive path-integrated estimators such as SPIDER, SNVRG, STORM, and PAGE (Section 3.2, Table 1).

Artificial Intelligence Ontology (AIO) Grounding

Mapped AIO Classes

AIO Target Class	Mapping Relation	Mapping Rationale
`AIO:LogisticRegression` Logistic Regression	related_match	Provides non-convex and PL finite-sum stochastic optimization applicable to regularized empirical risk minimization and deep classifiers.

Evidence Sources & Primary Literature

3 Sources

Source ID	Publication / Document	Type / Access	Reference & Checksum
`r375-primary-pdf`	Non-convex Finite-Sum Optimization Via SCSG Methods Lihua Lei, Cheng Ju, Jianbo Chen, Michael I. Jordan	primary paper full_text	ID: https://papers.nips.cc/paper/2017/hash/2eb5657d37f474e4c4cf01e4882b8962-Abstract.html sha256:0e538f5216a0…
`r375-arxiv-abs`	Non-convex Finite-Sum Optimization Via SCSG Methods (arXiv abstract) Lihua Lei, Cheng Ju, Jianbo Chen, Michael I. Jordan	primary paper abstract_only	ID: https://arxiv.org/abs/1706.09156 sha256:060517232df1…
`r375-metadata-cr`	Non-convex Finite-Sum Optimization Via SCSG Methods (Crossref metadata) Lihua Lei, Cheng Ju, Jianbo Chen, Michael I. Jordan	primary paper abstract_only	ID: https://papers.nips.cc/paper/2017/hash/2eb5657d37f474e4c4cf01e4882b8962-Abstract.html sha256:6de5db2f23b6…

Ontology & Grounding Topology

Open in interactive network graph →

Curation Provenance

Curator: Antigravity

Method: ai_assisted

Model: Gemini

Created: 2026-10-19T07:38:00Z

Updated: 2026-10-19T07:38:00Z

Source File: data/curated/ScsgStochasticallyControlledStochasticGradientForNonconvexOptimization.yaml · Schema: curated_concept.yaml

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