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 for finite sums and 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
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 . 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 is bounded below by a finite number . For some and all ,
For online problems, additionally assume, for some ,
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 is -smooth. For a finite sum , use uniform indices and . Exact full-gradient refreshes then eliminate the need for (3).
Choose a fixed step size , a probability , and integer batch sizes . Initialize with a refresh at a deterministic . For , compute
then draw a fresh independent Bernoulli variable with , and set
Both evaluations in each difference use the same sample. For finite sums, replace every refresh, including initialization, by the full gradient; set for cost accounting and sample inner indices independently with replacement. Return for an independent uniform . The expected cost of this implementation is
This count includes the final estimator update, which can be omitted without changing the returned point or the guarantee.
A short convergence proof
Write , , , and . Let online and for exact finite-sum refreshes. In both settings .
Lemma 1 (Tracking error). Under Assumption 1,
Proof. Condition on all randomness used to construct ; then is also fixed. A refresh has conditional mean-square error at most . In the recursive branch, write , where
The increment has conditional mean zero. Independence within the batch, the variance identity, and (2) bound its conditional second moment by . Its cross term with vanishes. Average over the fresh Bernoulli choice and the past, and use (4). ◻
Lemma 2 (Descent). For the update (4),
Proof. Apply -smoothness to and substitute
Taking expectations gives (8); conditional unbiasedness of is not required. ◻
Theorem 1 (Expected stationarity). Let and . If
then PAGE satisfies
Proof. Use the nonnegative Lyapunov quantity . Multiply (7) by and add (8). The terms cancel, giving
The bracket is nonnegative: with , condition (9) gives
Sum over and use and . Division by yields (10), because is independent and uniform.
Finite-sum complexity. Take exact refreshes, , , , and equality in (9). Then , so , and . For a target , choosing gives . Moreover, (6) gives
The cost from rounding is absorbed by .
Online complexity. Choose
and equality in (9). Again , while . With
the first two terms in (10) sum to at most . Thus . Since and ,
For fixed problem parameters this is as . In either setting, Cauchy–Schwarz also gives .
Interpretation and scope. The term shows why initialization belongs in the proof. A sampled refresh leaves a noise floor , which must decrease with the requested accuracy. The probability and balance the expected work while permitting a step size of order . Cost bounds are in expectation over the random refreshes. The chosen horizons use 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]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 (NeurIPS), 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.
- [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 Richtarik. 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, 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]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 Thrampoulidis, 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 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]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]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