In this work, we propose and study a novel stochastic optimization algorithm, termed the normal map-based proximal random reshuffling (norm-PRR) method, for nonsmooth nonconvex finite-sum problems. Random reshuffling techniques are prevalent and widely utilized in large-scale applications, e.g., in the training of neural networks. While the convergence behavior and advantageous acceleration effects of random reshuffling methods are fairly well understood in the smooth setting, much less seems to be known in the nonsmooth case and only few proximal-type random reshuffling approaches with provable guarantees exist. We establish the iteration complexity ${\cal O}(n^{-1/3}T^{-2/3})$ for norm-PRR, where $n$ is the number of component functions and $T$ counts the total number of iteration. We also provide novel asymptotic convergence results for norm-PRR. Specifically, under the Kurdyka-{\L}ojasiewicz (KL) inequality, we establish strong limit-point convergence, i.e., the iterates generated by norm-PRR converge to a single stationary point. Moreover, we derive last iterate convergence rates of the form ${\cal O}(k^{-p})$; here, $p \in [0, 1]$ depends on the KL exponent $\theta \in [0,1)$ and step size dynamics. Finally, we present preliminary numerical results on machine learning problems that demonstrate the efficiency of the proposed method.

本文提出并研究了一种新颖的随机优化算法，称为基于正态映射的近端随机重排（norm-PRR）方法，用于非光滑非凸有限和问题。我们建立了norm-PRR的迭代复杂度O(n^{-1/3}T^{-2/3})，其中n是组成函数的数量，T表示迭代总数。此外，在Kurdyka-Łojasiewicz不等式下，我们建立了norm-PRR的强极限点收敛性，并得到了迭代的最终收敛速度为O(k^{-p})的形式；其中，p∈[0, 1]取决于KL指数θ∈[0,1)和步长动态。最后，我们还提供了关于机器学习问题的初步数值结果，证明了该方法的效率。

一种新的非平滑非凸有限和优化问题随机重排方法