Home / Curated / Mathematical Methods / Unified Parametric Theory of Proximal SGD

Unified Parametric Theory of Proximal SGD

Mathematical Methods AIMech:UnifiedSgdParametricRecursionTheory DRAFT

Aliases: Unified (A,B,C,D1,D2,rho) Theory of SGD, ABC-SGD Parametric Framework, SGD-star, Q-SGD-SR

A unified parametric convergence analysis framework for composite strongly convex stochastic optimization min_{x in R^d} f(x) + R(x) using proximal stochastic gradient iterates x^{k+1} = prox_{gamma R}(x^k - gamma g^k) with unbiased gradient estimator E_k[g^k] = nabla f(x^k). The framework characterizes the stochastic oracle and auxiliary variance-tracking sequence sigma_k^2 >= 0 via six non-negative parameters (A, B, C, D_1, D_2, rho) satisfying two coupled inequalities: E_k[||g^k - nabla f(x^*)||^2] <= 2 A D_f(x^k, x^*) + B sigma_k^2 + D_1 and E_k[sigma_{k+1}^2] <= (1 - rho) sigma_k^2 + 2 C D_f(x^k, x^*) + D_2. Under stepsize 0 < gamma <= min{1 / (A + C M), rho / (2 mu (1 - B M))} with M > B / rho, the Lyapunov potential V_k = ||x^k - x^*||^2 + M gamma^2 sigma_k^2 contracts linearly up to an explicit neighborhood (D_1 + M D_2) gamma^2 / min{gamma mu, rho - B M}, unifying mini-batch SGD, SAGA, L-SVRG, SEGA, jacSketch, DIANA, and Q-SGD-SR.

Identity Notes & Concept Scope Distinct from individual variance-reduced or quantized stochastic gradient methods (such as SAGA, L-SVRG, SEGA, or DIANA) because it defines the six-parameter (A, B, C, D_1, D_2, rho) meta-assumption (Assumption 4.1) and master Lyapunov contraction theorem (Theorem 4.1) that simultaneously derives existing and new methods (SGD-star, N-SAGA, N-SEGA, Q-SGD-SR) as parameter specializations.

Claims & Grounded Evidence

4 Claims

Mechanism #six-parameter-coupled-oracle-and-memory-inequalities

Assumption 4.1 characterizes any unbiased gradient estimator g^k (E_k[g^k] = nabla f(x^k)) and non-negative sequence {sigma_k^2} via six parameters A >= 0, B >= 0, C >= 0, D_1 >= 0, D_2 >= 0, and 0 <= rho <= 1 such that E_k[||g^k - nabla f(x^*)||^2] <= 2 A D_f(x^k, x^*) + B sigma_k^2 + D_1 and E_k[sigma_{k+1}^2] <= (1 - rho) sigma_k^2 + 2 C D_f(x^k, x^*) + D_2, where D_f(x^k, x^*) = f(x^k) - f(x^*) - <nabla f(x^*), x^k - x^*> is the Bregman divergence.

supports Source: A Unified Theory of SGD: Variance Reduction, Sampling, Quantization and Coordinate Descent · Locator: Section 4, Assumption 4.1, p. 4, Equations (7)-(8)

Mechanism #master-lyapunov-contraction-and-neighborhood-bound

Under mu-quasi-strong convexity of f and Assumption 4.1, Theorem 4.1 proves that for any M > B / rho and stepsize 0 < gamma <= min{1 / (A + C M), rho / (2 mu)}, the Lyapunov functional V_k = ||x^k - x^*||^2 + M gamma^2 sigma_k^2 satisfies E[V_k] <= [max{1 - gamma mu, 1 + B / M - rho}]^k V_0 + ((D_1 + M D_2) gamma^2) / min{gamma mu, rho - B / M}, yielding exact linear convergence to x^* whenever the noise floor constants satisfy D_1 = D_2 = 0.

supports Source: A Unified Theory of SGD: Variance Reduction, Sampling, Quantization and Coordinate Descent · Locator: Section 4, Theorem 4.1 and Corollary 4.1, pp. 4-5, Equations (9)-(11)
supports Source: A Unified Theory of SGD: Variance Reduction, Sampling, Quantization and Coordinate Descent (Crossref metadata) · Locator: Abstract

Application #shift-trick-sgd-star-and-quantized-arbitrary-sampling-specializations

The parametric framework recovers 16 existing and new methods described in Table 1, including SGD-star (which shifts stochastic gradients by nabla f_i(x^*) to achieve A = L_max, B = C = D_1 = D_2 = 0, rho = 1 and linear convergence without dynamic control variates), N-SAGA and N-SEGA under noisy oracles, and Q-SGD-SR combining arbitrary coordinate/minibatch sampling with unbiased quantization.

supports Source: A Unified Theory of SGD: Variance Reduction, Sampling, Quantization and Coordinate Descent · Locator: Section 3, Table 1, p. 4; Section 5 and Appendix A, Table 2, pp. 5-14

Limitation #quasi-strong-convexity-and-unbiased-oracle-requirement

The master theorem requires f to be mu-quasi-strongly convex around x^* and the stochastic gradient estimator g^k to be conditionally unbiased (E_k[g^k] = nabla f(x^k)), so biased contractive compressors with error feedback or nonconvex objectives require separate Lyapunov analyses.

supports Source: A Unified Theory of SGD: Variance Reduction, Sampling, Quantization and Coordinate Descent · Locator: Section 2, Assumption 2.1, p. 2; Section 4, Assumption 4.1(a), p. 4

⚠️ Curated Limitations & Negative Results

Requires f to satisfy mu-quasi-strong convexity around the global minimizer x^*.
Assumes conditionally unbiased stochastic gradient estimators E_k[g^k] = nabla f(x^k), excluding biased contractive compressors without error feedback.

Artificial Intelligence Ontology (AIO) Grounding

Mapped AIO Classes

AIO Target Class	Mapping Relation	Mapping Rationale
`AIO:RegressionAnalysis` Regression Analysis	related_match	Provides the unified convergence and variance-reduction theory for regularized empirical risk minimization and regression objectives.
`AIO:SparseLearning` Sparse Learning	related_match	Directly handles composite proximal operators R(x) such as L1 sparsity regularizers alongside randomized coordinate and subspace sampling.

Evidence Sources & Primary Literature

3 Sources

Source ID	Publication / Document	Type / Access	Reference & Checksum
`r575-primary-pdf`	A Unified Theory of SGD: Variance Reduction, Sampling, Quantization and Coordinate Descent Eduard Gorbunov, Filip Hanzely, Peter Richtarik	primary paper full_text	ID: https://proceedings.mlr.press/v108/gorbunov20a.html sha256:58ef7389889e…
`r575-arxiv-abs`	A Unified Theory of SGD: Variance Reduction, Sampling, Quantization and Coordinate Descent (arXiv abstract) Eduard Gorbunov, Filip Hanzely, Peter Richtarik	primary paper abstract_only	ID: https://arxiv.org/abs/1905.11261 sha256:e5ca580aa428…
`r575-metadata-cr`	A Unified Theory of SGD: Variance Reduction, Sampling, Quantization and Coordinate Descent (Crossref metadata) Eduard Gorbunov, Filip Hanzely, Peter Richtarik	primary paper abstract_only	ID: https://proceedings.mlr.press/v108/gorbunov20a.html sha256:d056e62a2f9f…

Ontology & Grounding Topology

Open in interactive network graph →

Curation Provenance

Curator: Antigravity

Method: ai_assisted

Model: Gemini

Created: 2026-10-19T10:58:00Z

Updated: 2026-10-19T10:58:00Z

Source File: data/curated/UnifiedSgdParametricRecursionTheory.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