Incremental Gradient Descent with Small Epoch Counts is Surprisingly Slow on Ill-Conditioned Problems
Authors: Yujun Kim
Jaeyoung Cha
Chulhee Yun
Venue: ICML 2025 poster (2025)
Keywords: Permutation-based SGD
Incremental Gradient Descent
Lower Bound
Convex Optimization
Primary area: theory->optimization
TL;DR: We study Incremental Gradient Descent in the small epoch regime and show that it exhibits severe slowdown especially in the presence of nonconvex components.

Abstract: Recent theoretical results demonstrate that the convergence rates of permutation-based SGD (e.g., random reshuffling SGD) are faster than uniform-sampling SGD; however, these studies focus mainly on the large epoch regime, where the number of epochs $K$ exceeds the condition number $\kappa$. In contrast, little is known when $K$ is smaller than $\kappa$, and it is still a challenging open question whether permutation-based SGD can converge faster in this small epoch regime (Safran and Shamir, 2021). As a step toward understanding this gap, we study the naive deterministic variant, Incremental Gradient Descent (IGD), on smooth and strongly convex functions. Our lower bounds reveal that for the small epoch regime, IGD can exhibit surprisingly slow convergence even when all component functions are strongly convex. Furthermore, when some component functions are allowed to be nonconvex, we prove that the optimality gap of IGD can be significantly worse throughout the small epoch regime. Our analyses reveal that the convergence properties of permutation-based SGD in the small epoch regime may vary drastically depending on the assumptions on component functions. Lastly, we supplement the paper with tight upper and lower bounds for IGD in the large epoch regime.

Incremental Gradient Descent with Small Epoch Counts is Surprisingly Slow on Ill-ondditonned Problems
Yujun Kim
Jaeyoung Cha 11
Chulhee Yun
Abstract
where the objective F(x) is the average of finite number of component functions f(()). In modern deep learning ap- plications, the number of components is often extremely large, making full gradient optimization methods compu- tationally expensive.
Recent theoretical results demonstrate that the convergence rates of permutation-based SGD (e.g., random reshuffling SGD) are faster than mniform-sampling SGD; however, these studies focus mainly on the large epoch regime, where the number of epochs K exceeds the condition number K. In contrast, little is known when K smaller than 6, and it is still challenging open question whether permutation- converge faster in this small epoch regime (Safran & Shamir, 2021). As a step toward understanding this gap, we study the naive deterministic variant, Incremental Gradient Descent (IGD), on smooth and strongly convex functions. Our lower bounds reveal that for the small epoch regime, IGD can exhibit surprisingly slow convergence even when all component functions are strongly convex. Fur- thermore, when some component functions are al- lowed to be nonconvex, we prove that the optimal- ity gap of IGD can be significantly worse through- out the small epoch regime. Our analyses reveal that the convergence properties of permutation- based SGD in the small epoch regime may vary drastically depending on the assumptions on com- ponent functions. Lastly, supplement the paper with tight upper and lower bounds for IGD in the large epoch regime.
address this, stochastic gradient descent (SGD) and its variants have gained attention for their computational efficiency and scalability (Lan, 2020).
SGD methods can be categorized based on the strategy used to select the component index i(t) at iteration t: (1) with- replacement SGD, and (2) permutation- -assd SGD. In with- replacement SGD, also known as each index drawn independently from uniform distribu- tion over {1, (..,...., n).
SGD can
SGD,
This approach has been the primary focus of theoretical studies, as it guarantees the stochastic gradient at each step to be unbiased estimator of the gradient of the overall objective F (Bubeck et al., 2015).
.
In contrast, permutation-based SGD- indices are sampled in a shuffled order, also referred to as without- replacement SGD or shuffling gradient methods-is more commonly used in practice. Its popularity arises from strong empirical performance and simplicity of implementation, making it the standard choice for real-world machine learn- ing applications. However, despite its widespread use, the theoretical understanding of permutation-base SGD had remained underdeveloped until recently, due to challenges arising from the lack of independence between iterates.
Nevertheless, recent advances have successfully addressed the theoretical challenges of permutation-basse (Haochen & Sra, 2019; Nagaraj et al., 2019). For exam- ple, Random Reshuffling (RR), one of the most common permutation- methods, randomly shuffles the indices at the start of each epoch. has been thcoretically shown that RR achieves a convergence rate of (11/kK²) for smooth and strongly convex objectives, which is faster than the rate O(1 ((]/KK) of with-replacement SGD,, where K is the num- ber of epochs (Ahn et al., 2020; Mishchenko et al., 2020).
SGD
1. Introduction
Many machine learning and deep learning tasks can be formulated as finite-sum minimization problems:
min ZE
F(x)
f((x),
'Equal contribution 'Kim Jaechul Graduate School of AI, Korea Advanced Institute Science and Technology. Correspondence to: Chulhee Yun <chulhee. yun kaist.ac.kr>>.
While these results suggest that RR. is theoretically superior to with-replacement methods, the story is far from complete. Existing analyses of permutation-based SGD are mostly restricted the large epoch regime, where K sufficiently large relative the problem's 's condition number (delined
Proceedings of the 4nnd International Conference Machine Learning. Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).

---

Incremental Gradient Descent with Small Epoch Counts is Surprisingly Slow on Ill-Conditioned Problems
in Section 2. However, this regime is often unrealistic in practical machine learning scenarios, especially when training large language models. Neural network training typically involves highly ill-conditioned optimization land- scapes (L. et al., 2018; Ghorbani et al., 2019), where x is large, and K is comparatively small due to computational constraints. In such cases, the small epoch regime, where K is smaller than K, becomes significantly more relevant, yet its convergence behavior remains poorly understood.
In Section 3.2, we study whether a suitable permutation strategy can accelerate permutation- small epoch regime. We prove that there exists a per- mutation such that repeatedly using it in permutation- based SGD can outperform with-replacement SGD (Theo- rem 3.7). To our knowledge, this is the first result showing the existence of a permutation- SGD method that con- verges faster than with-replacement SGD in this regime.
SGD in the
In Section 4, we establish tight convergence rates for IGD in the large epoch regime. We derive matching lower and upper bound rates, up polylogarithmic factors, for scenarios where all components are convex some nonconvex (Theorems 4.1, 4.3 and 4.4). Unlike in the small epoch regime where nonconvex components significantly slow convergence, the rate gap between these two scenarios is only a factor of K, revealing the clear distinction in the behavior of IGD in the small and large epoch regimes.
In fact, Safran & Shamir (2021) establish a lower bound in strongly convex objectives for RR. revealing that RR can- not outperform with-replacement SGD in the small epoch regime. This highlights the need to further investigate permutation- methods under small epoch constraints and explore whether they can outperform with-replacement SGD in such settings. However, analyzing permutation- based SGD in the small epoch regime poses significant theoretical challenges (as explained in Section 2.4). Even for Incremental Gradient Descent (IGD) (Bertsekas, 2011; 1; Gurbuzbalaban et al., 2019), the simplest permutation based SGD method where components are processed sequentially and deterministically from indices 1 to n in each epoch, its convergence behavior in this regime is not well-understood.
2. Preliminaries
We start by introducing the basic notation used through- out this paper. We use n to denote the number of com- ponent functions and K to denote the total number of epochs. The Euclidean norm is denoted by || ||- For a positive integer N E N, we use [N] to represent the set (1, N). The symbol q = poly(p1,
In this study, as an initial step toward understanding the convergence behavior of permutation-bast SGD in the small epoch regime, we focus on the convergence analysis of IGD. Our study presents convergence rates for both the small epoch regime and the large epoch regime, offering a result that highlights the distinct behavior of permutation- based SGD in the small epoch regime.
means that can be expressed as a finite sum of monomials of the form ppp2 ..p.. where each 6; is a bounded real number (which may be negative or non-integer). Similarly, q = polylog(M1,... ... P.) denotes a function expressible as q E(sa.....)) log" IIie[s P for bounded real and o;.
Importantly, while existing works use O and Ω (or Ô and Ω to hide polylogarithmic factors) to express the growth rates of the convergence rates, we adopt the symbols S and 2 in this paper to describe our results in better detail. Formally, x S y means that there exists a universal constant e >>> 0 such that S c- y polylog(n, K, μr, L...) holds for the specified n, K, and other parameters; vice- versa, 2 y means 2 c. y- polylog(n,, K, μr ....). Unlike O and Ω which are often used to express the asymptotic behavior of the rate as K + co, S and Z here apply to all valid values of K. The reason for using these symbols is that many of the upper and lower bounds in this paper are established in the small epoch regime, where the total number of epochs K is explicitly bounded above by the condition number k.
1.1. Summary of Our Contributions
Our analysis focuses on the setting where the objective F is smooth and strongly convex, and the step size is kept con- stant throughout the optimization process. We summarize our contributions as follows, where the convergence rates reflect the function optimality gap at the final iterate. For a clear overview, we refer readers to Table and Figure 1.
).
In Section 3, we provide convergence analyses of IGD in the small epoch regime. We establish lower bound con- vergence rates under three scenarios (Theorems 3.1, 3.3 and 3.5): (i) strongly convex components sharing the same Hessian, (ii) strongly convex components, and (iii) allow- ing nonconvex components. Additionally, we provide the upper bound convergence rates for the first two cases (The- orem 3.2, Proposition 3.4). Our results indicate that even with stronger assumptions, IGD remains slower than the known upper bound of with with-reepaccement SGD. Further- more, IGD exhibits surprisingly slow convergence even when all components are strongly convex, and the inclusion of nonconvex components further amplifies this slowdown.
2.1. Definitions and Assumptions
We list definitions and assumptions that will be used to describe the function class.
Definition 2.1 (Smoothness). A differentiable function F:: Rd R is L-smooth, for some L. 0, if
VF(2)) - FF(y)) S T.I. - yll. Var, y E Rdd
2

---

Incremental Gradient Descent with Small Epoch Counts is Surprisingly Slow on IIl-Conditioned Problems
Table 1. Summary of our results. All upper bounds, except for Theorem 3.7, apply to arbitrary permutation based SGD. Theorem 3.7
specificallly applies to a permutation-based SGD method proposed in its theorem. All lower bound results apply to IGD. Gradient Assumption
Epoch
Component Assumption
Convergence Rate
Strongly Convex
O
kk
Theorem 3.2
[ )lI - C.
Identical Hessian
Theorem 3.1
(v) VF(x)] 1 G.
nk
L H**
Mishchenko et al. (2020)
[[[((')]] C.
Small K S
Strongly Convex
Ω
L.
min {1, k²
1.2 Theorem 3.3
[[V - VF())] < S [VV Var
(F((m))-F(()))
14"
Potentially Nonconvex
5
G
Theorem 3.5
(Vf - S (
L
2pnk L
Strongly Convex
o
Theorem 3.7'
[Vf(=')]| S.
pa
LG:
o
Liu & Zhou (2024a)
S SC.
Convex
11a
k²*=
Large
52
L.G k=
Theorem 4.1
(V)) S &G
K Z
O
L'G #²k
Theorem 4.42
- - Va
Potentially Nonconvex
Ω
L K
Theorem 4.33
[V[[(a)- - < |V+x|V Va
Only shows the existence of permutation that guaraniees this convergence, and O(va). Roquires K 2 max(u² /x2, xx"") and x 2 n.
Roquires K 2 P)K.
Definition 2.2 (Strong Convexity). A differentiable function F:Rd + TR is p-strongly convex, for some μl > 0, if
2.2. Algorithms
Algorithm Permutation- Based SGD
F(y) F(x) + (VF(w), m)
Input: Initial point æo. Step size 17. Number of epochs K Initialize ad. = 27 for k: = 1 to K do
for all w. y E Rd. If this inequality holds with f O, we say that F is convex.
Generate permutation 0s [m]] + [r]]
Now, we define a common assumption on the objective function used in our analyses.
for to m do x a 1) So. (a.
Assumption 2.3 (Common Assumption). The overall func- tion F: Rd + R is p-strongly convex and each component function f is L-smooth.
end for
k+1 x T end for Output: xx
Additionally, we define the condition number of F as K. 4. which is closely related to the problem geometry. We note that component smoothness is commonly utilized in the literature studying permutation-battt
We present the basic pseudocode for permutation-baas based SGD methods in Algorithm 1. At the start of k-tth epoch, permutation
SGD (Ahn et al., 2020; Mishchenko et al., 2020; Lu et al., 2022a; Liu & Zhou, 2024a).
[r] + [n] is generated. The algorithm then updates the iterate according to the component functions in the order fa,(1), (1) the permutation 0% is generated determines the specific variant of permutation- SGD. Here, we describe some popular methods studied in the literature:
The method by which
Lastly, we introduce assumptions on the gradients. Assumption 2.4 (Bounded Gradient Errors). There exists constants G 2 0 and P 2 0 such that, for all æ E Rd and i E [n].
Incremental Gradient Descent (IGD, Algorithm 2):
(~)) VF(x)) 5 PIVF(>)]I
Each 0g is the identity permutation.
Assumption 2.5 (Bounded Gradients at the Optimum). There exists a constant G. 2 0 such that, for all E [n], the gradient norm of each component function satisfies
Single Shuffling (SS): The first permutation o1 is drawn uniformly at random and reused for all epochs.
Random Reshuffling (RR): Each σ is independently drawn uniformly at random every epoch.
\VA(2")] < G..
Gradient Balancing (GraB (Lu et al., 2022a)): Each d is selected based on observations at the previous epoch.
Our results require either Assumption 2.4 or Assumption 2.5. Notably, whenever Assumption 2.4 holds, Assumption 2.5 also holds with G. = G' because V F F(=") = 0.
It has been widely studied that the performance guaran-
3

---

Incremental Gradient Descent with Small Epoch Counts is Surprisingly Slow on Ill-Conditioned Problems
tees vary drastically with the choice of permutation strategy (Mohtashami et al., 2022; Lu et al., 2022b). In general, one might expect IGD to converge slowly, as the identity mapping could represent the worst-case scenario for con- vergence. In contrast, GraB can be faster than TGD, SS, or RR as it adaptively selects effective permutations over time.
permutation-baseer SGD methods that go beyond RR, focus- ing on manually selecting permutations that induce faster convergence rather than relying random permutations. A notable work by Lu et al. (2022a) proposes practical permutation-based SGD algorithm called GraB and pro- vides a theoretical guarantee of convergence at the rate of Ó 1 R.R ) strictly faster rate than RR. Later, Cha et al. (2023) establishes matching lower bound, confirming that GraB is optimal (for low-dimensional functions).
In this paper, we derive upper bound results for arbitrary permutation-basse SGD, and the lower bound results for IGD. These results allow to characterize how much the convergence of permutation-based SGD deteriorates when permutations are chosen in the worst-case manner. For further clarification of the relationship between the upper and the lower bound, we point readers to Appendix A.3.
We note that most of these works require a condition on K of the form K 2 n² log(nK) with a 2 1.
Small Epoch Analysis. The convergence behavior of permutation- based in the small epoch regime was first ex- plicitly investigated by Safran & Shamir (2021). They pro- vide both upper and lower bounds for RR and SS in both the small and large epoch regimes, with the rates matching ex- actly up to polylogarithnic factors for quadratic objectives with commuting component Hessians. Interestingly, in the small epoch regime, both RR and SS achieve a convergence rate of O ( ), equivalent to the known rate of O ,T for with-replacement SGD, where the total number of itera- tions T can be expressed nK in the without-replacement setting (Shamir & Zhang, 2013; Liu & Zhou, 2024b).
2.3. What is known so far?
For simplicity, in this section, we use the conventional sym- bols O-)) and ?(-) (even for the small epoch regime) to denote upper and lower bounds, respectively. The symbol (-) hides the dependency on polylogarithmic factors. Con- vergence rates are expressed in terms of n, K, μr, and L to represent the optimality gap of the function.
Permutation-Based SGD. Numerous studies have ex- plored the convergence of permutation-based SGD (Bert- sekas, 2011; Recht & Ré, 2012; Haochen & Sra, 2019; Nagaraj et al., 2019; Gurbuzbalaban et al., 2019; Safran & Shamir, 2020; 2021; Ahn al., 2020; Mishchenko et al., 2020; Rajput et al., 2020; 2022; Nguyen et al., 2021; Lu et al., 2022a; Cha et al., 2023; Liu & Zhou, 2024a; Cai & Diakonikolas, 2024). Here, we summarize recent advances in the convergence analysis of the last iterate for strongly convex objectives, and we refer readers to these works for a more comprehensive understanding.
To the best of our knowledge, no meaningful upper bound result with a rate of Ó jun ) has been established for permutation based SGD in the small epoch regime. This rate is of significant importance, as it corresponds to the rate for with-replacement SGD and matches the best-known lower bound for RR in this regime (Safran & Shamir, 2021; Cha et al., 2023). The upper bounds provided by Safran & Shamir (2021) for RR and SS are restricted to quadratic objectives with additional assumptions, and therefore, do not differ significantly from the scenario of a 1-dimensional quadratic objective.
For both RR and SS, under the assumption of component convexity, Mishchenko et al. (2020) derive a convergence rate of Ó L2 ). Later, Liu & Zhou (2024a) improve this (Pnka)
Some knowledgeable readers may point to the results of Mishchenko et al. (2020), which present the conver- gence rates for RR without imposing any constraint on K. Specifically, under component convexity, Theorem 2 of Mishchenko et al. (2020) states
result by factor of K, showing a rate of Ö p ). The corresponding lower bounds, 22( (2 (= ), are established by Cha et al. (2023) for RR and Safran & Shamir (2021) for SS. thereby fully closing the gap between the upper and lower bounds only up polylogarithmic factors.
E
|| x =
eep ===
PK V2L
D2
p2nK2
There are also several works that derive upper bounds appli- cable to arbitrary permutation-ban based SGD, which naturally encompass the convergence of IGD. Under the assumption of component convexity, Liu & Zhou (2024a) establish a rate of Ó( (x),) ), which is slower than the rate for RR by factor of n. For the matching lower bound, Safran & Shamir
where := ||10 x=I|. However, we believe that Theo- rem 2 does not provide a tight bound in the small epoch regime for two reasons. First, the polynomial term induces the function optimality gap of O L'
Lxx)), which is slower
(PnK))
than the lower bound rate for RR by factor of K- Sec- ond, as K decreases below the exponential term grows rapidly and dominates, deviating substantially from the rate of Ō (nn)): ). While their Theorem 1 improves the exponen- tial term by assuming a strong convexity of components, it leaves the polynomial term unchanged. Also, a more recent
(2020) derive a rate of 12( _ ) for IGD, revealing gap of k between the upper and lower bounds.
Recent research (Rajput et al., 2022; Lu et al., 2022b; Mohtashami et al., 2022) has shifted toward exploring
4

---

Incremental Gradient Descent with Small Epoch Counts is Surprisingly Slow on IIl-Conditioned Problems
result by Liu & Zhou (2024a) (Theorem 4.6) refines the polynomial term and also improves the exponential term
vex. For each scenario, establish convergence lower bound and demonstrate degradation in convergence.
to exp (-K/k) LF. However, since the term inside the exponential remains unchanged, this still fails to reveal a
3.1. Convergence Analysis of IGD
tight bound when K' is small.
We introduce our first lower bound result of IGD in the small epoch regime.
While Koloskova et al. (2024) derive an upper bound con- vergence rate for permutation-baat based SGD that does not rely on large K for nonconvex objectives, we were unable to extend their proof techniques to the strongly convex setting to yield a rate of ( pmk
Theorem 3.1. For any 2 2, K 2 2, and K S 12k, there ex- ists a 3 3-dimensional function F satisfying Assumptions 2.3 and 2.4 with P = O, where each component function shares the same Hessian, i.e., V² f((x)) = V F(x) for all E [n] and x E RR², along with an initialization point æ,, such that for any constant step size n,, the final iterate x obtained by Algorithm 2 satisfies
2.4. Why Do Existing Bounds Require Large Epochs?
To understand the challenges in establishing upper bounds for permutation-based SGD, it is important to observe that, unlike with rethareppacement SGD, permutation- based SGD uses each component function exactly once per epoch. There- fore, n steps of update in permutation-basee SGD can be expressed as an approximation of gradient descent on the overall objective, combined with cumulative error term. Much of the prior literature on establishing the upper bounds for permutation-baset SGD focuses on capturing the "cu- mulative error" effect within a single epoch.
G F(z - =F(=) 2 μK
The proof of Theorem 3.1 is presented in Appendix B. Note that if all component functions share the same Hes- sian, they are also u-strongly convex. To the best of our knowledge, the previous best lower bound rate for IGD in this setting was G² (Safran & Shamir (2020)), and Theo- rem 3.1 improves it by factor of K. Additionally, RR has a lower bound of pnk (Safran & Shamir (2021)), and the optimal permutation permutation--aasee based SGD method has a lower bound of LG K= (Cha et al. (2023)) the same setting.
pk²
Technically, to show that the cumulative error within an epoch is small, the step size must be sufficiently small to ensure that the iterate does not move too far during single epoch. Specifically, the step size must be less than (1//nL), where L represents the smoothness parame- ter (Mishchenko et al., 2020; Liu & Zhou, 2024a). However, when the number of epochs K is small, the step size should be larger in order to bring the iterate close to the optimal point. In fact, the step size should be at least as large as a value proportional to 1/K.
For with-replacement SGD, the known upper bound on the function optimality gap is Ga (Liu & Zhou, 2024b),
which is faster than the rate G unk
aK in Theorem 3.1 by factor of n. We emphasize that this comparison is made under conditions advantageous to IGD, as the lower bound from Theorem 3.1 assumes all component functions share the same Hessian, while the upper bound for with-replacement SGD does not require such a condition. However, this comparison has some subtleties: the upper bound rate is derived under varying step size scheme, leaving open the possibility that IGD can converge faster under such a scheme. For a more complete comparison, it would be important to extend Theorem 3.1 to the varying step size setting, which we leave for future work.
These two requirements- need for a small step size to control error within single epoch and the need for larger step size to achieve fast convergence when K is mmallllear to conflict. Consequently, existing analyses generally hold only when K is sufficiently large. While some analyses are valid even when K is small, their bounds are not tight as discussed in the previous subsection.
Next, we present the upper bound for arbitrary permutation- based SGD methods when each component is 1-dimensional and shares the same Hessian.
3. IGD in Small Epoch Regime
We have highlighted that studying permutation-ae bbased SGD in the small epoch regime, where the total number of epochs K satisfies K S R, is both underexplored and highly challenging, despite its practical relevance. As an initial step toward understanding its convergence behavior in this regime, we investigate IGD, the simplest and deterministic permutation based SGD method. We explore this regime un- der three distinct scenarios: (i) each component is strongly convex with a common Hessian, (ii) each component is strongly convex, and (iii) some components may be noncon-
Theorem 3.2. Let 2 1, E KKS K. and an initialization functioonn point Tu. Suppose F is a 1-dimensional function satisfying Assumptions 2.3 and 2.5. Assume that each component function ft shares the same Hessian for all i E [m]] and x E R. Then, for any choice of permutation a% in each epoch, the final iterate oek obtained by Algorithm I with the [[uo G.
step size n pak max (log]
(1xo-=1)) ,1 satisfies
G
μK"
5

---

Incremental Gradient Descent with Small Epoch Counts is Surprisingly Slow on IIl-Conditioned Problems
The proof of Theorem 3.2 is in Appendix C.I. We note that the minimum epoch requirement K 2 is necessary for valid analysis, mentioned in Safran & Shamir (2021) (Remark 2). While Theorem 3.2 additionally requires the objective to be 1-dimensional due to technical challenges, the bound can be directly applied to objectives with diagonal Hessians, which aligns with the construction in the proof of Theorem 3.1.
The proof of Proposition 3.4 is presented in Appendix C.2. The squared distance bound in Proposition 3.4 naturally translates to a function optimality gap of k= Although Theorem 3.3 and Proposition 3.4 do not match in general, they do align when K ((( in this case, both bounds
L'G²
become the rates LG" and LG: μ² to polylogarithmic factors. n achieving tight match up
Now, we present the result for the case where nonconvex components exist. While some slowdown in convergence expected, Theorem 3.5 reveals that it is far more drastic.
Indeed, the function class Theorems 3.1 and 3.2 apply to is restrictive. However, our next theorem indicates that the convergence of IGD deteriorates immediately when the identical Hessian assumption is removed, even when each component function remains strongly convex.
Theorem 3.5. For any n Z 4, K 2 4, and K S 2. there ex- ists a 2-dimensional fanction F satisfying Assumptions 2.3 and 2.4 with P = 3 such that for any constant step size y, the final iterate starting from the initialization point Do = =D,,) satisfies
Theorem 3.3. For any n 2 3, K 2 2, and K S - there exists 4-dimensional function F satisfying Assump- tions 2.3 and 2.4 with P = L, where each component func- tion is p--strongly convex, along with an initialization point an, such that for any constant step size 1, the final iterate K obtained by running Algorithm 2 satisfies
16 Ki,
x obtained by running Algorithm 2
F(a - F(x*) 2 min { (DD2
G2
(1 (1+ L
L
2
F(x - -F(x)) 2
LG2
n² min {1,
x²
Our construction involves component functions that are con- cave in particular directions. The proof of Theorem 3.5 is presented in Appendix B.3. One distinction of this statement is the explicit inclusion of the initial distance D. This depen- dence cannot be removed unless the initial point is placed exponentially far from the global minimum, which would lead to an unfair comparison with upper bound theorems, as they typically include a log D term in their bounds.
K*
Theorem 3.3 is a technically complex result, and we briefly outline the key strategy here. We construct each compo- nent function by applying a rotation, positioning each min- imizer to form a regular n-poolgonn The key idea is that, with a carefully chosen initialization, the iterates preserve rotational symmetry and also form regular n-polygon, maintaining constant distance from the global minimizer throughout the optimization process. The proof of Theo- rem 3.3 is presented in Appendix B.2.
Roughly, expression of the form (1 + a)* can be approxi- mated by exp(ab). Applying this to (1 + 2n )", we obtain the approximation exp( g ). Thus, when K = (x)) the second term scales as C and as K decreases, grows at rate exponential in x.. This contrasts with other bounds, which typically exhibit polynomial dependence on k
Compared to Theorem 3. Theorem 3.3 provides a consis- tently larger lower bound. Specifically, depending on the relationship between K and VK, the bound in Theorem 3.3 larger by a factor of either kK or x²3 //3,, 3, both exceeding 1 in the small epoch regime. When K- = (1s). both bounds in Theorems 3.1 and 3.3 become C.
To validate our findings, we conduct experiments on our lower bound constructions in Appendix G. For Theorem 3.3, we confirm that the iterates follow a circular trajectory, as in- tended by the original design. For Theorem 3.5, we observe that the function optimality gap for IGD skyrockets whereas other germutation-based SGD methods remain robust in the small epoch regime. To our knowledge, no upper bound exists for RR in this setting with nonconvex components. Based on experimental results for Theorem 3.5, we conjec- ture that RR will theoretically exhibit robust convergence in this nonconvex component setting, unlike IGD.
Theorem 5 of Mishchenko et al. (2020) provides an upper bound for IGD when all component functions are strongly convex. We restate this result in Proposition 3.4, with slight modification to extend its applicability to arbitrary permutation-based SGD methods.
Proposition 3.4 (Mishchenko et al. (2020), Theorem 5). Let n 2 1, K 2 E, and xo be the initialization point. Suppose F is a function satisfying Assumptions 2.3 and 2.5 where each component function is p-strongly convex. Then, for any choice of permutation 0%k in each epoch, the final iterate x obtained by running Algorithm I with a step size [|0,-20"||uK) )
While our lower bound results are stated in terms of the func- tion optimality gap align with the form of upper bounds, our proof can be directly extended to derive lower bounds in terms of the distance to the optimal solution. Specifically, the lower bounds on the distance metric ||.,5 - -x='] are:
2 unk max { |log
satisfies
VRG.
G G min {1, } and min {D. & (1 2 nK for Theorems 3.1, 3.3 and 3.5, respectively.
n/2)
L
LG2
||a5% 2=1 <
6

---

Incremental Gradient Descent with Small Epoch Counts is Surprisingly Slow on Ill-Conditioned Problems
3.2. Breaking the Barrier of With-Replacement SGD
mal performance in terms of and K among permutation- based SGD methods. Second, this rate outperforms the rate of _ wnk for with-replacement SGD (Liu & Zhou, 2024b) whenever n 2 H² /
Up to this point, we have analyzed the worst-case conver- gence behavior of permutation-based SGD with respect to the permutation choice in the small epoch regime. A natural question that follows is: what happens in the best case?
K. In particular, even when K S k. problems involving a large number of component functions with small input dimensions can still satisfy this condition.
Unlike the large epoch regime where the question has been sufficiently explored (Lu et al., 2022a; Cha et al., 2023), the small epoch regime remains less understood. In this section, we slightly deviate from the main topic and demonstrate that a well-designed permutation can enable permutation- based SGD to achieve a faster convergence rate than with- which RR
To our knowledge, this is the first result showing that a permutation-based SGD method may outperform with- replacement SGD in the small epoch regime. However, we identify two key limitations. First, Theorem 3.7 is not an implementable algorithm, as it requires prior knowledge of component gradients at x". Second, the upper bound in Theorem 3.7 and the lower bound established by Cha et al. (2023) still differ by factor of H² An interesting future direction would be to design a practical permutation-basee SGD method that tightly matches this lower bound.
replacement SGD in the small epoch has been proven not to do so (Safran & Shamir, 2021).
Before presenting our finding, we introduce an additional lemma that is used in deriving our result.
Lemma 3.6 (Herding Algorithm (Bansal & Garg, 2017)). Let L .n Ed satisfy || S 1 for all [n]] and Ei=1 2; = 0. Then, there exists an algorithm, Herding, that oulputs permutation : [m] [m]] such that
We conclude by suggesting a setting where we can effi- ciently obtain this permutation. Suppose all component functions have the same Hessian so that V - V2F F O. Then, the gradient difference Vf: VF remains constant across the domain, leading to the following equation:
E Zo(3 || < H, where H = ÖVVa).
max
Vii(2)) = V (xx") - FF = (i(oz) - VF(z)).
The Herding algorithm was used in Lu et al. (2022a) for designing GraB. Our next theorem leverages Herding in different way to show the existence of permutation-based SGD method (but impractical) that achieves accelcration even in the small epoch regime.
In this scenario, we can use scaled gradient errors at the initialization f
FF(x)))/GG. which can be effi- ciently obtained, as inputs to Herding to attain the desired permutation a. Furthermore, the lower bound construction of Cha et al. (2023), which achieves rate of LG p==*Kz+ also satisfies the identical Hessian assumption. This confirms the algorithmically optimal convergence for this specific function class, up to factor of H2 gap.
Theorem 3.7 (Herding at Optimum). Let n. 2 1, K Z A. and Tu be the initialization point. Suppose F is a func- tion satisfying Assumptions 2.3 and 2.5 where each com- ponent function is s-storngly convex. Then, there exists a permutation such that the final iterate æ obtained by running Algorithm 1 with K epochs of a and a step size
4. IGD in Large Epoch Regime
|log [|000-00" . }. satisfies
We now shift focus to the large epoch regime, where K 2 K. We examine convergence under two distinct scenar- ios: (i) each component is convex, and (ii) some components may be nonconvex. While the presence of nonconvex com- ponents significantly deteriorates convergence in the small epoch regime, we observe that this effect diminishes in the large epoch regime.
1) knk max
VNHG.
HLG
|| | K
11
Unlike GraB which dynamically adapts the permutation at each epoch based on the gradient observations, Theo- rem 3.7 applies a fixed a consistently throughout entire epochs. The permutation ø is obtained by running Herding for the scaled component gradients at the global optimum x", ensuring maxie[m] || Σj=1 (e(n((")) < II.., The proof of Theorem 3.7 is presented in Appendix C.3.
4.1. Convergence with Component Convexity
We first focus on the case where all components are convex. Theorem 4.1. For any n 2 2. 2 2, and K 2 K, there ex- ists a 3 3-dimensional function F satisfying Assumptions 2.3 and 2.4 with P = 0, where each component function shares the same Hessian, along with an initialization point En, such that for any constant step size n, the final iterate obtained by running Algorithm 2 satisfies
By T-smoothness, it immediately follows that the function optimality gap is bounded as F (( F(x*) X H²L We make two key observations regarding this result. First, LG Cha et al. (2023) prove the lower bound rate of a²n² Ka appli- cable to arbitrary permutation- based SGD without any con- straint on K. This confirms that Theorem 3.7 achieves opti-
LG2
F(* K F(x*)
7

---

Incremental Gradient Descent with Small Epoch Counts is Surprisingly Slow on IIl-Conditioned Problems
The detailed proof of the theorem is provided in Ap- pendix D.I. As previously discussed in Theorem 3.1, since the overall function is strongly convex and each component function shares the same Hessian, it follows that each com- ponent function is also j--ttrongly convex. The previous G best lower bound for IGD in this setting was μk² (Safran & Shamir, 2020), and our result improves upon this by a factor of K. Also, when K ((x), this bound simplifies to L. thereby continuously interpolating the lower bound results in the small epoch regime (Theorems 3.1, 3.3 and 3.5).
nonconvex components, Proposition 4.2 is no longer appli- cable for direct comparison. Theorem 4.4 addresses this by providing an upper bound allowing nonconvex component functions for arbitrary permutation based SGD.
Theorem 4.4. Let 2 K 2 (1 + P)R, and Do be the initialization point. Suppose F is a func- tion satisfying Assumptions 2.3 and 2.4. Then, for any choice of permutation ok in each epoch, the final iter- ate x obtained by Algorithm 1 with a step size n ank max {log (F(as) FF K2
2
.1] satisfies
Next, we present a complementary upper bound result, orig- inally established in Theorem 4.6 of Liu & Zhou (2024a). For consistency with the assumptions used throughout this paper, we restate it under slightly stronger assumptions.
L2
F(a K - F(x")
The proof of Theorem 4.4 is in Appendix E. This upper bound aligns with the lower bound in Theorem 4.3, differ- ing only by polylogarithmic factors, when the objective is sufficiently ill-conditioned and the number of epochs K is sufficiently large, specifically K Z max { ///,,, x²]
Proposition 4.2 (Liu& & Zhou (2024a), Theorem 4.6), Let 2 1, K 2 K, and To be the initialization point. Sup- pose F is function satisfying Assumptions 2.3 and 2.5 where each component function is convex. Then, for any choice of permutation T% in each epoch, the final iterate obtained by Algorithm I with the step size 17 = "="==="1''=' unk max {log LGa(1+log K3 ) .13 satisfies
Importantly, the convergence rate in this setting degrades by only a factor of x compared to the convex components case. These results highlight an intriguing behavior of TGD: allowing nonconvex components significantly degrades con- vergence in the small epoch regime; however, this slowdown is much less severe in the large epoch regime.
LG2
F(ah)) - F(x") S 12K2
We observe that the lower bound in Theorem 4.1 and the upper bound in Proposition 4.2 match exactly, up poly- logarithmic factors. The component functions for the lower bound satisfy strictly stronger assumptions than those re- quired for the upper bound. Unlike upper bounds where stronger assumptions may improve the convergence rate, ful- filling stronger assumptions in lower bound analyses rather strengthens the result of the bound. Thus, Theorem 4.1 remains valid lower bound matching Proposition 4.2.
Similar to the small epoch case, the lower bounds in the large epoch regime can also be expressed in terms of the distance to the optimum. Specifically, the lower bounds on jaK (for K 2 max(n² /n² x²))
>> x=] are nK and LG for Theorems 4.1 and 4.3, respectively.
4.3. Comparison with Other Methods
Here, we provide detailed comparison of the convergence rates across different permutation-based SGD methods.
4.2. Convergence without Component Convexity
Random Reshuffling. In the large epoch regime, Liu & Zhou (2024a) show that RR achieves an upper bound of LG nnn-. while Cha et al. (2023) establish a tight matching lower bound under the same setting. Both results assume that the component functions are convex. This implies that in settings where all component functions are convex, RR outperforms IGD by a factor of n in terms of convergence rate in the large epoch regime.
In this section, we investigate the case where the assump- tion of component convexity is removed. Our next theorem, Theorem 4.3, establishes a lower bound for IGD, quantify- ing the degradation in convergence rate when nonconvex components are included in the large epoch setting.
Theorem 4.3. For any n 2 4. K 2 n, and K > max {x2 /n?, 3,, there exists a 4-dimensional function F satisfying Assumptions 2.3 and 2.4 with P- K, along with initialization point Zo. such that for any constant step size n, the final iterate obtained by running Algorithm 2 satisfies
Optimal Permutation-basee SGD. Lu et al. (2022a) demonstrate that GraB achieves an upper bound of H= => K
where H is a constant that scales as vdd (Lemma 3.6). Simi- larly, Cha et al. (2023) establish lower bound of L*G² for any permutation strategy over K epochs, assuming suf- ficiently ill-conditioned problems and a large number of epochs. Both results are derived without assuming compo- nent convexity. Together, these results indicate that, when nonconvex components exist and d is fixed, the optimal con-
L2G2
F( - F(x*) 2
-
n K2
The proof of Theorem 4.3 is presented in Appendix D.2. Ad- ditional assumptions on n and K are introduced for techni- cal reasons. Since the construction in Theorem 4.3 involves
8

---

Incremental Gradient Descent with Small Epoch Counts is Surprisingly Slow on III-Conditioned Problems
vergence rate for permutation-baset SGD in the large epoch regime is L'G² K² This implies that in settings where some components nonconvex, IGD converges at rate slower than optimal permutation- based SGD by a factor of n²
SIGACT Symposium on Theory of Computing, pp. 914 926, 2017.
Bertsekas, D. P. Incremental proximal methods for large scale convex optimization. Mathematical programming. 129(2):163-195, 2011.
5. Conclusion
Bubeck, S. al. Convex optimization: Algorithms and com- plexity. Foundations and Trends@ in Machine Learning, 8(3-4):231-357, 2015.
We provide detailed analysis of IGD across both small and large epoch regimes, considering various assumptions on the component functions. Our results show that, unlike in the large epoch regime, even when the component functions are strongly convex, the convergence can be significantly slow. Furthermore, the presence of nonconvex components exacerbates this slowdown exponentially. We also demon- strate the existence of permutation-ban SGD method that allows faster convergence in the small epoch regime.
Cai, X. and Diakonikolas, J. Last iterate convergence of in- cremental methods and applications in continual learning. arXiv preprint arXiv:2403..mm 068833,,, 2024.
Cha, J., Lee, J., and Yun, C. Tighter lower bounds for shuffling SGD: Random permutations and beyond. In International Conference on Machine Learning, pp. 3855- 3912. PMLR, 2023.
Finally, highlight two promising directions for future work. The first is to establish tight convergence bound for RR in the small epoch regime, similar to our analy- sis for IGD in Section 3. We discuss the current state of research and the key challenges in this direction in Ap- pendix A.4. The second is develop an efficient and prac- tical permutation-based SGD method that enjoys provable fast convergence in this regime.
Garrigos, G. and Gower, R. M. Handbook conver- gence theorems for (stochastic) gradient methods. arXiv preprint arXiv:2301.1125: 2023.
Ghorbani, B., Krishnan, S., and Xiao, Y. An investigation into neural net optimization via hessian eigenvalue den- sity. In International Conference on Machine Learning, pp. 2232-2241. PMLR, 2019.
Acknowledgements
Gurbuzbalaban, M., Ozdaglar, A., and Parrilo, P. A. Con- vergence rate of incremental gradient and incremental newton methods. SIAM Journal on Optimization, 29(4): 2542-2565, 2019.
This work was partly supported by a National Research Foundation of Korea (NRF) grant funded by the Korean government (MSIT) (No. (3-2023-002113352 and an Insti- tute for Information & communications Technology Plan- ning & Evaluation (ITP)) grant funded by the Korean gov- ernment (MSIT) (No. 05-2009-111900075 Artificial Intelli- gence Graduate School Program (KAIST)), CY acknowl- edges support from a grant funded by Samsung Electronics Co., Ltd.
Haochen, J. and Sra, S. Random shuffling beats SGD after finite epochs. International Conference on Machine Learning, pp. 2624-2633, PMLR, 2019.
Koloskova, A., Doikov, N., Stich, S. U., and Jaggi, M. On convergence of incremental gradient for non-convex smooth functions. In Forty-first International Confer- ence on Machine Learning, 2024. URL https:// openreview net / forum 1idiidd2222x
Impact Statement
This paper aims to advance the theoretical understanding of convex optimization in machine learning. While optimiza- tion methods have broad applications, we do not foresee any specific ethical concerns or socictal implications arising directly from this work.
Lan, G. First-order and stochastic optimization methods for machine learning, volume 1. Springer, 2020.
Li, H., Xu, Z., Taylor, G., Studer, C., and Goldstein, T. Visualizing the loss landscape of neural nets. Advances neural information processing systems, 31, 2018
References
Liu, Z. and Zhou, Z. On the last-iterate convergence of shuffling gradient methods. In Forty-first International Conference on Machine Learning, 2024a. URL https: / //oeerreview net forum? didyddyyddiii jwHDu.
Ahn, K., Yun, C., and Sra, S. SGD with shuffling: optimal rates without component convexity and large epoch re- quirements. Advances in Neural Information Processing Systems, 33:17526-17535 2020.
Liu, Z. and Zhou, Z. Revisiting the last-iterate conver- gence of stochastic gradient methods. In The Twelfth International Conference on Learning Representations,
Bansal, N. and Garg, S. Algorithmic discrepancy beyond partial coloring. Proceedings of the 49th Annual ACM

---

Incremental Gradient Descent with Small Epoch Counts is Surprisingly Slow Ill-Conditioned Problems
2024b. URL
forum?
J. W. (eds.), Advances in Neural Information Processing Systems, 2021. URL https::hpp/.......... forum Brrumiidd-NKwwwuUB
id=xxaEhwC1I4.
httptts://ppeeeeeeeeeee wpw.reviee.eeeeeeeeeeeeeeeeee.ee net//
Lu, Y. Guo, W., and Sa, D. Grab: Finding provably better data permutations than random reshuffling. Oh, A. H., Agarwal, A., Belgrave, D., and Cho, (eds.), Advances in Neural Information Processing Systems, 2022a. URL https:/ opwnreview.ee..............e...e ner/forum? id=nDemfqKHTpR,
Shamir, and Zhang, T. Stochastic gradient descent for non-smooth optimization: Convergence results and opti- mal averaging schemes. In International conference on machine learning, pp. 71-79. PMLR, 2013.
Yun, C., Rajput, S., and Sra, S. Minibatch vs local SGD with shuffling: Tight convergence bounds and beyond. In International Conference Learning Representations, 2022. URL https: /appnreviewwweeeeeeeeeeeeeeeewwe net ffrrmmrrmm Id=LdwwbaP24 wbBP2m1g
Lu, Y. Meng. S. Y., and De Sa, C. general analysis of example-selection for stochastic gradient descent. In International Conference Learning Representations (ICLR), volume 10, 2022b.
Mishchenko, K., Khaled, A., and Richtárik, Random reshufiling: Simple analysis with vast improvements. Ad- vances in Neural Information Processing Systems, 33: 17309-17320, 2020.
Mohtashami, A., Stich, S., and Jaggi, M. Character- izing & finding good data orderings for fast conver- gence of sequential gradient methods. arXiv preprint arXiv:2202.01883 2022.
Nagaraj, D., Jain, P., and Netrapalli, P. SGD without replace- ment: Sharper rates for general smooth convex functions. In International Conference Machine Learning, pp. 4703-4711. PMLRR 2019.
Nguyen, L. M., Tran-Dinh, Q., Phan, D. T., Nguyen, H., and Van Dijk, M. unified convergence analysis for shufffing-type gradient methods. Journal of Machine Learning Research, 22(207):1 2021.
Rajput, S., Gupta, A., and Papailiopoulos, D. Closing the convergence gap of SGD without replacement. In Interna- fional Conference on Machine Learning, pp. 7964-7973. PMLR, 2020.
Rajput, S., Lee, K., and Papailiopoulos, D. Permutation- based SGD: Is random optimal? In International Confer- ence on Learning Representations, 2022. URL https: / /poenrevveww net./ forum? d==ii Ba АНКТYXE.
Recht, B. and Ré, C. Toward a noncommutative arithmetic- geometric mean inequality: Conjectures, case-studies, and consequences. In Conference on Learning Theory, pp. 11-1. JMLR Workshop and Conference Proceedings, 2012.
Safran, and Shamir, O. How good is SGD with random shuffling? In Conference on Learning Theory, pp. 3250- 3284. PMLR, 2020.
Safran, I. and Shamir, O. Random shuffling beats SGD only after many epochs on ill-conditioned problems. Beygelzimer, A., Dauphin, Y., Liang, P., and Vaughan,
10

---

we refer as Incremental Gradient Descent with Small Epoch Counts is Surprisingly Slow on Ill-Conditioned Problems
A. Supplementary Details
In this section, we provide additional details omitted from the main text.
A.1. Visualization of Upper and Lower Bounds
We begin by presenting plot that summarizes our theoretical findings. Theorems 3.1 to 3.5 (and the result from Mishchenko et al. (2020)) apply to the small epoch regime (K S k), and Theorems 4. to 4.4 (and the result from Liu & Zhou (2024a)) apply the large epoch regime (K Z λ). the figure, solid lines indicate upper bounds and dash-dot lines represent lower bounds. Each color represents pair of upper and lower bounds derived under similar assumptions matching bounds. The vertical line K marks the transition between the small and large epoch regimes. Both axes log-scaled for better visualization of rate differences.
Theorem 3.2 (UB)
Theorem 3.1 (LB)
Mishchenko (2020) (UB)
Theorem 3.3 (LB)
Theorem 3.5 (LB)
Liu & Zhou (2024a) (UB)
Theorem 4.1 (LB)
Theorem 4.4 (UB)
Optimality Gap
L²62//12
Theorem 4.3 (LB)
1G2//22
G2/H
G²/L-
VK
K Epoch
max(k3 x x22
Figure I. Visualization of the bounds in Table 1. Both log-scaled. Upper bounds (UB) represented using solid line, and lower bounds (LB) are depicted with dash-dot line. The small and large epoch results are combined into a single figure with separation by the vertical line K Upper bound results for the small epoch regime only hold under K > s/n, while lower bound results hold for K greater than some constant.
A.2. Pseudeocode IGD
Next, we provide the pseudocode for IGD as Algorithm

---

Incremental Gradient Descent with Small Epoch Counts is Surprisingly Slow on Ill-Conditioned Problems
Algorithm 2 Incremental Gradient Descent
Input: Initial point Te. Step size 7), Number of epochs K Initialize a1- for k = to K do
for = 1 to n do
x. = - - ((a(-)
end for
2g ++1 æ
end for
Output: T
A.3. Connecting IGD) Lower Bounds with Upper Bounds of General Permutation-Bas SGD
In this paper, we derive upper bound results for arbitrary permutation-base SGD, and the lower bound results for IGD. To clarify the connection between these results, we explain why the lower bounds derived for IGD are relevant to the upper
bounds for arbitrary permutation-basee SGD. Intuitively, deriving the upper bound for arbitrary permutation-basee SGD can be viewed as bounding the following sup problem from above:
inf step size y
sup function F(()) permutation {o.)
F(at") F(x=).
(1)
On the other hand, the corresponding lower bound is that bounds the following sup-inf problem from below:
sup function F(w) step 1)
inf F(x F((x)).
22)
permutation fo, fr.)
Notably, in the lower bound formulation, the permutations fox Hi= appear in the supremum term. This implies that the lower bound for IGD, which can be formulated as:
sup inf F(an F(x=),
function F(a)) step size
where every og is an identity mapping, is most equation (2). Therefore, our lower bound results, derived specifically for IGD, also provide valid lower bounds for the upper bound results established for any permutation- SGD.
To further clarify, we compare it with the work of Lu et al. (2022a). In Lu et al. (2022a), the authors introduce permutation- based SGD algorithm called GraB that provably converges faster by carefully selecting permutations each epoch. This problem can be formulated as bounding the following inf-sup problem:
inf
sup F(x F(x").
(4)
step size permutation )o
function F(x)
In addition, Cha et al. (2023) proves that GraB is an optimal permuration-based SGD by providing a lower bound that holds for every possible combination permutations over K epochs:
sup function (()
inf stop size permutation )
F(a F(x=).
(5)
Clearly, equation (4) and equation (5) are smaller than equation (1) and equation (2), respectively.
A.4. Status and Open Challenges in Establishing Tight Bounds for RR in the Small Epoch Regime
We begin by summarizing the current state of research on R. in the small epoch regime. To the best of our knowledge, there are two noteworthy results (under the assumption that the overall function is strongly convex and each component is smooth):
12

---

Incremental Gradient Descent with Small Epoch Counts is Surprisingly Slow on IIl-Conditioned Problems
1. (Mishchenko et al., 2020): When all component functions also strongly convex, an upper bound of Ó 12 provided.
is
2. (Safran & Shamir, 2021): When all component functions are quadratic and their Hessians commute, a tight convergence rate of ( pnk is established.
Unlike scenario (2) where the authors provide matching UB and LB (up to polylogarithii factor), the lower bound in scenario (I) is unknown, and it remains open whether the rate O mank can be improved not.
1,2
Given this context, there are two clear directions for future exploration in small epoch RR literature:
Upper Bound Direction. Improve the existing bound Ō or derive new bounds under weaker assumptions (e.g.. convexity, or even without convexity).
" under the strongly convex component assumption,
Lower Bound Direction. Develop matching lower bound (under the strongly convex component case) to close the gap with the existing upper bound ( (=k=))
The primary challenge on the upper bound side is that deriving new upper bounds in the small epoch regime appears to require sophisticated analytical techniques (due challenges discussed in Section 2.4). As can be found in Safran & Shamir (2021). even the proof for ID quadratic is highly technical. One promising technique (2024). In contrast to traditional analyses that group updates within single epoch (i.e., chunks of size n), this method groups updates into chunks of size := 1/m/L. While this chunk-based approach can be successfully applied to derive upper bounds for IGD, it becomes problematic for RR. Specifically, when the chunk size t does not align neatly within epochs, handling the dependencies between iterates becomes extremely difficult.
explored is from Koloskova et al.
Regarding the lower bound direction, we believe any progress beyond current results will likely require more complicated constructions that go beyond simple quadratic functions. This is because for simple quadratic functions where the Hessians commute with each other (c.g.. x2) - + a, + x byz2), the tight rate of O p is already established by
Safran & Shamir (2021). Therefore, to surpass the existing LB barrier D( junk ), future constructions must involve quadratic functions with non-commuting Hessians even non-quadratic functions, necessitating more advanced analytical techniques. While our own lower bound construction in Theorem 3.3 is based on quadratic functions with commumitn Hessians, tailored to IGD, and do not clear way extend this idea to RR.
13

---

Incremental Gradient Descent with Small Epech Counts is Surprisingly Slow on IIl-Conditioned Problems
B. Proofs for Small Epoch Lower Bounds
In this section, we present the detailed proofs for Theorems 3.1, 3.3 and 3.5 which are the lower bound results in the small epoch regime. To establish these results, we construct a specific function F that achieves the stated lower bound for each theorem. We note that constructing lower-bound function for SGD presents a significant challenge, must exhibit poor convergence for any choice of step size 1j. The difficulty lies in the fact that the convergence behavior of SGD is highly sensitive to y. a small step size leads to slow updates, whereas a large step size can cause divergence.
To overcome this challenge, we partition the positive real line of possible step sizes into three regimes: small, moderate, and large. For each regime, we design a distinct nower-bound function tailored to follow the stated convergence behavior within that range. Finally, we combine these functions across dimensions, ensuring that the resulting function satisfies the stated lower bound for any choice of r/. This "dimension-ee ddimension-aggregatnng technique has been developed the recent literature (e.g.. Safran & Shamir (2021); Yun al. (2022); Cha et al. (2023)).
B.1. Proof of Theorem 3.1
Theorem 3.1. For any n 2 2, 2 2. and K S 30C, there exists a 3-dimensional function F satisfying Assumptions 2.3 and 2.4 with P- O, where each component function shares the same Hessian, i.e., f(())) = V F()) for all [n]] and x: E RR along with an initialization point Tu, such that for any constant step size nT. the final iterate x. obtained by Algorithm 2 satisfies
G2 μK
F F(x))
Proof. We divide the range of step sizes 17 > 0 into three regimes that will be specified subsequently. For each regime, we construct the overall functions Fi, F2, and F' respectively, along with their respective component functions and initial point. Each function is 1-dimensional and satisfies Assumption 2.3. F1 and F3 satisfy Assumption 2.4 with G = p = 0, and F2 satisfies with / = 0. Also, the component functions within each overall function share the same Hessian. Importantly, each function is designed to satisfy the following properties:
(Small step size regime) There exists an initialization point ze poly(и, L, n. K, G) such that for any choice of 7 E <((,, wik) (O.,nix) the final iterate z obtained by running Algorithm 2 satisfies Fi (x, Fi Fi(x))))x))))))))( G
pk
(Moderate step size regime) There exists an initialization point yo рolу(μ, L, n, K, G) such that for any choice of E pank i.). the final iterate y/ obtained by running Algorithm satisfies F2 k F2 ス @²
(Large step size regime) There exists an initialization point poly(μ, I, K, G) such that for any choice of 17 e [22 o0), the final iterate z obtained by running Algorithm 2 satisfies Fs(= F2(22) G²
pk
Here, xx, y, =x denote the minimizers of F1, Fz, and F3, respectively. Detailed constructions F1, Fg, and F3, as well as the verification of the assumptions and the stated properties are presented in Appendices B. to B.1.3.
We now aggregate these functions across dimensions: F(x) F(x. y, 2) = Fi + F2(2) + Fz(2) and f((z) fu((z) + (2) + (z) for all E [n). Here, fi. fus f1i. fai denote the i-th component function of F. F1, F2, and Fs. respectively. Since each dimension is independent, it is obvious that x= (x", ","""""" 2²) minimizes F.
Finally, by choosing the initialization point as xo = (ro, yo, 20). the final iterate x = (xth K , in) obtained by running Algorithm on satisfies
G2
F(x F(x") 2
uK*
regardless of the choice of 1) > 0.
Note that F satisfies the stated assumptions
ı < (in(F) vz) F2))), (+((=))) = VFF(w) max (') VB) VB((3))
LI,
14

---

Incremental Gradient Descent with Small Epoch Counts is Surprisingly Slow on Ill-oonditioned Problems
and
< + 50+ G.
Moreover, f1(r) = ding(V>Ji((t) V f2:(y), fu())) = diag f1 (ty),, (+) = F²F(2) holds,
since the component functions within each overall function share the same diagonal Hessian. This concludes the proof of Theorem 3.1.
In the following subsections, we present the specific construction of F1, F2. and Fs. and demonstrate that each satisfies the stated lower bound within its corresponding step size regime. For simplicity of notation, we omit the index of the overall function when referring its component functions, e-g., write fa(z) instead of fı((2). Moreover, we the common variable notation z while constructing functions for each dimension, though we use different variables in the diieeniin-aggregaann step.
B.I.1. CONSTRUCTION OF Fi
Let Fi (z) = _=² with component functions f((x) = F1)x) for all E [n]. It is clear that Fi satisfies Assumption 2.3, Assumption 2.4 with P 0, and its component functions share an identical Hessian. Also, we note that x 0 and (i(x)) 0.
Let the initialization be xo-
G wvk
1 For all E (o, pmk (0,
). the final iterate is given by
nk
G 4uvK
F = - (1-1p))ak 20
K
3D
nk
K
where the last inequality uses the fact that (1 - 1 2 1 for all m 2 2.
Thus, we have
(x G²
- = 2 k
-
B. 1.2. CONSTRUCTION OF F22
We construct the function by dividing the cases by the parity of n. We first consider the case where n is even, and address the case where n is odd later in this subsection. Let (z)z) #k x² with component functions
4k x² + Ga nk
if i
f((x)
2 x2 - Ga
otherwise.
It is clear that Ji satisfies Assumption 2.4 with P= 0 and shares the same Hessian. From the assumption K S 2,,,, we have # μK < 4. Hence, each f; is L-smooth and μ-sttrongly convex. Also, we note that x" 0 and Fz(x*) 0.
By Lemma F.1, the final iterate obtained by running Algorithm 2 is given by
z K (1 - nuk)nk nk xo + μK
G 1 1 (1 -_-n 3
1+ (1-nuK); (1 (1-
(6)
For any 17 E kok ) it follows that 1 S SpK
2 2K S 1. Then, we have (1 nuKynk $ (1 1 nk L R
K < ee-1 which implies 1 - (1 - -nnK))n
2 1 1 e- Moreover, we have (1 muK)* < (1 - (1= S e 3 and thus,
1- (1 - (1-nuk) 1 1-e-1
> 2
1 (1 nuK)=
Substituting these inequalities into equation (6) and setting zo = O, we obtain
> (1-e) 1--el (1-e-1) 1)(0)))) (1 - G
2μK
15

---

Incremental Gradient Descent with Small Epoch Counts is Surprisingly Slow on Ill-Conditioned Problems
and
uk
G²
(2( Fa(x²)
(5
K
2
2
We now consider the case where n is odd. Let F2(x) = uk x² with component functions
2
uk x²
if i=
2
f1(x)
x² + Ga
if 2 (n + 1)/2, if
uk x² Ga
Compared to the case of even n, f1(x) nk x22 is introduced newly. is clear that fa satisfies Assumption 2.4 with P 0 and shares the same Hessian. From the assumption K 2x, we have μ S pK S 2 Hence, each is L-smooth and j--ttrongly convex. Also, we note that x² and F2(x*) = 0.
2
By Lemma F.2, the final iterate obtained by running Algorithm 2 is given by
in = 11-1111 (LTTKK) nk 20 +
G
1- 1- nuK) nk
(1-())nu)))))
1- - nukK)"
For any jun ) it follows that 1 S nuK
2)
<
2uk L
2K
< 1. Then, we have (1 - nukYnk <
nk 41- 1)
x
e- K < <e-l. Moreover, (1 - nuk) I (1 _ < e mm
S c
holds for n 2 2. Substituting these inequalities into
equation (7) and setting zo = 0, we have
K G
1 - e
(1 e tj2.
k
Thus, we obtain the following optimality gap:
μK
G
F2(x - F2(x*) -(2a))=)(aa)==
(It >
B.1.3. CONSTRUCTION OF F3
Let Fx(x)) = 42 with component functions f((x) F2(x) for all E [n]. It is clear that Fi satisfies Assumption 2.3, Assumption 2.4 with P = 0, and its component functions share an identical Hessian. Also, we note that x = 0 and Fa(r")= = 0. For all 1 E 17, oo), the final iterate is given by
x = (1-n xp-
In this regime, the step size is excessively large, resulting in
1 1- < 1 L L - -1,
which implies (11 - nL)=K| 2 1. Thus, the iterate does not converge and satisfies
x >
ooo--
By setting the initialization To
G
we have
VaLK
L k) >
L
G
- - Fs(x*)
(xo)²
2
pk
16

---

Incremental Gradient Descent with Small Epoch Counts is Surprisingly Slow on IIl-Conditioned Problems
B.2. Proof of Theorem 3.3
Theorem 3.3. For any n 2 3, and K S Tēz there exists a 4-dimensional function F satisfying Assumptions 2.3 and 2.4 with P = 1, where each component function p-stronngy functioon is for any constant step size 77. the final iterate ax obtained by running Algorithm 2 satisfies
convex, along with initialization point 2o, such that
LG 4
K²
) - F(x")=
min
1.
K
Proof. Similar to the approach Theorem 3.1, we divide the range of step sizes into three regimes. For each regime, we construct the overall functions Fi, F2, and F3 respectively, along with their respective component functions and an initial point. Finally, we aggregate these functions across different dimensions to derive the stated lower bound.
The functions F1 and F3 are 1-dimensional, and F2 is 2-dimensional function. Each function is carefully designed to satisfy the following properties:
(Small step size regime) There exists an initialization point = рolу(и, L, K, G) such that for any choice of E (0, knn the final iterate z obtained by running Algorithm 2 satisfies F (1xx) Fi (xx)
LG min
1 K
(Moderate step size regime) There exists initialization point (Vo, 20) = poly(p, L, n, K, G) such that for any choice the final iterate (y =xk) obtained by running Algorithm 2 satisfies F22 (y 2 F2 2
of 77
LG min x T.)
E
jonk
2
(Large step size regime) There exists an initialization point wp = L,, K,G.K G) such that for any choice of 1) (0) 00), the final iterate w.Kk obtained by running Algorithm satisfies F3 (a Fz(w=) LG # min
L, n,,
Here, x², (y", 2*). and w" denote the minimizers of F1, F2, and F3, respectively. All these functions are designed to satisfy Assumption 2.3. Fi and F3 satisfy Assumption 2.4 with G P 0, and F2 satisfies with P = 1. Moreover, each component function within each overall function is j-strongly convex. Detailed constructions of F1, F2, and F3, well as the verification of the ussumptions and the stated properties are presented in Appendices B.2.1 to B.2.3.
By following a similar approach to the proof of Theorem 3.1, we can conclude that the aggregated 4-dimensional function F(x)= == F(z, y, z, w) = (x) + =2) + Fs(w) and component functions satisfy Assumption 2.3. Additionally,
(v)) V F(=) < [+)()=) (=) -V - V>2())) + [[V]s(=) F>3(2))
0 OG+ (V +0 G (V+(())
thus satisfying Assumption 2.4 with 1. Also, since each dimension is independent, it is obvious that x (x" 3 2², w²) minimizes F. Moreover, by choosing the initialization point as an (ao, yo: Fo, wo), the final iterate t (xth vn 2n w obtained by running Algorithm 2 F satisfies
F(x K) F(x") R
LG 42
min 1,
R²
K4
regardless of the choice of 17 > O.
This concludes the proof of Theorem 3.3.
In the following subsections, we present the specific construction of F1, F2, and F3. and demonstrate that each satisfies the stated lower bound within its corresponding step size regime. For simplicity of notation, we omit the index of the overall function when referring to its component functions, e.g., we write f((x) instead of fı(()). Moreover, we use the common variable notation x (and y) while constructing functions for each dimension, though we use different variables in the "dimension-aggrrggttonn" step.
17

---

Incremental Gradient Descent with Small Epoch Counts is Surprisingly Slow on IIl-Conditioned Problems
B.2.1. CONSTRUCTION OF F1
Let Fi (x) 50² with component functions ft()) (x) for all E [n]. It is clear that Fi satisfies Assumption 2.3, Assumption 2.4 with G P O, and has p-strongly convex component functions. Also, note that x 0 and Fi(r")= 0.
Let the initialization be zo = v min (1,
# G. For all 1y E (0, knk) ) the final iterate is given by K²J
K n = (1 - -2)) x0 2
(
nk
To 2 VVViin {I,
G Ap
nk
K2
where the last inequality uses the fact that (1
!/ m 2
i
1
for all m 2.
Thus, we have
LG
x²
(x(xK) - - = - (x 2
min 1,
n.2
K
B.2.2. CONSTRUCTION OF F22 In this subsection, let L' denote L/2. We introduce the design of each component function as follows:
"x² + 12² Gx
if i = 1, if2 i S n,
[x
(fi (Ri-1)- (x.
where
R == cos 0
sin 0g cos 0:
sin 0g
is the matrix for the counter-clock wise rotation in R2 by an angle 0, = i8 with d ==
Using these component functions, the overall function Fg == 1 Ei= fi is given by "nt + 22). This result can be verified by expanding the closed form of fi:
f<(x,)) 1 (1r cos 8:-1 + y sin 0 )2 + _ (- (-x 0=- cos cos 1,2
L'
G(x cos 6,- yin 1;
2
1
2 (n 0:-1 + T,' sin2 0,-1) x² (usin² 0:-1 + Tt' cos? 0: 0:-1) y²
+ (n L') sin 0,-1 cos 1080.-127
G( 8:-1 + ysnn 0
Since 3, utilize Lemmas B.1 and B.2, and obtain
n
1
sin 0:-1
cos 0; =0,
n
n
1
1
sin 2
0,
cos
P-1
2
1
sin 0:11 cos cosos-s
=
sin O2(1-1) = 0.
2n
Using these results, the overall function is simplified to
F2 v) 1+ T!
(x2 + y²))
which has a minimizer (x*. y²* = (0,0).
18

---

Incremental Gradient Descent with Small Epoch Counts is Surprisingly Slow on Ill-Conditioned Problems
Note that each component function f4 is obtained by rotating J1, and hence S4 inherits the properties of /1- We can easily check that Ji is both p-strongly convex and T-smooth. Also, the gradient difference between the component function fi and the overall function F2 can be expressed as
#+
Vi(xz,)) -
[1 G)
2, Ly
2
11 I''
G, - μ
2 2
2
11
11
< +
2
2
- 11 2
11
= +
2
[L' +
+ 1
S
= G + F
2
2
proving that the construction satisfies Assumption 2.4 with P 1.
Before delving into the detailed proof, we outline the intuition for the construction. We start by designing a step-size- dependent initialization point (uo(1), vo()),, where 1) E junk 2.). For i E [n], we define (u,(1) (n)) the result of running a single step of gradient descent on fi with a step size 17, starting from (u)-1(n), (-1)))
The key idea is to carefully design (w)( (1))) so that each subsequent iterate (v+(1), (1)) is obtained by rotating (u-1(1),, (7)) by an angle = 2x. This aligns with our construction of the component functions fú, which are also generated by continually rotating fi by the same angle 8. As result, the relative position between each iterate and the component function used to compute the next iterate is preserved throughout the entire update process. This symmetry ensures that the trajectory of the iterates (n) v, (r)) forms a regular n-sided polygon. Consequently, after running Algorithm 2, the final iterate and the initialization point (uo (1), vo())) are identical.
At the last step of the proof, we will show that the choice of the initialization point (uo( bonk ). Vo( p )) can be made in a step-size-independent manner without significantly affecting the final optimality gap, even when the step size v) is chosen from
rather than being fixed J
We now proceed to describe the exact construction of (wo(n), vo (n)). Consider the gradient of the component function fi (x, v). which is given by:
V Vafi(a, -ar- G and Vyli(H, = F'y.
A single iteration of gradient descent on fi using the step size 1) yields:
"n (1) = un(n) - (1) G), 01 (17) vo (17) T, vo))-
(8)
To maintain the rotational relationship between successive iterates, we require that the updated iterate (u, (7), Bn (1)) satisfies the following relationship:
un (n) vi (m)
coos sin 87 Tuo (1)
(9)
sin 8
cos 8
(o
As mentioned earlier, this rotational relationship ensures that the trajectory of the iterates forms a regular n-sided polygon. Recall that the component function fa is defined as:
f(la, v) = (f1 (RQ-1))- (x,
14 0 L
0
Additionally, let A
Since
[x] - G
vf((,v) = y
0
19

---

Incremental Gradient Descent with Small Epoch Counts is Surprisingly Slow on Ill-Conditioned Problems
the gradient of can then be expressed
x (i( = Ri-1 (A(Rii-)-1
())
(10)
-
y
If (wi (n), vn (n)) satisfies both equation (8) and equation (9), then the subsequent iterate (u2(1), #2(1)) satisfies:
(2)(1)] [2(
U1 (n)) U1 (1)
[
(I (RIA(R))
+ GR
[
uo (17)
=(I -I--nRiACE (-RRIA(RI)- R1
+ n/G
[v((1)
Ri (I- n))
(1)
0
) 0
Tuu (1))
[uo())) [o(())
GGG
Rı
RR
vo(
(7))
Thus, if the initial point (n)( to (17) and its successive iterate (u1(1), 2n (1)) satisfies the rotational relationship, this relation persists throughout the entire update process. Consequently, the trajectory of the iterates forms a regular r-sided polygon.
To enforce this rotational relationship, solve the following system of equations:
(n))) cos vo(n) sin d = (1 - (1)))un0))))) + nG
(o(1)) sin 8 + un (1)) cos ē = (1 -1--)/())oo(m)
From these, we derive:
rp' (1 - cos 6)
u0(1) (1 cos () (μ L')n) + 172 722'' pL' nGG
(1I)
sin 5
vo(n) (1 cos (2 - (1 - L')n) + xZ IG..
(12)
Note that the numerator of (n) is positive as shown below:
(a) LI
L'
82
nL' (1 - c)
2
2 K
(6) nL
L
27 2
4umnK K
n
T/
nT. 8n 2
2
4 K
(c) nT.
>
(13)
where we apply 17 2 jok and the inequality cos <
g²
z (a), substitute T'' 1/2 and = (b), and apply
2 3 >>> 2he and 2 16m K at (c). Also, we have 2 - (μr + L' L')m > 0 for 3. Thus, un(r) is always positive and to (1))
is always negative for 7 JanK )
Let (u)( of (n)) denote the i-th iterate at the k-th epoch of Algorithm 2 using the step size n and the initialization point (M)( vo ())))) By definition, (ut (n)), v (n)) represents the final iterate after K epochs. Due to rotational symmetry, (u. (m), v (n)) is identical to (un(n): 2o (1)). Thus, the distance between the final iterate and the minimizer of F2 can be lower bounded by the z-coordinate of the initialization point:
(u (n). 02 (n)))l (I(uo(n), vo(r)) 2 uo(n).
20

---

Incremental Gradient Descent with Small Epoch Counts is Surprisingly Slow on Ill-onnditioned Problems
We now derive a lower bound for uo(7). We begin by upper bounding its denominator:
82 (1 - cos (2 - (1 + L')n) + up' < .2 + n² pL'
4
+TfuL'.
2
n2
Substituting this result into equation (11) gives
(nIL' (1 cos cos8))nG + 1T?
12 2v/221
un (n)
:= (11))
4
Sm
where apply equation (13) at the second inequality. We easily check that (0(1) is increasing function of n and thus the minimum value is attained at 7 pnK Substituting unk we have
L'G
jun
Br 12
p222k² + 2pL/
LG
12 L 2
16 12² K2 + 24L
G
pk
24 16T +
pk
In summary, the distance between the final iterate and the minimizer of F2 is bounded as:
[1 (m), L (n))] = (1(uo(n) =,(()))) 2 uo(n) 2 p(n) 2 p
(a) G
2
min
{1,
K } K2
(14)
umk
32
where (a) is derived through the following process:
6 unnk
Ak
8x K
(6)
G
min
K 8m
2
G min {1,
R K2
16
2L +
2/
4p
K2
32
kka
K
Here, we use the inequality
Ita 2 2 min {1,u} u for all a 2 0 at (b).
The function optimality gap can then be bounded as:
Fu (n), 2 (1)) F2(x".0") 4 (1 (n), on (n)) 12
LG² n12
min 1
4
K
for 17 Jank 2) However, caveat is that the initialization point (uo(T)) (n)) depends on the choice of 17. Our goal
is to identify unified, step-size- -iddeiiendeee initialization point (zo. yo) that achieves the same lower bound (up to a scaling factor). Specifically, we aim to ensure:
K Un ) min (1, 1,
LG 1
2
F2
16)
K
for any choice of 7) E K 2).
We claim that this goal can be achieved by setting the initialization point as (zo, yo) (mol ( ) vol ( )). To prove this claim, consider two sequences of iterates: {x v ) [e[[]]Me[[]]] and {u, (17), of (n) [e( Both sequences are generated using the same permutation id,, and the same step size 17, but they differ in their initialization points. Specifically, 1 (af, y." starts from the initial point (oo( pan) ), vol pm )). while (uf (n). of (n)) starts from the initial point (ua(7), vo())).
Recall the gradient of f. from equation (10):
xx fil. v) Ri-1 (A(Ri-1)-
G (0)
y1
21

---

Incremental Gradient Deseent with Small Epoch Counts is Surprisingly Slow on IIl-Conditioned Problems
The update rule for the iterates generated by IGD is:
x 1-1
[ - 1/ -
+
n
(
and
T (m)
u (1)
= =( - (I--))A--A(R--)))
+ +nGGRe
u (n)
(7)
Taking the difference between the two sequences of iterates, have:
x u (n)
I - n (1) V - of
= (I 1---1Ri-i (
1 of (n)
Since Ri-1 is an unitary matrix, it follows that R,-1A((R-1))- t pll Thus, we obtain the inequality I -R 3
- -n which leads the following bound:
||(at - (n). of of (n)) S (1- ||( 1
(n), v() -
Based on this inequality, we will demonstrate that (> - 2 (n), 3 - (n)) is not significant. This can be interpreted as the gap between the initialization points shrinking progressively throughout the optimization process. Specifically, we have
[= 2 (11) 2/ 2/ (n))
S (1 mn)) 11 un (n). yo vo(i))) [[ - uo())) y0 - vo(
(ual
wnk uo( vo
va (1))) wnk
1e-
uo( 1 - mo(1))
vo unk
2o (n)
wnk
(6)
Vo( unk
+ +lub(1))
(c)
8T K
K + k uo(n)
140 (1)
no
pnkk
(4)
16.
mo
(2)
1A3
2
(1
K
(1)) o/ (n))
Here, we apply:
(a): v 2 unK and (ro, un)
un
jnn
up
j
(b). (d): wn()) is positive and increasing (shown Lemma B.3).
(c): Follows from Lemma B.4.
(e): K < x. I6x
(f): (n) K (7))
In summary, the distance between (xr K) and the minimizer of Fz can be bounded as:
[xx, K vn . 2 (1 (n), of (n)) (,,, = K (m). 2 K K (n)ill 2 (1- (1-2) 2) |1(t5 (n). (()))
22

---

Incremental Gradient Descent with Small Epoch Counts is Surprisingly Slow on Ill-Conditioned Problems
where we have already derived that [1 (1)) un (r))
32#"M
G
min {I,
K=
in equation (14). Thus, we conclude
(1-2et 2c 11-20-1)
G
[1 v,) m1
K
min 1, K2
32 1
and consequently,
Fa Vnl) - F2(x",9")
L' L'+ 1 4
(1
M/
K)
||
2
8
(1
K Un
||
2
LG
112
min
1
K
k²
B.2.3. CONSTRUCTION OF P3
Let Fx(x)= = _ with component functions fi(x) F2(x) for all i [n]. It is clear that Fi satisfies Assumption 2.3,
Assumption 2.4 with G = P 0 and has p-strongly convex component functions. Also, we note that x² = =0 and Fa(x*)= =
For all E 1 oo), the final iterate is given by
K = (1-1)bb
In this regime, the step size excessively large, resulting in
1- nb S 1 S -1,
which implies [1 nL)=k 1. Thus, the iterate does not converge and satisfies
2
|ool-
By setting the initialization To = C min {1, K ), we have
L ) 22 7 (50))²
L
LG
6²
Fa(2 Pa(x")
min
2
K
B.3. Proof Theorem 3.5
Theorem 3.5. For any n. 2 K 2 and K S 2, there exists a 2 2-dimensional function satisfying Assumptions 2.3 and 2.4 with P 3 such that for any constant step size r7, the final iterate x obtained by running Algorithm starting from the initialization point Do (D,0) satisfies
F(* F(x") 2 min {
G² (1+ (DD
L 2umK
Proof. Similar to the approach in Theorem 3.1, divide the range of step sizes into two regimes. For each regime, we construct the overall functions F1 and Fz, respectively, along with their respective component functions and an initial point. Finally, we aggregate these functions across different dimensions to derive the stated lower bound.
Each function 1-dimensional and carefully designed to satisfy the following properties:
(Small step size regime) For any choice of the initialization point xo D and step size 1j E (o, ndb ). the final iterate z obtained by running Algorithm satisfies Fi - =i(=*) μD?
(Moderate & Large step size regime) There exists an initialization point yo = poly(u, L,n, K, G) such that for any choice of E [ o0). the final iterate y obtained by running Algorithm 2 satisfies F2(y F2(y") >
G² 11 L I.
Here, x² and y" denote the minimizer F, and Fz, respectively. Both functions are designed to satisfy Assumption 2.3. Fj satisfies Assumption 2.4 with G P = 0. and F2 satisfies with P 3. Detailed constructions F, and Fz, as well as the verification of the assumptions and the stated properties are presented in Appendices B.3.1 and B.3.2.
23

---

Incremental Gradient Descent with Small Epoch Counts is Surprisingly Slow on Ill-Conditioned Problems
By following a similar approach to the proof of Theorems 3.1 and 3.3, we can conclude that the aggregated 2-dimensional function F(x)) F(x, y) Fi (ar) F2(y) and its component functions satisfy the stated assumptions. Also, since each dimension is independent, it is obvious that x² = yx" minimizes F. Finally, by starting from the initialization point as Zy = (D, 0), the final iterate x = (1 V obtained by running Algorithm 2 on F satisfies
F(x - F(x") 2 min {
G² L
L
)
DD2
1+
2unk
for any choice of D E IR and 17 > 0.
This concludes the proof of Theorem 3.5.
One key distinction of Theorem 3.5 compared to other lower bound theorems is the explicit inclusion of D in the statement. While it is possible to express the lower bounds in other theorems with dependency on D, we chose to leave this dependency only for Theorem 3.5 due the unique behavior of the term
G L (1 11+ L
Unlike typical bounds, this expression cannot be simplified into a clear, closed-form polynomial expression. Its proportional degree with respect to μ., I,, n, and K varies depending on their values. In particular, when K' small (e.g., near $), the term exhibits exponential growth, scaling as c² C where is constant greater than 1.1. I.
This exponential growth introduces challenges when attempting to express the bound without the "min" operator, as in other theorems. Specifically, the first coordinate of the initialization point, To, would need to grow to an exponential scale, which undesirable to when comparing to the upper bound theorems that hide logarithmic dependency. For these reasons, we leave the dependency on D explicitly the bound.
In the following subsections, present the specific construction of F1 and F2, and demonstrate that each satisfies the stated lower bound within its corresponding step size regime. For simplicity of notation, we omit the index of the overall function when referring to its component functions, e.g., we write fi(r)) instead of f1;()). Moreover, we use the common variable notation v while constructing functions for each dimension, though we use different variables in the "dimension--gggreattinn"" step.
B. CONSTRUCTION OF Fi
Let (x)) = x² with component functions f((x) Fi( for all i [n]] clear that Fi satisfies Assumptions 2.3 and 2.5 with G P = 0. Also, we note that x= 0 and F1 0.
For all E (0. μnn ) the final iterate is given by
nk
In = (1 - (1-
x0 2 "
1
Ip
2
nk
4
where the last inequality uses the fact that (1
m jm
>
1 for all m 2 2.
4
Thus, for zo = D, we have
(x( - Fi(x*)
L k (1
HD
2
B.3.2. CONSTRUCTION OF F2
In this section, we focus on the case when n is even. If n is odd, we set n - 1 components satisfying the argument, and introduce an additional zero component function. This adjustment does not affect the final result, but only modifies the parameters 14, L. n by at most constant factor.
Let F2(x)= _-2 with component functions
x22 + Ga ifi < 2/2 otherwise.
f((x)
402 Ga
24

---

Incremental Gradient Descent with Small Epoch Counts is Surprisingly Slow on Ill-Conditioned Problems
Note that the first n/2 component functions strongly convex, while the remaining component functions are concave. The overall function F2 is j-strrongly convex, since & 2 ll holds from the assumption 4, thereby satisfying Assumption 2.3.
Also, it is clear that fi satisfies Assumption 2.4 with P = 3. We note that x 0 and F2(x*) 0.
We now consider the relationship between z and zn A Applying Lemma F.3, we have
n2 2 (1 -1- n1) vo + T,
G
nL 2) (1+ (1- (1+ (11+
k+1 20 =
1+
(15)
From K S K. we have 1) 2 unk 2 three terms of its binomial expansion, which is possible because nt 2 2:
mZ We now derive the lower bound for (1
mo 2)
To do this, we consider the first
1+
a 2
2
1 + 2
21
2
?
+
2 n2
=1+14
4 n
n(n - 2)
5 1 9
2
8
2
4
where the last inequality uses n 2 4. Equivalently, the following inequality holds:
n
7
1
1 $
1
2
2
1
2
2
Using this inequality, the numerical term in equation (15) becomes
1+ ) (1 (1+ (1-)))))
n4
1 (1
n
2>
[1
-2 2
1+
9
Substituting this back to equation (15) yields
nI. (1 (1-n1)$3*)
G
(
1 nb
+/1
1
9T.
Note that if zn is non-negative, we have 20 k+1 +1
G (1
m
0. By setting the initialization point zo O, each z
remains non-negative throughout the process, and therefore the final iterate x.K satisfies:
nL 2
:
G
L
+
9L
9L
2pmK
where we apply 2 wnk at the last step. Consequently, the optimality gap is lower bounded as:
F2(x F2(x") =
L
2
G
1+
L
2pnk
B.4. Technical Lemmas
Lemma B.1. For any 2, the following holds:
1=0
where denotes the imaginary unit. In particular, the following equations hold:
2π
n-
2Tj
cos
0, and
sin
n
7
1=0
25

---

Incremental Gradient Descent with Small Epoch Counts is Surprisingly Slow on Ill-Conditioned Problems
Proof. Let ( = 2. Then, n" 2
holds. Moreover, we have
n-1
5" 1-
Σ 1=0
5
(1-1)=00 = O.
Since Ç - 1 + 0, it follows that Σド=0 52 = 0. This leads to the results Σj= cos
2nj
and
Σj= sin
2nj = 0.
Lemma B.2. For any 2 3, the following equations hold:
2rj cos²
2T
1
4
sin
and
sin
2
1
n
71
Y
Proof. First, notice that
4Tj
cos
(1
+ 008
n
n
2rj
1 (1
4TJ
sin
)
n
n
Hence, it suffices to prove Σj- cos Ari = and Σド sin d
Let ( = 45 where denote the imaginary number.
Then, 5" -1 = etii 1 = 0 holds. Moreover, we have
-1
ΣΦ 1==
55 (S (5-1)=00 = 0.
Since ( for 3, it follows that Σj=0 Çd 0. This leads the results Σ}= 008 inj 0 and Σラ= sin And 0.
Lemma B.3. For 1) E p 2)) un( is an increasing function of 1)-
Proof. Recall the expression for (v) given in equation (11):
nL'' (1 cos 6)
un( = (1 - cos (2 ( L')m) + nu 7G.
For simplicity of the notation, let a 1 - cos 5, b(n) (nT a)n, and c(n) = a(2 nin I/)) 122 Then, un(r)) can be expressed as b(n) G and (n) becomes (b'(n)e(n) b(n)c'(n) G/c(n) It suffices to prove the numerator <(g)
8' (((n)((r) b(t)c (1) is non-negative.
Expanding the numerator, we obtain
8' (())((()) b(n)c'(m) (n) (2mL' - a)(1" uL uL' na(p + L') 2a) - (1²2L' (2npL' a(p + L'))
U2 2 - 1j 12'a'' aL' (3p 22') + no(4L' + a(p + L')) - 2a²)
(2m²²uL' -12 aL''L((3) (3 L') n (u+ L'))
=-1ñal.2 + Anall 20²
a - 1 -a)).
(16)
Since v/''= =/ < 1, we have 221 < nlL' Moreover, we have a = cos < nL' from equation (13).
Substituting these results into equation (16), we have
b'(n)c(n) (()) 1² - L - 2a)= 2 a(4nL' - -nL' mL') 21aL'' 2 0.
Therefore, we conclude that (n( an increasing function with respect to 7)
26

---

Incremental Gradient Descent with Small Epoch Counts is Surprisingly Slow Ill-Conditioned Problems
Lemma B.4. For E pnk t).
the absolute value of vo(n) is bounded by wo(n) as follows:
8
(vo -
(1).
Proof. Starting from equations (11) and (12), we have where employ s 5 = - cos < ni from equation (13), and L' L. Finally, applying the condition 1) 2 unk completes the proof of desired inequality.
sin 6
(v((n)]
n7'' (1 cos 8) uo(n)
2m
2
nL uo(n)
4m
Tm uo(n)
8π uo()))
mLL
n:
27

---

Incremental Gradient Descent with Small Epoch Counts is Surprisingly Slow on Ill-Conditioned Problems
C. Proofs for Small Epoch Upper Bounds
In this section, we provide detailed proofs for Theorem 3.2, Proposition 3.4, and Theorem 3.7 which correspond to upper bound results in the small epoch regime.
C.1. Proof of Theorem 3.2
Theorem 3.2. Let n 2 L, KSKK K, and an initialization point ag. Suppose F. is a 1-dimensional function satisfying Assumptions 2.3 and 2.5. Assume that each component function fo shares the same Hessian for all i E [m] and R. Then, for any choice of permutation ok in each epoch, the final iterate xx obtained by Algorithm I with the step size 17 pnk max log - .13
satisfies
G
- - F(x*) S
μK
Proof. Since each fi has the identical Hessian, we have f2f((x) = v²F(() for every I E R. Consequently, for all i E [n]. we can express the gradient difference as follows:
= Vf(=") - [ -V'f(o)-V=((a)) da Vf((x*).
Vf((2) -F)))
For simplicity, let a, = (xx) for [n]. Then, from the definition of F(x) = Σ fx()), we have Em= at Furthermore, it follows from Assumption 2.5 that |a,| S G.. To further classify the indices, we define
4 {i E [n]] a, 2 0} and {i [n] a <
Here, 1 represents the collection of component functions whose minima are greater than or equal to z", while I_ consists of the remaining functions.
We begin by presenting the following lemma:
Lemma C.1. Let E R with < and let p' and g' denote the results of performing single step of gradient descent on a j-strongly convex and L-smooth I-dimensional function f, starting from p and respectively, with a step size < L Then, it holds that < o' - p' & (1 np)(q - p).
p'
The proof for Lemma C.1 is presented in Appendix C.4. Now, let 20 = x", initialized at the minima of the overall function F, and define zi the i-th iterate of the k-th epoch, using the same permutations employed for 2 but instead starting from the initial point 2g- Since the distance between of and 2 decreases by at least factor of (1 1//4) at each iteration (Lemma C.I), we have
G. L zbl S e nnuk 100 x'15
2n S (1 mpp1) KK [20
(17)
where we substitute r = pnk max
log
( G.
1} in the last step. This demonstrates that K and = remain
sufficiently close. For the rest of the analysis, we mainly focus on how far KK can deviate from x". The bound for F(a will later be controlled by leveraging L-smoothness between r and K
In the special case where I_ 0. all a; are equal to since E ai = 0. In this scenario, = remains at x because v fz+)) holds for all [n]. resulting in = x Using this, have
F(* < F(z#) + (V
K J
2n
K
K
(:: L-mmootthsssss)
L
G, F(x)) + <
G2 F(x") +
G2
= F(x)) +
2 T,
2T.
2μ
where we apply K < x the last inequality. This concludes the proof for this special case. For the remainder of the proof, we assume T_ # 0.
28

---

Incremental Gradient Descent with Small Epoch Counts is Surprisingly Slow on IIl-Conditioned Problems
For each & [K], define z as the maximum possible final iterate obtained after running Algorithm 1 starting from x², i.e,, the largest value among the (n!)* possible options. Similarly, for each is E [K]. let at denote the minimum among the (nt) options, also starting from x². Consequently, by convexity of F, F( ) can naturally be upper bounded by
max FF(=)),((=5)
The following lemma helps us to establish upper bounds for # - xx* and -( -x)).
x²).
Lemma C.2. Let tor ke denote the sequence of permutations applied over K epochs to generate sf. These permutations and the corresponding 2 satisfy the following properties:
The permutations )
Jk=1 applied during the first K - epochs, produce 24 K-1
For any k E [K]. all indices in 1+ appear before all indices in I_ in the permutation oz.
For any [K], let 24 K.I- Then, the inequality 2+ S <x S 24 holds.
k.I- denote the |1-1-th iterate in the k-th epoch, i.e., obtained after processing all indices I..
For R and its corresponding permutations (0r Mi-r the following properties hold:
The permutations (or ) applied during the first - epochs, produce z
For any k E [K]. all indices in I- appear before all indices in I+ in the permutation oz.-
For any k E [K]. let KJJ denote the |1+|-th iterate in the k-th epoch, i.e., obtained after processing all indices in 1+. Then, the inequality 2 k.l+ 2 x= 2 z holds.
The proof for Lemma C.2 is presented in Appendix C.4. Define T [|7+1] + [n] as the ordering of I+ used during the K-th epoch to generate 2 from _K We then define the sequence of iterates Ug, W1 W14, where un xx and each subsequent u; is obtained by applying gradient update using the component function (x) to U1-1- We emphasize the following two key points:
1. K.I. xx ug- 2+
2. The sequences of iterates 24 K.I_
2K and uo.... uir are generated by the same component function ordering.
From these observations, we conclude that 2 < | as Lemma C.1 ensures that the relationship S 9 is preserved under gradient descent (i.e., p S g, then p/ S of after each update). Together with xx < =x from Lemma C.2, we obtain 0 S - - x² S u -xx x².
Similarly, define -- [|T-]] >> [n] the ordering of I_ used during the K-th epoch generate =K from K,I, Also, define the sequence of iterates vo, V1,.... l|.l where vo = x² and each subsequent v; is obtained by applying gradient update using the component function fr_ (f) to u/-1- Then, we have x² 2 z 2 2|r_1, leading to 0 S -(= - xx) - (1)r__ =x").
To summarize the process so far, we aim to upper bound | - x= where z is the final iterate obtained using the same permutations as x but starting from 20 = x" instead of 20 .r. Since 2 and 2 represent the maximum and minimum possible final iterate of = respectively, the followings hold:
-xll max (2 - x²1} S max (11z11 x", 1(11-1 - x²)} Am
K
and therefore, by convexity of F.
F(z S max (F(m)),)) F()
(18)
We now focus providing the upper bound for max (F(M),,), (( ()} To this end, we introduce the following lemma:
Lemma C.3, With a step size < t. 0 VF(u.) & 2G, holds for all i E {0} U [[4]] and 2 VF(e,) 2 -2G, holds for all j E (0) [T-]]
29

---

Incremental Gradient Descent with Small Epoch Counts is Surprisingly Slow Ill-Conditioned Problems
The proof for Lemma C.3 is presented in Appendix C.4. Using Lemma C.3, we can upper bound the increments in the per-iteration function evaluation as follows:
F(u4) = F(ug-1)+ VF(a)dd
S F((u-1) [14 - Ui (1; + (w: - u;-1))l
= =((u-1) + VT VF + -u, - -4-1))
= =((u-1) VF((,11) a az) VF(u t (wi u.-1))l
S FF(u-1) + 77.0.
(19)
where 0 C; I 1 by Mean Value Theorem. The last inequality follows from the bounds I VF(u,-1) 2G, and 0 < (x2(0) 2 G. (since ( (i) E I.). Additionally, min (VF(u=)), V Fu()) s VP(uu-1 + G (u: u;-1)) S max (VF(u,1), VF(u)) holds as VF is a strietly increasing function.
Unrolling equation (19) for i = 1,2,.... [44. we obtain:
F(UL)) & F(x") + 4ymG.
By applying a similar argument, we can derive a corresponding bound for v/r_1
F(vL-)) F((*)) 4mm
Therefore, equation (18) becomes
F(z F(x*)++++ 4nnG?
We now proceed to derive the upper bound for F(xx), ). We already established in equation (17) that a Consequently, by applying L-smoothness,
=
S../L.
F(* s F(* (VF(= ( 2ht
- 2k)
T.
K
K
2
2
G.
L
G.
< (F(x*) + Amm.? + +G..
T
2
T.
4G
L. [ - x²1
5G
= F(x"))
log
[1]
μK
2L
where we used the fact that VF((*) S max (VF(= - vF(=z)} < max -V - VF(O)))) s 2G, and
77 unk max log [1xa-x1]
G. J. Since K $ N, we have 2 μK, and therefore.
F -()) < G
μk
This concludes the proof Theorem 3.2.
C.2. Proof of Proposition 3.4
Proposition 3.4 (Mishchenko et al. (2020), Theorem 5). Let n 2 1, K t. and xo be the initialization point. Suppose
F is a function satisfying Assumptions 2.3 and 2.5 where each component function is p-strongly convex. Then, for any choice of permutation ag in each epoch, the final iterate K obtained by running Algorithm with a step size n unk max log [[.-=="|uK ) .1), satisfies
VRG.
LG2
x-112
k²
30

---

Incremental Gradient Descent with Small Epoch Counts is Surprisingly Slow IIl-Conditioned Problems
Proof. The original statement by Theorem 5 in (the appendix of) Mishchenko al. (2020) holds only for IGD. We here extend the theorem to hold for arbitrary permutation-based SGD, and reorganize some terms facilitate clear comparison to the proof of Theorem 3.7.
We begin by noting the specific epoch condition stated as K 2 in the theorem statement:
2x 2
||:00 x xu
.1).
K
max
log
VRG²
Under this condition, the specified step size 17
max {log
| (|uu VKG.
) 13 satisfies S +
unk
For each k E [K], we use the permutation σn to define a sequence of iterates { as follows:
T x", / F2 (o)))))))')))
The sequence 2 be interpreted as the sequence starting from x' obtained by using the component gradients in the same order as æ, but the gradients are being evaluated at x" instead of x;-1- From Σn= Vfa(()(z²)) = =VF((")) = 0, we can easily deduce that , x²
| 2h.1 || using an iteration recursive inequality:
We analyze the square norm distance
|
-
|| fo.
(2 (2) 1/V (a(( (x))))))"")
-1 1 - - 112 21 ( (af -7. Vi (x V (oo())
+ 2²
- (x"x())
(a)
| x -11 112 -2n (D (2 Disii 24 D to (3 x0))
²² | (1)) (1 (==)
(20)
fz)), y) denotes the Bregman divergence of f between and y. At (a), apply the three-point identity of the Bregman divergence.
Here, (x, : = f(x) f
The term Digao 1
1. 1) in equation (20) can be bounded as follows:
Dinco (4)
2 | 2 1/21
by the j-sttrng convexity of the component function. Moreover, from Lemma 2.29 of Garrigos & Gower (2023), we have
(V Voo < 2T. S,,D,,,.. 1==" 2²))
Substituting these inequalities into equation (20), we derive
||a| 2i < | - ai 1|2 - 21/(1 - -1yL)D sarco (2 (x"-1;=²)= mnp | wha-1l1 + 2n s,, (2,,1-,,"")
(1 mhu ||at= =1, 2n S0s00 (2%;;-1,
(1 m//1 || - - 1| + 1 Ln²
(21)
where we apply 1 T 2 0 and Dj Do (a (=²= 2 0 at (a). At (b), we utilize the T-smoothness of the component function and the triangle inequality:
L
2
1 (n..)²
Diogo (xf,--1,")
< -
- x'11==
f (o"))
2
2
31

---

Incremental Gradient Descent with Small Epoch Counts is Surprisingly Slow on IIl-Conditioned Problems
Thus, by unrolling equation (21) over all [K] and all i [n]. and noting that KK,n xx
k+1,0 obtain
nk
| x:" x011" 2 (1 - -mn)" |xe a²1I² + Ln
(1 (1-1)) -m)
= (1 - -nnn 100 - x011 + +1 In G? (1 n2)
9/4
|200 11 1 G
S e qmnn
We now substitute = anR max log [ ) 3. When | x'll sufficiently large, the above inequality simplifies to
|000 x="
LG nr² 1²K2
1 [+4log²
[1200 x01 uK VKG.
LG
K2
On the other hand, when |az0 x² is small that 1 is chosen after the operation, the above inequality simplifies to
RG?
4LG²
LG?
| x 101
e²
p²
p
K2
where we use ||000 x² S e In particular, using the L-smoothness of F, the function optimality gap can be bounded as:
yKG.
F(x - F(x") < 2 N - x x01|² S L2G2
This ends the proof of Proposition 3.4.
C.3. Proof of Theorem 3.7
Theorem 3.7 (Herding at Optimum). Let 2 1, K Z 5. and No be the initialization point. Suppose F is a func- tion satisfying Assumptions 2.3 and 2.5 where each component function is p-strongly convex. Then, there exists permutation such that the final iterate a obtained by running Algorithm I with K epochs of and step size .1). satisfies
77 pnk max log ||",-="|||m (lpk
VKHG.
H 222
K n
x²" 2
Proof. We begin by noting the specific epoch condition stated K 2 n
in the theorem statement:
2 2x log
[ x pnk .1).
K
max
VKHG.
n
Under this condition, the specified step size 17 unk max {1og
[Ima-mr" [Ima-""llank] vKHG.
)
.13 satisfies 1) S 1 I.
Next, we consider the scaled gradient of each component function at x":
fi("))
Vf2(x*)
Vln( G,
G.
G.
From Assumption 2.5, we have f (x= S G. for all e [n]. Thus, the norm of each element is bounded by Also, since Σm V((=*) nVF((") 0, it follows that these elements sum to O. Therefore, apply the Herding algorithm, as stated in Lemma 3.6, to obtain permutation o² [n] + [n] satisfying
V V (x))
HGG.
(22)
32

---

Incremental Gradient Descent with Small Epech Counts is Surprisingly Slow on IIl-Conditioned Problems
where H ((v)). We will demonstrate that this permutation o² is the desired one: the final iterate x obtained by running Algorithm for K epochs of a² satisfies the desired upper bound.
Using o", we define a sequence of iterates {æ; 12=0 as follows:
T x.
z; = - VV (or
Note that the sequence is obtained by using the component gradients at the minimizer x² From Ex= ()=()) nV Fxx") = 0, we can easily deduce that x; = x = x=
The proof follows the approach used Theorem in Mishchenko et al. (2020) with several modifications using the property from the Herding algorithm. We analyze the square norm distance || - x;|l using an iteration-wise recursive inequality:
| 2/ - = || | v (o - (0 - Vo (x))))
| xi- 1|@ -21/ (,ū - 2/-11 V fo (x Vfo((((²)))
+ r2 | V (s) (o
|| x;_1 11 - 2n (~ x²) + D fare (2)_,, Da (2)=1,
V fo (1) (x 1) (or
(23)
Here, (f 3) := = f(x) fly
(zy) y) denotes the Bregman divergence of f between and y. At (a), we
apply the three-point identity of the Bregman divergence.
The term Dir- (x x 1) in equation (23) can be bounded as follows:
Di (a
2 |
k
by the p-strong convexity of the component function. Moreover, from Lemma 2.29 of Garrigos & Gower (2023), we have
(oo-co (=- )1 S 2LD form (0f-1,
fo
Substituting these inequalities into equation (23), we derive
| x; 11 < x 1-1 2 11 2ny(1 -1LLD sn
m/ / 11 + 2nD (0/-1,
(1 mhu || -zi=ll 22mDs- forca (x) (2;-1,x²)
(6)
(1 mnl) || x; 11@ + H H2n LG?
(24)
where we apply 1 nt. 2 0 and Do (=*) 2 0 at (a). At (b), we utilize the T-smoothness of the component function and the property of the Herding algorithm, given in equation (22):
Disna (2i-,,
S 2 | x²1 10"11=
L
2
Σ V (oro)
1L <
(HG.)²
2
Thus, by unrolling equation (24) over all k [K] and all i [n), and noting that a; x xx, we obtain
nk
1 x=" 1| S (1 m |all
101 + H2 L.G2
Σ (1 mpp)²
(1 mn) nk
(1 mm))nK 10:00
11
H2n
7p
33

---

Incremental Gradient Descent with Small Epoch Counts is Surprisingly Slow Ill-Conditioned Problems
kmink 11200 - x²1 LG
We now substitute simplifies to
unk
max
log
|10-= I ) 3. When |20 æ²Il is sufficiently large, the above inequality VRHG.
H² LG? m a²11²
1 4
4lgg log?
xz1l pnn)
))
LG n K?
n2 K?
VKHG.
On the other hand, when | x= is small so that 1 chosen after the max operation, the above inequality simplifies to
a - x
1
e
GH
LH' H'
p²
p 1TRK2*
where we use ||0 x=1 In particular, using the L-smoothness of F, the function optimality gap can be bounded
S
YrHG. ank
L
H
F( - F(x")
|, x x01²²
p2n²
This ends the proof of Theorem 3.7.
C.4. Technical Lemmas
Lemma C.1. p, p, E R with < and let p' and o' denote the results of performing single step of gradient descent on a p-strongly convex and L-smooth 1-dimensional function f, starting from p and respectively, with a step size < t Then, it holds that < d' - p' & (1 mp)(a - p).
Proof. Using the gradient descent update rule, we obtain:
p' = p pー (V(p)
y' = q y vV(((
The difference between o' and p' can then written as:
- p' = (q - (V/(g) vs()))
= -q / V² f(u) du. .p
(25)
Since (u) satisfies μ S V2f(u) L, have pla p) 1 4 f() du Lig p). Substituting this inequality
equation (25) yields
0 < (1-nt)(appp) 5 s p' < (1 mp)(a p),
where the first inequality holds due to 1) < 7.
Lemma C.2. Let (o yk denote the sequence of permutations applied over K epochs to generate af. These permutations and the corresponding 2 satisfy the following properties:
The permutations {ox Tk=1 applied during the first K - 1 epochs, produce 24
+ K-1
K-1
For any k E [K], all indices in 1 appear before all indices in I_ in the permutation ox.
For any k E [K], let z denote the |1 iterate in the k-th epoch, i.e., obtained after processing all indices in I... k.I. Then, the inequality 24 S xx S 2 holds.
34

---

Incremental Gradient Descent with Small Epoch Counts is Surprisingly Slow Ill-Conditioned Problems
For 25 and its corresponding permutations tor M the following properties hold:
The permulations (Th { ) applied during the first K - epochs, produce 2==
J==1
For any k E [K] all indices in I- appear before all indices in 1+ in the permutation ox--
For any [K], let R.I- denote the |I+l-th iterate in the k-th epoch, i.e., obtained after processing all indices in L+. k.I,, 2_ 2 xx - holds.
Then, the inequality
1 Proof. We provide the proof for = and its corresponding permutations for k=1- The proof for = and for Jk=1 is analogous, as flipping the sign of a's leads to identical circumstances.
Step 1: The First Property. Let w - denote the iterate obtained by running Algorithm with the sequence of permutations {or /== starting from x= with step size Since 2 K-1 is defined as the maximum possible iterate after running Algorithm with K 1 epochs, it follows that wt K-1 S 24
K
Assume for contradiction that K- < 2 K-1, By Lemma C.I. , the iterate obtained by applying of starting from K-1 24 exceeds 2f.. This contradicts the definition of z which is the maximum possible final iterate after K epochs. Therefore, we conclude that w k-1 =h1
By recursively applying this reasoning, we deduce that for all I [K], running Algorithm with permutations for 3 generates 24.
Step The Second Property. We now prove the following claim:
Claim. Consider two steps of gradient updates using component functions f((x) and fz(2) with a, aj, starting from the initialization u. Then, regardless of the choice of the step size 17 applying Si first, followed by fz. results in a larger iterate than applying fj first, followed by fi.
Proof of the claim. The update equations are:
ti - 1/ (VF(u) - ai); Ui u, (VF(u)) aa))
" = -- (VF(u) az)
Uje uy - (VF(u,) a.).
Since as < aj, we have u, < Uj. Also, because V a monotonically increasing function, it follows that VF(u:) < Fugz). Now, check that subtracting uji from Uij yields positive difference:
Wij Ujj (u: -n (VF(w.)) az)) - [u)=-((F((u -a)))
(VF((u, VF(u)) +u,+ (u, + na,s)
=0
VF(()) 0.
Thus, Uja > Uij holds, completing the proof of the claim.
From the claim, conclude in of all indices in I_ (indices corresponding negative values) must appear before indices in 1 (indices corresponding to positive values). Otherwise, if there exists index in I_ that immediately follows an index in 14, switching these two indices would result in larger final iterate (due to Lemma C.1), contradicting the optimality of o This concludes the proof of the second property.
Step 3: The Third Property. Define M = Eier, 04 = - -ieer ai We claim that:
Claim.
1f0 1 2 - S y,M then -11M S 2+
k+1l -x" < holds.
A+1.1- is obtained by applying gradient update starting from 2 using the first I_ Proof of the claim. Note that the iterate 2 component functions of the permutation σ Let of denote the first 1_ parts of the permutation ok. We verify the bound as follows:
Lower Bound: -n S 24 k+1.1
x².
35

---

Incremental Gradient Descent with Small Epoch Counts is Surprisingly Slow on IIl-Conditioned Problems
By Lemma C.I, the iterate 24 -+1,1- is least large the iterate obtained by applying gradient updates following of starting from x² Also, if < x= holds, then
-VF())= = -F(x))-F(()) / (FF(a) s 1(x -p).
p x² holds. Thus, if the iterate falls below x², the next iterate obtained by applying the gradient update from the component in I_ will also remain below x².
This property guarantees that when the gradient update starts xx and follows of every iterate remains below x². Moreover, the total contribution of the gradient updates towards the negative direction by indices in I_ when starting from x is at most 11 Eier_ a4 1.M. Hence, 2+ I+I.J- xx 2 -M.M holds.
Upper Bound: 2+
-+1J1- xx S.
Again, by Lemma C.I, the iterate x_ from x² + n.M.
--1 is at most the iterate obtained by applying gradient updates following of. starting
xx holds. This means that the iterate obtained by following of starting from x² + n.M is also greater than x². Due to the property stated in the proof of lower bounding 24 J+I.J-- all intermediate iterates should be greater than x" as well. This leads to a contradiction, as the total contribution of the gradient updates towards the negative direction by indices in I_ when starting from x" + nyM will exceed n,M, leading 2+ I+L. x² 2 holds.
1+1.1 Assume by contradiction that 2+
-+III_- to fall below x". Hence,
Combining these two bounds, we obtain
1+1.1 - x² 50
MM S 24
and this ends the proof of the claim.
The claim shows that if O < 2f - x² 1 M, then -nI S 2+
1-1.1_ - x²' < 0 holds. By analogous reasoning,
if - 2+ 1-1,11 xx < 0, then < 2 k-1 x² < n holds. Combining these two statements, we have: if
0 5 xx S. M,, then 0 S x+1 x² S MM and 2+
k+1.1 xx² S 24 k++ hold.
Using these, we now proceed by induction to prove the third property. For the base case, the initialization point is 20 = x², satisfying the initial condition by 2 - x=- By induction, it follows that
k. < x= S
kk
for all & E [K]. This concludes the proof the third property.
Lemma C.3. With step size < t. S VF(u.) < 2G. holds for all i E (0000144) and 0 2 VF(1;) 2 -2G, holds for all j E (0) [|]]]]
Proof. Recall that the sequence iterate {4)) is defined as un = x" and each subsequent u, is obtained by applying a gradient update using the component function (x) u4-1- Specifically, we have
u 7/ (1,
u:-1 - m (VF((u))) - (x)())
for E [|_[]]
Now, we will prove by induction that 0 < VF((s) < 2G. holds for all E [[++]]. Initially, we have no = x² and thus V((uo) = O. Now, assume that 0 < VF(u)11) < 2G.. We divide the proof into two cases based on the value of (F(
Case 1. (F(U)-1) S ox,()-
36

---

Incremental Gradient Descent with Small Epoch Counts is Surprisingly Slow on Ill-Conditioned Problems
In this case, the update equation becomes:
Uj Uj-1 (VF(u)1)) - ar, 2 uj-1,
meaning that the iterate increases. Since F is an increasing function, we have VF(u,) 2 VF(u)-1) 2
Also, using the fact that all [a,] is bounded by G., bound the difference of the gradient between successive iterates via the L-smoothness of F:
(F)))) (F(u--)) s Llu u--1l S nL., G..
Thus, the deviation of (u,)) from VF(Ug-1) is most G., leading the following inequality:
VF(u)) & (F(uy-1) + G. ax2 G. 2G..
Case 2. VF(uj-1) (z)
In this case, the update equation becomes:
Uj 0j-1 (VF(uj-1) ax,())) S Uj-1,
meaning that the iterate decreases. Since FF is an increasing function, we have VP(u;) S 5 2G. Furthermore, by L-smoothness of F, we have VF(u)-1) - VF(x*) S L (uy-1 - x*). Then, can ensure that új is greater than equal to x² as follows:
" = 1j-1 1/V (F(U)-1)- - an,
2 Un-1 1/ (()-))
2 unー _ L - =x"
1
For both cases, we have shown that S VF(u,) < 2G..
We apply the same approach for (u:) The key difference is that the sign of a. is negative. This leads the result 0 2 VF(u,) 2 -2G. for all j E [.-]. This concludes the proof of Lemma C.3.
37

---

Incremental Gradient Descent with Small Epoch Counts is Surprisingly Slow on IIl-Conditioned Problems
D. Proofs for Large Epoch Lower Bounds
D.I. Proof of Theorem 4.1
Theorem 4.1. For any n. 2 2, k 2 2, and K 2 K, there exists a 3-dimensional function F satisfying Assumptions 2.3 and 2.4 with P = O, where each component funcciion shares the same Hessian, along with an initialization point æo. such that for any constant step size T7, the final iterate obtained by running Algorithm 2 satisfies
LG
F(w)) F("") 2 p2
Proof. Similar to the approach in Theorem 3.1, divide the range of step size into three regimes. For each regime, construct the overall function Fi, F2, and F3, respectively, along with their respective component functions and initial point. Finally, we aggregate these functions across different dimensions to derive the stated lower bound.
Each overall function is 1-dimensional, and carefully designed to satisfy the following properties:
(Small step size regime) There exists an initialization point zo poly(H, L, G) such that for any choice of 17 pmk the final iterate x obtained by running Algorithm 2 satisfies Fi (x Fi Fi
LG
(Moderate step size regime) There exists an initialization point ye poly(u, n, K, G) such that for any choice of E jank 2)) the final iterate vi obtained by running Algorithm 2 satisfies F2 (2 K F2(y") ž
Lo
pk
(Large step size regime) There exists an initialization point 2p poly(и, I, K, G)) such that for any choice of 17 [ oo). the final iterate zn obtained by running Algorithm 2 satisfies Fz Fa(=*) PK*
LC
Here, x², y², x" denote the minimizers of F1, F2. and Fs. respectively. All these functions are designed to satisfy Assumption 2.3. F1 and F3 satisfy Assumption 2.4 with component function within each overall function shares the same Hessian. Detailed constructions of Fi, F2, and F3, as well as the verification the assumptions and the stated properties are presented in Appendices D.1.1 D.1.3.
= 0, and F2 satisfies with = 0. Moreover, each
By following similar approach to the proof of Theorems 3.1 and 3.3, function F(x)= == Fxx =) Fi (x)) F2(v) + F=(=) and its component functions satisfy the stated assumptions. Also, since each dimension is independent, it is obvious that x= = (x", (x",v""," ,²","") minimizes F. Finally, by choosing the initialization point as 2o (Io, yo, zo), the final iterate x = (x yn _K obtained by running Algorithm 2 on I' satisfies
conclude that the aggregated 3-dimensional
LG
F(x F(x*) 2
K22
regardless of the choice of r > 0.
This concludes the proof Theorem 4.1.
In the following subsections, we present the specific construction of Fi. F2, and F3, and demonstrate that each satisfies the stated lower bound within its corresponding step size regime. For simplicity of notation, omit the index of the overall function when referring to its component functions, e.g., we write f((x) instead of f1x(1). Moreover, use the common variable notation z while constructing functions for each dimension, though we use different variables in the "dimension-aggrreattion" step.
D.1.1. CONSTRUCTION OF Fi
Let F (2) Kt 2 with component functions f((x) (x) for all i e [n]. It clear that F1 satisfies Assumption 2.3 and Assumption 2.4 with G = P 0, and its component functions share an identical Hessian. Also, we note that x 0 and Fi(=))=)
Let the initialization be xo = R nk- For all 17 (0, w ) the final iterate is given by
G
1
VRG
.K
= -11-11) 2
>
nk
4uK
38

---

Incremental Gradient Descent with Small Epoch Counts is Surprisingly Slow on IIl-Conditioned Problems
where the last inequality uses the fact that (1 1 )m 2 1/4 for all 2 2.
Thus, we have
(-(a)) = 44 )x 2 122 K2
LG
D.1.2. CONSTRUCTION OF F2
In this subsection, we let L' denote L/2. We construct the function by dividing the cases by the parity of n. We first consider the case where n is even, and address the case where n is odd later in this subsection. Let F2(x) = 4 with component functions
1 + Gx T
if n/2,
f1(z) =
4 Ga
otherwise.
Since 2, we have ='= 2 μ.. Thus, it is clear that f; satisfies Assumptions 2.3 and 2.4 with P 0, and shares the same Hessian. By Lemma F.1, the final iterate obtained by running Algorithm is given by
2
G 1 1 (1- (1-n
x = (1 nL.nk so + D' (+ (1 (1- )a.))ak..
By applying 17 2 knk
and setting
O, we derive
G 1 1- (1-n11)) (1 101 - IT..imn
zn L'
K
(1-
G
2 21'
- 11-1111111 (1 (1 - m))
G
1 (1- , nx
2 2T/
(1-(1nL'))
G
Σ 21/
(1 (1 11-nni nL)) (1 - c-
(26)
We analyze equation (26) by dividing the range of 1 into two regimes. Regime 1. 17 In this regime, can bound (1 - n as:
1 1 junk nt:)
mid' 21 (1 nnL')
MnL' L'
1 (1 nLL) >
4
4μK
where the second inequality uses e - <
u for all u E [0, 1]. Substituting this inequality into equation (26) gives 2
K (1-
8uK
Consequently, the function optimality gap satisfies
L'
LG2 μ1² K??
F2(x F2(x*)
(2 >
2
Regime 2. 17 E [ 1)
39

---

Incremental Gradient Descent with Small Epoch Counts is Surprisingly Slow on IIl-Conditioned Problems
In this regime, we bound 1/1/33
(1-m) 1)
1 1 (1-mLLh 21 1
[ n
2 e
Substituting this inequality into equation (26) gives
(1 (1-
21'
Since K K. we have + 2 2 2. Therefore, the final iterate x can be bounded as:
2 (1 (1-e-1) G
nK
Consequently, the function optimality gap satisfies
L' (x 22 LG
F2(21) -2( =
2
μ²K²²
We now focus on the case where n is odd. Let F2(x) 5/' x² with component functions
x
if 1
f1(x) =
L x² + Ga
if 2 is (n + 1)/2, if (m + 3)/2 sssm. n.n. n.
Ga
Compared to the case of even n, fz( = L/ is introduced newly. By Lemma F.2, the final iterate x.Kk obtained by running Algorithm satisfies the following equation:
2
1- - LlLiak
z = =1 (1- mkk so + T 1 (1 n/.'1m (1- -
kk
By applying 17 2 ank
1 and setting To O, we have
G 1 1- (1- nL'Ynk
(1 (1-(1-(()))) =1) 2
K
D 1- (1 - -1111²
1 (1- 1/ (1 (1-11-LL))
G
T7 (1- 11-((1 (1 (1-11/ n1n )))
1 - (1 - 1/110
1 1 (1 -
(1-nL')a-1 11
2 T7 (1 -(1 -1- ))) )))
(1-1-11/) 1 - n1-
G
(1 (1-n
(1 - nank)
1 (1-11-
21/
1 (1 nT'p
G
(1 1
1- (1 nT/ym- 1-(1-n1//--
1 11-11n (1 11-117L1)
21
Note that the inequality
1- nI- 1
2
1 (--11LL1 2
40

---

Incremental Gradient Descent with Small Epoch Counts is Surprisingly Slow on IIl-Conditioned Problems
holds for 2 2 since
2 2-2(1 2-2(11-11)) - 1- 11-11 =D'I"* + 12 2(1 2 (1 n1'1""
+ (1-11))-1221111----11111))-11111 nL'))
+ 11 -12(-=1/)=11111133
Hence, we deduce that
K
du (1 (1- (1- (1 (1-(11111))))111111 + 41'
G
(27)
We again analyze equation (27) by dividing the range of 17 into two regimes. Regime 1. 1) pmnk m
In this regime, we can bound (1 - m)L') - as:
1 1 (1 -I)
ata-122!
(1 (1- n( (__n1)1))) n(n
1)L'
MnnL' L'
4
8
8HK'
where the second inequality uses e' < 1 / for all u E [0, 1]. Substituting this inequality into equation (27) gives
(1-
32μK
Consequently, the function optimality gap satisfies
L'
LG
P2(x F2(x*)
2
4²2
Regime 2. 17 E 1 3)
In this regime, we can bound (1 - (1-1
- as:
21-(1-1) (1-1 _
1 - (1 - -T.t'² 2 1 -
2 2
- 21
Substituting this inequality into equation (27) gives
(1-
4L'
Since K3 2 16, we have 1 = 3 2 ak
Therefore, the final iterate r.K can be bounded as:
z 2 (1-e (1 -1
24K
Consequently, the function optimality gap satisfies
L' F2(xK) F2(x*)=
LG2
k) 2
2 K?

---

L'G Incremental Gradient Descent with Small Epoch Counts is Surprisingly Slow on IIl-Conditioned Problems
D.1.3. CONSTRUCTION OF F3
Let (x)x) = 2 with component functions fi(x) F2(2) for all E [n]. It is clear that Fi satisfies Assumption 2.3, Assumption 2.4 with G P = 0 and its component functions share identical Hessian. Also, note that x=" 0 and Fa(r")= = 0.
For all E 1 oo), the final iterate is given by
3 = (1 nb))a xo-
In this regime, the step size excessively large, resulting in
2 L -1 1- n- S
which implies (11 - ,L)=k
1. Thus, the iterate does not converge and satisfies
1 2
ool-
By setting the initialization To μk
G
we have
L (xo)² 2
LG2
Fa(x)) - Fa(x")))++)) = (x,)²²
2 2
1² K2
D.2. Proof of Theorem 4.3
Theorem 4.3. For any 2 A 2a2n and K 2 max (n2/n2, x3/2) there exists 4-dimensional function F satisfying Assumptions 2.3 and 2.4 with P K, along with initialization point Do, such that for any constant step size the final iterate obtained by running Algoritimm 2 satisfies
L2G
F( F(x=) 2
p K2
Proof. Similar to the approach in Theorem 3.1, we divide the range of step sizes. However, unlike the previous theorems where the range divided into three regimes, we divide the range into four regimes this case. For each regime, we construct the overall functions Fi, F2, Fa. and F4, along with their respective component functions and an initial point. Finally, we aggregate these functions across different dimensions derive the stated lower bound.
Each function is I-dimensional, and carefully designed to satisfy the following properties:
(Small step size regime) There exists an initial point zo poly(и, L, n, K, K,G) such that for any choice of rj
(o. (0.= the final iterate ..KK obtained by running Algorithm satisfies Fi (x Fi (i()) > L'd"
(Moderate step size regime 1) There exists an initial point yo = poly(μ, L, n, K, G) such that for any choice of 1 E pnk ) the final iterate v obtained by running Algorithm 2 satisfies (y ( Fe(y
KK
(Moderate step size regime 2) There exists an initial point 20 = poly(μ, L, n, K, G) such that for any choice of [ 7.), the final iterate =X obtained by running Algorithm 2 satisfies Fs(2 Fz(2")
L
17 e A
(Large step size regime) There exists initial point wp = poly(p, L, K, G) such that for any choice of n E [t, 00). the final iterate w obtained by running Algorithm 2 satisfies F3 (w - Fa(w")
L²G=
K
Here, x², 1/", 2", and w" denote the minimizers of F1, F2, Fs,, and Fa, respectively. All these functions designed to satisfy Assumption 2.3. Fi and Fa satisfy Assumption 2.4 with G = P = 0, Fa satisfies with P = 0. and F2 satisfies with P= K. Detailed constructions for Fj through F4, as well as the verification of the assumptions and the stated properties are presented in Appendices 1 to D.2.4.
By following a similar approach to the proof of Theorems 3.1 and 3.3, we can conclude that the aggregated 4 4-dimensional function F(x:) = (i(x) + (v) + Fs(z) + (w( satisfy the stated assumptions (additional sealar G can be absorbed
42

---

Incremental Gradient Descent with Small Epech Counts is Surprisingly Slow Ill-ondiiioned Problems
by rescaling G in each overall function). Also, since each dimension is independent, it is obvious that x (x 11 ww) minimizes F. Finally, by choosing the initial point 2n (To, yo, 2o, Wo), the final iterate x.. (x Un obtained by running Algorithm 2 on F satisfies
K _K w
L² k²K2
F(x F(x") 2
regardless of the choice of r7 > 0.
This concludes the proof of Theorem 4.3.
In the following subsections, we present the specific construction of F1, F2. F3, and F2, and demonstrate that each satisfies the stated lower bound within its corresponding step size regime. For simplicity of notation, omit the index of the overall function when referring its component functions, e.g., write f((x) instead of f1((2). Moreover, common variable notation x while constructing functions for each dimension, though we use different variables in the "dimension-aggrrgattor step.
the
D.2.1. CONSTRUCTION OF Fi
Let (x) = 52" with component functions f((x) = (x) for all E [n]. It is clear that Fi satisfies Assumption 2.3 and Assumption 2.4 with G 0. Also, we note that xx
and Fi Fxxx)
LG For all (o, (nn) the final iterate is given by μ²
Let the initialization be To
1
n
LG
2 k (1 m
In 2
1
2o 2
nk
442K
where the last inequality uses the fact that (1 ) 2 1/2 for all m 2
Thus, we have
1 1 L2G 2
F1(2 -i((")
K2
D.2.2. CONSTRUCTION OF F2
In this section, we focus on the case when n is a multiple of 4. Otherwise, we set 4 _ components satisfying the argument, and introduce at most three zero component functions. This adjustment does not affect the final result, but only modifies the parameters au and L by at most constant factor.
Let (2(x:) x² with component functions
Gx
if n/44 if n/4+1 n/2. if n 3n/4. if 3n/4+1
x
f((x)
Gæ
L-Au x2
For simplicity of the notation, let denote L 4p. Since 2 4, we have 0 < L. Thus, each fs is L-smooth, ensuring that the construction satisfies Assumption 2.3. The gradient difference between the component function Si and the overall function F& is bounded as
|| + G [1(L u
if Hisis n/4 or n/2 3n/4.
[V)((>) -F2(()) 1
if n/4 +1 i n/2 or 3n/4 + 1sisn.
(x || Therefore, the construction satisfies Assumption 2.4 with P = k. Additionally, we note that . and F²(x*)= O. Using these component functions, we first derive the closed-form expression for the iterates obtained by running Algorithm 2:
Since VF2(x) = pæz, it follows that [[(L- - n)æ(| < K
* n/ = 20 4
43

---

Incremental Gradient Descent with Small Epoch Counts is Surprisingly Slow on IIl-Conditioned Problems
(1 nD) 2 (1 10-11 nL) ynG
x n/2
(1 nL)
x n/4
nnG
(1 -1,1²² z + (1 (1 - (1-nL) mM
3n/4 x//2
4
4
k J3//1 (1 + na)² (1 TT) zt (1 + na)² (1 (1-))))))) 1
b F (1 + naa)
Let (1 -1-//// T and q: = (1 na)= R. Using these definitions, the epoch-wise recursion equation can be expressed as:
=pqu + q(1 -p) TM 30 k+1
4
By unrolling the above equation over & E [K], we obtain the final iterate K.
T K (pq)** 20 + 1- (pg) K
8(1 - p) 7mG
(28)
pq
4
We now state key inequalities regarding p and
[ )
Lemma D.1. Under the conditions K 2 K 2 n 2 3, the following inequalities for 1j E
if 1 E
1 juk 12
1. 1 - --
BpK
n2
if 1 E
" 1)
8L
L mL.
2. -(9)) K 2 e-l
if E unk +
3. T T-79
if 17 E
The proof of Lemma D.1 is presented in Appendix D.3. Setting the initialization point To = 0, equation (28) simplifies to
1- (pq)*
qnG
1
gMG
1-P P
g(l - p)
2
1. (1 p)
rnG.
(29)
n pq
Pq
4
4
pq
Now, we divide the range step size into regimes:
pak #
and
# A
Regime 1. 17 jnn #
In this regime, we have 1 - p 8uK
and 1-p9 z sqnu
Substituting these inequalities to equation (29) results
(1 (1- LG
xx z
40μ2K
Regime 2. 17 IL m In this regime, we have 1 - 2 and 1
2
Substituting these inequalities to equation (29) results
1-pq
npG
1-e
n²
p2
2
40
LL3
40
L
Using the assumption K > no. it follows that n >
x
K. resulting
(1- LG
40μ2K
44

---

Incremental Gradient Descent with Small Epech Counts is Surprisingly Slow on IIl-Conditioned Problems
Combining the results for the subdivided step size regimes, we have
In z (1 11-e (1-e-)) LG
40₂²
[ jmn )
for all 17 Finally, the function optimality gap is
(1x))²² L2
F2(2,) F2(x*)= = 2 4 K2
1
2
D.2.3. CONSTRUCTION OF F3
We focus the case where is even. If is odd, we introduce additional zero component function. This does not affect the final result but only modifies each parameter at most by constant factor.
In this subsection, we let T'' denote 1./ Let F3
x=² with component functions
b/ x² + Gr
if i otherwise.
11x)) =
I x² Gr
It is clear that each ft is L-smooth. Since 2 2, we have L' 2 μ. Thus, F3 is p-strongly convex, satisfying
Assumption 2.3. Also, we can easily verify that the construction satisfies Assumption 2.4 with P = O. We note that x = 0 and Fx = 0.
By Lemma F.1, the final iterate obtained by running Algorithm 2 is given by
zx (1-n11) -1-n
nk
T/ 1+ 1+ (1-1-11/) n//) (1-11nnL')at
G. 1- (1-nL')
3o +
Recall that nL 2nd7 and 3 1. Since 17 [ b), it follows that
I.-
1 S i, and (1 T//T/uk se
(1 - nT)n <
2n
Using these inequalities and setting the initialization as zo 0, the final iterate xit is expressed as:
G (1 nI)= (1 (1- (1-11- nL'juk) 2
G1 -1-c1
G (1 (1-e-1)²
K 2 D' (1
c1- # 2 L' 2
L'
2
Finally, the function optimality gap becomes
L'
G2
1.G
Fa(2 FF((==(())))
(2
k)²
z >
2
L
| K2
where the last inequality holds since 2 3/22.
D.2.4. CONSTRUCTION OF Fa
Let Fx) 2 with component functions fz(x) Fa(x) for all E [n]. It is clear that F, satisfies Assumption 2.3, Assumption 2.4 with G = P = O. Also, we note that x= = 0 and (x()) O.
For all E | oo), the final iterate is given by
xx = (1 - (1-nTT))m x
45

---

Incremental Gradient Descent with Small Epoch Counts is Surprisingly Slow on Ill-Conditioned Problems
In this regime, the step size excessively large, resulting in
2 2- L -1, 1- n- - 1
which implies [1 2 1. Thus, the iterate does not converge and satisfies
1 2
ooo-
By setting the initialization zo = vR pk- we have
)x(xx) F=(xx)) - (1 2
L L L²G²
(x0)²
K2
D.3. Technical Lemmas
Lemma D.1. Under the conditions K
K 2 n
the following inequalities hold for 1) E
pank +t)) n
L Spk
if 1) E
1. 1 P2
j 1.7
if 1
1 nL.
2. 1 (pq) K 2
e-
if 1
ynk 1
3. 1
if 1 E
# nT.
Proof. Recall the definitions of and q:
p = (1 nL) ;
(1 + na) = (1 n(L 4
To prove the first inequality, we divide the range of step size into two regimes: Junk 1/ and [/ n...). Note that the first
regime may be empty depending on the condition on K, but remains valid (i.e. wnk S + under the condition K 2 x² //n in the current theorem.
Regime 1. 77 E jmnk 1
In this regime, we can bound as:
L 8pK
p (1 (1- nL) <
<
unk
L Here, the first step holds because 17 2 unk In the final step, utilize the inequalities ap < 1 and e S 1 - fu for all " E [0, 1]. Hence, we can obtain 1 - 2 BuK
Regime 2. 1) [ . In this regime, we can bound as:
2 nu S
p= p=
8L'
Here, the first step holds because 17 2 E At the final step, we utilize the inequalities N and e x < 1 fu for all [0, 1]. Hence, obtain 1 1-
To bound 1 (, K, we first establish bounds for pq:
pq (1 (1 na)+ 12
-
-Tp
46

---

Incremental Gradient Descent with Small Epoch Counts is Surprisingly Slow on Ill-Conditioned Problems where we apply
_1_ at the last step. Therefore, obtain pak
1 (pg) 2 1 -
( =1-e-1 -1-
K
The last inequality requires more careful analysis. We further refine the bounds for pq. Using a that
4u < L, it follows
1
1 -L) 2 4np 4m
n²
71K
where the second step is due to 1) - WI
1 and last step holds by the condition k 2 2 3. Hence,
py nL) a (1 na) (1 (L a) v/aa (1 4nf 11)
(30)
We again divide the range of step size into two regimes: Regime 1. 17 E jun'' )
pnnk +t and [ +
In this regime, we have 17² L S mh.. Hence, equation (30) becomes
5
2 (1 4nj - 1/ 2 (1 5mp) ; 2 Tmp
Ey² <1 since 5mp < 1r
<assuming 2 2 3). Therefore, we obtain the following inequality:
1 pq
5mmu
Regime 2. 17 E [ )
In this regime, we have 122 2 m.. Hence, equation (30) becomes
pq 2 4np 12,3) (1 51)21,33 21 2
since 2,2 < n²
5 <1 <asssuming n 2 3). Therefore, we obtain the following inequality:
1 - 2 5r
This concludes the proof of the lemma.
47

---

Incremental Gradient Descent with Small Epoch Counts is Surprisingly Slow on III-Conditioned Problems
E. Proofs for Large Epoch Upper Bounds
In this section, we provide detailed proof for Theorem 4.4.
E.1. Proof of Theorem 4.4
Theorem 4.4. Let n. 2 1, K 2 (1 + P)R, and 2o be the initialization point. Suppose F is a function satisfying Assumptions 2.3 and 2.4. Then, for any choice of permutation ox in each epoch, the final iterate x obtained by Algorithm I
with a step size 1j = uak max (log (F(#s) F(="))"" k²) ) _13 satisfies
1PGD
L2G
F(x - F(x") 2 n²K²
Proof. We begin by noting the specific epoch condition used to prove the statement:
K 2 8k max (1, P} max log
(F(zo) - F(xx") 1) K2
.1.
I2G²
Given this epoch condition and the choice of step size n specified in the theorem statement, have nnL S / min {1,2}. which will be repeatedly utilized throughout the proof.
Consider the following epoch-wiss recursive inequality for the objective function:
L
F (x) k+11
S F (x)) + V (a²)
s+1
xx²)= +
k+1 - =zill
x
2
= FF - 7n
VF (xx)
1
Σ
Saa (z)- +
1T²n²
1 n
V faa (zf-1)
n2 i=1
2
72
1 n
F (x))
nmm
VF (a:))
2
mpn
(o)
(a
2
2
n
+
1m
VF
(x))
k
1
V
(o, (at-1)
+
n)²n L 2
1 1
V
Sou (of-1)
2
1=1
(0)
S F (x))
mm 2
VF (z)) ||
+
m
FF
(x))
V Vo (
2
1=1
(b)
< F (x))
m
VF
(a)))' ||
nL2
m
111
*
(31)
2
where (a) holds due to npl. < 1 1 and (b) follows from the inequality:
a Vfa (xtt1)
VF (x+)
(xt) - V (z
=
n
[(x(() (2t)
V 11
2
|
k
x 1
Next, we need to derive an upper bound for ||
112 For t [n], we have
||00 x. 1 n
farli (at-
48

---

Incremental Gradient Descent with Small Epoch Counts is Surprisingly Slow on Ill-onnditioned Problems
2
S 31)²
(oott (xf-1) - Voan (ati)
+ +3/f²
Σ (Voono (xt) - VF (at))
t
+ 3m²
F (20))
(a)
S 31 2
I
||
|
+ 1 6n2f (ce + p2 |F((+)))*) + 3 |F (=))]*
1=1
= 31 1L2
+ 1- 2
+ 3 G2
2Pd) || (=5))l
(32)
Here, (a) is derived by applying Assumption 2.4 through the following sequence of inequalities:
(Vooc VF
S t
(x)
VF
+
PIVF
t Σ
(2 + 2P2 |VF()))²))
i=1
s 212 (c² + p2 |VF(
Summing equation (32) over I = I,...,n n- 1, we have
(n- 1)m
- 2 + 6n² (n - 1)m(2n - 1) 0²
k 2-1
1|2 < 312
1
2
6
i=1
(n
1)m(2n 1)
+ 31/²
(1 (1+2P2) VF [1
6
S 33 2
Σ
k
1|
2 + 2n""n' + (1+2(
VF (1))
Given mmL S 4. it follows that 3n S and the above inequality simplifies to
Σ c o 1| I 4n + 21 VF (1
(33)
Substituting equation (33) to equation (31) results in
F (x) 111 S F (at)
|F (x))
2
2 +
nT?
Σ
n
k
x-11 2
2
2
i=1
S F(x))
TM
( ||
+
nL?
(An + (122)) [( 1))
2
2
S F(
MM
(1
- 2n 12 (1+ (1+2P')) |F
2 +
2
(0)
S F(*))
np
(>(())) 1| * 22
4
(
2 F(z)))
au
(F(z))
F(x')) + 27 n L'
2
49

---

Incremental Gradient Descent with Small Epoch Counts is Surprisingly Slow on IIl-Conditioned Problems
where (a),
rmL s and rn 1. ensuring 1 (1 2 + 1. and (b), utilize the 4f
assumption that F satisfies y--strongly convexity. We note that (b) is the only step where j--ttoong convexity of F is utilized, and it also holds under the weaker assumption that F satisfies the Polyak-Lojasiewicz condition. Thus, Theorem 4.4 remains valid when F satisfies the PL condition.
Rearranging this inequality leads to
mm F (xx =(x')= & (1-
(F (xx) - FF + L
2
and we can obtain
K
F (xx) Fxx") 1 (1- muu (F - F(x')) + 2n L2
[
1744
2
2
k=1
< (1
K
(F (xx) - F(xx)) + 21 L2
2
my
(xx) F") + 4n I
zank i
< c
We now substitute 7 unn above inequality becomes
2 max (og
(F(x)))F((()) -F(e)) F((e))) )a²k3 LAG²
1 For the case when F(xo) - F(xx") is sufficiently large,
L2G²
G
(F(zo) F(z K2
L2G²
F (x: F(xx) S
log²
1 K
L?G
1
For the case when F(xo)) - F(x") small so that is chosen after the max operation, the above inequality then becomes
F (x*)) F(x)) S 1 e. K
L²G²
16L
L2G²
KK² <
where we utilize F(x.)) - F(x*) s..
L'G²t ka. This ends the proof of Theorem 4.4.
50

---

Incremental Gradient Descent with Small Epoch Counts is Surprisingly Slow on Ill-Conditioned Problems
F. Lemmas
Lemma F.1. Let n an even number. Define F(x) = x²² with Compnnetttannctiinn
f((x) = 2 x +
Gr f
-02²²
Ga
otherwise.
Then, the final iterate x obtained by running Algorithm 2 for K epochs with a step size i starting from the initialization point zo, satisfies:
K zn = (1-1aa)
G 1 - (1-na)²
(1- (1- 11-11-ma)mk)
To a 1+ (1 - r/a3
Proof. For i S 2, the update rule is given as:
x = - n/x + G) (1 na))=;11 1/G.
For 2 + 1, the update rule is given as:
- (ax - -1 na) x + nG.
By sequentially applying the component functions, derive the following epoch- wise recursion equation:
n
k+I 0
-1-100 -1-na)" na)"= n Σ (1-N0 na)"aa + GnG
(1-na)-
Σ
(1- (1-na)" na)"= n-i
G (1- (1-
= (1 - (1- 20
(34)
where the last equality follows from the following observation:
G
na) )0- + G/
Σ
- 11-na)"=i=np (1)(1=)a)²
Σ
(1 (1-18 (1-ma)" n-
1=1
i= ++
i= +1
m/G (1 - (1 naa² [[]))))))
(1 na
Tja
G 1 - (1-(1- na) ;)
By unrolling equation (34) over A E [K]. we obtain the equation for the final iterate 2./h:
G 1- (1- 1aa)" nk
(1- (1 -nnaaa? 2
z
(1 - na nk
To
a 1 1- (1 - 7a)"
G 1- (1- ma)² "
(1 - na) nk
(1- - (1_))_m)
00
1 + (1 - na)5
Lemma F22 Let n be an odd number. Define F(x) = 222 with component functions
if =i=1.
2
f((x)
gx² + Ga
if2 sisis 11/2,
gI² Gr if (n 3)/2 sin
Then, the final iterate a obtained by running Algorithm 2 for epochs with step size n starting from the initialization point Vy. satisfies:
G. 1- (1 (1- 1-(1-70)n (1- (1 -na)
K 1
(1- =1-na)nkk
20
a 1 (1 m1a)n
51

---

Incremental Gradient Deseent with Small Epoch Counts is Surprisingly Slow on IIl-Conditioned Problems
Proof. Compared Lemma F.1, we have an additional component function [1(x) _ at the beginning of each epoch. For this function, the update for at is given as:
= - (1 rja)azg-
Thus, the epoch-wise equation in equation (34) of Lemma F.1 is modified as follows:
20 ++1 (1 maa""=af
G (1 (1 - na) = (1 - n + G
(1 (1 na) =
By unrolling the above inequality over & [K], we obtain the equation for the final iterate a
x = (1 na) 2o +
G. 1- 1-(1- -1--na)" maa)n
(1 (1- (1 na)
a 1 1 1-(1- -1111a))
Lemma F.3. Let n be even number. Define F(x) g. x with component funciinnn
20²² + Gr
n/2
f((x)
--²² Gr
otherwise.
Consider applying Algorithm for single epoch, starting from zyj equation:
The updated iterate k+1 satisfies the following
k+1 = (1+ na ) (1- na) 2 10
a ) na 3 (1+ (1 (1+(1-na)3) -2) G ((1+
Proof. For 3. the update rule is given as:
x =
- =
+ (C) (1- GG.
By sequentially applying the first half of the component functions, we obtain
$
Σ (1 11-ma1 na)² (1 na)² 20 nG 1- (1 na)
(1 na) 2
G
1ja
==0
G
(1 na)
$ 2
(1 (1 - n)))).
(35)
a
For i 2 2 + 1, the update rule is given as:
a -- = (1+ ():
na nG.
7)
2
Substituting the result from equation (35) into the update rule for the second half of the component functions, obtain
k+1 (equivalently, ) as follows:
B
2 2 (1++))=-1
0
1+1
11
nay
x
G
Σ
1+
may
(1+
na $
2 + GG.
2
na
i=0
na
L +
2G (
(1+
+
17
-1)
2
ny
G (1 (1 - maa))) + 2G (11 na : -1)
(1
na)
a
a
=
(1+
nay
(1 - na) z +
G ((1+ )
(1+ (1 - na)3) -2)
2
52

---

Incremental Gradient Descent with Small Epoch Counts is Surprisingly Slow on Ill-Conditioned Problems
G. Experiments
this section, we validate the lower bound convergence rates for the functions used lower bound construction of Theorems 3.3 and 3.5. We compare the performance of four permutation- SGD methods: IGD, RR, Herding at Optimum, and with-replacemmet SGD. Here, Herding Optimum refers the instance of Algorithm using the permutation suggested from Theorem 3.7 satisfying equation (22). As mentioned in Section 3.2, this permutation is generally unknown without prior knowledge of x". However, for the specific functions used in the lower bound construction, we can explicitly determine a permutation that satisfies equation (22). Thus, the plot for Herding represents the convergence rate achieved by a well-chosen permutation in permutation-based SGD.
Additionally, we conduct experiments using the MNIST (appendix G.3) and CIFAR-I0 (appendix G.4) datasets. For the real-world dataset, we compare the performance of IGD, RR, and with-replacement SGD. Training loss and the test accuracy of both MNIST and CIFAR-I0 reveal the significant slowdown of IGDat the early stages of the training. For details of the experiments, refer readers to the corresponding subsections.
G.1. Results for the Function in Theorem 3.3
Recall that the proof of Theorem 3.3 uses 4-dimensional functions, formulated through the "dimension aggregation" step. For clear observation, conduct experiments using the construction for the "Moderate" step size regime, and remove the first and the last dimension.
We use the parameters which corresponds to the moderate step size regime. First, we examine the trajectory of IGD when initialized at x in Figure 2. Recall that our construction is carefully designed so that the trajectory forms a regular n-polygon when starting from (T), (n)) (see Appendix B.2 for definitions). As illustrated in Figure 2, even when the iterate starts x", gradually drifts outward and rotates along a circular path.
1.0 x 10º, L = 1.0 x 10 G = 1.0 10 = 1.0 x 103, and choose the step size as v) unk
Optimization Trajectory of IGD
Initial Point
Start of Epochs
0.2
Final Iterate
0.1
Y Position
-02-
0.2
0.1
0.1
0.2
X Position
Figure 2. Trajectory of IGD with the function for Theorem 3.3, starting from the x" (the origin, purple dot), when K = 20. Blue dots starting point of each epoch, æf. while the cyan dot indicates the final iterate xf
Figure reports the function optimality gap for different permutation-batt SGD methods, when initialized at 1 (uo( pakk Vol ynk) )))) ))). Results for RR and with-replacement SGD, which involves randomness, are reported after av- eraging over 20 trials for each number of epochs k. The shaded region represents the first and the third quartiles across the 20 trials.
53

---

Incremental Gradient Descent with Small Epoch Counts is Surprisingly Slow on IIl-Conditioned Problems
One might wonder why the trend of IGD does not match the rate derived in Theorem 3.3, given by LG min 1, K J. We
believe this occurs because the theoretical rate serves as a lower bound on the true convergence rate, and the empirical performance of TGD in this experiment can be influenced by additional factors not captured in the theoretical bound.
Incremental Gradient Descent
10:
Random Reshuffling
Herding
10-2
With-replacement
Optimality Gap
10
10-4
10-4:
10-14
17
10
16a
10a
10
Epoch
Figure 3. Experiments on Theorem 3.3 for IGD, RR, Herding at Optimum, and with-replacement SGD. Both axes are log-scaled.
G.2. Results for the Function in Theorem 3.5
Recall that the proof of Theorem 3.5 uses 4-dimensional functions, formulated through the "dimension aggregation" step. For clear observation, we conduct experiments using the construction for the "Moderate Large" step size regime, and remove the first dimension.
We use the parameters 1.0 x 109, T. = 1.0 x 10 G 1.0 10 n 1.0 x 102, and choose the step size as 1) pnK
19a
Incremental Gradient Descent
Random Reshuffling
1014
Herding With-replacement
Optimallty City Gap
10
10
10-4.
102
10
10a
Epoch
Figure 4, Experiments Theorem 3.5 for IGD, RR, Herding Optimum, and with-replacement SGD. Both axes are log-scaled.
Figure 4 reports the function optimality gap for different permutation-bant based SGD methods, when initialized at (0, Results for RR and with-replacemeet SGD, which involves randomness, are reported after averaging over 20 trials for each number of epochs, k. The shaded region represents the first and the third quartiles over the 20 trials. As suggested by Theorem 3.5, the function optimality gap increases sharply as K decreases. In contrast, RR remains robust even for small K.
54

---

Incremental Gradient Descent with Small Epoch Counts is Surprisingly Slow IIl-Conditioned Problems
G.3. Experiments on MNIST Dataset
For the MNIST dataset, we consider the binary classification using only the data corresponding the labels 0 and 7. We consider the natural data ordering where all 0 images are followed by all / images. In this configuration, have total of 5,923 6,742 = 12,665 training data. We use step size 77 0.01 throughout every part of the training.
1G0
10a
SGD
0.8
Training Loss
10-1
Accuracy
0.7
0.6
10-3
IGD
10
SGD
2
8
10
0
4
10
Epochs
Epochs
(a) Training loss
(b) Test accuracy
Figure 5. Experiments on MNIST dataset for IGD, RR, and with-replacement SGD, y-axis for the training loss is log-scaled.
Figure 5 reports the training loss and the test accuracy for different permutation- based SGD methods, with a random initialization. Results are reported after averaging over 10 trials for each number epochs, k. The shaded region represents the 95% confidence interval over 10 trials. Unlike the experiments on the functions corresponding the theorems using fixed initialization, the randomness in the initialization for this experiment introduces confidence interval even to IGD. Both the loss and the accuracy show no significant difference between RR and with-replacement SGD, while IGD shows significantly slower convergence compared to the other two methods.
G.4. Experiments on CIFAR-10 Dataset
For the CIFAR-10 dataset, we also consider the binary classification using only the data corresponding to the labels airplane and automobile. We consider the natural data ordering where all airplane images are followed by all automobile images. In this configuration, we have a total of 5,000 + 5,000 = 10,000 training data. We use a step size 7j = 0.001 throughout every part of the training.
One slight difference from the experiment on the MNIST dataset that we use a mini-batch of size 16 for the training. This due the instability of IGD training. To ensure convergence of IGD with reasonable step size-such that the loss function decreases even with a small number of training epochs-ws employ its mini-batch variant. For fair comparison, we also adopt the corresponding mini-batch versions of RR and with-replacement SGD.
Figure 6 reports the training loss and the test accuracy for different permutation-based SGD methods, with a random initialization. Results are reported after averaging over 10 trials for each number epochs, k. The shaded region represents the 95% confidence interval over trials. Both the loss and the accuracy show no significant difference between RR and with-replacement SGD, while IGD shows significantly slower convergence compared to the other two methods.
55

---

Incremental Gradient Descent with Small Epoch Counts is Surprisingly Slow on IIl-Conditioned Problems
7x10-1
IGD
0.8
Ba LU33
Accuracy
0.7-
x 10-1.
IGD
10
Epochs
Epochs
(a) Training loss
(b) Test accuracy
Figure 6. Experiments CIFAR-10 10 dataset for IGD, RR, and with-replacement SGD, y-axis for the training loss log-scaled.
56


Reviews:
[{"review_id": "DiWETndT09", "reviewer": "Reviewer_oG8h", "summary": "This paper analyzes Incremental Gradient Descent (IGD) method in various convex settings, and establishes lower bounds of IGD in the small epoch regime and large epoch regime. This paper also provides upper bound results for arbitrary permutation-based SGD in several small epoch and large epoch regimes. This paper also design a new permutation-based SGD method that outperforms with-replacement SGD in small epoch regime with strongly convex component functions.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the thoughtful review. Below, we address the reviewer’s concerns.\n\n1. **The storyline of paper is not so clear.**\n    - While our analysis does involve three different permutation schemes—Incremental Gradient Descent (IGD), arbitrary permutation-based SGD, and Herding at Optimum—we would like to clarify that these schemes form a well-connected framework rather than a disjointed collection of results.\n    - First, we emphasize that **(1) IGD** appears exclusively in **lower bounds**, and **(2) Arbitrary permutation-based SGD** appears only in **upper bounds**. Importantly, arbitrary permutation-based SGD contains the worst-case permutation scenario. Therefore, when the LB of IGD matches the UB of arbitrary permutation-based SGD, we obtain tight convergence guarantees for worst-case permutation-based SGD (as discussed in Line 171 (left) and Appendix A). Our results establish such bounds across both small and large epoch regimes, and under varying assumptions on the component functions.\n    - **Herding at Optimum** (Theorem 3.7) illustrates how fast permutation-based SGD can converge under (near-)optimal permutations in the small epoch regime. Together, the three schemes characterize the full spectrum of convergence behavior for permutation-based SGD, from worst-case to (nearly) best-case. One caveat is that as discussed in Line 377 (left), the current Herding at Optimum is not an implementable algorithm in general scenarios; making it practical is a promising direction for future work.\n2. **Several assumptions are very restrictive.**\n    - We would like to clarify several points that may help the reviewer better understand the context behind these choices.\n    - First, unlike the upper bound analysis, strong assumptions in lower bound theorems strengthen the result. This is because the **narrower** the function class for which a lower bound holds, the **stronger** the applicability when compared with upper bounds.\n    - Also, we acknowledge that assumptions on the component functions’ Hessians (e.g., identical Hessians or strong convexity) may appear restrictive. However, our results show that the convergence behavior of IGD varies significantly under different settings. Thus, these assumptions serve to illustrate meaningful distinctions, rather than to artificially strengthen the conclusions.\n    - Lastly, in upper bound analyses, stronger assumptions indeed weaken the result. As pointed out by the reviewer, 1D setting in Theorem 3.2 is quite restrictive. However, deriving upper bounds for permutation-based SGD methods in the small epoch regime is known to be **extremely challenging** without strong assumptions. Specifically, [1] derives an upper bound for Random Reshuffling, but only under strong conditions—quadratic objectives with component Hessians that are mutually commutative, symmetric, and PSD—essentially reducing the problem to 1D.\n3. **This paper seems to lack a striking result.**\n    - We would like to highlight that our main contribution lies in addressing a largely underexplored regime: **the small-epoch behavior of shuffling methods**. To our knowledge, except for the result by [1], no prior work establishes tight convergence bounds in this regime.\n    - Our paper provides tight lower and upper bounds for IGD in this regime. While IGD is the simplest among permutation-based methods, the theoretical analysis in this regime is highly nontrivial and challenging (see Section 2.4).\n    - In particular, when the component functions are allowed to be nonconvex, we show that the convergence of IGD can be *exponentially* slow. Our result is the first to rigorously establish this phenomenon, suggesting that permutation-based SGD methods can suffer severe slowdowns in the small epoch regime. This motivates further investigation into whether similar slowdowns occur in other permutation-based SGD methods, including Random Reshuffling (RR).\n4. **Adding some simple numerical experiments would boost the confidence in the correctness of the proofs.**\n    - We would like to note that we included numerical experiments on our lower bound constructions in Appendix G (as mentioned in Line 303 (right)). These experiments confirm that IGD exhibits slow convergence on the constructed objectives from Theorems 3.3 and 3.5. In particular, we observe exponential-type slow convergence in the case of Theorem 3.5.\n    - In addition, another reviewer suggested evaluating performance in a more practical scenario. During the rebuttal period, we conducted experiments on a binary classification task using two selected labels from the MNIST dataset. We kindly refer the reviewer to our response to Reviewer RSZD for further details.\n\nWe hope our responses have fully addressed your concerns. If you have any remaining concerns or questions, we would be happy to respond.\n\n---\n\n[1] Safran, Itay, and Ohad Shamir. \"Random shuffling beats SGD only after many epochs on ill-conditioned problems.\" NeurIPS 2021", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "Yes", "theoretical_claims": "I do not have the time to go through all the details. Up to what I have verified, everything looks correct.", "experimental_designs_or_analyses": "NA, purely theoretic work.", "relation_to_broader_scientific_literature": "There are several permutation-based SGD published in past ICML events.", "essential_references_not_discussed": "NA", "other_strengths_and_weaknesses": "Strengths:\n- This paper is generally well-written.\n- The upper bound and lower bound analysis of IGD is comprehensive, complementing existing work.\n- The discovered slow performance of IGD in the small epoch regime is interesting.\n\nWeaknesses:\n- The storyline of paper is not so clear. The current version seems like a collection of upper bounds and lower bounds under various setups, using different permutation schemes, i.e., the results are not strongly connected. \n- Several assumptions are very restrictive, e.g., 1-dimension assumption in Theorem 3.2\n- This paper seems to lack a stricking result imho.", "other_comments_or_suggestions": "Adding some simple numerical experiments to justify the theoretical results would greatly boost the confidence in the correctness of the proofs.", "questions_for_authors": "NA", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "lKKCwTUF8Z", "reviewer": "Reviewer_oi4v", "summary": "The paper is inspired by the common use of shuffling-based methods such as Random Reshuffling in practice, and the authors provide new theoretical results for specific permutations. In particular, they give new lower bounds on the Incremental Gradient (IG) method in the low-epoch regime, which wasn't considered much in the prior literature. The results concern the strongly convex case, but with multiple options on the individual components: either all of them are strongly convex, or just convex, or even potentially nonconvex. Somewhat surprisingly, this affects the provided lower bounds, despite that distinction having smaller importance in the large-epoch regime. \n\nThe results can be of interest due to the popularity of shuffling methods in practice and the fact that there are still open questions and gaps. The result concerning Herding is interesting since it shows that potentially better permutations can be obtained to make shuffling methods faster.\n\n## update after rebuttal\n\nI thanks the authors for the interesting discussion. I remain positive this is a good paper and I hope it gets accepted.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the careful review and for the positive assessment of our paper. Below, we address the reviewer’s concerns and comments.\n\n1. **The main limitation of the work, in my opinion, is that it considers the least interesting of the shuffling methods.**\n    - We agree with the reviewer’s view that IGD is the least interesting among the shuffling methods, and that deriving new results for RR would be more impactful. While we did attempt to extend our analysis to RR, we were unable to derive new convergence bounds. Nevertheless, given the scarcity of existing literature on permutation-based SGD in the small epoch regime, we believe that IGD offers a good starting point for understanding this regime better.\n    - Specifically, for IGD, constructing a lower bound requires designing a function specifically tailored to exhibit poor performance under a fixed permutation, and it is acceptable if this function converges quickly under other permutations. In contrast, for RR, we now have to design a function that consistently exhibits slow convergence on average over a wide range of permutations, making the analysis more challenging.\n    - We believe that obtaining new bounds (both upper and lower) for RR on general functions in the small epoch regime likely requires fundamentally new techniques. Developing such bounds for more complex shuffling schemes remains an important direction for future work.\n2. **From the proofs, it appears to me that the lower bounds can be immediately extended to also include claims on the distance to the solutions.**\n    - Yes, the reviewer is absolutely correct that the proofs can be directly applied to derive lower bounds in terms of the distance to the solution, i.e., $\\lVert x_n^K - x^*\\rVert$. The reason why we state the lower bounds in terms of the function optimality gap is to match the form of the upper bounds. This consistency allows us to make a direct comparison and claim tightness between the lower and upper bounds. We will add a remark to clarify that our lower bound proofs can directly be used to obtain bounds in terms of the distance metric.\n3. **Minor suggestion (vector, plural, capitalize)**\n    - Thank you for the careful reading. We have revised your suggested corrections.\n\nWe are glad the reviewer took the time to read the proofs of Theorems 3.1 and 3.7. If the reviewer is interested, we would also like to recommend going over Theorem 3.3, which we believe contains the most novel idea in the paper. If there are any further comments or questions, we would be happy to address them.", "claims_and_evidence": "All theoretical claims are supported by rigorous proofs. One of the results is also verified numerically.", "methods_and_evaluation_criteria": "The used criteria are standard in the optimization community.", "theoretical_claims": "I checked the correctness of Theorems 3.1 and Theorem 3.7. The former is a simple construction based on three one-dimensional functions, each of which plays a role in a certain stepsize regime: small, medium, or large. The small and the large regime functions are simple quadratics. The actually interesting case is the medium stepsize, that's when the dynamic is controlled by linear terms that make IG stray away from the optimal point.\n\nThe proof of Theorem 3.7 is mostly the same as the proof of Theorem 1 in (Mishchenko et al., 2020), which the authors explicitly state in the appendix. The main difference is the variance bound, which for Herding is improved since it's by definition better than a randomly sampled permutation.", "experimental_designs_or_analyses": "The numerical results are pretty simple and their soundness is immediately verifiable.", "relation_to_broader_scientific_literature": "The work follows up on the series of papers published in the last few years and adds a solid contribution closing some of the theoretical gaps.", "essential_references_not_discussed": "I don't think there are any crucial papers missed. The paper doesn't discuss some of the papers on random reshuffling in other settings (proximal, distributed, etc.) but I think it's completely reasonable as the main focus on closing the gaps in the most basic setting of stochastic optimization.", "other_strengths_and_weaknesses": "The main limitation of the work, in my opinion, is that it considers the least interesting of the shuffling methods. I still believe it provides sufficient new intuition to publish the paper, but I just wanted to point out that having new results on random reshuffling would have been more interesting.", "other_comments_or_suggestions": "From the proofs, it appears to me that the lower bounds can be immediately extended to also include claims on the distance to the solutions. Am I missing something? If not, I encourage the authors to state those as well.\n\nMinor:  \nIn the equation in Definition 2.1, $x$ and $y$ after the $\\forall$ symbol should be bold as well.  \n\"Cha et al.(2023) establishes\" -> \"Cha et al.(2023) establish\".  \nIt would be nice to capitalize names in the citations, for instance \"SGD\" instead of \"Sgd\".", "questions_for_authors": "Please see my suggestion/question on the extension of lower bounds to distances.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "6WhKfXsA4C", "reviewer": "Reviewer_RSZD", "summary": "This paper studies the Incremental Gradient Descent, a permutation-based SGD method. The authors derive a lower bound on the algorithm's progress when the number of epochs is small. This paper provides results for various classes of problems, when 1. all he component functions are strongly convex, 2. all components are strongly convex with the same Hessian, or 3. some functions are non-convex. This is an essential result as modern machine learning applications are ill-conditioned; in most cases, we are in a small epoch regime.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We appreciate the reviewer for the constructive feedback. Below, we address the reviewer’s concerns.\n\n1. **Similar lower bounds can be derived for other algorithms like SGD (with uniform sampling) in the small epoch regime.**\n    - As the reviewer pointed out, it is true that any algorithm (including IGD, SGD with uniform sampling, etc) with a finite number of iterations will naturally have some lower bound. However, our focus is more specific: given a fixed number of epochs $K$, we aim to characterize how fast an algorithm converges to the minimum with respect to $K$.\n    - It is well known that for SGD with uniform sampling, both the upper and lower bounds are of order $O(1/\\mu T)$, where $T$ is the total iterations. Recall that $T = nK$ in our setting. This rate holds uniformly in both the large and small epoch regimes. In contrast, our results for IGD reveal a clear separation between the convergence rates in the large and small epoch regimes. In particular, we show that in the small epoch regime, the LB for IGD is strictly worse than the UB for SGD with uniform sampling. This directly implies that IGD converges more slowly than SGD with uniform sampling in this setting.\n    - If we have misunderstood the reviewer's question, we would appreciate it if you could kindly clarify.\n2. **The algorithm's proofs use a step size that depends on the optimal point $x_*$.**\n    - The reason why we introduced $x^*$ into the step size is to reduce the dependence of the final convergence rate on the initial optimality gap $f(x_0)-f(x^*)$ from linear to a logarithmic scale. Even if the step size is chosen without $x^*$, the overall dependence on major parameters (e.g., $\\mu, L, n, K$) remains unchanged.\n    - We also would like to note that using step sizes depending on $x^*$ is a common practice in the literature [1, 2, 3].\n3. **The paper requires experiments to evaluate if IGD performs worse than SGD with uniform sampling in the small epoch regime.**\n    - During the rebuttal period, we conducted experiments on a binary classification task using two selected labels from the MNIST dataset. We trained a CNN using IGD, RR, and with-replacement SGD. In our setup, IGD uses all samples from one class, followed by the remaining samples from the other class. We provide the figures for the training loss and test accuracy at the following link: https://anonymous.4open.science/r/ICML2025-IGD-134A. In the figures, confidence intervals are calculated over 10 different runs; for IGD, the variability arises from different random initializations. As expected, we observe that IGD converges much slower than vanilla SGD. We plan to conduct more extensive experiments on broader datasets and model architectures, and will include these results in the next revision. We hope this addresses your concerns.\n4. **IGD is deterministic. Why do you need assumptions 2.4, 2.5?**\n    - We note that our upper bound results hold for arbitrary permutation-based SGD, not solely for IGD. As this covers all possible permutation selection schemes, including random choices, we believe that it is natural to have some kind of gradient error bound like Assumptions 2.4 and 2.5.\n    - However, even when focusing solely on upper bounds for IGD, we still believe that Assumptions 2.4 and 2.5 are essential. While IGD is a deterministic algorithm, the convergence behavior is still significantly influenced by the structure of component gradients. For instance, in the case where all components are identical, i.e., $f_i=f$, IGD can exhibit an exponential convergence rate. On the other hand, when the gradients of component function differ substantially from each other, the iterates can fluctuate significantly, leading to slower convergence.\n    - As discussed in Section 2.4, a key technique in analyzing the convergence of permutation-based SGD methods is controlling the cumulative error within each epoch. We note that this cumulative error and the fluctuation of iterates are closely related. Therefore, even for IGD—the simplest and fully deterministic permutation-based algorithm—some form of assumption to control gradient error is still necessary to establish proper convergence guarantees.\n    - Finally, we note that similar assumptions on component gradients are commonly made in prior IGD literature [4, 5].\n\nIf you have any remaining questions or comments, we will happily answer them.\n\n---\n\n[1] Lu, Yucheng, et al. \"Grab: Finding provably better data permutations than random reshuffling.\" NeurIPS 2022\n\n[2] Cha, Jaeyoung, et al. \"Tighter lower bounds for shuffling SGD: Random permutations and beyond.\" ICML 2023\n\n[3] Liu, Zijian, and Zhengyuan Zhou. \"On the last-iterate convergence of shuffling gradient methods.\" ICML 2024\n\n[4] Mishchenko, Konstantin, et al. \"Random reshuffling: Simple analysis with vast improvements.\" NeurIPS 2020\n\n[5] Koloskova, Anastasia, et al. \"On convergence of incremental gradient for non-convex smooth functions.\" ICML 2024", "claims_and_evidence": "The algorithm's proofs use a step size that depends on the optimal point $x_*$. This is not practical as $x_*$ is unknown.", "methods_and_evaluation_criteria": "The paper doesn't provide extensive experiments, so it is hard to evaluate whether the IGD algorithm is worse than SGD with uniform sampling for the small epoch regime.", "theoretical_claims": "The authors claim \"Our lower bounds reveal that for the small epoch regime, IGD can exhibit surprisingly slow convergence even when all component functions are strongly convex.\"", "experimental_designs_or_analyses": "The papers lack experiments. It fails to show in practice that Incremental Gradient Descent does not perform well in the small epoch regime.", "relation_to_broader_scientific_literature": "This is an essential result as modern machine learning applications are ill-conditioned; and in most cases, we are in a small epoch regime. Therefore, this result helps us to understand what is a good algorithm for training modern neural networks.", "essential_references_not_discussed": "I am happy with the papers cited in the paper to understand this work.", "other_strengths_and_weaknesses": "Strength:\n1. The paper provides new lower bounds for Incremental Gradient Descent in small epoch regime.\n2. This paper provides insight into the computationally constrained setting.\n\nWeakness:\n1. I believe similar lower bounds can be derived for other algorithms like SGD (with uniform sampling) in the small epoch regime. This is because you put a upper bound on the number of iterations (with condition number).\n2. The paper requires experiments to evaluate if IGD performs worse than SGD with uniform sampling in the small epoch regime.\n3. The step sizes in Theorem 3.2, Proposition 3.4 require the knowledge of $x_*$ which is not known in practice.", "other_comments_or_suggestions": "1. Authors should conduct more experiments to evaluate the performance of these algorithms in the small epoch regime.", "questions_for_authors": "1. The IGD algorithm is deterministic. Then why do you need assumptions 2.4, 2.5 to prove convergence?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "PwCwhIJo4s", "reviewer": "Reviewer_1iDN", "summary": "This work investigates the convergence of shuffling gradient methods, especially focusing on the small epoch regime. The authors establish several new upper/lower bounds that are matched to each other, providing new insights into the finite-sum optimization problem.\n\n## update after rebuttal\n\nI keep my positive score as this is a good paper in my opinion.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We appreciate the reviewer for the positive feedback. Below, we address the reviewer’s comments.\n\n1. **The exponential term in Theorem 4.6 of [Liu et al., 2024] is in the order of $LD^2 \\exp(-K/\\kappa)K^{-1}$, which improves a factor of $K$.**\n    - Thank you for pointing out this issue. We have revised our original statement to accurately reflect that Theorem 4.6 of [Liu et al., 2024] also refines the exponential term. Specifically, we now write: “Also, a more recent result by [Liu & Zhou, 2024] (Theorem 4.6) refines the polynomial term and also improves the exponential term to $\\exp(-K/\\kappa) \\frac{LD^2}{K}$. However, since the term inside the exponential remains unchanged, this still fails to reveal a tight bound when $K$ is small.”\n2. **Can the assumption in Proposition 3.4 be relaxed to $\\frac{1}{n} \\sum_{i=1}^n \\|\\| \\nabla f_i (x^*) \\|\\| \\le G_*$?**\n    - Great question. Yes, the reviewer is absolutely right that we can obtain exactly the same convergence result as in Proposition 3.4 under the weaker assumption $\\frac{1}{n} \\sum_{i=1}^n \\|\\| \\nabla f_i (x^*) \\|\\| \\le G_*$. The reason why we state the stronger assumption is to maintain consistency with the assumptions used throughout the rest of the paper.\n\nIf you have any remaining questions or comments, we will happily answer them.", "claims_and_evidence": "All claims are proved.", "methods_and_evaluation_criteria": "N/A.", "theoretical_claims": "As far as I can see, theorems are correct.", "experimental_designs_or_analyses": "The experiments are enough to demonstrate the correctness of theorems.", "relation_to_broader_scientific_literature": "N/A.", "essential_references_not_discussed": "N/A.", "other_strengths_and_weaknesses": "The paper is written clearly and is highly polished. There is no specific weakness I can find.", "other_comments_or_suggestions": "I found one inaccurate statement.\n\nLine 216 (right column), [1] also refines the exponential term. Concretely, the exponential term in Theorem 4.6 of [1] is in the order of $LD^2\\exp(-K/\\kappa)K^{-1}$, which improves a factor of $K$. Although this change doesn't imply [1] is optimal in the small epoch regime, it is better to be accurate. \n\n**Reference**\n\n[1] Liu, Zijian, and Zhengyuan Zhou. \"On the last-iterate convergence of shuffling gradient methods.\" arXiv preprint arXiv:2403.07723 (2024).", "questions_for_authors": "I only have one question.\n\nTheorem 5 in [1] only requires $\\frac{1}{n}\\sum_{i=1}^n\\left\\Vert\\nabla f_i(\\boldsymbol{x}^*)\\right\\Vert \\leq G_*$ in contrast to the stronger assumption $\\left\\Vert\\nabla f_i(\\boldsymbol{x}^*)\\right\\Vert \\leq G_*,\\forall i\\in\\left[n\\right]$ assumed in Proposition 3.4. Can this gap be fixed?\n\n**Reference**\n\n[1] Mishchenko, Konstantin, Ahmed Khaled, and Peter Richtárik. \"Random reshuffling: Simple analysis with vast improvements.\" Advances in Neural Information Processing Systems 33 (2020): 17309-17320.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: Summary: The paper inspired studies of shuffling-based methods and provides new theoretical results for specific permutations. In particular, it gives new lower bounds on the Incremental Gradient (IG) method in the low-epoch regime. The results concern the strongly convex case, but with multiple options on the individual components: either all of them are strongly convex, or just convex, or even potentially nonconvex.

On Reviews: All reviewers suggested acceptance. During the rebuttal phase, the authors respond clearly to all questions raised.

I advise the authors to incorporate the feedback they received into the updated version of their work, especially the comments regarding upper and lower bounds for RR in the small epoch regime, mentioned during discussion with Reviewer oi4v.

I recommend acceptance.
Decision: Accept (poster)