Effective Meta-Regularization by Kernelized Proximal Regularization
Year: 2021

Abstract:
We study the problem of meta-learning, which has proved to be advantageous to accelerate learning new tasks with a few samples. The recent approaches based on deep kernels achieve the state-of-the-art performance. However, the regularizers in their base learners are not learnable. In this paper, we propose an algorithm called MetaProx to learn a proximal regularizer for the base learner. We theoretically establish the convergence of MetaProx. Experimental results confirm the advantage of the proposed algorithm.

heading: 1 Introduction
text: Humans, by leveraging prior knowledge and experience, can easily learn new tasks from a handful of examples. In contrast, deep networks are data-hungry, and a large number of training samples are required to avoid overfitting. To reduce the labor-intensive and time-consuming process of data labeling, meta-learning (or learning to learn) [3, 37] aims to exact meta-knowledge from seen tasks to accelerate learning on unseen tasks. Recently, meta-learning has been receiving increasing attention due to its diverse successful applications in few-shot learning [41, 12, 39, 35], hyperparameter optimization [14], neural architecture search [24, 44], and reinforcement learning [29].
Many meta-learning algorithms operate on two levels. A base learner learns task-specific models in the inner loop, and a meta-learner learns the meta-parameter in the outer loop. A popular class of algorithms is based on meta-initialization [12, 25, 11, 38], such as the well-known MAML [12]. It learns a model initialization such that a good model for an unseen task can be learned from limited samples by a few gradient updates. However, computing the meta-gradient requires back-propagating through the entire inner optimization path, which is infeasible for large models and/or there are many gradient steps. During testing, it is common for MAML’s base learner to perform many gradient steps to seek a more accurate solution [12]. However, for regression using a linear base learner and square loss, we will show that though the meta-learner can converge to the optimal meta-initialization, the base learner may overfit the training data at meta-testing.
Another class of meta-learning algorithms is based on meta-regularization [28, 43, 7, 8, 9], in which the base learner learns the task-specific model by minimizing the loss with a proximal regularizer (a biased regularizer from the meta-parameter). Denevi et al. [7] uses a linear model with efficient closed-form solution for the base learner. However, extending to nonlinear base learners requires computing the meta-gradient using matrix inversion, which can be infeasible for deep networks [28].
To introduce nonlinearity to the base learner, a recent approach is to make use of the kernel trick. For example, R2D2 [4] and MetaOptNet [22] use deep kernels [42] in meta-learning for few-shot
∗Corresponding author.
35th Conference on Neural Information Processing Systems (NeurIPS 2021).
classification. Specifically, the deep network is learned in the meta-learner, while a base kernel is used in the base learner. Though they achieve state-of-the-art performance, their base learners use a Tikhonov regularizer rather than a learnable proximal regularizer as in meta-regularization methods.
As learning a meta-regularization has been shown to be effective in linear models for regression [7] and classification [8], in this paper we propose a kernel-based algorithm to meta-learn a proximal regularizer for a nonlinear base learner. After kernel extension, the learnable function in the proximal regularizer is a function in the reproducing kernel Hilbert space (RKHS) induced by the base kernel. The proposed algorithm is guaranteed to converge to a critical point of the meta-loss and its global convergence is also established. Experiments on various benchmark regression and classification datasets demonstrate the superiority of the proposed algorithm over the state-of-the-arts. Notations. Vectors are denoted by lowercase boldface, and matrices by uppercase boldface. For a vector x, ‖x‖ = √∑ i x 2 i and diag(x) constructs a diagonal matrix with x on the diagonal. ‖ · ‖H is the norm on the Hilbert spaceH. N (0, σ2) is the univariate normal distribution with mean zero and variance σ2. N (m,Σ) is the multivariate normal distribution with mean m and covariance matrix Σ.

heading: 2 Related Work
text: In meta-learning, a collection T of tasks are used to learn a meta-parameter θ and base learner’s parameters {w1, . . . ,w|T |}. Each task τ is sampled from a given distribution p(τ), and has a support set Sτ = {(xi, yi) : i = 1, . . . , ns} and a query set Qτ = {(xi, yi) : i = 1, . . . , nq}, where x ∈ Rd are the features and y the labels. Let f(·; w) be a model parameterized by w and L(D; w) ≡ ∑ (x,y)∈D `(f(x; w), y) be the supervised loss on data set D, where `(·, ·) is a loss function that is assumed to be convex w.r.t. the first argument. In each meta-training iteration, a batch B of tasks are randomly sampled from T . The base learner takes a task τ from B and the meta-parameter θ to build the model f(·; wτ ). After all tasks in the batch are processed by the base learner, the meta-learner minimizes the loss ∑ τ∈B L(Qτ ; wτ ) w.r.t. θ, and the iteration repeats. During meta-testing, given an unseen task τ ′ ∼ p(τ), a model f(·; wτ ′) is similarly learned from Sτ ′ and θ. Finally, its performance is evaluated on Qτ ′ .
Popular meta-learning algorithms usually construct the task-specific model by: (i) metainitialization [12, 25, 11, 38], (ii) meta-regularization [7, 8, 9, 28, 43], or (iii) metric learning [35, 4, 22, 27]. A representative meta-learning algorithm based on meta-initialization is MAML [12]. Its base learner learns wτ by gradient descent from a learnable initialization. Computing the meta-gradient ∇θL(Qτ ; wτ ) needs to back-propagate through the inner optimization path and involves second-order derivatives. This can be expensive for large models and/or when there are many gradient steps.
For meta-learning algorithms based on meta-regularization, the base learner learns wτ by minimizing a proximal regularized loss
L(Sτ ; w) + λ
2 ‖w − θ‖2, (1)
where λ > 0 is the regularization parameter. The meta-gradient can be computed directly from the learned wτ , without back-propagating through the inner optimization trajectory [28]. Though more efficient, this still takes O(n3θ) time [28], where nθ is the number of parameters in θ. Metric learning methods have been widely studied in few-shot learning [39, 35, 4, 22, 27]. The meta-learner maps raw samples to an embedding space via a a deep network, then feeds the embeddings to the base learner to train a simple task model. Typical models include non-parametric prototype classifier (ProtoNet [35]), linear models like ridge regression (R2D2 [4]), SVM classifier (MetaOptNet-SVM [22]), and softmax classifier (ANIL [27]). In particular, the base learners in R2D2 [4], MetaOptNet [22] and DKT [26] seek solutions in the dual space, which achieve state-ofthe-art performance. However, their base learners use a Tikhonov regularizer, which is not learnable as in meta-regularization approaches.

heading: 3 Meta-Regularization by Kernelized Proximal Regularization

heading: 3.1 Meta-Initialization versus Meta-Regularization
text: In this section, we consider a simple regression setting with linear model and square loss. Each task τ is a linear regressor with parameter w∗τ ∈ Rd. We assume that each input x is sampled
Algorithm 1 MAML [12]. Require: step size γ and ηt, batch size b; 1: for t = 1, 2, 3, . . . do 2: sample a batch Bt of tasks from p(τ); 3: base learner: 4: for τ ∈ Bt do 5: w(gd)τ = ψt − γX>τ (Xτψt − yτ ); 6: gτ = 12 ∑ (x,y)∈Qτ ∇ψt(x
>w(gd)τ − y)2; 7: end for 8: meta-learner: ψt+1 = ψt − ηtb ∑ τ∈Bt gτ ; 9: end for
Algorithm 2 CommonMean [7]. Require: hyperparameter λ, step size ηt, batch size b; 1: for t = 1, 2, 3, . . . do 2: sample a batch Bt of tasks from p(τ); 3: base learner: 4: for τ ∈ Bt do 5: w(prox)τ = minw 12‖Xτw−yτ‖ 2+ λ 2 ‖w−θt‖2;
6: gτ = 12 ∑ (x,y)∈Qτ ∇θt(x >w (prox) τ − y)2; 7: end for 8: meta-learner: θt+1 = θt − ηtb ∑ τ∈Bt gτ ; 9: end for
from N (0, σ2xI), and the output y is obtained as x>w∗τ + ξ, where ξ ∼ N (0, σ2ξ ) is the random noise. We compare two representative meta-learning algorithms: (i) MAML [12], which is based on meta-initialization and performs one gradient descent step in the inner loop of the bilevel optimization problem; and (ii) learning around a common mean (denoted CommonMean) [7], which is based on meta-regularization. It learns the model parameters for task τ by minimizing the loss with a proximal regularizer around the meta-parameter θ:
w(prox)τ =argmin w ∑ (xi,yi)∈Sτ 1 2 (w>xi−yi)2+ λ 2 ‖w−θ‖2 = (λI+X>τ Xτ )−1(λθ+X>τ yτ ), (2)
where Xτ = [x>1 ; . . . ; x > ns ] is the sample matrix from Sτ , and yτ = [y1; . . . ; yns ] is the corresponding label vector. Algorithms 1 and 2 show MAML and CommonMean, respectively, for this problem.
Recently, Balcan et al. [2] study the convex online meta-learning setting and show that both approaches achieve the same average task regret. Here, we consider the offline setting. First, the following Proposition shows that both MAML and CommonMean converge to the same meta-parameter. All proofs are in the appendix.
Proposition 1. Let ηt = 1/t. Assume that γ < 1/σ2x. Both ψt in MAML (with one inner gradient step) and θt in CommonMean converge to w̄ = Eτw∗τ .
The following Proposition shows that w̄ in Proposition 1 is also the best ψ (for MAML) or θ (for CommonMean) with the smallest population risk for this meta-learning problem.
Proposition 2. Assume that γ < 1/σ2x. We have w̄ = argminθ EτESτEQτ ∑ (x,y)∈Qτ(x >w (prox) τ −
y)2 =argminψ EτESτEQτ ∑ (x,y)∈Qτ (x >w (gd) τ −y)2.
During meta-testing, we sample a task τ ′ ∼ p(τ) with parameter w∗τ ′ . Let Xτ ′ be the sample matrix from Sτ ′ , and yτ ′ be the corresponding label vector. We assume that Xτ ′ is full rank and ns < d. To simplify notations, we drop the subscript τ ′ in the following. Let the singular value decomposition of X be UΣV> (where Σ = diag([ν1, . . . , νns ])), and V ⊥ be V’s orthogonal complement.
As only forward passes are needed, it is common for the base learner in MAML to perform multiple gradient steps [12]. With the convex loss and linear model here, the base learner can obtain a globally optimal solution w(gd∞) directly (which is equivalent to taking infinite gradient steps). As is common in few-shot learning, the number of support samples is much smaller than feature dimensionality. Hence, w(gd∞) is not unique but depends on the learned initialization. Let w(gd∞) be written as w(gd∞) = Va(gd∞) + V⊥b(gd∞). For gradient descent, its update direction X>(Xw − y) = VΣU>(Xw − y) is always in the span of V and so b(gd∞) remains unchanged.
Let w∗ and θ be written as w∗ = Va∗ + V⊥b∗ and θ = Va0 + V⊥b0. Moreover, let ã = a0 − a∗ and b̃ = b0 − b∗. Proposition 3 ([17]). Assume that γ < min1≤j≤ns 1/ν2j . We have Eξ‖w(gd∞)−w∗‖2 = ‖b(gd∞)−
b∗‖2 + ∑ns j=1 ( σξ νj )2 , where the expectation is over the label noise vector ξ.
For CommonMean, using the Woodbury matrix identity, w(prox) = θ+X>(λI+XX>)−1(y−Xθ) = V(a0 + ΣU
>(λI + XX>)−1(y − Xθ)) + V⊥b0 ≡ Va(prox) + V⊥b(prox), where b(prox) = b0. Assume that w(gd∞) is initialized with θ. Since b(gd∞) remains unchanged, w(prox) and w(gd∞) only differ in the components lying in the column space of V.
Proposition 4. Eξ‖w(prox) −w∗‖2 = ‖b̃‖2 + ∑ns j=1 ( λãj λ+ν2j )2 + ∑ns j=1 ( σξ (λ/νj)+νj )2 , where the expectation is over the label noise vector ξ.
As can be seen, when the labels are noise-free (σ2ξ = 0), w (gd∞) performs better than w(prox). However, when the labels are noisy, as ns < d, gradient descent always converges to zero training error and overfits the noisy labels. On the other hand, the estimation error of w(prox) equals to that of w(gd∞) when λ = 0. For λ > 0, it trades off between fitting the noisy labels (the last term in Proposition 4) and introducing an estimation bias of a∗ (the second term in Proposition 4).

heading: 3.2 Proposed Algorithm
text: It is straightforward to use the dual formulation for the CommonMean algorithm. When the square loss is used as `(·, ·), it is easy to see that the dual variable has the closed-form solution
ατ = (I + λ −1XτX > τ ) −1(yτ −Xτθ). (3)
Compared with the primal formulation, we only need to invert a ns × ns matrix (instead of the d× d matrix λI + X>τ Xτ ). In meta-learning, usually ns d (e.g., ns = 5). From the dual solution ατ , the primal solution can be recovered as wτ = θ + λ−1X>τ ατ . Given a query example (x, y) ∈ Qτ , the model predicts ŷ = x>wτ = x>θ + λ−1x>X>τ ατ . The loss gradient is ∇θ`(ŷ, y) = ∇1`(ŷ, y)∇θ ŷ, where ∇1`(ŷ, y) denotes the gradient w.r.t. the first argument, and ∇θ ŷ = x + λ−1(∇θατ )>Xτx,∇θατ = −(I + λ−1XτX>τ )−1Xτ . The complexity of computing ∇θ`(ŷ, y) is thus very low (O(n3s + n2sd)). The dual formulation also allows introduction of nonlinearity with the kernel trick. Based on deep kernels [42], recent state-of-the-arts (R2D2 [4], MetaOptNet [22], and DKT [26]) propose to use a base kernel in the base learner and update the deep network in the meta-learner. However, their regularizers are not learnable. We consider to learn a proximal regularizer. An input x is mapped to z = NN(x;φ) in an embedding space E via a deep network parameterized by φ. With the dual formulation, θ in (2) allows extra flexibility over [22, 4, 7]. Specifically, θ becomes a function fθ ∈ H, the reproducing kernel Hilbert space (RKHS) corresponding to a given kernel function K on E × E . The base learner obtains a model fτ ∈ H by minimizing
min f∈H ∑ (xi,yi)∈Sτ `(f(zi), yi) + λ 2 ‖f − fθ‖2H , (4)
where ‖ · ‖H is the norm on H. By setting fθ = 0, this recovers the state-of-the-arts of MetaOptNet [22], R2D2 [4], and DKT [26]. However, Proposition 4 suggests that a good fθ provides good meta-knowledge by biasing the task model.
By the representer theorem [34], the solution of (4) is fτ = fθ + ∑
(xi,yi)∈Sτ ατ,iKzi , where Kzi = K(zi, ·) ∈ H, and ατ = [ατ,1; . . . ;ατ,ns ] is obtained from the convex program
min ατ ∑ (xi,yi)∈Sτ `(fτ (zi), yi) +α > τ K(Zτ ,Zτ )ατ , (5)
where Zτ = [z>1 ; . . . ; z > ns ], and K(Zτ ,Zτ ) is the kernel matrix. Note that the hyperparameter λ in (4) is absorbed into z as the network is learnable. With the square loss, the dual solution of (5) is ατ = (I +K(Zτ ,Zτ ))−1(yτ − fθ(Zτ )), where fθ(Zτ ) = [fθ(z1); . . . ; fθ(zns)]. For general loss functions, the dual problem has no closed-form solution, but this has only ns variables (which is usually small) and can be solved efficiently.
After the base learner has obtained the dual solution ατ , the meta-learner updates fθ and network parameter φ by one gradient descent step on the validation loss ∑ (x,y)∈Qτ `(ŷ, y), where ŷ ≡ fτ (z) = fθ(z) +K(Zτ , z)>ατ . Using the chain rule, ∇(θ,φ)`(ŷ, y) = ∇1`(ŷ, y)∇(θ,φ)ŷ. The first component∇1`(ŷ, y) can be computed directly and the second component is
∇(θ,φ)ŷ = ∇(θ,φ)fθ(z) + (∇(θ,φ)K(Zτ , z))>ατ + (∇(θ,φ)ατ )>K(Zτ , z). (6)
Both ∇(θ,φ)fθ(z) and ∇(θ,φ)K(Zτ , z) can be obtained by direct differentiation. By the chain rule,∇(θ,φ)ατ = ∇pατ∇(θ,φ)p, where p = [fθ(z1); . . . ; fθ(zns);K(Zτ , z1); . . . ;K(Zτ , zns)] ∈ Rns+n2s is the input to the dual problem. ∇(θ,φ)p can be directly computed. When the square loss is used, ∇pατ = −(I + K(Zτ ,Zτ ))−1 [ I | I⊗α>τ ] . For a general loss, ατ is obtained by solving the convex program. Hence, ατ depends implicitly on p and ∇pατ can be obtained by implicit differentiation. Denote the dual objective in (5) by g(p,α). By the implicit function theorem [32], ∇pατ = − ( ∇2αg(p,ατ ) )−1 ∂2 ∂p∂αg(p,ατ ),
where ∇2αg(p,ατ ) = ∑ (xi,yi)∈Sτ ∇ 2 1`(fτ (zi), yi)K(Zτ , zi)K(Zτ , zi)> + K(Zτ ,Zτ ),
∂2 ∂p∂αg(p,ατ ) = [ K(Zτ ,Zτ )D | (K(Zτ ,Zτ )D)⊗α>τ + v> ⊗ I + I⊗α>τ ] , D = diag([∇21`(fτ (z1), y1); . . . ;∇21`(fτ (zns), yns)]), v = [∇1`(fτ (z1), y1); . . . ;∇1`(fτ (zns), yns)], where ⊗ is the Kronecker product. The whole procedure, called MetaProx, is shown in Algorithm 3. Let nφ and nθ be the numbers of parameters in φ and θ, respectively. Computing ∇(θ,φ)`(ŷ, y) takes O(n3s + n2s(nθ + nφ)) time, which is linear in the number of meta-parameters. This is lower than the other meta-learning algorithms (e.g., MAML [12] with single step takes O(n2φ) time, iMAML [28]: O(n3φ), CommonMean [7]: O(d3)).
Algorithm 3 MetaProx. Require: step size ηt, batch size b;
1: for t = 1, 2, · · · , T do 2: sample a batch Bt of tasks from T ; 3: base learner: 4: for τ ∈ Bt do 5: zi = NN(xi;φt) for each (xi, yi) ∈ Sτ ; 6: fτ (z;α) ≡ fθt(z) +K(Zτ , z)>α denote the task model w.r.t. dual variables; 7: ατ = argminα ∑ (xi,yi)∈Sτ `(fτ (zi;α), yi) +α
>K(Zτ ,Zτ )α; 8: gτ = ∑ (x,y)∈Qτ ∇(θt,φt)`(ŷ, y), where ŷ = fτ (z;ατ ) and z = NN(x;φt);
9: end for 10: meta-learner: (θt+1,φt+1) = (θt,φt)− ηtb ∑ τ∈Bt gτ ; 11: end for
Classification. We consider extension from regression to N -way classification. For task τ , the base learner learns the model fτ = [f (1) τ ; . . . ; f (N) τ ] for the N classes by minimizing
min f(1),...,f(N)∈H ∑ (xi,yi)∈Sτ `(ŷi, yi) + λ 2 ∑N c=1 ‖f (c) − fθ(c)‖2H, (7)
where ŷi = [f (1)(zi); . . . ; f (N)(zi)], and fθ(1) , . . . , fθ(N) ∈ H are functions learned by the metalearner. By the representer theorem [34], fτ = [fθ(1) +K(Zτ , ·)>α (1) τ ; . . . ; fθ(N) +K(Zτ , ·)>α (N) τ ],
where [α(1)τ ; · · · ;α(N)τ ] is obtained from the convex program minα(1),...,α(N) ∑
(xi,yi)∈Sτ `(ŷi, yi)+∑N c=1α
(c)>K(Zτ ,Zτ )α(c). As [α(1)τ ; · · · ;α(N)τ ] ∈ RNns and both N,ns are typically very small (e.g., N = 5, ns = 5 in 5-way 5-shot classification), this convex program can be solved efficiently. The meta-learner then updates the network parameter φ and {fθ(1) , . . . , fθ(N)} by one gradient descent step on the validation loss ∑ (xi,yi)∈Qτ `(ŷi, yi). Computing∇(θ(1),...,θ(N),φ)`(ŷ, y) takes
O((Nns)3 + (Nns)2(nφ + ∑N c=1 nθ(c))) time, where nθ(c) is the size of θ
(c). This is again linear in the number of meta-parameters and thus very efficient.

heading: 3.3 Theoretical Analysis
text: Let Lmeta(θ,φ) = 1|T | ∑ τ∈T ∑ (x,y)∈Qτ `(fθ(z;ατ ), y) be the empirical loss of
Eτ∼p(τ) ∑
(x,y)∈Qτ `(fθ(z;ατ ), y), where z = NN(x;φ). With the linear kernel and square loss, the dual solution (3) is affine in the meta-parameter, and so is the primal solution wτ = θ + λ
−1X>τ ατ . Thus, the meta-loss Lmeta(θ,φ) is convex and convergence follows from convex optimization [5, 7]. After introducing nonlinearity, the meta-loss is no longer convex. The following introduces Lipschitz-smoothness assumptions, which have been commonly used in stochastic non-convex optimization [15, 31] and meta-learning in non-convex settings [11, 43].
Assumption 1 (Smoothness). (i) The deep network NN(x;φ) is Lipschitz-smooth, i.e., ‖∇φNN(x;φ) − ∇φNN(x;φ′)‖ ≤ β1‖φ − φ′‖ with a Lipschitz constant β1 > 0; (ii) the kernel K(z, z′) is Lipschitz-smooth w.r.t. (z, z′); (iii) fθ(z) is Lipschitz-smooth w.r.t. (θ, z); (iv) ∇21`(ŷ, y) is Lipschitz w.r.t. ŷ, i.e., |∇21`(ŷ, y) − ∇21`(ŷ′, y)| ≤ β2|ŷ − ŷ′| with a Lipschitz constant β2; (v) Eτ∼T ‖∇(θ,φ) ∑ (x,y)∈Qτ `(fθ(z;ατ ), y) − ∇(θ,φ)Lmeta(θ,φ)‖
2 = σ2g, where τ ∼ T denotes uniformly sample a task from T .
The following Lemma guarantees smoothness of the meta-loss. Lemma 1. Lmeta(θ,φ) is Lipschitz-smooth w.r.t. (θ,φ) with a Lipschitz constant βmeta. Theorem 1. Let the step size be ηt = min(1/ √ T , 1/2βmeta). Algorithm 3 satisfies
min1≤t≤T E‖∇(θt,φt)Lmeta(θt,φt)‖2 = O ( σ2g/ √ T ) , where the expectation is taken over the random training samples.
This rate is the same as MAML [11, 19] and Meta-MinibatchProx [43]. For MAML with J > 1 gradient steps, Ji et al. [19] assumes that the step size in the inner loop is of the order 1/J. This slows down inner loop learning when J is large. On the other hand, MetaProx does not have this restriction, as its meta-gradient depends only on the last iterate rather than all iterates along the trajectory.
Next, we study the global convergence of MetaProx. Prior work [13, 43] focus on the case where Lmeta(θ,φ) is strongly convex in (θ,φ). This can be restrictive in deep learning. We instead only require `(ŷ, y) to be strongly convex in ŷ. This assumption is easily met by commonly-used loss functions such as the square loss and logistic loss with a compact domain. A recent work [40] studies the global convergence of MAML in over-parameterized neural networks. Over-parameterization is closely related to the assumption of uniform conditioning [18, 21, 23]. Assumption 2 (Uniform conditioning [23]). A multivariable function M(θ,φ) is µ-uniformly conditioning if its tangent kernel [18] satisfies min(θ,φ) λmin(∇(θ,φ)M(θ,φ)∇>(θ,φ)M(θ,φ)) ≥ µ > 0, where λmin(·) is the smallest eigenvalue of the matrix argument.
Assume that the loss `(·, ·) is ρ-strongly convex w.r.t. the first argument and Assumption 1 holds. Let xτ,j be the jth query example of task τ , zτ,j be its embedding, and ŷτ,j = fθ(zτ,j) + K(Zτ , zτ,j)>ατ be its prediction, where ατ is the dual solution. Let M(θ,φ) =[ ŷτ1,1; . . . ; ŷτ1,nq ; . . . ; ŷτ|T |,1; . . . ; ŷτ|T |,nq ] be an auxiliary function which maps the meta-parameter to predictions on all query examples. The following Theorem shows that the proposed algorithm converges to a global minimum of the empirical risk Lmeta(θ,φ) at the rate of O(σ2g/ √ T ). The rate is improved to exponential if the meta-learner adopts full gradient descent. Theorem 2. Assume thatM(θ,φ) is uniform conditioning. (i) Let ηt = min(1/ √ T , 1/2βmeta). Algo-
rithm 3 satisfies min1≤t≤T ELmeta(θt,φt)−min(θ,φ) Lmeta(θ,φ) = O ( σ2g/ √ T ) , where the expectation is taken over the random training samples. (ii) Let ηt = η < min(1/2βmeta, 4|T |/ρµ) and Bt = T . Algorithm 3 satisfies Lmeta(θt,φt)−min(θ,φ) Lmeta(θ,φ) = O((1− ηρµ/4|T |)t).

heading: 4 Experiments

heading: 4.1 Few-shot Regression
text: Data sets. Experiments are performed on three data sets.
(i) Sine. This is the sinusoid regression problem in [12]. Samples x’s are uniformly sampled from [−5, 5]. Each task τ learns a sine function y = aτ sin(x+ bτ ) + ξ, where aτ ∈ [0.1, 5], bτ ∈ [0, π], and ξ ∼ N (0, σ2ξ ) is the label noise. We consider both σ2ξ = 0 (noise-free) and σ2ξ = 1. In addition to the 5-shot setting in [12], we also evaluate on the more challenging 2-shot setting. We randomly generate a meta-training set of 8000 tasks, a meta-validation set of 1000 tasks for early stopping, and a meta-testing set of 2000 tasks for performance evaluation. (ii) Sale. This is a real-world dataset from [36], which contains weekly purchased quantities of 811 products over 52 weeks. For each product (task), a sample is to predict the sales quantity for the current week from sales quantities in the previous 5 weeks. Thus, each product contains 47 samples. We evaluate on the 5-shot and 1-shot settings. We randomly split the tasks into a meta-training set of 600 tasks, a meta-validation set of 100 tasks, and a meta-testing set of 111 tasks.
(iii) QMUL, which is a multiview face dataset [16] from Queen Mary University of London. This consists of grayscale face images of 37 people (32 for meta-training and 5 for meta-testing). We follow the setting in [26] and evaluate the model on 10-shot regression. Each person has 133 facial images covering a viewsphere of±90◦ in yaw and±30◦ in tilt at 10◦ increment. A task is a trajectory taken from the discrete manifold for images from the same person. The regression goal is to predict the tilt given an image. In the in-range setting, meta-training tasks are sampled from the entire manifold. In the more challenging out-of-range setting, meta-training tasks are sampled from the sub-manifold with yaw in [−90◦, 0◦]. In both settings, meta-testing tasks are sampled from the entire manifold. We randomly sample 2400 tasks for meta-training, and 500 tasks for meta-testing. As in [26], we do not use a meta-validation set since the dataset is small.
Network Architecture. For Sine and Sale, we use the network in [12], which is a small multilayer perceptron with two hidden layers of size 40 and ReLU activation. For QMUL, we use the three-layer convolutional neural network in [26]. The embeddings are always from the last hidden layer. We use a simple linear kernel as base kernel, and fθ(z) = θ>z.
Implementation Details. We use the Adam optimizer [20] with a learning rate of 0.001. Each minibatch has 16 tasks. For Sine and Sale, the model (φ and fθ) is meta-trained for 40, 000 iterations. To prevent overfitting on the meta-training set, we evaluate the meta-validation performance every 500 iterations, and stop training when the loss on the meta-validation set has no significant improvement for 10 consecutive evaluations. For QMUL, we follow [26] and meta-train the model for 100 iterations. We repeat each experiment 30 times. For performance evaluation, we use the average mean squared error (MSE) on the meta-testing set.
Baselines. On Sine and Sale, we compare MetaProx with CommonMean [7], MAML [12], MetaOptNet-RR [22], Meta-MinibatchProx [43], and iMAML [28]. CommonMean is a linear model, and MetaOptNet-RR is equivalent to MetaProx when fθ = 0. Following [12], we set the number of inner gradient steps for MAML to 1 during meta-training, and 20 during meta-validation and meta-testing. Both Meta-MinibatchProx [43] and iMAML [28] are meta-regularization approaches. For QMUL, we compare MetaProx with the baselines reported in [26] (namely, DKT [26], Feature Transfer [10], and MAML). As further baselines, we also compare with Meta-MinibatchProx and MetaOptNet-RR to evaluate the improvement of MetaProx due to the learnable fθ.
Results on Sine. Figure 1 shows the convergence curves of MetaProx and the baselines. We do not show the convergence of CommonMean, as it does not use a neural network backbone as the other methods. As can be seen, MetaProx converges much faster and better than the non-kernel-based methods (MAML, iMAML and Meta-MinibatchProx). In the 2-shot settings, MetaProx converges to a loss smaller than that of MetaOptNet-RR.
Figure 2 shows the learned functions on 2 meta-testing tasks (τ1 with (a = 4.6, b = 3.2) and τ2 with (a = 3.7, b = 0.5)) in the 5-shot setting and more challenging 2-shot setting. As can be seen, MetaProx always fits the target curve well. Though MAML, iMAML and Meta-MinibatchProx can fit the support samples, it performs worse in regions far from the support samples. This is especially noticeable in the 2-shot setting.
Table 1 shows the MSE on the meta-testing set. Obviously, CommonMean (a linear model) fails in this nonlinear regression task. MetaProx and MetaOptNet-RR significantly outperform the other baselines. MetaProx (with the learned fθ) performs better than MetaOptNet-RR, particularly when the data is noisy.
Results on Sale. As can be seen from Table 1, the linear model (CommonMean) performs poorly as expected. MetaProx again outperforms the other baselines, particularly in the more challenging 1-shot setting.
Results on QMUL. Table 2 shows that MetaProx achieves the lowest MSE and the kernel methods (DKT+RBF, DKT+Spectral, MetaOptNet-RR, and MetaProx) perform better than non-kernel-based methods (Feature Transfer, MAML, and Meta-MinibatchProx). MetaProx with the learnable fθ reduces the errors of MetaOptNet-RR by half.

heading: 4.2 Few-shot Classification
text: Datasets. We use the standard 5-way K-shot setting (K = 1 or 5) on the mini-ImageNet [39] dataset, which consists of 100 randomly chosen classes from ILSVRC-2012 [33]. Each class contains 600 84× 84 images. We use the commonly-used split in [30]: the 100 classes are randomly split into 64 for meta-training, 16 for meta-validation, and 20 for meta-testing.
Network Architecture. For the network backbone, we use the Conv4 in [12, 39] and ResNet12 in [22]. As the cosine similarity is more effective than `2 distance in few-shot classification [6], we adopt the cosine kernel K(z, z′) = cos(z, z′) as base kernel, where z is the embedding of sample x extracted from the last hidden layer as in regression. For each c = 1, . . . , 5, fθ(c) = [Kq(1) ; . . . ;Kq(5) ]>θ (c) is a weighted prototype classifier on the embedding space, where
q(1), . . . ,q(5) are the class centroids computed from Sτ , and the weights {θ(1), . . . ,θ(5)} are metaparameters.
Baselines. We compare MetaProx with the state-of-the-arts: (i) meta-initialization: MAML [12] and its variants FOMAML [12], and REPTILE [25]; (ii) meta-regularization: iMAML [28] and Meta-MinibatchProx [43]; and (iii) metric learning: ANIL [27], R2D2 [4], ProtoNet [35], and MetaOptNet [22] with SVM using the linear kernel and cosine kernel. .
Implementation Details. The entire model is trained end-to-end. `(ŷ, y) is the cross-entropy loss. The CVXPYLayers package [1] is used to solve the dual problem. We train the model for 80, 000 iterations, and each mini-batch has 4 tasks. We use the Adam optimizer [20] with an initial learning rate of 0.001, which is then reduced by half every 2, 500 iterations. To prevent overfitting, we evaluate the meta-validation performance every 500 iterations, and stop training when the meta-validation accuracy has no significant improvement for 10 consecutive evaluations. We report the classification accuracy averaged over 600 tasks randomly sampled from the meta-testing set.
Results. Tables 3 and 4 show the results for Conv4 and ResNet-12, respectively. As can be seen, MetaProx is always the best. Compared with MetaOptNet-SVM, MetaProx is better due to the learnable regularizer.

heading: 5 Conclusion
text: In this paper, we proposed MetaProx, an effective meta-regularization algorithm for meta-learning. MetaProx combines deep kernel and meta-regularization. By reformulating the problem in the dual space, a learnable proximal regularizer is introduced to the base learner. The meta-parameters in the regularizer and network are updated by the meta-learner. We also established convergence of MetaProx. Extensive experiments on standard datasets for regression and classification verify the effectiveness of learning a proximal regularizer.

heading: Acknowledgements
text: This work is supported by NSFC grant 62076118.

Review summaries:
The authors proposed a kernelized proximal regularization method (MetaProx) for meta learning. MetaProx combines deep kernel and proximal meta regularization, allowing learnable regularization by reformulating the proximal problem in dual space. Thorough theoretical analysis are provided as well as empirical studies on regression and classification task.

This paper introduces a new functional regularisation for meta learning. Often times meta learning algorithms can overfit to the training datasets and hence an introduction of a regularisation in terms of the outer loop parameters is a sensible choice. In particular, they build upon the Common mean algorithm and consider the dual form in which they can derive closed form solutions to the optimisation problem. Their main contribution is that the method remains computationally cheap, competitive in terms of performance and provide some theoretical insights into their proposed method MetaProx.

This paper proposes a new meta-learning algorithm. Following the meta-regularization method, this paper proposes a new proximal regularizer instead of the traditional regularizer to reduce the computational complexity significantly. The algorithm is reasonable and interesting which also shows high performance in experiments.

The authors proposed an effective meta-regularization algorithm (MetaProx) for meta-learning. A learnable proximal regularizer with deep kernel is introduced to learn the base learner. The computation complexity of meta-gradient is linear in the number of meta-parameters. Experiments on synthetic dataset and mini-ImageNet show that the proposed method outperforms the popular few-shot learning methods.