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
data  management
analysis  methods
Venue: NeurIPS_cc_2024_Conference
Published: 2024-05-14 11:56:04

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.

Main paper: 
 introduction: 
 Hyperparameters significantly influence the convergence behavior of learning algorithms as well as the efficiency and generalization performance of the trained model [1, 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 [4] , random search [5] , Bayesian optimization [6, 7, 8] , and evolutionary algorithms [9, 10] , which often suffer from the problem of scaling up. Recently, gradient-based methods have achieved excellent empirical performance in high-dimensional HO problems [11, 3, 12] .In gradient-based methods, HO is formulated as a bilevel programming problem. The inner level 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 is 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, 2, 14] or approximately applying the implicit function theorem (IFT) [1, 15, 16, 12] .To investigate the underlying reason for their success, existing work establishes generalization upper bounds based on algorithmic stability [17, 18] . 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 to key factors. Meaningful bounds for a 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 obtain 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: (1) 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 1 . 
related work: 
 Algorithmic stability [20, 21] measures the change in the model output when a single training example is replaced. It is shown to 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, a stability-based generalization bound, and a stability analysis depending on the algorithm. Below, we introduce the related work based on these three elements. 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, 27] 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 [28] , or change in the hypothesis [29, 30] are investigated for fine-grained 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 data-dependent generalization bounds to explain the effectiveness of practical techniques like proper initialization. sharper lower bounds by constructing a special class of loss functions. [34] adopts a similar approach by construction to 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 [34] . Compared with [34] , we consider a more complicated and nontrivial bilevel optimization problem, where the interaction between inner and outer processes brings a significant impact on the analysis. A detailed comparison is provided in Section 5.3 and Appendix E.Stability for bilevel programming. [17] extend the notion of 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, 3, 40, 41, 42, 43] 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 a vector a, ∥•∥ denotes its Euclidean norm. For a matrix A, ∥•∥ denotes its spectral norm. Additionally, let a 1 ⊜ a 2 denote a 1 and a 2 are collinear by a non-negative factor, namely, ∃a ≥ 0 s.t. a 1 = aa 2 .ℓ : Ω → R is L-Lipschitz continuous if ∀u, v ∈ Ω, ∥ℓ(u) -ℓ(v)∥ ≤ L∥u -v∥. It is γ-smooth if ∀u, v ∈ Ω, ∥∇ℓ(u) -∇ℓ(v)∥ ≤ γ∥u -v∥.Twin datasets. A pair of datasets are considered twin datasets if they differ in only a single data point, denoted by S ≃ S. Throughout this paper, we use a tilde symbol to distinguish their corresponding notions, e.g., examples z and z, output parameters w and w.Asymptotic notations. Denote with a n ≲ b n that a n is bounded above by b n up to a constant factor for sufficiently large n, and conversely by a n ≳ b n . We say a n ≍ b n if a n ≲ b n and a n ≳ b n .Question: Does the paper discuss the limitations of 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 in 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 on 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 a few datasets or with a 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, a facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or a 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 be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an important role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations. 
ho as bilevel programming: 
 Denote the testing, validation, and training distributions on the data space Z by D test , D val and D tr , and corresponding losses by ℓ test , ℓ val and ℓ tr . Since the validation phase is generally regarded as a rehearsal for testing, D val and ℓ val are commonly assumed to be consistent with D test and ℓ test .S val = {z val i } m i=1 i.i.d. ∼ (D val ) m and a training set S tr = {z tr j } n j=1 i.i.d. ∼ (D tr ) n ,HO algorithms seek the best-performing hyperparameter-parameter pair on S val . Denote by λ the hyperparameter in space Λ, θ the (model) parameter in space Θ. This process can be formulated as the following bilevel problem:λ ≈ arg min λ∈Λ 1 m m i=1 ℓ val (λ, θ(λ); z val i ), where θ(λ) ≈ arg min θ∈Θ 1 n n j=1 ℓ tr (λ, θ; z tr j ).Here, θ(λ) is selected by its training performance under the given λ and ℓ val (λ, θ(λ); z) can be rewritten as a compound validation loss L(λ; z) considering θ(λ) a function of λ.Various methods are proposed to solve this nested problem, among which gradient-based algorithms have recently achieved success in scalability [11, 3, 12] . As shown in Algorithm 1, 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,EQUATIONwhere 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:2 EQUATIONWhile representative IFT-based methods leverage the implicit function theorem and Neumann series to obtain an alternative estimation [12] :EQUATIONPlease refer to Algorithm 1 for the whole process. Notably, this paper adopts a common theoretical assumption [19, 17] of constant inner step sizes and decreasing outer step sizes. 3Algorithm 1 Gradient-based bilevel HO for k = 1 to K do 5:uniformly sampling j k from [n]6:θ k ← θ k-1 -η k ∇ θ ℓ tr (λ t-1 , θ k-1 ; z tr j k ) 7:end for 8:uniformly sampling i t from [m] 9:g ← ∇L(λ t-1 ; z val it ) ▷ UD-based algorithm in Eq. ( 2), IFT-based algorithm in Eq. (λ t ← λ t-1 -α t g 11: end for 12: return λ T and θ KThe generalization behavior of HO algorithms characterizes the selected model's potential performance on the unseen test data. Specifically, denoting the hyperparameter output by a stochastic HO algorithm A as A(S val , S tr ), we are interested in the difference between its expected testing risk and empirical validation risk, namely generalization error defined asEQUATIONStability-based generalization 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). A stochastic HO algorithm A is ϵ arguniformly argument stable on validation whereEQUATIONOur analysis mainly leverages this notion following [31] , as it is the key measure for stability bounds under the Lipschitz continuous condition. ϵ arg differs from the uniform stability ϵ stab defined in [17, Definition 1] only by a Lipschitz constant L (i.e., ϵ stab ≤ Lϵ arg ), and our results for ϵ stab are also provided in Theorem 5.6 and Theorem C.7 for direct comparison with former works. Existing stabilitybased generalization bound [17, Theorem 1] shows that uniform stability guarantees generalization in expectation for HO algorithms that ϵ gen ≤ ϵ stab .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 δ t := ∥λ t -λt ∥ at the t-th step. Theorem 3.2 (Recursion upper bound for UD, Theorems 2 and 3, [17] ). Suppose the compound validation loss L(•; z) is L-Lipschitz continuous and γ-smooth for all z ∈ Z, and the training loss ℓ tr (λ, •; z) is γ tr -smooth for all λ ∈ Λ and z ∈ Z. Then for all1 ≤ t ≤ T , E A [δ t ] ≤ 1 + (1 -1/m)α t γ E A [δ t-1 ] + 2αtL m , where L ≲ (1 + ηγ tr ) K , γ ≲ (1 + ηγ tr ) 2K .Unrolling this recursion, we directly get the stability upper bound in recursion form:EQUATIONAs this result does not explicitly display its order w.r.t. T under decreasing step sizes α t ≤ c/t, [17] further deforms Eq. ( 6) with the bounded loss condition to obtain ϵ stab ≲ T(1-1/m)γc(1-1/m)γc+1 /m.[18] analyzes a specific IFT-based algorithm, which, under certain assumptions, achieves a similar result of ϵ stab ≲ T q /m with q < 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.Question: For each theoretical result, does the paper provide the full set of assumptions and a complete (and correct) proof? Answer: [Yes]• Examples of negative societal impacts include potential malicious or unintended uses (e.g., generating fake profiles, surveillance), fairness 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 a direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an 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 a 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 as 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 or 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 to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML). 
expansion properties of update rules: 
 This paper endeavors to establish tight lower bounds for uniform (argument) stability as 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 a 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 [19] and the key difference lies in our focus on 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 a general framework for analyzing the lower bounds of algorithmic stability.Let w be a general notation for parameters (or hyperparameters) in space Ω. 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 t } T t=1 and {G ′ t } T t=1 , and the corresponding outputs by {w t } T t=1 and {w ′ t } T t=1 . Intrinsically, the divergence between w t and w ′ t 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 to 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 to characterize properties of update rules leading to increasing divergence. Definition 4.1 (σ-divergent). Two update rules G and Intuitively, σ-divergent update rules produce sufficiently divergent output parameters and a ρ-growing update rule scales the divergence between parameters with a sufficiently large factor. The direction v is chosen as the most expansive direction, as detailed with a concrete example in Section 5.4.G ′ are σ-divergent along v if for all w ∈ Ω, G(w) -G ′ (w) ⊜ v, ∥G(w) -G ′ (w)∥ ≥ σ. Definition 4.2 (ρ-growing). An update rule G is ρ-growing along v if for all w, w ′ ∈ Ω such that w -w ′ parallel with v, G(w) -G(w ′ ) ⊜ w -w ′ , ∥G(w) -G(w ′ )∥ ≥ ρ∥w -w ′ ∥.One-step SGD can be generally formulated as G ℓ,α (w) = w -α∇ℓ(w), where the loss function directly impacts this gradient-based update rule. We now define the µ-expansive property for the loss function which leads to the growing property of SGD.Definition 4.3 (µ-expansive). A differentiable function ℓ : Ω → R is µ-expansive along v if for all w, w ′ ∈ Ω that ww ′ parallel with v, there exists µ w,w ′ ≥ µ such that ∇ℓ(w) -∇ℓ(w ′ ) = -µ w,w ′ (w -w ′ ).This paper mainly focuses on the case when µ > 0 where the loss function is nonconvex. We have µ ≤ 0 for the convex case. When µ > 0, Definition 4.3 connects to µ-strongly concavity. 5 These concepts are equivalent in the one-dimensional case. In general, µ-strongly concavity imposes uniform curvature in all directions, while µ-expansiveness restricts concavity in only one direction with an additional restriction for the colinearity of ∇ℓ(w) -∇ℓ(w ′ ) and -(w -w ′ ). See Appendix G.2 for details. We illustrate a simple loss function in Fig. 1 that satisfies Definition 4.3.Notably, the directional restrictions on the update rules in Definitions 4.1 to 4.3 simplify the lowerbound calculations as it enables us to focus only on the norm of the divergence at each step and get rid of directional variation, which aids in a clearer understanding of divergence dynamics. As a first attempt to 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 to exhibit a specific directional component rather than strict alignment as in the current definitions.The following lemma shows that the expansiveness of the loss function can induce the growing property of SGD. Suppose ℓ is µ-expansive along v and 1 + αµ ≥ 0, then G ℓ,α is (1 + αµ)-growing along v. 
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 lower-bounded recursion of hyperparameter divergence that aligns with Theorem 3.2 given the expansion properties of the outer optimization, followed by a 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.We first establish a uniform argument stability lower bound by considering the outer level of the bilevel programming as a single-level optimization problem w.r.t. the hyperparameters. This approach takes the compound validation loss L as a whole, temporarily disregarding the dependence of this loss on the inner-level solution and the inner Jacobian.Suppose S val and Sval are twin validation sets differing only on the i-th entry, and denote the sequences of update rules on S val and Sval as {G zi t ,αt } T t=1 and {G zi t ,αt } T t=16 respectively. 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 4.4 and B.2, we obtain a lower bound of the stability in the following Theorem 5.1. Theorem 5.1 (Lower bound given outer-level expansion properties, proof in Appendix B.3). Suppose there exists a nonzero vector v along which G zi,αt and G zi,αt are 2α t L ′ -divergent and L(•; z) is γ ′ -expansive for all z ∈ S val . Then we haveE A [δ t ] ≥ 1 + α t (1 -1 m )γ ′ E A [δ t-1 ] + 2αtL ′ m and ϵ arg ≥ T t=1 T +1 s=t+1 1 + α s (1 -1/m)γ ′ 2α t L ′ m .Theorem 5.1 echos the upper bound formulation in Eq. (6) . The distinctions arise solely in the smooth/expansive coefficients γ/γ ′ and the continuous/divergent coefficients L/L ′ . Consequently, the alignment of these two bounds (i.e., 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 E.Based on Theorem 5.1, our next step towards building stability lower bounds is analyzing the expansive coefficient γ ′ and divergent coefficient L ′ of outer-level optimization where the hypergradient is used for update. As can be observed in Eq. ( 1), the inner Jacobian ∇ λ θ K (λ) is a 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 θ K (λ) regarding λ denoted by L θ K , to provide a guarantee for the effect of the hypergradient.Denote corresponding inner update rules as G λ,η and G λ ′ ,η given hyperparameters λ and λ ′ . Applying them consecutively for K times, we get two sequences of inner updates. Theorem 5.2 presents how the expansion properties of the inner problem characterize the lower bound of L θ K . Theorem 5.2 (Lower bound of Lipschitz of the inner-level solution, proof in Appendix B.4). Given any two hyperparameters λ, λ ′ ∈ Λ, suppose there exists a nonzero vector v along which G λ,η and G λ ′ ,η are ∥λ -λ ′ ∥σ tr -divergent and ℓ tr (λ, •; z) is µ tr -expansive for all z ∈ S tr with µ tr > 0. Then we haveL θ K ≥ σ tr ηµ tr [(1 + ηµ tr ) K -1].Omitting constants that depend on η, σ tr , and µ tr , we get L θ K ≳ (1 + ηµ tr ) K .It is worth mentioning that our lower bound for L θ K is matched with its upper bound in [17] (see in Theorem 3 and Proposition 2), which prepares us to obtain a tight lower bound.Motivated by Theorems 5.1 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 HO algorithms. Example 5.3. We introduce an HO problem as follows. The validation loss and training loss are given by:ℓ val (λ, θ; z) = ℓ tr (λ, θ; z) = 1 2 θ ⊤ Aθ + λ ⊤ θ -yx ⊤ θ, where A ∈ R d×d is symmetric. Denote the eigenvalues of A as γ 1 ≤ • • • ≤ γ d . Let γ 1 < 0 and |γ 1 | ≥ |γ d |,and v 1 be a unit eigenvector for γ 1 . Let S val and Sval be a pair of twin validation datasets differing at the i-th example wherez i = (x i , y i ) = (v 1 , 1), zi = (x i , ỹi ) = (-v 1 , 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 D for the results of (strongly) convex losses.Notably, our example satisfies Assumption B.1 adopted for establishing the stability upper bounds where the loss functions are Lipschitz continuous and smooth. Hereafter we denote L(•; z) as L-Lipschitz continuous and γ-smooth, and ℓ tr (λ, •; z) as γ tr -smooth, where γ tr = |γ 1 |.Example 5.3 is 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 a non-zero inner Jacobian. The final term provides a connection for parameters and data. ℓ val and ℓ tr 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., v 1 ) which corresponds to the smallest eigenvalue. It represents the least convex direction, thereby offering the greatest expansiveness of the loss (see Fig. 1 ), 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 S val and Sval are set to align reversely with v 1 to 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 γ and the expansion coefficient µ 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.The following proposition shows that Example 5. L ≍ L ′ ≍ (1 + ηγ tr ) K , γ = γ ′ ≍ (1 + ηγ tr ) 2K .Combining the lower bound in Theorem 5.1 with the upper bound in Eq. ( 6), we instantly getEQUATIONwhere 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.e., α t = c for all t, Eq. ( 7) explicitly reveals the scale of ϵ arg regarding T :ϵ arg ≍ 1 + c(1 -1/m)γT /m. However, for linearly decreasing step sizes α t ≤ c/t, additional scaling steps 7 are necessary and the deformed result is provided below. T ln(1+(1-1 m )cγ ′ ) m ≲ ϵ arg ≲ T (1-1 m )cγ m ,where γ = γ ′ ≍ (1 + ηγ tr ) 2K as in Proposition 5.4.The scaling steps unavoidably create a discrepancy between the deformed lower and upper bounds, while their quotient,T (1-1 m )cγ-ln(1+(1-1 m )cγ ′ ), is small given a small c (e.g., 0.01). We compare the practical output hyperparameter distances and the theoretical bounds in Fig. 2 .Notably, the upper bound in our result is not contradictory to the existing upper bound of ϵ arg ≲T (1-1/m)γc (1-1/m)γc+1 /m in [17] because we remove the bounded loss assumption, i.e., ∃a, b ∈ R s.t. L ∈ [a, 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, we can further obtain similar results of uniform stability by introducing additional assumptions as below.Theorem 5.6 (Uniform stability of UD-based algorithms, proof in Appendix B.7). Following the same condition as in Theorem 5.5, and additionally, if the initial points θ 0 = 0, λ 0 = 0, and v 1 ⊥ x val j for any j ∈ [m]\i and v 1 ⊥ x tr j for any j ∈ [n], then Algorithm 1 has uniform stabilitythat T ln ( 1+(1-1 m )cγ ′ ) m ≲ ϵ stab ≲ T (1-1 m )cγ m, where γ = γ ′ ≍ (1 + ηγ tr ) 2K as in Proposition 5.4.Technically, we adopt these additional assumptions following [34] to simplify the formulation of L(λ T , z) -L(λ ′ T , z) by eliminating the quadratic term and reducing it to be colinear with λ T -λ ′ T . By doing so, a clear relation can be established between the loss divergence and the hyperparameter divergence, which leads to a transfer from uniform argument stability to uniform stability. Remark. For now, we have characterized the stability error as an upper bound on the generalization error. Let us now 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 m = aN assigned to the validation set S val and n = (1 -a)N assigned to the training set S tr , where a ∈ (0, 1). The expected population risk can be decomposed into the generalization error and the empirical validation risk as follows:E A,S val ,S tr ,z test L(A(S val , S tr ); z test ) = ϵ gen (I) + E A,S val ,S tr   1 m m i=1 L(A(S val , S tr ); z val i )   (II).On one hand, the generalization bound ϵ gen ≤ ϵ stab = Θ(1/aN ) (as in Eq. ( 7)) suggests that a should be sufficiently large to keep term (I) small. On the other hand, a 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 a involves a trade-off to optimize the overall population risk. 
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 lower-bounded 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 in 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, a uniform stability lower bound does not directly imply a 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 is a purely theoretical work, we have not identified any direct, significant societal impacts that must be emphasized. 
safeguards: 
 Question: Does the paper describe 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)? 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 a 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 a best faith effort. 12. Licenses for existing assets Question: 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? Answer: [NA] Justification: This paper does not use existing assets. Guidelines:• The answer NA means that the paper does not use existing assets.• The authors should cite the original paper that produced the code package or dataset.• The authors should state which version of the asset is used and, if possible, include a 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 of use in the package should be provided. For popular datasets, paperswithcode.com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of a dataset. 
 
 Appendix: A.1 Overview of the main contributions Recursive lower bound:T t=1 T s=t+1 (1 + α s (1 -1/m)γ ′ ) 2αtL ′ m , where γ ′ = γ ≍ (1 + ηγ tr ) 2K , L ′ ≍ (1 + ηγ tr ) K (Ours)Recursive upper bound:T t=1 T s=t+1 (1 + α s (1 -1/m)γ) 2αtL m , where γ ≲ (1 + ηγ tr ) 2K , L ≲ (1 + ηγ tr ) K [17]Deformed lower bound:≳ T ln(1+(1-1/m)cγ ′ m , where γ ′ = γ ≍ (1 + ηγ tr ) 2K (Ours)Deformed upper bound:≲ T (1-1/m)cγ m , where γ ≲ (1 + ηγ tr ) 2K (Ours)Recursive lower bound:T t=1 T s=t+1 (1 + α s (1 -1/m)γ ′ ) 2αtL ′ m , where γ ′ = γ ≍ (1 + ηγ tr ) 2K , L ′ ≍ (1 + ηγ tr ) K (Ours)Recursive upper bound: T t=1 T s=t+1 (1 + α s (1 -1/m)γ) 2αtL m , where γ ≲ K(1 + ηγ tr ) 2K , L ≲ (1 + ηγ tr ) K (Ours) Deformed lower bound ≲ T ln(1+(1-1/m)cγ ′ ) m , where γ ′ ≳ (1 + ηγ tr ) 2K (Ours) Deformed upper bound ≲ T (1-1/m)cγ m , where γ ≲ K(1 + ηγ tr ) 2K (Ours) A.2We first list some assumptions in the derivation for upper bounds [17] , 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. G ℓ,α (w) -G ℓ,α (w ′ ) =w -w ′ -α ∇ℓ(w) -∇ℓ(w ′ ) =w -w ′ + αa(w -w ′ ) =(1 + αµ w,w ′ )(w -w ′ ),where µ w,w ′ ≥ µ and thus 1 + αµ w,w ′ ≥ 1 + αµ ≥ 0 by assumption. Therefore, we haveG ℓ,α (w) -G ℓ,α (w ′ ) ⊜ w -w ′ and ∥G ℓ,α (w) -G ℓ,α (w ′ )∥ ≥ (1 + αµ)∥w -w ′ ∥, which implies G ℓ,α is (1 + αµ)-growing on v according to Definition 4.2.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 w 0 = w ′ 0 ∈ Ω. Suppose there exists a nonzero vector v along which, for all 1 ≤ t ≤ T , G t ̸ = G ′ t are σ-divergent and G t are ρ-growing. Then we have w t -w ′ t ⊜ v for all 1 ≤ t ≤ T and recursively,∥w 0 -w ′ 0 ∥ = 0, ∥w t -w ′ t ∥ ≥ ρ∥w t-1 -w ′ t-1 ∥ + σ, G t ̸ = G ′ t , ρ∥w t-1 -w ′ t-1 ∥, G t = G ′ t , t ≥ 1.Proof. Without loss of generality, assume v 1 is a unit vector (i.e., ∥v 1 ∥ = 1). At the initial point, we have w 0 -w ′ 0 = 0 ⊜ v. According to Definition 4.1 and Definition 4.2, ifw t-1 -w ′ t-1 ⊜ v, then w t -w ′ t = G t (w t-1 ) -G ′ t (w ′ t-1 ) = G t (w t-1 ) -G t (w ′ t-1 ) + G t (w ′ t-1 ) -G ′ t (w ′ t-1 ) G t ̸ = G ′ t G t (w t-1 ) -G t (w ′ t-1 ) G t = G ′ t = ρ t (w t-1 -w ′ t-1 ) + σ t v, G t ̸ = G ′ t , ρ t (w t-1 -w ′ t-1 ), G t = G ′ t , = (ρ t ∥w t-1 -w ′ t-1 ∥ + σ t )v, G t ̸ = G ′ t , ρ t ∥w t-1 -w ′ t-1 ∥v, G t = G ′ t, where ρ t ≥ ρ and σ t ≥ σ. 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.1: Suppose there exists a nonzero vector v along which G zi,αt and G zi,αt are 2α t L ′ -divergent and L(•; z) is γ ′ -expansive for all z ∈ S val . Then we haveϵ arg ≥ T t=1 T s=t+1 1 + α s (1 -1/m)γ ′ 2α t L ′ m .Proof. Using Lemma 4.4, we have G zi t ,αt and G zi t ,αt are (1 + α t γ ′ )-growing for all 1 ≤ t ≤ T . Denote δ t = ∥λ t -λt ∥ for each step t. As Algorithm 1 is initialized with the same starting point, we know that λ 0 = λ0 and thus δ 0 = 0. For all 1 ≤ t ≤ T , there is a probability of 1 -1 m to select the same examples and 1 m otherwise. Consequently, by the law of total probability, we have the recurrence relationE A [δ t ] ≥ 1 - 1 m E A [(1 + α t γ ′ )δ t-1 ] + 1 m E A [δ t-1 + 2α t L ′ ] (Lemma B.2, the law of total probability)= 1 + α t (1 - 1 m )γ ′ E A [δ t-1 ] + 2α t L ′ m (linearity of expectation),By unwinding the recurrence from T to 1, for all S val ≃ Sval ∈ Z m , S tr ∈ Z n we haveEQUATIONwhich impliesϵ arg ≥ T t=1 T s=t+1 1 + α s (1 -1/m)γ ′ 2α t L ′ m .B.4 Proof of Theorem 5.2Here we prove a more general version of Theorem 5.2 in the main paper by additionally considering the cases where µ tr ≤ 0. Theorem 5.2 in the main paper can be simply derived by letting µ tr > 0. Theorem B.3 (Lower bound of Lipschitz of the inner-level solution, generalized Theorem 5.2). Given any two hyperparameters λ, λ ′ ∈ Λ, suppose there exists a nonzero vector v along which G λ,η and G λ ′ ,η are ∥λ -λ ′ ∥σ tr -divergent and ℓ tr (λ, •; z) is µ tr -expansive for all z ∈ S tr where 1 + ηµ tr ≥ 0.Then we haveL θ K =      σ tr ηµ tr [(1 + ηµ tr ) K -1], µ tr > 0, σ tr K, µ tr = 0, σ tr η|µ tr | [1 -(1 -η|µ tr |) K ], µ tr < 0.Omitting constants that depend on η, σ tr , and µ tr , we getL θ K ≳    (1 + ηµ tr ) K , µ tr > 0, K, µ tr = 0, 1, µ tr < 0.Proof. First, for any λ and λ ′ , we establish a lower bound of ∥θ K (λ) -θ K (λ ′ )∥ in a recursion way. Using Lemma 4.4, we have G λ,η and G λ ′ ,η are (1 + ηµ tr )-growing. For any inner step 1 ≤ k ≤ K, we haveEQUATION+ ηµ tr ≥ 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 (λ) -θ K (λ ′ )∥ ≥ K-1 k=0 (1 + ηµ tr ) k σ tr ∥λ -λ ′ ∥,which implies that for any λ ∈ Λ. According to the mean value theorem for vector valued multivariable function, there exists a c on line segment determined by λ and λ ′ such that ∥∇θ K (c)(λ-λ ′ )∥ ≥ ∥θ K (λ) -θ K (λ ′ )∥, and for triangle inequality, we have ∥∇θK (c)∥∥λ -λ ′ ∥ ≥ ∥∇θ K (c)(λ -λ ′ )∥.Therefore, by the definition of Lipschitz continuity, it holds that L θ K ≥ ∥∇θ K (c)∥ ≥ ∥θ K (λ) -θ K (λ ′ )∥ ∥λ -λ ′ ∥ ≥ σ tr K-1 k=0 (1 + ηµ tr ) k =        σ tr (1+ηµ tr ) K -1 ηµ tr , µ tr > 0, σ tr K, µ tr = 0, σ tr 1-(1-η|µ tr |) K η|µ tr | , µ tr < 0,(I -ηA) k   2I -ηA K-1 k=0 (I -ηA) k   = η K-1 k=0 (1 -ηγ 1 ) k   2 -ηγ 1 K-1 k=0 (1 -ηγ 1 ) k   ≍    (1 -ηγ 1 ) 2K , γ 1 < 0, K, γ 1 = 0, 1, γ 1 > 0.Proof. For simplicity, we denote ηK-1 k=0 (I -ηA) k 2I -ηA K-1k=0 (I -ηA) k by C, then C is symmetric and has eigenvectors v 1 , . . . , v d as well. Based on the symmetric of C, ∥C∥ equals to its maximum absolute eigenvalue, which can be expressed as∥C∥ = sup i |∥Cv i ∥| = sup i η K-1 k=0 (1 -ηγ i ) k   2 -ηγ i K-1 k=0 (1 -ηγ i ) k   = sup i    2ηK γ i = 0, η K-1 k=0 (1 -ηγ i ) k 2 -ηγ i 1-(1-ηγi) K 1-(1-ηγi) γ i ̸ = 0 = sup i 2ηK γ i = 0, η K-1 k=0 (1 -ηγ i ) k 1 + (1 -ηγ i ) K γ i ̸ = 0.The last equation forγ i ̸ = 0 holds for 1 -ηγ i ≥ 1 -ηγ d ≥ 0.We define h(γ):= η K-1 k=0 (1 -ηγ) k 1 + (1 -ηγ) K , which is decreasing on (-∞, γ d ],achieving the maximum at the smallest eigenvalue γ 1 . Therefore, ∥C∥ = η K-1 k=0 (1 -ηγ 1 ) k   2 -ηγ 1 K-1 k=0 (1 -ηγ 1 ) k   ≍    (1 -ηγ 1 ) 2K , γ 1 < 0, K, γ 1 = 0, 1, γ 1 > 0.L ≍ L ′ ≍    (1 + ηγ tr ) 2K , γ 1 < 0, K, γ 1 = 0, 1, γ 1 > 0, and γ = γ ′ ≍    (1 + ηγ tr ) 2K , γ 1 < 0, K, γ 1 = 0, 1, γ 1 > 0.Proof. As Example 5.3 satisfies Assumption B.1, we have L ′ ≤ L ≲ (1 + ηγ tr ) K by Theorem 3 in [17] . We are going to verify that L ′ ≳ (1 + ηγ tr ) K and γ = γ ′ ≳ (1 + ηγ tr ) 2K in the following.Given a hyperparameter λ, a constant step size η and a initial point θ 0 , at each step 1 ≤ k ≤ K, we have an inner updateEQUATIONAs L ′ and γ ′ describe the expansion properties of SGD on L, we first investigate the gradient of the compound validation loss∇L(λ; z) = θ K (λ) + ∇ λ θ K (λ) ⊤ Aθ K (λ) + λ -yx .For all λ ∈ Λ, the outer update divergence when SGD picks the distinct examples isG zi,αt (λ) -G zi,αt (λ) = α t ∇L(λ; z i ) -∇L(λ; zi ) = α t ∇ λ θ K (λ) ⊤ -y i x i -(-ỹ i xi ) = -2α t ∇ λ θ K (λ) ⊤ v 1 (y i = ỹi = 1, x i = v 1 , xi = -v 1 ) = 2α t η K-1 k=0 (I -ηA) k v 1 (A is symmetric) = 2α t η K-1 k=0 (1 -ηγ 1 ) k v 1 (Av 1 = γ 1 v 1 ) = 2α t η K-1 k=0 (1 + ηγ tr ) k v 1 . (γ tr = |γ 1 | = -γ 1 )Recalling Definition 4.1, we have G zi,αt and G z ′ i ,αt are α t L ′ -divergent along v 1 , whereEQUATIONFor the case that γ 1 < 0, we haveL ′ ≍ (1 + ηγ tr ) K .Next, we are going to clarify that L(λ) is γ ′ -expansive along v 1 , and γ ′ equals to the smooth constant γ of L(λ). As L is twice differentiable, according to the definition of smoothness, we haveEQUATION≍    (1 + ηγ tr ) 2K , γ 1 < 0, K, γ 1 = 0, 1, γ 1 > 0.Eq. ( 11) holds forγ tr = |γ 1 | = -γ 1 . For all λ, λ ′ ∈ Λ, such that λ -λ ′ = av 1 ⊜ v 1 where a ∈ R + , we have ∇L(λ; z) -∇L(λ ′ ; z) = θ K (λ) -θ K (λ ′ ) + ∇ λ θ K (λ) ⊤ Aθ K (λ) + λ -yx -∇ λ ′ θ K (λ ′ ) ⊤ Aθ K (λ ′ ) + λ ′ -yx = -η K-1 k=0 (I -ηA) k (λ -λ ′ ) -η K-1 k=0 (I -ηA) k   -Aη K-1 k=0 (I -ηA) k + I   (λ -λ ′ ) = -η K-1 k=0 (I -ηA) k   2I -ηA K-1 k=0 (I -ηA) k   (λ -λ ′ ) = -η K-1 k=0 (I -ηA) k   2I -ηA K-1 k=0 (I -ηA) k   av 1 = -η K-1 k=0 (1 -ηγ 1 ) k   2 -ηγ 1 K-1 k=0 (1 -ηγ 1 ) k   av 1 = -η K-1 k=0 (1 + ηγ tr ) k   2 + ηγ tr K-1 k=0 (1 + ηγ tr ) k   (λ -λ ′ ), := -γ ′ (λ -λ ′ ).According to Definition 4.3, this implies L(λ) is γ ′ -expansive along v 1 . Thereforeγ ′ = γ ≍    (1 + ηγ tr ) 2K , γ 1 < 0, K, γ 1 = 0, 1, γ 1 > 0.For the case that γ 1 < 0, we obtain that γ ′ = γ ≍ (1 + ηγ tr ) 2K .B.6 Proof of Theorem 5.5Here we prove a more general version of Theorem 5.5 in the main paper where γ 1 < 0 by additionally considering the cases where γ 1 ≥ 0. T ln(1+(1-1 m )cγ ′ ) m ≲ ϵ arg ≲ T (1-1 m )cγ m , where γ = γ ′ ≍    (1 -ηγ 1 ) 2K , γ 1 < 0, K, γ 1 = 0, 1, γ 1 > 0.as in Proposition B.5.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 5.1 and utilizes a scaling operation that whenr = ln(1+(1-1/m)cγ ′ ) (1-1/m)cγ ′, it holds that 1 + x ≥ exp(rx) for any x ∈ (1 -1/m)cγ ′ /t|1 ≤ t ≤ T . According to Theorem 5.1, we haveEQUATION1 t ≥ ln t2+1 t1 )) = T t=1 T + 1 t + 1 r(1-1/m)cγ ′ 2cL ′ tm ≥ 2cL ′ m (T + 1) r(1-1/m)cγ ′ T +1 t=2 t -r(1-1/m)cγ ′ -1 ≥ 2cL ′ m (T + 1) r(1-1/m)cγ ′ T +2 2 t -r(1-1/m)cγ ′ -1 dt (∀a > 0, T +1 t=2 t -a-1 ≥ T +2 2 t -a-1 dt) = 2cL ′ m (T + 1) r(1-1/m)cγ ′   2 -r(1-1/m)cγ ′ -(T + 2) -r(1-1/m)cγ ′ r 1 -1/m cγ ′   = 2L ′ r(m -1)γ ′ (T + 1) r(1-1/m)cγ ′ 2 -r(1-1/m)cγ ′ -(T + 2) -r(1-1/m)cγ ′ ≥ 2cL ′ mln 1 + (1 -1/m)cγ ′   T + 1 2 ln(1+(1-1/m)cγ ′ ) -1   . (r = ln(1+(1-1/m)cγ ′ ) (1-1/m)cγ ′) Then, we continue to derive the right side of the result (i.e., the upper bound). Based on Eq. ( 6), we haveEQUATION1 t ≤ ln t2 t1-1 )) = T t=1 T t (1-1/m)γc 2cL tm = 2cL m T (1-1/m)γc T t=1 t -(1-1/m)γc-1 ≤ 2cL m T (1-1/m)γc 1 + T 1 t -(1-1/m)γc-1 dt (∀a > 0, T t=1 t -a-1 ≤ 1 + T 1 t -a-1 dt) = 2cL m(1 -1/m)cγ 1 + 1 -1/m γc T (1-1/m)γc -1 = 2L (m -1)γ 1 + 1 -1/m γc T (1-1/m)γc -1 .Therefore, it holds thatEQUATION)Omitting the constants depending on c, γ, and L, γ′ and L ′ , we haveT ln ( 1+(1-1 m )cγ ′ ) m ≲ ϵ arg ≲ T (1-1 m )cγ m, which completes the proof.B.7 Proof of Theorem 5.6Theorem 5.6: Following the same condition as in Theorem 5.5, and additionally, if the initial points θ 0 = 0, λ 0 = 0, and v 1 ⊥ x val j for any j ∈ [m]\i and v 1 ⊥ x tr j for any j ∈ [n], then the order of uniform stability ϵ stab w.r.t. T satisfies T ln (1+(1-1 m )cγ ′ ) m ≲ ϵ stab ≲ T (1-1 m )cγ m, where γ = γ ′ ≍ (1 + ηγ tr ) 2K as in Proposition 5.4.Proof. In the following, we show that ϵ stab explicitly shows the same order as ϵ arg in Theorem 5.5 with additional assumptions for Example 5.3. For the upper bound, it is easy to get with Lipschitz condition that ϵ stab = sup To obtain the lower bound, we need to explicitly derive the optimization process of A(S val , S tr ) and A( Sval , S tr ) (i.e., λ T and λT ), and corresponding loss values.S val ≃ Sval ∈Z m ,S tr ∈Z n ,z∈ZFrom the proof of Proposition 5.4, we know thatθ K (λ) = G λ,η G λ,η . . . G λ,η (θ 0 ) = (I -ηA) K θ 0 -η K-1 k=0 (I -ηA) k (λ -y tr j k x tr j k ) = -η K-1 k=0 (I -ηA) k (λ -y tr j k x tr j k ). (θ 0 = 0) = -η K-1 k=0 (I -ηA) k λ + η K-1 k=0 (I -ηA) k y tr j k x tr j k := -B K λ + b tr K , where symmetric matrix B K := η K-1 k=0 (I -ηA) k and vector b tr K := η K-1 k=0 (I -ηA) k y tr j k x tr j k . Building upon θ K (λ), we can derive L(λ, z) as L(λ, z) = 1 2 θ ⊤ K (λ)Aθ K (λ) + λ ⊤ θ K (λ) -yx ⊤ θ K (λ) = 1 2 (-B K λ + b tr K ) ⊤ A(-B K λ + b tr K ) + λ ⊤ (-B K λ + b tr K ) -yx ⊤ (-B K λ + b tr K ) = 1 2 λ ⊤ (B K AB K -2B K )λ + (-b tr⊤ K AB K + b tr⊤ K + yx ⊤ B K )λ + 1 2 b tr⊤ K Ab tr K -yx ⊤ b tr K = 1 2 λ ⊤ B K (AB K -2I)λ + (-b tr⊤ K AB K + b tr⊤ K + yx ⊤ B K )λ + 1 2 b tr⊤ K Ab tr K -yx ⊤ b tr K ,whose gradient is∇ λ L(λ, z) = B K (AB K -2I)λ + (-B K Ab tr K + b tr K + yB K x) = B K (AB K -2I)λ + yB K x + b tr K -B K Ab tr K .Then, the update rule of λ can be expressed asλ t =λ t-1 -α t ∇ λ L(λ t-1 , z it ) = λ t-1 -α t B K (AB K -2I)λ t-1 + y it B K x it + b tr K -B K Ab tr K = I -α t B K (AB K -2I) λ t-1 -α t y it B K x it -α t (b tr K -B K Ab tr K ). Now, by unwinding the recurrence from T to 1 with λ 0 = 0, we can obtainλ T = T t=1 I -α t B K (AB K -2I) λ 0 + T t=1 T s=t+1 I -α s B K (AB K -2I) (-α t y it B K x it ) + T t=1 T s=t+1 I -α s B K (AB K -2I) (-α t (b tr K -B K Ab tr K )) = T t=1 T s=t+1 I -α s B K (AB K -2I) (-α t y it B K x it ) r + T t=1 T s=t+1 I -α s B K (AB K -2I) (-α t (b tr K -B K Ab tr K )) a1 . (λ 0 = 0)Recall that S val and Sval only differ in the i-th entry where z i = (x i , y i ) = (v 1 , 1), zi = (x i , ỹi ) = (-v 1 , 1). Denote 1[•] as the indicator function. We simplify the term r as follows:r = T t=1 T s=t+1 I -α s B K (AB K -2I)   -α t B K m j=1 y j x j 1[i t = j]   = m j=1 T t=1 1[i t = j] T s=t+1 I -α s B K (AB K -2I) -α t B K y j x j = T t=1 1[i t = i] T s=t+1 I -α s B K (AB K -2I) (-α t B K y i x i ) + m j̸ =i T t=1 1[i t = j] T s=t+1 I -α s B K (AB K -2I) -α t B K y j x j = T t=1 1[i t = i] T s=t+1 I -α s B K (AB K -2I) (-α t B K v 1 ) + m j̸ =i T t=1 1[i t = j] T s=t+1 I -α s B K (AB K -2I) -α t B K y j x j = T t=1 1[i t = i] T s=t+1   I -α s η K-1 k=0 (I -ηA) k (Aη K-1 k=0 (I -ηA) k -2I)     -α t η K-1 k=0 (I -ηA) k v 1   + m j̸ =i T t=1 1[i t = j] T s=t+1 I -α s B K (AB K -2I) -α t B K y j x j = T t=1 1[i t = i] T s=t+1   1 -α s η K-1 k=0 (1 -ηγ 1 ) k (γ 1 η K-1 k=0 (1 -ηγ 1 ) k -2)     -α t η K-1 k=0 (1 -ηγ 1 ) k   v 1 + m j̸ =i T t=1 1[i t = j] T s=t+1 I -α s B K (AB K -2I) -α t B K y j x j = - T t=1 1[i = i t ] T s=t+1 1 -α s L ′ (γ 1 L ′ -2) α t L ′ v 1 b:=τ v1 + m j̸ =i T t=1 1[i t = j] T s=t+1 I -α s B K (AB K -2I) -α t B K y j x j a2 ,whereL ′ = η K-1 k=0 (1 -ηγ 1 )k as in Proposition B.5. We further define a := a 1 + a 2 , and then λ T = a 1 + a 2 -b = ab. Follow the same process of derivation, we have λT = a + b where the opposite symbol for b arise fromx i = v 1 while xi = v 1 .Recall that we have assumed that v 1 ⊥ x tr k for any k ∈ [n] and v 1 ⊥ x val j for any j ∈[m] that j ̸ = i, thus v ⊤ 1 b tr K = 0 and v ⊤ 1 x j = 0, j ̸ = i ∈ [m]. Therefore, a ⊤ b = T t=1 (-α t (b tr K -B K Ab tr K )) ⊤ T s=t+1 I -α s B K (AB K -2I) τ v 1 + m j̸ =i T t=1 1[i t = j] -α t B K y j x j ⊤ T s=t+1 I -α s B K (AB K -2I) τ v 1 .As B K := η K-1 k=0 (I -ηA) k and v 1 is the eigenvector of A, we have a ⊤ b = 0, i.e., a ⊥ b. Now, we are ready to discuss L(λ T , z) -L( λT , z).L(λ T , z) -L( λT , z) = 1 2 λ ⊤ T B K (AB K -2I)λ T + (-b tr⊤ K AB K + b tr⊤ K + yx ⊤ B K )λ T - 1 2 λ⊤ T B K (AB K -2I) λT -(-b tr⊤ K AB K + b tr⊤ K + yx ⊤ B K ) λT = 1 2 λ ⊤ T B K (AB K -2I)λ T - 1 2 λ ′⊤ T B K (AB K -2I) λT c +(-b tr⊤ K AB K + b tr⊤ K + yx ⊤ B K )(λ T -λT ),wherec = 1 2 (a -b) ⊤ B K (AB K -2I)(a -b) - 1 2 (a + b) ⊤ B K (AB K -2I)(a + b) = -2a ⊤ B K (AB K -2I)b -2b ⊤ B K (AB K -2I)a = -4a ⊤ B K (AB K -2I)b (by symmetric) = 4a ⊤ B K (AB K -2I)τ v 1 = 4(γ 1 L ′ -2)τ a ⊤ v 1 = 0.Therefore, L(λ T , z) -L( λT , z) can be simplified asL(λ T , z) -L( λT , z) = (-b tr⊤ K AB K + b tr⊤ K + yx ⊤ B K )(λ T -λT ) = -2(-b tr⊤ K AB K + b tr⊤ K + yx ⊤ B K )b (λ T -λT = -2b) = -2yx ⊤ B K b = -2yL ′ τ x ⊤ v 1 . (b = τ v 1 )Let z * = (v 1 , 1), we have|L(λ T , z * ) -L( λT , z * )| = 2L ′ τ ∥v 1 ∥ 2 = 2L ′ τ = L ′ ∥λ T -λT ∥. (∥λ T -λT ∥ = 2τ) Therefore, by the definition of ϵ stab , we haveϵ stab ≥ |L(λ T , z * ) -L( λT , z * )| = L ′ ∥λ T -λT ∥ ≥ T t=1 T s=t+1 1 + α s (1 -1/m)γ ′ 2α t L ′ m ,where the last inequality holds for Eq. ( 8) in the proof of Theorem 5.1. Following the proof of Theorem B.6, we can further deriveϵ stab ≥ 2cL ′ 2 T +1 2 ln(1+(1-1/m)cγ ′ ) -1 mln 1 + (1 -1/m)cγ ′ .Omitting the constants regarding c, γ ′ and L ′ , we haveϵ stab ≳ T ln ( 1+(1-1 m )cγ ′ ) m, which completes the proof.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.5 of Appendix C. These jointly lead to uniform argument stability bounds in Theorem C.6. For completeness, we also derive an upper bound for the IFT algorithm based on existing techniques [17] , presented together as follows.We first introduce the several lemmas useful for the following proofs.Lemma C.1 (Lemma 2 in [17] ). Suppose Λ and Θ are convex and compact with non-empty interiors, Z is compact, Λ × Θ × Z is included in an open set Ω and f (λ, θ; z) ∈ C k (Ω), then for all i ≤ k -1 order partial differential h(λ, θ; z) of f (λ, θ; z), we have sup Lemma C.1 implies that any i ≤ 1 order partial differential of ℓ val (λ, θ; z) is Lipschitz and any i ≤ 2 order partial differential of ℓ tr (λ, θ, z) is Lipschitz continuous under Assumption B.1. We denote the maximal Lipschitz constants among them as Q. Lemma C.2 (Theorem 3 in [17] ). Denote θ K (λ) as L θ K -Lipschitz continuous, we have L θ K ≲ (1 + ηγ tr ) K .Lemma C.3. In the case of Example 5.3, the ∇ λ θ K (λ) calculated by the IFT-based algorithm is exactly ∇ λ θ K (λ).Proof.∇ λ θ K (λ) = -∇ 2 θλ ℓ tr (λ, θ K (λ))η K-1 k=0 I -η∇ 2 θθ ℓ tr (λ, θ K (λ)) k = -η K-1 k=0 [I -ηA] k = ∇ λ θ K (λ).(Eq. ( 9))Now, we are ready to prove Propositions C. Proof. According to Lemma 1 in [17] , the Lipschitz continuous coefficient L = sup λ∈Λ ∇ λ L(λ; z) . For all λ ∈ Λ, we have∇ λ L(λ; z) = ∇ λ ℓ val (λ, θ K (λ); z) + ∇ λ θ K (λ)∇ θ ℓ val (λ, θ K (λ); z) ≤ ∇ λ ℓ val (λ, θ K (λ); z) + ∇ λ θ K (λ) ∇ θ ℓ val (λ, θ K (λ); z) ≤ Q + Q ∇ λ θ K (λ) = Q + Q ∇ 2 θλ ℓ tr (λ, θ K (λ))η K-1 k=0 I -η∇ 2 θθ ℓ tr (λ, θ K (λ)) k ≤ Q + ηQ ∇ 2 θλ ℓ tr (λ, θ K (λ)) K-1 k=0 I -η∇ 2 θθ ℓ tr (λ, θ K (λ)) k ≤ Q + ηQ 2 K-1 k=0 1 + η∥∇ 2 θθ ℓ tr (λ, θ K (λ))∥ k ≤ Q + ηQ 2 K-1 k=0 1 + ηγ tr k = Q + Q 2 1 + ηγ tr K -1 γ tr .Omitting the constants depending on Q, η, and γ tr , we get L ≲ ( 1 + ηγ tr K ).To obtain the smoothness coefficient γ, we first discuss the Lipschitz continuty coefficient of ∇ λ θ K (λ). In the following, we use ℓ tr to represent ℓ tr (λ, θ K (λ)) when there is no ambiguity.∇ λ ∇ λ θ K (λ) = ∇ λ   -∇ 2 θλ ℓ tr (λ, θ K (λ))η K-1 k=0 I -η∇ 2 θθ ℓ tr (λ, θ K (λ)) k   = -   ∇ 3 θλλ ℓ tr + ∇ λ θ K (λ)∇ 3 θλθ ℓ tr ) η K-1 k=0 I -η∇ 2 θθ ℓ tr ) k   B1 -   ∇ 2 θλ ℓ tr η K-1 k=1 -η ∇ 3 θθλ ℓ tr + ∇ λ θ K (λ)∇ 3 θλθ ℓ tr ) k I -η∇ 2 θθ ℓ tr (λ, θ K (λ)) k-1   B2 .We bound the spectral norm of B 1 and B 2 , respectively.∥B 1 ∥ = ∇ 3 θλλ ℓ tr + ∇ λ θ K (λ)∇ 3 θλθ ℓ tr ) η K-1 k=0 I -η∇ 2 θθ ℓ tr ) k ≤ Q + Q ∇ λ θ K (λ)   η K-1 k=0 (1 + ηγ tr ) k   ≤ Q + QL θ K   η K-1 k=0 (1 + ηγ tr ) k   ≲ (1 + ηγ tr ) 2K . (Lemma C.2)In addition,∥B 2 ∥ = ∇ 2 θλ ℓ tr η K-1 k=1 -η ∇ 3 θθλ ℓ tr + ∇ λ θ K (λ)∇ 3 θλθ ℓ tr ) k I -η∇ 2 θθ ℓ tr (λ, θ K (λ)) k-1 = ∇ 2 θλ ℓ tr η -η ∇ 3 θθλ ℓ tr + ∇ λ θ K (λ)∇ 3 θλθ ℓ tr ) K-1 k=1 k I -η∇ 2 θθ ℓ tr (λ, θ K (λ)) k-1 ≤ Qη 2 Q + Q ∇ λ θ K (λ)   K-1 k=1 k(1 + ηγ tr ) k-1   ≤ Qη 2 Q + QL θ K K(1 + ηγ tr ) K - (1 + ηγ tr ) K -(1 + ηγ tr ) ηγ tr -1 ≲ K(1 + ηγ tr ) 2K .Denote ∇ λ θ K (λ) to be L ∇ λ θ K -Lipschitz continuous for all λ ∈ Λ, then we haveL ∇ λ θ K = sup λ∈Λ ∇ λ ∇ λ θ K (λ) ≤ ∥B 1 ∥ + ∥B 2 ∥ ≲ K(1 + ηγ tr ) 2K .With the above result and Lemma C.3, we have that for all λ, λ ′ ∈ Λ,∇ λ L(λ; z) -∇ λ L(λ ′ ; z) ≤ ∇ λ ℓ val (λ, θ K (λ); z) -∇ λ ℓ val (λ ′ , θ K (λ ′ ); z) + ∇ λ θ K (λ)∇ θ ℓ val (λ, θ K (λ); z) -∇ λ θ K (λ ′ )∇ θ ℓ val (λ ′ , θ K (λ ′ ); z) ≤ ∇ λ ℓ val (λ, θ K (λ); z) -∇ λ ℓ val (λ ′ , θ K (λ); z) + ∇ λ ℓ val (λ ′ , θ K (λ); z) -∇ λ ℓ val (λ ′ , θ K (λ ′ ); z) + ∇ λ θ K (λ)∇ θ ℓ val (λ, θ K (λ); z) -∇ λ θ K (λ)∇ θ ℓ val (λ ′ , θ K (λ ′ ); z) + ∇ λ θ K (λ)∇ θ ℓ val (λ ′ , θ K (λ ′ ); z) -∇ λ θ K (λ ′ )∇ θ ℓ val (λ ′ , θ K (λ ′ ); z) ≤ Q∥λ -λ ′ ∥ + Q θ K (λ) -θ K (λ ′ ) + ∇ λ θ K (λ) Q∥λ -λ ′ ∥ + Q θ K (λ) -θ K (λ ′ ) + Q ∇ λ θ K (λ) -∇ λ θ K (λ ′ ) ≤ Q∥λ -λ ′ ∥ + QL θ K ∥λ -λ ′ ∥ + L θ K Q∥λ -λ ′ ∥ + QL θ K ∥λ -λ ′ ∥ + QL ∇ λ θ K ∥λ -λ ′ ∥ ≲ K(1 + ηγ tr ) 2K ∥λ -λ ′ ∥.which implies that γ ≲ K(1 + ηγ tr ) 2K . L ′ ≳ (1 + ηγ tr ) K , γ ′ ≳ (1 + ηγ tr ) 2K .Proof. According to Lemma C.3, in the case of Example 5.3, the hypergradient calculated with the IFT-based algorithm is 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 γ ′ as in Proposition 5.4 that L ′ =≳ (1 + ηγ tr ) K and γ ′ ≳ (1 + ηγ tr ) 2K , which complete the proof.Combining the lower bound in Theorem 5.1 with the upper bound in Equation ( 6), we instantly have EQUATION)cγ ′ ) m ≲ ϵ arg ≲ T (1-1 m )cγ m , where γ ≲ K(1 + ηγ tr ) 2K , γ ′ ≳ (1 + ηγ tr ) 2K as in Proposition C.5.The upper bound is not limited to Example 5.3, but holds in more general case with the same mild assumption in [17] (see Assumption B.1). Notably, in contrast to the outcomes observed with the UD-based algorithm, the upper bound incorporates an 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 a similar guarantee for the uniform stability ϵ stab detailed in Theorem C.7.Proof. Based on properties in Propositions C.4 and C.5 the same proof as Theorem 5.5, 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 θ 0 = 0, λ 0 = 0, and v 1 ⊥ x val j for any j ∈ [m]\i and v 1 ⊥ x tr j for any j ∈ [n], then the order of uniform stability ϵ stab w.r.t. T satisfiesT ln ( 1+(1-1 m )cγ ′ ) m ≲ ϵ stab ≲ T (1-1 m )cγ m, where γ and γ ′ are the same as in Proposition C.5.Proof. With the same proof as Theorem 5.6, we can get the result.Recalling that in Example 5.3, ℓ tr (λ, θ; z) = 1 2 θ ⊤ Aθ +λ ⊤ θ -yx ⊤ θ, where the smallest eigenvalue of A is γ 1 . Therefore, when γ 1 ≥ 0 (γ 1 > 0), ℓ tr (λ, θ; z) is convex (strongly convex) w.r.t. θ for all z ∈ Z. Utilizing the case for γ 1 ≥ 0 (γ 1 > 0) in Proposition B.5 and the same proof as in Theorem B.6 and Theorem 5.6, 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 ℓ tr ). Solving Example 5.3 by UD-based Algorithm 1 with constant inner step size η where 1 -ηγ d ≥ 0 and decreasing outer step sizes α t = c/t with c as a positive constant has uniform argument stability thatT ln(1+(1-1 m )cγ ′ ) m ≲ ϵ arg ≲ T (1-1 m )cγ m ,where γ = γ ′ ≍ K when γ 1 = 0 and γ = γ ′ ≍ 1 when γ 1 > 0 as in Proposition B.5.Proof. Please refer to the proof of Proposition B.5 and Theorem B.6 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 ℓ tr ). Following the same condition as in Theorem D.1, and additionally, if the initial points θ 0 = 0, λ 0 = 0, and v 1 ⊥ x val j for any j ∈ [m]\i and v 1 ⊥ x tr j for any j ∈ [n], then Algorithm 1 has uniform stability thatT ln(1+(1-1 m )cγ ′ ) m ≲ ϵ stab ≲ T (1-1 m )cγ m ,where γ = γ ′ ≍ K when γ 1 = 0 and γ = γ ′ ≍ 1 when γ 1 > 0 as in Proposition B.5.Proof. Please refer to the proof of Theorem 5.6.As discussed in Section 4, deriving a stability lower bound entails constructing an example with maximum instability, and we need to 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-based bilevel HO algorithms and the single-level SGD have equivalent formulation observing corresponding relations between λ ↔ w, L ↔ ℓ, S val ↔ S and stability definitions Definition 3.1 ↔ Eq. ( 15). As a result, given the smoothness constants γ for L and ℓ, the stability upper bounds under the bounded loss condition for the bilevel (ϵ stab ≲ T(1-1/m)γc(1-1/m)γc+1 /m in [17] ) and single-level (ϵ stab ≲ T γc γc+1 /m in [19] ) algorithms have similar results. Given those properties, their stability lower bounds can be analyzed in a general framework: construct a welldesigned example, examine its key properties, and derive the stability lower bound in response to these properties.Our proposed lower-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 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 [19] . Based on this, Appendix E.2 leverages the lower-bounded expansion properties established in Section 4 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 a 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 w 0 ; dataset S; step size scheme α 2: Output: The parameter w T 3: for t = 1 to T do 4:uniformly sampling i t from [m] 5: g ← ∇ℓ(w t-1 ; z it ) 6:w t ← w t-1 -α t g 7: end for 8: return w T 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 a sampleS = {z i } m i=1 i.i.d.∼ D m . Suppose w is the parameter to optimize in space Ω, and its loss on an example z is ℓ(w; z). The single-level SGD is shown in Algorithm 2. Following [19] , the generalization error of single-level SGD is defined asEQUATIONand we say a single-level stochastic algorithm A is ϵ arg -uniformly argument stable if,EQUATIONBased on these definitions, [19] has shown that stability guarantees generalization in single-level problems: if a stochastic algorithm A is ϵ arg -uniformly argument stable and the loss function ℓ(w; z) is L-Lipschitz on Ω for all z ∈ Z, then we haveEQUATIONWe first present a single-level example following [34] .Example E.1. Suppose Ω = {w : ∥w∥ ≤ W } where W > 0, andZ = X × Y where X = {x : ∥x∥ ≤ 1} and Y = [-1, 1]. Assume the loss function is ℓ(w; z) = 1 2 w ⊤ Aw -yx ⊤ w, where A ∈ R d×d is a symmetric matrix. Denote the eigenvalues of A as γ 1 ≤ • • • ≤ γ d , where γ 1 < 0 and |γ 1 | ≥ |γ d |,and v 1 as a unit eigenvector of A for γ 1 . Additionally, suppose the twin datasets S and S are different at the i-th entry, where Proof. For all w ∈ Ω,z i = (x i , y i ) = (v 1 , 1), zi = (x i , ỹi ) = (-v 1 , 1).G zi,αt (w) -G zi,αt (w) = -α t ∇ℓ(w; z i ) -∇ℓ(w; zi ) = -α t (y i x i -ỹi xi ) = 2α t v 1 ⊜ v 1 .Recalling Definition 4.1, this implies G zi,αt and G zi,αt are 2α t L ′ -divergent where L ′ = 1. Additionally, for all w, w ′ ∈ Ω such that ww ′ collinear with v 1 and any z ∈ Z, we have∇ℓ(w; z) -∇ℓ(w ′ ; z) = A(w -w ′ ) = γ 1 (w -w ′ ) = -|γ 1 |(w -w ′ ).Recalling Definition 4.3, this implies ℓ(w; z) is γ ′ -expansive on Ω for all z ∈ Z where γ ′ = |γ 1 |.Given Proposition E.3, we can directly leverage Theorem 5.1 to obtain a stability lower bound.Theorem E.4 (Lower bound of single-level SGD in recursion form). In th case of Example E.1, running SGD for T steps on a γ-smooth loss function has uniform argument stability withϵ arg ≥ T t=1 T s=t+1 1 + α s (1 -1/m)γ 2α t m .Proof. Using Theorem 5.1 and Proposition E.3, we gets the result.Following the proof of Theorem 5.5 we can deform the result in Theorem E.4 to display an explicit order under decreasing step sizes.Theorem E.5 (Lower bound of single-level SGD in deformed form). In th case of Example E.1, running SGD for T steps on a γ-smooth loss function with step sizes α t = c/t has uniform argument stability withϵ arg ≥ 2c mln 1 + (1 -1/m)cγ   T + 1 2 ln(1+(1-1/m)cγ) -1   .Omitting constant factors that depends on c and γ, we haveϵ arg ≳ T ln(1+(1-1/m)cγ) m .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 w.r.t. m. To see this, we first show that the step-size settings are equivalent. In particular, α t = a 0.99γt (Lemma 3, [34] ) is equivalent to α t = c t (Theorem E.5, ours) with c = a 0.99γ . Based on this equivalence, we can rewrite the lower bound in [34] as ϵ arg ≳ T 0.99cγ m 1+0.99cγ with assumptions c = 1, 0 < γ < 0.1 0.99 and T > m (detailed in the proof of Theorem 4, [34] ). In contrast, our lower bound of ϵ arg ≳ T ln(1+(1-1/m)cγ) m in Theorem E.5 holds for any c > 0, γ > 0, T ≥ 1, relaxing the conditions. Regarding the tightness of the lower bound, our result is sharper concerning m givenlim m→∞ T 0.99cγ m 1+0.99cγ T ln(1+(1-1/m)cγ) m= 0 for fixed T . In addition, concerning T , our result is comparable observing that the ratio of the powers on T differ slightly, namely 0.96 ≤ 0.99cγ ln(1+(1-1/m)cγ) ≤ 1.06 for all m ≥ 100, under the scope of application of their result (i.e., c = 1 and 0 < γ < 0.1 0.99 ). The superiority of our lower bound stems from a loose result in Lemma 3 in [34] . Denote ∆ t := w t -wt . It states that E A [∥∆ T ∥|∆ t0 ̸ = 0] ≥ 1 2n ( T t0 ) 0.99cγ , while this can be improved into E A [∥∆ T ∥|∆ t0 ̸ = 0] ≥ 1 2m ( T t0 ) 0.99cγ + ( T +1 t0+1 ) 0.99cγ ∆ t0 , which will lead to a sharper lower bound.Denote δ t := ∥w t -wt ∥. The proof leverages an intermediate result of Theorem 3.12 in [19] . Lemma E.6 ([19], Theorem 3.12). Assume ℓ(•; z) is L-Lipschitz and γ-smooth for all z ∈ Z.Running SGD with step sizes α t , for all S ≃ S ∈ Z m , we have the recurrence relation:∀1 ≤ t ≤ T, E A [δ t ] ≤ 1 - 1 m (1 + α t γ)E A [δ t-1 ] + 1 m E A [δ t-1 ] + 2α t L .Unwinding the recursion we have the stability upper bound. Theorem E.7 (Upper bound of single-level SGD in recursion form). Assume ℓ(•; z) is L-Lipschitz and γ-smooth for all z ∈ Z. In th case of Example E.1, running SGD with step sizes α t has uniform argument stability withϵ arg ≤ T t=1 T +1 s=t+1 1 + (1 -1/m)α s γ 2α t (γW + 1) m .Proof. As defined, ϵ arg = sup S≃ S∈Z m E A [δ T ] and. Unwinding the recursion in Lemma E.6 and using the fact that L ≤ γW + 1 in Proposition E.2, we get the result.Here we set an additional α T +1 = 0 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, we get ϵ arg ≍1+(1-1/m)αγ T m, showing an exploding rate w.r.t. T . When adopting linearly decreasing step sizes α t ≤ c/t, 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 ℓ(•; z) is L-Lipschitz and γ-smooth for all z ∈ Z. Running SGD for T steps with step sizes α t ≤ c/t has uniform argument stability ofϵ arg ≤ 2(γW + 1) (m -1)γ 1 + 1 -1/m γc T (1-1/m)cγ -1 .Omitting constant factors that depends on c, γ and W , we have ϵ arg ≲ T (1-1/m)cγ m .Proof. The proof follows the scaling for the upper bound in Theorem 5.5.Combining Theorem E.8 and Theorem E.5, we haveT ln(1+(1-1/m)cγ) m ≲ ϵ arg ≲ T (1-1/m)cγ m. Notably, the discrepancy between the lower and upper bounds is unavoidable, stemming from the scaling steps required to obtain an explicit order, and this gap becomes small when we have large m and small cγ. Concerning the lower and upper bounds in recursion form in Theorem E.5 and Theorem E.7, our results are tightly matched.Remark. Notice that Theorem 3.8 in [19] presents an upper bound of ϵ arg ≲ T γc γc+1 m , which is tighter than our result of ϵ arg ≲ T (1-1/m)γc m but with additional bounded loss assumption that ℓ(w; z) ∈ [0, 1]. Both results are based on the recurrence relation in Lemma E.6. They derive the upper bound with a hitting time t 0 and bound the loss divergence after t 0 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 as a fair and clear comparison with the lower bound.We acknowledge that the bounded loss assumption is commonly adopted for upper-bound analysis in theoretical works. Despite [19] , several following works also adopt this technique. [34] derive the upper bound of ϵ arg ≲ T γc m γc+1 in the nonconvex case with a similar approach by bounding the loss after hitting time t 0 , with an additional setting for t 0 = n. However, there appears to be a misuse of Lemma 4 in their proof of Theorem 5, which leads to their result being tighter compared to [19] in the case of T cγ cγ+1 ≤ m. Specifically, in the proof of Theorem 5, they decomposeE A [∥∆ T ] into two terms that E A [∥∆ T ] ≤ E A [∥∆ T ∥|∆ n = 0]P[∆ n = 0] + E A [∥∆ T ∥|∆ n ̸ = 0]P[∆ n ̸ = 0]to bound these two terms separately. For the second term, the union bound is used to getE A [∥∆ T ∥|∆ n ̸ = 0]P[∆ n ̸ = 0] ≤ 1 n n t=1 E A [∥∆ T ∥|H = t], where H = t denotes that t is the first time SGD pick the different entry in the twin datasets. E A [∥∆ T ∥|H = t] is further bounded using Lemma 4 thatE A [∥∆ T ∥|∆ t = 0] ≤ ( T t ) a 2L n to get E A [∥∆ T ∥|H = t] ≤ ( T t ) a 2Ln . While this appears to be a misuse as H = t can only imply ∆ t-1 = 0 and whether ∆ t = 0 remains uncertain, where Lemma 4 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 ϵ arg ≲ T m even with constant step sizes. A detailed comparison of existing results is listed in Table 2 . T (1-1/m)γc m (Ours)Lower bound --EQUATIONT 0.99cγ m 1+0.99cγ [34] F Details of simulationsThe implementing code is provided in the supplementary material. All simulations can be conducted on the CPU of a laptop.To examine the tightness and validity of the upper and lower bounds presented in Theorem 5. The comparison is shown in Fig. 2 . We plot the output hyperparameter distances with increasing T from 1000 to 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, to examine the linear trends of their relative magnitude.Here we implement additional simulations to examine the tightness between the recursive upper/lower bounds and deformed upper/lower bounds presented in Eq. ( 7) and Appendix B.6. Specifically, the recursive upper bound is calculated byT t=1 T s=t+1 1 + α s (1 -1/m)γ 2α t L ′ /m and the recursive lower bound is calculated by (7) . The deformed upper bound is calculated by T (1-1 m )cγ /m and the deformed lower bound is calculated by T ln(1+(1-1 m )cγ ′ ) /m. As for the coefficients: we set γ tr = 1 in Example 5.3. L ′ is calculated with (1 + ηγ tr ) K -1 /γ tr as in Eq. ( 10) and L is calculated with L = 0.1+1.1L ′ as they are of the same order of magnitude. γ = γ ′ is calculated with η K-1 k=0 (1 + ηγ tr ) k 2 + ηγ tr K-1 k=0 (1 + ηγ tr ) k as in Eq. (11) .T t=1 T s=t+1 1 + α s (1 -1/m)γ 2α t L/m in Eq.During the optimization, we fix η = 0.01, n = 100 and c = 0.01. For the simulation regarding T , we set K = 100 and m = 100 and plot the results of the recursive upper bounds for T from 1000 to 5000 in the horizontal axis with the corresponding other three bounds in the vertical axis, shown in Fig. 4 . 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 to 200 in the horizontal axis with the corresponding other three bounds in the vertical axis, shown in Fig. 5 . For the simulation regarding m, we set T = 1000 and K = 100 and plot the results of the recursive upper bounds for m from 100 to 2000 in the horizontal axis with the corresponding other three bounds in the vertical axis, shown in Fig. 6 .All curves exhibit linear trends, indicating these bounds are in the same order w.r.t. T , K, and m. In HO, the model is typically evaluated during the validation phase and is expected to generalize well on unseen test data based on its validation performance. Therefore, we focus on the impact of perturbations in the validation set in 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 an interesting topic for future work.Considering the similarities between average stability [32, Definition 2] and uniform stability, our techniques may be adapted to the data-dependent setting for average stability with some modifications. In this section, we present a 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 i denote a copy of S with the i-th element replaced by z ′ i , G S,t /G Si,t and w S,t /w Si,t denote the SGD update rules and the updated parameters optimized on S and S i at the step t. With a slight adjustment Section 4.2 and a similar proof as in the current paper, Theorem 5.1 can be modified as: Suppose there exists a nonzero vector v(S, S i ) along which G S,t and G Si,t are 2α t L ′ (S, S i )-divergent and L(•; z) is γ ′ t (S, S i )-expansive for all w S,t -w Si,t that parallel with v(S, S i ). Then we haveE A [δ t (S, S i )] ≥ [1 + α t (1 -1/m)]γ ′ t (S, S i )E A [δ t-1 (S, S i )] + 2α t L ′ (S, S i )/m. This recursion closely corresponds with the recursive upper bound in [32, Eq.(19) ]:E A [δ t (S, S i )] ≤ [1 + α t (1 -1/m)]ψ t (S, S i )E A [δ t-1 (S, S i )] + 2α t L(S, S i )/m,and the matching of γ ′ t & ψ t , 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. Specifically for average stability, a core challenge is calculating the expectation over S and S i 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 to clarify a possible approach to extend our framework.Assume that the data follows a distribution D that p(z) = 0.5 if z = (v 1 , 1), 0.5 if z = (-v 1 , 1). S i.i.d.and z ′ i ∼ 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 ) = ∥y i x i -y ′ i x ′ i ∥/2 and µ t (S, S i ) = 0 for zi = z ′ i , µ t (S, S i ) = |γ 1 | for z i ̸ = z ′i . This leads to the average argument stability lower bound:ϵ arg ≥ T t=1 T s=t+1 (1 + α s (1 -1/m|γ 1 |))α t /m.In this section, we discuss a possible approach to extend our framework on the analysis of generalization lower bounds. We first present a lemma clarifying the fundamental equivalence between generalization and stability. Then a lower bound on the expected hyperparameter divergence is established by slightly modifying Example 5.3 with additional design on the data distribution, which will imply the generalization lower bound under certain conditions. Proof. According to the definition of generalization error in Eq. ( 4) and the linearity of expectation,EQUATION.As it is assumed D val = D test and S val ′ i.i.d. sampled from D val independent from S val , term (a) can be rewritten as(a) = E A,S val ,S tr   1 m m i=1 E z val i ′ [L(A(S val , S tr ); z val i ′ )]   .Under the expectation, S val and Sval i is exchangeable, then term (b) can be rewritten as (b) = 1 m m i=1 E A, Sval i ,S tr L(A( Sval i , S tr ); z val i ′ ) = 1 m m i=1 E A,S val ,z val i ′ ,S tr L(A( Sval i , S tr ); z val i ′ ) .ϵ gen ≤ ϵ stab := sup S tr ,S val ,z val i ′ E A [L(A(S val , S tr ); z val i ′ ) -L(A( Sval i , S tr ); z val i ′ )],where ϵ stab is commonly upper bounded assuming L-Lipshcitz of the loss asϵ stab ≤ Lϵ arg := L sup S tr ,S val ≃ Sval E A [∥A(S val , S tr ) -A( Sval , S tr )∥].This paper attempts to derive lower bounds of ϵ arg which will not directly imply the generalization lower bounds because ϵ arg is fundamentally a distribution-agnostic upper bound for the generalization error. In order to obtain a generalization lower bound, a promising way is to extend Example 5.3 with additional assumption on the validation distribution rather than directly specifying S val and Sval .We present a primary result below for the lower bound of 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:ℓ val (λ, θ; z) = ℓ tr (λ, θ; z) = 1 2 θ ⊤ Aθ + λ ⊤ θ -yx ⊤ θ, where A ∈ R d×d is symmetric. Denote the eigenvalues of A as γ 1 ≤ • • • ≤ γ d . Let γ 1 < 0, γ d ≤ 0,and v 1 be a unit eigenvector for γ 1 . Suppose the validation distribution follows: EQUATIONT t=1 T s=t+1 1 + α s (1 -1/m)γ α t L ′ m ,whereL ≍ L ′ ≍ (1 + ηγ tr ) K , γ = γ ′ ≍ (1 + ηγ tr ) 2K .Proof. We first decompose ϵ gen,arg conditioned on the of z val i and z val i ′ as This result sheds light on the analysis of the generalization lower bound by establishing the lower bound on the expected hyperparameter divergence since it will induce a generalization lower bound if there exists a positive real constant L such that |ϵ gen | ≥ Lϵ gen,arg . One possible situation is that the designed compound validation loss satisfies for all z ∈ Z, |L(λ; z) -L(λ ′ ; z)| ≥ L∥λ -λ ′ ∥. As the generalization lower bound is beyond the main scope of this paper, further design and derivation may be left for future research.ϵ gen,arg = 1 m m i=1 P[z val i = z val i ′ ]E A,S tr ,S val ,z val i ′ [∥A(S val , S tr ); -A( Sval i , S tr )∥|z val i = z val i ′ ] + 1 m m i=1 P[z val i ̸ = z val i ′ ]E A,S tr ,S val ,z val i ′ [∥A(S val , S tr ) -A( Sval i , S tr )∥|z val i ̸ = z val i ′ ] = 1 m m i=1 P[z val i ̸ = z val i ′ ]E A,1. Claims Question: Do the main claims made in the and introduction accurately reflect the paper's contributions and scope? Answer: [Yes] Justification: Our claims accurately match our 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 in 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. • It is fine to include aspirational goals as motivation as long as it is clear that these goals are not attained by the paper.For formula neatness, we set an unused ηK+1 = 0 as a placeholder, and similarly αT +1 = 0 in Eq. (6).Namely, η k = η and αt ≤ c t , with a constant c > 0. The decreasing step size is also widely adopted in the optimization convergence analysis works, such as SGD[44,45], AdaGrad[46], Adam[47,48].4 Definition 3.1 considers perturbing the validation set instead of the training set. The relevant discussion is provided in Appendix G.1Namely, ∀w, w ′ ∈ Ω, ⟨∇ℓ(w) -∇ℓ(w ′ ), ww ′ ⟩ ≤ -µ∥w -w ′ ∥ 2 .We slightly abuse the notation in the subscript of the update rule as in Section 4.2, since the loss function in this contest can be solely distinguished by the selected sample. We use a similar simplification for the inner update rules in the next section.For instance, 1 + x ≤ e x is used in[19]. 


Decision: 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.

Reviews: review: paper_summary: paper_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.
strength_weakness: strength_weakness: 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.
questions: 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: limitations: No potential social impact.
paper_summary: paper_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.
strength_weakness: strength_weakness: - **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.
questions: questions: - **Q1**: Can the lower bound be extended to algorithms that use warm-starting strategy?
limitations: limitations: N/A
paper_summary: paper_summary: The paper provides new lower bounds for the uniform stability of UD-based and IFT-based algorithms in hyperparameter optimization.
strength_weakness: strength_weakness: 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.

2. 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.
questions: questions: 1. Are the bounds the authors present in theorems 5.6,5.7 tight?

When 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.

2. Does the technique of the paper can lead also to lower bounds for the average stability?
limitations: limitations: Yes.

Comments: title: Expanding our methods to generalization lower bounds
Potential misunderstanding regarding the tightness of our results
comment: Thanks for the helpful comments and for increasing the score. We are glad that we have addressed the reviewer's main concerns.
Thank you for the clarifications. I have updated my score.
We want to clarify that **our methods, specifically the constructed examples and the analysis framework, can inspire the establishment of generalization lower bounds.** As a result, **we present a preliminary generalization lower bound** for bilevel (UD and IFT-based) HO algorithms using Example 5.3 and for single-level SGD using Example E.1 with additional assumptions on the data distribution.

In particular for bilevel HO algorithms, further assume that the data follows a distribution $D$ where $p(z)=0.5$ for $z=(v_1, 1)$ and $(-v_1, 1)$ respectively, $S^{val}\overset{i.i.d.}{\sim} D^m$, ${z^{val}}'_ i \sim D$, and other conditions follow Example 5.3 in the paper. We derive $L'(S, S^{(i)})=\eta\Vert \sum_{k=1}^{K-1}(I-\eta A)^k(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)})=\gamma'$ (as in Lines 586-588) for $z_i\neq z_i'$. This leads to a generalization lower bound: $$\epsilon_ {gen}\geq\sum_ {t=1}^T\prod_ {s=t+1}^T(1+\alpha_ s(1-1/m\gamma'))\alpha_tL'/m,$$ where $L' \asymp L \asymp (1+\eta\gamma^{tr})^{K}$ and $\gamma' = \gamma \asymp (1+\eta\gamma^{tr})^{2K}$. When adopting decreasing step sizes, we further have: $$\epsilon_{gen}\gtrsim T^{\ln(1+(1-1/m))c\gamma'}/m.$$ More detailed illustrations and results for single-level SGD have been presented in the above response for Q2 from Reviewer 3C12.

We will add relevant discussions and detailed proofs in the final version.
Thank you for your response.

There might be a potential misunderstanding that: the recursive lower and upper bounds in Eq.(7) are indeed tight, and **for a constant step size** where $\alpha_t = c$ for all $t$ (which is commonly adopted in practice), Eq.(7) directly provides **tight** bounds: $\left[(1 + c(1 - 1/m)\gamma)^T - 1\right] \frac{2cL'}{m} \leq \epsilon_{\text{arg}} \leq \left[(1 + c(1 - 1/m)\gamma)^T - 1\right] \frac{2cL}{m}$. Therefore, we argue for the practical implications of our results.

In the submission, to align with the setting where $\alpha_t \leq \frac{c}{t}$ (which is widely discussed in theoretical works such as [17] and [18]), we present lower bounds in Theorems 5.6 and 5.7. 

We will add the discussion in the final version.
Thank you for the detailed response!

Although the reviewers addressed each of my questions individually, I want to highlight my main concern, which relates to the combined implications of all their answers. 

The technique used by the authors to bound uniform stability involves lower bounding the expansion of the algorithm. As the authors mentioned in their response, this approach has an inherent limitation due to the "unavoidable scaling steps needed to reveal an explicit order with respect to $T$." Consequently, unless the step sizes of the algorithm are $o\left(\frac{1}{t}\right)$ (which I believe are not typically used in practice), the lower bounds provided by the authors are not tight and exhibit a polynomial difference (with a constant degree) with respect to $T$ when compared to the best-known stability upper bounds. Together with the fact that a lower bound for uniform stability does not necessarily imply a lower bound for generalization, this weakens the significance of the results.