Proximal Random Reshuffling Under Local Lipschitz Continuity

We study proximal random reshuffling for minimizing the sum of locally Lipschitz or locally smooth functions and a proper lower semicontinuous convex function without assuming coercivity or the existence of limit points. The algorithmic guarantees pertaining to near-approximate stationarity rely on a new tracking lemma linking the iterates to trajectories of conservative fields. One of the novelties in the analysis consists of handling set-valued mappings with unbounded values. In the locally smooth case, it improves the known convergence rate from nearly $O(k^{-1/4})$ to nearly $o(k^{-1/2})$.

Funding: This research was supported in part by the Division of Electrical, Communications and Cyber Systems [Grant EPCN 2023032] and the Office of Naval Research [Grant N00014-21-1-2282] to C. Josz; in part by the Hong Kong Research Grants Council [ECS Project 27301425] and the University of Hong Kong [start-up fund] to L. Lai; and in part by the Guangdong Provincial Key Laboratory of Big Data Computing, The Chinese University of Hong Kong, Shenzhen to X. Li.