Almost Sure Convergence of Stochastic Gradient Methods under Gradient Domination
Authors: Simon Weissmann
Sara Klein
Waïss Azizian
Leif Döring
Venue: Accepted by TMLR ()

Abstract: Stochastic gradient methods are among the most important algorithms in training machine learning problems. While classical assumptions such as strong convexity allow a simple analysis they are rarely satisfied in applications. In recent years, global and local gradient domination properties have shown to be a more realistic replacement of strong convexity. They were proved to hold in diverse settings such as (simple) policy gradient methods in reinforcement learning and training of deep neural networks with analytic activation functions. We prove almost sure convergence rates $f(X_n)-f^*\in o\big( n^{-\frac{1}{4\beta-1}+\epsilon}\big)$ of the last iterate for stochastic gradient descent (with and without momentum) under global and local $\beta$-gradient domination assumptions. The almost sure rates get arbitrarily close to recent rates in expectation. Finally, we demonstrate how to apply our results to the training task in both supervised and reinforcement learning.

Published in Transactions on Machine Learning Research (4/2025)
Almost Sure Convergence of Stochastic Gradient Methods under Gradient Domination
Simon Weissmann" Institute of Mathematics University of Mannkeim 68138 Monnheim, Germany
simon. immo..vrismmmmmuuuimmmnniniinti
Sara Klein*
sar..lein@umiimmmmhein
Institute of Mathematics University of Mannheim 68138 Mannkeim, Germany
Waiss Azizian
aziss Gumiv www.eenrrennobeeellirr.e.ee alapooble-apps.ff
Univ. Grenoble Alpes, CNRS Inria, Crenoble INP, LJK 38000 Grenoble, France
Leif Döring
lef.dderriag@@ummmmmnneii....m.
Institute of Mathematics University of Mannheim 68138 Mannkeōm, Germany
Reviewed on OpenReview: https: // openreview. net/ forum? id= 0TumN8m223
Abstract
Stochastic gradient methods are among the most important algorithms in training machine learning problems. While classical assumptions such as strong convexity allow a simple analysis they are rarely satisfied applications. In recent years, global and local gradient domination properties have shown to be a more realistic replacement strong convexity, They were proved hold in diverse settings such as (simple) policy gradient methods in reinforcement learning and training of deep neural networks with analytic activation functions. We prove almost. sure convergence rates f(X,,) f E o(n" (((n===*(()) of the last iterate for stochastic gradient descent (with and without momentum) under global and local B-gradient domination assumptions. The almost sure rates get arbitrarily close to recent rates in expectation. Finally, we demonstrate how to apply our results to the training task in both supervised and reinforcement learning.
1 Introduction
First-order methods to minimize an objective function f have played central role in the success machine learning. This is accompanied by growing interest in convergence statements particularly for stochastic gradient methods in different settings. To ensure convergence to the global optimum some kind of convexity assumption on the objective function is required. Especially in machine learning problems the standard
These authors contributed equally this work.

---

Published in Transactions on Machine Learning Research (4/2025)
(strong) convexity assumption is nearly never fulfilled. However, it is well known that achieving convergence towards global optima is still possible under weaker assumption, namely under the gradient domination property, often referred to as Dolyak-Lojasiewiccs (PL))inequalitty (Polyak) 1963) Also in reinforcement learning, multiple results have shown that the objective function for policy gradient methods, under specific paramelrizatiinn fulfills weak type of gradient domination and therefore provably achieves convergence towards the global optimum (Mei et al. 2020 2021 Fatkhullin et al.) 2023 Klein et al., 2024p. Improving the understanding of rates and optimal step size choices for stochastic first order methods is of significant interest. for the machine learning and reinforcement learning community. Many classical results identify convergence rates for the expected error ( - f*] In the present article, we focus on almost sure convergence rates for the error f(X,) - f* in stochastic gradient schemes under weak gradient domination. The contribution of this work is as follows:
(i) Under global gradient domination with parameter 3 (on the entire function domain), we prove that the last iterate of stochastic gradient descent (SGD) and stochastic heavy ball (SHB) converge almost surely and in expectation towards the global optimum with rate arbitrarily close to o(n o The almost sure and expectation rates of convergence that we obtain depend on the gradient domination parameter B and are the same for both algorithms and convergence types. For SGD this rate is arbitrarily close to the tight upper bound known in expectation (Fatkhullin et al. 2022), while the almost sure convergence rate is new for the (weak) gradient domination assumption (see Theorem 4.1 and discussion afterwards). To the best of our knowledge for SHB this is the first convergence result lowards global optima under (weak) gradient domination, for both almost sure convergence and convergence in expectation (see Theorem 4.2
(ii) We consider the case where the gradient domination property holds only locally, either around stationary points or around global minima. We provide the first local convergence rates under these settings: we prove that SGD remains within the good local region with high probability and, conditioned on this event, we obtain converges rates almost surely and in expectation (see Theorem 5.1 and Theorem 5.2
(iii)
Our local setting covers generic classes of functions. In particular, we demonstrate that it encompasses the training lask of deep neural networks with analytic activation functions in supervised learning. Our result illustrates that the iterates of SGD are likely to become trapped in areas of local minima when the step size small. We verify under mild conditions, that SGD converges to local minima with given convergence speed (see Corollary 6.1
(iv) Finally, we derive novel convergence results for policy gradient methods in reinforcement learning. We show that local gradient domination holds around the global optimum for the softmax parametrization resulting in the first local convergence rate for stochastic policy gradient with arbitrary batch-size (see Corollary 7.2).
We sunmarize the contributions of this paper in Table D These findings are also illustrated in numerical toy experiment in Appendix B where we have implemented SGD and SHB for monomials with increasing degree.
1.1 Literature Review and Classification of our Contribution
The roots of stochastic gradient methods trace back to Robbins and Monro (1951). Since then, various variants of SGD have been established as fundamental algorithms for optimizing complex models in the realm of machine learning. We refer to Bottou et al. (2018) and Garrigos and Gower (224) for a detailed overview.
We start the review with the literature deriving convergence rates in expectation for SGD. Under the JuvexityyPolyak assumptions of smoothness and (strong) convexity PPlyyk (1987) : Moulines and Bach (2011); ys Nguyen et al.
(2018); Wang et al.] (2021): : Liu et al. (2023) studied convergence rates towards global optima. Morcover, many articles additionally analyze the non-convex case and prove convergence rates for the gradient norm
towards zero (Ghadimi and Lan 2013 Li et al.] 2023 Liu et. al. 2023 Nguyen et al. 2023
2

---

Published in Transactions on Machine Learning Research (4/2025)
Table 1: Summary of known and new results. Table presents convergence rates for tuned step size (e 0 arbitrarily small). Dom.: gradient domination holds locally or globally; local*; additional assumption on "/1 required and results holds only locally. almost surely; E: in expectation. Ref.: for some cited results minor adjustments necessary.
Step size
Rate
Dom.
Algo.
Conv.
Ref.
Theorem 4.1
a.8.
Liu and uua 2022
Thm. 1)
SGD
Theorem
ii;
E
Khaled and Richtárik (2023
Thm. 3)
global
Theerem
4.2
(1);
a.8.
Liu and Yuan 2002
Thm. 2)
/ (n o (n
SHB
Theorem
4.2
[ii];
E
Liang ct al.
2023
Thm. 4.3)
Theorem
5.1
[ū];
a.8.
Theorem
5.2
(ii)
local*
SGD
Thcorem
5.1 (ii); Theorem 5.2 (ii)):
E
Mertikopoulos et al.
2020 Thm. 4)
a.s.
Theorem
4.1
SGD
Theorem
[ii];
global
E
Fatkhullin et al.
2022
Cor. 1)
a.s.
Thcorem
4.2
(i)
(/,1/0 1ll (n ( )o (n x5-
---1
SHB
E
Thcorem 4.2
(ii)
Theorem
a.s.
Theorem
local*
SGD
Theorem
111
E
Theorem
5.2
111
Notably, several other results regarding convergence of SGD towards global optima have been established under the gradient domination setting (Karimi et al. 2016). Bassily et al. (2018): Liu et al. (2022) demonstrate exponential convergence rates expectation in the overparameterized setting under strong gradient domina- tion. See also Madden et al. (2024), where high-probability convergence bounds are shown using the (str) gradient domination property. Further high-probabiln bounds on the approximation error are provided in Scaman et al. (2022) under generalized gradient domination property, the so-called Eoparable-Eojasiewiic assumption, fulfilled by smooth neural networks. In Lei et al. (2020) also strong gradient domination is assumed, where the smoothness assumption is weakened through a-Hölder continuity, achieving rate of ((L)) in expectation. The Equation (ABC) condition is introduced in Khaled and Richtárik (2023) and where ) convergence shown under strong gradient domination. Furthermore, Fatkhullin et al. 2022 and Fontaine et al. (2021) consider generalivations of gradient domination that include our definition as a special case. They derive convergence rates expectation which we encompass with our result and extend to almost sure convergence (see also the discussion behind Theorem 4.1 Finally, Masiha et. al. (2024) established both upper and lower bounds for projected gradient descent under gradient domination.
All the results mentioned so far consider convergence in expectation or high-probability bounds, although originally, motivated by Robbins and Siegmund (971), research commencce with the quest for almost sure convergence rates for gradient methods. recent years, Sebbouh et al. (2021) and, building upon it, Liu and Yuan (022) derive almost sure convergence rates towards global optima under convexity for SGD and SHB. In addition, Liu and Yuan (2022) study SHB and Nesterov acceleration under PL. Returning the attention back to SGD with respect to gradient domination also some almost convergence results have been
3

---

Published in Transactions on Machine Learning Research (4/2025)
established. As an extension to the PL-type gradient domination, in Chouzenoux et al. 2023 the so-called KT. property is assumed, which contains gradient domination as a special case. The authors demonstrate almost sure convergence to a critical point, though without a rate. To conclude, to the best of our knowledge the derived almost sure convergence rate under gradient domination in Theorem 4.1 is novel.
Next, we want to provide further insights to the literature regarding SHB. In the realm of momentum methods, Polyak's Heavy-Ball Method (HBM) (Polyak) [964] and Nesterov's accelerated gradient method
(Nesterov] 1983) stand out as foundational contribution. The authors of Gadat et al. (2018) provide a
detailed description of the stochastic formulation of HBM and establish almost sure convergence but without
giving a rate. In Yang et al. (2016); Orvicto et al. (020);; Yan et al. (2018); Mai and Johansson (2220) Zhou
ett al. (2000) convergence rates in expectation are shown in (strongly) convex and non-convex settings, where the non-convex analysis covers convergence of the norm of the gradient. Convergence of momentum methods
under the strong gradient domination property and lincar convergence due to an overparametrized machine
learning setting is shown in Gess and Kassing (2023). Liang et al. (2023) determine O(2) convergence rate for SHB under strong gradient domination. Our main result for SHB presented in Theorem 4.2 describes almost sure convergence and convergence in expectation under global gradient domination. Both result are quantified with a given rate of convergence.
In the following, we aim to differentiate our local convergence analysis from existing results in the literature. There has been a lot of effort to derive local convergence guarantees for stochastic first order methods. In Dereich and Kassing (2024) almost sure convergence of SGD to a stationary point under the local gradient domination (for x²) demonstrated, provided that the process (Xx)) remains local, albeit without a rate. A local analysis of SGD towards minima without any gradient domination assumption is presented in Fehrman et al. 2020). Instead, rank assumption is imposed on the Hessian, and mini-batches, along with resampling, are leveraged to ensure convergence to the global optimum with high probability. The resulting rate does not converge to zero and requires an increasing batch size. Finally, under the global Lipschitz assumption on the objective, it can be verified that SGD almost surely converges to a stationary point as demonstrated by Mertikopoulos el al. (2020). In the same work the authors derive a local convergence analysis under local strong convexity. Our analysis in Section 5 builds upon Mertikopoulos et al.] (2020) and generalizes their results to the local gradient domination property. In our analysis we distinguish the cases where the local gradient domination property holds in neighbourhood of local minimum or in the neighbourhood of the global optimum respectively. Finally, we would like to acknowledge that related results have been independently obtained in the recent preprint Qiu et al. (024)).
For the application in the training of DNNs, it is worth noting that local convergence of SGD has been analyzed under stronger variants of gradient domination by Wootowytsch (2023); An and Lu (2024). Due to the stronger form of gradient domination, specific sub-classes of DNNs need to be considered to verify these assumptions whereas our result is only constrained to analytic activation functions. Under the machine learning noise conditions in Wojtowytsch 2023 convergence toward zero loss with high probability is shown, provided that the initial loss is sufficiently small. In contrast, An and Lu (2024) demonstrate convergence towards zero loss under initialization in a local (strong) Lojasiewicz region. Indeed, one can construct DNNs
satisfying the latter condition (Chatterjee 2022).
For the application in reinforcement lcarning, recent results showed that choosing the tabular softmax parametrization in policy gradient (PG) algorithms results in objective functions which fulfill a non-uniform gradient domination property (Mei et al.) 2020: Yuan et al. 2022 Klein et al., 2024]. While convergence of
PG for exact gradients is well understood, convergence rates for stochastic PG are rare and mostly require
very large batch sizes (Ding et al. 2022 Klein et al.) 2024 Ding et al. 2023 It is noteworthy that a similar
local analysis for stochastic policy gradient under entropy regularization is presented in Ding et al. (2023) Their local result is also based on MMetikopoulos et al. (020)) but requires an increasing batch size sequence to obtain cooveenneeee towards the regularized optimun with high probability. In contrast, we consider both the unregularized and entropy regularized setting and observe that one can also achieve convergence arbitrarily close to o( ( without the need for increasing batch size. Moreover, the local convergence occurs almost surely on an event with high probability.
4

---

Published in Transactions on Machine Learning Research (4/2025)
2 Mathematical Background Optimization under Gradient Domination
We consider the problem of solving the minimization problem of the form
min f(x),
(1)
EER
where f: IR + denotes the objective function of interest. Throughout this paper we assume that the objective function is bounded from below by f = inf f(x) > -00 and satisfies the classical L-smoothness assumption (cither locally or globally): Assumption 2.1. The objective function I IR is differentiable and the gradient V is
(i) globally L-Lipschitz continuous, i.. there exists > 0 such that [[V Vf(iil & L|| - yll for all x; y E IR..
(ii) locally L-Lipschitz continuous, i.c. for all R > 0 there exists L(R) > 0 such that [Vv vf(vil L(Ri|| -----111 yll for all 2,y E Rd with (z]. lul S R.
Using (global) L-smoothness, the descent lemina provides the inequality
L f S f(x) + (VI(x).y x) lyy x||
(2)
which is a fundamental instrument analyze first order optimization methods. As motivation recall the iterative update generated by gradient descent with constant step size y S +. i.c.
In+1 = In - >V)()))
#1 Rd
Applying Equation 2 and the itcration scheme yields the itcrative descent property
[f(en+1) - f*) (f(x.) f f-1
2 2 (
Under further strong convexity assumption it is classical to show that the gradient deseent algorithm converges to global minimum at a linear rate. In order to derive convergence rate without assuming convexity of J one can use dominating relations of the gradient fz() with respect to the optimality gap f(x) - f*. particular, as demonstrated in Karimi al. (2016) it is nowadays well-known that gradient descent converges linearly under the PL-condition which assumes that there exists c such that for all æ E Fd there holds
[V cf(()) 8
with exponent , 1/2 Polyak 1963). It is worthwhile to emphasize that Equation (3) is weaker than strong convexity, the classical textbook assumption that fails for many applications. Under the PI-condition the iterative descent property can be written as recursion:
-((++))-11 (1 - 29 (1-2)) (f(wm)
In fact, there are many works analyzing (stochastic) first order methods under the weaker Fojasiewicz condition formulated in (local) areas around stationary points x" and exponents [1/2, Lee et al. (016);;
Fatkhullin et al. (0022) Scaman et al. (2022); Wilson et al. (019). For general [1/2, 1] the recursive descent property reads as
(f( - l4] [f(x)) - fr]
2 (f(an) -
2
leading to sub-linear convergence for 1/2.
For the purpose of our analysis of stochastic gradient methods, we collect the following types of global and local gradient domination properties.
5

---

Published in Transactions on Machine Learning Research (4/2025)
Definition 2.2. Let f :R R be continuously differentiable with f inf f(x) > -00.
We say that satisfies the global gradient domination property with parameter A 12, 1] there exists c> 0 such that for all E IR it holds true that
|V[(())] 2 200l22///0/ (f(x)-
2. Let x² E Rd be stationary point, i.c. Vf(x=) O. We say that satisfies local gradient domination
property in at with parameter 8.r E 1 if there exist radius r=" > 0 and constant Cz" > 0 such that
|V/('>]| 2 cx ((x)))
(4)
for all E (x") fy R =|,=* - yl1 S }. We say that f satisfies a local gradient domination property in f" with paramcter B E 1] if there exist a radius r > O and a constant c > 0 such that
(x*)
IV 2 -(f
for all x E B
R : f(
Remark 2.3. If B = 2: we will call the gradient domination strong since is implied by strong convexity. In contrast, we call the gradient domination weak for (5. ( 1]. Moreover, note that for the local gradient domination property in x" the parameters and may depend on x². Furthermore, emphasize that for the definition of the local gradient domination in f we do not require the existence of x² E arg min [(x).
The PL-condition mentioned above is special case of the general global gradient domination property for B = In Lojasiewicz/ (1965) it has been demonstrated that all analytic functions satisfy the local gradient domination property, emphasizing the particular significance of the local case. Further, it has been proved that all overparametrized neural networks fulfill the local gradient domination property (Liu et al. 2022
See also Madden et al. [024]; Dereich and Kassing 2024]; Frei and Gu (2021) and references therein for the
application of (strong) gradient domination to (deep) neural networks. In Fatkhullin et al. (2022) Attouch
et al. [2010) Bolte al.
20144] Zhou et al. (2018) examples of functions are discussed that fulfill the (weak)
gradient domination property. For instance, one-dimensional monomials f(x) = |x P. p.p. 2, satisfy the weak global gradient domination property with 3 = p-1, We refer to Fatkhullin et al. (2022 Appendix A) for longer list of globally gradient dominated functions including convex and non-convex functions. Notably, in reinforcement. learning it is known that the tabular max parametrization leads to a parametrized value function that satisfies the so-called 'non-uniform' PT-inequality (Mei et al.) 2020 2021 Klein et al. 2024). In Section 7 we will show how this non-uniform gradient domination implies local gradient domination in f" This renders our local analysis of stochastic gradient methods specifically applicable RL. As mentioned earlier, since every analytic function already satisfies local gradient domination, we expect that the local analysis can encompass further parametrizations, such as neural networks.
p
2.1 Assumptions the Stochastic First Order Oracle
Let PP) be underlying probability space. In general, we assume that access the exact gradient V fz) through a stochastic first order oracle V Rd x M + Rdd defined by
Vax, ()) = V fz(x) + Z m),
x E m mEM,
(5)
where (M, is a measurable space, Z Rd x M + Rd is a state dependent B(R") @ MM/B(R")-eaaurrlll) mapping describing the error to the exact gradient Vf. The stochastic gradient evaluation is then modelled through (ax, {), where the random variable Ç Ω M independent of the state x E Rd. We make the following unbiasedness and second moment assumption:
Assumption 2.4. We assume that for each E Rd it holds that
B[Z(x,() == / Z(x, ((w))dP(w)
and there exist non-negative constants A, B and C such that for all x E Rd it holds that (1)111 < A(f(x) + B[V C.
(ABC)

---

Published in Transactions on Machine Learning Research (4/2025)
It is worth noting that the Equation |BCC assumption is generalization of the bounded variance assumption that appears for A = B = 0. It was introduced by [Khaled and Richtárik (2023) as expected smoothness condition and shown to be the weakest assumption among many others.
2.2 Stochastic Gradient Methods
The following two classical optimization algorithms will be analyzed in this article. Both algorithms are described as discrete time stochastic process (Xn)neN driven by noisy gradient evaluations in Equation (5) In each iteration, we assume that the stochastic first order oracle accessed through the evaluation Sn+1 which is a copy of Ç independent from the current state Xn.
The stochastic gradient descent. (SGD) scheme given by the stochastic update
Xat1 = X, The V(Xn: Sn+1),
where X1 a Rd-valued random vector which denotes the initial state. keep the notation simple, we will introduce (Xx) := ((X,: Sn+1) suppressing the explicit noise representation through (Gn)neN in the following. The iterative update formula then reads
Xa+1 = Xn Th (Xn))
(SGD)
The iterative scheme of stochastic heavy ball (SHB) is defined by
X X "/ Vn (X,) v(x, Xn-1).
(SHB)
with initial Rd-valued random vector X1. The additional summand is called the momentun term with momentum parameter E (0.1). 1). In both cases, (7m)nER denotes a sequence of positive step sizes and we denote by (Fa)nen the natural filtration induced by the process (Xn)neN. Note that we adopt the convention where the set of natural numbers N refers to the positive integers excluding zero. When necessary, we explicitly define No N U (0}.
Example 2.5 (Expected risk minimization). In order give more insights into the considered setting of our stochastic first order oracle we formulate specific one based on expected risk minimization. In expected risk minimization we interested in minimizing objective function of the form
f(x) B[F(2, / F(x, ((w)) dIP(w)
where F: Rd x M + IR is B(R)) @ BM In notation the stochastic first order oracle then takes the form
((x()) = Vf(z) + (V.F(I, = V.F(x))
and the iterative update of SGD reads
X = X, - V V.F(Xng Sn+1)
with a sequence of independent and identically distributed (Sn). The itcrative scheme of SHB can be written in similar way. Note that this scenario also includes empirical risk minimization where the objective function takes finite sum form, with Ç u((1....,N))
N M f(x) N
= <)]
Exemplifying the SGD method, we illustrate the typical steps of the convergence analysis for first-order optimization methods. First, the smoothness of the function f is exploited by applying the descent inequality Equation 2 to the itcration scheme and then applying conditional expectations,
Lnd 2
(ff(X Ful S f(x)) V/ [Vxx( + Va [.).

---

Published in Transactions on Machine Learning Research (4/2025)
Next, f is subtracted on both sides and the variance term of the stochastic gradient is controlled through the Equation |BCC] condition:
+x F... < (1+
LAni 2
)
(f(Xn) - -m
BL 2
LC
(6)
Without further assumptions this incquality now be used to show that the gradient Vf(X,) converges almost surely to zero. In order to obtain convergence towards a global optimum additional assumptions are needed. For instance, it is sufficient to incorporate the global gradient domination property defined in Definition 2.2 which yields an iterative inequality of the form
LA B[((X.+1) Fal < (1 -1-22 2 (U(X)) - 10--111-1 BL 2
(() LC 2
(7)
Typically, the expectation is taken on both sides of the inequality to derive a convergence rate in expectation by working with recursive inequalities. In this article we push the argument further. We combine smoothness and gradient domination with variant of the Robbins- -Siggmudd Theorem (see Lemma A.2 to derive almost sure convergence rates.
3 Preliminary Discussion on Super-Martingale Convergence Rates
In the previous section, we have sketched how to combine the global gradient domination property with smoothness to derive a recursive inequality of the form
E[Yn+1 Ful < (1 + crr)), 027 X2 + can
where Y, :- f(X,) f For analysing these inequalities, we must deal separately with the strong gradient domination case (8 = } and the weak gradient domination case (3 > 1)) to avoid divisions by zero. For the former case the recursive incquality simplifics, whereas a more complex analysis is required for the latter. To establish almost sure convergence rates we employ convergence lemmaa for super-martingal based on the Robbins- Robbins-Sigmund Theorem. This methodology has been introduced in [Sebouuh al. (2021) and further utilized in Liu and Yuan (2022) to analyze SGD and SHB under (strong) convexity. It is noteworthy to mention that their analysis is under the similar noise assumption formulated in Assumption 2.4
f³.
In the following, we illustrate how to extend the arguments to convergence under the global gradient domination property. Here is our super-martingale result that also encompasses Liu and Yuan 2022 Lemma 1) when B = 1/2 for completeness:
Lemma 3.1. Let (Yn)neN be sequence of non-negative random variables on an underlying probability space (2,F,P) PP) with nalural filtration (Fu)neN and suppose there erists 3 E 12, 1], cr, ea 2 0 and c2 > O such that
E[ Fa] S (1 cn 2n y28 + carh.
for all n 2 1, where Tn + for some fixed 0 E (). Then, for any
(axx (2 20,
042 26-12
: B (b,1)
E (2- 20, 1)
: :
(Ya)ne vanishes almost surely with Y, E (1,ta)-
The proof of this lemma is based on the well-known Robbins- Sabbins-Siegmund theorem (Robbins and Siegmund 1971 Theorem 1) and is provided in full detail in Appendix C
4 Convergence for Global Gradient Domination Property
In this part of the paper, we provide our global convergence result in a non-convex and globally smooth setting. Combining the recursive inequality Equation with the super-martingale convergence result from Lemma 3.1 leads to the following theorem.
8

---

Published in Transactions on Machine Learning Research (4/2025)
Theorem 4.1. Suppose Assumption 2.1 and Assumption 2.4 fulfilled and let f satisfy the global Denole by (Xu)eeN the sequence generaled For any
gradient dominalion properly from Definition 2. with 3 E
3.
by Equation [SD] using step size nn θ
with E 2
1).
max (2 20, 28
0+28-22
),1]
3 ( 1]
E
(2 - (2-00,1)
5 =
it holds that
1
(i) f(Xm) - EO nd- a.s., and (ii) -[ - -
n211
Proof. Recall, in Section
we derived Equation
E[f(Xn+1) - fr Ful < (1
LA (J(Xn)- (7m 2
B (J(()) (+)(0 + LC1
2
which will be the basis of the proof of Theorem 4.1
We treat again both cases for B == and 8 E (5) separately:
6 In this case, Equation 7 results in the super- mapre-martinnale inequality
LA
BL
Yn + LC
E E
Ful (1+
nno²
in
2
with Yn = f(x,)) f- By the choice of 7n there exists N > 0 and a constant ē > 0 such that nnc
LA- 2
BL 2 2 2% for all n 2 N. Thus,
LC
E| Fxl (1-87))
Yn ),)),,
87h)
2
for all n 2 N. Then, claim (i) follows by applying Lemma 3.1 with 0, 2, To prove claim (ii) we multiply (n + 1)"-" on both sides and take the expectation. It follows that
LC 2 and f 2
LC
[n + 1)(1-)) y < (1 - 67m) + "B +
(n + 1)
LC
$ (1 (1 1 + (1 - n)n E[Yy] +
(n + 1) 1- 7n2
2
Zon + 1-n ő(1 - 7)7h
LC
B[ +
(n + 1/
n
2
As On +(+)) we obtain that ε% the dominating term. Hence, there exists constant č > 0 and Ñ such that Ey 1-n al a(1a))a > čr for all 2 N. Thus, for all 2 N
LC (n 7
Ei n 1 (1 217%) n "[Y,
We apply Lemma A.3 with w. - On = 2n and bn = + 1> and obtain that n EY,) -
for n + 0o which yields claim (ii). Note that Σn bn < oo as 1 - 77 < 29 for (2 20, 1).
3 E (2, 1]: In this case, Equation results in the super- super-martingal. incquality
E|a+t1 Ful S (1+
LA 2
Yn - (7m
BL
LC 2y23
2
n
2
9

---

Published in Transactions on Machine Learning Research (4/2025)
I". with y, = =((x)) -" By the choice of "/ there exists 02 > 0 and N₁ > such that c2 for all n 2 N1:
BLe 2 mn7n
LA Y, -22 Y28
L2 + LCn
E EI n+1
Frl (1+
We deduce claim (i) from Lemma 3.1 with C1 = LA
2 C2 = = C3 = LC and B E (2.
For claim (ii) we firstly proceed as the proof of Lemma 3.1 Therefore, one can choose the auxiliary
parameter 1 <<g q and find constants ca, C3, N1 0 such that for all 2 N1 by EquationEquation (22 we
have
1 E[(n + 1)1 F S n "y ca noo
28g-1 20-1
n "y + cs(n + (7m + 77))
Next, we take the expectation to obtain
1
28q-1 20-1
E[ + hY S (1 Ca
"Ynl + cscn ( + 172
+ +mm)
2
1200
for all n 2 N1, implying that Un E(n - nYal
as + 0o by Lemma A.3
Note that we have chosen 8, n7 < oc, and (n < oo (see
239-1 0c. Σn (n + 1) 10 7m -/-
and q as in Lemma 3.1 such that Σn 2n अह
Equation
23
Equation [2]] and Equation
25 Therefore, the assumptions of Lemma A.3 are met.
To the best of our knowledge our theorem presonts the first convergence rate for SGD under weak gradient domination with respect to almost sure convergence.
It natural ask which 0 leads to the best convergence rate. Optimizing for n yields an optimal choice 29 to achieve the best possible rate of convergence. This specific choice yields lower bound of the A = 4
ক and therefore almost sure convergence of the form of + where p is arbitrarily close to - (see also Table 1. We emphasize that the rate we obtain is arbitrarily
interval given by 2 20
#+23-2
23-1
close to the one obtained in Fontaine et al. (2021 Fatkhullin et al. (2022) in expectation. According to Fatkhullin et al. 2022 Prop. 2) the rate attained, if the recursive inequality is indeed an equality.
Roughly speaking, our result guarantees a faster convergence rate for 'stronger' gradient domination properties 0+28-2 for 3 sufficiently close to our result is consistent the one (i.e. for smaller 3). Indeed, as 2 20 > 23-1
presented in Liu and Yuan 2002 Thm. 1) by replacing the p-strongly convex assumption with the strong gradient domination property with / =
Similar arguments can be used derive almost sure convergence rates for SHB under global gradient domination:
Theorem 4.2. Suppose Assumption 2.1 and Assumption 2.4 are fulfilled and let f satisfy the global gradient domination property from Definition by Equation SHBB using step size in
2. with 3 E 1 1. Denote by (Xn)neN the sequence generated For any
- θ for 0 E [ 1).
max 20, 0+29 0429-2).1) ).1) 28-1
: (
E
- (2-20,1) 1)
: : =
it holds that
1 n-ー
(i) f(Xn) - f fre Eo ( a.s., and (ii) (lf((x)-ffe)
For the proof of Theorem definitions
4.2 recall the definition of the iteration scheme Equation
SHB
Using the following
Zn X,, + 1-
W Wn X, -x
(8)
10

---

Published in Transactions on Machine Learning Research (4/2025)
one can derive the iterative evolution
W NW,, 7/n (X,,)
(9)
In v(Xn).
Zn+1 Zn
(10)
1-
The first equation follows directly from the definition of Wn. For the second equation we compute
zut1 Xu+1 + 1+ Wat1 (1 +
1 - )x++1
V
V Xn
1-
1 - V/ X -
i/n
V(Xn) + --
-Xx= - -Xn-1) (Xn
V
1
Zn In V v(Xn).
We will utilize these auxiliary variables in the proof.
Proof of Theorem 4-2 The proof begins as in the proof of Theorem 2 in Liu and Yuan (2022). Using only
L-smoothness and assumption Equation (ABC), they show that for any og (0, r-2), À E (v, 1) there exist
constants C1. C22 C4 > 0 such that choosing the step size In ~ no for some E (2, 1) results in [Lu and Yuan
2022 Equation (21))
[lf( (
(11)
$ (1
(2n)) +cr7
for all n 2 N and some N > sufficiently large. Next, we apply the global gradient domination property for any 8 E 12 1] to derive
B[S(?n+1) - 5r +||W++
(12)
s (1+ f²) - -Zx) fa)28 + +(+ (d++)nilll,,ll + tomn.
For the remaining proof, we denote On = f(Zm) - f Similar as before, we treat both cases for = and
f E ( 1] scparately:
3 : Instead of p-strong convexity use the gradient domination inequality [[
cfs f()));
the same inequality is implied by strong convexity using = μ. Then, Claim (i) follows using the same proof as Liu and Yuan 2022 Thm. 2b)). Note that the inequality
1
[f(=)) S f(x)
(13)
2L
used in the last step only requires the L-smoothness assumption Nesterov 2004 Sec. 1.2.3).
For Claim (ii) we consider Equation
12 which simplifies for 3 = to
B[Qn+1+ ||W++1l* 2 F, S (1 en cc37m) Qn + (A+ -2 c.
By the choice of 7n there exists N > and ē 02 > 0, such that cos - an 2 ê17n and À + c2n s 82% for all > N. Hence, for n N
E[Q + [ Fr) < (1 877 Qn, + +1 (1 82 W 2 + c
< (1 min 02)) (Qn + ||,, + c47
Let 6 = min(E1, ]2), multiply by (n + 1)'- on both sides and use Equation
17 to obtain for n 2
[i + 1) 1- (Qu+1+ + ([*) Fr
< (n + 1) 11 )27) (Q,, + |W, 1?2) + enni (1)
s (n 1- (1 - 7)m (1 - (z) (Q, + 13) + (nn 11)
1- cs T)
n 1 (Q. ||W,|1?) +c472nn 1)2-9.
C5 n
n
11

---

Published in Transactions on Machine Learning Research (4/2025)
Taking expectation and using that there exists és > 0 and N > N such that cs 1-n + os(l-n) 2 05 Cn7 we have for all n 2 N
B[(n + 1)1-3 (Qn+1 + s (1 )57m) E [n' - (Qn + ||
(| [[]] + can 1)2
Note that Σn 7 (n+ + 1) < do because v E (2- 20, 1) implies 1- < 20 which yields that E [n- (Qn + [|3]] + To finish the proof, one can derive
We can apply Lemma A.3
Hence, E[(Q, || []]] E ((,,t,)
f(xm) - S Qn \/(22)1 + 22 + Tu²
2(1 w) W 11?
(14)
To derive this equation, recall that Zn - xx = -- Wn, such that by L-smoothness we obtain
L
- V - (V[((,)),) + L
(())) - Zn) + = -
2(1 - u[]= Ww.l
Next, apply Cauchy-Schwarz and Young's incquality to obtain
v²
Lu²
ff f" -++ + |f(2))| +
|W 2 +
I| 113
2(1 v)z
2(1 4)
Using inequality Equation
13
get almost surely
2 T.²
v)2 Wm, 1 S (1+ L) max (I. 2(1 w)2 (1,2(1-17) )(hn +/Wxl13)
D²
-M (1++) L)Qn
(15)
implying that B[(f(x)) [r] ( which proves Claim (ii).
B (2. 1]: For Claim (i), note that in Equation
12 X 1, such that
E[Qn+1 [| 12 Fx 5 (1+ + (1 -2 I 22 c4
s (1+ + max(ci, (2))) + ||,, (12) + cosTr (Qn + || 12)20 + c.nh
By Lemma 3.1 we obtain that Qn + |Wa112 = f(Zm) f [..ll E o ( for all 1 E
(max{2- 20,
0+28 0+28-2). (..1) 1). We apply the incquality in Equation (15) conclude that also f(X,) f e
29
(nt.)) for all n E (max 20, - ).11 This proves Claim (i).
For Claim (ii), we again use the trtckkk from Lemma 3.1 Equation
12
For < < we have that
E[Qn+1+ + 11 < (1 + cn - - c0 + 0os7 (7% Qn - Q20) - (A + (2+ c
Now with Equation 20 in Lemma 3.1
there exists 03 2 0 such that
28n-1
E[Qn+1 + 1| Fr) < (1 + ci 2 o033g) Qn 637m
(A 1 (2+ can
By the choice of 7a there exists ह > and N > such that e en2 00378 2 2n and + 02 S 717g for all
n 2 N. Thus, for all 2 N,
28g-1
E[Qu+1 W [r) < (Q. + [W,ll))
max ca) (Th"
+ +
12

---

Published in Transactions on Machine Learning Research (4/2025)
For max(cz, ca) =: 02 multiply on both sides with (n + 1)1=" and take the expectation to obtain for n 2 N
B[(n + 1)=-1 (Qn+1 ||
- (n + 1)² 1)=-1(1 - [( + ||,, ||
22 + 1)
'n
20-1
m
28g
s (n 1 n)) -
|| |3] ē2( 1)²-
7m
+
7
1-n
2 (1 7)?
Ein (Q |[,]
n
2
( + 1)²-1
7/
Next, there exists N N and ēσ > 0 such that for all n 2 N
234-1
El(n + 1)t-9 (Qn+1 + | [2]] s (1
+ I[, + 82(n++ + 1)²
23-1
+ + 2
289-1 T/-
From the proof of Lemma 3.1 we choose the auxiliary parameter g such that ,,, (n+1)
7/1
+ 9/2
<
00
(see Equation 24 and Equation 25 ). By applying again Lemma A.3 we obtain B[n1-1(Q, + 1|W, [13)
0.
Le. EIQ, + |IW E ol -.) Finally, Claim (ii) follows again by Equation
115
To the best of our knowledge, result gives the first convergence proof of SHB to global optima under weak gradient domination, with rates for almost sure convergence and convergence of expectations. The resulting convergence rate using the optimized step size are summarized in Table In the strong gradient domination setting our rate in expectation gets arbitrarily close to the )( convergence obtained in Liang et al. 20233 It is noteworthy that the utilization of SHB our analysis does not yield a superior convergence rate compared to SGD, This arises from the proof technique and aligns with the findings in [iu and Yuan 22022 Sebbouh et al. (2021) where the authors similarly achieve acceleration. In general, for deterministic scttings acceleration of gradient methods
achieve improvements of convergence rates (Wilson et al. 2019) Though in the special case of gradient domination with B 2 HB well as Nesterov cannot accelerate in the deterministic setting as shown in Yue et al. (2023).
5 Convergence for Local Gradient Domination Property
In this section, want to generalize the analysis in Mertikopoulos et al. (2020) under local strong convexity to the weaker local gradient domination property for different cases of B. We consider the two cases of local gradient domination separately. The contributions and differences of our results under less restricted assumptions are the following:
First, we show in both cases that SGD remains in the gradient dominated region with high probability by only assuming local gradient domination instead of local strong convexity. Especially in the case of a local minimum x" this is challenging task, we have to ensure that the SGD scheme (X,)neN remains close to x² without exploiting convexity. We can guarantee this whenever x* is in isolated connected compact set of local minima X'. We prove convergence towards the level set of X and obtain Theorem 5.1 Second, additionally to convergence in expectation we prove almost sure convergence conditioned on the "good ovent". Third, due to the weaker gradient domination assumption and no convexity, one cannot expect the convergence X, to (local or global) mininum x", instead we focus on convergence of f(Xa) to f(x*). In Liu and Zhou 2023) they delve into the rationale behind considering this as more robust metric.
The main result under local gradient domination in local minimum x* is follows:
Theorem 5.1. Fix some tolerance level 8 and let X Rdd be an isolated compact connected set of local. mánima with level I = f(x*) for all x² x Suppose that f salisfy the local gradient. domination
13

---

Published in Transactions on Machine Learning Research (4/2025)
property in each x² E X², is locally G-Lipschitz continuous and satisfies Assumption 2.1 Morcover,
suppose. Assumplion 2-4 hold true. Denole by (Xn)neN the sequence generated by Equalion SGD using step size I'n = e for 0 E (2,1) and suppose that "n S 71 for "/ sufficiently small enough such that be
En=1 22 2 for some > 0 independent of 6. Then, the following holds:
(i) There erist subsets U and of If such that, X1 E Ui the event Su (Xn u for all 1. has probability at least - 5.
Moreover, there erists 3 E [ 1J such that for any
max 10-20 20,
-
e+29 28-
1,1
: (2.
(2 (2-20,1)
:
it holds that
1 nl
(10) 1s(x)) - 1/ EO
moTo)) a..., and (im) (XI)(X,)) nnd Eo
We would like to emphasize that our result does not provide convergence rates in high probability. Instead, we restrict the probability space to "good" events (encoded in U) that occur with high probability 6. Conditioned these events, we establish convergence with rate that is independent of 8. The dependence on 8 instead manifests in the step size "no which ensure that the iterations (Xm)ReN remain within 24 with probability at least 5. Notably, this is the only aspect of our convergence result that depends on 5.
In the following, we only sketch the proof in the main part and provide the full proof in Appendix
Sketch of proof. The proof is split into several intermediate steps outlined as follows:
First, we unily the gradient domination property around the set of local minima X and obtain a radius r such that the unified gradient domination property is fulfilled in all open balls with radius r around x" E x (Lemma D.I..
Based on this we construct the two sets U, U1 S TRd defined as neighborhoods of X constructed such that the gradient domination property holds within this region,
ui = {x E Rd
r inf || x²1 || < 2 [(x) -15 )
U = (i E Rdd
inf
||I - x²1 /
r
x Ex
and the events
a2 = (Xx Eu for all S n} Ω
such that Ou = nm 2n occurs with high probability. This means, when starting in U4 the gradient trajectory does remain in U for all gradient steps with high probability.
We present a row of Lemmata to show that P(2,) 2 - for all n E N, claim (i) of the Theorem. To show P(2,) 2 1 - 8 we construct the sets Cn and E, defined in Equation 29 and Equation (34 such that E, n Cn C an+1 (Lemma D.6) while Lemma D.5 is used to prove this claim. The sets En are such that f(x,) remains close to f We exploit the unified gradient domination property Lemma D.6 c) to prove
to construct the sets F,, (Temma D.4) and derive a recursive inequality
that this event occurs with high probability (Lemma D.7) The sets C₂ are such that X remains close to X,, and exploit the finite variance assumption to show that these events occur with high probability (Lemma D.S).
Finally, claim (ii) and (iii) are shown directly the proof of Theorem 5.1 at the end of Appendix where employ the uniform gradient domination in Sz.
14

---

Published in Transactions on Machine Learning Research (4/2025)
The main result concerning local gradient domination in f* is presented below and does not necessitate the existence of a local minimum or any stationary point. It is worth noting that the definition of local gradient domination in f" guarantoes the gradient domination property for any x with f(r) close to f Consequently,, this definition ensures that functions satisfying this property cannot possess local minima or saddle points within this region.
Theorem 5.2. Fir some tolerance level > O. Suppose f satisfies the local gradient doménation properly in f from Definition 2.2 with 3 E 1 1] and B C Rd. Moreover, suppose within B; f is G-Lipschitz
continuous, Assumption 2.1 ( and Assumption 2.4 hold true. Denote by (Xa)eEN the sequence generated by Equation SSD ussin a step size To = O ( for 0 E (2 and suppose that "In I 7 for n sufficiently
Be small such that n= In 3GC for some
independent of 8. Then, the following holds:
If (i) There erist subsets and of IRd such that, X1 E Ui the event Say (Xn, E for all n = 1.2.... has probability at least 6.
Moreover, for any
28 max (2 - 20, 0+28-2), ),1)
: E (
- (2-20,1) 1)
it holds that
( (11 (ntt.)) a.s., and (iti ( Eo (
(ii) (f(X)) ((Xx))-F') ft)a co
The outline of the proof is similar to the proof of Theorem 5.1 We provide the full proof and more details the sets U and U1 as well as on 3 in Appendix D
6 Application in the training of neural networks
In supervised learning one aims approximate an unknown model y Rdd + 12dy by a parametrized function Iw .R.. + R with parameter w E Rdw, Given family of training data ((Z(m), ((())) mEN generated i.i.d. samples from unknown distribution Miz,y) one usually chooses the parameter w E IRd by solving
min wERd
Epzn [( Y)),
where 4 Rd Rd + R is a user specific data discrepancy. One popular choice of parametrizations are DNNs. We define neural network of depth I. E N by the recursion
20 = 2, === ode (Aeze11+ be), t= 1.....,,7 L
(w(2) ALEL-1 dy.
The weights b2)) of the DNN are collected in w E W == (Rdexd: x Rd)) ~ Rd=, and od Rdd R2d describes the component-wise application of the activation function a a:R-
Provided that a and & are analytic, and (Z, Y' are compactly supported RRd x idd-valued random variables. E Euggy, [g( (Z), Y)] is analytic (Dereich and Kassing 2024 Thm. 5.2). By Lojasiewicz [963] Thm. 11), or Lojasiewicz (9655] $2, Thm. 2), it therefore satisfies local gradient domination in any stationary point. More preciscly, for any stationary point w, there exist 8r, E 1 1] and Cw., > 0 such that equation 4 in Definition 2.2 is satisfied. The local smoothmess is inherently guaranteed by the fact that the loss function is analytic. To elaborate, every analytic function is infinitely differentiable, such that all derivatives remain locally bounded. Concerning Assumption 2.4 we assume that the underlying data in the supervised learning problem is compactly supported, ensuring that Assumption 2.4 is always satisfied locally.
then NDNN dd R,, defined by
15

---

Published in Transactions on Machine Learning Research (4/2025)
In our notation, the stochastic first order oracle takes the form V(w, (2, V W (w) + (V (gn V (DNN
where we denote (= (Z,y) and the iterative SGD then reads
Wa+1 = W. 7n V V (gw, (2a+1),Yatt)
with Sn = (Zn: Yn) independent and identical distributed. The iterative scheme of SHB can be written similarly. Note that this scenario also includes the empirical risk minimization of X7 Σm= (g (z(m)) y (m)) when Ç - (Z, )
Em=1 0(26m) (y(m); see Example 2.5 for more details. In this case, Assumption 2.4 is 1 M
satisfied even with A = O. Thus, the following local convergence is a direct consequence of Theorem 5.1
Corollary 6.1. Let 0>00000 O. Denote by (Wn)nen the sequence generaled by SGD with w + W (mr) as objective function, step size "nn E O(n for I E (2. 1), and assume that fDNN analytic. Let W be on isolated compact set of local minima with level l f1NNN for all w" W and suppose Assumption 2.4 is satisfied within W Suppose that ?n I "i for sufficiently small 71 (depending on ö), then there crist two subsets U, of Rd such that W1 Elh implies that the event Suy (W,, E U, for all 1) has probability at least 1 - 8. Moreover, there erists B E 1/ such that for any
max (2- 20, 0+20-2),1) ),1) 28-1
: :BE (
(2-28% (2-20.1)
:
it holds that (W,))W,, 1|1n o(n"-1) almost surely and in erpectation.
In words: If the iterates of SGD reach a certain area around local minimum, they are likely to become trapped in that region with high probability, provided that the step size is sufficiently small. This results shows that, under very general conditions, SGD converges to local minima and furthermore quantifies the convergence speed.
Remark 6.2. One may similarly apply Theorem 5.2 in the training of DNNs to derive convergence towards global minimum with high probability provided that the initial loss fDNN (X1) and initial step size 71 are sulficiently small.
7
Application in Reinforcement Learning
Recent results showed that choosing the tabular softmax paramelrization in policy gradient (PG) results in objective functions which fulfill a non-uniform gradient domination property (Mei et al.
algorithms
2020 Yuan
ct al.
2022
Klein ct al. 2024). While convergence of PG for exact gradicnts well understood, convergence
rates
for stochastic PG are rare and mostly require very large batch sizes DDing et al. 2022 Klein et al,
2024
Ding et al. 2023).
Let (S, (S...p.r.p)) be discounted MDP with finite state space S, finite action space A and discount factor [0, 1). Further, r: S A + R4 is the positive expected reward function and p(s'|s, describes the transition probability from state s to s' under action a. As in Mei et al. (2020) we assume that the rewards are bounded in [0, 1]. Consider the stationary tabular softmax policy for parameter w E ||SAAA i.c.
exp(w(s,a)
Thn (als) = EvEA, ex)(w(s.a'))
Vs VeES,EEA
In the following we consider entropy regularized PG jointly with vanilla PG by setting = when no regularization considered. Then, for an initial state distribution μ, the value function under the softmax parametrization is given by
V (4) -ET
p' r'r(S,, An)
- >IE Σg p log (T (ArlSa)
1=0
16

---

Published in Transactions on Machine Learning Research (4/2025)
and denote by VT(1) the global optimum and by n the optimal policy. X 0 there exists unique optimal policy which can be represented by the tabular softmax parametrivation Nachum et al. (2017). Therefore, there must exist a continuum of optimal parameters w", such that V/"" (#) = V (m); see also the discussion in Ding et al. (002)). If X = 0 no such parameters exists.
In order to maximize the objective we use stochastic gradient ascent. For X = this is called stochastic policy gradient method or REINFORCE. Note that e.g., Zhang et al. (2020) provide stochastic first order oracle which meets the conditions required in Assumption 2.4 For A > 0, stochastic gradient estimator
that satisfies Assumption 2.4 with A = B = 0 is presented in Ding et al. (2023) Eq. (4)). In both cases
non-uniform Pl-inequality holds Mci ct al. 2020 Lem. 8, Lem. 15): For every w E IR S|||| it holds that
V V (w)ll2 2 (x(1)) (VX - (M))",
with x = 1 if X = 0 and = if x 0 and
minles Rw (x)]ss) vis(
X = 0, A > 0.
(ww
(16)
[8(1pp min, (()) mill,fa Tw (a|s))
Here (s) denotes the best possible action in state s. W.Loog. we assume that a a*(s is unique, otherwise one can simply consider the maximum over all possible best actions, i.e. replace minses Tw (s)ss) with minges mina is optimal action in (a We prove that this implies a local gradient domination property with B = 1 (weak PT.) for x = 0 and B 2 (strong PT.) for X A>0 0.
Proposition 7.1. There enists r, r,c > 0 such that for all w E B = {w: (V:V)())> - V (p) sr it holds that (w) 2 c.
The proof of this proposition is given in Appendix
As the objective function w + V (H) is smooth and Lipschitz on ||S||A|| (see Yuan al. (2022) Lem. E.1) for À x= 0 and Ding et al. (2023) for À >> 0), all assumptions in Theorem 5.2 are satisfied and we obtain the following result.
Corollary 7.2. Let 6 > O. Denote by (Wn)nen the sequence generated by SGD with -VX" (N) objective function, step size To O(n-) for O E (2. 1) and suppose "/n S " for sufficiently small n (depending on 5). Then, there crist two subsets U,th of RISIAA such that W1 E th implies that the event Du (Wn E U, for all 2 1} has probability at least - 8. Moreover, for any
(max (2- 20,20,000 0), x==00. 0, E
(2-20,1) 20,1), 1),
x
it holds that (VI()) VTTh (n))la E o(n"-1) almost surely and in expectation.
In words: If the (regularized) stochastic policy gradient algorithm is started close enough to the optimum nearly 3) (o(n-1) respectively) almost sure rate of convergence can be obtained by choosing 0 = 2 (0 close to 1 respectively) This is in contrast to o(n-1) (linear convergence) known in (regularized) policy gradient with access to exact gradients.
3
Remark 7.3. Note that and in Lemma 7.1 can be explicitly chosen (see Remark E. Hence, one choose the neighbourhoods U and U1 w.r.t. as in Equation (39 and Lemma D.10 in Appendix D to find an explicit neighbourhood Ui as condition for initialization.
Our convergence result in Corollary 7.2 extends the local convergence analysis of stochastic policy gradient under entropy regularization from Ding et al. 2023). Like their work, our analysis builds on MMetikopoulos el al. (2020). However, while Ding el al. (2023) require an increasing batch size sequence to ensure convergence to the regularized optimum, we achieve local convergence for both the unregularized and entropy-regularin settings without this requirement. For X > 0, our method attains convergence arbitrarily close to of o(L) that matches the rate obtained by Ding et al. (2023) while avoiding the need to increase batch sizes. Finally, we highlight that local convergence holds almost surely on an event with high probability.
17

---

Published in Transactions on Machine Learning Research (4/2025)
Acknovledgements Sara Klein thankfully acknowledges the funding support by the Hanns-Seidel Beidel-Stiftung e. and is grateful to the DFG RTG1953 "Statistical Modeling of Complex Systems and Processes" for funding this research. Waiss Azizian was supported in part by the French National Research Agency (ANR) in the framework of the PEPR IA FOUNDRY project (ANR-23-PELA-0003) and MIAI@Grenoble Alpes (ANR-19-P31A-0003))
References
Jing An and Jianfeng Tu. Convergence of stochastic gradient descent under a local Lojasiewicz condition for deep neural networks. arXiv Preprint, arXiv:2304.09221. 2024.
Hédy Attouch, Jérôme Bolte, Patrick Redont, and Antoine Soubeyran. Proximal alternating minimization and projection methods for nonconvex problems: An approach based on the kurdyka-Lojasiowice incquality. Mothemalics of Operalions Research, 35(2):438 457, 2010.
Raef Bassily, Mikhail Belkin, and Siyuan Ma. On exponential convergence of SGD in non-convex over- parametrizeellaaming. arXiv Preprint, arXiv:1811.02564 2018.
Jérôme Bolte, Shoham Sabach, and Marc Teboulle. Proximal alternating linearized minimization for nonconvex and nonsmooth problems. Mathematical Programming, (46(1))4594494 2014.
Léon Bottou, Frank E. Curtis, and Jorge Nocedal. Optimization methods for large-scale machine learning. SIAM Review, 60(2):223 311, 2018.
Sourav Chatterjee. Convergence of gradient descent for deep neural networks. arXiv Preprint, arX1v:220.16462, 2022.
Emilie Chouzenoux, Hean-Baptiste Fest, and Audrey Repetti. Kurdyka--Lojasiewiizz property for stochastic optimization algorithms in non-convex setting. arXiv Preprint, arXiv:2302.06147 2023.
Steffen Dercich and Sebastian Kassing. Convergence of stochastic gradient descent schemes for Lojasiewicz- landscapes. Journal of Machine Learning, 3(3):245 281, 2024. ISSN 2790-2048. doi:
4208/jmm..240009
Yuhao Ding, Junzi Zhang, and Javad Lavaei. Beyond exact gradients: Convergence of stochastic soft-max policy gradient methods with entropy regularization. arXiv Preprint, arXiv:2110.10111, 2022.
Yuhao Ding, Junzi Zhang, and Javad Lavaci. Local analysis of entropy-regularized stochastic soft-max policy gradient methods. In 2023 European Control Conference (ECC), pages 1 8. IEEE, 2023.
Ilyas Fatkhullin, Jalal Etesami, Niao Hc, and Negar Kiyavash. Sharp analysis of stochastic optimization under global Lojadlka-Lojssewiizz incquality. In Advances in Neural Information Processing Systems, volume 35, pages 15848. Curran Associates, Inc., 2022.
Ilyas Fatkhullin, Anas Barakat, Anastasia Kireeva, and Niao He. Stochastic policy gradient methods: Improved sample complexity for Fisher- neneer-non-eegeee non-degenerate policies. In Proceedings of the 40th International Conference on Machine Learning, volume 202 of Proceedings of Machine Learning Research, pages 9827-99 0827-9869. PMLR, 29 Jul 2023.
Benjamin Fehrman, Benjamin Gess, and Arnulf Jentzen. Convergence rates for the stochastic gradient descent method for non-convex objective functions. Journal of Machine Learning Research, 21(136):1-49 2020.
Xavier Fontaine, Valentin De Bortoli, and Alain Durmus. Convergence rates and approximation results for sgd and its contimuous-time counterpart. In Proceedings of Thirty Fourth Conference on Learning Theory, volume 134 of Proceedings of Machine Learning Research, pages 1965 2058. PMLR, 15 19 Aug 2021.
Speneer Frei and Quanquan Gu. Proxy convexity: unified framework for the analysis of neural networks trained by gradient descent. In Advances in Neural Information Processing Systems, volume 34, pages 7937-7949. Curran Associates, Inc., 2021.
18

---

Published in Transactions on Machine Learning Research (4/2025)
Sébastien Gadat, Fabien Panloup, and Sofiane Saadane. Stochastic heavy ball. Electronic Journal of Statistics, 12(1))461- - -529, 2018.
Guillaume Garrigos and Robert M. Gower. Handbook of convergence theorems for (stochastic) gradient methods. arXiv Preprint, arXiv:2301.112255 2024.
Benjamin Gess and Sebastian Kassing. Convergence rates for momentum stochastic gradient. descent with noise of machine learning type. arXiv Preprint, arXiv:2302.035500 2023.
Saced Ghadimi and Guanghui Lan. Stochastic first- and zeroth-order methods for nonconvex stochastic programming. STAM Journal Oplimization, 2344)22341-2233 2013.
Hamed Karimi, Julie Nutini, and Mark Schmidt. Linear convergence of gradient and proximal-gradien methods under the Polyak-Fojasiewieez condition. In Machine Learning and Knowledge Discovery in Databases, pages 795-811, Cham, 2016. Springer International Publishing.
Ahmed Khaled and Peter Richtárik. Better theory for SGD in the nonconvex world. Transactions on Machine Learning Research, 2023. ISSN 2835-8856. Survey Certification.
Sara Klein, Simon Weissmann, and Leif Döring. Beyond stationarity: Convergence analysis of stochastic softmax policy gradient methods. In The Twelfth International Conference on Learning Representations, 2024.
Jason D. Loe, Max Simchowitz, Michael Jordan, and Benjamin Recht. Gradient descent only converges minimizers. In 29th Annual Conference on Learning Theory, volume 49 of Proceedings of Machine Learning Research, pages
PMLR, 23 26 Jun 2016.
Yunwen Lei, Ting Hu, Guiying Li, and Ke Tang. Stochastic gradient descent for nonconvex learning without bounded gradient assumptions. IEEF Transactions on Neural Networks and Learning Systems, 31 (10): 4394 4400, 2020.
Haochuan Li, Jian Qian, Yi Tian, Alexander Rakhlin, and Ali Jadbabaie. Convex and non-convex optimization under generalized smoothness. In Thirty-seuenth Conference on Newral Information Processing Systems, 2023.
Yuqing Liang, Jinlan Liu, and Dongpo Xu. Stochastic momentum methods for non-convex learning without bounded assumptions. Neural Networks, 165:830-888 845, 2023.
Chaoyue Liu, Libin Zhu, and Mikhail Belkin. Loss landscapes and optimization in over-parameteerized 2022.
non-linear systems and neural networks. Applied and Computational Harmonic Analysis, Special Issue on Harmonic Analysis and Machine Learning.
Jun Liu and Ye Yuan. On almost sure convergence rates of stochastic gradient methods. In Proceedings of Thirty Fifth Conference Learning Theory, volume 178 of Proceedings of Machine Learning Research, pages 2963-2983. PMLR, 02-05 Jul 2022.
Zijian Lin and Zhengyuan Zhou. Revisiting the last-iterate convergence of stochastic gradient methods. arXiv Preprint, arXiv:2312.08331 2023.
Zijian Liu, Ta Duy Nguyen, Thien Hang Nguyen, Alina Enc, and Huy Nguyen. High probability convergence of stochastic gradient methods. In Proceedings of the 40th International Conference on Machine Learning, volume 202 of Proceedings of Machine Learning Research, pages 21884-21911 PMLR, 23-29 Jul 2023.
Stanislaw Lojasiewicz. Une propriété topologique des sous-ensembles analytiques récls. Les équations
dérivées partielles, 117:87-80 1963.
-ueeell) Stanislaw Lojasiewicz. Eusembles semi-analytiques. Lectures Notes IHES (Bures-sur- Yvelle), 1965.
Liam Madden, Emiliano Dall' Anese, and Stephen Becker. High probability convergence bounds for non-convex stochastic gradient descent with sub-weibull noise. Journal of Machine Learning Research, 25(241):1-36,
2024. URT. httt:://jmm: http:/rrrrr/aappp/////2/2222
html
19

---

Published in Transactions on Machine Learning Research (4/2025)
Vien Mai and Mikacl Johansson. Convergence of stochastic gradient method with momentum for non-smooth non-convex optimization. In Proceedings of the 37th Internalional Conference on Machine Learning, volume 119 of Proceedings of Machine Learning Research, pages 6630 6639. PMLR, 13 18 Jul 2020.
Saced Masiha, Saber Salchkaleybar, Niao He, Negar Kiyavash, and Patrick Thiran. Complexity of minimizing functions with stochastic first-order oracles, 2024.
segjeetod-gradien--dommie
Jincheng Mei, Chenjun Xiao, Csaba. Szepesvari, and Dale Schuurmans. On the global convergence rates of softmax policy gradient methods. In Proceedings of the 37th International Conference on Machine Learning, volume 119 of Proceedings of Machine Learning Research, pages 0820-6829) PMLR, 13-18 Jul 2020.
Jincheng Mei, Yue Gao, Bo Dai, Csaba Szepesvari, and Dale Schuurmans. Leveraging non-uniformity first-order non-convex optimization. In Proceedings of the 38th International Conference on Machine Learning, volume 139 of Proceedings of Machine Learning Research, pages 7555-7564. PMLR, 18-24 Jul 2021.
Panayotis Mertikopoulos, Nadav Hallak, Ali Kavis, and Volkan Cevher. On the almost sure convergence stochastic gradient descent in non-convex problems. Advances in Neural Information Processing Systems, volume 33, pages 1117-1128, Curran Associates, Inc., 2020.
Eric Moulines and Francis Bach. Non-asymptotic analysis of stochastic approximation algorithms for machine learning. In Advances in Neural Information Processing Systems, volume 24. Curran Associates, Inc., 2011.
Ofir Nachum, Mohammad Norouzi, Kelvin Xu, and Dale Schuurmans. Bridging the gap between value and policy based reinforcement learning. In Advances in Neural Information Processing Systems, volume Curran Associates, Inc., 2017.
Yurii Nesterov. Introductory Leclures Convex Optimizalion. Springer New York, NY, 2004.
Yurii Evgen'evich Nesterov. A method of solving a convex programming problem with convergence rate O(P)). In Doklady Akademii Nauk, volume 269, pages 543 547. Russian Academy of Sciences, 1983.
Lam M. Nguyen, Phuong Ha Nguyen, Peter Richtárík, Katya Scheinberg, Martin Takác, and Marten Dijk. New convergence aspects of stochastic gradient algorithms. Journal of Machine Learning Research, 20:176:1-176:9, 2018.
Ta Duy Nguyen, Thien Hang Nguyen, Alina Enc, and Huy Le Nguyen. High probability convergence of clipped-sgd under heavy-tailed noise. arXiv Preprinl, 2XXiv:2302005337, 2023.
Antonio Orvieto, Jonas Kohler, and Aurelien Lucchi. The role of memory in stochastic optimization. In Uncertainty in Artificial Intelligence, pages 356-366 PMLR, 2020.
Boris Polyak. Some methods of speeding up the convergence of iteration methods. User computational mathematics and mathematical physics, 4(5):1 17, 1964.
Boris T Polyak. Introduction to Optimization. Translations scries in mathematics and engineering. Optimiza- tion Software, Publications Division, 1987.
B.T. Polyak. Gradient methods for the minimisation of functionals. USSR Compulational Mathemalics and Mathematical Physics, 3(4):864-877 878, 1963.
Junwen Qiu, Bohao Ma, and Andre Milzarek. Convergence of SGD with momentum in the nonconvex case: A time window-based analysis. arXiv Preprint, 2ati::2405.199444 2024.
H. Robbins and D. Siegmund. A convergence theorem for non negative almost supermartingales and some applications. In Optimizing Methods in Statistics, pages 233-257. Academic Press, 1971.
Herbert Robbins and Sutton Monro. A stochastic approximation method. The Annals of Mathematical Statistics, 22(3):400-40) 407, 1951.
20

---

Published in Transactions on Machine Learning Research (4/2025)
Kevin Scaman, Cedric Malherbe, and Ludovic Dos Santos. Convergence rates of non-convex stochastic gradient descent under generic. Lojasiewicz condition and local smoothness. In Proceedings of the 39th International Conference on Machine Learning, volume 162 of Proceedings of Machine Learning Research, pages 19310-19827. PMLR, 17-23 Jul 2022.
Othmane Sebbouh, Robert M Gower, and Aaron Defazio. Almost sure convergence rates for stochastic gradient descent and stochastic heavy ball. In Proceedings of Thirly Fourth Conference on Leurning Theory, volume 134 of Proceedings of Machine Learning Research, pages 3935 3971. PMLR, 15-19 Aug 2021.
Hongjian Wang, Mert Gurbuzbalaban, Lingjoon Zhu, Umut Simsekli, and Murat A Erdogdu. Convergence rates of stochastic gradient descent under infinite noise variance. In Advances in Neural Information Processing Systems, volume 34, pages 18866 18877. Curran Associates, Inc., 2021.
Ashia Wilson, Lester Mackey, and Andre Wibisono. Accelcrating rescaled gradient descent: Fast optimization of smooth functions. In Advances Neural Informalion Processing Systems, volume 32. Curran Associates, Inc., 2019.
Stephan Wojtowytsch. Stochastic gradient descent with noise machine learning type part Discrete time analysis. Journal of Nonlinear Science, 33(3):45, 2023. doi: 10.1007/5003332-022--0000 URL
Yan Yan, Tianbao Yang, Zhe Li, Qihang Lin, and Yi Yang. A unified analysis of stochastic momentum methods for deep learning. In Proceedings of the Twenty-Seventh International Joint Conference on Artificial Intelligence, IJCAJ-18, pages 0555-9961. International Joint Conferences on Artificial Intelligence Organization, 7 2018.
Tianbao Yang, Qihang Lin, and Zhe Li. Unified convergence analysis of stochastic momentum methods for convex and non-convex optimization. arXiv Preprint, arXiv:1604.03257, 2016.
Rui Yuan, Robert M Gower, and Alessandro Lazaric. A general sample complexity analysis of vanilla policy gradient. In International Conference on Artificial Intelligence and Statistics, pages 3332-3380. PMLR, 2022.
Pengyun Yue, Cong Fang, and Zhouchen Lin. On the lower bound of minimizing polyak-Eojasiewicr functions. In Gergely Neu and Lorenzo Rosasco, editors, Proceedings of Thirty Sixth Conference on Learning Theory, volume 195 of Proceedings of Machine Learning Research, pages 2948-2968. PMLR, 12-15 Jul 2023.
Kaiqing Zhang, Alce Koppel, Hao Zhu, and Tamer Başar. Global convergence of policy gradient methods (almost) locally optimal policies. SIAM Journal on Control and Optimization, 58(6):3586 3612, 2020.
Beitong Zhou, Jun Liu, Weigao Sun, Ruijuan Chen, Claire Tomlin, and Ye Yuan. pbsgd: Powered stochastic gradient descent methods for accelerated non-convex optimization. In Proceedings of the Twenty-Ninll International Joint. Conference on Artificial Intelligence, IJCAT-20, pages 3258 3266. International Joint. Conferences on Artificial Intelligence Organization, 7 2020.
Yi Zhou, Zhe Wang, and Yingbin Liang. Convergence of cubic regularization for nonconvex optimization under KL property. In Advances in Neural Information Processing Systems, volume 31. Curran Associates, Tnc., 2018.
21

---

Published in Transactions on Machine Learning Research (4/2025)
A Auxiliary Convergence Theorems
In the following section, we provide two specific convergence theorems used to prove almost sure convergence (Lemma A.2 as well as convergence in expectation (Lemına) A.3 The former one is direct consequence of the well-known Slbbinn-Sieggund theorem, provided here for completeness.
Theorem A.1 (Theorem in Robbins and Siegmuud (177 Let (2, (Fu)nen, P) a filtered probability space, (Zn)nEN, (An)neN, (Bn)eeN and (Cn)nEN be non-negative and adopted stochastic processes with
2
Σ
An < 0o and Σ
Bn 00
almost surely. Suppose that for each n E N the recursion
Bl [F.) (1 An) Bn On
is salisfied, then (i) there erists an almost surely finile random variable 7e0 such that Zn - 7oo almost surely as + do and (ti) En=1 Cn < do almost surely.
Lemma A.2. Let FS, (Fa)neN, IP) be a filtered probability space, (Yn)nEN, (an)nEN, (bn)nEN and (To)DEN be non-negative and adapted stochastic processes with
00
Σ bn <0 and Tn
On DO,
almost surely. Suppose that for each n N the recursion
Mlrn+1Yn41 Fn] S (1 - an bn
is satisfied, then we have Yn + almost surely as n + oc.
Proof. We define Zn = Yn, Bn == bn and Cn == anTn.n such that
Z F < Z, Cn + B,
for n E N. Using Lemma, A.1 we observe that there exists Zoo almost surely finite such that Zn = rn + Zoo almost surely as > oc. Moreover, we obtain that
Σ C,
anrnYn <0
almost surely, which yields that
lim inf Tn Yn = 1=000
almost surely, since En an oo almost surely. Since limit inferior and limit coincide for converging sequences, the assertion follows:
Zoc = lim T,YY = lim inf Y, =
n
n=000
almost surely.
The following Lemma will be applied to prove convergence in expectation.
Lemma A.3. Let (wn)nex be non-negalive sequence, such that wn+1 S (1 an)wn + bn, where (an)nEN and (b,)neN are neg-nigative sequences satisfying
oo and
b < 00.
n=
Then, limp-soo Wn. 0.
22

---

Published in Transactions on Machine Learning Research (4/2025)
Proof. W.l.o.g assume that Wn+1 (1 an)w,, + bn, otherwise could just increase an decrease b which would have effect on the summation tests. We obtain
u1 Wn w1 (wi+1 mp)
by
wydk-
Since wn - w1 is bounded below and Ex=1 by < 00, we deduce that Σk= wyak bounded. Since all sunmands are positive, the infinite sum converges. Thus, as a difference of two converging series also (wn)DeN converges. Finally, the convergence of Σx=1 w2ag implies lim in Wn 0 which, by the convergence of (wa)neN, implies lim, ,,, = lim inf, Wn 0.
B Numerical experiment Toy example
In the following numerical experiment, we aim to verify our thcoretical finding. We have implemented the same toy example similar to Fatkhullin et al. (2022) to Lest our theoretical findings. In our implementation, we consider both SGD and SHB applied to the objective function fp(x) = |x|; where æ E R, for various choices of p 2 2. It is straightforward to verify that fp satisfies the global gradient domination with parameter
8(p) p-1 It is noteworthy that for p 2, the fp obviously satisfics the PL condition with 3
whereas
23(m)
for increasing p oc, move towards (p) 1. We have used the step size schedule On - discussed
in Table and observed the almost sure convergence rates n पगाा as suggested by Theorem 4.1 and
Theorem 4.2 Note that our derived rates are arbitrarily close to the sharp upper bound known in expectation
Fatkhullin al. 20222.
1044
1018
12"10
3015
0.5
SCD,
1.07
STB.
/7
0L5
SETT,
0.59
12'15
Lasoectionl
Iteration
toration
om/r
10
SCDD 0.50
SCD, 3 0.02 SLDD 0.92
0.83
15"
Ileration
Toration
Figure 1: Pathwise error (f)(Xx)) of SGD and SHB for various choices of B E {0.5, 0.67, 0.83, 0.92). For each setting we have simulated 100 runs of length N = 10a. The bold lines correspond to the average error of SGD (red) and SHB (blue), and the black dash-dotted line corresponds to the theoretical rate ad-1,
Details of the implementation: Both algorithms have been implemented by hand using MATLAB. We have initialized both SGD and SHB with the initial state X1 [4155 2.5)) + [ 2.5, 1.5)) to force initials
23

---

Published in Transactions on Machine Learning Research (4/2025)
which are not close to the actual minimum x² = 0. The initial step sizes (B) for both algorithms are chosen 88
71 (0.5) = 0.2, (0.677 = 0.13, 21 = 0.004, 71 (0.92) = 10-
through which we counteract the decreasing smoothness for 8 + 1. The momentum parameter for SHB is fixed for all B as == 0.5. The exact gradients Sp are perturbed by independent additive noise following a standard normal distribution 1).
C Proof of Lemma 3.1
In the lollowing section, we present the proof of our super-martingale result..
Proof of Lemma 3.1 In the following, we treat both cases 3 = and ( 1] separately. 8 In this case, the inequality reduces
B[ FR] S (1 + c1 027,)y, + c37
By the choice of "n there exists some N and ě such that 62 - c17 2 217n for all n 2 N. Hence, for all n 2 N
B| F.) S (1 k17)) + c
such that the claim follows by Liu and Yuan 2022 Lem. 1).
B E (21] 1]: The proof uses the elementary incquality
(n (1+ n (1 17)n
(17)
which was also applicd and proved in Liu and Yuan 2022 Lem. 1). The aim is to apply the Robbins-Siegmund implication, Lemma A.2 in order to derive the almost sure convergence rale. Let S 2 be arbilrary for now. The key step of the proof is the following computation
B| [Fx] S (1 (1+ - 02 2-28 + +ca
= =11+ enn o2 Yn C2 Y28
c37
2
(18)
= -11+ c o2 + C2 (1/h 1 Yn Y221) Ca'
Similar to the case 3 = there exists some N > 0 and é > 0 such that 027 - c17 2 217 for all 2 N. Hence, for all 2 N we obtain the itcrative incquality of the form
BY Fi) S - Y, + 027 (18-1y, v22) + c3
(19)
The function + 28
takes it maximum at J
such that
9+ 0+
20
In 1n( 119-11, Y22) <
7n
Yn
(2 23-1
(2.3) 20-1
(20)
7n
(2,3) ス
(2
au=
2
= (23) I (1
2,3 1mm
28
holds almost surely. We define ō2 = c2(28) श (1 zz E (0, 00) for E (t) 1) and proceed with
E|Y+11 Fx] < (I ē
2m
+ c
(21)
24

---

Published in Transactions on Machine Learning Research (4/2025)
Next, apply the elementary inequality Equation 17 and choose such that < S 1. Morcover by the choice of Ta, there exists some > 0 such that
q
m 2 190 for all 2 N. It follows that for all n 2 N
E (n + 1) " Fi)
28y
s (n (n+1)) - [ + (n + 1) 82 ---1 + (n+1)111)
- (n + (1 - 1)m ))
200 , + (n + 1) 827
c4
26q_1
+ (n + 1) c3
+ 1- C1 a((-11)
n " + (n + 1)
'22
カター
+ (n + 1)= c
n08 n
We sot &3 max (ō2, 03) such that for all N
[1 + 1) "Y= Ful
1 1- ng0
ca(1 11)
20-1 n n' Ez(n (7h 20-1 72)
ngo+1
Observe that q0 1 by condition 0 < 1 q
Hence, there exists é4 > 0 and Ñ >> Nfor sufficiently large Ñ 2 N
such that for all n 2 N we have
28a-1 20-7 + +
E[ + 1)" 1F č
n + ca(n + 1)² (7
(22)
1290
In order to apply Robbins-Siegmund, more precisely Lemma A.2 sufficient conditions:
going to verify the following three
8
n19
=00
(23)
R=N
n1
1-1-20
20
< 00,
(24)
R=N
0(28g-1) 23-1
n
< 0.00
(25)
Then, Y, E (--)) almost surely.
The first condition Equation (23 is obviously satisfied, since assume 0 < L. For the second condition
4'
Equation 224 we may choose 1- - such that 17 20 < -1 The third condition Equation (25
gives 7 0(29g-1) 1 which leads to the condition > (2- (2-n)(28-1) Hence, all together obtain the 23-1
23
sufficient condition
0E max [ (2- (2 -
2,84 -1
2
In the following, we consider the two cases separately that correspond the maximum being either 7 or (2-n)(28-1) The first case occurs precisely for 1 < I.-I; the latter one for 1 10-1
28
28
ạ Firstly, let 48-1- In this situation the sufficient condition on 0 simplifies to
204-1
28
0 (
1 2 2'
The interval is non-empty for >> ببةةة which requires 7/ E 143
23 In this situation the sufficient condition on simplifics Secondly, let 2 43-1
(2 - (23 1)
0 0E
2,3 -1
25

---

Published in Transactions on Machine Learning Research (4/2025)
the interval is non-empty for < 28n - 23 + 17. Hence, q <(47 11 22 2 +
which requires the
condition E 13-11 1).
(48-2
Either case yields sufficient conditions and y (depending the auxiliary variable q) under which Yn o (x-²) holds almost surely. We will now utilize the free variable q to prove the claim.
Let 0 E (2
28 We set
48-1 and use the first case. The assumption > 2 - 20
48-1
2/3
max (2 20, 28-1-} implies 0 (1 2
49-2 (Note that > 4--1 is automatically fulfilled by
2 - >
48-2 2
for this choice of 0.)
48-1
Let 0 E 1-8-T: 1): By assumption we have f) 23-1
23
0+23-2 max 200, 0+28-2)
23-1111 We choose
(0, 2,1 28 + -n) -)) and use the second case. (Note that 7 43-1 again is automatically
18-2
fulfilled by #428-2 48-2
20-1 13-1 for this choice of 0.)
All in all we have proved that 0 (2.2) implies Y, E o (vtt)) almost surely for all E (max 0423 0428-23.1),
20,
23-1
D Proofs of Section 5
In the following section, present the proofs of Section
D.1 Proof of Theorem 5.1
Suppose that the assumptions of Theorem 5.1 hold throughout this section. In contrast to the global gradient
domination analysis may assume w.l.o.g. the uniform second moment bounds, i.e. A B = 0, instead of the more general Equation (АBC) condition. Choosing A, B > O would imply the bounded variance assumption the gradient estimator. Note therefore, that the first term A(f(x) - f(x")) and the second term B V (=)]] are both locally bounded by the local Lipschitz assumptions on and VS.
Note that every isolated local minimum {x*) is special case of an isolated compact connected set of local minima. In this case it holds that B Bg.. If X contains more then point, can unify the gradient domination property in neighbourhood of X due to compactness. The set X has to be connected to assure that all local minima are on the same level I.
Recall, the outline of the proof is structured as follows:
First, we unify the gradient domination property around the set of local minima X and obtain a radius such that the unified gradient domination property is fulfilled in all open balls with radius around xx x (Lemmna] D.I
Based on this we construct sets U, 24, C Rd and the events Ωn E (see Equation (26). Equation 27 and Equation (28)), such that n,, h, St occurs with high probability. To be precise, 24, and ti neighborhoods of X constructed such that the gradient domination properly holds within this region, and when starting in U₁ the gradient trajectory does remain in U for all gradient steps with high probability. Then, Ω2 describes the event that X₃ E for all k < n.
All following Lemmata before the proof of Theorem 5.1 devoted to show that P(())) 2 1 for all N. This then proves Claim (i) of the Theorem. Claim (ii) and (iii) will be shown directly in the proof of Theorem 5.1 at the end of this subsection.
In order show P(O))) 2 1-8 we construct set Cn and E, defined Equation 29 and Equation such that Fs, C. Satt (Lemma D.6] while Lemma. D.5 is used to prove this claim.
26

---

Published in Transactions on Machine Learning Research (4/2025)
The sets En are such that f(X,) remains close to f*. We exploit the unified gradient domination property to construct the sets En (Lemma D.4) and derive recursive inequality in Lemma D.6 c) to prove that this event occurs with high probability (Lemma D.7.
The sets Cn are such that N,+1 remains close to X, and we exploit the finite variance assumption lo show that these events occur with high probability (Lemma D.S
We denote by the open ball with radius r > 0 around a R.d and by
(x(x) fy E Rd
|| 111--p11 211 <r}
(x) = {y E Rd
|| - wl sr)
the closed ball with radius 0 around R4 In the following Lemma we unify the gradient domination property around the set of local minima X C Bdd Lemma D.1. There crists 0, 3 E [2, 1] and > 0, such that for all Uztex- (x it holds that
f(x) > 1 for x & x and [IV[(>)]I 2 cl((x) 1)
Proof. By the local gradient domination property, for every x' E X there exist Tx- > 0, Br- E [ 1] and Cr- > such that
|V 2 (x(x)()) - 18==, Ve (z").
Moreover, w.l.ogg we can assume that f(x) > I for all x E B,,- X", as X is an isolated compact connected set of local minima (otherwise choose small enough).
By the compactness X we can find a finite subset y C Cx such that
ú
U B (y") Sx V'
Then, we define 3 = ey By and c = myn Cyr For any x ú there exits y" e y such that
[f(())] Co- (f(x) 8) 2 c(f(z) - 1)
Thus, there exists an open neighbourhood ú of x and 8 1 1), 0, such that for all ú it holds that
f(x) > for x x and [V c(f(x) 1)
As ú is open by definition and x c U, we can find radius 0, such that Unrex- B,(x*) C û. This proves the claim.
Remark D.2. It is noteworthy that the unified gradient domination property obtained in the previous Lemma does not require an absolute value, as f(x) 2 I for all E Up ex- Bx(x).. This is crucial to obtain the recursive inequalities in Lemma D.4 and we will exploit this also in the proof of Theorem 5.1 to oblain the convergence rates.
In the following let r 0, e> 0 and B 1 1] chosen as in the previous Lemma, such that the unified gradient domination property holds for all E Uxex (x*)). Further define
= inf { f(x) f(x)-1:== -1:0
U By(a*) )
U
B (x'))
ant EX
x x*Ex"
Lemma D.3. It. holds that 0.
27

---

Published in Transactions on Machine Learning Research (4/2025)
Proof. If O, then there exists sequence (zn) Uxexx By (x") U Ex Bx(x") with f(æ,) - for n > cc. By definition of the set and compactness (boundedness) of X,, the sequence In is bounded:
3r + sup | S
||>*|| < co. <00.
x'EX
Hence, there is convergent sub-sequence (Imz) with Inz + for lt and by contimuity of f it holds that (z) =. Further, it holds for all x² E X that || - x²11 2 for all n E N such that inf || x= 2
On the other hand, by construction we have that æ E Uxrxx- B (x*) Uzrex- (²(x*) C Urexx. Bun (x*) C Uxexx (x").. And as f(v) > / for all y E (x(x)) \ X we deduce from f(x) = that a X This is a contradiction to ex || 2=1| 2 r
We choose c > 0, such that 20 + fe < s. We define the sets
41 = fx E RRd
inf **Ex*
|| x²1
< 2
r
f(x) - 1 2
(26)
u fr Rd
inf ex
|| x=
r
(27)
2
which are subsets of Rd and the decreasing sequence of events
Pn {Xx u for all & S n}
(28)
Cn [||x+11 Xull for all le S n}.
(29)
and Co = Ω2 which are measurable sets in P))
In order to prove Theorem 5.1 we will show that Qn has probability at least 1 - for all n N. To do this, we construct another sequence of events (Én) with E,, C Ωn which occur with probability at least for any N.
Therefore, fix the notation Dn = f(Xx) -,, Ext1 -(Vf(X,) Z(X,, Sn+1)) and 14 denotes the indicator function for mcasurable set A FP), i.. Ix(w) if w E A and In(w) = 0 if w & A. We prove the following (recursive) inequalities.
Lemma D.4. If B = 1, then it holds that
L
Datila, (1 - (1-7 D la + +n 12, +
1s || (xn))l
2
D
N60 1
(30)
k=1
k=1
j=k
L n
+
7kl
V (X+)
If 3 E (2. 1], for any 15 q 2, holds that
1
20y
In
Da,1la, (11 2 2) ) + +(23) 25-1 (1
22
+ 1
Vn+ (Xa)
2,3
< D2 2 +
23
[I 1302) 1360) Tust12 la
1k
(31)
km
km
km 1
L
+
2 kml
for ē (20) 2 (1 23 )2
28

---

Published in Transactions on Machine Learning Research (4/2025)
Proof. From L-smoothness can deduce that
Du+1= S Dn - 7/ (VS((())) (x+)((,,); + L/2 [V+++
L7
=D ~/ [X,'))) - 7m (VS(Xn), Z(Xm: (n+1)) +
\V++1(X,)lI
2
In
= Dn - 7m + 7 +
2 [V,+1(X,)1
for Z(x,, Sm-1) from Assumption 2.4 and Ext1 [V,((x,,,(X, Sat1)).
We separate the two cases of f::
3 = :: lteaating this inequality and using 1a, S 1o, it follows that
L
Dnt1la, S Dnla, in 1n Vf(X,)] + mn Snt1
1n, || (Xn))l
L
Dplnn mn 1) + Toln
1
Li2
=(1 - (n- + 775n-11a. +
1 1 (X)+1
2
< Dj nnc?) +
II (1 - -350²) j=k
TkEx+1la
1=1
1=1
(32)
L
+
II (1 2307)
22 VK++ (X+)
2
k=1
j=h
D
7x02)
+ Σ
II 7303)
rate+1
k=1
j=k
(X+))
2
k=1
where used that the unified gradient domination property holds for all Xx, k < n the event Ωn..
29

---

Published in Transactions on Machine Learning Research (4/2025)
8 (2,1); Similarly, the unified gradient domination property yields the claimed incquality for any 1 15 < <
L
Datila, 1a, S Dula. m,,,, (V(,)ll 1n,1 +
1s,
(Xn))2
2
L
s Dnlan me 1)2011, In, + in 1n + 1n, (X,]]
D nm + 7 + In
-D,Inn - -nc D20ln
la
2
In
= =(1 -- " + th (21-9D -D20 )n, + 7n5++1 la, +
|| 1 (Xn)l(1
2
289-1
!n
$ (1 c ) HDDDa + +22) v (1 )c²
2u
+ 1nt1l la +
| (Xn) 12
23
2
2 28-1
(33)
S D1
1k 0 12n + +
II - [I1-7ge²)
7/-
Jm
jmn
10
L n
12
II (1 - (1-33(8)
TEx+II Inn
+
Σ
II 1302) j=h
nhl Vi (
2
j=k
k=1
a
7
1
II - 13(7))
<
7/
1nn + 7
7k
k=1
k=1
j=k
L + V 1x+))
2
for ē= (23) क (1
2 )² from the function trick Equation 22 which we applicd in the forth incquality.
We also used that the unified gradient domination properly holds for all Xk, & S n on the event Qn
For B E ($:11 1] we know from the proof of Lemina 3.1 that we can choose the auxiliary parameter g from the previous lemma in such a way, that Σ n "7 is convergent for all 17 E (max 20, 6+20-2),1)
20g-1
(Condition (iit) to apply Lemma A.2 As < 1, it follows that Ems Y < oc holds true for all these choices of g. Now define
Mn =
Σ k=1
II
nELTI
M
Σ k=1
II (1- 2303) j=k
j=k
L
and
Sn
7k (Xe)
Then, (Mn) and ( are (-rrii-matinnalee with zero mean and (S,) is a (Fr+1) --sub-martinglle by Assumption 2.4 Note that by the choice of Yn we have that Σn na < oo and hence E[S,] < cc for all E N.
Next, define R2 = M + Sn and Rn ) + Sn respectively (with some abuse of notation), for every n N. Moreover, let
E, {R₁ for all k S n).
(34)
which is an meessrraee event on (PFF,P). We define Ro = 0 such that Eg = Ω.
Now let B. = En n Cn, then we will first show, that É, fulfills the property G, C 2x+1 for all n E N Lemma D.6 and then that É,, occurs with probability at least 1 in Lemma D.S
To prove that P.n 2h we need more auxiliary result.
Lemma D.5. Suppose 3. y IRd such that
30

---

Published in Transactions on Machine Learning Research (4/2025)
1. inf 1| x²1l < 2,2
f(y) -1 <18
8. ----vl vl1 :
Then it holds that ee byy x²1l <
Proof. By triangle inequality we have that inf== 11v-~*1| S 4 ie there exists x² E X such that I1y- S T. Suppose now, that inf=-ex x*1l 2 5, this means that y Ux-xx- Bug (x*) Uxexx B²(x"). By the definition of
= inf [(2) - -: ZE U
Bug (x))
U
By Ba()))
z'EX'
xt exx
this contradicts the second assumption f(v) - <
We deduce the following relations on the constructed sets:
28g-1
Lemma D.6. For B E [1, 1] let To Sn be sufficiently small such that En 7n ?1 > 0 be arbitrary. Furthermore, assume that the inátial X1 E U2 almost surely. Then,
2 and for 3 lel
a) Ent1 C En, Ent1 C En and p2+11 C Sn
b) En C 22p+
c) Define the events E,, En-1 En U 2 e). Then, for R. R. 1m-1: there ewists
Ö > O such that
E[Ra] E| + 12 + C eP(En-1).
Proof. a) Follows by definition of the events.
b) Note that Eg = l2 = Ω because
r. = Ω ||0- x011 < f(x) -15 c (x: inf || x'1l < E-
r
X1 U = {x: inf Ex
almost surely. We prove the assertion by induction. Let E E., Since E, C En C Ωn by induction assumption, we have w E Ω2 and thus w E 22 for all k < n. We will apply Lemma D.5 with x = (,(w) and y X (w)). By definition it holds that w E Es implies condition 3. and w E Ω, implies condition 1. of Lemma D.5 It remains to show condition 2., then follows that inf I|x++1(w) x'll < 5, ie. (w) E 24 and by w On we deduce w E Pat1.
To Prove condition 2. separate both cases for 3:
31

---

Published in Transactions on Machine Learning Research (4/2025)
3 2: The incquality Equation 30 and the induction hypothesis yield
Da+i(w)= = D ( (w)1 (w)
x Di(w)
II (1 n203) + Σ
II 2 (e5++I(w)an. (w) j=k
1=1
A=1
L
Nel
V (Xx(w))) 21)) (w)
2
k=1
n
Di(w)
II k=1
(L nc² + Σ
II (1 - m0033) (w) (w)
j=k
I.
2
[ k+1 V 11, (w)
2 k=1
V (w) + (w)
2
S 2c + vc <s,
where the equation in the third line is due to S2 for all & S n by induction.
B E 1]: Similarly, we obtain from Equation 42
Dn+1(w)= = Da+1 (1,
[I(1-2302 (30)) ) n (w) (w)
280
S Di(w)la, (w) II 7002) +
28-1
II
7k
k=1
km
j=k
n
kel V (xx(w))|1=1s..
k=1
(w)
II 120) + Σ
n
II 7363) ) > (w) (w)
k=1
j=
L
1 h+1 V (Xx(w)) 1 (w)
k=1
$ 2 + V (w) + (w(
< 2e + < s.
We used in both cases that that that condition 2. in Lemma D.5 is also satisfied which concludes the induction.
< 1 and the choice of such that 2e + Ve < s. This proves
c) Without loss of generality we consider the case B = 1/2. The computations for B E (1/2, 1] follow in line by replacing Mn with M By definition holds that E., En-1 (En-1 En) En- E.. Then we have
R, E
Rn- 1 En-1 + (Rn Rn- 1)
Rn- 1 LEn-2 RG 1 B + (Rn - 1n-1)lEn En-
Ro-1 Rn 1 + (Bn- - Pn- ) F
and for the last term
Rm Rn-1- Ma M² + Sn Sn-1
71 )) sn+1 1a, + 21 mn 10, Mn- + 7 24
(X))((
32

---

Published in Transactions on Machine Learning Research (4/2025)
We treat each of the summands the RHS seperately. It follows from the G-Lipschitz continuity and bounded variance assumption in Theorem 5.1 that
EE 1n,
E| ((x.). Vx+1(X,))) V)(),))
(x)) 1)1a,l S C² +1),
1n
0,
Blll x S C.
(35)
For the term Rn Bn-1 we have
E Rr
E (P(Fn-1).
Using (1-7nc) < and putting all together we obtain the claim
E Rm S E + + + + - cP((nn1))
Lemma D.7. Let 5 be lolerance level and 7n ' be sufficienlly small such that Σn= 7 1C-06- and the condition in Lemma D.6 is fulfilled. Then, have
8 2
IP E..) 2 1
Proof. The proof is along the lines of the proof of Proposition D2 in Mertikopoulos et al. 2020 For
completeness we repeat the arguments. First, observe that
Rn
B B
((=m-))=P((A)) \ F.))) P (R, 2 e)) E E. (R. [R))))]
R E.
On the other hand follows from Lemma D.10 that
<P((.)) < E Rm = E Rd +
+ +C Σ 1
Σ
P P(É ((E-1))
(36)
k=1
k=
Rearranging everything yiclds
GPC + G2 + +Cr
Σ P(Ex)
x and moreover since the events E,
with -= Em 2 By the assumption on the step size are disjoint we obtain
Σ
P(F
S
(37)
==
implying that
8
P(E,.) P(
E
> 1
(38)
2
0=
Lemma D.8. Let 8 0 be tolerance level and Yo. 7/1 be sufficiently smoll such that the condition in
Lemma D.O and Lemma D. 7 are fulfilled. Moreover, suppose 71 small enough such that 40 Then, we have
F3 >n
7 < /
P(( 2 1 - 5.
33

---

Published in Transactions on Machine Learning Research (4/2025)
Proof. By Lemma D have P(E,) 2 1 - 2- Morcover, by the additional step size assumption and
Markov's s inequality deduce that
P(C,) = P(Vk nn || - Xxll - r 2
P[]]X++1 - Xx/1> 2
Σ
P( (Xx))1 27/
[ (x+)1 47
47
Σ
40
2
2
1k
k=1
2 2
Together we obtain that F(B.) = P(D.) 2 1 1 + 2
Finally, ready to prove the main result in the local setting for the set of local minima X
Proof of Theorem 5.1 (i): Recall the definitions of Un and U above. Then it holds that
8
0 Pn
Hence, using Lemma D.8 we obtain
inlP(() 2 inf P(En) 2 1 P(2u) = n
n
(ii): We define D, D,la, and prove that D, o(1/n'-)), then the claim follows since 1 1a, almost surely.
From the proof of Lemma D44 and Lemma D.6 we have
In V 1 12
Dat < D, - cD + tn +
2
Hence, taking the conditional expectation gives
L B[ll V (Xx))= (11.)
B|Dn+1 < D. -7cD22 En Fnlln, +
2
LCC 2
< D. D20
n 2 mn.
where have used that D, and 1a, are F, F--aaasurrblee and V.+1 (X.)) S C from Equation with A = B 0. By our step size choice we can apply Lemma 3.1 obtain Claim (ii).
ABC
(iii): In the following, we again separate between the two cases of B.
3 = :: We have from Lemma D.4 Equation (30 and Lemma D.6 that
L V (Xn))
Dzst S (1 Tn m ln, +
2
34

---

Published in Transactions on Machine Learning Research (4/2025)
Taking expectations and multiplying by (n + 1)'=" leads to E LDDn+1 (n 1)
S (n + "1 - In ) [D]] + (n + 1)1 LCT2
s (n' 00 + (1 - 11-1) )) (1 - nnc ) )B [B[ + (n + 1) 1-n LCnh
2
(n 1 + (1 - n1)n -1 n 1 7 y/n 2 - (1-1)mm "y) cx-) E[Dn] + (n +n 1) 1 L.C
2 ",? L.C.
1 - 1 cnc (1 - 11) i) ?
1 +
n ED( + (n + 1) 711 2
where we used Equation
35
in the first inequality. By our choice of 7n there exists è >> 0 and N > 0 such 2 Ty for all n 2 N. Thus, for all n 2 N
that nnc 1-"
(1 m
LC 2
Wn+1 S (1- 27m) Un + (n + 1)' "/
where Wn = -[[n>>>Dn] Define On = 8n and bn = (n + 1) LC En On = =ZEn 7n oc and
Since Yn = O(#)), we have
2
(n + +++11 1) < oc, LC Σ
Σ bn
by Equation 24 in Lemma
3.1
Hence, we apply Lemma A.3 to prove that lim,- Wn = 0. By the definition
of Wn have verified that E (Xx,,,, 1) S E [
3 E (,, 1]: From Lemina
D.4 Equation (31b and Lemin D.6 have
In
Dn+1 (1
DD 67m + Nu la, +
VV [V)++((x))[]
2
28 )² Next we multiply with (n +1= 1)²-1 and use Equation 17 obtain for (28))22-11 (1
20-1
10 n+ (n + 1)"-"]
+ (n 1)2-1 I.C
(1- - 3 E(D,) + (n + 1)a 7 70y s (n 1)¹ 1)2-7(11
20
In
23
< (n' + (1 - 1) ") (1- - _/²² E[D + ci (n + 1) 11-
(7/n
+ 77)
(n + (1 n))n -9
(1 n)) -) B(Dm
+ + 1) 1- (7 žリ
1+ 1-
(1 (1- n)? 72
+ (n 1)1-"(mm 28g-1
+ +,))
n
n
for some Ci > 0. By our choice of 7n and q 2 1, there exists C2 > 0 and N > 0 such that 2 1-n
(1 (1-9)1362 2 c27g for all 2 N. Thus, for n 2 N
280-1 E[Dnti(n + 1)2 < D 1- 1 (1 (1- -27 + + (1 1)2 (mm + +
Define w, an 0274 and b, cn 1)1 (1:m
-リー1 + 72). We will again apply Lemma A.3 By the step size choice 7n 0 (+)) we have En, an = C2 Σn, 7 00, because S J Further,
Σ bn c1 Σ (n + 1) 1)
+ v/) 00,
35

---

Published in Transactions on Machine Learning Research (4/2025)
because choose the auxiliary parameter q as in the proof of Lemma 3.1 where showed in Equation 24 and Equation 25 that
2 n= 1- 20 00 and Σ
8
813
n
0C
n=N
n=N
All together we doduce that Wn vanishes infinity. Again, by the dcfinition of wn we have that [((((X,) [) < [.. o( (()))))
D.2 Proof of Theorem 5.2
Suppose Uhroughout this section that the assumptions in Theorem 5.2 are satisfied.
The proof will be similar to the previous section. Instead of assuring that (Xn) remains close to the set where we could guarantee the unified gradient domination property, it is now sufficient that f(X,) remains close to ʃ by the different definition of gradient domination definition in ʃ* This will simplify the proof. Moreover, we may again assume w.l.o.g. the uniform second moment bounds, i.e. A = B = 0, instead of the more general Equation (ABC) condition by the same argument as above but on the level scts.
Recall the notation
=- R f(z) f sr}.
and let 0 be the radius of the gradient domination property in f", then there exists 0, such that 2e + Ve < r, i.
u = B 2e+Ve Ve C B
(39)
Moreover, we define the set
U1 = =B
(40)
and the measurable subsets
2n = (Xx E U, for all & s 5n}
in PP).
The proof of Theorem 5.2 is again based on a series of auxiliary lemmas. The goal of these is to prove that with high probability we do not leave the gradient dominated region, i.c. Claim (i) in Theorem 5.2
In the following, we fix the notation D, f(X,) f* and D == lo Ext1 (V Z(Xms Ca+1)) and obtain the parallel result to Lemma D.4
Lemma D.9. B = 1, it holds that
I 1a, II (X,)1,
Dutila, - Dr + +nhEn42 la, +
a Dj
n II (1(- nakk+1 j=k
m 1a
(41)
k=1
+
2il VK+ (Xx)11
2
If 3 E (b, 1), for any 1595 2, it holds that
1
20g
Li2
Datila, S (1 (1- ---7,3 D, + +23) 28 (1
2
+ 1n,
+
23
2
< D
+
7'
28
(1- (11-336) nERtI1 I2
(42)
k=1
1=
7, n
+
2el
2
k=1
36

---

Published in Transactions on Machine Learning Research (4/2025)
for ė = (23)
I (23))=xx( 1 )
Proof. The proof follows line for line as in Lemma D.4 by replacing with f and taking the different definition Dn and Sh into account.
We continue in the previous section: For $ > 1 we know from the proof of Lemma 3.1 that we can choose the auxiliary parameter from the
previous lemma in such a way, that E n "mm
is convergent for all (max 20, -
2dg=1
< x holds true for all these (Condition (iii) to apply Lemma A.2 As < 1, it follows that En= Tn 20 choices of Now define
Mn
Σ
II j=b
2502)
TuEK+1
M Σ
a 7307)
TUEN+1 1s
j=k
and
Sn
22 V (Xx) (
k=1
Then, (M, neN and (M)²) are -martinnas with zero mean and (Sa)eeN ) ) by Assumption 2.4 Note that by the choice of In we have Σn 7 < oo and hence [[[Ss] < oc for all N. Next, define R., M2 + S, and R2 (M) + S, respectively (with some abuse of notation) for every N. Moreover, let
E, (Ra c for all k < n).
which is a mees-uuaera event on (D.F,I). We define Ro = such that Eg = Ω
With these definitions, we can directly prove parallel result Lemma D.6 without the auxiliary result
Lemma D.5
Lemma D.10. For E (1, 1] let "a S 71 be sufficiently small such that Σ 7m 28, and for = 1
let > 0 be arbitrary. Furthermore, assume that the initial X1 E Ui fx f(x) f(x*) $3 almost surely. Then,
a) Enti C En and P2+t C Pn
b) En C In+1
c) Define the events E., = En-1 \ En En-1 UR, 2 e}. Then, for R. = Rn 1, there ewists a
Ö > O such that
E E[RA] [[Ra)SERR S + C
G C -eP(En-1)
Proof. a) Follows by definition.
b) Note that Eg f2 = 22 because X, E U1 = 22 almost surely. We prove the claim by induction. Let w E E,, Since E,, C E,-1 On by induction assumption, we have w E Q2 and thus w E Og for all & n. It remains to show that X (w) E l4 to prove that w E P4 We separate both cases for 3:
37

---

Published in Transactions on Machine Learning Research (4/2025)
8 2: The incquality Equation
41
and the induction hypothesis yield
2
n II (302)
L
Dn+1(w) < Di(w) II (c)
T (w)
2
(X
2
j==
n
= (i(w))
II (1-))c)
Σ
II (1 (3
( (w)
1=k
+ 2
Rell V++1 (Xx(w)))
$ + v Rn(w) + (R(w)
2
< 2e + Vε.
Hence, (n+i(w) u by definition of u.
3 (,, 1}: Similarly, we obtain from Equation
42
n
284-1
n
-33)) ) mLC++(W)
(uti(w) S DI(W)
II - 120)
+
+ Σ
II
(1
k=1
h=1
j=k
+
tk
2
V (Xxx
k=
(w)
II
700) +
k
20-1
+
Σ
II -3(3)
(nEx+((W]ls)) (w)
k=
k=1
k=1
j=k
+ 2 k=0
Vi- ( (Xx(w)))
< + é
+ RR(w)) + Rn(w)
2 2
< 2E + Ve,
where we used that II (1 - 2e²) 1. Hence, it holds again that (n) U.
This prove that E 2,,41 and closes the induction.
c) Follows line by line as in Lemma D.6 part c).
j
Lemma D.11. Let 8 O be tolerance level and in 71 be sufficiently small such that Exe 7n 10--00 and the condition in Lemma D.10 is fulfilled. Then, we have
IPEE)) 2 1-
Proof. Line by line as in Lemma D.7
Finally, we are ready to prove the main result in the local setting for f*
Proof of Theorem 5.2 (i): Recall the definition of Ui and U above. Then it holds that
24
Pnn
n=l
38

---

Published in Transactions on Machine Learning Research (4/2025)
Hence, using Lemma D.11 obtain
P(Du) inf P(O,) 2 inf P(E)) 2 1 - 8.
The proof of Claim (īi) and (iii) follows line by line as in the proof of Theorem 5.1 by replacing I with f" and taking the different definitions of De. Da and Qn into account.
E Proofs of Section 7
In the following section, provide the proof of Section
Proof of Proposition 7.1 We consider the cases x = 0 and À > 0 separately.
Case X = 0: Define the optimal reward gap in every state & E S by
(3) = Q='ss
max ('( > 0, afa*(s)
where a" (s) denotes the best possible action in state a and Q" S x + R denotes the optimal Q-function defined by (s a) E 1- P "r(S,, A:) An = a]. W.l.o.g. we assume that a (s) is unique. Similarly let QT (s, a) _ EE= P 'r(S,, A.) = a] be the Q-function for policy Tw.
For any
choose min ja(s) min (s) and assume that B i.c. (*)--VV (n) Then, we have for every E S that
V=(6,) - V5 min,es ((8)
It follows for every S that
2 (0.))) - vTTm(.)
minges (p()
= as,
Σ (s.
aEA.
2 Σ
To (a (d) (s")
acA.
Σ (=(a)s) (8, a² (s)) (s,
(s)
2 (1 Tue (a (s){s) min A (s).
Rearranging results
The (a (s))s)
min pls) min (s)
Hence, for all u E B₁ can bound c(w) by
c(w) 2
a
> 0.
S (1 p)
Thus, setting V
proves the claim.
39

---

Published in Transactions on Machine Learning Research (4/2025)
Case A 0: For any E (0 choose a² cxexp (1=p)))
Amin, p(s) and assume that xxx By Ding 2la2
et al. 2023 Lem. 12) have
2(V1(1)) V (n))
(als) ==(aas)] S
Amin, ((s)
2rln2
V Amins su(s)
-1
exe
(1-P))
ainn (als). 8,0
where the last inequality is due to Nachum et al. 2017 Thm. 1). It follows directly that
min (s, a) (1 a)) min x (s, > 0.
Hence, we can bound cww) uniformly for all w E B by
2A
d. min (1) a)² min n (a|s)
<(w)= 2 |S| p)
11
(43)
Thus, setting c == [1(ppp] min& (1s)(1 - a)² min, क (als)²
2A
proves the claim.
Remark E.1. It is noteworthy, that we have multiple choices of and depending on E (0,
40


Reviews:
[{"review_id": "FG6PiwwfJC", "reviewer": "Reviewer_h3cd", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n- Deriving the convergence rate for SGD and SHB under both local and global gradient dominant properties \n- Providing almost sure bounds (to the best of my knowledge, they are novel) for SGD/SHB under local/global dominant properties\n- Applying the results in two settings of deep neural networks in supervised learning and policy gradient methods in reinforcement learning\n\nWeakness:\n- The main weakness is that no proof sketch of the main theorems is given in the main body.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The authors studied the convergence rate of stochastic gradient descent (SGD) and stochastic heavy ball (SHB) under the global/local gradient dominant property. In particular, for SGD, under the global dominant property, the proposed upper bound is arbitrarily close to the upper bound in the expectation given in (Fatkhullin et al. 2022). Moreover, they provided additional results for SGD/SHB under global/local dominant property in both almost sure and expectation guarantees. In the proofs, they used Robbins-Siegmund theorem in order to derive the convergence rates.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "- Please provide a proof sketch of Theorem 4.1 in the main body and mention any technical novelty in the proof compared to previous work.\n- As far as I know, the results for almost sure guarantees in previous work require that the norm of gradient is bounded almost surely. However, it seems that Assumption 4.2 is in expectation. I think it is better to emphasize this in the paper and compare the assumptions on the stochastic gradients in Table 1. \n- Regarding the tightness of the bound in the expectation in (Fatkhullin et al. 2022), to my understanding, they did not provide a lower bound. There, it is mentioned that if there is a function $f$ and a gradient estimator such that recursive inequality becomes equality, then their bound is tight. However, the main challenge is whether such a function and gradient estimator can be constructed to satisfy all the considered assumptions. I would suggest checking the following work on deriving lower bounds on the convergence rate under gradient dominant property: https://arxiv.org/pdf/2408.01839", "broader_impact_concerns": "Nothing specific to be mentioned.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "jmzEHG5hAi", "reviewer": "Reviewer_euVb", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "**Strengths:**\n1. The paper derives interesting results with almost sure convergence. The results with this strong convergence type are in the literature, and can be difficult to establish? \n\n2. The paper is well-written with a clear positioning of the contributions. The literature review seems comprehensive.  The motivation for the study is convincing. \n\n**Weakness:**\n1. **The main issue is that the claim of the main theorems 5.1 and 5.2 are not meaningful unless the dependence on failure probability $\\delta$ is specified in the rate.** \n2. It is also important to specify dependence on other constants. Specifically, the dependence on gradient dominance constant is important as it can be very small even for very simple non-convex problems, see, e.g., (Jarre, 2011). \n\n**Suggestion for improvements:**\n1. it is better to discuss separately the regularized and unregularized settings after Corollary 7.3., and carefully compare to prior work in these settings in both deterministic and stochastic settings. There are some works which derived similar local rates under weak gradient dominance and local hidden convexity (Junyu Zhang et al., 2021, Barakat et al., 2023). \n2. It would be useful to comment on what quantities are plotted in bold and not bold in toy experiment in appendix B. I assume these are all runs and the median/mean in bold? \n3. Is it possible to discuss the rates in more detail in the special cases $\\beta=1/2$ and $\\beta=1$? Is there any \"practical\" interest in the study of the values in between, i.e., are there any problems which satisfy your assumption with $\\beta \\in (1/2, 1)$ but not for $\\beta = 1/2$?\n\n\n**Typos and inaccuracies:**\n1. \"step size is is small\". \n2. Should be $f$? \"In Section 7 we will show how this non-uniform gradient domination implies local gradient domination for $f^∗$.\"\n3. On page 12, the reference is missing: \"The proof of this proposition is given in ??.\"\n4. What does Remark 7.2. mean? What is $\\alpha$?\n5. Missing reference on page 35: \"In the following section, we provide the proof of ??.\"\n6. This sentence is not accurate because works do not fit the description in the sentence. The former work does not consider neural networks. The latter does not prove 1/T rate. \"See also Madden et al. (2021) and Liu et al. (2022), where convergence rates of order O( 1 / T ) are shown for neural networks using the (strong) gradient domination property\".\n7. This description is also not accurate because Liu and Yuan (2022) consider PL inequality, not only strong convexity: \"In recent years, Sebbouh et al. (2021) and, building upon it, Liu and Yuan (2022) derive almost sure convergence rates towards global optima under strong convexity.\"\n\n**Questions:** \n1. Why is this the case? \"If λ > 0 there exists a continuum of  optimal parameters w∗, such that V πw∗  λ (μ) = V ∗  λ (μ).\"\n\n\nFlorian Jarre, On Nesterov’s Smooth Chebyshev-Rosenbrock Function. 2011. \nJunyu Zhang et al. On the convergence and sample efficiency of variance-reduced policy gradient method. NeurIPS 2021. \nAnas Barakat et al. Reinforcement Learning with General Utilities: Simpler Variance Reduction and Large State-Action Space. ICML 2023.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The paper offers a new set of results on stochastic optimization under gradient dominated condition, important generalization of well-known Polyak-Lojasievicz inequality. The key results of this work are the extension of in-expectation result to almost sure convergence guarantee, and the study of SGD (and heavy ball momentum) under local variant of gradient dominated condition. It is also demonstrated how the new theory can be applied to training neural networks and policy gradient methods in reinforcement learning.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "Please include the precise dependence on failure probability in the statement of main theorems 5.1 and 5.2., and consider the suggestions above.", "broader_impact_concerns": "n/a", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "7NFagvtrGy", "reviewer": "Reviewer_CDgH", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "- The paper is clear and well-written. The arguments are explained in a way that encourages broader adoption.\n- Almost-sure convergence rates are relatively rare, this is a welcome improvement! While the asymptotic nature of these guarantees makes them somewhat weaker than non-asymptotic bounds, they still provide value. A drawback of the current work is that there are no non-asymptotic high-probability rates presented. These would be very beneficial and seem like they might follow using similar probabilistic tools as to those used in the paper.\n- The noise assumption used is very general. It allows for affine noise, and is only assumed to hold in expectation. It's quite nice that almost-sure convergence can be obtained despite assuming the noise assumption holds only in expectation.\n-  I like the application to reinforcement learning, it is an interesting example of a more interesting example-- even though it only applies to finite state spaces and the domination constant can be really really tiny (it scales inversely with the size of the state space..)\n- The local gradient domination results require somewhat strong assumptions about remaining in the \"good\" region. The stepsize $\\gamma_1$ can be very, very tiny based on the required condition (the sum in Lemma E.6. being bounded). More discussion of this might strengthen the paper.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper studies almost-sure convergence rates for stochastic gradient descent (SGD) under gradient domination, the condition that $\\| \\nabla f(x) \\| \\geq (f(x) - f_{\\ast})^{2\\beta}$, where $\\beta \\in [\\frac{1}{2}, 1]$. This condition is a generalization of the well-known PL inequality, and the authors consider both a global version of it (where the assumption holds over all of $\\mathbb{R}^d$, the domain of $f$), and two different local versions (one defined by the assumption holding over a ball around the minimizer, and one defined by the assumption holding over a sublevel set). Theorem 4.1 gives the first main result of the paper: the almost-sure convergence of SGD under gradient domination, alongside convergence in expectation (though the latter is not new). Theorem 4.2 gives a similar result for the stochastic heavy-ball method. Unfortunately, the rate there is no better than that of SGD but this is to be expected, as optimization under the PL condition seems to be strictly harder than optimization under strong convexity, in the sense that it cannot be accelerated (Yue et al., 2023). In any case, this is the stochastic setting, so any improvement from acceleration would be in higher-order terms and asymptotically negligible anyway. Theorems 5.1 and 5.2 give similar results but under the local versions of the condition.\n\nYue, Pengyun, Cong Fang, and Zhouchen Lin. \"On the lower bound of minimizing polyak-Łojasiewicz functions.\" The Thirty Sixth Annual Conference on Learning Theory. PMLR, 2023.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "- Can you elaborate on this \"Provided that σ and Φ are analytic, and (Z, Y ) are compactly supported Rdz × Rdy -valued random variables,\nthen f DNN : Rdw → R+ defined by w 7 → Eμ(Z,Y ) [Φ(gw(Z), Y )] is analytic (Dereich and Kassing, 2024, Thm. 5.2) and therefore satisfies local gradient domination in any stationary point w∗ (see Definition 2.2) Lojasiewicz (1965).\" What would be the local gradient domination constant in this case? Can you give a more precise argument?\n- In p. 12, the \"The proof of this proposition is given in ??\" should point to p. 35/36. p.35 \"In the following section, we provide the proof of ??.\" should be fixed.\n- Appendix D doesn't show up in the table of contents for some reason, but the other appendices do.", "broader_impact_concerns": "N/A.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper received generally positive reviews, with reviewers highlighting its contributions to the analysis of almost sure convergence in stochastic optimization.
The two main issues raised during the review process were:
- the lack of a proof sketch for the main theorems in the initial submission
- need for a clearer discussion on noise assumptions and dependence on $\delta$.

This was addressed in the revision during the rebuttal.

Given the strength of the theoretical contributions, the careful revisions made by the authors, and the reviewers’ comments on the paper’s significance, I recommend acceptance.
Decision: Accept (poster)