Aggregated Momentum: Stability Through Passive Damping

Momentum is a simple and widely used trick which allows gradient-based optimizers to pick up speed along low curvature directions. Its performance depends crucially on a damping coefficient β. Large β values can potentially deliver much larger speedups, but are prone to oscillations and instability; hence one typically resorts to small values such as 0.5 or 0.9. We propose Aggregated Momentum (AggMo), a variant of momentum which combines multiple velocity vectors with different β parameters. AggMo is trivial to implement, but significantly dampens oscillations, enabling it to remain stable even for aggressive β values such as 0.999. We reinterpret Nesterov’s accelerated gradient descent as a special case of AggMo and analyze rates of convergence for quadratic objectives. Empirically, we find that AggMo is a suitable drop-in replacement for other momentum methods, and frequently delivers faster convergence. In spite of a wide range of modern optimization research, gradient descent with momentum and its variants remain the tool of choice in machine learning. Momentum methods can help the optimizer pick up speed along low curvature directions without becoming unstable in high-curvature directions. The simplest of these methods, classical momentum [23], has an associated damping coefficient, 0 ≤ β < 1, which controls how quickly the momentum vector decays. The choice of β imposes a tradoff between speed and stability: in directions where the gradient is small but consistent, the terminal velocity is proportional to 1/(1 − β), suggesting that β slightly less than 1 could deliver much improved optimization performance. However, large β values are prone to oscillations and instability [21, 4], requiring a smaller learning rate and hence slower convergence. Finding a way to dampen the oscillations while preserving the high terminal velocity of large beta values could dramatically speed up optimization. Sutskever et al.  found that Nesterov accelerated gradient descent [19], which they reinterpreted as a momentum method, was more stable than classical momentum for large β values and gave substantial speedups for training neural networks. However, the reasons for the improved performance remain somewhat mysterious. O’Donoghue and Candes [21] proposed to detect oscillations and eliminate them by resetting the velocity vector to zero. But in practice it is difficult to determine an appropriate restart condition. In this work, we introduce Aggregated Momentum (AggMo), a variant of classical momentum which maintains several velocity vectors with different β parameters. AggMo averages the velocity vectors when updating the parameters. We find that this combines the advantages of both small and large β values: the large values allow significant buildup of velocity along low curvature directions, while the small values dampen the oscillations, hence stabilizing the algorithm. AggMo is trivial to implement and incurs almost no computational overhead. We draw inspiration from the physics literature when we refer to our method as a form of passive damping. Resonance occurs when a system is driven at specific frequencies but may be prevented through careful design . Passive damping can address this in structures by making use of different materials with unique resonant frequencies. This prevents any single frequency from producing catastrophic resonance. By combining several momentum velocities together we achieve a similar effect — no single frequency is driving the system and so oscillation is prevented. ar X iv :1 80 4. 00 32 5v 2 [ cs .L G ] 2 3 Ju l 2 01 8 In this paper we analyze rates of convergence on quadratic functions. We also provide theoretical convergence analysis showing that AggMo achieves converging average regret in online convex programming [36]. To evaluate AggMo empirically we compare against other commonly used optimizers on a range of deep learning architectures: deep autoencoders, convolutional networks, and long-term short-term memory (LSTM). In all of these cases, we find that AggMo works as a drop-in replacement for classical momentum, in the sense that it works at least as well for a given β parameter. But due to its stability at higher β values, it often delivers substantially faster convergence than both classical and Nesterov momentum when its maximum β value is tuned. 2 Background: momentum-based optimization Classical momentum We consider a function f : R → R to be minimized with respect to some variable θ. Classical momentum (CM) minimizes this function by taking some initial point θ0 and running the following iterative scheme, vt = βvt−1 −∇θf(θt−1) θt = θt−1 + γtvt (1) where γt denotes a learning rate schedule, β is the damping coefficient and we set v0 = 0. Momentum can speed up convergence but it is often difficult to choose the right damping coefficient, β. Even with momentum, progress in a low curvature direction may be very slow. If the damping coefficient is increased to overcome this then high curvature directions may cause instability and oscillations. Nesterov momentum Nesterov’s Accelerated Gradient [19, 20] is a modified version of the gradient descent algorithm with improved convergence and stability. It can be written as a momentum-based method , vt = βvt−1 −∇θf(θt−1 + γt−1βvt−1) θt = θt−1 + γtvt (2) Nesterov momentum seeks to solve stability issues by correcting the error made after moving in the direction of the velocity, v. In fact, it can be shown that for a quadratic function Nesterov momentum adapts to the curvature by effectively rescaling the damping coefficients by the eigenvalues of the quadratic [28]. Quadratic convergence We begin by studying convergence on quadratic functions, which have been an important test case for analyzing convergence behavior [28, 21, 4], and which can be considered a proxy for optimization behavior near a local minimum [21]. We analyze the behavior of these optimizers along the eigenvectors of a quadratic function in Figure 1. In (a) we use a low damping coefficient (β = 0.9) while (b) shows a high damping coefficient (β = 0.999). When using a low damping coefficient it takes many iterations to find the optimal solution. On the other hand, increasing the damping coefficient from 0.9 to 0.999 causes oscillations which prevent convergence. When using CM in practice we seek the critical damping coefficient which allows us to rapidly approach the optimum without becoming unstable . On the other hand, Nesterov momentum with β = 0.999 is able to converge more quickly within high curvature regions than CM but retains oscillations for the quadratics exhibiting lower curvature. Convergence vs. condition number Figure 3 displays the convergence rate of each optimizer for quadratics with condition numbers (κ) from 10 to 10. The blue dashed line displays the optimal convergence rate achievable by CM with knowledge of the condition number — an unrealistic scenario in practice. The two curves corresponding to CM (red and purple) each meet the optimal convergence rate when the condition number is such that β is critical. On the left of this critical point, where the convergence rates for CM are flat, the system is ”under-damped” — it is in this setting that we observe oscillations during optimization. Nesterov momentum (green) is able to provide improved convergence in the under-damped regime because it dampens the oscillations. Details on the computation of these convergence rates are presented in