
Nesterov SGD is widely used for training modern neural networks and other machine learning models. Yet, its advantages over SGD have not been theoretically clarified. Indeed, as we show  in this paper, both theoretically and empirically, Nesterov SGD with any parameter selection does not in general provide acceleration over ordinary SGD. Furthermore, Nesterov SGD may diverge for step sizes that ensure convergence of ordinary SGD. This is in contrast to the classical results in the deterministic setting, where the same step size ensures accelerated convergence of the Nesterov's method over optimal gradient descent.

 To address the non-acceleration issue, we  introduce a compensation term to Nesterov SGD. The resulting  algorithm, which we call MaSS, converges  for same step sizes as SGD. We prove that MaSS obtains an accelerated convergence rates over SGD for any mini-batch size in the linear setting.   For full batch, the convergence rate of MaSS matches the well-known accelerated rate of the Nesterov's method. 

 We also analyze the  practically important question of the dependence of the convergence rate and  optimal hyper-parameters on the mini-batch size, demonstrating three distinct regimes: linear scaling, diminishing returns and saturation.

 Experimental evaluation of MaSS for several standard  architectures of deep networks, including ResNet and convolutional networks, shows improved performance over SGD, Nesterov SGD  and Adam. Many modern neural networks and other machine learning models are over-parametrized (5) . These models are typically trained to have near zero training loss, known as interpolation and often have strong generalization performance, as indicated by a range of empirical evidence including (23; 3). Due to a key property of interpolation -automatic variance reduction (discussed in Section 2.1), stochastic gradient descent (SGD) with constant step size is shown to converge to the optimum of a convex loss function for a wide range of step sizes (12) . Moreover, the optimal choice of step size η * for SGD in that setting can be derived analytically. The goal of this paper is to take a step toward understanding momentum-based SGD in the interpolating setting. Among them, stochastic version of Nesterov's acceleration method (SGD+Nesterov) is arguably the most widely used to train modern machine learning models in practice. The popularity of SGD+Nesterov is tied to the well-known acceleration of the deterministic Nesterov's method over gradient descent (15) . Yet, has not not theoretically clear whether Nesterov SGD accelerates over SGD. As we show in this work, both theoretically and empirically, Nesterov SGD with any parameter selection does not in general provide acceleration over ordinary SGD. Furthermore, Nesterov SGD may diverge, even in the linear setting, for step sizes that guarantee convergence of ordinary SGD. Intuitively, the lack of acceleration stems from the fact that, to ensure convergence, the step size of SGD+Nesterov has to be much smaller than the optimal step size for SGD. This is in contrast to the deterministic Nesterov method, which accelerates using the same step size as optimal gradient descent. As we prove rigorously in this paper, the slow-down of convergence caused by the small step size negates the benefit brought by the momentum term. We note that a similar lack of acceleration for the stochastic Heavy Ball method was analyzed in (9) . To address the non-acceleration of SGD+Nesterov, we introduce an additional compensation term to allow convergence for the same range of step sizes as SGD. The resulting algorithm, MaSS (Momentum-added Stochastic Solver) 1 updates the weights w and u using the following rules (with the compensation term underlined): Figure 1 : Non-acceleration of Nesterov SGD and fast convergence of MaSS. w t+1 ← u t − η 1∇ f (u t ), u t+1 ← (1 + γ)w t+1 − γw t + η 2∇ f (u t ). ( Here,∇ represents the stochastic gradient. The step size η 1 , the momentum parameter γ ∈ (0, 1) and the compensation parameter η 2 are independent of t. We proceed to analyze theoretical convergence properties of MaSS in the interpolated regime. Specifically, we show that in the linear setting MaSS converges exponentially for the same range of step sizes as plain SGD, and the optimal choice of step size for MaSS is exactly η * which is optimal for SGD. Our key theoretical result shows that MaSS has accelerated convergence rate over SGD. Furthermore, in the full batch (deterministic) scenario, our analysis selects η 2 = 0, thus reducing MaSS to the classical Nesterov's method (15) . In this case our convergence rate also matches the well-known convergence rate for the Nesterov's method (15; 4) . This acceleration is illustrated in Figure 1 . Note that SGD+Nesterov (as well as Stochastic Heavy Ball) does not converge faster than SGD, in line with our theoretical analysis. We also prove exponential convergence of MaSS in more general convex setting under additional conditions. We further analyze the dependence of the convergence rate e −s(m)t and optimal hyper-parameters on the mini-batch size m. We identify three distinct regimes of dependence defined by two critical values m * 1 and m * 2 : linear scaling, diminishing returns and saturation, as illustrated in Figure 2 . The convergence speed per iteration s(m), as well as the optimal hyper-parameters, increase linearly as m in the linear scaling regime, sub-linearly in the diminishing returns regime, and can only increase by a small constant factor in the saturation regime. The critical values m * 1 and m * 2 are derived analytically. We note that the intermediate "diminishing terurns" regime is new and is not found in SGD (12) . To the best of our knowledge, this is the first analysis of mini-batch dependence for accelerated stochastic gradient methods. We also experimentally evaluate MaSS on deep neural networks, which are non-convex. We show that MaSS outperforms SGD, SGD+Nesterov and Adam (10) both in optimization and generalization, on different architectures of deep neural networks including convolutional networks and ResNet (7) . The paper is organized as follows: In section 2, we introduce notations and preliminary results. In section 3, we discuss the non-acceleration of SGD+Nesterov. In section 4 we introduce MaSS and analyze its convergence and optimal hyper-parameter selection. In section 5, we analyze the mini-batch MaSS. In Section 6, we show experimental results.
This work proves the non-acceleration of Nesterov SGD with any hyper-parameters, and proposes new algorithm which provably accelerates SGD in the over-parameterized setting.
{"src": "scitldr-AIC_train", "paper_id": "r1gixp4FPH"}