Step-size Optimization for Continual Learning β part 2/2
Cleaned-text code points [15889, 26583). Bibliography omitted here; source.md includes it.
The experimental protocol is similar to the weight-flipping problem. We ran the experiment for 1 million steps. The trajectory reported in Figure 3 is for Adam with Ξ³ m = 1 \gamma_{m}=1 , where momentum is disabled, which is why we labeled the algorithm RMSProp. As before, we consider the correction of the bias at the start of the trajectory to be negligible. Results are reported for the best hyper-parameter configuration.
## 4 Step-size Optimization with IDBD
The Increment-Delta-Bar-Delta (IDBD) algorithm ( Sutton,, 1992 ) , presented next, is a step-size optimization method. Like RMSProp and Adam, IDBD is a two-level learning process: a base level and a meta level. The base level learns the weight vector π t \bm{w}_{t} used in the loss J t β ( π t ) J_{t}(\bm{w}_{t}) . The meta level learns meta-parameters , that is the step-size vector πΆ t \bm{\alpha}_{t} in Equation 1 , used in the base level to update the weights π t \bm{w}_{t} . The key difference between a step-size optimization method (e.g. IDBD) and a step-size normalization method (e.g. RMSProp) is that a step-size optimization method has an update rule for the meta level optimizing for the same loss J t β ( β
) J_{t}(\cdot) than the base level, as opposed to a step-size normalization method that uses a heuristic, normalization, to update the step-size vector πΆ t \bm{\alpha}_{t} at the meta level.
[noitemsep,nolistsep]
Ξ± 0 \alpha_{0} : initial step-size
ΞΈ \theta : meta step-size for the step-size update
To optimize at the meta level for the same loss than the base level, the general idea of meta-gradient proposes to derive the update rule of the meta level by taking the gradient of the loss with respect to the meta-parameters used in the update of the base level. In the case of IDBD, the step-size vector is defined as πΆ t = π π· t \bm{\alpha}_{t}=\bm{e}^{\bm{\beta}_{t}} , that is the exponential of a vector π· t {\bm{\beta}_{t}} . Updating the step-sizes in log-space guarantees that πΆ t \bm{\alpha}_{t} is always positive, and enables fast geometric updates. Other representation could have been chosen, like a sigmoid for example. Consequently, the IDBD algorithm is derived by taking the gradient of the linear least mean squared regression loss J t β ( π t ) = ( π t βΊ β π t β y t β ) 2 J_{t}(\bm{w}_{t})=(\bm{x}_{t}^{\intercal}\bm{w}_{t}-y^{*}_{t})^{2} with respect to the step-size vector π· t \bm{\beta}_{t} in log-space. Additionally, IDBD uses approximations in its derivation to keep the same complexity than Classic-SGD. See Sutton, (1992) for a complete description of that derivation.
We now give a mechanistic description of the IDBD algorithm to explain how it works. As with previous methods, IDBD first computes the error Ξ΄ t \delta_{t} . IDBD also keeps an average π t \bm{h}_{t} of the gradient Ξ΄ t β π t \delta_{t}\bm{x}_{t} for each component of the input π t \bm{x}_{t} . For a component i i at time t t , the absolute value of the average π ( t , i ) \bm{h}_{(t,i)} will be high for a weight π ( t , i ) \bm{w}_{(t,i)} if the recent gradients Ξ΄ t β π ( t , i ) \delta_{t}\bm{x}_{(t,i)} always have the same sign (moving in the same direction) and low if recent gradient oscillates around 0. Then, the step-size in log space π· ( t , i ) \bm{\beta}_{(t,i)} is increased if the last gradient Ξ΄ t β π ( t , i ) \delta_{t}\bm{x}_{(t,i)} correlates with the average π ( t , i ) \bm{h}_{(t,i)} , and decreased otherwise. Consequently, the step-size πΆ ( t , i ) \bm{\alpha}_{(t,i)} increases if the weight π ( t , i ) \bm{w}_{(t,i)} moves in a consistent direction over time (meaning the step-size was too small) and decreases when the direction oscillates (meaning the step-size was too high). The notation ( β
) + \left(\cdot\right)^{+} guarantees that ( 1 β πΆ t + 1 β
π t 2 ) + \left(1-\bm{\alpha}_{t+1}\cdot\bm{x}_{t}^{2}\right)^{+} is between 0 and 1 to discount the previous value π t \bm{h}_{t} .
The performance of IDBD on the weight-flipping and rate-tracking problems is shown on Figure 2 and Figure 3 respectively. On both cases, IDBD outperformed Classic SGD, RMSProp, and Adam. On the weight-flipping problem, IDBD learns to decrease the step-sizes for the inputs with constant weights and to keep the step-size high for inputs with flipping weights. On the 1D noisy rate-tracking problem, IDBD is able to track the optimal step-size.
## 5 Limitations of IDBD
The next step would be to use IDBD to learn the step-sizes in deep neural networks. A few open questions remain to be solved for such an endeavor. The first is how to generalize IDBD such that it be used to optimize all hyper-parameters. The second is that the main parameter of IDBD, the meta-step-size hyper-parameter, is sensitive to the magnitude of the gradients as shown in Figure 4 . In addition to the weights flipping between -1 and +1, labelled βMediumβ target weights, we also run a βSmallβ target weights and a βLargeβ target weights variants, respectively flipping from -.1 and +.1 and -10 and +10. Other parameters are the same. These two variants shifted the best meta-step-size for IDBD by 5 orders of magnitudes. Classic SGD on the other hand did not shift. Such sensitivity of the meta-step-size parameter to the variance of the inputs, the gradients, or the updates in general, makes it difficult to use IDBD in many common settings.
## 6 Existing Extensions of IDBD
IDBD was originally designed for linear regression but the idea of stochastic meta-gradient descent introduced in the paper is general. Indeed, a general formulation of meta-gradient in online optimization problems has been derived in Xu et al., (2018) . Meta-gradient in general has been used in a wide variety of settings, see Andrychowicz et al., (2016) or Xu et al., (2020) for examples.
There are different extensions of the IDBD algorithm, more specifically to different learning settings and problems. For example, Koop, (2008) extends IDBD to classification problems over linear regression problems. Kearney et al., (2019) , Thill, (2015) , and Young et al., (2018) extended the IDBD algorithm for temporal-difference (TD) learning in a reinforcement learning context. Schraudolph, (1999) extends the IDBD algorithm to multi-layer neural network with the SMD algorithm. SMD has been later applied to areas like independent component analysis ( Schraudolph and Giannakopoulos,, 2000 ) and complex human motion tracking ( Kehl and Van Gool,, 2006 ) .
To address the sensitivity of IDBD and SMD to the meta-step-size parameter, Mahmood et al., (2012) proposed the Autostep algorithm as a tuning-free extension. Sutton, (2022) summarizes the history and recent success of meta-learning algorithms in step-size adaptation methods.
## 7 Other Step-size Adaptation Algorithms
There are numerous optimization techniques developed for improving convergence or tracking of optimal parameters in stationary or online optimization problems ( Amari et al.,, 2000 ; Roux and Fitzgibbon,, 2010 ; Schaul et al.,, 2013 ; Desjardins et al.,, 2015 ; Bernacchia et al.,, 2018 ) . These techniques include (but are not limited to) second order optimization methods, variance reduction methods, and step-size normalization techniques. General meta-gradient step-size updates, like IDBD, are conceptually different from the aforementioned methods. For example, second order optimization methods such as Newton and quasi-Newton methods leverage information about the curvature of the loss landscape in weights space to obtain an improved direction ( Kochenderfer and Wheeler,, 2019 ) . In contrast, meta-gradient algorithms like IDBD perform updates in hyper parameters space (such as step-sizes) instead of the weight space (as demonstrated in Figure 1 ). Note also that in the example problems of Section 3 , second order methods have almost no advantage over first order methods because the average curvature in these problems is independent of the weights and is almost constant over different dimensions.
Other approaches include the work of van Erven and Koolen, (2016) , which introduces an online algorithm that runs multiple sub-algorithms, each with a different step-size, and learns to use the best step-size for online convex optimization problems. Wu et al., (2020) proposes to adapt the step-size according to accumulating gradients for L-Lipschitz continuous objectives. Koolen et al., (2014) proposes to use a grid of step-size and runs in linear time for prediction problems with expert knowledge. Jacobsen et al., (2019) introduces AdaGain. AdaGain was designed to work alongside other step-size adaptation methods. To that end, Adagain optimizes a generic proxy objective function independent of the base objective function: the vector of step-size is optimized so that the norm of the gradient of the base objective function becomes small. They show that AdaGain with RMSProp, for example, can outperform other methods in a continual learning setting.
Finally, variance reduction techniques such as SVRG ( Johnson and Zhang,, 2013 ) and SAGA ( Defazio et al.,, 2014 ) try to smooth out the noise and obtain lower-variance approximations of gradient of expected loss in stationary problems. This limits the application of these methods to online learning problems where such expected loss function does not exist.
## 8 A Promising Research Direction: Normalized Step-size Optimization
Adam and RMSProp are step-size normalization methods widely used in deep learning. They use momentum and normalization techniques to adapt the step-size vectors, often providing more stable updates compared to Classic SGD. These methods have been successful and are now ubiquitous. This paper has shown that they may not be enough, in the context of continual learning. On the other hand, meta-gradient algorithms like IDBD optimize the step-sizes with respect to the loss, but have other limitations such as stability and sensitivity to its step-size parameter. Optimizing step-sizes in deep neural-networks in a practical way for continual learning is still an open research question. Consequently, we see that combining normalization and optimization seem a promising research direction towards better step-size adaptation methods in deep networks. The Autostep algorithm ( Mahmood et al.,, 2012 ) can be seen as a possible attempt towards such direction.
Finally, it is possible that a good step-size adaptation method will improve learning in the continual learning setting but also in other setting. For example, a good step-size adaptation method may remove the need for a manually tuned step-size schedule, having to sweep over constant step-size parameters, or better learning in long training of large models.