Convergence, Sticking and Escape: Stochastic Dynamics Near Critical Points in SGD
Dmitry Dudukalov, Artem Logachov, Vladimir Lotov, Timofei Prasolov, Evgeny Prokopenko, Anton Tarasenko · 2025
Read Convergence, Sticking and Escape: Stochastic Dynamics Near Critical Points in SGD by Dmitry Dudukalov, Artem Logachov, Vladimir Lotov, Timofei Prasolov, Evgeny Prokopenko, Anton Tarasenko (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2505-18535.txt.
Introduction
Dmitry Dudukalov and co-authors analyze how stochastic gradient descent moves near critical points in a 2025 paper. The workhorse optimizer of machine learning wanders a landscape of valleys and passes, pushed by noisy gradients. When it settles, lingers, or escapes shapes what training finds.
One-dimensional landscapes are studied under both tame and wild noise. Descent reliably reaches its basin's floor unless it starts too near a peak. Near a blunt peak it can stick for a long time; near a sharp one it slips away, with calculable odds for each neighboring valley. Noise character and local geometry together script the dance.
Catalog record
| CREATOR | Dmitry Dudukalov, Artem Logachov, Vladimir Lotov, Timofei Prasolov, Evgeny Prokopenko, Anton Tarasenko |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 110 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2505-18535
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Convergence, Sticking and Escape: Stochastic Dynamics Near Critical Points in SGD Dmitry Dudukalov, Artem Logachov, Vladimir Lotov, Timofei Prasolov, Evgeny Prokopenko, Anton Tarasenko Abstract We study the convergence properties and escape dynamics of Stochastic Gradient Descent (SGD) in one-dimensional landscapes, separately considering infinite- and finite-variance noise. Our main focus is to identify the time scales on which SGD reliably moves from an initial point to the local minimum in the same “basin”. Under suitable conditions on the noise distribution, we prove that SGD converges to the basin’s minimum unless the initial point lies too close to a local maximum. In that near-maximum scenario, we show that SGD can linger for a long time in its neighborhood. For initial points near a “sharp” maximum, we show that SGD does not remain stuck there, and we provide results to estimate the probability that it will reach each of the two neighboring minima. Overall, our findings present a nuanced view of SGD’s transitions between local maxima and minima, influenced by both noise characteristics and the underlying function geometry. 1 Introduction The successful application of Stochastic Gradient Descent (SGD) to neural network training is often attributed to SGD’s ability to avoid sharp local minima and reach flat local minima ( Hochreiter and Schmidhuber, 1997 ; Keskar et al., 2016 ; Li et al., 2018 ) within a reasonable timeframe, which improves performance of the resulting neural network on the test data. However, it was demonstrated that SGD with Gaussian noise exits the basin of any local minimum in exponentially long timescales ( Freidlin et al., 1998 ) . This has led to the belief that the empirical success of SGD is due to heavy-tailed noise. The presence of heavy tails has been shown in many deep learning tasks ( Simsekli et al., 2019 ; Şimşekli et al., 2019 ; Nguyen et al., 2019a ; Mahoney and Martin, 2019 ; Garg et al., 2021 ; Srinivasan et al., 2021 ) . Simsekli et al. (2019) consider SGD as discrete approximations of Lévy driven Langevin equations and argue that the duration of time the SGD trajectory spends in each local minimum is proportional to the width of that minimum. Moreover, Wang et al. (2021) analyze SGD with truncated heavy-tailed noise and show that under appropriate time scaling sharp local minima disappear from the trajectory, leaving only flat local minima. Nevertheless, the initial location of SGD and the choice of time scale determine the system’s convergence to various local statistical equilibria, a phenomenon known as metastability ( Imkeller and Pavlyukevich, 2008 ) . Therefore, it is essential to select an appropriate amount of time for SGD to reach an effective solution to the optimization problem. The purpose of this paper is to rigorously study the two weaknesses of SGD: (1) unsuitable time scaling and (2) problematic starting points. To outline our approach to the aforementioned problems and the resulting findings, we begin by formally defining the object of study. For a given loss function f and a starting point x\in\mathbb{R} , SGD produces the following sequence: x_{k}^{\varepsilon}=x_{k-1}^{\varepsilon}-\varepsilon f^{\prime}(x_{k-1}^{\varepsilon})+\varepsilon\xi_{k},\ \ \ x_{0}^{\varepsilon}=x,\ \ \ k\in\mathbb{N}, (1) where \varepsilon>0 is the step-size of SGD (which eventually converges to zero) and \xi_{k} represents random noise with zero mean. We consider two different cases with regards to our noise (see conditions [ H 1 ] and [ H 2 ] ): either the tail-distribution is regularly varying with parameter \alpha\in(1,2), which is clearly heavy-tailed, or it has finite second moment, a scenario that includes both heavy and light tails. For a fixed \varepsilon>0 , equation ( 1 ) defines a sequence in n that either converges or oscillates, as illustrated in Figure 1 for a two-dimensional case to provide visual intuition, although our analysis focuses on the one-dimensional setting. In this paper, we study the behavior of the number of iterations n=n_{\varepsilon} as \varepsilon\to 0 in the framework of probabilistic limit theorems, under which key phenomena persist: convergence to a minimum, sticking to a critical point, and escaping from the neighborhood of a maximum. While each phenomenon is studied in a separate section, we highlight that their comparative analysis yields additional insights, and moreover, the proofs rely on a shared set of techniques. Figure 1 : Illustration of the behavior of the studied object. The Himmelblau function is considered as the objective function to be optimized. The noise \xi_{k} is generated from an isotropic distribution, with the norm \|\xi_{k}\| following a Pareto distribution with \alpha=1.2 . We initialize the SGD at the point x_{0}^{\varepsilon}=(-0.27,-0.92) , which is located in close proximity to a local maximum. The number of steps in the trajectory is the same across all four plots and equals 10^{5} . The step size varies from left to right as follows: \varepsilon=10^{-3},10^{-4},10^{-5},10^{-6}. Regarding the first phenomenon (i.e., convergence to a minimum) the condition that the number of steps is sufficiently small—characterized by H(1/\varepsilon)n_{\varepsilon}\rightarrow 0 in the regularly varying case (where H denotes the tail function of the distribution of |\xi_{1}| ) and by \varepsilon^{2}n_{\varepsilon}\rightarrow 0 when the second moment is finite—ensures that the sequence remains within the initial basin of attraction. However, if additionally \varepsilon n_{\varepsilon}\rightarrow\infty , then the sequence will have sufficient time to converge to a small neighborhood of the corresponding local minimum. We demonstrate that as \varepsilon\rightarrow 0 , the outcome of SGD, halted at time n_{\varepsilon} , converges in probability to that local minimum. Furthermore, we establish that almost sure convergence holds provided that the growth rate of n_{\varepsilon} is slightly reduced. Based on the analysis of our proofs, we conjecture that for n_{\varepsilon}>\varepsilon^{-2} , almost sure convergence does not hold, implying a restriction on the number of iterations to n_{\varepsilon}\in(\varepsilon^{-1},\varepsilon^{-2}) . This constraint is well-known in the variable step-size setting ( Robbins and Monro, 1951 ) . For the second phenomenon, if the starting point is positioned in a small neighborhood of a critical point which is not a local minimum, the convergence of the sequence to any local minima depends critically on the time scaling and the derivatives of the loss function. Hence, we first show conditions on the number of steps under which trajectory of SGD will not leave a neighborhood of the critical point. Crucial role here is played by the number of zero derivatives of the loss function which informs how flat is this critical point. In scenarios where the time scaling is sufficiently large to allow reaching local minima, an important question arises: which minimum will the sequence reach first? Given that the time scaling permits visiting only a single local minimum, only two minima are realistically achievable as the first point of convergence, possibly each with a non-zero probability. In general it is extremely difficult to answer this question analytically. In this paper we consider a simple case of a “sharp” maximum. More precisely, our loss function is a piecewise linear function in a neighborhood of such maximum. Here SGD will not “stick” to a critical point. The form of such loss function may be quite restrictive, nevertheless, such functions do appear in optimization literature ( Leenaerts and Van Bokhoven, 2013 ) . We consider the limiting probability of reaching the nearest local minimum on the right or