acceptodds
Under review as a conference paper at ICLR 2027

Tight Rates for Random Reshuffling: Phase Transitions and Cost of Nonconvex Components

Abstract

Random Reshuffling (RR) processes all components once per epoch in a fresh uniformly random order. We study the worst-case convergence of constant stepsize stochastic gradient descent under RR for a finite sum of smooth component functions whose average is strongly convex. Although recent works have established convergence guarantees for RR, most results require the number of epochs to be sufficiently large, and a tight characterization across the full range of epoch counts has remained under-explored, both with and without component convexity. For convex components, by characterizing tight rates up to polylogarithmic factors, we establish a phase transition at , where is the condition number: RR matches the convergence of with-replacement SGD below this threshold and achieves faster rates above it. Without component convexity, we prove that order epochs are necessary in the worst case to reduce the last-iterate squared distance below a constant fraction of its initial value. Moreover, beyond this threshold, the convergence rate of RR worsens by a factor of relative to the convex-component rate. Together, these results characterize the cost of allowing nonconvex components, which takes different forms depending on the ratio .

Primary area:
optimization
Keywords:
random reshuffling, without-replacement SGD, finite-sum optimization

Reviews

Among:
Shape:
1234this paper, Top 4%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 3.33 over 3 reviews, above 96% of the others.
Reviewer_mvzyOpenReview ↗
Rating
4
Confidence
3
Informativeness
2
Presentation
3
Soundness
3(+1)
Read review
Paper summary

The paper provides matching lower and upper bounds for SGD with random shuffling (they call RR) for strongly convex and smooth objectives. This extends recent work by Safran & Shamir that only held for quadratics (with commuting Hessians). The paper also considers the case where the individual loss functions are convex, or not. Perhaps the main take away is that RR can be theoretically faster than SGD with iid sample for the large epoch setting, where epochs$> $ condition number. 

Overall, the paper is well written and clear. Its contributions match exactly the contents, the bibliography is adequate, and I think there is some interest in understanding SGD with random shuffling, since this is what is done in practice when taking multiple passes over the data. Presenting also careful matching lower bounds really closes this question around analysiing RR for strongly convex. Finally, I've also sampled the proofs in the appendix, and find they too are written to a high standard, one for which I could easily follow the proofs. As such, I recommend accepting the paper. I have only minor questions and comments to make. 

[SGD-gen] SGD: General Analysis and Improved Rate,  Robert M. Gower, Nicolas Loizou, Xun Qian, Alibek Sailanbayev, Egor Shulgin, Peter Richtarik 2019 / International Conference on Machine Learning (ICML)

Critical strengths
  1. Filling in a clear gap in the analysis of SGD with random shuffling in the smooth strongly convex case

  2. Very clearly comparing this against SGD with i.i.d sampling

Critical weaknesses

The only weakness is really the standard asks for "more results", so I could always ask for more (what about the convex but non-strongly convex setting?), or "more impactful" since this is a specialized work for a rather specialized audience. But I do not think these are grounds for rejecting the paper.

Questions for authors

After Response The authors have answers all my question regarding unification or their results and the reliance on component wise convexity, and more. I'm satisfied with these answers, and maintain my high score (with a bit more confidence in my score)


I have only two main questions, and a few minor ones below.

Q1: With or without component convexity. I'm confused about the need for assuming component wise convexity for the SGD results in Proposition 3.3 and 3.4. First, the two results are very similar (just a bigger burn in phase of T≥κ2T\geq \kappa^2 for Prop 4.3).But also, I know that Proposition 3.3  also holds without strictly requiring that the componet functions be convex, see Theorem 3.2 in [SGD-gen]. This version of the proof assumes that a "expected smoothness" condition holds, for which the components function being convex and smooth is a sufficient condition. But there are also non-convex functions for which this condition holds, though I'm unaware of significant class of smooth functions (other than component wise convex) for which expected smoothness holds. You might also be able to loosen the assumptinos for you Theorem 3.2 (A.3 in appendix) by simply making (19) the assumption, as opposed to the consequence of component-wise convexity and smoothness. By doing this you might find that your resulting theorems holds for other functions classes. Furthermore, the proof of Proposition 4.3 (A.5) also requires only assuming expected smoothness, instead of the bound just above equation (12). In this sense, the proof of Proposition 3.3 and 3.4 could be unified using this expected smoothness assumption, the two results follow as mere corollaries, 

Q2: Comparing theory to practical multi epoch training. This is really a mix between a question and suggestion. Given how you show RR can be theoretically faster in the high epoch as compared to condition number regime, it would be interesting to at least take some of the smaller classification tasks and compare the number of epcohs to condition number. Such a logistic regression, with L2 regularization, and standard data sets from libsvm. This would highlight what your theory says in practice. It would maybe slightly strengthen the paper, but it also might not be insightful, or useful for this theoretical work (so take this as a light suggestion)

I also have some very minor point:

  1. Line 81: "RR can retain a constant fraction of its initial square distance when..." I couldn't make sense of this sentence when I first read it, but later understood after reading Proposition 3.1. I think it needs to be re-written. Maybe "The iterates of RR are bounded away from the solution by D/\sqrt{8}, where D is the initial distance?"
  2. Line 155: This quantity is sometimes referred to as gradient noise, see Garrigos 2023
  3. Proposition 3.1: Wouldn't it be better just to state that E∥xT−x∗∥2≥D2/8\mathbb{E}\| x_T -x^*\|^2 \geq D^2/8? Using this approx greater than for a constant bound is a little bit odd, since the "approx" bit could sometimes refer to dropping constants.
  4. Proposition 3.3: First, I was a bit confused if this proof was taken from Nguyen 2018 Theorem 2? If so you should state Proposition 3.3 [Nguyen 2018 Theorem 2]

And explain that you repeat the proof for convenience. If it's only adapted from Nguyen 2018 Theorem 2, then I think this is ok. The same question holds for Proposition 4.3

  1. You somtimes use DD or D0D_0 to denote the initial distance
3 comments

We sincerely thank the reviewer for the thorough reading of our paper. We particularly appreciate the detailed comments on our assumptions and proofs, as well as the suggestions for experiments and improvements to the presentation. Below, we address the two main questions and the minor comments.

Q1. Could Propositions 3.3 and 4.3 be unified using expected smoothness instead of component-wise convexity?

  • We have checked your suggestion, and we agree with the reviewer that Propositions 3.3 and 4.3 can be recovered using the expected smoothness condition (1n∑∣∇fi(x)−∇fi(x∗)∣2≤2L(F(x)−F(x∗))\frac{1}{n} \sum \\|\nabla f_i(x) - \nabla f_i(x^{\ast})\\|^2 \le 2 \mathcal{L}(F(x) - F(x^{\ast}))) without explicitly assuming component-wise convexity. Specifically, Theorem 3.1 of [SGD-gen], which considers SGD with a constant step size, gives an upper bound of O~(G∗2/(μ2T))\tilde{O}(G_{\ast}^2/(\mu^2 T)) when T≳L/μT \gtrsim \mathcal{L}/\mu. As the reviewer pointed out, we can take L=L\mathcal{L} = L when the components are convex and L=L2/μ\mathcal{L} = L^2/\mu when they are not necessarily convex. These recover the conditions T≳κT \gtrsim \kappa and T≳κ2T \gtrsim \kappa^2 in Propositions 3.3 and 4.3, respectively.

Could we also remove component-wise convexity for RR by directly assuming Eq. (19)?

  • This is an interesting suggestion. However, unlike SGD, it seems less straightforward to develop a unified framework for RR that covers both convex and nonconvex components by simply assuming Eq. (19). In our current proof of Theorem 3.2, we use the Bregman divergences of the individual component functions. More specifically, we show that the coefficients of these Bregman divergence terms are nonpositive, and then upper-bound the terms by zero using the nonnegativity of the Bregman divergences. Without component-wise convexity, the Bregman divergences are no longer guaranteed to be nonnegative, so the current proof does not straightforwardly extend to the nonconvex-component setting. In fact, our proof of Theorem 4.1 for the nonconvex-component setting takes a fundamentally different approach that does not rely on component-wise Bregman divergences. Likewise, replacing component-wise convexity with the expected smoothness assumption does not seem sufficient to extend the current proof, for the same reason.
  • That said, we think it may still be possible to introduce a different assumption, rather than Eq. (19), that would allow us to develop a unified framework for RR. Such a framework could potentially recover both the convex- and nonconvex- component results while also extending them to a broader class of functions. We think this is an interesting direction for future work.
  • Finally, we would also like to mention that our SGD results are mainly presented as benchmarks for comparison with RR, rather than as standalone contributions. For this reason, we stated the two SGD results separately under the same assumptions as the corresponding RR results, so that the comparisons could be made under consistent assumptions.

Q2. Can we verify a faster convergence of RR in high epoch as compared to condition number regime in a simple but practice-aligned experimental setting?

  • Following the reviewer’s suggestion, we conducted experiments on ℓ2\ell_2-regularized logistic regression to examine both the difference in the behavior between RR and SGD and whether the number of epochs required for RR to converge faster than SGD increases with the condition number. We updated our paper with the experiments in Appendix E. We explain the details and results below.
  • Logistic regression falls within our component-convex setting. We consider the finite-sum objective Fλ=1n∑i∈[n]fi,λ(w)F_\lambda = \frac{1}{n}\sum_{i \in [n]} f_{i, \lambda}(w) and fi,λ(w)=log⁡(1+exp⁡(−yixi⊤w))+λ2∥w∥22f_{i, \lambda}(w) = \log(1 + \exp(- y_i x_i^\top w)) + \frac{\lambda}{2}\lVert w\rVert_2^2, where yi∈+1,−1y_i \in \\{+1, -1\\}. We normalize all feature vectors by a common scale factor so that max⁡i∈[n]∥xi∥2=1\max_{i\in[n]}\lVert x_i\rVert_2=1. Under this normalization, FλF_\lambda is μ\mu-strongly convex with μ=λ\mu=\lambda, and each component is LL-smooth with L=λ+14L=\lambda+\tfrac14. Thus, κ=L/μ=1+14λ\kappa=L/\mu=1+\tfrac{1}{4\lambda}, allowing us to obtain large condition numbers by choosing sufficiently small values of λ\lambda.
  • To estimate how the squared distance to the minimizer decays with the epoch count KK, we fit a line to each window of five consecutive points on the log–log plot. The negative of the fitted slope gives the local decay exponent pp in K−pK^{-p}. For SGD, the estimated exponent was generally at most 1. For RR, it rose above 1 as KK increased, indicating faster convergence than SGD in the large-epoch regime. Lastly, the rise in the local exponent of RR tends to occur at larger epoch budgets as κ\kappa increases.

Minor Points

Q3-1. We now state the lower bound explicitly as E∥xnK−x∗∥2≥1/8∥x0−x∗∥2\mathbb{E} \lVert x_n^K - x^* \rVert^2 \ge 1/8 \lVert x_0 - x^* \rVert^2.

Q3-2. We have replaced the term “component-gradient variability” with “gradient noise”.

Q3-3. We originally used ≳D2\gtrsim D^2 for notational consistency with the upper bounds. We agree with the reviewer that writing ≥cD2\ge cD^2 with an explicit constant is clearer, and following the suggestion, we have revised the statements of Proposition 3.1, Theorem 4.2, and Proposition 4.4 accordingly.

Q3-4. The upper bounds in Propositions 3.3 and 4.3 are obtained by adapting the analyses underlying Theorems 2 and 4 of Nguyen et al. (2018), respectively, to a constant stepsize scheme. The proofs share the same backbone, but differ in how the recursions are unrolled to accommodate a constant stepsize. Since these bounds are not direct restatements of Nguyen et al. (2018), we describe these as adaptations in the text instead of using a heading such as “Proposition 3.3 [Nguyen et al., 2018, Theorem 2]”.

Q3-5. We now use DD consistently.

We hope our responses and revisions address your questions and suggestions. We would be happy to provide further clarification or discuss any remaining points.

Reviewer_mvzyOpenReview ↗

Thanks

Thanks for addressing all my questions. Ok, interesting that expected smoothness can unify these propositions, though not clear that this would actually improve the exposition of your results. In particular, because your proof still rely directly on assuming component-wise convexity, there are probably no gains in exposition in using expected smoothness to unite these propositions. Also thank you for the additional controlled logistic regression experiments. I'm satisfied with your answers, and will increase the confidence I have in my score.

Reviewer_1RsjOpenReview ↗
Rating
3
Confidence
2
Informativeness
3
Presentation
3
Soundness
3
Read review
Paper summary

The paper studies constant-stepsize random reshuffling (RR) for finite sums with LL-smooth components and a μ\mu-strongly convex average, focusing on the expected squared distance of the last iterate from the optimum. For convex components, the authors establish a tight worst-case rate of Θ~(G∗2μ2nKmin⁡{1,κK})\widetilde{\Theta}(\frac{G_*^2}{\mu^2 nK}\min\{1,\frac{\kappa}{K}\}) for K≳κ/nK\gtrsim\kappa/n, with the dependence on KK changing from 1/K1/K to 1/K21/K^2 around K≍κK\asymp\kappa. Without component convexity, they obtain a tight large-epoch rate of Θ~(LG∗2μ3nK2max⁡{1,κn})\widetilde{\Theta}(\frac{LG_*^2}{\mu^3 nK^2}\max\{1,\frac{\kappa}{n}\}) for K≳max⁡{κ,κ2/n}K\gtrsim\max\{\kappa,\kappa^2/n\}. They also show that the error can remain at least a constant fraction of the initial squared distance for K≲max⁡{κ,κ2/n}K \lesssim \max\{\kappa,\kappa^2/n\}. This gives a lower bound on the number of epochs needed to overcome the initialization error.

Critical strengths
  1. The convex-component result is a strong part of the paper. The authors prove tight squared-distance bounds for general smooth convex components, without assuming a quadratic model or commuting Hessians. The new lower bound improves the squared-distance bound obtained from the earlier function-value lower bound of Cha et al. (2023) by a factor of κ\kappa. This makes the phase transition at K≍κK\asymp\kappa sharp up to log factors.

  2. I also find the results without component convexity interesting. When κ≲n\kappa\lesssim n, the large-epoch rate is the same as in the convex-component case, but the initialization error can persist longer. When κ≳n\kappa\gtrsim n, the large-epoch rate is worse by a factor of κ/n\kappa/n, and RR needs more epochs before it beats SGD in worst-case scaling.

Critical weaknesses

I do not have major concerns about the paper. I have one question about the range of Theorem 4.2, as explained below.

Questions for authors

Theorem 4.2 does not exclude n<κ<1024nlog⁡2nn<\kappa<1024n\log_2 n, but the text following the theorem and Appendix D.1 say that the current constructions do not cover this range. Could the authors clarify how the theorem should be read in this interval? If the same lower bound follows with extra log factors, a short argument would be helpful. Otherwise, the range in the theorem should be stated more clearly.

The following are only suggestions for future work.

  1. The lower-bound construction for κ≤n\kappa\le n uses exponentially many dimensions and works for every permutation sequence. If the bound were only required to hold in expectation under RR, could the same initialization barrier be shown on one fixed instance in fixed or polynomial dimension, for every constant stepsize?

  2. It would also be interesting to see whether the bounds depend on how nonconvex the components are. For example, suppose each fif_i is τi\tau_i-weakly convex. Could the initialization threshold or the large-epoch rate be refined in terms of τ\tau? In particular, when κ≳n\kappa\gtrsim n, how much negative curvature is needed to obtain the extra κ/n\kappa/n factor?

2 comments

We thank the reviewer for the thoughtful review and suggestions for future work. Below, we address the question about Theorem 4.2 and discuss the two suggested research directions.

Q1. Theorem 4.2 does not exclude the crossover case n<κ<1024nlog⁡2nn < \kappa < 1024 n\log_2 n, but does not cover this range in the proof. How should we interpret Theorem 4.2 in this crossover range?

  • Thanks for pointing out this point. As mentioned in the paper, the original version has left a logarithmic gap in the crossover range between nn and κ\kappa. However, following the suggestion from reviewer BDb5, we were able to cover the remaining gap by slightly modifying the construction from the κ≤n\kappa \leq n case. Our Theorem 4.2 now applies to all nn and κ\kappa satisfying n≥1024n \ge 1024 and κ≥1024(1+log⁡n)\kappa \ge 1024(1 + \log n). We suppliment the proof for the crossover range in Appendix D.1.3, and modified the discussions accordingly.

Q2. In the κ≤n\kappa\le n regime of Theorem 4.2, could the initialization lower bound be established in expectation under RR using a single fixed instance in fixed or polynomial dimension?

  • Our construction involves assigning a separate coordinate to each possible set of component indices appearing in the first half of the final epoch, requiring (n⌊n/2⌋)\binom{n}{\lfloor n/2\rfloor} coordinates and thus exponential dimension. With this proof idea, we do not see a straightforward way to avoid exponential dimension, even if the guarantee is only required to hold in expectation under RR. In fact, our original aim was to establish a lower bound in expectation under RR. We later realized that the same construction also provides a lower bound for every permutation sequence, and stated this stronger guarantee in the paper.
  • However, a different proof idea may still yield a simpler lower-bound construction in fixed or polynomial dimension. We leave this as an open problem.

Q3. Could the initialization threshold or the large-epoch rate reflect the degree of nonconvexity of the components, for example, when each fif_i is τi\tau_i-weakly convex? In particular, how would this affect the additional κ/n\kappa/n factor when κ≳n\kappa \gtrsim n?

  • Our current lower-bound constructions use negative curvature of order LL, as permitted by the smoothness assumption. We did not explicitly parameterize our results by the degree of component nonconvexity.
  • In the nonconvex component lower bound construction for Theorem A.8, one coordinate accounts for the factor-κ/n\kappa/n slowdown relative to the convex-component case when κ≳n\kappa \gtrsim n. Along this coordinate, half of the components have curvature L/2L/2, and the other half have curvature 2μ−L/22\mu-L/2. Thus, the weak-convexity parameter in the construction is τ=L/2−2μ\tau=L/2-2\mu, which is of order LL.
  • For τ≤L/2−2μ\tau \leq L/2 - 2\mu, if we replace these curvatures by 2μ+τ2\mu+\tau and −τ-\tau, respectively, the components satisfy the τ\tau-weak convexity condition suggested by the reviewer. Note that the 2μ2\mu term ensures that the average objective has curvature μ\mu along this coordinate. Combining this modification with the remaining parts of the proof of Theorem A.8 gives the lower bound \Omega\\!\left(\frac{LG_{\ast}^2}{\mu^3 nK^2}\max\\!\left\\{1,\frac{\kappa}{n}\left(\frac{\mu+\tau}{L}\right)^2\right\\}\right), which is at least as large as the corresponding bound for convex components in Theorem 3.2.
  • In the regime κ≳n\kappa \gtrsim n highlighted by the reviewer, the factor max⁡1,κ/n\max\\{1, \kappa/n\\} thus becomes \max\left\\{1, \frac{\kappa}{n}\left(\frac{\mu+\tau}{L}\right)^2\right\\}. Consequently, when τ≫μLn\tau \gg \sqrt{\mu L n}, the construction exhibits an additional slowdown due to component nonconvexity.
  • Regarding the initialization threshold, given n≥1024n \geq 1024 and τ/μ≥1024(1+log⁡n)\tau/\mu \geq 1024(1 + \log n), the current Theorem 4.2 applied for L:=τL:=\tau gives an Ω(D2)\Omega(D^2) lower bound for K≲max⁡τμ,τ2μ2nK\lesssim \max\\{\frac{\tau}{\mu}, \frac{\tau^2}{\mu^2n}\\}. Together with the convex component case Ω(D2)\Omega(D^2) lower bound for K≲κnK\lesssim \frac{\kappa}{n}, this gives the initialization threshold of K≲max⁡κn,τμ,τ2μ2nK\lesssim \max\\{\frac{\kappa}{n}, \frac{\tau}{\mu}, \frac{\tau^2}{\mu^2n}\\}.

We hope our response clarifies these points and our perspective on the suggested directions. We would be happy to provide further details or discuss any additional questions.

Thank you for the response, which addresses most of my concerns. I keep my rating 3.

Reviewer_BDb5OpenReview ↗
Rating
3
Confidence
3
Informativeness
2
Presentation
3
Soundness
3
Read review
Paper summary

The paper characterizes the worst-case expected last-iterate convergence of constant-stepsize random reshuffling for smooth finite sums with a strongly convex average. With convex components, it establishes matching rates up to logarithmic factors and a transition near K≍κK\asymp\kappa, beyond which RR improves upon the corresponding SGD benchmark. Without component convexity, it identifies a longer initialization-error regime and an additional large-epoch factor max⁡{1,κ/n}\max\{1,\kappa/n\}. The authors prove convergence rates for RR and construct difficult examples showing that these rates cannot generally be improved, except for logarithmic factors. They also compare RR and SGD under the same assumptions and with the same number of gradient evaluations.

Critical strengths
  1. By giving upper and lower bounds with explicit dependence on the number of components nn, epoch count KK, and condition number κ\kappa, the paper explains when RR gains a worst-case advantage over SGD. With convex components, Theorem 3.2 identifies a transition near K≍κK\asymp\kappa: outside the initialization-dominated regime, RR matches SGD below this threshold and improves upon its rate by a factor of K/κK/\kappa above it, up to logarithmic factors. This connects the benefit of reshuffling to both the optimization budget and the conditioning of the problem. Within the analyzed parameter regimes, Theorems 4.1 and 4.2 identify two costs of dropping component convexity: initialization error can persist up to the epoch scale max⁡{κ,κ2/n}\max\lbrace \kappa,\kappa^2/n\rbrace, and the eventual RR error increases by a factor of max⁡{1,κ/n}\max\lbrace1,\kappa/n\rbrace relative to the convex-component rate, up to logarithmic factors. Thus, when nn is sufficiently larger than κ\kappa, the eventual rate is unchanged although the initialization regime can be longer; when κ\kappa is sufficiently larger than nn, the eventual rate also worsens. Together, these results explain when reshuffling can improve the worst-case guarantee and distinguish the effects of component nonconvexity on early progress and eventual convergence.

  2. The lower-bound constructions show that the slow behavior identified in the analysis can actually occur. For a fixed epoch budget in the regimes analyzed in Appendix D.1, the authors construct a single objective and starting point for which a constant fraction of the initial squared-distance error remains, regardless of the constant stepsize or sequence of component orders. The difficulty therefore persists even with a favorable ordering, making the result stronger than a lower bound based on an unlucky shuffle. For the large-epoch result in Theorem 4.1, a separate construction uses components with positive and negative curvature whose average remains strongly convex. Because gradients are evaluated at changing iterates, these components create a systematic drift that does not cancel when averaged over random permutations. The authors quantify this drift and combine it with other lower-bound constructions to establish the additional error caused by dropping component convexity. Together, these examples explain both the persistence of initialization error and the possible deterioration of the eventual rate, providing strong support for the claimed worst-case limits of constant-stepsize RR.

Critical weaknesses

None. My questions below concern minor clarifications of the theorem statements and their parameter ranges.

Questions for authors
  1. Could you clarify the exact epoch range covered by Theorem 3.2 and Theorem A.3, especially when n≫κn\gg\kappa? Both statements use K≳κ/nK\gtrsim\kappa/n, while the proof in Appendix C.2 (page 24, lines 1259 to 1262) requires

    K≥2ΛnKandnK≥16κΛnK.K\ge2\Lambda_{nK}\qquad\text{and}\qquad nK\ge16\kappa\Lambda_{nK}.

    The first condition concerns the number of epochs, while the second concerns the total number of gradient evaluations. When nn is large, satisfying the second condition does not automatically satisfy the first. Appendix C.2 explains that the convention also includes K≳1K\gtrsim1, but the associated logarithmic epoch requirement is less clear in the main statement.

    Does the claimed upper bound also hold for one or a few epochs when the total-update requirement is met but K<2ΛnKK<2\Lambda_{nK}? If so, could you indicate the argument covering that case? Otherwise, could the theorem explicitly state the sufficient condition

    K≥ΛnKmax⁡{2,16κ/n},K\ge\Lambda_{nK}\max\{2,16\kappa/n\},

    and clarify that the guarantee is subject to this additional logarithmic restriction on the epoch count?

  2. Could you clarify how Theorem 4.2 should be interpreted in the crossover range n<κ<1024nlog⁡2nn<\kappa<1024n\log_2 n, which Appendix D.1 (page 33) explicitly leaves outside its direct constructions? Since the theorem gives the initialization lower-bound threshold H=max⁡{κ,κ2/n}H=\max\{\kappa,\kappa^2/n\} up to logarithmic factors, could this range be covered by reusing the κ≤n\kappa\le n construction with a smaller smoothness parameter?

    Keeping μ\mu fixed, consider

    Leff=μn≤L,κeff=Leff/μ=n.L_{\mathrm{eff}}=\mu n\le L,\qquad \kappa_{\mathrm{eff}}=L_{\mathrm{eff}}/\mu=n.

    The resulting components would still be LL-smooth, because Leff≤LL_{\mathrm{eff}}\le L. Subject to the other conditions of the construction, applying the κ≤n\kappa\le n argument at κeff=n\kappa_{\mathrm{eff}}=n appears to give, for each prescribed epoch budget in the following range, a hard instance retaining a constant fraction of D2D^2:

    1≤K≤n1024(1+log⁡n).1\le K\le\frac{n}{1024(1+\log n)}.

    In the crossover range, H=κ2/n<10242n(log⁡2n)2H=\kappa^2/n<1024^2n(\log_2 n)^2, so the difference between this sufficient horizon and HH is at most an O((log⁡n)3)O((\log n)^3) factor, with numerical constants suppressed. This seems consistent with the logarithmic precision of the theorem.

    Is this argument valid while preserving the prescribed DD and G∗G_* and using a single objective and initialization for the prescribed horizon, independent of the chosen constant stepsize and permutation sequence? If so, could you include this extension and distinguish coverage of the crossover up to logarithmic factors from the remaining question of obtaining sharper constants or logarithmic dependence? If not, which assumption prevents the extension, and how should the parameter range of Theorem 4.2 be qualified?

1 comment

We thank the reviewer for the careful reading and constructive suggestions. Below we address the reviewer's two questions.

Q1. Could you clarify the epoch range of Theorems 3.2 and A.3, particularly when n≫κn\gg\kappa: does the upper bound hold when nK≥16κΛnKnK\ge16\kappa\Lambda_{nK} but K<2ΛnKK<2\Lambda_{nK}, or should the theorem statements explicitly include the additional logarithmic requirement on the epoch count?

  • Thank you for pointing out this ambiguity. As you noted, the upper bounds in Theorems 3.2 and A.3 are established under the sufficient conditions K≥2ΛnKK\ge2\Lambda_{nK} and nK≥16κΛnKnK\ge16\kappa\Lambda_{nK}. In our initial submission, because our notation ≳\gtrsim suppresses constant and polylogarithmic factors, we thought that the logarithmic epoch requirement could be left implicit and summarized the two conditions as K≳κ/nK \gtrsim \kappa/n. However, after your question, we carefully reconsidered this and realized that it is more accurate to write the condition as K≳max⁡1,κ/nK \gtrsim \max \\{1, \kappa/n\\}.
  • More specifically, if n≫κn \gg \kappa, the condition nK≥16κΛnKnK \ge 16 \kappa \Lambda_{nK} is weaker than K≥2ΛnKK \ge 2\Lambda_{nK}. Therefore, the sufficient condition for our upper bound reduces to K≥2ΛnKK \ge 2\Lambda_{nK}, and our guarantee does not cover epoch counts below this threshold. However, this gap is confined to a polylogarithmic epoch regime and does not affect our main scaling results, which are stated up to constant and polylogarithmic factors.
  • We have revised the conditions in Theorems 3.2 and A.3 from K≳κ/nK\gtrsim\kappa/n to K≳max⁡1,κ/nK\gtrsim\max\\{1,\kappa/n\\} and updated the accompanying discussion accordingly. (We refer the discussion below Theorem 3.2).

Q2. How should Theorem 4.2 be interpreted in the crossover range n<κ<1024nlog⁡2nn<\kappa< 1024 n\log_2 n? Could this range be covered by adjusting the smoothness parameter in the construction for κ≤n\kappa \leq n? If so, could you include this argument in the paper?

  • As noted in the paper, the two constructions in the submitted proof of Theorem 4.2 leave a gap in the crossover range, and do not provide any guarantee in this regime. Following the reviewer's suggestion, we can now fill this gap by keeping μ\mu fixed and setting Leff=μnL_{\mathrm{eff}}=\mu n. This gives κeff=n\kappa_{\mathrm{eff}}=n, allowing us to apply the construction in Appendix D.1.2. With this adjustment, the previously uncovered crossover range between κ\kappa and nn is reflected as a logarithmic drawback absorbed into the notation K≲max⁡κ,κ2/nK\lesssim\max\\{\kappa,\kappa^2/n\\}.
  • We have added Appendix D.1.3 to extend the existing construction to cover the previously omitted crossover regime n<κ<1024nlog⁡2nn<\kappa< 1024 n\log_2 n. Our Theorem 4.2 now applies to all nn and κ\kappa satisfying n≥1024n \ge 1024 and κ≥1024(1+log⁡n)\kappa \ge 1024(1 + \log n). We thank the reviewer for providing this constructive feedback.
  • This modification preserves the prescribed DD and G∗G_*. For given κ\kappa, nn, and KK, the construction yields a single objective and initialization for which the lower bound holds simultaneously for every constant stepsize and epoch permutations.

We hope these clarifications and revisions address your concerns. We would be happy to clarify any remaining points or answer further questions.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.