We introduce NAMSG, an adaptive first-order algorithm for training neural networks. The method is efficient in computation and memory, and is straightforward to implement. It computes the gradients at configurable remote observation points, in order to expedite the convergence by adjusting the step size for directions with different curvatures in the stochastic setting. It also scales the updating vector elementwise by a nonincreasing preconditioner to take the advantages of AMSGRAD. We analyze the convergence properties for both convex and nonconvex problems by modeling the training process as a dynamic system, and provide a strategy to select the observation factor without grid search. A data-dependent regret bound is proposed to guarantee the convergence in the convex setting. The method can further achieve a O(log(T)) regret bound for strongly convex functions. Experiments demonstrate that NAMSG works well in practical problems and compares favorably to popular adaptive methods, such as ADAM, NADAM, and AMSGRAD. Training deep neural networks (Collobert et al., 2011; Hinton et al., 2012; Amodei et al., 2016; He et al., 2016) with large datasets costs a huge amount of time and computational resources. Efficient optimization methods are urgently required to accelerate the training process. First-order optimization methods (Robbins & Monro, 1951; Polyak, 1964; Bottou, 2010; Sutskever et al., 2013; Kingma & Ba, 2015; Bottou et al., 2018) are currently the most popular for training neural networks. They are easy to implement since only first-order gradients are introduced as input. Besides, they require low computation overheads except for computing gradients, which is of the same computational complexity as just evaluating the function. Compared with second-order methods (Nocedal, 1980; Martens, 2010; Byrd et al., 2016) , they are more effective to handle gradient noise. Sutskever et al. (2013) show that the momentum is crucial to improve the performance of SGD. Momentum methods, such as HB Polyak (1964) , can amplify steps in low-curvature eigen-directions of the Hessian through accumulation, although careful tuning is required to ensure fine convergence along the high-curvature directions. Sutskever et al. (2013) also rewrite the Nesterov's Accelerated Gradient (NAG) (Nesterov, 1983) in a momentum form, and show the performance improvement over HB. The method computes the gradient at a observation point ahead of the current point along the last updating direction. They illustrate that NAG suppresses the step along high curvature eigen-directions in order to prevent oscillations. However, all these approaches are approximation of their original forms derived for exact gradients, without fully study on gradient noise. show the insufficiency of HB and NAG in stochastic optimization, especially for small minibatches. They further present ASGD and show significant improvements. However, the method requires tuning of 3 parameters, leading to huge costs that impede its practical applications. Among variants of SGD methods, adaptive methods that scale the gradient elementwise by some form of averaging of the past gradients are particularly successful. ADAGRAD (Duchi et al., 2011) is the first popular method in this line. It is well-suited for sparse gradients since it uses all the past gradients to scale the update. Nevertheless, it suffers from rapid decay of step sizes, in cases of nonconvex loss functions or dense gradients. Subsequent adaptive methods, such as RMSPROP (Tieleman & Hinton., 2012) , ADADELTA (Zeiler, 2012) , ADAM (Kingma & Ba, 2015) , and NADAM (Dozat, 2016) , mitigate this problem by using the exponential moving averages of squared past gradients. However, Reddi et al. (2018) show that ADAM does not converge to optimal solutions in some convex problems, and the analysis extends to RMSPROP, ADADELTA, and NADAM. They propose AMSGRAD, which fixes the problem and shows improvements in experiments. In this paper, we propose NAMSG, that is an efficient first-order method for training neural networks. The name is derived from combining a configurable NAG method (CNAG) and AMSGRAD. NAMSG computes the stochastic gradients at configurable observation points ahead of the current parameters along the last updating direction. Nevertheless, instead of approximating NAG for exact gradients, it adjusts the learning rates for eigen-directions with different curvatures to expedite convergence in the stochastic setting, by selecting the observation distance. It also scales the update vector elementwisely using the nonincreasing preconditioner of AMSGRAD. We analyze the convergence properties by modeling the training process as a dynamic system, reveal the benefits of remote gradient observations and provide a strategy to select the observation factor without grid search. A regret bound is introduced in the convex setting, and it is further improved for strongly convex functions. Finally, we present experiments to demonstrate the efficiency of NAMSG in real problems. 2 THE NAMSG SCHEME Before further description, we introduce the notations following Reddi et al. (2018) , with slight abuse of notation. The letter t denotes iteration number, d denotes the dimension of vectors and matrices, denotes a predefined positive small value, and S d + denotes the set of all positive definite d × d matrix. For a vector a ∈ R d and a matrices M ∈ R d × R d , we use a/M to denote M −1 a, diag(a) to denote a square diagonal matrix with the elements of a on the main diagonal, M i to denote the i th row of M , and , we use √ a for elementwise square root, a 2 for elementwise square, a/b for elementwise division, and max(a, b) to denote elementwise maximum. For any vector θ i ∈ R d , θ i,j denotes its j th coordinate where j ∈ {1, 2, . . . , d}. We define F ⊂ R d as the feasible set of points. Assume that F has bounded diameter D ∞ , i.e. x − y ≤ D ∞ for any x, y ∈ F, and ∇f t (x) ∞ ≤G ∞ , ∇f t (x) 1 ≤G 1 for all x ∈ F. The projection operation is defined as Π F ,A (y) = arg min x∈F A 1/2 (x − y) for A ∈ S d + and y ∈ R d . In the context of machine learning, we consider the minimization problem of a stochastic function, where x is a d dimensional vector consisting of the parameters of the model, and ξ is a random datum consisting of an input-output pair. Since the distribution of ξ is generally unavailable, the optimizing problem (1) is approximated by minimizing the empirical risk on the training set {ζ 1 , ζ 2 , ..., ζ N }, as In order to save computation and avoid overfitting, it is common to estimate the objective function and its gradient with a minibatch of training data, as where the minibatch S t ⊂ {1, 2, ..., N }, and b = |S t | is the size of S t . Firstly, we propose a configurable NAG method (CNAG). Since the updating directions are partially maintained in momentum methods, gradients computed at observation points, which lie ahead of the current point along the last updating direction, contain the predictive information of the forthcoming update. The remote observation points are defined asẋ t = x t − η t u t−1 where u t−1 is the updating vector, andẋ 1 = x 1 . By computing the gradient at a configurable observation pointẋ t , and substituting the gradient with the observation gradient in the HB update, we obtain the original form of CNAG, as where α t , β t , η t are configurable coefficients, and m 0 = 0. The observation distance η t can be configured to accommodate gradient noise, instead of η t = β t in NAG (Sutskever et al., 2013) . Both x t andẋ t are required to update in (4). To make the method more efficient, we simplify the update by approximation. Assume that the coefficients α t , β 1t , and η t , change very slowly between adjacent iterations. Substituting x t byẋ t + η t−1 α t−1 m t−1 , we obtain the concise form of CNAG, as where the observation factor µ t = η t (1 − β t )/β t , and we use x instead ofẋ for simplicity. In practical computation of CNAG, we further rearrange the update form as where only 3 scalar vector multiplications and 3 vector additions are required per iteration besides the gradient computation. Hereinafter, we still use (5) for simplicity in expressions. Then, we study the relation of CNAG and ASGD, that guides the selection of the momentum coefficient. shows that ASGD improves on SGD in any information-theoretically admissible regime. By taking a long step as well as short step and an appropriate average of both of them, ASGD tries to make similar progress on different eigen-directions. It takes 3 hyper-parameters: short stepα, long step parameterκ, and statistical advantage parameterξ.α is the same as the step size in SGD. For convex functions,κ is an estimation of the condition number. The statistical advantage parameterξ ≤ √κ captures trade off between statistical and computational condition numbers, andξ √κ in high stochasticity regimes. These hyper-parameters vary in large ranges, and are difficult to estimate. The huge costs in tuning limits the application of ASGD. The appendix shows that CNAG is a more efficient equivalent form of ASGD. For CNAG with constant hyper-parameters, the momentum coefficient β t = β = (κ − 0.49ξ)/(κ + 0.7ξ). Since the condition number is generally large in real high dimension problems, and the statistical advantage parameterξ ≤ √κ , β is close to 1. To sum up, the equivalence of CNAG and ASGD shows that in order to narrow the gap between the step sizes on eigen-directions with different curvatures, the momentum coefficient β should be close to 1. Finally, we form NAMSG by equipping CNAG with the nonincreasing preconditioner of AMSGRAD, and project the parameter vector x into the feasible set F. Algorithm 1 shows the pseudo code of NAMSG. Compared with AMSGRAD, NAMSG requires low computation overheads, as a scalar vector multiplication and a vector addiction per iteration, which are much cheaper than the gradient estimation. Almost no more memory is needed if the vector operations are run by pipelines. In most cases, especially when weight decay is applied for regularization, which limits the norm of the parameter vectors, the projection can also be omitted in implementation to save computation. We present the NAMSG method, which computes the gradients at configurable remote observation points, and scales the update vector elementwise by a nonincreasing preconditioner. It is efficient in computation and memory, and is straightforward to implement. A data-dependent regret bound is proposed to guarantee the convergence in the convex setting. The bound is further improved to O(log(T )) for strongly convex functions. The analysis of the optimizing process provides a hyperparameter policy (OBSB) which leaves only the step size for grid search. Numerical experiments demonstrate that NAMSG and OBSB converge faster than ADAM, NADAM, and AMSGRAD, for the tested problems.
A new algorithm for training neural networks that compares favorably to popular adaptive methods.
{"src": "scitldr-AIC_train", "paper_id": "HkxGaeHKvB"}