Year: 2019

Abstract:
Model-agnostic meta-learning (MAML) is known as a powerful meta-learning method. However, MAML is notorious for being hard to train because of the existence of two learning rates. Therefore, in this paper, we derived a sufficinent condition of inner learning rate α and meta-learning rate β for a simplified MAML to locally converge to local minima from any point in the vicinity of the local minima. We find that the upper bound of β depends on α. Moreover, we show that the threshold of β increases as α approaches its own upper bound. This result is verified by experiments on various few-shot tasks and architectures; specifically, we perform sinusoid regression and classification of Omniglot and MiniImagenet datasets with a multilayer perceptron and a convolutional neural network. Based on this outcome, we present a guideline for determining the learning rates: first, search for the largest possible α; next, tune β based on the chosen value of α.

text: Model-agnostic meta-learning (MAML) is known as a powerful meta-learning method. However, MAML is notorious for being hard to train because of the existence of two learning rates. Therefore, in this paper, we derived a sufficinent condition of inner learning rate α and meta-learning rate β for a simplified MAML to locally converge to local minima from any point in the vicinity of the local minima. We find that the upper bound of β depends on α. Moreover, we show that the threshold of β increases as α approaches its own upper bound. This result is verified by experiments on various few-shot tasks and architectures; specifically, we perform sinusoid regression and classification of Omniglot and MiniImagenet datasets with a multilayer perceptron and a convolutional neural network. Based on this outcome, we present a guideline for determining the learning rates: first, search for the largest possible α; next, tune β based on the chosen value of α.

heading: 1 INTRODUCTION
text: A pillar of human intelligence is the ability to learn and adapt to unseen tasks quickly and based on only a limited quantity of data. Although machine learning has achieved remarkable results, many recent models require massive quantities of data and are designed for solving particular tasks. Meta-learning, one of the ways of tackling this problem, tries to develop a model that can adapt to new tasks quickly by learning to learn new concepts from few data points (Schmidhuber, 1987; Thrun & Pratt, 1998).
Among meta-learning algorithms, model-agnostic meta-learning (MAML), a gradient-based metalearning method proposed by Finn et al. (2017), has recently been extensively studied. For example, MAML is used for continual learning (Finn et al., 2019; Jerfel et al., 2019; Spigler, 2019; Al-Shedivat et al., 2018), reinforcement learning (Finn et al., 2017; Al-Shedivat et al., 2018; Gupta et al., 2018; Deleu & Bengio, 2018; Liu & Theodorou, 2019) and probablistic inference (Finn et al., 2018; Yoon et al., 2018; Grant et al., 2018). The reason why MAML is widely used is because MAML is simple but efficient and applicable to a wide range of tasks independent of model architecture and the loss function. However, MAML is notorious for being hard to train (Antoniou et al., 2019). One of the reasons why training MAML is hard is the existence of two learning rates in MAML: the inner learning rate α and meta-learning rate β. A learning rate is known to be one of the most important parameters, and tuning this parameter may be challenging even if the simple gradient descent (GD) method is used. Nevertheless, we do not yet know the relationship between these two learning rates and have little guidance on how to tune them. Hence, guidelines for choosing these parameters are urgently needed.
In this paper, we investigate the MAML algorithm and propose a guideline for selecting the learning rates. First, in Section 2 we briefly explain by using an approximation how MAML can be regarded as optimization with the negative gradient penalty. Because the gradient norm is related to the shape of the loss surface, a bias towards a larger gradient norm can make training unstable. Next, based on the approximation explained in Section 2, in Section 3, we derive a sufficinent condition of α and β for a simplified MAML to locally converge to local minima from any point in the neighborhood of the local minima. Furthermore, by removing a constraint, we derive a sufficient condition for local convergence with fewer simplifications as well. We find that the upper bound βc of meta-learning rate depends on inner learning rate α. In particular, βc of α ≈ αc is larger than that of α = 0,
where αc is the upper bound of α. This is verified by experiments in Section 5. These results imply a guideline for selecting the learning rates: first, search for the largest possible α; next, tune β.

heading: 2 MAML AS OPTIMIZATION WITH NEGATIVE GRADIENT PENALTY

heading: 2.1 MAML
text: The goal of MAML is to find a representation that can rapidly adapt to new tasks with a small quantity of data. In other words, MAML performs optimization for parameters θ ∈ Rd that the optimizer can use to quickly reach the optimal parameter θ∗τ for task τ with few data points. To this end, MAML takes the following steps to update θ. First, it samples a batch of tasks from task distribution P (τ) and updates θ for each task τ with stochastic gradient descent (SGD). Although MAML allows multiple-step being taken to update θ, we will consider the case only one step being taken for simplicity. The update equation is as follows:
θ′τ = θ − α∇θLτ (θ) , (1)
where α is a step size referred to as the inner learning rate, Lτ (θ) is the loss of τ , and ∇θLτ (θ) is an estimate of the true gradient. The data used for this update is called training data. Next, MAML resamples data, referred to as test data, from each τ and computes the loss at the updated parameters θ′τ , obtaining Lτ (θ ′ τ ) for each task. Finally, to determine θ that can be adapted to θ ′ τ for all tasks, θ is updated with the gradient of a sum of loss values Lτ (θ′τ ) over all tasks. In other words,
θ ← θ − β∇θ ∑
τ∼P (τ)
Lτ (θ ′ τ ) , (2)
where β is the learning rate called the meta-learning rate and∇θ ∑ τ∼P (τ) Lτ (θ ′ τ ) is an estimate of the true gradient by using the test data. Though learning rates α and β can be tuned during training or different for each task in practice, we will think them as fixed scalar hyperparameters.

heading: 2.2 NEGATIVE GRADIENT PENALTY
text: Unless otherwise noted, we will consider the case of only one step being made per update, and the data are not resampled to compute the loss for updating θ. The case of multiple steps and that of training data and test data being separated are considered in Appendix A. The gradient of the loss at θ′τ is gτ (θ
′ τ ) = ∇θLτ (θ′τ ) = ∇θθ′τ ∂Lτ∂θ′τ , where g(·) is the gradient of L(·) with respect to θ. If α
is small, we can assume that I ∂Lτ∂θ′τ = gτ (θ); this seems to hold since α is usually small (Finn et al., 2017). Then,
∇θLτ (θ′τ ) = ∇θθ′τ ∂Lτ ∂θ′τ
= ( I − α∇2θLτ ) ∂Lτ ∂θ′τ
(3)
≈ gτ (θ)− αHτ (θ)gτ (θ). (4)
The result but not the procedure with the approximation is the same as that with the well-known firstorder approximation as long as data are not resampled and only one step being taken. The first order approximation has been mentioned by Finn et al. (2017) and extensively studied by Nichol et al. (2018) and Fallah et al. (2019). It is known that the error induced by the first-order approximation does not degrade the performance so much in practice (Finn et al., 2017). Also, Fallah et al. (2019) theoretically proved that the first-order approximation of MAML does not affect convergence result when each task is similar to each other or α is small enough.
For simplicity, we will assume that only one task is considered during training, omitting task index τ . Therefore, instead of ∑ τ∼P (τ) Lτ (θ ′ τ ), we will consider L(θ
′) as the loss of the simplified MAML. Since the MAML loss is just a sum of task-specific loss, extension to the case of multiple tasks being considered is straightforward, as provided in Appendix A.1.1. Because ∇θ(g(θ)⊤g(θ)) = 2H(θ)g(θ), if we define L̃(θ) = L(θ′),
L̃(θ) ≈ L(θ)− α 2 g(θ)⊤g(θ). (5)
The above means that the simplified MAML can be regarded as optimization with the negative gradient penalty. We will analyze this simplified MAML loss in Section 3. It can also be interpreted as a Taylor series expansion of the simplified MAML loss for the first-order term, up to scale:
L̃(θ) = L(θ − α∇θL(θ)) (6) ≈ L(θ)− α∇θL(θ)⊤∇θL(θ) (Taylor series expansion) = L(θ)− αg(θ)⊤g(θ). (7)
The fact that the simplified MAML is optimization with the negative gradient penalty is worth keeping in mind. Because the goal of gradient-based optimization is to find a point where the gradient is zero, a bias that favors a larger gradient is highly likely to make training unstable; this can be a cause of instability of MAML (Antoniou et al., 2019). In fact, as shown in Fig. 1, the gradient norm becomes larger during training, as do the gradient inner products, as Guiroy et al. (2019) observed.

heading: 3 LEARNING RATE FOR LOCAL CONVERGENCE
text: In this section, we will derive a sufficient condition of learning rate α and β for local convergence from any point in the vicinity of the local minima. To this end, we will assume that only one step is taken for update and training data and test data are not distinguished as we did in Section 2. Also, we do not consider SGD but steepest GD to derive the condition. In other words, same training data are assumed to be used continuously for updating parameters during training. First, we will consider the case of only single task being considered. Next, we will consider the case of multiple tasks being considered.

heading: 3.1 SINGLE TASK
text: 3.1.1 CONDITION FOR INNER LEARNING RATE α
First, we derive the sufficient condition of learning rate α. To this end, we will consider the sufficinet condition that a fixed point is a local minimum. Taking the Taylor series for the second-order term at a fixed point θ∗, the simplified MAML loss is
L̃(θ) ≈ L̃(θ∗) + 1 2 (θ − θ∗)⊤H̃(θ − θ∗). (8)
where H̃ = H − α ( Tg +H2 ) is the Hessian matrix of L̃(θ) at θ∗ and g = ∇θL(θ∗) ∈ Rd, H = ∇2θL(θ∗) ∈ Rd×d, and T = ∇3θL(θ∗) ∈ Rd×d×d. The calculation of H̃ is presented in Appendix B. We calculated the magnitudes of Tg and H2 numerically and observed that Tg was much smaller than H2 in practice. Hence, we will ignore Tg while deriving the condition and will
thus assume that H̃ = H − αH2. Further details are provided in Appendix C, and the case of Tg being considered is provided in Appendix D. Since PΛH̃P
⊤ = P [ΛH − αΛ2H ]P⊤ where ΛH̃ is a diagonal matrix with entries that are eigenvalues of H̃ and P is a matrix with rows that are eigenvectors of H̃ , the sufficinet condition of α for θ∗ to be a local minimum is
∀i, λ(H̃)i = λ(H)i − αλ(H)2i > 0 (9)
⇒ ∀i, α < 1 λ(H)i . (10)
Note that λ(A)i represents the ith eigenvalue of matrix A. Hence, the sufficient condition of α for θ∗ to be a local minimum is
∀i, α < 1 λ(H)i . (11)
Therefore, αc is the inverse of the largest eigenvalue of H .
3.1.2 CONDITION FOR META-LEARNING RATE β
Next, we derive the sufficient condition of meta-learning rate β for the simplified MAML to locally converge to the local minima discussed above from any point in the vicinity of the local minimum. This is an extension of research of LeCun et al. (1998). Since PP⊤ = I , the simplified MAML loss can be written as
L̃(θ) ≈ L̃(θ∗) + 1 2 ((θ − θ∗)⊤P )P⊤H̃P (P⊤(θ − θ∗)). (12)
By using the simplified loss defined in Eq. 8, the update equation of the parameter θ with GD is
θ(t+ 1) = θ(t)− β∇θL̃(θ) (13) = θ(t)− βH̃(θ − θ∗) (14)
where t (t = 0, ...,M ) is iteration and M is the total number of iterations. Hence, θ(t+ 1)− θ∗ = (I − βH̃)(θ(t) − θ∗). If we denote P⊤(θ − θ∗) by v, the simplified MAML loss in Eq. 12 is L̃(v) ≈ L̃(0) + 12v
⊤ΛH̃v. Because the gradient of L̃(v) for v is ∇vL̃(v) = ΛH̃v, the update equation of v is
v(t+ 1) = v(t)− βΛH̃v(t) = (I − βΛH̃)v(t), (15) where v(t) is the value of v during iteration t. Assuming that Eq. 11 holds, the sufficinet condition of β is as follows: for all i,
|1− βλ(H − αH2)i| = |1− β(λ(H)i − αλ(H)2i )| < 1 (16) ⇒ −1 + β(λ(H)i − αλ(H)2i ) < 1 (∵ λ(H)i − αλ(H)2i > 0 holds because of Eq. 11) (17)
⇒ β < 2 λ(H)i − αλ(H)2i . (18)
Consequently, the sufficient condition for the simplified MAML to locally converge to local minima from any point in the vicinity of the local minima is as follows:
∀i, α < 1 λ(H)i ∧ β < 2 λ(H)i − αλ(H)2i . (19)
Vanilla GD with learning rate β corresponds to MAML if α = 0. In this case, β < 2λmax is the condition of β, where λmax is the largest eigenvalue of H , because 2/λmax is smaller than any other 2/λi (LeCun et al., 1998). Though this holds for the simplified MAML as well, this is not the case if α is close to αc. The reason is that βc diverges as α approaches 1λ(H)i , or αc as Eq. 18 indicates. Hence, for the simplified MAML we must consider not only the largest but also other eigenvalues and in particular, the second-largest eigenvalue. In short, unlike when vanilla GD is employed, βc depends on α in the case of the simplified MAML, and βc is expected to be larger if α is close to αc, as shown in Fig. 2. This finding is validated by experiments presented in Section 5.

heading: 3.2 MULTIPLE TASKS
text: We discussed the case of only one task being available during training in Section 3.1. In this section, we derive upper bounds of α and β that apply if multiple tasks τ ∼ P (τ) are considered. Assumptions, except that multiple tasks are considered, are the same as those in Section 3.1.
3.2.1 CONDITION FOR α
Now, we define the simplified meta-objective as a sum of task-specific objectives: L̂(θ) =∑ τ∼P (τ) L̃τ (θ). Then, at a fixed point θ ∗,
L̂(θ) ≈ L̂(θ∗) + 1 2 (θ − θ∗)⊤Ĥ(θ − θ∗) (20)
= ∑
τ∼P (τ)
( Lτ (θ ∗) + 1
2 (θ − θ∗)(Hτ − αH2τ )(θ − θ∗)
) (21)
= ∑
τ∼P (τ)
( Lτ (θ ∗) + 1
2 (θ − θ∗)⊤Pτ (ΛHτ − αΛ2Hτ )P ⊤ τ (θ − θ∗)
) , (22)
where Ĥ is the Hessian matrix of L̂(θ) at θ. Note that we ignore Tτgτ as we did in Section 3.1.1. Since Hτ−αH2τ is not necessarily simultaneously diagonalizable for each task τ , we cannot exactly express eigenvalues of Ĥ as function of λ(Hτ ) and α. Therefore, instead of the exact value of αc, we will derive an upper bound of αc.
If θ∗ is a local minimum for all L̃τ (θ∗), θ∗ is a local minimum for L̂(θ) as well. Hence, if all eigenvalues of H̃τ = Hτ − 2αH2τ are positive for all tasks, those of Ĥ are positive as well. Therefore, if the inequality
∀τ, i, α < 1 λ(Hτ )i
(23)
holds, it guarantees that the condition that θ∗ is a local minimum of L̂(θ) is satisfied. Note that this is a sufficient condition if θ∗ is a local minimum for all L̃τ (θ∗). Since θ∗ can be a local minimum of L̂(θ) even when it is not a local minimum for all L̃τ (θ∗), the upper bound of α seems to be larger than that in Eq. 23 in practice.
3.2.2 CONDITION FOR β
The analysis for β is also basically the same as that performed in Section 3.1.2. Denoting P⊤τ (θ − θ∗) by vτ , we obtain ∑
τ vτ (t+ 1) = ∑ τ ( I − β [ ΛHτ − αΛ2Hτ ]) vτ (t). (24)
Since H̃τ is not always simultaneously diagonalizable for each task, as mentioned in Section 3.2.1, Pτ differs from task to task in general. Hence, we will consider an upper bound of βc as we did for αc in Section 3.2.1. Accordingly, if both Eq. 23 and
|1− β(λ(Hτ )i − αλ(Hτ )2i )| < 1 (25) hold for any eigenvalue λi of any task τ , it guarantees that β satisfies the condition for local convergence. Therefore, a sufficient for the simplified MAML to locally converge to local minima from any point in the neighborhood of the local minima in the case of multiple tasks is as follows:
∀τ, i, α < 1 λ(Hτ )i ∧ β < 2 λ(Hτ )i − αλ(Hτ )2i
(26)

heading: 4 RELATED WORKS
text: Sevral papers have investigated MAML and proposed various algorithms (Nichol et al., 2018; Guiroy et al., 2019; Eshratifar et al., 2018; Antoniou et al., 2019; Fallah et al., 2019; Khodak et al.,
2019; Vuorio et al., 2018; Finn et al., 2019; Deleu & Bengio, 2018; Liu & Theodorou, 2019; Deleu & Bengio, 2018; Grant et al., 2018). Nichol et al. (2018) studied the first-order MAML family in detail and showed that the MAML gradient could be decomposed into two terms: a term related to joint training and a term responsible for increasing the inner product between gradients for different tasks.
Guiroy et al. (2019) investigated the generalization ability of MAML. The researchers observed that generalization was correlated with the average gradient inner product and that flatness of the loss surface, often thought to be an indicator of strong generalizability in normal neural network training, was not necessarily related to generalizability in the case of MAML. Eshratifar et al. (2018) also noted that the average gradient inner product was important. Hence, the authors proposed an algorithm that considered the relative importance of each parameter based on the magnitude of the inner product between the task-specific gradient and the average gradient. Although the above studies were cognizant of the importance of the inner product of the gradients, they did not explicitly insert the negative gradient inner product, which is the negative squared gradient norm with simplifications, as a regularization term. To consider the simplified MAML as optimization with a regularization term is a contribution of our study.
Antoniou et al. (2019) enumerated five factors that could cause training MAML to be difficult. Then, they authors proposed an algorithm to address all of these problems and make training MAML easier and more stable. Behl et al. (2019), like us, pointed out that tuning the inner learning rate α and meta-learning rate β was troublesome. The authors approached this problem by proposing an algorithm that tuned learning rates automatically during training.
Fallah et al. (2019) studied the convergence theory of MAML. They proposed a method for selecting meta-learning rate by approximating smoothness of the loss. Based on this result, they proved that MAML can find an ε-first-order stationary point after sufficient number of iterations. On the other hand, we studied the relationship between the sufficient conditions of inner learning rate α and meta-learning rate β and showed that how the largest possible β is affected by the value of α.

heading: 5 EXPERIMENTS
text: In this section, we will present the results of experiments to confirm our expectation that MAML allows larger β if α is close to its upper bound. First, we will show the result of linear regression with simplifications used in Section 3.1. Because linear regression is convex optimization, the result is expected to exactly match the theory presented in Section 3.1. Second, to check if our expectation is confirmed in practice as well, we will present results of the practical case without any simplification. In particular, we conducted sinusoid regression and classification of Omniglot and MiniImagenet
datasets with a multilayer perceptron and a convolutional neural network (CNN). Note that the meta-objective used for experiments is not a sum of task-specific objectives but a mean of them.

heading: 5.1 LINEAR REGRESSION
text: We performed a linear regression, where the task is to regress a linear function with scale parameter in the range of [0, 5.0] and bias parameter in the range of [0, 5.0] based on data points in the range of [-5.0, 5.0]. The true function has the same architecture as that of the model. We employed the steepest gradient descent method to minimize the mean squared loss, where 1 step was taken during update. Only one task was considered during training and the same data was used to update the task-specific parameter and the meta parameter as we did in Section 3.1. Using these settings, we computed the training loss after 500 iterations with α in the range of [1e-5, 9e-2] and β in the range of [5e-3, 9e+0]. The eigenvalues are those of the Hessian matrix of the training loss at the end of the training, where α = 5e-2 and β = 7e-1. We chose this training loss because it was thought to be the closest to minima. Fig. 3 shows the training losses at various values of α and β. Horizontal axis indicates α and vertical axis indicates β. The curves are βc of two eigenvalues and the dashed line shows αc. In the case of linear regression with simplifications used in Section 3.1, the result of numerical experiment shows good agreement with upper bounds of βc and αc that we derived in Section 3.1, as shown in Fig. 3.

heading: 5.2 SINUSOID REGRESSION
text: We conducted a sinusoid regression, where each task is to regress a sine wave with amplitude in the range of [0.1, 5.0] and phase in the range of [0, π] based on data points in the range of [-5.0, 5.0]. A multilayer perceptron with two hidden units of size 40 and ReLU was trained with SGD. The batch size of data was 10, the number of tasks was 100, and 1 step was taken for update. Using these settings, we computed the training loss after 500 iterations with α in the range of [1e-4, 9e-1] and β in the range of [1e-2, 9e-0]. Fig. 4 (a) shows the training losses with various values of α and β. The dashed line indicates β of α = 0 over which training loss diverges. According to Fig. 4 (a), if α is close to the value above which the losses diverge, a larger β can be used. As explained above, we did not put any simplification as we did in Section 3 and 5.1 in the experiment, meaning that we used different data for updating task-specific parameter and meta parameter, considered multiple tasks, and employed not steepest GD but SGD as optimizer. Despite simplifications, surprisingly, this result confirms the expectation that MAML allows larger β if α is close to αc.

heading: 5.3 CLASSIFICATION
text: We performed classification of the Omniglot and MiniImagenet datasets (Lake et al., 2011; ravi & Larochelle, 2017), which are benchmark datasets for few-shot learning. The model used was essentially the same as that Finn et al. (2017), and hence, Vinyals et al. (2016) used. The task is a five-way one-shot classification, where the query size is 15, the number of update steps is two, and the task batch size is 32 for Omniglot and four for MiniImagenet. In this setup, we computed
the training losses after 100 iterations for the Omniglot dataset and one epoch for the MiniImagenet dataset with various values of α and β; for Omniglot, α was in the range of [1e-3, 9e-0] and β was in the range of [1e-1, 9e+1], and for MiniImagenet, α was in the range of [1e-4, 9e-1] and β was in the range of [1e-2, 9e-0]. Fig. 4 (b) and (c) show the training losses of classification task at various values of α and β. The dashed line indicates β of α = 0 above which training loss diverges. As shown in Fig. 4 (b) and (c), the maximum β is larger at large α. Even though the model architecture is composed of convolutional layer, max-pooling, and batch normalization (Ioffe & Szegedy, 2015) and practical dataset is used for training, our expectation is confirmed in this case as well. This result confirms that our theory is applicable in practice.
Our experimental result confirms that larger α is good for stabilizing MAML training. According to Fig. 4 (a), (b) and (c), moreover, while large β does not necessarily make training loss smaller, employing large α leads to smaller training loss comparatively. These result has a practical implication for tuning the learning rates: first, the largest possible α should be identified, and β may be subsequently tuned based on the value of α. Once you identify αc, MAML is likely to work well even if meta-learning rate is roughly chosen. Taking large α is desirable for the goal of MAML as well. The aim of MAML is to find a good initial parameter which quickly adapt to new tasks and the quickness is determined by inner learning rate α because α determines the step size from initial parameter to task-specific parameter when model is fine-tuned. Therefore, identifying αc is not only good for robustifying the model against divergence but also good for finding good initial parameter.

heading: 6 CONCLUSIONS
text: We regard a simplified MAML as training with the negative gradient penalty. Based on this formulation, we derived the sufficient condition of the inner learning rate α and the meta-learning rate β for the simplified MAML to locally converge to local minima from any point in the vicinity of the local minima. We showed that the upper bound of β required for the simplified MAML to locally converge to local minima depends on α. Moreover, we found that if α is close to its upper bound αc, the maximum possible meta-learning rate βc is larger than that used while training with ordinary SGD. This finding is validated by experiments, confirming that our theory is applicable in practice. According to this result, we propose a guideline for determining α and β; first, search for α close to αc; next, tune β based on the selected value of α.

heading: A NEGATIVE GRADIENT PENALTY: GENERAL CASE
text: In Section 2, we explained the simplest case of training data and test data being the same, only one task being considered and only one step being taken for update. In this section, we analyze the cases of waiving one of these simplifications. Here, we will interpret the simplified MAML loss as a Taylor series expansion of the MAML loss for the first-order term.
A.1 WHEN THE TRAINING DATA AND TEST DATA ARE DIFFERENT
When using different data to compute the losses for updating the task-specific parameters and the meta parameters as done in practical applications, the simplified loss is as follows:
L̃(θ) = Ltest(θ − α∇θLtrain(θ)) (27) ≈ Ltest(θ)− αg(θ)test⊤g(θ)train. (28)
where Ltrain and Ltest represent the loss values for training and test data, respectively, and gtrain and gtest are gradients of these losses.
A.1.1 WHEN MULTIPLE TASKS ARE CONSIDERED
When multiple tasks are considered, as MAML does, the meta-loss L̂(θ) is just a sum of losses L̃τ (θ) for all tasks τ :
L̂(θ) = ∑
τ∼P (τ)
L̃τ (θ) = ∑
τ∼P (τ)
( Ltestτ (θ)− αgτ (θ)test⊤gτ (θ)train ) . (29)
A.2 WHEN k STEPS ARE TAKEN DURING THE UPDATE
If task-specific parameters are updated with k-step SGD, the loss can be written as follows;
L̃k(θ) = Lk(θ)− α ( k∑ i g⊤k (θ)gi(θ) ) . (30)
Note that Li(θ) is the loss computed with the data at the ith step, and gi(θ) is the gradient of the loss.

heading: B CALCULATION OF H̃
text: Because H̃ is the Hessian matrix of L̃ at θ∗, we derive the Hessian of Eq. 8. Then,
H̃ = ∇2θL̃(θ) (31) = ∇2θ ( L(θ)− α
2 g(θ)⊤g(θ)
) (32)
= H(θ)− α∇θ (H(θ)g(θ)) (33) = H(θ)− α (∇θH(θ)g(θ) +H(θ)H(θ)) (34) = H − α(Tg +H2). (35)
C MAGNITUDE OF Tg AND H2
We conducted a sinusoid regression with essentially the same condition that we explain in Section 5.2 except that the total number of iterations is 50000 and learnig rates are fixed. Parameters α and β are 1e-2 and 1e-3 respectively. We calculated Tg numerically with the training error at the end of the training. As we showed in Section 3, especially large eigenvalues of H̃ are important for the upper bounds of learning rates. Therefore, if λ(Tg + H2)max ≈ λ(H2)max, we can ignore Tg when deriving the condition. We calculate the maximum and the second-largest eigenvalues of Tg, H2 and Tg+H2 of the trained model. As shown in Fig. 5 (a), λ(Tg+H2)max is almost equal to
λ(H2)max, and λ(Tg)max is by far smaller than them. Therefore, ignoring λ(Tg)max is reasonable when the conditions are derived. Furthermore, we calculate the Frobenius norm of Tg and H2. As Fig. 5 (b) indicates, the Frobenius norm of Tg is much smaller than that of H2, meaning that Tg is negligible in the sense of the magnitude of the norm as well. These results confirm that we can neglect Tg when considering H̃ .
D CONVERGENCE CONDITION WHEN Tg IS CONSIDERED
We assumed that Tg was negligible in Section 3. In this section, we derive a sufficient condition of α and β for the simplified MAML to locally converge to local minima from any point in the vicinity of the local minima under some assumptions when Tg is considered.
D.1 CONDITION FOR INNER LEARNING RATE α TO SATISFY
When Tg is considered, the Hessian matrix of the simplified MAML loss L̃ is H̃ = H − α ( Tg +H2 ) . Because H − α ( Tg +H2 ) is a real symmetric matrix, it can be diagonalized. Then, the sufficient condition that a fixed point θ∗ is a local minimum is
∀i, λ(H̃)i = λ(H − α ( Tg +H2 ) )i > 0. (36)
Note that Tg and H are not simultaneously diagonalizable, so we cannot decompose λ(H̃)i into eigenvalues of each matrix as we did in Section 3. Therefore, we have to consider the relationship among λ(H̃)i, λ(H)i and λ(Tg)i. In general, it is known that n× n Hermitian matrices A and B satisfy the following equation (Bhatia, 2001):
λ↓(A) + λ↑(B) ≺ λ(A+B), (37)
where λ(A) represents a vector with elements that are eigenvalues of A, ↑ indicates the operation of sorting a vector in the ascending order, and ↓ indicates that in the descending order. If two real vectors x,y ∈ Rd are related in the following way, x is said to be majorized by y and the relationship is written as x ≺ y:
k∑ i=1 x↓i ≤ k∑ i=1 y↓j for 1 ≤ k ≤ d, (38)
d∑ i=1 x↓i = d∑ i=1 y↓i . (39)
We define A = H − αH2 and B = −αTg; then,
λ↓(A) + λ↑(B) ≺ λ(A+B) (40) ⇒ λ↓(A)− αλ↓(Tg) ≺ λ(A+B) (41)
⇒ k∑
i=1
(λ↓(A)i − αλ↓(Tg)i) ≤ k∑
i=1
λ↓(A+B)i for 1 ≤ k ≤ d. (42)
Let us suppose that for top k eigenvalues of A, Tg, and A +B, conditions λ(A +B)i ≈ cA+B , λ(Tg)i ≈ cTg and λ(A)i ≈ cA hold, where cA+B , cA and cTg are some constant values. Then,
λ(A)i − αλ(Tg)i ≤ λ(A+B)i for 1 ≤ i ≤ k (43) ⇒ λ(H − αH2)i − αλ(Tg)i ≤ λ(H − α(Tg +H2))i for 1 ≤ i ≤ k. (44)
The sufficient condition for a fixed point θ∗ to be a local minimum is
∀i, λ(H − αH2)i − αλ(Tg)i > 0 (45)
Now, we assume that all eigenvalues of H below a threshold are 0; λ(H)i ≈ 0 for k < i ≤ n. In fact, many eigenvalues of the loss computed by a trained model such as a deep neural network are known to be very small. Thus, if the following condition is satisfied, it is enough to say that the condition is satisfied:{
λ(H − αH2)i − αλ(Tg)i > 0 for 1 ≤ i ≤ k αλ(Tg)i < 0 for k ≤ i ≤ d
(46)
⇒ { λ(H)i − αλ(H)2min − αλ(Tg)i > 0 for 1 ≤ i ≤ k λ(Tg)i < 0 for k ≤ i ≤ d
(47)
⇔ { λ(H)i − α(λ(H)2min + λ(Tg)i) > 0 for 1 ≤ i ≤ k λ(Tg)i < 0 for k ≤ i ≤ d
(48)
⇒ { λ(H)i − αλ(Tg)i > 0 for 1 ≤ i ≤ k λ(Tg)i < 0 for k ≤ i ≤ d (∵ λ(H)min = 0) (49)
In other words, if the smaller d− k eigenvalues of Tg are not negative values, the fixed point is not guaranteed to be a minimum, and if they are negative, satisfying Eq. 49 is sufficient.
D.2 CONDITION FOR META LEARNING RATE β TO SATISFY
Next, we derive a sufficient condition of meta-learning rate β. Our analysis will be based on the assumptions identical to those mentioned above. If the inequalities in Eq. 49 hold, it is sufficient for β to satisfy
∀i, −1 + β ( λ(H − αλH2)i − αλ(Tg)i ) ≤ −1 + βλ(H − α(Tg +H2))i < 1 (50)
⇒ ∀i, β < 2 λ(H)i − αλ(Tg)i (∵ λ(H)min = 0) (51)
for the condition of local convergence.

heading: E EXPERIMENT WITH ADAM
text: We conducted the same experiment as that explained in Section 5.2 and 5.3, but this time, we used Adam optimizer instead of SGD for the meta-optimizer (Kingma & Ba, 2014). The results are different from those we showed in Section 5. For training with Adam, MAML no longer allows us to use larger βc. Because Adam has more parameters that we have to consider than SGD does, this result is not at all surprising. Nonetheless, it is important to keep these facts in mind when Adam is used for MAML optimization.

Review summaries:
The authors study a method to help tuning the two learning rates used in the MAML training algorithm. First, they derive a necessary condition for the convergence of the gradient descent in the single task setting. The condition relies on the eigenvalues of the Hessian of the task loss. This condition is reminiscent of convergence criteria for gradient descent on quadratic objectives, and the authors make the interesting observation that the criteria for the exterior learning rate beta depends on the interior learning rate alpha. 

This paper studies the two learning rates \alpha and \beta used in Model-Agnostic Meta-Learning (MAML) algorithm by [Finn et al., 2017]. MAML is known to be difficult to train, and part of the reason why is the need to tune the two learning rates. Under simplifications, the paper derives some necessary conditions on \alpha and \beta for the MAML iterates to converge to local minima, and then verifies the theory by experiments on synthetic and real-world data.