Lower Bounds of Uniform Stability in Gradient-Based Bilevel Algorithms for Hyperparameter Optimization
Authors: Rongzhen Wang
Chenyu Zheng
Guoqiang Wu
Xu Min
Xiaolu Zhang
JUN ZHOU
Chongxuan Li
Venue: NeurIPS 2024 poster (2024)
Keywords: Uniform stability
Lower bound
Hyperparameter optimization
Bilevel programming
Primary area: learning_theory
TL;DR: We establish  uniform stability lower bounds for representative gradient-based bilevel hyperparameter optimization algorithms.

Abstract: Gradient-based bilevel programming leverages unrolling differentiation (UD) or implicit function theorem (IFT) to solve hyperparameter optimization (HO) problems, and is proven effective and scalable in practice. 
To understand their generalization behavior, existing works establish upper bounds on the uniform stability of these algorithms, while their tightness is still unclear. 
To this end, this paper attempts to establish stability lower bounds for UD-based and IFT-based algorithms. 
A central technical challenge arises from the dependency of each outer-level update on the concurrent stage of inner optimization in bilevel programming. 
To address this problem, we introduce lower-bounded expansion properties to characterize the instability in update rules which can serve as general tools for lower-bound analysis. 
These properties guarantee the hyperparameter divergence at the outer level and the Lipschitz constant of inner output at the inner level in the context of HO.
Guided by these insights, we construct a quadratic example that yields tight lower bounds for the UD-based algorithm and meaningful bounds for a representative IFT-based algorithm.
Our tight result indicates that uniform stability has reached its limit in stability analysis for the UD-based algorithm.

Lower Bounds of Uniform Stability in Gradient-Based Bilevel Algorithms for Hyperparameter Optimization
Rongzhen Wang Chenyu Zheng Guoqiang Wu
Xu Min', Xiaolu Zhang', Jun Zhou', Chongxuan Li
1 Gaoling School of Artificial Intelligence, Renmin University of China
2 Beijing Key Laboratory Big Data Management and Analysis Methods School of Software, Shandong University Ant Group {wangrz, cyzheng, chongxuanlij@ruc. edu. en; guoqiame inw.unnngguuu.cmmmm edw. edu. en;
minxu. mx@antgroup.....m.mmmmmooooo com; {yueyin. zxl,jun. zhouj Mhoujunneee aennunnnttatttaneeanennannaennne Cant in. com
Abstract
Gradient-based bilevel programming leverages unrolling differentiation (UD) or im- plicit function theorem (IFT) solve hyperparameter optimization (HO) problems, and is proven effective and scalable in practice. To understand the generalization behavior, existing works establish upper bounds on the uniform stability of these algorithms,, while their tightness is still unclear. To this end, this paper attempts to establish stability lower bounds for UD-based and IFT-based algorithms. central technical challenge arises from the dependency of each outer-level update on the concurrent stage of inner optimization in bilevel programming. To address this problem, we introduce instability update rules which can serve as general tools for lower-bound analysis. These properties guarantee the hyperparameter divergence at the outer level and the Lipschitz constant of inner output at the inner level in the context of HO. Guided by these insights, we construct quadratic example that yields tight lower bounds for UD-based algorithm and meaningful bounds for a representative IFT-based algorithm. Our tight result indicates that uniform stability has reached its limit in stability analysis for the UD-based algorithm.
expansion properties to characterize the
Introduction
Hyperparameters significantly influence the convergence behavior of learning algorithms as well as the efficiency and generalization performance of the trained model [ 2 3]. Hyperparameter
optimization (HO) algorithms aim to find the best hyperparameters (associated with the optimized model parameters) on a validation set. Classical approaches for HO include grid search 44, random
search [5], Bayesian optimization [6, 7 8), and evolutionary algorithms 19, 10), which often suffer
from the problem of scaling up. Recently, gradient-based methods have achieved excellent empirical
performance in high-dimensional HO problems [1] 3 12]
In gradient-based methods, HO is formulated seeks the best model parameters on the training set given current hyperparameters. In the outer level, hyperparameters are optimized with gradient descent. However, the gradient difficult to compute as it requires differentiating the optimized model parameters w.r.t. the hyperparameters. Two mainstream strategies have been developed to obtain this Jacobian by explicitly unrolling differentiation (UD) 13
bilevel programming problem. The inner level
2 [4] or approximately applying the implicit function theorem (IFT) [ 15 16 [2]
Correspondencee Chongxuan Li.
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

To investigate the underlying reason for their success, existing work establishes generalization upper bounds based on algorithmic stability [1] In particular, [17] presents a generalization framework associated with a notion of uniform stability for general bilevel programming in HO and stability upper bounds for the UD-based algorithm. Despite their efforts, such algorithms have not been fully understood and one of the key unsolved problems is whether existing stability analyses are tight.
To this end, this paper establishes lower bounds on the stability of gradient- based bilevel programming algorithms for HO. Technically, we begin by introducing lower-bounded expansion properties which inherently characterize the instability in general update rules including stochastic gradient descent (SGD) as detailed in Section 4 Our expansion properties, to a certain degree, mirror those introduced by [19]. with the distinction being our emphasis on lower bounds rather than upper bounds. This approach not only enables a comparative analysis with upper bounds to evaluate their alignment (i.e., tightness) but also lays down a conceptual framework for analyzing the lower bounds of algorithmic stability, generally applicable to both single-level SGD and various bilevel algorithms.
Building upon these properties, we explore the stability of the UD-based algorithm in Section 5 We first present a recursive stability lower bound that aligns with the existing upper bound at the outer level given the expansion properties of the compound validation loss, followed by an analysis of the Lipschitz constant of the inner output to maximize those expansion coefficients. Guided by these theoretical insights, we construct a quadratic example that yields a tight lower bound for the UD-based algorithm with constant step sizes and a nearly tight lower bound with linearly decreasing step sizes with respect key factors. Mcaningful bounds for representative IFT-based algorithm are also provided in Appendix C based on its essential connection to UD>-based methods. We highlight that the example is carefully designed to obtaín explicit stability lower bounds by overcoming the challenges posed by the intricate behavior of the bilevel algorithms, i.e. the dependence of each outer-level update on the current turn of inner optimization.
We outline our contributions as follows: (I)
We introduce lower-bounded expansion properties that can serve as general tools for analyzing lower bounds of the stability in gradient descent. (2) To our knowledge, we present the first lower bounds of uniform stability for both the UD-based and representative IFT-based algorithms, facing the challenge posed by the intricate formulation of the outer update in bilevel optimization. (3) Our lower bounds match existing upper bounds for the UD-based algorithm, verifying that uniform stability has reached its limit in characterizing the generalization of the UD-based algorithm. Detailed results are summarized in Table [
2
Related work
measures the change in the model output when a single training example is replaced. It shown be sufficient and necessary for learnability in certain cases (22). Stability-based generalization analysis of an algorithm typically consists of three key elements: a notion of stability, -tabelity-based generalization bound, and a stability analysis depending on the algorithm. Below, we introduce the related work based on these three elements.
Algorithmic stability 20 21
Algorithmic stability. 23 introduce uniform stability, which characterizes the worst-case change of loss and presents a stability- based generalization bound with high probability. Notable efforts [24] 25 26 (7] have been made to obtain sharper bounds for uniformly stable algorithms in general. Besides the uniform stability, various notions of stability that characterize the average change [22), local
change 288 change in the hypothesis 22 30 investigated for fine -nn-iga analyses.
Stability of stochastic gradient descent (SGD). SGD has been one of the workhorses in deep learning and therefore attracted much attention. To unravel the mystery behind its success, [19 analyze its (randomized) uniform stability on (strongly) convex and nonconvex losses. [31] analyze the uniform stability of (S)GD for nonsmooth convex losses and provide sharp upper and lower expectation bounds. 32 30 consider the on-average stability for SGD and build dete-dependent generalization bounds to explain the effectiveness of practical techniques like proper initialization.
Recent work establishes lower bounds on the uniform stability of SGD and investigates the tightness of corresponding upper bounds. [3 proves a general minimax optimal lower bound for stability generalization error together with optimization error on convex and smooth losses. [31] finds the general technique proposed by [33] is sub-optimal in convex but nonsmooth cases, and provides

---

sharper lower bounds by constructing special class of loss functions. [34 adopts a similar approach by construction present lower bounds for smooth and potentially nonconvex loss functions.
In this paper, we focus on the smooth and nonconvex cases in HO and provide stability lower bounds
by construction as [31] and 3A Compared with 34. consider more complicated and nontrivial
bilevel optimization problem, where the interaction between inner and outer processes brings
significant impact on the analysis. A detailed comparison is provided in Section 5.3 and Appendix B
Stability for bilevel programming. [77] extend the notion uniform stability to HO and analyze stability upper bounds of the UD-based algorithm, while the tightness of their result is largely open. Recently, it has been extended to the analysis of implicit gradient algorithms [18]. This
paper provides the first lower bounds, generally applying to two main categories of gradient- based
HO methods. There are other bilevel optimization algorithms 12 35 36
37
38
39
15] and
settings 2 16
42 4
where our framework can potentially be extended in future work.
3 Problem formulation
3.1 Elementary notations and definitions
Scalar, vector, and matrix. We employ lowercase letters (e.g., a), lowercase boldface letters (e.g., a), and uppercase boldface letters (e.g., A) to denote scalars, vectors, and matrices, respectively. For vector |I-Il denotes its Euclidean norm. For matrix A, ||-I| denotes its spectral norm. Additionally, let a = a2 denote and a2 are collinear by non-negative factor, namely, 3a 2 0 s.t. ai = aQ2-
Loss function. A differentiable function & Ω R is L-Lipschitz continuous if Vu, E Ω [(((u) - E(v)] & L|| - v/I. It is 7-smooth if Vu, v E Ω, [VV(() V((v)]] S 7 ll|.
Twin datasets. A pair of datasets are considered twin datasets if they differ in only single data point, denoted by S ~ S. Throughout this paper, we use tilde symbol to distinguish their corresponding notions, e.g., examples and 2, output parameters ur and ic.
Asymptotic notations. Denote with On S bn that on is bounded above by bn up to a constant factor for sufficiently large n, and conversely by an bn We say a, b, if a, S b, and an Z bn.
3.2 HO as bilevel programming
Denote the testing, validation, and training distributions the data space 2. by Dtest, Dvall and Dtr, and corresponding losses by grest, geal and ftt Since the validation phase is generally regarded as a rehearsal for testing, D and grai are commonly assumed to be consistent with Diest and frest
Given validation set Sval = {x]=1]] )m
i.i.d. ~
(Dra))" " and training set S = {- Jy=1 i.d. (Dtr)", parrrrratttttrrrrrtteerr
HO algorithms seek the best best-performing hyperparameter-pinn parameter pair Swall Denote by À the hyperparameter in space A, the (model) parameter in space θ. This process can be formulated as the following bilevel problem:
TR
n pt (t) 0: )
gval (2,0(A); >,aa),, where 0(2) Rs arg min Σ Å arg min AEA m
Σ OEO n2
Here, 0()) is selected by its training performance under the given and eval) (>, (());)) can be rewritten as a compound validation loss L(>; x) considering ( a function of A.
Various methods are proposed to solve this nested problem. among which gradient- gradient-based algorithms
have recently achieved success in scalability [1] 12 As shown Algorithm I gradient-based methods utilize SGD as the optimizer at both levels, where the primary challenge lies in the calculation of the gradient of the compound validation loss, called hypergradient,
VxC(A=2) vaalal (2. (x)=2) VAOK of (A (A, (A):2))
(I)
Jacobian

---

where the inner Jacobian involves differentiating through the inner-level optimization. To this end. the UD-based methods obtain the exact inner Jacobian by directly unrolling the inner differentiation
K-1
Vx (A)
Σ
Th+
(2,00)
II (I mh+1 (2. 0,)). <=++1
0=
While representative IFT-based methods leverage the implicit function theorem and Neumann series to obtain an alternative estimation [2]
K Σ 7K (2.00
vx = - "IK ( 0K
R=
Please refer to Algorithm| for the whole process. Notably, this paper adopts a common theoretical assumption [19 17 of constant inner step sizes and decreasing outer step sizes
Algorithm 1 Gradient-based bilevel HO
Input: Initialization Ao and Po: training set Str and validation set Sual; step size scheme a and r)
2: Output: The hyperparameter Xy and hypothesis 0
3: for 1 to T do
4: for k k= 1 to K do
5: uniformly sampling js from [n]]
6: 0g < 0x-1 The Vo o (Ac-1: O k- (
7: end for
8: uniformly sampling & from [m]
9: g -
(= (.) val)
UD-based algorithm in Eq. ② IFT-based algorithm in Eq.
x - 04g
11: end for
12: return AT and 0K
3.3 Generalization and stability of HO
The generalization behavior of HO algorithms characterizes the selected model's potential perfor- mance on the unseen test data. Specifically, denoting the hyperparameter output by stochastic HO algorithm A as A(Sval, Str), we are interested in the difference between its expected testing risk and empirical validation risk, namely generalization error defined as
m C(A(Sval, ; m Σ
1
'gen E AA BenDien [[(A(saal
Stability-based gencralization theory turns this problem into measuring the algorithmic robustness. We define the notion of uniform argument stability for HO algorithms, which captures the variation in algorithm outputs when replacing a single validation point 4
Definition 3.1 (Uniformly argument stability on validation). stochastic HO algorithm A earg" uniformly argument stable on validation where
Carg Smal EZ E
sup
EAIl St) A(šval S*)
(5)
Our analysis mainly leverages this notion following 31. under the Lipschitz continuous condition. Earg differs from the uniform stability estab defined in [17] Definition 1] only by Lipschitz constant L (i.e., Estab S Learg), and our results for Estab are also
it is the key measure for stability bounds
For formula neatness, we set an unused 7 NNaeely, пІ. = and S with constant 0. The decreasing step size also widely adopted in the optimization convergence analysis works, such as SGD [44 45 AdaGrad [46), Adam 48)
+1 = as placeholder, and similarly 4r = 0 in Eq.
'Definition33. 3.1 considers considerrs provided in Appendix G.I
perturbing the validation set instead of the training set. The relevant discussion is

---

provided in Theorem and Theorem C.7 for direct comparison with former works. Existing stability-
based generalization bound [7 Theorem shows that uniform stability guarantees generalization in expectation for HO algorithms that 6gen S 6stab-
Former work 17 constructs the first stability upper bound for UD-based HO algorithms. This result is fundamentally based on an upper-bounded recurrence relation of the distance between the outputs respectively optimized on twin validation sets, denoted by 6, := || Aell at the 1-th step.
Theorem 3.2 (Recursion upper bound for UD, Theorems 2 and 3. (17). Suppose the compound validation loss [(:;2) x) is L-Lipschitz continuous and y-smooth for all z E 2, and the training loss ( X, x;²) is 7d -mmoohhhh for all À E A and E Z. Then for all 1 S t < T, [aa6d]] S
[] [1+ (1 1/m))a77 [a(66-1] + 20yL, where L S (1 + k Y S (1 + 17
Unrolling this recursion, we directly get the stability upper bound in recursion form:
T T+1
Carg II
(1 1/mm)7 200L
(6)
m
[=1 ==1+1
As this result does not explicitly display its order w.r.t. T under decreasing step sizes 04 I c/t, further deforms Eq. ( with the bounded loss condition to obtain Estab S TT-1/m)504 /m.
17
analyzes specific IFT-based algorithm, which, under certain assumptions, achieves a similar result of éstab X /m with g < 1. Though these stability upper bounds have been established, their tightness is rarely explored, and the stability of IFT-based algorithms remains largely open. Therefore, this paper takes a first step towards establishing stability lower bounds (namely, how unstable an algorithm can be) for both UD-based and IFT-based HO algorithms.
18
4 Expansion properties of update rules
This paper endeavors to establish tight lower bounds for uniform (argument) stability defined in Definition 3.1 which is fundamentally the supremum of the output divergence. For iterative algorithms, this divergence accumulates recursively across the whole optimization process. Therefore, we first introduce lower-bounded expansion properties in Section 4.1 to characterize update rules that will induce guaranteed divergence at each iteration. This is followed by an analysis in Section 4.2 on how the objective functions within SGD need to be structured to satisfy these properties. We will see in Section 5 that, for gradient-based HO algorithms, these properties jointly lead to lower-bounded divergence recursion given the outer-level update properties in Theorem 5.1 and a lower-bounded Lipschitz constant of the inner output given the inner-level update properties in Theorem [5.2
Our expansion properties correspond, to some extent, with those presented by [9] and the key difference lies in focus lower bounds rather than upper bounds. This approach not only facilitates comparisons with upper bounds to discuss their alignments (i.e. tightness) but also provides general framework for analyzing the lower bounds of algorithmic stability.
4.1 Lower-bounded expansion properties of general iterative algorithms
Let w be a general notation for parameters (or hyperparameters) in space Q. An update rule is a function G Ω + Ω that maps w to its next state G(w). and an iterative algorithm is composed of a series of consecutive update rules. We denote two sequences of update rules by {G.] (G.)-=,, and the corresponding outputs by {w,) and [w/]-
17 and
Intrinsically, the divergence between w, and w., dynamically evolves across the entire process, driven by two factors: disparity in current update rules, and difference in current parameters resulting from prior updates. Our goal is systematically analyze how variations between two update sequences lead to substantial divergence in outputs. In the following, we introduce Definition 4.1 and Definition 4.2 correspondingly characterize properties of update rules leading to increasing divergence.
Definition 4.1 (o-divergent). Two update rules and G' are o-divergent along v if for all w E Ω
G(w) - G' (w) v. G(w) G' (w)ll 2 a.
Definition 4.2 (p-growing). An update rule G is p-growing along if for all w, w' Ω such that w w' parallel with v,
G(w)= G(w")= = ww, [[G((w) - G(w')) plww-- w'
5

---

0,12000
Upper
Lower bound
Upper bounds
0.01015
fiting uppa bourd
Linear firing of the lower bound
0,01000
0,00000
0.0115
0001500
0015000
0.0008
0.0000
0.0100
0.0111
00012
0.0013
0.0144
Hyperparameter distance
Figure 2: Practical output distances vs. theoretical
bounds in Theorem 5.. We implement UD-based
Figure 1: The loss surface of two-dimensional example: {(0)
Algorithm D on Example 5.3 The output hyper- parameter distances with increasing I' are plotted on the horizontal axis. The upper/lower bounds with corresponding T are plotted the vertical axis. The linear trends suggest these three values are of almost the same order w.r.t. T.
1 w Aw where A
The direction v is highlighted in red, along which exhibits expansive property.
0
Intuitively, o-divergent update rules produce sufficiently divergent output parameters and a p-growing update rule scales the divergence between parameters with a sufficiently large factor. The direction chosen as the most expansive direction, as detailed with a concrete example in Section 5.4
4.2 Lower-bounded expansion properties of SGD
One-step SGD can be generally formulated as Gt.a (w) w a V((w), where the loss function directly impacts this gradient-based update rule. We now define the μ-expansive property for the loss function which leads the growing property of SGD.
Definition 4.3 (p-expansive). A differentiable function é Ω + j-expansive along v if for all w, w' E Ω that w w' parallel with there exists Hw, 2 such that
V((w) V((w') aoo (w w
This paper mainly focuses on the case when > O where the loss function is nonconvex. We have μ for the convex case. When μ 0, Definition 4.3 connects to p-strongly concavity These concepts are equivalent in the one- mie-dimeniional case. In general, j--stronlly concavity imposes uniform curvature in all directions, while p-expansiveness restricts concavity in only one direction with an additional restriction for the colinearity of V((w) Vé(w") and -(w w'). See Appendix G.2 for details. We illustrate simple loss function in Fig. that satisfies Definition
Notably, the directional restrictions on the update rules in Definitions to simplify the lower- bound calculations as it enables to focus only the norm of the divergence each step and get rid of directional variation, which aids in clearer understanding of divergence dynamics. As a first attempt establish stability lower bounds for bilevel optimization problems, our work leaves open whether these conditions can be relaxed. A potential approach might involve requiring the divergence exhibit a specific directional component rather than strict alignment as in the current definitions.
The following lemma shows that the expansiveness the loss function can induce the growing property of SGD.
Lemma 4.4 (Growing property of SGD with expansive loss function, proof in Appendix B.2 Suppose is p-expansive along u and 1 + ap 2 0, then Gr,a + -gowwing along v.
Namely, Yw, w' E St. (V((w)- V((w'), w') -u/lw w/ll?

---

Lower bounds on uniform stability in HO
Based on tools introduced in Section 4 this section proceeds to precisely characterize the stability of gradient-based bilevel HO algorithms. In Section 5.1 we provide a power-bounded recursion of
hyperparameter divergence that aligns with Theorem 3.2 given the expansion properties of the outer optimization, followed by lower bound of Lipschitz constant of the inner output given the expansion properties of the inner optimization in Section 5.2 These findings pose insights in the construction of Example [5.3 at both the inner and outer levels to maximize the instability of HO algorithms. This quadratic example produces a tight lower bound for UD-based algorithms, detailed in Section [5.4] and meaningful bounds for IFT-based algorithms, provided in Appendix C
5.1 Stability lower bound given outer-level expansion properties
We first establish a uniform argument stability lower bound by considering the outer level of the bilevel programming as single-level optimization problem w.r.t. the hyperparameters. This approach takes the compound validation loss L as whole, temporarily disregarding the dependence of this loss on the inner-level solution and the inner Jacobian.
Suppose Sval and Sval are twin validation sets differing only on the i-th entry, and denote the se- quenees of update rules on Sval and Sival as [G.,, =1==1 and {G ... )T=YT._P rrepectivvly According to Definition 3.1 the uniform argument stability is lower-bounded by the hyparameter distance after T steps, which primarily depends on the divergent property of update rules on different examples and the expansiveness of the compound validation loss. By characterizing these properties and utilizing Lemmas and B.2 we obtain a lower bound of the stability in the following Theorem [5.
Theorem 5.1 (Lower bound given outer-level expansion properties, proof in Appendix B.3). Suppose there exists nonzero vector along which Gz,,a and Gz..a, 2a, L' L''-divvergent and Z( is 7t p'eexaansive for all z E gival, Then we have [
2 [1+ [1+a0 ae 1/) [>>]/xA0r-1 16
20, and
T T+1
Carg Σ
II
a1+a, 1/mm))
L
m
Theorem 5.1 echos the upper bound formulation in Eq. 6 The distinctions arise solely in the smooth/expansive coefficients 7/>" and the continuous/divergent coefficients L/L', Consequently, the alignment of these two bounds (i.c., their tightness) hinges on the values of these coefficients. As detailed later in Section 5.2 we delve deeper into the coefficients present in our lower bound by unfolding the bilevel problem, focusing on the solution of the inner level and its Jacobian.
Further, Theorem 5.1 not only applies to all HO algorithms that employs outer-level SGD but also to single-level SGD. In the context of single-level SGD, the expansion properties can be directly inferred from the loss function, as elaborated in Appendix
5.2 Lipschitz lower bound given inner-level expansion properties
Based Theorem 5.1 our next step towards building stability lower bounds is analyzing the expan- sive coefficient 7 and divergent coefficient L' of outer-level optimization where the hypergradient used for update. As can be observed in Eq. (I). the inner Jacobian V x xA)) is key bridge between the inner and outer level that significantly influence the hypergradient. Here, we measure the lower bound of its maximum volume, i.e., the Lipschitz continuity coefficient of x (A) regarding denoted by _xx, x, provide guarantee for the effect of the hypergradient.
Denote corresponding inner update rules as Gx,,, and Gx.,, given hyperparameters À and X. Apply- ing them consecutively for K times, get two sequences of inner updates. Theorem 5.2 presents how the expansion propertics of the inner problem characterize the lower bound L
Theorem 5.2 (Lower bound of Lipschitz of the inner-level solution, proof in Appendix B.4 Given any two hyperparameters X, X E A, suppose there exists nonzero vector v along which Gx.,, and
We slightly abuse the notation in the subscript of the update rule as in Section 4.2 this contest can be solely distinguished by the selected sample. We use similar simplification for the inner update rules in the next section.
since the loss function in
7

---

Gy are a - X divergent and (" ;2) is pt -xxpansive for all 2 E S with n² > 0. Then
we have
T ttH
TH [11 + "11"" m)"")) 1].
Omitting constants that depend on 7), ot,, and n², we get 1,0x 2 (1 + ))
It is worth mentioning that lower bound for 1 is matched with its upper bound in 17 (see in Theorem and Proposition 2), which prepares us to obtain tight lower bound.
5.3 An example with maximal simplification
Motivated by Theorems 5. and 5.2, the following example is carefully constructed, exhibiting all expansive and divergent properties as required by these theorems to establish tight lower bounds on uniform argument stability of gradient-based baased HO algorithms.
Example 5.3. We introduce an HO problem as follows. The validation loss and training loss are given by:
eval 0) (*, 0; A A0 + A yæ
where A E Rdxd is symmetric. Denote the eigenvalues of A as 71 I ... S Td- Let 71 < 0 and Ia| 2 hal. and Vi be a unit eigenvector for 7/1 Let Sival and Sival be pair of twin validation datasets differing the i-th example where
2, = (a vi) = (V1, 1), (-
In this example, A determines the convexity of the problem. Throughout the main text, we consider the most common nonconvex case where A is indefinite and symmetric. See Appendix for the results of (strongly) convex losses.
Notably, example satisfies Assumption B.I adopted for establishing the stability upper bounds where the loss functions are Lipschitz continuous and smooth. Hereafter we denote L(;; x) as T-Lipschitz continuous and y-smooth, and g (x, 1;) ""*-smothh, where 7tr hal-
Example 5.3 constructed adhering to the principle of maximal simplification. Specifically, the quadratic form is essential for inducing nonconvexity. The second bilinear cross term represents the simplest scenario for interaction between hyperparameters and parameters, ensuring non-zero inner Jacobian. The final term provides connection for parameters and data. eval and fer are set to be identical here for simplicity, and our results do not fundamentally depend on their consistency.
We emphasize the role of the eigenvector (i.e., f1) which corresponds to the smallest eigenvalue. represents the least convex direction, thereby offering the greatest expansiveness of the loss (see Fig. [. and both the inner and outer optimizations attain the highest level of divergence and expansiveness in this direction. Consequently, in Example 5.3 the distinct samples in gvall and Šival are set to align reversely with 81 make the HO algorithms unstable.
Remark. The constructed example is required to meet two essential criteria: first, it must reveal the instability inherent in the algorithms; second, it must allow precise calculation of the smoothness coefficient 7 and the expansion coefficient ju for the compound validation loss to verify the alignment between lower and upper bounds. Simultaneously satisfying these two requirements is challenging for bilevel algorithms. In Appendix G.3 we provide a ridge regression example to illustrate how the bilevel structure complicates the analysis of stability lower bounds.
5.4 Lower bounds of UD-based algorithms
The following proposition shows that Example induces the expansion of UD-based algorithms.
Proposition 5.4 (Expansion properties of UD- UD-based algorithmss, proof in Appendix B.5). Suppose we solve Example 5.3 by UD-based Algorithm with constant inner step size 1j where I 77/ 2 and outer step size an- Then (1) the outer update rules Gz,an and G2,a, are 20y I'- divergent along ur and (2) the composite validation loss L(:; x) is of -xpxanssvev along vn for all z E Svall where
LX x'
"r) K n x (1 mm 22
8

---

Combining the lower bound in Theorem 5.1 with the upper bound in Eq. 6 we instantly get
T (1+al (1+a(1111//1)
T II (1+ (L+a,(111/m))
20
201 (7)
earg
m
m
=1+=+11
=1141
where the bounds are in the same order w.r.t. T, K and m. These matching bounds in recursion form verify the tightness of the existing upper bound [17].
Specifically, for constant step sizes, i.c., a₁ = c for all t, Eq. explicitly reveals the scale of earg
regarding T: carg x (1 + c(1 1/m)>)* /m. However, for linearly decreasing step sizes ae S c/t, additional scaling steps are necessary and the deformed result is provided below.
Theorem 5.5 (Uniform argument stability of UD-based algorithms, proof in Appendix B.6 Solving with constant inner step size y where Ti 2 O and decreasing outer step sizes at c/t with as a positive constant has uniform argument stability that
Example 5.3 by UD-based Algorithm /
(1n(1+(1- 3)0))
T 1 jey
Earg
where y = x (1
17 as in Proposition
The scaling steps unavoidably create discrepancy between the deformed lower and upper bounds, while their quotient, T Iny-- )er',, is small given a small (e.g.. 0.01). We compare the practical output hyperparameter distances and the theoretical bounds in Fig.
Notably, the upper bound in our result is not contradictory to the existing upper bound of carg A f1-1/mine
Ta-1/m/vet] /m in 17 because we remove the bounded loss assumption, i.c.. Ea, 6 E RR s.t. L b). This modification is necessary to fairly compare the upper and lower bounds. Detailed discussion is provided in Appendix E.3
Based on the results of uniform argument stability, stability by introducing additional assumptions as below.
further obtain similar results of uniform
Theorem 5.6 (Uniform stability of UD-based based algorithms, proof in Appendix B.7). Following the same condition as in Theorem 5.5 and additionally, if the initial points Og 0, Ao 0, and
V1 1. ar for any j E [m]]y Vi and vi I. a. for any j E [ni), then Algorithm has uniform stability
that (1111 20)))) I Estab T0-- bey
where 7 7/ x (1 + 222K as in Proposition 5.4
to simplify the formulation of [(>r, 2) L(Xr, 2) by eliminating the quadratic term and reducing it to be colinear with ' X/- By doing so, clear relation can be established between the loss divergence and the hyperparameter divergence, which leads transfer from uniform argument stability to uniform stability.
Technically, we adopt these additional assumptions following 34
Remark. For now, we have characterized the stability error as an upper bound on the generalization error. Let
examine how this stability- based generalization bound informs the allocation of data between the validation and training sets. Suppose we have a total of N data points, with aN assigned to the validation set g and (1-a) assigned the training set StT, where a E 10. 'Te expected population risk can be decomposed into the generalization error and the empirical validation risk as follows:
-
m C(A(Sval ) xaa)
A, Sir gtea [C(A[Sva), Sur); zlett]
Egen + S.all ()
m
(
On one hand, the generalization bound Egen I Extab @(1 ((1/aN) (as in Eq. suggests that should be sufficiently large to keep term (I) small. On the other hand, should also be sufficiently small to get a low validation risk in term (II), since a larger training set generally improves validation performance. Thus, selecting involves trade-off to optimize the overall population risk.
For instance. 1 S c is used in 19

---

Conclusion and discussion
This paper establishes novel lower bounds of the uniform stability for various HO algorithms and shows the existing upper bound in UD-based algorithms is tight. This result indicates that the notion of uniform stability has reached its limit in stability analysis for the UD-based algorithm. The expansion properties proposed in this paper can serve as general tools for analyzing lower bounds of stability. This paper applies them to both single-level and bilevel optimization. We also discuss in detail potential extensions of our analysis framework on establishing average stability lower bounds and generalization lower bounds Appendix H.
Limitations and social impacts. This paper is constrained in the scope of smooth loss functions, while non-smooth scenarios [31] remain open. Moreover, uniform stability lower bound does not directly imply generalization lower bound. This gap exists as algorithmic stability is inherently introduced as a theoretical tool for analyzing the generalization upper bound. Alternative approaches might include directly deriving a generalization lower bound with examples considering the data distribution. This paper a purely theoretical work, we have not identified any direct, significant societal impacts that must be emphasized.
Acknowledgments and Disclosure of Funding
This work was supported by Beijing Natural Science Foundation (L247030); NSF of China (Nos. 62076145, 62206159); Beijing Nova Program (No. 20230484416); Major Innovation & Planning Interdisciplinary Platform for the "Double-First Class" Initiative, Renmin University of China; the Fundamental Research Funds for the Central Universities, and the Research Funds of Renmin University of China (22XNKJ13); the Natural Science Foundation of Shandong Province (Nos. ZR2022QF1 17), the Fundamental Research Funds of Shandong University; and the Ant Group Research Fund. The work was partially done at the Engineering Research Center of Next-Generatton Intelligent Search and Recommendation, Ministry of Education. G. Wu was also sponsored by the TaiShan Scholars Program.
References
[1] Yoshua Bengio. Gradient-basee optimization of hyperparameters. Neural computation, 1889-1988 2000.
[2] Luca Franceschi, Paolo Frasconi, Saverio Salzo, Riccardo Grazzi, and Massimiliano Pontil. Bilevel programming for hyperparameter optimization and meta-learning In ICML, volume 80, pages 1563-1572, 2018.
[3] Hanxiao Liu, Karen Simonyan, and Yiming Yang. DARTS: differentiable architecture search. In ICLR, 2019.
[4] Mehryar Mohri, Afshin Rostamizadeh, and Ameet Talwalkar. Foundations of Machine Learning. Adaptive computation and machine learning. MIT Press, 2012.
[5] James Bergstra and Yoshua Bengio. Random search for papee--rr optimization. Journal of machine learning research, 13(2). 2012.
[6] Jonas Močkus. On bayesian methods for seeking the extremum. In Optimization Techniques IFIP Technical Conference: Novosibirsk, July 1-7, 1974, pages 400-404. Springer, 1975.
[7] Jasper Snoek, Hugo Larochelle, and Ryan P Adams. Practical bayesian optimization of machine learning algorithms. Advances in neural information processing systems, 25, 2012.
[8] 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. The Journal of Machine Learning Research, (11))3098-3122 2020.
[9] 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.
10

---

[10] Max Jaderberg, Valentin Dalibard, Simon Osindero, Wojciech M Czarnecki, Jeff Donahue, Ali Razavi, Oriol Vinyals, Tim Green, lain Dunning, Karen Simonyan, et Population based training of neural networks. arXiv preprint arXiv: /7/ 1e11117111..99. 2017.
[11] Jelena Luketina, Mathias Berglund, Klaus Greff, and Tapani Raiko. Scalable gradient-based tuning of continuous regularization hyperparameters. In International conference on machine learning, pages 2952-2960. PMLR, 2016.
[12] Jonathan Lorraine, Paul Vicol, and David Duvenaud. Optimizing millions of hyperparameters by implicit differentiation. In AISTATS, volume 108, pages 1540-1552, 2020.
[13] 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.
[14] 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, pages 1723-1732. PMLR, 2019.
[15] Fabian Pedregosa. Hyperparameter optimization with approximate gradient. In JCML, vol- ume 48, pages 737-746, 2016.
[16] Aravind Rajeswaran, Chelsea Finn, Sham M. Kakade, and Sergey Levine. Meta-learning with implicit gradients. In NeurlPS, pages 113-124, 2019.
[17] Fan Bao, Guoqiang Wu, Chongxuan Li, Jun Zhu, and Bo Zhang, Stability and generalization of bilevel programming in hyperparameter optimization. Advances in neural information processing systems, 34:4529 4541, 2021.
[18] Congliang Chen, Li Shen, zhiqiang xu, Wei Liu, Zhi-Quan Luo, and Peilin Zhao. Exploring the generalization capabilities of AID-based bi-level optimization, 2024.
[19] Moritz Hardt, Ben Recht, and Yoram Singer. Train faster, generalize better: Stability of stochastic gradient descent. International conference on machine learning, pages 1225-1234. PMLR, 2016.
[20] William Rogers and Terry J Wagner. A finite sample distribution-fiet performance bound for local discrimination rules. The Annals of Statisties, pages 906-514, 1978.
[21] Luc Devroye and Terry Wagner. Distribution- performance bounds for potential function rules. IEEE Transactions Information Theory, 25(5):601 1979.
[22] Shai Shalev-Shwartz, Ohad Shamir, Nathan Srebro, and Karthik Sridharan. Learnability, stability and uniform convergence. The Journal of Machine Learning Research, 11:2635-2615 2010.
[23] Olivier Bousquet and André Elisseeff. Stability and generalization. The Journal of Machine Learning Research, 2:499-526, 2002.
[24] Vitaly Feldman and Jan Vondrak. Generalization bounds for uniformly stable algorithms. Advances in Neural Information Processing Systems, 31, 2018.
[25] Vitaly Feldman and Jan Vondrak. High probability generalization bounds for uniformly stable algorithms with nearly optimal rate. In Conference on Learning Theory, pages 1270-1279, PMLR, 2019.
[26] Olivier Bousquet, Yegor Klochkov, and Nikita Zhivotovskiy. Sharper bounds for uniformly stable algorithms. In Conference on Learning Theory, pages 610-626. PMIR, 2020.
[27] Yegor Klochkov and Nikita Zhivotovskiy. Stability and deviation optimal risk bounds with convergence rate ((1/n). Advances in Neural Information Processing Systems, 34:5065-5076,
2021.
11

---

[28] Zhun Deng, Hangfeng He, and Weijie Su. Toward better generalization bounds with locally elastic stability. In International Conference on Machine Learning, pages 2590-2600. PMLR, 2021.
[29] Tongliang Liu, Gábor Lugosi, Gergely Neu, and Dacheng Tao. Algorithmic stability and hypothesis complexity. In International Conference on Machine Learning, pages 2159-2167. PMLR, 2017.
[30] Yunwen Lei and Yiming Ying. Fine-grained analysis of stability and generalization for stochastic gradient descent. In International Conference on Machine Learning, pages 5809-5819, PMLR, 2020.
[31] Raef Bassily, Vitaly Feldman, Cristóbal Guzmán, and Kunal Talwar. Stability of stochastic gradient descent on nonsmooth convex losses. Advances in Neural Information Processing Systems, 33:4381 1-1991, 2020.
[32] Ilja Kuzborskij and Christoph Lampert. Data-dependent stability of stochastic gradient descent. In International Conference on Machine Learning, pages 2815-2824. PMLR, 2018.
[33] Yuansi Chen, Chi Jin, and Bin Yu. Stability and convergence trade-off of iterative optimization algorithms. arXiv preprint arXiv: 1804.0/619 2018.
[34] Yikai Zhang. Wenjia Zhang, Sammy Bald, Vamsi Pingali, Chao Chen, and Mayank Goswami. Stability of sgd: Tightness analysis and improved bounds. In Uncertainty in artificial intelli- gence, pages 2364-2373. PMLR, 2022.
[35] Risheng Liu, Jiaxin Gao, Jin Zhang, Deyu Meng, and Zhouchen Lin. Investigating bi-level optimization for learning and vision from a unified perspective: A survey and beyond. IEEE Trunsuctions on Puttern Analysis and Machine Intelligence, 44(12): 10045--0066 2022.
[36] Kaiyi Ji, Junjie Yang, and Yingbin Liang. Bilevel optimization: Convergence analysis and enhanced design. In ICML, volume 139 of Proceedings of Machine Learning Research, pages 4882-4892, 2021.
[37] Mathieu Dagréou, Pierre Ablin, Samuel Vaiter, and Thomas Moreau. framework for bilevel optimization that enables stochastic and global variance reduction algorithms. In NeurIPS, 2022.
[38] Saeed Ghadimi and Mengdi Wang. Approximation methods for bilevel programming. arXiv preprint 1802..1802.002 2018
[39] Xuxing Chen, Minhui Huang, Shiqian Ma, and Krishna Balasubramanian. Decentralized stochastic bilevel optimization with improved per-iteration complexity. In ICML, volume 202, pages 4641 1671, 2023.
[40] Luke Metz, Ben Poole, David Pfau, and Jascha Sohl-Dickstein. Unrolled generative adversarial networks. arXiv preprint 1XXiv:661.0021666 2016.
[41] Lingxiao Wang, Qi Cai, Zhuoran Yang, and Zhaoran Wang. On the global optimality of model-agnostic meta-learnng. In ICML, volume 119, pages 9837-9846, 2020.
[42] Hong Li and Li Zhang. A bilevel learning model and algorithm for self-organizing feed-forward neural networks for pattern classification. IEEE Transactions on Neural Networks and Learning 2020.
Systems,
[43] Risheng Liu, Jinyuan Liu, Zhiying Jiang, Xin Fan, and Zhongxuan Luo. A bilevel integrated model with data-driven layer ensemble for multi-modalle image fusion. IEEE Transactions on Image Processing, 30:1261-1274, 2020.
[44] Saced Ghadimi and Guanghui Lan. Stochastic first-and zeroth-order methods for nonconvex stochastic programming. SIAM journal on optimization, (44)))333122366 2013.
[45] Léon Bottou, Frank E Curtis, and Jorge Nocedal. Optimization methods for large-scale machine learning. SIAM review, 60(2))223-311 2018.
12

---

[46] Li Shen, Congliang Chen, Fangyu Zou, Zequn Jie, Ju Sun, and Wei Liu. A unified analysis of adagrad with weighted aggregation and momentum acceleration. IEEE Transactions on Neural Networks and Learning Systems, 2023.
[47] Fangyu Zou, Li Shen, Zequn Jie. Weizhong Zhang, and Wei Liu. A sufficient condition for convergences of adam and rmsprop. In Proceedings of the IEEE/CVF Conference on computer vision and pattern recognition, pages 11127-11135 2019.
[48] Congliang Chen, Li Shen, Fangyu Zou, and Wei Liu. Towards practical adam: Non-convexity, convergence theory, and mini-batch acceleration. Journal of Machine Learning Research, 23(229):1-47, 2022.
[49] Yunwen Lei. Stability and generalization of stochastic optimization with nonconvex and nonsmooth problems. In The Thirty Sixth Annual Conference on Learning Theory, pages 191-227. PMLR, 2023.
[50] Alireza Fallah, Aryan Mokhtari, and Asuman Ozdaglar. Generalization of model-agnostic meta- learning algorithms: Recurring and unseen tasks. Advances in Neural Information Processing Systems, 34:5469-5480, 2021.
13

---

A Overview of main results
A.1 Overview of main contributions
Table Overview of main contributions. The results presented here derived without the bounded loss assumption for fair comparison. Deformed bounds are derived under decreasing step size ar I c/t where > 0 a constant.
Our contributions
Comparable results
Expansion properties
o-divergent, p-growing (Ours)
a-bounded, -/-epaasivee 19
Recursive lower bound:
Recursive upper bound:
E II + a, 1/m)n') 20, where 7 = x (1+ ))7"")2k m
I1 + a22 1/m)
20y
where 7 S (1 + 2))
m
L' x (1 + t) (Ours)
L L (1+ "7 11
UD-based algorithm
Deformed lower bound:
Deformed upper bound:
S 7 1/m)er
where 7 x (1+ m7+m7*)) (Ours)
where ? S (1 17 (Ours)
Recursive lower bound:
Recursive upper bound:
E T II T (1 (1++00 a1 1/m))") 20,L'
Σ
T (1+ + a2 1/m)?)
20,4 m
where y = (1 m7(r)2
where y S K(1 m)*")22
L' x (1+ ") (Ours)
LS (1 ") (Ours)
IFT-based algorithm
Deformed lower bound
Deformed upper bound 7
where 3 2 (1 + ")))) )2 (Ours)
where y S K(1 + 177 fr j22 (Ours)
14

---

A.2 Dependent graph of main results
Definition 4.1 o-divergent update rules
Definition 4.2 p g-growing update rules
Definition 4.3
μ-expanstvee loss functions
specified on SGD
Lemma B.2
Lemma
Recursion of parameter divergence given expansion properties of update rules
Growing property of SGD given the expansive loss
Theorem 5.1
Theorem 5.2
Lower bound of uniform argument stability given expansion properties of the outer optimization
Lower bound of the Lipschitz constant of the inner output given expansion properties of the inner optimization
inspire the construction
satisfy
Example 5.3
Assumption B.1
Constructed example with Lipschitz continuous and smooth loss
Theorem 3.2
Proposition 5.4 for UD
Upper bound of uniform argument stability in recursion form
(Proposition C.5 for IFT)
Expansion properties of HO
algorithms on Example 5.3
Eq. 7 for UD
Theorem 5.5 for UD
(Eq. 11) for IFT)
scaled
(Theorem C.6 for IFT)
Tight uniform argument stability bounds recursion form
Deformed uniform argument stability bounds with explicit orders
Theorem 5.6 for UD (Theorem C.7 for IFT) Deformed uniform stability bounds with explicit orders
Figure 3: Dependent graph of our main results. The blue node denotes previous results and others our contributions. The solid line represents direct proof dependency. The dashed line is annotated with text therein.
B Proofs of main theoretical results
B.1
General assumptions
We first list some assumptions in the derivation for upper bounds 177, which are common theoretical conditions for an HO problem. We follow these assumptions throughout Section 5 The constructed Example 5.3 also satisfies these assumptions.
Assumption B.1. Let Ω be an open set including A x θ Z, we assume that
15

---

1. A and è are compact and convex with non-empty interiors, and 2 is compact,
2. (nl (A, 0; E (22), that is, gval is second order continuously differentiable on Q2
3. / (2, 0) E (92), that is, sp: is third order continuously differentiable on Ω
4. (A, 0; z) is " -smooth as a function of 0 for all 2 E Z and À E (the first and third points imply such constant 7th exists).
B.2 Proof of Lemma 4.4
Lemma 4.4 Assume & is y-expansivee on v and 1 + ap 2 0. then Gt, (1 + au) -growing on v.
Proof. Recalling Definition 4.3
for any w' colinear with we have
G G(,aww))
=w - w' a (V((w)) V((w'))
=w - w' + aa(w w')
=(1 + afw (w w'):
where Uroww' 2 j and thus 1 + afflw 2 1 + ap 2 0 by assumption. Therefore, we have Gt. (w) Ge (w') w w' and || (w) Gt. w ||
(1 [aa))/ww - -w']], which implies
Gt (1 + -growing on a according to Definition
B.3 Proof of Theorem 5.1
As the divergence of each step is entwined with prior results and shapes subsequent evolution, we first provide the following recursion for the parameter distance using the expansion properties. Lemma B.2 (Recursion of parameter divergence). Let the initial points be wa w/ Ω. Suppose there exists a nonzero vector v along which, for all S S T, Gt + G2 are a-divergent and G. are p-growing. Then we have We- w - v for all S t < T and recursively,
| w6ll 0, w will 2 {
p p|::-1 -
w to, G G. G = G
-w/ w [|llllo0
121.
p w
w
Proof. Without loss of generality, assume en is a unit vector (i.e., |/l = 1). At the initial point, we
have WD w/ = v. According to Definition 4.1 and Definition 4.2 if w - w/_ _ _ v, then
w, w/ = G;(w,, G((w(-1))
G (w(wi-1) - (w +
Gi(((=1)
G: + G¹
Gi(w[-1) G((w)
G. G
Pe(w,-1 -w w/-1) + o2v,
G.# G% G G/
Pe(wi-1 w/(1),,
(Pollwi-1 w/-1 + Dv
G G G G, G
Pellw,-11
w
where P: 2 p and or 2 a. Thus, we have the above recurrence relation for parameter distance, and all subsequent parameter divergence will be in the direction of v.
Now we are prepared to prove Theorem 5.T Suppose there exists a nonzero vector along which Gz and az are 2/ ddvverettttt and L(: x) is r/-expansive for all Sval, Then we have
T
20
Σ
II (1 (1+as 1/m)n') ==
Carg
m
Proof. Using Lemma 4.4 we have Gz and Gs are (1 arr for all 1 1t T. Denote ò, || X for each step t. As Algorithm is initialized with the same starting point,
16

---

we know that Au = Ao and thus 60 0. For all 1 st T, there is probability of 1 1 to select the same examples and otherwise. Consequently, by the law of total probability, have the recurrence relation
EA(o,] 2 1 1
EAl(1 + arr m EAlór-1 + 20x4' (Lemma B.2 the law of total probability)
1 + ++(111 - m n
BA |
20, L'
=
(linearity of expectation),
By unwinding the recurrence from T to for all S = 5 2m, su
2
we have
II (1+as(1-1/m)) 20rL'
EA(ōT]
Σ
(8)
m
t=
which implies
II (1 as 1/m))') 20,L'
Earg Σ
m
t=1 111e0t1
B.4 Proof of Theorem 5.2
Here we prove more general version of Theorem 5.2 the main paper by additionally considering the cases where / 0. Theorem 5.2 in the main paper can be simply derived by letting p > O.
Theorem B.3 (Lower bound of Lipschitz of the inner-level solution, generalized Theorem 5.2 Given any two hyperparameters X, X' A, suppose there exists nonzero vector along which Gx.,, and ;2) Gx a are ||> X' lath divergent and er (x, 2) is pt" -expansive for all E Sur where 1 mpp 0. Then we have
" mutt [(1 + mu 1], o K, o"
tr > 0
0xxx
nx O,
nla [1 -(1 - 11)/1001)
10 < O.
(1 )
p 0, 4 0, /²
Omilting constants that depend on otx, and nht we gel 10x
K,
1,
Proof. First, for any À and X', we establish a lower bound of ||0 (A) - 0 (X'Il in a recursion way. Using Lemma 4.4, we have Gx,,, and Gx are (1 ")) >-growing. For any inner step 1 & k < K, we have
(A) (x')ll
1, (0 (A)) Gx.,
| (0 (A)) GA, (X') + (x-((0= - (0 (X'))I
2 (1 + nu | (A) - (x-( + - - 1 ||ll|lll
(Lemma B.2
= (1 + 7/4 )1 (A) - 0x-1 + + - -
XII|]
[||al| = 1)
= (1 + np ()=")1(0==11 - 0x-1(X') + - A XII.
(1 + np" 2 0)
Using the fact that the algorithm is initialized with the same starting point and unwinding the above recurrence from K to 1, we obtain
K-1 (1+
| 0K (x
nn 7 XII,
km0
which implies that for any X E A. According to mean value theorem for vector valued multivari- able function, there exists c on line segment determined by À and X' such that ( 2
17

---

(A] 0x (X) []. and for triangle inequality, we have x - XII 2 [[0x(c)A- -XIII-
Therefore, by the definition of Lipschitz continuity, it holds that
our (1+nung mur
10x (A) A
0x (X)ll
K-1
1x 0,
k 2 [c)x
Σ
na
Iut K, o 1011-g//e" nlutt
112h 0, 11 O,
XII
which completes the proof.
B.5 Proof of Proposition 5.4
Before deriving Proposition 5.4 we present a technical lemma as follows.
Lemma B.4. Suppose that E Raxd is a symmetric matrix. We denote v1...., Ua the orthogonal unit eigenvectors of A and "/1 .... I "Ya the corresponding eigenvalues, where assume that 1 - ma 2 0. Then it holds that
K-1
K-1
K-1
E [I k=0
74)
21 - 7A - 7
=
Σ
m2)*
2 m
Σ (1 m))* k=0
k=
(1
1)))22
71 < 0
K
71 0,
1.
m1 > 0.
Proof. For simplicity, we denote v) > --1 (I nA)* 7)) ( 12 (I- by C, then C
symmetric and has eigenvectors U1.... Va as well. Based on the symmetric C, ||C|] equals its maximum absolute eigenvalue, which can be expressed as
||||| = suppl Cupll
K-1
K-1
Σ A=
(1 - m-)* 2 - m: Σ k=
(1 775)**
sup
27/K
7i = 0,
sup
11 Σ k= (1 (1-77))
-177/
177
1- 1-
1- ()x)
7/ *
2nK
7 0,
sup
"Σ k= (1-17:)* (1 (1- k7))
K-
7/2 + 0.
The last equation for 7/ A holds for 17; 2 mia 0.
We define h17) o (1- + (1- 17) k), which is decreasing on (-o0, 7u]. achieving the maximum at the smallest eigenvalue 71. Therefore,
K
K Σ k=
1-
71 <
||||| = n Σ (1
m
- m
(1 - m71
x
K.
= 0, V1 > O.
k=0
1,
Now, we are ready to prove Proposition 5.4 Here we prove a more general version of Proposition 5.4 in the main paper by additionally considering the cases where Y1 2 0. Proposition 5.4 in the main paper can be simply derived by letting 71 < O.
Proposition B.5 (Expansion properties of UD-based algorithms, generalized Proposition 5.4 Sup- pose solve Example 5.3 by UD-based Algorithm
Al-oorhhl 7 with constant inner step size 1) where 177a 0
18

---

and outer step size Then (1) the outer update rules Zz and Gz are 20 divergent along and (2) the composite validation loss L(;;)) is 7f -expansivvv along for all 2 E Sval, where
(1+ tr
21 < 0, 71 = 0, and = == x
(1 + m7
22
71 0,
LXL' x
K,
K,
0,
71 0,
1,
71 0.
Proof. As Example 5.3 satisfies Assumption B.1 we have L' - L S (1 + m trrk K by Theorem 3 in 17.
We are going to verify that L' 2 (1 + 17
and > 7 2 + 77 22k in the following.
Given a hyperparameter X, a constant step size and a initial point 0g. at each step 1 I & < K, we have an inner update
Gx,,(0x-1)) = 0:-1 V/
(A, Ax0x-1;2
1
=0 V 0 0 A0x k-1 + A 0k-1
2/
tr
O
0 17( (A0x=11 + X //a
- [U-1A)0--1 7({ 2リ x
where ju is uniformly sampled from [n]] Recursively, we gel
(x( = -Aa. (Gam(..GAm((0))
(),)((0)))
K-1 = (I- 0o (A) -2
k=0
so that
K-1
VxOx = -1 Σ [ (I-
k=0
As I,' and 7 describe the expansion properties of SGD on L, we first investigate the gradient of the compound validation loss
VC(A= = = 0x + Vx0x (A) (A0x (A) + - yyx)
For all X E A, the outer update divergence when SGD picks the distinct examples
Gz (A) Gz (A) a. aa (VL(A; 21) VL(A;
az VV K (A)
(-y: --0;
-20 VAOx(A (T)
11
(yi: = -0i 1, 30 Ui 3; v1)
K-1
20u1 Σ
(I -/)
(A is symmetric)
k=
K-1
2017
(1
(Av1 = v1
k=0
K-1
20ul
Σ
(1 177 "
(7 30"=|=== --1)
Recalling Definition 4.1 we have Gzaar and Gzio, are a, L' divergent along v1, where
K-1 = m1+ = nk x K - "1 /
m1+ 1//h = (1+m>
a 0,
71 0,
(10)
71 0.
For the case that 71 O, we have L' x (1 WrKK
19

---

Next, we are going to clarify that (()) is y expaansiee along U1, and > equals to the smooth constant y of (()). As C is twice differentiable, according to the definition of smoothness, we have
sup AEA
Supl|VA [(A; I|
IV k (A) + VAOR(AA)
(AVAOR(M) (AV + 1)Il
(V)0x(A)= = 0)
K-1
K-1
Σ 11 nA)a
21 - 1-
Σ
(1 nA)*
K=
k=
K-1
K-1
1 Σ (1 (1-m)) (1-m²)
2 m
m
Σ
(1 m))
(Lemma B.4
k=
" Σ (1 + th
2 177 tr
(1 m
(II)
(1 m))x
11 < 0, 71
K,
1.
71 > O.
Eq. 11 holds for 7tr = m/ = ->1 For all X, X' E A, such that X X = =wv 01 where
E R. we have
(((;;
2)(A22) 0x(A)- +xx(A)
+ +x0x((A) (A) (A0x(A)+ +X yz) VxOO((A)) (AO (X') + X' yyx)
K-1
K-1
K-1
Σ 71-1 - x) -1 Σ
(I (I-
-An
Σ (I 1))4a +1 +1)1-
k=0
k=0
K-1
K-1
Σ k=0
(I A)
21 7A Σ
II 7A)*
(A X')
k=0
R-1 Σ k=0
K Σ
=
(I - (I-1AA)
21 A
(I A²)*
avi
k=
K-1 Σ
K-1 2 m Σ
(1-m))
-
(1 7b &
avi
K=
k=
K-1 Σ
K-1
(1+m #gk
2 1+ 177 tr
Σ
(1 + m/
(A (1-1))
-1
0=
k=
=- X³)
According to Definition 4.3 this implies (()) is -eexxnssivee along 01. Therefore
(1 + 2r)2
71 0,
x
K,
0,
1,
71 0.
For the case that 71 < 0, we obtain that > = 7 x (1 + 22
B.6 Proof of Theorem 5.5
Here we prove a more general version of Theorem 5.5 in the main paper where 71 < 0 by additionally considering the cases where 71 2 0.
20

---

Theorem B.6 (Uniform argument stability of UD algorithm, generalized Theorem 5.3 Solving Example [53 by UD-based Algorithm D with constant inner step size oi where ni 2 and decreasing outer step sizes c/t with as positive constant has uniform argument stability that
T1n(1+(1- Jee)
T Joy
Earg
m
77
(1
)
711 < 0,
where 7 = 7/ x
K,
711 = 0,
as in Proposition B.5
1,
71 0.
Proof. We first derive the left side of the result (i.e., the lower bound). The derivation is built upon the resursion form of the lower bound in Theorem [_]] and utilizes a scaling operation that when
In In(++(1-1mmoc²) it holds that
2 exp(ræ) for any {(1 - 1/mmmm/////tt /t/1 Tt
(1-1/m30r
According to Theorem 5.1 we have
T
20yL'
II
(1 + a1(1 1/m)>/)
Earg
1=
amt+1
T
T
1
L0,L'
exp
1 m
m
s=++1
1
2CT.
2cI!
exp
1
(a: = c/t)
m1
lm
T'
2cL!
2cL'
exp
1
o
m
Tm
T+1 1
2cL'
2cL'
exp
c
+
(12>4>00 Eie,, 1 In =
m
t ++1
tm
Tm
r(1-1/m)or
T+1
2cL'
t+1
tm
1=1
2eI.
(T + 1)"d (1-1mmmm (1-1/m/m)o
m
2eL'
(T + 1) (1-1/mm))
dt
m
2
(Va > 0, D.T aa-1
_/2
T+2 1a-
(T + -1 (1(1m//m) -
2cL'
(T ()-))((-
2
m
r(1 11-1/m)om
r(m 1)71 (T + 1))(1- 1/mmor/ (2-((1-1mm)) (T + (1111mmy)
2L'
T+1 In 1n(1(1111/mcc>)
-1]
2cL'
In [+([-11/mmm)
(r
mln (1 + (1 1/m)ey
(1-1/mJey'
21

---

Then, we continue to derive the right side of the result (i.e., the upper bound). Based on Eq. (6 we have
204L
II s=t+1
(1 + a,
1/m)>)
Earg
m
T
II exp
(1-
yc
2cL
2cL
tm
T'm
t=1 ==
(1 m
1
Σ
1
2cL
2cL
exp
YC
lm
T'm
#=1+1
(1-
1
T
2cL
2cL
exp
celn
16>44,,, 1 5 (-ا
m
Im
Tm
(1-1/m))
2cT.
tm
2cL 7 11 1mm
T - (1-11/m)7e-1
1=1
2cL T( - (11m/))
1 / /
T
t (1-1/mm)00-1 dt
(va 0, Ei a-- s1+ f d--
2cL
(1+ (1- - 1/m) ((-1/mm)
m(1 1/m)oy
2L
( (1+ (1- 1/ml) xc) (11-111)) - ].
(m 1)%
Therefore, it holds that
ln( Im(L+(L22/m)er))
2cL'
T+1
-1
1 (1 1/m) 7c) (11-1/m) - 2L
S Carg I
(12)
mln(1 1 + (1 1/m)cy')
(m 1)7
Omitting the constants depending on c, 7, and L, yt and L', we have 7" (1-(1- mn son))
S Earg S
m
-- m
)er
which completes the proof.
B.7 Proof of Theorem 5.6
Theorem 5.6 Following the same condition as in Theorem 5.5 and additionally, if the initial
points Og 0. Ao O, and U1 i anaal for any j E [m]]i and 01 1 x.r for any j E [n], then
the order of uniform stability Gsabb w.r.t. 7 satisfies (1 de te7") 7 = (1 m try2K as in Proposition 5.4
T-ll 4 )ey
Catbb
where
m
m
Proof. In the following, we show that 6stab explicitly shows the same order as carg in Theorem 5.5 with additional assumptions for Example [.3] For the upper bound, it is easy get with Lipschitz condition that
EAllCCAASSva ,St)): L(A(Sva), )²);))]1]
Estab
sup
Stal S S 22m www.ssuEEea EE2
<
sup
[A stt) A(Sival S
&yul= 22 Su
L.arg:
22

---

and according to Theorem 5.5 we have estab S T- th Jey
To obtain the lower bound, we need to explicitly derive the optimization process of A(5 "(" and A(S (t)) (i.e., Ar and X and corresponding loss values.
From the proof of Proposition 5.4 we know that
(2) GA.n (G2m(...GGAmm GAm((o)))
K-1
= - nA)
K 00 - Σ (I n))a 11
k=U
K-1
= Σ (I nA)* (A - 1r
Vi )
(0g 0)
k=
Σ (I ,A)*> + Σ (I
AA ッリ 3/
k=
= - B + bk
where symmetric matrix BK = 1) Σk= (I 7²)** and vector b = 11 Σド= (I nA u x.
Building upon 0- (A), we can derive C(X, z) as
1 L(A, 2)
0x (A)
0 (A) yo 0K (A)
2
1-BBA+
bK)
A(- M bR) (- BR bb) -ya (- bk)
2
(BxABR 2Bx) +
T AB + T yo Bxx +
2 bx
Ab
yo b
2
1
1
Bx (ABB 21 T AB + DK + yz BR) DK
Ab ya T b
2
whose gradient is
VAC(A, 2) = BK(ABR - 21) (-BRAb
- + +b + yBKx)
= =Bx(ABr - 21)A yB b% Ab
Then, the update rule of À can be expressed as
A = at V VxC(A=-1,2
= - - at Bx(ABK - 21) + y,, BR x;, + b B Abbb
= [ - al (AB 21) A - 0r33/ B K; at (b - B KC Ab
Now, by unwinding the recurrence from T to 1 with A = 0, we can obtain
Ay I Bx - 21 Σ II [ a. Bx (-arth Br
+=
T
Σ II
I a, - 21) (-o B Ab
s=141
Σ
T- (ABx 20)-222 Bx
T a (-or B Ab*)).
I [1++
(0g = 0)
23

---

Recall that g and Stal only differ in the i-th entry where (2;, vi) (v1. 1), 2, = (i; 04)
(-U,,1) 1). Denote 1[:] as the indicator function. We simplify the term follows:
T
T
II
I -
BR -2)1
-a,BB
Σ 1 5
1=1 s=1+1
j=l
T
T
1 i]
I1
I- a. - -2)]
smttl
T
T II
Σ
1h =
I - O. oR -21] (koaaky
1
Σ
14 5]
II a. Bx 221)
T
Σ
14 =1
II
Bx (ABx 221] (-a,Bxo1)
t=1
8=t+1
T
T II
1/4
B, - -21) (-a,BKyjz))
a.
jyl
1=1
s=++1
K-1
(-aun
K-1
Σ
11 i
II
I 0
Σ (I (An Σ
(I - (I-mA)* -21)
Σ k=0
(I 7A)
1=1
x=++1
k=0
1 5]
II
[I
ag BR
21)] (-a,BRyja)
t=1
T
T II
K-1
K-1
K
Σ
1/ -1
0
Σ k=
(1 - 1-
Σ
(1 - (1-1m1)* 2)
Σ (1 (1-mi)) mm
11
[=1
k=0
k=
T
T
14 = 5
II
T
a, Bx - 21)] (-oz BKUjTj)
J
1=1
s=t+1
T
Σ
1[
II a=t+1
[1 - a. I' - 2)] (a,T.) 01
t=1
bi=Tu
Lli 5l
II 8=1+1
I B. - 21)] (-a,Bry,e))
jt t=1
where L' = K-1 (1 1711 as in Proposition B.5 We further define a == ai + a2, and then Ar = 02 - b = - b. Follow the same process of derivation, we have ÅT a + where the opposite symbol for b arise from x; v1 while ã; Vi.
Recall that we have assumed that V1 Φ for any E [n] and U1 1 val for any j E [m]] that j + i, thus v b% = 0 and vj x, 0.j # E [m]. Therefore,
a b
b - Bx T
II s=t1
I --aaa a,BB - -21) TU
m
1l4 5 (-o B.,
I a, Bx (AB -21) 781.
J
24

---

As BK E (I- and 1ı is the eigenvector of A, we have a b = 0, i.e. a 1 b.
Now, we are ready to discuss L(AI, z) C()r,2) 2).
[(xr,2) 2)
2 B - - + bK T AB + bK + +y Bx
BT 21)
(-b T AB + DE + +y Bx)
1 - (A -1)
Xy (AB -1) TT ABx bx + ya J Bx) ÅT),
where
1 aa b) B (AB (T) b) (a [a+ bb B (1)
2
-2a BRBBBA 21)
2b Bx 21)a
- B (ABK 2
(by symmetric)
-4aJ DO)BB((AB - TU1
44(nI' - 2)Ta T
=0.
Therefore, C(AT, 2) - L(AT, 2) can be simplified as
2)) L(²T, (-b AB D + y (R) - AT)
--2(-b% b AB + btr + yæ Bx)b
-x - -2b)
-2yxx B
-2yL'ra' " V1. UU.
(b TV=)
Let x² = (V1, 1), we have
[C(Ar, x1) c()r, x 2L'r|| 2L'r= L' Årll-
(lAr drll = 2T)
Therefore, by the definition of Cstab, have
(1+a,(1- 1/m)'') 20,L'
Estab 2 [C(AT, x²) L(Âr, x L'II
Arll > Σ II
m
t=1 s=t+1
where the last inequality holds for Eq. Theorem B.6, we can further derive
8 in the proof of Theorem 5.1 Following the proof of
In(14(21//m667)
2cL
2
T+1 2
Estab
mln (1 + (1 1/m)ey/)
Omitting the constants regarding 7 and L', we have Estab 2 1 (0 100))
which completes
the proof.
C Deferred results of IFT-based HO algorithm
Based on Example 5.3 we also investigate and establish a stability lower bound for the IFT-based algorithm. The stability analysis for the IFT-based algorithm is conducted following the same proof idea as the UD-based algorithm. Similarly to the analysis for the UD-based algorithm, we first obtain the expansive and divergent properties of the outer level in Proposition C.3 Appendix C These jointly lead to uniform argument stability bounds in Theorem For completeness, we also derive upper bound for the IFT algorithm based on existing techniques 17), presented together as follows.
We first introduce several lemmas useful for the following proofs.
25

---

Lemma C.1 (Lemma 2 in [7]). Suppose A and θ are convex and compact with non-empty interiors.
is compact, 2 is included an open set St and f(,.0; x) C** (St), then.for all i S k order partial differential h(x,, 0: z) of f(x, z), we have sup [|,(2, 0: A), 00 and 0E0,2E2
sup
(0)..e:))llee..
oc.
2
Lemma C.I implies that any S. 1 order partial differential of (A, 0;z) is Lipschitz and any i S
order partial differential of e*T 0, z) is Lipschitz continuous under Assumption B.1 We denote the maximal Lipschitz constants among them as Q.
Lemma C.2 (Theorem in 17
Denote 0x (X) L -iischhttt continuous, we have L S
(1 + (1+m")) ")
Lemma C.3. In the case of Example 5.3 the Vx0x (A) calculated by the IFT-based algorithm is exactly xx)x
Proof.
K
VAOK(A) - -o (A, (A)))n
1
2o ehr (A, (A, (AA))
K-1
1 Σ n-- K=
(A)x(A).
(Eq. 9
Now, we are ready to prove Propositions C.4 and C.5
Proposition C.4 (Lipshchitz properties of IFT-based algorithm). Suppose we solve Example 5.3 by IFT-based Algorithm with constant inner step size n where 1 - mya 2 0 and outer step size a Then the composite validation loss L(;22) is L-Lipschitz continuous and 7-smooth for all Svall where
L (1 (1+ r S K(1 (7
Proof. According to Lemma
in 17]. the Lipschitz continuous
coefficient
supxEA VAC(A; =)] For all X E A, we have
V VAL(A; |)|| = V val
V Vx (A, (A) (A, 0 A.Ok((A)z))
< V vm val
(A (A 2)
+ A,
(2.
< 9
(20K(A)
K-1
QQ+ Q
ViA lx (x))x
I (A
<Q V2 ET (A, (A)
(A
I (A,
k=
K-1
<Q+ Q
Σ
1 + // v2 20 pt (2, (x))))*
K-1
<Q+1Q²
Σ
(1 + "*
km
+ Q2 (1+ (1+ K -1
26

---

Omitting the constants depending on Q, n,, and n", we get L S ((1 + +m""))).
To obtain the smoothness coefficient 7, we first discuss the Lipschitz continuty coefficient of vxOx(A) In the following, we use E to represent etT (>, 0x (A)) when there is no ambiguity.
K-
VA VA = VA
m
I -
(A00
V (2. 0x
k=
K-
(Frse + VAO oxe
I - 1o
Σ
k=U
B1
K-1 V2
(Vio box e" + Vx0x (2Ox (t) )(({)
n Vo0 k-1
1
17
k=1
B2
We bound the spectral norm of Bj and B2, respectively.
K-
B = (oos E"r + +V
Σ
I - 1l 18 1"))
K-1
$ <Q+ ((++)1VA0x(211)
"
K=
K-1 $ <(Q+QL9K)
1 m
$ 11+1m
(eemm C.2
In addition,
K-1 Σ -17 -n((ii VOx e' =V [ - (A (x)) k-1
|B
ViAe 17
1=11
I- V (2. ( k-1
K-1
V2 0026"11 -17 Vi
VOoxe" E" + oAVo
Σ
Σ
k(1 + 1 19
SQn <0+ QL*x)
[<(++
(1 + u (1 + m72))) -1) 1)
17
S *
222
Denote Va0x to be L VA0x -Lipschitz continuous for all À E A, then we have
L VaOK
sup AEA
V VAVAO
< + B2l $ K(1 + m7. 2
27

---

With the above result and Lemma C.3 we have that for all A, X E A,
[AC(A:2) - <
<
(A, (xxx(()))))
Vx (x));
V Vx0x (A.K - VA
V (A, 0 (A):2) VA (X' 0x):
A); VA (X' (X' 0xx(xxx'';)))
+
Vx0K (A. (A.0x(A):2) o
S 4Q - X1I "
- 0x(2
+ 7x0x ( XII Q/ - -xxx)))))
+
[x0x(A
- -01 - X'I
L (Q1A) X'I QL J| -X'I)
+20 A XII
K(1+ m 2 2K || X/I..
which implies that 7 S (11+m=mm+))
Proposition C.5 (Expansion properties of IFT-based algorithms). Suppose we solve Example 5.3 by IFT-based Algorithm with constant inner step size 1) where 1 - 7i'd 2 O and outer step size Og, Then (1) the outer update rules Gz.or and G2, are 20, divergent along Un, and (2) the composite validation loss ((;2) is -exxanssivve along vn for all z E S where
L'
7 2 (1++1 m1
Proof. According to Lemma C.3 in the case of Example 5.3 the hypergradient calculated with the IFT-based algorithm the same as the UD-based algorithm, which implies they achieve the same parameter divergence in this example. Therefore, we have the same result for L' and 7 as in Proposition 5.4 that L' = (1 + ") and 7 2 (1 + *7*)22 which complete the proof.
C.1 Stability bounds of IFT-based HO algorithm
Combining the lower bound in Theorem
5.1 with the upper bound in Equation (6), we instantly have
T II (1+a,(1-1/m)/
20, L' Carg S
T
20r L
Σ II (1-1mm)))
(13)
m
m
Theorem C.6 (Uniform argument stability of [FT-based algorithm, proof in Appendix
C
Sooving
Example 5.3 by IFT-based Algorithm [ with constant inner step size 1, where 1 2 and
decreasing outer step sizes Oa c/t with a positive constant I 1n(1+0 2orr
S Carg
7 + eer where 7 S K(1 + 22)2 r 2 (1+ 11+m77 2522 as in Proposition C.5
m
The upper bound is not limited to Example 5.3 but holds in general case with the same mild assumption [77] (see Assumption B. Notably, in contrast to the outcomes observed with the UD-based algorithm, the upper bound incorporates extra factor of K, leading to a larger upper bound for the IFT-based algorithm and a misalignment between the lower and upper bounds.
We can further establish similar guarantee for the uniform stability estab detailed in Theorem C.7
28

---

Proof. Based on properties in Propositions C.4 and C.5 the same proof as Theorem 5.3 we get the result.
Theorem C.7 (Uniform stability of IFT-based algorithm). Following the same condition as in Theorem C.6 and additionally, if the initial points Oo 0, An O, and vi 1 x; for any
j E [m]] and U1 1 x². for any j E [n), then the order of uniform stability sab w.r.. T satisfies
7 11(1-11- )er))
T Jey
X Estab S
where y and 7f are the same as Proposition C.5
m
Proof. With the same proof Theorem 5.6, can get the result.
D Deferred results of UD-based algorithm on (strongly) convex inner loss
Recalling that in Example 5.3 er [A 0 2) = 1/0 1 0, where the smallest eigenvalue of A is Y11 Therefore, when V/ 2 0 (n1 > 0), (aT 0; z) is convex (strongly convex) w.r.t. for all 2. Utilizing the case for n 2 0 (n > 0) in Proposition B.5 and the same proof in Theorem and Theorem we can get the stability results for the convex (strongly convex) case in this section.
Theorem D.1 (Uniform argument stability of UD-based algorithms for (strongly) convex (*)), Solving Example 5.3 by UD-based Algorithm / with constant inner step size ii where 77d 2 and decreasing outer step sizes ay c/t with positive constant has uniform argument stability that
Tinl (1(1++1--00 11---)) )eyy)
T Jey
Earg
m
m
where 7 = - x K when 71 = 0 and 7 - x when "1 > as in Proposition B.5
Proof. Please refer to the proof of Proposition B.5 and Theorem where we generalize the results in the main paper for the (strongly) convex case.
Theorem D.2 (Uniform stability of UD-based algorithms for (strongly) convex (t), Following the
same condition as in Theorem D. and additionally, if the initial points On 0, O, and
01 1 o. for any E [m]) Vi and 0n 1 a.. for any j E [n], then Algorithm has uniform stability
that
pla(1+(1-h)0)
7(1 1 Jey
S Cstab
where 7 = 7/ K when ?11 0 and 7 -/ when 7 in Proposition B.5
Proof. Please refer to the proof of Theorem 5.6
E Deferred results of single-level SGD
As discussed in Section deriving a stability lower bound entails constructing an example with maximum instability, and need study two aspects of the constructed example: (1) properties of the (compound) loss, and (2) stability behavior of the outer SGD corresponding to these properties. For (2), the outer level of gradient paadeent-based bilevel HO algorithms and the single-level SGD have equivalent formulation observing corresponding relations between À ++ w. L + E, Svall +t S and stability definitions Definition 3.1 <>> Eq. (5)). a result, given the smoothness constants 7 for L and the
(1-1/mine stability upper bounds under the bounded loss condition for the bilevel (Estab S π 1/
in I7 and single-level (Cstab < TT /m in [19] algorithms have similar results. Given those properties, their stability lower bounds be analyzed in general framework: construct well- designed example, examine its key properties, and derive the stability lower bound in response to these properties.
Our proposed hower-bounded expansion properties in Section 4 and provable stability lower bound given these properties in Theorem 5.1 are generally applicable for both bilevel and single-level
29

---

analysis. Building upon these tools, we also establish stability lower bounds for single-level SGD in addition to our main results regarding bilevel algorithms. Notably, while the technique of stability analysis for the outer level of bilevel problems can be adapted to single-level ones, the stability behavior of bilevel and single-level problems are not directly comparable.
In this Section, we introduce basic concepts corresponding to stability analysis of single-level SGD in Appendix [E.1 introduced by [9]. Based on this, Appendix E.2 leverages the lower-bounded expansion properties established in Section to provide a stability lower bound for single-level SGD, which is tighter than the existing result in 34 Theorem 4]. An upper bound is established in Appendix E.3 for fair comparison between the lower and upper bounds without the bounded loss condition. Detailed comparison with existing works is provided in Table 2
Algorithm 2 Single-level SGD
1: Input: Initialization wo: dataset S: step size scheme a
2: Output: The parameter WT
3: for t 1 to '"" do
4: uniformly sampling from [m]]
5: g + V 2s,)
6: we f W arg
7: end for
8: return Wr
E.1 Problem formulation for the stability analysis of single-level SGD
Suppose we are interested in the distribution D on data space Z, from which we obtain sample
S= )m Li.d. D Suppose w is the parameter to optimize in space Ω2 and its loss on example Following [19] the generalization error
= is ((w; z). The single-level SGD is shown in Algorithm 2 of single-level SGD is defined
m > - (A(S);
1
m
Egen
EAS E EZ~D(((A(S):
(14)
and we say a single-level stochastic algorithm is uarguriffoyyy argument stable if,
farg sup
RAlllA(S)) - A(S) S~5E2m
(15)
Based on these definitions, 19 has shown that stability guarantees generalization in single-level problems: if stochastic algorithm A is carg unifformly argument stable and the loss function E(w:; 2) L-Lipschitz on for all & E 2, then we have
6gen S Extah S Learg.
(16)
E.2 Proof of uniform stability lower bound
We first present a single-level example following 34
Example E. Suppose Ω = (w || < W) where W > 0, and 2 = X x y where X = {æ
||ж||| S 1} and y = [_,, Assume the loss function is f(w; = 1/w" Aw ye where A E Rdxd is a symmetric matrix. Denote the eigenvalues of A as 71 .... Ya. where 71 < 0 and hz1l 2 hal. and v, as a unit eigenvector A for 7i. Additionally, suppose the twin datasets S and are different at the i-th entry, where 2, = (æ,, v)) = (v1, 1), 2, (ā,, ū.) = (-v1.1).
Proposition E.2 (Lipschitz continuty and smoothness coefficients). In Example E.I the loss function f(w; 2) L-Lipschitz continuous and 7-smooth on for all z E 2, where S hn W + and mi
Proof. As l twice differentiable on Ω Z, we have
sup sup [[w; 2) = sup sup || Aw - yæl S mn/W + 1,
zEZ wen
=e2 weB
sup sup / [(w;))]
= sup sup A|| = l71l-
2c2 wes?
=e2 wes?
30

---

Proposition E.3 (Divergent and expansive coefficients). Suppose we solve Example E. by single- level SGD, then the gradient update rules Gz,a, and Gz.a: are 20, divergent along in and f(w; 2) is of -expansivv along v on Qt for all E S, where I' and 7 = lml-
Proof. For all w E E
Gziar( (w)) Gz (w) -a (VE(u;;; Ve(w;; 2,)) = a0 - ū, = 20,01 - 11
Recalling Definition 4.1 this implies Gz,ay and Gz.,o are 2xx -divergent where I' 1. Addi- tionally, for all w, w E S such that w w' collinear with 1 and any E Z, we have
Vi(w'; A(w w') 71 (w w') w w'). v)(w;
Recalling Definition
4.3
this implies f(w: 2) is Y expansive on 12 for z E 2 where y = l//-
Given Proposition
E.3
directly leverage Theorem 5.1 obtain stability lower bound.
Theorem E.4 (Lower bound of single-level SGD in recursion form). In th case of Example E. running SGD for T steps on a 7ysmoooth loss function has uniform argument stability with
20c
Σ
II 1/m)7) sm1+1
Carg
m
Proof. Using Theorem 5.1 and Proposition E.3 we gets the result.
Following the proof of Theorem 5.5 order under decreasing step sizes.
deform the result in Theorem E.4 to display explicit
Theorem E.S (Lower bound of single-level SGD in deformed form). In th case of Example E.1 running SGD for T steps on 7-smooth loss function with step sizes at c/t t has uniform argument stability with
(11+(11/mm)a
2c
T+
earg
mln (1 1/m)cy)
Tla(2 1/mderr)
Omilting constant factors that depends on e and y, we have earg
Proof. The proof follows the scaling for the lower bound in Theorem 5.5
Remark. Compared with Theorem 4 in 34 our result relaxes the condition and improves its order To see this, first show that the step-size settings equivalent. In particular, 0g 0.99%t (Lemma 3, (34] is equivalent az (Theorem E.5 ours) with c 0.997 Based on this
T..99ey
equivalence, we can rewrite the lower bound
as Carg 2 mi10000 with assumptions c
< < bound of Garg 2 T
0.1 and > m (detailed in the proof of Theorem 4, [34)). contrast, our lower
0.99
in Theorem E.5 holds for any > 0, > 2 1, relaxing the conditions. Regarding the tightness of the lower bound, our result is sharper concerning m given
m
7o. 09ey
lim T.n 177J00
O for fixed T. In addition, concerning T. our result is comparable
observing that the ratio of the powers on differ slightly, namely 0.96 < (1(1m()))m))cp) S 1.06
0.99cy
for all m 2 100, under the scope of application of their result (i.e., c and 7 < 0.99 ). The
superiority of our lower bound stems from a loose result in Lemma 3 in 34 Denote A, == w. w
states that [[[[|r Ato # 0] Z 2n
1 0.9900, while this can be improved into EA Ar A #
0) > 1 (1))
T+1 0.9907 Ato. which will lead to sharper lower bound.
31

---

E.3
Proof of uniform stability upper bound
Denote de | -wyll The proof leverages an intermediate result of Theorem 3.12 19
Lemma E.6 (19]. Theorem 3.12). Assume [(;22) is L-Lipschitz and y-smooth for all 2.
Running SGD with step sizes at all S ~ S E 2", we have the recurrence relation: A1 S T,
EA(ō.] - (1-
- m (1 a and) [ 1 (EAl0r-1) 20,L).
m
Unwinding the recursion we have the stability upper bound. Theorem E.7 (Upper bound of single-level SGD in recursion form). Assume E(; z) is L-Lipschitz and y-smooth for all 2. In th case of Example E.7 running SGD with step sizes Or has uniform argument stability with
T
T+1
(1+ 1/m)as>) 20, (0 + +1)
Σ
II 8-1
Garg
m
Proof. As defined, earg S:uS 2
E (T) and. Unwinding the recursion in Lemma E.6 and
End
using the fact that L >W + in Proposition E.2 get the result.
Here we set an additional 0r+1 O for the expression neatness, Recalling Theorem E.4 the upper and lower bound are in exactly the same formulation with only difference in by a constant (i.e.. >W + 1), which means the lower and upper bound tightly match w.r.t. the key factors T and m.
Considering the case of constant step size, get earg X (1=(1-1/m)a>) showing an exploding rate w.r.t. T. When adopting linearly decreasing step sizes S m c/tt, the upper bound can also be deformed to reveal an explicit order w.r.t. key factors.
Theorem E.8 (Upper bound of single-level SGD in defromed form). Assume E(; 2) is T-Liipschit and 7-smooth for all z E 2. Running SGD for T steps with step sizes 04 S c/t has uniform argument stability of
2(TW +1) (m (m-17) 1yy (1+ ((10)))m((-//)))/) -1
Earg
Omitting constant factors that depends on c, 7y and W, we have earg S ( 1/m]er
m
Proof. The proof follows the scaling for the upper bound in Theorem 5.5
Combining Theorem E.8 and Theorem E.5 have 7ln(1+(01/m30)) Earg T1-1//mee m
Notably,
mi the discrepancy between the lower and upper bounds is unavoidable, stemming from the scaling steps required to obtain explicit order, and this gap becomes small when have large and small ey- Concerning the lower and upper bounds in recursion form in Theorem E.5 and Theorem F.7 our results are tightly matched.
T---1 which is tighter Remark. Notice that Theorem 3.8 in 19 presents upper bound of Carg
m
than our result of Earg S T 1/m)se but with additional bounded loss assumption that E(w; z) E [o, 1]. Both results are based on the recurrence relation in Lemma E.6] They derive the upper bound with a hitting time to and bound the loss divergence after to with the bounding loss constant (i.e., 1) and thus get a tighter upper bound. However, to derive lower bounds, we need to explicitly calculate the divergence between parameters and corresponding loss values, which will inevitably reveal all the terms in the recursion. In this case, the bounded loss assumption is not applicable and thus we present an upper bound without this condition
fair and clear comparison with the lower bound.
We acknowledge that the bounded loss assumption commonly adopted for boper- analysis in theoretical works. Despite [19], several following works also adopt this technique. (34) derive the
7T upper bound of earg S w in the nonconvex case with similar approach by bounding the loss after hitting time lo2 with an additional setting for Ig = n. However, there appears to misuse of
Lemma 4 in their proof of Theorem 5, which leads to their result being tighter compared to [19 in
32

---

< m. Specifically. in the proof of Theorem 5, they decompose Eall Ar] into two terms that A ATl S EAllAAT] A. OJF 0] + E EAllAT]||,, + [] * 0] to bound these two terms separately. For the second term, the union bound is used to get IR (T A * OP + 0] Σ 1
the case of T 10TI
n - [elll Arlll = f), where = 1 denotes that is the first time SGD pick the different entry in the twin datasets. EA A HT = t] is further bounded using Lemma 4 that EallAr | = 0] I (2)) to get Bz H = -] ( While this appears to be misuse as H = can only imply - = 0 and whether A, = 0 remains uncertain, where Lemma is not applicable. Another work 49 use a large constant to bound the loss divergence from the start of the evolution of the parameter divergence, which leads to an upper bound of earg S even with constant step sizes. A detailed comparison of existing results is listed in Table 2
Table 2: A detailed comparison of existing results on uniform stability of single-level SGD. We unify the notations that the loss function smsoohhh the dataset is of size m and SGD picks the different entry for the first time at to.
Step size
Constant de = a
Decreasing a, S c/t
Settings
Range of iterations with bounding loss
I
to ST
Upper bound
49
re+1 m
19
T(-1//m/r (Ours)
12
Results
plufll 1/m)en)
(Ours)
Lower bound
m 390y
F Details of simulations
The implementing code is provided in the supplementary material. All simulations can be conducted on the CPU of laptop.
F1 Hyperparameter distance and stability bounds
To examine the tightness and validity of the upper and lower bounds presented in Theorem 5.5 we implement UD-based Algorithm on Example 5.3 with linearly decreasing step sizes and compare the practical output hyperparameter distances with our theoretical bounds under a range of outer iterations T.
Specifically,
the loss functions and the twin validation sets as in Example 5.3 with A
-1 07
0 1 and []]
The optimization is implemented with fixed 7t = 1. K 100, m = 100,
0
n 100, 17 0.01, and 0.01.
The comparison is shown in Fig. 2 We plot the output hyperparameter distances with increasing T from 1000 5000 on the horizontal axis and the deformed lower bounds and upper bounds with corresponding T on the vertical axis. The dashed lines are linear fittings of the hyperparameter distances and the upper/lower bounds, examine the linear trends of their relative magnitude.
F.2 Recursive stability bounds and deformed stability bounds
Here we implement additional simulations to examine the tightness between the recursive upper/lower bounds and deformed upper/lower bounds presented in Eq. and Appendix B.6] Specifically, the recursive upper bound is calculated by Σ (== I -
a. 1/m)>) 20, / /m and the recursive lower bound is calculated by ΣT II. 15 (1 + a. 11 2a: in Eq. (7). The deformed upper bound is calculated by T 107 // and the deformed lower bound is calculated by Tin( pin(1+(1- [+(1- =)er") //m. As for the coefficients: set 7 1 in Example 5.3 L' is calculated with they are of the same
(
[11 # - 11/""" 5r in Eq. (10) and L is calculated with L
33

---

order of magnitude, 7 = calculated with 17 Ex=o (1 m7 tr 2 mytt Ek=ol (1 m)
as in Eq. (1
During the optimization, fix 0.01, 100 and 0.01. For the simulation regarding T, we set K = 100 and m 100 and plot the results of the recursive upper bounds for I' from 1000 to 5000 in the horizontal axis with the corresponding other three bounds the vertical axis, shown in Fig For the simulation regarding K, we set T = 1000 and m = 100 and plot the results of the recursive upper bounds for K from 25 200 in the horizontal axis with the corresponding other three bounds in the vertical axis, shown in 5 For the simulation regarding m. we set T 1000 and K 100 and plot the results the recursive upper bounds for from 100 2000 in the horizontal axis with the corresponding other three bounds in the vertical axis, shown in F
All curves exhibit linear trends, indicating these bounds are in the same order w.r.t. T, K, and
0.0250
Scaled upper bound
0.14
Scalal uppe hous!
Resursive lower bourd
lower heard
bound
Other boundss
Other bounds
0.10
010015
0.04
000200
0.0025
000
0.008
0,0040
0,0042
0.0044
0.0046
0.0045
0.00
0.02
0104
010
0.88
0.10
Recursive upper bound
Recursive upper bound
Figure The relations of bounds for T from 1000 to 5000.
Figure The relations of bounds for from
25 to 200.
Scalal uppar bound
Rounive imver hound
9.0055
0.0000
Other hounds
8.0055
0.0000
80015
80010
0.005
0.0000
00000
0,005
0,0010 0.0015 910200 baics uous daM35
Recursive upper bound
Figure 6: The relations of bounds for K from 100 to 2000.
G Additional discussions
G.1
Additional discussion for the definition of uniform stability on validation
In HO, the model is typically evaluated during the validation phase and is expected generalize well on unseen test data based on its validation performance. Therefore, we focus on the impact of perturbations the validation set our current definition of generalization error and uniform argument stability. However, in the context of meta-learning where both datasets play crucial roles (50), considering the perturbations in the training set may provide additional insights for generalization analysis, which might be interesting topic for future work.
34

---

G.2
Additional discussion for expansiveness and existing concepts
We first clarify that the convex loss function corresponds to Definition 4.3 for the case when μ S When the loss function is convex, we have (V((w) Vε(w"), w w") 2 0. According to
Definition 4.3 3 if the loss is additionally p-expansive, there exist Hw,w 2 μ such that
(Vi(w) - v((w"), w') {-Ho0 no (w wi), w')
-/www ||w w0ll 2 0,
thus have j S Mw,, w O.
When j > 0, j-sttongly concavity requires (V((w)- Ve(w'), -w') S -pll - w'll R for all w, w' Ω2 and Definition restricts that for all w, w' E Q that w parallel with v, there exists uwe 2 μ such that
(Vi(w) - Vi(w'), w w') (-w w (w w'), w w')
-w I| w w'll
S -111w w'll.
Therefore, w-expansivenesss along implies concavity only for w' parallel with v.
On the other hand, if we have (V((w) - V((w'), w - w') S -ulle w'l" for w - w' parallel with u, then
- w - w') S |V((w) - V((w"')llle w''l < - - w'113
and thus V - v((w")ll -ullw - w'll Therefore, compared with strongly concavity on a single direction, p ju-expansiveness has additional restriction for the colinearity of Vl(w) Vi(w") and (w - w').
Additionally, for the one-dimensional case, the condition w - w' parallel with some scalar is equiv- alent to Yw, w' E Q. Therefore, j--expansiveness along implies p-strongly concavity. Conversely, j--ttrongyy concavity implies that there exists a Man,an' 2 fu such that
(Vl(w) V((w")) )) w') -ww,ww (w-- w')² <-((w wn)
thus ju-strongly concavity conversely also implies ju-expansiveness along v. Therefore, these concepts equivalent the one-dimensional case.
G.3 Technical challenges of stability lower bound analysis for bilevel algorithms
The nested optimization in bilevel algorithms poses challenges to the stability analysis as the insta- bility and simplicity of the constructed example are both crucial for deriving a tight lower bound. Specifically, to examine the alignment of the lower and upper bounds, we need to precisely caleu- late the smooth coefficient ? and expansive coefficient of the compound validation loss for the constructed example. While the implicit and intricate formulation of V(()) bilevel optimization makes y and y difficult obtain. In the following, take ridge regression as example to illustrate how the bilevel structure hinders the stability analysis.
Example G.1 (Regularization coefficient in ridge regression). The validation loss and training loss are given by (2. 0) (u 0 x²)2 get (A, = (v - 0 x² + 2 0. Solving it with UD-based Algorithm we have the inner output as 0 (x(A) = - (I - A qe Din T)0, ΣX II n " "Tm,,, Tje and a far more complex inner Jacobian (A)x(A), resulting in unmeasurable hypergradient VL(A)= V v²0x(A((s) 0 (+)))=))
These complexities obstacle to precisely examine the divergence dynamics at each step. There- fore, we introduce expansion properties in Section 4 and the general lower bounded guarantees in Theorems 5.1 and 5.2 to jointly contribute to the careful construction of Example 5.3 As result, Example 5.3 exhibits the maximum instability while having a relatively simple outer gradient update feasible for lower bound analysis, which will lead to tight stability lower bounds presented in Section 5.4
35

---

H Potential extension of our framework
H.1 Extension on average stability lower bounds
Considering the similarities between average stability 32 Definition 2] and uniform stability, techniques may be adapted to the data-dependent setting for average stability with some modifications. In this section, present preliminary proof sketch for establishing the stability lower bound of single-level SGD based on the variant Example E.1
To account for the randomness in the sampled datasets, we first define some notations. Let S; denote a copy of S with the i-th element replaced by z'. Gs, s., and w denote the SGD update rules and the updated parameters optimized on S and S; at the step t. With a slight adjustment Section [4.2 and similar proof as in the current paper, Theorem (5.T can modified as: Suppose there exists nonzero vector (S, S;) along which Gs.t and Gs.,t are 20, (,,,, S,) diiverget and [(:;2) 2) is 7/(S, -xxpansvv for all WS, ws.t that parallel with vSS St). Then we have
(5 S.)] 2 [1 + (1 - h/ S,) ( + 2 L (S,S:) Si)/m. This recursion closely corresponds with the recursive upper bound in Eq.(19)):
Ex(o,(5, S,)] - [1 a,
La, 8.)/m,
and the matching of % & tht L' & L will further guide the design of the constructed example.
Therefore, our analysis framework can be adapted for the average stability with suitable modifications. challenge is calculating the expectation over S and S; for the above recursive formula, which is beyond the scope of our paper. In the following, we provide a proof sketch for establishing the average argument stability lower bound clarify possible approach to extend our framework.
Specifically for average stability,
Assume that the data follows distribution D that p(z) = 0.5 if = = =01, 1);
S i..dd
D
0.5
if = (-01,
and z/ D are independent of each other. The validation loss and training loss follow Example E.1 Under these assumptions, we derive that L'(S, S,) = I| - v/==111/2 / and (S, = 0 for 2 2, (s(S, S.) |i| for 24 # z/z This leads the average argument stability lower bound:
T II - (=1==
Carg Σ
H.2 Extension on generalization lower bounds
In this section, we discuss possible approach to extend our framework on the analysis of gener- alization lower bounds. We first present a lemma clarifying the fundamental equivalence between generalization and stability. Then lower bound on the expected hyperparameter divergence is established by slightly modifying 5.33 with additional design on the data distribution, which will imply the generalization lower bound under certain conditions.
Lemma H.1. Let Svall = (z val) and Swall = (zyal' ,..., vall be two independent samples (z)al, ...., 2. vall ..... vaa)) denote the twin validation set of Sval differing the i-th example. Consider Egen the generalization error defined in Eq. (4). Then, we have
drawn i.i.d. from Dval_ Let Syall
Egen
1
E A.S" sval zual
( (C(A(SVa) """ ) L(A(Š)a) :T'):=(aa1)
Proof. According the definition of generalization error in Eq. and the linearity of expectation,
Egen EA,sml EENDeme ((A((S))))))) ,
E
A. Str [[(A(SV)) (((())ma)S*))) 22aa))
(b)
36

---

As it is assumed D Deett and gvall isid. sampled from Dvall independent from S term (a)
can be rewritten as
1
[C(A(SVa) S44): 2, yall
(a) = EA
E sm
m
Under the expectation, Syall and Syaal is exchangeable, then term (b) can be rewritten as
1
S,8ral St [(A(S)a)) St)); vaaa
[C(A(STal ,54); 2; 2xal²
(b)
s g " stal
m
771
Combining (a) and (b) leads to the equation the theorem.
Lemma H.l shows fundamental relation between generalization and stability: The generalization eπror equals the expected loss divergence when replacing a single example in the validation set. Stability- generalization analysis typically takes the supremum on S SSall, 2 distribution-agnosiic upper bound of generalization error as
to obtain
sup EA(C(A(STaL 2 L(A(S) 2;a"")]
Cgen Cstab
where Stab is commonly upper bounded assuming L-Lipshcitz of the loss
Catab S Learg L
sup Ste Sval
EAllA(S Stt)
This paper attempts to derive lower bounds of Carg which will not directly imply the generalization lower bounds because Carg is fundamentally a distribution agnostic upper bound for the generalization error. In order obtain generalization lower bound, promising way is to extend Example 5.3 with additional assumption on the validation distribution rather than directly specifying S and Sival
We present a primary result below for the lower bound the expected hyperparameter divergence, which indicates a way to extend our methods on the analysis of generalization lower bounds.
Example H.2. We introduce an HO problem as follows. Let the validation loss and the training loss be:
gral (A, 0: (A
T A0 ATO yæ 0
where A Raxd is symmetric. Denote the eigenvalues of A as 71 < < ra. Let 0, Ja S and vn be unit eigenvector for 71. Suppose the validation distribution follows:
0.5
if = (f1, 1), if (-v,,)..
p(z) =
0.5
Theorem H.3. Suppose we solve Example H.2 UD-based Algorithm constant inner step size 7) where - 177 0 and outer step size dgg Denote that the expected hyperparameter divergence
as Egen,arg :- Σm 1 E AA ggaal
",.tt, 2pair [|A(Svv) S A(5yal M St² []]. Then, we have
Σ II (1+as a1 -1- 1/m)>) T. m
Eggn,arg
1=1 1=
where
Lx 1' 1r = (1 17 2K
37

---

Proof. We first decompose Egen,arg conditioned on the difference of z! and 2taal as
agen
P 2
= Sm || ||| , -A( || 2; 2aa1
vaal 2;
m
i Pl
val
"E s.su SSmll التججية |||A(( Sth) - - ,ttt بببجع + 2
|E
p val + 2,
val
JE A syall البيي |||A(55vl, , - A(5 |-1) + 2لسحب
i=1
m
R. A. ا 1 ||A(S Str) (trr) - A((Saa) Sth ||1 # =
2m
The last equation holds for that z! and zyaal are sampled from D specified in Example H.2 independently, which leads to P(z)al A 2qaal] 1/2.
According to Proposition 5.4 and Theorem 5.1 for any Sth, i E [m]. and S STal where z/all f zxal' ((-v1, 1), (vi, 1)), we have
20,L' m
|A(S SSt)) A(S Evall S
Σ II (1 (1+aa(1-1/all 1/m)7)
1=1
Therefore, holds that
T EE (1+
m
2a,L'
aLL'
-
Σ II (1+ 1/m)) m
Ggen,arg 2
2m 1111
m
==
This result sheds light on the analysis of the generalization lower bound by establishing the lower bound the expected hyperparameter divergence since it will induce generalization lower bound if there exists positive real constant & such that |ggen| 2 Legen.arg. One possible situation is that the designed compound validation loss satisfies for all z E 2, [C(x; - [(X; 2 L|> X As
the generalization lower bound is beyond the main scope of this paper, further design and derivation may be left for future research.
38

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: Our claims accurately match theoretical results and reflect the paper's contribution and scope.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
is fine to include aspirational goals as motivation as long as is clear that these goals not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations the work performed by the authors?
Answer: [Yes]
Justification: See Section 6
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create a separate "Limitations" section their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is low images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't 't acknowledged judgment and recognize that individual actions in favor of transparency play impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
the paper. The authors should use their best
3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
39

---

Justification: All theoretical results include complete proofs with clearly stated assumptions in the Appendix.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental Result Reproducibility
Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that it affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Question:
Answer: [Yes]
Justification: provide simulation code supplemental material. is sufficient for reproducing our experimental results.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, or if the contribution a specific model and empirical evaluation, it may be necessary either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g., in the case of large language model), releasing of a model checkpoint, or other means that appropriate to the research performed.
While NeurlPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) the contribution is primarily a new algorithm, the paper should make clear how reproduce that algorithm. (b) If the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) the contribution is a new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome deseribe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
40

---

The authors should provide scripts to reproduce all experimental results for the new reproducible, they Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, as described in supplemental material?
Question:
Answer: [Yes]
Justification: provide simulation code the supplemental material. is sufficient for reproducing our experimental results.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips.. cc/
public/guides/ Soaeleese/CooeSSmmmmiiiinoffee
for more details.
While we encourage the release of code and data, we understand that this might be possible, so "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https
/ https/cccppbllcgggudeeeeeeeeeeee Coaee//dddeSebmmmcia ssi onPolicy) for more details.
The authors should provide instructions data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
proposed method and baselines. only subset of experiments should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code is permitted.
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification: We provide simulation code with training details in the supplemental material.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to a level of detail that is necessary appreciate the results and make sense of them.
The full details can provided either with the code, in appendix, or as supplemental material.
7. Experiment Statistical Significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [No]
Justification: The simulation experiments in our paper validate the thcoretical results with the trend of the curves, where randomness does not affect the validity.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, or statistical significance tests, least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall with given experimental conditions).
41

---

The method for calculating the error bars should be explained (closed form formula, call a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
It should be clear whether the error bar is the standard deviation the standard error of the mean.
It is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful figures symmetric error bars that would yield results that are out of range (e.g. negative rates).
show in tables or
error bars are reported in tables or plots, The authors should explain the text how they were calculated and reference the corresponding figures tables in the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information on the puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [Yes]
Justification: See Appendix
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary failed experiments that didn't I make it into the paper).
9. Code Of Ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics http:////eeerrre...cci//////biae
Answer: [Yes]
Justification:
The research conducted in our paper conforms with the NeurIPS Code of Ethics.
Guidelines:
The answer NA means that the authors have reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., there a special consid- eration due to laws or regulations in their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive socictal impacts and negative societal impacts of the work performed?
Answer: [Yes]
Justification:
See Section G
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact why the paper does not address societal impact.
42

---

Examples of negative societal impacts include potential malicious unintended uses (e.g., disinformation, generating fake profiles, surveillance), faireess considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms monitor how system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper deseribe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification:
This paper does not release data or model.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [NA]
Justification: This paper does not use existing assets.
Guidelines:
The answer NA means that the paper does use existing assets. The authors should cite the original paper that produced the code package dataset.
The authors should state which version of the asset used and, possible, include URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (e.g., website). the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms use in package should be provided. For popular datasets, paperswithcone com/ datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
43

---

For existing datasets that are re-packaged, both the original license and the license of the derived asset (if has changed) should be provided.
If this information is not available online, the authors are encouraged to reach out to the asset's s creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification: This paper does not release new assets.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details the dataset/code/moodl as part their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsoureing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification: This paper does not involve crowdsourcing or research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included the main paper.
According the NeurIPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/review based the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: This paper does not involve crowdsourcing or research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Depending the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
44


Reviews:
[{"review_id": "JnC8aagzxy", "reviewer": "Reviewer_NBuR", "summary": "This paper studies the generalization bound of the hyper-parameter optimization problem. It provides a uniform lower-bound for the validation argument stability, which proves that the upper-bound of the validation argument stability in existing works is tight.", "questions": "My question is described in the weakness section. It is my major question, and I will consider raising the score if it is well answered.", "limitations": "No potential social impact.", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "The paper is well-written and easy to follow.\n\nThis paper studies the hyper-parameter optimization problem, which is of great importance to bilevel optimization community.\n\nThe paper' theoretical result on the lower-bound of validation argument stability is sound and novel. It provides good insight into the stability of the hyper-parameter optimization problem.", "weaknesses": "How does the current generalization bound depend on the number of data $n$ in training dataset? According to the current bound, it is beneficial to just divide more data into the validation set to increase $m$. It seems there is nothing that quantifies the negative impact of having a smaller training dataset. This could lead to unreasonable interpretation of the bound: suppose there is a dataset of size $N$ where we assign $m$ data into validation and $n=N-m$ into training dataset. According to the current bound, the generalization bound decreases in an order of $\\mathcal{O}(1/m)$, which suggests one should just use a largest $m$ possible, which is counter intuitive.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "# Response to Reviewer NBuR\n## W&Q: Interpretation of the current generalization bound w.r.t. validation and training sample sizes.\n\nWe thank Reviewer NBuR for the insightful question.\n\nIntuitively, the expected population risk can be divided into the generalization error and the empirical validation risk as $$E_ {S^{val},S^{tr}}[R(A(S^{val},S^{tr}))]=\\underbrace{E_ {S^{val},S^{tr}}[R(A(S^{val},S^{tr}))-\\hat{R}_ {S^{val}}(A(S^{val},S^{tr}))]}_ {\\text{(I): generalization error (Eq.(4) in our paper)}}+\\underbrace{E_ {S^{val},S^{tr}}[\\hat{R}_ {S^{val}}(A(S^{val},S^{tr}))]}_ {\\text{(II): empirical validation risk}}.$$  The first term is explicitly bounded w.r.t. the validation sample size $m$ in our paper ($\\epsilon_{gen}\\leq \\epsilon_{stab}=\\Theta(1/m)$, see Line 140 and Theorem 5.7.). The second term is implicitly bounded w.r.t. the training sample size $n$ since a larger training set generally leads to better validation performance. Therefore, **the assignment of validation and training sets is a trade-off between $\\text{(I)}$ and $\\text{(II)}$, which aligns with common discussions on generalization in validation, as seen in [Page 70, 4]  for cross-validation.**\n\nSpecifically, consider assigning $m=aN$ examples to $S^{val}$ and $n=(1-a)N$ examples to $S^{tr}$ where $a\\in(0,1)$. **On the one hand**, the generalization bound $\\epsilon_{gen}\\leq \\epsilon_{stab}=\\Theta(1/aN)$ (see Line 140 and Theorem 5.7) presented in our paper implies that $a$ needs to be sufficiently large for the term $\\text{(I)}$ to be small. **On the other hand**, as a larger training set generally leads to better validation performance, $a$ also needs to be sufficiently small to get a low validation risk in the term $\\text{(II)}$. Therefore, **the choice of $a$ represents a trade-off to achieve a favorable population risk**. \n\nTechnically, the absence of $n$ in the generalization bound arises from the formulation and decomposition of the generalization error. As defined, $\\epsilon_{gen}$ can be written as $E_{S^{tr}}[E_{S^{val}}[R(A(S^{val},S^{tr}))-\\hat{R}_{S^{val}}(A(S^{val},S^{tr}))]]$. Given a fixed $S^{tr}$ and the independence of $S^{val}$ and $S^{tr}$, the inner term becomes a difference between the expected and empirical validation risk, which is typically bounded with convergence analysis (e.g, stability, uniform convergence, e.t.c.). The outer expectation on $S^{tr}$ is often scaled as a supremum over $S^{tr}$. These technical analyses lead to a generalization bound solely on $m$.\n\nWe will add the above discussion in the revised version, and we believe this will improve our paper's clarity.", "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": "", "extra_scores": {}}, {"review_id": "IG9WPYFUzZ", "reviewer": "Reviewer_bA9a", "summary": "The authors consider gradient-based algorithms for hyperparameter selection. They derive lower stability bounds for UD and IFT-based algorithms that solve this problem. To get this lower bound, the authors introduce the notion of lower-bounded exansion property of the update rule of the hyperparameters.", "questions": "- **Q1**: Can the lower bound be extended to algorithms that use warm-starting strategy?", "limitations": "N/A", "rating": 8, "confidence": 2, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "- **S1**: This paper is very well written and easy to follow.\n\n- **S2**: The paper establishes lower bound on the stability of gradient-based methods for bilevel optimization. By doing so, they demonstrate the tighness of existing stability bounds for UD-based algorithms.\n\n- **S3**: To my knowledge, the use of the lower-bounded expansion property to prove lower stability bounds is novel.", "weaknesses": "- **W1**: The most efficient gradient-based algorithms use warm-starting strategy, meaning that the inner and the inverse Hessian vector product solvers are not reinitialized at each iteration [1]. It is not clear if these algorithms are covered by the analysis.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "# Response to Reviewer bA9a\n## W&Q: Extension of the lower bound analysis to algorithms with warm-starting strategy.\n\nWe thank Reviewer bA9a for the positive comments and thoughtful questions. \n\nWe are uncertain about the precise meaning of the \"warm-starting strategy\" you mentioned, as we do not find related definitions in the reference [1] *Gradient-based optimization of hyperparameters*. Please correct us if there is any misunderstanding in our response.\n\nIn our understanding, the \"warm-starting strategy\" may have two meanings. First, the inner parameter $\\theta$ is not reinitialized at each outer step. Second, the inverse Hessian vector product solver used to calculate the hypergradient is not reinitialized at each outer step.\n\nFor the inner warm starting, our lower bound analysis can be extended with necessary modifications. In Section 4, we define the expansion properties assuming that the update rule is a mapping from the parameter's current state to its next state, independent of its previous states. However, with the warm-starting strategy, the hyperparameter update depends on all its previous states. Therefore, our proposed definitions and corresponding analysis need to be adjusted to characterize this dependence. Specifically, Definition 4.2 can be modified as: An update rule $G$ is $\\\\{\\rho_ s\\\\}_ {s=1}^S$-growing along $v$ if for all \n$\\\\{w_ s,w_ s'\\\\}_ {s=1}^S$ such that $w_ s-w_ s'$ parallel with $v$, $G(w_ S)-G(w_ S) \\circeq w_ S-w_ S', \\Vert G(w_ S)-G(w_ S)\\Vert\\geq \\sum_ {s=1}^S\\rho_ s \\Vert w_ s-w_ s'\\Vert.$ Consequently, the recursion in Theorem 5.1 will take the form: $E_A[\\delta_t]\\geq a_tE_A[\\delta_{t-1}]+a_{t-1}E_A[\\delta_{t-2}]+\\dots+a_2E_A[\\delta_{1}]+2\\alpha_tL'/m$ in contrast of the current form: $E_A[\\delta_t]\\geq a_tE_A[\\delta_{t-1}]+2\\alpha_tL'/m$. The stability lower bound will be derived by unrolling this revised recursion.\n\nRegarding the inverse Hessian-vector product solvers, we clarify that the algorithms presented in our paper (Algorithms 1, Eq.(2) and Eq.(3)) do not calculate the inver Hessian and thus do not use such numerical solver. While we recognize that for some IFT-based algorithms where the hypergradient is decomposed as $\\nabla_ {\\lambda}L = \\nabla_ {\\lambda}\\ell^{val} -\\underbrace{\\nabla_ {\\theta}\\ell^{val}(\\nabla^2_ {\\theta\\theta}\\ell^{tr})^{-1}}_ {\\text{inverse Hessian vector product}}\\nabla^2_ {\\theta\\lambda}\\ell^{tr}$, the reinitialization of the solver might be an important factor to consider. We suggest a similar modification as for the inner warm-starting strategy, involving additional dependency on parameters, to extend our methods to this case.\n\nThanks again for your insightful questions. Warm starting is indeed a commonly used practice to enhance the efficiency of algorithms. We are not able to present a precise result on the lower bounds within this short rebuttal period, but we believe our work can inspire future attempts in these settings as described above. We will add relevant discussions in the revised version, and we believe this will improve the quality of our paper. We hope our response addresses your concerns and welcome any further feedback.", "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": "", "extra_scores": {}}, {"review_id": "B1rAoSxHQM", "reviewer": "Reviewer_3C12", "summary": "The paper provides new lower bounds for the uniform stability of UD-based and IFT-based algorithms in hyperparameter optimization.", "questions": "1. Are the bounds the authors present in theorems 5.6,5.7 tight?\n\nWhen denoting $ x = \\gamma \\left(1 - \\frac{1}{m}\\right) $ for $ \\gamma = \\gamma' $, the upper bound scales like $T^{cx} $ and the lower bound scales like $ T^{\\log(1+cx)} $. The authors state that when $ c $ is a small constant, ``the explicit lower bound closely aligns with the explicit upper bound'' (line 310). However, since  c appears in the exponent of T, for a multiplicative constant difference between the bounds,  c needs to depend on T.\n\n2. Does the technique of the paper can lead also to lower bounds for the average stability?", "limitations": "Yes.", "rating": 5, "confidence": 3, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "1. The general setting is described clearly.\n2. The uniform stability lower bounds presented in the paper are novel and clear.", "weaknesses": "1. In my view, the technique employed by the authors appears to be relatively straightforward. For the lower bound, they demonstrate that gradient algorithms may be costly when applied to a non-convex quadratic loss function. While this is not particularly surprising, it can result in a significant distance between the iterates of the two algorithms.\n\n2. The lower bound presented by the authors does not necessarily imply a generalization lower bound. This might be acceptable, given that there are existing works in the literature that show a lower bound for uniform stability (e.g., [30]). However, in relation to the previous point, I find the result to be less insightful.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "# Response to Reviewer 3C12\nWe thank Reviewer 3C12 for the thoughtful and constructive comments.\n## W1: Technical challenges of establishing the lower bounds\nWe agree that the instability of gradient-based algorithms on non-convex loss functions is intuitively expected, but rigorously establishing (nearly) tight lower bounds is a non-trivial task, especially for bilevel algorithms.\n\nFor bilevel algorithms, the stability bounds must consider key factors from both the outer and inner optimization processes (m, T, K), which poses challenges to achieving the tightness of the lower bounds. Moreover, the update of the outer parameters with the hypergradient (see Eq. (1), (2), (3), and the discussion for Example 5.4) becomes particularly complex due to the involvement of inner optimization, necessitating a careful design of the loss function beyond merely being non-convex. \n\n## W2: The implication of a stability lower bound.\nIndeed, as discussed in Section 6, a stability lower bound does not directly imply a generalization lower bound. However, our work focuses on characterizing the limit of the uniform stability on the generalization analysis, and we have presented (nearly) tight lower bounds for the UD-based algorithms which is currently missing in the literature and technically challenging as discussed in the response for W1. Moreover, our methods may inspire the establishment of the generalization lower bound as discussed in the following response for Q2 regarding single-level SGD.\n\n## Q1: The tightness of the lower bounds in Theorems 5.6 and 5.7.\n**The recursive lower and upper bounds in Eq.(7) are tight as claimed in Line 300,** while the adjusted bounds in Theorems 5.6 and 5.7 are not tight due to **unavoidable scaling steps needed to reveal an explicit order w.r.t. $T$**. \n\nFor a constant step size, i.e., $\\alpha_t = c$, Eq.(7) directly provides tight bounds that $[(1 + c(1 - 1/m)\\gamma)^T - 1]{2cL^\\prime}/{m} \\leq \\epsilon_{\\text{arg}} \\leq [(1 + c(1 - 1/m)\\gamma)^T - 1]{2cL}/{m}.$ However, when decreasing step sizes are adopted, additional scaling steps based on Eq.(7) must be applied to reveal an explicit order of the bounds w.r.t. $T$, resulting in the discrepancy between the bounds in Theorems 5.6 and 5.7.\n\nRegarding our statement of the close alignment, considering Thms 5.6 and 5.7, the discrepancy between $T^{cx}$ and $T^{\\log(1+cx)}$ is $T^{cx}/T^{\\log(1+cx)}=T^{cx-\\log(1+cx)}$ and thus depend on $T$. Following your suggestion, we will revise relevant statements to clarify that: the discrepancy between the bounds is $T^{cx}/T^{\\log(1+cx)}=T^{cx - \\log(1+cx)}$.\n\n## Q2: Extend the technique to the average stability.\n**Considering the similarities between average and uniform stability, we believe our techniques can be adapted to the data-dependent setting for average stability with some modifications, and we established a preliminary lower bound for single-level SGD using our Example E.1, which is comparable to the corresponding upper bound in [Theorem 4, 31].**\n\nTo account for the randomness in the sampled datasets, we first refine some notations. Let $S^{(i)}$ denote a copy of $S$ with the $i$-th element replaced by $z_i'$, $G_{S,t}$/$G_{S^{(i)},t}$ and $w_{S,t}$/$w_{S^{(i)},t}$ denote the SGD update rules and the updated parameters on $S$ and $S^{(i)}$ at the step $t$. With a similar proof as in the current paper and a slight adjustment on the Definition 4.3, Theorem 5.1 in our paper can be modified as: Suppose there exists a nonzero vector $v(S, S^{(i)})$ along which $G_{S,t}$ and $G_{S^{(i)},t}$ are $2\\alpha_tL'(S, S^{(i)})$-divergent and $L(\\cdot;z)$ is $\\gamma_t'(S, S^{(i)})$-expansive for all $w_{S,t} - w_{S^{(i)},t}$ that parallel with $v(S, S^{(i)})$. Then we have $$E_A[\\delta_t(S, S^{(i)})]\n\\geq [1+\\alpha_t(1-1/m)]\\gamma_t'(S, S^{(i)})E_A[\\delta_{t-1}(S, S^{(i)})]+2\\alpha_tL'(S, S^{(i)})/m.$$ \nThis recursion closely corresponds with the one in [Eq.(19), 31]: $$E_A[\\delta_t(S, S^{(i)})]\n\\leq [1+\\alpha_t(1-1/m)]\\psi_t'(S, S^{(i)})E_A[\\delta_{t-1}(S, S^{(i)})]+2\\alpha_tL(S, S^{(i)})/m,$$ and the matching of $\\gamma_t'\\\\&\\psi_t, L'\\\\&L$ will further guide the design of the constructed example.\n\nTherefore, our analysis framework can be adapted for the average stability with suitable modifications. However, specifically for average stability, a core challenge is calculating the expectation over $S$ and $S^{(i)}$ for the above recursive formula, which is beyond our ability to fully resolve within the short rebuttal period. Nevertheless, we can present a preliminary lower bound using Example E.1 with a simple assumption on the data distribution.\n\nAssume that the data follows a distribution $D$ that $p(z)=0.5$ for $z=(v_1, 1)$ and $z=(-v_1, 1)$ respectively, $S \\overset{i.i.d.}{\\sim} D^m$, $z_i' \\sim D$, and other conditions follow Example E.1 in our paper. Under these assumptions, we derive $L'(S, S^{(i)})=\\Vert y_ix_i-y_i'x_i'\\Vert /2$ and $\\mu_t(S, S^{(i)})=0$ for $z_i=z_i'$, $\\mu_t(S, S^{(i)})=\\vert\\gamma_1\\vert$ for $z_i\\neq z_i'$. This leads to the average stability lower bound: $\\epsilon\\geq\\sum_{t=1}^T\\prod_{s=t+1}^T(1+\\alpha_s(1-1/m\\vert\\gamma_1\\vert))\\alpha_t/m$. \n\nMoreover, for our example, Eq. (2) in Theorem 4 in [31] takes $\\gamma=\\vert \\gamma_1\\vert$. When adopting decreasing step sizes and removing the bounded loss assumption to get an adjusted upper bound as discussed in Lines 822-829, we further have: $$T^{\\ln(1+(1-1/m))c\\vert\\gamma_1\\vert}/m\\lesssim\\epsilon\\lesssim T^{(1-1/m)c\\vert\\gamma_1\\vert}/m.$$ \n\nFurthermore, related to the above W2, this lower bound also applies to another definition of average stability [Definition 5, 21] which is shown to be equivalent to the expected generalization error [Lemma 11, 21]. Therefore this lower bound is also a generalization lower bound.\n\nWe will add the above discussion and detailed proofs in the revised version. Thanks again for your valuable comments. We welcome any additional feedback to address any further questions.", "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": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: The paper makes an interesting contribution to the lower bounds on generalization error in a bi-level ERM setup. The authors are highly encouraged to address ReviewerNBuR's question on "how the generalization bound depends on the training dataset size" with a concrete bound (as opposed to a qualitative explanation) in the revision.
Decision: Accept (poster)