Year: 2020

Abstract:
In this study, we investigate learning rate adaption at different levels based on the hyper-gradient descent framework and propose a method that adaptively learns the optimizer parameters by combining different levels of adaptations. Meanwhile, we show the relationship between regularizing over-parameterized learning rates and building combinations of adaptive learning rates at different levels. The experiments on several network architectures, including feed-forward networks, LeNet-5 and ResNet-18/34, show that the proposed multi-level adaptive approach can significantly outperforms baseline adaptive methods in a variety of circumstances.

heading: 1 INTRODUCTION
text: The basic optimization algorithm for training deep neural networks is the gradient descent method (GD), which includes stochastic gradient descent (SGD), mini-batch gradient descent, and batch gradient descent. The model parameters are updated according to the first-order gradients of the empirical risks with respect to the parameters being optimized, while back-propagation is implemented for calculating the gradients of parameters (Ruder, 2016). Naïve gradient descent methods apply fixed learning rates without any adaptation mechanisms. However, considering the change of available information during the learning process, SGD with fixed learning rates can result in inefficiency and requires a large amount of computing resources in hyper-parameter searching. One solution is to introduce a learning rate adaptation. This idea can be traced back to the work on gain adaptation for connectionist learning methods (Sutton, 1992) and related extensions for non-linear cases (Schraudolph, 1999; Yu et al., 2006). In recent years, optimizers with adaptive updating rules were developed in the context of deep learning, while the learning rates are still fixed in training. The proposed methods include AdaGrad (Duchi et al., 2011), RMSProp (Tieleman and Hinton, 2012), and Adam (Kingma and Ba, 2015). In addition, there are optimizers aiming to address the convergence issue in Adam (Reddi et al., 2018; Luo et al., 2018) and to rectify the variance of the adaptive learning rate (Liu et al., 2019). Other techniques, such as Lookahead, can also achieve variance reduction and stability improvement with negligible extra computational cost (Zhang et al., 2019).
Even though the adaptive optimizers with fixed learning rates can converge faster than SGD in a wide range of tasks, the updating rules are designed manually while more hyper-parameters are introduced. Another idea is to use objective function information and update the learning rates as trainable parameters. These methods were introduced as automatic differentiation, where the hyper-parameters can be optimized with backpropagation (Maclaurin et al., 2015; Baydin et al., 2018). As gradient-based hyper-parameter optimization methods, they can be implemented as an online approach (Franceschi et al., 2017). With the idea of auto-differentiation, learning rates can be updated in real-time with the corresponding derivatives of the empirical risk (Almeida et al., 1998), which can be generated to all types of optimizers for deep neural networks (Baydin et al., 2017). Another step size adaptation approach called “L4”, is based on the linearized expansion of the loss functions, which rescales the gradient to make fixed predicted progress on the loss (Rolinek and Martius, 2018). Furthermore, by addressing the issue of poor generalization performance of adaptive methods, dynamically bound for gradient methods was introduced to build a gradual transition between adaptive approach and SGD (Luo et al., 2018).
Another set of approaches train an RNN (recurrent neural network) agent to generate the optimal learning rates in the next step given the historical training information, known as “learning to learn”
(Andrychowicz et al., 2016). This approach empirically outperforms hand-designed optimizers in a variety of learning tasks, but another study has shown that it may not be effective for long horizons (Lv et al., 2017). The generalization ability of this approach can be improved by using meta training samples and hierarchical LSTMs (long short-term memory) (Wichrowska et al., 2017).
Beyond the adaptive learning rate, learning rate schedules can also improve the convergence of optimizers, including time-based decay, step decay, exponential decay (Li and Arora, 2019). The most fundamental and widely applied one is a piece-wise step-decay learning rate schedule, which could vastly improve the convergence of SGD and even adaptive optimizers(Luo et al., 2018; Liu et al., 2019). It can be further improved by introducing a statistical test to determine when to apply step-decay (Lang et al., 2019; Zhang et al., 2020). Also, there are works on warm-restart (O’donoghue and Candes, 2015; Loshchilov and Hutter, 2017), which could improve the performance of SGD anytime when training deep neural networks.
We find that the existing gradient or model-based learning rate adaptation methods including hypergradient descent, L4 and learning to learn only focus on global adaptation, which could be further extended to multi-level cases. That focus aims to introduce locally shared adaptive learning rates such as the layer-wise learning rate and parameter-wise learning rate and considers all levels’ information in determining the updating step-size for each parameter. The main contribution of our study can be summarized as follows:
• We introduce hierarchical learning rate structures for neural networks and apply hypergradient descent to obtain adaptive learning rates at different levels. • We introduce a set of regularization techniques for learning rates to address the balance of
global and local adaptations and show the relationship with weighted combinations. • We propose an algorithm implementing the combination of adaptive learning rates at multiple
levels for model parameter updating.

heading: 2 MULTI-LEVEL ADAPTATION METHODS

heading: 2.1 LAYER-WISE, UNIT-WISE AND PARAMETER-WISE ADAPTATION
text: In the paper on hyper-descent (Baydin et al., 2017), the learning rate is set to be a scalar. However, to make the most of learning rate adaptation, in this study, we introduce layer-wise or even parameterwise updating rules, where the learning rate αt in each iteration time step is considered to be a vector (layer-wise) or even a list of matrices (parameter-wise). For the sake of simplicity, we collect all the learning rates in a vector: αt = (α1,t, ..., αN,t)T . Correspondingly, the objective f(θ) is a function of θ = (θ1, θ2, ..., θN )T , collecting all the model parameters. In this case, the derivative of the objective function f with respect to each learning rate can be written as
∂f(θt−1) ∂αi,t−1 = ∂f(θ1,t−1, ..., θN,t−1) ∂αi,t−1 = N∑ j=1 ∂f(θ1,t−1, ..., θN,t−1) ∂θj,t−1 ∂θj,t−1 ∂αi,t−1 , (1)
where N is the total number of all the model parameters. Eq. (1) can be generalized to groupwise updating, where we associate a learning rate with a special group of parameters, and each parameter group is updated according to its only learning rate. Notice that although there is a dependency between αt−1 and θt−2 with: αt−1 = αt−2 − β∇f(θt−2), where β is the updating rate of hyper-gradient descent, we consider that αt−1 is calculated after θt−2 and thus a change of αt−1 will not result in a change of θt−2. Assume θt = u(Θt−1, α) is the updating rule, where Θt = {θs}ts=0 and α is the learning rate, then the basic gradient descent method for each group i gives θi,t = u(Θt−1, αi,t−1) = θi,t−1 − αi,t−1∇θif(θt−1). Hence for gradient descent
∂f(θt−1)
∂αi,t−1 = ∇θif(θt−1)T∇αi,t−1u(Θt−1, αi,t−1) = −∇θif(θt−1)T∇θif(θt−2). (2)
Here αi,t−1 is a scalar with index i at time step t − 1, corresponding to the learning rate of the ith group, while the shape of ∇θif(θ) is the same as the shape of θi. We particularly consider two special cases: (1) In layer-wise adaptation, θi is the weight matrix of ith layer, and αi is the particular learning rate for this layer. (2) In parameter-wise adaptation, θi corresponds to a certain parameter involved in the model, which can be an element of the weight matrix in a certain layer.

heading: 2.2 REGULARIZATION ON ADAPTIVE LEARNING RATES
text: The selection of adaptation level should depend on a case-by-case basis. Global or parameter-wise adaptation is usually not the optimal choice across all circumstances. Recall that for deep neural networks, we typically use a relatively large architecture with regularization. This idea can also be applied to learning rate space with parameter structure. To address over-parameterization in implementing lower-level learning rate adaptation, we introduce regularization on learning rates to control the flexibility. First, for layer-wise adaptation, we can add the following regularization term to the loss function
Llr_reg_layer = λlayer ∑ l (αl − αg)2, (3)
where l is the indices for each layer, λlayer is the layer-wise regularization coefficient, αl and αg are the layer-wise and global-wise adaptive learning rates. A larger λlayer can push each layer’s learning rate towards the global learning rate across all the layers. Given a particular αg,t, the gradient of the loss function with respect to the learning rate αl in layer l can be written as
∂Lfull(θ, α) ∂αl,t = ∂Lmodel(θ, α) ∂αl,t + ∂Llr_reg(θ, α) ∂αl,t
= ∇θlf(θt−1)T∇αl,t−1u(Θt−2, αt−1) + 2λlayer(αl,t − αg,t). (4)
Notice that the time step index of layer-wise regularization term is t rather than t− 1, which ensures that we push the layer-wise learning rates towards the corresponding global learning rates of the current step t. Denoting by hl,t−1 = −∇θlf(θt−1)T∇θlu(Θt−2, αl,t−1), then the updating rule for learning rates can be written as
αl,t = αl,t−1 − β ∂Lfull(θ, α)
∂αl,t = αl,t−1 − β(−hl,t−1 + 2λlayer(αl,t − αg,t)). (5)
Eq. (5) has a close form solution but only applicable in the two-levels case. However, there is an extra hyper-parameter λlayer to be tuned. In addition, when there are more levels, components of learning rates at different levels can be interdependent. To construct a workable updating scheme for Eq. (5), we replace αl,t and αg,t with their relevant approximations. We take the strategy of using their updated version without considering regularization, i.e., α̂l,t = αl,t−1 + βhl,t−1 and α̂g,t = αg,t−1 + βhg,t−1, where hg,t−1 = −∇θf(θt−1)T∇αg,t−1u(Θt−2, αg,t−1) is the global h for all parameters. Here we regard α̂l,t and α̂g,t as the “virtual” layer-wise and global-wise learning rates for time step t and taking them into the right-hand side of Eq. (5) gives the new updating rule as follows
α∗l,t = αl,t−1 + βhl,t−1 − 2βλlayer(α̂l,t − α̂g,t) = (1− 2βλlayer)α̂l,t + 2βλlayerα̂g,t. (6)
Notice that in Eq. (6), the two terms are actually a weighted average of the layer-wise learning rate α̂l,t and global learning rate α̂g,t at the current time step. Since we hope to push the layer-wise learning rates towards the global one, the parameters should meet the constraint: 0 < 2βλlayer < 1, and thus they can be optimized using hyper-parameter searching within a bounded interval as well as gradient-based hyper-parameter optimizations. We can also consider the case where three levels of learning rate adaptations are involved, including global-wise, layer-wise, and parameter-wise adaptation. If we introduce two more regularization terms to control the variation of parameter-wise learning rate with respect to layer-wise learning rate and global learning rates, the regularization loss can be written as
Llr_reg_para = λlayer ∑ l (αl − αg)2 + λpara_layer ∑ l ∑ p (αpl − αl)2 + λpara ∑ l ∑ p (αpl − αg)2,
where αpl is the learning rate for the p-th parameter inside layer l. The second and third terms push each parameter-wise learning rate towards the layer-wise learning rate and the global learning rates, respectively. Like the two-level case, the updating rule with this three-level regularization can be approximated by the weighted combination of three components under “virtual approximation”. The detail of the updating rule for the three-levels case is given by Algorithm 1 in Section 2.3. We also provided a discussion on the bias of implementing “virtual approximation” in Appendix A.1.
In general, we can organize all the learning rates in a tree structure. For example, in the three-level case above, αg will be the root node, while {αl} are the children node at level 1 of the tree and {αlp}
are the children node of αl as leaf nodes at level three of the tree. In a general case, we assume there are L levels in the tree. Denote the set of all the paths from the root node to each of leave nodes as P and a path is denoted by p = {α1, α2, ..., αL} where α1 is the root node, and αL is the left node on the path. On this path, denote ancestors(i) all the ancestor nodes of αi along the path, i.e., ancestors(i) = {α1, ..., αi−1}. We will construct a regularizer to push αi towards each of its parents. Then the regularization can be written as
Llr_reg = ∑ p∈P ∑ αi∈p ∑ αj∈ancestor(i) λij(αi − αj)2. (7)
Under this pair-wise L2 regularization, the updating rule for any leave node learning rate αL can be given by the following theorem whose proof is provided in Appendix A.2. Theorem 1. Under virtual approximation, the effect of applying pair-wise L2 regularization Eq. (7) results in performing a weighted linear combination of virtual learning rates at different levels α∗L = ∑L j=1 γjα̂j with ∑L j=1 γj = 1, where each component α̂j is calculated by assuming no regularization.
Remarks: Theorem 1 actually suggests that a similar updating rule can be obtained for the learning rate at any level on the path. All these have been demonstrated in Algorithm 1 for the three-level case.

heading: 2.3 PROSPECTIVE OF ADAPTIVE LEARNING RATE COMBINATION
text: Motivated by the analytical derivation in Section 2.2, we can consider combining adaptive learning rates at different levels as a substitute and approximation of regularization on the differences in learning rates. This makes the effect of learning rate regularization trainable with gradient-based methods. In a general form, assume that we have L levels, which could include global-level, layer-level, unit-level and parameter-level, etc, Theorem 1 suggests the following updating rule: αt = ∑L j=1 γjα̂j,t. In a more general form, we can implement non-linear models such as neural networks to model the final adaptive learning rates with respect to the learning rates at different levels:αt = g(α̂1,t, α̂2,t...α̂L,t; θ), where θ is the vector of parameters of the non-linear model. We can treat the combination weights {γ1, ..., γL} as trainable parameters, which can also be globally shared or parameter/layer-specific. In this study, we consider the globally shared combination weights. We only need these different levels of learning rate to have a hierarchical relationship to apply this method. For example, we can further introduce “filter level” to replace layer-level for the convolutional neural network if there is no clear layer structure, where the parameters in each filter will share the same learning rate.
As the real learning rates implemented in model parameter updating are weighted combinations, the corresponding gradient matrices cannot be directly used for learning rate updating. In this case, we first break down the gradient by the combined learning rate to three levels, use each of them to update the learning rate at each level, and then calculate the combination by the updated learning rates. Especially, hp,t, hl,t and hg,t are calculated by the gradients of model losses without regularization, as is shown in Eq. (8)1.
hp,t = ∂f(θ, α)
∂αp,t = −∇θf(θt−1, α)|p · ∇αu(Θt−2, α)|p
hl,t = ∂f(θ, α)
∂αl,t = −tr(∇θf(θt−1, α)|Tl ∇αu(Θt−2, α)|l)
hg,t = ∂f(θ, α)
∂αt = − n∑ l=1 tr(∇θf(θt−1, α)|Tl ∇αu(Θt−2, α)l)
(8)
where ht = ∑ l hl,t = ∑ p hp,t and hl,t = ∑ p∈lth layer hp and f(θ, α) corresponds to the model loss Lmodel(θ, α) in Section 2.2. Algorithm 1 is the full updating rules for the newly proposed optimizer with three levels, which can be denoted as combined adaptive multi-level hyper-gradient descent (CAM-HD). In Algorithm 1, we introduce the general form of gradient descent based optimizers (Reddi et al., 2018; Luo et al., 2018): for SGD, φt(g1, ...gt) = gt and ψt(g1, ...gt) = 1, while
1Here we use trace form to represent the sum of the element-wise product but compute in the simplest way.
Algorithm 1: Updating the rule of three-level CAM-HD input: α0, β, δ, T initialization: θ0, γ1,0, γ2,0, γ3,0, αp,0, αl,0, α0, α∗l,0 = γ1,0αp,0 + γ2,0αl,0 + γ3,0α0 for t ∈ 1, 2, ..., T do
gt = ∇θf(θ, α) Update hp,t, hl,t and hg,t by Eq. (8). αp,t = αp,t−1 − βp ∂f(θt−1)∂α∗p,t−1 ∂α∗p,t−1 ∂αp,t−1 = αp,t−1 − βpγ1,t−1hp,t
αl,t = αl,t−1 − βl ∑ p ∂f(θt−1) ∂α∗p,t−1 ∂α∗p,t−1 ∂αl,t−1 = αl,t−1 − βlγ2,t−1 ∑ p hp,t = αl,t−1 − βlγ2,t−1hl,t
αt = αt−1 − βg ∑ l ∑ p ∂f(θ) ∂α∗p,t−1 ∂α∗p,t−1 ∂αt−1
= αt−1 − βgγ3,t−1hg,t α∗p,t = γ1,t−1αp,t + γ2,t−1αl,t + γ3,t−1αt
γ1,t = γ1,t−1 − δ ∂L∂γ1,t−1 = γ1,t−1 − δ ∑ p ∂L ∂α∗p,t−1 ∂α∗p,t−1 ∂γ1,t−1 = γ1,t−1 − δαp,t−1 ∑ p ∂L ∂α∗p,t−1
γ2,t = γ2,t−1 − δ ∂L∂γ2,t−1 = γ2,t−1 − δ ∑ p ∂L ∂α∗p,t−1 ∂α∗p,t−1 ∂γ2,t−1 = γ1,t−1 − δαl,t−1 ∑ p ∂L ∂α∗p,t−1
γ3,t = γ3,t−1 − δ ∂L∂γ3,t−1 = γ3,t−1 − δ ∑ p ∂L ∂α∗p,t−1 ∂α∗p,t−1 ∂γ3,t−1 = γ3,t−1 − δαt−1 ∑ p ∂L ∂α∗p,t−1 γ1 = γ1/(γ1 + γ2 + γ3), γ2 = γ1/(γ1 + γ2 + γ3), γ3 = γ1/(γ1 + γ2 + γ3) mt = φt(g1, ...gt) Vt = ψt(g1, ...gt) θt = θt−1 − α∗p,tmt/ √ Vt
end return θT , γ1,T , γ2,T , γ3,T , αp,T , αl,T , αT
for Adam, φt(g1, ...gt) = (1 − β1)Σti=1β t−1 1 gi and ψt(g1, ...gt) = (1 − β2)diag(Σti=1β t−1 2 g 2 i ). Meanwhile, the corresponding u(Θt−2, α) should be changed accordingly. Notice that in each updating time step of Algorithm 1, we re-normalize the combination weights γ1, γ2 and γ3 to ensure that their summation is always 1 even after updating with stochastic gradient-based methods. An alternative way of doing this is to implement Softmax function. In addition, the training of γs can also be extended to multi-level cases, which means we can have different combination weights in different layers. For the updating rates βp, βl and βg of the learning rates at different levels, we set: βp = npβ = β, βl = nlβ, βg = nβ, where β is a shared parameter. This setting will make the updating steps of learning rates at different levels be on the same scale considering their difference in the number of parameters. An alternative way is to take the average based on the number of parameters in Eq. (8) at first.

heading: 2.4 CONVERGENCE ANALYSIS AND ALGORITHM COMPLEXITY
text: The proposed CAM-HD is not an independent optimization method, which can be applied in any gradient-based updating rules. Its convergence properties highly depend on the base optimizer that is applied. By referring to the discussion on convergence in (Baydin et al., 2017), we introduce κp,t = τ(t)α ∗ p,t + (1− τ(t))α∞, where the function τ(t) is selected to satisfy tτ(t)→ 0 as t→∞, and α∞ is a chosen constant value. Then we can demonstrate the convergence analysis for the three-level case in the following theorem.
Theorem 2 (Convergence under mild assumptions about f ). Suppose that f is convex and L-Lipschitz smooth with ‖∇pf(θ)‖ < Mp, ‖∇lf(θ)‖ < Ml, ‖∇gf(θ)‖ < Mg for some fixed Mp, Ml, Mg and all θ. Then θt → θ∗ if α∞ < 1/L where L is the Lipschitz constant for all the gradients and t · τ(t)→ 0 as t→∞, where the θt are generated according to (non-stochastic) gradient descent.
In the above theorem, ∇p is the gradient of target function w.r.t. a model parameter with index p, ∇l is the average gradient of target function w.r.t. parameters in a layer with index l, and∇g is the global average gradient of target function w.r.t. all model parameters. The proof of this theorem is given in Appendix A.3. Notice that when we introduce κp,t instead of α∗p,t in Algorithm 1, the corresponding gradients ∂L(θ)∂α∗p,t−1 will also be replaced by ∂L(θ) ∂κ∗p,t−1 ∂κ∗p,t−1 ∂α∗p,t−1 = ∂L(θ)∂κ∗p,t−1 τ(t).
We also made an analysis on the number of parameters and algorithm complexity (See Appendix A.4). Our method will not increase the number of model parameters but requires extra space complexity ∆T during training. Also it requires an extra time complexity but at least one-order smaller than training with baseline setting, while the absolute ratio is smaller than the inverse of batch size ∆TT << 1/mb.

heading: 3 EXPERIMENTS
text: We use the feed-forward neural network models and different types of convolutions neural networks on multiple benchmark datasets to compare with existing baseline optimizers.For each learning task, the following optimizers will be applied: (a) standard baseline optimizers such as Adam and SGD; (b) hyper-gradient descent in (Baydin et al., 2017); (c) L4 stepsize adaptation for standard optimizers (Rolinek and Martius, 2018); (d) Adabound optimizer (Luo et al., 2018); (e) RAdam optimizer (Liu et al., 2019); and (f) the proposed adaptive combination of different levels of hyper-descent. The implementation of (b) is based on the code provided with the original paper. For each experiment, we provide the average curve and standard error bar in each time step with ten runs.

heading: 3.1 HYPER-PARAMETER TUNING
text: To compare the effect of CAM-HD with baseline optimizers, we first do hyperparameter tuning for the model training process with baseline optimizers by referring to related papers (Kingma and Ba, 2015; Baydin et al., 2017; Rolinek and Martius, 2018; Luo et al., 2018) as well as implementing an independent grid search. We mainly consider the hyper-parameters of batch size, learning rate, and momentum for models with different architecture. The search space for batch size is the set of {2n}n=3,...,9, while the search space for learning rate, hyper-gradient updating rate and combination weight updating rate (CAM-HD-lr) are {10−1, ..., 10−4}, {10−1, ..., 10−10} and {10−1, ..., 10−4} respectively. The selection criterion is the 5-fold cross-validation loss by early-stopping at the patience of 3. The optimized hyper-parameters for the tasks in this paper are given in Table 1. For the learning tasks with recommended learning rate schedules, we will apply these schedules as well.

heading: 3.2 COMBINATION RATIO AND MODEL PERFORMANCES
text: First, we perform a study on the combination of different level learning rates. The simulations are based on image classification tasks on MNIST and CIFAR10 (LeCun et al., 1998; Krizhevsky and Hinton, 2012). One feed-forward neural network with three hidden layers of size [100, 100, 100] and two convolutional network models, including LeNet-5 (LeCun et al., 2015) and ResNet-18 (He et al., 2016), are implemented. We use full training sets of MNIST and CIFAR10 for training and full test sets for validation. In each case, two levels of learning rates are considered, which are the global and layer-wise adaptation for FFNN, and global and filter-wise adaptation for CNNs. Adam-CAM-HD optimizer is implemented in all three simulations. We change the combination weights of two levels in each case to see the change of model performance in terms of test classification accuracy at epoch 10, with the corresponding updating rate δ = 0. Another hyper-parameter setting follows Table 1. We conduct ten runs at each combination weights with different parameter initializations for all three simulations and draw the error bars for standard errors. The result is given in Figure 1. We can see that in all three cases, the optimal performance is neither at full global level nor full layer/filter level, but a combination of two levels of adaptive learning rates. Still, the differences between the endpoints
and the optimal combination in terms of model performance have some statistical significance level. This supports our analysis in Section 2.2. Also, in real training processes, it is possible that the learning in favor of different combination weights in various stages and this requires the online updating of the combination weights.

heading: 3.3 FEED FORWARD NEURAL NETWORK FOR IMAGE CLASSIFICATION
text: This experiment is conducted with feed-forward neural networks for image classification on MNIST, including 60,000 training examples and 10,000 test examples. We use the full training set for training and the full test set for validation. Three FFNN with three different hidden layer configurations are implemented, including [100, 100], [1000, 100], and [1000, 1000]. Adaptive optimizers including Adam, Adam-HD with two hyper-gradient updating rates, and proposed Adam-CAM-HD are applied. For Adam-CAM-HD, we apply three-level parameter-layer-global adaptation with initialization of γ1 = γ2 = 0.3 and γ3 = 0.4, and two-level layer-global adaptation with γ1 = γ2 = 0.5. Figure 2 shows the validation accuracy for different optimizers during the training process of 30 epochs. We can learn that both the two-level and three-level Adam-CAM-HD outperform the baseline Adam optimizer with optimized hyper-parameters significantly. For Adam-HD, we find that the default hyper-gradient updating rate (10−7) for Adam applied in (Baydin et al., 2017) is not optimal in our experiments, while an optimized one of 10−9 can outperform Adam but still worse than Adam-CAM-HD with default hyper-gradient updating rate (10−7).

heading: 3.4 LENET-5 FOR IMAGE CLASSIFICATION
text: The second experiment is done with LeNet-5, an early-year convolutional neural network without involving many building and training tricks. We compare a set of adaptive Adam optimizers including Adam, Adam-HD, Adam-CAM-HD, and L4 for the image classification learning task of MNIST, CIFAR10 and SVHN (Netzer et al., 2011). For Adam-CAM-HD, we apply a two-level setting with filter-wise and global learning rates adaptation and initialize γ1 = 0.2, γ2 = 0.8. We also implement an exponential decay function τ(t) = exp(−rt) as was discussed in Section 2.4 with rate r = 0.002, while t is the number of iterations. For L4, we implement the recommended L4 learning rate of 0.15. For Adabound and RAdam, we also apply the recommended hyper-parameters in the original
papers. The other hyper-parameter settings are optimized in Table 1. As we can see in Figure 3,
Adam-CAM-HD again shows the advantage over other methods in all the three sub-experiments, except MNIST L4 that could perform better in a later stage. The experiment on CIFAR10 and SVHN indicates that the recommended hyper-parameters for Adabound, RAdam and L4 could fail in some cases with unstable accuracy curves. On the other hand, Adam-HD can not significantly outperform Adam with the recommended and optimized hyper-gradient updating rate shared with Adam-CAM-HD. The corresponding summary of test performance is given in Table 2, in which the test accuracy of Adam-CAM-HD outperform other optimizers on both CIFAR10 and SVHN. Especially, it gives significantly better results than Adam and Adam-HD for all the three datasets.

heading: 3.5 RESNET FOR IMAGE CLASSIFICATION
text: In the third experiment, we apply ResNets for image classification task on CIFAR10. We compare Adam and its adaptive optimizers, as well as SGD with Nestorov momentum (SGDN) and corresponding adaptive optimizers for training both ResNet-18 and ResNet-34. For SGDN methods, we apply a learning rate schedule, in which the learning rate is initialized to a default value of 0.1 and reduced to 0.01 or 10% (for SGDN-CAM-HD) after epoch 150. The momentum is set to be 0.9 for all SGDN methods. For Adam-CAM-HD SGDN-CAM-HD, we apply two-level CAM-HD with the same setting as the second experiment. In addition, we apply an exponential decay function with a decay rate r = 0.001. The validation accuracy results, training loss, and validation loss are shown in Figure 4. We can see that the validation accuracy of Adam-CAM-HD reaches about 90% in 40 epochs and consistently outperforms Adam, L4 and Adam-HD optimizers in a later stage. The L4 optimizer with recommended hyper-parameter and an optimized weight-decay rate of 0.0005 (instead of 1e-4 applied in other Adam-based optimizers) can outperform baseline Adam for both ResNet-18 and ResNet-34, while its training loss outperforms all other methods but with potential over-fitting. Adam-HD achieves better training loss than Adam after epoch 100. However, we find that the validation performance is not good with a default hyper-gradient coefficient of 10−8 (shared with Adam-CAM-HD). Instead, an optimized coefficient of 10−9 can make a safe but small improvement from Adam. RAdam performs slightly better than Adam-CAM-HD in terms of validation accuracy, but the validation cross-entropy of both RAdam and Adabound are worse than our method. Also, we find that in training ResNet-18/34, the validation accuracy and validation loss of SGDN-CAM-HD slightly outperform SGDN in most epochs even after the resetting of the learning rate at epoch 150.
The test performances of different optimizers for ResNet-18 and ResNet-34 after 200 epoch of training are shown in Table 3. Notice that the results of SGDN and SGDN-CAM-HD are achieved with a piece-wise constant learning rates schedule, while the results of Adam-based optimizers are achieved without a learning rate schedule. We can learn that the proposed CAMHD method can improve the corresponding baseline method (Adam, Adam-HD and SGDN)
with statistical significance in almost every case. Adam-CAM-HD performs a bit worse than RAdam but comparable to Adabound in terms of the average test accuracy for both ResNet-18 and ResNet-34. As a higher-level adaptation method, CAM-HD can be applied on top of RAdam/Adabound/L4 for further improvement.

heading: 4 CONCLUSION
text: In this study, we propose a gradient-based learning rate adaptation strategy by introducing hierarchical multiple-level learning rates in deep neural networks. By considering the relationship between regularization and the combination of adaptive learning rate at different levels, we further propose a joint algorithm for adaptively learning each level’s combination weight. Experiments on FFNN, LeNet-5, and ResNet-18/34 indicate that the proposed methods can outperform the standard ADAM/SGDN and other baseline methods with statistical significance. Although the advantage is not fully guaranteed, our method achieves a higher adaptation level and can be continuously reduced to baseline methods under a specific set of hyper-parameters. This could bring more thoughts and further study on implementing a hierarchical learning rate system for deep neural networks.

heading: A APPENDIX FOR PAPER: ADAPTIVE MULTI-LEVEL HYPER-GRADIENT DESCENT

heading: A.1 ANALYSIS ABOUT VIRTUAL APPROXIMATION
text: Consider the difference between Eq. (5) and Eq. (6) in the paper: α∗l,t − αl,t = −2βλlayer((α̂l,t − α̂g,t)− (αl,t − αg,t)). (9)
Based on the setting of multi-level adaptation, on the right-hand side of Eq. (9), global learning rate is updated without regularization α̂g,t = αg,t. For the layer-wise learning rates, the difference is given by α̂l,t − αl,t = 2βλlayer(αl,t − αg,t), which corresponds to the gradient with respect to the regularization term. Thus, Eq. (9) can be rewritten as:
α∗l,t − αl,t = −2βλlayer(2βλlayer(αl,t − αg,t)) = −4β2λ2l (1− αg,t αl,t )αl,t (10)
which is the error of the virtual approximation introduced in Eq. (6) in the paper. If 4β2λ2l << 1 orαg,t αl,t → 1, this approximation becomes accurate. Another way for handling Eq. (4) in the paper is to implement the previous-step learning rates in the regularization term. αl,t ≈ αl,t−1 − β(−hl,t−1 + 2λlayer(αl,t−1 − αg,t−1)). (11)
Since we have αl,t = α̂l,t−2βλlayer(αl,t−αg,t) and α̂l,t = αl,t−1 +βhl,t−1, using the learning rates in the last step for regularization will introduce a higher variation from term βhl,t−1, with respect to the true learning rates in the current step. Thus, we consider the proposed virtual approximation works better than last-step approximation.

heading: A.2 PROOF OF THEOREM 1:
text: Proof. Consider the learning regularizer Llr_reg(α) = ∑ p∈P ∑ αi∈p ∑ αj∈parents(i) λij(αi − αj)2. (12)
To apply hyper-gradient descent method to update the learning rate αL at level L, we need to work out the derivative of Llr_reg with respect to αL. The terms in Eq. (12) involving αL are only (αi − αj)2 where αj is an ancestor on the path from the root to the leave node αL. Hence
∂Lfull(θ, α) ∂αL,t = ∂Lmodel(θ, α) ∂αL,t + ∂Llr_reg(α) ∂αL,t
= −∇θLf(θt−1)T∇θLu(Θt−2, αt−1) + ∑
αj∈acenstors(L)
2λLj(αL,t − αj,t). (13)
As there are exactly L − 1 ancestors on the path, we can simply use the index j = 1, 2, ..., L − 1. The corresponding updating function for αn,t is:
αL,t = αn,t−1 − β(hL + L−1∑ j=1 2λLj(αL,t − αj,t))
≈ α̂L,t(1− 2β L−1∑ j=1 λLjαn,t) + L−1∑ j=1 (2βλLjα̂j,t))
= L∑ j=1 γjα̂j,t.
(14)
where
γL = 1− 2β L−1∑ j=1 λLj ,
γj = 2βλLj , for j = 1, 2, ..., L− 1.
(15)
This form satisfies α∗L = ∑L j=1 γjα̂j with ∑L j=1 γj = 1. This completes the proof.

heading: A.3 PROOF OF THEOREM 2:
text: Proof. We take three-level’s case discussed in Section 2 for example, which includes global level, layer-level and parameter-level. Suppose that the target function f is convex, L-Lipschitz smooth at all levels, which means for all θ1 and θ2:
||∇pf(θ1)−∇pf(θ2)|| ≤ Lp||θ1 − θ2|| ||∇lf(θ1)−∇lf(θ2)|| ≤ Ll||θ1 − θ2|| ||∇gf(θ1)−∇gf(θ2)|| ≤ Lg||θ1 − θ2|| L = max{Lp, Ll, Lg}
(16)
and its gradient with respect to parameter-wise, layer-wise, global-wise parameter groups satisfy ‖∇pf(θ)‖ < Mp, ‖∇lf(θ)‖ < Ml, ‖∇gf(θ)‖ < Mg for some fixed Mp, Ml, Mg and all θ. Then the effective combined learning rate for each parameter satisfies:
|α∗p,t| = |γp,t−1αp,t + γl,t−1αl,t + γg,t−1αt|
≤ (γp,t−1 + γl,t−1 + γg,t−1)α0 + β t−1∑ i=0 ( γp,t−1np max p {|∇f(θp,i+1)T∇f(θp,i)|}
+γl,t−1nl max l {|∇f(θl,i+1)T∇f(θl,i)|}+ γg,t−1|∇f(θg,i+1)T∇f(θg,i)| ) ≤ α0 + β
t−1∑ i=0 ( γp,t−1np max p {‖∇f(θp,i+1)‖‖∇f(θp,i)‖}
+γl,t−1nl max l {‖∇f(θl,i+1)‖‖∇f(θl,i)‖}+ γg,t−1‖∇f(θg,i+1)‖‖∇f(θg,i)‖ ) ≤ α0 + tβ(npM2p + nlM2l +M2g )
(17)
where θp,i refers to the value of parameter indexed by p at time step i, θl,i refers to the set/vector of parameters in layer with index l at time step i, and θg,i refers to the whole set of model parameters at time step i. In addition, np and nl are the total number of parameters and number of the layers, and we have applied 0 < γp, γl, γg < 1. This gives an upper bound for the learning rate in each particular time step, which is O(t) as t → ∞. By introducing κp,t = τ(t)α∗p,t + (1 − τ(t))α∞, where the function τ(t) is selected to satisfy tτ(t) → 0 as t → ∞, so we have κp,t → α∞ as t → ∞. If α∞ < 1 L , for larger enough t, we have 1/(L+ 1) < κp,t < 1/L, and the algorithm converges when the corresponding gradient-based optimizer converges for such a learning rate under our assumptions about f . This follows the discussion in (Karimi et al., 2016; Sun, 2019).

heading: A.4 ALGORITHM COMPLEXITY

heading: A.4.1 NUMBER OF PARAMETERS AND SPACE COMPLEXITY
text: The proposed adaptive optimizer is for efficiently updating the model parameters, while the final model parameters will not be increase by introducing CAM-HD optimizer. However, during the training process, several extra intermediate variables are introduced. For example, in the discussed three-level’s case for feed-forward neural network with nlayer layers, we need to restore hp,t, hl,t and hg,t, which have the sizes of S(hp,t) = ∑nlayer−1 l=1 (nl + 1)nl+1, S(hl,t) = nlayer and S(hg,t) = 1, respectively, where ni is the number of units in ith layer. Also, learning rates αp,t, αl,t, αg,t and take the sizes of S(ap,t) = ∑nlayer−1 l=1 (nl + 1)nl+1, S(al,t) = nlayer, S(ag,t) = 1, S(ag,t) = 1, and
S(a∗p,t) = ∑nlayer−1 l=1 (nl + 1)nl+1, respectively. Also we need a small set of scalar parameters to restore γ1, γ2 and γ3 and other coefficients.
Consider the fact that in training the baseline models, we need to restore model parameters, corresponding gradients, as well as the intermediate gradients during the implementation of chain rule, CAM-HD will take twice of the space for storing intermediate variables in the worst case. For two-level learning rate adaptation considering global and layer-wise learning rates, the extra space complexity by CAM-HD will be one to two orders’ smaller than that of baseline model during training.

heading: A.4.2 TIME COMPLEXITY
text: In CAM-HD, we need to calculate gradient of loss with respect to the learning rates at each level, which are hp,t, hl,t and hg,t in three-level’s case. However, the gradient of each parameter is already known during normal model training, the extra computational cost comes from taking summations and updating the lowest-level learning rates. In general, this cost is in linear relation with the number of differentiable parameters in the original models. Here we discuss the case of feed-forward networks and convolutional networks.
Recall that for feed-forward neural network the whole computational complexity is:
T (n) = O(m · niter · nlayer∑ l=2 nl · nl−1 · nl−2) (18)
where m is the number of training examples, niter is the iterations of training, and nl is the number of units in the l-th layer. On the other hand, when using three-level CAM-HD with, where the lowest level is parameter-wise, we need nlayer element products to calculate hp,t for all layers, one nlayer matrix element summations to calculate hl,t for all layers, as well as a list summation to calculate hg,t. In addition, two element-wise summations will also be implemented for calculating αp,t and α∗p. Therefore, the extra computational cost of using CAM-HD is ∆T (n) = O(nb · niter ∑nlayer l=2 (nl · nl−1 + nl)), where nb is the number of mini-batches for training. Notice that mb = m/nb is the batch size, which is usually larger than 100. This extra cost is more than one-order smaller than the computational complexity of training a model without learning rate adaptation. For the cases when the lowest level is layer-wise, only one element-wise matrix product is needed in each layer to calculate hl,t. For convolutional neural networks, we have learned that the total time complexity of all convolutional layers is (He and Sun, 2015):
O(nb · niter · nconv_layer∑
l=1
(nl−1 · s2l · nl ·m2l )) (19)
where l is the index of a convolutional layer, and nconv_layer is the depth (number of convolutional layers). nl is the number of filters in the l-th layer, while nl−1 is known as the number of input channels of the l-th layer. sl is the spatial size of the filter. ml is the spatial size of the output feature map. If we consider convolutional filters as layers, the extra computational cost for CAM-HD in this case is ∆T (n) = O(nb · niter ∑nconv_layer l=1 ((nl−1 · s2l + 1) · nl)), which is still more than one order smaller than the cost of model without learning rate adaptation.
Therefore, for large networks, applying CAM-HD will not significantly increase the computational cost from the theoretical prospective.

heading: A.5 SUPPLEMENTARY EXPERIMENTAL RESULTS

heading: A.5.1 LEARNING OF COMBINATION WEIGHTS
text: The following figures including Figure 5, Figure 6, Figure 7 and Figure 8 give the learning curves of combination weights with respect to the number of training iterations in each experiments, in which each curve is averaged by 5 trials with error bars. Through these figures, we can compare the updating curves with different models, different datasets and different CAM-HD optimizers.
Figure 5 corresponds to the experiment of FFNN on MNIST in Section 3.3, which is a three-level case. We can see that for different FFNN architecture, the learning behaviors of γs also show different patterns, although trained on a same dataset. Meanwhile, the standard errors for multiple trials are much smaller relative to the changes of the average combination weight values.
Figure 6 corresponds to the learning curves of γs in the experiments of LeNet-5 for MNIST image classification with SGD, SGDN and Adam, which are trained on 10% of original training dataset.
In addition, Figure 7 corresponds to the learning curves of γs in the experiments of LeNet-5 for CIFAR10 and SVHN image classification with Adam-CAM-HD.
As is shown in Figure 6, for SGD-CAM-HD, SGDN-CAM-HD and Adam-CAM-HD, the equilibrium values of combination weights are different from each other. Although the initialization γ1 = 0.2, γ2 = 0.8 and the updating rate δ = 0.03 are set to be the same for the three optimizers, the values of γ1 and γ2 only change in a small proportion when training with Adam-CAM-HD, while the change is much more significant towards larger filter/layer-wise adaptation when SGD-CAM-HD or SGDN-CAM-HD is implemented. The numerical results show that for SGDN-CAM-HD, the average value of weight for layer-wise adaptation γ1 jumps from 0.2 to 0.336 in the first epoch, then drop back to 0.324 before keeping increasing till about 0.388. For Adam-CAM-HD, the average γ1 moves from 0.20 to 0.211 with about 5% change. In Figure 7, both the two subplots are models trained with Adam-CAM-HD. For the updating curves in Figure 7(a), which is trained on CIFAR10 with Adam-CAM-HD, the combination weight for filter-wise adaptation moves from 0.20 to 0.188. Meanwhile, for the updating curves in Figure 7(b), which is trained on SVHN, the combination weight for filter-wise adaptation moves from 0.20 to 0.195.
The similar effect can also be observed from the learning curves of γs for ResNet-18, which is given in Figure 8 and we only take the first 8,000 iterations. Again, we find that in training ResNet-18 on CIFAR10, the combination weights of SGD/SGDN-CAM-HD change much faster than that of Adam-CAM-HD. There are several reasons for this effect: First, in the cases when γs do not move significantly, we apply Adam-CAM-HD, where the main learning rate (1e-3) is only about 1%-6% of the learning rate of SGD or SGDN (1e-1). In Algorithm 1, we can see that the updating rate of γs is in proportion of alpha given other terms unchanged. Thus, for the same tasks, if the same value of updating rate δ is applied, the updating scale of γs for Adam-CAM-HD can be much smaller than that for SGDN-CAM-HD. Second, this does not mean that if we apply a much larger δ for Adam-CAM-HD, the combination weights will still not change significantly or the performance will not be improved. It simply means that using a small δ can also achieve good performance due to the goodness of initialisation points. Third, it is possible that Adam requires lower level of combination ratio adaptation for the same network architecture compared with SGD/SGDN due to the fact that Adam itself involves stronger adaptiveness.

heading: A.5.2 OTHER EXPERIMENTAL RESULTS
text: In Figure 2, Figure 3 and Figure 4 of the paper, we have shown the curves of validation accuracies to compare different adaptive optimizers in a variety of learning tasks. Here we further provide the training and validation cross-entropy loss curves for corresponding methods in these tasks. Figure 8 is the full results of FFNNs, and Figure 9 is the results of LeNet-5.

Review summaries:
Setting appropriate learning rate for network optimization is an important task in deep learning applications. This paper investigates the setting of learning rates for network parameters in different levels, e.g., individual parameter, each layer and global levels. By setting the constraints on the learning rates at multiple scales, the paper derived a hierarchical learning rate setting approach, which is the combination of adaptive learning rates at different levels.