On the Stability and Generalization of Meta-Learning: the Impact of Inner-Levels

We thank for all your valuable comments. According to the weaknesses and questions, we will reply these individually as the following.

Weakness 1: Although we acknowledge certain typographical errors pointed out by the reviewer, we believe we have clarified the meaning of all symbols used in our paper. Regarding the terms $\hat{F}\_i(w, S\_i)$ and $\hat{L}\_{\lambda}(w, S\_i)$ and their relationship, we have explained them in lines 144-145. In particular, $\hat{F}\_i(w, S\_i)$ represents the empirical loss, i.e., the training loss, which has been explained in lines 132-133. We use $\hat{L}\_{\lambda}(w, S\_i)$ to reflect the effect of $\lambda$. If we did not do so, the definition of $F$ would be confusing. As for the term $\hat{\mathcal{K}}(w, S\_i)$, we have addressed it in lines 146-149: "For a practical PDF-based algorithm, it's difficult to obtain an exact solution of $\widehat{\mathcal{L}}\_{\lambda}(w, S\_i)$, so we typically resort to an inexact solution, $\widehat{\mathcal{K}}(w, S\_i) = \frac{1}{n} \sum\_{z \in S\_i} \ell(w\_{\mathcal{T}\_i}, z) + \frac{\lambda}{2} \| w\_{\mathcal{T}\_i} - w \|^2$."

Weakness 2 and Question 3: We would like to emphasize that our work significantly extends the contributions of [1]. While [1] investigates the trade-off in MAML, their analysis is conducted within a relatively narrow scope and lacks a general or extensible framework. In contrast, we introduce two flexible and broadly applicable frameworks—GDF and PDF—which are designed to accommodate a wide range of meta-learning algorithms. To illustrate the generality and practicality of these frameworks, we derive generalization bounds for six different algorithms. Moreover, our GDF framework provides a more robust and interpretable characterization of the trade-off. Specifically, when comparing our Theorem 2 with the results of [1], let us consider the case where $T=m$. Under this, our theorem 2 yields a bound $\mathcal{O}(\frac{Q}{n}+\frac{\sqrt{F(w^0)-\min\_{\mathcal{W}}F}}{m})$ whereas the bound in [1] is $\mathcal{O}(\frac{1}{n}+F(w^T)-\min\_{\mathcal{W}}F))$. It is evident that our second term $\frac{\sqrt{F(w^0)-\min\_{\mathcal{W}}F}}{m})$ is significantly lower than the corresponding $F(w^T)-\min\_{\mathcal{W}}F$ in [1]. Although our first term is looser than theirs $\frac{1}{n}$, we argue that it is intuitive outcome.. In particular, this statement, "For sufficiently large $Q$, $\alpha\leq \frac{1}{QL}$ yields negligibly small learning rate, implying the inner update will be close to initialisation $w\_{\tau\_i,0}^t$" reinforces the validity of our bound. Intuitively, if the inner-loop update is too close to the initialization, the model fails to learn task-specific information effectively, leading to larger generalization error—similar to the behavior observed when $Q=1$. However, the results in [1] ca not explain the trade-off relationship either is sufficiently small or large $Q$ when $\alpha\leq \frac{1}{QL}$, which means their results is not robust.

Question 1: The core idea of MAML involves applying a few gradient descent steps on a small number of training samples to adapt the meta-model to test tasks. Therefore, We use Fig. 1 to illustrate an interesting phenomenon, i.e., a larger number of $Q$ is not suitable for MAML. To address the reviewers' concerns, we also provide further experiment for MAML when $Q>20$. The experiment is also conducted on the Omniglot dataset. We employ a $3\times 3$ CNN and use the Cross-Entropy Loss as the loss function. For each training task, the number of support samples and query samples to $n^{\rm{tr}}=1$ and $n^{\rm{ts}}=5$, respectively. For each test task, we use $n^{\rm{tr}}=1, n^{\rm{ts}}=15$. In addition, each task is formulated as a $5$-way classification problem.

Question 2: In theoretical analysis, two identical assumptions do not necessarily imply that the difficulty and process of derivation under the two settings is the same, especially in stability analysis. In fact, the condition of some parameter is stricter in non-convex. For instance, under convex setting, the step size $\eta\leq\frac{1}{L\_Q}$ with $L\_Q = \alpha\rho Q(1+\alpha L)^{Q-1} + (1+\alpha L)^{Q}L$. In contrast, under non-convex setting, the step size $\eta\_t \leq \frac{c}{t}$ and $c\leq\min\{\frac{1}{L_Q},\frac{1}{4(2L\_Q\rm{ln}(T))^2}\}$ with $L\_Q= \frac{3\rho(1+\alpha L)^{2(Q-1)}}{L} + (1+\alpha L)^{Q}L$.

Question 4: Referring to the Eq (1) and Eq(2) in this paper, we can get $F(w)=\frac{1}{m}\sum\_{i=1}^{m} F\_i(w)=\frac{1}{m}\sum\_{i=1}^{m} \mathbb{E}\_{\mathcal{D}\_i} \mathbb{E}\_{z\in\mathcal{P}\_i}[\ell(w\_{\mathcal{T}\_{i}}^Q(w, \mathcal{D}\_i),z]$. Then we can find that $F_i(w)$ is benefited by $Q$ due to $w\_{\tau\_i}^Q(w, \mathcal{D}\_i)=w-\alpha\sum\_{q=0}^{Q-1}\nabla \widehat{\mathcal{L}}\_i( w\_{\tau\_i}^q,\mathcal{D}\_i)$. Therefore, both $F(w^T)-\min\_{\mathcal{W}}F$ and $F(w^0)-\min\_{\mathcal{W}}F$ can be improved by increasing $Q$. The main difference is that $F(w^T)-\min\_{\mathcal{W}}F$ can also be improved by the number of outer-loop iterations $T$.

Question 5: Since our work primarily focuses on generalization error, while other studies emphasize transfer error, it is difficult to make a fair comparison regarding the tightness of the bounds. Generalization error measures the discrepancy between training tasks and test tasks, making it a key metric for evaluating the practical capability of meta-learning algorithms.

[1] Zhou, P., Zou, Y., Yuan, X.T., Feng, J., Xiong, C. and Hoi, S., 2021, December. Task similarity aware meta learning: Theory-inspired improvement on MAML. In Uncertainty in artificial intelligence (pp. 23-33). PMLR.

We thank for all your valuable comments. According to the questions, we will reply these individually as the following.

Question 1: In the inner-level process of GDF, the learner $w$ needs to find task-specific parameters $w\_{\tau_i}$ after undergoing $Q$ times gradient updates. This process can be formulated as $w\_{\tau\_i}=w-\alpha\sum\_{q=0}^{Q-1}\nabla \widehat{\mathcal{L}}\_i(w\_{\tau\_i}^q,\mathcal{D}\_i)$. To emphasize its difference of inner-levels from PDF, we give the optimization objective of inner-process, i.e., Eq(2)=$\min\_{w\_{\mathcal{T}\_{i}}}\left\langle\sum\nolimits\_{q=0}^{Q-1}\nabla \widehat{\mathcal{L}}\_{i}(w\_{\mathcal{T}\_{i}}^{q},\mathcal{D}\_i),w\_{\mathcal{T}\_{i}}-w\right\rangle+\frac{1}{2\alpha}\|w\_{\mathcal{T}\_{i}}-w\|\_{2}^{2}$. By taking the derivative on $w\_{\tau_i}$ and making the gradient equal to $0$, Eq(2) can be written as $w\_{\tau_i}=w-\alpha\sum\_{q=0}^{Q-1}\nabla \widehat{\mathcal{L}}\_i (w\_{\tau_i}^q,\mathcal{D}\_i)$..

Question 2: As we illustrated in section 3.2, PDF aims to obtain an exact solution of its empirical meta-loss $\widehat{L}\_{\lambda}(w, S\_i)=\min\_{w\_{\mathcal{T}\_i}}\{\frac{1}{n}\sum\_{z\in S\_i} \ell(w\_{\mathcal{T}\_i} , z)+\frac\lambda2\|w\_{\mathcal{T}\_i}-w\|^2 \}$ which is difficult in practical algorithms. Therefore, we often solve an approximation, i.e., $\widehat{\mathcal{K}}(w, S\_i)=\frac{1}{n}\sum\_{z\in S\_i} \ell(w\_{\mathcal{T}\_i}, z)+\frac\lambda2\|w\_{\mathcal{T}_i}-w\|^2$ in Algorithm 1.

Thank you for your valuable suggestions, we will reply these as follows.

Weakness 1: We appreciate the reviewer for pointing out the typographical errors, which we will promptly correct.

Weakness 2 and Question 2: To further clarify the meaning of $Q$, we can use MAML as an example. MAML utilizes available training data from multiple tasks to derive a meta-initialization that performs well after a few updates during testing, tailored to a new task. Unlike traditional supervised learning, where the goal is to find a model that generalizes well to a new task without any adaptation, MAML focuses on finding an initial model that can efficiently learn a new task with only a small amount of labeled data by performing $Q$ gradient updates. Therefore, in this paper, our framework requires undergoing $Q$ gradient updates at the inner level to adapt to a small amount of data. We will add some relevant concepts explanation based on your advice.

Weakness 3: We are sorry to make you confused and will explain them in details. Our work primarily focuses on the generalization error in meta-learning, which quantifies the performance gap between training and testing phases. The upper bound of this generalization error characterizes the worst-case performance at test time, and thus, optimizing this upper bound is critical for ensuring the real-world applicability of meta-learning algorithms. Moreover, stability is a powerful analytical tool in generalization theory. It helps us understand which parameters affect generalization and how they influence it. Crucially, the definition of stability plays a central role in this analysis, as it directly determines the tightness and relevance of the resulting bounds. Therefore, we introduce two novel stability definitions for our frameworks.

Weakness 4: We further elaborate on our results and the proof approach. Our work focuses on the generalization error in meta-learning, and stability proves to be a powerful tool for deriving the generalization error of algorithms. The first step involves introducing two novel stability definitions for our frameworks, namely GDF and PDF. Based on these definitions, we derive Theorem 1, which states: $\mathbb{E}\_{\mathcal{A}, \mathcal{S}}\left[F(w\_{\mathcal{S}})-\widehat{F}(w\_{\mathcal{S}},\mathcal{S}\_{i})\right] \leq \frac{1}{m} \sum\_{i=1}^m \frac1{n^{\rm{ts}}} \sum\_{j=1}^{n^{\rm{ts}}} \mathbb{E}\_{\mathcal{A}, \mathcal{S}, \widetilde{S}\_{i,k}^{\rm{tr}}, \tilde{z}\_{i,j}^{\rm{ts}}}[\ell(w\_{\mathcal{T}\_i}(w\_{\mathcal{S}}, \widetilde{S}\_{i,k}^{\rm{tr}}), \widetilde{z}\_{i,j}^{\rm{ts}})- \ell\left(w\_{\mathcal{T}\_i}(w\_{\widetilde{\mathcal{S}}}, \widetilde{S}\_{i,k}^{\rm{tr}}), \widetilde{z}\_{i,j}^{\rm{ts}}\right)] \leq \epsilon.$ This provides a bound for the generalization error, $\epsilon\_{\rm{gen}}$. It is important to note that $w\_{\mathcal{S}}$ and $w\_{\widetilde{{\mathcal{S}}}}$ are two different outputs of a randomized algorithm $\mathcal{A}$, which correspond to two neighboring datasets, $\mathcal{S}$ and $\widetilde{{\mathcal{S}}}$, differing by a single data point. Therefore, in our proof, the key idea is to bound the difference between $\ell(w\_{\mathcal{T}\_i}(w\_{\mathcal{S}}, \widetilde{S}\_{i,k}^{\rm{tr}}), \widetilde{z}\_{i,j}^{\rm{ts}})- \ell\left(w\_{\mathcal{T}\_i}(w\_{\widetilde{\mathcal{S}}}, \widetilde{S}\_{i,k}^{\rm{tr}}), \widetilde{z}\_{i,j}^{\rm{ts}}\right)$. Under our assumption that the loss function is $G$-Lipschitz over $\mathbb{R}^d$, i.e., $| \ell(w,z) - \ell(u,z)|\leq G|w-u|$, we aim to bound the difference between $w\_{\mathcal{T}\_i}(w\_{\mathcal{S}}, \widetilde{S}\_{i,k}^{\rm{tr}})$ and $w\_{\mathcal{T}\_i}(w\_{\widetilde{\mathcal{S}}}, \widetilde{S}\_{i,k}^{\rm{tr}})$. This difference is inherently dependent on the updating rule used by different algorithms.

Weakness 5: We have submitted our code in the supplementary materials. You can check them by downloading the supplementary materials.

Weakness 6 and Question 4: Our results indicate that the objective function $F(w^0)$ plays a crucial role in reducing the generalization bound. For instance, in the non-convex setting, the generalization bound of GDF is $\mathcal{O}((\frac{1+\frac{1}{c\gamma}}{m}\Phi_Q)^{\frac{1}{c\gamma}}(F(w^0)T)^{\frac{c\gamma}{1+c\gamma}})$ and the generalization bound of PDF is $\mathcal{O}((\frac{1+\frac{1}{c\gamma}}{m}\Phi_Q)^{\frac{1}{c\gamma}}(F(w^0) T)^{\frac{c\gamma}{1+c\gamma}})$. We can observe that size of $F(w^0)$ is important when $T$ is sufficiently large.

To reduce the term $F(w^0)$, we begin with the definition of $F(w)=\frac{1}{m}\sum_{i=1}^m F_i(w)$. Let us consider a simple relaxation technique: given a constant $\beta\in[0,1)$ and $\hat{m}\leq \frac{m}{2}$ with the losses sorted by $\{F_i(w^0)\}$ in ascending order, we can obtain that $\sum_{i=1}^{\hat{m}}F_i(w^0)^{\psi{(i)}} \leq \sum_{i=\hat{m}+1}^{m}F_i(w^0)^{\psi{(i)}}$, where $\psi{(i)}$ is a mapping function associating the index with the original loss $F_i(w^0)$. Based on this, we can derive that $F(w^0) = \frac{1}{m}\sum_{i=1}^mF_i(w^0)^{\psi{(i)}} \geq \frac{1+\beta}{m}\sum_{i=1}^{\hat{m}}F_i(w^0)^{\psi{(i)}} + \frac{1-\beta}{m} \sum_{i=\hat{m}+1}^{m} F_i(w^0)^{\psi{(i)}}$. Motivated by this result, we propose the following optimization objective:

We thank for your valuable comments and will reply them as the following.

Question 1: In generalization analysis, upper bounds are particularly valuable because they characterize the worst-case performance of an algorithm, thereby enhancing its reliability in real-world applications. Especially in stability-based analyses, upper bounds provide deeper insights into the intrinsic properties of learning algorithms. An algorithm $\mathcal{A}$ is said to be $\epsilon\_{\text{gen}}$-stable if the change in its output loss, when applied to two neighboring datasets that differ by a single sample, is bounded by $\epsilon\_{\text{gen}}$. By deriving an upper bound on this stability, we are able to systematically trace how differences between neighboring datasets propagate through both the inner and outer learning levels. This enables our bound to precisely reflect the influence of the inner-level optimization. Moreover, our work makes a significant technical contribution: to the best of our knowledge, this is the first study to establish generalization bounds for meta-learning under two scalable algorithmic frameworks. In addition, we introduce two novel definitions of stability, which serve as the theoretical foundation for our analysis. We also recognize that the lower bound is valuable for the next generation of deductions, and will consider exploring this area of work in the future.

Question 2: Thanks for you suggestions and we additionally provide two experiments results in the convex setting and non-convex setting to verify our theoretical results again.

Few-shot regression on the new synthetic dataset: Unlike the experiments conducted in our paper that the tasks are created randomly as random sinusoid function, we recreated tasks randomly as either random sinusoid functions, or random linear functions. The amplitude of the sinusoids varies within $[0.1,5.0]$ and the phase within $[0,\pi]$. The slope and intercept of the lines vary in $[-3.0, 3.0]$. The inputs are sampled uniformly in $[-5.0,5.0]$. We also use an MLP network with Means square error loss function. The generalization error is assessed as the difference between training and test errors. For each training task, we set the number of support samples and query samples to $n^{\text{tr}}=5$ and $n^{\text{ts}}=5$, respectively, while for each test task, we use $n^{\text{tr}}=5$,$n^{\text{ts}}=15$. Then we report our results as follows:

Few-shot classification on CIFARFS: We conduct the experiment by using the real-world CIFARFS dataset, which is also a few-shot classification taks. It splits the 100 classes from CIFAR-100 into 64, 16 and 20 classes for training, validation, and test respectively. Each class contains 600 images of size 32×32×3. We employ a 3×3 CNN to align support samples and query samples to $n^{\text{tr}}=1$ and $n^{\text{ts}}=5$, respectively. For each test task, we use $n^{\text{tr}}=1$ and $n^{\text{ts}}=15$. Then we report our results as follows:

As shown in the table above, a trade-off relationship exists among the GDF algorithms, i.e., MAML, MetaSGD, and FOMAML, while a beneficial relationship is observed among the PDF algorithms, including MetaProx, iMAML, and FOMuML. Furthermore, we present experiments with our new objective, demonstrating that it improves the generalization error across the six algorithms.