Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: summary: This paper studies the generalization of meta-learning algorithms. In particular, this paper has three contributions:
1- Extending the stability analysis for convex smooth functions to convex Holder-smooth functions (similar to [30] for single task)
2- Improving the stability analysis of nonconvex functions
3- High probability generalization bounds

In particular, the authors show that the meta learning algorithms are less stable in the nonsmooth convex case, compared to smooth convex case. 
strengths_and_weaknesses: Overall, I find the paper and its results interesting to the community. My main concern is that the algorithmic stability is defined in a way that the whole dataset corresponding to a task changes. This makes the analysis simpler (as it would be closer to the single task case), but the results will not be tight with respect to the number of samples per task (m), as the authors point out in Remark 5.   

questions: I would appreciate it if the authors discuss how they could potentially study the effect of $m$ in generalization of meta-learning  algorithms for smooth and nonsmooth functions.
limitations: Yes.
review_title: null

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: summary: This manuscript provide fine-grained analysis of stability and generalization for modern meta learning algorithms by considering more general situations including -Holder continue convex, smooth convex and smooth non-convex functions. First, the authors give the lower and upper bounds of the uniform argument stability for -Holder continue convex functions and smooth convex functions respectively to show that meta learning algorithms in the smooth convex case is more stable than that in the non-smooth convex case. Second, a tighter stability bound of  than the existing bound  is proved. Then, to show the advantage of S/Q episodic strategy for meta learning over traditional ERM strategy, the authors develop a near-optimal high-probability generalization bound , and further improve the bound to  by considering Polyak-Łojasiewicz condition. Finally, a generalization bound for meta learning with dependent episodes is given.
strengths_and_weaknesses: Pros
1.The symbol description of the manuscript is relatively detailed.
2.The manuscript comprehensively considers various function settings, and gives relatively tight results.
3.The results of this manuscript are compared with the results of many previous works, and the authors show the situations where these results are better in detail.

Cons
1.The coefficient of Theorem 1 cited in this manuscript is slightly different from that in the reference [6].
2.In Appendix D1.1, Lemma D.1 does not mention the precondition of  which is written in the subtitle. So what is this precondition for?
3.At the beginning of the proof of Theorem 2 (line 71 in Appendix) and Theorem 3 (line 223 in Appendix) in this manuscript, the nonexpansiveness of projection operator is used. Whether the nonexpansiveness needs to be proved?

In summary, I believe this paper is interest. It provides some tighter stability bounds and generalization bounds for meta learning. 
questions: 1. For the upper bound of the uniform argument stability in Theorem 3 in line 259 of the manuscript, there is not the prove of it in Appendix. Similarly, the upper bound in line 267 of the manuscript is also not proved.
2. In line 293 of the manuscript, the authors show the result of Theorem 1 in reference [8] is  and , that is, the bound is , which is the same as the bound of Theorem 5 in this manuscript. Why does the authors think the result of this manuscript is better that that in reference [8]?

limitations: It seems no potential negative societal impact, sine this paper just considers theoretical properties of meta learning.
review_title: null

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: summary: 
This paper studies stability and generalization in meta-learning. Specifically, it develops matching upper and lower bounds for non-smooth convex loss function with Holder continuous subgradients, as well as smooth convex and smooth nonconvex functions.

The paper also provides generalization bounds for both independent and dependent episode environments. It shows that in the independent episode environment, the generalization bound of $O(1/\sqrt{n})$ is nearly optimal. And it can achieve $O(1/n)$ with an additional curvature (Polyak-Lojasiewicz) condition of the loss function.

strengths_and_weaknesses: **Strengths**

1. This is the first work that captures the effect of dependent episodes in generalization ability, which explains the empirical discovery that meta learning trained with independent episodes generalizes better than with dependent episodes.

2. The consideration of the weakest curvature condition, Polyak-Lojasiewicz condition, instead of the strong-convexity condition for O(1/n) rate of generalization is interesting.

3. This work develops stability of meta learning for both smooth and non-smooth loss functions. And conduct experiments with examples in both conditions to verify their theorems.

4. The paper provides matching upper and lower bounds for stability to show the upper bound is tight. 

**Weaknesses**

1. The comparison to [8,16] is not clear, which is the most relevant papers that also provide stability-based generalization bounds for meta learning.

2. The techniques to obtain stability in non-smooth convex loss are not new as it is already established in single-level problems [30]. And the technique for lower bound is also not new. The paper directly assumes continuity or smoothness or convex assumptions for the outer level function w.r.t. the meta parameter w, therefore, the analysis of single-level ERM can be directly applied without many challenges that are uniquely caused by the bi-level (compositional) structure of the problem.


3. The authors sometimes exchange the notions of “transfer error” and “generalization gap” in the paper. For example, in lines 302, 322, and 344, Table A.2, should the “transfer error” be the “generalization gap”?

4. The stability bound in Theorem 4 requires step sizes $\eta_j = O(\frac{1}{j})$, while the convergence of a smooth nonconvex loss function for compositional or bilevel problems requires outer level step size is at least $\eta_j = O(\frac{1}{\sqrt{j}})$ (see e.g. [1,2,3]). What is the step size used for the experiments presented in Section 6, where both the training error and generalization gap converge? This phenomenon should receive more explicit discussions.


5. Since the experiment settings belong to a non-convex non-smooth loss function, it is not covered by the theoretical results that include smooth convex, smooth non-convex, and non-smooth convex functions. It would be better to conduct some simulations with the loss functions under the Assumptions used in the theoretical results to verify the theoretical rates more explicitly. Therefore, the experiments in Section 6 do not serve the purpose of verifying the theoretical claims. The observation that a non-smooth non-convex loss function has similar convergence rates in the generalization gap as the smooth non-convex loss function suggests further study and should be pointed out clearly in the paper.

6. Some discussions are not clear to me, as detailed in “Questions”. 

[1] Closing the gap: tighter analysis of alternating stochastic gradient methods for bilevel problems

[2] On the Convergence Theory of Gradient-Based Model-Agnostic Meta-Learning Algorithms

[3] Theoretical Convergence of Multi-Step Model-Agnostic Meta-Learning



questions: **Major comments**

1. Questions regarding Table A.2

* Why in Table A.2, there is no comparison with [8,16], which is the most relevant paper that also provides stability-based generalization bounds for meta learning?

* In Table A.2, what is the difference between \gamma_n and \beta_n should be stated more clearly. For example, the uniform stability definitions in those papers are the same or not? If they are the same, why don’t you use the same notation?

* In Table A.2, the last column should be generalization gap bounds instead of transferring error bounds as it does not explicitly include the dependence of the training error \hat{er}(\cdot).


2. Questions regarding the new uniform stability notion

* Definition 2 is a stronger notion of uniform stability compared to single level problems and the definition in [8,16] for meta learning, since it requires changing both K points in the training set and q points in the test set. Why is it necessary to define the uniform stability of meta learning in this way instead of just changing one point in the training or test set?

* Though the new transfer error bound is sharper, it requires the stronger uniform stability definition in Definition 2. Therefore it is not a very fair comparison with existing works such as [8].

3. Questions regarding the notation A(S)(S)

* The notation A(S)(S) is a bit confusing to me, what is the output of hypothesis A(S)(S) should be stated clearly. Is it the per-task (e.g. for the i-th task) hypothesis or the meta model hypothesis (w)? 

* Does this S belong to S or it can be any set S? Since I see A(S)(S), A(S)(S^{tr}), and A(S)(S^{tr}_i).

4. Questions regarding remark 1

* In Remark 1, line 236-237, how does Theorem 2 show the importance of good embedding to generalization? To show this, I would expect a term in Eq. (4) that is directly related to the representation or embedding error. I think the authors need to elaborate more on this point.


**Minor comments**

1. Should line 130: $|\partial f(u,z) - \partial f(v,z)| be \|\partial f(u,z) - \partial f(v,z)\|$ instead?

2. What is S^{tr} in Eq. (2) and line 163, is it $S^{tr} = \{ S^{tr}_i\}_{i=1}^n$ or is it just a general notation of S^{tr}_i?

3. In line 163-164, why is S ~ D^m and S ~ D_{\tau} at the same time?

4. In this paper, if I understand correctly, the number of episodes is equal to the number of tasks in meta training. This should be stated more clearly at the beginning of the paper, for example, move Algorithm 1 to the main text as it is important to understand the settings of the analysis.

5. Should line 161-162: $\mathbf{D}_{\tau}$ be  $\mathbf{D}_{\tau}^m$?

6. It would be more interesting to add additional experiments on real-world data such as for few-shot image classification tasks.

7. It would be better if the authors could add a theoretical curve of the generalization gap v.s. the number of tasks in Figure 1 and Figure 2.

8. In Remark 1, line 232-234, it is stated that [29, 30] have stability bounds that depend on the empirical risk, which I do not agree since they obtain dependence on either the population risk or the expected empirical risk, which is not directly the empirical risk minimized during optimization without expectation over the data sample and algorithm. Therefore, their theoretical results do not imply small training error leads to a small generalization error.

9. Grammar

* Line 160: as follow -> as follows 

* Line 423: stability notations -> stability notions
 

limitations: n/a
review_title: null

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: summary: This work provides a comprehensive stability analysis of gradient-based modern meta-learning algorithms, i.e. that use Support/Query (S/Q) splits of the task dataset for meta-training. In particular, the authors provide matching upper and lower stability bounds for  convex loss functions with $(\alpha, G)$-Holder subgradients and for smooth functions. The bounds show that in the non-smooth convex case, meta-learning algorithms are inherently less stable than in the smooth convex case. In particular, the lower bound in the non-smooth case is vacuous. In the smooth case, the bounds are sharper than previous analysis. Furthermore, they also develop a near-optimal generalization upper bound in high probability, which shows the advantage of S/Q training compared to  empirical risk minimization (ERM). With the additional PL curvature condition, the authors derive a faster generalization bound. Finally, they derive  bounds for the case where the  episodes have a dependency relation encoded in a graph. Experiments on a synthetic regression problem with L1 and L2 loss validate the theoretical findings.
strengths_and_weaknesses: Strengths:
+ Original and significant results on S/Q meta-learning. In particular, I am not aware of lower bounds for this setting.
+ Clearly written.

Weaknesses:
- Some incorrect and not novel claims. (See Question 1 and 2)
- The case with vacuous lower-bound is not analyzed in the experiments.

**Update after the discussion with the authors**

The authors properly addressed my main concerns by updating the manuscript. Therefore I increase the score from 6 to 7
questions: Major question and comments.
1. Theorem 6 does not contain a valid bound since in the RHS it has $(1+ \eta) er$ instead of just $er$. From the analysis we can see that this result follows from [12, Theorem 1.2], which specifies that it is useful only when the empirical error is small, which might happen when dealing with overparameterized neural networks. The correct fast bound is [12, Theorem 1.1] which bounds the excess risk instead of the generalization error. I think this should be clarified and claims should be modified accordingly.
2. The advantage of S/Q meta-learning over ERM has already been shown by [8]. I think readers might mistakenly think that this is a new result of the paper. I suggest removing this fact from the claims in the introduction and possibly cite [8] in Remark 6.
3. Proof of Theorem 5 uses Lemma E.1 in the appendix, which should be equivalent to [5, Corollary 8]. However, such corollary is only an upper bound, the lower bound is derived in the subsequent section of [5]. I think this should be clarified and the proof should be expanded.
4. I suggest the authors either include log terms inside $O()$ or use $\tilde{O}(\cdot)$.


Minor questions and typos:
1. Looking at [6, Theorem 12], I think you should replace $\gamma$ with $2\gamma$ in the bound of Theorem 1.
2. Addiction -> addition.
3. Theorem 1 corresponds to [8, Theorem 2], not [8, Theorem 1] 
4. In Remark 6 “m=1 in few-shot learning”. If m=1 is impossible to split the dataset in support and query. At least should be m=2 but in practice is larger than that.

References:

[5]  O. Bousquet, Y. Klochkov, and N. Zhivotovskiy. Sharper bounds for uniformly stable algorithms. In Conference on Learning Theory (COLT), pages 610–626, 2020.

[6] O. Bousquet and A. Elisseeff. Stability and generalization. Journal of Machine Learning Research (JMLR), 2:499–526, 2002.

[8] J. Chen, X. Wu, Y. Li, Q. LI, L. Zhan, and F. Chung. A closer look at the training strategy for modern meta-learning. In Conference on Neural Information Processing Systems (NeurIPS), pages 396–406, 2020.

[12] Y. Klochkov and N. Zhivotovskiy. Stability and deviation optimal risk bounds with convergence rate o(1/n). In Conference on Neural Information Processing Systems (NeurIPS), 2021.




limitations: The authors adequately discuss the limitations of the analysis in Remark 5.
review_title: null

Meta-review: metareview: The reviewers and AC are in agreement that this paper is a solid work, and its contributions are significant. The theoretical results of this paper advance the theory of meta-learning, and, in particular, the provided generalization guarantees are strong. All reviewers were satisfied with the responses provided by the authors and even one of the reviewers increased their score. Overall, this is a good paper and my recommendation is "Accept".

AC
confidence: Certain
Decision: Accept