High Probability Guarantees for Random Reshuffling

We consider the stochastic gradient method with random reshuffling (mathsfRR) for tackling smooth nonconvex optimization problems. mathsfRR finds broad applications in practice, notably in training neural networks. In this work, we provide high probability complexity guarantees for this method. First, we establish a high probability ergodic sample complexity result (without taking expectation) for finding an varepsilon-stationary point. Our derived complexity matches the best existing in-expectation one up to a logarithmic term while imposing no additional assumptions nor modifying mathsfRR's updating rule. Second, building on this analysis, we propose a simple stopping criterion embedded with a computable stopping test for mathsfRR (denoted as mathsfRR-mathsfsc). This criterion is guaranteed to be triggered after a finite number of iterations, enabling us to prove the same order high probability complexity for the returned last iterate. The fundamental ingredient in deriving the aforementioned results is a new concentration property for random reshuffling, which could be of independent interest. Finally, we conduct numerical experiments on small neural network training to support our theoretical findings.