Revisiting Convergence: Shuffling Complexity Beyond Lipschitz Smoothness

We thank the reviewer for acknowledging our contribution and careful attention to details. We will make modifications as suggested by the reviewer.

Thanks for the careful reading and constructive feedback. Below we respond to each point in detail:

Assumption 4.3: Since component gradients behave as gradient estimations of the full gradient, this assumption can be viewed as a generalization of the more common assumption $\mathbb{E}[\|\nabla F(w;\xi)-\nabla F(w)\|]\leq \sigma^2$, which is used in most $\ell$-smooth work, e.g., [1], [2].

W1: We want to mention that another key novelty is our analysis for the condition $t<\tau$, where each step's analysis must account simultaneously for both the event $t<\tau$ and the preceding steps within the same epoch due to shuffling. This dual conditioning has not been addressed by prior work that focuses only on either shuffling or $\ell$-smoothness. Additionally, assumption 4.3 is relaxed compared to other $\ell$-smooth literature.

W2: Achieving a logarithmic dependency on $1/\delta$ remains an open challenge under $\ell$-smoothness, and establishing such a result would constitute a significant advancement. As noted in Remark 4.5, most existing works under $\ell$-smooth assumptions exhibit polynomial dependencies on $1/\delta$. Intuitively, under $\ell$-smoothness, the parameter $\delta$ accounts for bad cases from both variance and smoothness, whereas $L$-smooth scenarios only considers the former. Thus, significantly improving this dependency is nontrivial and would require substantial theoretical breakthroughs.

W3: We agree that the experiments can better support our theory following the advice in 'claim and evidence' section. However, it can be hard to implement in reality, since the function $\ell$ and constant $p$ are hard to determine. We leave it as a future work to design a better algorithm to work in practice.

W4: We agree with that. As we mentioned in Section 4.3, the potentially large constant $G'$ in Theorems 4.9 and 4.12 is indeed undesirable. These theorems are intended as initial steps toward a broader analysis without any variance assumptions.

Q1: These counterexamples generally do not necessarily satisfy the $(L_0,L_1)$-smoothness conditions. One motivation to move from $(L_0,L_1)$-smoothness to generalized $\ell$-smoothness is to cover functions such as double exponential functions $f(x)=a^{b^x}$ or rational functions $f(x)=P(x)/Q(x)$, where $P$ and $Q$ are polynomials, which satisfy $(L_0,L_1)$-smoothness conditions but not $\ell$-smooth.

Q2: Yes, we can use the theoretical results and give diminishing stepsizes. As suggested in theorem 4.4, as long as the stepsizes satisfy the constraints, they can be either constant or diminishing.

[1] Li, Haochuan, Alexander Rakhlin, and Ali Jadbabaie. "Convergence of adam under relaxed assumptions." Advances in Neural Information Processing Systems 36 (2023): 52166-52196.

[2] Xian, Wenhan, Ziyi Chen, and Heng Huang. "Delving into the convergence of generalized smooth minimax optimization." Forty-first International Conference on Machine Learning. 2024.

Thank you very much for your detailed and helpful comments. Please find our responses below:

W1: We appreciate your perspective but respectfully disagree that the paper is merely combining existing results. As we emphasize in Section 4.2, the main technical challenge arises specifically from analyzing the case when $t<\tau$. Each step in our analysis is conditioned not only on the event $t<\tau$ but also on all previous steps within the same epoch, due to the shuffling method. This dual conditioning has not been addressed by prior work that focuses only on either shuffling or $\ell$-smoothness. Additionally, our results hold under the relaxed gradient assumption (Assumption 4.3), and even without it, thereby broadening their scope compared to existing $\ell$-smooth literature. We hope the reviewer can reconsider the novelty of our contribution in this context. Moreover, even if the novelty aspect were debated, considering the popularity of shuffling algorithms and restrictive nature of Lipschitz smoothness assumptions, our contributions extend theoretical guarantees to a broader class of problems. Thus, we respectfully suggest that novelty alone should not be considered a decisive reason for rejection.

W2: We agree and will explicitly add the additional parameters for completeness. Thank you for this suggestion.

Q1: Thanks for bringing up this important point. We apologize for any confusion caused. Indeed, complexities in Theorems 4.9 and 4.12 should not be directly compared to those in Theorems 4.8 and 4.11 due to the potentially large constant $G'$, which implicitly depends on $p$, as discussed in Section 4.3. The results in 4.9 and 4.12 are meant to be initial analyses for scenarios without the variance assumption. For completeness, if we did apply variance Assumption 4.3 and follow proof in Theorem 4.6, we could derive corresponding complexities of $\mathcal{O}(n^{\frac{p}{2}+1}\epsilon^{-\frac{1}{2}})$ and $\mathcal{O}(n^{\frac{p}{2}+1}\epsilon^{-\frac{3}{2}})$ for strongly convex and non-strongly convex cases respectively, with arbitrary shuffling scheme.

Q2: Thank you for catching this typo. You are correct—the proper step size should be $\eta_t=\frac{6\log(T)}{\mu T}$. The learning rate currently listed in the draft mistakenly corresponds to the inner-loop step size. We appreciate your attention to details.

Thanks for the careful reading and constructive feedback. Below we respond to each point in detail:

Q1: Achieving a logarithmic dependency on $1/\delta$ remains an open challenge under $\ell$-smoothness, and establishing such a result would constitute a significant advancement. As noted in Remark 4.5, most existing works under $\ell$-smooth assumptions exhibit polynomial dependencies on $1/\delta$. The only exception is in Theorem 4.1 of [1], where independence between steps allows for a log dependence; however, they turn to polynomial dependence in Theorem 6.2 a few pages later, after the independence is lost. That means no log complexity has been achieved with dependence between steps and $\ell$-smoothness. Intuitively, under $\ell$-smoothness, the parameter $\delta$ accounts for bad cases from both variance and smoothness, whereas $L$-smooth scenarios only considers the former. Thus, significantly improving this dependency is nontrivial and would require substantial theoretical breakthroughs. We respectfully ask the reviewer to reconsider whether this aspect should be regarded as a major weakness, given the current state-of-the-art under similar assumptions.

Q2: Thanks for highlighting this, we apologize for the confusion. The complexity bounds in Theorems 4.9 and 4.12 should not be directly compared to those in Theorems 4.8 and 4.11. The constant $G'$ in Theorems 4.9 and 4.12 can potentially be very large (as we mention in Section 4.3) and is implicitly influenced by $p$ through $G'$. These results serve as initial steps toward analyzing cases with no variance assumptions whatsoever. For completeness, if we were to adopt the variance Assumption 4.3 (similar to Theorem 4.6), we could derive results following proof of Theorems 4.6, yielding total gradient evaluation complexities of $\mathcal{O}(n^{\frac{p}{2}+1}\epsilon^{-\frac{1}{2}})$ and $\mathcal{O}(n^{\frac{p}{2}+1}\epsilon^{-\frac{3}{2}})$ for strongly convex and non-strongly convex cases with arbitrary scheme, respectively.

Q3: To clarify the dependency of $T$ on $\delta$: note first that we have $H=\mathcal{O}(\delta^{-1})$, which implies $G=\mathcal{O}(\delta^{-\frac{1}{2-p}})$ and consequently $L=\mathcal{O}(\delta^{-\frac{p}{2-p}})$. Combining these with the constraints $\eta^3 T \leq \mathcal{O}(L^{-2})$ and $T \geq \frac{32\Delta_1}{\eta\delta\epsilon^2}$ gives the specified polynomial dependencies. Sorry for the confusion here, we will clarify this reasoning further in the appendix of a revision.

Q4: Not really. The parameter $p$ is implicitly included within $L$ as we have $L=\mathcal{O}(n^{\frac{p}{2}})$.

W3: Thanks for catching the missing assumption here, and $G'$ is finite indeed, but we need to add a short proof for that. We will add these in revision.

W4: Sorry for the confusion from the wording. By "smooth along the training trajectory," we meant that smoothness conditions hold between consecutive points during training, not necessarily globally across the entire trajectory. We recognize this wording was imprecise and will clarify this point explicitly to avoid misunderstandings.

We greatly appreciate the reviewer’s insights and suggestions, which have significantly improved the clarity of our manuscript.

[1] Li, H., Rakhlin, A., Jadbabaie, A. (2023). Convergence of adam under relaxed assumptions.