On the Stability and Generalization of Meta-Learning
Authors: Yunjuan Wang
Raman Arora
Venue: NeurIPS 2024 poster (2024)
Keywords: meta learning
stability analysis
generalization guarantees
Primary area: optimization

Abstract: We focus on developing a theoretical understanding of meta-learning. Given multiple tasks drawn i.i.d. from some (unknown) task distribution, the goal is to find a good pre-trained model that can be adapted to a new, previously unseen, task with little computational and statistical overhead. We introduce a novel notion of stability for meta-learning algorithms, namely *uniform meta-stability*. We instantiate two uniformly meta-stable learning algorithms based on regularized empirical risk minimization and gradient descent and give explicit generalization bounds for convex learning problems with smooth losses and for weakly convex learning problems with non-smooth losses. Finally, we extend our results to stochastic and adversarially robust variants of our meta-learning algorithm.

On the Stability and Generalization of Meta-Learning
Yunjuan Wang
Raman Arora
Department of Computer Science Johns Hopkins University
Department Computer Science Johns Hopkins University Baltimore, MD, 21218 aroraêcs, jhu edu
Baltimore, MD, 21218 ywang5096jhu. edu
Abstract
We focus on developing a theoretical understanding of meta-leamiig. Given multiple tasks drawn i..dd from some (unknown) task distribution, the goal is find a good pre-trained model that can be adapted to a new, previously unseen, task with little computational and statistical overhead. We introduce novel notion of stability for meta-learning algorithms, namely uniform meta-stability. We instantiate two uniformly meta-stable learning algorithms based regularized empirical risk minimization and gradient descent and give explicit generalization bounds for convex learning problems with smooth losses and for weakly convex learning problems with non-smooth losses. Finally, we extend our results to stochastic and adversarially robust variants of our meta-learning algorithm.
Introduction
Traditional machine learning algorithms excel at generalizing, but they often require extensive training data and assume that both training and test data come from the same distribution or task. In real- world scenarios, large sets of training data from single task are often lacking. Instead, training data may stem from diverse tasks with shared similarities, while test data come from entirely new tasks. The challenge is to rapidly adapt to these unseen tasks without the need to train from scratch.
To address this challenge, meta-learning, also referred to Dearning-to-leame has emerged as an effective approach. Meta-learning has gained significant attention recently [Hospedales et al., 2021], with applications spanning across various domains including computer vision [Nichol et al., 2018] and robotics [Al-Shedivat et al., 2017], ranging from few-shot classification [Snell et al., 2017], hyperparameter optimization [Franceschi al., 2018], to personalized recommendation systems [Wang et al., 2022].
As the name suggests, meta-learning operates on two levels of abstraction to enhance learning over time. On an intra-task level, the learner needs to find models that perform well on individual tasks. On a meta-level, the learner needs to figure out useful meta-information, perhaps prior over tasks, that relates different tasks and allows transferring and adaptation of knowledge to new unseen tasks efficiently (both in terms of statistical as well computational overhead). It is typical to represent such intarmffrommnnn in the form of a pre-trained model, which we can represent using certain parammeresssss. Distinct from a standard setting, meta-learning involves training on a diverse set of tasks. At test time, we evaluate the performance of the pre- trained model on new unseen tasks while allowing it to adapt using small sample the test task.
An increasing body of empirical research dedicated advancing meta-leaming algorithms, among which agneltagnostic meta-learning (MAML) [Finn et al., 2017] stands out prominent approach. MAML designed to find good meta- parammeer w which facilitates the learning of task task-specific parameters through single step of gradient descent. In particular, given a set of m tasks denoted as { MAML estimates the peta-parreettr as argmmnn, m En L(,,, D,), where taec-fie parameters are computed as u, = w VLWW, D,).
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

However, a notable limitation of MAML is that it requires computing second-ord order derivatives, which is computationally demanding for deep neural networks in practical applications. This computational complexity also poses a challenge for a theoretical understanding of MAMI., an aspect that remains largely under-explored. To mitigate this challenge, several MAMI. variants have been proposed, including first-order MAML [Finn et al., 2017], Reptile [Nichol et al., 2018], and iMAML [Rajeswaran et al., 2019]. Owing to its success, MAML has been used for robust adversarial meta-learning [Yin et al., 2018, Goldblum et al., 2020, Wang et al., 2021, Collins et al., 2020], differential private meta-learning [Li et al., 2019], and personalized federated learning [Chen et al., 2018, Fallah et al., 2020].
Another popular framework for meta-learning is based on a "proximal" update, wherein the task-specific parameter are iteratively learned by minimizing the empirical loss and an & regu- larizer [Denevi et al., 2018, Zhou et al., 2019, Denevi et al., 2019a, 1a, 2020, Jiang et al., 2021]. Given task D and a meta- pera--arreeter w, the task-specific parameter u are defined as u = argmin, L(u D) + ||u wwl". This regularization strategy ensures that the task-specifie parameter remains close the meta- paramear similar strategy has been explored in other contexts. For exam- ple, Kuzborskij and Orabona [2017] study the problem of hypothesis transfer learning and show fast rate on the generalization error a task-specific parameter u returned by regularized empirical risk minimization conditioned on good meta-parameter w. Yet, it remains unclear how to ensure finding such a good meta-pane paraa-arreeter,, provably. Relatedly, Denevi et al. [2019b] study stochastic gradient de- scent with biased regularization for linear model and incrementally update the bias (meta-paramedd Concurrently, Zhou et al. [2019] proposed the Meta-Prox algorithm as a generic stochastic meta- learning approach. Specifically, given a set of meta-training tasks Di...., Dm, the preta-parameter is estimated by solving min, D
m min, L(u, D2) + & |lu w|l? Zhou et al. [2019] argue that Meta-Pros Prox- is generalization of MAML since the gradient descent update in MAML be viewed as taking the first-order Taylor expansion of the objective, [Zhou et al., 2019, Section 3.1].
In this work, we adopt the framework of Zhou et al. [2019] to study meta-learning from a theoretical perspective. Given m tasks drawn i.i.d. from some (unknown) task distribution μ., our goal is find a good pre-trained model (the meta-parameter) which can be adapted to a new unseen task, drawn i..dd from p,, at test time, using gradient descent. Our key contributions are as follows.
1. We introduce a novel notion of stability for meta-learning algorithms, namely uniform meta-stability. For 33rm uniformly meta-stable algorithm, we bound the generaliza- tion gap by O log (mn/5) + vlog (1/8)/(mn)).
We consider two variants of task- spe-ifpeiiiic learning - based on regularized empirical risk minimiza- tion (RERM) and gradient descent (GD)- within our meta-learning framework. We apply our stability-basee analysis to these variants to learning problems with convex, smooth losses and weakly convex, non-smooth losses. Our results are summarized in Table 1.
Algorithm
Loss
Conditions
Uniform meta-stability 3
Algo. with RERM
convex, G-Lipschitz
Y 5
Am
An
Algo. with RERM
convex, H-smonth, M-hounded
TS 2.
X(2n
HM
13
+
Xim+1J
RM
Algo. with GD
convex, G-Lipschitz, H H-soooth
n H422 2
G
+
G²
Algo. with GD
p-weakly convex, G-Lipschitz
15 x7 22
G
X
G G
Algo. 3 with GD
p-weakly convex, G- G-Lipschitz
n 1 Sr A22p G
G² Am
w.h.p.
Table 1: Bounds on uniform meta-stability |3 for different families of learning problems. Here, n is the step-size for GD for task-specific learning, Y is the step-size for GD for meta-paramete learning, m is the number of tasks during training, n is the number of training data for the task at test time.
3. We extend our results to stochastic and adversarially robust variants of our meta-learning algorithm.
1.1 Related Work
Algorithmic Stability Analysis. In many machine learning problems, standard learning theoretic tools. such as uniform convergence, do not apply since the associated complexity measures are unbounded or undefined (e.g., nearest neighbor classification), or yield guarantees that are not meaningful. Stability- based analysis is an alternative approach for obtaining generalization bounds

---

in such settings, introduced by Bousquet and Elisseeff [2002] and further developed in a long line of influential works [Elisseeff et al., 2005, Mukherjee et al., 2006, Shalev-Shwariz et al., 2010, Liu et al., 201 More recently, there have been significant breakthroughs in this field, with the work of Feldman and Vondrak [2018, 2019]. Bousquet et al. [2020], Klochkov and Zhivotovskiy [2021], thereby improving the high probability bounds for uniformly stable learning algorithms beyond those established by Bousquet and Elisseeff [2002]. These results are complemented by Hardt et al. [2016], who provide the generalization bounds via algorithmic stability analysis of stochastic gradient for stochastic convex optimization with smooth loss functions. Subsequent work by Bassily et al. [2020] improves upon these results by removing the smoothness assumption, while Zhou et al. [2022]. Lei [2023] advance the state-of-the the- art by relaxing the convexity assumption.
Theoretical Guarantees for Meta-Learning. There has been significant progress in understanding the theoretical aspects of meta-learning, both in terms of convergence guarantees [Fallah et al., 2019, Ji et al., 2020, Mishchenko et al., 2023] and the generalization guarantees. The first generalization analysis can be traced back to Baxter [2000], who assumed that all tasks are sampled i.i.d. from the same task distribution. Subsequent works have enriched the guarantees through various learning theoretic constructs, including VC theory (Ben-Davit and Schuller, 2003, Maurer, 2009, Maurer et al.. 2016], information-theoreticc theoretic tools [Chen et al., 2021, Jose and Simeone, 2021. Jose et al., 2021, Rezazadeh et al., 2021, Hellström and Durisi. 2022]. PAC-Bayes framework [Pentina and Lampert, 2014, Amit and Meir, 2018, Rothfuss et al., 2021, Farid and Majumdar, 2021, Liu et al., 2021, Ding et al., 2021, Rezazadeh, 2022, Riou et al., 2023, Zakerinia al., 2024], etc. Other works that do not rely on the task distribution assumption instead choose to get a handle on the bound by defining certain metrics to measure either the task similarity [Du et al., 2020, Tripuraneni et al., 2020, Guan and Lu, 2021] or the divergence between the new tasks and the training sample for the training tasks [Fallah al., 2021]. Finally, several works focus on the online meta-learning setting, also referred to as the lifelong learning [Pentina and Lampert, 2014, Balcan et al., 2019, Denevi et al., 2019a,b, Meunier and Alquier, 2021].
prominent line of work, starting with that of Maurer [2005], focuses on giving theoretical guarantees for meta-learning via algorithmic stability analysis. More recently, Chen et al. [2020] establish connections between single-tast task learning with support/query (cpisodic) meta-learning algorithms, providing generalization gap of O vm) (where is the number of tasks) for smooth functions that is independent of the sample size n - this was shown to be nearly optimal in Guan et al. [2022]. Subsequently, Fallah et al. [2021] show bound of O(1/mn) for strongly convex functions and by leveraging a new notion of stability. Al-Shedivat et al. [2021] extend the result of Maurer [2005] to practical meta-learning algorithms for Lipschitz and smooth losses. Farid and Majumdar [2021] derive a PAC-Bayes bound to address the qualitatively different challenges of generalization within the task compared to that at the meta-level. Other relevant work includes analyzing the stability of bilevel optimization [Bao et al., 2021] and federated learning [Sun et al., 2024] for smooth functions.
2 Problem Setup and Preliminaries
Notation. Throughout the paper, we denote scalars and vectors with lowerease italics and lowercase bold Roman letters, respectively; e.g., u, We work in Euclidean space and use ||-Il and |1-1|2 to denote the & norm. We use [n]] to represent the set {1, 21, n), and define U(n] to be the uniform distribution over (n]. Let Hw be the Euclidean projection onto W. We adopt the standard O-notation and use S and O interchangeably. We use Ô hide poly-logarithmic dependence on the parameters.
Let X' denote the input and output spaces, respectively. Consider supervised learning setting where each data point is denoted by z = (x, drawn from some unknown distribution 'D over 2 = X'x V We consider a hypothesis space H (maps from X
-> ))) parameterized by w E x Z + I denote the loss function. We say that a loss function é is M-bounded if Vw E W, Vz E D, P,E(W, 2) S M; E is p-strongly convex if VW1, W2 E W, Vz D, E(W1,2) 2) > ((W2, z) + (Ve( z), W1 W2)
W. where W- S Rd is a closed set with radius D. Let é Rdd
E || w2l if μ = O, we say É(, z) is convex. We say l is G-Lipschitz continuous if VW1, W2 E W. Vz E D. [[[[[(]..)) l(w2, z) I|I < G - E is H-smooth if Vw1, W2 E W, e D. (V Ve(We, 11, < H || wellg-
#
In a standard (single-task) learning setup, given a model w, the expected loss on task D and the empirical loss a training sample S drawn i..d. from D. are defined, respectively, as follows.
3

---

- EEND [((w,))]; L(w,S)= 1 - f(w.z).
=
In meta-learning framework, we consider distributions {D) associated with m different tasks that are drawn from some (unknown) task distribution μ.. For each task j. assume that the learner has access to n training examples drawn i..d. from Dj. i.e., S = { ~ Dj. We denote the cumulative training data as S = 5- and refer to it the meta-sample.
A meta-learning algorithm A takes the meta-sample S input and outputs an algorithm A(S) (X' x / - H. The performance of the meta- meta-algorithm A is measured in terms of its ability to generalize w.r.t loss ((.) to a new (previously unseen) task from the task distribution Je; we also refer to it as the transfer risk:
()) = -E--,Es----L((()(( D).
The goal of meta-learning is learn useful prior over tasks help with rapid adaptation to new tasks. Formally, we pose the problem as learning a meta-model, parameterized by what we will refer to as meraa-arrmeterr w, that performs well can be adapted easily to new task D μ. in particular, that task-specific model can be quickly learned from a task-specific training set S ~ D of size n using the following proximal update:
variety of tasks. The hope is that the meraapaa
u = wrw L(u, S) + 2 ||u - ||
where À > 0 is regularization parameter.
Algorithm 1 Prox Meta-Learning Algorithm A
Algorithm 2 Task -ask-spe Algorithm Ausk
Input: Meta-sample = (S, [-, epochs T, K,
Input:
Pretrained model training data S, #epochs K, step size 17, reg. parameter
step sizes 7. y), regularization parameter À
1: Option (RERM):
1: W1 = 0.
2: for = 1, do do
2: www.Sn=aggmmnnewww..
||u-wll ||u-w||
3:
l.... m do
3: Option 2 (GD):: Set ((1) (w, =
4: ((W,,S)) = Aus ( (w,, Sj, K, A)
4: for t = -1.2,..., K 1 do
% Using Algorithm 2
5: ulk+1) (W,8) (w,
5: end for
7 (VI(ulk)) 8)
6: Calculate the gradient, V/j [m]. = VFs Sj), w,)= ->(((we Sz) -we).
+)(u(k)(w, w))
7: Updatew
m - j= (u(,, we)
6: u u( (w, S) = lu (w,
8: W4+1 = =1w((w-1))
7: end for
9:
end for
8: return
Option 1 (RERM): SW
10:
return @AAunk (WT+1, A)
Option (GD): * > (()) (w, (w,
The meta- meta-maraaaaaaeeee parameter itself is learned the given meta-sample S by minimizing a regularized empirical loss averaged over tasks, where the regularization term penalizes the task-specific models in proportion the E2 distance from the meta-parameter [Zhou et al., 2019]:
W = argmin 1 - min Fs, (u, w) == argmin 1 min NEW
L(u, + 2 I|u wl
(1)
wEW m
NeW
wEW m
The formulation above involves a bi-level optimization problem. The upper-level optimization involves finding the meta-pant peta-parameter which requires solving the lower-level optimization problem of finding task-specific model parameters u. We consider both Gradient Descent (GD) as well Regularized Empirical Risk Minimization (RERM) for task-specific learning (see Algorithm 2 for more details); for meta-learning we employ a gradient descent method (see Algorithm l).
We would like to bound the transfer risk in terms of the empirical multi-task risk:
L(A(S), : Σm (S),)) To do so, we rely on the stability of the meta- algorithm.
Stability of Meta-Learning Algorithm. Given a meta-sample S = و- define Sti) to be the meta-sample obtained by replacing the training samples S, for the j-th task, in S, by another i.i.d. sample S ~ Dj. We refer to S, 86) as neighboring meta-samples. For task-specific training sample {zt) n i=1 let S(i) denote the training data obtained by replacing the i-th example z' S by another example z' ~ D drawn independently; we refer to S, (() as neighboring samples.
Theorem 2.1 (Maurer [2005]). Suppose the aeta-algo A satisfies:

---

1. (Uniform Stability of Single-Tast Learning) For any meta-sample S and any S, S(,)) [((A(S)(S), ((A(S) z) I B.
2. (Uniform Stability of Meta-l.earning) For any S, SU) and any given training set S ~ D,
[[A(S)(S), - ((A(S))
Then, for M-bounded loss f, with probability at least 8, we have that
L(A(S), 1) S L(A(S), + (m3' + MM v log (1/6) + 3.
Theorem 2.1 follows using a simple extension of arguments in Bousquet and Elisseeff [2002]. By utilizing sharper bounds tailored for uniformly stable algorithms [Bousquet et al., 2020]. tighter bound can be achieved, as demonstrated in Theorem 2.2 below. A similar result was shown in Guan et al. [2022] for episodic training algorithms (except there is no 5).
Theorem 2.2. Suppose the meta-algorithm satisfies the same conditions shown in Theorem 2.1. Then for M-bounded loss f, with probability at least 8, we have that
L(A(S); ()) S L(A(S),)) + 3r log (m) log (1/6) M /log (1/8) ( +
Uniform Meta-Stability
Motivated by prior work (i.e., Theorem 2.1 and the definitions therein), introduce notion of stability which measures the sensitivity of the learning algorithm as we replace both a task in the meta-sample as well single training example available for the task at test time.
say that a meta-learning algorithm is 3- uniformly meta-stable for any neighbouring meta-samples S, st), and neighboring samples S(), for any task D ~ f and any D, we have that
Definition (Uniform Meta-Stability).
L( (()() 2) ((A(S)))(S())
- 3.
The definition above is rather natural. Intuitively, for a meta-learning algorithm to transfer well, we require that the learning algorithms, i.e., A(S) and A(S'). returned on neighboring meta-samples, when trained on two neighboring samples return models that predict similarly. Our first result bounds the generalization gap in terms of the uniform meta-stability parameter.
Theorem 3.1. Consider meta-learning problem for some M bouudddd loss function é and task distribution p. Let S be a meta-sample consisting of training samples on m tasks each of size and let S 'D be a sample of size on a previously unseen task D ~ J.. Then, for any 3-uniformly meta-stable learning algorithm A, we have that with probability 1 8,
L(A(S), () S L(A(S), S) + 3 log (mn) log (1/6) + M /log (1/8) (mn).
The result above direct analogue of Theorem 2.1 with stability parameters B, 3 both subsumed into a single meta-stability parameter. We do obtain a faster rate of convergence as we instantiate concrete algorithms and specialize our results to specific problems Section 4.1, we will see notable improvement in rates from 1//m to 1/m, for n. > m.
We conclude the section by presenting alternate notion of algorithmic meta-stability and basic result that directly bounds the generalization gap for the meta-learning problem.
Definition (On-Average Meta-Stability). Let be an (unknown) underlying task distribution. We say that a meta-learning algorithm is 3- average-replace-onne -oeelacce-oe--ettte meta-stabll if
Eg - (P:) (8, (+DD++ (" j- (-Um)
((
((A(((((()))))))
s B.
Theorem 3.2. Let be underlying task distribution. Given meta-sample S, test task D μ., and ~ D", for any B -on--ooeragee aerragereppcc------mne----taaa meta-learning algorithm A, we have that (LA4)))) (L(A(S), L(A(S), S)] B.
E [p ),,",
4 Bounding Transfer Risk
In this section, we consider a concrete meta- meta-learning algorithm given in Algorithm 1.
5

---

4.1 Convex and Smooth Losses
We begin with meta-learning problems with convex, Lipschitz (and potentially smooth) losses.
Lemma 4.1. Assume that the loss function é is convex and G-Lipschitz loss. Let S, SÚ) denote neighboring meta-samples and S, s(t) the neighboring samples test task. Then, the following holds for Algorithm with RERM for task-specific learning (i.e., Option for Algorithm 2) AT 2 1,
sup (,m (
G 2G Am
-
An
Further, l convex, M-bounded and H-smooth, then setting X H, y S f. we have VT 2 1,
2/2HM
2An H + n 4/2HM
[(())()) A(S (S()))
sup 8,5 S.S.je(m)).i
2 H (m +1)
We now use the result above with Theorem 3.1 to get the following bound on the transfer risk.
Theorem 4.2. The following holds for Algorithm with step-size y S 3 on given mata-s S, and RERM for task-specific learning (i.e., Option 1 for Algorithm 2), for all T 2 1:
1. For convex, M-bounded, and G G-Lipschitz loss functions, with probability at least 5
G An
C² log (mn) log (1/8) + M MMolog (1/8) Am
L(A(S).)) L(A(S).))
+
mn
2. For convex, M-hounded, and H-smooth loss functions (H S X), with probability at least
HM
HM (m + 1)A
log (mm) log (1/8)+ M Mvlog (1/5)
L(A(S),))
(2n 1)X
Vmn
Next, we give analogous results for GD for task-specific learning (i.e., Option for Algorithm 2), albeit for smooth loss functions. Lemma 4.3 bounds the output sensitivity of the meta-learning algorithm. We use it with Theorem 3.1 to give the generalization guarantee in Theorem 4.4.
Lemma 4.3. Assume that the loss function is convex, G-Lipschitz and H-smooth. Let S, SÚ) denote neighboring meta-samples and S, 860 the neighboring samples on test task. Then the following holds for Algorithm with GD for task-specific learning (i.e., Option for Algorithm 2) with 1) S #*22 for all T 2 1 as long
set 7 X7
A A(S))) -
4eG Am
2G +
sup (.S.je(m))ii((n
An"
Theorem 4.4. Assume that the loss function convex, M-bounded, G-Lipschitz and H-smooth. Xт on given meta-sample S, and GD for
Suppose we run Algorithm for T iterations with S 1
task-specific learning (Option 2, Algorithm 2) with # Then, with probability least 6,
G²
G2
log (mn) log (1/5) M Mog (1/5)
L(A(S), p) & L(A(S).))
Am
An
Vmn
The results above show that meta-stable learning algorithms not overfit. The bound on the generalization gap of ( + > is tighter than what we would obtain using prior work. Indeed, we show that Theorem 2.2 yields a rate Õ + + vm (see Theorems C.2 and C.3 in Appendix), which is worse for all < n². Notably, the bounds on the generalization gap are independent of the number of iterations of the meta lcarning Algorithm 1 and the number of iterations of GD for Algorithm 2. This holds since the objective we are minimizing strongly convex (given the strongly convex regularizer), which ensures that the output sensitivity (in Lemmas 4.3 and 4.1 are independent of T and K. In itself, this should not be surprising since only bound the generalization error in terms of the empirical error the latter may not be small unless the algorithms have converged. To get better handle on the generalization error we focus on excess (transfer) risk bounds in Section 4.3. But first we give a similar development for another important problem class.

---

4.2 Weakly Convex and Non-smooth Losses
Here, we focus more practical setting of learning problems with loss functions that weakly convex and non-smooth. The notion of weak convexity is often used in non-convex optimization literature in variety of problems including robust phase retrieval [Davis et al., 2020] and dictionary learning [Davis and Drusvyatskiy, 2019]; see Drusvyatskiy [2017] for an extended discussion.
Definition. A function f(w) is p-weakly conver w.r.t. |1-I1 if f(w) + & ||ll is convex in w.
The class of weakly convex functions is contained within the larger class of non-smooth functions and semi-smooth functions [Mifflin, 1977]. It includes convex functions and smooth functions with Lipschitz continuous gradient as special cases; p 0 implies that the function is strongly convex. An important example from a practical perspective is that of training over- wer-pparaeterizeed two-layer neural networks with smooth activation functions using smooth loss [Richards and Rabbat, 2021]. We first bound the sensitivity of Algorithm for weakly convex and non-smooth losses.
Lemma 4.5. Assume that the loss function is p-weakly convex and G-Lipschitz. Let S. St)) denote neighboring meta- sattlls and S, ((t) the neighboring samples on a test task. Then the following holds for Algorithm with À 2 2p, and GD for task- siss---pcifiic learning (i.e., Option 2 for Algorithm 2)
with yj S I.. for all 2 1 as long as we set y S X7.
SeG 8G Am
sup
-
(8eG 2G)
An
Using the result above in conjunction with Thm 3.1 gives the following bound on the transfer risk. Theorem 4.6. Assume that the loss function is p-weakly convex, M-hounded, and G-L.ipschitz. Suppose we run Algorithm for T iterations with 7 S XT: À 2 2p meta-sample S, and GD for
task-specific learning (Option 2, Algorithm 2) with 1) S Then, with probability at least 1 8,
G
G2
log (mn) log (1/5) Mv Mylog/// (1/6)
L(A(S), (2) S ((A(S))S) + V
+
Am
An
Vmn
Proof of Theorem 4.6 follows from Lemma 4.5 and Theorem 3.1. A few remarks are in order.
For learning rate 7 S X Theorem 4.6 gives a rate of (( 1 m n vim) on the generalization
gap. This naturally suggests setting 1) IR. where K > min {m, is the number of iterations of GD in task-specific learning. Then, similar to the discussion in Section 4.1, Theorem 4.6 gives a tighter bound, when n > m, than those derived using prior work (Theorem 2.2); we refer the reader to Theorem D.4 in the appendix for further details.
Our proof technique shares similarities with Bassily et al. [2020]. However, our result is not a straightforward application of theirs as we deal with bi-level optimization problem and focus on weakly convex functions. It is worth noting that our results for weakly convex non-smooth losses require regularization parameter À 2 2p, which can be chosen practice using cross- validaaali
The work most related to ours is that of Guan et [2022]. However, our results are fundamentally different from theirs in several aspects. Firstly, the algorithms we study are different. Guan et al. [2022] focus on support/query (S/Q) training strategies (aka episodic training) where each task Sy is split into two non-overlapping parts the support set S for training the task-specific parameter and the query set S/s for measuring the algorithm's 's performance [Vinyals al., 2016]. The meta- parameter is learned by minimizing the loss computed over the query set. Such S/Q training strategy is popular for modern gradient-based meta-learning algorithm such as MAML for few-shot learning [Finn et al., 2017], where the optimization objective can be written as min 1
m ΣØ= L(w- (L(w,STr) Sf*). One notable limitation is that Guan et al. [2022] assume that the loss function on the task level, e.g., S,) L(w V St")), SJ*),, is convex or (Hölder) smooth. Such an assumption is highly impractical, as demonstrated by [Mishchenko et al., 2023, Theorem 1, Theorem 2], which provides several counterexamples where L is convex and smooth but It is neither convex nor smooth. In contrast, we directly deal with L being weakly convex and nonsmooth. Our approach requires more involved proof that deals with stability of bi-level optimization. This is in stark contrast with Guan et al. [2022] who directly reduce the meta-learning problem to single-task learning problem without considering the bi-level structure of the problem.
The work of Fallah et al. [2021] proposed notion of stability similar to ours. The difference that they consider S/Q training and define the stability by changing a mini-batch of samples in Syr as
7

---

well as a single sample in S.a, Moreover, their focus is primarily on strongly convex losses. They discuss generalization to training tasks and unseen tasks separately, as they do not assume all tasks are sampled from the same task distribution. Another related work of Guan and Lu [2021] present a generalization bound of O(yC/mn) under task relatedness assumption, where C' captures the logarithm of the covering number of hypothesis class that possibly depends on the dimension d. More recently, Riou et al. [2023] provide generalization bounds with fast rate of O + H, albeit under an additional extended Bernstein's 's condition.
4.3 Excess Transfer Risk
In the previous sections, we focused on establishing that meta-stable rules do not overfit to the meta-sample. In this Section, we focus on the question of whether meta-learning Algorithm can achieve a small generalization error, i.e., are they guaranteed to transfer well on unseen tasks? We show that by focusing on the computational aspects, i.e., by bounding the optimization error in terms of the number of iterations. Furthermore, we give bounds on excess risk, wherein the benchmark is the performance of the best possible in-class predictor.
Let u, argmin L(u, D), uz argmingew L(u, Sj). Vj E [m]] be the optimal task specific hypotheses for the unseen task and the given training tasks, respectively. Given meta-algorithm A, the excess transfer risk can be decomposed as follows:
I (A(S)))) 1 [1AASS)6),.)))
(S),)) -I,
Excess Transfer Risk (A)
Generoiizztion Clop (AA)
Optimiizaiio and Approximaation Exge+
[L S;) L(u., Sy]]
S,) D))-
3=1
3yje[m], D3 www..ng..ppp..... (D Pym
To control excess risk, we need to bound Egen (A) and Eopt+app (A) simultaneously. The bounds on the first term are presented in the previous section. Here, we focus on analyzing the second term.
Theorem 4.7. Assume that the loss E is convex and G-Lipschitz. Define uj argmin, L(u, Sy). Vj E and using GD for task-
[m]. Suppose we run Algorithm for T iterations with step-size ? specific learning (i.e., Option 2 for Algorithm 2), to find an algorithm A(S) = Ansk (WT+1,,))) which then run on S, for K iterations with step-size 1) 2 Then, we have that
D2
L(A inn L(u, S
12
n
where W is defined in Equation (1). Here 0² m Σラ | -wu is the approximation error, and ||WT+1 ~
x +
n2 An
+ 2(G+2XD12) is the optimization error.
Finally, to bound the excess transfer risk for convex and non-smooth losses, we use Theorem 4.6 with Theorem 4.7 to get that in expectation over the sampling of data (meta-sample S and sample S)
El[Enss (A4) < ((ge) [ (A)
7 X
G²
G
D2 nn n
+G T +
AD
Am An
By properly choosing step size 17 = 0 (x ), we obtain that the expected excess transfer risk 1 + 1 + $ + + Similarly, for convex, Lipschitz and smooth An
decays at rate of O( ' + Am losses, applying Theorem 4.4 with Theorem 4.7 and selecting 17 O( X/R m, n tend to infinity, the
results in expected x Therefore, as K,T,m,
excess transfer risk of O( AyK
excess risk converges to o². As a represents the average distance between the optimal task-specific parameters u, 's and the optimal estimated meta-parameter w. the excess risk is small when small. It is also typical to set the regularization parameter À inversely proportional to the sample size n (e.g.. ((1 vn)).
Denevi et al. [2019a] study the same algorithm as ours except in the online setting. However, the function classes they consider are limited to compositions of linear hypothesis classes with convex and closed losses. In contrast, our work considers a broader range of functions, encompassing not only convex, Lipschitz, and smooth functions but also weakly-convex and non-smooth functions. The
8

---

m ). where Varm captures the relatedness among the tasks sampled from the task environment. Unfortunately,
bound on expected excess risk shown in Denevi et al. [2019a] takes the form O Varm
v
which depends on Varm a quantity that often not known a priori in practice. To compare with our work, set K = n, 7 m, " 0(1/v/)) and À = ((1/vn) Vnn..Thnn applying Theorem 4.4 with Theorem 4.7, we obtain that [A) y
this bound relies on a specific choice of X - O
log(n)
Var
_ Considering both Varm and a as constants, the bound on expected
Vn
excess risk based our analysis is tighter than that of Denevi et al. [2019a] when S common setting studied in meta- leta-learning framework.
We also conduct a simple experiment to empirically verify the tightness of our generalization bounds, which we defer to Appendix A due space limitations.
Implications of the Generalization Bounds 5
Next, we present stochastic and adversarially robust variants of the meta-learning Algorithm
5.1 Proximal Meta-Learning with Stochastic Optimization
We adapt Algorithm to utilize aunpling-wit--repllceeee training set of a single task; see Algorithm 3 for more details. We show that with high probability the sensitivity of this stochastic meta-learning algorithm is bounded.
where at each iteration we process the
Lemma 5.1. Assume that the loss function is p-weakly convex and G-Lipschitz. Let S, S denote test task. Then, with probability at least 1 1-co expp (-T²²² /m²). the following holds for Algorithm 3 with À 2 2p, and GD for task-
neighboring meta- satalss and S, S the neighboring samples
specific learning (i.c., Option 2 for Algorithm 2) with S 1.- for all T 2 1 as long as we set S X7
A(S)(S) - ((()) (8eG + / sup (M)
7 +
8eG
8G
Am +
An"
5.2 Robust Adversarial Proximal Meta-Learning
We consider inference-time adversarial at- tacks with general threat model B: X -
Algorithm Stochastic Prox Meta Meta-nng
2x. Specifically, given an input example x E B() S RR represents the set of all possible perturbations of x that adversary can choose from. This includes the typical examples such as the Lpp threat models that are often considered in practice, or a discrete set of designed transformations.
Input: Meta-sample S S= ) epochs T, K, step
size 7 77 regularization parameter X.
I: W1 = 0.
2: for / = 1, ..... do
3: Sample je ~ U(m].
4: u(w., S,, = Ausk Sp K, 17, A).
% Using Algorithm 2
Calculate the gradient
Given a model parameter w, let ((w,z) = B() f(w,2) Z) denote the adversarial loss.
Vf', (u( (,, S,,), We) ->((ww, S()(We,Sj)))) -we). (u(we, S,,), Wt).
6:
Update W++1 We
We adapt the standard meta-learmin frame-
7:
W [lw(W++)).
work simply by considering the robust vari-
8:
end for
ant, ?. of the standard loss We denote the robust transfer risk and empirical ro- bust multi-task risk as (mb(((()) and (A()) S). Now, given meta-sample S. the goal is to learn robust prior (e.g., pre-trained model) for rapid adaptation to and robust generalization on new tasks. We adopt the framework presented in Section 2 except 2) on robust loss in Algorithm 2 yields adversarial training. We use Algorithm for meta- meta--carning. We now relate loss function with its adversarially robust counterpart.
9: return ( K,
use robust loss for task-specific training; indeed, using GD (Option
Proposition 5.2. Given loss function (()z)) and its adversarial counterpart E(., z), the following holds: (1) If é G-Lipschitz (in its first argument), then is G-Lipschitz. (2) ? is not H H-smooth even if é is -moohh... (3) If l is -moohhth in w, then é is H- H-weakly convex in w.
Using the result above with Theorem 3.1 yields the following bound on robust (transfer) risk.

---

Corollary 5.3. Assume that the loss is M-bounded and H-smooth. Suppose we run Algorithm 1 for T itterttions with y S X 7 S x 2H, and wherein task-specific learning Algorithm 2 (GD)
is invoked with robust loss é, we have that with probability at least - 5,
+
G
7 A
G²
G2
log (mn) log (1/8)+ M Myllg (1/6)
Am
An
Vmn
Note that prior work on robust adversarial meta-learning [Yin et al., 2018, Goldblum al., 2020, Wang et al., 2021] ] focuses on empirical study of the problem; we present first theoretical guarantees.
6 Conclusion
In this paper, we introduce novel notion of stability for meta-learning algorithms, namely uniform meta-stability, and offer a tighter bound on the generalization gap for the meta-learning problem compared to existing literature. We instantiate uniformly meta-stable learning algorithms and give generalization guarantees for both convex, smooth losses as well as weakly convex and non-smooth losses. Several avenues for further exciting research remain. For instance, it remains to be seen our bounds are tight. Can we show lower bounds on the generalization error for meta-learning? Additionally, understanding how meta- meta-learning relates to federated learning may offer insights how to extend the theory to broader applications and inform the design of new algorithms. Finally, motivated by data privacy considerations, it would be interesting to extend setup to privacy- preserving meta-learning, similar in spirit to the recent work of Zhou and Bassily [2022].
Acknowledgments and Disclosure of Funding
This research supported, in part, by the DARPA GARD award HR001 12020004, NSF CAREER award ITS- 194321,,, funding from the Institute for Assured Autonomy (IAA) at JHU, and the Spring '22 workshop on "Learning and Games" at the Simons Institute for the Theory of Computing. YW acknowledges the support of Amazon Fellowship.
References
Maruan Al-Shedivat, Trapit Bansal, Yuri Burda, Ilya Sutskever, Igor Mordatch, and Picter Abbeel. Continuous adaptation via meta-learning in nonstationary and competitive environments. arXiv preprint Xrv: :XX.:/710.03641 2017.
Maruan Al-Shedivat, Liam Li, Eric Xing, and Ameet Talwalkar. On data efficiency of meta-learning In International Conference on Artificial Intelligence and Statistics, pages 1369-1377. PMLR,
2021.
Ron Amit and Ron Meir. Meta-learning by adjusting priors based on extended pac-bayes theory. In International Conference on Machine Learning, pages 205-214, PMLR, 2018.
Maria-Florine Balcan, Mikhail Khodak, and Ameet Talwalkar. Provable guarantees for gradient- meta-learning. In International Conference on Machine Learning, pages 423- PMLR, 2019.
Fan Bao, Guoqiang Wu, Chongxuan Li, Jun Zhu, and Bo Zhang. Stability and generalization of bilevel programming hyperparameter optimization. Advances in neural information processing systems, 34:4529 4551, 2021.
Raef Bassily, Vitaly Feldman, Cristóbal Guzmán, and Kunal Talwar. Stability of stochastic gradient descent on nonsmooth convex losses. Advances in Neural Information Processing Systems, 33: 4381-4391, 2020.
Jonathan Baxter. A model of inductive bias learning. Journal of artificial intelligence research, 12: 149-198, 2000.
Shai Ben-David and Reba Schuller. Exploiting task relatedness for multiple task learning. In Learning Theory and Kernel Machines: 16th Annuul Conference Leurning Theory and 7th Kernel Workshop, COLT/Kernel 2003, Washington, DC, USA, August 24-27, 2003, Proceedings, pages 567-580. Springer, 2003.
10

---

Olivier Bousquet and André Elisseeff. Stability and generalization. The Journal of Machine Learning Research, 2:499-526, 2002.
Olivier Bousquet, Yegor Klochkov, and Nikita Zhivotovskiy. Sharper bounds for uniformly stable algorithms. In Conference on Learning Theory, pages 610-626 PMLR, 2020.
Fei Chen, Mi Luo, Zhenhua Dong, Zhenguo Li, and Xiuqiang He. Federated meta-learning with fast convergence and efficient communication. arXiv preprint arXiv: 078760 2018.
Jiaxin Chen, Xiao-Ming Wu, Yanke Li, Qimai Li, Li-Ming Zhan, and Fu-lai Chung. A closer look at the training strategy for modern meta-learning. Advances in Neural Information Processing Systems, 33:396-4000 2020.
Qi Chen, Changjian Shui, and Mario Marchand. Generalization bounds for meta-learning: An information-theerriiic analysis. Advances in Neural Information Processing Systems, 34:25878- 25890, 2021.
Liam Collins, Aryan Mokhtari, and Sanjay Shakkottai. Tosk-robust modcl-agnostic meta-learning, Advances in Neural Information Processing Systems, 33: 188188-08887,, 2020.
Damek Davis and Dmitriy Drusvyatskiy, Stochastic moodel-based minimization of weakly convex functions. SIAM Journal on Optimization, 29)))227-2339 2019.
Damek Davis and Benjamin Grimmer. Proximally guided stochastic subgradient method for nons- mooth, nonconvex problems. SIAM Journal on Optimization, 1903):1908-19933 2019.
Damek Davis, Dmitriy Drusvyatskiy, and Courtney Paquette. The nonsmooth landscape of phase retrieval. IMA Journal of Numerical Analysis, 40(4):2652-2699) 2695, 2020.
Giulia Denevi, Carlo Ciliberto, Dimitris Stamos, and Massimiliano Pontil, Learning to learn around common mean. Advances in neural information processing systems, 31, 2018.
Giulia Denevi, Carlo Ciliberto, Riccardo Grazzi, and Massimiliano Pontil. Learning-tor -o-lecmm stochas- tic gradient descent with biased regularization. In International Conference on Machine Learning, pages 1566-1575 PMLR, 2019a.
Giulia Denevi, Dimitris Stamos, Carlo Ciliberto, and Massimiliano Pontil. Online-within-onlle meta-learning. Advances in Neural Information Processing Systems, 32, 2019b.
Giulia Denevi, Massimiliano Pontil, and Carlo Ciliberto. The advantage of conditional meta-learning for biased regularization and fine tuning. Advances in Neural Information Processing Systems, 33: 964-974, 2020.
Nan Ding, Xi Chen, Tomer Levinboim, Sebastian Goodman, and Radu Soricut. Bridging the gap between practice and pac-bayes theory in few-shot meta-learning. Advances in Neural Information Processing Systems, 34:29506-299 16, 2021.
Dmitriy Drusvyatskiy. The proximal point method revisited. arXiv preprint arXiv:1712.06033 2017.
Simon S Du, Wei Hu, Sham M Kakade, Jason D Lee, and Qi Lei. Few-shot learning via learning the representation, provably. arXiv preprint arXiv:2002.0943: 2020.
Andre Elisseeff, Theodoros Evgeniou, Massimiliano Pontil, and Leslie Pack Kaelbing, Stability of randomized learning algorithms. Journal of Machine Learning Research, 6(1), 2005.
Alireza Fallah, Aryan Mokhtari, and Asuman Ozdaglar. On the convergence theory of gradient- braed model-agnostic meta-learning algorithms. arxiv preprint: 1908.10400) 2019.
Alireza Fallah, Aryan Mokhtari, and Asuman Ozdaglar. Personalized federated learning: A meta- learning approach. arXiv preprint arXiv:2002.07948, 2020.
Alireza Fallah, Aryan Mokhtari, and Asuman Ozdaglar. Generalization of model-agnostic meta-
learning algorithms: Recurring and unseen tasks. Advances in Neural Information Processing Systems, 34:5469-5480, 2021.

---

Alec Farid and Anirudha Majumdar. Generalization bounds for meta-learning via pac-bayes and uniform stability. Advances in neural information processing systems, 34:2173-2186, 2021.
Vitaly Feldman and Jan Vondrak. Generalization bounds for uniformly stable algorithms. Advances in Neural Information Processing Systems, 31, 2018.
Vitaly Feldman and Jan Vondrak. High probability generalization bounds for uniformly stable algorithms with nearly optimal rate. Conference on Learning Theory, pages 1270-1279. PMLR, 2019.
Chelsea Finn, Pieter Abbeel, and Sergey Levine. Model-agmostic meta-learning for fast adaptation of deep networks. International conference on machine learning, pages 1126-1135. PMLR, 2017.
Luca Franceschi, Paolo Frasconi, Saverio Salzo, Riceardo Grazzi, and Massimiliano Pontil. Bilevel programming for hyperparameter optimization and meta-learning. In International conference on machine learning, pages 1568-1577. PMLR, 2018.
Micah Goldblum, Liam Fowl, and Tom Goldstein. Adversarially robust few-shot learning: meta-learning approach. Advances in Neural Information Processing Systems, 33:1 13:6688--78895 2020.
Jiechao Guan and Zhiwu Lu. Task relatedness-based generalization bounds for meta learning. In International Conference Learning Representations, 2021.
Jiechao Guan, Yong Liu, and Zhiwu Lu. Fine- Fine-grained analysis of stability and generalization for modern meta learning algorithms. Advances in Neural Information Processing Systems, 35: 18487-18500, 2022.
Moritz Hardt, Ben Recht, and Yoram Singer. Train faster, generalize better: Stability of stochastic gradient descent. In International conference on machine learning, pages 1225-1234. PMLR, 2016.
Fredrik Hellström and Giuseppe Durisi. Evaluated emi bounds for meta learning: Tightness and expressiveness. Advances in Neural Information Processing Systems, 35:20648-20660, 2022.
Timothy Hospedales, Antreas Antoniou, Paul Micaelli, and Amos Storkey. Meta-learning in neural networks: A survey. IEEE transactions on pattern analysis and machine intelligence, 44(9): 5149-5169, 2021.
Kaiyi Ji, Jason Lee, Yingbin Liang, and Vincent Poor. Convergence of meta-learning with task-specific adaptation over partial parameters. Advances in Neural Information Processing Systems, 13:11490-11500, 2020.
Weisen Jiang, James Kwok, and Zhang. Effective meta-regularizatton by kernelized proximal regularization. Advances in Neural Information Processing Systems, 34:26212-26222 2021.
Sharu Theresa Jose and Osvaldo Simeone. theoorition-theoretiiic generalization bounds for meta- learning and applications. Entropy, 23(1):126, 2021.
Sharu Theresa Jose, Osvaldo Simeone, and Giuseppe Durisi. Transfer meta-learning: Information- theoretic bounds and information meta-risk minimization. IEEE Transactions on Information Theory, 68(4):774- 2021.
Yegor Klochkov and Nikita Zhivotovskiy. Stability and deviation optimal risk bounds with conver- gence rate o11 /n). Advances in Neural Information Processing Systems, 34:5065-5076, 2021.
Ilja Kuzborskij and Francesco Orabona. Fast rates by transferring from auxiliary hypotheses. Machine Learning, 106: 2017.
Yunwen Lei. Stability and generalization of stochastic optimization with nonconvex and nonsmooth problems. In The Thirty Sixth Annual Conference Learning Theory, pages 191-227. PMLR, 2023.
Jeffrey Li, Mikhail Khodak, Sebastian Caldas, and Ameet Talwalkar, Differentially private meta- learning, arXiv preprint
2019.
12

---

Tianyu Liu, Jie Lu, Zheng Yan, and Guangquan Zhang. Pac-bayes bounds for meta-learning with data-dependent prior. arXiv preprint arX1v:2102.03748, 2021.
Tongliang Liu, Gábor Lugosi, Gergely Neu, and Dacheng Tao. Algorithmic stability and hypothesis complexity. In International Conference on Machine Learning, pages 2159-2167. PMLR, 2017.
Andreas Maurer. Algorithmic stability and meta-learning. Journal of Machine Learning Research, (6), 2005.
Andreas Maurer. Transfer bounds for linear feature learning. Machine learning, 75(3):327-350, 2009.
Andreas Maurer, Massimiliano Pontil, and Bernardino Romera-Paredess. The benefit of multitask representation learning. Journal of Machine Learning Research, 17(81):1-32, 2016.
Dimitri Meunier and Pierre Alquier. Meta-strategy for learning tuning parameters with guarantees. Entropy, 23(10):1257, 2021.
Robert Mifflin. Semismooth and semiconvex functions in constrained optimization. SIAM Journal on Control and Optinization, 15(6):959 972, 1977.
Konstantin Mishchenko, Slavomir Hanzely, and Peter Richtárik. Convergence of first-order algorithms for meta-learning with moreau envelopes. arXiv preprint arXiv:2301.06800 2023.
Sayan Mukherjee, Partha Niyogi, Tomaso Poggio, and Ryan Rifkin. Learning theory: stability is sufficient for generalization and necessary and sufficient for consistency of empirical risk minimization. Advances in Computational Mathematics, 25:161-193, 2006.
Alex Nichol, Joshua Achiam, and John Schulman. On first-order meta-learning algorithms. arXiv 2018.
preprint
Anastasia Pentina and Christoph Lampert. A pac-bayesian bound for lifelong learning. In Interna- fional Conference on Machine Learning, pages 991-999. PMLR, 2014.
Aravind Rajeswaran, Chelsea Finn, Sham M Kakade, and Sergey Levine. Meta-learning with implicit gradients. Advances in neural information processing systems, 32, 2019.
Yao-Feng Ren and Han- Ying Liang. On the best constant in marcinkiewicz--yygnnd inequality. Statistics & probability letters, 53(3):227-233 2001.
Arezou Rezazadeh. A unified view on pac-bayes bounds for meta-learning. In International Conference on Machine Learning, pages 18576-18595. PMLR, 2022.
Arezou Rezazadeh, Sharu Theresa Jose, Giuseppe Durisi, and Osvaldo Simeone. Conditional mutual information- based generalization bound for meta learning. In 2021 IEEE International Symposium on Information Theory (ISIT), pages 1176-1181. IEEE, 2021.
Dominic Richards and Mike Rabbat. Learning with gradient descent and weakly convex losses. In International Conference on Artificial Intelligence and Statistics, pages 1990-1998. PMLR, 2021.
Charles Riou, Pierre Alquier, and Badr-Eddine Chérief-Abdellatif, Bayes meets bernstein at the meta level: analysis of fast rates in meta-learning with pac-bayes. arXiv preprint / 2023.
Jonas Rothfuss, Vincent Fortuin, Martin Josifoski. and Andreas Krause. Pacoh: Bayes-optimal meta-learning with pac-guarantees. In International Conference on Machine Learning, pages 9116-9126. PMLR, 2021.
Shai Shalev-Shwarde and Shai Ben-David. Understanding machine learning: From theory to algorithmss Cambridge university press, 2014.
Shai Shalev-Shwartz, Ohad Shamir, Nathan Srebro, and Karthik Sridharan. Learnability, stability and uniform convergence. The Journal of Machine Learning Research, 0222635-2670. 2010.
13

---

Jake Snell, Kevin Swersky, and Richard Zemel. Prototypical networks for few-shot learning, Advances in neural information processing systems, 30, 2017.
Zhenyu Sun, Xiaochun Niu, and Ermin Wei. Understanding generalization of federated learning via stability: Heterogeneity matters. In International Conference on Artificial Intelligence and Statistics, pages 676 684. PMLR, 2024.
Nilesh Tripuraneni, Michael Jordan, and Chi Jin. On the theory of transfer learning: The importance of task diversity. Advances in neural information processing systems, 33:7852-7862, 2020.
Oriol Vinyals, Charles Blundell, Timothy Lillicrap, Daan Wierstra, al. Matching networks for one shot learning. Advances in neural information processing systems, 29, 2016.
Chunyang Wang, Yanmin Zhu, Haobing Liu, Tianzi Zang, Jiadi Yu, and Feilong Tang. Deep meta-learning recommendation systems: survey. arXiv preprint arXiv:2206. 04415, 2022.
Ren Wang, Kaidi Xu, Sijia Liu, Pin-Yu Chen, Tsui-Wei Weng, Chuang Gan, and Meng Wang. On fast adversarial robustness adaptation in model-agnostic meta-learning. arXiv preprint arXiv:2102.10454, 2021.
Jiancong Xiao, Yanbo Fan, Ruoyu Sun, Jue Wang, and Zhi Zhi-Quan Luo. Stability analysis and generalization bounds of adversarial training, Advances in Neural Information Processing Systems, 35:15446-1545, 2022.
Yue Xing, Qifan Song, and Guang Cheng. On the algorithmic stability of adversarial training. Advances in neural information processing systems, 34:26523-265333 2021.
Chengxiang Yin, Jian Tang, Zhiyuan Xu, and Yanzhi Wang. Adversarial meta-learning. arXiv 2018.
preprint
Hossein Zakerinia, Amin Behjati, and Christoph H Lampert. More flexible pac-bayesian meta- learning by learning learning algorithms. arXiv preprint arXiv:2402.04054 2024.
Pan Zhou, Xiaotong Yuan, Huan Xu, Shuicheng Yan, and J'ashi Feng. Efficient meta learning via minibatch proximal update. Advances in Neural Information Processing Systems, 32, 2019.
Xinyu Zhou and Raef Bassily. Task-level differentially private meta learning. Advances in Neural Information Processing Systems, 15:20947-209955 2022.
Yi Zhou, Yingbin Liang, and Huishuai Zhang. Understanding generalization error of sgd in nonconvex optimization. Machine Learning, pages 1-31, 2022.
14

---

Supplementary Material
A Experiments
In this section, we conduct simple experiment to empirically verify our generalization bounds.
Setting. Following the experimental setting in Nichol et al. [2018] and Zhou et al. [2019], we consider a synthetic one-dimensional sine wave regression problem. The goal is approximate the distribution of parameters of function [2z ox, (3) = a sin( x + 8). The task environment is a joint distribution ((a, 9) of the parameters a and 3. We take D(a, (3) to be a product distribution of D(a)= = ([-5, 5) (3) = U(10, r)). We generate the meta-sample by first sampling m training tasks, i.c., pairs of (a, 3) sampled independently from D(a, 3). For each of these m tasks, we sample = 10 points, 21. .......
uniformly on [-5,5] 5] and label them ys f(x;; a, (). Similarly, at test time we generate new task from the task distribution and generate training sample of size n (by sampling z's uniformly on the interval |-5, 5] and labeling them using faz a, 8). We sample 1000 new tasks at test time. For each of the test task, we also generate an evaluation set of size 200, and use it to estimate the mqaare error between the predictions of the learned model and the true labels. Our hypothesis class is two layer network of width 40 and lanh(.) activation function. We run Algorithm for T = 100 iterations with a step size of y 0.1 and regularization parameter = 0.5. Algorithm (GD) is run for K = 15 iterations with step size dj = 0.02. The experiment is conducted
T4 GPU.
Results. We report the transfer risk, the average empirical risk (over tasks), and the generalization gap for different values of m and n in Figure 1. In the plot on the left, we fix n = 10, and vary the number of tasks from 10 to 5000. In the plot in the middle, the number of samples n from 5 to 1000. In the plot on the right, we choose m n, and scale m and n simultaneously from 10 to 1000. We observe that in all of these three scenarios, as m (and/or n) increase, both the generalization gap as well as the transfer risk decrease. Moreover, the generalization gap decreases at rates approximately (11/m + 1/n + 1/ 1//m)) for these three scenarios as suggested by our theoretical result.
fix m 1000, and change
4.9
4.5
(LA(S),
2.5
L(A(S),
3.5
(LA(S),
(LA(5),
(L)(S),
((A(S),
8 20
2.5
Epm
2:0
1.0
1.5
3.04
0.5
00
0.0
number tasks
number samples
Figure 1: Error plots function of: (left) the number of tasks for fixed 10; (middle) the
number of training samples n on a test task for fixed m = 1K; (right) both m and n.
B Missing Proofs of Section
The following Lemmas and Theorems are used for proving Theorem 3.1.
Lemma B.1 (Bounded difference//cciiamnid' inequality). Consider function of indepen- dent random variables 21,-.., En that take their value in 2. Suppose that f satisfies the bounded differences property, namely, for any I...., n and any 2.,...; En, o E 2, it holds that
S(aI,..., =n) [( ... 1- 2/1 Z44 2n) S 8.
Then we have for any p 2 2,
[2 2n) - E (2 z0)1pp s 2/mp3.
Theorem B.2 (Marcinkiewicz- Zyymuud's inequality Ren and Liang [2001]). Let Ti,,.., be independent centered random variables with a finite p-th moment for 2 2. Then
Σ
<3v 2np
15

---

Theorem B.3. Let Z = (Zi..... Zn) be vector of independent random variables each taking values in Z. Let Z = (Zi.... -mm be vector of independent random vectors each taking values in Z". Let 9j. (2")²² n -> IR be some functions such that the following holds for any E [n],] E [m]]
(1).
M a.S.,
(2). E 19.. (Z,
0 a.s.,
(3). Is.a has a bounded difference 33rm w.r.t. all variables except the (i, i)-th variable.
Then we have
I3.e (2 Z) 2 mn3 log (mn) M /mn.
Proof of Theorem B.3. The proof is extension of [Bousquet et al., 2020, Theorem 4]. Without loss of generality, we suppose that 2h, 2". Otherwise, we add extra functions that equal to zero. Consider sequence of partitions Co..... Cs with Co = {{i} : E [n]]. Ck [m]}, and to get Cj from Ci+1 we split each subset into Ci+1 into two equal parts. We have
Co = (0)) ... {2 Ci = (11,2) ..... {2t 1,2*]] Ca {{1....,,*)]
2*1]
By construction, we have |C| 2 and |C| = 2 for each C E Ct. For each i E [n] and I = O....,k k, denote by (i) E G the only set from C that contains i. In particular, (i) = {i} and (i) = [n]]
Similarly, we consider a sequence of partitions E,...., E, with & = {b) : jE [m]], & = {m]} and to get &g from E9+1 we split each subset in Eg+1 into two equal parts. We have
Eo = {{1) (2")) & = {(1, 2) f3, 4] ,..... (2" - 1,2" &, = ((1,...,2"')
By construction, we have | - and | 2a for each E' Eg. For each j [m] and q 0. ...... .T, denote by (j) E the only set from &, that contains j. In particular, E (j) {j) and (j) [m]]
For each i E [m]],j E [m]] and every 1 = ......k. = 0, ,,....,, consider the random variables
0 = (m/)),m))) (m))
i.e. conditioned on 7,j, 7 and all the vectors that are not the same set as Z,j in the partition E and all the variables that are not in the same set as z; in the partition C,. In particular, 9 = 9j. o Esgg, zz) We can write telescopic sum as follows:
k-1 1
45 - Elgg, Zz 2:]
2.0 Σ
0+10 Dj.
+
93
rd+1 93.4
7=0
1=0
and the total sum of interest satisfies by the triangle inequality
k-1
F5.r
<
E 1 2 2.]
+ +
0+1.0
r1+1 93
q=u
Since
E E[gg,a 2:]l
$ M and E E [E
2 z.))
by applying McDiarmid inequality in
Lemma 1. we have
E Lg 12,
2mmMM.
(2)
16

---

We observe that
93
1+1++1
(z 4 (m)) 2w)
=E E 93.
1 (Z (m] Zi, 2(x)) (0((c++(())
(The expectation take w.r.t the variable Zg, (')((i)(C(
(Z Am] 74, 7x, (i) M, (The expectation take w.r.t the variable Ze, $ E (E++
mm]
As function 0j.1 preserves the bounded differences property, if we apply McDiarmid's inequality conditioned on 7,j. 7 [m]]LE 74 (H)) we obtain uniform bound
4.0 03.3 1.0
(7 7 mi) mm) 24 (n)oo))) S 2/24+13
r/41 (z,, (miiEE>)) (M)CUA())) S 2V2 [9/1
-
as there are 2 indices in CI+1 (i) and indices in EV+ (j)
Now we focus EYEE. Eieco 9j.i 9j. 1,0 for E E Ey and ΣJEE Eiecy 931 9js C, respectively. Since 9j.0 9j. terms are independent and zero mean conditioned on Ro))) Applying Theorem B.2, we have
r.41 for C' 1+1,0 for E E9 C depends on Zj, Zmm] (m(j) Zi, (p)) the
Σ JE SEC
Σ
Ij.
a
Ij
9,0,0
(Zmm)x
93. - 93 02.11002 |
36
29
Σ
(m)))
2
JEE'
IECO
Integrating with respect to (2/m] and using
9+1.
S 2V 20-1 we have
ΣΣ iECO
933
I 6v x 2 3 12V2- 298.
JEFV
Applying triangle incquality over all sets C E Co, E E Eg gives us that
0+1.0 Σ 3/10
Σ
93 9),4
9110
9j,5
/E(m)
EC SE
22 12V2-122 2-93 = 12
Similarly, 93 - 9js for j E", E",
E C depends on 2,, Ci 1()), the terms are independent and zero mean conditioned on 4n]] 10)) Applying Theorem B.2, we have
r.1+
Σ Σ
9 035
rl 0/111
(zm))or)
JEE IEC!
< 36 20+r
244r
JEE
FE
Integrating with respect to (zr))(r) and using
rd
r.41
22/2++13, we have
Σ ΣΣ 9j
rd+1
6V x 2V 12v2 2
jEE iec
17

---

Applying triangle inequality over all sets C³ E E,,, E" E & gives us that
ΣE rd+1 93,
Σ
Σ
rd+1
93.6
JElm sEin]
B'EE,,C'E,, JEB'
s 2 . $ 12V2-22442
Recall that 2* 2n, 2 < 2m due to the possible extension the sample. Therefore we have
m
n
1
93.5
2+10
93
93
I 48 11882mm.33300 (m)7+ [log (n)])
2 mn log (mn)
Combined with Equation (2) get the required bound.
We now restate and prove Theorem 3.1.
Theorem 3.1. Consider a meta-learning problem for some M-bounded loss function and task distribution μ.. Let S be meta-sample consisting of training samples tasks each of size and let S ~ 'D be a sample of size n on a previously unseen task D ~ Then, for any 3-uniformly meta-stable learning algorithm A, have that with probability 1 6,
L(A(S), p) & L(A(S) + 3 log (mn) log (1/8) + M /loo (1/8) (mm).
Proof of Theorem 3.1. order make use of Theorem B.3, we consider the following functions:
9j. 9j.i (Z, Z) (s) Dyr DD, ( z4)
By the definition of uniform meta stability, we can write the following decomposition:
mn (I(A(S),,) T(A(S)))))
1o, ((11)))))).)))
E (5 E B(S), -
Dmr
Djnup
((A(S) (()S)))))))))))))((S(s))s)))))))
(A(S)))
RR
E
((s Be (S)
+mm3
Dmn
Djngs
m
mn3
95
Sm, Zi...., 2 zn] 2M a.s. for i E [n].] E [m]. Applying Theorem B.3 as well as [Bousquet and Elisseeff, 2002, Lemma achieves the results.
Moreover, we have
0 and |g <
Theorem 3.2 can be directly proved by the definition of uniform meta-stability.
18

---

Theorem 3.2. Let be an underlying task distribution. Given meta- meta-sample S, test task D ~ and D", for any B an--averge-rrplace-ono paapllac-ooe-mmt-stttieeee stale meta-learning algorithm A, we have that
(py (")",,,, (LAAS)) - ())
Proof of Theorem 3.2. Since and are both drawn i.i.d. from D, and S and Sj are both drawn Li.d. from μ4, have
[s-] -P ~ Bo..
= =Bs B (8)) (P)) ((
BB 18 2D (D) (L
((
as well as
Bg (D)) (D (P)
((A(S)())).s))
= =E s- m "P)
-ym j~U[m) [L(A(S)(S)),S.,)
1=ر (S) =B;
", " (1wp::/:........uuuooooooooo0aa0
As result, we have
(L( E [D (D,1"") ((A(S)))))))))))())))))()))))I L(A(S),
< 8
(By definition of -or-wweage-ppplccccooe-mctaaaaaa
C Missing Proofs of Section 4.1
Lemma C.1 (Shaley-Shwarts and Ben-David [2014]). Given S and S(0,, for a fixed w, define u(w, S) and u(w, (@w is achieved via Algo. 1 with Option RERM. Then / is convex, G-Lipschitz, we have sups,ie[M] |lu(w, S) - u(w, s()) S 4G If f convex and H-smooth (H s An) ) we have
An
[u([ 8) uww,St s(o)]| <
An
Lemma 4.1. Assume that the loss function l' is convex and G-Lipschitz loss. Let S, S6) denote neighboring meta-samples and S, g( the neighboring samples on test task. Then, the following holds for Algorithm with RERM for task speeific learning (i.e., Option for Algorithm 2) VT 2
((() ((S)))(S()) I
G 2G An
sup J,m
Am
Further, if is convex, M-bounded and H/-mmooth, then setting À >> H, 7 S J. have VT 2
2/2HM
4V2HM
[(())()) A(S 2 H 2An H (1+1))
sup S.S.jE(m))iE(()
Proof of Lemma 4.1. We slightly abuse the notation, at iteration f, define w, = A(S), w/ A(S(1)). Given 1T define u(WT+1.S) A(S)( u ((W (S())
first consider the setting where the loss is convex, G-Lipschitz. Recall that Es(u, w) L(u, + à I|u 2| If is convex, then Fs w) is >-strongly-convex w.r. u. Define u(w,S) argmingew (u, w), u(w' S) = argmin Fs(u, w'). We have the following:
Fs(u(w', (S), w) Fs(u(w, S), w) 2 A |[u(w, S) u(w', S)
Fs(u(w, S), w') - Fs(u(w', (S, w') 2 A ||u(w, S) S)l"
19

---

Sum the above gives us that
2A [u(,, 5) - u(w',
S Fs(u(w' ,S, w) Fs(u(w, w) - Fs((((,, S), w) - -ssu((' (s(u(w")),,')
A (lu(Ww, ,8) -w]=- | - [0]== (u((w,, 8) -w'12 |ll(ww,)) -w'')
w'll))
2
(u( - SS), w - -w)
S A |lu(w, u(w', s)]l ||w w'll
This gives us that
|u(w, S) ulw', SS]l S 1 ||w www--l---
w'll
(3)
Similarly, define u(w', .S' argmingew Fss (u, w'), we have
Fs(u(w', S'), w) Fus((w, 8), w) 2 > |lu(w, S) w'), (u S), w)) (u-(ww S'), w/) 2 A [lu(w, S) - (uw'''')l"
u(w 88)1
Sum the above gives us that
2A ||u(w, S) - u(w.s')
S FF((uww',S) w) F - - 88), w')
(u
-
I ((U("')''),s) ((u(w, S) I.((w, S), S') ((u(w',''),
A [lu(w' S' - w/2 |u((w, 8) - w/ + |u(w, S) - w/1 ||u(w' -ass'--wil -w])) < 2G (lu uww u + A (u(w, 5) - -u(w' w w')
+ 2
(E is G-Lipschitz)
- -w'l 2G [|u(w, - uww. || + A (lu(w, 8) - u(w', s')ll ||w-
This gives us that
- 2 1
G
1 +
(4)
x
Finally, at iteration f, we have
W. - >> We 1 Σ u(w., Sj)
||we+1 - - <
- w/ +1
w/ u( u(w St)
(Projection is non-expansive)
1
m
(1 >>> - w/) + 7d
(u(we, - -u(w',
=
m
j=1
m 1
< (1 - (1)) l/w, - will + 72
|| - w/ll + m
2
||w, - w/1l + 5
m7 2
(Equation (3), (4)
(1 T> || will + 7G
71
2
m
Choose 7 S X
1 Vt. Rearrange gives us that
W1+1 - W
- |w/-w/l
G
1
<
(1 (1-2\/2)(t] (1 (1- 72/2)
m (1
-
7
Note that at initialization when we have //wr will Telescoping from to T
WT4+ - w
G T
1
(1 (1->\/2)*
(1
72
20

---

Calculate gives us that
2G
||TT+1- - W
Ann
Similarly, define u(Wr+1, S) = grw Es(u, w/+1), (00) argmingew Fis (u, w/y), have
((r)))(+))))))))))).)))))))))))) - -F Fs( wr+1) 2 [((Wr+,5)) - S( stt) / Fs(u(WT+1, S(D), wr+1)
Fgl (u(WT+1, w/-1) Fss (u(WS+11 w34+1) 21 x U(WT+1,8) -uW ((1))
Sum the above gives us that
2A - //00
-
$ FFs(u(W(+1:: ((0) WT+1) Fu
+ Fst (u(W wh++) - ( (u(WT+1,)0))) w(+1)
= = ,( - S) - (u(W)
(0)) ||
+ (1) 2 | (() -W4+1 2
< U(WT+I:5) - u( -
2G
|(o)| ( + +>(u(WT+1,SH) u( 5 WT+1 - w/+1) (E G-Lipschitz)
2G <
[u(Wr+1.)) u( u(w 1( |()) + [u(rr1,5)) u(WT+1, |Wr+1 w
n
This gives us that
[u(WTH,))) - u(W
||
S ||r41 - wr+1ll +
2G
S
G
+
2G
(5)
An
Xm
An
We now consider the surrogate loss is convex, non-negative and H-smooth. Note that such loss also self-bounded. From similar argument, we have
|[-ww| () u(w' < -
Moreover,
2\ S) - u(w'
S Fs(u((', (e((u w) - Fs( w) + (u( (w) (s S'), w')
L(u(w',
((u(w",''),s) SS),,) - L[u(w, S) (), (u(wwwu')).a
+ A
2 (lu(w'.5') w/ |u[w w// S) - -lu((w - -w'l²)
<
S| |u(w/00 (5) u (ww, S)
(l is H Hmsoohh)
+ S) - uw w- w')
(VV2HL(((w.)).) S),5) + 22HL(u( S'), (u(w','') u(w, S)ll
+ H Hl(luu' S') u(w, S)1l + /u((w, - u(w',)) ||w - wwwl||
(l is H-smooth)
21

---

which is equivalent as
(HH,, + /2HL(u(W' S'',,")) M// - w'll ( H)
[u(w, S) S
2A H
V2H
(VI(u(w, S) + L(u(w', (1) + l|ww-w/l w/l (6)
X
Finally, at iteration 4, we have
We+1 We+1ll
u(we, (WW,::s)) 5i)
m
1 m
x
We 7d
We Σ j=1
w/ + +-2 w/
Σ u( Sj) j=1
m
m
(Projection is non-expansive)
(->>)( w/) +71
(u(we, Sy) - u(w,, s(W).,;)))
j=1
11 m 11-11
< (1->A) liwe will
| - ww'l
2
1
V2H
[[u(ww (I Sy). + v [[u((W,))).8)) + l|we - w'll
+ m x
(Equation (3), (6))
m + 1 71)
l| ||w:-w// will 7V2H
(VILU(w.. Sy), (0)1,))+((((()())) ())
2m
m
Telescope gives us that
2m 72) T-4 ( (VIlu(w,, ([ (
[TT+ WT++|1
m
m
4v 2HM
X(m + 1)
where the last line holds we consider M M-bounded loss. Otherwise, we have
2/2H
(1 (Wmay ((
|WT+1 - WTHllls A(m +
+ max Lax (8)
[E(T]
Therefore, we have
21 [u(,,)) 5) - u(w',
S Fs(u(w',,St )(()), w) - FF(u( w, S). w) S) + Fst (s (), w') - (u S(0)), w')
T(u(w', -[(uww,)())) )) I(u(w, S) + L(u(w, S), T((uww, 180)
+ A (Iu(ww (()) w| |lu(w, 8) w/ ()(w, - 5 ((u(w', ((()) )²) l(u(w', s((()))))))) - S),z' Clu(w', e(u(w')))zz)) ,8),z))
-|u((w 8(0) w/ w(1²)
X (u(w, - u(w', S()))))) w w-w w)
n HHH(uu(.SS).t 2H(( ||u[w' ul(. S)
1
+ u(w ((W, u(w, 5) + +A/lu(w, S) (llpww)))-www-.6 [|////ww] w'll
(l is H-smooth
22

---

Rearrange gives us,
[uww,S)-
2Am H (V2He(u(w,S),z) 22HE(u(W' ((H())())(()))
1
An
l|w-w'l w'll
(9)
2An H
Plug in WT+1 and w/++1 gives that
2V2HM
4V2HM
U( u(W
s(n)
2An H 2An H (m+1)
If we apply Lemma 4.1 and Lemma C.I with Theorem 2.2, we have the following theorem. Theorem C.2. The following holds for Algorithm 1 with step-size 7 I X on a given meta-sample S,
and RERM for task-specific learning (i.e., Option 1 for Algorithm 2), for all T 1:
1. For convex, M-bounded, and G-Lipschitz loss functions, with probability at least - 5
G²
M
G²
L(A(S). S L(A(S), S) +
log (m) log (1/8) + Vlog (1/6) + An
Amn
Vm
2. For convex, M-bounded, and H-smooth loss functions (H S X), with probability at least 5
HM
M
HM
& ( S) (m + 1)A
log (m) log (1/6) + log (1/6) + An
Proof of Theorem C.2. We slightly abuse the notation, iteration t, define we A()), w/ A(S61), u(WT+1, = u($)) (()))) Apply Lemma 4.1 gives that ((A(S)(S), 8) I(A(S()) = ((u(WT+1,3)) [ S),
< G ||l(WT++, - SW
(G-Lipschitz)
|WT+ w
(Equation (3))
2
2
Am
Apply Lemma C.1 gives us that
- ((A(S)()())))) |(A1))())))-(((()))))))))))
()) -((u(wT+1, S()), 2)
I [ -u(-uuuww) u(Wr+1, s(3)
4G2
An
Apply Theorem 2.2 with 3' =
B
1C2
achieves the results.
Am
An
Similarly, if the loss is M-bounded, convex, non-negative and H-smooth, we have
S) - ((A(S)))()))
= -
H
S V2 8), 8) (| |u
u(w 8) |Iu(wr+,,)) S)
(1 is H H-soohhh)
[T++1 -or--Wrrh wr+il + H
V2HM 5
|WT1 w1
(Equation (7))
4HM
4H2M
(m + 1)A
(m (m 1)2
8HM
(A 2 H)
(m + 1)X
23

---

Apply Lemma C.I gives us that
((A(S)(S)) 2) - ((A(S)()
[(u(wr+1,,)::) -a::)-((wwww) 8(0))
H 2 S (2 | [(WT++, - u( s s00)
(W - 1 ,(00)
8HM
16H
Xn
X2n2
24HM
(A H)
An
Apply Theorem 2.2 with 3'
8HM 24HM (m+1]XX An
achieves the results.
1 given meta-sample S, Theorem 4.2. The following holds for Algorithm with step-size S I and RERM for task-specific learning (i.c., Option for Algorithm 2), for all T 2 1:
1. For convex, M-bounded, and G-Lipschitz loss functions, with probability at least - 5
G² G²
log (mm) log (1/5) M Mylog log (1/8) Vmn
I(A(S).)) ((A(S)
An
Am/
2. For convex, M-bounded, and H-smooth loss functions (H S X), with probability at least 5
LLA(S).)))L(((())5)))) (
(2n (pm-)) - 1)X
HM
HM (m + 1)A
log (mm) log (1/6)+ M (1/6)
Vmn
Proof of Theorem 4.2. We slightly abuse the notation, at iteration define w, A(S), w/ A(S u(WT+1, ((S) +1 8(0) (88)) For l to be convex and G- Lipschitz, applying Lemma 4.1 gives us that
((A())())) (((
((u((w++:)))2) - (( S(0),)
$ G u( - u(w u(w u(W
G Am
202
+
Xn
Further apply Theorem 3.1 gives us the result. For f to be convex, M boundedd and H-smooth, we have
- ((44))())))-(((((())))))))))) 2)
((uu(w++,, ((u(w/ ((u(W/+1:00 S(0))
S 22HH(U(WTHI,.) S), ( (((WT+11
- uWW St:)
||| + Ju(TT+1:)) - -u(W/++1 s(ii
H
2
2/2HM + 2An - И (m 11)
4V2HM
H
222HM
4V2HM
V2HM
2An -
2An
2An 11 (m+
4HM
8HM
8H2M
16H²
(m + 1)X + (2n- - 1)
(2n- 1)X
(m + 1)
12HM
24HM
(H X)
(2n 1)x
(m + 1)A
Apply Theorem 3.1 gives the results.
24

---

Lemma 4.3. Assume that the loss function is convex, G-Lipschitz and H H-smooth. Let S, S denote neighboring meta-samples and S, ( the neighboring samples on a test task. Then the following holds for Algorithm with GD for task-specific learning (i.e., Option 2 for Algorithm 2) with 17 S TF42X
for all T' 2 1 as long as we set 7 S X
[(() - A(S))) ((0))
4eG
2G
sup 8, J.
Am +
An
Proof of Lemma 4.3. We slightly abuse the notation, at iteration I, define w, = A(S), w/ A(SO1), U(WT+1, S) = ((S) (())) ((8)) Recall that (s, w) L(u,S) |u -u-wa w/p. If l is convex, then Fs(u, w) is X-strongly-convex w.r.t u. If f is H H-smooth, then
(V - VL(,, > / [VL(u,))- - VL(v,S)1
Given S, S" for any w, w. we have
| ju (w, (S - u u s')
$ (W uk (w', 17 (VLL(u()(w,))) S). + > (ul()(w w)
(Projection is non-expansive)
- (' > (u(t) -w))))
w|)||
<1 u - ( sS) + n1 ||w- w'l 22/
Given S, for any w, w', we have
(((+))( (w. 8)= - (++ 1) (w',))
s (k) S) - u (w'
(Projection is non-expansive)
(k) (w. (w, (,,,) (w).)))-))VV((/000)0 S), (, () w)) (w)
-
(0) (w) (S- - u ( (w (W + 20(W- w)
(w .))
wlll + ([00 -
w//// S
11 ( (S)) (w,)) () .s) 1²) 1/2
+ (I (a- 2n)r [ _
wll Mllny
( (W.S), 1/2
+ {(1 n/2 27/(1 - - (inn [VT - (w(
(I. is H-smooth, 11 5 3
25

---

5 s1-
(ul)))|u(()ww (w)) ( s] + Xn) llw w'll
(10)
Combine the above two cases gives us that
(w, S,) -u( u((+t) s3)s
1
m72
((() (w, S2) ( (w, (w. + _ (
- (w
(w, - //4) (w', 8}) + +\7 /|w wwww--1--- 2 m
s (1 Xn)
m j=1
m
Given We, W/, when k- = L, (w,, us that
we, u. ST) =u')(w' w/- Telescoping gives
1 m m
Σ
(wr) - - ((() /| S (1 + (1 - ->n))= l|w: - will + Am
2G
2G
S <21|w, - w'll +
(11)
Am
Finally, at iteration 1, we have
||r+11
W'+1ll ||
m
< W1 -
Wx
(w,, 83)
-w(+>d W/
(k) (w/z ST)
m
K
==1
(Projection is non-expansive)
K
(1 1--7)[(w--- w!) + 7d
1
(1 (wi, u(()(w(,
K
,=1
k=1
< (1 - (1-7A) l|w: will + >7
(21lw=
w'll +
2G
(Equation (11))
Am
2
= (1 + 7A) /|w, - wwll +
m
Note that W1 = w1 =0. Choosing 7 S xt. and telescoping gives us that
|WT+| - W S 1 + (1+7) l/w, - -w'll +
2G
2eG
(12)
mXT
Amn
where the inequality holds because (1+ + T)T= I e. Similarly, we have (0)))(((+))0000
[++1 (w S) - [++ ((++)(w' s(3)
< 1 (., S) (8) (w') - 7 (V(VLuu
()) + > (w.)) (w,) (x))))>)(((( -w) w)
(Projection is non-expansive)
- VV((u()('' (W/ -
- -w))
S <ll// - [|/l |||+| (1- -))) (u())(w. - ww ((T))
+1 (w.)) (s Vl(u (w (V (W.))) 8))
26

---

+1 V (w', (L ) ((11))
1l'l #|/ + 2Gh +
(1--1)) m22)
|| Vil
(w', ( )
n
VL((u VV (()) (
1/2
+1 (
-
w|ll + 2GM + (1 (1 (1
- - s(ii\ ((
S
1| M////s
1/2
+ *(12 12 211(1 ( ((ii
[I(u
Vi(u (), S(i))) /?2
H
(L is H -mooohh, 75
$ (1 A1- | | (w, S) (w',
+ +nd l|w -wll + 2Gn
(13)
Therefore we have Vk E [K - 1).
2G
uu (1++ (W)) s (1 (1=+(-)n)*-)) || 1 w/ +
An
= - ( 1 (W = W/++ plug in Equation (12), we have As
K
(W
1
(k)
(
1:: StO)
K
1
|WT+| W + 2G
S min
2, +
Anj
An
2eG +
2G
$ min
2, 2,1+
Am
An
4eG
2G
+
Am
An
The following theorem can be derived via Theorem 2.2 and Lemma 4.3.
Theorem C.3. Consider a meta-learning problem with convex, MM-bounded, G-Lipschitz and H- smooth loss function. Then, after T iterations of Algorithm with 7 S x on given sata-sample S, and GD for task-specific learning (i.c., Option 2 for Algorithm 2) with 1 H42x we have with probability at least 1 8,
G2
M
G2 An
I(A(S).)) & L(A(S),
log (m) log (1/5) Am
v log (1/8) +
Vm
Proof of Theorem C.3. We slightly abuse the notation, at iteration I, define w. A(S), w/: 800) (())) If the loss is M -bbunded, A(S(I),, (KT+1, (()) u (K
27

---

convex and G-Lipschitz, apply Equation (10) gives us
- ((A(S())
[[uu S), L( 1) I, S),
SG [1( (WT+1,, - u (
(G-Lipschitz)
2 G (1 - Xn) |u( (WI+1 - u u( (wT++11 53 >//l/ww ||/lwr+1-a w1llll
(Equation (10))
5 G ||++ w/441ll
2e0
(Equation (12))
Amn
Given S, S,)() For any w, by Equation (13), for all k E [K< - 1]. we have
(w (w,
2G + (1- (w, (w.
2G An (Telescope)
Therefore, we have
((A(5)(()22)-(((((((()))
1 K
K
(
(WT+1,
-1
(k) (WT+1, (WT+1,
K
K
k=1
k=1
K
K
<
G
u
(k)
(WT+1: S)
(1)
(WT41, S(9)
K
K
k=
k
2G
An
Apply Theorem 2.2 with 3 =
2cC Am
with 3 = 2C
An gives us the result.
Theorem 4.4. Assume that the loss function is convex, M M-bounded, G-Lipschitz and H-smooth. Suppose we run Algorithm for T iterations with y S xт on given meta meta-ssmple S, and GD for task-specific learning (Option 2, Algorithm 2) with 1) S # Then, with probability at least 8,
G2 G² )n) Am
M /og (1/5)
L(A(S), & ())
log (mn) log (1/5)+
Vmn
Proof of Theorem 4.4. We denote We A(S), w/ A(S))), u(WT+1. ASS) N(WT+1, (SS))) For l be convex and G-Lipschitz, applying Lemma 4.3 gives us that
((A(S)())))) ((A(S))
1 K
1
(
-1 (WT+1,
u(
(w/ W Sti))
K
K
k=1
K
<
G
(WT+1,
(8)
( 1011
K
K
k=1
k=1
1
GrG²
202
min
2
XnK
Am
An"
Further apply Theorem 3.1 gives us the result.
28

---

D Missing Proofs of Section 4.2
We start with proposition that provide some equivalent characterizations of weak convexity.
Proposition D.1 (Proposition 2.1 in Davis and Grimmer [2019]). Suppose f: IR" + R U foo) is closed function and p > 0, then the following are equivalent:
1. For any W1 E R f() ||- will is convex.
2. For any W1, W2 E Rd with g(wi) E @w(w)), we have
f(w2) f(w1) + (g(w1), w2 w1) - ||w2 wwll?
3. For any W1, W2 E 12 and A > 0,
f(Aw1 + (1 A)w2) S Xf(w1) + (1 (1)()) + pA(1 -
|| w2ll
2
Lemma D.2. [Bassily et al. [2020]] Given S and S(1), for fixed w, consider u(w, S) and u(w, st are achieved via Algo. with gradient descent for iterations. Then if l convex and G-L.ipschitz have suPrg[m]
K 1k=1 (*) (w, (w. K Σ (w.
K
4GKg 4GnyKK
Below we provide our key Lemma D.3 for the stability analysis.
Lemma D.3. Consider meta-learning problem with p-weakly convex and G-Lipschitz. loss function. Let S, S(i denote neighboring meta-samples and S, S(() the neighboring samples on test task. Then, after T iterations of Algorithm 1 with y I xT A 2 2p, and GD for task-specific learning (i.e.,
Option 2 for Algorithm 2) with v) S X
2eG
sup S.jE(m]
WT+1 WT41 S 2eG
+
Am
Proof of Lemma D.3. l is p p-weakly convex, then from Proposition D.1 we have that (Vl(u) V((v),u- v) 2 -p p u|u
v/12 Vu, v RRd Rd
Given S and S', for any and w', have
Vk E [ - 1], | (((tt)(ww (w, (k+1) (w',
s (w, - (w', [L(I S), + A (w) -w)
(Projection is non-expansive)
(L(u ( (W'S'',, - > (u(t)("'.')) S') - -w)
(1 m/1) | - w -
m7d 7//l wll 27G
26
$ (1+ (1 m1)att | wll +
1
(Telescope, (I) SW = w, (w' w.)
And therefore
K
K Σ
||w - w'll + 2G
(4) (w. S)
< min 2,1 AnK (1) ( S')
K
K
A
We now focus on the situation where we give S and S' with fix w. For simplicity, we define
5, = ||lu(() (w,, S) (*()) (w/,, S) Note that 8, = l|w, will- We have
6x+1 = [u(++)) ((++)) S)
29

---

1 (w)) -1 ()
S)
(Projection is non-expansive)
- -VL.u( - (u()) -w:) ww)
S An - wcll+ (1- n2) -)
- - -w/l + As
where we define
A - (
We have that
A = (1 - 02 + C2
- 2m(11 - 12)( (1( (w) (w/, S), (W (w),))))) 5),
< (1 22) + 222 + +nn(11 - m
(l p-weakly convex)
$ (1 n G²²
in 1 2 2p)
Therefore, we have
2 + 22 |we wwe-w/ll w/ll² -2270002 l|
will S 4 s (1 m2)) G2
(14)
Rearrange it gives us that
82 22172 |w will?
2Am l|w w6 8k+1
82
Gr²G²
+
(1 - 77) (1-72)*+1 K+I (1 - n2) k+1
(1 - 172) m/2)
k+1
(1 - 171)a
(1- (1-17)**1 x
Telescoping from 1s 1 to K gives us that
8
K
22 |/= w/ll
2
K 2Am 2An - -w,l 0x+1
K
4n2
(1- 72) K+I
(1 - {7))
K+1
(1-n2) -nn))a+1
(1 - 1/2) K+I km
kml
km
Thus
K
52 K+ + 22172 l/w, -w'l1 Σ
(1
22n llw, -
aoll::-wlll will ww:l 5x+1
4n10²
K-1
S A + 22m l/w, - will
6x+1 - )²))
4n
K
X + 2Am(1 7/) ||W: - w'll
5a(1 1//))<>
(15)
A=1
Now we start proving the following bound by induction:
5x $ 2/
will + 2G V 11
7-
30

---

This claim holds when h- = 1. For the inductive step, we assume it holds for some k E [K] and prove the result for k + 1. We consider the following two cases. ox++ S ma] dg. induction automatically holds. Otherwise, 0k+1 > max ds. Applying Equation (15) gives us that
82 + 22 l| - |w: Σ 1=1
2Am llw, w'll 0x+1 17)
4n16²
+ +22m(1 -))) l|we -w'll Σ
8u (1 -n)
5=1
2 4n + 2Am(1 - 11) lwe - ww'l- 0x+1
Σ
(1 - -))))
==1
which is equivalent to
&
62+1 + x-2217211 (/// - ww'l Σ
(1 77))a²
5=1
4n/G² < X
k
+ 2Ar l|w- wollda+1
1 (1 n11)
Σ (1 1//
j=l
Rearrange gives us that
&
6k+1 - 20///w -
1+ (1-1-17) - 1721/ Σ (1 - -n)))=
j=1
< Xx loll - will 1+ (1-11)) Σ (1 -))) ))
4n
Iww - w/ll? (1 - - -1)))tt2
Therefore, we have
Vk E [K 1] (((+t)(w., - (
1+ |+ (1 111) Σ (1 n2) m2))-)
< 2G x +2 |an \0//lwe- - will
==1
< 2 2| - will + 2G/// /
And therefore
1 K
(k) (Wr, 5)
1
Σ
u (k) (k) 5)
<2| -wlll + +2G 7
71
(16)
K
k=1
As result,
|Wi+1 - w241 ||
K
K
< W. -
We
1
(+) (w., Si)
-.,+7d W
1
(k)
(W/
88)
K
K k=
1=1
1=1
j=1
(Projection is non-expansive)
= - -11-7) l|w; - will +
Σ
m
K
u (we, S,)
1
Σ
K
(w
K
m
K
k=1
1=1
31

---

Σ (1 - (1-1A) llwe will + m
7)
2 2/|we
will + 2G 2
+ 72
221lw - will + 2G
m
m7
x
2G7
< (1+ [/w - w/ll 2G/V /nd n
m
Telescoping gives us that
2G
WWT+1-we w/2+2/+ 1 +1+
2GG
+
A
Am
Choosing 7 J X7 gives us that
2G Xm
2eG
|| || - wT+1l - (1 (1+7)) 7)
T 2G
2eG
Am
We remark that if we consider convex and non-smooth loss function by setting P = 0, then follow a similar argument, Equation (14) can be replaced by
+ + X²11² ||w,- w'll* 22 ||w, will s A (1
m)) G
And therefore Equation (16) can be replaced by
[ Sw u 1 (w', S)
h (1 1//)
s 2G X 2
An l|w, will
Σ (1 1))22k22)
z=1
$ 2
llw, w'll + =20 /²"
22/lw: w/ll + 2G /
6n 11
and the rest follows.
Theorem D.4. Consider meta-learning problem with p-weakly convex, M-bounded, G-Lipschitz loss function. Then, after T' iterations of Algorithm I with y S x A 2 2p, and GD for task-specific
learning (i.e., Option 2 for Algorithm 2) with 17 S x. we have with probability at least 1 - 5,
G2
M
G2 +GInIK
I( p) ()) + G²
log (m) log (1/0)
v log (1/8)+
Am
Vm
An
By setting 7) 1 X we have
G
2²
M
G G
log (m) log (1/8)+ +
log (1/8)+
WV
Xm
vm
An A/K
Proof of Theorem D.4. If the loss is M M-bounded and G-Lipschitz, apply Lemma D.3 gives us L(A - L L(A ((A(S (S))
L
(N) (WTH)
L
Σ
(2) (w/ (wT+))))
K
K
k=
k=
K
S
G
(1) (W K
(kk (1))(WT++ (w'++1:8) S)
(G-Lipschitz)
k=1
< 2G |WT+1 - wh+ || + 202
11
(Equation (16)
V>
/ /
4eG²
(4eG2 + +2G²)
(Lemma D.3)
Am
1
4eG²
< (4e + 2
(Set 17 S XR
AVK K
Am
32

---

On the other hand, applying Lemma D.2 gives us that
((A(S)(5)) ((A(S) 2) = ((u ((T S), - E(u (1 W
S |u(ktt)(wr.sb - - (KT.
4G + TAG
4G 4G²
(Set 1) S XR)
AvK
Plug back into Theorem 2.2 gives the result.
Lemma 4.5. Assume that the loss function is p-weakly convex and G-Lipschitz. Let S. S denote
neighboring meta-samples and S, S the neighboring samples on a test task. Then the following holds for Algorithm with À 2 2p, and GD for task-specific learning (i.e., Option 2 for Algorithm 2)
with 1y S x. for all T 2 1 as long as we set S XT
A(S())(S())) S (8eG 2G) 7 ((S) (.m
8EG Am +
8G
sup
An
Proof of Lemma 4.5. We slightly abuse the notation, at outer iteration I, define Wi A(S), W/ A(SS)). Given wi, at inner iteration k, define (())(w),)) (S()) We now provide the upper bound on K Ex= u (WT+1, - R E u (WT+1, s()) Recall that if is p-weakly convex, then we have
(SS) (w,,
(Ve(u) - Ve(v), u v) 2 -pllu vIl
We apply similar procedure as Lemma D.3. For simplicity, we define dz [u(t)
(w,, S) - u(()
Note that &1 = ||w, w/ll- We have
ox+1
(k+1) (ws, S) - (x++)) (w),
(k( (WL,,,)) S) ( 5(1)) (w., +1 (u())( ( ww)
- -VL(u(t S()), s(i)) A (u(K) - w:)
< Anllww -olll,-wclll+ (1 - m/11 (u. u (W', ((oss
((ns
= = -wil + As
where we define
A n/2) (w.) ((0)
n 11
We have that
A = (1 - 12)2288 + 222
- 22n(11 - )))(u(*((TT+4.)) (u)) (WT+).) (V S(1))
33

---

= (1 - =11m1))8f + G77²
- 2m(1 - 121 (1) -) S(0), 1I. S)))))/( ,())) ())
21/(1 m/1) (11 8) - 1 (wT+,, ) Ve(u (8) (W'
S(() s(i)),)))
< (1 - 2 + Gn2 + 2n(1 - No)pa + 4Gm(1 17>) 0E
$ (1 (1- m 0n + 4Gn(1 m71)1 6%
(n S 2 2 2p)
Therefore, we have
4G (1))) 0%
02 + X²11 |W,- w(ll 3 -2 l[w, - ww/l S A S
+
n
Rearrange it gives us that
22 W. - will
2Ar
-ww,-w/ll -w: 5x-1
(1 (1-)))*+ k++
(1 - 1-m)))+1
(1 11-1/1 172)
4n7
1G2(1-12108
+ (1 - m/)2+11
(1 n2)*
(1 (1-m))) k+1
Telescoping from h= = 1 to K gives us that
8241
K 2n1 |/ wil? 2
K+I +
(1 - (1-
(1 17)
K
2xm [|w, - will 8k+1
K
4n²
K
4G - 12
+ >
(1- 172)) k+]
k= (1- n1 (1-n2)+tt k+
k=1 n (1 - 112))
1=1
Thus
8/ + 22rp ||w: w/ll Σ6
(1 - m))k=* - 22n -w'll 6x+1
k=1
4nG² X
K-1
8k+1 (1 - =)2)k== 4Gn(1 -2A) K
<
+ 2\n /|we - will
Σ
8x - k-
k=1
4nG2²
+ (2 ())(1-n))]ww: will + 4Gn((1 (V))
K
6k(1 - 1/)
(17)
A
n
k==1
Now we start proving the following bound by induction:
ōk S 2G 2G V / 4 [|w will + 8G(1 - 172)
(18)
An
This claim holds when A = 1. For the inductive step, we assume it holds for some k E [K] and prove the result for k 1. We consider the following two cases. If 6x41 S max,e]s) dg. induction automatically holds. Otherwise, 8k+1 > max 5g. Applying Equation (17) gives us that
82 + X212 liwe - w/ll "0 (1- n2) - -22n l|we will 6x+1
5=1
4n,2 s A
+ (2x1(1 (22n(1-nA)llve) (//11-7A))11 I1we wow w/ll + 4G (G1(1--n))
6k41 Σ (1 n2)a-5
n
j=1
34

---

which is equivalent to
2
6k+1 - 11 -nn)]lw; ww/l Σ 1--)))+++ 4Gn(1 - 771)
(1 - An) A-j
n
1=1
AnG² +
1 1 4Gn(1-10 -11)
Σ
(1 - (1n)
==1
Therefore, we have
& Σ
Sx+152G V A +2 2\n
1=1
+ 4Gm(L1
&
Σ (1 (1-11)}a- 1=1
1 + 1| w'll
8G(1 mp)
2GG V
An
Plug in Lemma D.3 gives that
7 8eG 8G' Am
dx+1 S BeG++2GT
An
Therefore we have
K
(0) (WT+I,
Σ (k)
( (w/ (WT+1
(8eG + 2G)
V 1 SeG
+
8G
Am
An
Moreover, setting 7 = XK gives us that
(4) (WT+1,
Σ
(WT)))
(w)
|=
SeG + 2G
8EG
8G An
K
K
AVK K
Am
Theorem 4.6. Assume that the loss function is p-weakly convex, M-bounded, and G-Lipschitz. 1 xT À 2p meta-sample S, and GD for
Suppose we Algorithm for T iterations with y S
task-specific learning (Option 2, Algorithm 2) with 17 S f. Then, with probability least 1 8.
L(A(S), 1) $ ((A(S),)) + (22
17 X
G
G2
log (mn) log (1/5)+ + M / (1/8)
+
Am
An
/ mn
Proof of Theorem 4.6. For to be G-Lipschitz, applying Lemma 4.1 gives that
((A(S)())))) ((( ((((3)))))))(((((()))))))))
K
K
1
(K) (WT+1,5),2 -1
(k) (w/
(WT+1,
K
K k=1
K
G
(1)
(WT+1,
(k)
(w/ (w1++1,5(1)
K
K
k=
k=1
SeG² 8G2
< (8eG² 202)
11
Am
An"
Plug it back into Theorem 3.1 gives the result.
35

---

Theorem D.5 (Restatement of Theorem 4.7). Assume the loss E is convex and G-Lipschitz. Define uj = argmin, L(,, Vj E [m]. Suppose we run Algorithm 1 with GD for task-specific learning with y = XM to find an algorithm A(S) = MaT+(WW+1,) which is then run on S, for K iterations with step-size S . Then, we have that
+ GDmA ((A(())))) - inf (;) 27(1 27((1-A)j MAjK 2(1-1/A
D2
G2n
+ > A||WT+1 - -|WT++-W||++ +112
n (1-7))(2-1) 171
where 0² == *
K
i uu]? with w as defined in Equation (1). || - w/l 1
j=
8D2 + 1D2
+ m
2D ICG-2AD1 YAK
yAK
2A
wl7. u" S) = argmin.ew [[u S) + 2 ||u-w|?] w|p]. uj = argmin L(,, Vj E [m]. We slightly abuse the notation by defining u (w) A(S) at inner iteration k for given Wy. Then we have
Proof of Theorem D.5. Recall the definition w = -argmmn to Dن min, ((uu; 1 |
a (+tt (w (W..SS) (,), w;]l?
S3) - $ (1 - m/ai) (1) (we, S5) - u;) + (we- - uz) - VL (1)
|Iw (we. -1 (VL(u( (,,,,, (w,)))
()))) 8))))))))) - -u5l1 2
(w,, (we, Sw,, 53) ?
$ (1 - //// | ( (We,, ST) u5 2 = 7 VL (2) (w,, (w Sy) S,) 1| + + l/ - u3]?
+ 21) ///// | (2)) (w.. (3S uz w/ - -;حl + x -ujll
- -2n(1 - 1An
8;), 8,), (w.,
(w., Sj) - uj)
= (a- 1/11 ||(0)) (w., 8T) - ui| + 7 wr - u;ll) +1² VL(u (k) (Wr, S;), |²
+,²²G || - -ujl - -2n(11 - 7>1 VL (4) (wz, Sy). Sy), u (8) (We, SS) u;)
$ ( (we, 83) - -u]l 2
1/1
|| - ujl 1 + 6² + 17 + |w - uill
+ 2 - n7
((a + b)2 < (1+ p)a² + +(1 + 1/p)b² with 12-1A)mA
(1-1Aj²
22n - n2) (w,, (k) (wr, S,) uz)
Rearrange it and telescope it gives us that
L
u (*) (w)))))
S,)
K
1=1
K
(u( (w:, Sy), L(u,,
(Jensen's 's inequality)
1=1
K
(((((()) (1) (we, (W,, (W) -u;)
(Convexity)
|1]]| + G2 + 77 AG
j=1 ΣK= |W - uēll + Iー Σx |w uu31 |
K
2n(1 [7[1-AAA -A)KK" + G2n
D2
2GDmA
A >||w, w|| fww + 2o²
- 1w]- (1- 1/1)
(0² 1 K 1
+
+
2(1 1/a)
1 1- y7
36

---

Follow from [Zhou et al., 2019, Theorem 1I, we now control || - ww] Define u" (we,, Sy) =
argmin, Fs, (u, we) argmin, L(u, S,) + 2/ Ilu well.. We start with the following:
| - w - 1lw We - 77
1
m
K
u (10 (we, ST)
(we,
We
m
==1
k=
2
K
<
W1 w 7i
Ws
1
(8)
m
K
km
m1
< l/w--
w/1
2nd
We
W, W.
u (k) (we, S3)
m
J=1
k=1
1 m
+ +
W1
(wr:
(19)
m
j=1
We now bound the latter two terms separately as follows:
2
m
(8) (Wes S2)
W
m
K
1=1
K
1
u (w(w,, ST) - -u( 85))
W1
u² (we, Sj) +
K
K
j=1
1=1
3=1
k=1
m
2 m
2 2
Wt
(W2, Sj)
(1() - u² uw(,, (wr:
m
K
m
j=1
j=1
k=1
2 m
1
K
(8) ( ST) - u² (w,, Sy)) ||
S
DD2
+
m
K
1=1
k=
as well as
W,-
W,
We
m
1
(k) (w., S3))
m ==1
K
K
1
(w: W, W. - -0---u((u u'(ww,, S,])
m
k=1
K
Wz - の (we, S,) - u² (we,, 5z)
K
1=1
k=1
m
K
W. - w. x (uFs)((((A), m.))
1
llw, - -w|2
-2
2
m
k=1
K
(1(b)) Sw) u² (we, s?)??
(we,,)))
2m
K
K
||,,
2/|
||w,
w/1
(we, Sy) - u² uw( Sp)l Fss, (u, w) is X-strongly convex w.r.t. w)
2
2m
K
j=1
Σ j=1
1
K
(*)) Sy) u" (w,, 5,) sw,,,,,))'' 1
1|w,
2/|2
2m
K
k=1
37

---

where the common term [ulk)(w,, u" nwww, 8y)1| can be controlled as follows:
((tt1) (w,, 5,) u² (we. | ||?
(we, S2) Fs, (w,, w.) u" (w,, Sj) 1
(u(ctt)(w,))))) S5) - u" (we, s,)l /|| - 2n VFs, (u(*) Sj), we), u (w,t)) - u u"(w,, S,))
+ 1? VFs, (u (4) (we. S3), wen
S,), s (1 ) (x+1) (ee, St) - u² (we, Si) 2 +1²² (L(u(t)(w.. (w),,)) + (w,, (Fs, (u, w) is X-strongly convex w.r.t. u)
<11-21/) (w,, u
+ + (PP(++2DD)
D2 + n(G + 2XD)2 $ 4(1 - 2
(Telescoping)
2X
Plug back into Equation (19) gives us that
|e++1 - w1
m
K
(8)) (We, Sy) u² (we: s,)) s,))?²
< |/ w/| 1172-277
27d
Wt
w|
2m
k=
K
+ 8D2 +
2
(8) (w,,, (Wr, ST) u- (We,, (ws,,
m
K
j=1
k=1
K Σ 4(1-2m 2m1-2m)) 1( 2XD)2
$ <1 (1- (1->A) /| WW - -w1 + 7
2
k=1
+ 88D2 + 1 K
8(1 - 211A)* D2 + I/ + +2XD)2
Σ
K
A
k=1
2D
+ n(G ((G+2)D))
4D2
+ nG++XD)3
< <1 (11-7A) We - w/ 2 Krt
(8D2+ 1
nAK
2A
Choosing = + XT
gives us that
|| - w
$ (1 } l|:; - 21
+
2D2
n/(G + 2AD]3
+
8D2 +
4D2
+
1(G + 2XD)²
T
nAK
2X
T
nAK
A
SDD + 4D²
+ [G+2XD]
nAK
2D
(/G + 2AD)²
(Telescope)
T
2A
E Missing Proofs in Section 5
Theorem E.1 (Bennett's inequality). Let T1, .1,..., Fn be independent r.v. with finite variance.
Further assume Jz,- Ex.| I a a.s. for all i. Define S, Dx [2; - E[p,]] and o² Σ E (z+ E[x,))² Then for any t 0.
at の
PS > 1) S exp
where h(u)) (1 + u) log (1 + u)
38

---

Lemma 5.1. Assume that the loss function is p-weakly convex and G- G-Lipschitz. Let S, S denote neighboring meta- samples and S, S() the neighboring samples on test task. Then, with probability at least exp (-7 /m²), the following holds for Algorithm 3 with À 2 2p, and GD for task-
specific learning (i.e.. Option for Algorithm 2) with v S x. for all T 2 1 as long as we set r S XT.
((S) - (55)) s (8cG +
+8cG++2)) 2
SeG 8G
sup S.
Am An
Proof of Lemma 5.1. We slightly abuse the notation, at outer iteration define wt A(S).
w/ A(S())). Given We, at inner iteration k define ( (w,, S) (SS) (w')
(SS))) From a similar argument as Lemma D.3, Ak E [K 1]. we have
(u(kt)(ww (We, S) (u(++)) (1/, 5 2 l|w, w'll 2G
A
| ( - ( (((+)((W..S)))
< 2 f/ will + 2G
?
X
Let us define ri = 1(S,, * Sj.). Note that at every step t, Ea(r)) = 1. Moreover, note that fre :t t [T]] is an independent sequence of Bernoulli random variables. As result,
We+1 - w/+1|l
K
K
<
W1- yt
Wz
u (we, S3t) w/6 7d
W/
1
Σ
(
K
K
k=1
k=1
(Projection is non-expansive)
= -11 - 72) - + 7d
(k) (w,, S5:)
1
Σ
(b) (w)
K
(11 -/--:///ww will + +20 77 +7drr [|w,-w/l++ 2G
-r. -
S (1->>)) [Iv
A
w/1l+ + 2GvVVvVV + 2GyM
(1++ ||; - 2 2Ghr,
Telescoping gives that
T
< 2G / 7 +1++ + 2Gy Σ (1+ (1+ r
|WT+ - 1rr41-w411l
Further taking expectation w.r.t the randomness of the algorithm and gives us that
7 +
2G
Ex [a][wr11-w/ - || s (1 71+
( V
22G
Am
Choosing 7 S 1 X7 gives us that
EA Fa||WT+1- - wr+1ll S (1 /
22G
"1
20
S 2eG
TJ +
2eG
x
Xm
Am
Plug this back into Equation (18) gives us that
EA [K(H))) 8) -)-u((+)))) (K+1) (w/r WT44, |(0)s
s $2G
17
+ 4EA ||w, - -w'l + 8G(1 mTA)
X
An
(8eG + +GG) " SrG
8G
Am +
An
39

---

Setting S 1 We note that for each ry has variance smaller than 1. Define random variable
It (1 + T -r. We have
|x BBrol] (1 + T
1 )²m (re-
B(ro))
S
B|x,]| s (1 + 7 )-1
(1- (1- 1
m
Σ E (c. -(a))
200
1
Tea
m
m
m
Hence by Bennett's inequality Theorem E.I, have
P
Eu+
rr
1
Σ
(1
S eexp
T
T
m²
1=1
Therefore, with probability at least 1 exp
2-1
/m²)
we have
||T+1 - w1+lll s S2G V
+
1
)r
dmπ Σ
2G
1
1 1-1
S
2GG
2eG
T
T
Am
and therefore with probability at least
exp (-T2 e- we have
vk E [K- - 11, (K-))) (WTH) (K+t) (W/H1) ( /|
(or-wwi) w/ll + 8G(L nA)
5 2G x + Nl|w
An
in
8cG 8G
$ (8eG + 2G)
A Am +
An
By triangle inequality, we have with probability at least
- exp (-T2 e²/m²²
K
K
$ (8eG + 20) / s(0)
8cG 8G
(k) (WT41, S)
(k) (w (wFH,,
+ Am +
K
K
An
Proposition 5.2. Given loss function ((.,2) and its adversarial counterpart E(., 2). the following holds: (1) If l is G-Lipschitz (in its first argument), then é is G-Lipschitz. (2) é is not H7 -moothhh even if f is H-smooth. (3) If l is H-smooth in w, then i is H H-weakly convex in w.
Proof of Proposition 5.2. Given W1, W2, define
21 arginax E(W1, 2)
REB(x)
Ż2 argmax ((w2, Z). zz
For the first item, it holds
[(W1,2) - E(W2, 2) = [|0(W), 21) - E(W2, 22)11
max (le(w1, 21) ((W2,22)) ((12,22)).1(((,,2)) (2(w1,22) E(22, 22)1
< G -|
For the second item, the non-smoothness of the adversarial loss has been verified in Xing et al. [2021], Xiao al. [2022]. For the third item, E(W, z) is H1-smooth implies that E(w, z) is /1-weally convex. and further derive that Ê(w, z) is H-weakly convex because
E(w2, 2) l(w2, 22)
2 E(w2, 71)
(By definition of 2,, 22)
2 E(w1, 21) + (g(w1, 21), - -w1)
|lw will?
2
(g(w1. 21) E Ol(w2, ž1), apply Proposition D.I)
= =((w,, 2) + ([(w,, 2), W2 - w.) - L
||w will
(Redefine g(wl,2) 2) E de 2))
2
40

---

NeurIPS Paper Checklist
A. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: We further expand on the claims made in abstract and introduction in Section and 4. The detailed proofs are provided in the Appendix.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made the paper and important assumptions and limitations. A No or NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
It is fine to include aspirational goals as motivation long is clear that these goals are not attained by the paper.
B. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors? Answer: [Yes]
Justification: We list the required assumptions in the statement of each theorems. Several limitations are described together with future work Section 6.
Guidelines:
The answer NA means that the paper has limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create a separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (c.g.. independence assumptions, noiseless settings, model sellsspeciiiationn asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low or images are taken in low lighting. Or speech-to-tex, system might not be used reliably to provide closed captions for online lectures because it fails handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and faimesss.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community, Reviewers will be specifically instructed to not penalize honesty concerning limitations.
C. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
41

---

Answer:
[Yes]
Justification:
All the proofs are provided in the Appendix.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide a short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should complemented by formal proofs provided in appendix supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
D. Experimental Result Reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Answer: [Yes]
Justification: Please Section A in the Appendix.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution be necessary to either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g.. in the case of large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
specific model and empirical evaluation, may
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily new algorithm, the paper should make it clear how to reproduce that algorithm. (b) If the contribution is primarily a new model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with open-source dataset instructions for how construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors welcome describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results.
E. Open access to data and code
42

---

Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, as described in supplemental material?
Question:
Answer: [Yes]
Justification: Please see Section A in the Appendix. The code is provided in the supplemen- tary file.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips cc/
httpc//guiess/ccodeeeeee ceaibmmssssooooooooooooooooooooe cesssonoolioo Policy) for more details.
While encourage the release of code and data, understand that this might not be possible, so "No" an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https: / //nips. cc/
http//uudee//eeeee CCtpes//ooSSubmmeecc cessinnoolccyy for more details.
The authors should provide instructions data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
F. Experimental Setting/Details
Question:
Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification: Please Section A in the Appendix.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, as supplemental material.
G. Experiment Statistical Significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer: [Yes]
Justification: Please see Section A in the Appendix.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi-
dence intervals, statistical significance tests, least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for
example, train/test split, initialization, random drawing of some parameter, or overall with given experimental conditions).
43

---

The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g.. Normally distributed errors).
should be clear whether the error bar is the standard deviation or the standard error of the mean.
It is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables figures symmetric error bars that would yield results that are out of range (c.g. negative emror rates).
If error bars reported in tables plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables the text.
H. Experiments Compute Resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed reproduce the experiments?
Question:
Answer: [Yes]
Justification: Please see Section A in the Appendix.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well as estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that NeurIPS Code of Ethics https: / /nwuriss.s... cc wctppblcc////ccccccccccccctclltt htwpa///eehhcchceeellieleeleeeee
didn't 't make it into the paper).
Code Of Ethics
Question: Does the research conducted in the paper conform, in every respect, with the
Answer: [Yes]
Justification:
The theoretical nature of the results means there are minimal ethical concerns.
Guidelines:
The answer NA means that the authors have reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special cireumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., if there is special consid- eration due to laws or regulations in their jurisdiction).
J. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [Yes]
Justification:
See Section 5.2 and 6.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact or why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
44

---

The conference expects that many papers will be foundational research and not tied particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology being used intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms monitor how system learns from feedback over time, improving the efficiency and accessibility of MI..
K. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification:
The paper poses no such risks.
Guidelines:
The answer NA means that the paper poses such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
L. Lieenses for existing assets
Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper. properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [NA]
Justification: The paper does not use existing assets.
Guidelines:
The answer NA means that the paper does existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (c.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (c.g., website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswi thcode. com com/dataseta has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
45

---

If this information is not available online, the authors are encouraged to reach out to the asset's 's creators.
M. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification: The paper does not release new assets.
Guidelines:
The answer NA means that the paper does not release new assets,
Researchers should communicate the details of the dataset/code/moodl as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
N. Crowdsourcing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification:
The paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsoureing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According the NeurIPS Code of Ethies, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
O. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Question:
Answer: [NA]
Justification: The paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing research with human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurlPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
46


Reviews:
[{"review_id": "z2U3Tokt7A", "reviewer": "Reviewer_S84Y", "summary": "The authors introduce a new notion of stability for meta-learning algorithms and they show how it is possible to bound their generalization gap by their stability property. The new definition of stability measures the sensitivity of the learning algorithm as one replaces both a task in the meta-sample as well as a single training example available for the task at test time. They consider two variants of within-task algorithms – based on regularized empirical risk minimization (RERM) and gradient descent (GD). For meta-learning they employ a gradient descent method. They apply their stability-based analysis to these variants to learning problems with convex, smooth losses and weakly convex, non-smooth losses. Finally, they adapt their results to stochastic and robust variants to inference-time adversarial attacks of the proposed meta-learning algorithms.", "questions": "1. The underline should be removed in the paper.\n\n2. It would be nice to relate Thm. 3.1 to the question about the possibility to get meta-learning rates going as $1/(nm)$, with $n$ the number of within-task points and $m$ the number of tasks.\n\n3. 'Indeed, we show that Theorem 2.2 yields a rate of $O( 1/m + 1/n + \\sqrt{m})$, which is worse for all $n > m$.' Why? Moreover this is the setting less frequent in Meta-learning (where usually one assumes $n << m$). \n\n4. In Thm. 3.2 I expected a term of the form $1/(\\eta m) + 1/(\\lambda n)$, instead of $1/(\\lambda m) + 1/(\\lambda n)$. \n\n5. Please compare more in detail the bound in Thm. 4.7 on the excess risk with those in the reference [A] above.", "limitations": "I do not see any potential negative societal impact of this work.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "1. The introduction of a new meta-learning stability is innovative and alternative.\n\n2. The effort of providing a theoretical analysis on the topic is valuable.\n\n3. The topic is interesting for the venue.", "weaknesses": "1. The method is not new. It coincides with that in [A]\n\n2. The comparison with the literature should be clearer. In particular, I would like to have more details and about the advantages and disadvantages w.r.t. the reference below [B].\n\n[A] Giulia Denevi, Carlo Ciliberto, Riccardo Grazzi, and Massimiliano Pontil. Learning-to-learn stochastic gradient descent with biased regularization. In International Conference on Machine Learning, pages 1566–1575. PMLR, 2019a. \n\n[B] Andreas Maurer and Tommi Jaakkola. 'Algorithmic stability and meta-learning'. Journal of Machine Learning Research, 6(6), 2005.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "W1 / Q5: We never claim we provide a new meta-learning algorithm. Our algorithm is indeed of the same nature as in [r2] and [A]. We now provide a detailed comparison between our result and [A].\n\n- **Different Function Classes Considered.** The function classes considered in [A] are limited to compositions of linear hypothesis classes with convex and closed losses. In contrast, our work considers a broader range of functions, encompassing not only convex, Lipschitz, and smooth functions but also weakly-convex and non-smooth functions.\n\n- **Different Analysis Techniques.** [A] employs a primal-dual formulation of bias regulation ERM due to the simplicity of linear classifier that discussed above. Given our broader range of function classes, we introduce a new definition of stability and use stability arguments to derive generalization bounds.\n\n- **The expected excess risk is different.** The expected excess risk from Theorem 4.7 in our paper is of the form $O(\\frac{1}{\\lambda\\sqrt{K}}+\\frac{1}{\\lambda m}+\\frac{1}{\\lambda n}+\\frac{\\lambda}{T}+\\lambda\\sigma^2),$\nwhere $m$ is the number of tasks, $n$ is the number of samples per task, $K$ is the number of iterations for task-specific algorithm 2 and $T$ is the number of iterations for meta-learning algorithm 1,\n$\\sigma$ is the approximate error that captures the average distance between the optimal task-specific parameters $\\mathrm{u}_j$'s and the optimal estimated meta-parameter $\\mathrm{\\hat w}$. \nMoreover, choosing $K=O(n^2)$ and $\\lambda=O(\\frac{1}{\\sqrt{n}})$, the expected excess risk is \n$O(\\frac{\\sqrt{n}}{m}+\\frac{1}{\\sqrt{n}}+\\frac{1}{T\\sqrt{n}}+\\frac{\\sigma^2}{\\sqrt{n}}),$\nwhich depends on the number of tasks $m$. \nOn the other hand, Algorithm 2 in [A] assumes solving the within-task problem approximately, so there's no within task iteration $K$ involved in the bound. The expected excess risk in [A] is of the form $O(\\frac{Var_m}{\\sqrt{n}}+\\frac{1}{\\sqrt{T}}),$ where $Var_m$ captures the relatedness among the tasks sampled from the task environment. Note that this bound is gained based on a specific choise of $\\lambda$ that depends on $Var_m$, which is unlikely to know ahead in practice.\nMoreover, assuming $Var_m$ is a constant, then this bound is independent of the number of tasks $m$. Therefore, our bound is tighter when $n\\lesssim m$. \n\nW2: We present the main result from [B] as Theorem 2.1 in Sec 2. The advantage of [B] is that it directly leverages the uniform stability argument from single-task learning to meta-learning. [B] considers uniform stability definitions at both the task-sample and meta-sample levels. By applying new tools from [r3], we provide Theorem 2.2, which improves upon Theorem 2.1 under the same definition of uniform stability. \nOn the other hand, our paper introduces a new notion of uniform stability that accounts for changes at both the task-sample and meta-sample levels, specifically designed for meta-learning, and provides the corresponding generalization gap, as shown in Theorem 3.1. In each specific setting (convex+Lipschitz, convex+smooth, weakly-convex+non-smooth), we primarily compare our results (derived from Thm 3.1) with those derived from Thm 2.2. For further details, see lines 235-238 and 269-271.\n\nQ2: To achieve a rate of $1/mn$, stronger assumptions may be necessary. Prior work has demonstrated this: [r1] obtained a rate of $1/mn$ for strongly convex functions with Lipschitz continuous Hessians, while [r4] presented a generalization bound of $O(\\sqrt{\\frac{C}{mn}})$ under the task-relatedness assumption, where $C$ accounts for the logarithm of the covering number of the hypothesis class. More recently, [r5] provided $O(\\frac{1}{m}+\\frac1n)$ fast rate generalization bounds under an additional extended Bernstein's condition. Exploring the possibility of obtaining faster rates by considering stronger conditions in our setting could be an interesting direction for future work.\n\nQ3: When $n>m$, the generalization gap derived from Theorem 3.1 is $O(\\frac1m+\\frac1n+\\frac{1}{\\sqrt{mn}})=O(\\frac1m)$. The generalization gap derived from Theorem 2.2 is $O(\\frac1m+\\frac1n+\\frac{1}{\\sqrt{m}})=O(\\frac{1}{\\sqrt{m}})$, which is worse that the former. \nWe note that when $n<m\\leq n^2$, the generalization gap derived from Theorem 3.1 can be simplified as $O(\\frac1n)$. The generalization gap derived from Theorem 2.2 can be simplified as $O(\\frac{1}{\\sqrt{m}})$, which is still worse than the former.\n\nQ4: There is no similar form term in Theorem 3.2. We guess the reviewer refers to Lemma 4.2. \nNevertheless, we don't understand what's the intuition of having term of form $1/\\eta m +1/\\lambda n$. \n$\\lambda$ is the regularization term, but $\\eta$ is the step size for task-specific algorithm.\n\n[A] Giulia Denevi, Carlo Ciliberto, Riccardo Grazzi, and Massimiliano Pontil. Learning-to-learn stochastic gradient descent with biased regularization. In International Conference on Machine Learning, pages 1566–1575. PMLR, 2019a.\n\n[B] Andreas Maurer. 'Algorithmic stability and meta-learning'. Journal of Machine Learning Research, 6(6), 2005.\n\n[r1] Fallah, Alireza, Aryan Mokhtari, and Asuman Ozdaglar. \"Generalization of model-agnostic meta-learning algorithms: Recurring and unseen tasks.\" Advances in Neural Information Processing Systems 34 (2021): 5469-5480.\n\n[r2] Zhou, Pan, et al. \"Efficient meta learning via minibatch proximal update.\" Advances in Neural Information Processing Systems 32 (2019).\n\n[r3] Bousquet, Olivier, Yegor Klochkov, and Nikita Zhivotovskiy. \"Sharper bounds for uniformly stable algorithms.\" Conference on Learning Theory. PMLR, 2020.\n\n[r4] Guan, J, and Lu Z. \"Task relatedness-based generalization bounds for meta learning.\" In International Conference on Learning Representations, 2022.\n\n[r5] Riou, Charles, Pierre Alquier, and Badr-Eddine Chérief-Abdellatif. \"Bayes meets bernstein at the meta level: an analysis of fast rates in meta-learning with pac-bayes.\" arXiv preprint arXiv:2302.11709 (2023).", "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": "", "extra_scores": {}}, {"review_id": "Qpjq0G7hDE", "reviewer": "Reviewer_SWCq", "summary": "This submission introduces a new bound on the transfer risk of meta-learning based on a modified form of algorithmic stability. Several examples of how the new bound can be used to analyze the transfer risk of meta-learning algorithms built on gradient-based optimisation are provided. A comparison with the existing bound of Maurer (2005) is given, where it is shown that the new bound is generally better.", "questions": "N/A", "limitations": "There is no substantial discussion of the limitations, but this might be because there is no downside over the existing bound. The authors do provide some examples of what is still generally missing from meta-learning theory.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "* The submission introduces a new bound on the transfer risk of meta-learning based on a modified form of algorithmic stability. The new stability definition seems intuitive, and enables the bound to have a much better dependence on the sampling error compared to the conventional meta-learning bound based on algorithmic stability.\n* They provide several examples of how the new bound can be used to analyze the transfer risk of meta-learning algorithms built on gradient-based optimisation. Several combinations of loss function properties (convex, weakly convex, Lipschitz, smooth, etc) are considered.\n* The submission also considers some small extensions to stochastic and adversarial settings.", "weaknesses": "* The proofs can be a bit hard to follow at times. For example, the construction of $\\mathcal{C}_l$ is the proof of Theorem B.3 is somewhat underspecified, and I could not really follow what was going on here.\n* When analysing specific algorithms with the new framework, it would have been good if the submission also contained a comparison with papers that also focus on, e.g., convex smooth meta-learning settings. The work of Giulia Denevi, Massimiliamo Pontil, and others could be relevant here.\n* The submission could be improved by providing a more detailed discussion of the implications of the new bound, and the fundamental high-level reasons for the differences. For example, the main difference that I can see is improved dependence on the sampling error compared with Maurer (2005) [Note: Tommi Jaakkola is erroneously listed as a co-author in this submission]. A high-level overview of the proof strategy and any other benefits that I missed would be good.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**Proof idea.** Our proof leverages the same sample-splitting approaches as described in [1,2]. The recursive structure is based on the specific telescoping sum. The design of the sequence of partitions $\\mathcal{C_0},\\ldots,\\mathcal{C_k}$ relates to the analysis of the terms $g_{i,j}^{q,0}-g_{i,j}^{q+1,0}$, and the sequence of partitions $\\mathcal{E_0},\\ldots,\\mathcal{E_r}$ relates to the analysis of the terms $g_{i,j}^{r,l}-g_{i,j}^{r,l+1}$. Please refer to the answer to Reviewer VSfZ for a detailed discussion on the proof.\n\n**Comparison with literature.**\nWe discuss some of the related work in page 7 line 276-300. We now provide a detailed comparison between our result and [3].\n- **Different Function Classes Considered.** The function classes considered in [A] are limited to compositions of linear hypothesis classes with convex and closed losses. In contrast, our work considers a broader range of functions, encompassing not only convex, Lipschitz, and smooth functions but also weakly-convex and non-smooth functions.\n\n- **Different Analysis Techniques.** [A] employs a primal-dual formulation of bias regulation ERM due to the simplicity of linear classifier that discussed above. Given our broader range of function classes, we introduce a new definition of stability and use stability arguments to derive generalization bounds.\n\n- **The expected excess risk is different.** The expected excess risk from Theorem 4.7 in our paper is of the form $O(\\frac{1}{\\lambda\\sqrt{K}}+\\frac{1}{\\lambda m}+\\frac{1}{\\lambda n}+\\frac{\\lambda}{T}+\\lambda\\sigma^2),$\nwhere $m$ is the number of tasks, $n$ is the number of samples per task, $K$ is the number of iterations for task-specific algorithm 2 and $T$ is the number of iterations for meta-learning algorithm 1,\n$\\sigma$ is the approximate error that captures the average distance between the optimal task-specific parameters $\\mathrm{u}_j$'s and the optimal estimated meta-parameter $\\mathrm{\\hat w}$. \nMoreover, choosing $K=O(n^2)$ and $\\lambda=O(\\frac{1}{\\sqrt{n}})$, the expected excess risk is \n$O(\\frac{\\sqrt{n}}{m}+\\frac{1}{\\sqrt{n}}+\\frac{1}{T\\sqrt{n}}+\\frac{\\sigma^2}{\\sqrt{n}}),$\nwhich depends on the number of tasks $m$. \nOn the other hand, Algorithm 2 in [A] assumes solving the within-task problem approximately, so there's no within task iteration $K$ involved in the bound. The expected excess risk in [A] is of the form $O(\\frac{Var_m}{\\sqrt{n}}+\\frac{1}{\\sqrt{T}}),$ where $Var_m$ captures the relatedness among the tasks sampled from the task environment. Note that this bound is gained based on a specific choise of $\\lambda$ that depends on $Var_m$, which is unlikely to know ahead in practice.\nMoreover, assuming $Var_m$ is a constant, then this bound is independent of the number of tasks $m$. Therefore, our bound is tighter when $n\\lesssim m$. \n\n**Comparison with [Maurer 2005].**\nWe present the main result from [B] as Theorem 2.1 in Sec 2. The advantage of [B] is that it directly leverages the uniform stability argument from single-task learning to meta-learning. [B] considers uniform stability definitions at both the task-sample and meta-sample levels. By applying new tools from [r3], we provide Theorem 2.2, which improves upon Theorem 2.1 under the same definition of uniform stability. \nOn the other hand, our paper introduces a new notion of uniform stability that accounts for changes at both the task-sample and meta-sample levels, specifically designed for meta-learning, and provides the corresponding generalization gap, as shown in Theorem 3.1. In each specific setting (convex+Lipschitz, convex+smooth, weakly-convex+non-smooth), we primarily compare our results (derived from Thm 3.1) with those derived from Thm 2.2. For further details, see lines 235-238 and 269-271.\n\n[1] Feldman, Vitaly, and Jan Vondrak. \"Generalization bounds for uniformly stable algorithms.\" Advances in Neural Information Processing Systems, 2018.\n\n[2] Bousquet, Olivier, Yegor Klochkov, and Nikita Zhivotovskiy. \"Sharper bounds for uniformly stable algorithms.\" Conference on Learning Theory, 2020.\n\n[3] Giulia Denevi, Carlo Ciliberto, Riccardo Grazzi, and Massimiliano Pontil. Learning-to-learn stochastic gradient descent with biased regularization. In International Conference on Machine Learning, 2019.", "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": "", "extra_scores": {}}, {"review_id": "pykFKOPJXH", "reviewer": "Reviewer_VSfZ", "summary": "This paper introduces the notion of \"uniform meta-stability\" to bound the generalization error of $\\ell_2$-regularized meta-learning problem. Theoretical guarantees are respectively established for smooth loss functions as well as weakly convex losses that are not necessarily smooth. Variants of the algorithm on stochastic and adversarially robust meta-learning problems are investigated.", "questions": "See Weaknesses.", "limitations": "There is no explicit discussion regarding the limitations of this work. Social impact is not applicable.", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "1. This paper provides a solid theoretical analysis regarding the stability and generalization of meta-learning. \n2. Application of the theoretical results to stochastic and adversarially robust meta-learning is both interesting and promising. \n\nHowever, I have several concerns on the applicable scope and technical assumptions of this paper.", "weaknesses": "Major concerns:\n\n1. The scope of this paper can be quite limited. In particular, this paper focuses exclusively on the specialized meta-learning formulation where i) an explicit $\\ell_2$-regularization is leveraged to encode the prior, and ii) the inner-level and outer-level rely on the same dataset. These two particular structures are intentionally designed in [1] to simplify the computation of meta-gradient. In contrast, most widely-used meta-learning algorithms like MAML employ i) GD-based implicit regularization [2] or a generic explicit regularizer beyond $\\ell_2$, and ii) the support/query (S/Q) training setup. Unfortunately, it seems that the results of this paper are merely applicable to the problem addressed in [1]. \n2. Some assumptions made in this paper are rather strong. For instance, it is assumed in line 127 that $\\mathcal{W}$ is closed with a finite radius (i.e., compact). This compactness premise is uncommon in meta-learning. It is not made in not only the most related work [3], but also [1] which this paper builds upon. In addition, while [3] provided an analysis for Holder smooth loss, this paper requires it to be weakly convex, which is a stronger assumption. \n\nMinor comments:\n1. In line 141, the symbol $\\mathcal{H}$ comes out of the blue without definition, which I guess might be the hypothesis space. \n2. In line 242, \"this should not surprising\" should be corrected to \"this should not be surprising\". \n\n[1] P. Zhou, X. Yuan, H. Xu, S. Yan, and J. Feng, \"Efficient Meta-Learning via Minibatch Proximal Update,\" NeurIPS 2019.  \n[2] E. Grant, C. Finn, S. Levine, T. Darrell, and T. Griffiths, \"Recasting Gradient-Based Meta-Learning as hierarchical Bayes,\" ICLR 2018.  \n[3] J. Guan, Y. Liu, and Z. Lu, \"Fine-grained analysis of stability and generalization for modern meta learning algorithms,\", NeurIPS 2022.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**Limited Scope.** Apply l2 regularization is common in meta-learning literature [1,4,5,6,7,8] and transfer learning literature in general [9,10].\nExtending our idea to MAML and S/Q learning could be interesting future direction.\n\n**Compact radius assumption.** The compact radius assumption is only necessary for obtaining the excess transfer risk, as discussed in Theorem 4.7 in Section 4.3. This is a standard assumption in the optimization literature and has been utilized in previous work that provided excess transfer risk results; see, for example, Assumption 1 and Algorithm 1 in [4]. We emphasize that the generalization gap based on the stability argument (Sections 4.1 and 4.2) does not rely on such assumptions, which is consistent with prior work [1,3] as they do not consider excess transfer risk.\n\n**Weakly-convexity assumption.** A weakly convex function is essentially non-convex and non-smooth but with bounded lower curvature. This is a milder assumption than requiring the loss to be smooth and is achievable in practical scenarios, such as training neural networks using gradient descent [11]. In contrast, [3] considers Hölder smooth loss, which is another way of relaxing the smoothness assumption, and it appears to be limited to linear classifiers based on the examples provided in [3]. Moreover, we have discussed the limitations of [3] as it assumes that the loss function after gradient update $\\hat R(\\cdot, S)$ is convex or Hölder smooth (see lines 284-288).\n\n\n\n[1] P. Zhou, X. Yuan, H. Xu, S. Yan, and J. Feng, \"Efficient Meta-Learning via Minibatch Proximal Update,\" NeurIPS 2019.\n\n[2] E. Grant, C. Finn, S. Levine, T. Darrell, and T. Griffiths, \"Recasting Gradient-Based Meta-Learning as hierarchical Bayes,\" ICLR 2018.\n\n[3] J. Guan, Y. Liu, and Z. Lu, \"Fine-grained analysis of stability and generalization for modern meta learning algorithms,\", NeurIPS 2022.\n\n[4] Giulia Denevi, Carlo Ciliberto, Riccardo Grazzi, and Massimiliano Pontil. \"Learning-to-learn stochastic gradient descent with biased regularization.\" In International Conference on Machine Learning, 2019.\n\n[5] Zhou, Xinyu, and Raef Bassily. \"Task-level differentially private meta learning.\" Advances in Neural Information Processing Systems, 2022.\n\n[6] Jiang, Weisen, James Kwok, and Yu Zhang. \"Effective meta-regularization by kernelized proximal regularization.\" Advances in Neural Information Processing Systems, 2021.\n\n[7] Balcan, Maria-Florina, Mikhail Khodak, and Ameet Talwalkar. \"Provable guarantees for gradient-based meta-learning.\" International Conference on Machine Learning, 2019.\n\n[8] Rajeswaran, Aravind, et al. \"Meta-learning with implicit gradients.\" Advances in neural information processing systems, 2019.\n\n[9] Kuzborskij, Ilja, and Francesco Orabona. \"Stability and hypothesis transfer learning.\" International Conference on Machine Learning, 2013.\n\n[10] Kuzborskij, Ilja, and Francesco Orabona. \"Fast rates by transferring from auxiliary hypotheses.\" Machine Learning, 2017.\n\n[11] Richards, Dominic, and Ilja Kuzborskij. \"Stability & generalisation of gradient descent for shallow neural networks without the neural tangent kernel.\" Advances in neural information processing systems, 2021.", "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": "", "extra_scores": {}}, {"review_id": "U1oLI3ylaY", "reviewer": "Reviewer_zAce", "summary": "The paper presents stability analysis for meta-learning. The paper first introduces a uniform meta-stability, where there is both a change of the task in the meta-sample and also a change of an example for the task at test time. For this uniform meta-stability, the paper gives high-probability bounds of the order of $\\beta+O(1/\\sqrt{mn})$, where $\\beta$ is the stability parameter, m is the number of tasks and n is the number of examples per task. The paper then considers a prox meta-learning algorithm with two task-specific algorithms. For these algorithms, the paper establishes stability bounds for different problem settings: convex & Lipschitz, convex & smooth and weakly-convex problems. Applications to proximal-meta learning with stochastic optimization and robust adversarial proximal meta-learning are also given.", "questions": "Is the proof of Theorem B.3 correct?\n\nIn Theorem 4.7, the paper uses $\\sigma^2=\\frac{1}{K}\\sum_j\\|\\hat{w}-u_j^*\\|$. It seems that $K$ should be $m$?\n\nTypos:\n- Below Theorem 4.4: \"should not surprising\"", "limitations": "No potential negative societal impacts.", "rating": 4, "confidence": 4, "soundness": 2, "presentation": 3, "contribution": 3, "strengths": "The paper introduces a new stability probability measure for meta-learning, and give both high-probability bounds and bounds in expectation for algorithms satisfying this uniform meat-stability.\n\nThe paper also studies two algorithms and establishes stability bounds under different problem settings. These bounds better than existing bounds in the sense of involving $1/\\sqrt{mn}$, which shows the benefit of considering several tasks together.\n\nThe paper is clearly written and the main contributions are clearly stated.", "weaknesses": "In Theorem 4.4, the paper establishes risk bounds of the order of $\\frac{1}{\\lambda m}+\\frac{1}{\\lambda n}+\\sqrt{1/(mn)}$. However, $\\lambda$ should be often small in practice. For example, Theorem 4.7 gives bounds depending on $\\lambda\\sigma^2$. To get meaningful bounds, $\\lambda$ should be of the order $o(1)$. At the end of Section 4.3, the paper suggests $\\lambda=O(1/\\sqrt{n})$. In this case, the excess risk bounds in Theorem 4.4 are of the order of $\\sqrt{n}/m+1/\\sqrt{n}$. Then, the term $\\sqrt{1/(mn)}$ does not play an important role in the generalization. Also, Theorem 4.1 requires $\\lambda\\geq H$ in the smooth case, which requires a large regularization parameter.\n\nIn Theorem 4.6, the risk bounds involve $\\sqrt{\\eta/\\lambda}$. Therefore, the bounds would be nonvacuous only if $\\eta$ is small and $\\lambda$ is large. However, a small $\\eta$ would affect the convergence of the algorithm. Therefore, it may be difficult to find a balance between stability and optimization. \n\nIn the proof of Theorem B.3, the paper uses the identity (I omit the index $j,i$ for brevity)\n$$\ng^{0,0}-g^{r,k}=\\sum_{g=0}^{r-1}\\sum_{l=0}^{k-1}(g^{q,l}-g^{q+1,l+1}).\n$$\nHowever, it seems that this identity does not hold. For example, let us consider the simple case $r=2,k=2$. Then the identity becomes\n$$\ng^{0,0} - g^{2,2} = g^{0,0} - g^{1,1} + g^{0,1}- g^{1,2} + g^{1,0} - g^{2,1} + g^{1,1} - g^{2,2}.\n$$\nIt is clear that this identity does not hold. Therefore, it seems that the proof of Theorem B.3 is not rigorous.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**Choice of $\\lambda$.**\n\n$\\lambda=O(1/\\sqrt{n})$ is just one choice of $\\lambda$ that leads to non-vacuous excess risk and there are other options. For example, if choosing $\\lambda=O(1/n^{\\frac14})$, then under the setting where $\\sqrt{n}\\leq m \\leq n^{3/2}$, the generalization gap from Theorem 4.4 is of rate $O(\\frac{1}{\\lambda m}+\\frac{1}{\\lambda n} + \\frac{1}{\\sqrt{mn}})=O(\\frac{n^{\\frac14}}{m}+\\frac{1}{n^{\\frac34}}+\\frac{1}{\\sqrt{mn}})=O(\\max(\\frac{n^{\\frac14}}{m},\\frac{1}{n^{\\frac34}}))$. This is tighter than the generalization gap that derived from Theorem 2.2, which is of rate $O(\\frac{1}{\\lambda m}+\\frac{1}{\\lambda n} + \\frac{1}{\\sqrt{m}})=O(\\frac{n^{\\frac14}}{m}+\\frac{1}{n^{\\frac34}}+\\frac{1}{\\sqrt{m}})=O(\\frac{1}{\\sqrt{m}})$.\n\nTheorem 4.1 requires $\\lambda>H$ for smooth loss under Option 1 for Algorithm 2. However, Theorem 4.7 only considers Option 2 for Algorithm 2. The corresponding theorem for the generalization gap in this case is Theorem 4.4, where we only assume $\\lambda>0$. \n\n**Balance between stability and optimization.**\n\nWe discussed the proper choice of $\\eta=O(\\frac{1}{\\lambda K^{2/3}})$ for convex and Lipschitz losses to achieve a decaying excess risk, as described in lines 320-323. With sufficiently large $K, T$, by appropriately choosing $\\lambda=o(1)$, the excess risk remains non-vacuous.\n\n**Proof of Theorem B.3.**\n\nWe thank the reviewer for carefully checking our proof. For given $r=k=2$, the right decomposition would be $g^{0,0}-g^{2,2}=g^{0,0}-g^{1,0}+g^{1,0}-g^{2,0}+g^{2,0}-g^{2,1}+g^{2,1}-g^{2,2}$.\n\nWe now fix the equation the reviewer point it out as well as some other typos as follows. We note that proof of Theorem B.3 is an extension of  [Bousquet et al., 2020, Theorem 4], and the following fix would not change our main result.\n\nContinue with line 689 in the paper, we have the following \n\n$g_{j,i}-\\mathbb{E}[g_{j,i}|Z_j,z_i]=\\sum_{q=0}^{r-1}g_{j,i}^{q,0} - g_{j,i}^{q+1,0}+\\sum_{l=0}^{k-1} g_{j,i}^{r,l} - g_{j,i}^{r,l+1},$\n\nand the total sum of interest satisfies by the triangle inequality\n$||\\sum_{j=1}^m\\sum_{i=1}^n g_{j,i}||\\leq ||\\sum_{j=1}^m\\sum_{i=1}^n \\mathbb{E}[g_{j,i}|Z_j,z_i]||+\\sum_{q=0}^{r-1}||\\sum_{j=1}^m\\sum_{i=1}^n g_{j,i}^{q,0}-g_{j,i}^{q+1,0}||\n+\\sum_{l=0}^{k-1}||\\sum_{j=1}^m\\sum_{i=1}^n g_{j,i}^{r,l}-g_{j,i}^{r,l+1}||.$\n\nApply McDiarmid’s inequality gives us that\n$||g_{j,i}^{q,0}-g_{j,i}^{q+1,0}||(Z_j,Z_{[m]\\backslash E^{q+1}(j)},z_i,z_{[n]\\backslash C^{0}(i)})\\leq 2\\sqrt{2^{q+1}}\\bar\\beta$, \n\n$||g_{j,i}^{r,l}-g_{j,i}^{r,l+1}||(Z_j,Z_{[m]\\backslash E^{r}(j)},z_i,z_{[n]\\backslash C^{l+1}(i)})\\leq 2\\sqrt{2^{l+1}}\\bar\\beta$.\n\n\nSince $g_{j,i}^{q,0}-g_{j,i}^{q+1,0}$ for $j\\in E^q, i\\in C^0$ depends on $Z_j$, $Z_{[m]\\backslash E^{q+1}(j)}$, $z_i$, $z_{[n]\\backslash C^0(i)}$, \nthe terms are independent and zero mean conditioned on $Z_{[m]\\backslash E^{q+1}(j)}$. \n\nApplying Theorem B.2, we have \n\\begin{align*}\n||\\sum_{j\\in E^q}\\sum_{i\\in C^0} g_{j,i}^{q,0} - g_{j,i}^{q+1,0}||^2(Z_{[m]\\backslash E^q})\n\\leq 36\\cdot 2^{q} \\frac{1}{2^q} \\sum_{j\\in E^q}\\sum_{i\\in C^0}||g_{j,i}^{q,0}-g_{j,i}^{q+1,0}||^2(Z_{[m]\\backslash E^q})\n\\end{align*}\n\n\nIntegrating with respect to $(Z_{[m]\\backslash E^q})$ and using $||g_{j,i}^{q,0} - g_{j,i}^{q+1,0}||\\leq 2\\sqrt{2^{q+1}}\\bar\\beta$, we have\n\\begin{align*}\n||\\sum_{j\\in E^q}\\sum_{i\\in C^0} g_{j,i}^{q,0}-g_{j,i}^{q+1,0}||\n\\leq 6\\sqrt{2^{q}}\\times 2\\sqrt{ 2^{q+1}}\\bar\\beta= 12\\sqrt{2}\\cdot2^{q}\\bar\\beta.\n\\end{align*}\n\n\nApplying triangle inequality over all sets $C^0\\in\\mathcal{C_0},E^q\\in\\mathcal{E_q}$ gives us that\n\n\\begin{align*}\n||\\sum_{j\\in[m]}\\sum_{i\\in[n]} g_{j,i}^{q,0}-g_{j,i}^{q+1,0}||\n\\leq \\sum_{E^q\\in\\mathcal{E_q},C^0\\in\\mathcal{C_0}}||\\sum_{j\\in E^q, i\\in C^0}g_{j,i}^{q,0} - g_{j,i}^{q+1,0}||\n\\leq12\\sqrt{2}\\cdot 2^{r+k}\\bar\\beta.\n\\end{align*}\n\nSimilarly, applying triangle inequality over all sets $C^l\\in\\mathcal{C}_l,E^r\\in\\mathcal{E}_r$ gives us that\n\n\\begin{align*}\n||\\sum_{j\\in[m]}\\sum_{i\\in[n]} g_{j,i}^{r,l}-g_{j,i}^{r,l+1}||\n\\leq \\sum_{E^r\\in\\mathcal{E_r},C^l\\in\\mathcal{C_l}}||\\sum_{j\\in E^r, i\\in C^l}g_{j,i}^{r,l} - g_{j,i}^{r,l+1}||\\leq12\\sqrt{2}\\cdot 2^{r+k}\\bar\\beta.\n\\end{align*}\n\nRecall that $2^k < 2n, 2^r<2m$ due to the possible extension of the sample. Therefore we have\n\\begin{align*}\n\\sum_{q=0}^{r-1}||\\sum_{j=1}^m\\sum_{i=1}^n g_{j,i}^{q,0}-g_{j,i}^{q+1,0}||\n+\\sum_{l=0}^{k-1}||\\sum_{j=1}^m\\sum_{i=1}^n g_{j,i}^{r,l}-g_{j,i}^{r,l+1}||\n\\lesssim mn\\bar\\beta \\log(mn).\n\\end{align*}\n\n[Bousquet et al., 2020] Bousquet, Olivier, Yegor Klochkov, and Nikita Zhivotovskiy. \"Sharper bounds for uniformly stable algorithms.\" Conference on Learning Theory. PMLR, 2020.", "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": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: This paper investigates the quantification of stability and generalization performance in meta-learning algorithms, addressing both convex and weakly convex problems with non-smooth losses. A newly proposed stability measure, adapted from existing ones, is tailored for this specific setting. While the two algorithms considered are fairly standard, some mismatches exist, such as in the projection operation. Under the strong assumptions made, other properties, like G-Lipschitz continuity and M-boundedness, are straightforward, though they may not hold in practice. The paper provides insights into how the meta-learning structure, the number of tasks or samples, and the regularization parameter influence stability and generalization performance. However, the numerical results are limited, as only toy examples are presented. Despite this, most reviewers generally acknowledge the contribution of this work, and the authors have addressed the majority of the concerns raised.
Decision: Accept (poster)