Venue: ICLR 2023 Conference

Reviews:

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: This paper studies the generalization of bilevel optimization problems which are widely used in machine learning, e.g., meta-learning, hyper-parameter optimization, and 
reinforcement learning. Specifically, the authors conduct a thorough analysis of the generalization of first-order (gradient-based) methods for the bilevel optimization problem. 
Technically, in comparison with the previous work, the (advanced) algorithmic stability tool is used to give a high probability generalization bound which improves the previous best one $\sqrt(n)$ 
to $\log(n)$, where $n$ is the sample size. Besides, some particular settings (e.g., strongly-convex-strongly-convex (SC-SC)) are also involved. Finally, experimental results are provided to support the 
theoretical results.

strength_and_weaknesses: ## Strength

1. Overall, this paper is very well written.
2. This paper is sound since the claims are supported by formal theoretical results. Besides, experimental results are also provided to corroborate the theory. 
3. The proofs seem reasonable and right although I have not checked them line-by-line.
4. It clearly discusses the differences with related work, especially the previous work[1*].




## Weaknesses

1. The expression about "generalization error" is not suitable. In this paper, the authors define the bilevel generalization error as the difference between the population risk and empirical risk. It is strange because in statistical learning theory, 
the generalization error usually refers to the population risk and the related expression in this paper can be confusing. I suggest the authors use the generalization gap, just as in previous work[1*].  
2. While this paper refines the generalization analyses over previous work[1*], few additional insights can be offered to explain the practical phenomena and design effective learning algorithms in comparison with previous work[1*].
3. I do not agree with the expression about the limitation of the previous work[1*] (mainly in Remark 4). [1*] made an assumption that the update of $y$ in the inner level after the reinitialization will not be affected by the value specified for $x$, which may have a gap with the practical algorithms.
But, the main reason is to decouple the variables $x$ and $y$, and the proof is technically right.
4. As discussed in 3, how the authors deal with the case when updating the outer variable $x$ but the inner variable $y$ can be dependent on the $x$ and the hyper-gradient is used. Please give more explanations and discussions. 



[1*]Fan Bao, Guoqiang Wu, Chongxuan Li, Jun Zhu, and Bo Zhang. Stability and generalization of bilevel programming in hyperparameter optimization. NeurIPS 2021
clarity,_quality,_novelty_and_reproducibility: Please see the section 'Clarity, Quality, Novelty And Reproducibility'.

summary_of_the_review: In summary, this paper conduct refined generalization analyses for the bilevel optimization problems over previous work via advanced stability techniques. But, some necessary discussions and revisions should be made.
review_title: null

final_score: rating: 3: reject, not good enough
review_content: summary_of_the_paper: This paper studies the generalization of bilevel optimization algorithms in the framework of algorithm stability. It focuses on two algorithms, namely, single-time scale (SSGD) and two-time scale (TSGD) with first-order stochastic gradient updates. 

Different from prior work, the algorithms considered do not require reinitialization in the inner loop. Experiments on data reweighting and meta-learning are provided to show how the generalization performance changes w.r.t. the number of iterations.

strength_and_weaknesses: **Strengths**

* The paper is clearly written and easy to follow.
* The paper considers two algorithms SSGD, and TSGD without reinitialization in the inner loop, which are different from prior works and are important in bilevel optimization. It fills the gap in the current literature.

**Weaknesses** 

**1. The bound is loose.** 

1.1)	The stability bounds derived in this paper seem to have worse dependence on the outer iteration number $K$ than [Bao et al. 2021]. It has exponential dependence in $K$ in the worst case in this paper while only polynomial dependence on $K$ in [Bao et al. 2021].

1.2)	No discussion of the tightness of the bound is provided in either theoretical or empirical form.

1.3)	It is contour-intuitive that when $f$ and $g$ are strongly convex, the stability has worse rate on $K$ (exponential) than when $f$ $g$ are non-convex (polynomial). I believe the bounds of SC-SC and C-C cases are not tight.

**2. Incorrectness** 

2.1) Summary of the most relevant work [Bao et al. 2021] is incorrect. 

a) My understanding for paper [Bao et al. 2021] is that it assumes the compositional function $f(x, \hat{y}(x, D_{m2}); \xi)$ w.r.t. $x$ is Lipschitz continuous, which also has a dependence in number of iterations $T$ in the inner loop. Therefore, the summary in Table 1 for UD[Bao et al. 2021] which does not depend on $T$ is not accurate. In addition, [Bao et al. 2021] provides the results of convex case in the appendix.

b) What is $\nabla f$? The comparison of UD[Bao et al. 2021] and TSGD in appendix A is not correct as the gradient of $x$ in the outer loop is not the same based on my understanding. Because it requires second-order information for UD[Bao et al. 2021].

2.1) Outer update/reference of SSGD and TSGD is incorrect. 

a) In Algorithms 1 & 2, the update for outer parameter $x$ does not take gradient w.r.t. function $\hat{y}$? Could you add references to the two algorithms analyzed in this paper, for single timescale and two-time scale, separately? 

b) If the update for outer parameter $x$ does not take gradient w.r.t. function $\hat{y}$, it is not the same as the algorithm for some two-time scale methods referenced in this paper such as [Ghadimi & Wang, 2018], [Ji et al. 2021] as they require the second-order information of the loss during the update of $x$.

**3. Lack of clarity**
 
a) How does the results in this paper compare with existing stability analysis on specific bilevel problems such as minmax problems and meta-learning?

b) Although different algorithm stability concepts are defined, only uniform-stable in expectation is used for the main theorems in Section 4. Why do you need to define uniform stability with probability $1-\delta$ in Definition 4, (a)?

c) Why do you need Theorem 1 (c)? Theorem 1 (c) is not used in Section 4.

d) The proofs are not clear. Some proofs of the TSGD case are omitted due to claimed similarity of the SSGD case (see pages 20-21). However, I suggest that you include proof for TSGD case and omit the SSGD case.

**3.2 Minor comments**

a) In Theorem 1 (c), what is $e$?

b) In Theorem 1 (c), A is uniform stable with probability at least $1 - \delta$?

c) Throughout the paper, why do you use $\nabla_y g$ for the update of $y$  and $\nabla f$ for the update of $x$ but not $\nabla_x f$ ?

d)	The notation $G$ is used for both inner population risk and update function, please use different notations to avoid confusion.

clarity,_quality,_novelty_and_reproducibility: **Clarity**

The writing is clear. However, some of the claims are not well supported. See Weaknesses – Incorrectness. And Weaknesses-Lack of Clarity. 


**Quality**
The paper deals with an important problem of algorithm stability in bilevel optimization. The paper and the proof is clearly written. Experiments on meta-learning and data reweighting are conducted.


**Novelty**
Though prior works exist that consider algorithm stability of bilevel learning, this paper considers two different algorithms without reinitialization in the inner loop.
summary_of_the_review: This paper considers generalization in terms of algorithm stability for two bilevel algorithms SSGD, and TSGD, without reinitialization in the inner loop, which is different from prior works.

However, the TSGD algorithm described in the paper is different from what is referenced. Since the papers referenced all require second-order information in the update of outer parameters. But this paper does not require second-order information.

Also the summary in Table 1 is not reasonable for prior work [Bao et al. 2021], since it should also depends on $T$, the number of inner iterations.

For the above reasons, I recommend rejection.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: Authors propose to study the stability of estimators based on bilevel optimization problems. Using the notion of algorithmic stability, authors managed to bound the generalization error. This analysis is proposed for usual bilevel optimization algorithms (single-timescale and two-timescale SGD).
strength_and_weaknesses: Major concerns:
- Even though authors provide a long list of points comparing their work against Bao et al 2021, I am not sure I understood the difference:
  - (1) "Their study is only for the hyper-parameter" I do not see how the class of problem you consider is more general
  - (4) Could you comment on why exactly their analysis needs a renitilization of the inner parameters?
  - (5) I agree, but you do not especially seem to provide extensive experimental results
Could you comment on this?

- **Experimental part** Except from the sentence "The trend of generalization error in terms of K and T matches with our analysis in Theorem 4", there are no links between the experiments and the proposed analysis.
Would it be possible to obtain more quantitative results than "a trend"?
I am not asking for SOTA experiments, but it would be nice to have quantitative experiments validating the provided theorems. For instance, would it be possible to provide experiments in the setting of Theorem 4? to compute the value of $\beta$, and check its variation as a function of T and K?

clarity,_quality,_novelty_and_reproducibility: Paper is rather clear and original
summary_of_the_review: Contribution seems interesting and new. I would appreciate if the distinction with previous work was clearer, and if experiments validate more the data
review_title: null

final_score: rating: 1: strong reject
review_content: summary_of_the_paper: This work studies the generalization of bilevel optimization problem. Specifically, this work analyzes the SSGD and TSGD bilevel optimization algorithms. This work adopts the notion of uniform stability on validation in expectation [1], and analyze the stability coefficient $\beta$ to build a generalization bound of the two algorithms. This work also introduces the notion of argument stability (a special case of uniform stability), and provides a high probability bound for almost surely uniform stable algorithms. 
strength_and_weaknesses: **Strength**

This paper makes the following extensions compared to [1]:

1. This paper considers the stability bound of SSGD and TSGD algorithms, which is not studied in [1]

2. This paper also studies the case where the outer level problem is convex or strongly convex.

3. This paper provides a better high probability bound from $O(\beta \sqrt{m_1})$ to $O(\beta \log m_1)$ compared to [1]. The improvement is significant.



**Weakness**

There are some improper or incorrect claims on the prior work [1], upon which this work is built:

1. [1] studies the UD algorithm, and it seems that the author has some misunderstanding on the UD algorithm. Indeed, UD view $y$ produced by the inner level optimization as a function of $x$, i.e., $y(x) = H_{T-1} \circ H_{T-2} \circ \cdots \circ H_{0} (x)$, where $H_t$ represents the gradient update in Line 6 of Algorithm 3. When UD optimizes $x$, it would use the gradient $\nabla_x f(x, y(x); D_{m_1}) = \nabla_x f(x, y; D_{m_1}) + \nabla_x y(x) \nabla_y f(x, y; D_{m_1})$, instead of $\nabla_x f(x, y; D_{m_1})$ in Line 8 of Algorithm 3. This means that UD would backward through the optimization trajectory of $y$. However, as shown in Remark 4, the author thinks UD treat $y(x)$ as an argument indpendent $x$, which is an incorrect claim. As a result, the claim "However, there are some technical flaws
in their analysis..." in Section 1, and the claim "...and thus cannot be treated as an argument independent of $\lambda_t'$, which is misused and causes technical flaws in their proof subsequently" in Remark 4 are both incorrect.

2. Since this work consider totally two different algorithms SSGD and TSGD other than UD. Perhaps it is less proper to state "for the SC-SC and C-C cases with single-timescale update strategy we significantly improve the generalization bounds compared with [1]", since the algorithm already changes.

3. This work claims that "[1] only considers a general setting for inner function" in Section 1. However, [1] also considers convex and strongly convex inner functions. These results are provided in Appendix C in [1].

4. This work claims that the bound of [1] "is quite loose in some cases" in Section 1. However, [1] constructs a worst case (see Appendix B in [1]) to prove that the bound of [1] is tight if no extra assumptions of inner or outer functions are provides. Besides, [1] also gives tighter bound when convex or strongly convex assumptions are made. Therefore, the claim that the bound of [1] "is quite loose in some cases" is improper.

5. This work claims that [1] has an undesirable issue "the stability for general bilevel optimization is still unknown". However, the problem formulation of bilevel optimization (see Eq.(2)) in this work is exactly the same as [1]. Therefore, the range of bilevel optimization considered in this work is not more general than [1] in theory, and this undesirable issue remains in this work. As a result, the claim "our work is the first thorough generalization analysis for general bilevel optimization problem" is improper.

Other questions:

5. The notion of argument stability is a special case of uniform stability, and it is obvious that a $\beta$-argument-stable (in expectation) algorithm is also a $L_f \beta$-uniform-stable (in expectation) algorithm. Is it necessary to introduce this additional notion?

6. Theorem (1) c assumes the algorithm $A$ is uniform stable almost surely. This assumption looks quite strong for random algorithms, since it requires for all possible randomness in the algorithm, changing a data point in the validation set won't cause the loss to change more than $\beta$. Can SSGD and TSGD satisfy this assumption? It seems that the author does not verify this assumption for the studied SSGD and TSGD algorithms, and does not establish high probability bounds for the two algorithms.

7. In Talbe 1, the TSGD with C-C setting has a $O(T^K/m_1)$ bound, and TSGD with NC-NC setting has a $O(T^{1-\kappa_6} K^{\kappa_6} / m_1)$ bound. The former is much looser. Why a stronger assumption leads to a looser bound?

Typos:

8. In the second line below Eq.(2), $g(x, y(x); \xi_i)$ shoud be $g(x, y; \xi_i)$.

9. In the third line in the seoncd paragraph of Section 2.2, $f(x, y(x); \xi)$ should be $f(x, y; \xi)$.

10. In Line 7 of Algorithm 2, $x_k^t$ should be $x_k$.

[1] Stability and Generalization of Bilevel Programming in Hyperparameter Optimization

[2] Train faster, generalize better: Stability of stochastic gradient descent
clarity,_quality,_novelty_and_reproducibility: There are some typos in paper and should be double checked. The technique in this work is relatively less novel, since its technique mainly follows [1,2].

summary_of_the_review: It is nice to study the generalization of SSGD and TSGD bilevel optimization algorithms, since they are commonly used. However, many parts in this work need to be revised before being ready for publishment. For example, the author should carefully check the prior work [1], and revise claims on this work; the bound of TSGD in Table 1 should be checked and discussed; the writting should be double checked.
review_title: null

Meta-review: metareview:_summary,_strengths_and_weaknesses: 
This paper studies the generalization performance of bilevel optimization problems.
The paper considers two algorithms SSGD, and TSGD without reinitialization in the inner loop, which are different from prior works and are important in bilevel optimization. It is easy to follow, yet the novelty appeared not significant enough.

justification_for_why_not_higher_score: 
There are some improper or incorrect claims on the prior work, upon which this work is built.
The technique in this work is lacks novelty, since its technique mainly follows papers mentioned in the reviews. 
justification_for_why_not_lower_score: A well written paper.
Decision: Reject