Variance Reduction Methods Do Not Need to Compute Full Gradients: Improved Efficiency through Shuffling
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , , , , |
|---|---|
| Format: | Preprint |
| Publié: |
2025
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866909985177337856 |
|---|---|
| author | Medyakov, Daniil Molodtsov, Gleb Chezhegov, Savelii Rebrikov, Alexey Beznosikov, Aleksandr |
| author_facet | Medyakov, Daniil Molodtsov, Gleb Chezhegov, Savelii Rebrikov, Alexey Beznosikov, Aleksandr |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2502_14648 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Variance Reduction Methods Do Not Need to Compute Full Gradients: Improved Efficiency through Shuffling Medyakov, Daniil Molodtsov, Gleb Chezhegov, Savelii Rebrikov, Alexey Beznosikov, Aleksandr Machine Learning Optimization and Control 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. |
| title | Variance Reduction Methods Do Not Need to Compute Full Gradients: Improved Efficiency through Shuffling |
| topic | Machine Learning Optimization and Control |
| url | https://arxiv.org/abs/2502.14648 |