Search papers, labs, and topics across Lattice.
This paper provides a comprehensive generalization analysis of Stochastic Gradient Descent with Momentum (SGDM) by establishing tight on-average model stability bounds for smooth and convex problems. The analysis encompasses both Polyak's and Nesterov's momentum schemes and exploits small optimization error bounds along the trajectory, without requiring Lipschitz loss functions. By combining optimization error bounds with the generalization analysis, the paper derives optimal excess population risk bounds for SGDM with both Polyak's and Nesterov's momentum.
Momentum doesn't hurt generalization in SGDM, and this paper proves it with tight stability bounds applicable to both Polyak's and Nesterov's variants.
Stochastic gradient descent with momentum (SGDM) is one of the most widely used optimization algorithms in machine learning. While optimization properties of SGDM have been extensively studied in the literature, it remains insufficiently understood whether and when SGDM can generalize well to unseen data. In particular, it has been conjectured that while momentum accelerates training, it may degrade generalization. In this paper, we close this gap by developing a comprehensive generalization analysis of SGDM through the lens of algorithmic stability. More specifically, we introduce a generalized SGDM framework that encompasses both Polyak's and Nesterov's momentum schemes, and establish tight on-average model stability bounds for smooth and convex problems. Notably, the obtained bounds exploit small optimization error bounds along the trajectory, apply to any momentum parameter in the interval $[0, 1)$, and do not require the commonly assumed Lipschitzness of loss functions. We further derive optimization error bounds for the generalized SGDM, and combine them with our generalization analyses to obtain optimal excess population risk bounds for SGDM with both Polyak's and Nesterov's momentum.
