# Convergence of ease-controlled Random Reshuffling gradient Algorithms under Lipschitz smoothness

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 30 of its 77 references that are in the map.
- First posted on arXiv 4 Dec 2022.

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

- [Adam: A Method for Stochastic Optimization](https://mlsanity.com/paper/1412.6980/) (2014)
- [On Large-Batch Training for Deep Learning: Generalization Gap and Sharp Minima](https://mlsanity.com/paper/1609.04836/) (2016)
- [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)
- [AdaGrad stepsizes: Sharp convergence over nonconvex landscapes](https://mlsanity.com/paper/1806.01811/) (2018)
- [Minimizing Finite Sums with the Stochastic Average Gradient](https://mlsanity.com/paper/1309.2388/) (2013)
- [Better Theory for SGD in the Nonconvex World](https://mlsanity.com/paper/2002.03329/) (2020)
- [Random Reshuffling: Simple Analysis with Vast Improvements](https://mlsanity.com/paper/2006.05988/) (2020)
- [Adam Can Converge Without Any Modification On Update Rules](https://mlsanity.com/paper/2208.09632/) (2022)
- [LAG: Lazily Aggregated Gradient for Communication-Efficient Distributed Learning](https://mlsanity.com/paper/1805.09965/) (2018)
- [Why Random Reshuffling Beats Stochastic Gradient Descent](https://mlsanity.com/paper/1510.08560/) (2015)
- [SGD for Structured Nonconvex Functions: Learning Rates, Minibatching and Interpolation](https://mlsanity.com/paper/2006.10311/) (2020)
- [Stochastic (Approximate) Proximal Point Methods: Convergence, Optimality, and Adaptivity](https://mlsanity.com/paper/1810.05633/) (2018)
- [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)
- [Stochastic Methods for Composite and Weakly Convex Optimization Problems](https://mlsanity.com/paper/1703.08570/) (2017)
- [Stochastic Gradient Descent for Nonconvex Learning without Bounded Gradient Assumptions](https://mlsanity.com/paper/1902.00908/) (2019)
- [Incremental Gradient, Subgradient, and Proximal Methods for Convex Optimization: A Survey](https://mlsanity.com/paper/1507.01030/) (2015)
- [Stochastic Quasi-Gradient Methods: Variance Reduction via Jacobian Sketching](https://mlsanity.com/paper/1805.02632/) (2018)
- [Proximal and Federated Random Reshuffling](https://mlsanity.com/paper/2102.06704/) (2021)
- [Adaptive Sampling Strategies for Stochastic Optimization](https://mlsanity.com/paper/1710.11258/) (2017)
- [Convergence Rate of Incremental Gradient and Newton Methods](https://mlsanity.com/paper/1510.08562/) (2015)
- [Server-Side Stepsizes and Sampling Without Replacement Provably Help in Federated Optimization](https://mlsanity.com/paper/2201.11066/) (2022)
- [On the Convergence Rate of Incremental Aggregated Gradient Algorithms](https://mlsanity.com/paper/1506.02081/) (2015)
- [Random Reshuffling with Variance Reduction: New Analysis and Better Rates](https://mlsanity.com/paper/2104.09342/) (2021)
- [Federated Optimization Algorithms with Random Reshuffling and Gradient Compression](https://mlsanity.com/paper/2206.07021/) (2022)
- [Convergence of Random Reshuffling Under The Kurdyka-Lojasiewicz Inequality](https://mlsanity.com/paper/2110.04926/) (2021)
- [Improved Analysis and Rates for Variance Reduction under Without-replacement Sampling Orders](https://mlsanity.com/paper/2104.12112/) (2021)

## Abstract (arXiv)

In this work, we consider minimizing the average of a very large number of smooth and possibly non-convex functions, and we focus on two widely used minibatch frameworks to tackle this optimization problem: Incremental Gradient (IG) and Random Reshuffling (RR). We define ease-controlled modifications of the IG/RR schemes, which require a light additional computational effort {but} can be proved to converge under {weak} and standard assumptions. In particular, we define two algorithmic schemes in which the IG/RR iteration is controlled by using a watchdog rule and a derivative-free linesearch that activates only sporadically to guarantee convergence. The two schemes differ in the watchdog and the linesearch, which are performed using either a monotonic or a non-monotonic rule. The two schemes also allow controlling the updating of the stepsize used in the main IG/RR iteration, avoiding the use of pre-set rules that may drive the stepsize to zero too fast, reducing the effort in designing effective updating rules of the stepsize. We prove convergence under the mild assumption of Lipschitz continuity of the gradients of the component functions and perform extensive computational analysis using different deep neural architectures and a benchmark of varying-size datasets. We compare our implementation with both a full batch gradient method (i.e. L-BFGS) and an implementation of IG/RR methods, proving that our algorithms require a similar computational effort compared to the other online algorithms and that the control on the learning rate may allow a faster decrease of the objective function.