# Convergence of Random Reshuffling Under The Kurdyka-Lojasiewicz Inequality arXiv: https://arxiv.org/abs/2110.04926 · HTML: https://mlsanity.com/paper/2110.04926/ ## Key facts - Cited by 16 papers in the map (data through 14 Oct 2026). - Builds on 20 of its 59 references that are in the map. - First posted on arXiv 10 Oct 2021. ## Builds on (most cited first, 20 of 20) - [PyTorch: An Imperative Style, High-Performance Deep Learning Library](https://mlsanity.com/paper/1912.01703/) (2019) - [Optimization Methods for Large-Scale Machine Learning](https://mlsanity.com/paper/1606.04838/) (2016) - [Nonconvex Optimization Meets Low-Rank Matrix Factorization: An Overview](https://mlsanity.com/paper/1809.09573/) (2018) - [Random Reshuffling: Simple Analysis with Vast Improvements](https://mlsanity.com/paper/2006.05988/) (2020) - [Global Convergence of ADMM in Nonconvex Nonsmooth Optimization](https://mlsanity.com/paper/1511.06324/) (2015) - [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) - [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) - [Inertial Proximal Alternating Linearized Minimization (iPALM) for Nonconvex and Nonsmooth Problems](https://mlsanity.com/paper/1702.02505/) (2017) - [iPiano: Inertial Proximal Algorithm for Non-Convex Optimization](https://mlsanity.com/paper/1404.4805/) (2014) - [Convergence Rate of Incremental Gradient and Newton Methods](https://mlsanity.com/paper/1510.08562/) (2015) - [Splitting methods with variable metric for KL functions](https://mlsanity.com/paper/1405.1357/) (2014) - [Global convergence of splitting methods for nonconvex composite optimization](https://mlsanity.com/paper/1407.0753/) (2014) - [Recht-R'e Noncommutative Arithmetic-Geometric Mean Conjecture is False](https://mlsanity.com/paper/2006.01510/) (2020) - [Douglas-Rachford splitting for nonconvex optimization with application to nonconvex feasibility problems](https://mlsanity.com/paper/1409.8444/) (2014) - [The proximal alternating direction method of multipliers in the nonconvex setting: convergence analysis and rates](https://mlsanity.com/paper/1801.01994/) (2018) - [Improved Analysis and Rates for Variance Reduction under Without-replacement Sampling Orders](https://mlsanity.com/paper/2104.12112/) (2021) - [An inertial forward-backward algorithm for the minimization of the sum of two nonconvex functions](https://mlsanity.com/paper/1410.0641/) (2014) - [Convergence Rates of Subgradient Methods for Quasi-convex Optimization Problems](https://mlsanity.com/paper/1910.10879/) (2019) ## Built on by (most cited first, 16 of 16) - [On the Convergence of Federated Averaging with Cyclic Client Participation](https://mlsanity.com/paper/2302.03109/) (2023) - [On the existence of global minima and convergence analyses for gradient descent methods in the training of deep neural networks](https://mlsanity.com/paper/2112.09684/) (2021) - [A Unified Convergence Theorem for Stochastic Optimization Methods](https://mlsanity.com/paper/2206.03907/) (2022) - [On the Last-Iterate Convergence of Shuffling Gradient Methods](https://mlsanity.com/paper/2403.07723/) (2024) - [Sampling without Replacement Leads to Faster Rates in Finite-Sum Minimax Optimization](https://mlsanity.com/paper/2206.02953/) (2022) - [Distributed Random Reshuffling over Networks](https://mlsanity.com/paper/2112.15287/) (2021) - [High Probability Guarantees for Random Reshuffling](https://mlsanity.com/paper/2311.11841/) (2023) - [Convergence Rates of Training Deep Neural Networks via Alternating Minimization Methods](https://mlsanity.com/paper/2208.14318/) (2022) - [A New Random Reshuffling Method for Nonsmooth Nonconvex Finite-sum Optimization](https://mlsanity.com/paper/2312.01047/) (2023) - [Distributed Random Reshuffling Methods with Improved Convergence](https://mlsanity.com/paper/2306.12037/) (2023) - [Convergence of Sign-based Random Reshuffling Algorithms for Nonconvex Optimization](https://mlsanity.com/paper/2310.15976/) (2023) - [Decentralized Weakly Convex Optimization Over the Stiefel Manifold](https://mlsanity.com/paper/2303.17779/) (2023) - [Shuffling the Stochastic Mirror Descent via Dual Lipschitz Continuity and Kernel Conditioning](https://mlsanity.com/paper/2603.16042/) (2026) - [Convergence of ease-controlled Random Reshuffling gradient Algorithms under Lipschitz smoothness](https://mlsanity.com/paper/2212.01848/) (2022) - [Beyond adaptive gradient: Fast-Controlled Minibatch Algorithm for large-scale optimization](https://mlsanity.com/paper/2411.15795/) (2024) - [Stochastic Saddle Avoidance Beyond Unit Excitation and Smoothness: A Pathwise Lyapunov-Perron Framework](https://mlsanity.com/paper/2608.03001/) (2026) ## Abstract (arXiv) We study the random reshuffling (RR) method for smooth nonconvex optimization problems with a finite-sum structure. Though this method is widely utilized in practice such as the training of neural networks, its convergence behavior is only understood in several limited settings. In this paper, under the well-known Kurdyka-Lojasiewicz (KL) inequality, we establish strong limit-point convergence results for RR with appropriate diminishing step sizes, namely, the whole sequence of iterates generated by RR is convergent and converges to a single stationary point in an almost sure sense. In addition, we derive the corresponding rate of convergence, depending on the KL exponent and the suitably selected diminishing step sizes. When the KL exponent lies in [0,frac12], the convergence is at a rate of O(t-1) with t counting the iteration number. When the KL exponent belongs to (frac12,1), our derived convergence rate is of the form O(t-q) with q∈ (0,1) depending on the KL exponent. The standard KL inequality-based convergence analysis framework only applies to algorithms with a certain descent property. We conduct a novel convergence analysis for the non-descent RR method with diminishing step sizes based on the KL inequality, which generalizes the standard KL framework. We summarize our main steps and core ideas in an informal analysis framework, which is of independent interest. As a direct application of this framework, we also establish similar strong limit-point convergence results for the reshuffled proximal point method.