On the Convergence to a Global Solution of Shuffling-Type Gradient Algorithms
Authors: Lam M. Nguyen
Trang H. Tran
Venue: NeurIPS 2023 poster (2023)
Keywords: stochastic gradient
shuffling type gradient method
global convergence
TL;DR: We investigate a new framework for the convergence of shuffling-type gradient algorithm to a global solution under some conditions.

Abstract: Stochastic gradient descent (SGD) algorithm is the method of choice in many machine learning tasks thanks to its scalability and efficiency in dealing with large-scale problems. In this paper, we focus on the shuffling version of SGD which matches the mainstream practical heuristics. We show the convergence to a global solution of shuffling SGD for a class of non-convex functions under over-parameterized settings. Our analysis employs more relaxed non-convex assumptions than previous literature. Nevertheless, we maintain the desired computational complexity as shuffling SGD has achieved in the general convex setting.

On the Convergence to a Global Solution of Shuffling-Typ Gradient Algorithms
Lam M. Nguyen" IBM Research
Trang H. Tran" School of ORIE Cornell University Ithaca, NY, USA htt27@cornell. edu
Thomas J. Watson Research Center Yorktown Heights, NY, USA
LamNguyen. Bamnguyen..M.TDeib.... MLTD@ibb.... com
Abstract
Stochastic gradient descent (SGD) algorithm is the method of choice in many machine learning tasks thanks to its scalability and efficiency in dealing with large-scale problems. In this paper, we focus on the shuffling version of SGD which matches the mainstream practical heuristics. We show the convergence to global solution of shuffling SGD for a class non-convex functions un- der peceeparameterized settings. Our analysis employs more relaxed non-convex assumptions than previous literature. Nevertheless, we maintain the desired compu- tational complexity as shuffling SGD has achieved in the general convex setting.
Introduction
In the last decade, neural network- models have shown great success in many machine learning applications such as natural language processing [Collobert and Weston, 2008, Goldberg et al., 2018], computer vision and pattern recognition [Goodfellow al., 2014, He and Sun, 2015). The training task of many learning models boils down the following finite-sum minimization problem:
1 T1
min WER
F(w)
f(w;
(1)
where f(:;): Rd IR is smooth and possibly non-convex for [m] {1, n). Solving the empirical risk minimization (1) had been a difficult task for a long time due to the non-convexity and the complicated learning models. Later progress with stochastic gradient descent (SGD) and its variants [Robbins and Monro, 1951, Duchi et al., 2011, Kingma and Ba, 2014] have shown great performance in training deep neural networks. These stochastic first-order methods are favorable thanks to its scalability and efficiency in dealing with large-scale problems. At each iteration SGD samples index uniformly from the set [I,...,n], and uses the individual gradient Vf(:;) to update the weight.
While there has been much attention the theoretical aspect of the traditional i.idd. (independently identically distributed) version of SGD [Nemirovski et al., 2009, Ghadimi and Lan, 2013, Bottou data sampling schemes. Also known
al., 2018), practical heuristics often without-replaceenet as shuffling sampling schemes, these methods generate some random or deterministic permutations of the index set 21,2...., n. and apply gradient updates using these permutation orders. Intuitively, a collection of such n individual updates is a pass over all the data, or an epoch. One may choose to create new random permutation the beginning of each epoch (in Random Reshuffling scheme) or use a random permutation for every epoch (in Single Shuffling scheme), Alternatively, one may use
'Equally contributed. Corresponding author: Lam M. Nguyen
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

Incremental Gradient scheme with fixed deterministic order of indices. In this paper, we use the term unified shuffling SGD for SGD method using any data permutations, which includes the three special schemes described above.
Although shuffling sampling schemes usually show better empirical performance than SGD [Bottou, 2009], the theoretical guarantees for these schemes are often more limited than vanilla SGD version, due to the lack of statistical independence. Recent works have shown improvement in computational complexity for shuffling schemes over SGD in various settings [Gürbötzbalaba et al., 2019, Haochen and Sra, 2019, Safran and Shamir, 2020, Nagaraj al., 2019, Nguyen et al., 2021, Mishchenko et al., 2020, Ahn et al., 2020]. In particular, in a general non-convex setting, shuffling sampling schemes improve the computational complexity in terms of á for SGD from O (o² (02 to O (na/) h
where is the bounded variance constant [Ghadimi and Lan, 2013, Nguyen al., 2021, Mishchenko et al., 2020].. We summarize the detailed literature for multiple settings later in Table 1.
While global convergence is a desirable property for neural network training, the non-convexity landscape of complex learning models leads to difficulties in finding the global minimizer. In addition, there is little to work studying the convergence to global solution of shuffling thufe SGD algorithms for a general non-convex setting. The closest line of research investigates the Polyak- Lojasiewicz (PL) condition (a generalization of strong-convexity), which demonstrates similar convergence rates as the strongly convex rates for shuffling SGD methods [Haochen and Sra, 2019, Ahn et al., 2020, Nguyen et al., 2021]. In another direction, Gower al. [2021] and Khaled and Richtárik [2020] investigates the global convergence for some class of non-convex functions, however for vanilla SGD method. Beznosikov and Takáč [2021] investigate a random shuffle version of variance reduction methods (e.g. SARAH algorithm Nguyen et al. [2017]. but this approach only can show convergence stationary points. With target on shuffling SGD methods and specific learning architectures, we come up with the central question of this paper:
How can we establish the convergence to global solution for class of non-convex functions using shuffling-ty -type SGD algorithms? Can we exploit the structure of neural networks to achieve this goal?
We answer this question affirmatively, and our contributions are summarized below. Contributions.
We investigate new framework for the convergence of shuffling-type gradient algorithm to a global solution. We consider a relaxed set of assumptions and discuss their relations with previous settings. We show that our average- -L inequality (Assumption holds for wide range of neural networks equipped with squared loss function.
Our analysis generalizes the class function called star-M -mmooth-convex. This class contains non-convex functions and is more general than the class of star-convex smooth functions with respect to the minimizer (in the over-parameterized settings). In addition, our analysis does not use any bounded gradient or bounded weight assumptions.
We show the total complexity of O 2374 for a class of non-convex functions to reach an ê-accurate global solution. This result matches the same gradient complexity stationary point for unified shuffling methods in non-convex settings, however, we are able to show the convergence to a global minimizer.
n
1.1 Related Work
In recent years, there have been different approaches to investigate the global convergence for machine learning optimization. This includes a popular line of research that studies some specific neural networks and utilizes their architectures. The most early works show the global convergence of Gradient Descent (GD) for simple linear networks and two-layer networks [Brutzkus al., 2018, Soudry et al., 2018, Arora et al., 2019, Du et al., 2019b]. These results are further extended to deep learning architectures [Allen-Zhu et al., 2019, Du al., 2019a, Zou and Gu, 2019]. This line of research continues with Stochastic Gradient Descent (SGD) algorithm, which proves the global convergence of SGD for deep neural networks for some probability depending on the initialization process and the number of input data [Brutzkus et al., 2018, Allen-Zhu et al., 2019, Zou et al.,
"The computational complexity is the number of (individual) gradient computations needed to reach an é-accurate stationary point (i.e. a point v E Rd that satisfies || [[)]] < E.)

---

2018, Zou and Gu, 2019]. The common theme that appeared in most of these references is the over- parameterized setting, which means that the number of parameters in the network are excessively large [Brutzkus et al., 2018, Soudry et al., 2018, Allen-Zhu et al., 2019, Du et al., 201 1019a, Zou and Gu, 2019]. This fact is closely related to our setting, and we will discuss it throughout our paper.
Solyak-Lojasiewicz (PL) condition and related assumptions. An alternative approach is to investigate some conditions on the optimization problem that may guarantee global convergence. A popular assumption is the Polyak-Lojasiewicz (PL) inequality, a generalization of strong-convexity [Polyak, 1964, Karimi et al., 2016, Nesterov and Polyak, 2006]. Using this PL assumption, it can be shown that (stochastic) gradient descent achieves the same theoretical rate as in the strongly convex setting (i.e linear convergence for GD and sublinear convergence for SGD) [Karimi et al., 2016, De et al., 2017, Gower et al., 2021]. Recent works demonstrate similar results for shuffling type SGD [Haochen and Sra, 2019, Ahn et al., 2020, Nguyen et al., 2021]. both for unified and randomized shuffling schemes. On the other hand, [Schmidt and Roux, 2013, Vaswani et al., 2019] propose to use a new assumption called the Strong Growth Condition (SGC) that controls the rates at which the stochastic gradients decay comparing to the full gradient. This condition implies that the stochastic gradients and their variances converge to zero at the optimum solution [Schmidt and Roux, 2013, Vaswani et al., 2019]. While the PL condition for F implies that every stationary point of F is also a global solution, the SGC implies that such a point is also a stationary point of every individual function. However, complicated models as deep forwadd neural networks generally have non non-optimal stationary points [Karimi et al., 2016]. Thus, these assumptions are somewhat strong for non-convex settings.
Although there are plenty of works investigating the PL, condition for the objective function F [De et al., 2017, Vaswani et al., 2019, Gower et al., 2021], not many materials devoted to study the PL inequality for the individual functions (:; A recent work [Sankararaman et al., 2020] analyzes SGD with the specific notion of gradient confusion for perrperraeterrized settings where the individual functions satisfy PL condition. They show that the neighborhood where SGD converges linearly depends on the level of gradient confusion (i.e. how much the individual gradients are negatively correlated). Taking a different approach, we investigate the PL property for individual functions and further show that our condition holds for general class of neural networks with quadratic loss.
Over-paramaterizes settings for neural networks. Most of the modern learning architectures contain deep and large networks, where the number of parameters are often far more than the number of input data. This leads to the fact that the objective loss function is trained closer and closer to zero. Understandably, in such settings all the individual functions f(:;;) are minimized simultaneously at O and they share common minimizer. This condition is called the interpolation property (see e.g. (Schmidt and Roux, 2013, Ma et al., 2018, Meng et al., 2020, Loizou et al., 2021J) and is studied well in the literature (see e.g. [Zhou et al., 2019, Gower et al., 2021]). For a comparison, functions satisfying the strong growth condition necessarily satisfy the interpolation property. This property implies zero variance of individual gradients at the global minimizer, which allows good behavior for SGD near the solution. In this work, we slightly change this assumption which requires a small variance up some level of the threshold Note that when letting 0, assumption exactly recovers the interpolation property. Star-convexity and related conditions. There have been many attentions to a class of structured non-convex functions called star-convex [Nesterov and Polyak, 2006, Lee and Valiant, 2016, Bjorck et al., 2021]. Star-convexity can be understood as convexity between global minimizer Ws. The name star-convex comes from the fact that each sublevel set is star-shaped [Nesterov and Polyak, 2006, Lee and Valiant, 2016]. Zhou et al. [2019] shows that if SGD follows star-convex path and there exists a common global minimizer for all component functions, then SGD converges global minimum.
arbitrary point w and the
In recent progress, Hinder et al. [2020] considers the class of quasar-convex functions, which further generalizes star-convexity. This property was introduced originally in [Hardt et al., 2018] under the name 'weakly quasi-convex', and investigated recently in literature [Hinder et al., 2020. Jin, 2020, Gower et al., 2021]. This class uses parameter ( (0, 1] to control the non-convexity of the function, where < = 1 yeilds the star-convexity and ( approaches 0 indicates more non-convexity [Hinder et al., 2020j. Intuitively, quasar-convex functions unimodal all lines that pass through a global minimizer. Gower et al. [2021] investigates the performance of SGD for smooth and quasar-
3

---

convex functions using an expected residual assumption (which is comparable to the interpolation property). They show a convergence rate of O(1/vK) for i..d. sampling SGD with the number of total iterations K, which translates to the computational complexity of O (1/E²). To the best of our knowledge, this paper is the first work studying the relaxation of star-convexity and global convergence for SGD with shuffling sample schemes, not for the i.i.d. version.
2 Theoretical Setting
We first present the shufflin-type gradient algorithm below. Our convergence results hold for any permutation of the training data {1, ... n2). including deterministic and random ones. Thus, our theoretical framework is general and applicable for any shuffling strategy, including Incremental Gradient, Single Shuffling, and Random Reshuffling.
Algorithm 1 (Shufiting-Tl Type Gradient Algorithm for Solving (1))
Initialization: Choose an initial point wo dom (F).
2: for / === 1.2, .., do
3: Set w/ 1z
4: Generate any permutation ((1) of [n] (either deterministic or random);
5: for = L.......... do
6: Update w!t)
(t) w-1 1/s
(1) f(w([
7: end for
(t)
8: Set Wi wnn
9:
end for
We further specify the choice of learning rate 1) describe the set of assumptions used in our paper.
(1) in the detailed analysis. Now we proceed to
Assumption 1. Suppose that fü = min f(w; i) -c, i fI.....n].
Assumption 2. Suppose that f(; L-smooth for all i E {l,..., n), i.e. there exists constant E (0, +00) such that:
[V; ((w'=i)) s L|[w- w'll, Vw,, w' Rd.
Assumption is required in any algorithm to guarantee the well-definedness of (1). In most applica- tions, the component losses are bounded from below. By Assumption 2, the objective function F is also L-smooth. This Lipschitz smoothness Assumption is widely used for gradient-type methods. In addition, we denote the minimum value the objective function F. = minwerd F(w). worthy to note the following relationship between F, and the component minimum values:
F. min F(w) min WER!
min (f WERd
Σ> 57
wERd
n
We are interested in the case where the set of minimizers of F is not empty. The equality F, EE= f attains if and only if a minimizer of F is also the common minimizer for all component functions. This condition implies that the variance of individual functions is 0 at the common minimizer.
2.1 PL Condition for Component Functions
Now are ready to discuss the Polyak-Lojasiewicz condition follows. Definition 1 Poolyak-Lojasiewiee condition). We say that f satisfies Polyak-Lojastewizz (PL) in- equality for some constant > if
|V](w)]| 2n(s(w) f*], Vw E ER,
(4)
where f miD f(w).

---

The PL condition for the objective function F is sufficient to show global convergence for (stochas- tic) gradient descent [Karimi al., 2016, Nesterov and Polyak, 2006, Polyak, 1964]. It is well known that function satisfying the PI. condition is not necessarily convex [Karimi et al., 2016). However, this assumption on somewhat strong because implies that every stationary point of F is also global minimizer. Our goal is to consider class of non-convex function which is more relaxed than the PL condition on F' while still having the good global convergence properties. In this paper, we formulated an assumption called "average PL inequality", specifically for the finite sum setting:
Assumption 3. Suppose that f(; that
satisfies average PL inequality for some constant μ >> 0 such
(V((=))) 2μ Σis(us) - [t], Ve E Bdd
(5)
==1
where 17 = win f(w;
Comparisons. Assumption 3 weaker than assuming the PI. inequality for every component function f(z(). In general setting, Assumption is not comparable to assuming the PL. inequality for F. Formally, if F' satisfies PL the condition for some parameter T > 0, then we have:
2r(F(w) - F.] < [F(())
IV i)11?.
(6)
However, by equation (3) we have that [F(w) F.] S 1 inequality for each function f-) cannot directly imply the PL condition on F. and vice versa.
fT). Therefore, the PL.
In the interpolated setting where there is a common minimizer for all component function f(;;)) can be shown that the PL condition on F' is stronger than our average PL assumption:
"
72 E ([( - fi 2 (F() F.] S (VF S Σ
[V
72
On the other hand, our assumption cannot imply the PL inequality on unless we impose a strong relationship that upper bound the sum of individual squared gradients 1 \ fu: in terms of the full squared gradient ||V F(w)l for every E RRd For these reasons, the average PL Assumption 3 is arguably more reasonable than assuming the PL inequality for the objective function F. Moreover, we show that Assumption holds for general class of neural networks with a final bias layer and squared loss function. We have the following theorem.
Theorem 1. Let {(x(0, ( )²= is a training data set where x(() E R is the input data and y() E Re is the output data for i = 1...., n. We consider an architecture h(w;;) i) with w be the vectorized weight and h consists final bias layer b:
h(w; i) = W wT= 20; +
where w vec({0. W,b)) and z(0;i) are some inner architectures, which can be chosen arbitrarily. Next, we consider the squared loss f(w; i) = //: i) y 112 Then
IV 1 2 2[ i) ft), Vw e Rdd.
where f == min f(w; i).
Therefore, for this application, Assumption holds with === 1.
2.2 Small Variance at Global Solutions
In this section, we change the interpolation property in previous literature [Ma et al., 2018, Meng al., 2020, Loizou al., 2021] by a small threshold. For any global solution w, of F, let us define
T Σ T1
a = inf w. EWW
[V[(==)))1
(8)
We can show that when there is a common minimizer for all component functions (i.e. when the equality F. Σ f holds), the best variance of is O. It is sufficient for our Theorem to impose (ev)lleve upper bound on the variance o²:
5

---

Assumption 4. Suppose that the best variance at w, is small, that is, for E >> 0
0 S Pe,
(9)
for some P > O.
It is important to note that in current non-convex literature, Assumption 4 alone (or, assuming a = 0 alone) is not sufficient enough to guarantee a global convergence property for SGD. Typically, some other conditions the good landscape of the loss function needed to complement the weer-parameterized setting. Thus, we have motivation to introduce our next assumption.
2.3 Generalized Star-Smooth-Conwer Condition for Shuffling Type Algorithm
We introduce the definition of star-smooth-convex function follows.
Definition 2. The function is -smoohh--ooh with respect to reference point i E IRd
if
[Vg(w) V < (Vg((w) - Vg(ū), i)) Yu Rd
(10)
It is well known that when is L-smooth and convex [Nesterov, 2004], we have the following general inequality for every w, w' Rd.
VV(ww> (g(w")1l & ((Vg(w) Vg(w'), w')
(11)
Our class of star-smoohh-conee convex function requires similar inequality to hold only for the special point w' ú. Interestingly, this related class of star-convex functions, which satisfies the convex inequality for the minimizer Wt:
(star-convexity w.r.t w) g(w) g(w) s (Vg(w), w)) Yu eR..
(12)
This class of functions contains non-convex objective losses and is well studied in the literature (see e.g. [Zhou et al., 2019]). Our Lemma shows that the class of star-smooth- convexx function is broader than the class of L-smooth and star-convex functions. Therefore, our problem of interest is non-convex general.
Lemma 1.
The function g is
with respect to for some constant M > 0 if
one of the two following conditions holds:
g L-smooth and convex.
2. g L-smooth and g is star-convex with respect to
Proof. The first statement of Lemma follows directly from equation (11). We have that y is star-M-ssmott-conves with respect to any reference point and M = L.
Now proceed to the second statement. From the star-convex property of g with respect to ú, have
g(w) ( ) s (Vg(w), w- úd), Ve Rd.
and Vg(()) 0 since à is the global minimizer of g. On the other hand, g is L-smooth and we have
g g Sg g w 1 Vg(w) < ((w)
2L [Vg[w))1
which is equivalent to VV((2)]1 & 2L[g(w) - g (())), i e [n]. Since Vg(w) = i E [n]] we have for Ve E Rdd
2L[g(w) (( < 2 - Vg(()), w w.). function as in Definition 2 with M 2L.
This is
For the analysis of shuffling type algorithm in this paper, we consider the general assumption called the generalized star- star-smooth-comvex condition for shuffling algorithms:

---

Assumption 5. Using Algorithm 1, let us assume that there exist some constants M > and N 2 0
such that at each epoch t I,...,T, we have for i ,
[ (1) n 10 (i)) (](ww; < M
f
(m:
1-1 (1)) - V f((w:: ( (i), wf w.)
+ N
Im - 100113
(13)
where w, is a global solution of F.
We note that it is sufficient for our analysis to assume the case N = 0, i.e. the individual function (1) is star-M --soooot--cooeex with respect to w. for every i = 1,.... n as in Definition 2. that case, the assumption does not depend on the algorithm progress.
Assumption 5 is more flexible than the star-M -ws-ssoohhcoooee one (10) because an additional term (c)
N N >. ||w! wi 1| for some constant N > 0 allows for extra flexibility in our setting, where the right-hand side term (V (w;; i) fw i), w w.) could be negative for some w E R
Note that we do not impose any assumptions bounded weights bounded gradients. Therefore, (t) wa (f)) 2 cannot be uniformly bounded by any universal constant.
the term 1 Ei |ml|
3 New Framework for Convergence a Global Solution
In this section, we present our theoretical results. Our Lemma 2 first provides recursion to bound the squared distance term || w- 1|2: Lemma 2. Assume that Assumptions 1, 2, 3, and 5 hold. Let {wn (ūg}?== be the sequence generated by Algorithm 1 with 0 < Th S min 23 II } For every y > O we have
l w. (1 + Cini) |0-,- w.ll? 2 + C2no2 Cam(F(ur-))) - -F...
(14)
where w. a global solution of F, F. min F(w), and
Ci 8L²
3 + 14N
4y
M
6M
C2 M + ++ GL2
3ML +
(15)
12M
C3 7+1 M
a
Rearranging the results of Lemma 2, we have
1
1 + Cimi
C2 C3
F(W.-1)- F.
|| w.1
1| 1.112
(16)
C3
C3nh
Therefore, with an appropriate choice learning rate that guarantee (1/ne + CiTit) S 1/mh-1, we can unroll the recursion from Lemma 2. Thus we have our main result in the next Theorem.
Theorem Assume that Assumptions 1, 2, 3, and 5 hold. Let {w+)T= be the sequence generated by Algorithm I with the learning rate T) 3t where O < T}s S min { 1M }
> Let the number of iterations T = 3372 for some X > 0 and 0. Constants C1, Cz. and C2 are defined in for any Y > O. We further define K= + C g3/3/2 and specify the learning rate Da/s
KT)-1 = K'rno and vjo K Dxx such that Da/E < min a 1
2M 2L for some constant
K
D > 0. Then we have
1
K Kexp(AC,D3)
C2 0202 C3
-FI5
F.I
10000 - w. w.ll e
(17)
T
C&DA
where F. = min F(w) and of is defined in (8).
Our analysis holds for arbitrarily constant values of the parameters y, À and D. In addition, show our current analysis for every shuffling scheme. An interesting research question arises: whether the convergence results can be improved if one chooses to analyze a randomized shuffling scheme in this framework. However, we leave that question to future works.
Using Assumption 4, can show the total complexity of Algorithm I for our setting.
7

---

Table 1: Comparisons of computational complexity (the number of individual gradient evaluations)
needed by SGD algorithm to reach an É-accurate solution w that satisfies F(w) - F F(w.) ) S & (or FVF (w)] < & in the non-convex case).
Shuffling Schemes
Global Solution
Settings
References
Complexity
Nemirovski et al. [2009],
o +
Shamir and Zhang [2013] (1)
x
Convex
Mishchenko et al. [2020],
Nguyen al. [2021] (2)
2372
PL condition
Nguyen et al. [2021]
no² 21/2
/
/
Star-convex
Gower et al. [2021] (3)
O
(
x
/
related
22
Ghadimi and Lan [2013]
0
Non-convex
Nguyen et al. [2021],
O
( gaya
/
Mishchenko et al. [2020] (5)
Our setting (non-convex)
This paper, Corollary (4)
O
N(Nvi)a/2 24/2
We note that the assumptions in this table comparable and only show the roughly complexity in terms of In addition, to make fair comparisons, only report the complexity of unified shuffling schemes. (1) Standard results for SGD in convex literature often use a different set of assumptions from the one in this paper (e.g. bounded domain that || w.| Ao for each iterate and/or bounded gradient that Ell (w:; i)ll S G²). We report corresponding complexity for rough comparison.
[Mishchenko et al., 2020] shows bound for Incremental Gradient while [Nguyen al., 2021] has unified setting. We translate these results unified shuffling schemes from these references to convex setting. (3) Since we cannot find reference containing the convergence rate for vanilla SGD and star-convex functions, adapt the reference Gower et al. [2021] here. This paper shows result for L-smooth and quasar convex function with an additional Expected Residual (ER) assumption, which weaker
assuming smoothness for
f(:;) and interpolation property. The convec results hold when the quasar-convex parameter is 1.
Since we use different of assumptions than the other references, we only report the rough comparison m, N and é, where N is constant from Assumption and NV1 max (N, 1). Note that framework of star-smooth-comm arbitrary é. We explain the detailed complexity helow and in the Appendix.
in the function. In addition, we need a² = 0 so that the complexity holds with
(5) Standard literature for SGD in non con-convex setting assumes a bounded variance that E, [[]f(w;; [F())] o² we report the rough comparison.
Corollary 1. Suppose that the conditions in Theorem 2 and Assumption 4 hold. Choose C DA = and E = é/G such that < & S G with the constants
D²
C2P
G =
1000
-w.11
where
C33
Cs
C SLa
14NL" 41a
+
M
3M
2 + 1 + G17 + 3MIZ
C2 M
12ML
C3 = 12+1 M
//2
Then, the we need? T
6772 epochs guarantee
T
min [F(Wy-1) F.) T 1515T
Σ F(w.-1) - F.] S
8

---

Computational complexity. Our global convergence result in this Corollary holds for fixed value of é in Assumption Thus, when + this assumption equivalent to assuming o² The total complexity of Corollary is O schemes for SGD in convex setting [Mishchenko et al., 2020, Nguyen et al., 2021J. However, our result holds for a broader class of functions that are possibly non-convex. Comparing to the non- convex setting, current literature [Mishchenko et al.. 2020, Nguyen et al., 2021] also matches our rate the order of é, however, we can only prove that SGD converges stationary point with weaker criteria [F))]] < for general non- convex funtions. Table shows these comparisons in various settings. Note that when using a randomized shuffling scheme, SGD often performs better rate in terms of the data in various settings with and without (strongly) convexity. For example, in strongly convex and/or PL setting, the convergence rate of RR is O O(vn/Vē), which is better than unified schemes with (n V [Ahn al., 2020]. However, for fair comparison, do not report these results in Table as our theoretical analysis is derived for unified shuffling scheme.
This rate matches the best known rate for unified sampling
If we further assume that L, M, N > 1, the detailed complexity with respect to these constants is
L (MM + N)332
o
T2
10/2
63/2
We present all the detailed proofs in the Appendix. Our theoretical framework is new and adapted to the finite-sum minimization problem. Morcover, it utilizes the choice of shuffling sample schemes to show a better complexity in terms of é than the complexity of vanilla i..d. sampling scheme.
Numerical Experiments
In this section, we show some experiments for shuffling-type SGD algorithms to demonstrate our theoretical results of convergence global solution. Following the setting of Theorem 1, consider the non-convex regression problem with squared loss function. We choose fully connected neural networks in our implementation. We experiment with different regression datasets: the Diabetes dataset from sklearn library [Efron et al., 2004, Pedregosa et al., 201 1] with 442 samples in dimension 10; the Life expectancy dataset from WHO [Repository, 2016] with 1649 trainable data points and 19 features. In addition, we test with the California Housing data from StatLib repository (Repository, 1997, Pedregosa al., 2011] with a training set of 16514 samples and 8 features.
For the small Diabetes dataset, we use the classic LeNet-300- 100 model [LeCun et al., 1998]. For other larger datasets, of 900 neurons. We apply the randomized reshuffling scheme using PyTorch framework [Paszke et al., 2019]. This shuffling scheme is the common heuristic in training neural networks and is implemented in many deep learning platforms (e.g. TensorFlow, Py PyTorc, and Keras [Abadi et al., 2015, Paszke al., 2019, Chollet et al., 2015]).
similar fully connected neural networks with an additional starting layer
For each dataset {I; }, we preprocess and modify the initial data lightly to guarantee the over- parameterized setting in experiment. We do this by using pre-training stage: firstly GD/SGD algorithm to find a weight w that yields a sufficiently small value for the loss function (for Diabetes dataset train 10-8 and for other datasets we train to 10-2). Letting the input data I; be fixed, we change the label data to ÿJ such that the weight w yields a small loss function (c) for the optimization associated with data (I,, (.). and the distance between ýi and y; is small. Then the modified data is ready for the next stage. We summarize the data (after modification) in our experiments in Table 2.
Table 2: Datasets used in our experiments
Data name
# Samples
# Features
Networks layers
Sources
Diabetes
442
10
300-100
Efron et al. [2004]
Life Expectancy
1649
19
900-300-100
Repository [2016]
California Housing
16514
8
900-300-100
Repository [1997]

---

For each dataset, we first tune the step size using a coarse grid search [0.0001, 0.001, 0.01, 0.1, for 100 epochs. Then, for example, if 0.01 performs the best, we the second grid search [0.002, 0.005, 0.01, 0.02, 0.05] for 5000 epochs. Finally, we progress to the training stage with 10 epochs and repeat that experiment for random seeds. We report the average results with confidence intervals in Figure 1.
10
Diabetes
Life Expectancy
California Housing
10-1
Shuffing SGD
Shuftling SGD
Shuftingg 5GD
10
10-2
10-1
10-3
10-3
Fiw
10"1
10
10-1
10
10
10"
7.5
2.5 100 5-10"
2.5-100 5-10 7.5-100
Number of effective passes
Number of effective passes
Number effective passes
Figure 1: The train loss produced by Shuffling SGD algorithm for three datasets: Diabetes, Life Expectancy and California Housing.
For California Housing data, Shuffling SGD fluctuates toward the end of the training process. Nevertheless, for all three datasets converges steadily a small value of loss function. In summary. this experiment confirms our theoretical guarantee that demonstrates a convergence to global solution for shufflin--type SGD algorithm in neural network settings.
5 Conclusion and Future Research
In this paper, our focus is on investigating the global convergence properties of shufflin-tyype SGD methods. We consider more relaxed set of assumptions in the framework of star-smooth-conve functions. We demonstrate that our approach achieves total complexity of O ga7z ) to attain an É-accurate global solution. Notably, this result aligns with the previous computational complexity of unified shuffling methods in non-convex settings, while ensuring that the algorithm converges to global solution. Our theoretical framework revolves around the shuffling sample schemes for finite-sum minimization problems in machine learning.
We also provide insights into the relationships between our framework and well-established over- parameterized settings, as well as the existing literature on the star-cone convexity class of functions. Furthermore, we establish connections with neural network architectures and explore how these learning models align with our theoretical optimization frameworks.
This paper prompts several intriguing research questions, including practical network designs and more relaxed thcoretical settings that can support the global convergence of shuffling SGD methods. Additionally, extending the global convergence framework other stochastic gradient methods [Duchi et al., 2011 1, Kingma and Ba, 2014] and variance reduction methods [Le Roux et al., 2012, Defazio et al., 2014, Johnson and Zhang, 2013, Nguyen al., 2017], all with shuffling sampling schemes, as well as the exploration of momentum shuffling methods [Tran et al., 2021, 2022], represents a promising direction.
An interesting research question that arises is whether the convergence results can be further enhanced by exploring the potential of randomized shuffling scheme within this framework [Mishchenko et al., 2020]. However, we leave this question for future research endeavors.
10

---

References
Martín Abadi, Ashish Agarwal, Paul Barham, Eugene Brevdo, Zhifeng Chen, Craig Citro, Greg S. Corrado, Andy Davis, Jeffrey Dean, Matthieu Devin, Sanjay Ghemawat, Ian Goodfellow, Andrew Harp, Geoffrey Irving, Michael Isard, Yangqing Jia, Rafal Jozefowicz, Lukasz Kaiser, Manjunath Kudlur, Josh Levenberg, Dandelion Mané, Rajat Monga, Sherry Moore, Derek Murray, Chris Mike Schuster, Jonathon Shlens, Benoit Steiner, Ilya Sutskever, Kunal Talwar, Paul Tucker, Vincent Vanhoucke, Vijay Vasudevan, Fernanda Viégas, Oriol Vinyals, Pete Warden, Martin Wattenberg, Martin Wicke, Yuan Yu, and Xiaoqiang Zheng. TensorFlow: Large-scale machine learning on heterogeneous systems, 2015. URL https: //ww::/wwwwww... tensorflow org/. Software available from tensorflow.org.
Olah,
Kwangjun Ahn, Chulhee Yun, and Suvrit Sra. Sgd with shuffling: optimal rates without compo- nent convexity and large epoch requirements. In H. Larochelle, M. Ranzato, R. Hadsell, M. F. Balcan, and H. Lin, editors, Advances in Neural Information Processing Systems, volume 33, pages 17526-17535, Curran Associates, Inc., 2020. URL https: https::/ neurips cc/ Paper pdf.
Zeyuan Aluen-Zhu, Yuanzhi Li, and Zhao Song. A convergence theory for deep learning via over- parameterizaaioon In Kamalika Chaudhuri and Ruslan Salakhutdinov, editors, Proceedings of the 36th International Conference on Machine Learning. volume 97 of Proceedings of Machine Learning Research, pages 242-252. PMLR, 09-15 Jun 2019. URL http: htttp://proceedingg mml. html.
press/v97/
Sanjeev Arora, Simon Du, Wei Hu, Zhiyuan Li, and Ruosong Wang. Fine-grained analysis of optimization and generalization for overparameterized two-layer neural networks. Kamalika Chaudhuri and Ruslan Salakhutdinov. editors, Proceedings of the 36th International Conference on Machine Learning, volume 97 of Proceedings of Machine Learning Research, pages 322-332. PMLR, 09-15 Jun 2019. URL http: testtt::/pprooe http///rroceeeeesse/eee///. mlr. waa...reeeavv1 arrar htmml1.......... html.
Aleksandr Beznosikov and Martin Takáč. Gandom-reshuuflee sarah does not need a full gradient computations. arXiv preprint arXiv:2111.13322, 2021.
Johan Bjorck, Anmol Kabra, Kilian Q. Weinberger, and Carla Gomes. Characterizing the loss landscape in non-negative matrix factorization. Proceedings of the AAAI Conference Artificial Intelligence, 3568)6676-66776 May 2021. URL httph:tt////oe //ojs.///////.//// aaai org/ index.ndxiiii. wwwp.pppp/pee.ieee.mmpp phpp/AAT/ AAAT/ article/vies/166t 16836.
L. Bottou, F. E. Curtis, and Nocedal. Optimization Methods for Large-Scale Machine Learning. SIAM Rev, 60(2):223-311, 2018.
Léon Bottou. Curiously fast convergence of some stochastic gradient descent algorithms, 2009.
Alon Brutzkus, Amir Globerson, Eran Malach, and Shai Shalev-Shwartz. SGD learns over- parameterized networks that provably generalize linearly separable data. In International Conference on Learning Representations, 2018. URL httpss//openrevien wwt.:/.eeeeeoooiieeeeeeeee xJ33wwxRb.
Francois Chollet et al. Keras. Gitflub, 2015. URL
Ronan Collobert and Jason Weston. A unified architecture for natural language processing: deep neural networks with multitask learning. In William W. Cohen, Andrew McCallum, and Sam Roweis, editors, Machine Learning, Proceedings of the Twenty-Fifth International Conference (ICML 2008), Helsinki, Finland, June 5-9, 2008, volume 307 of ACM International Conference Proceeding Series, pages 160-167. ACM, 2008. doi: (0.1145/1390135 39.1999111111.7.7... URL https: //doi. //doi.org//a 10.g///../.. 1144/1390156..3907777 1390177.
Soham De, Abhay Yadav, David Jacobs, and Tom Goldstein. Automated Inference with Adaptive Batches. In Aarti Singh and Jerry Zhu, editors, Proceedings of the 20th International Conference Artificial Intelligence and Statistics, volume 54 of Proceedings of Muchine Learning Research, pages 1504-1513. PMLR, 20-22 Apr 2017. URL. htttss:/pproceeeee de17a. html.
mlr, paress/54.
11

---

Aaron Defazio, Francis Bach, and Simon Lacoste-Julien, Saga: A fast incremental gradient method with support for non-strongly convex composite objectives. In Advances in Neural Information Processing Systems, pages 1646-1654, 2014.
Simon Du, Jason Lee, Haochuan Li, Liwei Wang, and Xiyu Zhai Gradient descent finds global minima of deep neural networks. In Kamalika Chaudhuri and Ruslan Salakhutdinov, editors, Proceedings of the 36th International Conference on Machine Learning, volume 97 of Proceedings of Machine Learning Research, pages 1675-1685. PMLR, 09-15 Jun 2019a. URL http://
proceedings mlr www.mm.....peeeeee prressvv7// /dw1/c....cc//////// html.
Simon S. Du, Xiyu Zhai, Barnabas Poczos, and Aarti Singh. Gradient descent provably optimizes parameteriezed neural networks. In International Conference on Learning Representations, 2019b. URL ht https:
John Duchi, Elad Hazan, and Yoram Singer. Adaptive subgradient methods for online learning and stochastic optimization. Journal of Machine Learning Research, 12:2121-2159, 2011.
Bradley Efron, Trevor Hastie, lain Johnstone, and Robert Tibshirani. Diabetes dataset, 2004. URL /etpss//wwie stat. ncsu. edu/"boos/ /ooo//vrr /var.. www.sseeeetteeeeeeee diabetes html.
S. Ghadimi and G. Lan. Stochastic first-and zeroth-order methods for nonconvex stochastic program- ming. SIAM J. Optim., (3(4))2341-2366) 2013.
Yoav Goldberg, Graeme Hirst, Yang Liu, and Meng Zhang. Neural network methods for natural language processing. Comput. Linguistics, 44(1), 2018. doi: 10.1162/COLI A 00312. URL
bttps://dott org/10. //////.112.///// 1162/COLI_r_0031
lan Goodfellow, Yaroslav Bulatov, Julian Ibarz, Sacha Arnoud, and Vinay D. Shet. Multi-digit number recognition from street view imagery using deep convolutional neural networks. In Yoshua Bengio and Yann LeCun, editors, 2nd International Conference on Learning Representations, ICLR 2014, Banff, AB, Canada, April 14-16, 2014, Conference Track Proceedings, 2014. URL htaa:://arxivv wwrxiv.oor//oi oww.oogg///....o.ooooooooooooo httgg/as//31...... 1012220............. 6082.
Robert Gower, Othmane Sebbouh, and Nicolas Loizou. Sgd for structured nonconvex functions: Learning rates, minibatching and interpolation. In International Conference on Artificial Intelli- gence and Statistics, pages 1315-1322 1323. PMLR, 2021.
M. Gürbüzbalaban, A. Ozdaglar, and P. A. Parrilo. Why random reshuffling beats stochastic gradient descent. Mathematical Programming, Oct 2019. ISSN 1436-4646. doi: 10.1007/ 110107-019-01440-w URL http: / dx. doi. org/ 10. 100000000000001-90110001000
Jeff Haochen and Suvrit Sra. Random shuffling beats sgd after finite epochs. In International Conference on Machine Learning, pages 2624-2633, PMLR, 2019.
Moritz Hardt, Tengyu Ma. and Benjamin Recht. Gradient descent learns linear dynamical systems. Journal of Machine Learning Research, 19(29);1-44, 2018. URL http://jmlz iaaplirorggppppppeee papers/ v19/16-465 httml.
Kaiming He and Jian Sun. Convolutional neural networks at constrained time cost. In IEEE Conference on Computer Vision and Pattern Recognition, CVPR 2015, Boston, MA, USA, June 7-12, 2015, pages 5353-5360. IEEE Computer Society, 2015. doi: 10. 10.1000/CVP..2015..7599 URL https: //doi. org/ 10. 1109/CVPR, 2015. 7299173.
Oliver Hinder, Aaron Sidford, and Nimit Sohoni. Near-optimal methods for minimizing star-convex functions and beyond. In Conference on Learning Theory, pages 1894-1938, PMLR, 2020.
Jikai Jin. On the convergence of first order methods for quasar-convex optimization. arXiv preprint arXiv:2010.04937 2020.
Rie Johnson and Tong Zhang. Accelerating stochastic gradient descent using predictive variance reduction. In Advances in Neural Information Processing Systems, pages 315-323, 2013.
12

---

Hamed Karimi, Julie Nutini, and Mark Schmidt. Linear convergence of gradient and proximal- gradient methods under the Giuseppe Manco, and Jilles Vreeken, editors, Machine Learning and Knowledge Discovery in Databases, pages 795-811, Cham, 2016. Springer International Publishing.
condition. In Paolo Frasconi, Niels Landwehr,
Ahmed Khaled and Peter Richtárik. Better theory for sgd in the nonconvex world. arXiv preprint arXiv:2002.03329, 2020.
Diederik P. Kingma and Jimmy Ba. abs/1412.6980, 2014.
Adam: A method for stochastic optimization. CoRR,
Nicolas Roux, Mark Schmidt, and Francis Bach. stochastic gradient method with an exponential convergence rate for finite training sets. In NIPS, pages 2663-2671, 2012.
Yann LeCun, Léon Bottou, Yoshua Bengio, and Patrick Haffner. Gradient-based learning applied to document recognition. Proceedings of the IEEE, 86(11):228--2524, 1998.
Jasper C.H. Lee and Paul Valiant. Optimizing star-convex functions. In 2016 IEEE 57th Annual Symposium on Foundations of Computer Science (FOCS), pages 603-614, 2016. doi: 10.1 FOCS.2016.711
Nicolas Loizou, Sharan Vaswani, Issam Hadj Laradji, and Simon Lacoste-Julien. Stochastic polyak step-size for sgd: An adaptive learning rate for fast convergence. In Arindam Banerjee and Kenji Fukumizu, editors, Proceedings of The 24th International Conference on Artificial Intelligence and Statistics, volume 130 of Proceedings of Machine Learning Research, pages 1306-1314. PMLR, 13-15 Apr 2021. URL http: http:::tpppc/eeeeeeeeee http:///ooeeeeenneeeeeeeees mlr. www.m..p..s/.eememmmmm press/vv30/loozoouus
html.
Siyuan Ma, Raef Bassily, and Mikhail Belkin. The power of interpolation: Understanding the effectiveness of SGD in modern wer-parametrized learning. In Jennifer Dy and Andreas Krause, editors, Proceedings of the 35th International Conference on Machine Learning, volume 80 of Proceedings of Machine Learning Research, pages 3325-3334 PMLR, 10-15 Jul 2018. URL http:://preeee sttp://prrcceedings mlr. press/v80/ maa.a....aa.mm..mmmmmmmmm.aa.//a html.
Si Yi Meng, Sharan Vaswani, Issam Hadj Laradji, Mark Schmidt, and Simon Lacoste-Julien. Fast and furious convergence: Stochastic second order methods under interpolation. In Silvia Chiappa and Roberto Calandra, editors, Proceedings of the Twenty Third International Conference on Artificial Intelligence and Statistics, volume 108 of Proceedings of Machine Learning Research, pages 1375-1386. PMLR, 26-28 Aug 2020. URL attp://proceedings mlr. www.mm/...........m.mm.mm press/v108/ meng20a. html.
Konstantin Mishchenko, Ahmed Khaled Ragab Bayoumi, and Peter Richtárik. Random reshuffling: Simple analysis with vast improvements. Advances in Neural Information Processing Systems, 33, 2020.
Dheeraj Nagaraj. Prateek Jain, and Praneeth Netrapalli. Sgd without replacement: Sharper rates for general smooth convex functions. In International Conference Machine Learning, pages 4703 4711, 2019.
A. Nemirovski, A. Juditsky, G. Lan, and A. Shapiro. Robust stochastic approximation approach to stochastic programming. SIAM J. on Optimization, 19(4):1574-1609 2009.
Yurii Nesterov. Introductory lectures on convex optimization : basic course. Applied optimization. Kluwer Academic Publ., Boston, Dordrecht, London, 2004. ISBN 1-4020-7553-7.
Yurii Nesterov and Boris T Polyak. Cubic regularization Newton method and its global performance. Mathematical Programming. 108(1):177-205, 2006.
Lam M Nguyen, Jie Liu, Katya Scheinberg, and Martin Takáč. Sarah: A novel method for machine learning problems using stochastic recursive gradient. In Proceedings of the 34th International Conference on Machine Learning- Volume 70, pages 2613-2622 JMLR. org, 2017.
Lam M. Nguyen, Quoe Trah-Dinh, Dzung T. Phan, Phuong Ha Nguyen, and Marten van Dijk. A unified convergence analysis for shuffling-type gradient methods. Journal of Machine Learning Research, 22(207): 2021. URL http: / jmwr. orgo/o/////.o patp///ppps/////////// 20- 1238. html.
13

---

Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, Alban Desmaison, Andreas Kopf. Edward Yang. 7achary Veto,o Martin Raison, Alykhan Tejani, Sasank Chilamkurthy, Benoit Steiner, Lu Fang, Junjie Bai, and Soumith Chintala. Pytorch: An imperative style, segh-performance deep learning library. In Advances in Neural Information Processing Systems 32, pages 8024-8035.
Curran Associates, Inc., 2019.
F. Pedregosa, G. Varoquaux, A. Gramfort, V. Michel, B. Thirion, O. Grisel. M. Blondel, P. Pretten- hofer, R. Weiss, V. Dubourg, J. Vanderplas, A. Passos, D. Cournapeau, M. Brucher, M. Perrot, and E. Duchesnay. Scikit-learn: Machine learning in Python. Journal of Machine Learning Research, 12:2825-2830, 2011.
Boris T. Polyak. Some methods of speeding up the convergence of iteration methods. USSR Computational Mathematics and Mathematical Physics, 4(5):1-17, 1964.
Global Health Observatory Data Repository. Life expectancy and healthy life expectancy, 2016. URL https://apps. who. gttgggh///ttaaiiieee main. wtwpeeewwaannnnnnnmaeeeee SDG20116LEAEE
StatLib Repository, California housing, 1997. URL htpp::///ww.dc.fc.uupppp dec. u.c.uuppp/"1torg/
Regression/cal wwwhooonclllllaa cal_housiig...... html.
Herbert Robbins and Sutton Monro. stochastic approximation method. The Annals of Matematical Statistics, 22(3):400-407, 1951.
Itay Safran and Ohad Shamir. How good is sgd with random shuffling? In Conference on Learning Theory, pages 3250-3284. PMLR, 2020.
Karthik Abinav Sankararaman, Soham De, Zheng Xu, W Ronny Huang, and Tom Goldstein. The impact of neural network overparameterization on gradient confusion and stochastic gradient descent. International conference on machine learning, pages 8469-8479. PMLR, 2020.
Mark Schmidt and Nicolas Le Roux. Fast convergence of stochastic gradient descent under a strong growth condition, 2013.
Ohad Shamir and Tong Zhang. Stochastic gradient descent for non-smooth optimization: Convergence results and optimal averaging schemes. In Sanjoy Dasgupta and David McAllester, editors, Proceedings of the 30th International Conference on Machine Learning, volume 28 of Proceedings of Machine Learning Research, pages 71-79, Atlanta, Georgia, USA, 17-19 Jun 2013. PMLR. mlr press/ /v2/////////// h0t///hmmr1133 htmll.
URL https: http::://ppooceediii
Daniel Soudry, Elad Hoffer, Mor Shpigel Nacson, Suriya Gunasekar, and Nathan Srebro. The implicit bias of gradient descent on separable data. J. Mach. Learn. Res., 19(1):2822-288 January 2018. ISSN 1532-4435.
Trang Tran, Lam M Nguyen, and Quoe Tran-Dinh. SMG: shuffling gradient-based method with momentum. In Marina Meila and Tong Zhang, editors, Proceedings the 38th International Conference on Machine Learning, volume 139 of Proceedings of Machine Learning Research, pages 10379-10389. PMLR, 18-24 Jul 2021. URL
mlr press/vi39)
tran21b. html.
Trang H Tran, Katya Scheinberg, and Lam M Nguyen. Nesterov accelerated shuffling gradient method for convex optimization. In Kamalika Chaudhuri, Stefanie Jegelka, Le Song, Csaba Szepesvari, Gang Niu, and Sivan Sabato, editors, Proceedings of the 39th International Conference on Machine Learning, volume 162 of Proceedings of Machine Learning Research, pages 21703-21732. PMLR, 17-23 Jul 2022. URL https: httpp::/procceeddai http///poeeeennn.e/ee////o mlr. wwwps/eevvvveeee vttp/v12///// www1///taaaa...... trantaanna2222 html.
Sharan Vaswani, Francis Bach, and Mark Schmidt. Fast and faster convergence of sgd for over- parameterized models and an accelerated perceptron. In Kamalika Chaudhuri and Masashi Sugiyama, editors, Proceedings of the Twenty-Seconl International Conference on Artificial Intelligence and Statisties, volume 89 of Proceedings of Machine Learning Research, pages 1195- 1204. PMLR, 16-18 Apr 2019. URL https:tt//.. /ttp///eoooeeeeeee//eee/e/ee/.ee mlr. wal..ppees/vv8 htt.//////awai1/11 19a. html.
14

---

Yi Zhou, Junjie Yang, Huishuai Zhang, Yingbin Liang, and Vahid Tarokh. Sgd converges to global minimum in deep learning via star-convex path. arXiv preprint arXiv:9901.0045/ 2019.
Difan Zou and Quanquan Gu. An improved analysis of training over-parameten peerpparameterized deep neural networks. In Hanna M. Wallach, Hugo Larochelle, Alina Beygelzimer, Florence d' Alché-Buc, Emily B. Fox, and Roman Gamett, editors, Advances in Neural Information Processing Systems 32: Anmual Conference Neural Information Processing Systems 2019, NeurlPS 2019, December 8-14, 2019, Vancouver, BC, Canada, pages 2053-2062, 2019.
Difan Zou, Yuan Cao, Dongruo Zhou, and Quanquan Gu. Stochastic gradient descent optimizes over-parameterized deep relu networks, 2018
15

---

On the Convergence to a Global Solution of ShufflingTTpe Gradient Algorithms
Supplementary Material, NeurIPS 2023
A Theoretical settings: Proof of Theorem 1
A.1 Proof of Theorem
Proof. Let us use the notation (w;; = de (h(w;)) i]) 1 (1:(ww;)) - y01 We consider architecture h(w; i) with w be the vectorized weight and h consists of a final bias layer b:
h(w;; i) = W (0; + +
where w vec({0, W, 6}) and =0; are some inner architecture, which can be chosen arbitrarily. Firstly, we compute the gradient of f(;; with respect to E RR. For j = 1,..., C, we have if(w; 0b3
0s. (b(w;i))
ah(w;i)e
06,(x)
00((x)
i , n.
Ob,
Ob
Ook
i (amp(())))
Ong 1==h(ur;))
(18)
The last equality follows since ah(w:)) 0 for every k + j and Oh(w:))) words, it is the identity matrix.
1 for k j. In other
ob,
Let us denote that fi min f(w; i) and of = min, (x()). We prove the following statement for 1:
I (w; 12 2 | (z) 2p(0s(h(w:;)) - o. 2 (w; - f;1,
for every w E Rdd and 1....,m.
We begin with the first inequality:
(Dflust))²
(ofluz;i))
I/ 2)1
Σ
Σ
Ow,
dw,
Øb,
1=1
j=d-ot1
(2))
(18)
1 (=)
dzz
1==h(103))
Now let us prove the PL condition for each function (I)), i.e., there exists constant >> 0 such that:
(+)((1)) 2 (n(d)(x)) Φ5 Ve R i == I....,n.
Recall the squared loss that d, (z) = 111 - 1 1 and (.).(z) = - (.) We can see that the constant y = satisfies the following inequality for every Re, i 1 i=,,..,,
V.)(())]1 = || (0 2 || - - y 11 2μ²)(x) 2 24(xx(x) - 0i
where the last inequality follows since o; 2 0.
The PL condition for Φ; directly implies the second inequality. The last inequality follows from
the facts that fw:; i) = &hs (h(w:w) and fü = min f: 2 ming (x(x)) = d.. Hence, Theorem is proved.
D
16

---

B Preliminary results for SGD Shuffling Algorithm
In this section, present the preliminary results for Algorithm 1. Firstly, from the choice of learning
rate ni; ( : it and the update ((t) = w Ti f we have
(4)
(t)
n (i + 1)) in Algorithm 1, for E [m].
i-1
(1) (1) = w1- w
"
= w
1
(1) ; (j (j+1) 1)).
(19)
1=0
Hence,
w = w
(+++)
(t)
V fu (0 1)).
(20)
Next, we refer a Lemma in [Nguyen et al., 2021] to bound the updates of shuffling SGD algorithms. Lemma (Lemma Nguyen et al. [2021]. Suppose that Assumption 2 holds for (1). Let (w:") } be generated by Algorithm with the learning rate d); (8) in 0 for given positive sequence (m Ifo <00< nn S 3. for all 1 1, we have
|/0u (0) w.112
S 41110 (1)
wwll2 + 80; nh.
(21)
==0
R-1
8L2
16L
Σ
(t)
w
S n
w. 11? 1000
+
1/2
+
20
.T..
(22)
n
3
3
)=0
Now considering the term
10)
(1) 112 we get that
-wo
1
(20)
x
nh
V ; 19 + +1)
[ x (j + 1)) Vs(w:; n (0) + 1)))
n
S 1/
V ( ; 2 + v v[.,; 2
TI
j=0
T.2112 n-1
Σ
|1ub (2) w.1l 11
(21) 4L 2 /
||m0 w. 112 + 8L n -2
We further have
n
n-1
w
w
(1)
112
(6)
10 +
w (0)
71
71
0=0
1=0
16I
m/
2
wwo w. 11
(8)
mt +
20 ni
3
4L2
1/
mml0
(x)
w.
12
8L2 m
0
(23)
17
n
17

---

C Main results: Proofs of Lemma 4, Lemma 2, Theorem 2, and Corollary 1
C.1 Proof of Lemma
Lemma 4. Let {w: JT=1 Then, under Assumptions 1, 2, and 5, we have
(T be the sequence generated by Algorithm I with (0) Th. with 0 < S
a for 1/: S 2L'
2M
(1+2) - -w.1? S (1 + ++B 11m6 -w.12 1l0 (
V (1:==:==00000) + B2no
2M ==1
(24)
where
B1
81.
14M
3
M
(25)
B3 M
+
1
SN 3M
GZ7
Proof. We start with Assumption Using the inequality |||a|1 - |lb11 S ||a - b/1 we have for
1 t= .,.....7 T and i 1, ,,...,...
1/ / (0) (V (1))
$ <IV (1) Vfww.: (1))
(9)
M(V
(.w π (1)), w w.) + N Σ
10
(f)
(1)
1=1
f (2) x (1)) w - - w.) - M(VS(w; x (1)) ;-11 -w.)
(0)
(1) 1 1012
This statement is equivalent to
(V (6)
( (1))
w02 w.)
2M / (0 (1)) M (V
1
(V w (1) -w.)
N
M 10 w0 11
(26)
For any W. E W from the update (19) we have,
|!!! w. 2 (19)
mml 1 w.112
2T
(
(e)
(1) (0)), (0) (2))
w.) + The (1
n12
(26)
mm (" w.ll 2Mn
2t
|/ (w:
(6) n (1))l2 +
2n
V.(w: _ (1))2²
Mn
2Th
(V (w.; (1) (i)), (0) w.) + 2n,
Σ |!
(t) w 11
n
Mn n
[ T (1))
(t)
n?
(a)
[1--1
(8)
w=112
T/
|VS 1: (0)) +
2n [V[w,; (1) (1))²
2Mn
Mn
2n
(Vi(w,; π (1) (i))
w.) +
2q.N 1/0 w0
(4)
Mn
||
w.|l2
T
|
10
( ; 19 (1)1
2n
(0
2M
Mn
18

---

21 (V (w.: π (1)), w111 w
(1)
27
( w0 (0) w.)
N 1
| (1)
wwb 1
Mn
n i=1
1 (t)
wr
The
(2) [
27x
Vf(w.; T (1)))*
2M
Mn
1/t VI(wa;; n (1) (1))] + " - -w0"1 w6011
(8)
2nh (Vf(w, π (1) (i)) mn w.) + Mn
N 1
I (0)
w 0 112
n
where (a) follows since The S 2M and (b) follows by the inequality 2(a, b) < |||
Note that E (w, (i)), w w.) = (VF(w.), solution of F. Now sum the derived statement for 1, ....., n and get
w (t) w.) = 0 since w. is global
[/ee(() w.,11 S 1
w.11?
| [V (1
2M n
+ 1h
2
+ 1
1
V f(
1/t (0)0
(1) :-
w
(1)
wo
M
71
71
21 1
Σ
|| 1100
wo
(t)
M
(2,22)
S 1mm6
w
1/s
Σ
[V (
2M n
1=1
+
(
2
+
noo +
1
1w/0
(2)
=. +
16I2
o. + 2n
M
3
2N
Σ
10
(t)
11
100
wo
M
(23)
1100
(2)
w.ll" 11
Tt
[V
(2))1
2M
2
8L3T1²²
|| (1) - w. w. + 16LL'R
+ 1
11107
0²
+ 2n
M
3
3
I.N 1p.
w. 112 + 32NT, 2
4N
(1(0))
0 +
o²
3M
3M
M
16N
|mm0 (6)
11 -----
02
Mn
Mn
where we apply the derivations from Lemma 3. Now noting that Me 2L n S 1 and rearranging the terms we get:
||m(() 1=111 < |/
(1)
wr111
1h
(0 (1))
(4)
2M
1=1
8L2
16N
8NL²
1/ 12110000
(1)
w..12
3M
M
2
2N
N
N
+1+
no?
M
3L2
2L2
3M
ML2
ML
Since (L) (t+1) We, we have the desired result in (24).
w/
19

---

C.2 Proof of Lemma 2
Proof. From (24) where B1 and B2 are defined in (25), we have
|m/0 (1+1)_ - w.wl
< (1 + Biml (/20 (2) wo11
Th 2M
(i)))2 + B2no?
1=1
(a)
S
(1 + BBin)) 1100 w.1?
7
Tk
(w)
10 0 क ()))l
+
1 2M
n
+ Y
(0)
-
v ; π
11) (i)l + B2n
2M n
(2)
(1 + B Bin)
1100 (t) w.ll 112
7 1/:
n
V (1) ग (0 (i)1I*
7 2M 7
1 1-
Σ
100 - -w0 (2) 1| + +B20²
+ 2M
1=1
(22)
(1 + B1TT') ) 11/00 (1) - -w.l1
7 It
V [ (0; (0))1 +
7+1 1 2M n.
i=1
11
181
16T.202
+ 2M
(6)
-w- w= + 3
-
11
2
+ 20.
+ BBnii?
3
4n6
1/1 L2
8
+ B1yr² +
11 (1) w2
+
B2 +
1100
3M
M
3M
7
T/ 1
IV - (1))1
+ 1 2M n
B1 + 47
T2
8
1 + ni
|10000 (2) -w,11 +
Bg +
+
no?
3M/
M
3M
2um 1
(t)
x (0)) - [i]]
++1 2M n
i=1
1 + 1 Bi + 47
3M ))
|106 (1) w. w.112 + B2 + Th
811 4
+
M
3M
A puntle
[ F(w!")) - F.]
+1 1 M
1 + 3 Bi + 3M )) 110/6 (1) - -w + BB +
47
7
+ ?
noo 2
4M
6M
7 pTl [ (w0 (1) F.],
x+ 1 M
where (a) follows since - 11b| <
-
- |||| for any y > 0 and (b) follows since 7/: S 27.
(t+1) = wr. we obtain the desired result in (14).
Since we
C.3 Proof of Theorem
A for some X > 0 क Proof. Fort t = I,...,T =
T
T = =1= +
S (1D no
= =(1+ C,D 2333//////22/ 710 = (1 + (1+
DVs
(1 + C. D3 exp (C2 D3)
D
n
5 (1+ (8&31)
< min
(27)
2M 2L
20

---

since (1+2) Se, > O. From (14), we have
1 - + Cink || - w.l2
1
C2
[F((t-1)- - F+] -
| - w.l²
+
(28)
C3 1/t
Canl
C3
We proceed to prove the following inequality for(= t= -=,....,?
1
1
- + Civi -1 S
(29)
7h
7/-1
From (27), and 77 = -Tt-1 where = (1+ (3 we have
Cini = C2K2 1/1 = C2K2
17-1
32/3/2 C
DVE
I K2 K
since T-- 5 K
K
K 1
1
since K + (1+0,D))312)
T|-11
T/-1
Kitt-1
1
1
since T) KT
Kyp-1
T
fort I....,T. T. Hence, from (28), we have
1
|
+Cin?
1
C2
[F((,,1)) - F.] 5
+
1|00=1-000 -
[4 - w.11 -w,lw
C
7/
Call
Ca
1
w.ll2 1
C2 o²
|0,-
| w. 112 +
-3
Cznlt
C3
Averaging the statement above for t 1,....
......T, T. we have
C2
F(Wr-1) - F. Cs7ou |00 w.
(a) K expp
g3/2
C2
11000 w.l 1| +
C3 o
C3DVē
K cxxp(A,,D3 D3)
C2
11000
1000-,111 5 +
1.
C3 0.
CzDA
where (a) follows since nnu
DVee expp(AC D3J
and T
2375
C.4 Proof of Corollary
Proof. Choose 12. we have
C SL2
3 + 11NL" 4
M
3M5
C2 2 + 1 + 61
5
+ 3MI3
SN
T2MT.
C3 1=41 M
Note that K = 1 1 ++C+ g3 and C, D3 = -1/X, we get that K = 1 < 2. We continue from the statement of Theorem 2 and the choice C₁ 13 1:
1
K (exp(AC,DD)
C2
F 11
F.)
1
11112 2 +
0
T
C&DA
C3
1=1
2
C D2 exp(A
C2 02 since K 2
| w. 1|
CDD3X
Cs
Cs
20, D2
C2
<
1
w.ll2.e+
x²
since DD =1
C2
C3
21

---

20, D2E
C2
1000
w.ll2 .
Pe
equation (9)
C3
C3
20 D
C2P
1100
wa1l2
Ge
C3
C3
with
20 20
C2P
G
100
w.
C3
C3
Let < S 1 and choose Ge. Then the number of iterations
XG
T 3//2
83/2
2C; w.112 + C2P 3/2
C3
(2C, 12,DDeellus 11112 C2P)
23/2
C2D&C
3/2
2DPeeliuo w. 11?
8L2 + 14NL
1L²
(2-AM +
+
8N
P
3M
12ML
3//2
3/2
1812 + 14NL2
4L2
D3
1 =
15
3M
I"4I M
guarantee
T -
min [F (F( F.]
ISST
Hence, the total complexity (number of individual gradient computations needed reach é accuracy) is
If we further assume that L, M,, > 1:
3/2
1
22Deell00 1,1
8ML + 14N +
1L2
+
(2+
M
GL
SM
31
8N
12L
5
P
T
g3/2
3/2
882
14N12
D3
M
3M
1++1
< 1
(O((M 31 (
I
3/2
83/2
(M + N23/2
= o
13/2
83/2
(* 3///
and the complexity is O
1072
22


Reviews:
[{"review_id": "5ltdycFsQR", "reviewer": "Reviewer_VXbB", "summary": "The paper analyzes convergence properties of shuffling-type methods (shuffle SGD and incremental gradient) to the global solution under relaxed assumptions for non-convex overparameterized functions. Particularly, the paper relaxes frequently used PL-condition to the averaged PL of local functions $f_i$, which is a weaker assumption under interpolation regime, and also imposes a weak star-smooth convex condition.", "questions": "1. Is assuming both Assumption 5 and Assumption 3 still weaker than just assuming PL (Def 1) ?\n\n2. Is there a relation between a constant N and sigma ? (to compare the rates in Table 1). \n\n3. Is the epsilon in line 241 the same as the epsilon in Assumption 4 ? If not, change the notation. \n\n4. I did not find the definition of parameter $\\lambda$ (used in line 241) in the paper. \n\n5. Which variant of shuffling SGD was used in experiments ?", "limitations": "yes", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "- The paper is well written and easy to follow. All the assumptions are well explained in the paper. \n- Related works are well explained. \n- I did not check the proof details but the convergence rate looks correct (although it seems it is possible to improve convergence rate for shuffle SGD variants).", "weaknesses": "1. My main concern is that the set of assumptions is not well motivated: would be nice to see examples of functions that do not satisfy PL-condition, but satisfy your relaxed conditions.\n\n2. It is unclear how tight this bound is under proposed assumptions. Assuming PL, it is possible to achieve faster $\\epsilon^{-1/2}$ convergence. Is it not possible to achieve under your set of assumptions ? \n\n3. The paper advertises a lot analyzing shuffling-type algorithms, however its convergence rates are same as for the incremental gradient methods. For random reshuffling and single shuffling SGD faster dependence on the number of functions $n$ is possible to achieve.\n\n4. I did not understand why in experiments the initial labels are changed. Wouldn’t it be enough just to take a large over-parameterized model ? Modifying the training data seems strange to me, especially because usually the purpose of the theory is to explain the realistic training scenarios. Coming up with new datasets that explain the theoretical results makes it look like the theory doesn’t apply to realistic training scenarios.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**Thank you so much for your time and your positive evaluations of our paper. We also thank you for your constructive comments and suggestions. We hope that our responses below answer all of your questions. Should you need any other clarification, please leave a comment and we are happy to discuss with you. While we are not able to upload a revision for the rebuttal, we will add all the details of our discussion to the next version.**\n\n> My main concern is that the set of assumptions is not well motivated: would be nice to see examples of functions that do not satisfy PL-condition, but satisfy your relaxed conditions.\n\nThe traditional PL condition $|| \\nabla F(w)||^2 \\geq 2 \\mu [F(w)-F_*]$ is quite strong because it implies that every stationary point of the objective function $F$ is also a global minimizer ($|| \\nabla F(w)||^2=0 \\Rightarrow F(w)-F_*=0$), which is not true for most of the neural networks. Hence we are motivated to consider weaker assumptions, e.g. we have proved that the PL condition on $F$ is stronger than our average PL assumption under over-parameterized settings (section 2.1, line 174). More importantly, we showed that our `average PL' condition holds for a wide class of neural networks with squared losses (in Theorem 1). Note that this general class of networks does not satisfy the PL-condition. \n\n> It is unclear how tight this bound is under proposed assumptions. Assuming PL, it is possible to achieve faster $\\epsilon^{-1/2}$ convergence. Is it not possible to achieve under your set of assumptions?\n\nIt is well-known that the property and behavior of the PL condition on $F$ is close to strongly convex conditions. Therefore, it is possible to obtain similar convergence rates for the PL condition on $F$ as in the strongly convex cases. As mentioned above, the PL condition on $F$ implies that every stationary point of the objective function $F$ is also a global minimizer, which is a strong assumption since the convergence criteria for non-convex problems is based on $|| \\nabla F(w)||^2=0$ which automatically implies the global solution. For our set of assumptions, we cannot imply that a stationary point of the objective function $F$ is also a global minimizer. Therefore, our set of assumptions do not have such nice properties like the PL condition on $F$ or strongly convex, and the current results are the best we can do so far.\n\n> The paper advertises a lot analyzing shuffling-type algorithms, .... For random reshuffling and single shuffling SGD faster dependence on the number of functions $n$ is possible to achieve.\n\nThe shuffling-type scheme can be understood as generating any permutation including incremental gradient methods, single shuffling, and random reshuffling. The goal of our analysis is focusing on the analysis for the general shuffling-type scheme. We thank you for your suggestion to improve the convergence bounds for random reshuffling schemes. This is an interesting question that we have considered before submission. However, showing improvement in the overall bound for RR is nontrivial since we are using different proof techniques compared to the previous work and we were only able to improve a factor of $n$ in one of the terms in the final bound. Although it may be possible to further improve the results, we strongly believe that the current contributions already merit publication. Due to the time limit, we leave the question of improving the rate for RR scheme to future work.\n\n> Modifying the training data seems strange to me, especially because usually the purpose of the theory is to explain the realistic training scenarios...\n\nInitially, we modified the training data in order to make sure that there exists a solution that interpolates the data. Thus this satisfies our purpose to show that the algorithm could find a global solution (and the modification on the data is not much). We agree with you that the alternative option is to find a large over-parameterized model, however, we cannot theoretically check how over-parameterized the model should be to guarantee that the interpolation exists, unless the loss function is trained to the minimizer in the experiment (which is the goal we are trying to demonstrate). We also note that our theory can only be partially/closely matched with realistic scenarios (as in our effort with Assumption 3), it can only match partially/approximately as our theory offers strong results (convergence to global solutions).\n\n> Is assuming both Assumption 5 and Assumption 3 still weaker than just assuming PL\n\nTo the best of our knowledge, the two settings are not comparable. However, as mentioned above, the PL condition on $F$ has a very nice behavior since it implies that every stationary point of the objective function $F$ is also a global minimizer (which is a key for non-convex analysis since it just needs to find a stationary point to guarantee the global solution). We note that our assumptions do not have such property.\n\n> Is there a relation between a constant N and sigma\n\n$\\sigma^2$ in Table 1 is a bounded variance constant while $N$ is a different constant that we introduce in this paper. They are from different assumptions so they don't have any relation.\n\n> Is the epsilon in line 241 the same as the epsilon in Assumption 4?\n\n$\\epsilon$ in line 241 is the same as $\\epsilon$ in Assumption 4.\n\n> I did not find the definition of parameter $\\lambda$ (used in line 241) in the paper.\n\nThe parameter $\\lambda$ is a hyper-parameter that can be any constant greater than $0$. This $\\lambda$ shows how the number of iterations of the algorithm compared to some order of epsilon.\n> Which variant of shuffling SGD was used in experiments?\n\nWe use random reshuffling scheme for the experiments. \n\n**Finally, we hope our answers address all of your questions. We thank you again for your positive evaluations of our paper. When all your concerns are resolved, we sincerely hope that you could consider increasing your score and support us.**"}, {"review_id": "kUoLdBhZ6V", "reviewer": "Reviewer_7CVX", "summary": "Shuffling-type SGD is widely used in practice, for which the prior works only provide gradient norm guarantees in nonconvex settings. This paper studies the convergence to a global solution for shuffling-type gradient algorithms under nonconvex settings, under a new analytical framework of more relaxed nonconvex assumptions, i.e., average PL condition and generalized star-smooth-convex condition. ", "questions": "1. The notation in Section 4 is confusing. The authors used $\\epsilon$ in Assumption 4, but in Line 254 they say ``$\\hat{\\epsilon}$ in Assumption 4''. I feel that the authors are meant to use $\\hat{\\epsilon}$ for Assumption 4.\n2. Could the authors comment on the comparison between the average PL condition and PL condition when $\\sigma_*^2 \\neq 0$?\n2. Could the authors explain the reason of adding the term $\\frac{1}{n}\\sum_{i = 1}^{n}||w_i^{(t)} - w_0^{(t)}||^2$ in Assumption 5? Does it help the analysis? Can this term be changed to only dependent on $w_{i - 1}^{(t)}$? Because from the discussion in the paper, this term is added to allow negative $\\langle \\nabla f(w;i) - \\nabla f(w_*; i), w - w_* \\rangle$.\n3. In prior works for shuffling-type SGD, the coefficient in front of $\\sigma_*^2$ in the convergence bound like Eq. (17) in Theorem 2 usually depends on the stepsize $\\eta_t$, then one can take $\\eta_t = O(1/T)$ to guarantee exact convergence to the solutions. However, I see the constant coefficient for $\\sigma_*^2$ in Eq. (17), and the authors are choosing increasing stepsizes as $\\eta_t = K\\eta_{t - 1}$ where $K > 1$ (meaning the initial stepsize needs to be very small). Could the authors explain the intuition for this stepsize choice and the reason not getting stepsize-dependent coefficient? ", "limitations": "Please see the weaknesses and questions above. ", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. The authors generalize two assumptions -- PL condition and star-M-smooth-convex condition -- to investigate the convergence to global solutions in nonconvex settings. Although average PL condition: cannot be directly compared with PL condition, in the interpolated settings (all component functions share the same minimizer) the average PL condition is weaker than PL condition and also covers certain neural networks with squared loss functions. \n2. The authors provide a convergence guarantee of shuffling-type SGD towards global solutions under new assumptions, while the prior works only investigate either the global convergence for SGD sampling without replacement or the gradient norm guarantees for shuffling-type SGD.", "weaknesses": "1. I appreciate the discussion on the comparison between the average PL condition and PL condition the authors made in the main paper, and the applicability of average PL condition in neural networks. However, I am not sure about the comparison between these assumptions beyond the interpolated settings (which seems a strong and restricted assumption).\n2. For the generalized star-M-smooth-convex condition (Assumption 5), I understand that the term $\\frac{1}{n}\\sum_{i = 1}^{n}||w_i^{(t)} - w_0^{(t)}||^2$ allows for more flexibility as the inner product term on the R.H.S. can be negative. But it still looks a bit unnatural to me, especially it depends on the all the iterates from the next (future) cycle generated by the algorithm.\n3. Here is my major concern. The final result obtained in Theorem 2 with **increasing** learning rates only guarantees the convergence to global solutions within a fixed neighborhood of radius $O(\\hat{\\epsilon})$. The increasing learning rate does not match the empirical practice.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**Thank you so much for your time and your appreciation that the contribution and soundness of our paper is good. We hope that our responses below answer all of your questions. Should you need any other clarification, please leave a comment and we are happy to discuss with you. While we are not able to upload a revision for the rebuttal, we will add all the details of our discussion to the next version of our paper.**\n> I appreciate the discussion on the comparison between the average PL condition and PL condition the authors made in the main paper, and the applicability of average PL condition in neural networks. However, I am not sure about the comparison between these assumptions beyond the interpolated settings (which seems a strong and restricted assumption). and Could the authors comment on the comparison between the average PL condition and PL condition when $\\sigma_{*}^2 \\neq 0$?\n\nBeyond the interpolated settings, these two assumptions are not comparable. However, the PL condition on $F$: $|| \\nabla F(w)||^2 \\geq 2 \\mu [F(w) - F_*]$ is quite strong because it implies that every stationary point of the objective function $F$ is also a global minimizer ($|| \\nabla F(w)||^2=0 \\Rightarrow F (w) - F_* = 0$), which is not true for most of the neural networks. The convergence criteria for non-convex is based on $|| \\nabla F(w)||^2 = 0$ so it automatically implies the global solution if we could find a stationary point. For our set of assumptions, we cannot imply that a stationary point of the objective function $F$ is also a global minimizer. Moreover, we showed that our `average PL' condition holds for a wide class of neural networks with squared losses (in Theorem 1). Therefore, we believe that our average PL condition is more reasonable. In addition, over-parametrized setting is well-known in deep learning applications where the the number of parameters of a neural network is very large and could interpolate the data (see e.g. [Schmidt and Roux, 2013, Ma et al., 2018, Meng et al., 2020, Loizou et al., 2021]) (that is $\\sigma_*^2 = 0$).\n> the term $\\frac{1}{n} \\sum_{i=1}^n ||w_i^{(t)}-w_0^{(t)}||^2$… looks a bit unnatural to me\n\nWe would like to note that our analysis also holds under condition: $ ||\\nabla f(w_{i-1}^{(t)};\\pi^{(t)}(i))-\\nabla f(w_*;\\pi^{(t)}(i))||^2 \\leq M \\langle \\nabla f(w_{i-1}^{(t)};\\pi^{(t)} (i))-\\nabla f(w_*;\\pi^{(t)}(i)), w_{i-1}^{(t)}-w_* \\rangle$ (star-M-smooth-convex in Definition 2) without needing the term $N \\frac{1}{n}\\sum_{i=1}^{n}||w_{i}^{(t)} - w_{0}^{(t)}||^2$. Our Lemma 2 in the Appendix shows that the class of star-smooth-convex function is broader than the class of $L$-smooth and star-convex functions -- non-convex class functions which were widely considered in the literature (see e.g. Zhou. et al, \"SGD Converges to Global Minimum in Deep Learning via Star-convex Path\", ICLR 2019). We added the term $N \\frac{1}{n} \\sum_{i=1}^{n}||w_{i}^{(t)}-w_{0}^{(t)}||^2$ just to allow extra flexibility for our setting. We can simply assume star-M-smooth-convex condition in Definition 2 without depending on the algorithm iterates and obtain the desired results. We will clarify this in the next version of our paper. \n> the increasing learning rate does not match the empirical practice.\n\nThe increasing learning rates are not really an issue as long as they are still smaller than some threshold (in our case in Theorem 2: $0 < \\eta_t \\leq \\min (\\frac{n}{2M},\\frac{1}{2L})$). There are some existing work with increasing learning rates, see e.g. [Tran-Dinh et al, A Hybrid Stochastic Optimization Framework for Composite Nonconvex Optimization, Math. Programming, 2022]. Although our guarantee for a global solution is within a fixed neighborhood of radius $\\mathcal{0}(\\hat{\\epsilon})$, this $\\hat{\\epsilon}$ can be chosen to be small for some desired accuracy. Moreover, our learning rate is only increased by a small factor of $1+C*\\epsilon^{3/2}$, which does not change the training process much. In fact, we have experimented with learning rate increasing by small factor (approximately 0.0001-0.000001) where the training trajectory is not much different from the constant learning rate. We will add the results in our revised version.\n> I feel that the authors are meant to use $\\hat{\\epsilon}$ for Assumption 4.\n\nWe define $\\epsilon=\\hat{\\epsilon}/G$ in Line 251 in Corollary 1. In Assumption 4, it is $\\epsilon$.\n> Could the authors explain the reason of adding the term $\\frac{1}{n} \\sum_{i=1}^n||w_i^{(t)}-w_0^{(t)}||^2$ in Assumption 5? Does it help the analysis?\n\nAs we mentioned above, we do not need to add the term $N \\frac{1}{n} \\sum_{i=1}^{n}||w_{i}^{(t)}-w_{0}^{(t)}||^2$ for our analysis in order to obtain the desired result. We do this just to allow extra flexibility for our setting.\n> Could the authors explain the intuition for this stepsize choice and the reason not getting stepsize-dependent coefficient?\n\nWe thank you for your question! Our proof techniques are different from the previous works since we use different settings to obtain the convergence to a global solution while the previous work can only guarantee the convergence to a stationary point in the non-convex cases. Therefore, it is not strange if we could obtain a different bound including the constant coefficient for $\\sigma_*^2$ as in Eq. (17). For this reason, we also need Assumption 4 (small $\\sigma_*^2$ for overparametrized setting) to guarantee the $\\epsilon$-accurate global solution. We choose a learning rate $\\eta_t=K \\eta_{t-1}$ in order to handle the recursive derivation in Eq. (28) in Appendix to obtain the desired result. Note that finding a global solution for a non-convex problem is very critical in optimization for machine learning.\n\n**Finally, we hope our answers address all of your questions. Since you appreciate the contributions of our paper, when all your concerns are resolved, we hope that you could re-evaluate the paper and consider increasing your score and support our approach.**"}, {"review_id": "dhMB5NqqPo", "reviewer": "Reviewer_MeiV", "summary": "In this paper, the authors demonstrate the convergence of the shuffling version of Stochastic Gradient Descent (SGD) to a global solution for a class of non-convex functions. Notably, the analysis of the algorithm relies on more relaxed non-convex assumptions compared to previous works, while maintaining the same computational complexity as shuffling SGD in the convex setting.", "questions": "In regards to Assumption 3, the authors claim that it is a weaker condition compared to assuming the PL inequality for every component function. However, when examining the example provided in Theorem 1 to satisfy Assumption 3, it appears that the presented example actually satisfies the PL inequality for every component function.\nIs there are any well-known loss functions that fulfill Assumption 3 without necessarily satisfying the stronger condition of PL inequality for every component function?", "limitations": "yes", "rating": 6, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 2, "strengths": "1. The paper is clear and well written. Moreover, the motivation for the paper is well-explained.\n\n 2. The authors assume more relaxed assumptions compared to previous work in the non-convex setting. The authors explain carefully the assumption and the contribution upon previous works.\n\n3. By leveraging these assumptions, the authors derive a novel complexity bound for achieving convergence to a global minimizer. Notably, this complexity matches the performance of unified shuffling methods in previous works, which aimed for convergence to a stationary point.", "weaknesses": "A potential weakness of the paper is that the analysis, upon closer inspection, appears to follow a relatively straightforward path and bears similarities to previous works. In this context, the main distinguishing factor is the introduction of the average PL condition, which specifically enables the establishment of a bound for the shuffling version of SGD.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**Thank you so much for your time and for your positive evaluations of our paper. We also thank you for your appreciation of our novel complexity bound. We hope that our responses below answer all of your questions. Should you need any other clarification, please leave a comment and we are happy to discuss with you. While we are not able to upload a revision for the rebuttal, we will add all the details of our discussion to the next version of our paper.** \n\n\n> A potential weakness of the paper is that the analysis, upon closer inspection, appears to follow a relatively straightforward path and bears similarities to previous works. In this context, the main distinguishing factor is the introduction of the average PL condition, which specifically enables the establishment of a bound for the shuffling version of SGD.\n\nWe thank you for your comment! We believe that our proof techniques are novel and different from the previous works since we use different settings to obtain the convergence to a global solution while the previous work can only guarantee the convergence to a stationary point in the non-convex cases. Note that finding a global solution for a non-convex problem is very critical in optimization for machine learning. \n\n\n> In regards to Assumption 3, the authors claim that it is a weaker condition compared to assuming the PL inequality for every component function. However, when examining the example provided in Theorem 1 to satisfy Assumption 3, it appears that the presented example actually satisfies the PL inequality for every component function. Is there are any well-known loss functions that fulfill Assumption 3 without necessarily satisfying the stronger condition of PL inequality for every component function?\n\nWe thank you for your insightful question! Indeed, Assumption 3 is weaker than the PL condition for every component function, and it is a strength of our analysis as it can deal with a more general assumption. While we are not aware of a well-known loss function that satisfies Assumption 3 without satisfying the component PL condition, it is an interesting research question. We note that since Theorem 1 already covers a broad class of neural networks with squared losses, it is understandable that the broader class may cover some of the machine learning losses. Thus the details of what other problems can be satisfied by our average PL assumption is a future research direction. This shows the potential of our work.\n\n**Finally, we hope our answers address all of your questions. We thank you again for your positive evaluations of our paper.  When all your concerns are resolved, we sincerely hope that you could consider increasing your score and support us.**"}, {"review_id": "vuRbes1gns", "reviewer": "Reviewer_JrBJ", "summary": "This paper provides the convergence to a global solution of `shuffling' SGD (where the index set is permuted and apply gradient updates according to the permutation order) for a class of non-convex functions, in the over-parameterized setting.", "questions": "Please provide bounds on the constants in Assumption 5 for some concrete example classes of non-convex functions which were not included in previous global convergence proofs.\n\n\n\n", "limitations": "yes", "rating": 5, "confidence": 4, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "The paper provides a good comprehensive background of previous work on the convergence of shuffling SGD. The theoretical results are stated clearly, and experiments on real data sets are implemented.", "weaknesses": "The big weakness of the paper is that the class of non-convex functions under consideration is not defined using interpretable or standard assumptions.  In particular, I am skeptical that this non-convex class is  weaker than previously considered function classes (in particular, the PL condition of Nguyen et al.)\n\nThe problem is that the quantities in Assumption 5 are not calculable beyond the convex setting;  only in the convex setting is it clear what the constant N in Assumption 5 is  (where N=0).  Beyond the convex setting, there is no way to measure N and in turn, gauge the sample complexity results presented in this paper.   \n\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**Thank you for your constructive comments on our paper. We hope that our responses below answer all of your questions. Should you need any other clarification, please leave a comment and we are happy to discuss with you. While we are not able to upload a revision for the rebuttal, we will add all the details of our discussion to the next version of our paper.** \n\n> The big weakness of the paper is that the class of non-convex functions under consideration is not defined using interpretable or standard assumptions. In particular, I am skeptical that this non-convex class is weaker than previously considered function classes (in particular, the PL condition of Nguyen et al.)\n\nWe would like to note that the PL condition on $F$ (in Nguyen et al): $|| \\nabla F (w) ||^2 \\geq 2 \\mu [ F (w) - F_* ]$ is quite strong because it implies that every stationary point of the objective function $F$ is also a global minimizer ($|| \\nabla F (w) ||^2 = 0 \\Rightarrow F (w) - F_* = 0$), which is not true for most of the neural networks. The convergence criteria for non-convex is based on $|| \\nabla F (w) ||^2 = 0$ so we only need to find a stationary point and automatically it is the global solution. For our set of assumptions, we cannot imply that a stationary point of the objective function $F$ is also a global minimizer. \n\nMoreover, we rigorously showed that our `average PL' condition (Assumption 3) holds for a wide class of neural networks with squared losses (in Theorem 1) -- so we do not even need to assume it since we already proved it. \n\nIn addition, we would like to note that our analysis also holds under condition: $ || \\nabla f(w_{i-1}^{(t)};\\pi^{(t)} ( i )) - \\nabla f(w_*;\\pi^{(t)} ( i )) ||^2 \\leq M \\langle \\nabla f(w_{i-1}^{(t)}; \\pi^{(t)} ( i )) - \\nabla f(w_*;\\pi^{(t)} ( i )), w_{i-1}^{(t)} - w_* \\rangle$ (star-M-smooth-convex in Definition 2) without needing the term $N \\frac{1}{n} \\sum_{i=1}^{n} || w_{i}^{(t)} - w_{0}^{(t)} ||^2$. Our Lemma 2 in the Appendix shows that the class of star-smooth-convex function (a class of non-convex functions) is broader than the class of $L$-smooth and star-convex functions -- non-convex class functions which were widely considered in the literature (see e.g. Zhou. et al, \"SGD Converges to Global Minimum in Deep Learning via Star-convex Path\", ICLR 2019). We only added the term $N \\frac{1}{n} \\sum_{i=1}^{n} || w_{i}^{(t)} - w_{0}^{(t)} ||^2$ since to allow extra flexibility for our setting. We can simply assume star-M-smooth-convex condition in Definition 2 without an extra term of $N \\frac{1}{n} \\sum_{i=1}^{n} || w_{i}^{(t)} - w_{0}^{(t)} ||^2$. \n\nFor these reasons, we politely disagree with your impression that our assumptions are not interpretable. Since the PL assumption implies a global minimizer on stationary points, it might not be an effective tool to fully explain the behavior of training problems. On the other hand, our ‘average PL’ assumption is proved for a general class of neural networks with squared losses, which is a good way to interpret the assumption. \n\n\n> The problem is that the quantities in Assumption 5 are not calculable beyond the convex setting; only in the convex setting is it clear what the constant N in Assumption 5 is (where N=0). Beyond the convex setting, there is no way to measure N and in turn, gauge the sample complexity results presented in this paper and Please provide bounds on the constants in Assumption 5 for some concrete example classes of non-convex functions which were not included in previous global convergence proofs.\n\nThank you for your comment. We believe this is a minor misunderstanding as we do not need to add the term $N \\frac{1}{n} \\sum_{i=1}^{n} || w_{i}^{(t)} - w_{0}^{(t)} ||^2$ for our analysis in order to obtain the desired result. We do this just to allow extra flexibility for our setting. Even without this term (i.e. $N = 0$), our class function is still non-convex since it is broader than the class of $L$-smooth and star-convex functions -- non-convex class functions which were widely considered in the literature (see e.g. Zhou. et al, \"SGD Converges to Global Minimum in Deep Learning via Star-convex Path\", ICLR 2019). We will consider removing the term with $N$ if you think it clarifies our paper better.\n\n**Finally, we hope our answers address all of your questions. Please do not hesitate to contact us if you need any additional clarifications regarding the assumptions of our paper. Although our assumption might not be standard and might not appear in prior work, we believe it offers novelty and interpretations to the setting of neural networks with squared loss function. We are looking forward to discussing these details with you. After our discussions, we kindly ask that you re-evaluate the paper and consider increasing your score.**"}]

Author rebuttal:
**General Response:** 

**First of all, we would like to thank the AC and all other reviewers for your hard work and for reviewing our paper.** 

**To all reviewers:** Below we first highlight our contributions for you to have a better overview of our paper, after which we clarify current misunderstanding and/or confusion around our work. By addressing your concerns we hope you will be motivated to discuss our paper with us and clear up any remaining unclarity.  

We emphasize that finding a global solution for a non-convex problem is very critical in optimization for machine learning. We further note that it is impossible to guarantee convergence to a global solution in a general non-convex setting without additional assumptions, and certain existing results rely on strong properties (e.g convexity, PL, strong growth) to obtain this. Our paper proposes another perspective of showing the convergence to a global solution by taking the advantage of the `average PL' condition which we show it holds for a wide class of neural networks. Overparametrized setting is a well-known setting in deep learning applications where the the number of parameters of a neural network is very large and could interpolate the data (see e.g. [Schmidt and Roux, 2013, Ma et al., 2018, Meng et al., 2020, Loizou et al., 2021]) (that is $\sigma_*^2 = 0$). 

We emphasize that our main contributions are in the form of a new developed theoretical framework to show the convergence to a global solution of shuffling type gradient algorithms. We have also provided some experiments to confirm our theory. Our theoretical results are significant since we are the first to obtain the convergence to a global solution for this class of non-convex problems. To the best of our knowledge, we are the first to provide the 'average PL' condition and show that it holds for a wide class of neural networks. Therefore, our theoretical results are significant: finding a global solution for a class of non-convex problems is an important and non-trivial problem. 

**This general response together with our individual responses to each reviewer address the reviewers' concerns. Given the significance of our theoretical and algorithmic framework which provides global convergence for non-convex problems, we sincerely encourage the reviewers to re-evaluate our work and consider increasing their scores.** 

**Please do not hesitate to contact us if there are additional clarifications that we can make to convince the reviewers of the significance of our paper. We appreciate AC’s effort and time to handle the review discussion and we also value all the reviewers’ feedback and comments. We are looking forward to receiving follow-up responses and giving clarifications to help the discussion of our work.**

Sincerely,

Authors


Meta-review: The paper analyzes the convergence of gradient-based optimizers under arbitrary orderings of the training data, also known as shuffling-type methods or incremental gradient. It analyzes convergence to the global solution under relaxed assumptions for non-convex over-parameterized objectives. Particularly, the paper relaxes frequently used PL-condition to the averaged PL of local functions, which is a weaker assumption under interpolation regime, and also imposes a weak star-smooth convex condition.

After discussion and feedback, the consensus is that this paper gives valuable contributions under interesting assumptions. The assumptions are particularly crucial as most literature uses assumptions far from realistic non-convex functions, so we positively evaluated the non-standard and more relaxed assumptions used here instead, although in some cases they could be explained more (e.g. specific examples showing the new assumptions are weaker).

Overall, the paper is well written, and we hope the detailed feedback can help to clarify the camera-ready version of the paper.
Decision: Accept (poster)