One-Prox Random Reshuffling for Nonsmooth Nonconvex Optimization: Complexity and KL Last-Iterate Rates

Random reshuffling (RR) has been widely applied to large-scale finite-sum optimization. However, existing proximal RR methods for such problems with nonsmooth structure typically either require multiple proximal evaluations per epoch or couple the proximal parameter with the reshuffling stepsize. In this paper, we propose a proximal algorithm for nonsmooth nonconvex random reshuffling (PNRR) that simultaneously addresses these two issues. PNRR requires only one proximal evaluation per epoch while allowing the proximal parameter to be chosen independently of the reshuffling stepsize and kept constant. We establish finite-time complexity guarantees for PNRR, including an incremental first-order oracle complexity of $\mathcal{O}(n{ϵ}^{-2})$ and a proximal oracle complexity of $\mathcal{O}({ϵ}^{-2})$. Compared with several representative methods, the complexity advantage of PNRR becomes more pronounced in the high-accuracy regime. Under the Kurdyka–\Lojasiewicz (KL) framework, we further prove that the whole sequence generated by PNRR converges to a critical point. Moreover, under polynomially decaying stepsizes, we obtain explicit polynomial convergence rates for the function values, stationarity measure, and iterate error, while exponentially decaying stepsizes yield geometric convergence of all three quantities when the KL exponent is below $1/2$. Numerical experiments on logistic regression and nonconvex binary classification demonstrate the competitive and stable performance of PNRR.