betaFeedback

WorksMathematics

Variance Reduction Note 3: The Convergence of PAGE

Abstract

The probabilistic gradient estimator (PAGE) alternates randomly between an accurate gradient refresh and a cheap recursive correction. This third expository note on recursive variance reduction explains the algorithm and gives a self-contained convergence proof for smooth nonconvex optimization. A Lyapunov function combines objective decrease with estimation error, turning the refresh probability into an explicit contraction parameter. The resulting expected oracle complexity is O(n+n ε−2)O(n+\sqrt n\,ε^{-2}) for finite sums and O(ε−3)O(ε^{-3}) for online problems, with the other problem parameters fixed. Initialization, refreshes, and both evaluations in each gradient difference are counted. The presentation is pedagogical and makes no claim of a new algorithm or convergence rate.

Random refreshes and recursive corrections

Consider the smooth, possibly nonconvex objective

min⁡x∈RdF(x):=Eξ[f(x;ξ)],g(x;ξ):=∇f(x;ξ).(1)\min_{x\in\mathbb{R}^{d}} F(x) := \mathbb{E}_{\xi}[f(x;\xi)], \qquad g(x;\xi) := \nabla f(x;\xi). \tag*{(1)}

Recursive estimators such as SARAH and SPIDER [23, 26] use shared-sample differences to track changes in the gradient. A refresh prevents the accumulated tracking error from becoming too large. PAGE, introduced by Li et al. [31], performs this refresh with a specified probability at every iteration. The resulting random refresh times remove the need for a prescribed epoch length.

The method has two computational scales: an expensive refresh batch and a smaller batch of gradient differences. The refresh probability balances their expected costs. Its mathematical role is equally direct: refreshing replaces the old estimation error, so that error survives with probability 1−p1-p. This yields a short Lyapunov proof with a constant step size. Related probabilistic designs include loopless SVRG [18]; STORM instead incorporates a damped recursive correction at every step [33]. For a general introduction to variance reduction, see [2].

The oracle and the PAGE update

Assumption 1. The differentiable function FF is bounded below by a finite number F⋆F_{\star}. For some L>0L>0 and all x,y∈Rdx,y\in\mathbb{R}^{d},

E[g(x;ξ)]=∇F(x),E∥g(x;ξ)−g(y;ξ)∥2≤L2∥x−y∥2.(2)\mathbb{E}[g(x;\xi)] = \nabla F(x), \qquad\mathbb{E}\left\|g(x;\xi)-g(y;\xi)\right\|^{2} \le L^{2}\left\|x-y\right\|^{2}. \tag*{(2)}

For online problems, additionally assume, for some σ≥0\sigma\ge0,

E∥g(x;ξ)−∇F(x)∥2≤σ2.(3)\mathbb{E}\left\|g(x;\xi)-\nabla F(x)\right\|^{2} \le\sigma^{2}. \tag*{(3)}

Fresh samples are independent of the past and of one another. A sampled function can be evaluated at two specified points. Norms are Euclidean.

Jensen’s inequality implies that FF is LL-smooth. For a finite sum F(x)=n−1∑i=1nfi(x)F(x)=n^{-1}\sum_{i=1}^{n}f_i(x), use uniform indices and g(x;i)=∇fi(x)g(x;i)=\nabla f_i(x). Exact full-gradient refreshes then eliminate the need for (3).

Choose a fixed step size η>0\eta>0, a probability p∈(0,1]p\in(0,1], and integer batch sizes B,b≥1B,b\ge1. Initialize v0v_0 with a refresh at a deterministic x0x_0. For t=0,…,T−1t=0,\ldots,T-1, compute

xt+1=xt−ηvt,(4)x_{t+1}=x_t-\eta v_t, \tag*{(4)}

then draw a fresh independent Bernoulli variable Ct+1C_{t+1} with Pr⁡(Ct+1=1)=p\Pr(C_{t+1}=1)=p, and set

vt+1={1B∑i=1Bg(xt+1;ζt+1,i),Ct+1=1,vt+1b∑i=1b[g(xt+1;ξt+1,i)−g(xt;ξt+1,i)],Ct+1=0.(5)v_{t+1}= \begin{cases} \frac{1}{B}\sum_{i=1}^{B}g(x_{t+1};\zeta_{t+1,i}), & C_{t+1}=1,\\ v_t+\frac{1}{b}\sum_{i=1}^{b}\left[g(x_{t+1};\xi_{t+1,i})-g(x_t;\xi_{t+1,i})\right], & C_{t+1}=0. \end{cases} \tag*{(5)}

Both evaluations in each difference use the same sample. For finite sums, replace every refresh, including initialization, by the full gradient; set B=nB=n for cost accounting and sample inner indices independently with replacement. Return xRx_R for an independent uniform R∈{0,…,T−1}R\in\{0,\ldots,T-1\}. The expected cost of this implementation is

EN=B+T[pB+2(1−p)b].(6)\mathbb{E}N=B+T[pB+2(1-p)b]. \tag*{(6)}

This count includes the final estimator update, which can be omitted without changing the returned point or the guarantee.

A short convergence proof

Write et=vt−∇F(xt)e_t=v_t-\nabla F(x_t), Qt=E∥et∥2Q_t=\mathbb{E}\lVert e_t\rVert^2, Dt=E∥vt∥2D_t=\mathbb{E}\lVert v_t\rVert^2, and Gt=E∥∇F(xt)∥2G_t=\mathbb{E}\lVert\nabla F(x_t)\rVert^2. Let ν2=σ2/B\nu^2=\sigma^2/B online and ν2=0\nu^2=0 for exact finite-sum refreshes. In both settings Q0≤ν2Q_0\le\nu^2.

Lemma 1 (Tracking error). Under Assumption 1,

Qt+1≤(1−p)Qt+(1−p)L2η2bDt+pν2.(7)Q_{t+1}\le(1-p)Q_t+\frac{(1-p)L^2\eta^2}{b}D_t+p\nu^2. \tag*{(7)}

Proof. Condition on all randomness used to construct xt,vtx_t,v_t; then xt+1x_{t+1} is also fixed. A refresh has conditional mean-square error at most ν2\nu^2. In the recursive branch, write et+1=et+Zt+1e_{t+1}=e_t+Z_{t+1}, where

Zt+1=1b∑i=1b[g(xt+1;ξi)−g(xt;ξi)]−[∇F(xt+1)−∇F(xt)].Z_{t+1}=\frac{1}{b}\sum_{i=1}^{b}\left[g(x_{t+1};\xi_i)-g(x_t;\xi_i)\right]-\left[\nabla F(x_{t+1})-\nabla F(x_t)\right].

The increment has conditional mean zero. Independence within the batch, the variance identity, and (2) bound its conditional second moment by L2∥xt+1−xt∥2/bL^2\lVert x_{t+1}-x_t\rVert^2/b. Its cross term with ete_t vanishes. Average over the fresh Bernoulli choice and the past, and use (4). ◻

Lemma 2 (Descent). For the update (4),

EF(xt+1)≤EF(xt)−η2Gt−η2(1−Lη)Dt+η2Qt.(8)\mathbb{E}F(x_{t+1})\le\mathbb{E}F(x_t)-\frac{\eta}{2}G_t-\frac{\eta}{2}(1-L\eta)D_t+\frac{\eta}{2}Q_t. \tag*{(8)}

Proof. Apply LL-smoothness to xt+1=xt−ηvtx_{t+1}=x_t-\eta v_t and substitute

2⟨∇F(xt),vt⟩=∥∇F(xt)∥2+∥vt∥2−∥et∥2.2\langle\nabla F(x_t),v_t\rangle=\lVert\nabla F(x_t)\rVert^2+\lVert v_t\rVert^2-\lVert e_t\rVert^2.

Taking expectations gives (8); conditional unbiasedness of vtv_t is not required. ◻

Theorem 1 (Expected stationarity). Let Δ=F(x0)−F⋆\Delta= F(x_0) - F_\star and c=(1−p)/(pb)c = (1-p)/(pb). If

0<η≤1L(1+c).(9)0 < \eta\le\frac{1}{L(1+\sqrt{c})}. \tag*{(9)}

then PAGE satisfies

E∥∇F(xR)∥2≤2ΔηT+Q0pT+ν2≤2ΔηT+ν2pT+ν2.(10)\mathbb{E}\left\|\nabla F(x_R)\right\|^2 \le\frac{2\Delta}{\eta T} + \frac{Q_0}{pT} + \nu^2 \le\frac{2\Delta}{\eta T} + \frac{\nu^2}{pT} + \nu^2. \tag*{(10)}

Proof. Use the nonnegative Lyapunov quantity Φt=E[F(xt)−F⋆]+ηQt/(2p)\Phi_t = \mathbb{E}[F(x_t) - F_\star] + \eta Q_t/(2p). Multiply (7) by η/(2p)\eta/(2p) and add (8). The QtQ_t terms cancel, giving

Φt+1−Φt≤−η2Gt−η2[1−Lη−cL2η2]Dt+η2ν2.\Phi_{t+1} - \Phi_t \le-\frac{\eta}{2}G_t - \frac{\eta}{2}[1-L\eta-cL^2\eta^2]D_t + \frac{\eta}{2}\nu^2.

The bracket is nonnegative: with r=cr=\sqrt{c}, condition (9) gives

Lη+cL2η2≤11+r+r2(1+r)2≤1.L\eta+cL^2\eta^2 \le\frac{1}{1+r}+\frac{r^2}{(1+r)^2}\le1.

Sum over t=0,…,T−1t=0,\ldots,T-1 and use ΦT≥0\Phi_T\ge0 and Φ0=Δ+ηQ0/(2p)\Phi_0=\Delta+\eta Q_0/(2p). Division by ηT/2\eta T/2 yields (10), because RR is independent and uniform. □\square

Finite-sum complexity. Take exact refreshes, B=nB=n, b=⌈n⌉b=\lceil\sqrt{n}\rceil, p=b/(n+b)p=b/(n+b), and equality in (9). Then c=n/b2≤1c=n/b^2\le1, so η≥1/(2L)\eta\ge1/(2L), and Q0=ν2=0Q_0=\nu^2=0. For a target ε>0\varepsilon>0, choosing T=max⁡{1,⌈4LΔ/ε2⌉}T=\max\{1,\lceil4L\Delta/\varepsilon^2\rceil\} gives E∥∇F(xR)∥2≤ε2\mathbb{E}\left\|\nabla F(x_R)\right\|^2\le\varepsilon^2. Moreover, (6) gives

EN=n+3nbn+bT≤n+3bT=O(n+nLΔε2).(11)\mathbb{E}N=n+\frac{3nb}{n+b}T\le n+3bT=O\left(n+\frac{\sqrt{n}L\Delta}{\varepsilon^2}\right). \tag*{(11)}

The O(n)O(\sqrt{n}) cost from rounding TT is absorbed by nn.

Online complexity. Choose

B=max⁡{1,⌈2σ2/ε2⌉},b=⌈B⌉,p=bB+b.(12)B=\max\{1,\lceil2\sigma^2/\varepsilon^2\rceil\},\qquad b=\lceil\sqrt{B}\rceil,\qquad p=\frac{b}{B+b}. \tag*{(12)}

and equality in (9). Again c=B/b2≤1c=B/b^2\le1, while ν2≤ε2/2\nu^2\le\varepsilon^2/2. With

T=⌈4Δηε2+1p⌉,(13)T=\left\lceil\frac{4\Delta}{\eta\varepsilon^2}+\frac{1}{p}\right\rceil, \tag*{(13)}

the first two terms in (10) sum to at most ε2/2\varepsilon^2/2. Thus E∥∇F(xR)∥2≤ε2\mathbb{E}\left\|\nabla F(x_R)\right\|^2\le\varepsilon^2. Since b/p=B+bb/p=B+b and η−1≤2L\eta^{-1}\le2L,

EN≤B+3bT=O(B+BLΔε2)=O(1+σ2ε2+(1+σε)LΔε2).(14)\begin{aligned} \mathbb{E}N\le B+3bT=O\left(B+\frac{\sqrt{B}L\Delta}{\varepsilon^2}\right) \\ &=O\left(1+\frac{\sigma^2}{\varepsilon^2}+\left(1+\frac{\sigma}{\varepsilon}\right)\frac{L\Delta}{\varepsilon^2}\right). \tag*{(14)} \end{aligned}

For fixed problem parameters this is O(ε−3)O(\varepsilon^{-3}) as ε↓0\varepsilon\downarrow0. In either setting, Cauchy–Schwarz also gives E∥∇F(xR)∥≤ε\mathbb{E}\|\nabla F(x_R)\|\le\varepsilon.

Interpretation and scope. The term Q0/(pT)Q_0/(pT) shows why initialization belongs in the proof. A sampled refresh leaves a noise floor ν2\nu^2, which must decrease with the requested accuracy. The probability p=b/(B+b)p=b/(B+b) and b≲Bb\lesssim\sqrt{B} balance the expected work while permitting a step size of order 1/L1/L. Cost bounds are in expectation over the random refreshes. The chosen horizons use Δ\Delta or an upper bound on it; online batch selection also uses a variance bound. The theorem concerns a random iterate and first-order stationarity. Linear rates under a Polyak–Łojasiewicz condition need an additional assumption and are treated in the original PAGE paper [31].

Recommended reading

Variance-reduction methods. Basic guarantees [1, 2, 3]; gradient memories and control variates [4, 5, 6, 7, 8, 9, 10]; sampling and acceleration [11, 12, 13, 14, 15, 16, 17, 18, 19]; nonconvex and recursive estimators [20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32]; momentum and adaptive schedules [33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43]; second-order extensions [44, 45, 46, 47]; lower bounds [48].

Compositional optimization. Two-level approximation [49, 50, 51, 52]; finite-sum and recursive estimators [53, 54, 55, 56]; multilevel tracking [57, 58, 59, 60]; coupled and partially observed blocks [61, 62, 63, 64, 65]; projection-free methods [66, 67, 68, 69, 70]; statistical-model applications and federated extensions [71, 72, 73, 74].

Sign-based optimization. Quantization, signSGD, majority voting, and error feedback [75, 76, 77, 78, 79]; variance-reduced sign updates and Lion [80, 81, 82]; compressed gradient tracking [83, 84, 85, 86, 87]. Related distributed control-variate methods include SCAFFOLD, FedPAGE, decentralized hybrid estimators, and ProxSkip [88, 89, 90, 91].

Minimax optimization. Finite-sum saddle-point methods, matrix games, and variance-reduced extragradient [92, 93, 94, 95]; recursive, hybrid, adaptive, and decentralized nonconvex minimax methods [96, 97, 98, 99]; a variational-inequality treatment [100].

References

  1. [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. [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. [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. [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 (NeurIPS), volume 25, 2012.
  5. [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.
  6. [6]Rie Johnson and Tong Zhang. Accelerating stochastic gradient descent using predictive variance reduction. In NeurIPS, volume 26, 2013.
  7. [7]Jakub Konečný and Peter Richtarik. Semi-Stochastic Gradient Descent Methods. arXiv preprint arXiv:1312.1666, 2013.arxiv.org/abs/1312.1666
  8. [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. [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. [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. [11]Hongzhou Lin, Julien Mairal, and Zaid Harchaoui. A Universal Catalyst for First-Order Optimization. In NeurIPS, volume 28, 2015.
  12. [12]Zeyuan Allen-Zhu. Katyusha: The first direct acceleration of stochastic gradient methods. arXiv preprint arXiv:1603.05953, 2016.
  13. [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. [14]Zeyuan Allen-Zhu. Katyusha X: Simple Momentum Method for Stochastic Sum-of-Nonconvex Optimization. In ICML, PMLR 80:179–185, 2018.
  15. [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. [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. [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. [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. [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. [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. [21]Zeyuan Allen-Zhu and Elad Hazan. Variance reduction for faster non-convex optimization. In ICML, PMLR 48:699–707, 2016.
  22. [22]Zeyuan Allen-Zhu. Natasha: Faster Non-Convex Stochastic Optimization via Strongly Non-Convex Parameter. In ICML, PMLR 70:89–97, 2017.
  23. [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. [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. [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. [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. [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. [28]Zhe Wang, Kaiyi 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. [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. [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. [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. [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. [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. [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. [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. [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. [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. [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. [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. [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. [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. [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. [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. [44]Zhize Li. SSRGD: Simple Stochastic Recursive Gradient Descent for Escaping Saddle Points. In NeurIPS, volume 32, 2019.arxiv.org/abs/1904.09265
  45. [45]Zeyuan Allen-Zhu. Natasha 2: Faster Non-Convex Optimization Than SGD. In NeurIPS, volume 31, 2018.
  46. [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. [47]Dongruo Zhou, Pan Xu, and Quanquan Gu. Stochastic Variance-Reduced Cubic Regularized Newton Methods. In ICML, PMLR 80:5990–5999, 2018.
  48. [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. [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. [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. [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. [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. [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. [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. [55]Junyu Zhang and Lin Xiao. A composite randomized incremental gradient method. In ICML, PMLR 97:7454–7462, 2019.
  56. [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. [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. [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. [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. [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. [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. [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. [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. [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. [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. [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. [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. [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. [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. [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. [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. [72]Davoud Ataee Tarzanagh, Mingchen Li, Christos Thrampoulidis, and Samet Oymak. FedNest: Federated Bilevel, Minimax, and Compositional Optimization. In ICML, PMLR 162:21146–21179, 2022.arxiv.org/abs/2205.02215
  73. [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. [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. [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. [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. [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. [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. [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. [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. [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. [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. [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. [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. [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. [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. [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. [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. [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. [90]Ran Xin, Usman A. Khan, and Soummyа 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. [91]Konstantin Mishchenko, Grigory Malinovsky, Sebastian Stich, and Peter Richtarik. ProxSkip: Yes! Local Gradient Steps Probably Lead to Communication Acceleration! Finally!. In ICML, PMLR 162:15750–15769, 2022.arxiv.org/abs/2202.09357
  92. [92]P. Balamurugan and Francis Bach. Stochastic variance reduction methods for saddle-point problems. In NeurIPS, volume 29, 2016.
  93. [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. [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. [95]Junchi Yang, Siqi Zhang, Negar Kiyavash, and Niao He. A Catalyst Framework for Minimax Optimization. In NeurIPS, volume 33, 2020.
  96. [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. [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. [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. [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. [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

Paper details

vlnc:W_s2vdu5dk
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 0

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Mathematics

Not recorded for this paper

View statement
Looking for related papers…
Contents