While momentum-based methods, in conjunction with the stochastic gradient descent, are widely used when training machine learning models, there is little theoretical understanding on the generalization error of such methods. In practice, the momentum parameter is often chosen in a heuristic fashion with little theoretical guidance. In this work we use the framework of algorithmic stability to provide an upper-bound on the generalization error for the class of strongly convex loss functions, under mild technical assumptions. Our bound decays to zero inversely with the size of the training set, and increases as the momentum parameter is increased. We also develop an upper-bound on the expected true risk, in terms of the number of training steps, the size of the training set, and the momentum parameter.
This paper presents an analysis of generalization error of SGD with multiple passes for strongly convex objectives using the framework of algorithmic stability [Bousquet and Elisseef, 2002] and its recent use to analyze generalization error of SGD based methods [Hardt, Recht and Singer 2016].
The problem considered by this work is interesting and raises the possibility of understanding generalization related questions of SGD style methods when augmented with momentum, which is common practice in Deep Learning [Sutskever et al. 2013]. That said, there are some concerns about the results as presented in this paper, which I will elaborate below:
- Consider the stability bound admitted by theorem 2: The special case (similar to theorem 3.9 of Hardt et al 2016) when the learning rate alpha = 1/beta (which is the typical learning rate that theory advocates), and setting kappa = beta/gamma where kappa is the condition number of the problem, leads to the following bound on momentum allowed by theorem 2, which is:
(something non-positive) <= mu < 1/(3*kappa). 
This is basically the regime where momentum does not make any difference towards accelerating optimization. Referring to the standard value of momentum for strongly convex functions, we see that the momentum is set as mu = (sqrt(kappa)-1)/(sqrt(kappa)+1) [Nesterov, 1983], or, mu = ( (sqrt(kappa)-1)/(sqrt(kappa)+1) )^2  [Polyak,1964]. Upon simplification of this standard momentum values, we see that mu \approx 1 - 1/sqrt(kappa) which grows close to one as kappa grows large. On the other hand, the momentum values admitted by the paper for their bound is super tiny (which gets to zero as the condition number kappa grows large). This essentially implies there is not much about momentum that is captured by the bound of theorem 2 since there is no characterization of the provided bound for theoretically advocated and practically used parameters for momentum.
- In proposition 1, there is no quantitative description of what "sufficiently small" mu (momentum parameter) is - this statement is imprecise. As mentioned in the previous point, sufficiently small mu really is not descriptive of momentum parameters employed in practice (mu in practice typically is >= 0.9). For strongly convex objectives, this should be closer to 1- (1/sqrt(kappa)). Sufficiently small mu parameter essentially does not yield quantitatively different behaviors compared to standard SGD. 
In summary, while this paper attempts to make progress on an interesting question, but falls short and doesn't really capture the behavior of these methods that is even mildly reflective of practice (even in terms of the parameter regimes admitted by the bounds proven in the theorems).
- This paper does not perform a thorough literature survey of published results. Furthermore, this paper does not present a precise treatment of assumptions (and implications) amongst other works cited in the paper (see for e.g. [4] below). 
[1] Polyak (1987) presents (generalization) behavior of Heavy Ball momentum with noisy (inexact) gradients.
[2] Several efforts in Signal Processing literature do consider the similar setting as one considered by this paper, which is that of Heavy Ball (called accelerated LMS) method with noisy gradients: refer to Proakis (1974), Roy and Shynk (1990), Sharma et al. (1998). 
[3] Kidambi et al (2018) estimate the "optimization" power (which is a part of characterization of generalization error [Bach and Moulines 2011], since this dominates at the start of optimization) of HB method with Stochastic Gradients and prove that HB+stochastic gradients does not offer any speedup over vanilla SGD.
[4] Loizou and Richtarik provide an analysis of stochastic heavy ball with super large batch sizes (so they end up showing accelerated rates) under similar assumptions as considered by this paper, such as assuming the function is smooth and strongly convex. However, the paper dismisses the work of Loizou and Richtarik to be working with a different set of assumptions - this is not really true.