Variance Reduction Methods Do Not Need to Compute Full Gradients: Improved Efficiency Through Shuffling

Daniil Medyakov, Gleb Molodtsov, Savelii Chezhegov, Alexey Rebrikov, Aleksandr Beznosikov
Proceedings of The 29th International Conference on Artificial Intelligence and Statistics, PMLR 300:244-252, 2026.

Abstract

Stochastic optimization algorithms are widely used for machine learning with large-scale data. However, their convergence often suffers from non-vanishing variance. Variance Reduction (VR) methods, such as SVRG and SARAH, address this issue but introduce a bottleneck by requiring periodic full gradient computations. In this paper, we explore popular VR techniques and propose an approach that eliminates the necessity for expensive full gradient calculations. To avoid these computations and make our approach memory-efficient, we employ two key techniques: the shuffling heuristic and the concept of SAG/SAGA methods. For non-convex objectives, our convergence rates match those of standard shuffling methods, while under strong convexity, they demonstrate an improvement. We empirically validate the efficiency of our approach and demonstrate its scalability on large-scale machine learning tasks including image classification problem on CIFAR-10 and CIFAR-100 datasets.

Cite this Paper

BibTeX
@InProceedings{pmlr-v300-medyakov26a, title = { Variance Reduction Methods Do Not Need to Compute Full Gradients: Improved Efficiency Through Shuffling }, author = {Medyakov, Daniil and Molodtsov, Gleb and Chezhegov, Savelii and Rebrikov, Alexey and Beznosikov, Aleksandr}, booktitle = {Proceedings of The 29th International Conference on Artificial Intelligence and Statistics}, pages = {244--252}, year = {2026}, editor = {Khan, Emtiyaz and Li, Yingzhen and Solin, Arno and Ramdas, Aaditya}, volume = {300}, series = {Proceedings of Machine Learning Research}, month = {02--05 May}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/v300/main/assets/medyakov26a/medyakov26a.pdf}, url = {https://proceedings.mlr.press/v300/medyakov26a.html}, abstract = { Stochastic optimization algorithms are widely used for machine learning with large-scale data. However, their convergence often suffers from non-vanishing variance. Variance Reduction (VR) methods, such as SVRG and SARAH, address this issue but introduce a bottleneck by requiring periodic full gradient computations. In this paper, we explore popular VR techniques and propose an approach that eliminates the necessity for expensive full gradient calculations. To avoid these computations and make our approach memory-efficient, we employ two key techniques: the shuffling heuristic and the concept of SAG/SAGA methods. For non-convex objectives, our convergence rates match those of standard shuffling methods, while under strong convexity, they demonstrate an improvement. We empirically validate the efficiency of our approach and demonstrate its scalability on large-scale machine learning tasks including image classification problem on CIFAR-10 and CIFAR-100 datasets. } }
Endnote
%0 Conference Paper %T Variance Reduction Methods Do Not Need to Compute Full Gradients: Improved Efficiency Through Shuffling %A Daniil Medyakov %A Gleb Molodtsov %A Savelii Chezhegov %A Alexey Rebrikov %A Aleksandr Beznosikov %B Proceedings of The 29th International Conference on Artificial Intelligence and Statistics %C Proceedings of Machine Learning Research %D 2026 %E Emtiyaz Khan %E Yingzhen Li %E Arno Solin %E Aaditya Ramdas %F pmlr-v300-medyakov26a %I PMLR %P 244--252 %U https://proceedings.mlr.press/v300/medyakov26a.html %V 300 %X Stochastic optimization algorithms are widely used for machine learning with large-scale data. However, their convergence often suffers from non-vanishing variance. Variance Reduction (VR) methods, such as SVRG and SARAH, address this issue but introduce a bottleneck by requiring periodic full gradient computations. In this paper, we explore popular VR techniques and propose an approach that eliminates the necessity for expensive full gradient calculations. To avoid these computations and make our approach memory-efficient, we employ two key techniques: the shuffling heuristic and the concept of SAG/SAGA methods. For non-convex objectives, our convergence rates match those of standard shuffling methods, while under strong convexity, they demonstrate an improvement. We empirically validate the efficiency of our approach and demonstrate its scalability on large-scale machine learning tasks including image classification problem on CIFAR-10 and CIFAR-100 datasets.
APA
Medyakov, D., Molodtsov, G., Chezhegov, S., Rebrikov, A. & Beznosikov, A.. (2026). Variance Reduction Methods Do Not Need to Compute Full Gradients: Improved Efficiency Through Shuffling . Proceedings of The 29th International Conference on Artificial Intelligence and Statistics, in Proceedings of Machine Learning Research 300:244-252 Available from https://proceedings.mlr.press/v300/medyakov26a.html.

Related Material