{"id":"59f1c284-9dcc-44a5-95d8-049573fc1c63","arxiv_id":"2411.16081","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":3,"one_line_summary":"AID-based bi-level optimization is uniformly stable with sample-dependent bounds comparable to single-level nonconvex SGD, and diminishing step sizes yield smaller generalization gaps than constant step sizes.","lead":"This paper proves uniform stability bounds for AID-based bi-level optimization, showing that small validation-set changes cause bounded changes in the learned solution. It combines these bounds with convergence rates to argue that diminishing step sizes generalize better than constant step sizes.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Theorem IV.11's convergence proof omits an O(K) variance term; with K=Theta(log T) that term is O(1), so the claimed convergence and the subsequent generalization trade-off are not established as written.","rationale":"The reader's verdict is CONDITIONAL, with the stated weakest assumption being that the MNIST/Fashion-MNIST experiments use nonconvex LeNet5 losses and therefore do not satisfy Assumption IV.2's strong convexity. That is a valid concern about the empirical corroboration, but it does not touch the validity of the theoretical stability theorem. The more load-bearing issue is in the convergence theorem: the proof of Theorem IV.11 explicitly bounds the variance of the hypergradient estimator by an O(K) quantity and then discards it when choosing K = Theta(log T). For diminishing step sizes eta_mt = alpha/t, the accumulated normalized variance is Theta(1), not o(1), so the displayed inequalities do not imply the stated O(1/log T) convergence. Since the paper's advertised generalization gap and the claimed superiority of diminishing over constant step sizes are obtained by combining stability with this convergence result, the central claim is not established as written. The concern is potentially repairable: a sharper variance analysis exploiting the contractive z-recursion may replace the O(K) bound with an O(1) bound, in which case Theorem IV.11 would follow. This is exactly the kind of issue a CONDITIONAL verdict should require the authors to fix. The reader's rationale already notes an 'unaccounted K-dependent variance term', but the reader's weakest_assumption field identifies a different concern, hence agreement is partial rather than full. I retain the CONDITIONAL verdict: the uniform-stability contribution appears novel and plausible, but the convergence bridge and the associated trade-off claims need a corrected proof or a revised theorem statement.","tokens_in":31720,"tokens_out":12468,"duration_ms":125444,"concrete_test":"Re-derive Lemma 16 using the contractive structure of the z-iteration instead of Cauchy-Schwarz: from z_k = (I - eta_z A_k) z_{k-1} + eta_z b_k, prove E||z_K - E z_K||^2 <= (1 - eta_z mu)^2 E||z_{K-1} - E z_{K-1}||^2 + C eta_z^2, giving an O(1) or O(eta_z) bound rather than O(K). Then substitute this corrected bound into the final display of Theorem IV.11 and check whether sum_t eta_mt^2 E||Delta_t - E Delta_t||^2 / sum_t eta_mt vanishes for eta_mt = alpha/t. If it vanishes, the theorem is repairable; if the O(K) bound is tight, Theorem IV.11 is false as stated and the generalization trade-off Corollaries IV.14 and IV.16 are unsupported.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central claim requires both uniform stability (Theorem IV.7 / Corollary IV.8) and convergence (Theorem IV.11) to translate stability into a generalization-gap statement. The proof of Theorem IV.11 contains a gap precisely at this bridge. Lemma 16 bounds the hypergradient-estimator variance as E||Delta_t - E Delta_t||^2 <= L0^2 + 2L1^2( K L1^2 Dz^2 + 2K eta_z^2 L1^2 L0^2 + 2K L0^2 )/mu^2 + 2Dz^2 L1^2, i.e. O(K). This term is carried into the final display of Theorem IV.11 as sum_t 2 eta_mt^2 times that bound. With eta_mt = alpha/t, we have sum_t eta_mt = Theta(log T) and sum_t eta_mt^2 = Theta(1). Therefore the normalized variance contribution is Theta(K)/Theta(log T) = Theta(1) when K = Theta(log T), not o(1). The proof then states 'when K is large (1 - eta_z)^{2K} will small' and drops this variance term, so the claimed rate min_t E||grad Phi(x_t)||^2 = O(1/log T) does not follow from the displayed inequalities. Consequently Corollaries IV.14 and IV.16, which combine convergence with stability to compare diminishing and constant step sizes, inherit the gap. The strong-convexity mismatch with the experiments is a separate concern; the missing variance control is more directly load-bearing because it affects whether any convergence-guaranteed generalization result is proven.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies the generalization behavior of AID-based bi-level optimization. It proves a uniform stability bound for Algorithm 1 under Lipschitz and strong-convexity assumptions, obtaining ε_stab = O(T^q/n) with q < 1 for diminishing step sizes. It then presents a convergence analysis for time-varying step sizes and combines stability with convergence to claim generalization-gap trade-offs, arguing that diminishing rates give a smaller gap than constant rates at the same optimization error. The paper includes experiments on a toy transfer-learning problem, MNIST data selection, and Fashion-MNIST data mixture.","tokens_in":32056,"tokens_out":12663,"duration_ms":113952,"significance":"If the main claims are established, the stability analysis is a valuable contribution: AID-based methods have previously been difficult to analyze because the coupled sequences (x, y, m, z) prevent a direct reduction to single-level optimization, and the paper's induction over four coupled sequences is nontrivial. Matching the O(T^q/n) sample order of ITD-based and single-level nonconvex SGD would be a noteworthy result. The paper also addresses a timely question, since generalization guarantees for AID-based bi-level methods are largely missing in the literature. The strengths are the formal stability framework and the explicit treatment of the momentum and inner-loop sequences; the main weakness, detailed below, is that the convergence proof contains an unhandled variance term that is load-bearing for the advertised rates.","major_comments":[{"comment":"Lemma 16 upper-bounds the variance E||Δ_t − EΔ_t||^2 by an O(K) expression. In the final display of the proof of Theorem IV.11, the term Σ_t 2η_mt^2 times this bound is present, and it is then dropped with the sentence \"when K is large (1 − η_z)^{2K} will small\". With η_mt = α/t and K = Θ(log T), we have Σ_t η_mt^2 = Θ(1), so the dropped term is Θ(K) = Θ(log T). After division by Σ_t η_mt = Θ(log T), it remains Θ(1), not o(1). The stated rate min_t E||∇Φ(x_t)||^2 = O(1/log T) therefore does not follow from the displayed inequalities, and Corollaries IV.14 and IV.16 inherit this gap. The proof needs either a sharper, summable variance bound, a different choice of K or step sizes that makes the term vanish, or an explicit revision of the claimed rate.","section":"Appendix B, proof of Theorem IV.11, Lemma 16"},{"comment":"The generalization error is decomposed into four terms, with term (II) identified as an optimization error. However, no bound is provided for term (II): the convergence theorem controls min_t E||∇Φ(x_t)||^2, which is a gradient-norm measure, and the corollaries translate this only into a statement about the stability bound log ε_stab. Since Φ is nonconvex, a small gradient norm does not imply a small function-value gap, so the gap between the empirical training error and the best-in-class error (term (II)) is not controlled. The claimed trade-off between \"optimization error\" and \"generalization gap\" is therefore not established for the total generalization error defined in Section III-B. The authors should either restrict their claims to the stability term (term (I)) or add an assumption such as a Polyak-Łojasiewicz condition that connects gradient norm to function suboptimality.","section":"Section III-B and Section IV-D, Corollaries IV.14 and IV.16"},{"comment":"The proof of Lemma 9 uses the condition μη_yt ≥ L1^2 η_yt^2 (equivalently η_yt ≤ μ/L1^2) to obtain the contraction (1 − μη_yt/2) for the y-sequence. This condition is not stated in Theorem IV.7 or Corollary IV.8, which only require η_z ≤ 1/L1. Without an explicit upper bound on η_yt, the coefficient (1 − μη_yt/2) may not be a contraction, and the O(T^q/n) stability bound is not proven as stated. The theorem and corollary should include the implied step-size restriction, or the proof should be revised to avoid this condition.","section":"Theorem IV.7 and Lemma 9 (Appendix A)"},{"comment":"The MNIST and Fashion-MNIST experiments train a LeNet5 network with cross-entropy loss as the lower-level problem. The lower-level objective is then neither strongly convex in the network parameters nor does it have uniformly Lipschitz second derivatives, so Assumption IV.2, which is used in the stability proof (Lemmas 7, 8, 9) and in the definition of the hypergradient, is not satisfied. The experiments therefore do not directly corroborate the theoretical results. They should be explicitly described as outside the scope of the theory, or the theory should be extended to non-strongly-convex lower-level problems.","section":"Sections V-B and V-C, Assumption IV.2"}],"minor_comments":[{"comment":"There are several typos: \"Initilize\" should be \"Initialize\" in Algorithm 1; \"Baot et al.\" should be \"Bao et al.\" in Section I; \"Hard et al.\" should be \"Hardt et al.\" in Section II; \"wih\" should be \"with\" in Assumption IV.1; \"vairable\" should be \"variable\" in Section IV; \"tunned\" should be \"tuned\" in Remark IV.6.","section":"Throughout"},{"comment":"The expression \"∥mt−1 + ˜mt−1∥\" appears twice and should read \"∥mt−1 − ˜mt−1∥\"; otherwise the induction is bounding a sum of two independent norms rather than the difference.","section":"Lemma 3 and proof of Theorem IV.7"},{"comment":"The theorem uses the quantity D2 without defining it. From the proof, the intended quantity appears to be Dz or possibly L2; the notation should be made consistent.","section":"Theorem IV.11"},{"comment":"In the final bound, the term \"2KL^2_0\" is missing its denominator \"/µ^2\" in the typeset formula; the displayed inequality is otherwise dimensionally inconsistent.","section":"Lemma 16"},{"comment":"The proof states that \"By taking the derivative, the function value is decreasing while T increases,\" but the derivative is not shown and T is discrete; a short monotonicity argument would make the step more transparent.","section":"Corollary IV.16"}],"recommendation":"major_revision","confidential_remarks":"The stability analysis is a genuine contribution and the paper fits the journal's scope. My main concern is that the advertised convergence rate in Theorem IV.11 is not established because the O(K) variance term is dropped without justification; since this term is Θ(1) after normalization under the paper's own step-size choices, the claimed O(1/log T) rate and the ensuing trade-off corollaries are unsupported. This appears fixable in principle with a tighter variance analysis or revised claims, so I recommend major revision rather than rejection. The strong-convexity mismatch with the deep-learning experiments should also be addressed honestly."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"The main novelty is real: the four-sequence stability analysis for AID-based bilevel optimization. Bao et al. covered ITD, Hardt et al. covered single-level SGD, and nobody had a stability bound for the AID structure where y_t depends on all previous x's. The coupling argument for x_t, y_t, m_t, z^K_t is a genuine contribution, and the O(T^q/n) stability bound in Corollary IV.8 looks plausible.\n\nBut the generalization claim rests on a bridge that does not hold as written. The stress-test is correct: Lemma 16 bounds the hypergradient-estimator variance by O(K). That term enters the final display of Theorem IV.11 multiplied by sum_t eta_mt^2, which is Theta(1) for eta_mt = alpha/t. With K = Theta(log T), the contribution is Theta(K)/Theta(log T) = Theta(1), not o(1). The sentence \"when K is large (1 - eta_z)^(2K) will small\" addresses the geometric term, not the O(K) variance. So the claimed O(1/log T) convergence rate does not follow from the displayed inequalities, and Corollaries IV.14 and IV.16 inherit the gap. This is the load-bearing flaw, not a typo.\n\nSeparately, the experiments on MNIST and Fashion-MNIST train LeNet5 under cross-entropy, which violates the mu-strong convexity of the lower-level problem in Assumption IV.2. The toy example satisfies the assumption; the real-data experiments don't. The authors say they show \"applicability in some nonconvex scenario,\" but the theory explicitly assumes strong convexity in y. That mismatch is worth flagging, though it's secondary to the convergence gap.\n\nThe paper would deserve a serious referee. The stability theorem is a first and may well be correct; the convergence proof can be repaired or the rates softened. The comparison between diminishing and constant step sizes should be re-examined or explicitly qualified. If I were handling it, I'd send it out, and the referee should focus on Appendix B and the K-dependence.","headline":"Real stability first for AID-based bilevel methods, but the convergence proof has an unaccounted O(K) variance term that breaks the advertised generalization trade-off.","tokens_in":32622,"tokens_out":2129,"would_cite":false,"duration_ms":19071,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["68T05","90C26"],"pacs":[],"model":"deepseek-v4-flash","headline":"The paper shows AID-based bi-level optimizers have the same uniform-stability order as single-level nonconvex SGD, with diminishing step sizes beating constant ones at matched optimization error.","keywords":["bi-level optimization","approximate implicit differentiation","uniform stability","generalization bounds","step-size schedule","nonconvex optimization","SGD with momentum"],"falsifier":"On any bi-level problem that satisfies the assumptions (the ridge-regression toy example in the paper qualifies), fix $T$, run Algorithm 1 once per validation set for two validation sets of size $n$ that differ in a single sample, and measure the expected output difference: the theorem predicts a gap of order $T^q/n$, so a gap that fails to shrink with $n$, or that grows faster than $T^q$ with iterations, refutes Theorem IV.7. A sharper probe is to shrink the strong-convexity parameter $\\mu$ toward zero, since $C_m$ and the exponent $q$ then blow up and the bound diverges: a problem in that regime where replacing one validation sample still moves the output by an $n$-independent amount would falsify the claim.","tokens_in":31504,"feed_emoji":"📉","tokens_out":12144,"duration_ms":100223,"temperature":0.7,"pith_summary":"Bi-level optimization trains a model and its hyperparameters together, but the standard approximate implicit differentiation (AID) family cannot be collapsed into a single-level problem, so its generalization behavior has been open. This paper establishes that AID-based methods are uniformly stable: replacing one validation sample changes their output by at most $O(T^q/n)$ with an exponent $q<1$ under diminishing step sizes, the same sample order as nonconvex single-level SGD and ITD-based bi-level methods. Combined with a new convergence analysis for time-varying step sizes, the paper derives a generalization gap at $\\epsilon$-accurate solutions and concludes that a diminishing learning rate beats a constant one at equal optimization error. The practical stakes are direct: memory-efficient implicit differentiation carries no theoretical generalization penalty, and decaying schedules are the safe choice for small validation sets, at the price of a slower $O(1/\\log T)$ convergence in the pure decaying regime.","feed_headline":"AID-based bi-level methods generalize like single-level SGD","feed_subtitle":"Diminishing step sizes shrink the validation-to-test gap as fast as classical nonconvex SGD does.","key_machinery":"The load-bearing object is a coupled-run stability recursion over the four iterate sequences of Algorithm 1 — the outer variable $x_t$, the inner variable $y_t$, the momentum $m_t$, and the inner-loop estimate $z^k_t$ — executed on two validation sets that differ in one sample. The key structural fact (Lemmas 8–11) is that the $z$-difference at step $t$ depends only on the previous $(x,y)$-difference and not on its own history, so the $z$-loop can be eliminated; the remaining differences then contract under a product of factors $1+\\eta_{xt}\\eta_{mt}C_m+\\eta_{mt}C_m+\\eta_{yt}L_1$, whose telescoping yields the $O(T^q/n)$ stability order. On the convergence side, two descent lemmas — one bounding $\\|y_t-y^*(x_t)\\|^2$ and one bounding the momentum/outer potential — telescope provided $\\eta_{mt}$, $\\eta_{mt}/\\eta_{xt}$, and $\\eta_{mt}/\\eta_{yt}$ are non-increasing, which is precisely the diminishing-step-size regime the stability analysis favors.","core_discovery":"The paper's central claim is that the uniform stability of AID-based bi-level optimization matches the classical nonconvex single-level benchmark despite the two-level structure. The obstruction is that in Algorithm 1 the inner variable $y_t$, the momentum $m_t$, and the implicit-gradient estimate $z^k_t$ all depend on the full past of the outer variable $x_t$, so a one-sample change in the validation set propagates through three coupled sequences. By tracking all of these differences between two runs, the paper proves $\\epsilon_{\\mathrm{stab}} = O(T^q/n)$ with $q=(2C_m\\alpha+L_1\\beta)/(2C_m\\alpha+L_1\\beta+1)<1$ for $\\eta_{xt}=\\eta_{mt}=\\alpha/t$ and $\\eta_{yt}=\\beta/t$ (Corollary IV.8), and it gives a convergence theorem for time-varying step sizes that yields $O(1/\\sqrt{T})$ accuracy for $\\Theta(1/\\sqrt{T})$ rates. Joining the two results, the paper shows that at a fixed optimization accuracy $\\epsilon$ the log-stability of the diminishing-rate schedule grows as $O(1/\\epsilon)$, while the constant-rate schedule can only reach an exponential level, and it concludes that the diminishing schedule attains a smaller generalization gap at the same optimization error.","pith_inferences":["An editorial extension: since the stability proof uses no convexity of the outer level and only the inner problem's strong convexity, the same $O(T^q/n)$ order should carry over to AID variants with conjugate-gradient or variance-reduced hypergradient estimation; the paper does not state this, but nothing in Lemmas 8–11 blocks it.","An editorial extension: the image-classification experiments violate the theorem's strong-convexity requirement on the inner problem, so the empirical agreement supports a conjecture the paper leaves implicit — that the stability order survives under a much weaker curvature condition, such as a gradient-dominance inequality.","An editorial extension: the theory suggests a concrete rule for hyperparameter tuning with small validation sets — use the fastest decaying schedule that still meets the optimization target, since the stability gap shrinks like $1/n$ while the iteration cost grows only as $T^q$ with $q<1$."],"forward_implications":["AID-based bi-level methods obtain a generalization gap of the same sample order ($O(T^q/n)$) as ITD-based methods and single-level nonconvex SGD, so the memory-efficient implicit-differentiation family carries no theoretical generalization penalty.","With $\\Theta(1/t)$ step sizes the stability bound is $O(T^q/n)$ with $q<1$, yielding $\\log \\epsilon_{\\mathrm{stab}} = O(1/\\epsilon)$ at $\\epsilon$-accuracy; with $\\Theta(1/\\sqrt{T})$ step sizes the convergence is $O(1/\\sqrt{T})$ while stability stays bounded, so both regimes are usable.","At the same optimization error, a diminishing learning rate produces a smaller generalization gap than a constant one across the schedules analyzed, making decaying step sizes the theoretically preferred choice for AID-based bi-level training.","For constant step sizes the achievable log-stability at $\\epsilon$-accuracy can only reach an exponential-in-$1/\\epsilon$ level as $T$ grows, so the diminishing schedule is strictly better in the regime where both attain the same error.","The convergence result holds for any monotone non-increasing schedule with $\\eta_{mt}/\\eta_{xt}$ and $\\eta_{mt}/\\eta_{yt}$ non-increasing and $K=\\Theta(\\log T)$ inner-loop steps, so the analysis covers whole families of schedules, not a single tuned configuration."],"supporting_citations":[{"why":"Supplies the ITD-based bi-level stability result and the stability-in-expectation definition whose sample order the paper's AID bound must match.","marker":"[1]"},{"why":"Gives the implicit-function-theorem gradient formula (Proposition III.1) that defines the AID hypergradient and the standard bi-level assumptions the analysis builds on.","marker":"[23]"},{"why":"Establishes the coupled-run stability framework and the nonconvex single-level SGD bound ($O(T^k/n)$) that the paper adapts and compares itself against.","marker":"[36]"},{"why":"Provides the constant-learning-rate convergence result for AID-style bi-level methods that Theorem IV.11 extends to time-varying step sizes.","marker":"[33]"},{"why":"Supports the claim that the inner-loop estimate z needs less accuracy than x and y, justifying the $K = \\Theta(\\log T)$ choice and the omission of warm-up.","marker":"[45]"}],"fun_headline_variants":["AID bi-level optimization matches SGD generalization bounds","Diminishing steps give AID methods SGD-class stability","Bi-level AID: uniform stability on par with nonconvex SGD","AID-based bi-level methods proven as stable as SGD"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The inner-level function $g(x,\\cdot,\\zeta)$ must be $\\mu$-strongly convex in $y$ with Lipschitz gradients and Lipschitz second derivatives, so that the optimal-response map $y^*(x)$ is Lipschitz and the implicit-gradient estimate stays bounded; the image-classification experiments in the paper do not satisfy this curvature condition.","fun_headline_variants_meta":{"raw":{"variants":["AID bi-level optimization matches SGD generalization bounds","Diminishing steps give AID methods SGD-class stability","Bi-level AID: uniform stability on par with nonconvex SGD","AID-based bi-level methods proven as stable as SGD"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000365,"raw_usage":{"total_tokens":1996,"prompt_tokens":1010,"completion_tokens":986,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":626,"completion_tokens_details":{"reasoning_tokens":918}},"tokens_in":626,"tokens_out":986,"duration_ms":9109,"temperature":1.0,"reasoning_tokens":918,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-12T13:33:30.769694+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"On any bi-level problem that satisfies the assumptions (the ridge-regression toy example in the paper qualifies), fix $T$, run Algorithm 1 once per validation set for two validation sets of size $n$ that differ in a single sample, and measure the expected output difference: the theorem predicts a gap of order $T^q/n$, so a gap that fails to shrink with $n$, or that grows faster than $T^q$ with iterations, refutes Theorem IV.7. A sharper probe is to shrink the strong-convexity parameter $\\mu$ toward zero, since $C_m$ and the exponent $q$ then blow up and the bound diverges: a problem in that regime where replacing one validation sample still moves the output by an $n$-independent amount would falsify the claim.","supporting_citations":[{"cited_title":"Stability and generalization of bilevel programming in hyperpa- rameter optimization,","cited_arxiv_id":null,"evidence_quote":"Supplies the ITD-based bi-level stability result and the stability-in-expectation definition whose sample order the paper's AID bound must match."},{"cited_title":"Train faster, gener- alize better: Stability of stochastic gradient descent,","cited_arxiv_id":null,"evidence_quote":"Establishes the coupled-run stability framework and the nonconvex single-level SGD bound ($O(T^k/n)$) that the paper adapts and compares itself against."},{"cited_title":"Decentralized Stochastic Bilevel Optimization with Improved per-Iteration Complexity","cited_arxiv_id":"2210.12839","evidence_quote":"Provides the constant-learning-rate convergence result for AID-style bi-level methods that Theorem IV.11 extends to time-varying step sizes."},{"cited_title":"Will Bilevel Optimizers Benefit from Loops","cited_arxiv_id":"2205.14224","evidence_quote":"Supports the claim that the inner-loop estimate z needs less accuracy than x and y, justifying the $K = \\Theta(\\log T)$ choice and the omission of warm-up."}],"review_version":1}