Stability and Generalization of Bilevel Programming in Hyperparameter Optimization
Authors: Fan Bao
Guoqiang Wu
Chongxuan Li
Jun Zhu
Bo Zhang
Venue: NeurIPS 2021 Poster (2021)
Keywords: hyperparameter optimization
generalization
bilevel optimization
stability

Abstract: The (gradient-based) bilevel programming framework is widely used in hyperparameter optimization and has achieved excellent performance empirically. Previous theoretical work mainly focuses on its optimization properties, while leaving the analysis on generalization largely open. This paper attempts to address the issue by presenting an expectation bound w.r.t. the validation set based on uniform stability. Our results can explain some mysterious behaviours of the bilevel programming in practice, for instance, overfitting to the validation set. We also present an expectation bound for the classical cross-validation algorithm. Our results suggest that gradient-based algorithms can be better than cross-validation under certain conditions in a theoretical perspective. Furthermore, we prove that regularization terms in both the outer and inner levels can relieve the overfitting problem in  gradient-based algorithms. In experiments on feature learning and data reweighting for noisy labels, we corroborate our theoretical findings.

Stability and Generalization of Bilevel Programming in Hyperparameter Optimization
Fan Bao", Guoqiang Wu", Chongxuan Li', Jun Zhu', Bo Zhang Dept. of Comp. Sei. & Tech., Institute for AI, Tsinghua- Hainguaa-Huawei Joint Center for AI BNRist Center, State Key Lab for Intell. Tech. & Sys., Tsinghua University, Beijing, China bf19@ wwinglu.tinggua.... iet.iaaaeduccc. gguoqiangw990, chongxuanli 1991 @@@@ @gmail.com, (deszj, deszb) @ essinghua.edu.cn
Abstract
The cradient-basedl bilevel programming framework is widely used in hyperpa- rameter optimization and has achieved excellent performance empirically. Previous theoretical work mainly focuses on its optimization properties, while leaving the analysis generalization largely open. This paper attempts to address the issue by presenting an expectation bound w.r.t. the validation set based on uniform stability. Our results can explain some mysterious behaviours of the bilevel programming in practice, for instance, overfitting to the validation set. We also present an ex- pectation bound for the classical cross-validation algorithm. Our results suggest that gradient- -ased algorithms can be better than cross- vols-daaiiotion under certain conditions thcoretical perspective. Furthermore, we prove that regularization terms in both the outer and inner levels can relieve the overfitting problem in gradient- basee algorithms. In experiments on feature learning and data reweighting for noisy labels, we corroborate our theoretical findings.
Introduction
Hyperparameter optimization (HO) is common problem arising from various fields including neural architecture search [24] 8), feature learning [10), data reweighting for imbalanced or noisy samples [33 37 9 35), and remi-supervised learning [14). Formally, HO seeks the hyperparameter- hypothesis pair that achieves the lowest expected risk on testing samples from an unknown distribution. Before testing, however, only set of training samples and a set of validation ones are given. The validation and testing samples are assumed to be from the same distribution. In contrast, depending on the task, the underlying distributions of the training and testing samples can be the same 24 10 or different [33].
Though various methods 11 have been developed to solve HO (See Section for comprehensive review), the bilevel progrumming (BP) 6,
32 [0] framework is a natural solution and has achieved excellent performance in practice (24). BP consists of two nested search problems: in the inner level, it seeks the best hypothesis (c.g., a prediction model) on the training set given specific configuration of the hyperparameter (c.g., the model architectures), while in the outer level, seeks the hyperparameter (and its associated hypothesis) that results in the best hypothesis in terms of the error on the validation set.
'Equal contribution. G. Wu is now at School of Software, Shandong University and C. Li is now at Gaoling School of AI, Renmin University of China. The work was done when they were at Tsinghua University. 1 *Correspondigg author.
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

Generally, it is hard to solve the BP problem exactly, and several approximate algorithms have been developed in previous work. As a classical approach, Cross-validation (CV E can be viewed as an approximation method. It obtains a finite set of hyperparameters via grid search [31 or random search [2] as well as a set of the corresponding hypothesises trained the inner level, and selects the best hyperparameter-lyy potthess pair according to the validation error. CV is well understood in theory [31 36] but suffers from the issue of scalability [T)] Recently, alternative algorithms (2] 10
I1 29 35 based on unrolled differentiation (UD) have shown promise on tuning up to millions of hyperparameters. In contrast to CV, UD exploits the validation data more aggressively: it optimizes the validation error directly via (stochastic) gradient descent in the space of the hyperparameters, and the gradient is obtained by finite steps of unrolling in the inner level.
Though promising, previous theoretical work IO 39 35 of UD mainly focuses on the optimization, while leaving its generalization analysis largely open. This paper takes first step towards solving and aims to answer the following questions rigorously:
Can we obtain certain learning guarantees for UD and insights to improve it?
When should we prefer UD over classical approaches like CV a theoretical perspective?
Our first main contribution is to present notion of uniformly stable on validation (in expectation) and an expectation bound of UD algorithms (with stochastic gradient descent in the outer level) on the validation data as follows:
|Expected risk of UD- BDD-Emg EEmprrical risk of UD on validation S Ô T and Ō (1+ m1p)
(
)
)2k
(1)
where T and K are the numbers of steps in the outer level and the inner level respectively, K E (0,
is a constant, 1) is the learning rate in the inner level, 7op is a smoothness coefficient of the inner loss, m is the size of the validation set and S means the inequality holds in expectation. As detailed in Section[4 [.1] our results not only present the order of the important factors in the generalization gap but also explain some mysterious behaviours of UD in practice, for instance, the trade-off on the values of T and K [10].
Our second main contribution is to systematically compare UD and CV from the perspective of
generalization in Section 4.2 Instead of using the existing high probability bounds of CV (see
Theorem 4.4 in 31 we present an expectation bound of CV for a direct comparison to Eq. ① as
follows -
(V llo
Expected risk of CV - Empirical risk of CV on validation| S O
(2)
On the one hand, Eq. and Eq. 2 suggest that with a large T CV has a much lower risk of
overfitting than UD. On the other hand, the dependence of Eq. 2 on m is o (vm) //))
which is worse than that of UD. Furthermore, as discussed before, probably UD has much lower validation risk than CV. Indeed, we show that CV with random search suffers from the curse of dimensionality. These analyses may explain the superior performance of UD 241 especially when we have a reasonable choice of T. a sufficiently large m and sufficiently high- nigh-dimensional hyperparameter space.
Our third main contribution is to present regularized UD algorithm in Section 4.3 and prove that both a weight decay term of the parameter in the inner level and that of the hyperparameter in the outer level can increase the stability of the UD algorithms. Thus, the generalization performance will probably improve if the terms do not hurt the validation risk too much.
Finally, experiments presented in Section 6 validate our theory findings. In particular, we reproduce the mysterious behaviours of UD (c.g.. overfitting to the validation data) observed in [10], which can be explained via Eq. (T. Besides, empirically compare UD and CV and analyze their performance via Eq. ① and Eq. Further, we show the promise of the regularization terms in both levels.
WWiile CV can refer to general class of approaches by splitting a training set and a validation set, we focus on grid search and random search and denote the two methods as CV collectively.
"We not find a strong dependency of CV on K in both the theory and practice.
'Every hyperparameter considered corresponds to loop for the inner level optimization, which is the computational bottleneck in HO. Therefore. for fairness, assume UD and CV share the same I' by default.

---

2 Problem Formulation
Let Z, ④ and A denote the data space, the hypothesis space and the hyperparameter space respectively.
8: A x θ x - (a, bj is a bounded loss functior and its range is s(E) = b a.
6
Given a hyperparameter À E A, hypothesis @ θ and distribution D on the data space Z, R(A, 0, D) denotes the expected risk of X, 0 on D, ie.. R(A, 0, D) = E [e(A, 2)]. Hyperparam- eter optimization (HO) seeks the hyperparameter- hyperprrameter--yotteeiss pair that achieves the lowest expected risk on testing samples from an unknown distribution.
Before testing, however, only a training set 5t of size n and a validation set 5 of size m are accessible. As mentioned in Section[]] we consider general HO problem, where the distribution of the testing samples De is assumed to be the same as that of the validation ones Deal but can differ from that of the training ones D In short, we assume D Dec, but do not require D D Given hyperparameter À e A, hypothesis 0 E ④ and the validation set gwal Rooal (X, 0, S
denotes the empirical risk of X, 0 on Swal, i.e., fe (2,0, = + - e(A, 0, 2g The empirical
risk on training is defined as R (Ar 1 Σ p. 0 2T)). where si can be a slightly modified
(e.g., reweighted) version of é for i-th training sample"
Technically, an HO algorithm A is a function mapping Str and Sual to hyypeparameeee-hyyoohhsss pair, i... A : Z" x d + A x θ contrast, a randomized HO algorithm does not necessarily return deterministic hyperparameeler-yypothssss pair but more generally a random variable with the
outcome space e.
Though extensive methods 17 have been developed to solve HO (See Section S for comprehen- sive review), the bilevel programming 66
32 10 is a natural solution and has achieved excellent performance in practice recently [24] It consists of two nested search problems as follows:
(S Sual)
arg min Arnal (A, O*, (A, Swal), where 0* (X,,
arg min Re O*
AEA
lEB
Outer level optimization
Inner level optimization
(3)
In the inner level, it seeks the best hypothesis on Str given a specific configuration of the hyperpa- rameter. In the outer level, it seeks the hyperparameter X (Str SSaat) (and its associated hypothesis 0r (S"rr ,, S*r) that results in the best hypothesis in terms of the error on gual_ Eq. (3) is sufficiently general to include large portion of the HO problems we are aware of, such as:
set of network archi- tecture, let 0 be the parameters in the neural network defined by the coefficients, and let / be the cross-entropy loss associated with 0 and X. Namely, L(2, 0 2) = (E)h),.(z)))) where h-) is a neural network with architecture À and parameter 6.
Differential Architecture Search (4 Let À be the coefficients
Feature Learning [TO] Let X be a feature extractor, let 0 be the parameters in a classifier that takes features as input and let I be the ross-entroppy loss associated with and Namely, 1(A, 8, 2) = (h( y). where hx(-) is the feature extractor and (-(-) is the classifier.
Data Reweighting for Imbalanced Noisy Samples 351
Let À be the coefficients of the training data, let 0 be the parameters of a classifier that takes the data as input, let 7 be the cross-entropy loss associated with 0. Namely, 1(0,2) 2) = CE 2), where ha(-) the classifier and is irrelevant to A. The empirical risk on the training set is defined through reweighted version of the loss (r((), 0, 2;) a ().))(0,, z;). where a-) is the sigmoid function and X; is the coefficient corresponding to z;-
'This formulation also includes the case where the loss function is irrelevant the hyperparameter. Also Appendix discussion of the boundedness assumption of the loss function. Whiie in many tasks such as differential architecture search (24) and feature learning 10 yo is just the same l, we distinguish between them to include tasks where pii and are different, such data reweighting (35).
3

---

Algorithm 2 Cross-validation for hyper- parameter optimization
Algorithm Unrolled differentiation for hyperparameter optimization
1: Input: Number of steps T and K;
1: Input: Number of steps T and K; initialization 6g and Ao; learning rate scheme and
initialization { and (0)) -=
learning rate scheme 1/
2: Output: The hyperparameter dud and hypothesis and
2: Output: The hyperparameter dev
3: for = 0) to T 1 do
and hypothesis Oew
4: 0 0g
3: for to K do
5: for k = 0 to K - do
6: 0+1 0% 1]++1 V Pe ( 0, 0,5 Ne=
4: 0 k+1
f
0%
M&+1 Vo (Ae, 00
7: end for
8: Act1 + de aut1 X (A, fx (ual) 12=2
5: end for
6: t f arg min Roal (de, Staal) 1StST 7: return dy and 0
9: end for
return 'T and 0%
10:
Approximate the Bilevel Programming Problem
In most of the situations (e.g., neural network as the hypothesis class 24 ), the global optima of both the inner and outer level problems in Eq. ( are nontrivial to achieve. It is often the case to approximate them in certain way (e.g., using (stochastic) gradient descent) as follows:
A(str, sual)
arg min Rral (A, Staal) where ((A,stT) argmin R (2,0,5 mEG
XEA
Approximate outer level optimization
Approximate inner level optimization
Here (A,, St)) can be deterministic or random. In this perspective, we can view the unrolled differentiation (UD) and cross-validation (CV) algorithms as two implementation of Eq. ④
solve Eq. via performing finite steps of gradient descent in both levels. Given a hyperparameter, the inner level performs K updates, and keeps the whole computation graph. The computation graph is a composite of K parameter updating functions, which are differentiable with respect to X, and thereby the memory complexity (K). As a result, the corresponding hypothesis is function of the hyperparameter. The outer level updates the hyperparameter a single step by differentiating through inner updates, which has (K) time complexity, and the inner level optimization repeats given the updated hyperparameter. Totally, the outer level updates T times. Formally, it is given by Algorithm | where we omit the dependency of X and f on gual and St simplicity.
Unrolled differentiation. The UD-based algorithms p 10
29 35
In some applications
24 10 n. and m can be very large and we cannot efficiently calculate the T In this case, stochastic gradient descent (SGD) can be used to update the
gradients in Algorithm hyperparameter (corresponding to line in Algorithm 1 as follows:
d a a Rual (A, (x)0%(()),, (2))))2
(5)
where zj is randomly selected from Swal Similarly, we can also adopt SGD when updating the hypothesis and then all intermediate hypothesises are random functions of À and Str
Cross-validation. CV is a classical approach for HO. first obtains a finite of hyperparameters. which is often subset of A, via grid search [11 or random search [2 Then, it separately trains the inner level to obtain the corresponding hypothesis given a hyperparameter. Finally, selects the best cerpaaameter-hypothe
pair according to the validation error. It is formally given by Algorithm 2 where we use gradient descent to approximate the inner level (i.e., line 4). We can also adopt SGD to update the hypothesis.
'I our experiments, the hyperparameter is too digeeninnsio to perform grid search, and thus random search is preferable. Nevertheless, they will be shown have similar theoretical properties.

---

In terms of optimization, CV searches over prefixed subset of A in discrete manner, while UD leverages the local information of the optimization landscape (i.e., gradient). Therefore, UD is more likely to achieve a lower empirical risk on the validation data with the same T. In the following, we will discuss the two algorithms from the perspective of generalization.
Main Results
We present the main results below for clarity, and the readers can refer to Appendix A for all proofs.
4.1 Stability and Generalization of UD
In most of the recent HO applications descent (SGD) is adopted for its scalability and efficiency. Therefore, we present the main results on UD with SGD in the outer level here
10 24
that we are aware of, stochastic gradient
Recall that a randomized HO algorithm returns a random variable with the outcome space x θ in general. To establish the generalization bound, we define the following notion of uniform stability validation in expectation.
Definition 1. randomized HO algorithm A is 3 B-uniformly stable on validation in expectation if for all validation datasets Swal, S'val vall E 7 such that Swot, S'val differ in at most one sample, we have
WSS E E V2 E E, [(AAStr, S E(A(Str s'vol), S 3.
Compared existing work [.S], Definition considers the expected influence of changing one validation sample on randomized HO algorithm. The reasons are two-folded. On the one hand, in HO, the distribution of the testing samples assumed to the same as that of the validation ones but can differ from that of the training ones [33], making it necessary to consider the bounds on the validation set. On the other hand, classical results CV suggest that such bounds are usually tighter than the ones on the training set (31)
If a randomized HO algorithm is 3-uniformly stable on validation in expectation, then we have the following generalization bound.
Theorem 1 (Generalization bound of a uniformly stable algorithm). Suppose a randomized HO algorithu A is 3-uniformly stable on validation in expectation, then
E A. (D*r"", (Daatt [R(A(Str goal), Dral) frcal (A Seal), sual) B.
Note that this is an expectation bound for any randomized HO algorithm with uniform stability. We now analyze the stability, namely bounding B. for UD with SGD in the outer level. Indeed, we consider general family of algorithms that solve Eq. 44 via SGD in the outer level without any restriction on the inner level optimization in the following Theorem 2
Theorem 2 (Uniform stability of algorithms with SGD in the outer level). Suppose 0 is random function a function space G3 and 4 Z". Vz Z. 4g E 9g. E(), g(>, Stt), 2) as a function
s(t) of A is L-Lipschitz continuous and 7-Lipschitz smooth, let e S TL and solving Eq. (4) with T steps SGD and learning rate ar in the outer level is B-uniformly stable on validation in expectation with
c(1 c(111/mm))) <111//m))+4 Then,
2cI2 m
(1
(s(()
-1) +1)+
3
K
2e1,2
which is increasing w.E.t and 7, (Recall that s())
is the range of the loss.)
Theorem doesn't assume a specific form of ô. Indeed, UD instantiates â as the output of SGD or GD in the inner level. For SGD, the corresponding G3 is formed by iterating over all possible random indexes and initializations in Ô. For GD, the corresponding G3 is only formed by iterating over all
"See Appendix D for the results on UD with GD in the outer level. The generalization gap of UD with GD in the outer level has exponential dependence on I' and K, and has the same 1/m dependence SGD.
5

---

possible initializations in 8, since GD uses full batches. We analyze the constants L and y appearing in 8 of UD, which solves the inner level problem by either SGD or GD. given the following mild assumptions on the outer loss l and the inner loss vi-
Assumption 1. A and are compact and convex with non-empty interiors, and Z is compact.
Assumption 2. E(x,0, ) E (S2), where Q is an open set including A x θ x Z (i.e., E is second order continuously differentiable on St).
Assumption 3. (), 0,2) (12), where Qi is an open set including A x θ x Z (i.e., pps is third order continuously differentiable on St).
Assumption 4. (p:(2,0, z) is -Lipscchi smooth as function of for all
S S n, E 2 and
E A (Assumption [ and Assumption 3 imply such a constant "ip exists).
Theorem 3. Suppose Assumption 3 SGD or GD with learning rate 7,, then VS E Z Vz E Z. Vig E Gg. ((), g(,, Str), as a function
4 hold and the inner level problem is solved with K steps
of X = (((1 + 17,) Lipschitz continuous and Y ((L + )2k) Lipschitz smooth.
Generally, a neural network composed of smooth operators satisfy all assumptions. We notice that the continuously differentiable assumption in Assumption [ and Assumption 3 does not hold for ReLU, However, we argue that there are many smooth approximations of ReLU including Softplus, Gelu [16), and Lipswish [5], which satisfy the assumption and achieve promising results in classification and deep generative modeling.
Remark:
1 Theorem 2 and Theorem 3 we obtain an expectation bound of UD that depends on the number of steps in the outer level T. the number of steps the inner level K and the validation sample size Roughly speaking, its generalization gap has an order of
Combining the results in Theorem
[T or Ör (1+77))) ). In Appendix B, we construct a worst case where the Lipschitz constant L in Theorem 3 increases at least exponentially w.r.t. K. According to Theorem / the stability bound also increases exponentially w.r.t. K in the worst case. Besides, if we further assume the inner loss Pi is convex or strongly convex, we can derive tighter generalization gaps. Indeed, the dependence on K of the generalization gap is O(3)) in the convex case and (11 in the strongly convex case. Please see Appendix C for a complete proof.
Our results can explain some mysterious behaviours of the UD algorithms in practice 10. According to Theorem and Theorem 3l very large values of K and T will significantly decrease the stability of UD (i.e., increasing 3), which suggests a high risk of overfitting. On the other hand, we use very small T and K, the empirical risk the validation data might be insufficiently optimized, probably leading to underfitting. This trade-off on the values of K and T' has been observed in previous theoretical work [10. which mainly focuses on optimization and does not provide formal explanation. We also confirmed this phenomenon in two different experiments (See results in Section 6.2).
As for the number of validation data m, the generalization gap has an order of O (+)), which is satisfactory compared to that of CV presented in Section
4.2 Comparison with CV
CV is classical approach for HO with theoretical guarantees, which serves as a natural baseline of our results on UD in Theorem[] [ Theorem 2 and Theorem However, existing results on CV (see Theorem 4.4 in (31) are in the form of high probability bounds, which are not directly comparable to ours. To compare under the same theoretical framework to obtain meaningful conclusions, we present an expectation bound for CV as follows.
Theorem 4 (Expectation bound of CV), Suppose Str ~ (Dtry", Suat ~ (Dualy ym and Sir and Sual are independent, and let A (Str, Syal) denote the results of CV as shown in Algorithm 2 then
log T
E R(A 6M (StT.
( Soaal) Doal - R RA (0 ) 1 s(O)
2m
Technically, the expectation bound of CV is proved via the property of the maximum of a set of subgaussian random variables (see Theorem 1.14 in [44), which is distinct from the union bound used in the high probability bound of CV (see Theorem 4.4 in (31). In Appendix G.2, we also verify
the O( / (.) dependence of the expectation bound empirically.

---

On one hand, we note that the growth of the generalization gap w.r.t T's is logarithmic in Theorem 4 which is much slower than that of our results on UD. Besides, it does not explicitly depend on K. Therefore, sharing the same large values of K and T. CV has much lower risk of overfitting than
(( / which is worse than that of UD. Furthermore, as discussed in Section 3] probably UD has a much lower validation risk than CV via exploiting the gradient information of the optimization landscape. Indeed, we show that CV with random search suffers from the curse of dimensionality (See Theorem 7 in Appendix E). Namely, CV requires exponentially large T w.r.t. the dimensionality of the À to achieve a reasonably low empirical risk. The above analysis may explain the superior performance of UD (24), especially when we have reasonable choice of I' and K, sufficiently large and a sufficiently high-dimensional hyperparameter space.
UD. On the other hand, the dependence of Theorem 4 on is O
4.3
The Regularized UD Algorithm
Building upon the above theoretical results and analysis, we further investigate how to improve the stability of the UD algorithm via adding regularization. Besides the commonly used weight decay term on the parameter in the inner level, we also employ similar one on the hyperparameter in the outer level. Formally, the regularized bilevel programming problem is given by:
X (S*r Smal) = arg min Rmal() (X, 0 (A, St"), Smaa)) + 2
4 |1
AEA
Regularized outer optimization
V/ where 0 (1, arg min Rd (A,0,
2
11012
(6)
BE
Regularized inner level optimization
where y and V are coefficients of the regularization terms. Similar to Algorithm| I we use UD to approximate Eq. (6). We formally analyze the effect of the regularization terms in both levels (See Theorem and Theorem 3 in Appendix A). In summary, both regularization terms can increase the stability of the UD algorithm, namely, decreasing 3 in certain way. In particular, the regularization in the outer level decreases x Theorem [ while the regularization in the inner level decreases and y in Theorem 3 Therefore, we can probably obtain better generalization guarantee by adding regularization in both levels, assuming that the terms do not hurt the validation risk too much.
Related work
Hyperparamter optimization. In addition to UD 9 10
11
29 35 and CV 2 31 analyzed
in this work, there are alternative approaches that can solve the bilevel programming problem in
HO approximately. including implicit gradient [1 32 26 27). Bayesian optimization [38 21 and
hypernetworks (25 (28). Implicit gradient methods directly estimate the gradient of the outer level problem in Eq. 3 which generally involves iterative procedure such as conjugate gradient (2)
and Neumann approximation (26) to estimate the inverse of Hessian matrix. [27] also shows that the identity matrix be good approximation of the Hessian matrix. Bayesian optimization [3
21 views the outer level problem of Eq. (4) as a black-box function sampled from a Gaussian process (GP) and updates the posterior of the GP as Eq. (4) is evaluated for new hyperparameters. Hypernetworks [25 28 learn a proxy function that outputs an approximately optimal hypothesis
29 35) also has variants which are more time and 35 proposes a faster version of UD by truncating the differentiation w.r.t. the hyperparameter, while proposes memory-saving version of UD by approximating the trace of inner level optimization in a linear interpolation scheme.
given a hyperparameter. Besides, UD 9 10
memory efficient 355
To our knowledge, the analysis of HO in previous work mainly focuses on convergence [10] 35
and unrolling bias [39] from the optimization perspective. The generalization analysis is largely open, which can be dealt with stability framework in principle. In fact, in addition to UD 9 10
analyzed in this work, Theorem ii also potential tool for HO algorithms discussed above [
26 27
38
21
25
28
29
35 upon which future work can be built.
Bilevel Programming. The bilevel programming is extensively studied from the perspective of optimization. 12 13 20 analyze the convergence rate of different approximation methods (c.g.. UD
7

---

and implicit gradient) when the inner level problem is strongly convex. [99] analyze the complexity lower bounds of bilevel programming when the lower level problem is strongly convex. [8] analyze the convergence rate of bilevel programming under the setting of meta-learning.
Stability. The traditional stability theory 3 builds generalization bound of learning algorithm by studying its stability w.r.t. changing one data point in the training set. It has various extensions.
7 [5] extend the stability for randomized algorithms. 7 focuses on the random perturbations of
the cost function. [15] focuses on the randomness in SGD and provides generalization bounds in
expectation. Our bound for UD solved by SGD is also in expectation. In such cases, as claimed by [15), "high probability bounds are hard to obtain by the fact that SGD is itself randomized, and thus concentration inequality must be devised to account for both the randomness in the data and in the training algorithm". The stability notion is also extended to meta-learning (30) 4 where the stability analyzed w.r.t. changing one meta-dataset to bound the transfer risk on unseen tasks. This work differs from previous extensions in that it considers the stability w.r.t. changing one data point in the validation set, which leads a generalization bound w.r.t. empirical risk on the validation set.
Experiments
We conduct experiments to validate our theoretical findings, which are three-folded as follows:
1. We reproduce the mysterious behaviours of UD (e.g., overfitting to the validation data) observed in (10) and attempt to explain them via Theorem[aand Theorem
2. We empirically compare UD and CV and analyze their performance from the perspective of the expectation bounds in Theorem 2 and Theorem
3. We show the promise of the regularization terms in both levels validate Theorem 2 and Theorem 3 in Appendix A.
6.1 Experimental settings
In our experiments, consider two widely used aasks, learning [10] and data reweighting for noisy labels [35. Please refer to Section for the formulation of the two tasks.
In feature learning, we evaluate all algorithms the Omniglot dataset [2 following [0). Omniglot consists of grayscale images, and we resize them to 28 x 28. The images are symbols from different alphabets. We randomly select 100 classes and obtain training, validation and testing set of size 500, 100, and 1000 respectively. À represents the parameters in a linear layer of size 784 - 256 following the input x. 0 represents the parameters in MLP of size 256 128 100 to predict the label y. We employ a mini-batch version of SGD in both levels of UD with a learning rate 0.1 and batch size 50.
In data reweighting, we evaluate all algorithms on the MNIST dataset 23 following 335 MNIST consists of grayscale hand wwrtten digits of size 28 x 28. We randomly select 2000, 200, and 1000 images for training, validation and testing respectively. The label of a training sample is replaced by uniformly sampled wrong label with probability 0.5. À represents the logits of the weights of the training data, and 0 represents the parameters in an MLP size 784 + 256 > 10. We employ a mini-batch version of SGD in both levels of UD with batch size 100. The learning rate is 10 in the outer level and 0.3 in the inner level.
By default, CV shares the same inner loop as UD for a fair comparison in both settings. We tune learning rates and coefficients of the weight decay on another randomly selected set of the same size as the validation set. To eliminate randomness, we average over 5 different runs and report the mean results with the standard deviations in all experiments. Each experiment takes at most 10 hours in one GeForee GTX 1080 Ti GPU.
6.2 Trade-off on the values of T and K in UD
Figure I presents the results of UD the feature learning (FL) and data reweighting (DR) tasks, with preseetsss
different values of K and T. On the one hand, in both tasks, UD with a large K (e.g., 256 in FL) and a large T overfits the validation data. Namely, the validation loss continues decreasing while the testing loss increases. On the other hand, small value of K (c.g.. I in FL) and T will result in
8

---

2.5
K-16
K=]
K-16
1.4
entropy
1.5
K-128
K-04
K-256
K-04
1-8
256
entropy
1.4
K-512
0.5
5000 (a) Validation loss (FL)
2000
6000
0000
8000
10000
2000
60.00
00.0
8000
15000
1950
20:00
1000
4000
5000
1830
20:00
1000
4000
(b) Testing loss (FL)
(c) Validation loss (DR)
(d) Testing loss (DR)
Figure 1: Results of UD in feature learning (FL) and data reweighting (DR). In both settings, the performance of UD is sensitive to the values of K and T. We plot the generalization gap in Appendix G.1.
underfitting to the validation data. The trade-off on the values of and agree with our analysis in Theorem and Theorem 3
We also try a smaller learning rate in the inner level and get similar overfitting phenomenon of a larger K. For instance, learning rate
UD (see results in Appendix G.3). In such case, of = 0.1 requires
1024 inner iterations to overfit. This can explained by our Theorem 3
which implies that smaller requires larger K to make the generalization gap unchanged.
6.3 Comparison between CV and UD
1.3
K=16
Ke16
entropy
K-64
K-64
K=120
K=128
K-512 1.3
4.6
K=
Km256
1.3
1.0
2000
6000
6000
8000
10000
2000
6000
6000
8000
15000
1030
2000
3000
4000
5000
1000
2000
1000
4000
5000
(a) Validation loss (FL)
(b) Testing loss (FL.
(c) Validation loss (DR)
(d) Testing loss (DR)
Figure 2: Results of CV in feature learning (FL) and data reweighting (DR). We do not observe the overfitting phenomenon CV in all settings. We plot the generalization gap in Appendix G.I.
presents the results of CV in the feature learning (FL) and data reweighting (DR) tasks. First, unlike UD, we not observe the overfitting phenomenon when using large T and K. This corroborates our analysis in Theorem g which claims that the generalization gap of CV grows logarithmically w.r.t. T and does not explicitly depends on K, Second, we note that the validation loss of CV is clearly higher than that of UD in Figure I which may explain the relatively worse testing loss of CV. Lastly, in FL, the validation loss of CV does not decrease clearly using up to 10,000 hyperparameters. This is because the dimensionality of the hyperparameter is around 200,000, which is too large for CV to optimize, as suggested in Theorem
Figure 2
Appendix E.
We also compare between CV and UD with smaller number of hyperparameters (see results in Appendix G.4). this case, the validation losses of UD and CV are comparable and both algorithms fit well on the validation data. However, UD overfits much severely, leading to worse testing loss than CV. The results agree with our theory.
6.4 Effects Regularization in Both Levels UD
Figure 3 presents the results of the regularized UD algorithms where the weight decay term is added in the outer (referred to as Reg-outer) or the inner level (referred to as Reg-inin Reg-inner). We observe that in most of the cases, both Reg-outer and Reg-inner can individually relieve the overfitting problems of UD. Further, within range, the larger the coefficients of weight decay terms, the better results. Such behaviours confirm our Theorem 2 and Theorem 3 in Appendix A. We note that if the regularization too heavy, for instance, v 0.1 Panel (b) Figure 3 the optimization might be unstable. This suggests another trade-off on determining the values of a and

---

u=0
4.0
U-00
8.0
H-16-3
0-16-2
V-1o33
entropy
3
entroyy
2-
entropy
entropy
0.8
1.5
H-1e 2
0.8
2.0
2000
60.00
6000
8060
10000
2000
60.00
80.0
8000
15000
1950
20.00
1000
4000
5000
1950
20:00
1000
4000
5000
(a) Reg-outer (FL)
(b) Reg-inner (FL)
(c) Reg-outer (DR)
(d) Reg-inner (DR)
Figure 3: Testing loss of the regularized UD algorithms in feature learning (FL) and data reweighting (DR). Reg-outer and Reg-inner refer to adding regularization individually in the outer and inner levels of UD respectively. We set K 256 in FL and K 512 in DR. In most of the cases, both Reg-outer and Reg-inner can relieve overfitting in UD but overall there is no clear winner.
H-0 V-le-2
H-0, v-0
U-1e-2
Cross entropy
8.5
3e-3 y=
p- 9-16-2
p-16-3 v=16.2
1.5
p-1o-2 u-0
p=o, velei2
p-1e-2 v=16-2
Cross entropy
2.0
p- 1e-4,
3e-5,
1e-5.
v=1o-2
entrogy
0.8
3e-5,
v-1e-2
v=
0.8
3.0
Cross
3.0
2000
40000
6000
8000
10000
2000
40000
6000
8000
13000
1000
2030
3000
4000
5000
1000
2000
3000
4000
5000
(a) Reg both (FL)
(b) both (FL)
(c) Reg-both (DR)
(d) Reg-Regbee both (DR)
Figure 4: Testing loss of the regularized UD algorithms in feature learning (FL) and data reweighting (DR). Reg-both refers to adding regularization both the outer and inner levels of UD. We set K = 256 in FL and K = 512 in DR. In most of the cases, Reg-both is slightly worse than the winner of Reg-outer and Reg-inner.
According to Figure 3 considering the two tasks together, there is clear winner of Reg-inner and Reg-outer overall. In fact, our Theorem 2 and Theorem 3 in Appendix A show that they influence / in incomparable ways. We further apply the two weight decay terms at the same time (referred to as Reg-both), and the results are demonstrated in Figure 4 We find that Reg-both is slightly worse than the winner of Reg-outer and Reg-inner. We hypothesize that if one of the weight decay terms can successfully relieve the overfitting problem, then adding another may hurt the final generalization performance because of higher validation loss. A deeper analysis of the issue is left as future work.
7 Conclusion
The paper attempts to understand the generalization behaviour of approximate algorithms solve the bilevel programming problem in hyperparameter optimization. In particular, we establish an expectation bound for the unrolled differentiation algorithm based on notion of uniform stability on validation. Our results can explain some mysterious behaviours of the bilevel programming in practice, for instance, overfitting to the validation set. We also present an expectation bound of the classical cross-validatin algorithm. Our results suggest that unrolled differentiation algorithms can be better than cross-valle validation in a theoretical perspective under certain conditions. Furthermore, we prove that regularization terms in both the outer and inner levels can relieve the overfitting problem in the unrolled differentiation algorithm. In experiments on feature learning and data reweighting for noisy labels, we corroborate our theoretical findings.
As an early theoretical work in this area, we find some interesting problems unsolved in this paper, which may inspire future work. First, we do not consider the implicit gradient algorithm, which is an alternative approach to unrolled differentiation and can be analyzed in the stability framework in principle. Second, the comparison between the weight decay terms in different levels is not clear yet. Third, in Theorem 2 we assume the learning rate in the outer level ( as in 15), which is gap between our analysis and the practice.
10

---

Acknowledgements
We thank Yuhao Zhou for valuable feedback on our work. This work was supported by NSFC Projects (Nos. 61620106010, 6206113600) 136001, 616211 U1811461, U19B2034, U19A2081), Beijing NSF Project (No. JQ19016). Tsinghua-Bosct Joint Center for Machine Learning, Beijing Academy of Artificial Intelligence (BAAD, grant from Tsinghua Institute for Guo Qiang. Tiangong Institute for Intelligent Computing, and the NVIDIA NVAIL Program with GPU/DGX Acceleration.
References
[1] Yoshua Bengio. Gradient-based optimization of hyperparameters. Neural computation, 12(8):1889-1900 2000.
[2] James Bergstra and Yoshua Bengio. Random search for hyper-paramette optimization. Journal of machine learning research, 13(2), 2012.
[3] Olivier Bousquet and André Elisseeff. Stability and generalization. The Journal of Machine Learning Research, 2:499-526, 2002.
[4] Jiaxin Chen, Xiao-Ming Wu, Yanke Li, Qimai Li, Li-Ming Zhan, and Fu-lai Chung. closer look at the training strategy for modern meta-learning Advances in Neural Information Processing Systems, 33, 2020.
[5] Ricky TQ Chen, Jens Behrmann, David Duvenaud, and Jörn-Herrik Jacobsen. Residual flows for invertible generative modeling. arXiv preprint arXiv: 1906.02900 2019.
[6] Benoît Colson, Patrice Marcotte, and Gilles Savard. An overview of bilevel optimization. Annals of operations research, 153(1):235-255 2007.
[7] Andre Elisseeff, Theodoros Evgeniou, Massimiliano Pontil, and Leslie Pack Kaelbing. Stability of randomized learning algorithms. Journal of Machine Learning Research, 6(1), 2005.
[8] Thomas Elsken, Jan Hendrik Metzen, Frank Hutter, et al. Neural architecture search: A survey.
J. Mach. Learn. Res., 20(55):1-21, 2019.
[9] Luca Franceschi, Michele Donini, Paolo Frasconi, and Massimiliano Pontil. Forward and reverse gradient-based hyperparameter optimization. In International Conference on Machine Learning, pages 1 1165-1173. PMLR, 2017.
[10] Luca Franceschi, Paolo Frasconi, Saverio Salzo, Riccardo Grazzi, and Massimiliano Pontil. Bilevel programming for hyperparameter optimization and meta-learning. In International Conference on Machine Learning, pages 1568-1577. PMLR, 2018.
[11] Jie Fu, Hongyin Luo, Jiashi Feng, Kian Hsiang Low, and Tat-Seng Chua. Drmad: distilling reverse-mode automatic differentiation for optimizing hyperparameters of deep neural networks. arXiv preprint arXiv: 000670011111.1111110000011 2016.
[12] Saced Ghadimi and Mengdi Wang. Approximation methods for bilevel programming. arXiv preprint arXiv: /802.02246, 2018.
[13] Riccardo Grazzi, Luca Franceschi, Massimiliano Pontil, and Saverio Salzo. On the iteration complexity of hypergradient computation. In International Conference Machine Learning, pages
PMLR, 2020.
[14] Lan-Zhe Guo, Zhen-Y Zhang, Yuan Jiang, Yu-Feng Li, and Zhi-Hua Zhou. Safe deep semi- supervised learning for unseen-class unlabeled data. In International Conference Machine Learning, pages 3897-3906. PMLR, 2020.
[15] 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.
[16) Dan Hendrycks and Kevin Gimpel. Gaussian error linear units (gelus). arXiv preprint axXiv:1606.08415,200 2016.

---

[17] Frank Hutter, Jörg Lücke, and Lars Schmidt- Thieme. Beyond manual tuning of hyperparameters. KI- Küinstliche Intelligenz, 29(4): 2015.
[18] Kaiyi Ji, Jason D Lee, Yingbin Liang, and H Vincent Poor. Convergence of meta-learning with lask-specifie adaptation over partial parameters. arXiv preprint arXiv:2006. 09486, 2020.
[19] Kaiyi Ji and Yingbin Liang. Lower bounds and accelerated algorithms for bilevel optimization. arXiv preprint arXiv: 102.03922 2021.
[20] Kaiyi Ji, Junjie Yang, and Yingbin Liang. Bilevel optimization: Convergence analysis and enhanced design. In International Conference on Machine Learning, pages 4882-4892. PMLR, 2021.
[21] Kirthevasan Kandasamy, Karun Raju Vysyaraju, Willie Neiswanger, Biswajit Paria, Christo- pher R Collins, Jeff Schneider, Barnabas Poczos, and Eric P Xing. Tuning hyperparameters without grad students: Scalable and robust bayesian optimisation with dragonfly. arXiv preprint arXiv: 1903.06694, 2019.
[22] Brenden M Lake, Ruslan Salakhutdinov, and Joshua B Tenenbaum. Human-level concept learning through probabilistic program induction. Science, 150062666:1332-1111 2015.
[23] Yann LeCun, Corinna Cortes, and CJ Burges. Mnist handwritten digit database. ATT Labs [Online]. Available: http://yann.lecu www.:....ueeee.................. coccm..co//xxb/nniist. 2, 2010.
[24] Hanxiao Liu, Karen Simonyan, and Yiming Yang. Darts: Differentiable architecture search. arXiv preprint arXiv: 18066090555 2018
[25] Jonathan Lorraine and David Duvenaud. Stochastic hyperparameter optimization through hypernetworks. arXiv preprint arXiv:1802.099 2018.
[26] Jonathan Lorraine, Paul Vicol, and David Duvenaud. Optimizing millions of hyperparameters by implicit differentiation. International Conference on Artificial Intelligence and Statistics, pages
PMLR, 2020.
[27] Jelena Luketina, Mathias Berglund, Klaus Greff, and Tapani Raiko. Scalable gradient- based tuning of continuous regularization hyperparameters. International conference on machine learning, pages 2952-292228 2960. PMLR, 2016
[28] Matthew MacKay, Paul Vicol, Jon Lorraine, David Duvenaud, and Roger Grosse. Self-tuning networks: Bilevel optimization of hyperparameters using structured best-response functions. arXiv preprint arXiv: /908,0 2019.
[29] Dougal Maclaurin, David Duvenaud, and Ryan Adams. Gradient-based hyperparameter opti- mization through reversible learning. In International conference on machine learning, pages 21 2112-2122. PMLR, 2015.
[30] Andreas Maurer and Tommi Jaakkola. Algorithmic stability and meta-learning. Journal of Machine Learning Research, 6(6), 2005.
[31] Mehryar Mohri, Afshin Rostamizadeh, and Ameet Talwalkar. Foundations of machine learning. MIT press, 2018.
[32] Fabian Pedregosa. Hyperparameter optimization with approximate gradient. In International conference on muchine learning. pages 737-746. PMLR, 2016.
[33] Mengye Ren, Wenyuan Zeng. Bin Yang, and Raquel Urtasun. Learning to reweight examples for robust deep learning. In International Conference on Machine Learning, pages 4334-4343. PMLR, 2018
[34] Phillippe Rigollet and Christian Hütter. High dimensional statisties. Lecture notes for course 185997, 813:814, 2015.
[35] Amirreza Shaban, Ching-An Cheng, Nathan Hatch, and Byron Boots. Truncated back- propagation for bilevel optimization. In The 22nd International Conference on Artificial Intelligence and Statistics, pages 1723-1732. PMLR, 2019.
12

---

[36] Shai Shalev-Shwarke and Shai Ben-David, Understanding machine learning: From theory to algorithms. Cambridge university press, 2014.
[37] Jun Shu, Qi Xie, Lixuan Yi, Qian Zhao, Sanping Zhou, Zongben Xu, and Deyu Meng. Meta-weight-net: Learning explicit mapping for sample weighting. arXiv preprini arXiv:1902.07379, 2019.
[38] Jasper Snoek, Hugo Larochelle, and Ryan P Adams. Practical bayesian optimization of machine learning algorithms. arXiv preprint arXiv:/206.220 2012.
[39] Yuhuai Wu, Mengye Ren, Renjie Liao, and Roger Grosse. Understanding short-horizon bias in stochastic meta-optimization. arXiv preprint arXiv:1803.02022) 2018.
Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's
contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes] See Section 7
(c) Did you discuss any potential negative societal impacts of your work? [No] We are not aware of potential negative impacts currently since this is theoretical work.
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes] See Section
(b) Did you include complete proofs of all theoretical results? [Yes] See Appendix A.
3. If you ran experiments..
(a) Did you include the code, data, and instructions needed reproduce the main perimental results (either in the supplemental material or as a URL)? [Yes] See https:///iithb. http:////ggttuub..oombbaaafataee com//baofff//ttbiiitt/.
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [Yes] See Section 6.1
(c) Did you report error bars (e.g., with respect the random seed after running experi-
ments multiple times)? [Yes] See all figures in Section 6
(d) Did you include the total amount of compute and the type of resources used (c.g., type of GPUs, internal cluster, or cloud provider)? [Yes] See Section 6.1
4. If you using existing assets (e.g., code, data, models) or curating/releasing
assets...
(a) If your work uses existing assets, did you cite the creators? YYss] See Section 6.
(b) Did you mention the license of the assets? [N/A]
(c) Did you include any new assets either in the supplemental material or as a URL? [N/]]
We only use existing assets.
(d) Did you discuss whether and how consent was obtained from people whose data you're using/curating? [N/A] We use public data.
(e) Did you discuss whether the data you are using/curating contains personally identifiable information offensive content? [N/A] We use public data.
5. If you used crowdsourcing conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, if applicable? [N/A]
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, if applicable? [N/A]
(c) Did you include the estimated hourly wage paid participants and the total amount spent on participant compensation? [N/A]
13


Reviews:
[{"review_id": "l0AohLcmDkn", "reviewer": "Reviewer_QRtq", "summary": "This paper analyzes, using stability, the generalization properties of a gradient-based bilevel optimization algorithm for hyperparameter optimization.\n\nBilevel 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.\n\nThis 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.\n", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "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": "", "main_review": "#### **Originality**\n1. 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.\n\n#### **Significance**\n2. 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).\n\n#### **Quality**\n3. The theoretical results seem correct. I checked most of the proofs although I am not very familiar with stability results. \n\n4. 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.\n\n5. 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.\n\n6. 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.\n\n#### **Clarity**\n7. The main paper and the proofs in the supplementary are quite easy to follow and clearly written.\n\n#### **Final Score**\nI 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.\n\n#### **Additional Comments**\n\n1. (1) what does the or mean? Maybe it can be clearer even in the introduction.\n2. Line 95: I found it a bit unclear the explanation of differentiable neural architecture search.\n3. Line 164: $s(\\ell)$ not defined.\n4. Line 175 Also assumption 1 is needed.\n5. Line 194: reference to existing CV results could be more precise. The high probability bounds for CV start at page 68 of [25].\n7.Omniglot setting is a bit unclear (lines 262-267): $lambda$ is the linear layer at the input or output of the network?\n\n#### **Post Rebuttal**\nThe 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.\n\n#### **References**\n\n[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.\n\n[25] Mehryar Mohri, Afshin Rostamizadeh, and Ameet Talwalkar. Foundations of machine learning. MIT press, 2018.\n\n[A]  R. Grazzi, L. Franceschi, M. Pontil, and S. Salzo, “On the iteration complexity of hypergradient computation,” 2020.\n\n[B]   K. Ji, J. Yang, and Y. Liang, “Bilevel optimization: Nonasymptotic analysis and faster algorithms,” 2020.\n\n[C]  S. Ghadimi and M. Wang, “Approximation methods for bilevel programming,” 2018\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "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. \n\nThe 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_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "12"}, "extra_text": {}}, {"review_id": "jTP2-gCmYQ", "reviewer": "Reviewer_AbZm", "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.\n", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "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": "", "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.\n\nMy 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.\n\nIn 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. \n\nAlgorithm 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.\n\nMinor comments:\n\nThere is a superfluous ( in the statement $\\gamma=O((())$ in Theorem 3.\n\nRef [11] and [12] are the same\n\n\n-------------------------\nAfter authors' response\n\nThank you for the response. After reading other reviews and response, I would keep my score.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "There seems to be no limitations and societal impact.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "7"}, "extra_text": {}}, {"review_id": "jHEqStkknDZ", "reviewer": "Reviewer_eAVT", "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. ", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "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": "", "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.\n\nQuality: 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).\n\nClarity: 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.\n\nSignificance: 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). ", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "See the above main review", "review_text": "", "extra_scores": {"ethical_concerns": "None", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "10hours"}, "extra_text": {}}, {"review_id": "9qE_nRXaRj9", "reviewer": "Reviewer_ZjhP", "summary": "The paper studies bilevel optimization problems, more precisely hyperparameter optimization (HO).\nIt aims at understanding the generalization behavior of algorithms used to solve the latter.\nIn HO, a validation loss (typically prediction mean squared error on left out data) is minimized with respect to some hyperparameters (eg, regularization strength)\nsubject to the constraint that the parameter/hypothesis (eg the regression coefficient) minimize an inner loss (depending on the hyperparameter) on a training data.\n\n", "questions": "", "limitations": "", "rating": 5, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "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": "", "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.\nRecently 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.\n\nSome bilevel algorithms overfit to the validation set (even if it is never seen in the inner problem).\nTo understand this, the paper presents a notion of uniform stability on the validation set when HO is solved with stochastic gradient descent.\nThe paper also proposes to regularize both the inner and outer optimization problems to avoid overfitting of 1st order bilevel algorithms.\n\nClarifications : \n- 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) \n- 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 ?", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": ".", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3 "}, "extra_text": {}}, {"review_id": "0HNqEdt6rOu", "reviewer": "Reviewer_1Yjf", "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.", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "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": "", "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.\n\nPros: \n1.\tBilevel 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. \n2.\tThe 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. \n3.\tThe 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.\n4.\tThe experiments support the theoretical results to certain degree. \n\nHowever, I have several concerns about this submission. \n\nCons:\n1.\tMy 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). \n2.\tMy 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).  \n3.\tThis 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.\n4.\tFor 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. \n5.\tFor 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. \n\nIn 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.  \n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "6"}, "extra_text": {}}]

Author rebuttal:

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)