On Stability and Generalization of Bilevel Optimization Problems
Authors: Meng Ding
Mingxi Lei
Yunwen Lei
Di Wang
Jinhui Xu
Venue: Submitted to ICLR 2023 (2023)
Keywords: bilevel optimization
generalization
stability

Abstract: (Stochastic) bilevel optimization is a frequently encountered problem in machine learning with a wide range of applications such as meta-learning, hyper-parameter optimization, and reinforcement learning. Most of the existing studies on this problem only focused on analyzing the convergence or improving the convergence rate, while little effort has been devoted to understanding its generalization behaviors. In this paper, we conduct a thorough analysis on the generalization of first-order (gradient-based) methods for the bilevel optimization problem. We first establish a fundamental connection between algorithmic stability and generalization error in different forms and give a high probability generalization bound which improves the previous best one from $O(\sqrt{n})$ to $O(\log n)$, where $n$ is the sample size. We then provide the first stability bounds for the general case where both inner and outer level parameters are subject to continuous update, while existing work allows only the outer level parameter to be updated. Our analysis can be applied in various standard settings such as strongly-convex-strongly-convex (SC-SC), convex-convex (C-C), and nonconvex-nonconvex (NC-NC). Our analysis for the  NC-NC setting can also be extended to a particular nonconvex-strongly-convex (NC-SC) setting that is commonly encountered in practice. Finally, we corroborate our theoretical analysis and demonstrate how iterations can affect the generalization error by experiments on meta-learning and hyper-parameter optimization.

Under review as a conference paper at ICLR 2023
ON STABILITY AND GENERALIZATION OF BILEVEL OPTIMIZATION PROBLEM
Anonymous authors Paper under double-blind review
ABSTRACT
(Stochastic) bilevel optimization is frequently encountered problem in machine learning with wide range of applications such as meta-learning, hyper-parameter optimization, and reinforcement learning. Most of the existing studies this problem only focused on analyzing the convergence or improving the conver- gence rate, while little effort has been devoted understanding its generalization behaviors. In this paper, we conduct a thorough analysis on the generalization of first-order ggradient-based methods for the bilevel optimization problem. We first establish fundamental connection between algorithmic stability and gener- alization gap in different forms and give a high probability generalization bound which improves the previous best one from (vvn) to Oloog n.), where is the sample size. We then provide the first stability bounds for the general case where both inner and outer level parameters are subject to continuous update, while ex- isting work allows only the outer level parameter to be updated. Our analysis can be applied in various standard settings such as (SC-SC), convex-convex (C-C), and nonconvex-nonconver (NC-NC). Our analy- sis for the NC-NC setting can also be extended to particular xonconvex-stronglyy convex (NC-SC) setting that is commonly encountered in practice. Finally, we corroborate our theoretical analysis and demonstrate how iterations can affect the generalization gap by experiments on meta-learning and paper-parameter opti- mization.
convex-stroonglll
INTRODUCTION
(Stochastic) bilevel optimization widely confronted problem in machine learning with various applications such as meta-lcarning (Finn et al. 2017: Bertinetto et al.) 2018 Rajeswaran et al. 2019) hyper-parameter optimization (Franceschi et al. 2018 Shaaan al., 2019, Baydin et al,,
2017 Bergstra et al. 2011 Luketina et al.] (016)). reinforcement learning (Hong et al. (020). and
few-shot learning (Koch et al.) 2015 Santoro et al. 2016 Vinyals et al., 2016). The basic form of this problem can be defined as follows
min R(x) (x, (x)) Eg [f (x, y (x): XER*;
s.t. y" (x) = arg min (G(x.y) = Eelo(x,y: yER
where f: R X Rd R and R4 x R + R are two continuously differentiable loss functions with respect and y. Problem ( has an optimization hierarchy of two levels, where the outer-level objective function depends on the minimizer of the inner-level objective function g-
Due to its importance, the above bilevel optimization problem has received considerable attention in recent years. A natural way to solve problem (I) is to apply alternating stochastic gradient up- dates with approximating Vyg(x,y) y) and V y), respectively. Briefly speaking, previous efforts mainly examined two types of methods to perceive an approximate solution that is close to the op- timum y (x). One is to utilize the aigle-timescale strategy (Chen al. 2021 Guo et al. 2021 Khanduri et al. 2021] Hu et al. 2022). where the updates for y and x are carried out simultanc
ously. The other one is to apply the two-timescale strategy (Ghadimi & Wang 2018 [] et al. 2021

---

Under review as a conference paper at ICLR 2023
STABILITY BOUNDS IN VARIOUS SETTINGS
REPERENCE
SC-SC O(1/m))
C-C
NC-NC
NC-SC K /mm)
SSGD (TIIs WORK) TSGD (THIS WORK)
O(Ni R72 mm)) D((Ka)**/m) /mm))
O(K"² fmL) O(T "s Kn' /mmm)))) OTT "6 K /mm))
((ea)) /m))
Table I: Summary of main results, 14z constont for all above; T: inner iterations; K: outer iserations, mi: size of outer datasct. SSGD single-timesaal and two-timescale methods, stochastic gradient descent.
and TSGD stand Algoritim [and Algorithm
[
Hong et al. 2020; Pedregosa 2016). where the update of y is repeated multiple times to achieve a more accurate approximation before conducting the update of x.
While there is long list of work on bilevel optimization, most of the existing work only focuses on either analyzing its convergence behaviors (Ghadimi & Wang 2018: Hong et al., 2020 Ji al. 2021 or improving its convergence rate, based on the convexity and the smoothness properties of (( and/or g(--) (Liu et al., 2020 Li et al. 2020). Contrarily, only little effort devoted to understanding the generalization behavior of the problem. To the best of our knowledge, there is only one recent work on the generalization analysis for bilevel problems (Bao et al., (02T), which presents the first expected uniform stability bound. However, there still several undesirable issues in this work: (1) Their result is only for the uniform stability (which could be deduced from argument stability with certain conditions, see Definition 4 for details), leaving the analysis of other stronger definitions of algorithmic stability open; (2) Additionally, the UD algorithm allows the outer level parameters to be updated continuously but needs reinitialize the inner level parameters before each iteration in the inner loop, which is not commonly used in practice due to their inefficiency (see line 4 in Algorithm 3 (3) The proof of Theorem in their work is unclear to show whether the update of outer level parameters is argument dependent on the inner level parameters, where may exist some gap in the analysis of UD algorithm (see Appendix E for detailed discussions). (4)Their experiments take only hyper-parameter optimization into consideration and neglect other applications in the bilevel optimization instances.
To address all the aforementioned issues, we give in this paper thorough analysis on the general- ization behaviors of first-order (gradient-based) methods for general bilevel optimization problem. We employ the recent advances of algorithmic stability to investigate the generalization behaviors in different settings. Specifically, our main contributions can be summarized as follows:
Firstly, we establish a fundamental connection between generalization gap and different notations of algorithmic stability (argument stability and uniform stability) for any ran- domized bilevel optimization algorithms in both expectation and high probability forms. Specifically, we show that the high probability form of the generalization gap bound can be improved from (Vvn) to Ollog n) compared with the result Bao et al. 2021
Next, we present the stability bounds for gradient-based methods with either single- timescale two-timescale update strategy under different standard settings. To the best of our knowledge, this work provides the first stability bounds for the two-timescale (dou- ble loop) algorithms, which allows the accumulation of the sub-sampled gradients in the inner level. In detail, we consider the settings of strongly-convex-stron storee--strolllycoovee (SC-SC), convex-convex (C-C), and amconvex-nonconee sis to a particular nonconvex-stronge wsttssstt--ooooeee (NC-SC) setting that is widely appeared in practice. Table T is the summary of our main results.
(NC-NC), and further extend our analy-
Thirdly, we provide the first generalization bounds for the case where both the outer and inner level parameters
subject to continuous (iterative) changes. Compared to the pre- vious work (Bao et al. 2021), our work does not need the reinitialization step hefore each iteration in the inner level and hence algorithm carry over the last updated inner level parameters, which is more general and practical.
Finally, we conduct empirical studies to corroborate our theories via meta-learning and hyperparameter optimization, which are two applications of bilevel optimization.
Due to space limitations, all the proofs and additional experiments included in Appendix.
2

---

Under review as a conference paper at ICLR 2023
1.1 RELATED WORK
Research at the interface between generalization and the bilevel problem can be roughly classified into two categories. The first one includes all the research on bilevel optimization. In recent decades, extensive studies have been done on this topic, which suggests that bilevel optimization has a wide range of applications in machine learning such as hyper-parameter optimization (Franceschi et al. 2018 Lorraine & Duvenaud, 2018 Okuno et al. 2021). meta learning (Bertinetto et al. [2018] Rajeswaran et al.1 Soh et 2020) and reinforcement learning (Yang et [018 2018] ['schiatschek] et 2019). Most of the existing work studies the problem from an optimization perspective. For
example, Ghadiimi & Wang (2018) 8); Ji et al. (2021) provide the convergence rate analysis based on the nonconvex-strongle seroreeeeesttoooggyooeeeeee conveex assumption for the two functions f((:.) and g(-,,). .). (Grazzi et al. 2020)
considers the iteration complexity for hypergradient computation. (Liu et al., 2020 Li et al. 2020) present an asymptotic analysis for the convex- maavex-strongl-ooo coonvexx setting. Perhaps the most related one to ours from the generalization standpoint (i.e., the expectation of population risk and empirical risk) is [ao al. (2021), while there may exist some gap in the analysis of UD) algorithm. In this work, we employ a novel approach to examine the stability bounds of bilevel optimization problems. Firstly, our work analyzes the generalization behavior by observing how different settings can have an impact on the stability bounds directly. Secondly, our work adopts a stronger version of stability called argument stability, which can imply the previously used uniform stability if the function is sufficiently smooth. Furthermore, our work does not need to reinitialize the inner-level parameters and allows them to carry over their last updated parameters at each time updating the inner level. This indicates that y in the inner level is updated iteratively and depends on the current parameter of x, which is more common and efficient practice.
The second category includes all the work on stability analysis. There is a long list of research on stability and generalization (Bousquet & Elisseeff 2002; Mukherjee et al.) 2006 Shalev-Shwardd et al. 2010)) Bousquet& & Elisseeff (2002) first introduces the notion of uniform stability and estab- lishes the first framework of stability analysis. Hardt et al. (2016) later extends the stability analysis to iterative algorithms based stochastic gradient methods for the vanilla stochastic optimization. After that, there are subsequent studies on generalization analysis for various problems via algorith-
mie stability, such as minmax problems (Lei al. [021 Farnia & Ozdaglar 202 Zhang al.,
2021] and pairwise learning (Yang et al. 2002: Lei et al. 2020 Xue et al.) 2021 Huai et al. 2020). However, it notable that due to the additional stochastic function in the constraint in the bilevel optimization, all the previous techniques and results cannot be applied to our problem. Although the generalization analysis of minmax optimization is somewhat similar ours, involves only one ob- jective function ff and a single level in algorithms for typical minmax optimization problems, while in the bilevel optimization algorithms there is an inner level and an outer level, which is considerably more challenging.
2
PRELIMINARIES
2.1 DEFINITIONS AND ASSUMPTIONS
In the following, we give some necessary definitions and assumptions that are widely used in bilevel optimization (Ghadimi & Wang 2018 Ji et al. 2021 Khanduri et al.) 2021) and generalization analysis (Hardt et al., 2016; Lei et al. 2021).
Definition 1 (Joint Lipschitz Continuity). A function f(x y) is jointly L-Lipschitz over R41 x R2 if for all x E Rd E Rd, the following holds, yf(x.y) - f(x', y')l S
X x11 lly -'1
Definition 2 (Smoothness). A function f is I-smooth over a set S if for all u, w E S the following is true, f Vf(w)ll = 2||u - w||-
Definition 3 (Strong Convexity). A function f is p-stronglyy convexx over set S, if for all u, S, the following holds, f(u) + (Vf(u), w u) + 2
" [|w u/I2 I f(w).
Assumption (Inner-level Function Assumption). We assume the inner stochastic function g(x. y)
in (I) satisfies the following:
( g y) v) is jointly Lipschhtt for any x E Rd4 and y Rd (i) g(x, y) is continuously differentiable and l -mooohhh for any (x E IRd: x TRd2.
3

---

Under review as a conference paper at ICLR 2023
Assumption 2 (Outer-level Function Assumption), We assume the outer stochastic function f(x.
in (T) satisfies the following:
(iit) f (x.y) is jointly L, Lipischhtz for any R and y R2
(iv) y) is continuously differentiable and I s-mooth for any (x,y) E TR x RRd
2.2 PROBLEM FORMULATION
Given two distributions TD, and D2, in the (stochastic) optimization problem we aim to find the minimizer of Problem (T). However, since the distributions are often unknown, in practice we only have two sinite-size datasets Dm, = { i i= m ~ [DT"" and Dm, = {{: i= I,... m2} ~ D2" where each &, and S are i.i.d. sampled from D1 and D22 respectively. Based on these datasets, will design some (randomized) algorithm A with output A (Dm Dmg) - (x, y) E Rd Rd,, Our goal is to investigate the generalization behavior of such output. Note that although there are two stochastic functions in the bilevel optimization problem, we only care about the generalization of the outer-level one since it is the one that we prefer to minimize.
Below we define the generalization gap to measure the generalization behavior. Given distribu- tion D1 and a finite data Dm,, D the population risk function R(x,y, defined as y.
y,,, D1) of x, y on D1 == Eg-n, If (x, y(x): and its empirical risk function on Dm, is Rx y, Pm,) = mi E yx):
Moreover, for a fixed hyperparameter x E Rd
and y(x) E R ( note that y(x) might be dependent on x), we define the difference between the population risk and the empirical risk over (x, (x)) as the bilevel generalization gap of (x, yx)): E. E,[R((x y) Rx,x y), where E, denotes the expectation of Dmy ~ D When there is no ambiguity, we simplify thereafter the notations as follows: R(x. yI) = R(x. y) and Rg (x. y, Dm,) = Ro (x. Our goal is thus to analyze the bilevel generalization gap of the output of algorithm A A(Dm. D ) based on Dm, and Dmn. Since the generalized error depends on the algorithm itself, in the following we will introduce the algorithms to be considered in this paper.
Most of the existing algorithms adopt the following idea: first approximate y" on Dm, for a given parameter x in the inner level and then seek the hyperparameter x" (Dm, Dm2) with corresponding hypothesis y (x" (Dmy, Dmg), ) Dma)) by the below estimation:
x(Dm, Dmn)) z arg min Rx (xx Dmi);
(2)
where ((x, Dam) v arg min Gx, Dmg),
y
where Go(X, y, Dma.) Dmmg) is the empirical risk of G(x,y) over Dmg. iee. G(x,y; Dmg) Em (()) Most of the current gradient-based (first-order) algorithms for approxi- mating (2 can be categorized into two classes: single-timesee
methods and two-timescale meth- ods. The single-timescale method performs the updates for y and simultaneously via stochastic gradient descent (SGD), while the two-timescale method updates multiple times before updating x (via stochastic gradient descent). As there are numerous approaches for both classes (see Related Work section for details), in this paper we will analyze the generalization behaviors for the most classical and standard one in each class, i.e., tinleetimescale SGD (SSGD; Algorithm I and two- timescale SGD (TSGD; Algorithm 2 There is a long list of work (Chen et al. 2021 (Ghadimi & Wang 2018 Ji et al. 202T) based on either SSGD or TSGD.
GENERALIZATION AND STABILITY FOR BILEVEL OPTIMIZATION
Algorithmic stability is one of the classical approaches to analyzing the generalization bound for algorithms. Roughly speaking, the algorithmic stability of (randomized) algorithm A measures how the output of algorithm A changes if we change one data sample in the input dataset. While there are various notions of stability, most of the existing work on analyzing the stability of stochastic op- timization, pairwise learning and minimax optimization focuses on the uniform-stability stability (Bousquet & Elisseeffi 2002) and the argument-stability (Liu et al. 2017 Lei & Ying. 2020). Thus, we also adopt these two notions of stability for the bilevel optimization problem. Briffy speaking, uniform- stability focuses on the resulting change in population risk function, while the argument-stabile considers the resulting change in arguments, i.e., the output of the algorithm.
Definition 4 (Algorithmic Stability). Let A DD IDiia + Rdi x d2 be randomized algorithm.
4

---

Under review as a conference paper at ICLR 2023
Algorithm
Single-timeseale SGD (SSGD)
Algorithm 2 Swo-timescale SGD (TSGD)
Input: number of iterations K, step sizes Og
1: Input: number of iterations K, step sizes Oz
Og. initialization Xo.Yo. Datasets Dm, and
ay. initialization Xo.Yo
Dma
2: Output: XK YK
2: Output: YK
for k 0 to K 1 do
3: for k K 1 do
4: y y
4: Uniformly sample i [m2], E [m]]
for T T do
5: Yk+1 = - ay (xk: Yk (x(x))
6: Uniformly sample i E [m2]]
6: XK+11 Xx az (xx,
7:
y ++1 = - ay
7: end for
8: end for
8: return XK and YK
9: Uniformly sample j [m,]
10: Xx+1 Xx 02 (x (x)):
11:
end for
12:
return XK-
(a) A is B-uniformly-stablle if for all datasets Dmu D' D and Dmz D such that Dm, and D mi differ in at most one sample, we have the following for any ~ D1:
EAll (Al) Dm.). f(A(D),, my Pmz),E) S 3.
is B-uniformly-stable with probability at least - we have the following for any { ~ D1 with probability at least ō:
[(A(Dmm Dmgg. [(A(D), Dm B
(b) is B-argumment-stable in expectation if for all datasets Dmny: D' m such that Dm and Di, differ in most sample, have:
DDT and Dmn ~
(([]) Dm.) A(D Dmm)
Note that the definition of uniform stability in expectation is the same as the definition in (Bao cet al. 2021). Thus, our other definitions can considered as extensions of the previous stability for bilevel optimization. In the following, present Theorem a our first result, which shows crucial relationship between generalization gap and algorithmic stability for an algorithm A.
Theorem 1, Let A : g x + Rd Rd be a randomized BO algorithm.
(a) If A is ß-uniform-stable in expectation, then the following holds for Dm,, DD Dmy D
EA, [R(A(Dmy Dmmp) (A(A) Dmn))) B.
(b) If A is B-argument-stable in expectation and Assumption holds, then the following holds for Dmn ~ DTT Dmg mpp EAD,,, [R(A(Dm)) Dm,g) R, (A(AAD Dmn))) LyB.
(c) Assume that |s(x, E) < M for some M 2 O. If A 3-uniform-stable almost surely, then for Dm, 13 Dmz ~ D the following holds with probability 1 1 8:
R[A Dm.)) (A(A(Dm, Dm,))
4M
log + 12V228 mi log e
28
+
mm
where is the base of the natural logarithms.
Remark 1. The above theorem suggests that the generalization gap can be controlled by several notions of algorithmic stability. Part (a) and Part (b) show that the expectation of generalization gap can be bounded by uniform stability and argument stability with the Lipschitz constant, respectively; Part (c) indicates that the generalization gap for the algorithm is no more than O log(m1) +
5

---

Under review as a conference paper at ICLR 2023
1/ /mmi) with probability 1-6. 6. Compared with the existing work (Bao et al. 2021). Theorem I considers argument stability additionally, which is a stronger notion of stability than uniform stability (since uniform stability can be deduced from argument stability with the condition that the function is sufficiently smooth). Moreover, we use the McDiarmid's inequality and the equivalence of tails and moments for the random variable with mixture of sub-gaussian and sub-exponential tails (Lemma in Bousquet et al. (2020)), which provide a significantly improved high probability bound Part (c) (i.e., improving from (33mm) )
in Bao et (2021) (
(3 log m1)).
STABILITY ANALYSIS FOR BILEVEL OPTIMIZATION ALGORITHMS
Motivated by Theorem | it is sufficient to analyze its stability, As mentioned in the previous Section 2.2 we will consider the stability of SSGD and TSGD. For simplicity we let SC-SC denote the where / and y both strongly convex functions. C-C, NC-NC, and NC-SC are also denoted in similar manner with "C" representing convex function and "NC" representing nonconvex function.
that analyze the generalization behaviors for any algorithm,
4.1 STABILITY BOUNDS FOR SINGLE-TIMESCAL SGD
As we see from Algorithm D SSGD updates and simultaneously. In the following develop stability bounds for this algorithm in different settings.
Theorem 2. Suppose that Assumptions 7 hold and Algorithm A is SSGD with K iterations:
(a) Assume that Problem 7 is SC-SC with strongly convexity parameters μs and Pg- Let 0₂ = ay (see Lemma Tor details) be the step sizes. Denote I max maxx(l,,4 (1g,,g) Then, A is B B-argument-stable in expectation, where
B < O (12) r22) (ma (ug Fg (2,))
(b) Assume that Problem in expectation, where
ae is C-C. Let ag ay be the step sizes. Then, is 8-argument-stabbe
(a + (a) (2+ 2 max (aoll)) (aylg))) K/2
)
B s m (
(c) Assume that Problem constant 2 0 and I max (g). Then, A is 3-argument-stabie in expectation, where
7 NC-NC. Let the step sizes satisfy max (atzy ary S c/k: for some
B < o ((m)ee)))) (2cL) 12
where 1,, lg and Ly. Lg are smoothness constants and Lipschitz constants for f. 9. respectively. Remark Note that the above stability bounds are independent of the specific form of the objective more reliant the properties the loss functions and sample size m,, and the stability bounds in the C-C and NC-NC cases are related to the number of iterations additionally. Specifically, Part(a) establishes stability bound of (1/mi) in the SC-SC setting and Part(b) considers a C-C case with a stability bound (H* K/2 /m²) related the number of iterations and the data size, where Ki is constant. The NC-NC case is discussed in Part(c) which provides stability bound of O(K येा /m1), where is constant to control the step size and is the larger smoothness number ly and lg. The conclusions here match the existing results in minmax problems (Lei et al. 2021 Farnia & 3 2021))
function ((---) and the exact form of the sample distribution ID, which
4.2 STABILITY BOUNDS FOR TWO-TIMESCALE SGD
Compared with the above SSGD, Two-timescale SGD (TSGD; Algorithm 2 always achieves more accurate approximate solutions by updating y multiple times before updating In this section, we extend our analysis from SSGD to TSGD. Particularly, compared with the results in Bao et al. provide stability bounds in Theorem 3 for the case where the inner level parameter 2021).

---

Under review as a conference paper at ICLR 2023
(y) is updated iteratively (i.e., consistency). We further explore in Theorem 4 particular NC-SC setting, which is commonly appeared in bilevel optimization applications such as meta learning and hyperparameter optimization.
Theorem 3. Suppose that Assumptions 2 and (g(-,-)l 1. Let A be the TSGD algorithm with K iuteriiterations and I imner-iterations Then we have
(a) Assume that Problem I is SC-SC. Let l = max 1+(ayte)
(1-aytoja, and a oz = Gg min(1/1g 1/( + pa]s be the step sizes. Then, A is B-argument-stable in expectation, where
3 S m1 -1 V 1333
(
27
(1 + (1+a))* al)*
12y aglg)
(b) Assume that Problem (1) is C-C. aet = step sizes. Then, A is 5-argument-stabie in expectation, where
[t(a)a) and ax ay S 2 be the I-ayts
ty
[1703 (2, (1 (1)+))
27
BSO mi
(c) Assume that Problem 7 is NC-NC. Let the step sizes satisfy max ( S k for some constant 2 0 and I max (1 Then, B-argument-stue stable expectation, where
B 0=
(2cL, v 17 T2rT)
TOTT
K.FFFI
Tel
Remark 3. Compared with the previous results for SSGD, the stability bounds of TSGD depend on the number iterations in the outer level loop, the number of iterations in the inner level loop, and the data size in the outer level loop. If the step sizes are sufficiently small, bounds in Theorem 3 are asymptotically the same as the bounds of SSGD in Theorem 2 Thus, Theorem 3 can be considered
see that the
generalization of the previous one. The dependence on T also reveals our novelty compared with the existing work of stability analysis for other problems, such as simple SGD and minmax problems. To the best of our knowledge, this work provides the first stability bounds for the two-timescale (double loop) algorithms, which allows the accumulation of the sub-sampled gradients in the inner level.
results with the ones in (Bao al. 2021), we have the following ob- servations. 1) They only established the uniform stability bound for the Unrolled Differentiation algorithm 3 where the algorithm is reinitialized at each time entering the inner level loop, indicat- ing that takes into account the changes to only one parameter in the outer level loop, while our algorithm considers the update for both parameters. Its proof needs assume that the update of in the inner level after the reinitialization will not be affected by the value specified for x. However, this assumption is quite uncommon and is probably the reason that they do not need make any ussumption on the inner level objective function (see Appendix EJin details). In contrast, our work allows the inner level parameters to be updated consistently (i.e., carrying over the value in the last update), instead of being reinitialized at each time entering the inner level loop. Specifically, we allow v to be employed the beginning of the (k- + 1)-th outer level iteration, rather than Yo- This enables to obtain different stability bounds for different inner level objective functions from novel perspective.
Remark 4. Comparing
In the following, extend analysis particular NC-SC setting that is frequently encountered in real-world applications and optimization analysis.
Theorem 4. Suppose that Assumptions Andd hold, 0 0 f(--)) and Problem D is NC-SC. Let A be the TSGD Algorithm with K for constant 2 Denote = max (1 J.). Then, A is 3-uniform-stable in expectation, where
and T inner-iterations with max Taz, ay) S c/k
(2cLsV 1 1272
POTTI
(TI + 14 + 2/c)
B 856 O
my
mg)
7

---

Under review as a conference paper at ICLR 2023
Remark 5. Compared with previous analysis, now sketch the technique differences in our analysis. We consider the bound of the term (6x,8) 0y.x)² = (I|x, x lly - ykll),,
while we employ åæ | - + llye yk'llz in the previous analysis, where (xR; Y') are the outputs of TSGD after & iterations for Dm, and D respectively with Den and Di differing in one sample. In the NC-SC setting, we show that (6x,4+1, Sy,+1)² - ((1 + ag (1 + ( (S means the entry-wise inequality), which means our term can be controlled. Then, we take the expectation of it to derive our uniform stability bound. To achieve the generalization gap over continuously changing parameters, it is imperative to take into account the growth of (6x,k; Sy.4) instead of 6x in [Bao et al. 2021). Appendix C.3 provides more details.
Thus, based our previous results, we now provide the first generalization bounds in the NC-NC setting for both SSGD and TSGD.
Corollary 5. Assume that the problem is NC-NC, If(., :)) S 1 for all &, and Assumptions and 2 hold. Denote I = maxil;, [1 with max Agy S c/k for constant 2 0. Then, the generalization gap of SSGD I with K iterations is bounded by O(K की. /m1).
Corollary 6. Assume that the problem is NC-NC, (-) S 1 for Jolall& &, and Assumptions and hold. Let = max{l,, 1 with maxfaz, 0 S e//k. Then, the generalization gap of TSGD with
K outer iterations and T inner iterations bounded by O K K---aae (ol=- (m11)
we can derive the above corollaries on generalization gap from stability bounds. Corollary 5 and Corollary show that extremely high number of iterations (K for SSGD and K,T for TSGD) will drastically reduce the stability these algorithms and increase the generalization gap, which will make these algorithms increase the risk of overfitting. We will also verify it in the following experiments.
Remark 6. By Theorem
EXPERIMENTS
In this section, we empirically validate our previous theoretical results on real world datasets. Two experiments, including meta-learning and hyperparameter optimization, are conducted via Algo- rithm 2 TSGD (note that when T' 1, TSGD is just SSGD). Due to the space limitation, we just present the meta learning experiment here, leaving the hyperparameter optimization experiment and other details in the Appendix D
5.1 META LEARNING
Consider the few-shot meta-learning problem with M tasks bution Py. We aim to learn model that can rapidly adapt to different tasks. Firstly, the embedding model é is shared by all tasks to learn embedded features. Secondly, the task-specific parameter w; is to adapt the shared embedding to its own sub-problent Thus, the overall problem of meta-learning can be formulated as follow:
M) sampled from distri-
min Lo (é, w²) EEEDD T. [C w]:
(3a)
s.t. 20- arg min C / (Ø, w) ET. [Coy (Ø, w.)
(3b)
where D. and DIe are the training and testing datasets for task T. Each w; is computed from one or more gradient descent updates from on the corresponding task (rapid adaptation), i.e., w; = の a aV (,, (tb, w:). In the inner level, the base learner optimizes the series of w; for each tasks (Equation 3b). the outer level, the meta-learner optimizes the embedding model Φ using the minimizers / learned from the inner level and computes the loss from the testing dataset (Equation 3aj.
Settings and Implementation We evaluate the behavior of the 5-way-1-shot task on the Omnilot dataset (Lake et al. 2015). i.e., it aims to classify 5 unseen classes from only 1 labeled sample. contains 1623 different handwritten characters from 50 different alphabets. The image is in greyscale with a size 28 x 28. We follow similar settings in Di et al. (202I). A five-layer fully-connected network is constructed, where the task-specific parameter w; corresponds to the last layer of the
8

---

Under review as a conference paper at ICLR 2023
18
T=1
T=1
15-
T=1
0.7
T=2
Cooss Cooss Entray Loas
T=2
T=2
T
2.5
T=4
2.0
T
T=8
T=8
T=8
01
500
1000
1300
2000
2500
500
1000
1300
2000
2500
500
1000
1300
2000
2500
(a) Mcta-training Loss
(b) Meta-testing Loss
(c) Generalization Gap
Figure I: Results of meta learning with various values of T and K
network and the shared embedding model & corresponds to all preceding layers. Thus, we train the two sets of layers separately the outer and inner level of optimization. We build our model and establish our training using the software library learn2learn (Arnold et al. 2020). We follow the official vain-validation--est partition and train @ w; using the training set. The size of each layer in the network is 784 256 128 - 64 - 64 + 5. We set the number of tasks for training and testing set to 2000 and the batch size tasks to 32. The learning rate of & and w, are 0.002 and 0.01, respectively. Results evaluated based on the average of 5 trial runs with different random seeds.
Results Evaluation Figure presents the learning curves training set, testing set and the gener- alization gap with different values of inner iterations T and outer iterations K, Generalization gap estimated by the difference between training and testing loss. On one hand, it can be the model easily overfits on the testing set as K increases drastically (Figure Tb) and the effect of T' is very limited. On the other hand, with an appropriate value of K, smaller T (i.e) will result in underfitting on the testing loss (T' = 1 in the Figure Ic causes highest generalization gap due to the underfitting training process). The trend of generalization gap terms of K and T indicates that large values of iteration numbers will increase the risk of overfitting, which matches with our analysis in Theorem that the stability of TSGD will decrease drastically.
that
CONCLUSION
We give a thorough analysis on the generalization of first-order (gradient-based) methods for the bilevel optimization framework. In particular, we establish quantitative connection between gen- cralization and algorithmic stability and provide the first generalization bounds of the continuous updates for inner parameters and outer parameters in multiple settings. Our experiments suggest that inappropriate iterations will cause underfitting and overfitting easily. The tendency of general- ization gap also validates our theoretical results.
From the discussion in previous sections, we only discussed the first-order method, while there exist number of estimating second-order and momentum-based approaches to solve the bilevel optimization problem. Dealing with the approximation hypergradient in generalization analysis is another direction for future work.
REFERENCES
Sébastien M R Amoll, Praateek Mahajan, Dehajyoti Datta, Ian Bunner, and Konstantinos Saitas Zarkias. learn2leam: A library for Meta-Learning research. August 2020. URL http://
Doxiv.or//abs/200
12284
Fan Bao, Guoqiang Wu, Chongxuan Li. Jun Zhu, and Bo Zhang. Stability and generalization of
bilevel programming in hyperparameter optimization. Advances in Neural Information Process- ing Systems, 14:4529-4544 2021.
Atilim Gunes Baydin, Robert Comish, David Martinez Rubio, Mark Schmidt, and Frank Wood.
Online learning rate adaptation with hypergradient descent. arXiv preprint 1703:0703..4782, 2017.

---

Under review as a conference paper at ICLR 2023
James Bergstra, Rémi Bardenet, Yoshua Bengio, and Balázs Kégl. Algorithms for hyper- parameter optimization. Advances in neural information processing systems, 24, 2011.
Luca Bertinetto, Joao F Henriques, Philip HS Torr, and Andrea Vedaldi. Meta-learning with differ- entiable closed-form solvers. arXiv preprint /rXiv:/805.08/ 2018.
Olivier Bousquet and André Elissefff. Stability and generalization. The Journal of Machine Learn- ing Research, 2:499-526, 2002.
Olivier Bousquet, Yegor Klochkov, and Nikita Zhivotovskiy. Sharper bounds for uniformly stable algorithms. In Conference on Learning Theory, pp. 610-626. PMLR, 2020.
Tianyi Chen, Yuejiao Sun, and Wotao Yin. A single-timescale stochastic bilevel optimization method. arXiv preprint arXiv:2102.044 022.0467,, 2021.
Farzan Farnia and Asuman Ozdaglar. Train simultancously, generalize better: Stability of gradient- based minimax learners. In International Conference on Machine Learning, pp. 3174-3185. PMLR, 2021.
Chelsea Finn, Pieter Abbeel, and Sergey Levine. Model-agnostic meta-learning for fast adaptation of deep networks. In International conference on machine learning. pp. 1126-1135. PMLR, 2017.
Luca Franceschi, Paolo Frasconi, Saverio Salzo, Riceardo Grazzi, and Massimiliano Pontil. Bilevel programming for hyperparameter optimization and meta-learning. In International Conference on Machine Learning, pp. 1568-1577. PMLR, 2018
Saeed Ghadimi and Mengdi Wang. Approximation methods for bilevel programming. arXiv preprint arXiv:1802.0222 2018
Riccardo Grazzi, Luca Franceschi, Massimiliano Pontil, and Saverio Salzo. On the iteration com- plexity of hypergradient computation. In International Conference on Machine Learning, pp. 3748 3758. PMLR, 2020.
Zhishuai Guo, Quanqi Hu, Lijun Zhang, and Tianbao Yang. Randomized stochastic variance- reduced methods for multi-task stochastic bilevel optimization. arXiv preprint arXiv:2105.02266. 2021.
Moritz Hardt, Ben Recht, and Yoram Singer. Train faster, generalize better: Stability of stochastic gradient descent. In International conference on machine learning, pp. 1225-1234. PMLR, 2016.
Mingyi Hong, Hoi-To Wai, Zhaoran Wang, and Zhuoran Yang. A two-timescale framework for bilevel optimization: Complexity analysis and application to actor-critic. arXiv preprint arXiv:2007.05170. 2020.
Xiaoyin Hu, Nachuan Xiao, Xin Liu, and Kim-Chua Toh. An improved unconstrained approach for bilevel optimization. arXiv preprint arXiv:2208. 00732, 2022.
Mengdi Huai, Di Wang, Chenglin Miao, Jinhui Xu, and Aidong Zhang- Pairwise learning with differential privacy guarantees. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 34, pp. 694-701, 2020.
Kaiyi Ji, Junjie Yang, and Yinghin Liang. Bilevel optimization: Convergence analysis and enhanced design. In International Conference Machine Learning, pp. 4882-4892 PMLR, 2021.
Prashant Khanduri, Siliang Zeng, Mingyi Hong. Hoi-To Wai, Zhaoran Wang, and Zhuoran Yang. A near-optimal algorithm for stochastic bilevel optimization via momblltmmmmm Advances in Neural Information Processing Systems, 34, 2021.
Gregory Koch, Richard Zemel, Ruslan Salakhutdinov, et al. Siamese neural networks for one-shot image recognition. In JCML deep learning workshop, volume 2, pp. 0. Lille, 2015.
Brenden M Lake, Ruslan Salakhutdinov, and Joshua B Tenenbaum. Human-level concept learning through probabilistic program induction. Science, 350K6266):133--13333 2015.
Yann LeCun. The mnist database of handwritten digits. http://yann. lecun. com/exdb/nmist// 1998.
10

---

Under review as a conference paper at ICLR 2023
Yunwen Lei and Yiming Ying. Fine-grained analysis of stability and generalization for stochastic gradient descent. In International Conference on Machine Learning, pp. 5809-5819. PMLR, 2020.
Yunwen Lei, Antoine Ledent, and Marius Kloft. Sharper generalization bounds for pairwise learn- ing. Advances in Neural Information Processing Systems, 33:21236-21246 2020.
Yunwen Lei, Zhenhuan Yang, Tianbao Yang, and Yiming Ying. Stability and generalization of stochastic gradient methods for minimax problems. In International Conference on Machine Learning. pp. 6175-6186. PMLR, 2021.
Junyi Li, Bin Gu, and Heng Huang. Improved bilevel model: Fast and optimal algorithm with theoretical guarantee. arXiv preprint arXiv:2009.006690 2020.
Risheng Liu, Pan Mu, Xiaoming Yuan, Shangzhi Zeng, and Jin Zhang. A generic first-order gorithmic framework for bi-level programming beyond lower-level singleton. In International Conference on Machine Learning, pp. 6305 6315. PMLR, 2020.
Tongliang Liu, Gábor Lugosi, Gergely Neu, and Dacheng Tao. Algorithmic stability and hypothesis complexity. In International Conference on Machine Learning. pp. 2159 2167. PMLR, 2017.
Jonathan Lorraine and David Duvenaud. Stochastic hyperparameter optimization through hypernet- works. arXiv preprint arXiv: 1802vv180..090 09949, 2018.
Jelena Luketina, Mathias Berglund, Klaus Greff, and Tapani Raiko. Scalable gradient- tuning of continuous regularization hyperparameters. In International conference machine learning, pp. 00.22955226 PMLR, 2016.
Sayan Mukherjee, Partha Niyogi, Tomaso Poggio, and Ryan Rifkin. Learning theory: stability is
sufficient for generalization and necessary and sufficient for consistency of empirical risk mini- mization. Advances in Computational Mathematics, 25(1):161-195 2006.
Takayuki Okuno, Akiko Takeda, Akihiro Kawana, and Motokazu Watanabe. On pr-hypeerarameter learning via bilevel nonsmooth optimization. J. Mach. Learn. Res., 22:245-1, 2021.
Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury. Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, et al. Pytorch: An imperative style, high- performance deep learning library. Advances in neural information processing systems, 32, 2019.
Fabian Pedregosa. Hyperparameter optimization with approximate gradient. International con- ference machine learning, pp. 737-746. PMLR, 2016.
Aravind Rajeswaran, Chelsea Finn, Sham M Kakade, and Sergey Levine. Meta-learning with im- plicit gradients. Advances in neural information processing systems, 32, 2019.
Adam Santoro, Sergey Bartunov, Matthew Botvinick, Daan Wierstra, and Timothy Lillicrap. Meta- learning with aeamory-augmenter neural networks. In International conference on machine learn- ing, pp. 1842-1850. PMLR, 2016.
Amirreza Shaban, Ching-An Cheng, Nathan Hatch, and Byron Boots. Truncated back-propagation for bilevel optimization. In The 22nd International Conference Artificial Intelligence and Statistics, pp. 1722-1732. PMLR, 2019.
Shai Shalev-Shward Ohad Shamir, Nathan Srebro, and Karthik Sridharan. Learnability, stability and uniform convergence. The Journal of Machine Learning Research, 11:2635-2670 2010.
Jae Woong Soh, Sunwoo Cho, and Nam Ik Cho. Meta-transfer learning for zero-shot super- resolution. In Proceedings of the IEEF/CVF Conference Computer Vision and Pattern Recog- nition, pp. 3516-3525, 2020.
Sebastian Tschiatschek. Ahana Ghosh, Luis Haug, Rati Devidze, and Adish Singla. Learerr-aware teaching: Inverse reinforcement learning with preferences and constraints. Advances in Neural Information Processing Systems, 32, 2019.

---

Under review as a conference paper at ICLR 2023
Roman Vershynin. High-dimensional probability. 2018.
Oriol Vinyals, Charles Blundell, Timothy Lillicrap, Daan Wierstra, et al. Matching networks for one shot learning. Advances in neural information processing systems, 29, 2016.
Zhiyu Xue, Shaoyang Yang, Mengdi Huai, and Di Wang. Differentially private pairwise learning revisited. In IJCAI, pp. 3242-3248, 2021.
Zhenhuan Yang, Yunwen Lei, Puyu Wang, Tianbao Yang, and Yiming Ying. Simple stochastic and online gradient descent algorithms for pairwise learning. Advances in Neural Information Processing Systems, 14:20160-201777 2021.
Zhuoran Yang, Zuyue Fu, Kaiqing Zhang, and Zhaoran Wang- Convergent reinforcement learning with function approximation: bilevel optimization perspective. 2018.
Junyu Zhang, Mingyi Hong. Mengdi Wang, and Shuzhong Zhang. Generalization bounds for stochastic saddle point problems. In International Conference on Artificial Intelligence and Statis- fics, pp. 568-576. PMLR, 2021.
12

---

Under review as a conference paper at ICLR 2023
A COMPARISON BETWEEN UD AND TSGD
Algorithm Unrolled differentiation (UD)
Algorithm 4 Two-timescale SGD (TSGD)
1: Input: number of iterations K, step sizes Oz.
Input:
number of iterations K, step sizes Ogz
Og. initialization Xo-Yo
Oy. initialization Xo-Yo. Datasets: Dm D Dmz
2: Output: XK. YK
3: for 0 to K do
Output: XK. YK
4: yk + Yu
for k 0 to K 1 do
5: for .+1 = y ay Vyg(xk yic (xx); Dmn)
0 T do
y y
6:
for = 0 to T - do
7: end for
yk [+1 y Oy (xk: (xx)); Dmn))
8: X1+11 X V ( (xx); Dmn)
end for X X2 az (xxx y (xx);; Deaa)
9:
end for
10:
return XK. Yk
end for
return XX. y
B PROOF OF PRELIMINARIES
B. THE PROOF OF THEOREM 1
Proof of Part (a). Since & and & are drawn from the same distribution, we know
EALR(A(D Dmg); ), D1) R,(A(D Ding); Dm, )]
EA,EED SDD, (f((A Dm ),E) (A(Dm) (mm))Ee))
=EAAEIEDI &DD, (,,, E.41,-.Emm Dmg ),E,) E1) (A(D)m D Dma),E))
= -EACEEDM, S-D, (mm) ),)) -((A(D D,)) S B, where D'n, and Dmn differ in most sample &,-
Proof of Part (b). Similarly, we have (ALf(A(Dm, Dm) - f (A(D Dmz): Dm,)) Em SDD, (f(A(DDmm Dm,)) )) (A(D D m2) Ed]
EAACIED SDD.
Dm,)) Ex) f(A(Dm, D,,))
-EAGEEDD DDD. (SA(D' Dm22) ((A(mm Em)]
EAAEEEDM END, | Dmng)= A(Dmy Dmg) ]l| S L
To prove high probability bounds, need the following lemma on the concentration behavior the summation of weakly dependent random variables.
Lemma 7 (Bousquet et al. 2020). Let Z (Zi.... Zn) be vector of independent random vari-
ables with each taking values in Z, and g1.... In some functions gi Z - such that the following holds for any [m]
E [gx(Z)) 7 S M a.s.
E [2x(2) Z = a.s.,
9: has bounded difference 3 with respect to all variables except for the i-th variable.
Then, for any p 2
Σ 9 (Z)
< 112v2pn [log, no 4M ypm,
13

---

Under review as a conference paper at ICLR 2023
where the Ly-Rorm of random variable Z is denoted by |Z (BIlZ /p, 1.
Next, we state the following well-known relationship between tail bounds and moment bounds. Lemma (Bousquet et al. 2020; Vershynin 2018). Let a, b E R4. Let Z be a rundom variable with || S vpa + pb and p 2 2. Then, for any (0, 1), we have, with probability least 5
Z S e av logí 3 log ))
Proof of Part (c). In order to make use of Lemma 7 to obtain the generalization bounds, we will introduce:
B LE,, ((((() Dmgi {))] f(A(D), Dm.iE:)). where D Ei Eit, Emi and obeys identical distribution of &,.
Hence, we have:
(R(A(Dm) Dmz); D1) R2(A(Dm: Dmna): Dm,)) >
(E f (A(Dm, Dm.)i:)) f(A(Dm, Din))
mi
(BenD. (A(D m1 Di) - -E (AA(D Pmz)iE))
Be ~D, EEWD. [f(A(D))) Dm)):)) :mu()))
(E f(A(Di m1 Di)): f(A(Dm, Dmnd)iEi)
mi
It then follows from the definition of uniform stability that
[R(A (Dmm) m1: ); D1) R. (.(A Dmn,; Dmn))
228 +
BE EE-D. ( -
f(A(Di Dmgi Ei)
=28 +
hg
Notice that all conditions of hold. Thus, the following outcome can be derived for any p 2 2:
Σ hx(E) < 122 [log, mi] + 4M /pm..
Combining Lemma and Lemma with h, defined above, we have the following inequality with probability 1 8:
Σ h.(5)) <
<e
4M
log é + 12v22 [log, mi v log e 8) 5
mm
The deviation bound now follows immediately:
RR( (T(A(Dm, my Dmg);Di) R. (A((m,, Dmn); Dm,))
4M
< 23 + e
log g
+ 12v28 [log, mil / log )
m
The proof is completed.
14

---

Under review as a conference paper at ICLR 2023
C
MAIN PROOF
C.I APPROXIMATE EXPANSIVITY OF UPDATE RULES
With step size Or and Czy the update rules for single can be presented:
x - Vx), ( x [yy] y - By Vy ].
G.
Definition 5 (expansivity). An update rule is n-expansive if for every 2, x' E R y. v E ERo
- S nV/1x x11 1 y'll..
Lemma 9. Suppose that Assumptions aandd 2 hold for Problem
M Then:
1. If f and g are cinn-cooo then G2 is (1 max yr -xxpansive with step size ag Og.
2. If J and g are convex functions, then Gg is (V2+ 2 max ( (100,)))) (xepannsieee expansive with step size azz, Cty.
3. If f and g are strongly-convex with Py and Pg respectively, then G. is 2 - 20 (ug + Mg) ag -ee--expanivve with step size:
(uz + 1b)) - ((us + m2g) 0.512
S a2² = ag
(ug + Mb) + VV (uz + m2y2 -0.51
1
S min
Pi + Kg
12
Proof. In Case 1 with the NC-NC objectives and the smoothness of objectives on Assumptions and 2 we have
G.
x
G,
(1
x' y'
DI=
x x ag (Vf(x, (x(,'')) y' tay (V xx V (x (x))))
y
x' y'
a, (ff(x,))
ay ( - Vr9 (x.
x x-x x'
(1 max (1yam,
In case with the monotonicity of the convex objective's gradient, we have:
x ox (vf(x,y) (f(x)))) 20
( y' By (V y)) Vyg y')) ))> 20. 0.
Thus, the stated result then follows:
G. x 1) -G. G. ([ DI
x x' ]1²
x x x' ]'[
ar (V/xx)))) -
-2
y y
ay (Vyg(x,)) - -v
au V ( Vf ag (1 vxg(x.)))
< max{(1)aa)) )2, (1,g,)²) (16b,)))))) ||
x' x y-y y
]1"
+ ||x x'12
15

---

Under review as a conference paper at ICLR 2023
and
(1 y 1) G.
x' 1//
([ x'
y' 1)
2
x - x'
y y' |1" -2 y y ]'[
x' - x
ag (Vf(x'' -
vf(x'y)
Gs
=
ay (V (7 (x9(x,)))
0, (V .) - (5(xx
By (v -) - V/g (x (xg(x()''))
S (( )2 (2
||
| yy y'
x x'
][e
2
+ lly y'13.
(5)
Combining the above equations 6 and inequality E ax)² I k: - az. we can derive the expansive of update rule Go under convexity condition:
x G. G. ([ y 1) -G.
(1
x r DI
x x' S (2+ maxx (1arr) ||
y y' ][:
If f and g are strongly-comee convex, then, f(x.y) = y)
(1xx|++11>|] (1xx))
and g(x = y(x,y)
Ho
(|x[ 2 + [1y|1²) will be convex. With the above conclusions, we can derive the following:
y ) - GG
([ x
D>
GT
y
=|| y y
x'
]1. -20x
|
x x ]
(VI(x.y) - - F/X (vyg(x,y) - Vyg(( ]
y
+ +a.² 2 ||
(Vx(x,y) - (x),
(V y) - Vyg (x,x))
||[
x x
]1|
+ aa²² 2 |[[ (vi(x.y) Vf(x'
][
=(1 11-((n (az/11 + oz
y y
(V)g(x.y) V (x))))
x x-x x
]"
(vf(x,)) - vi(x,y)
-2(1 - 022ls - 02 ax
y - y
(Vyā(x,y) - (x)(x'
< <(1- (1, (uz + kg)) + a22 212) || - x11²?
The penultimate inequality arises from the smoothness of f. g. which is based on our assumption for simplicity that [ = max 1, and the details will be revealed as follows:
1
x' || -
x
yyg(x,y) - (x) ][r
(x (x
(f((x,) y) v)(x,)) (v)ā(x,)) - vxr(x'y))
+ (ur + p
|[[
x x-x'
y y
x x-x
y y ['[
(vi(x,y) - vi(x,))
]
+ 2 (1y + (gg)
(Vyā(x,y) - Vvō(x'.))
vf(x,y) - vī((,)) (v - (x0(x(y))
+ + #2g?
x x- ||
y- ]1º 2
Similar to the convex case, we can have:
Gr ([ y )) G. ([ x y'
-c,
1)
< 2 (1 20 (ny + M2) + az 219)
|[
y - y' 11.
x - x'
16

---

Under review as a conference paper at ICLR 2023
C.2 SINGLE TIMESCALE
We first introduce the following lemma before providing the proof of the Theorem.
Lemma 10 Hardt et al. (2016)) Consider two sequences of updates Gy..., G and
(G ..... y with initial points Xo = X Yo = Yo- Define 8y = VIIxA x/112 + lIve - -V(ll.
Then, we have:
njOx
iG
(G is n-expansive x
(I x
1)
8x+1 S min(n, 1)6x + 20
if sup
so
G is 1y expansive
Proof. The first part of the inequality obvious from the definition of expansivity and the assump- tion of G = y, For the second bound, note that:
8k+1
Go
Xk
)
G
Yk
k
Xx
Xx
+
G²
([ X
1)
x x yu -v
Yk
Yk
k
< 8 +
G.
Yk
Xk
))
Yk
X
+
G² ([
x
yy
]1
< 6p + 2c.
Also, 8x41 can be further expressed as:
5k+1
G
X
G
G
Xk
G.
([
x
G2
([ (
x
c.
1)
Yk
y/
G
Xk:
G.
([
x
||
スx ] G. ([
-G,
G²
([
x yk
Yk
yx
y%
< 110x + 20.
Combining the above completes the proof of the Lemma 10
Now, we ready prove Theorem 2
Proof of Part(a). Suppose that D m. and D' are two neighboring sets differing only in sample. Consider the updates G G_..... ..., GK and (G!),,., (GKy. We can observe that the example chosen by the algorithm is the same in Dm, D m, at step k with probability 1-1/m1 and different with proba- bility 1 1/m:- In the former case, have identical update rules, while / 20 (14 11g) + o212.
17

---

Under review as a conference paper at ICLR 2023
expansive can be employed in the latter through lemma I0.
E [6x+1l 2 (1 (1-1)) 1 |1]] (2(1 20, (u1 + 11g) + a 222))) 1/2 E [0rd
1
1
E [ōxb
+
2 (a + (azlig)
m1
mi
mi
(2 (1 2az (us + Ug) + a²) 1/2 E [6
2
v ((aLLa)² + (g=Lg)
mi
2/ (arley)² + (as (1) )²
Σ (2(1 20, (My + Un) 2) 1/2
m1
1=0
2/ (axt,)) + (1s }
(2(1- - 2a (uy + M²) + 2)) 1/2
$
m1
1=0
2 2v (an + (Ck (1g
00
(1) -
(1 2az (ps + M4) + a +.5)
m1
(aaLs)) + 210
m1
Oer (We + +bg)
0212
2 0.25
L3 + L3
mi (uy My
Here (1) comes from the mean equality vab S (a + b)/2 for any a,b 2 0 and the assumption of 0x (urtt))+/(uutttn +m,)² 0..5 which finishes the proof.
(uy+ag) ) -0.5
Proof of Part(b). The proof of Part(b) is analogous to the above, thus we use the same notations for this part.
E (5k-1] 1) S
(1-11) mi
1/2 (2 2 max (a)))
EE [Mt]]
1
E
[5
+
V 1.702 + 12003
m1
m1
2/ 13 + Lāag
= (2 + 2 max (2
1/2 E [ō&] +
mi
2 1300 + +za
2 + 2 max 17 13a2
E [6x] <
m1
V2 2 + max 17 12a0 } -
(Ba2. 12a2 2 41
v 17 - 1302
2 + 2 max
E 188k 5o
m1
To prove stability in the NC-NC case, we introduce the following lemma:
Lemma 11 (Hardt et al. (016))) Assume that f(x,y;)) is Ly-Lisschitz continuous and 0 < y; S Let Dmn and D'm, be two datasets differing in only one sample. Denote (X) and (KR. as the output of K steps of SSGD (single-timescale algorithm) on Dmn and D'my. respectively. Then, the following holds for every E
K). where ds
v ||xx xx,11 + llyx- -y!l?:
ko El (xx. f (x6, <
m1 + L 5k, 0].
18

---

Under review as a conference paper at ICLR 2023
Proof of Part(c). Applying Lemma 11
get ready to prove the NC-NC case. Analogous to the
previous case, we have:
(1-
[
dl
(1
df
2c
12 12
[6x+41
E [okl +
E
[ög
m1
k
m
20 17 +
cl
1
+
E
[6
+
my k
The following can be derived:
20 123 + 12
d
E
[8x]
=
0] S
II
1+
mik
k= +1 t=k+1
T
}
13 +
exp
mik
km Ro tmm4-11
K
dl
20
12 + 12
exp
m. k
#1
1=
2e 17
+
12 4
exp(el - log (K/k)
m,k
k kg +1
2c 123 + 12
K
k
-d
m7
A Ri
2, 17
9
K
mil
lio
Hence, Lemma
1 indicates:
kn
2L
13
+
12
K
el
m
mnl
Ko
The right hand side is approximately minimized when
a
Ko
(2cL.
Katt.
Therefore, we have
(2cLs
K Katt
8 I
miel
for argument stability.
C.3 TWO-TIMESCALE SGD (TSGD)
C.3.1 STANDARD SETTINGS
With step size ag and aty the update rule for two-timescale can be presented as:
([
Xk
X a, a V yk ay ΣT Vyg(
GT
yk
Analogous the single-timescale case, we first provide the expansivity of the update rules.
19

---

Under review as a conference paper at ICLR 2023
Lemma 12. Suppose that Assumptions 0 and 2 hold for Problem
7
Let al
max pa 1+(ayla)² for simplicity sake and assume 0 S 1. Then:
1-ayte
I and g are non-convex funccion,x Gr is (1 + olT) exppansive..
2. If f and g are convex functions, Gr is (1 + expansive with step size agg, Cty
3. If f and are strongly-convex with 2 and My respectively, Gr is 1 + al al-expansive with step size:
0₂ = ag S H + Hg
Proof. In Case with the NC-NC objectives by the triangle inequality, we have:
Gr [[ x
y [
-GT
Gr
(I x
y D
([x =| GT
Gr ([ x' 1)| ([x1) -Gr
- Gr
(1 x
y D
The first item can be derived from:
([ xx 1) Gr
([ x
DI-
x x' - 0z
a0 (Vf(x,)) - (x('))))
Gr
0g Ly==1 Vx - (x'
(1 0g 7,y) x x'1l
The second item can be derived from:
GT
([ x' y 1) -Gr
Gr
(I 5/4 DDI
x
y y' + T-1 02 (g Vyg (x' xx,xe)
x' - ax (Vf('')) - (x(x'')))
x' x' y y'
]| + Ei= ag (Vyg(x' Vyg (x xxxee))
as (VI(x',)) y) v. (x', y'))
From the Lipschitz continuous, we have:
T-1
T-1
Σ Og Vog(xxy)) Veg (x, 1
Σ aylo Iyy - y''l
Now we consider the t-th update:
aglg 1|x*
y'll a | ay Vug (x', x")) - --1 + ay Vug (x', y(1))|
ayyy y (y* (ag)g)
y 1
I (ayls)' (110)""1p000 - (59)7] + (agl))
1300 - (xx))
According to the accumulation of the both side, we have:
Σ ayyy ||s -(x*)|
-x Σ (aybb)) 1500 - -(-)' + (ayl ) -x-)
anyy
1 (aglg))²
(a,gg)) - (aylg)) T+1
100 (r
1 aylg
1 -aylg
1 (aglg)² T + (aylg)) - (ag1g) T+1
11500 - 1100-1
1 --ayg
(crylg) 2
||y - (y)'ll
agly
20

---

Under review as a conference paper at ICLR 2023
Let al = max (aglg; +(an//a")) 1-ayly J. then:
Gr
(I
1) Gr x 1x y
([ x
D) $1 Tal)
||
x x-x
yy
In case 2, with the monotonicity of the convex objective's 's gradient, we have:
(x - x", az (V/(x,)) V (x) 20 2 0.
(y y', Byy vxg(xx)) -
Thus, the stated result then follows:
GGr ([ x xx y 1) -Gr Gr (I
x' y
DI
x x'
y y ][
2
x x T
y y ]
ax (Vf(x,)) - Vf (x(,))))
-
ΣTO ay (Vyg(x. Vyg xx,)
Oz ( - V + Etoo ay (yg((x)')) - Vyg (x,))())
mmxx (gra2)
(1+ (agbg)
y y ]|r
x'
+ ||x x'I
S
aggl agga
(6)
and the second decomposition can be obtained by the NC-NC case:
Or (1
x xxx 1) GT
DI s (1+ max (1 + (anph)) (1x x y'
-Gr
1 -ayys agys
3) 11y Ily- y'll.
-y'l.
(7)
let al = max [
}. Combining the above equations 6 and inequality VI+ <
1-ayls (1 + ad)?, then we can derive the expansive of update rule GT under convexity condition:
Gr (I x' y' D) D|{ x x-x x' y أー y
|[
|||
cr
If f and g are strongly-convex, then, f(x.y) = f(x. 4/4 (||x + |ly and g(x, y) = y(x,y) - t (|x|| + l|) will be convex. Let 0r = ag = a and denote al = maxfa fazls, 4 can derive the following with the conclusions from the convex case:
T- }. we
(1
GT
x
Gr
x'
y
y
x - x' ]|²
_ 20xz
x x' 1"
(V((,))) - (5(x'y))
IT-
(Vrg(x,))- Vxg xx, (x,)
y y
y y-y y
(Vi(x,)) - v (x', ,)) (vxg(x,))) y¹) - Vyg (x, (x,)
ax 2
| x x'
]1²
2
(vi(x,) Vi(x' ())
2
= - -(1- + ax
+ +a²²
ΣF- Vy"(x,'') Vg xx xx)st))
y
x x'
ー ]"
T
V V)(x,y) - v/ vi(x'y))
2 azll - a Oz
(Vgō(x,y' y²) - Vyă X )))
< (1- - 2a (ry + m1y + o2?? ||x - x112
21

---

Under review as a conference paper at ICLR 2023
The penultimate inequality arises from the smoothness of f, 9, which is based on assumption for simplicity that I max(!s, [1 (1-aylo)ay
3+(ad))) ). and the details will be revealed as follows:
x - x y y 12 ?
||
vf(x,y) (x(x''
7
T-1
V)g(x. - Vgg xx xx)r))
1=
V y)(x,y) - 7f(x')1 ,r)
+ (uz + #ggg ||
x-x x'
][²
Σi= T-1
V yt) - Vyō x, xe
y-y V vf(x,y) - v)(x,y)
x x-x T
]' y-y
+ 2 (1r + +Ma)
ΣT-1 Vvr((x,y)) Vyğ X, xxyxt))
V)(,,)) - vx(')y))
+ (yy m3)²
x x-x x' y y-y
]|:
Ei (Vyo(x, y²) - Vyğ (x, (x.)1e))
Similar to the convex case, we can have:
G.
([ xx --G.
Go ([
x' y =
||
x-x
y-y'
Proof. Because the main proof of Lemma 12 is similar to that of Lemma 9 we omit it.
Next, we give bound for the update rule GT and prepare to prove Theorem Since g() is a ly -mmooth function, we have:
y (xx 41) S (x, 8") + (Vg (x, y²) y 44 -y" + Lg
2 1
+ 1g 2
{x(x,8)) (Vg (x, (x,y") ag Vg (x)
l1ay Vg
5g(x,8) - ay (1- aylo
Vg (x, ||2
2
The two sides are accumulated from t 1 to t T and we could derive the following by Cauchy-Schwarz inequality:
Vi x xx3'' g (x,
9 (x,YT)
T
Σ Vg(x,y')
<T T
V (x. y")
a, (2 ap1n)
T (g (x, 9 yr)) a2 a,y',)
Hence, the bound of GT equals to v L7a +
((o(xxy))gg(xxx
Now, we ready to give the
ay(2-a.1,)
proof of Theorem 3
Proof of Part(a). Suppose that Dyn and D',,, are two neighboring sets differing in only one sample. Consider the updates Gl..., G and (GtY.... ..... (G We can observe that the example chosen by algorithm is the same in D Dm,, D'my at step is with probability methods, in the former case, we have identical update rules, while (1 + al)-expansive be employed in the latter through lemma 10
1/ml and different with
probability 1/m,. Similarly to the previous
22

---

Under review as a conference paper at ICLR 2023
_
al)R [ōx] + 1
E [6 S
1- m1
(1
E [ōx]
111
2
(T (x, 9 (x, yrl)
2
+ m
1,702 +
a2 - -Oz4g)
T (x, (x. 2
2
(1 (1+ al) [6x] +
m1 V
1702 +
as (2 - -aglg)
E [ S
2
1.303+ + (g (x) - g (xx,)r)
(1+ k 1-1+a
-
m1
(x arlg)
V 1.90% + (0,(3-y47))
27
)² (1 + al)
B [ 0
m1
The proof of Part(b) is the same as Part(a) and Part(c) are analogous to their counterparts in the tinleetimesccae case. Thus, we omit them here.
C.3.2 PARTICULAR SETTING
We introduce the following lemma as an extension of expansivity for the particular NC-SC setting. Lemma 13. Consider Problem ( in the NC-SC setting and assume that Assumptions | and 2 hold. Suppose that (x,y) y) and (x.y') are produced by Algorithm 2 with step size Og ag. Let al = (axx(all,,, Then, we have the following expansivity equality:
GT ([ 1) Gr ([ x y D)
1 aIgT
][
x-x y y
0
1 axtl + a.
Proof. By the triangle inequality, we have:
Gr [[ x xx y 1) Gr ([ x' y
>I= Gr
([x)) Gr (1
x' y
([x' x {x]) Gr ([ x
D)
The first item can be derived from:
Gr (l
x y ))
Gr (1
x' y DII= y- y + ag Σx (V (Vyg(xx y²) Vyg(x's y")
x' - a, (Vf(x,)) - vf(x'r))
< (1 + o'l ||x - x'1l
If g is strongly-convex, then x(x,y) g(x,y) - 5 (1 + [|/l)3) will be convex. With the monotonicity of ğ gradient,, we can derive the following:
x' y
1) GT
([
x' y'
1)
GT
= =||
x' x'
y y' 11" 2a
x' - x' T
y y- y' ]'[
(Vf(x,)) y) F/(C,))
(Vgg(x')) (x0(x))))
(V fxx' y) Vf(x w'))
2
(V (1x0(x') y)- Vyg (x', .y))
x' - x'
y - y' ]1"
+ a2. 2 |1
(V50(x (x0((')) ][
(V/(x,)) y) - v((x')))
= (1 -aat4a)
x' - x'
(Vyg(x.y) V5g(2 ]
(V/(x' () - V
- (1 (rHti) ax
y y'
< (1 - ) + + 2 2 ||y y!
23

---

Under review as a conference paper at ICLR 2023
Hence, the second item can be derived GT
(I x y 1) GT
(1
x {
))
s
(1 azp2 +
aglT)lly-yi
Next, we consider the extension of the growth lemma:
Lemma 14. Consider two sequences of updates Cip...., GK and (GI)), (CKy with initial points Xo X Yo =y, Define 6x,1 -x(x and by,4 = I1yx-y'l y'll- Suppose that Gl is --exaansivv for every (x )c4)) (x,)), ((G4)+ = (xx))xx)))))) y) and
G - x ow supxy
YG+ 81 1 og. ((oty -yl
supxy
X(aby' x
supx.y
S Oz:
supxy
s S...
Then, we have
6g,441 0y,h+1
5g.k
Ox 2
S 1
0y.
Now, we are ready to give the proof of Theoree
Proof.
E 10
1+ oH
1 + (TI (4g) 1
0
1
E 1y.++1
m71
1+ d
1+ ( - Mg) 1
0
E [0
20l,
+ m1
k
E 18y
+
20f.TT
+ ol
0
][
E
[6a,kk]
20l mik
1+ c (TI- (b))
E3 [0g.
2elg T
mik
E 18
K
K
1+ 4/4
0 1+ + (TT - 1o)
11
Rel &
<
[8y.K]
201 T
k= 1
++#++
exp
Lt=k+1 k
K
2dl 2el
exp Ek Et=k+1 &h (TI (b))
k=
may
20 17 T21
K
exp
Lt= oh (Tl + pb))
k
m1
k
k=
20 12 T212 K -
K
k
(T
m1
k=
2 13 + T2z
e(((++-p))
K
mi (Tl + wny)
ko
According to Lemma we have:
21 11, + T2 9
((T(+I-)))
Ko
K
E
m. my mTl + 1b) ku
Let p= Tl+1 - Mg. The right hand side is approximately minimized when
+1
ko (2cL. / (223
CP K WT
24

---

Under review as a conference paper at ICLR 2023
Therefore, have
(2cLLV 14 12
K (p + 2/c)
mip
C.4
THE PROOF OF COROLLARY
Proof of Corollary
5 Based on the proof of previous result in
C.2
we have:
ku
2L
17
+
K Ko
dl
B (1, (d v/)
m1
m1l
The right hand side is approximately minimized when
lo (2cLsV12 11 atr
K
Therefore, have
(2cL, (
K कोे
(1 2/c)
E (1 - -f'
mil
O(K aीo /m1).
Proof of Comollar 0 Based on the previous result, we have:
2L 112 + T22
An
K
Tel
[1f((,,) - (x', 20
m1 miTl
The right hand side is approximately minimized when
ko
K kTt.. (2cL 13 +12)
Therefore, have
12 1
Jall
K TatI (TI c/2)
Tel
Blf((z 9) ff2580)))
myTl
Trofi K rdltI
m1
25

---

Under review as a conference paper at ICLR 2023
D ADDITIONAL EXPERIMENT
D.1 META LEARNING
We also conduct other experiment with single timescale (Algorithm 1 on meta learning to validate our theoretical findings. The model overfits with large value of K, which matches our theorem
155
Chess Energyy Loss
1.5
1.0
1.0
03
0.5
1.1
0.
Meta-training Loss
(b) Meta-testing Loss
(c) Generalization Gap
Figure 2: Results of Meta Learning with single timescale optimization
An additional experiment on the MNIST dataset is conducted for Theorem following the same settings on Omnilot dataset. Both Figure Ic and Figure 3c validate the influence of and 7 on the generalization gap. When K is relatively small, is dominant since the gap with is higher than that with T = 2, 4. When K is large, The effect of T fades and it contributes less to the trend of the gap.
15
T=1
T-1
04
T=2
T=2
T=4
T=4
T=1
T=8
T
T
0.5
T=4
6.1
T=8
0.0
04
300
430
500
100
202
4.00
500
500
300
400
500
(a) Meta-training Loss
(b) Meta-testing Loss
(c) Generalization Gap
Figure Results of Meta Learning with single timescale optimization
D.2 HYPERPARAMETER OPTIMIZATION
Hyperparameter optimization (HO) is also instance of bilevel optimization that minimizes the validation error model parameterized by w with respect to hyperparameter X. Mathematically, the objective function could be given by:
min L (A) = EςED. L {E)
(8a)
s.t. w = arg minE (C(w, x; + Rw,,),
(8b)
where Der and Dent are the training and validation sets and R is the regularizer. In the inner level, the procedure optimizes w using the training set (Fquation 8b In the outer level, it optimizes using the validation set (Equation Sa).
Settings and Implementation We adopt the task of data hyper-cleaning. aims to reweight data samples with the noisy label. Therefore, the hyperparameter À is the weight of each sample in the training set. We follow a similar setting in Bao et al. (202T) on the MNIST dataset [LeCun] 1998), which consists of greyscale hand-written digits with size 28 x 28. The model wo corresponds to the classification network and the hyperparameter À corresponds to the weights of each individual training sample. We establish the experiment using Py Torch (Paszke al. 2019). The model w is
26

---

Under review as a conference paper at ICLR 2023
2-layer fully connected network with size 784 + 256 10 for the 10 digit classification. The hyperparameter is a weighting vector with length 2000 for all training samples. We randomly sample 2000, 1000 and 1000 images for the training, validation and testing set. Training samples are corrupted with the probability of 50%, iee, roughly half samples are labeled with random and wrong values, instead of the correct ones. We train using the training using the validation set in the outer level. The batch size is 32 and the learning rate for w and À are 0.01 and 10, respectively. Results evaluated based the average of trial runs with different random seeds.
in the inner level and
Results Evaluation Figure44demonstratte the results of A on the regularized HO problem where the inner level function is often strongly-convex. It is clearly shown in Figure 44 that 7 causes the increase of testing loss and indicates that the risk of model overfitting increases T rises. Additionally, the generalization gap maintains a consistent relationship with both inner and outer iterations, 7 and respectively, which corresponding to our Theorem 4
1.9
T=1
T=2
Cress Entrpy Loos
1.5
T=2
T=1
T=2
Entrpy
2.5
T=4
T=4
T=4
T=8
T=8
0.00
T=8
Crots
1000
2000
4000
5000
1000
2000
3000
4000
2000
3000
5000
(a) Validation Loss
(b) Testing Loss
(c) Generalization Gap
Figure 4: Results of hyperparameter optimization with various values and
We also conduct the experiment with smaller learning rate 0.001 and larger number of steps (64, 128, 256} in the inner level. Compared to Figure 4 Figure similar behavior in terms of the effect of the value of and T. while Figure 5c performs higher variance caused by the accumulation of inner level updates. Furthermore, we can show that performance on the test dataset comparable performance with smaller inner iteration even when inner iteration T substantially increases, suggesting the effectiveness of TSGD and validating Theorem 4
T=1
T=1
T=1
T=64
T=64
T=64
2.9-
T 128
Cross Entroy
T=128 128
T=128
T= 256
T 256
256
1.5
1.1
500
1000
1500
2000
500
1000
1500
2000
300
1000
1500
2000
(a) Validation Loss
(b) Testing Loss
(c) Generalization Gap
Figure 5: Results of hyperparameter optimization with large values of T
27

---

Under review as a conference paper at ICLR 2023
E EXISTING GAP IN THE ANALYSIS OF UD
The proofs in [Bao et al. 2021 make us suspect that (A) is more or less treated as an argument independent of A, even though the description ((A) said be dependent on A.
In the proof of Theorem 2 (Appendix A.2 of (Bao et al. 2021 page 14), the following equations
given,
(A (8tr ,Sual)
(Xe, (Ae, Ne,55t Sth) =) (Xe,0)
e (A
.2) l (Xe, i (X St1) .2)
(x.
This implies that 0 (A,, St)) = 0 and 1 (N. dent of which may conflict with the dependence on A. Suppose (Bao et al.) (021) uses improper notations here, but in their following proof, there is still something confusing:
Shr) = 0 which seems to suggest that ((A) is indepen-
I to S t. They have the To understand the issue better, let de 11 Xill- Suppose that following inequality in the proof.
E [| (Ac.0) 0) (X. 0] EE if (Ae 0) (x.0) 18, -
+ +E [|s (A..0) f (x,.0) 180000
LE |de 100==0 + P (ōeo > s(f).
The left hand side is to measure the expected difference of function f with arguments (Ae, 0). The first equation decomposes the left hand side according to two possible cases of 6t, (i.e., &t, or 5% > 0). The first term of the inequality is derived from the Lipschitz continuous property of f. However, to use the Lipschitz continuity of the multivariate function f with respect to 9, i.e.
(f 0) f(M, 0) = LIIA, -Xil
i needs to be the same varible (i.c., they have the same value all the time) in both f(A,, 0) and f(X, 0). However, from the UD algorithm in (Bao al. 2021) it is clear that Ô will not always have the same value s(),, i) and f(Y, 0) when changes.
St). Since Sual and great are assumed to differ by at most one point, without loss of generality, we suppose that SGD selects the different point at timestep 1,. Then, we have
(Nto Specifically, when tor 5eo 0, Ato Xr, we have 0 Str) = @
fo+1
to
de, (ee. I
Swal) * Xe (Ae. O Sreat
d,, #0
0z (Ac,, 5t)) + 0 (X,,,
This means that 06 (X,, Str) # 00 1u+1 Str for all lgg the update of ê and use the
value of 0 in the previous iteration. Thus, we cannot use the Lipschitz property to derive the first term in the aforementioned inequality. That is why we think there may exist some gap the analysis of UD algorithms in (Bao et al. 2021).
28


Reviews:
[{"review_id": "dd04boAgPeL", "reviewer": "Reviewer_Wyf6", "summary": "", "questions": "", "limitations": "", "rating": 1, "confidence": 5, "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": "", "summary_of_the_paper": "This work studies the generalization of bilevel optimization problem. Specifically, this work analyzes the SSGD and TSGD bilevel optimization algorithms. This work adopts the notion of uniform stability on validation in expectation [1], and analyze the stability coefficient $\\beta$ to build a generalization bound of the two algorithms. This work also introduces the notion of argument stability (a special case of uniform stability), and provides a high probability bound for almost surely uniform stable algorithms. ", "summary_of_the_review": "It is nice to study the generalization of SSGD and TSGD bilevel optimization algorithms, since they are commonly used. However, many parts in this work need to be revised before being ready for publishment. For example, the author should carefully check the prior work [1], and revise claims on this work; the bound of TSGD in Table 1 should be checked and discussed; the writting should be double checked.\n", "strength_and_weaknesses": "**Strength**\n\nThis paper makes the following extensions compared to [1]:\n\n1. This paper considers the stability bound of SSGD and TSGD algorithms, which is not studied in [1]\n\n2. This paper also studies the case where the outer level problem is convex or strongly convex.\n\n3. This paper provides a better high probability bound from $O(\\beta \\sqrt{m_1})$ to $O(\\beta \\log m_1)$ compared to [1]. The improvement is significant.\n\n\n\n**Weakness**\n\nThere are some improper or incorrect claims on the prior work [1], upon which this work is built:\n\n1. [1] studies the UD algorithm, and it seems that the author has some misunderstanding on the UD algorithm. Indeed, UD view $y$ produced by the inner level optimization as a function of $x$, i.e., $y(x) = H_{T-1} \\circ H_{T-2} \\circ \\cdots \\circ H_{0} (x)$, where $H_t$ represents the gradient update in Line 6 of Algorithm 3. When UD optimizes $x$, it would use the gradient $\\nabla_x f(x, y(x); D_{m_1}) = \\nabla_x f(x, y; D_{m_1}) + \\nabla_x y(x) \\nabla_y f(x, y; D_{m_1})$, instead of $\\nabla_x f(x, y; D_{m_1})$ in Line 8 of Algorithm 3. This means that UD would backward through the optimization trajectory of $y$. However, as shown in Remark 4, the author thinks UD treat $y(x)$ as an argument indpendent $x$, which is an incorrect claim. As a result, the claim \"However, there are some technical flaws\nin their analysis...\" in Section 1, and the claim \"...and thus cannot be treated as an argument independent of $\\lambda_t'$, which is misused and causes technical flaws in their proof subsequently\" in Remark 4 are both incorrect.\n\n2. Since this work consider totally two different algorithms SSGD and TSGD other than UD. Perhaps it is less proper to state \"for the SC-SC and C-C cases with single-timescale update strategy we significantly improve the generalization bounds compared with [1]\", since the algorithm already changes.\n\n3. This work claims that \"[1] only considers a general setting for inner function\" in Section 1. However, [1] also considers convex and strongly convex inner functions. These results are provided in Appendix C in [1].\n\n4. This work claims that the bound of [1] \"is quite loose in some cases\" in Section 1. However, [1] constructs a worst case (see Appendix B in [1]) to prove that the bound of [1] is tight if no extra assumptions of inner or outer functions are provides. Besides, [1] also gives tighter bound when convex or strongly convex assumptions are made. Therefore, the claim that the bound of [1] \"is quite loose in some cases\" is improper.\n\n5. This work claims that [1] has an undesirable issue \"the stability for general bilevel optimization is still unknown\". However, the problem formulation of bilevel optimization (see Eq.(2)) in this work is exactly the same as [1]. Therefore, the range of bilevel optimization considered in this work is not more general than [1] in theory, and this undesirable issue remains in this work. As a result, the claim \"our work is the first thorough generalization analysis for general bilevel optimization problem\" is improper.\n\nOther questions:\n\n5. The notion of argument stability is a special case of uniform stability, and it is obvious that a $\\beta$-argument-stable (in expectation) algorithm is also a $L_f \\beta$-uniform-stable (in expectation) algorithm. Is it necessary to introduce this additional notion?\n\n6. Theorem (1) c assumes the algorithm $A$ is uniform stable almost surely. This assumption looks quite strong for random algorithms, since it requires for all possible randomness in the algorithm, changing a data point in the validation set won't cause the loss to change more than $\\beta$. Can SSGD and TSGD satisfy this assumption? It seems that the author does not verify this assumption for the studied SSGD and TSGD algorithms, and does not establish high probability bounds for the two algorithms.\n\n7. In Talbe 1, the TSGD with C-C setting has a $O(T^K/m_1)$ bound, and TSGD with NC-NC setting has a $O(T^{1-\\kappa_6} K^{\\kappa_6} / m_1)$ bound. The former is much looser. Why a stronger assumption leads to a looser bound?\n\nTypos:\n\n8. In the second line below Eq.(2), $g(x, y(x); \\xi_i)$ shoud be $g(x, y; \\xi_i)$.\n\n9. In the third line in the seoncd paragraph of Section 2.2, $f(x, y(x); \\xi)$ should be $f(x, y; \\xi)$.\n\n10. In Line 7 of Algorithm 2, $x_k^t$ should be $x_k$.\n\n[1] Stability and Generalization of Bilevel Programming in Hyperparameter Optimization\n\n[2] Train faster, generalize better: Stability of stochastic gradient descent", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "YH4wAwYHYC", "reviewer": "Reviewer_jxJW", "summary": "", "questions": "", "limitations": "", "rating": 6, "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": "", "summary_of_the_paper": "Authors propose to study the stability of estimators based on bilevel optimization problems. Using the notion of algorithmic stability, authors managed to bound the generalization error. This analysis is proposed for usual bilevel optimization algorithms (single-timescale and two-timescale SGD).", "summary_of_the_review": "Contribution seems interesting and new. I would appreciate if the distinction with previous work was clearer, and if experiments validate more the data ", "strength_and_weaknesses": "Major concerns:\n- Even though authors provide a long list of points comparing their work against Bao et al 2021, I am not sure I understood the difference:\n  - (1) \"Their study is only for the hyper-parameter\" I do not see how the class of problem you consider is more general\n  - (4) Could you comment on why exactly their analysis needs a renitilization of the inner parameters?\n  - (5) I agree, but you do not especially seem to provide extensive experimental results\nCould you comment on this?\n\n- **Experimental part** Except from the sentence \"The trend of generalization error in terms of K and T matches with our analysis in Theorem 4\", there are no links between the experiments and the proposed analysis.\nWould it be possible to obtain more quantitative results than \"a trend\"?\nI am not asking for SOTA experiments, but it would be nice to have quantitative experiments validating the provided theorems. For instance, would it be possible to provide experiments in the setting of Theorem 4? to compute the value of $\\beta$, and check its variation as a function of T and K?\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "X83JjKYzFvb", "reviewer": "Reviewer_rxeE", "summary": "", "questions": "", "limitations": "", "rating": 5, "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": "", "summary_of_the_paper": "This paper studies the generalization of bilevel optimization problems which are widely used in machine learning, e.g., meta-learning, hyper-parameter optimization, and \nreinforcement learning. Specifically, the authors conduct a thorough analysis of the generalization of first-order (gradient-based) methods for the bilevel optimization problem. \nTechnically, in comparison with the previous work, the (advanced) algorithmic stability tool is used to give a high probability generalization bound which improves the previous best one $\\sqrt(n)$ \nto $\\log(n)$, where $n$ is the sample size. Besides, some particular settings (e.g., strongly-convex-strongly-convex (SC-SC)) are also involved. Finally, experimental results are provided to support the \ntheoretical results.\n", "summary_of_the_review": "In summary, this paper conduct refined generalization analyses for the bilevel optimization problems over previous work via advanced stability techniques. But, some necessary discussions and revisions should be made.\n", "strength_and_weaknesses": "## Strength\n\n1. Overall, this paper is very well written.\n2. This paper is sound since the claims are supported by formal theoretical results. Besides, experimental results are also provided to corroborate the theory. \n3. The proofs seem reasonable and right although I have not checked them line-by-line.\n4. It clearly discusses the differences with related work, especially the previous work[1*].\n\n\n\n\n## Weaknesses\n\n1. The expression about \"generalization error\" is not suitable. In this paper, the authors define the bilevel generalization error as the difference between the population risk and empirical risk. It is strange because in statistical learning theory, \nthe generalization error usually refers to the population risk and the related expression in this paper can be confusing. I suggest the authors use the generalization gap, just as in previous work[1*].  \n2. While this paper refines the generalization analyses over previous work[1*], few additional insights can be offered to explain the practical phenomena and design effective learning algorithms in comparison with previous work[1*].\n3. I do not agree with the expression about the limitation of the previous work[1*] (mainly in Remark 4). [1*] made an assumption that the update of $y$ in the inner level after the reinitialization will not be affected by the value specified for $x$, which may have a gap with the practical algorithms.\nBut, the main reason is to decouple the variables $x$ and $y$, and the proof is technically right.\n4. As discussed in 3, how the authors deal with the case when updating the outer variable $x$ but the inner variable $y$ can be dependent on the $x$ and the hyper-gradient is used. Please give more explanations and discussions. \n\n\n\n[1*]Fan Bao, Guoqiang Wu, Chongxuan Li, Jun Zhu, and Bo Zhang. Stability and generalization of bilevel programming in hyperparameter optimization. NeurIPS 2021", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "LF0oEWR_Bu", "reviewer": "Reviewer_GoE2", "summary": "", "questions": "", "limitations": "", "rating": 3, "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": "", "summary_of_the_paper": "This paper studies the generalization of bilevel optimization algorithms in the framework of algorithm stability. It focuses on two algorithms, namely, single-time scale (SSGD) and two-time scale (TSGD) with first-order stochastic gradient updates. \n\nDifferent from prior work, the algorithms considered do not require reinitialization in the inner loop. Experiments on data reweighting and meta-learning are provided to show how the generalization performance changes w.r.t. the number of iterations.\n", "summary_of_the_review": "This paper considers generalization in terms of algorithm stability for two bilevel algorithms SSGD, and TSGD, without reinitialization in the inner loop, which is different from prior works.\n\nHowever, the TSGD algorithm described in the paper is different from what is referenced. Since the papers referenced all require second-order information in the update of outer parameters. But this paper does not require second-order information.\n\nAlso the summary in Table 1 is not reasonable for prior work [Bao et al. 2021], since it should also depends on $T$, the number of inner iterations.\n\nFor the above reasons, I recommend rejection.\n", "strength_and_weaknesses": "**Strengths**\n\n* The paper is clearly written and easy to follow.\n* The paper considers two algorithms SSGD, and TSGD without reinitialization in the inner loop, which are different from prior works and are important in bilevel optimization. It fills the gap in the current literature.\n\n**Weaknesses** \n\n**1. The bound is loose.** \n\n1.1)\tThe stability bounds derived in this paper seem to have worse dependence on the outer iteration number $K$ than [Bao et al. 2021]. It has exponential dependence in $K$ in the worst case in this paper while only polynomial dependence on $K$ in [Bao et al. 2021].\n\n1.2)\tNo discussion of the tightness of the bound is provided in either theoretical or empirical form.\n\n1.3)\tIt is contour-intuitive that when $f$ and $g$ are strongly convex, the stability has worse rate on $K$ (exponential) than when $f$ $g$ are non-convex (polynomial). I believe the bounds of SC-SC and C-C cases are not tight.\n\n**2. Incorrectness** \n\n2.1) Summary of the most relevant work [Bao et al. 2021] is incorrect. \n\na) My understanding for paper [Bao et al. 2021] is that it assumes the compositional function $f(x, \\hat{y}(x, D_{m2}); \\xi)$ w.r.t. $x$ is Lipschitz continuous, which also has a dependence in number of iterations $T$ in the inner loop. Therefore, the summary in Table 1 for UD[Bao et al. 2021] which does not depend on $T$ is not accurate. In addition, [Bao et al. 2021] provides the results of convex case in the appendix.\n\nb) What is $\\nabla f$? The comparison of UD[Bao et al. 2021] and TSGD in appendix A is not correct as the gradient of $x$ in the outer loop is not the same based on my understanding. Because it requires second-order information for UD[Bao et al. 2021].\n\n2.1) Outer update/reference of SSGD and TSGD is incorrect. \n\na) In Algorithms 1 & 2, the update for outer parameter $x$ does not take gradient w.r.t. function $\\hat{y}$? Could you add references to the two algorithms analyzed in this paper, for single timescale and two-time scale, separately? \n\nb) If the update for outer parameter $x$ does not take gradient w.r.t. function $\\hat{y}$, it is not the same as the algorithm for some two-time scale methods referenced in this paper such as [Ghadimi & Wang, 2018], [Ji et al. 2021] as they require the second-order information of the loss during the update of $x$.\n\n**3. Lack of clarity**\n \na) How does the results in this paper compare with existing stability analysis on specific bilevel problems such as minmax problems and meta-learning?\n\nb) Although different algorithm stability concepts are defined, only uniform-stable in expectation is used for the main theorems in Section 4. Why do you need to define uniform stability with probability $1-\\delta$ in Definition 4, (a)?\n\nc) Why do you need Theorem 1 (c)? Theorem 1 (c) is not used in Section 4.\n\nd) The proofs are not clear. Some proofs of the TSGD case are omitted due to claimed similarity of the SSGD case (see pages 20-21). However, I suggest that you include proof for TSGD case and omit the SSGD case.\n\n**3.2 Minor comments**\n\na) In Theorem 1 (c), what is $e$?\n\nb) In Theorem 1 (c), A is uniform stable with probability at least $1 - \\delta$?\n\nc) Throughout the paper, why do you use $\\nabla_y g$ for the update of $y$  and $\\nabla f$ for the update of $x$ but not $\\nabla_x f$ ?\n\nd)\tThe notation $G$ is used for both inner population risk and update function, please use different notations to avoid confusion.\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}]

Author rebuttal:

Decision: Reject