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. A fundamental issue for any machine learning algorithm is its ability to generalize from the training dataset to the test data. A classical framework used to study the generalization error in machine learning is PAC learning BID0 BID1 . However, the associated bounds using this approach can be conservative. Recently, the notion of uniform stability, introduced in the seminal work of Bousquet and Elisseeff BID2 , is leveraged to analyze the generalization error of the stochastic gradient method (SGM) BID3 . The result in BID3 ) is a substantial step forward, since SGM is widely used in many practical systems. This method is scalable, robust, and widely adopted in a broad range of problems.To accelerate the convergence of SGM, a momentum term is often added in the iterative update of the stochastic gradient BID4 . This approach has a long history, with proven benefits in various settings. The heavy-ball momentum method was first introduced by Polyak BID5 , where a weighted version of the previous update is added to the current gradient update. Polyak motivated his method by its resemblance to a heavy ball moving in a potential well defined by the objective function. Momentum methods have been used to accelerate the backpropagation algorithm when training neural networks BID6 . Intuitively, adding momentum accelerates convergence by circumventing sharp curvatures and long ravines of the sublevel sets of the objective function BID7 . For example, Ochs et al. has presented an illustrative example to show that the momentum can potentially avoid local minima BID8 . Nesterov has proposed an accelerated gradient method, which converges as O(1/k 2 ) where k is the number of iterations (Nesterov, 1983) . However, the Netstrov momentum does not seem to improve the rate of convergence for stochastic gradient (Goodfellow et al., 2016, Section 8.3.3) . In this work, we focus on the heavy-ball momentum.Although momentum methods are well known to improve the convergence in SGM, their effect on the generalization error is not well understood. In this work, we first build upon the framework in BID3 to obtain a bound on the generalization error of SGM with momentum (SGMM) for the case of strongly convex loss functions. Our bound is independent of the number of training iterations and decreases inversely with the size of the training set. Secondly, we develop an upper-bound on the optimization error, which quantifies the gap between the empirical risk of SGMM and the global optimum. Our bound can be made arbitrarily small by choosing sufficiently many iterations and a sufficiently small learning rate. Finally, we establish an upper-bound on the expected true risk of SGMM as a function of various problem parameters. We note that the class of strongly convex loss functions appears in several important machine learning problems, including linear and logistic regression with a weight decay regularization term.Other related works: convergence analysis of first order methods with momentum is studied in (Nesterov, 1983; BID11 BID12 BID13 BID14 BID15 BID16 BID17 . Most of these works consider the deterministic setting for gradient update. Only a few works have analyzed the stochastic setting BID15 BID16 BID17 . Our convergence analysis results are not directly comparable with these works due to their different assumptions regarding the properties of loss functions. In particular, we analyze the convergence of SGMM for a smooth and strongly convex loss function as in BID3 , which is new.First-order methods with noisy gradient are studied in BID18 and references therein. In BID18 , the authors show that there exists linear regression problems for which SGM outperforms SGMM in terms of convergence.Our main focus in this work is on the generalization, and hence true risk, of SGMM. We are aware of only one similar work in this regard, which provides stability bounds for quadratic loss functions BID19 . In this paper, we obtain stability bounds for the general case of strongly convex loss functions. In addition, unlike BID19 , our results show that machine learning models can be trained for multiple epochs of SGMM with bounded generalization errors. We study the generalization error and convergence of SGMM for the class of strongly convex loss functions, under mild technical conditions. We establish an upper-bound on the generalization error, which decreases with the size of the training set, and increases as the momentum parameter is increased. Secondly, we analyze the convergence of SGMM during training, by establishing an upper-bound on the gap between the empirical risk of SGMM and the global minimum. Our proposed bound reduces to a classical bound on the optimization error of SGM BID20 for convex functions, when the momentum parameter is set to zero. Finally, we establish an upper-bound on the expected difference between the true risk of SGMM and the global minimum of the empirical risk, and illustrate how it scales with the number of training steps and the size of the training set. Although our results are established for the case when the learning rate is constant, they can be easily extended to the case when the learning rate decreases with the number of iterations. We also present experimental evaluations on the notMNIST dataset and show that the numerical plots are consistent with our theoretical bounds on the generalization error and the convergence gap.
Stochastic gradient method with momentum generalizes.
{"src": "scitldr-AIC_train", "paper_id": "S1lwRjR9YX"}