모멘텀을 사용한 확률적 경사 하강법은 알고리즘적으로 안정적이다

Stochastic Gradient Descent with Momentum is Algorithmically Stable

모멘텀을 사용한 확률적 경사 하강법(SGDM)은 머신 러닝에서 가장 널리 사용되는 최적화 알고리즘 중 하나입니다. SGDM의 최적화 특성에 대한 연구는 광범위하게 진행되었지만, SGDM이 언제 그리고 어떻게 새로운 데이터에 대해 잘 일반화될 수 있는지에 대한 이해는 여전히 부족합니다. 특히, 모멘텀은 학습 속도를 가속화하지만 일반화를 저하시킬 수 있다는 추측이 제기되어 왔습니다. 본 논문에서는 알고리즘 안정성이라는 관점에서 SGDM의 포괄적인 일반화 분석을 수행하여 이러한 간극을 메웁니다. 구체적으로, 우리는 Polyak 및 Nesterov의 모멘텀 방식을 모두 포함하는 일반화된 SGDM 프레임워크를 제시하고, 매끄럽고 볼록한 문제에 대한 모델 안정성 경계를 엄격하게 도출합니다. 주목할 점은 얻어진 경계가 최적화 과정에서의 작은 오차 경계를 활용하며, $[0, 1)$ 구간 내의 모든 모멘텀 파라미터에 적용되며, 일반적으로 가정되는 손실 함수의 리프시츠 연속성을 요구하지 않습니다. 또한, 일반화된 SGDM에 대한 최적화 오차 경계를 도출하고, 이를 일반화 분석과 결합하여 Polyak 및 Nesterov의 모멘텀을 사용하는 SGDM에 대한 최적의 과잉 모집단 위험 경계를 얻습니다.

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.