Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 5: Marginally below the acceptance threshold
review_content: summary: The paper studies bilevel optimization problems, more precisely hyperparameter optimization (HO).
It aims at understanding the generalization behavior of algorithms used to solve the latter.
In HO, a validation loss (typically prediction mean squared error on left out data) is minimized with respect to some hyperparameters (eg, regularization strength)
subject to the constraint that the parameter/hypothesis (eg the regression coefficient) minimize an inner loss (depending on the hyperparameter) on a training data.


main_review: Cross validation coupled with grid search is a classical procedure to solve HO, but scales badly with the number of parameters to tune.
Recently the focus has shifted to 1st order, gradient based methods, based either on implicit or iterative differentiation in the inner problem to compute the gradient of the outer loss with respect to the hyperparameter.

Some bilevel algorithms overfit to the validation set (even if it is never seen in the inner problem).
To understand this, the paper presents a notion of uniform stability on the validation set when HO is solved with stochastic gradient descent.
The paper also proposes to regularize both the inner and outer optimization problems to avoid overfitting of 1st order bilevel algorithms.

Clarifications : 
- it seems to me that there is a confusion between cross validation (a formulation of the bilvel optimization problem where the outer cost is the average over folds of performance on left out data) and grid search (applicable to any HO problem, where the hyperparameter space is discretized). The authors tend to use CV when they mean grid search, this should be fixed (since, for example, CV can be solved with 1st order methods) 
- how is the Lipschitzness assumption on the Loss in thm 2 valid ? For a simple ridge regression, as a function of lambda, can it be lipschitz without bounding the coefficients ? the strong convexity assumption also seems unverified in practice. Can you exemplify some losses which enter into your framework ?
limitations_and_societal_impact: .
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: In this paper, the authors provide a stability and generalization analysis for bilevel optimization (based on unrolled differentiation, i.e., iterative differentiation via backpropagation) and cross validation (CV) like grid search or random search for hyperparameter optimization. They provide excess uniform stability bounds on validation data  for both UD and CV under certain assumptions, and show that for UD, the stability bound has a scaling of $T^\kappa/m$, where $T$ is the total number of outer iterations and $m$ is the number of validation samples. For CV method, they show that the stability bound scales with $\sqrt{\frac{\log T}{2m}}$. In the appendix, the authors also show that the empirical risk (different from the stability metric) for CV method suffers from a curse of dimensionality. The authors provide experiments showing that UD methods are easier to overfit than CV methods when increasing the number $T,K$ of iteration numbers and a regularization can help to improve the generalization of UD methods.
main_review: In this paper, the authors provide a stability and generalization analysis for bilevel optimization (based on unrolled differentiation, i.e., iterative differentiation via backpropagation) and cross validation (CV) like grid search or random search for hyperparameter optimization. They provide excess uniform stability bounds on validation data  for both UD and CV under certain assumptions, and show that for UD, the stability bound has a scaling of $T^\kappa/m$, where $T$ is the total number of outer iterations and $m$ is the number of validation samples. For CV method, they show that the stability bound scales with $\sqrt{\frac{\log T}{2m}}$. In the appendix, the authors also show that the empirical risk (different from the stability metric) for CV method suffers from a curse of dimensionality. The authors provide experiments showing that UD methods are easier to overfit than CV methods when increasing the number $T,K$ of iteration numbers and a regularization can help to improve the generalization of UD methods. My detailed comments are given as below.

Pros: 
1.	Bilevel optimization and hyperparameter optimization are both  important and timely topics recently, and this paper provides some theoretical investigation on the stability and generalization in these two areas. 
2.	The comparison between UD (i.e., gradient-based bilevel optimization methods) and CV (such as random search methods) is a good step to help people understand their differences. 
3.	The authors provide a theoretical justification on the tradeoff on $K$ and $T$ (i.e., the overfitting and underfitting for different choices of $K,T$)  found by Franceschi et al., 2018.
4.	The experiments support the theoretical results to certain degree. 

However, I have several concerns about this submission. 

Cons:
1.	My first concern is the tightness of the results. For UD methods, it seems to that the stability bounds increase exponentially with the number $K$ of the inner gradient steps, and such a large dependence is not verified via lower bounds or experiments. It seems to me the authors derive such a dependence by using the recursive updates of gradient descent combined with smoothness of the inner loss functions (this is why the base number is $1+\eta\gamma_{\varphi}$ in the worst case). However, for the case when the inner loss has refined structure, i.e., convexity or strong convexity, I guess the bound may not increase with $K$ (if this is true, the claims on the tradeoff on $K$ should be rephrased depending on the geometry of the inner loop). Therefore, I first hope there are some comments or justification on the tightness of such exponential dependences and also wish the authors can check whether such dependences still hold for convex or strongly-convex inner loop (which are also interesting and common geometries for bilevel optimization). 
2.	My second concern is that the assumptions made in this paper are a little bit restrictive. For example, they require the objective function value to be bounded, which is a strong assumption given unbounded feature space (e.g., this is hard to hold even for linear classifier). In addition, they require the loss function is second- and third-order continuously defendable, and hence such assumptions will eliminate the widely used ReLU activation (indeed the authors motivate their assumptions using neural networks with smooth operators).  
3.	This paper is poorly structured and not very easy to follow. For example, in Theorem 2 and Theorem 3, it is not clear to me what is $\mathcal{G}_{\hat\theta}$ and what is $g(\lambda,S^{tr})$. In addition, the assumptions are made on both $l$ and $\varphi_i$, and it takes me some time to figure out $l$ is a loss over validation data and $\varphi_i $ is a loss on the $i^{th}$ training data sample. Why do not use $l_i$ for the $i^{th}$ validation data for a consistence?  I may miss something, but it takes me much time to search for the definitions of such notations. I suggest that the authors recall the definitions of them before the statements of the results.
4.	For the results on CV, Mohri et al., 2018 derived the high-probability bounds, whereas this paper provides a bound in expectation. Based on my experience, high-probability bounds are often more harder than expectation bounds. The authors state that their expectation bounds involve new developments of independent interest. For this reason, I highly suggest that the authors can sketch the novelty of their bounds, and how their bounds differ from the existing high probability ones. This will strengthen this paper a lot. 
5.	For the experiments, I have one question. The authors set a learning rate 0.3 for the inner loop for UD method, which may be a little bit large. A large learning rate may prevent the inner iterates from approaching the optimal point. Therefore, I suggest that the authors choose a smaller learning rate, e.g., 0.1, 0.05, or 0.01 to verify this phenomenon. 

In summary, I am not very excited about the results in this paper, because the findings are not new and the techniques such as the uniform stability are a little bit standard. In addition, the results and presentation need more time to be enhanced or revised to reach the bar of NeurIPS. If the authors can provide a good response, especially the tightness check via any lower bound, I am open to increase my score.  

limitations_and_societal_impact: Yes
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: This paper is an early theoretical work on generalization of hyperparameter optimization (HO) task. It analyzes the generalization error on validation of unrolled differentiation (UD) and cross validation (CV) methods in expectation and compare them. Besides, a regularized UD algorithm is designed in this paper. Detailed experiments are performed to compare CV with UD, and UD is claimed a better method. Given experimental results show that the regularized UD algorithm improves the performance. 
main_review: Originality: This paper is an early theoretical work on generalization of HO task, giving expectation generalization error bound of UD and CV (previous works always focus on optimization). The differences are clearly demonstrated and related work are cited.

Quality: The submission is technically sound and the claims are well supported. Stability theory is a commonly used method when analyzing generalization error, the method is used appropriately. However, the high probability bound is always better than the expectation bound, this paper does not analyze the high probability one and the reason is not clear. Moreover, the generalization error is applied on validation rather than the testing set, the reason is not clear and the comparison is not given (the explanation given in Section 4.1 is the comparison between training and validation from my perspective).

Clarity: The submission is clearly written and well organized. However, the paper claims that Theorems 2 and 3 give a generalization gap in an order of $O(T^k/m)$ or $O(f(K))$, where $f$ is an increasing function w.r.t $K$. But what kind of $f$ is not explained in the main paper (e.g. $e^K$ and $\sqrt{K}$ are quite different). Moreover, the paper does not explain why the results (both CV and UD) is not related to $n$, the number of training samples, which is an important term from my perspective.

Significance: Via stability theory, the paper gives $O(1/m)$ and $O(\sqrt{1/m})$ generalization gap in expectation for UD and CV, respectively. And the idea can be extended to more related situations. However, previous work gave a high probability $O(\sqrt{1/m})$ generalization gap for CV ([25] as cited in the paper), so it seems the result given in this paper (on CV) is not a better one, or even worse (because we often consider that high probability bounds are better than expectation ones). 
limitations_and_societal_impact: See the above main review
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: This paper analyzes, using stability, the generalization properties of a gradient-based bilevel optimization algorithm for hyperparameter optimization.

Bilevel optimization consists in two nested optimization problems: the outer problem aims at minimizing an objective function where some of the variables are a solution of the inner problem. This work considers the setting where inner and outer objectives are the training and validation losses respectively, which arises in hyperparameter optimization. The authors analyze the bilevel optimization algorithm (named UD) consisting in $T$ (stochastic) gradient descent steps on the validation set (consisting of $m$ samples) with gradient computed using unrolling differentiation, i.e. using automatic differentiation to compute the derivative of $K$ steps of (stochastic) gradient descent steps on the train set. This algorithm is used to solve a large variety of machine learning problems like meta-learning or hyperparameter optimization, but its theoretical generalization properties are largely unknown.

This work presents uniform stability bounds which lead to generalization guarantees for stochastic UD without any convexity assumption on the bilevel loss functions. More specifically, it shows a $\tilde O(T^{\mathcal{k}}/m)$ or $\tilde O(f(K))$ (f increasing) upper bound on the absolute value of the expected difference between the true and the empirical risk, where the expectation is taken w.r.t. the algorithm and the training and validation sets.  It further shows a $O(\sqrt{\log(T)/m})$ bound for cross-validation (CV). The analysis shows that with sufficiently low $T$ and $K$ and sufficiently high $m$ UD can be better than CV but also that when $T$ and $K$ are too high UD might suffer more from overfitting on the validation set, a phenomenon which has been observed in practice. The authors also explain how adding L2 regularization in the outer and inner levels can help improve stability. Empirical results on feature learning and data reweighting are in line with the theoretical findings.

main_review: #### **Originality**
1. The work extends the results of  [12] to the bilevel setting and is one of the first if not the first that studies stability and generalization properties of bilevel problems. The authors could consider [A, B], which study unrolled differentiation (UD) from the optimization point of view with a strongly-convex inner problem. This additional assumption could improve the dependence on the number of inner iterations $K$ in the bound. There are several works concerning bilevel optimization rates with strongly-convex inner problem (see [C] and subsequent works citing it). Maybe the authors could compare their work with some of them.

#### **Significance**
2. Many machine learning problems like meta-learning, hyperparameter optimization, neural architecture search, can be cast into the bilevel framework. Overfitting the validation set can be a serious issue for gradient based bilevel methods and this work is a first step in understanding its theoretical properties. The authors shows interesting generalisation bounds but should discuss more about the exponential dependences on the number of iterations (see 4 and 5 in the quality section).

#### **Quality**
3. The theoretical results seem correct. I checked most of the proofs although I am not very familiar with stability results. 

4. I think the authors should explicitly write, in the introduction and later on, that the UD bound (in particular $f$) has an exponential dependence on $K$  and maybe provide the complete UD bound combining theorem 1, 2 and 3 in a corollary or a theorem. I think this exponential dependence should be discussed as a limitation of the approach.

5. The authors present (In the supplementary) a result on the stability of gradient descent  in the non-convex setting which suffers an exponential dependence on the number of steps $T$ and $K$ while enjoying the same $1/m$ dependence as stochastic gradient descent on the number of examples in the validation set $m$. I think it would add value to the paper to bring this result to main part and discuss it more, since in practice the bilevel gradient might be computed using the full or a big part of the validation set (in the experiments, a minibatch is half of the validation set). This is because the validation is usually smaller than the training set and the validation loss is computed $T$ times while the train loss  is computed $T \times K$ times. Also the authors may also discuss how this result contrasts with what stated in [12] at page 26, where the authors could not prove stability results for gradient descent.

6. The experiments show that UD overfits to the validation set with sufficiently high $K$ and $T$, while CV does not suffer from this issue. However, all the experiments have a large number of hyperparameters, hence due to the course of dimensionality, CV does not even achieve a competitive validation accuracy. Experiments with 1 or 2 hyperparameters that show CV in the overfitting regime could be a worthy addition  to the paper. Another valuable addition would be a figure showing the difference between test and validation loss, which could provide a more direct comparison with the theoretical bounds.

#### **Clarity**
7. The main paper and the proofs in the supplementary are quite easy to follow and clearly written.

#### **Final Score**
I am giving a score of 6. I am willing to increase the score if the authors take into account some of the comments in the quality section.

#### **Additional Comments**

1. (1) what does the or mean? Maybe it can be clearer even in the introduction.
2. Line 95: I found it a bit unclear the explanation of differentiable neural architecture search.
3. Line 164: $s(\ell)$ not defined.
4. Line 175 Also assumption 1 is needed.
5. Line 194: reference to existing CV results could be more precise. The high probability bounds for CV start at page 68 of [25].
7.Omniglot setting is a bit unclear (lines 262-267): $lambda$ is the linear layer at the input or output of the network?

#### **Post Rebuttal**
The authors  claimed to make several modifications to the next version of the paper to address most of my concerns. I am thereby increasing the score form 6 to 7.

#### **References**

[12] Moritz Hardt, Ben Recht, and Yoram Singer. Train faster, generalize better: Stability of stochastic gradient descent. In Proceedings of The 33rd International Conference on Machine Learning, pages 1225–1234. PMLR, 2016.

[25] Mehryar Mohri, Afshin Rostamizadeh, and Ameet Talwalkar. Foundations of machine learning. MIT press, 2018.

[A]  R. Grazzi, L. Franceschi, M. Pontil, and S. Salzo, “On the iteration complexity of hypergradient computation,” 2020.

[B]   K. Ji, J. Yang, and Y. Liang, “Bilevel optimization: Nonasymptotic analysis and faster algorithms,” 2020.

[C]  S. Ghadimi and M. Wang, “Approximation methods for bilevel programming,” 2018

limitations_and_societal_impact: The authors discussed part of the limitations in the conclusion section of the paper. Other limitations, which I addressed in the main review, are the exponential dependence on $K$ and the exponential dependence on $T$ for gradient descent. 

The authors did not wrote a section addressing societal impact and wrote as a reason that the work is mostly theoretical. I agree with the authors.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: In this paper, the authors study bilevel programming for hyperparameter optimization, which involves an outer level optimization on hyperparameter and an inner optimization on hypothesis. Unlike most of existing studies focusing on optimization, the authors study the generalization by using the tool of algorithmic stability. The authors introduce a new stability measure called uniform stability on validation, which considers the sensitivity of the algorithm w.r.t. a change of example in the validation dataset. The authors show the connection between generalization and the proposed algorithmic stability. If the outer level algorithm is SGD, the authors develop uniform stability under some smoothness and Lipschitz assumptions, which were shown to hold under some regularity assumptions on training loss and validation loss. Experimental results are also reported to show the performance of a bilevel programming method (UD) w.r.t different parameters and its comparison with CV.

main_review: The application of stability analysis to study generalization bounds of bilevel programming is interesting. The paper is clearly written and easy to follow. The proofs seem to be correct.

My major comment is on the novelty of the analysis. As far as I can see, the arguments in proving Theorem 1 and Theorem 2 follow the existing analysis. In particular, Theorem 2 is proved in the same way as Theorem 3.8 in [12]. The form of stability bounds are also similar and there seems not to be enough novelty in the theoretical analysis. Furthermore, the learning rate there requires to be of the order of $O(1/t)$, which may be very small to get a reasonable low empirical risk. Indeed, it can be shown that SGD with the learning rate $O(1/t)$ requires $O(\exp(1/\epsilon))$ iterations to get the excess empirical accuracy $O(\epsilon)$. This huge number of iterations limits the application of Theorem 2 in practice to understand the performance of Algorithm 1.

In Theorem 3, the authors show the Lipschitz continuity and smoothness of $\ell(\lambda,g(\lambda,S),z)$ under some regularity conditions. However, the Lipschitz & smoothness parameter have an exponential dependency on $K$. Therefore, the learning rate $\eta$ should be very small to get a small Lipschitz & smoothness parameter. Since the authors consider a constant learning rate $\eta$, the learning rate should be of the order of $1/K$ for a moderate Lipschitz & smoothness parameter. This rate may make the algorithm converge slowly in practice. 

Algorithm 1 (Line 8) requires to compute $\nabla_{\lambda}\hat{R}^{val}(\lambda,\theta_K^t(\lambda,S^{val}))$. It is not clear to me how to compute this gradient since $\theta_K^t(\lambda,S^{val})$ also depends on $\lambda$. The complexity of computing this gradient may grow as an increasing function of $K$. It would be helpful to explain this gradient computation and its associated complexity.

Minor comments:

There is a superfluous ( in the statement $\gamma=O((())$ in Theorem 3.

Ref [11] and [12] are the same


-------------------------
After authors' response

Thank you for the response. After reading other reviews and response, I would keep my score.
limitations_and_societal_impact: There seems to be no limitations and societal impact.
review_title: null

Meta-review: The paper  is among the early theoretical work on studying the stability and generalization of hyperparameter optimization (HO) task in contrast to the optimization properties widely studied in the literature.  It used a notion of uniform stability for validation to get the rate of $O({T^\kappa\over m})$ in comparison to $O({\sqrt{\log T}\over m})$ using CV approaches. There are various interesting discussions on the implication of the comparisons on the possible superior performance of UD in HO framework. Experiments validate the theoretical findings. The reviewers' concerns/questions on the tightness of the exponential dependence on K , possible improvement of the bounds if the inner loss is convex or strongly, and other questions on the experiments are well responded in the rebuttal. 
Decision: Accept (Poster)