Title: ONLINE HYPERPARAMETER ADAPTATION VIA AMORTIZED PROXIMAL OPTIMIZATION

Abstract: Effective performance of neural networks depends critically on effective tuning of optimization hyperparameters, especially learning rates (and schedules thereof). We present Amortized Proximal Optimization (APO), which takes the perspective that each optimization step should approximately minimize a proximal objective (similar to the ones used to motivate natural gradient and trust region policy optimization). Optimization hyperparameters are adapted to best minimize the proximal objective after one weight update. We show that an idealized version of APO (where an oracle minimizes the proximal objective exactly) achieves global convergence to stationary point and locally second-order convergence to global optimum for neural networks. APO incurs minimal computational overhead. We experiment with using APO to adapt a variety of optimization hyperparameters online during training, including (possibly layer-specific) learning rates, damping coefficients, and gradient variance exponents. For a variety of network architectures and optimization algorithms (including SGD, RMSprop, and K-FAC), we show that with minimal tuning, APO performs competitively with carefully tuned optimizers.

1. INTRODUCTION:

Tuning optimization hyperparameters can be crucial for effective performance of a deep learning system. Most famously, carefully selected learning rate schedules have been instrumental in achieving state-of-the-art performance on challenging datasets such as ImageNet (Goyal et al., 2017) and WMT (Vaswani et al., 2017) . Even algorithms such as RMSprop (Tieleman & Hinton, 2012) and Adam (Kingma & Ba, 2015) , which are often interpreted in terms of coordinatewise adaptive learning rates, still have a global learning rate parameter which is important to tune. A wide variety of learning rate schedules have been proposed (Schraudolph, 1999; Li & Malik, 2016; Baydin et al., 2017) . Seemingly unrelated phenomena have been explained in terms of effective learning rate schedules (van Laarhoven, 2017) . Besides learning rates, other hyperparameters have been identified as important, such as the momentum decay factor (Sutskever et al., 2013) , the batch size (Smith et al., 2017) , and the damping coefficient in second-order methods (Martens & Grosse, 2015; Martens, 2010) .

There have been many attempts to adapt optimization hyperparameters to minimize the training error after a small number of updates (Schraudolph, 1999; Andrychowicz et al., 2016; Baydin et al., 2017) . This approach faces two fundamental obstacles: first, learning rates and batch sizes have been shown to affect generalization performance because stochastic updates have a regularizing effect (Dinh et al., 2017; Li et al., 2017; Mandt et al., 2017; Smith & Le, 2018; van Laarhoven, 2017) . Second, minimizing the short-horizon expected loss encourages taking very small steps to reduce fluctuations at the expense of long-term progress (Wu et al., 2018) . While these effects are specific to learning rates, they present fundamental obstacles to tuning any optimization hyperparameter, since basically any optimization hyperparameter somehow influences the size of the updates.

In this paper, we take the perspective that the optimizer's job in each iteration is to approximately minimize a proximal objective which trades off the loss on the current batch with the average change in the predictions. Specifically, we consider proximal objectives of the form J(φ) = h(f (g(θ, φ))) + λD(f (θ), f (g(θ, φ))), where f is a model with parameters θ, h is an approximation to the objective function, g is the base optimizer update with hyperparameters φ, and D is a distance metric. Indeed, approximately solving such a proximal objective motivated the natural gradient algorithm (Amari, 1998) , as well as proximal reinforcement learning algorithms (Schulman et al., 2017; 2015) . We introduce Amortized Proximal Optimization (APO), an approach which adapts optimization hyperparameters to minimize the proximal objective in each iteration. We use APO to tune hyperparameters of SGD, RMSprop, and K-FAC; the hyperparameters we consider include (possibly layer-specific) learning rates, damping coefficients, and the power applied to the gradient covariances.

Notice that APO has a hyperparameter λ which controls the aggressiveness of the updates. We believe such a hyperparameter is necessary until the aforementioned issues surrounding stochastic regularization and short-horizon bias are better understood. However, in practice we find that by performing a simple grid search over λ, we can obtain automatically-tuned learning rate schedules that are competitive with manual learning rate decay schedules. Furthermore, APO can automatically adapt several optimization hyperparameters with only a single hand-tuned hyperparameter.

We provide theoretical justification for APO by proving strong convergence results for an oracle which solves the proximal objective exactly in each iteration. In particular, we show global linear convergence and locally quadratic convergence under mild assumptions. These results motivate the proximal objective as a useful target for meta-optimization.

We evaluate APO on real-world tasks including image classification on MNIST, CIFAR-10, CIFAR-100, and SVHN. We show that adapting learning rates online via APO yields faster training convergence than the best fixed learning rates for each task, and is competitive with manual learning rate decay schedules. Although we focus on fast optimization of the training objective, we also find that the solutions found by APO generalize at least as well as those found by fixed hyperparameters or fixed schedules.

2. AMORTIZED PROXIMAL OPTIMIZATION:

We view a neural network as a parameterized function z = f (x, θ), where x is the input, θ are the weights and biases of the network, and z can be interpreted as the output of a regression model or the un-normalized log-probabilities of a classification model. Let the training dataset be {(x i , t i )} N i=1 , where input x i is associated with target t i . Our goal is to minimize the loss function:

EQUATION

)

where Z is the matrix of network outputs on all training examples x 1 , . . . , x N , and T is the vector of labels. We design an iterative optimization algorithm to minimize Eq. 1 under the following framework: in the kth iteration, one aims to update θ to minimize the following proximal objective:

EQUATION

where x is the data used in the current iteration, P is the distribution of data, θ k is the parameters of the neural network at the current iteration, h(•) is some approximation of the loss function, and D(•, •) represents the distance between network outputs under some metric (for notational convenience, we use mini-batch size of 1 to describe the algorithm). We first provide the motivation for this proximal objective in Section 2.1; then in Section 2.2, we propose an algorithm to optimize it in an online manner.

2.1. MOTIVATION FOR THE PROXIMAL OBJECTIVE:

In this section, we show that by approximately minimizing simple instances of Eq. 2 in each iteration (similar to Schulman et al. (2015) ), one can recover the classic Gauss-Newton algorithm and Natural Gradient Descent (Amari, 1998) . In general, updating θ so as to minimize the proximal objective is impractical due to the complicated nonlinear relationship between θ and z. However, one can find an approximate solution by linearizing the network function:

EQUATION

where J = ∇ θ f (x, θ) is the Jacobian matrix. We consider the following instance of Eq. 2:

EQUATION

where ∆z f (x, θ) -f (x, θ k ) is the change of network output, t is the label of current data x. Here h(•) is defined as the first-order Taylor approximation of the loss function. Using the linear approximation (Eq. 3), and a local second-order approximation of D, this proximal objective can be written as:

EQUATION

where

J = ∇ θ f (x, θ k ) is the Jacobian matrix on data x, ∇ 2 D ∇ 2 zD(z, f (x, θ k ))

is the Hessian matrix of the dissimilarity measured at z = f (x, θ k ).

Solving Eq. 5 yields:

EQUATION

where G E x∼P J ∇ 2 DJ is the pre-conditioning matrix. Different settings for the dissimilarity term D yield different algorithms. When

D(z, zk ) = z -zk 2 2

(7) is defined as the squared Euclidean distance, Eq. 6 recovers the classic Gauss-Newton algorithm.

EQUATION

8) is defined as the Bregman divergence, Eq. 6 yields the Generalized Gauss-Newton (GGN) method. When the output of neural network parameterizes an exponential-family distribution, the dissimilarity term can be defined as Kullback-Leibler divergence:

EQUATION

in which case Eq. 6 yields Natural Gradient Descent (Amari, 1998) . Since different versions of our proximal objective lead to various efficient optimization algorithms, we believe it is a useful target for meta-optimization.

2.2. AMORTIZED OPTIMIZATION:

Although optimizers including the Gauss-Newton algorithm and Natural Gradient Descent can be seen as ways to approximately solve Eq. 2, they rely on a local linearization of the neural network and usually require more memory and more careful tuning in practice. We propose to instead directly minimize Eq. 2 in an online manner.

Finding good hyperparameters (e.g., the learning rate for SGD) is a challenging problem in practice.

We propose to adapt these hyperparameters online in order to best optimize the proximal objective. Consider any optimization algorithm (base-optimizer) of the following form: θ ← g(x, t, θ, ξ, φ).

(10) Here, θ is the set of model parameters, x is the data used in this iteration, t is the corresponding label, ξ is a vector of statistics computed online during optimization, and φ is a vector of optimization hyperparameters to be tuned. For example, ξ contains the exponential moving averages of the squared gradients of the parameters in RMSprop. φ usually contains the learning rate (global or layer-specific), and possibly other hyperparameters dependent on the algorithm.

For each step, we formulate the meta-objective from Eq. 2 as follows (for notational convenience we omit variables other than θ and φ of g):

J (φ) = h(f (x, g(θ, φ))) + λ E x∼P [D(f (x, g(θ, φ)), f (x, θ))].

(11) Here, x is a random mini-batch sampled from the data distribution P. We compute the approximation to the loss, h, using the same mini-batch as the gradient of the base optimizer, to avoid the short horizon bias problem (Wu et al., 2018) ; we measure D on a different mini-batch to avoid instability that would result if we took a large step in a direction that is unimportant for the current batch, but important for other batches. The hyperparameters φ are optimized using a stochastic gradient-based algorithm (the meta-optimizer) using the gradient ∇ φ J(φ) (similar in spirit to (Schraudolph, 1999; Maclaurin et al., 2015) ). We refer to our framework as Amortized Proximal Optimization (APO). The simplest version of APO, which uses SGD as the meta-optimizer, is shown in Algorithm 1. One can choose any meta-optimizer; we found that RMSprop was the most stable and best-performing meta-optimizer in practice, and we used it for all our experiments.

Algorithm 1: Amortized Proximal Optimization (SGD as meta-optimizer)

Input : η, θ 0 , φ 0 , M , T Output: θ θ ← θ 0 φ ← φ 0 for i ← 1, . . . , M do sample data (x, t) for t ← 1, . . . , T do sample x ∼ P J(φ) = h(f (x, g(x, t, θ, ξ, φ))) + λD(f (x, g(x, t, θ, ξ, φ)), f (x, θ)) φ ← φ -η∇ φ J(φ) end θ ← g(x, t, θ, ξ, φ) end return θ

3. ANALYSIS OF AN IDEALIZED VERSION:

When considering optimization meta-objectives, it is useful to analyze idealized versions where the meta-objective is optimized exactly (even when doing so is prohibitively expensive in practice). For instance, Wu et al. (2018) analyzed an idealized SMD algorithm, showing that even the idealized version suffered from short-horizon bias. In this section, we analyze two idealized versions of APO where an oracle is assumed to minimize the proximal objective exactly in each iteration. In both cases, we obtain strong convergence results, suggesting that our proximal objective is a useful target for meta-optimization.

We view the problem in output space (i.e., explicitly designing an update schedule for z i ). Consider the space of outputs on all training examples; when we train a neural network, we are optimizing over a manifold in this space:

M = {(f (x 1 , θ), f (x 2 , θ), . . . , f (x N , θ)) | θ ∈ R D } (12)

We assume that f is continuous, so that M is a continuous manifold. Given an oracle that for each iteration exactly minimizes the expectation of proximal objective Eq. 2 over the dataset, we can write one iteration of APO in output space as:

EQUATION

where z i is ith column of Z, corresponding to the network output on data x i after update, z k,i is the current network output on data x i .

3.1. PROJECTED GRADIENT DESCENT:

We first define the proximal objective as Eq. 4, using the Euclidean distance as the dissimilarity measure, which corresponds to Gauss-Newton algorithm under the linearization of network. With an oracle, this proximal objective leads to projected gradient descent:

EQUATION

)

Consider a loss function on one data point (z) : R d → R, where d is the dimension of neural network's output. 1 We say the gradient is L-Lipschitz if:

∇ z (z 1 ) -∇ z (z 2 ) ≤ L z 1 -z 2 . (A1)

When the manifold M is smooth, a curve in M is called geodesic if it is the shortest curve connecting the starting and the ending point. We say M have a C-bounded curvature if for each trajectory v(t) : [0, 1] → R d going along some geodesic and v(t) 2 = 1, there is v(t) ≤ C with spectral norm. For each point Z ∈ M, consider the tangent space at point Z as T Z M. We call the projection of ∇ L(Z) onto the hyperplane T Z M as the effective gradient of L at Z ∈ M. It is worth noting that zero effective gradient corresponds to stationary point of the neural network.

We have the following theorem stating the global convergence of Eq. 14 to stationary point: Theorem 1. Assume the loss satisfies A1. Furthermore, assume L is lower bounded by L * and has gradient norm upper bound G. Let g * T be the effective gradient in the first T iterations with minimal norm. When the manifold is smooth with C-bounded curvature, with λ ≥ {CG, L 4 }, the norm of g * T converges with rate O 1 T as:

EQUATION

This convergence result differs from usual neural network convergence results, because here the Lipschitz constants are defined for the output space, so they are known and generally nice. For instance, L = 1 when we use a quadratic loss. In contrast, the gradient is in general not Lipschitz continuous in weight space for deep networks.

3.2. PROXIMAL NEWTON METHOD:

We further replace the dissimilarity term with:

EQUATION

which is the second-order approximation of Eq. 8. With a proximal oracle, this variant of APO turns out to be Proximal Newton Method in the output space, if we set λ = 1 2 :

EQUATION

where

Z -Z k 2

H is the norm with local Hessian as metric. In general, Newton's method can't be applied directly to neural nets in weight space, because it is nonconvex (Dauphin et al., 2014) . However, Proximal Newton Method in output space can be efficient given a strongly convex loss function.

Consider a loss (z) with µ-strongly convex:

(z) -(z * ) ≥ µ 2 z -z * 2 , (A2)

where z * is the unique minimizer and µ is some positive real number, and L H -smooth Hessian: for any vector v ∈ R d such that v = 1, there is:

∇ 2 z (z 1 )v -∇ 2 z (z 2 )v ≤ L H z 1 -z 2 . (A3)

The following theorem suggests the locally fast convergence rate of iteration Eq. 17: Theorem 2. Under assumptions A2 and A3, if the unique minimum Z * ∈ M, then whenever iteration (17) converges to Z * , it converges locally quadratically2 :

lim k→∞ Z k+1 -Z * Z k -Z * 2 ≤ L H µ .

Hence, the proximal oracle achieves second-order convergence for neural network training under fairly reasonable assumptions. Of course, we don't expect practical implementations of APO (or any other practical optimization method for neural nets) to achieve the second-order convergence rates, but we believe the second-order convergence result still motivates our proximal objective as a useful target for meta-optimization.

4. RELATED WORK:

Finding good optimization hyperparameters is a longstanding problem (Bengio, 2012) . Classic methods for hyperparameter optimization, such as grid search, random search, and Bayesian optimization (Snoek et al., 2012; 2015; Swersky et al., 2014) , are expensive, as they require performing many complete training runs, and can only find fixed hyperparameter values (e.g., a constant learning rate). Hyperband (Li et al., 2016) can reduce the cost by terminating poorly-performing runs early, but is still limited to finding fixed hyperparameters. Population Based Training (PBT) (Jaderberg et al., 2017) trains a population of networks simultaneously, and throughout training it terminates poorly-performing networks, replaces their weights by a copy of the weights of a better-performing network, perturbs the hyperparameters, and continues training from that point. PBT can find a coarse-grained learning rate schedule, but because it relies on random search, it is far less efficient than gradient-based meta-optimization.

There have been a number of approaches to gradient-based adaptation of learning rates. Gradientbased optimization algorithms can be unrolled as computation graphs, allowing the gradients of hyperparameters such as learning rates to be computed via automatic differentiation. Maclaurin et al. (2015) propagate gradients through the full unrolled training procedure to find optimal learning rate schedules offline. Stochastic meta-descent (SMD) (Schraudolph, 1999) adapts hyperparameters online. Hypergradient descent (HD) (Baydin et al., 2017) takes the gradient of the learning rate with respect to the optimizer update in each iteration, to minimize the expected loss in the next iteration.

In particular, HD suffers from short horizon bias (Wu et al., 2018) , while in Appendix F we show that APO does not.

Some authors have proposed learning entire optimization algorithms (Li & Malik, 2016; 2017; Andrychowicz et al., 2016) . Li & Malik (2016) view this problem from a reinforcement learning perspective, where the state consists of the objective function L and the sequence of prior iterates {θ t } and gradients {∇ θ L(θ t )}, and the action is the step ∆θ. In this setting, the update rule φ is a policy, which can be found via policy gradient methods (Sutton et al., 2000) . Approaches that learn optimizers must be trained on a set of objective functions {f 1 , . . . , f n } drawn from a distribution F; this setup can be restrictive if we only have one instance of an objective function. In addition, the initial phase of training the optimizer on a distribution of functions can be expensive. APO requires only the objective function of interest and finds learning rate schedules in a single training run.

In principle, APO could be used to learn a full optimization algorithm; however, learning such an algorithm would be just as hard as the original optimization problem, so one would not expect an out-of-the-box meta-optimizer (such as RMSprop with learning rate 0.001) to work as well as it does for adapting few hyperparameters.

5. EXPERIMENTS:

In this section, we evaluate APO empirically on a variety of learning tasks; Table 1 gives an overview of the datasets, model architectures, and base optimizers we consider.

In our proximal objective,

J (φ) = h (f (x, g(θ, φ))) + λ E x∼P [D (f (x, g(θ, φ)) , f (x, θ))],

h can be any approximation to the loss function (e.g., a linearization); in our experiments, we directly used the loss value h = , as we found this to work well in many settings. As the dissimilarity term D, we used the squared Euclidean norm.

We used APO to tune the optimization hyperparameters of four base-optimizers: SGD, SGD with Nesterov momentum (denoted SGDm), RMSprop, and K-FAC. For SGD, the only hyperparameter is the learning rate; we consider both a single, global learning rate, as well as per-layer learning rates. For SGDm, the update rule is given by:

EQUATION

where g = ∇ . Since adapting µ requires considering long-term performance (Sutskever et al., 2013) , it is not appropriate to adapt it with a one-step objective like APO. Instead, we just adapt the learning rate with APO as if there's no momentum, but then apply momentum with µ = 0.9 on top of the updates. For RMSprop, the optimizer step is given by:

EQUATION

We note that, in addition to the learning rate η, we can also consider adapting and the power to which s is raised in the denominator of Eq. 21-we denote this parameter ρ, where in standard RMSprop we have ρ = 1 2 . Both and ρ can be interpreted as having a damping effect on the update. K-FAC is an approximate natural gradient method (Amari, 1998) based on preconditioning the gradient by an approximation to the Fisher matrix, θ ← θ -F -1 ∇ . For K-FAC, we tune the global learning rate and the damping factor.

Meta-Optimization Setup. Throughout this section, we use the following setup for metaoptimization: we use RMSprop as the meta-optimizer, with learning rate 0.1, and perform 1 metaoptimization update for every 10 steps of the base optimization. We show in Appendix E that with this default configuration, APO is robust to the initial learning rate of the base optimizer. Each meta-optimization step takes approximately the same amount of computation as a base optimization step; by performing meta-updates once per 10 base optimization steps, the computational overhead of using APO is just a small fraction more than the original training procedure.

5.1. TOY OPTIMIZATION PROBLEMS:

Rosenbrock. We first validated APO on the two-dimensional Rosenbrock function, f (x, y) = (1 -x) 2 + 100(y -x 2 ) 2 , with initialization (x, y) = (1, -1.5). We used APO to tune the learning rate of RMSprop, and compared to standard RMSprop with several fixed learning rates. Because this problem is deterministic, we set λ = 0 for APO. Figure 1 (a) shows that RMSprop-APO was able to achieve a substantially lower objective value than the baseline RMSprop. The learning rates for each method are shown in Figure 1(b) ; we found that APO first increases the learning rate to make rapid progress at the start of optimization, and then gradually decreases it as it approaches the local optimum. In Appendix D we show that APO converges quickly from many different locations on the Rosenbrock surface, and in Appendix E we show that APO is robust to the initial learning rate of the base optimizer.

Badly-Conditioned Regression. Next, we evaluated APO on a badly-conditioned regression problem (Recht & Rahimi, 2017) , which is intended to be a difficult test problem for optimization algorithms. In this problem, we consider a dataset of input/output pairs {(x, y)}, where the outputs are given by y = Ax, where A is an ill-conditioned matrix with κ(A) = 10 10 . The task is to fit a two-layer linear model f (x) = W 2 W 1 x to this data; the loss to be minimized is

L = E x∼N (0,I) ||Ax -W 2 W 1 x|| 2 2 .

Figure 1 (c) compares the performance of RMSprop with a hand-tuned fixed learning rate to the performance of RMSprop-APO, with learning rates shown in Figure 1(d) . Again, the adaptive learning rate enabled RMSprop-APO to achieve a loss value orders of magnitude smaller than that achieved by RMSprop with a fixed learning rate.

5.2. REAL-WORLD DATASETS:

For each of the real-world datasets we consider-MNIST, CIFAR-10, CIFAR-100, SVHN, and FashionMNIST-we chose the learning rates for the baseline optimizers via grid searches: for SGD and SGDm, we performed a grid search over learning rates {0.1, 0.01, 0.001}, while for RMSprop, we performed a grid search over learning rates {0.01, 0.001, 0.0001}. For SGD-APO and SGDm-APO, we set the initial learning rate to 0.1, while for RMSprop-APO, we set the initial learning rate to 0.0001. These initial learning rates are used for convenience; we show in Appendix E that APO is robust to the choice of initial learning rate. The only hyperparameter we consider for APO is the value of λ: for SGD-APO and SGDm-APO, we select the best λ from a grid search over {0.1, 0.01, 1e-3}; for RMSprop, we choose λ from a grid search over {0.1, 0.01, 1e-3, 1e-4, 1e-5, 0}. Note that because each value of λ yields a learning rate schedule, performing a search over λ is much more effective than searching over fixed learning rates. In particular, we show that the adaptive learning rate schedules discovered by APO are competitive with manual learning rate schedules.

5.2.1. MULTI-LAYER PERCEPTRON ON MNIST:

First, we compare SGD and RMSprop with their APO-tuned variants on MNIST, and show that APO outperforms fixed learning rates. As the classification network for MNIST, we used a twolayer MLP with 1000 hidden units per layer and ReLU nonlinearities. We trained on mini-batches of size 100 for 100 epochs.

SGD with APO. We used APO to tune the global learning rate of SGD and SGD with Nesterov momentum (denoted SGDm) on MNIST, where the momentum is fixed to 0.9. For baseline SGDm, we used learning rate 0.01, while for baseline SGD, we used both learning rates 0.1 and 0.01. The training curve of SGD with learning rate 0.1 almost coincides with that of SGDm with learning rate 0.01. For SGD-APO, the best λ was 1e-3, while for SGDm-APO, the best λ was 0.1. A comparison of the algorithms is shown in Figure 2(a) . APO substantially improved the training loss for both SGD and SGDm. We compare K-FAC with a fixed learning rate and a manual learning rate schedule to APO, used to tune 1) the learning rate; and 2) both the learning rate and damping coefficient.

RMSprop with APO. Next, we used APO to tune the global learning rate of RMSprop. For baseline RMSprop, the best fixed learning rate was 1e-4, while for RMSprop-APO, the best λ was 1e-5. Figure 2 (b) compares RMSprop and its APO-tuned variant on MNIST. RMSprop-APO achieved a training loss about three orders of magnitude smaller than the baseline.

5.2.2. CIFAR-10 EXPERIMENTS:

We trained a 34-layer residual network (ResNet34) (He et al., 2016) on CIFAR-10 (Krizhevsky & Hinton, 2009), using mini-batches of size 128, for 200 epochs. We used batch normalization and standard data augmentation (horizontal flipping and cropping). For each optimizer, we compare APO to 1) fixed learning rates; and 2) manual learning rate decay schedules.

SGD with APO.:

For SGD, we used both learning rates 0.1 and 0.01 since both work well. For SGD with momentum, we used learning rate 0.01. We also consider a manual schedule for both SGD and SGDm: starting from learning rate 0.1, and we decay it by a factor of 5 every 60 epochs. For the APO variants, we found that λ=1e-3 was best for SGD, while λ = 0.1 was best for SGDm. As shown in Figure 2 (c), APO not only accelerates training, but also achieves higher accuracy on the test set at the end of training.

RMSprop with APO. For RMSprop, we use fixed learning rates 1e-3 and 1e-4, and we consider a manual learning rate schedule in which we initialize the learning rate to 1e-3 and decay by a factor of 5 every 60 epochs. For RMSprop-APO, we used λ = 1e-3. The training curves, test accuracies, and learning rates for RMSprop and RMSprop-APO on CIFAR-10 are shown in Figure 2 (d). We found that APO achieved substantially lower training loss than fixed learning rates, and was competitive with the manual decay schedule. In particular, both the final training loss and final test accuracy achieved by APO are similar to those achieved by the manual schedule.

K-FAC with APO. We also used APO to tune the learning rate and damping coefficient of K-FAC.

Similarly to the previous experiments, we use K-FAC to optimize a ResNet34 on CIFAR-10. We used mini-batches of size 128 and trained for 100 epochs. For the baseline, we used a fixed learning rate of 1e-3 as well as a decay schedule with initial learning rate 1e-3, decayed by a factor of 10 at epochs 40 and 80. For APO, we used λ = 1e-2. In experiments where the damping is not tuned, it is fixed at 1e-3. The results are shown in Figure 3 . We see that K-FAC-APO performs competitively with the manual schedule when tuning just the global learning rate, and that both training loss and test accuracy improve when we tune both the learning rate and damping coefficient simultaneously.

5.2.3. CIFAR-100 EXPERIMENTS:

Next, we evaluated APO on the CIFAR-100 dataset. Similarly to our experiments on CIFAR-10, we used a ResNet34 network with batch-normalization and data augmentation, and we trained on minibatches of size 128, for 200 epochs. We compared SGD-APO/SGDm-APO to standard SGD/SGDm using (1) a fixed learning rate found by grid search;

(2) a custom learning rate schedule in which the learning rate is decayed by a factor of 5 at epochs 60, 120, and 180. We set λ = 1e-3 for SGD-APO and λ = 0.1 for SGDm-APO. Figure 4 shows the training loss, test accuracy, and the tuned learning rate. It can be seen that APO generally achieves smaller training loss and higher test accuracy.

5.2.4. SVHN EXPERIMENTS:

We also used APO to train an 18-layer residual network (ResNet18) with batch normalization on the SVHN dataset (Netzer et al., 2011) . Here, we used the standard train and test sets, without additional training data. We used mini-batches of size 128 and trained our networks for 160 epochs. We compared APO to 1) fixed learning rates, and 2) a manual schedule in which we initialize the learning rate to 1e-3 and decay by a factor of 10 at epochs 80 and 120. We show the training loss, test accuracy, and learning rates for each method in Figure 5 . Here, RMSprop-APO achieves similar training loss to the manual schedule, and obtains higher test accuracy than the schedule. We also see that the learning rate adapted by APO spans two orders of magnitude, similar to the manual schedule. 

5.3. BATCH NORMALIZATION AND WEIGHT DECAY:

Batch normalization (BN) (Ioffe & Szegedy, 2015) is a widely used technique to speed up neural net training. Networks with BN are commonly trained with weight decay. It was shown that the effectiveness of weight decay for networks with BN is not due to the regularization, but due to the fact that weight decay affects the scale of the network weights, which changes the effective learning rate (Zhang et al., 2018; Hoffer et al., 2018; van Laarhoven, 2017) . In particular, weight decay decreases the scale of the weights, which increases the effective learning rate; if one uses BN without regularizing the norm of the weights, then the weights can grow without bound, pushing the effective learning rate to 0. Here, we show that using APO to tune learning rates allows for effective training of BN networks without using weight decay. In particular, we compared SGD-APO without weight decay and SGD with weight decay 5e-4. Figure 6 shows that SGD-APO behaved better than SGD with a fixed learning rate, and achieved comparable performance as SGD with a manual schedule.

6. CONCLUSIONS:

We introduced amortized proximal optimization (APO), a method for online adaptation of optimization hyperparameters, including global and per-layer learning rates, and damping parameters for approximate second-order methods. We evaluated our approach on real-world neural network optimization tasks-training MLP and CNN models-and showed that it converges faster and generalizes better than optimal fixed learning rates. Empirically, we showed that our method overcomes short horizon bias and performs well with sensible default values for the meta-optimization parameters.

Guodong Zhang, Chaoqi Wang, Bowen Xu, and Roger Grosse. Three mechanisms of weight decay regularization. arXiv preprint arXiv:1810.12281, 2018.

A PROOF OF THEOREM 1

We first introduce the following lemma:

Lemma 1. Assume the manifold is smooth with C-bounded curvature, the gradient norm of loss function L is upper bounded by G. If the effective gradient at point Z k ∈ M is g k , then for any

0 < γ ≤ 1 4CG there exist Z ∈ M such that ∇ Z L(Z k ), Z -Z k + 1 2γ Z -Z k 2 F ≤ - γ 4 g k 2 .

Proof. We construct the Z satisfying the above inequality. Consider the following point in R d :

Y Z k -γg k . Also, consider a geodesic v : [0, γ g k ] → M such that v = 1, v(0) = g k g k . Define point Z v(γ g k ) ∈ M.

We show that Z is a point satisfying the inequality in the lemma. Firstly, we notice that

Y -Z ≤ C 2 γ 2 g t 2 .

This is because when we introduce the extra curve ṽ : [0, γ g k ] → R d going directly from Z k to Y with unit speed, there is

Y -Z = v(γ g t ) -ṽ(γ g t ) = γ gt t=0 v(t)dt - γ gt t=0 v(t) dt ≤ γ gt t=0 v(t) -v(t) dt = γ gt t=0 t t =0 v(t )dt - t t =0 v(t )dt dt = γ gt t=0 t t =0 v(t )dt dt ≤ γ gt t=0 t t =0 v(t ) dt dt ≤ γ gt t=0 t t =0 Cdt dt = C 2 γ 2 g t 2 .

Here we use the fact that v = 0 and v ≤ C. Therefore we have

∇ Z L(Z k ), Z -Z k + 1 2γ Z -Z k 2 F = ∇ Z L(Z k ), (Z -Y) + (Y -Z k ) + 1 2γ (Z -Y) + (Y -Z k ) 2 F ≤ ∇ Z L(Z k ), Z -Y + ∇ Z L(Z k ), Y -Z k + 1 2γ Z -Y 2 F + 1 2γ Y -Z k 2 F = - γ 2 g k 2 + ∇ Z L(Z k ), Z -Y + 1 2γ Z -Y 2 F ≤ - γ 2 g k 2 + CG 2 γ 2 g k 2 + C 2 8 γ 3 g k 4 ≤ - γ 2 g k 2 + CG 2 γ 2 g k 2 + C 2 G 2 8 γ 3 g k 2 .

Here the first equality is by introducing the extra Y , the first inequality is by triangle inequality, the second equality is by the definition of g k being ∇ Z L(Z k ) projecting onto a plane, the second inequality is due to the above bound of Y -Z , the last inequality is due to

g k ≤ ∇ Z L(Z k ) .

Since γ ≤ 1 4CG , there is therefore

∇ Z L(Z k ), Z -Z k + 1 2γ Z -Z k 2 F ≤ - γ 4 g k 2 ,

which completes the proof. Now we return to the proof of Theorem 1:

Proof. For the ease of notation, we denote the effective gradient at iteration k as g k . For one iteration, there is

L(Z k+1 ) ≤ L(Z k ) + ∇ Z L(Z k ), Z k+1 -Z k + L 2 Z k+1 -Z k 2 ≤ L(Z k ) + ∇ Z L(Z k ), Z k+1 -Z k + 2λ Z k+1 -Z k 2 ≤ L(Z k ) - 1 16λ g k 2 .

Here the first inequality is due to the Lipschitz continuity and the fact that total loss equals to the sum of all loss functions, and the second inequality is due to λ ≥ L 4 , the third inequality is due to Lemma 1 with γ = 1 4λ . (When λ ≥ CG, there is naturally γ ≤ 1 4CG , satisfying the assumptions in Lemma 1.) So we have

L(Z k+1 ) ≤ L(Z k ) - 1 16λ g k 2 .

Telescoping, there is

g * t 2 ≤ 1 T T -1 t=0 g t 2 ≤ 16λ T [L(Z 0 ) -L * ] .

B PROOF OF THEOREM 2:

Proof. For notational convenience, we think of Z as a vector rather than a matrix in this proof.

The Hessian ∇ 2 L(Z) is therefore a block diagonal matrix, where each block is the Hessian of loss on a single data.

First, we notice the following equation:

arg min Z∈M ∇ Z L(Z k ), Z -Z k + 1 2 Z -Z k 2 H = arg min Z∈M ∇ Z L(Z k ), Z -Z k + 1 2 (Z -Z k ) T ∇ 2 L(Z k )(Z -Z k ) = arg min Z∈M 1 2 Z -Z k -∇ 2 L(Z k ) -1 ∇ L(Z k ) 2 ∇ 2 L(Z k ) -∇ L(Z k ) 2 [∇ 2 L(Z k )] -1 = arg min Z∈M Z -Z k -∇ 2 L(Z k ) -1 ∇ L(Z k ) 2 ∇ 2 L(Z k ) .

Here

v 2 A v T Av

is the norm of vector v defined by the positive definite matrix A. ∇ 2 L(Z k ) -1 is the inverse of positive definite matrix ∇ 2 L(Z k ), therefore also positive definite.

As a result of the above equivalence, one step of Proximal Newton Method can be written as:

Z k+1 = arg min Z∈M Z -Z k -∇ 2 L(Z k ) -1 ∇ L(Z k ) 2 ∇ 2 L(Z k ) .

Since Z * ∈ M by assumption, there is:

Z k+1 -Z k -∇ 2 L(Z k ) -1 ∇ L(Z k ) ∇ 2 L(Z k ) ≤ Z * -Z k -∇ 2 L(Z k ) -1 ∇ L(Z k ) ∇ 2 L(Z k ) .

Now we have the following inequality for one iteration:

Z k+1 -Z * ∇ 2 L(Z k ) ≤ Z k+1 -Z k -∇ 2 L(Z k ) -1 ∇ L(Z k ) ∇ 2 L(Z k ) + Z * -Z k -∇ 2 L(Z k ) -1 ∇ L(Z k ) ∇ 2 L(Z k ) ≤ 2 Z * -Z k -∇ 2 L(Z k ) -1 ∇ L(Z k ) ∇ 2 L(Z k ) = 2 Z * -Z k + ∇ 2 L(Z k ) -1 (∇ L(Z k ) -∇ L(Z * ) ∇ 2 L(Z k ) ≤ 2 √ µ ∇ 2 L(Z k )(Z k -Z * ) -∇ L(Z k ) + ∇ L(Z * ) .

Here the first inequality is because of triangle inequality, the second inequality is due to the previous result, the equality is because ∇ L(Z * ) = 0, the last inequality is because of the strong convexity.

By the Lipschitz continuity of the Hessian, we have:

∇ 2 L(Z k )(Z k -Z * ) -∇ L(Z k ) + ∇ L(Z * ) ≤ N i=1 ∇ 2 (z k,i )(z k,i -z * i ) -∇ L(z k,i ) + ∇ L(z * i ) ≤ L H 2 N i=1 z k,i -z * i 2 = L H 2 Z k -Z * 2 .

Therefore, we have: Here we highlight the ability of APO to tune several optimization hyperparameters simultaneously. We used APO to adapt all of the RMSprop hyperparameters {η, ρ, }. As shown in Figure 7 (a), tuning ρ and in addition to the learning rate η can stabilize training. We also used APO to adapt per-layer learning rates. Figure 7 (b) shows the per-layer learning rates tuned by APO, when using SGD on MNIST. Figure 7 (c) uses APO to tune per-layer learning rate of RMSprop on MNIST.

Z k+1 -Z * ≤ 1 √ µ Z k+1 -Z * ∇ 2 L(Z k ) ≤ L H µ Z k -Z * 2 . C MULTIPLE

Figure 8 shows the adaptation of the additional ρ and hyperparameters of RMSprop, for training an MLP on MNIST. Tuning per-layer learning rates is a difficult optimization problem, and we found that it was useful to use a smaller meta learning rate of 0.001 and perform meta-updates more frequently.

K-FAC. We also used APO to train a convolutional network on the FashionMNIST dataset (Xiao et al., 2017) . The network we use consists of two convolutional layers with 16 and 32 filters respectively, both with kernel size 5, followed by a fully-connected layer. The results are shown in Figure 7 (d), where we also compare K-FAC to hand-tuned RMSprop and RMSprop-APO on the same problem. We find that K-FAC with a fixed learning rate outperforms RMSprop-APO, while K-FAC-APO substantially outperforms K-FAC. The results are shown in Figure 7 (d). We also show the adaptation of both the learning rate and damping coefficient for K-FAC-APO in Figure 7 (d).

D ADDITIONAL EXPERIMENTS ON ROSENBROCK:

In this section, we present additional experiments on the Rosenbrock problem. We show in Figure 9 that APO converges quickly from different starting points on the Rosenbrock surface. Figure 9 : RMSprop-APO convergence from different initializations on the Rosenbrock surface. We find that RMSprop-APO achieves very low training loss starting from any of the points (x, y) ∈ {(-1, 1.5), (-2, 2), (0, 0), (0.5, 0.5), (1, -1)}. In this section we show that APO is robust to the choice of initial learning rate of the base optimizer.

E ROBUSTNESS TO INITIAL LEARNING RATE:

With a suitable meta learning rate, APO quickly adapts many different initial learning rates to the same range, after which the learning rate adaptation follows a similar trajectory. Thus, APO helps to alleviate the difficulty involved in selecting an initial learning rate. First, we used RMSprop-APO to optimize Rosenbrock, starting with a wide range of initial learning rates; we see in Figure 10 that the training losses and learning rates are nearly identical between all these experiments.

Next, we trained an MLP on MNIST and ResNet34 on CIFAR-10 using RMSprop-APO, with the learning rate of the base optimizer initialized to 1e-2, 1e-3, 1e-4, 1e-5, 1e-6, and 1e-7. We used the default meta learning rate 0.1. As shown in Figure 11 , the training loss, test accuracy, and learning rate adaptation are nearly identical using these initial learning rates, which span 5 orders of magnitude.

F THE NOISY QUADRATIC PROBLEM:

In this section we apply APO to the noisy quadratic problem investigated in (Wu et al., 2018; Schaul et al., 2013) , and demonstrate that APO overcomes the short horizon bias problem. We optimize a quadratic function f

(x) = x T Hx, where x ∈ R 1000 , H is a diagonal matrix H = diag{h 1 , h 2 , • • • , h 1000 }, with eigenvalues h i evenly distributed in interval [0.01, 1].

Initially, we set x with each dimension being 100. For each iteration, we can access the noisy version of the function, i.e., the gradient and function value of function

f (x) = (x -c) T H(x -c).

Here c is the vector of noise: each dimension of c is independently randomly sampled from a normal distribution at each iteration, and the variance of dimension i is set to be 1 hi . For SGD, we consider the following four learning rate schedules: optimal schedule, exponential schedule, linear schedule and a fixed learning rate. For SGD with APO, we directly use function f as the loss approximation h, use Euclidean distance norm square as the dissimilarity term D, and consider the following schedules for λ: optimal schedule(with λ ≥ 0), exponential schedule, linear schedule and a fixed λ. We calculate the optimal parameter for each schedule of both algorithms so as to achieve a minimal function value at the end of 300 iterations. We optimize the schedules with 10000 steps of Adam and learning rate 0.001 after unrolling the entire 300 iterations.

The function values at the end of 300 iterations with each schedule are shown in Table 2 . seen that SGD with APO achieves almost the same training loss as optimal SGD for noisy quadratics task. This indicates that APO doesn't suffer from the short-horizon bias mentioned in (Wu et al., 2018) .

G ADAM EXPERIMENTS:

Adam (Kingma & Ba, 2015) is an adaptive optimization algorithm widely used for training neural networks, which can be seen as RMSProp with momentum. The update rule is given by:

EQUATION

vt ← v t /(1 -β t 2 ) (25)

EQUATION

where g t = ∇ θ t (θ t-1 ).

Similar to SGD with Nesterov momentum, we fixed the β 1 and β 2 for Adam, and used APO to tune the global learning rate η. We tested Adam-APO with a ResNet34 network on CIFAR-10 dataset, and compared it with both Adam with fixed learning rate and Adam with a learning rate schedule where the learning rate is initialized to 1e-3 and is decayed by a factor of 5 every 60 epochs. Similarly to SGD with momentum, we found that Adam generally benefits from larger values of λ. Thus, we recommend performing a grid search over λ values from 1e-2 to 1. As shown in Figure 14 , APO improved both the training loss and test accuracy compared to the fixed learning rate, and achieved comparable performance as the manual learning rate schedule. 

H COMPARISON WITH POPULATION-BASED TRAINING:

Population-based training (PBT) (Jaderberg et al., 2017) is an approach to hyperparameter optimization that trains a population of N neural networks simultaneously: each network periodically evaluates its performance on a target measure (e.g., the training loss); poorly-performing networks can exploit better-performing members of the population by cloning the weights of the better network, copying and perturbing the hyperparameters used by the better network, and resuming training. In this way, a single model can essentially experience multiple hyperparameter settings during training; in particular, we are interested in evaluating the learning rate schedule found using PBT.

Here, we used PBT to tune the learning rate for RMSprop, to optimize a ResNet34 model on CIFAR-10. For PBT, we used a population of size 4 (which we found to perform better than a population of size 10), and used a perturbation strategy that consists of randomly multiplying the learning rate by either 0.8 or 1.2. In PBT, one can specify the probability with which to re-sample a hyperparameter value from an underlying distribution. We found that it was critical to set this to 0; otherwise, the learning rate could jump from small to large values and cause instability in training. Figure 15 compares PBT with APO; we show the best training loss achieved by any of the models in the PBT population, as a function of wall-clock time. For a fair comparison between these methods, we ran both PBT and APO using 1 GPU. We see that APO outperforms PBT, achieving a training loss an order of magnitude smaller than PBT, and achieves the same test accuracy, much more quickly. 

:

For convenience of notation, we omit the dependence of loss on the fixed label.

It is worth noting that here we don't need assumptions of manifold M being even differentiable. Therefore, the result holds for neural networks where non-smooth activation functions like ReLU are used.

Figures and Tables:

Figure3: K-FAC results on CIFAR-10. We compare K-FAC with a fixed learning rate and a manual learning rate schedule to APO, used to tune 1) the learning rate; and 2) both the learning rate and damping coefficient.

Figure 5: Comparison of RMSprop and RMSprop-APO used to optimize a ResNet on SVHN.

Figure 6: SGD with weight decay compared to SGD-APO without weight decay, on CIFAR-10.

Figure 7: (a) Tuning multiple RMSprop parameters from {η, ρ, } on MNIST. (b) Tuning per-layer learning rates for SGD on MNIST. (c) Tuning per-layer learning rates for RMSprop on MNIST. (d) K-FAC and RMSprop on FashionMNIST.

Figure 8: Adaptation of ρ and using RMSprop-APO on MNIST.

,y) = (0.5, 0.5) Init (x,y) = (1, -1) (b) RMSprop-APO learning rate adaptation from different initial (x,y) positions on the Rosenbrock surface.

RMSprop-APO learning rate adaptation with different initial learning rates.

Figure 10: RMSprop-APO performance on Rosenbrock, starting with different initial learning rates for the base optimizer.

Figure 11: Robustness to initial learning rates on MNIST and CIFAR-10. Top row: RMSprop-APO tuning an MLP on MNIST. Bottom row: RMSprop-APO tuning ResNet34 on CIFAR-10. (a) Training loss; (b) test accuracy; (c) learning rate adaptation.

Figure12plots the training loss and learning rate of SGD during the 300 iterations under optimal schedule, figure13plots the training loss and λ under optimal schedule for SGD with APO. It can be

Figure 12: Loss and learning rate for SGD.

Figure 13: Loss and learning rate for APO.

Figure14: Adam results on CIFAR-10. We compare Adam with a fixed learning rate and a manual learning rate schedule to Adam-APO.

Figure 15: Training loss and test accuracy of APO and PBT, as a function of wall-clock time.

Summary of the datasets, model architectures, and optimizers we investigate.

Table content: <table><tr><td/><td/><td/><td/><td colspan="2">Dataset</td><td/><td/><td colspan="3">Architecture</td><td/><td/><td>Optimizer</td><td/><td/><td colspan="2">Batch Size</td></tr><tr><td/><td/><td colspan="7">Rosenbrock &amp; 2-Layer Linear</td><td>-</td><td/><td/><td/><td>RMSprop</td><td/><td/><td>-</td><td/></tr><tr><td/><td/><td/><td/><td colspan="2">MNIST</td><td/><td/><td/><td>MLP</td><td/><td/><td colspan="2">SGD, RMSprop</td><td/><td/><td colspan="2">100</td></tr><tr><td/><td/><td/><td colspan="4">FashionMNIST</td><td/><td colspan="3">2-Layer CNN</td><td/><td colspan="2">RMSprop, K-FAC</td><td/><td/><td colspan="2">100</td></tr><tr><td/><td/><td/><td/><td colspan="2">CIFAR-10</td><td/><td/><td/><td colspan="2">ResNet-34</td><td/><td colspan="3">SGD, RMSprop, K-FAC</td><td/><td colspan="2">128</td></tr><tr><td/><td/><td/><td/><td colspan="2">CIFAR-100</td><td/><td/><td/><td colspan="2">ResNet-34</td><td/><td/><td>SGD</td><td/><td/><td colspan="2">128</td></tr><tr><td/><td/><td/><td/><td colspan="2">SVHN</td><td/><td/><td/><td colspan="2">ResNet-18</td><td/><td/><td>RMSprop</td><td/><td/><td colspan="2">128</td></tr><tr><td>10 15 10 13 10 11 10 9 10 7 10 5 10 3 10 1 10 1 Training Loss</td><td>0</td><td>10000</td><td>20000 Iteration</td><td>30000 RMSprop lr=1e-2 40000 RMSprop lr=1e-3 RMSprop lr=1e-4 RMSprop-APO</td><td>10 7 10 6 10 5 10 4 10 3 10 2 Learning Rate</td><td>0</td><td>10000</td><td>20000 Iteration</td><td>30000 RMSprop lr=1e-2 40000 RMSprop lr=1e-3 RMSprop lr=1e-4 RMSprop-APO</td><td>10 12 10 10 10 8 10 6 10 4 10 0 10 2 10 2 Loss</td><td>0</td><td>10000</td><td>20000 Iteration RMSprop lr=0.001 30000 40000 RMSprop-APO</td><td>10 7 10 2 10 3 10 6 10 5 10 4 Learning Rate</td><td>0</td><td>10000</td><td>20000 Iteration RMSprop lr=0.001 30000 40000 RMSprop-APO</td></tr><tr><td/><td/><td/><td>(a)</td><td/><td/><td/><td/><td>(b)</td><td/><td/><td/><td/><td>(c)</td><td/><td/><td/><td>(d)</td></tr></table>

Experiments on MNIST and CIFAR-10, with and without APO. Upper row: mean loss over the training set. Middle row: accuracy on the test set. Bottom row: learning rate per iteration. We use ResNet34 for CIFAR-10, and train for 200 epochs with learning rate decayed by a factor of 10 every 60 epochs.

Table content: <table><tr><td/><td/><td/><td/><td/><td/><td/><td/><td/><td>Training Loss</td><td colspan="2">SGD lr=0.1 SGD lr=0.01 SGDm lr=0.01 SGD schedule SGDm schedule SGD-APO =0.001 SGDm-APO =0.1</td><td>10 3 10 2 10 1 10 0 Training Loss</td><td>RMSprop lr=1e-3 RMSprop lr=1e-4 RMSprop schedule RMSprop-APO =1e-3</td></tr><tr><td/><td/><td/><td/><td/><td/><td/><td/><td/><td/><td/><td>10 4</td><td>0 25 50 75 100 125 150 175 200 Epoch</td></tr><tr><td colspan="2">0.972 0.974 0.976 0.978 0.980 0.982 0.984 0.986 0.988 Test Accuracy</td><td>20</td><td>40 Epoch 60 SGD lr=0.1 80 SGD lr=0.01 SGDm lr=0.01 SGD-APO =0.001 100 SGDm-APO =0.1</td><td colspan="2">0.9700 0.9725 0.9750 0.9775 0.9800 0.9825 0.9850 0.9900 0.9875 Test Accuracy</td><td>0</td><td>20</td><td>40 Epoch 60 RMSprop lr=1e-3 80 RMSprop lr=1e-4 RMSprop-APO, =1e-5 100</td><td>0.96 0.94 0.80 0.82 0.84 0.86 0.88 0.90 0.92 Test Accuracy</td><td colspan="2">25 50 75 100 125 150 175 200 Epoch SGD lr=0.1 SGD lr=0.01 SGDm lr=0.01 SGD schedule SGDm schedule SGD-APO =0.001 SGDm-APO =0.1</td><td>0.95 0.94 0.88 0.89 0.90 0.91 0.92 0.93 Test Accuracy</td><td>0 25 50 75 100 125 150 175 200 Epoch RMSprop lr=1e-3 RMSprop lr=1e-4 RMSprop schedule RMSprop-APO =1e-3</td></tr><tr><td>10 2 10 1 10 0 10 1 Learning Rate</td><td colspan="3">0 10000 20000 30000 40000 50000 60000 Iteration SGD lr=0.1 SGD/SGDm lr=0.01 SGD-APO =0.001 SGDm-APO =0.1</td><td>10 6 10 5 10 4 10 3 Learning Rate</td><td colspan="4">0 10000 20000 30000 40000 50000 60000 Iteration RMSprop lr=1e-3 RMSprop lr=1e-4 RMSprop-APO, =1e-5</td><td>10 4 10 3 10 2 10 1 10 0 Learning Rate</td><td>10000 SGD/SGDm lr=0.1 30000 Iteration 50000 SGDm lr=0.01 SGDm-APO =0.1 SGD-APO =0.001 SGD/SGDm schedule</td><td>70000</td><td>10 5 10 4 10 3 Learning Rate</td><td>10000</td><td>30000 Iteration 50000 RMSprop lr=1e-3 70000 RMSprop lr=1e-4 RMSprop schedule RMSprop-APO =1e-3</td></tr><tr><td colspan="4">SGD/SGDm MNIST</td><td colspan="5">RMSprop MNIST</td><td colspan="3">SGD/SGDm CIFAR-10 RMSprop CIFAR-10</td></tr><tr><td/><td/><td/><td>(a)</td><td/><td/><td/><td/><td>(b)</td><td/><td>(c)</td><td>(d)</td></tr><tr><td colspan="3">Figure 2:</td><td/><td/><td/><td/><td/><td/><td/><td/></tr></table>

Peer review (iclr2019):
 I raised my rating. After the rebuttal. - the authors address most of my concerns. - it*s better to show time v.s. testing accuracy as well. the per-epoch time for each method is different. - anyway, the theory part acts still more like a decoration. as the author mentioned, the assumption is not realistic. ------------------------------------------------------------- This paper presents a method to update hyper-parameters (e.g. learning rate) before updating of model parameters. The idea is simple but intuitive. I am conservative about my rating now, I will consider raising it after the rebuttal. 1. The focus of this paper is the hyper-parameter, please focus and explain more on the usage with hyper-parameters. - no need to write so much in section 2.1, the surrogate is simple and common in optimization for parameters. After all, newton method and natural gradients method are not used in experiments. - in section 2.2, please explain more how gradients w.r.t hyper-parameters are computed. 2. No need to write so much decorated bounds in section 3. The convergence analysis is on Z, not on parameters x and hyper-parameters theta. So, bounds here can not be used to explain empirical observations in Section 5. 3. Could authors explain the time complexity of inner loop in Algorithm 1? Does it take more time than that of updating model parameters? 4. Authors have done a good comparison in the context of deep nets. However, - could the authors compare with changing step-size? In most of experiments, the baseline methods, i.e. RMSProp are used with fixed rates. Is it better to decay learning rates for toy data sets? It is known that SGD with fixed step-size can not find the optimal for convex (perhaps, also simple) problems. - how to tune lambda? it is an important hyper-parameter, but it is set without a good principle, e.g., "For SGD-APO, we used lambda = 0.001, while for SGDm-APO, we used lambda = 0.01", "while for RMSprop-APO, the best lambda was 0.0001". What are reasons for these? - In Section 5.2, it is said lambda is tuned by grid-search. Tuning a good lambda v.s. tuning a good step-size, which one costs more?