Sharper Bounds of Non-Convex Stochastic Gradient Descent with Momentum

I don't agree with authors' claim that this paper is the first one studying the generalization bound of SGDM and that the two referred papers, Li & Orabona 2020 and Cutkosky & Mehta 2021, provide convergence bound (defined w.r.t. the ERM loss $\nabla F_S$). I believe both referred papers actually provide generalization bound, e.g., see Li & Orabona Theorem 1 and Cutkosky & Mehta Theorem 2. Both theorems provide upper bounds on the generalization loss $\nabla F$ instead of the ERM loss $\nabla F_S$. Also I'd like to point out the difference in terms of data sampling: this paper considers sampling with replacement from a fixed dataset so that there could be repeated data, while the referred papers sample an i.i.d. data from the unknown population distribution in every iteration. This subtle difference is not mentioned in the paper. If my understanding is correct, the results of this paper is less novel than it claims.

As a related question, does Theorem 3.1 (and similarly Theorem 3.5) also hold for the generalization loss $\nabla F$? It seems to me that if we slightly modify Assumption 2.4 and 2.8 by replacing $\nabla F_S$ with $\nabla F$, then the same analysis in the proof in C.1 still holds: smoothness (eq. 5) is not affected; the martingale difference concentration on page 20 and the sub-Weibull concentration on page 21 still hold with $\nabla F_S$ replaced by $\nabla F$. In other words, is it true that the same analysis (under slightly different assumptions) provides a generalization bound?

As a disclaimer, I'm not an expert in the field of learning theory, and I could be wrong with my understandings. I will be glad to reevaluate the results if the authors point out I'm wrong.

Missing baselines for comparison in numerical experiments. (details in questions)

• The amount of improvement compared to related work seem very marginal. For instance, compared to Li & Orabona, a related work that this manuscript often refers to, the improvement is only from $\log(T/\delta)$ to $\log(1/\delta)$. I get that Theorem 3.1 also holds for heavy tailed noise ($\theta > 1$), but in that case the authors admit the bound does not improve over standard SGD.
• I am not an expert in generalization bound for stochastic gradient methods. Yet, a quick search shows [1], which is present in the references of this paper, but I could not find where it was cited. At least some comparison to [1] should be provided.
• SGDM with decaying step size is quite outdated at this point, with cosine or more sophisticated sche dules, for instance [2]. As such, I’m not sure how useful these results are.
• Experiments are shown for convex examples like logistic regression and Huber loss. What is the point of these experiments, when the entire paper is about non-convex bounds?
• Writing should be vastly improved. Many paragraphs and sentences are dense and long, hurting readability quite a bit: e.g., line 210 to 215 is one sentence, Remark 3.2, entire experimental setup from 466 to 492 is one paragraph… etc).

[1] Ramezani-Kebrya et al. (2024) “On the Generalization of Stochastic Gradient Descent with Momentum”

[2] Defazio et al. (2024) "The Road Less Scheduled”

Although I'm not so familiar with related literature, it seems that there are many existing high-probability and generalization bounds established for various optimization methods. It is unclear what are the key differences (see also Questions)

The empirical section is left somewhat underbaked - it will be worthwhile presenting additional results on more realistic tasks/datasets/neural networks (including transformer style architectures).