WorksMathematics

Variance Reduction Note 4: The Convergence of SVRG

Published Nov 03, 2026Fresh — added to the Hub within the last 30 daysv14 min read

AI contributions

Not recorded for this paper

Abstract

Stochastic variance-reduced gradient (SVRG) uses a full gradient at a snapshot point to correct inexpensive component gradients. This fourth expository note on variance reduction explains that control variate and gives a self-contained proof of linear convergence for the classical strongly convex finite-sum setting. Each component is assumed convex and smooth, while only their average must be strongly convex. A second-moment bound links the estimator to the objective gaps at the current iterate and the snapshot. Summing a distance recursion over an epoch then yields a geometric decrease and an oracle complexity of order $(n+L/μ)\log(1/τ)$ for objective accuracy $τ$ , with the initial gap fixed. The result uses a random snapshot update and counts all full-gradient computations. No new algorithm or rate is claimed.

A snapshot as a control variate

Consider the finite-sum problem

\min_{x\in\mathbb{R}^{d}} F(x) := \frac{1}{n}\sum_{i=1}^{n} f_i(x). \tag*{(1)}

Sampling a single component gradient is inexpensive, but its noise can persist at the minimizer: individual $\nabla f_i(x_\star)$ need not vanish even when $\nabla F(x_\star) = 0$ . SVRG, introduced by Johnson and Zhang [6], corrects this noise using a snapshot $\widetilde{x}$ and its exact gradient. For a uniform random index $i$ , the estimator is

v(x,\widetilde{x};i) = \nabla f_i(x) - \nabla f_i(\widetilde{x}) + \nabla F(\widetilde{x}). \tag*{(2)}

The subtracted and added terms have the same expectation. Consequently, the estimator is unbiased for $\nabla F(x)$ , while the shared index cancels much of the component noise. At $x = \widetilde{x}$ , it equals the full gradient for every index.

This note develops the classical strongly convex analysis. Related finite-sum methods include SAG, SAGA, and proximal SVRG [4, 8, 10]. Recursive approaches such as SARAH, SPIDER, and PAGE [23, 26, 31] use a different form of correction. An overview of these method families appears in [2].

Assumptions and the epoch algorithm

Assumption 1. Each $f_i : \mathbb{R}^{d} \to\mathbb{R}$ is convex, differentiable, and has an $L$ -Lipschitz gradient, with $L > 0$ . Their average $F$ is $\mu$ -strongly convex for some $0 < \mu\le L$ : for all $x,y$ ,

F(y) \ge F(x) + \langle\nabla F(x), y-x \rangle+ \frac{\mu}{2}\lVert y-x\rVert^{2}. \tag*{(3)}

Let $x_\star$ be its unique minimizer, $F_\star= F(x_\star)$ , and $h(x) = F(x) - F_\star$ . Norms are Euclidean.

The components need not be strongly convex and need not share a minimizer. We do not assume uniformly bounded stochastic-gradient variance. The proof instead derives a bound that shrinks with the objective gaps.

Fix an initial snapshot $\tilde{x}_0$ , a step size $\eta> 0$ , and an integer epoch length $m \ge1$ . At epoch $s = 0,1,\ldots$ :

Compute the full snapshot gradient $\tilde{g}_s = n^{-1}\sum_{i=1}^{n}\nabla f_i(\tilde{x}_s)$ , and initialize $x_0 = \tilde{x}_s$ .

For $t = 0,\ldots,m-1$ , draw a fresh independent uniform index $i_t \in\{1,\ldots,n\}$ and update

v_t = \nabla f_{i_t}(x_t) - \nabla f_{i_t}(\tilde{x}_s) + \tilde{g}_s,\qquad x_{t+1} = x_t - \eta v_t. \tag*{(4)}

Choose $J_s$ independently and uniformly from $\{0,\ldots,m-1\}$ , and set $\tilde{x}_{s+1} = x_{J_s}$ .

The inner index $t$ restarts at each epoch. This random snapshot choice is the variant analyzed below; the proof averages the function values of precisely these $m$ iterates. An implementation may draw $J_s$ in advance and retain its selected iterate without storing the whole trajectory. The cost per epoch is at most $n + 2m$ component-gradient evaluations, using $O(d)$ auxiliary vector storage when snapshot component gradients are recomputed as needed.

A short linear-convergence proof

The proof first controls component-gradient differences at the solution, then bounds the SVRG estimator, and finally sums a distance recursion over one epoch.

Lemma 1 (Gradient differences and objective gaps). Under Assumption 1, for every $x$ ,

\frac{1}{n}\sum_{i=1}^{n}\lVert\nabla f_i(x)-\nabla f_i(x^\star)\rVert^2 \le2Lh(x). \tag*{(5)}

Proof. Define $\psi_i(u) = f_i(u) - f_i(x^\star) - \langle\nabla f_i(x^\star),u-x^\star\rangle$ . Convexity gives $\psi_i(u) \ge0$ , and $\psi_i$ is $L$ -smooth. Apply its descent inequality at $u=x$ with $y=x-\nabla\psi_i(x)/L$ :

0 \le\psi_i(y) \le\psi_i(x) - \frac{1}{2L}\lVert\nabla\psi_i(x)\rVert^2.

Thus $\lVert\nabla f_i(x)-\nabla f_i(x^\star)\rVert^2 \le2L\psi_i(x)$ . Averaging over $i$ gives (5), because $n^{-1}\sum_i\nabla f_i(x^\star)=\nabla F(x^\star)=0$ .

Lemma 2 (Unbiasedness and second moment). For fixed $x$ , $\tilde{x}$ and a uniform index $i$ , the estimator in (2) satisfies

\mathbb{E}_i[v] = \nabla F(x),\qquad\mathbb{E}_i\lVert v\rVert^2 \le4L[h(x)+h(\tilde{x})]. \tag*{(6)}

Proof. Unbiasedness follows by averaging (2). Set $a_i=\nabla f_i(x)-\nabla f_i(x^\star)$ and $c_i=\nabla f_i(\tilde{x})-\nabla f_i(x^\star)$ . Then $v=a_i-(c_i-\mathbb{E}_i c_i)$ . Hence

\mathbb{E}_i\lVert v\rVert^2 \le2\mathbb{E}_i\lVert a_i\rVert^2+2\mathbb{E}_i\lVert c_i-\mathbb{E}_i c_i\rVert^2

\le2\mathbb{E}_i\lVert a_i\rVert^2+2\mathbb{E}_i\lVert c_i\rVert^2\le4L[h(x)+h(\tilde{x})],

using the variance identity and Lemma 1.

Theorem 1 (Contraction per epoch). Suppose Assumption 1 holds. If $0 < \eta< 1/(2L)$ and $m$ are chosen so that

\rho:= \frac{1}{\mu\eta m(1-2L\eta)}+\frac{2L\eta}{1-2L\eta}<1, \tag*{(7)}

then after $S$ epochs,

\mathbb{E}h(\tilde{x}_S)\le\rho^S h(\tilde{x}_0). \tag*{(8)}

In particular, $\eta=1/(10L)$ and $m=\lceil50L/\mu\rceil$ ensure $\rho\le1/2$ .

Proof. Condition on the start of an epoch and denote its snapshot by $\tilde{x}$ . All expectations in this paragraph are conditional on that snapshot. Condition further on the history before drawing $i_t$ . Unbiasedness, convexity of $F$ , and Lemma 2 imply

\begin{aligned} \mathbb{E}_{i_t}\left\|x_{t+1}-x_\star\right\|^2 = \left\|x_t-x_\star\right\|^2 - 2\eta\left\langle\nabla F(x_t),x_t-x_\star\right\rangle+\eta^2\mathbb{E}_{i_t}\left\|v_t\right\|^2 \\ &\leq\left\|x_t-x_\star\right\|^2-2\eta(1-2L\eta)h(x_t)+4L\eta^2h(\tilde{x}). \end{aligned}

Take expectations over the inner history and sum for $t=0,\ldots,m-1$ . The squared distances telescope, and the final one is nonnegative:

2\eta(1-2L\eta)\sum_{t=0}^{m-1}\mathbb{E}h(x_t)\leq\left\|\tilde{x}-x_\star\right\|^2+4L\eta^2mh(\tilde{x}).

Strong convexity gives $\left\|\tilde{x}-x_\star\right\|^2\leq2h(\tilde{x})/\mu$ . Divide by $2\eta(1-2L\eta)m$ and use the independent uniform snapshot choice to obtain $\mathbb{E}[h(\tilde{x}_{s+1})\mid\tilde{x}_s]\leq\rho h(\tilde{x}_s)$ . The tower property and induction prove (8). For the stated parameters, $1-2L\eta=4/5$ , and the two terms in (7) are at most $1/4$ and $1/4$ .

Oracle complexity and accuracy. Let $\kappa=L/\mu$ and $\Delta_0=h(\tilde{x}_0)$ . With the parameters in Theorem 1, an objective target $0<\tau<\Delta_0$ is reached after

S=\left\lceil\log_2\frac{\Delta_0}{\tau}\right\rceil\quad\Longrightarrow\quad\mathbb{E}h(\tilde{x}_S)\leq\tau. \tag*{(9)}

The total component-gradient count is at most

N\leq S(n+2\lceil50\kappa\rceil)=O\left((n+\kappa)\left[1+\log\frac{\Delta_0}{\tau}\right]\right). \tag*{(10)}

If $\Delta_0\leq\tau$ , no epochs are needed for this theoretical guarantee. Choosing $S$ in advance uses $\Delta_0$ or an upper bound.

The objective and stationarity criteria can also be related explicitly. Applying smoothness at $x-\nabla F(x)/L$ and using the global lower bound $F_\star$ gives

\left\|\nabla F(x)\right\|^2\leq2Lh(x). \tag*{(11)}

Thus taking $\tau=\varepsilon^2/(2L)$ ensures $\mathbb{E}\left\|\nabla F(\tilde{x}_S)\right\|^2\leq\varepsilon^2$ and, by Cauchy–Schwarz, $\mathbb{E}\left\|\nabla F(\tilde{x}_S)\right\|\leq\varepsilon$ . Here $\tau$ measures objective error, while $\varepsilon$ measures gradient norm; the distinction matters when comparing rates across methods.

Interpretation and scope. The second moment in (6) decreases as both the inner iterate and the snapshot approach the solution. This permits a fixed step size and geometric improvement without assuming that every component gradient vanishes at $x_\star$ . The proof requires convex components, a strongly convex average, and the specified random snapshot rule. It does not establish the same rate for the last inner iterate or a nonconvex objective. Nonconvex SVRG analyses [20, 21] and loopless variants [18, 19] use different arguments. The exact snapshot gradient is also essential to this proof; approximating it introduces another error term.

References

[1]Saeed Ghadimi and Guanghui Lan. Stochastic first- and zeroth-order methods for nonconvex stochastic programming. SIAM Journal on Optimization, 23(4):2341–2368, 2013.arxiv.org/abs/1309.5549
[2]Robert M. Gower, Mark Schmidt, Francis Bach, and Peter Richtárik. Variance-reduced methods for machine learning. Proceedings of the IEEE, 108(11):1968–1983, 2020.arxiv.org/abs/2010.00892
[3]Eduard Gorbunov, Filip Hanzely, and Peter Richtarik. A Unified Theory of SGD: Variance Reduction, Sampling, Quantization and Coordinate Descent. In AISTATS, PMLR 108:680–690, 2020.arxiv.org/abs/1905.11261
[4]Nicolas Le Roux, Mark Schmidt, and Francis Bach. A stochastic gradient method with an exponential convergence rate for finite training sets. In Advances in Neural Information Processing Systems (NIPS), volume 25, 2012.
[5]Shai Shalev-Shwartz and Tong Zhang. Stochastic Dual Coordinate Ascent Methods for Regularized Loss Minimization. Journal of Machine Learning Research, 14(16):567–599, 2013.DOI
[6]Rie Johnson and Tong Zhang. Accelerating stochastic gradient descent using predictive variance reduction. In NeurIPS, volume 26, 2013.
[7]Jakub Konečný and Peter Richtárik. Semi-Stochastic Gradient Descent Methods. arXiv preprint arXiv:1312.1666, 2013.arxiv.org/abs/1312.1666
[8]Aaron Defazio, Francis Bach, and Simon Lacoste-Julien. SAGA: A fast incremental gradient method with support for non-strongly convex composite objectives. In NeurIPS, volume 27, 2014.
[9]Aaron J. Defazio, Tiberio S. Caetano, and Justin Domke. Finito: A Faster, Permutable Incremental Gradient Method for Big Data Problems. arXiv preprint arXiv:1407.2710, 2014.arxiv.org/abs/1407.2710
[10]Lin Xiao and Tong Zhang. A proximal stochastic gradient method with progressive variance reduction. SIAM Journal on Optimization, 24(4):2057–2075, 2014.arxiv.org/abs/1403.4699
[11]Hongzhou Lin, Julien Mairal, and Zaid Harchaoui. A Universal Catalyst for First-Order Optimization. In NeurIPS, volume 28, 2015.
[12]Zeyuan Allen-Zhu. Katyusha: The first direct acceleration of stochastic gradient methods. arXiv preprint arXiv:1603.05953, 2016.
[13]Zeyuan Allen-Zhu and Yang Yuan. Improved SVRG for Non-Strongly-Convex or Sum-of-Non-Convex Objectives. In ICML, PMLR 48:1080–1089, 2016.
[14]Zeyuan Allen-Zhu. Katyusha X: Simple Momentum Method for Stochastic Sum-of-Nonconvex Optimization. In ICML, PMLR 80:179–185, 2018.
[15]Xun Qian, Zheng Qu, and Peter Richtarik. SAGA with Arbitrary Sampling. In ICML, PMLR 97:5190–5199, 2019.arxiv.org/abs/1901.08669
[16]Robert M. Gower, Peter Richtarik, and Francis Bach. Stochastic Quasi-Gradient Methods: Variance Reduction via Jacobian Sketching. arXiv preprint arXiv:1805.02632, 2018.arxiv.org/abs/1805.02632
[17]Fanhua Shang, Yuanyuan Liu, Kaiwen Zhou, James Cheng, Kelvin Kai Wing Ng, and Yuichi Yoshida. Guaranteed Sufficient Decrease for Stochastic Variance Reduced Gradient Optimization. In AISTATS, PMLR 84:1027–1036, 2018.arxiv.org/abs/1802.09933
[18]Dmitry Kovalev, Samuel Horvath, and Peter Richtarik. Don’t Jump Through Hoops and Remove Those Loops: SVRG and Katyusha are Better Without the Outer Loop. arXiv preprint arXiv:1901.08689, 2019.arxiv.org/abs/1901.08689
[19]Xun Qian, Zheng Qu, and Peter Richtarik. L-SVRG and L-Katyusha with Arbitrary Sampling. Journal of Machine Learning Research, 22(112), 2021.
[20]Sashank J. Reddi, Ahmed Hefny, Suvrit Sra, Barnabas Poczos, and Alex Smola. Stochastic variance reduction for nonconvex optimization. In International Conference on Machine Learning (ICML), PMLR 48:314–323, 2016.arxiv.org/abs/1603.06160
[21]Zeyuan Allen-Zhu and Elad Hazan. Variance reduction for faster non-convex optimization. In ICML, PMLR 48:699–707, 2016.
[22]Zeyuan Allen-Zhu. Natasha: Faster Non-Convex Stochastic Optimization via Strongly Non-Convex Parameter. In ICML, PMLR 70:89–97, 2017.
[23]Lam M. Nguyen, Jie Liu, Katya Scheinberg, and Martin Takáč. SARAH: A novel method for machine learning problems using stochastic recursive gradient. In ICML, 2017.arxiv.org/abs/1703.00102
[24]Lam M. Nguyen, Katya Scheinberg, and Martin Takac. Inexact SARAH Algorithm for Stochastic Optimization. arXiv preprint arXiv:1811.10105, 2018.arxiv.org/abs/1811.10105
[25]Lihua Lei, Cheng Ju, Jianbo Chen, and Michael I. Jordan. Non-convex finite-sum optimization via SCSG methods. In NeurIPS, volume 30, 2017.arxiv.org/abs/1706.09156
[26]Cong Fang, Chris Junchi Li, Zhouchen Lin, and Tong Zhang. SPIDER: Near-optimal non-convex optimization via stochastic path-integrated differential estimator. In NeurIPS, volume 31, 2018.arxiv.org/abs/1807.01695
[27]Dongruo Zhou, Pan Xu, and Quanquan Gu. Stochastic nested variance reduction for nonconvex optimization. In NeurIPS, volume 31, 2018.arxiv.org/abs/1806.07811
[28]Zhe Wang, Kaivi Ji, Yi Zhou, Yingbin Liang, and Vahid Tarokh. SpiderBoost and momentum: Faster stochastic variance reduction algorithms. In NeurIPS, volume 32, 2019.arxiv.org/abs/1810.10690
[29]Nhan H. Pham, Lam M. Nguyen, Dzung T. Phan, and Quoc Tran-Dinh. ProxSARAH: An Efficient Algorithmic Framework for Stochastic Composite Nonconvex Optimization. Journal of Machine Learning Research, 21(110):1–48, 2020.arxiv.org/abs/1902.05679
[30]Zhize Li, Slavomir Hanzely, and Peter Richtarik. ZeroSARAH: Efficient Nonconvex Finite-Sum Optimization with Zero Full Gradient Computation. arXiv preprint arXiv:2103.01447, 2021.arxiv.org/abs/2103.01447
[31]Zhize Li, Hongyan Bao, Xiangliang Zhang, and Peter Richtárik. PAGE: A simple and optimal probabilistic gradient estimator for nonconvex optimization. In ICML, 2021.arxiv.org/abs/2008.10898
[32]Samuel Horvath and Peter Richtarik. Nonconvex Variance Reduced Optimization with Arbitrary Sampling. In ICML, PMLR 97:2781–2789, 2019.arxiv.org/abs/1809.04146
[33]Ashok Cutkosky and Francesco Orabona. Momentum-based variance reduction in non-convex SGD. In NeurIPS, volume 32, 2019.arxiv.org/abs/1905.10018
[34]Quoc Tran-Dinh, Nhan H. Pham, Dzung T. Phan, and Lam M. Nguyen. A hybrid stochastic optimization framework for stochastic composite nonconvex optimization. arXiv preprint arXiv:1907.03793, 2019.
[35]Kfir Y. Levy, Ali Kavis, and Volkan Cevher. STORM+: Fully adaptive SGD with recursive momentum for nonconvex optimization. In NeurIPS, volume 34, 2021.
[36]Feihu Huang, Junyi Li, and Heng Huang. SUPER-ADAM: Faster and Universal Framework of Adaptive Gradients. In NeurIPS, volume 34, 2021.arxiv.org/abs/2106.08208
[37]Zijian Liu, Ta Duy Nguyen, Thien Hang Nguyen, Alina Ene, and Huy L. Nguyen. META-STORM: Generalized fully-adaptive variance reduced SGD for unbounded functions. arXiv preprint arXiv:2209.14853, 2022.arxiv.org/abs/2209.14853
[38]Ali Kavis, Stratis Skoulakis, Kimon Antonakopoulos, Leello Tadesse Dadi, and Volkan Cevher. Adaptive Stochastic Variance Reduction for Non-convex Finite-Sum Minimization. In NeurIPS, volume 35, 2022.
[39]Wei Jiang, Sifan Yang, Yibo Wang, and Lijun Zhang. Adaptive variance reduction for stochastic optimization under weaker assumptions. In NeurIPS, volume 37, pages 22047–22080, 2024.arxiv.org/abs/2406.01959
[40]Benjamin Dubois-Taine, Sharan Vaswani, Reza Babanezhad, Mark Schmidt, and Simon Lacoste-Julien. SVRG Meets AdaGrad: Painless Variance Reduction. arXiv preprint arXiv:2102.09645, 2021.
[41]Bingcong Li, Lingda Wang, and Georgios B. Giannakis. Almost Tune-Free Variance Reduction. In ICML, PMLR 119:5969–5978, 2020.arxiv.org/abs/1908.09345
[42]Zijian Liu, Ta Duy Nguyen, Alina Ene, and Huy L. Nguyen. Adaptive Accelerated (Extra-)Gradient Methods with Variance Reduction. In ICML, PMLR 162:13947–13994, 2022.arxiv.org/abs/2201.12302
[43]Ganzhao Yuan. Adaptive Lipschitz-Free Proximal Gradient Methods for Stochastic Composite Nonconvex Optimization. arXiv preprint arXiv:2502.21099v4, 2026.arxiv.org/abs/2502.21099
[44]Zhize Li. SSRGD: Simple Stochastic Recursive Gradient Descent for Escaping Saddle Points. In NeurIPS, volume 32, 2019.arxiv.org/abs/1904.09265
[45]Zeyuan Allen-Zhu. Natasha 2: Faster Non-Convex Optimization Than SGD. In NeurIPS, volume 31, 2018.
[46]Zhe Wang, Yi Zhou, Yingbin Liang, and Guanghui Lan. Stochastic Variance-Reduced Cubic Regularization for Nonconvex Optimization. In AISTATS, PMLR 89:2731–2740, 2019.arxiv.org/abs/1802.07372
[47]Dongruo Zhou, Pan Xu, and Quanquan Gu. Stochastic Variance-Reduced Cubic Regularized Newton Methods. In ICML, PMLR 80:5990–5999, 2018.
[48]Yossi Arjevani, Yair Carmon, John C. Duchi, Dylan J. Foster, Nathan Srebro, and Blake Woodworth. Lower bounds for non-convex stochastic optimization. Mathematical Programming, 199:165–214, 2023.arxiv.org/abs/1912.02365
[49]Mengdi Wang, Ethan X. Fang, and Han Liu. Stochastic compositional gradient descent: Algorithms for minimizing compositions of expected-value functions. arXiv preprint arXiv:1411.3803, 2014.arxiv.org/abs/1411.3803
[50]Mengdi Wang, Ji Liu, and Ethan X. Fang. Accelerating stochastic composition optimization. Journal of Machine Learning Research, 18(105):1–23, 2017.arxiv.org/abs/1607.07329
[51]Saeed Ghadimi, Andrzej Ruszczynski, and Mengdi Wang. A Single Timescale Stochastic Approximation Method for Nested Stochastic Optimization. SIAM Journal on Optimization, 2020.arxiv.org/abs/1812.01094
[52]Tianyi Chen, Yuejiao Sun, and Wotao Yin. Solving Stochastic Compositional Optimization is Nearly as Easy as Solving Stochastic Optimization. arXiv preprint arXiv:2008.10847, 2020.DOI
[53]Xiangru Lian, Mengdi Wang, and Ji Liu. Finite-sum composition optimization via variance reduced gradient descent. In International Conference on Artificial Intelligence and Statistics (AISTATS), PMLR 54:1159–1167, 2017.arxiv.org/abs/1610.04674
[54]Tsung-Yu Hsieh, Yasser El-Manzalawy, Yiwei Sun, and Vasant Honavar. Compositional Stochastic Average Gradient for Machine Learning and Related Applications. arXiv preprint arXiv:1809.01225, 2018.arxiv.org/abs/1809.01225
[55]Junyu Zhang and Lin Xiao. A composite randomized incremental gradient method. In ICML, PMLR 97:7454–7462, 2019.
[56]Wenqing Hu, Chris Junchi Li, Xiangru Lian, Ji Liu, and Huizhuo Yuan. Efficient Smooth Non-Convex Stochastic Compositional Optimization via Stochastic Recursive Gradient Descent. In NeurIPS, volume 32, 2019.
[57]Junyu Zhang and Lin Xiao. Multi-level composite stochastic optimization via nested variance reduction. arXiv preprint arXiv:1908.11468, 2019.arxiv.org/abs/1908.11468
[58]Wei Jiang, Bokun Wang, Yibo Wang, Lijun Zhang, and Tianbao Yang. Optimal algorithms for stochastic multi-level compositional optimization. In ICML, PMLR 162:10195–10216, 2022.arxiv.org/abs/2202.07530
[59]Krishnakumar Balasubramanian, Saeed Ghadimi, and Anthony Nguyen. Stochastic Multi-level Composition Optimization Algorithms with Level-Independent Convergence Rates. arXiv preprint arXiv:2008.10526, 2020.arxiv.org/abs/2008.10526
[60]Wei Jiang, Sifan Yang, Yibo Wang, Tianbao Yang, and Lijun Zhang. Revisiting stochastic multi-level compositional optimization. IEEE Transactions on Pattern Analysis and Machine Intelligence, 47(7):5613–5624, 2025.DOI
[61]Bokun Wang and Tianbao Yang. Finite-Sum Coupled Compositional Stochastic Optimization: Theory and Applications. In ICML, PMLR 162:23292–23317, 2022.arxiv.org/abs/2202.12396
[62]Wei Jiang, Gang Li, Yibo Wang, Lijun Zhang, and Tianbao Yang. Multi-block-single-probe variance reduced estimator for coupled compositional optimization. In NeurIPS, volume 35, pages 32499–32511, 2022.arxiv.org/abs/2207.08540
[63]Quanqi Hu, Dixian Zhu, and Tianbao Yang. Non-Smooth Weakly-Convex Finite-sum Coupled Compositional Optimization. In NeurIPS, volume 36, 2023.arxiv.org/abs/2310.03234
[64]Wei Jiang, Sifan Yang, Yibo Wang, Lijun Zhang, and Zechao Li. Solving finite-sum coupled compositional optimization via multi-block-single-probe estimator. arXiv preprint arXiv:2609.15723, 2026.arxiv.org/abs/2609.15723
[65]Xingyu Chen, Bokun Wang, Ming Yang, Qihang Lin, and Tianbao Yang. Stochastic Momentum Methods for Non-smooth Non-Convex Finite-Sum Coupled Compositional Optimization. In NeurIPS, volume 38, 2025.arxiv.org/abs/2506.02504
[66]Elad Hazan and Haipeng Luo. Variance-Reduced and Projection-Free Stochastic Optimization. In ICML, PMLR 48:1263–1271, 2016.arxiv.org/abs/1602.02101
[67]Tesi Xiao, Krishnakumar Balasubramanian, and Saeed Ghadimi. A Projection-free Algorithm for Constrained Stochastic Multi-level Composition Optimization. In NeurIPS, volume 35, 2022.arxiv.org/abs/2202.04296
[68]Wei Jiang, Sifan Yang, Wenhao Yang, Yibo Wang, Yuanyu Wan, and Lijun Zhang. Projection-free variance reduction methods for stochastic constrained multi-level compositional optimization. In ICML, PMLR 235:21962–21987, 2024.arxiv.org/abs/2406.03787
[69]Hamed Hassani, Amin Karbasi, Aryan Mokhtari, and Zebang Shen. Stochastic Conditional Gradient++. arXiv preprint arXiv:1902.06992, 2019.arxiv.org/abs/1902.06992
[70]Wei Jiang, Sifan Yang, Wenhao Yang, Yibo Wang, Yuanyu Wan, Zechao Li, and Lijun Zhang. Projection-free multi-level algorithms for stochastic constrained compositional optimization. arXiv preprint arXiv:2609.15679, 2026.arxiv.org/abs/2609.15679
[71]Wei Jiang, Jiayu Qin, Lingyu Wu, Changyou Chen, Tianbao Yang, and Lijun Zhang. Learning unnormalized statistical models via compositional optimization. In ICML, PMLR 202:15105–15124, 2023.arxiv.org/abs/2306.07485
[72]Davoud Ataee Tarzanagh, Mingchen Li, Christos Trampoulidis, and Samet Oymak. FedNest: Federated Bilevel, Minimax, and Compositional Optimization. In ICML, PMLR 162:21146–21179, 2022.arxiv.org/abs/2205.02215
[73]Wei Jiang, Jiayu Qin, Lingyu Wu, Changyou Chen, Tianbao Yang, and Lijun Zhang. Optimizing unnormalized statistical models through compositional optimization. IEEE Transactions on Pattern Analysis and Machine Intelligence, 48(2):1949–1960, 2026.DOI
[74]Hongchang Gao, Junyi Li, and Heng Huang. On the Convergence of Local Stochastic Compositional Gradient Descent with Momentum. In ICML, PMLR 162:7017–7035, 2022.
[75]Dan Alistarh, Demjan Grubic, Jerry Li, Ryota Tomioka, and Milan Vojnovic. QSGD: Communication-Efficient SGD via Gradient Quantization and Encoding. In NeurIPS, volume 30, 2017.
[76]Wei Wen, Cong Xu, Feng Yan, Chunpeng Wu, Yandan Wang, Yiran Chen, and Hai Li. TernGrad: Ternary Gradients to Reduce Communication in Distributed Deep Learning. In NeurIPS, volume 30, 2017.arxiv.org/abs/1705.07878
[77]Jeremy Bernstein, Yu-Xiang Wang, Kamyar Azizzadenesheli, and Anima Anandkumar. signSGD: Compressed optimisation for non-convex problems. In ICML, PMLR 80:560–569, 2018.arxiv.org/abs/1802.04434
[78]Jeremy Bernstein, Jiawei Zhao, Kamyar Azizzadenesheli, and Anima Anandkumar. signSGD with majority vote is communication efficient and fault tolerant. In International Conference on Learning Representations (ICLR), 2019.
[79]Sai Praneeth Karimireddy, Quentin Rebjock, Sebastian U. Stich, and Martin Jaggi. Error feedback fixes SignSGD and other gradient compression schemes. In ICML, PMLR 97:3252–3261, 2019.arxiv.org/abs/1901.09847
[80]Wei Jiang, Sifan Yang, Wenhao Yang, and Lijun Zhang. Efficient sign-based optimization: Accelerating convergence via variance reduction. In NeurIPS, volume 37, pages 33891–33932, 2024.arxiv.org/abs/2406.00489
[81]Xiangning Chen, Chen Liang, Da Huang, Esteban Real, Kaiyuan Wang, Hieu Pham, Xuanyi Dong, Thang Luong, Cho-Jui Hsieh, Yifeng Lu, and Quoc V. Le. Symbolic discovery of optimization algorithms. In NeurIPS, volume 36, 2023.arxiv.org/abs/2302.06675
[82]Wei Jiang, Mao Xu, Wenhao Yang, Yibo Wang, Zechao Li, and Lijun Zhang. Convergence analysis of the Lion optimizer in centralized and distributed settings. In ICML, PMLR 306:53308–53333, 2026.arxiv.org/abs/2508.12327
[83]Konstantin Mishchenko, Eduard Gorbunov, Martin Takac, and Peter Richtarik. Distributed Learning with Compressed Gradient Differences. arXiv preprint arXiv:1901.09269, 2019.arxiv.org/abs/1901.09269
[84]Eduard Gorbunov, Konstantin P. Burlachenko, Zhize Li, and Peter Richtarik. MARINA: Faster Non-Convex Distributed Learning with Compression. In ICML, PMLR 139:3788–3798, 2021.arxiv.org/abs/2102.07845
[85]Wei Jiang, Zechao Li, and Lijun Zhang. Revisiting distributed sign-based variance reduction. arXiv preprint arXiv:2609.18656, 2026.arxiv.org/abs/2609.18656
[86]Peter Richtarik, Igor Sokolov, and Ilyas Fatkhullin. EF21: A New, Simpler, Theoretically Better, and Practically Faster Error Feedback. In NeurIPS, volume 34, 2021.arxiv.org/abs/2106.05203
[87]Alexander Tyurin and Peter Richtarik. DASHA: Distributed Nonconvex Optimization with Communication Compression, Optimal Oracle Complexity, and No Client Synchronization. arXiv preprint arXiv:2202.01268, 2022.arxiv.org/abs/2202.01268
[88]Sai Praneeth Karimireddy, Satyen Kale, Mehryar Mohri, Shashank Reddi, Sebastian Stich, and Ananda Theertha Suresh. SCAFFOLD: Stochastic Controlled Averaging for Federated Learning. In ICML, PMLR 119:5132–5143, 2020.arxiv.org/abs/1910.06378
[89]Haoyu Zhao, Zhize Li, and Peter Richtarik. FedPAGE: A Fast Local Stochastic Gradient Method for Communication-Efficient Federated Learning. arXiv preprint arXiv:2108.04755, 2021.arxiv.org/abs/2108.04755
[90]Ran Xin, Usman A. Khan, and Soummya Kar. A Hybrid Variance-Reduced Method for Decentralized Stochastic Non-Convex Optimization. In ICML, PMLR 139:11459–11469, 2021.arxiv.org/abs/2102.06752
[91]Konstantin Mishchenko, Grigory Malinovsky, Sebastian Stich, and Peter Richtarik. ProxSkip: Yes! Local Gradient Steps Provably Lead to Communication Acceleration! Finally!. In ICML, PMLR 162:15750–15769, 2022.arxiv.org/abs/2202.09357
[92]P. Balamurugan and Francis Bach. Stochastic variance reduction methods for saddle-point problems. In NeurIPS, volume 29, 2016.
[93]Yair Carmon, Yujia Jin, Aaron Sidford, and Kevin Tian. Variance Reduction for Matrix Games. In NeurIPS, volume 32, 2019.arxiv.org/abs/1907.02056
[94]Tatjana Chavdarova, Gauthier Gidel, Francois Fleuret, and Simon Lacoste-Julien. Reducing Noise in GAN Training with Variance Reduced Extragradient. In NeurIPS, volume 32, 2019.arxiv.org/abs/1904.08598
[95]Junchi Yang, Siqi Zhang, Negar Kiyavash, and Niao He. A Catalyst Framework for Minimax Optimization. In NeurIPS, volume 33, 2020.
[96]Luo Luo, Haishan Ye, Zhichao Huang, and Tong Zhang. Stochastic recursive gradient descent ascent for stochastic nonconvex-strongly-concave minimax problems. In NeurIPS, volume 33, 2020.arxiv.org/abs/2001.03724
[97]Quoc Tran-Dinh, Deyi Liu, and Lam M. Nguyen. Hybrid Variance-Reduced SGD Algorithms for Minimax Problems with Nonconvex-Linear Function. In NeurIPS, volume 33, 2020.
[98]Feihu Huang, Xidong Wu, and Zhengmian Hu. AdaGDA: Faster adaptive gradient descent ascent methods for minimax optimization. In AISTATS, PMLR 206:2365–2389, 2023.
[99]Lesi Chen, Haishan Ye, and Luo Luo. An Efficient Stochastic Algorithm for Decentralized Nonconvex-Strongly-Concave Minimax Optimization. In AISTATS, PMLR 238:1990–1998, 2024.
[100]Ahmet Alacaoglu and Yura Malitsky. Stochastic variance reduction for variational inequality methods. In Conference on Learning Theory (COLT), PMLR 178:778–816, 2022.arxiv.org/abs/2102.08352

Variance Reduction Note 4: The Convergence of SVRG

Abstract

A snapshot as a control variate

Assumptions and the epoch algorithm

A short linear-convergence proof

Recommended reading

References

Publication

Taxonomy

Authors

AI contributions

More in Mathematics

More in Mathematics