mlsanityData to 14 Oct 2026

A New Random Reshuffling Method for Nonsmooth Nonconvex Finite-sum Optimization

arXiv 2312.01047 ↗First posted 2 Dec 2023math.OC cs.LGcited by 4

Not on the map. Why?

Abstract (arXiv)

Random reshuffling techniques are prevalent in large-scale applications, such as training neural networks. While the convergence and acceleration effects of random reshuffling-type methods are fairly well understood in the smooth setting, much less studies seem available in the nonsmooth case. In this work, we design a new normal map-based proximal random reshuffling (norm-PRR) method for nonsmooth nonconvex finite-sum problems. We show that norm-PRR achieves the iteration complexity cal O(n-1/3T-2/3) where n denotes the number of component functions f(·,i) and T counts the total number of iterations. This improves the currently known complexity bounds for this class of problems by a factor of n-1/3 in terms of the number of gradient evaluations. Additionally, we prove that norm-PRR converges linearly under the (global) Polyak-Lojasiewicz condition and in the interpolation setting. We further complement these non-asymptotic results and provide an in-depth analysis of the asymptotic properties of norm-PRR. Specifically, under the (local) Kurdyka-Lojasiewicz inequality, the whole sequence of iterates generated by norm-PRR is shown to converge to a single stationary point. Moreover, we derive last-iterate convergence rates that can match those in the smooth, strongly convex setting. Finally, numerical experiments are performed on nonconvex classification tasks to illustrate the efficiency of the proposed approach.

Key facts. Cited by 4 papers in the map (data through 14 Oct 2026). Builds on 37 of its 104 references that are in the map. First posted on arXiv 2 Dec 2023.

Builds on

37 of 104 references.

References · 37

  1. 2015Deep Residual Learning for Image Recognitioncited by 52,096
  2. 2019PyTorch: An Imperative Style, High-Performance Deep Learning Librarycited by 20,305
  3. 2014Very Deep Convolutional Networks for Large-Scale Image Recognitioncited by 15,364
  4. 2016Optimization Methods for Large-Scale Machine Learningcited by 1,150
  5. 2013Stochastic First- and Zeroth-order Methods for Nonconvex Stochastic Programmingcited by 724
  6. 2016Linear Convergence of Gradient and Proximal-Gradient Methods Under the Polyak-Lojasiewicz Conditioncited by 539
  7. 2019SGD: General Analysis and Improved Ratescited by 207
  8. 2018Stochastic model-based minimization of weakly convex functionscited by 159
  9. 2020Is Local SGD Better than Minibatch SGD?cited by 151
  10. 2013Mini-batch Stochastic Approximation Methods for Nonconvex Stochastic Composite Optimizationcited by 143
  11. 2018Stochastic subgradient method converges on tame functionscited by 124
  12. 2020Random Reshuffling: Simple Analysis with Vast Improvementscited by 115
25 more
  1. 2018SGD and Hogwild! Convergence Without the Bounded Gradients Assumptioncited by 95
  2. 2015Why Random Reshuffling Beats Stochastic Gradient Descentcited by 79
  3. 2018Random Shuffling Beats SGD after Finite Epochscited by 67
  4. 2020SGD for Structured Nonconvex Functions: Learning Rates, Minibatching and Interpolationcited by 67
  5. 2019SGD without Replacement: Sharper Rates for General Smooth Convex Functionscited by 61
  6. 2016Error bounds, quadratic growth, and linear convergence of proximal methodscited by 60
  7. 2020A Unified Convergence Analysis for Shuffling-Type Gradient Methodscited by 58
  8. 2017Stochastic Methods for Composite and Weakly Convex Optimization Problemscited by 48
  9. 2015From error bounds to the complexity of first-order descent methods for convex functionscited by 43
  10. 2016Stochastic Quasi-Newton Methods for Nonconvex Stochastic Optimizationcited by 37
  11. 2016Calculus of the exponent of Kurdyka-Lojasiewicz inequality and its applications to linear convergence of first-order methodscited by 35
  12. 2021Proximal and Federated Random Reshufflingcited by 33
  13. 2014iPiano: Inertial Proximal Algorithm for Non-Convex Optimizationcited by 30
  14. 2021Convergence of stochastic gradient descent schemes for Lojasiewicz-landscapescited by 28
  15. 2014Splitting methods with variable metric for KL functionscited by 26
  16. 2018Analysis of nonsmooth stochastic approximation: the differential inclusion approachcited by 23
  17. 2018Tight Dimension Independent Lower Bound on the Expected Convergence Rate for Diminishing Step Sizes in SGDcited by 18
  18. 2014Convergence of Stochastic Proximal Gradient Algorithmcited by 17
  19. 2015ℓ1-regularized Neural Networks are Improperly Learnable in Polynomial Timecited by 16
  20. 2021Convergence of Random Reshuffling Under The Kurdyka-Lojasiewicz Inequalitycited by 16
  21. 2022A Unified Convergence Theorem for Stochastic Optimization Methodscited by 12
  22. 2019A Stochastic Extra-Step Quasi-Newton Method for Nonsmooth Nonconvex Optimizationcited by 7
  23. 2021A trust region-type normal map-based semismooth Newton method for nonsmooth nonconvex composite optimizationcited by 4
  24. 2018A Stochastic Semismooth Newton Method for Nonsmooth Nonconvex Optimizationcited by 3
  25. 2020Extrapolated Proximal Subgradient Algorithms for Nonconvex and Nonsmooth Fractional Programscited by 3

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2026: 4.

4 papers.

  1. 2026Shuffling the Stochastic Mirror Descent via Dual Lipschitz Continuity and Kernel Conditioningcited by 1
  2. 2026Achieving Linear Speedup for Composite Federated Learningcited by 0
  3. 2026Stochastic Saddle Avoidance Beyond Unit Excitation and Smoothness: A Pathwise Lyapunov-Perron Frameworkcited by 0
  4. 2026Centered Permutation Prefixes for SGD with Random Reshuffling: Sharp Rates, H"older Geometry, and Composite Proximal Extensionscited by 0