# Nesterov Accelerated Shuffling Gradient Method for Convex Optimization

arXiv: https://arxiv.org/abs/2202.03525 · HTML: https://mlsanity.com/paper/2202.03525/

## Key facts

- Cited by 10 papers in the map (data through 14 Oct 2026).
- Builds on 24 of its 57 references that are in the map.
- First posted on arXiv 7 Feb 2022.

## Builds on (most cited first, 24 of 24)

- [Adam: A Method for Stochastic Optimization](https://mlsanity.com/paper/1412.6980/) (2014)
- [PyTorch: An Imperative Style, High-Performance Deep Learning Library](https://mlsanity.com/paper/1912.01703/) (2019)
- [Fashion-MNIST: a Novel Image Dataset for Benchmarking Machine Learning Algorithms](https://mlsanity.com/paper/1708.07747/) (2017)
- [Optimization Methods for Large-Scale Machine Learning](https://mlsanity.com/paper/1606.04838/) (2016)
- [Stochastic First- and Zeroth-order Methods for Nonconvex Stochastic Programming](https://mlsanity.com/paper/1309.5549/) (2013)
- [SAGA: A Fast Incremental Gradient Method With Support for Non-Strongly Convex Composite Objectives](https://mlsanity.com/paper/1407.0202/) (2014)
- [SARAH: A Novel Method for Machine Learning Problems Using Stochastic Recursive Gradient](https://mlsanity.com/paper/1703.00102/) (2017)
- [Fast and Faster Convergence of SGD for Over-Parameterized Models and an Accelerated Perceptron](https://mlsanity.com/paper/1810.07288/) (2018)
- [Random Reshuffling: Simple Analysis with Vast Improvements](https://mlsanity.com/paper/2006.05988/) (2020)
- [Analysis and Design of Optimization Algorithms via Integral Quadratic Constraints](https://mlsanity.com/paper/1408.3595/) (2014)
- [SGD and Hogwild! Convergence Without the Bounded Gradients Assumption](https://mlsanity.com/paper/1802.03801/) (2018)
- [Why Random Reshuffling Beats Stochastic Gradient Descent](https://mlsanity.com/paper/1510.08560/) (2015)
- [Random Shuffling Beats SGD after Finite Epochs](https://mlsanity.com/paper/1806.10077/) (2018)
- [How Good is SGD with Random Shuffling?](https://mlsanity.com/paper/1908.00045/) (2019)
- [SGD without Replacement: Sharper Rates for General Smooth Convex Functions](https://mlsanity.com/paper/1903.01463/) (2019)
- [A Unified Convergence Analysis for Shuffling-Type Gradient Methods](https://mlsanity.com/paper/2002.08246/) (2020)
- [SGD with shuffling: optimal rates without component convexity and large epoch requirements](https://mlsanity.com/paper/2006.06946/) (2020)
- [Closing the convergence gap of SGD without replacement](https://mlsanity.com/paper/2002.10400/) (2020)
- [Fast Convergence of Stochastic Gradient Descent under a Strong Growth Condition](https://mlsanity.com/paper/1308.6370/) (2013)
- [Proximal and Federated Random Reshuffling](https://mlsanity.com/paper/2102.06704/) (2021)
- [New Convergence Aspects of Stochastic Gradient Algorithms](https://mlsanity.com/paper/1811.12403/) (2018)
- [On the Influence of Momentum Acceleration on Online Learning](https://mlsanity.com/paper/1603.04136/) (2016)
- [SMG: A Shuffling Gradient-Based Method with Momentum](https://mlsanity.com/paper/2011.11884/) (2020)
- [Accelerating SGD with momentum for over-parameterized learning](https://mlsanity.com/paper/1810.13395/) (2018)

## Built on by (most cited first, 10 of 10)

- [Tighter Lower Bounds for Shuffling SGD: Random Permutations and Beyond](https://mlsanity.com/paper/2303.07160/) (2023)
- [Last Iterate Convergence of Incremental Methods and Applications in Continual Learning](https://mlsanity.com/paper/2403.06873/) (2024)
- [Empirical Risk Minimization with Shuffled SGD: A Primal-Dual Perspective and Improved Bounds](https://mlsanity.com/paper/2306.12498/) (2023)
- [High Probability Guarantees for Random Reshuffling](https://mlsanity.com/paper/2311.11841/) (2023)
- [On the Convergence to a Global Solution of Shuffling-Type Gradient Algorithms](https://mlsanity.com/paper/2206.05869/) (2022)
- [Learning to Shuffle: Block Reshuffling and Reversal Schemes for Stochastic Optimization](https://mlsanity.com/paper/2604.00260/) (2026)
- [Shuffling Momentum Gradient Algorithm for Convex Optimization](https://mlsanity.com/paper/2403.03180/) (2024)
- [Accelerated Gradient Methods with Biased Gradient Estimates: Risk Sensitivity, High-Probability Guarantees, and Large Deviation Bounds](https://mlsanity.com/paper/2509.13628/) (2025)
- [Adaptive Gradient Regularization: A Faster and Generalizable Optimization Technique for Deep Neural Networks](https://mlsanity.com/paper/2407.16944/) (2024)
- [Adjusted Shuffling SARAH: Advancing Complexity Analysis via Dynamic Gradient Weighting](https://mlsanity.com/paper/2506.12444/) (2025)

## Abstract (arXiv)

In this paper, we propose Nesterov Accelerated Shuffling Gradient (NASG), a new algorithm for the convex finite-sum minimization problems. Our method integrates the traditional Nesterov's acceleration momentum with different shuffling sampling schemes. We show that our algorithm has an improved rate of O(1/T) using unified shuffling schemes, where T is the number of epochs. This rate is better than that of any other shuffling gradient methods in convex regime. Our convergence analysis does not require an assumption on bounded domain or a bounded gradient condition. For randomized shuffling schemes, we improve the convergence bound further. When employing some initial condition, we show that our method converges faster near the small neighborhood of the solution. Numerical simulations demonstrate the efficiency of our algorithm.