Fine-Grained Analysis of Stability and Generalization for Modern Meta Learning Algorithms
Authors: Jiechao Guan
Yong Liu
Zhiwu Lu
Venue: NeurIPS 2022 Accept (2022)
Keywords: meta learning
episodic training strategy
algorithmic stability
generalization bounds
support/query set

Abstract: The support/query episodic training strategy has been widely applied in modern meta learning algorithms. Supposing the $n$ training episodes and the test episodes are sampled independently from the same environment, previous work has derived a generalization bound of $O(1/\sqrt{n})$ for smooth non-convex functions via algorithmic stability analysis. In this paper, we provide fine-grained analysis of stability and generalization for modern meta learning algorithms by considering more general situations. Firstly, we develop matching lower and upper stability bounds for meta learning algorithms with two types of loss functions: (1) nonsmooth convex functions with $\alpha$-H{\"o}lder continuous subgradients $(\alpha \in [0,1))$; (2) smooth (including convex and non-convex) functions. Our tight stability bounds show that, in the nonsmooth convex case, meta learning algorithms can be inherently less stable than in the smooth convex case. For the smooth non-convex functions, our stability bound is sharper than the existing one, especially in the setting where the number of iterations is larger than the number $n$ of training episodes. Secondly, we derive improved generalization bounds for meta learning algorithms that hold with high probability. Specifically, we first demonstrate that, under the independent episode environment assumption, the generalization bound of $O(1/\sqrt{n})$ via algorithmic stability analysis is near optimal. To attain faster convergence rate, we show how to yield a deformed generalization bound of $O(\ln{n}/n)$ with the curvature condition of loss functions. Finally, we obtain a generalization bound for meta learning with dependent episodes whose dependency relation is characterized by a graph. Experiments on regression problems are conducted to verify our theoretical results.

Fine-Grained Analysis of Stability and Generalization for Modern Meta Learning Algorithms
Jiechao Guan 1.3
Yong Liu
Zhiwu Lu
School of Information, Renmin University of China, Beijing, China Gaoling School of Artificial Intelligence, Renmin University of China, Beijing, China 3 Beijing Key Laboratory of Big Data Management and Analysis Methods {2014200990, liuyonggsai, luzhiwu)@ruc. edu.cn cn
Abstract
The support/query episodic training strategy has been widely applicd in modern meta learning algorithms. Supposing the n training episodes and the test episodes are sampled independently from the same environment, previous work has derived generalization bound of O(1/vn) for smooth non-convex functions via algorith- mic stability analysis. In this paper, we provide fine-grained analysis of stability and generalization for modern meta learning algorithms by considering more gen- eral situations. Firstly, we develop matching lower and upper stability bounds for meta learning algorithms with two types of loss functions: (I) nonsmooth convex functions with a- o-Höller continuous subgradients (a E [0, 1)): (2) smooth (includ- ing convex and non-convex) functions. Our tight stability bounds show that, in the nonsmooth convex case, meta learning algorithms can be inherently less stable than the smooth convex case. For the smooth non-convex functions, our stability bound is sharper than the existing one, especially in the setting where the number of iterations larger than the number n of training episodes. Secondly, we derive improved generalization bounds for meta learning algorithms that hold with high probability. Specifically, we first demonstrate that, under the independent episode environment assumption, the generalization bound of O(1/vn) via algorithmic stability analysis is near optimal. To attain faster convergence rate, we show how to yield a deformed generalization bound of O(In n/'n) with the curvature condition loss functions. Finally, we obtain a generalization bound for meta learning with dependent episodes whose dependency relation is characterized by graph. Experiments on regression problems are conducted to verify our theoretical results.
Introduction
The last decade has witnessed the success of deep learning techniques in machine learning community 28 25 [T]. However, the need of large amount of annotated data hinders their application in real-life which employs knowledge from past tasks to
scenarios. To alleviate this issue, meta learning facilitate adaptation to the new task, has emerged as promising direction to reduce annotation cost.
Traditional meta learning algorithms directly minimize the empirical error over all samples in the 38 36). To improve the generalization ability meta learning algorithms, recent works propose the support/query (S/Q) episodic training strategy 45 20 41) Specifically, in modern meta learning algorithms, each episode/task is split into two non-overlapped parts: support set and query set. The support is used to learn hypothesis, and the query is used to measure the performance of the learned hypothesis on that episode. Therefore, the S/Q episodic strategy regards
training tasks 3
"Corresponingg Author
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

each task as training instance and updates the meta learning model by implementing episode-level stochastic gradient descent (SGD). Supposing the n training episodes and the test episodes are sampled independently from the same environment, previous work [ has derived high-probability generalization bound of D(1/vn) for modern meta learning. Such bound is obtained via algorithmic stability analysis [6] for smooth non-convex loss functions. However, it is still unknown whether such generalization bound of ( Vn) is optimal, and whether we can obtain sharper bounds for modern meta learning. Further, there is still lack of comprehensive comparisons between the bounds obtained via S/Q episodic training and the bounds obtained via traditional empirical risk minimizing (ERM).
In this work, we will address the above problems via algorithmic stability analysis. Algorithmic stabiliity, roughly speaking, bounds the change in the model output by the algorithm when single data in the dataset is replaced. Our goal is to provide fine- sine-griined analysis of stability and generalization for modern meta learning algorithms by considering more general situations. Firstly, we develop matching lower and upper stability bounds for meta learning algorithms with two types of loss functions: (1) nonsmooth convex functions with a-Hölder continuous subgradients where 0 I a < 1; (2) smooth (including convex and non-convex) functions. Our tight stability bounds demonstrate that, in the nonsmooth convex case, modern meta learning algorithms can be less stable than in the smooth convex case. In particular, the lower stability bound for nonsmooth convex functions is vacuous even if we train modern meta learning algorithms with a relatively small constant step size in SGD, In the smooth non-convex case, our derived bound is sharper than the existing one [8], especially in the setting where the number of SGD iterations is larger than the number n of training episodes. Secondly, we provide -robbbbbaybllityy generalization bounds for modern meta learning algorithms with the aforementioned two types of loss functions. Specifically, we first demonstrate that, under the independent episode environment assumption, the bound of O(1/ /n) is near optimal and is independent of the sample size m per episode. We thus show that, in terms of the sharpness of the generalization bounds, the S/Q episodic training strategy is superior to the traditional ERM strategy for meta learning (see Remark (6) To obtain faster convergence rate, we next show how to yield deformed generalization bound of OIn with additional curvature assumption (i.e.. Polyak- Lojasiewicz condition (46)) of the loss function. Finally, we use the graph approximation technique 47 to obtain bound for meta learning with dependent episodes whose dependency relation can be characterized by graph. To the best of our knowledge, this is the first bound that captures how the dependency between episodes can affect the generalization behavior of meta learning algorithms.
Overall, our contributions are four-fold: (1) We provide matching lower and upper stability bounds for modern meta learning algorithms with general loss functions. The stability bound for nonsmooth convex functions implies that modern meta learning algorithms are not stable enough; and the stability bound in the smooth non-convex case is sharper than the existing one. (2) We develop a near-optimal high-probability bound of 0(1vvl) on the transfer error in meta learning. Such bound is also used to reveal the advantage of the S/Q episodic strategy for meta learning over the traditional ERM strategy. (3) We derive deformed generalization bound of O (Inn//) with additional curvature condition of loss functions. (4) We obtain the first bound for meta learning with dependent episodes. Experiments on regression problems are conducted to validate the convergence of our generalization bounds.
2 Related Work
Algorithmic Stability Theory. Algorithmic stability analysis is an important tool to provide theoretical guarantee for the learnability of machine learning models. [40] has shown that there are non-trivial problems where traditional uniform convergence analysis (i.e., empirical process theory (44) fails to hold, but stability can be identified as the sufficient and necessary condition for learnability. There two main groups in this direction: (1) The first group develop different notations of stability and connect their relation to the generalization of specific algorithms. Among them, uniform stability the most widely used notation and has been utilized to analyze the stability and generalization of regularized ERM algorithms [6]. Hypothesis stability is a weaker notation and has been used to show the stability of k-Nearest Neighbor model [2.. Both of the above algorithmic stability notions have been extended to the randomized setting to demonstrate the stability of Bagging algorithm [5]. In recent years, different notations have been employed to analyze the stability and in-expectation generalization bounds of stochastic gradient descent method, which include
uniform stability (24), on-average stability (29), uniform argument stability [33 2). on-average model stability (31 and locally elastic stability (10). (2) The second group aims to derive tight
probabiiiyy generalization bounds for uniformly stable algorithm in single-task learning. The
first probaiiiyyy bound has been derived by (6), and has been improved in [18. Recently, nearly

---

optimal generalization bounds of O() have been established in [19] [19] where n is the size of training dataset. Further, with additional Bernstein condition, [27 derives a generalization bound of Q(1 (()/ In this work, we aim to provide tight stability bounds and improved iigh-roobbillity generalization bounds for episodic meta learning algorithms. The key step to achieve our goal is to reveal the equívalence of notations between single-task learning and episodic meta learning, hence we can extend the demonstration techniques from 77 27
47 to the episodic meta learning setting.
Generalization Bounds for Meta Learning. Supposing the n training tasks and the novel tasks are sampled independently from the same environment, [ derives the first generalization bound on the transfer error over the novel task for meta learning. Under the independent task environment assumption, we can categorize existing transfer error bounds into three main groups: (1) transfer error bounds of hypothesis space. Such bounds are always achieved via covering number analysis A or VC theory (5). and hence are always dimension-depeedent,, The latest upper bound in this group nm
is of ((1/ Vrm + 1/ 1//m) in (22 Theorem 5], where m is the sample size per task. (2) transfer error bounds of the hyper-distribution
of prior. Such bounds are obtained via PAC-Bayes analysis 38 39 [3]. The tightest bound in this group is of order O(1/Vn + 1/m) in [1 Theorem 3]. (3) transfer error bounds of the algorithm. Such bounds are obtained via algorithmic stability analysis []. The tightest bound in this group is of O(1/ /T) in [ Theorem 4] for episodic meta learning algorithms. Detailed comparisons between different transfer error bounds can be found in Table A.2 of Appendix|A] There also exist other works without the task environment assumption. Instead, they choose to bound the excess risk on the novel task by proposing sask-similrr measurement [14,
or using the total variation distance as the diversity measurement between novel task and training tasks [16]. In this work, we take the task environment assumption and follow the work of [8] Our first improvement is to demonstrate that the bound of O(1/vn) /n) is near optimal. Besides, we show how to obtain a deformed generalization bound of O n//n) with additional curvature assumption of the loss function. Further, we derive a bound with dependent training episodes, revealing how dependency relation between episodes can affect the generalization of meta learning algorithms.
3 Problem Formulation
In supervised learning, a sample space -= X' X'' x/ is product space of an input space X' and an output
space V. H {hme= : w E W) is the hypothesis space where the hypothesis h. E H is parameterized by parameter w in the parameter space W. A measurable function f H x 2 - [0, M] > 0) is defined as a nonnegative and bounded loss function, whose loss of hypothesis h over a sample is denoted by f(h 2) or [w, 2). Let (A) denote the set of probability measures over the set A.
Loss Functions. Throughout we assume that the parameter space W C Rd. Thus, we use unambigu- ously ||- || = |1- the Euclidean norm. Let Projy be the Euclidean projection onto W, which is nonexpansive [|Projy (r)jProjy(())) $ ||l- For any fixed x E Z, a function f(,2); W + R
is convex if for all u, v W. f(u, 2) 2 f(v, (g. v), where g E Ōf(v, z), and (v, denotes the set of subgradients of f(,22) a. Let f(u 2) denote the subgradient with the least norm. If f(, 2) is differentiable, 2) denotes the gradient of [(, )), i.e., 0f(,2)
(V =)). f(e,2), (((,z)))(((() < ailu - oll. For any 2 E Z,
For any = E Z. f(- 2) is o-Lipschitz e. Wf f(, 2) is G-smooth Vu, V E W. (I0f(u, 2) -f(c, 2)ll S Giluu v/]. We also give the definition of function with (a, HHHöle continuous subgradient as follows. We may refer to such functions as (a, G)-Hölr smooth or a- HöHöle smooth function for simplicity when the context is clear.
Definition 1 Let G > 0, a E [0. For any 2 E 2. a function f(,, 2) is called (a, G) -H-Höl smooth if its subgradient is (a, GY-Hölder continuous, i.., (.(,)) satisfies the following conditions:
Yu, U E W,
(l0f(u,))
z)|l <
(I)
If (1) holds with a then f(-,2) is a G-smooth function: if (1 holds with a 0, this implies the subgradient boundedness of 2). The examples of loss functions in machine learning satisfying include the g-norm hinge-loss fww, 2) = mmax(0, 1 1 yw),)))) for classification and the q-th power absolute distance loss f(w,,) z) = ly (w, 2:|1 for regression, whose subgradients are both
{g - Höölder continuous for some > 0 if g E [1,2] (see ()) For (a, -H-Hölder smooth function, define c, = (1 + ffa a E (0, 1]; and co = sup, (l0f z)ll + G, if a = 0.
Single- Task Learning. The training dataset S {2j (Iz, m3) }y)} is given by m independent
draws from unknown distribution D on Z (i.c., D E M2)).. An algorithm A takes S as input
3

---

and outputs a hypothesis A(S) in H. The set of such algorithms depends only on H. and 2 and will be denoted by A(H, 2). In single-task learning. a hypothesis A(S) is always obtained by minimizing the empirical error on S: ((A(S), S) & +n Σ f(A(S), zz)- The performance of the returned hypothesis A(S) is measured by the expected/gennralizatiin distribution D: ((A(S), D) & EE (A(S), 2). The goal of learning theory is thus to give a (lower or upper) bound on the expected error based on the empirical error on the training dataset S.
error with respect to (w.r.t)) the data
Meta Learning. Following existing theoretical works for meta learning 34 38 8 that the distributions {D+ associated with different training tasks drawn from the same task environment т, which is a probability distribution over the set of all data distributions on 2 (i.e., T E (M During the training process, a meta-sample S {S: S." U S/ R=1 is available, where S/r iid. D.K of size K is the training set, and S iid. Dj of size q is the test set of the i-th training task. In this work, we assume that K + -q = m for notation convenience. The training set and the test set are also called support set and query set [8), respectively. Let A(A(H, 2), z be the set of meta learning algorithms. For any A E A(A(H,, 2), 2. it takes the meta- meta-sampll sample input and outputs an algorithm (inner-task algorithm) A(S) -m== 2
we assume
S = {S.) performance of the learned inner-task algorithm is measured by the expectation of the generalization
H. The
error w.r.t. the task environment T, which is defined as the transfer error by [3 8 as follows:
er( (r(A(S)) r) A
(2)
Actually, the environment 7 can define induced distribution D, MMm, by setting DF(P) (F)FF for any measurable set F C Zmm Define the estimator (SA( -
L(A(S)(S")) S**), where S = Str USt S iid. D Then we can rewrite the transfer error as a simple form: er(A(S), r) = ESSD. (S),,, 5). This means that, the training error ((A S) is the unbiased version of the transfer error er T) = the fact that, in single-task learning, the empirical error ff (A(S), 2) is the unbiased version of the generalization error L(A(S), D) D f z). Therefore, transfer error bound is formally equivalent to a single-task generalization error bound under the identifications 2 <> 2nh I <> I, A A. The relation of the notations between single-task learning and meta learning is listed in Table B.1 in Appendix B In practice, it is difficult to minimize er( (S(((S).7) directly as we have no information of the environment distribution Instead, we choose to minimize the following empirical risk based on the S/Q episodic training strategy. The goal of meta learning theory is thus to give bound on the transfer error, based on the empirical multi-task error on the meta-sample S:
This is similar to
1 n TI
n L(A(S)(S))) St+) = n Σ (.).
er (A(())
(3)
Uniform Stability of Meta Learning Algorithms. We say two meta-samples S = [ and S' = (5 are neighboring, denoted by S S,,tt if they only differ on a single entry, i.e., there exists E [m] s.t. Vj # i, S₁ = S and S; * S We also define S = (St,,..,S%,.....5 S..,. } as the neighboring meta sample of S that differs only on the i-th entry. We next define the uniform stability of meta algorithms with episodic training strategy, which is formulated explicitly in [8] Definition 3].
Definition 2 (Uniform stability of modern meta learning algorithms) A meta algorithm A has uniform stability w.n.t the loss function L if the following holds for any meta- veeta-sample S for any i [n], any D ~ T, Str "K ~ DD: (E(A(S)()))))))))) - i(A(S))
St))
Since I(A(S), S) ((A St*), we can also define the uniform stability of A as: VS D., Vi E [n]. (S), - (S") (S),,)) S)I <. Such definition is analogous to the uniform stability of an inner-task algorithm A in single-task learning (see Definition D. Appendix D under the identifications: 1 ++ f. A ++ A, + S. Thus, we can directly apply the existing uniform stability based generalization bound from single-task learning 6 Theorem 12] to obtain the uniform stability based transfer bound for episodic meta learning [8] Theorem 2), without lengthy and somewhat duplicate proof in [ We list such fundamental uniform stability based transfer error bound in I for later comparison. To derive sharper transfer error bounds, our key step is to utilize the equivalent relation between the notations of single-task learning and episodic meta learning, thus extending fast-rate bounds in single-task learning 27 47 to the cpisodic meta learning setting.
Theorem

---

Theorem Suppose the S/Q episodic meta learning algorithm A has uniform stability w.r.t the estimator S) bounded by M. Then, for any task distribution E (M (2)), any 8 E (0, 1), the following inequality holds with probability at least 1 - 5 over the draw of meta sample S:
In (1/6)
cr(A(S), S (r(A(S), + + (2ny + M
2n
4 Uniform Argument Stability Bounds of Meta Learning Algorithms
For modern meta learning algorithm with deep neural networks 20 41,, always employ stochas- tic gradient descent (SGD) method minimize the empirical error 1 learn a good feature embedding. Formally, we define the
t Σx= ((A(S)()))) S to gradient update rule at (t + 1)-th step as: Wt+1 Projw(w, - ne (S,,,, ). where is is indepen- dently and identically drawn (i.i.d.) from the uniform distribution (nif([n]). Therefore, although L(A(S)(S))) s,;) is the loss only calculated over the query samples S it is still related to the support samples Str and the updated parameter W++11 is also related to SY." Therefore, we define an equivalent empirical loss ((()())))) S) - (AA (S*r),
St*) S to indicate that: the empirical loss over the episode S = 5t U is related to the whole episode sample S, and so is the output hypoth- esis A (S). Therefore, for the empirical error 1 Σ i= (S,)) S,), the episode-level SGD update rule is: W2+-1 = Projw [w;-- - Qw. R( [/y St, ). The pseudo code as well as several examples of modern meta learning algorithms can be found in Subsection[4.1 In this section, provide lower and upper stability bounds for meta learning with sampling-we with-replacement SGD method. First, we give the definition of uniform argument stability of episodic meta learning algorithms.
Definition 3
(Uniform argument stability of meta learning algorithms). Given a meta learning algorithm A, any neighboring meta samples S, S' and any training episode S E 2"h we define the uniform argument stability random variable of A d (S,S'; = [[A(S)(S) - ASS))
A is defined as a uniform argument 3-stable meta learning algorithm if for some B > 0, have sups-s', ,s (S S) S 3 or sups=-' ,s AS, S); < B, where EA denote the expectation w.r.t. the internal randomness of A. For meta learning algorithm with SGD method, the internal randomness of A comes from the randomness of sampling each iteration. Note that if R(-, S) is Lipschitz function for any S E z" the uniform argument stability of A implies the uniform stability of A in Definition 2 In this work, we investigate the stability of modern meta learning algorithms with sampling- siiing-wit--repacemmee bounds on EA (S) (SS')(S)) across different settings in Subsections 4.2 4.3
SGD training strategy. Therefore, we will derive lower and upper
4.1 Pseudo Code of Modern Meta Learning Algorithms
Algorithm 1 Support/Query Episodic Training based Meta Learning Algorithm
1: Input: training dataset S = { with S; {8 S/ J. # of iterations T,, learning rates V)
(t E [7]).
2: Initialize: the parameters of deep neural networks w1-
3: for = 1 to T do
4: Uniformly sample one of n training episodes with replacement. Let is be the episode index.
5: Wt+1 = Projw We p, St.))
// episode-level SGD update
6: end for
7: return WT+1
We provide several specific meta learning algorithms to illustrate the calculation of loss R(w;, S..) on the episode S;, at the (-th iteration, where w, is always the parameters of the feature extractor that shared across different episodes. For the metric-learning based algorithms [4] 45 in classification, ho,, is regarded as the feature extractor to output the feature vector Iww, (x) with data x as input. Then
log expl- d(( / (x), cy)
Σ R(w, St)= 9 (2.1))
Eeexpl exp( d(hmg (x),ck)}²
5

---

where C Norm E (t. w= (w) (2) is the prototype (i.e., averaged vector) of the sample features in the support set S with the same class label k; -((.-) is the distance between two feature vectors, e-g. the Fuclidean distance in ProtoNet [4I], and the Cosine distance in MatchingNet [45].
For the classifier-leanning based meta learning algorithm MetaOptNet 30)
[u,, = - Σ log exp(A(hiur (x)) 2
Σn exp(A(hmn (1), ox)}
(2.y)
where {oh ) are the parameters of the classifier returned by supervised learning algorithms (e.g. SVM) on the support set Si, (,) represents the inner product. For the gradient-learning based meta algorithm MAML [20), let ag be the learning rate of the inner-task algorithm at the t-th iteration, then
R(w, S..) = Σ
f(we
Ot Σ
Of(w,,2');
K
ZES
2'EST
4.2 Stability Bounds for Nonsmooth Functions with a-Hölder Continuous Subgradients
In this subsection, we provide lower and upper stability bounds for episodic meta learning algorithm whose loss function is nonsmooth convex and has a-Hölder continuous subgradient with S 1.
Theorem V fixed S zTn let R((,S) be a convex and (a, G)-Hölder smooth function, where [0, 1). Let A be meta learning algorithm with hempling-with--aee replaheepllcemment SGD. Denote by w and w'J the outputs after j(j E (T]) steps of SGD on S and S respectively. Define Rs (w) = R(w, St). Vw W. Then VS t (S,A(S is upper bounded by
V2aa
T
R
20 (w;)
RSi
2a (w))]]
20 n
T
RIia (wg, Si) + RIia (wz, St]
(4)
In addition, if R)(-,S) is bounded by M and the step size nij 1) Vj [T], we can obtain the lower and upper bounds of the uniform argument stability of A: C. 14a (min I ITVT+ W2 sups,s's , (A S'; S 4T (irrmmin ( TTNT ).
Remark Our upper stability bound in Eq. (7) depends on the empirical risk during the optimization process. Formally, Eq. (4) shows that, the stability of modern meta algorithm increases if we find good parameters W/ with small empirical risk (wy) at the j-th optimization step. This illustrates key insight that optimization is beneficial to improve the generalization of algorithms. Besides, our stability upper bound also implies the importance of a good embedding (42) (which may have a good initialization and low empirical risk during the first several optimization steps) to generalization.
We additionally suppose the function to be bounded by M such that the stability bounds can be used to analyze the generalization bounds in the next section where the loss function is always assumed to be bounded. Note that when a = 0, R((-, S) is nonsmooth Ca -Lipschitz convex function, and our lower and upper stability bounds recover the results in [2]. For bounded convex a- o-Hölder smooth functions, the lower stability bound implies that modern meta learning algorithms are not stable enough even if we train them with a relatively small constant step size in each SGD iteration.
Remark 2
Remark 3 The above result shows that, for bounded convex o- c-Hölder smooth funttiinnntioon (a E [0, 1)). the uniform argument stability parameter 3 (ca rio (min 1, T/TT/nn////// //n////////////// + /T) Another work (31] also focuses on convex o-- o--ölder smooth function. funcciiunnttin. Using the technique from (3IV. we obtain the upper stability bounds for bounded convex o-Hölder smooth function under the same conditions: OCcaM ri TT
or 3 S Occ.M T (nI /T + nT/T/))) (see Theorems C. C.2 in Appendix C.2.2p. both of which are larger thun our light stability bound in Theorem 2 Sunder
the setting T n. When T > n, the upper bound 3 < OCc, M 14 (17-a /T + TTTT))) in
Theorem C.2 is slightly sharper than the upper bound O (c,,Mris TM (nVT + nTTnn) m)) in Theorem
4.3
Stability Bounds for Smooth Functions
In this subsection, we provide lower and upper uniform argument stability bounds for modern meta learning algorithms with smooth functions. First, we consider smooth convex functions.

---

Theorem 3 A fixed S E zm, let S) be a G-smooth convex function. Let A be meta learning algorithm with sampling-wite praplling-withhhppeeee replaceeplnemment SGD. Denote by w and w'j the outputs after j(} (T) steps of SGD on neighboring meta samples S and S', respectively. Then VS E zz, ,1 S 2/G.
V2G T 72
BAIIA(S)(S) A(())( S
E.AEAly R(w,, + Rlwy, j=1
In addition, if RR.,S) () is bounded by M, we can obtain the lower and upper bounds of the uniform argument stability of A: n. Eÿ= Mlj S s (ASA(S,S' 2v2MG
Σ}=1 ?3-
If we set all = then for bounded convex functions, the tight stability bound of O 27 under the
smooth case is sharper than the stability bound of (minn1, T. "/vVT++ 7/" in Theorem 2 under the nonsmooth case. This indicates that in the smooth case, meta learning algorithms are more stable than in the nonsmooth case. Finally, we give stability bounds for smooth non-convex functions.
Theorem 4 A fixed S E g let R(., S) be a o-Lipschitz and G-smooth function. Asmooth.function Let A be mela learning algorithm. Denote by wj and w'y the outputs after j(j E [T]) steps of SGD on S and S respectively. Define the learning rate T = 30
a. Vj [T] with a 0. Then VS E zm, the lower and
upper stability bounds of A satisfy: 6n S sups.s' A S); < 11 (n)oT"
T
n++#
Under the same step size setting, existing upper uniform argument stability bound in 8 Theorem3] or in [33] Proposition 4] for non-convex, smooth and Lipschitz function is of O(Tri=/n) Our
bound of order O /n=+a) is improved over the existing bound when T S n. Besides, our stability bound can be non-vacuous for multi-pass SGD setting (i.c., when = kn, ht E N) where the number T of SGD iterations larger than n, as long as k S n//
High Probability Transfer Error Bounds for Meta Learning
In this section, we establish high probability bounds for transfer error er (AAAA)(( r). Specifically, still consider two kinds of loss function: (1) convex and (a, Gr-Hölder smooth function (a E [0, 1)); (2) non-convex, o-Lipschitz and G-smooth function. We always assume that the loss function I((-,-) is bounded by M. Define a, = M पंं if R(w S) is convex and (a,, G')-Hllde smooth function; o. if R(, is o-Lipschitz and G-smooth function. We just exhibit the generalization bounds of randomized algorithm A by supposing PA example illustrate how to calculate do in Example D.] in Appendix D The generalization bound
S) > 3) S ōy- We provide an
for deterministic meta algorithm (e.g. with gradient descent) can be stated by setting ón = O.
5.1 Near Optimal Transfer Error Bound for Meta Learning with Independent Episodes
We denote by a S b the existence of some universal constant c >> such that a S cb. Then we obtain the following near optimal bound of O11/v// under the independent task environment assumption.
Theorem Let A E A(A(H, 2), zm) a uniform argument 3-stable meta algorithm, i.e., supses ,s EA (())))))(S)) - (SS S B. For any S E 2 let R(:,5) be [0, -valued, and satisfy one of the two following conditions: (I) R((,S) is convex and (ax, G--Hölderr smooth
(a [0, 1): (2) R(-,S) S) is a-Lipschitz and G-smooth. Suppose PA (S, S': S) > B < 8y. Then for any independent task environment T E (M(M,(()) any 8 E (0, 1), the following holds with probability least 8 Sn over the draw of S and the internal randomness of A:
1 M
Th M
Fa. In
Vn V (1/0) - S 0.
Vn VFVVE In (1/8).
Remark 4 Our transfer error bound in Theorem 5 has three udvantages over the bound in Theorem 7 from [] (1) Theorem giies a biobbbbbobbilityy upper bound of O ((vTV) M\ VT) ) for transfer error, where is the uniform stability parameter and always scales as ((1/n); in contrast, our upper bound of O
(31l In n. + Vn) improved by replacing the v factor before the stability parameter with In n. (2) [8], the uniform stability 7 = Of /n), whereas our uniform argument stability = O /n +a) is tighter when T S n, ie., when the uniform stabiliy bound 7 = O(T=# /n) is non-vacuous. (3) Our high probabbiyyy transfer error bound of order O(1/ is near optimal.
7

---

We uncover two limitations of stability-based meta learning theory: (1) Recall the lower stability bound for meta learning algorithms with convex a-Hölder smooth function (a E [0. 1)) in
Remark 5
R (NVTT + =[Il /n) when T 2 This indicates that the lower transfer error bound is greater than a constant and will not converge to zero with the increase of n. Thus, the stability- transfer error bound is vacuous and cannot provide asymptotic guarantees for convex Hölder smooth functions. (2) The Sabilittybased transfer error bound of O(1/ (T) in Theorem 5 is near optimal. Such result is consistent with the observation in (36] Section 2| that under the (f.i.d) task environment assumption, the term 0 Vn) in the generalization bound is unavoidable. Thus, to obtain sharper generalization bounds for meta learning (e.g. the bound of O(1/ ///////m) or even O(1 /mn)), we need to consider other stability notions (e.g. ((6)), or suppose stronger task relatedness in the environment (e.g. 15 (22)), or even drop the task environment assumption (e.g. [1 431)
Theorem 2 we find that the lower transfer error bound in Theorem er ()((A())))
Ta In (1/ M 14=
Remark 6 Under the independent task environment assumption, we compare our bound of O(1 Vn)
via S/Q episodic training strategy with other transfer error bounds that are obtained via traditional
ERM strategy over all samples in training tasks. In detail, the bound from [34 Theorems 2 and 6]
via algorithmic stability analysis is of O(1/m + 1/)V);; the bounds from 138 Theorem 1] and (39
Theorem 2] via PAC-Bayes analysis are of O(1
(11/// nn + 1/ /m); the bound from (22) Theorem 5] via
covering number analysis is of (1/ [nmmmmm++ + 1/ +1/
1//m). m). All of these bounds via ERM strategy involve a
term ((1 /m). and such term can be large when m is relatively small (e.g. m = or m = 10 in the few-shot learning setting). Thus, in terms of the tighmess of transfer error bounds, the S/Q episodic training strategy is superior to the ERM strategy for meta learning, when << n. Such result was also pointed out by (8) and is more rigorously demonstrated in this work Detailed comparisons between different transfer error bounds for meta learning are shown in Table A.2 in Appendix A
5.2 Fast Transfer Error Bound of O(n O(nn/n) for Meta Learning with Independent Episodes
To obtain faster convergence rate, we need to take additional assumption. The generalized Bernstein condition is one of the most widely used condition to attain fast convergence rate of generalization bound in single-task learning 133 27]. Next, we extend the generalized Bernstein condition to the meta learning setting, where we study the optimal algorithm A' instead of the optimal hypothesis.
Definition& 4 (Generalized Bernstein Condition for Meta Learning) Assume that A'H, 2) = Argmin A(H, A(H.2)er (z,er(A,r)) T) is a set of risk minimizers in a closed set. We say that an algorithm A together with the environment I and the empirical estimator I satisfies the generalized Bernstein condition for some > 0, AA E A(H, 2), there is a A E A (H,, 2), such that
ES-D. (1(A. - 1(A" S))
S))² 2 S <B(er(A,T)) - (aredtt)--rAA,A,,. ,r)""))))
(5)
27 has shown that in single-task learning, a strongly-convex and Lipschitz function satisfies the generalized Bernstein condition. In this work, we relax the grrong-convexity condition by considering the following Polyak-Lojasieva condition, one of the weakest curvature conditions of functions.
Definition 5 PPolyak-Lojasivvir (461) Any function f W + IR satisfies the Lojjsiwwijis (PL) condition on W with parameter μ > if for all w E W, f(w) - f(w*) I 1 [|2" f(w)
2u where w" denotes the Euclidean projection of w onto the set of global minimizer of f in W.
A key insight into the PL condition is that it is the sufficient and necessary condition to guarantee the linear convergence of gradient descent methods for smooth convex optimization problem [37]. Such PL condition can also be satisfied by many non-convex neural network models, such as the two-layer neural networks with ReLU activation functions (32] and the deep linear residual networks 23 We will show that if the functions in Theorem 5 additionally satisfy the PL. condition, then the loss functions in meta learning also satisfy the generalized Bernstein condition Definition 4 Thus, we can derive "deformed" transfer error bound of (lnn/n) for modern meta learning algorithms.
Theorem 6 Under the same conditions of Theorem for any fixed S E 2mh let R((,S) S) additionally satisfy there exist e > 0, such that for any environment 7 E Mi holds with probability at least - å - ón over the draw of S and the internal randomness of A:
condition in Definition
Suppose P A S': S) > 38] S 5g. Then, and any d E (0, 1). the following
c(1 + +1/n) (n (o.3lnn
M In 5
er er(A(S), S (1 + ())rr
n
8

---

Recall in Section 4 our stability parameter is always 3 = (11/n). Hence, when the empirical error in the RHS of the above bound is close zero, the transfer error bound always scales as OIn n/nn).
5.3 Transfer Error Bound for Meta Learning with Dependent Episodes
In this subsection, we investigate the generalization bound for meta learning algorithms with depen- dent episodes whose dependency relation can be characterized by graph. The approach undertaken to establish our results is based on the forest approximation of the dependency graph [26] Formally, a dependency graph is an undirected graph I = (V. of a random vector $ = (S ...,. S,,) if the satisfied: (1) V(T) [m]: (2) if I, J C. [n] are non-adjacent in I, then {Sthez and {S, hey are independent. We next give the concept of forest approximation.
following two conditions
Definition 6 (Forest Approximation (47]) Given a graph I, a forest F, and a mapping é V(T) - V(F), if éu δ(v) or (ō(u), o(v)) (FF) for any (u, E(T), we say that (④, F) is forest approximation I. Ler (T) denote the set forest approximations of
Intuitively, a forest approximation transform a graph into a forest by merging vertices and removing self-loops. We then give the definition of forest complexity, which measures how a dependency graph looks like a forest, and hence measures the strength of dependency among random variables in S.
Definition 7 (Forest Complexity (47)) Given a graph I' and any forest approximation (d. (G)
with F consisting of trees (Tibee(a) Define X(o.F) = E(a,)EE(F)) (lp-1(w) +
(w)))
E min 10 (x))2 We call A(T) FF) A( the forest complexity of the graph r = (V, F)) Here, (1) is the set of pre-images of the element
For sample S whose components are independent, we choose the identity map and its dependency graph as the forest approximation. Hence A(T) = > 1
n. For sample S whose dependency graph r is a tree, the identity map between P and itself is a forest approximation of Т. Then A(T) < [1 +)
+1 = 4n --3 (n). More examples of forest approximation can be found
in 47 Section 3.3]. We next give a forest- cress-ccomplxxtty based transfer error bound for meta learning.
Theorem Under the same conditions of Theorem except that S is meta sample of size n with dependency graph P. Let the maximum degree of the graph I is A. Suppose PA (S. 3) S 5y. Then, for any environment T E M1(M] (2)). any 8 E (0, the following holds with probubility at least - 8 -- do over the draw of S and the internal randomness of A:
M
A(T) In 1/8
er cr(A(S), (A)
+ (20 B+
2
When S is independent sample, the forest complexity A(T) n, the maximum degree A 0, and the above forest-complexity based generalization bound degenerates to the bound in Theorem [ for meta learning with independent episodes. When S is a dependent sample, A(T) will be greater than Both the complexity A(T) and the maximum degree A will increase with more dependency relation between samples in S (i.e., with more adjacent edges in its dependency graph section, we conduct experiments on regression problems to show the convergence performance of the generalization bound for meta learning with dependent episodes. The corresponding forest-complexity based generalization bound for such problem is provided in Example D.2 in Appendix D.3
E)). In the next
Experiments
To verify our theoretical analysis, we conduct experiments few-shot regression problems to show the convergence performance of our generalization bounds with independent and dependent episodes.
Experimental Settings. We follow the experimental setting in 20 g The problem aims to approximate the distribution of parameters of function f(x) the joint distribution p(a, 33 of the parameters a and B. We set p(a) = -l-
(3r). The task environment is
5. 5], p( = U x]. For independent setting, we construct training episodes by sampling pairs (a, B) from the task distribution = p(a,,3) ;3); for dependent setting, we construct the first half training episodes by sampling pairs (a, from T = p(a, .3) independently, and construct the rest half training episodes by setting (-a, 3) with (a, 3) from the first half training episodes. Each training episode contains

---

HAMA
MARK-
MAX0
MAX
Sect tank
Hill of Cooks
Juc tadk
kiph of
(a) Bilevel, la loss
(b) Bilevel, l loss
(c) MAML, loss
(d) MAML. 4 loss
Figure 1: Convergence analysis of generalization gaps for independent tasks.
Supp of
(a) Bilevel, 12 loss
(b) Bilevel, l loss
(c) MAML, 1n loss
(d) MAML, 4 loss
Figure 2: Convergence analysis of generalization gaps for dependent tasks.
5 support samples and query samples. In both settings, the 600 test episodes constructed by sampling (a, () from J independently, each containing 5 support samples and 15 query samples. We implement meta learning algorithms MAML [20] and Bilevel Programming [21] with square loss (12) and absolute loss (42). The neural network has two hidden layers of size 40 with ReLU activation functions. The generalization gap is the absolute distance between the training error and test error.
Experimental Results. From Figures we can observe that: (1) The generalization gap both independent and weakly dependent episode settings can converge to O with the increase of the training episodes, demonstrating the asymptotic behaviour of our transfer error bounds in Theorems 5 and 7 (2) The generalization gap with independent episodes can converge to zero more quickly than the gap with dependent episodes. The test error with independent episodes also always converge to the lower level than the one with dependent episodes. The better convergence performance with independent episodes truly demonstrate how the dependency between episodes can affect the generalization of meta learning algorithms. (3) With non-convex neural network models, both square loss and nonsmooth absolute loss can lead to similar convergence performance of generalization bounds.
7 Conclusion and Future Work
In this work, we provide fine-grad fine-grained analysis of stability and generalization for modern meta learning algorithms. From the perspective of stability, our tight stability bounds implies that in the nonsmooth convex case the meta learning algorithm is less stable than in the smooth convex case. The stability bounds in the smooth non-convex case enjoys an order of (11/n) even for the multi-pass SGD setting. From the perspective of generalization, we demonstrate that the nigh-probabiling transfer error bound of ((1/vn) optimal. Based on this bound, we uncover the limitations of algorithmic stability analysis for meta learning, and reveal the advantage of episodic training strategy for meta learning over tradition ERM training strategy. Further, by extending the generalized Berstein condition to the meta learning setting, we obtain a deformed generalization bound of O rt/n) with additional
condition. Finally, we derive generalization bound for meta learning with dependent episodes. Experiments are also provided show the convergence performance of generalization error with independent and dependent episodes. In the future, we will explore new stability notions to see whether we can develop sharper generalization bounds for meta learning.
Acknowledgments and Disclosure of Funding
Jiechao would like to thank Dr. Mingxue Quan from School of Mathematics in Renmin University of China for helpful discussions. We thank all reviewers for their constructive suggestions to improve the quality of this paper. This work was supported in part by National Natural Science Foundation of China (61976220 and 61832017). Beijing Outstanding Young Scientist Program and Large-Scale Pre- Pre-Training Program 468 of Beijing Academy of Artificial Intelligence (BAAI). Prof. Zhiwu Lu is the corresponding author of this paper.
10

---

References
[1] M. Al-Shedivat, L. Li, E. Xing, and A. Talwalkar. On data efficiency of meta-learning. In International Conference Artificial Intelligence and Statistics (AISTAT), pages 1369-1377, 2021.
[2] R. Bassily, V. Feldman, C. Guzmán, and K. Talwar. Stability of stochastic gradient descent nonsmooth convex losses. In Conference on Neural Information Processing Systems (NewrIPS), 2020.
[3] J. Baxter. Learning internal representations. In Conference on Learning Theory (COLT), pages 311-320, 1995.
[4] Baxter. A model of inductive bias learning. Journal of Artificial Intelligence Research, 12:149-198, 2000.
[5] S. Ben-David and R. Schuller. Exploiting task relatedness for mulitple task learning. In Conference on Learning Theory (COLT), pages 567-580, 2003.
[6] O. Bousquet and A. Elisseeff. Stability and generalization. Journal of Machine Learning Research (JMLR), 2:499-526, 2002.
[7] O. Bousquet, Y. Klochkov, and N. Zhivotovskiy. Sharper bounds for uniformly stable algorithms. In Conference on Learning Theory (COLT), pages 610-626, 2020.
[8] Chen, X. Wu, Y. Li, Q. LI, Zhan, and F. Chung. A closer look at the training strategy for modern meta-learning. In Conference on Neural Information Processing Systems (NewrIPS), pages 396-406, 2020.
[9] A. Christmann and Steinwart. Support Vector Machines. Springer, 2008
[10] Z. Deng, H. He, and W. J. Su. Toward better generalization bounds with locally elastic stability. International Conference on Machine Learning (ICML), pages 2590-2600, 2021.
[11] J. Devlin, M. Chang, K. Lee, and K. Toutanova. BERT: pre- pre-training of deep bidirectional transformers for language understanding. In Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies (NAACI-HLTT), pages 4171-4186, 2019.
[12] L. Devroye and T. J. Wagner. Distribution free inequalities for the deleted and holdout error estimates. IEFE Transactions on Information Theory, 25(2):202-25 1979.
[13] N. Ding, X. Chen, T. Levinboim, S. Goodman, and R. Soricut. Bridging the gap between practice and PAC-Bayes theory few-shot meta- hetannea..,ng. In Conference Neural Information Processing Systems (NeurIPS), pages 29506-299 12106629516,,. 2021.
[14] S. S. Du, W. Hu, S. M. Kakade, D. Lee, and Q. Lei. Few-shot learning via learning the representation, provably. In International Conference on Learning Representatinss (ICIR), 2021.
[15] A. Flisseeff, T. Evgeniou, and M. Pontil, Stability of randomized learning algorithms. Journal of Machine Learning Research (JMLR), 6:55-79, 2005.
[16] A. Fallah, A. Mokhtari, and A. E. Ozdaglar. Generalization of model-agnostic meta-learning algorithms: Recurring and unseen tasks. In Conference Neural Information Processing Systems (NeurIPS), 2021.
[17] A. Farid and A. Majumdar. Generalization bounds for meta-learnin via PAC-Bayes and uniform stability. In Conference on Neural Information Processing Systems (NeurIPS), pages 2173-2186, 2021.
[18) V. Feldman and J. Vondrák. Generalization bounds for uniformly stable algorithms. In Conference Neural Information Processing Systems (NeurIPS), pages 9770-9780, 2018.

---

[19] V. Feldman and J. Vondrák. High probability generalization bounds for uniformly stable algorithms with nearly optimal rate. In Conference on Learning Theory (COLT), pages 1270- 1279, 2019.
[20] C. Finn, P. Abbeel, and S. Levine. Model-agnostic meta-learing for fast adaptation of deep networks. In International Conference on Machine Learning (ICML), pages 1126-1135, 2017.
[21] L. Franceschi, P. Frasconi, S. Salzo, R. Grazzi, and M. Pontil. Bilevel programming for hyperparameter optimization and meta-learning. In International Conference on Machine Learning (ICML), pages 1563-1572. 2018.
[22] J. Guan and Z. Lu. Task relatedness- based generalization bounds for meta learning. In International Conference Learning Representations (ICL.), 2022.
[23] M. Hardt and T. Ma. Identity matters in deep learning. In International Conference on Learning Representations (ICLR), 2017.
[24] M. Hardt, B. Recht, and Y. Singer. Train faster, generalize better: Stability of stochastic gradient descent. In International Conference Machine Learning (ICML), pages 1225-1234, 2016.
[25] K. He, X. Zhang, S. Ren, and Sun. Deep residual learning for image recognition. In IEEE Conference Computer Vision and Pattern Recognition (CVPR), pages 770-778, 2016.
[26] Janson. Large deviations for sums of partly dependent random variables. Random Structures & Algorithms, 24(3):234-2455 2004.
[27] Y. Klochkov and N. Zhivotovskiy. Stability and deviation optimal risk bounds with convergence rate o(1/n). In Conference on Neural Information Processing Systems (NeurIPS), 2021.
[28] A. Krizhevsky, I. Sutskever, and G. Hinton. Imagenet classification with deep convolutional neural networks. In Conference on Neural Information Processing Systems (NeurIPS), pages 1106-1114, 2012.
[29] I. Kuzborskij and C. H. Lampert. Data-dependent stability of stochastic gradient descent. In International Conference Machine Learning (ICML), pages 2820-2822 2018.
[30] K. Lee, Maji, A. Ravichandran, and S. Soatto. Meta-learning with differentiable convex optimization. In JEEE Conference Computer Vision and Pattern Recognition (CVPR), pages 10657-10665, 2019.
[31] Y. Lei and Y. Ying. Fine-grained analysis of stability and generalization for stochastic gradient descent. In International Conference on Machine Learning (ICML), pages 5809-5819, 2020.
[32] Y. Li and Y. Yuan. Convergence analysis of two-layer neural networks with relu activation. In Conference on Neural Information Processing Systems (NeurIPS), pages 597-607, 2017.
[33] T. Liu, G. Lugosi, G. Neu, and D. Tao. Algorithmic stability and hypothesis complexity. In International Conference on Machine Learning (ICML), pages 2159 2269,2117,,11 2017.
[34] A. Maurer. Algorithmic stability and meta-learning. Journal of Machine Learning Research (JMLR), 6:967-994, 2005.
[35] A. Maurer. Transfer bounds for linear feature learning. Machine Learning, 75(3):327-350,
2009.
[36] A. Maurer, M. Pontil, and B. Romera-Paredess. The henefit of multitask representation learning. Journal of Machine Learning Research (JMLR), 17:81:1-81:32 2016.
[37] I. Necoara, Y. E. Nesterov, and F. Glineur. Linear convergence of first order methods for non-strongly convex optimization. Mathematical P Programming, 175(1-2):69-107, 2019.
[38] A. Pentina and C. Lampert. A PAC-Bayesian bound for lifelong learning. In International Conference of Machine Learning (ICML), pages 991-999, 2014.
12

---

[39] J. Rothfuss, V. Fortuin, M. Josifoski. and A. Krause. PACOH: Bayes-optimal meta-learning with PAC- GuCaaaaansess. International Conference on Machine Learning (ICML), pages 9116 9116-9126, 2021.
[40] S. Shalev-Shwartz, O. Shamir, N. Srebro, and K. Sridharan, Learnability, stability and uniform convergence. Journal of Machine Learning Research (JMLR), 11:2635-2670, 2010.
[41] Snell, K. Swersky, and R. Zemel. Prototypical networks for few-shot learning. In Conference on Neural Information Processing Systems (NeurIPS), pages 4077-4087, 2017.
[42] Y. Tian, Y. Wang, D. Krishnan, J. B. Tenenbaum, and P. Isola. Rethinking few-shot image classification: A good embedding is all you need? In European Conference on Computer Vision (ECCV), pages 266-282, 2020.
[43] N. Tripuraneni, M. I. Jordan, and C. Jin. On the theory of transfer learning: The importance of task diversity. In Conference on Neural Information Processing Systems (NeurIPS), pages 7852-7862, 2020.
[44] A. W. van der Vaart and Wellner. Weak Convergence and Empirical Processes: With Applications Statistics. Berlin: Springer, 1996.
[45] O. Vinyals, C. Blundell, T. Lillicrap, K. Kavukcuoglu, and D. Wierstra. Matching networks for one shot learning. In Conference on Neural Information Processing Systems (NeurIPS), pages 3630-3638, 2016.
[46] H. Zhang. New analysis of linear convergence of gradient-type methods via unifying error bound conditions. Mathematical Programming, 180(1):371-416, 2020.
[47] R. R. Zhang, X. Liu, Y. Wang. and L.. Wang. Mcdiarmid-type inequalities for graph-dependent variables and stability bounds. In Conference on Neural Information Processing Systems (NeurIPS), pages 00889-1089,,000
Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's
contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes] See Remark 5
(c) Did you discuss any potential negative societal impacts of your work? [N/A]
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Ye]] See Sections
(b) Did you include complete proofs of all theoretical results? [Yes] See Appendix.
3. If you ran experiments..
(a) Did you include the code, data, and instructions needed reproduce the main exper- imental results (either in the supplemental material or as a URLY? [Yes] See Supple- mentary Material.
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [Yes] See Section 6
(c) Did you report error bars (e.g., with respect the random seed after running experi-
ments multiple times)? [Yes] See Figures]
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, or cloud provider)? [Yes] See Supplementary Material.
4. If you using existing assets (e.g., code, data, models) or curating/releasing
assets...
(a) If your work uses existing assets, did you cite the creators? [Yes] See Section 6
13

---

(b) Did you mention the license of the assets? [N/A]
(c) Did you include any assets either in the supplemental material URL? [No]
(d) Did you discuss whether and how consent obtained from people whose data you're using/curating? [N/A]
(e) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [N/A]
5. If you used crowdsoureing conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, if applicable? [N/A]
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, if applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent participant compensation? [N/A]
14


Reviews:
[{"review_id": "goohdZaO6J", "reviewer": "Reviewer_rSh4", "summary": "This paper studies the generalization of meta-learning algorithms. In particular, this paper has three contributions:\n1- Extending the stability analysis for convex smooth functions to convex Holder-smooth functions (similar to [30] for single task)\n2- Improving the stability analysis of nonconvex functions\n3- High probability generalization bounds\n\nIn particular, the authors show that the meta learning algorithms are less stable in the nonsmooth convex case, compared to smooth convex case. ", "questions": "I would appreciate it if the authors discuss how they could potentially study the effect of $m$ in generalization of meta-learning  algorithms for smooth and nonsmooth functions.", "limitations": "Yes.", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Overall, I find the paper and its results interesting to the community. My main concern is that the algorithmic stability is defined in a way that the whole dataset corresponding to a task changes. This makes the analysis simpler (as it would be closer to the single task case), but the results will not be tight with respect to the number of samples per task (m), as the authors point out in Remark 5.   \n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "fnGyC1A2e3P", "reviewer": "Reviewer_DKCG", "summary": "\nThis paper studies stability and generalization in meta-learning. Specifically, it develops matching upper and lower bounds for non-smooth convex loss function with Holder continuous subgradients, as well as smooth convex and smooth nonconvex functions.\n\nThe paper also provides generalization bounds for both independent and dependent episode environments. It shows that in the independent episode environment, the generalization bound of $O(1/\\sqrt{n})$ is nearly optimal. And it can achieve $O(1/n)$ with an additional curvature (Polyak-Lojasiewicz) condition of the loss function.\n", "questions": "**Major comments**\n\n1. Questions regarding Table A.2\n\n* Why in Table A.2, there is no comparison with [8,16], which is the most relevant paper that also provides stability-based generalization bounds for meta learning?\n\n* In Table A.2, what is the difference between \\gamma_n and \\beta_n should be stated more clearly. For example, the uniform stability definitions in those papers are the same or not? If they are the same, why don’t you use the same notation?\n\n* In Table A.2, the last column should be generalization gap bounds instead of transferring error bounds as it does not explicitly include the dependence of the training error \\hat{er}(\\cdot).\n\n\n2. Questions regarding the new uniform stability notion\n\n* Definition 2 is a stronger notion of uniform stability compared to single level problems and the definition in [8,16] for meta learning, since it requires changing both K points in the training set and q points in the test set. Why is it necessary to define the uniform stability of meta learning in this way instead of just changing one point in the training or test set?\n\n* Though the new transfer error bound is sharper, it requires the stronger uniform stability definition in Definition 2. Therefore it is not a very fair comparison with existing works such as [8].\n\n3. Questions regarding the notation A(S)(S)\n\n* The notation A(S)(S) is a bit confusing to me, what is the output of hypothesis A(S)(S) should be stated clearly. Is it the per-task (e.g. for the i-th task) hypothesis or the meta model hypothesis (w)? \n\n* Does this S belong to S or it can be any set S? Since I see A(S)(S), A(S)(S^{tr}), and A(S)(S^{tr}_i).\n\n4. Questions regarding remark 1\n\n* In Remark 1, line 236-237, how does Theorem 2 show the importance of good embedding to generalization? To show this, I would expect a term in Eq. (4) that is directly related to the representation or embedding error. I think the authors need to elaborate more on this point.\n\n\n**Minor comments**\n\n1. Should line 130: $|\\partial f(u,z) - \\partial f(v,z)| be \\|\\partial f(u,z) - \\partial f(v,z)\\|$ instead?\n\n2. What is S^{tr} in Eq. (2) and line 163, is it $S^{tr} = \\{ S^{tr}_i\\}_{i=1}^n$ or is it just a general notation of S^{tr}_i?\n\n3. In line 163-164, why is S ~ D^m and S ~ D_{\\tau} at the same time?\n\n4. In this paper, if I understand correctly, the number of episodes is equal to the number of tasks in meta training. This should be stated more clearly at the beginning of the paper, for example, move Algorithm 1 to the main text as it is important to understand the settings of the analysis.\n\n5. Should line 161-162: $\\mathbf{D}_{\\tau}$ be  $\\mathbf{D}_{\\tau}^m$?\n\n6. It would be more interesting to add additional experiments on real-world data such as for few-shot image classification tasks.\n\n7. It would be better if the authors could add a theoretical curve of the generalization gap v.s. the number of tasks in Figure 1 and Figure 2.\n\n8. In Remark 1, line 232-234, it is stated that [29, 30] have stability bounds that depend on the empirical risk, which I do not agree since they obtain dependence on either the population risk or the expected empirical risk, which is not directly the empirical risk minimized during optimization without expectation over the data sample and algorithm. Therefore, their theoretical results do not imply small training error leads to a small generalization error.\n\n9. Grammar\n\n* Line 160: as follow -> as follows \n\n* Line 423: stability notations -> stability notions\n \n", "limitations": "n/a", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "**Strengths**\n\n1. This is the first work that captures the effect of dependent episodes in generalization ability, which explains the empirical discovery that meta learning trained with independent episodes generalizes better than with dependent episodes.\n\n2. The consideration of the weakest curvature condition, Polyak-Lojasiewicz condition, instead of the strong-convexity condition for O(1/n) rate of generalization is interesting.\n\n3. This work develops stability of meta learning for both smooth and non-smooth loss functions. And conduct experiments with examples in both conditions to verify their theorems.\n\n4. The paper provides matching upper and lower bounds for stability to show the upper bound is tight. \n\n**Weaknesses**\n\n1. The comparison to [8,16] is not clear, which is the most relevant papers that also provide stability-based generalization bounds for meta learning.\n\n2. The techniques to obtain stability in non-smooth convex loss are not new as it is already established in single-level problems [30]. And the technique for lower bound is also not new. The paper directly assumes continuity or smoothness or convex assumptions for the outer level function w.r.t. the meta parameter w, therefore, the analysis of single-level ERM can be directly applied without many challenges that are uniquely caused by the bi-level (compositional) structure of the problem.\n\n\n3. The authors sometimes exchange the notions of “transfer error” and “generalization gap” in the paper. For example, in lines 302, 322, and 344, Table A.2, should the “transfer error” be the “generalization gap”?\n\n4. The stability bound in Theorem 4 requires step sizes $\\eta_j = O(\\frac{1}{j})$, while the convergence of a smooth nonconvex loss function for compositional or bilevel problems requires outer level step size is at least $\\eta_j = O(\\frac{1}{\\sqrt{j}})$ (see e.g. [1,2,3]). What is the step size used for the experiments presented in Section 6, where both the training error and generalization gap converge? This phenomenon should receive more explicit discussions.\n\n\n5. Since the experiment settings belong to a non-convex non-smooth loss function, it is not covered by the theoretical results that include smooth convex, smooth non-convex, and non-smooth convex functions. It would be better to conduct some simulations with the loss functions under the Assumptions used in the theoretical results to verify the theoretical rates more explicitly. Therefore, the experiments in Section 6 do not serve the purpose of verifying the theoretical claims. The observation that a non-smooth non-convex loss function has similar convergence rates in the generalization gap as the smooth non-convex loss function suggests further study and should be pointed out clearly in the paper.\n\n6. Some discussions are not clear to me, as detailed in “Questions”. \n\n[1] Closing the gap: tighter analysis of alternating stochastic gradient methods for bilevel problems\n\n[2] On the Convergence Theory of Gradient-Based Model-Agnostic Meta-Learning Algorithms\n\n[3] Theoretical Convergence of Multi-Step Model-Agnostic Meta-Learning\n\n\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "OTyjbmapI9C", "reviewer": "Reviewer_Skjh", "summary": "This manuscript provide fine-grained analysis of stability and generalization for modern meta learning algorithms by considering more general situations including -Holder continue convex, smooth convex and smooth non-convex functions. First, the authors give the lower and upper bounds of the uniform argument stability for -Holder continue convex functions and smooth convex functions respectively to show that meta learning algorithms in the smooth convex case is more stable than that in the non-smooth convex case. Second, a tighter stability bound of  than the existing bound  is proved. Then, to show the advantage of S/Q episodic strategy for meta learning over traditional ERM strategy, the authors develop a near-optimal high-probability generalization bound , and further improve the bound to  by considering Polyak-Łojasiewicz condition. Finally, a generalization bound for meta learning with dependent episodes is given.", "questions": "1. For the upper bound of the uniform argument stability in Theorem 3 in line 259 of the manuscript, there is not the prove of it in Appendix. Similarly, the upper bound in line 267 of the manuscript is also not proved.\n2. In line 293 of the manuscript, the authors show the result of Theorem 1 in reference [8] is  and , that is, the bound is , which is the same as the bound of Theorem 5 in this manuscript. Why does the authors think the result of this manuscript is better that that in reference [8]?\n", "limitations": "It seems no potential negative societal impact, sine this paper just considers theoretical properties of meta learning. ", "rating": 7, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Pros\n1.The symbol description of the manuscript is relatively detailed.\n2.The manuscript comprehensively considers various function settings, and gives relatively tight results.\n3.The results of this manuscript are compared with the results of many previous works, and the authors show the situations where these results are better in detail.\n\nCons\n1.The coefficient of Theorem 1 cited in this manuscript is slightly different from that in the reference [6].\n2.In Appendix D1.1, Lemma D.1 does not mention the precondition of  which is written in the subtitle. So what is this precondition for?\n3.At the beginning of the proof of Theorem 2 (line 71 in Appendix) and Theorem 3 (line 223 in Appendix) in this manuscript, the nonexpansiveness of projection operator is used. Whether the nonexpansiveness needs to be proved?\n\nIn summary, I believe this paper is interest. It provides some tighter stability bounds and generalization bounds for meta learning. ", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "3pPcuy1_i6Z", "reviewer": "Reviewer_E4JU", "summary": "This work provides a comprehensive stability analysis of gradient-based modern meta-learning algorithms, i.e. that use Support/Query (S/Q) splits of the task dataset for meta-training. In particular, the authors provide matching upper and lower stability bounds for  convex loss functions with $(\\alpha, G)$-Holder subgradients and for smooth functions. The bounds show that in the non-smooth convex case, meta-learning algorithms are inherently less stable than in the smooth convex case. In particular, the lower bound in the non-smooth case is vacuous. In the smooth case, the bounds are sharper than previous analysis. Furthermore, they also develop a near-optimal generalization upper bound in high probability, which shows the advantage of S/Q training compared to  empirical risk minimization (ERM). With the additional PL curvature condition, the authors derive a faster generalization bound. Finally, they derive  bounds for the case where the  episodes have a dependency relation encoded in a graph. Experiments on a synthetic regression problem with L1 and L2 loss validate the theoretical findings.", "questions": "Major question and comments.\n1. Theorem 6 does not contain a valid bound since in the RHS it has $(1+ \\eta) er$ instead of just $er$. From the analysis we can see that this result follows from [12, Theorem 1.2], which specifies that it is useful only when the empirical error is small, which might happen when dealing with overparameterized neural networks. The correct fast bound is [12, Theorem 1.1] which bounds the excess risk instead of the generalization error. I think this should be clarified and claims should be modified accordingly.\n2. The advantage of S/Q meta-learning over ERM has already been shown by [8]. I think readers might mistakenly think that this is a new result of the paper. I suggest removing this fact from the claims in the introduction and possibly cite [8] in Remark 6.\n3. Proof of Theorem 5 uses Lemma E.1 in the appendix, which should be equivalent to [5, Corollary 8]. However, such corollary is only an upper bound, the lower bound is derived in the subsequent section of [5]. I think this should be clarified and the proof should be expanded.\n4. I suggest the authors either include log terms inside $O()$ or use $\\tilde{O}(\\cdot)$.\n\n\nMinor questions and typos:\n1. Looking at [6, Theorem 12], I think you should replace $\\gamma$ with $2\\gamma$ in the bound of Theorem 1.\n2. Addiction -> addition.\n3. Theorem 1 corresponds to [8, Theorem 2], not [8, Theorem 1] \n4. In Remark 6 “m=1 in few-shot learning”. If m=1 is impossible to split the dataset in support and query. At least should be m=2 but in practice is larger than that.\n\nReferences:\n\n[5]  O. Bousquet, Y. Klochkov, and N. Zhivotovskiy. Sharper bounds for uniformly stable algorithms. In Conference on Learning Theory (COLT), pages 610–626, 2020.\n\n[6] O. Bousquet and A. Elisseeff. Stability and generalization. Journal of Machine Learning Research (JMLR), 2:499–526, 2002.\n\n[8] J. Chen, X. Wu, Y. Li, Q. LI, L. Zhan, and F. Chung. A closer look at the training strategy for modern meta-learning. In Conference on Neural Information Processing Systems (NeurIPS), pages 396–406, 2020.\n\n[12] Y. Klochkov and N. Zhivotovskiy. Stability and deviation optimal risk bounds with convergence rate o(1/n). In Conference on Neural Information Processing Systems (NeurIPS), 2021.\n\n\n\n", "limitations": "The authors adequately discuss the limitations of the analysis in Remark 5.\n", "rating": 7, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n+ Original and significant results on S/Q meta-learning. In particular, I am not aware of lower bounds for this setting.\n+ Clearly written.\n\nWeaknesses:\n- Some incorrect and not novel claims. (See Question 1 and 2)\n- The case with vacuous lower-bound is not analyzed in the experiments.\n\n**Update after the discussion with the authors**\n\nThe authors properly addressed my main concerns by updating the manuscript. Therefore I increase the score from 6 to 7", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept