Convergence of Random Reshuffling Under The Kurdyka-{\L}ojasiewicz
  Inequality
  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 $\mathcal{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 $\mathcal{O}(t^{-q})$ with $q\in
(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.
