Revisiting Convergence: A Study on Shuffling-Type Gradient Methods

We thank the reviewer for their valuable comments.

We have updated the experimental section to include both strongly convex and non-strongly convex cases, as well as results for all three shuffling schemes. These updates can be viewed in the revised PDF. Additionally, we are currently working on experiments with image datasets and will include them in future updates.

We thank the reviewer for their constructive feedback. In response, we have completed experiments on the CIFAR-10 image dataset; covered all three shuffling schemes; as well as strongly convex, non-strongly convex, and nonconvex cases. Please refer to our revised manuscript for detailed results and analysis.

Thanks for the response. While we appreciate the thoroughness of the review process, we are disappointed by the conclusion that the score should be maintained. We believe our experiments have addressed all the concerns you mentioned. If they resolve your concerns, we kindly ask for a reconsideration of the rating. If any additional issues remain, please let us know and we would be happy to provide further clarifications.

We thank the reviewer for the comments. Below we will try to address the concerns and questions of the reviewer.

For the Weakness:

We have updated the conclusions to rely on weaker assumptions. Please refer to the updated version of the paper.

For the Questions:

• Definition 2.2 Missing Subscript for $x$:
  We apologize for the lack of clarity. What we meant is that for any $x$ in the domain and any $x_1, x_2$ close enough to $x$, the property should hold. Specifically, we should have included "$\forall x \in \text{dom}(f)$" in the definition. However, the $x$ on the right-hand side does not need a subscript. Definition 2.2 is therefore distinct from both symmetric and asymmetric generalized smoothness definitions in [1]. We have updated the definition accordingly.

• Use of $\|\nabla F(w)\| \leq G$ in Lemmas A.2 and A.4:
  In Definition 2.2, if $\|\nabla f(x)\|$ is bounded above, we recover standard Lipschitz smoothness for any pair of points close enough to $x$. The statement on line 672 is justified by the following:

  1. From the induction hypothesis, $w^{(t)}_{k-1}$ is close enough to $w^{(t)}_0$.
  2. The term $\|\nabla F(w^{(t)}_0)\|$ is bounded due to the definition of $\tau$ and Lemma A.3.

• Can $G$ Be Large, and Is It Hidden in $O$?
  According to Theorem 4.4, $G = O\left(\left(\frac{4\Delta_1}{\delta}\right)^{\frac{1}{2-p}}\right)$, where $0 \leq p < 2$ is the degree of the $\ell$ function. It is possible for $G$ to be quite large, which is reasonable given the relatively loose assumption on the gradient. In some cases, the gradient can indeed be very large, but it is polynomial in $\Delta_1$ and $1/\delta$. The term $G$ is hidden in the $O$ notation because it is independent of $n$ and $\epsilon$.

• Bounding $\|\nabla f(x)\|$:
  We cannot directly bound $\|\nabla f(x)\| = \|\nabla f(x) - \nabla f(x^*)\| \leq (L_0 + L_1 \|\nabla f(x^*)\|)R = RL_0$ because, in Definition 2.2, the points $x_1, x_2$ need to be close enough to $x$. There is no guarantee that $x$ is close to $x^*$ here. Additionally, we do not make an assumption such as $\|x - x^*\| \leq R$.

• Similarity to Standard Smoothness Analysis:
  Our analysis is not equivalent to standard smoothness analysis. The key differences are as follows:

  1. We do not always assume standard smoothness. Since we do not have a bound for $\|\nabla f(w;i)\|$, it is not possible to give an upper bound for $\|\nabla F(w)\|$ along the trajectory. Instead, we use $G$ that controls the probability of the gradient norm exceeding $G$.
  2. To apply standard smoothness properties, we condition all results on the event $t < \tau$, where $\tau$ is the time when the gradient norm exceeds $G$. Under this conditioning, many results from standard smoothness cannot be directly applied.

• Redundant Notation $r$:
  The variable $r$ was used to simplify notation but is now redundant. We have removed $r$ from the draft. Thank you for pointing this out.

Since the reviewer referred to [1] multiple times, we would like to provide a comparison between [1] and our work.

Our definition of $\ell$-smoothness is derived from Definition 2 in [2], and it is equivalent to the condition $\|\nabla^2 f(x)\| \leq \ell(\|\nabla f(x)\|)$ almost everywhere, where $\ell$ is a sub-quadratic, non-decreasing function. The generalized smoothness in [1] can be viewed as a special case of $\ell$-smoothness with $\ell(x) = L_0 + L_1 x^\alpha$ for $\alpha \in [0, 1]$.

In terms of proof techniques, [1] uses normalization to handle potentially large gradients, whereas our approach allows for large gradients but ensures that they occur only with a small probability $\delta/2$. We further demonstrate that the gradient norm bound $G$ is not excessively large, as it is independent of $\epsilon$ or $n$ in the nonconvex case. Consequently, the challenges addressed in our work are significantly different from those in [1].

References:

[1] Chen, Z., Zhou, Y., Liang, Y., and Lu, Z. (2023). Generalized-smooth nonconvex optimization is as efficient as smooth nonconvex optimization. In International Conference on Machine Learning (pp. 5396-5427).

[2] H. Li, J. Qian, Y. Tian, A. Rakhlin, and A. Jadbabaie. Convex and non-convex optimization under generalized smoothness. In Thirty-seventh Conference on Neural Information Processing Systems, 2023a.

We thank the reviewer for the comments. Below we will try to address the concerns and questions of the reviewer.

• Additional Parameters Introduced by $\ell$-Smoothness:
  Since the $\ell$ function and the value of $\sigma$ are difficult to obtain in practice, the results in our paper may not provide optimal guidance for choosing hyperparameters. However, the primary contribution of this work lies in providing convergence guarantees under weaker smoothness assumptions.

• Incorporating Adaptive Algorithms:
  Regarding the possibility of incorporating the respective toolbox from adaptive algorithms, there has been work on shuffling algorithms with variance reduction techniques, such as in [1]. Moreover, since variance reduction has been successfully combined with generalized smoothness in [2], we believe it is indeed feasible to integrate such techniques into shuffling algorithms. This represents a promising direction for future research.

• Step-Size Policies and Any-Time Convergence Guarantees:
  The proposed step-size policies rely on prior knowledge of the iteration horizon $T$. However, the step-size and $T$ can be determined simultaneously at the start of the algorithm, as demonstrated in our parameter choices under Theorem 4.4. Achieving an any-time bound is also possible but may not be very useful. By replacing the iteration horizon $T$ with the current iteration index $t$, the $1 - \delta$ probability and the bound for the average gradient norm (previously $\epsilon^2$) would adjust accordingly.

References:

[1] Malinovsky, Grigory, Alibek Sailanbayev, and Peter Richtárik. "Random reshuffling with variance reduction: New analysis and better rates." Uncertainty in Artificial Intelligence. PMLR, 2023.

[2] Li, Haochuan, Alexander Rakhlin, and Ali Jadbabaie. "Convergence of adam under relaxed assumptions." Advances in Neural Information Processing Systems 36 (2024).

We thank the reviewer for the comments. Below we will try to address the concerns and questions of the reviewer.

1. Noise Assumption:
   We have updated the noise assumption in the new draft to match the assumption in [1]. In the strongly convex case, the results now align with [1] under the same assumption, as outlined in the second paragraph of Theorem 1 in [1].

2. Dependence on $\delta$:
   We have explicitly added the dependence on $\delta$ in the remarks below Theorems 4.4, 4.8, and 4.11. However, we humbly disagree with the assertion that the polynomial dependence on $\delta$ is weak. Under the $\ell$-smoothness assumption, the dependence of $T$ on $\delta$ is commonly polynomial. For instance:

   • Theorem 6.2 in [2],
   • Theorem 5.3 in [3],
   • Theorem 4.13 in [4].

   This is because, under $\ell$-smoothness, $\delta$ accounts for the probability that Lipschitz smoothness does not hold—a consideration absent in standard Lipschitz smoothness settings. Therefore, it is not appropriate to directly compare the dependence on $\delta$ here with that in Lipschitz smoothness.

   Furthermore, there are results under $\ell$-smoothness with a $\log(1/\delta)$ dependency (e.g., Theorems 4.1 and 4.2 in [2]). However, in those cases, it is proved that the gradient norm is always bounded before $T$ in the probability space, which does not hold in our case. Improving the dependency to $\log(1/\delta)$ here would require a significant advancement in techniques under $\ell$-smoothness and is beyond the scope of this paper.

3. Descriptions of Existing Works:
   We have corrected inaccuracies in the descriptions of some existing works. Thank you for pointing these out.

4. Threshold vs. Exact Stepsize:
   Regarding the comment about stepsize thresholds (e.g., Theorem 4.5) versus exact choices (e.g., Theorem 4.12), we now provide explicit stepsize choices in the paragraphs following the relevant theorems. However, we have retained the threshold form in some cases as it provides a more accurate description of our results.

References:

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

[2] Haochuan Li, Alexander Rakhlin, Ali Jadbabaie. "Convergence of Adam Under Relaxed Assumptions." NeurIPS 2023.

[3] Haochuan Li, Jian Qian, Yi Tian, Alexander Rakhlin, Ali Jadbabaie. "Convex and Non-convex Optimization Under Generalized Smoothness." NeurIPS 2023.

[4] Wenhan Xian, Ziyi Chen, Heng Huang. "Delving into the Convergence of Generalized Smooth Minimax Optimization." ICML 2024.