Does Momentum Change the Implicit Regularization on Separable Data?
This provides theoretical assurance for practitioners using momentum-based optimizers in machine learning, though it is incremental as it extends known results to momentum variants.
The paper tackles the problem of how momentum affects generalization in optimization algorithms by proving that gradient descent with momentum (GDM) converges to the L2 max-margin solution on linear classification with separable data and exponential-tailed loss, ensuring low-complexity models and generalization, with numerical experiments supporting the results.
The momentum acceleration technique is widely adopted in many optimization algorithms. However, there is no theoretical answer on how the momentum affects the generalization performance of the optimization algorithms. This paper studies this problem by analyzing the implicit regularization of momentum-based optimization. We prove that on the linear classification problem with separable data and exponential-tailed loss, gradient descent with momentum (GDM) converges to the L2 max-margin solution, which is the same as vanilla gradient descent. That means gradient descent with momentum acceleration still converges to a low-complexity model, which guarantees their generalization. We then analyze the stochastic and adaptive variants of GDM (i.e., SGDM and deterministic Adam) and show they also converge to the L2 max-margin solution. Technically, to overcome the difficulty of the error accumulation in analyzing the momentum, we construct new potential functions to analyze the gap between the model parameter and the max-margin solution. Numerical experiments are conducted and support our theoretical results.