Revisiting Convergence: A Study on Shuffling-Type Gradient Methods

Authors: Qi He, Peiran Yu, Ziyi Chen, Heng Huang
Primary area: optimization
Keywords: shuffling-type gradient methods, convergence analysis, relaxed smoothness assumptions

Abstract:
Shuffling-type gradient methods are favored in practice for their simplicity and rapid empirical performance. Despite extensive development of convergence guarantees under various assumptions in recent years, most require the Lipschitz smoothness condition, which is often not met in common machine learning models. We highlight this issue with specific counterexamples. To address this gap, we revisit the convergence rates of shuffling-type gradient methods without assuming Lipschitz smoothness. Using our stepsize strategy, the shuffling-type gradient algorithm not only converges under weaker assumptions but also match the current best-known convergence rates, thereby broadening its applicability. We prove the convergence rates for nonconvex, strongly convex, and non-strongly convex cases, each under both random reshuffling and arbitrary shuffling schemes, under a general bounded variance condition. Numerical experiments further validate the performance of our shuffling-type gradient algorithm, underscoring its practical efficacy.

Decision: reject
Reviewer scores: 8, 5, 5, 5

Reviews and discussion:
<thread>
creation date:
1730153137637

thread_type:
official_review

<thread_object>
creator: reviewer_ryk7

<content>
summary:
This paper examines the convergence rate of shuffling-type gradient methods without assuming Lipschitz smoothness, achieving results that match the current best-known convergence rates. The theoretical analysis covers non-convex, strongly convex, and non-strongly convex cases under both random reshuffling and arbitrary shuffling schemes.

strengths:
1. The theoretical analysis is rigorous and considers multiple cases for different function properties.
2. The authors discuss the limitations of their work and suggest directions for future research.

weaknesses:
My main concern is the experimental section, which feels too limited and simple to fully support the theoretical findings.
1. The data used in the experiments is relatively simple. It would be valuable to see if this method remains effective on more complex datasets, such as image datasets or applications with large language models.
2. Additionally, since the theoretical analysis includes both random reshuffling and arbitrary shuffling, it would strengthen the paper to show results for both methods compared to the baseline SGD.
3. Similarly, since the analysis considers three different cases (non-convex, strongly convex, and non-strongly convex), conducting experiments separately under each case would add depth to the findings.

questions:
See the Weaknesses above.
</content>
</thread_object>

</thread>
<thread>
creation date:
1730559931333

thread_type:
official_review

<thread_object>
creator: reviewer_h6th

<content>
summary:
The paper considers shuffling-type gradient descent under more general smoothness assumption -- $L_0, L_1$-smoothness.

strengths:
Results match the standard Lipschitz smoothness rates

weaknesses:
Variance assumptions, which are stronger than the most standard bounded variance assumption

questions:
- Definition 2.2 seems missing subscript for $x$ in the right hand side. It is unclear what authors mean. It could be either symmetric (x is any of  $x_1$ or $x_2$) either non-symmetric $L_0, L_1$-smoothness (maximization over $x_1$ $x_2$ interval), see [1]. Or something different? Symmetric case is much easier to analyze. I tried to get it through the proofs, and it was very strange to see, that everywhere (e.g. Lemma A.2, Lemma A.4 ) authors used $\|\|\nabla F(\omega)\|\| \le G$, and then said (line 672) that "From definition 2.2, we can use Lipschitz smoothness". The standard smoothness AFAIU. So the question: Can the $G$ be huge? Is it just hidden to the $\cO$? and  is the analisys mainly like for the standard smoothness?
It seems to me that it actually is, because in lines 615, 704, 890, 1000, etc authors use standard smoothness inequalities. 
I simply can bound  $|\|\nabla f(x) \|\| = |\|\nabla f(x) - \nabla f(x^*) \|\| \ \le (L_0 + L_1|\|\nabla f(x^*) \|\|)R = RL_0$ which could be a G.
and then my effective smoothness is $L= L_0 + RL_0L_1$.
In the non-symmetric we have extra exponents as a multipliers, according to [1].
Is this what authors effectively did? Of course the one can recover the same rate as for standard smoothness. The problem is that the constant will be huge.

- what is $r := G/L$ in Theorem 4.5, Theorem 4.6, Lemma A.1, Lemma A.2.  I couldn't find where authors referr to $r$. What is it for? The results of the mentioned theorems and lemmas do not depend on $r$.
Then $r$ is appearing in Lemma A.4 and in bounds two subsequent trajectory points difference norm. Which mainly coincides  with my above bound on the gradient (if we plug in the step).

I briefly check the proofs and it seems they are to adapting my above bound on the gradient norm to the stochastic case (which is where the weaker variance assumption is used -- no expectation, and the difference between the full gradient and its stochastic counterpart is estimated).

However, the correct approach is to allow the step size to increase as the gradient norm approaches zero. E.g [1] suggests clipping with gradient norm in the denominator -- when the norm is large - the stepsize is small and vice-versa.

If I was mistaken, I would be glad to investigate the proofs more carefully if authors argued that I was wrong. My understating is that gradient norm is just trivially bounded and the contribution is poor.

References:
[1] Z. Chen et al. 2023 Generalized-Smooth Nonconvex Optimization is As Efficient As Smooth Nonconvex Optimization
</content>
</thread_object>

</thread>
<thread>
creation date:
1730675399968

thread_type:
official_review

<thread_object>
creator: reviewer_uhrc

<content>
summary:
This paper studies the shuffling method under the generalized smooth assumption, which was proposed recently to fit many modern machine learning tasks. The authors proved that, under properly picked parameters, the shuffling method provably converges under the weak smoothness condition for both nonconvex/strongly convex/convex objectives. Numerical experiments are also conducted to support the theory.

strengths:
I appreciate the paper tries to tackle more realistic problems (i.e., functions with non-uniform smoothness) and studies the shuffling algorithm, an arguably more common scheme in practice.

weaknesses:
**Major points**.

1. All convergence results are proved in a high-probability manner. However, the dependence on the margin $\delta$ is in the order of $\mathrm{poly}(1/\delta)$, which makes the results weak. I also suggest the authors explicitly give the dependence on $\delta$ in the final sample complexity.

2. Some descriptions of the existing works contain wrong facts. **(addressed)**

   - Lines 90-91, the bounded variance assumption is **not** required to improve the rate $\mathcal{O}(1/T^2)$ to $\mathcal{O}(1/(nT^2))$ in Nguyen et al. (2021). Instead, Nguyen et al. (2021) can handle **unbounded** variance.

   - Lines 92-93, results in both Mishchenko et al. (2020) and Nguyen et al. (2021) hold under **unbounded** variance condition. The current description is not correct.

3. The conditions on noises, i.e., Assumptions 4.3, 4.4, and 4.7, are strong compared with the existing literature, which significantly reduces the impact of the work. I will elaborate more on this point in the following.


4. Nonconvex part. **(addressed)**

   - Random reshuffling scheme.

     - In this case, previous works only consider Assumption 4.7, or even a weaker version, i.e., the non-uniformly bounded variance, to obtain the $\mathcal{O}(\sqrt{n}/\epsilon^{3})$ sample complexity.

     - However, to recover the same rate, this work requires much stronger Assumptions 4.3 and 4.4 in Theorems 4.5 and 4.6, respectively. Hence, the results in this paper are not directly comparable to prior literature.

     - When only Assumption 4.7 holds, Corollary 4.8 has extra dependence on $n$ as indicated by the authors.

     - In addition, I am not sure why Corollary 4.8 is a corollary and cannot find its proof. Did I miss anything?

   -  Arbitrary shuffling scheme.

      - Again, the authors require stronger Assumption 4.3 to make their sample complexity as good as the previous results. However, the latter can hold under non-uniformly smoothness, e.g., see Nguyen et al. (2021). As such, the claim in Lines 63-64 is misleading.

   - Moreover, imposing three assumptions on noises may confuse the reader. Especially, the proofs under Assumptions 4.3 and 4.4 are similar as claimed in Lines 860-863. I didn't see a necessary reason for the authors to do so.

4. Strongly convex and convex parts. 

   - Assumption 4.3 is strong and not assumed in previous best-known results, making the contributions weak. **(addressed)**

   - As far as I know, the previous best results don't need any assumption on the noises for convex problems (Assumption 4.14). Hence, whichever condition among Assumptions 4.3, 4.4, and 4.7 is used, the result is not an improvement in my opinion.

5. The writing can be improved. Some theorems give a threshold on the stepsize (e.g., Theorem 4.5) but others give an exact choice (e.g., Theorem 4.12). Can the author present a unified statement? **(addressed)**

**Minor points**. **(addressed)**

1. Line 290, the second $T=\mathcal{O}(\frac{1}{\epsilon^3})$ should be $\mathcal{O}(\frac{n}{\epsilon^3})$.

2. Line 310, $Delta_1$ should be $\Delta_1$.

questions:
See **Weaknesses**.
</content>
</thread_object>

</thread>
<thread>
creation date:
1730678178522

thread_type:
official_review

<thread_object>
creator: reviewer_9cy6

<content>
summary:
This paper revisits the case of random shuffling-type stochastic gradient methods for finite sum minimization problems. More precisely, the paper considers objectives without  the traditional structural assumption of Lipschitz smoothness. In doing so, the authors focus on non-convex, strongly convex and convex objectives which satisfy as a smoothness "surrogate" the notion of $\mathcal{l}-$ smoothness.
To that end, the authors provide respective convergence rates for each respective case.

strengths:
The paper is extremely well written and enjoyable to read. Moreover, as far I checked the math seems correct and sound. Without being an expert myself on the respective literature, I find the respective very interesting and challenging from a theoretical standpoint.

weaknesses:
My main concerns consider two main factors:

First, the notion of $\mathcal{l}-$ smoothness introduces additional parameters to be tuned as it becomes apparent from the definitions of the step-sizes in the main theorems. It would be could to include some discussion of how difficult are these to be evaluated both  in real life scenarios and in theory. More precisely, do the authors believe that the respective toolbox from the adaptive  algorithm like in [1] can be incorporated?

Secondly, the proposed step-size policies seem to rely on a prior knowledge on the iteration horizon $T$. Do the authors believe that an any time convergence rate guarantee can be achieved? 


[1] Adaptive Stochastic Variance Reduction for Non-convex Finite-Sum Minimization, Neurips 2022.

questions:
See weaknesses
</content>
</thread_object>

</thread>
<thread>
creation date:
1732150202615

thread_type:
official_comment

<thread_object>
creator: authors

<content>
title:
Update of draft

comment:
We have updated our paper in response to the reviewers' valuable suggestions. Below is a summary of the key changes we have made:

- We are now using a weaker noise assumption (Assumption 4.3), aligning with [1]. All the theorems and proofs have been modified accordingly.
- The flow of the proofs in the appendix has been reorganized to improve readability.
- Typos have been corrected.

We also plan to work on numerical experiments soon, as suggested by reviewer RYK7.

[1] Nguyen, Lam M., et al. "A unified convergence analysis for shuffling-type gradient methods." *Journal of Machine Learning Research*, 22.207 (2021): 1-44.
</content>
</thread_object>

</thread>
<thread>
creation date:
1732855629122

thread_type:
official_comment

<thread_object>
creator: authors

<content>
comment:
We sincerely thank the reviewers for their constructive feedback, which has greatly contributed to improving our manuscript. As the revision has reached a temporary conclusion, we would like to summarize the changes we have made:

1. **Weaker assumptions**: We now use a weaker assumption of general bounded variance, aligning it with the assumption made under Lipschitz smoothness.
2. **Expanded analysis**: We have extended our analysis to cover both strongly convex and non-strongly convex cases without any variance assumptions.
3. **Additional experiments**: We conducted more numerical experiments, including:
   - All three shuffling schemes,
   - Both strongly convex and non-strongly convex cases,
   - Image datasets.

We believe that currently we have addressed all the concerns raised by the reviewers. We look forward to further responses and suggestions to continue refining and improving the manuscript. Thank you again to all the reviewers for their invaluable feedback.
</content>
</thread_object>

</thread>


Metareview:
metareview:
This paper studies the convergence guarantees of shuffling based gradient methods in non-Lipshitz settings. Authors show that, this algorithm with a careful schedule converges under weak assumptions. Authors consider various settings, e.g. nonconvex, convex, assuming bounded variance. They further provide empirical studies for demonstration.


This paper was reviewed by four reviewers and received the following Scores/Confidence: 5/4, 5/4, 5/3, 8/2. I think the paper is studying an interesting topic but authors are not able to convince the majority of the reviewers sufficiently well about the importance of their contributions. The following concerns were brought up by the reviewers:
  
- There were many concerns raised by the reviewers and I appreciate that the authors provided a major revision of their work. However, given the number of points raised, addressing all reviewer concerns would require significant revision, which then requires another set of reviews.

- Novelty of technical analysis.
  
- Experimental results are limited and do not sufficiently support main claims.

- Convergence guarantees have a weak dependence on the margin.


Three out of four reviewers rejects the paper. As such, based on the reviewers' suggestion, as well as my own assessment of the paper, I recommend not including this paper to the ICLR 2025 program.