Pith. sign in

REVIEW 3 minor 80 references

Stochastic Saddle Avoidance Beyond Unit Excitation and Smoothness: A Pathwise Lyapunov-Perron Framework

T0 review · 0 major / 3 minor · reviewed 2026-08-08 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

Pith's one-line read This paper proves that stochastic recursions almost surely avoid strict saddles without unit excitation, replacing the noise-excitation mechanism with verifiable pathwise tail conditions and a Lyapunov–Perron graph argument.

desk verdict A genuinely new pathwise framework that removes unit excitation and delivers the first a.s. saddle-avoidance result for random reshuffling; the proofs are detailed and the soft spots are minor. read the letter →

arxiv 2608.03001 v2 pith:D7QHCNC2 submitted 2026-08-04 math.OC cs.LGmath.DSstat.ML

Junwen Qiu , Bohao Ma , Andre Milzarek , Junyu Zhang This is my paper · ORCID
classification math.OCcs.LGmath.DSstat.ML MSC 90C1590C2665K0562L20
keywords saddleavoidanceunitexcitationstochasticmirrordescentrandomreshufflingLyapunov-Perronnonsmoothoptimizationapproximationstrict
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

This paper claims that a broad class of stochastic recursions $z_{k+1}=z_k-\alpha_k G(z_k;\xi_k)$ almost surely avoid the unstable zeros of their mean field $F$, without unit excitation: the noise is never required to have a uniformly positive projection in every direction. The authors prove that, along almost every random seed path, the set of initial points whose trajectories can stay trapped near an unstable zero has Lebesgue measure zero. This replaces the center-stable manifold argument used in deterministic saddle avoidance with a path-dependent change of variables and a Lyapunov–Perron contraction argument, and it works even though the sampled maps share neither a common fixed point nor a common linearization. If correct, the theorem yields almost sure strict saddle avoidance for stochastic mirror descent, for a normal map-based proximal stochastic gradient method on nonsmooth composite objectives, and for random reshuffling, and it converts iterate-convergence guarantees into convergence to local minimizers.

What carries the argument

The central object is the path-dependent change of variables $U_k = I - S_k$ with $S_k = \sum_{i=k}^\infty \alpha_i J_i$, where $J_i = DG(z_*;\xi_i) - DF(z_*)$; applying it to the centered recursion removes the sample-dependent linear perturbation from the leading term, leaving the common matrix $H = DF(z_*)$ in control of the spectral splitting. The Lyapunov–Perron operator $T_\zeta$ acts on a weighted sequence space $Y_\theta$ and expresses the center-stable component forward and the unstable component backward as a contraction; its fixed points form a Lipschitz graph $h: E^{cs} \to E^u$ over the center-stable subspace, and that graph has Lebesgue measure zero. This graph is exactly the set of transformed initial points whose trajectories can remain in a bounded neighborhood of the saddle.

What would settle it

Choose a two-dimensional recursion $z_{k+1} = z_k - \alpha_k(H z_k + b_k + J_k z_k)$ with $H$ having one negative eigenvalue and adversarial deterministic sequences $(b_k, J_k)$ for which the Assumption 2.10 tails diverge — say, $b_k = \alpha_k^{-1}$ on sparse blocks or $J_k$ chosen so that $S_k$ does not converge — and test numerically whether a positive-measure set of initial points converges to $0$; a positive-measure basin would show that the tail conditions are necessary rather than merely sufficient.

Watch

Extended reading notes

Core claim

The paper's central claim is Theorem 2.14: under local regularity of the sampled fields (Assumption 2.2) and the pathwise oracle condition (Assumption 2.10), the recursion (3) satisfies $P(\lim_{k\to\infty} z_k \in Z^*)=0$, where $Z^*$ is the set of unstable zeros of $F$ — points where $F(z_*)=0$ and $DF(z_*)$ has an eigenvalue with negative real part. Equivalently, if $z_0$ has a density, a trajectory cannot converge to a strict saddle of the mean-field dynamics. The authors show this is the natural stochastic replacement for the deterministic center-stable manifold theorem, and they verify the required conditions for i.i.d. martingale-type noise and for without-replacement finite-sum sampling.

Load-bearing premise

The argument stands on Assumption 2.10, which requires that the accumulated weighted errors vanish along almost every oracle path: $S_k\to 0$, $S_{k+1}J_k\to 0$, and the series $\sum \alpha_k b_k$ and $\sum \alpha_k S_{k+1}b_k$ converge; if any of these pathwise tails fails, the change of variables and the contraction argument no longer control the dynamics.

Editorial extensions

If this is right

  • Stochastic mirror descent under relative smoothness (with SGD as the Euclidean special case) avoids strict saddles almost surely under standard i.i.d. sampling with finite moments, with no unit excitation and no generic tilt.
  • For nonsmooth composite objectives, the normal map-based proximal stochastic gradient method avoids active strict saddles almost surely; combined with the associated KL-based iterate convergence theory, this gives almost sure convergence to local minimizers of the original objective.
  • Random reshuffling almost surely avoids strict saddles under locally Lipschitz Hessians and step sizes with summable squares, despite its dependent and biased stochastic gradients; the paper reports this as the first asymptotic almost-sure strict saddle avoidance result for random reshuffling.
  • As a by-product, when the noise is absent the avoidance result extends deterministic mirror descent saddle avoidance from Lipschitz smoothness to relative smoothness.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • Beyond the paper: any oracle that verifies the two pathwise series conditions in Assumption 2.10 — not only i.i.d. or without-replacement sampling — would make the corresponding algorithm inherit Theorem 2.14; the paper's examples are therefore a template rather than an exhaustive list.
  • Beyond the paper: the pathwise formulation suggests that saddle avoidance does not require a noise component in the unstable direction at all; vanishing noise (interpolation) and low-dimensional noise (finite-sum with $n<d$) are both covered, so the mechanism is geometric rather than excitation-based.
  • Beyond the paper: a natural next test is to verify Assumption 2.10 for cyclic or biased without-replacement schemes, or for momentum-augmented recursions; the paper lists distributed, momentum, alternating, and block-coordinate methods as plausible future applications.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

0 major / 3 minor

Summary. The paper studies the stochastic recursion z_{k+1}=z_k-\alpha_k G(z_k;\xi_k) with mean field F, and proves an almost sure avoidance theorem for unstable zeros of F under assumptions that replace unit excitation by pathwise conditions on the accumulated noise and linearization errors (Assumption 2.10). The proof fixes a seed realization, applies the path-dependent change of variables U_k=I-\sum_{i=k}^\infty \alpha_i J_i, and uses a Lyapunov-Perron argument to show that initial states whose trajectories stay near an unstable zero form a Lipschitz graph over the center-stable subspace, hence a Lebesgue null set; Fubini's theorem then gives the almost sure statement. The framework is applied to stochastic mirror descent (Corollary 4.8), a normal map-based proximal stochastic gradient method (Corollaries 4.16 and 4.17), and random reshuffling (Corollary 5.3). The applications verify the oracle assumptions under i.i.d. finite-moment sampling and under without-replacement permutation sequences.

Significance. If correct, the paper is a substantial advance: it removes the unit-excitation assumption that is standard in stochastic saddle avoidance and extends the measure-zero basin mechanism to sampled maps that do not share a common fixed point or common linearization. The pathwise Lyapunov-Perron framework is original and internally consistent, and the proof is unusually detailed; Assumption 2.10, while strong, is explicitly verified for the two principal sampling models in Propositions 2.11 and 2.12. The paper also provides the first asymptotic almost sure strict saddle avoidance statement for random reshuffling without injected perturbations. The central theorem involves no fitted parameters or circular reasoning, and the external convergence theorem [61] used for the NSGD applications is cleanly separable from the avoidance proof.

minor comments (3)
  1. [Section 3.3-3.4, Eq. (17)] The seed-independence of the radius \delta in (17), and hence of \delta_0 in Theorem 2.13, is asserted but not fully justified: Lemma 3.3 supplies constants C_H, \kappa, \nu for a fixed reindexed step-size sequence, while the same \delta is used for every tail \{\alpha_{m+\ell}\}_{\ell\ge0}. Please add an explicit uniformity argument (e.g., using the fixed Jordan block sizes and the fact that the finite tail sums \sum_{\ell=0}^{K-1}\alpha_{m+\ell}^2 vanish as m\to\infty) to show that C_H, \kappa, and \nu can be chosen uniformly over all sufficiently large reindexing starts m. The claim is true, but the present text leaves this point implicit.
  2. [Corollary 4.16 and [61, Theorem 3.6]] The step F_\lambda(z_k)\to0 almost surely is delegated to [61, Theorem 3.6], but the hypotheses of that theorem are not reproduced. Please either quote the theorem or state precisely how Assumption 4.15 and the step-size condition (31) imply its hypotheses; otherwise the reader cannot verify the conversion from convergence of prox_{\lambda\varphi}(z_k) to convergence of z_k in the proof of Corollary 4.16.
  3. [Notation, Section 3.4 and Lemma A.2] The symbol m is used for the reindexing start in Section 3.4 and also for the Jordan block size in Lemma A.2; renaming one of the two uses would avoid confusion for the reader.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the avoidance theorem is proven from explicit pathwise assumptions; the only author-overlapping citation is an auxiliary, non-circular convergence result.

full rationale

The central claim, Theorem 2.14, is derived directly from the stated Assumptions 2.2 and 2.10. The pathwise change of variables U_k = I - S_k, the transition estimates, and the Lyapunov–Perron graph construction in Section 3 are all carried out in the paper, and the trapping null-set conclusion is obtained from those arguments rather than from an assumed conclusion. Assumption 2.10 is strong, but it is a verifiable sufficient condition: Proposition 2.11 verifies it for i.i.d. martingale-type noise and Proposition 2.12 verifies it for without-replacement sampling, so the applications are not circularly relying on the avoidance statement. The only author-overlapping citation is [61], used in Corollary 4.16 and Corollary 4.17 for the auxiliary iterate-convergence guarantee F_lambda(z_k) -> 0 and for KL-based full-sequence convergence. That cited theorem is external to the avoidance proof and does not assume or encode the avoidance conclusion; it is a separate convergence result that the paper explicitly invokes to translate avoidance into convergence to local minimizers. No fitted parameter is renamed as a prediction, no uniqueness theorem is imported from the authors' prior work to force a choice, and no ansatz is smuggled in via self-citation. The paper is therefore self-contained with respect to its claimed saddle-avoidance derivation, and the mild concern about a load-bearing self-citation does not rise to circularity.

Assumptions & free parameters 0 free parameters · 5 assumptions · 0 invented entities

The central theorem is conditional on Assumption 2.2 and Assumption 2.10, both explicitly stated and verified for the applications. No free parameters are fitted to data and no new entities are postulated. Standard mathematical background is used throughout.

assumptions (5)
  • domain assumption Assumption 2.2: regularity of F, local equicontinuity of {DG(.;xi)}, and lipeomorphism of the update maps.
    Standing assumptions of the framework; verified for SGD/mirror descent, normal map proximal methods, and random reshuffling.
  • domain assumption Assumption 2.10: pathwise tail summability of noise increments and linearization errors.
    Core hypothesis enabling the path-dependent change of variables; verified under i.i.d. martingale noise and without-replacement sampling.
  • domain assumption Strict saddle property or active strict saddle property for the objective.
    Used to identify stationary points that are not local minimizers as saddles; standard in the saddle avoidance literature.
  • domain assumption Step-size conditions: alpha_k -> 0, sum alpha_k = infinity, and appropriate squared summability conditions.
    Stated in Section 2.4 and in each application; needed for the transition estimates and stochastic oracle verification.
  • standard math Standard measure-theoretic, spectral splitting, and contraction mapping background.
    Used throughout the proofs of Theorems 2.13 and 2.14, including Fubini, Lebesgue null sets, real Jordan forms, and Banach fixed point arguments.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Stochastic Saddle Avoidance Beyond Unit Excitation and Smoothness: A Pathwise Lyapunov-Perron Framework." pith.science (2026). https://pith.science/paper/D7QHCNC2

@misc{pith2026260803001,
  author       = {Pith},
  title        = {Pith review of: Stochastic Saddle Avoidance Beyond Unit Excitation and Smoothness: A Pathwise Lyapunov-Perron Framework},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/D7QHCNC2}},
  note         = {Machine review of arXiv:2608.03001}
}
read the original abstract

Unit excitation (UE) is a common assumption in stochastic saddle avoidance: the stochastic error must have a uniformly positive component along every direction, in expectation. This condition gives a direct way to rule out convergence to strict saddles, but it also oversimplifies the actual noise structure, and does not match many stochastic optimization regimes. In overparameterized or interpolation models, the noise may vanish near stationarity. In finite-sum problems, the stochastic gradient noise may lie in a low-dimensional, data-dependent subspace. In these (common) scenarios, UE is naturally not satisfied. In this paper, we prove an abstract almost sure avoidance theorem for stochastic recursions without UE. The theorem replaces UE-type requirements by verifiable pathwise conditions. In applications, these conditions follow, e.g., from local smoothness and finite-moment assumptions under standard i.i.d. sampling, or from the finite-sum structure under without-replacement sampling. Since the stochastically sampled maps generally do not share a fixed point, the celebrated center-stable manifold argument used in deterministic analyses is not directly applicable. Instead, we use a path-dependent change of variables together with a pathwise Lyapunov--Perron-based proof strategy. As applications, we obtain strict saddle avoidance for stochastic mirror descent (including SGD) and for random reshuffling. For nonsmooth composite objectives, we prove avoidance results for a proximal-type stochastic gradient method. Combining these insights with suitable iterate convergence guarantees, this allows establishing convergence to local minimizers of the original objective function.

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

80 extracted references · 64 canonical work pages

  1. [61]

    J. Qiu, L. Jiang, and A. Milzarek,A normal map-based proximal stochastic gradient method: Convergence and identification properties, arXiv preprint arXiv:2305.05828, (2025)

    arXiv 2025

  2. [1]

    Abadi et al.,TensorFlow: Large-scale machine learning on heterogeneous distributed systems, arXiv preprint arXiv:1603.04467, (2016)

    M. Abadi et al.,TensorFlow: Large-scale machine learning on heterogeneous distributed systems, arXiv preprint arXiv:1603.04467, (2016)

    arXiv 2016

  3. [2]

    Absil, R

    P.-A. Absil, R. Mahony, and B. Andrews,Convergence of the iterates of descent methods for analytic cost functions, SIAM J. Optim., 16 (2005), pp. 531–547

    work page 2005

  4. [3]

    Attouch and J

    H. Attouch and J. Bolte,On the convergence of the proximal algorithm for nonsmooth functions involving analytic features, Math. Program., 116 (2009), pp. 5–16

    2009

  5. [4]

    Attouch, J

    H. Attouch, J. Bolte, P. Redont, and A. Soubeyran,Proximal alternating minimization and projection methods for nonconvex problems: an approach based on the Kurdyka-Łojasiewicz inequality, Math. Oper. Res., 35 (2010), pp. 438–457

    work page 2010

  6. [5]

    Attouch, J

    H. Attouch, J. Bolte, and B. F. Sv aiter,Convergence of descent methods for semi-algebraic and tame problems: proximal algorithms, forward-backward splitting, and regularized Gauss-Seidel methods, Math. Program., 137 (2013), pp. 91–129

    work page 2013

  7. [6]

    Bach,Self-concordant analysis for logistic regression, Electron

    F. Bach,Self-concordant analysis for logistic regression, Electron. J. Stat., 4 (2010), pp. 384–414

    work page 2010

  8. [7]

    H. H. Bauschke, J. Bolte, and M. Teboulle,A descent lemma beyond Lipschitz gradient continuity: first-order methods revisited and applications, Math. Oper. Res., 42 (2017), pp. 330–348

    work page 2017

Show all 80 references
  1. [8]

    H. H. Bauschke and P. L. Combettes,Convex analysis and monotone operator theory in Hilbert spaces, vol. 408, Springer, 2011

    2011

  2. [9]

    Beck and M

    A. Beck and M. Teboulle,Mirror descent and nonlinear projected subgradient methods for convex optimization, Oper. Res. Lett., 31 (2003), pp. 167–175

    2003

  3. [10]

    Benaïm,A dynamical system approach to stochastic approximations, SIAM J

    M. Benaïm,A dynamical system approach to stochastic approximations, SIAM J. Control Optim., 34 (1996), pp. 437–472

    1996

  4. [11]

    ,Dynamics of stochastic approximation algorithms, in Seminaire de probabilites XXXIII, Springer, 1999, pp. 1–68

    1999

  5. [12]

    Beneventano,On the trajectories of SGD without replacement, arXiv preprint arXiv:2312.16143, (2024)

    P. Beneventano,On the trajectories of SGD without replacement, arXiv preprint arXiv:2312.16143, (2024)

    2024 arXiv

  6. [13]

    Bhojanapalli, B

    S. Bhojanapalli, B. Neyshabur, and N. Srebro,Global optimality of local search for low rank matrix recovery, in Advances in Neural Information Processing Systems, vol. 29, 2016

    2016

  7. [14]

    Bianchi, W

    P. Bianchi, W. Hachem, and S. Schechtman,Stochastic subgradient descent escapes active strict saddles on weakly convex functions, Math. Oper. Res., 49 (2024), pp. 1761–1790

    2024

  8. [15]

    Bolte, S

    J. Bolte, S. Sabach, M. Teboulle, and Y. V aisbourd,First order methods beyond convexity and Lipschitz gradient continuity with applications to quadratic inverse problems, SIAM J. Optim., 28 (2018), pp. 2131–2151

    2018

  9. [16]

    Bottou, F

    L. Bottou, F. E. Curtis, and J. Nocedal,Optimization methods for large-scale machine learning, SIAM Rev., 60 (2018), pp. 223–311

    2018

  10. [17]

    D. L. Burkholder, B. J. Da vis, and R. F. Gundy,Integral inequalities for convex functions of operators on martingales, in Proceedings of the Sixth Berkeley Symposium on Mathematical Statistics and Probability, Vol. II: Probability theory, 1972, pp. 223–240

    1972

  11. [18]

    C. D. Dang and G. Lan,Stochastic block mirror descent methods for nonsmooth and stochastic optimization, SIAM J. Optim., 25 (2015), pp. 856–881

    2015

  12. [19]

    Daniilidis, W

    A. Daniilidis, W. Hare, and J. Malick,Geometrical interpretation of the predictor-corrector type algorithms in structured optimization problems, Optimization, 55 (2006), pp. 481–503

    2006

  13. [20]

    Da vis and D

    D. Da vis and D. Drusvyatskiy,Proximal methods avoid active strict saddles of weakly convex functions, Found. Comput. Math., 22 (2022), pp. 561–606. 35

    2022

  14. [21]

    Da vis, D

    D. Da vis, D. Drusvyatskiy, and L. Jiang,Active manifolds, stratifications, and convergence to local minima in nonsmooth optimization, Found. Comput. Math., 26 (2026), pp. 779–861

    2026

  15. [22]

    Def azio, F

    A. Def azio, F. Bach, and S. Lacoste-Julien,SAGA: A fast incremental gradient method with support for non-strongly convex composite objectives, in Advances in Neural Information Processing Systems, vol. 27, 2014

    2014

  16. [23]

    J. Deng, W. Dong, R. Socher, L.-J. Li, K. Li, and L. Fei-Fei,ImageNet: A large- scale hierarchical image database, in Proc. IEEE Conf. Comput. Vis. Pattern Recognit., 2009, pp. 248–255

    2009

  17. [24]

    Dosovitskiy, L

    A. Dosovitskiy, L. Beyer, A. Kolesnikov, D. Weissenborn, X. Zhai, T. Unterthiner, M. Dehghani, M. Minderer, G. Heigold, S. Gelly, J. Uszkoreit, and N. Houlsby, An image is worth 16x16 words: Transformers for image recognition at scale, arXiv preprint arXiv:2010.11929, (2020)

    2020 arXiv

  18. [25]

    Driggs, J

    D. Driggs, J. Tang, J. Liang, M. Da vies, and C.-B. Schönlieb,A stochastic proximal alternating minimization for nonsmooth and nonconvex optimization, SIAM J. Imaging Sci., 14 (2021), pp. 1932–1970

    2021

  19. [26]

    Drusvyatskiy and A

    D. Drusvyatskiy and A. S. Lewis,Optimality, identifiability, and sensitivity. arXiv preprint, arXiv:1207.6628, 2012

    2012 arXiv

  20. [27]

    R. Ge, F. Huang, C. Jin, and Y. Yuan,Escaping from saddle points—online stochastic gradient for tensor decomposition, in Proceedings of the 28th Conference on Learning Theory, vol. 40 of Proceedings of Machine Learning Research, PMLR, 2015, pp. 797–842

    2015

  21. [28]

    Gower, O

    R. Gower, O. Sebbouh, and N. Loizou,SGD for structured nonconvex functions: Learning rates, minibatching and interpolation, in International Conference on Artificial Intelligence and Statistics, PMLR, 2021, pp. 1315–1323

    2021

  22. [29]

    Gürbüzbalaban, A

    M. Gürbüzbalaban, A. Ozdaglar, and P. A. Parrilo,Why random reshuffling beats stochastic gradient descent, Math. Program., 186 (2021), pp. 49–84

    2021

  23. [30]

    N. T. V. Hang and E. Sarabi,A fresh look into variational analysis of ⌋2-partly smooth functions. arXiv preprint, arXiv:2411.00655v2, 2026

    2026

  24. [31]

    W. L. Hare and A. S. Lewis,Identifying active constraints via partial smoothness and prox- regularity, J. Convex Anal., 11 (2004), pp. 251–266

    2004

  25. [32]

    Hastie, R

    T. Hastie, R. Tibshirani, and J. Friedman,The elements of statistical learning, Springer Series in Statistics, Springer, New York, second ed., 2009. Data mining, inference, and prediction

    2009

  26. [33]

    R. A. Horn and C. R. Johnson,Matrix Analysis, Cambridge University Press, New York, NY, 2nd ed., 2012

    2012

  27. [34]

    J. Hu, T. Tian, S. Pan, and Z. Wen,On the local convergence of the semismooth newton method for composite optimization. arXiv preprint, arXiv:2211.01127v2, 2022

    2022 arXiv

  28. [35]

    C. Jin, R. Ge, P. Netrapalli, S. M. Kakade, and M. I. Jordan,How to escape saddle points efficiently, in Proceedings of the 34th International Conference on Machine Learning, vol. 70 of Proceedings of Machine Learning Research, PMLR, 2017, pp. 1724–1732

    2017

  29. [36]

    C. Jin, P. Netrapalli, R. Ge, S. M. Kakade, and M. I. Jordan,Stochastic gradient descent escapes saddle points efficiently, arXiv preprint arXiv:1902.04811, (2019)

    2019 arXiv

  30. [37]

    Johnson and T

    R. Johnson and T. Zhang,Accelerating stochastic gradient descent using predictive variance reduction, in Advances in Neural Information Processing Systems, vol. 26, 2013

    2013

  31. [38]

    C. Josz, L. Lai, and X. Li,Proximal random reshuffling under local Lipschitz continuity, arXiv preprint arXiv:2408.07182, (2024). 36

    2024 arXiv

  32. [39]

    Kurdyka,On gradients of functions definable in o-minimal structures, Ann

    K. Kurdyka,On gradients of functions definable in o-minimal structures, Ann. Inst. Fourier (Grenoble), 48 (1998), pp. 769–783

    1998

  33. [40]

    J. D. Lee, I. Panageas, G. Piliouras, M. Simchowitz, M. I. Jordan, and B. Recht, First-order methods almost always avoid strict saddle points, Math. Program., 176 (2019), pp. 311– 337

    2019

  34. [41]

    J. M. Lee,Introduction to Smooth Manifolds, vol. 218 of Graduate Texts in Mathematics, Springer, New York, 2 ed., 2012

    2012

  35. [42]

    A. S. Lewis,Active sets, nonsmoothness, and sensitivity, SIAM J. Optim., 13 (2002), pp. 702–725

    2002

  36. [43]

    A. S. Lewis and T. Tian,Identifiability, the KL property in metric spaces, and subgradient curves, Found. Comput. Math., 25 (2025), pp. 905–942

    2025

  37. [44]

    Li and A

    X. Li and A. Milzarek,A unified convergence theorem for stochastic optimization methods, in Advances in Neural Information Processing Systems, vol. 35, 2022, pp. 33107–33119

    2022

  38. [45]

    X. Li, A. Milzarek, and J. Qiu,Convergence of random reshuffling under the Kurdyka– Łojasiewicz Inequality, SIAM J. Optim., 33 (2023), pp. 1092–1120

    2023

  39. [46]

    Liu and Y

    J. Liu and Y. Yuan,Almost sure saddle avoidance of stochastic gradient methods without the bounded gradient assumption, arXiv preprint arXiv:2302.07862, (2023)

    2023 arXiv

  40. [47]

    H. Lu, R. M. Freund, and Y. Nesterov,Relatively smooth convex optimization by first-order methods, and applications, SIAM J. Optim., 28 (2018), pp. 333–354

    2018

  41. [48]

    Mertikopoulos, N

    P. Mertikopoulos, N. Hallak, A. Ka vis, and V. Cevher,On the almost sure convergence of stochastic gradient descent in non-convex problems, in Advances in Neural Information Processing Systems, vol. 33, 2020, pp. 1117–1128

    2020

  42. [49]

    Mishchenko, A

    K. Mishchenko, A. Khaled, and P. Richtárik,Random reshuffling: Simple analysis with vast improvements, in Advances in Neural Information Processing Systems, vol. 33, 2020

    2020

  43. [50]

    Muşat and N

    A.-A. Muşat and N. Boumal,A non-autonomous center-stable set theorem for saddle avoidance in optimization, arXiv preprint arXiv:2603.02782, (2026)

    2026 arXiv

  44. [51]

    Nagaraj, P

    D. Nagaraj, P. Jain, and P. Netrapalli,SGD without replacement: Sharper rates for general smooth convex functions, in International Conference on Machine Learning, 2019

    2019

  45. [52]

    Nedić and A

    A. Nedić and A. Ozdaglar,Distributed subgradient methods for multi-agent optimization, IEEE Trans. Automat. Control, 54 (2009), pp. 48–61

    2009

  46. [53]

    Nemirovski, A

    A. Nemirovski, A. Juditsky, G. Lan, and A. Shapiro,Robust stochastic approximation approach to stochastic programming, SIAM J. Optim., 19 (2008), pp. 1574–1609

    2008

  47. [54]

    L. M. Nguyen, Q. Tran-Dinh, D. T. Phan, P. H. Nguyen, and M. v an Dijk,A unified convergence analysis for shuffling-type gradient methods, J. Mach. Learn. Res., 22 (2021), pp. Paper No. 207, 44

    2021

  48. [55]

    Ouyang and A

    W. Ouyang and A. Milzarek,Variational properties of decomposable functions. Part I: Strict epi-calculus and applications. arXiv preprint, arXiv:2311.07267v2, 2024

    2024 arXiv

  49. [56]

    Program., 212 (2025), pp

    ,A trust region-type normal map-based semismooth Newton method for nonsmooth nonconvex composite optimization, Math. Program., 212 (2025), pp. 389–435

    2025

  50. [57]

    Panageas, G

    I. Panageas, G. Piliouras, and X. W ang,First-order methods almost always avoid saddle points: The case of vanishing step-sizes, in Advances in Neural Information Processing Systems, vol. 32, 2019

    2019

  51. [58]

    Paszke, S

    A. Paszke, S. Gross, F. Massa, A. Lerer, J. Bradbury, G. Chanan, T. Killeen, Z. Lin, N. Gimelshein, L. Antiga, et al.,Pytorch: An imperative style, high-performance deep learning library, in Advances in Neural Information Processing Systems, vol. 32, 2019. 37

    2019

  52. [59]

    Pemantle,Nonconvergence to unstable points in urn models and stochastic approximations, Ann

    R. Pemantle,Nonconvergence to unstable points in urn models and stochastic approximations, Ann. Probab., 18 (1990), pp. 698–712. [60]R. A. Poliquin and R. T. Rockafellar,Generalized Hessian properties of regularized nons- mooth functions, SIAM J. Optim., 6 (1996), pp. 1121–1137

    1990

  53. [62]

    J. Qiu, X. Li, and A. Milzarek,A new random reshuffling method for nonsmooth nonconvex finite-sum optimization, J. Mach. Learn. Res., 26 (2025), pp. Paper No. [191], 46

    2025

  54. [63]

    J. Qiu, B. Ma, and A. Milzarek,Random reshuffling with momentum: Complexity bounds and last-iterate convergence, arXiv preprint arXiv:2404.18452, (2026)

    2026 arXiv

  55. [64]

    Rajput, A

    S. Rajput, A. Gupta, and D. Papailiopoulos,Closing the convergence gap of SGD without replacement, in International Conference on Machine Learning, 2020

    2020

  56. [65]

    Robbins and S

    H. Robbins and S. Monro,A stochastic approximation method, Ann. Math. Statist., (1951), pp. 400–407

    1951

  57. [66]

    S. M. Robinson,Normal maps induced by linear transformations, Math. Oper. Res., 17 (1992), pp. 691–714

    1992

  58. [67]

    R. T. Rockafellar,Convex Analysis, vol. 28 of Princeton Mathematical Series, Princeton University Press, Princeton, NJ, 1970

    1970

  59. [68]

    R. T. Rockafellar and R. J.-B. Wets,Variational analysis, vol. 317 of Grundlehren der Mathematischen Wissenschaften, Springer-Verlag, Berlin, 1998

    1998

  60. [69]

    Safran and O

    I. Safran and O. Shamir,How good is SGD with random shuffling?, arXiv preprint arXiv:1908.00045, (2019)

    2019 arXiv

  61. [70]

    Schmidt and N

    M. Schmidt and N. L. Roux,Fast convergence of stochastic gradient descent under a strong growth condition, arXiv preprint arXiv:1308.6370, (2013)

    2013 arXiv

  62. [71]

    J. Sun, Q. Qu, and J. Wright,When are nonconvex problems not scary?, arXiv preprint arXiv:1510.06096, (2015)

    2015 arXiv

  63. [72]

    ,A geometric analysis of phase retrieval, arXiv preprint arXiv:1602.06664, (2016)

    2016 arXiv

  64. [73]

    ,Complete dictionary recovery over the sphere I: Overview and the geometric picture, IEEE Trans. Inform. Theory, 63 (2017), pp. 853–884

    2017

  65. [74]

    Sutskever, J

    I. Sutskever, J. Martens, G. Dahl, and G. Hinton,On the importance of initialization and momentum in deep learning, in Proceedings of the 30th International Conference on Machine Learning, vol. 28 of Proceedings of Machine Learning Research, PMLR, 2013, pp. 1139–1147

    2013

  66. [75]

    J. N. Tsitsiklis, D. P. Bertsekas, and M. Athans,Distributed asynchronous deterministic and stochastic gradient optimization algorithms, IEEE Trans. Automat. Control, 31 (1986), pp. 803–812

    1986

  67. [76]

    V an den Dries,Tame topology and o-minimal structures, Cambridge University Press, 1998

    L. V an den Dries,Tame topology and o-minimal structures, Cambridge University Press, 1998

    1998

  68. [77]

    V anderbauwhede,Centre Manifolds, Normal Forms and Elementary Bifurcations, Vieweg+Teubner Verlag, Wiesbaden, 1989, pp

    A. V anderbauwhede,Centre Manifolds, Normal Forms and Elementary Bifurcations, Vieweg+Teubner Verlag, Wiesbaden, 1989, pp. 89–169

    1989

  69. [78]

    V asw ani, F

    S. V asw ani, F. Bach, and M. Schmidt,Fast and faster convergence of SGD for over- parameterized models and an accelerated perceptron, in the 22nd International Conference on Artificial Intelligence and Statistics, PMLR, 2019, pp. 1195–1204

    2019

  70. [79]

    R. Vershynin,High-Dimensional Probability: An Introduction with Applications in Data Science, Cambridge Series in Statistical and Probabilistic Mathematics, Cambridge University Press, Cambridge, 2018. 38

    2018

  71. [80]

    Xiao and T

    L. Xiao and T. Zhang,A proximal stochastic gradient method with progressive variance reduction, SIAM J. Optim., 24 (2014), pp. 2057–2075

    2014

  72. [81]

    Yu and X

    H. Yu and X. Li,High probability guarantees for random reshuffling, arXiv preprint arXiv:2311.11841v3, (2023). 39

    2023 arXiv

Pith tools

Reviewed August 8, 2026 · model on record in the stance chip above.