Incremental Gradient Descent with Small Epoch Counts is Surprisingly Slow on Ill-Conditioned Problems

We appreciate the reviewer for the positive feedback. Below, we address the reviewer’s comments.

1. 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$.
   • 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.”
2. Can the assumption in Proposition 3.4 be relaxed to $\frac{1}{n} \sum_{i=1}^n \|\| \nabla f_i (x^*) \|\| \le G_*$?
   • 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.

If you have any remaining questions or comments, we will happily answer them.

We appreciate the reviewer for the constructive feedback. Below, we address the reviewer’s concerns.

1. Similar lower bounds can be derived for other algorithms like SGD (with uniform sampling) in the small epoch regime.
   • 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$.
   • 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.
   • If we have misunderstood the reviewer's question, we would appreciate it if you could kindly clarify.
2. The algorithm's proofs use a step size that depends on the optimal point $x_*$.
   • 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.
   • We also would like to note that using step sizes depending on $x^*$ is a common practice in the literature [1, 2, 3].
3. The paper requires experiments to evaluate if IGD performs worse than SGD with uniform sampling in the small epoch regime.
   • 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.
4. IGD is deterministic. Why do you need assumptions 2.4, 2.5?
   • 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.
   • 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.
   • 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.
   • Finally, we note that similar assumptions on component gradients are commonly made in prior IGD literature [4, 5].

If you have any remaining questions or comments, we will happily answer them.

[1] Lu, Yucheng, et al. "Grab: Finding provably better data permutations than random reshuffling." NeurIPS 2022

[2] Cha, Jaeyoung, et al. "Tighter lower bounds for shuffling SGD: Random permutations and beyond." ICML 2023

[3] Liu, Zijian, and Zhengyuan Zhou. "On the last-iterate convergence of shuffling gradient methods." ICML 2024

[4] Mishchenko, Konstantin, et al. "Random reshuffling: Simple analysis with vast improvements." NeurIPS 2020

[5] Koloskova, Anastasia, et al. "On convergence of incremental gradient for non-convex smooth functions." ICML 2024

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.

1. The main limitation of the work, in my opinion, is that it considers the least interesting of the shuffling methods.
   • 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.
   • 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.
   • 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.
2. 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.
   • 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.
3. Minor suggestion (vector, plural, capitalize)
   • Thank you for the careful reading. We have revised your suggested corrections.

We 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.

We thank the reviewer for the thoughtful review. Below, we address the reviewer’s concerns.

1. The storyline of paper is not so clear.
   • 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.
   • 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.
   • 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.
2. Several assumptions are very restrictive.
   • We would like to clarify several points that may help the reviewer better understand the context behind these choices.
   • 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.
   • 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.
   • 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.
3. This paper seems to lack a striking result.
   • 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.
   • 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).
   • 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).
4. Adding some simple numerical experiments would boost the confidence in the correctness of the proofs.
   • 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.
   • 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.

We hope our responses have fully addressed your concerns. If you have any remaining concerns or questions, we would be happy to respond.

[1] Safran, Itay, and Ohad Shamir. "Random shuffling beats SGD only after many epochs on ill-conditioned problems." NeurIPS 2021