Improved Last-Iterate Convergence of Shuffling Gradient Methods for Nonsmooth Convex Optimization

We appreciate the reviewer's positive feedback. We will answer the reviewer's question below.

Question. Thanks for the deep question. We will discuss it from the following two perspectives.

• As mentioned in our Subsection 1.2 (see Lines 122-142, right column), the lower bound in [1] can be read as $\Omega\left(\frac{1}{J^{1/4}n^{1/4}\sqrt{K}}+\frac{1}{\sqrt{nK}}\right)$ for the suffix average of the last $J$ epohs, i.e., $\frac{1}{Jn}\sum_{j=K-J}^{K-1}\sum_{i=1}^{n}\boldsymbol{x}_{jn+i+1}$. Therefore, for the average over all $K$ epochs, the lower bound is $\Omega\left(\frac{1}{n^{1/4}K^{3/4}}+\frac{1}{\sqrt{nK}}\right)$. In other words, the rate $\Omega\left(\frac{1}{n^{1/4}K^{3/4}}\right)$ for the average iterate could only be possible in the small epoch regime, i.e., $K\leq n$.

• To be honest, we have no idea whether this rate is tight. If it is indeed achievable, then it means that there exists at least one problem instance such that the average iterate can improve over the last iterate by a factor of $K^{-1/4}$, which is highly surprising and even seems impossible in our opinion since we have never seen an optimization method exibithing such a property if the stepsize is fine picked. As such, we suspect the lower bound for the average iterate should be improved.

References

[1] Koren, Tomer, et al. "Benign underfitting of stochastic gradient descent." Advances in Neural Information Processing Systems 35 (2022): 19605-19617.

We thank the reviewer for the endorsement of our work. We would like to address the reviewer's concerns below.

W1&Q2. To make the bounds for SS decrease to $0$, it indeed needs some other technique in addition to the analysis sketched in Section 5 (as mentioned at the end of the same section). In a high-level way, we need to utilize both the randomness and the deterministic property of SS, in which the former is described in Section 5 and the latter refers to that the index goes over the whole set $[n]$ in every epoch. These two key points are formalized in Lemmas B.2 and B.3, respectively. As such, proving SS converging to $0$ when $K\to \infty$ is possible once the conditions in Lemmas B.2 and B.3 are fulfilled. A special case is $\psi=I_\mathcal{C}$ used in Theorem 4.6, which further includes the situation $\psi\equiv 0$ (i.e., take $\mathcal{C}=\mathbb{R}^d$). For a more detailed discussion and some inadequate points of Lemma B.3, we kindly refer the reviewer to Lines 1427-1445.

W2&W3. Thanks for the suggestion. We will try to incorporate your comments in the revision when more space is available.

Q1. On Page 39 of the arXiv version of [1] (or Page 20 of the supplementary of the NeurIPS version), they obtained the rate in the order of $O\left(\eta G^2 (\sqrt{nK}+K)+\frac{D^2}{\eta nK}\right)$ where $\eta$ is the stepsize. Thus, the best $\eta =\Theta\left(\frac{D}{G\sqrt{(\sqrt{nK}+ K)nK}}\right)$ gives us the rate $O\left(GD\sqrt{\frac{\sqrt{nK}+K}{nK}}\right)=O\left(\frac{GD}{n^{1/4}K^{1/4}} \lor \frac{GD}{\sqrt{n}}\right)$, where we use $O(a+b)=O(a \lor b)$ for $a,b\geq 0$. Moreover, we believe the statement $K\geq n$ in their Theorem 6 in the main text is a typo and should be corrected to $K\leq n$ as used in their supplementary (see the page we mentioned at the beginning).

References

[1] Koren, Tomer, et al. "Benign underfitting of stochastic gradient descent." Advances in Neural Information Processing Systems 35 (2022): 19605-19617.

We thank the reviewer for the positive comments. We will answer the reviewer's questions below.

Q1. Our analysis is still inspired by and related to [1] but with some necessary changes to fit the shuffling method. However, whether the framework of [2] can be used to simplify the proof is unclear to us. We briefly explain why in the following.

• After a quick read, we think the core result of [2] is their Theorem 1, which relates the last-iterate convergence to the regret guarantee in online learning. As far as we can check, their Lemma 7 (the key to prove Theorem 1) relies on the fact that the gradient oracle $g_t$ is an unbiased estimator of $\nabla f(\boldsymbol{x}_t)$ conditioning on the history.

• In contrast, the gradient oracle in our setting is $g_t=\nabla f_{\textsf{i}(t)}(\boldsymbol{x}_t)$, which is unfortunately biased due to the shuffling-based index $\textsf{i}(t)$.

As such, their analysis immediately failed in our setting. Hence, how to make the idea in [2] work under the shuffling scheme remains unknown currently.

Q2. Indeed, the improvement (or deterioration) comes from both the analysis and the algorithmic change. Simply speaking, the current analysis that considers randomness naturally leads us to make the proximal update happen in every step. More precisely, if we want to utilize randomness in the analysis, it is natural to recognize every single step as an update (one can think about SGD as an example). Therefore, the difference between our algorithm and [3] arises since the latter's analysis is epoch-wise, which therefore requires the proximal update to happen at the end of every epoch.

• For RR, such a different view is enough to improve the convergence, as commented by the reviewer (also pointed out in our Section 5).

• But for SS, things become tricky. As shown by our results, the new view (and hence the variation in the algorithm) is enough to guarantee better rates in the small epoch regime, but is inadequate in the large epoch regime. It turns out that one critical point missed in the proof is the deterministic property of the shuffling method, i.e., the index in every epoch goes over the entire set $[n]$ (the key property used in [3]). Hence, we could expect a better result for SS if this fact is used in the analysis (as stated in the last paragraph in Section 5). However, this is not an easy task due to the algorithmic change, especially for a general $\psi$. But for some $\psi$ (including but not limited to $\psi=I_\mathcal{C}$ in Theorem 4.6), we still can make it work. For the most general case and more details, we kindly refer the reviewer to our Lemma B.3 and the discussion in Lines 1427-1445.

References

[1] Zamani, Moslem, and François Glineur. "Exact convergence rate of the last iterate in subgradient methods." arXiv preprint arXiv:2307.11134 (2023).

[2] Defazio, Aaron, et al. "Optimal linear decay learning rate schedules and further refinements." arXiv preprint arXiv:2310.07831 (2023).

[3] Liu, Zijian, and Zhengyuan Zhou. "On the Last-Iterate Convergence of Shuffling Gradient Methods." International Conference on Machine Learning. PMLR, 2024.

We thank the reviewer for the valuable feedback. We would like to answer the reviewer's questions below.

Typos&Suggestions. Thanks for carefully reading and the helpful comments. We have corrected/modified them accordingly.

Q1. Thanks for the interesting question. Honestly, we do not have too many insights on this phenomenon and don't want to provide a misleading explanation. We hope it can be fully understood in future research.

Q2. Yes, as stated in Theorem 5 of [1], the lower bound construction is for $G_i\equiv 4$. We also mentioned this point in Remark d under Table 1.

Q3. We note that $G_{f,2}\approx \sqrt{n}G_{f,1}$ is a very special case, but doesn't need to be worried about. Suppose we have $B$ gradient evaluation budgets, then the rate of every related algorithm is as follows (for simplicity, we consider the non-strongly convex case):

• GD: $O(\frac{G_{f,1}D}{\sqrt{T}})=O(\frac{\sqrt{n}G_{f,1}D}{\sqrt{nT}})=O(\frac{\sqrt{n}G_{f,1}D}{\sqrt{B}})$.
• SGD: $O(\frac{G_{f,2}D}{\sqrt{T}})=O(\frac{G_{f,2}D}{\sqrt{B}})\approx O(\frac{\sqrt{n}G_{f,1}D}{\sqrt{B}})$.
• Theorem 4.7 in [2]: $O(\frac{G_{f,1}D}{\sqrt{K}})=O(\frac{\sqrt{n}G_{f,1}D}{\sqrt{nK}})=O(\frac{\sqrt{n}G_{f,1}D}{\sqrt{B}})$.
• Our Theorem 4.2 for RR: $O(\frac{n^{1/4}\sqrt{G_{f,1}G_{f,2}D}}{\sqrt{T}})=O(\frac{n^{1/4}\sqrt{G_{f,1}G_{f,2}D}}{\sqrt{B}})\approx O(\frac{\sqrt{n}G_{f,1}D}{\sqrt{B}})$.

As such, all algorithms have the same rate. Therefore, we believe our analysis for RR is optimal in this case.

Lastly, for SS, our Theorems 4.5 and 4.7 are never optimal for whatever case. Hence, we only need to discuss Theorem 4.6. In this special case, as one can check, it degenerates to the same rate $O(\frac{\sqrt{n}G_{f,1}D}{\sqrt{B}})$ given above. Thus, we believe Theorem 4.6 in this special case is also unimprovable.

References

[1] Koren, Tomer, et al. "Benign underfitting of stochastic gradient descent." Advances in Neural Information Processing Systems 35 (2022): 19605-19617.

[2] Liu, Zijian, and Zhengyuan Zhou. "On the Last-Iterate Convergence of Shuffling Gradient Methods." International Conference on Machine Learning. PMLR, 2024.