{"id":"0a0dd92d-3cfb-42e2-850b-a7c6653db4a0","arxiv_id":"2412.06436","paper_version":3,"verdict":"CONDITIONAL","confidence":"HIGH","novelty_score":5.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":5,"one_line_summary":"A computable a-posteriori bound on the inexact piggyback hypergradient enables adaptive tolerance and step-size control for bilevel learning of convex regularizers.","lead":"A new bilevel learning scheme computes approximate hypergradients for the piggyback method with fully computable error bounds, and adaptively chooses inner-solver tolerances and step sizes. It is demonstrated on learning total variation discretizations and input-convex neural network regularizers for CT reconstruction.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Theorem 2's bound (17) appears to omit two positive cross terms, so the advertised a-posteriori inequality does not follow from the proof as written.","rationale":"The reader's weakest assumption concerned the violation of strong convexity and C^{2,1} regularity in the TV experiment. That is a legitimate applicability concern, but it does not attack the internal validity of Theorem 2 under the stated assumptions. My check of the proof found a different and more direct problem: the final assembly of (17) appears to drop two positive cross terms, C_X^1 ϵx ϵy and C_Y^2 ϵx ϵy, during the expansion after substituting (14)–(15). If this is correct, the theorem as stated is not proved, and the central a-posteriori certificate is not yet established even in the smooth, strongly convex regime. The issue is concrete and checkable by symbolic expansion; it does not require new experiments or assumptions. Because the error is localized and likely fixable by adding the missing terms to (17), the appropriate disposition remains conditional revision rather than outright rejection, matching the reader's CONDITIONAL verdict. I therefore leave the verdict unchanged while flagging that the specific supporting inequality needs correction.","tokens_in":19243,"tokens_out":14889,"duration_ms":139230,"concrete_test":"Independently re-derive (17) by expanding (∥y˜∥+ϵy)(C_X^1 ϵx + C_X^2 ϵy + δX) + (∥x˜∥+ϵx)(C_Y^1 ϵx + C_Y^2 ϵy + δY) + ϵy∥X˜∥ + ϵx∥Y˜∥ and compare term-by-term with the printed (17). If the expansion contains C_X^1 ϵx ϵy + C_Y^2 ϵx ϵy beyond the printed terms, the theorem statement is missing positive terms; alternatively, exhibit constants C_X^1, C_Y^2, and values ϵx, ϵy for which the right-hand side of (17) is strictly smaller than this expansion, disproving the claimed inequality.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central claim is Theorem 2: a fully computable a-posteriori bound for the inexact hypergradient. The last step of the proof assembles (17) from the four-term triangle bound ∥z−∇L∥ ≤ ∥y˜∥∥ΔX∥ + ϵy∥X̂∥ + ∥x˜∥∥ΔY∥ + ϵx∥Ŷ∥, where ΔX = X˜−X̂ and ΔY = Y˜−Ŷ, by replacing ∥X̂∥ with ∥X˜∥+∥ΔX∥ and ∥Ŷ∥ with ∥Y˜∥+∥ΔY∥ and then substituting (14)–(15). Expanding (∥y˜∥+ϵy)(C_X^1 ϵx + C_X^2 ϵy + δX) + (∥x˜∥+ϵx)(C_Y^1 ϵx + C_Y^2 ϵy + δY) + ϵy∥X˜∥ + ϵx∥Y˜∥ yields, in addition to every term printed in (17), the positive cross terms C_X^1 ϵx ϵy + C_Y^2 ϵx ϵy. These are not bounded by the printed C_Y^1(ϵx)^2 + C_X^2(ϵy)^2 terms in general; for large C_X^1 or C_Y^2 and comparable ϵx, ϵy they dominate. Therefore (17), as stated, does not follow from the preceding inequalities. Since (17) is the advertised certificate enabling adaptive tolerances, the central claim is not yet established as written; the bound needs the additional cross terms or a separate argument bounding them.","agreement_with_reader":"disagree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies bilevel optimization for learning linear operators in variational image reconstruction, where the lower-level problem is a convex saddle-point problem and the hypergradient is computed by a piggyback primal-dual differentiation scheme. The main theoretical contribution is an a-posteriori error bound (Theorem 2) for the inexactly computed hypergradient, expressed in terms of residuals, tolerances, and known constants, together with a transfer of the adaptive inexact descent framework of [39] to this setting (Theorem 3). The paper also reports experiments on learning total-variation discretizations and on training fields-of-experts and input-convex neural-network regularizers.","tokens_in":19512,"tokens_out":9553,"duration_ms":94942,"significance":"If Theorem 2 is correct, the paper fills a genuine gap: it provides a fully computable certificate for the accuracy of a piggyback-computed hypergradient, enabling principled tolerance control and adaptive step sizes in bilevel learning. The constants in (18) are explicit, the bound depends only on computable residuals and problem parameters, and the convergence result is imported from [39] rather than re-derived. The numerical results for the ICNN regularizer are encouraging: Table 1 reports 31.43 dB PSNR for the bilevel-trained ICNN versus 29.32 dB for ACR with the identical architecture. The main qualifications are that Eq. (17) must be corrected and that the experiments must either satisfy or explicitly disclaim the paper's regularity assumptions.","major_comments":[{"comment":"The final inequality (17) does not follow from the proof as written. Substituting (25)–(26) into the four-term triangle bound, together with ∥ˆX∥≤∥˜X∥+∥ΔX∥ and ∥ˆY∥≤∥˜Y∥+∥ΔY∥, yields, in addition to every term printed in (17), the cross terms C_X^1 ϵx ϵy + C_Y^2 ϵx ϵy. These terms are positive and are not bounded by the printed terms C_Y^1 (ϵx)^2 + C_X^2 (ϵy)^2 in general, because C_X^1 and C_Y^2 are independent constants that can dominate. The bound can be repaired by adding (C_X^1+C_Y^2)ϵx ϵy to the right-hand side; this preserves the a-posteriori and fully computable character, so the issue is correctable, but the central certificate as stated is not yet established.","section":"§3.1, Theorem 2, Eq. (17)"},{"comment":"The total-variation experiment is performed on the non-smooth problem (30), and the authors explicitly acknowledge that 'the non-smooth term does not fully satisfy the regularity assumptions imposed on g'. Since Lemma 3, Theorem 2, and the convergence transfer from [39] all require Assumptions 1 and 3 (strong convexity and local C^{2,1} regularity of the relevant functions), the results in Figures 1–3 do not provide an empirical check of the proved bound. The paper should either smooth the regularizer, for example with a Huber-type approximation, and rerun, or state clearly that this experiment is a heuristic illustration outside the theorem's hypotheses.","section":"§4.1, Eq. (30) and surrounding text"},{"comment":"It is not clear that the ICNN lower-level problem satisfies Assumption 1. The term µg/2∥x∥² is quadratic only in x; the objective also contains δ_C(Vx,z) and γψ_w(Wz), and ψ_w has a linear tail for arguments larger than w. Thus there is no evident strong convexity in the joint variable (x,z), and the statement 'to ensure strong convexity of the primal function g' appears to require an additional argument or an additional quadratic penalty in z. As a consequence, the ICNN experiments, like the TV experiments, are outside the proved assumptions unless a joint strong-convexity argument is supplied.","section":"§4.2, Eq. (33)"}],"minor_comments":[{"comment":"The notation 'δ2(Y,˜x.˜y)' contains a period instead of a comma; it should read 'δ2(Y,˜x,˜y)'.","section":"§3.1, Eq. (10b)"},{"comment":"The expression '∥∇1(ˆx)−∇1(˜x)∥' should read '∥∇ℓ1(ˆx)−∇ℓ1(˜x)∥'.","section":"§3.1, Remark 3"},{"comment":"The stopping criterion for solving (ASI) should reference Lemma 3, i.e., Eq. (10) and the conditions (13), rather than (14)–(15), since (14)–(15) bound the distance to (ˆX,ˆY), not directly the residual to (¯X,¯Y).","section":"§3.1, Algorithm 2, line 5"},{"comment":"The statement of Theorem 3 should list the hypotheses needed from [39, Theorem 3.19]; in particular, Lemma 5 assumes that the upper-level loss ℓ is convex, but the theorem statement only mentions Assumptions 2 and 3.","section":"§3.2, Theorem 3"}],"recommendation":"major_revision","confidential_remarks":"The cross-term omission in Eq. (17) is a local algebraic error and can be fixed without changing the method, but it is load-bearing because the paper's advertised contribution is precisely the computable a-posteriori certificate. The assumption violations in the numerical experiments should be addressed by rephrasing the claims or by smoothing the regularizers. There are no concerns about attribution or overlap with [28,39] beyond what the authors state."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Short version: the paper's advertised a-posteriori bound for inexact piggyback hypergradients is a real contribution, but the proof of Theorem 2 as printed does not establish (17). The stress-test note is right: after substituting the triangle bounds, you pick up the cross terms C_X^1 ϵx ϵy + C_Y^2 ϵx ϵy, which are missing from the printed bound. Since (17) is the certificate that drives the adaptive tolerances, this is load-bearing. The good news is it is also easily repairable: add those two terms to the right-hand side, and the bound remains fully computable and the rest of the framework goes through. So the correct verdict is 'promising but needs a revision,' not 'wrong idea.'\n\nWhat is actually new: an a-posteriori, computable error bound for the hypergradient computed via primal-dual style differentiation, extending [39] to this setting. Lemmas 3 and 4 are fine under the stated assumptions, and the adaptive backtracking routine is a reasonable way to turn the bound into step-size and tolerance control. The writing is clear and the attribution to [39] is honest: Theorem 3 is explicitly inherited, and the paper does not oversell it.\n\nThe softer spots are real but not fatal. The TV experiment violates the strong convexity and C^{2,1} assumptions, and the authors admit it; for a paper whose selling point is rigorous control, that is a gap between theory and demonstration. The experimental validation is narrow: one test image for CT, no error bars, no released code. That matters less for the math but limits the empirical claim. The convergence guarantee is a black-box import from the authors' earlier work, so the independent contribution is the bound, not the convergence theorem.\n\nIf I were the editor I would send this to peer review, but with the expectation of major revision. The referee should ask for the corrected bound, a discussion of whether the missing terms can be bounded or must be included, and stronger experiments (multiple images, error bars, or code). The paper deserves a serious referee because the underlying idea is likely correct and useful even if this version of the proof has a gap.","headline":"Genuinely useful a-posteriori bound for inexact piggyback hypergradients, but Theorem 2's proof is missing two positive cross terms; repairable, but the current version should not be accepted as-is.","tokens_in":20177,"tokens_out":3252,"would_cite":false,"duration_ms":28309,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["90C30","90C26","65K10","68T07"],"pacs":[],"model":"deepseek-v4-flash","headline":"This paper derives a fully computable a-posteriori error bound for the approximate hypergradient computed by primal-dual style differentiation, and an adaptive method that uses it to set tolerances and step sizes.","keywords":["bilevel optimization","hypergradient","a-posteriori error bound","primal-dual method","piggyback differentiation","adaptive step-size","input-convex neural network","total variation"],"falsifier":"Take a finite-dimensional quadratic lower-level problem where the saddle point and hypergradient have closed forms, compute the bound (17) with the true constants at several tolerance combinations, and verify it holds; a single violation would refute the theorem. Alternatively, on the ICNN-CT setup, compute the bound's right-hand side at the final iterate and compare with the actual gradient error estimated by a high-accuracy solve.","tokens_in":18947,"feed_emoji":"🧮","tokens_out":5276,"duration_ms":50972,"temperature":0.7,"pith_summary":"The paper establishes a computable a-posteriori error bound for the hypergradient obtained by primal-dual style (piggyback) differentiation when the lower-level problem is solved only inexactly. It shows that the error of the approximate hypergradient can be controlled by residual-based terms involving the primal-dual residuals, tolerances for the lower-level and adjoint problems, and constants like strong convexity and Hessian Lipschitz constants. It then integrates this bound into an adaptive backtracking line-search method that dynamically adjusts tolerances and step sizes, proving convergence of the upper-level iterates. Experiments on learning TV discretizations and training input-convex neural networks for CT reconstruction support the approach.","feed_headline":"New error bound certifies inexact hypergradients in bilevel learning","feed_subtitle":"A fully computable a-posteriori estimate sets tolerances and step sizes adaptively, with a convergence guarantee.","key_machinery":"The machinery is the inexact piggyback method: the lower-level saddle-point problem (S) and its adjoint problem (ASI) are solved inexactly with PDHG, and the hypergradient is formed as z = ỹ ⊗ X̃ + Ȳ ⊗ x̃. The error analysis rests on Lemma 3, which gives residual-to-distance bounds for the adjoint problem using strong convexity, and Lemma 4, which establishes Lipschitz continuity of ∇²g with constant L_{∇²g*}(L_{∇g})³. Theorem 2 combines these to produce the fully computable bound (17), which is then used in the adaptive backtracking line search from the companion framework MAID to choose tolerances and step sizes.","core_discovery":"The central discovery is Theorem 2: if the lower-level saddle-point solution is approximated within tolerances εx and εy, and the adjoint system is solved within residual-based tolerances δX and δY, then the approximate hypergradient z = ỹ ⊗ X̃ + Ȳ ⊗ x̃ satisfies an explicit bound, inequality (17), in terms of those tolerances and problem constants. The bound is a-posteriori and fully computable: it uses only residuals, tolerances, and known constants such as the strong convexity parameters and Lipschitz constants of gradients and Hessians, so it can serve as a stopping criterion. This gives, for primal-dual style bilevel differentiation, a principled way to choose how accurately the lower-level and adjoint problems must be solved to make progress in the upper-level optimization.","pith_inferences":["A practical extension the paper leaves implicit: the bound (17) can serve as a per-iteration stopping criterion, so one could run the lower-level solver with loose tolerances early in training and tighten them only when the line-search condition fails, further reducing total cost.","The bound requires knowing or upper-bounding constants such as L_{∇²g*} and L_{∇²f}; in applications these are rarely known, so a usable implementation must estimate them, and the effectiveness of the adaptive method depends on those estimates being conservative enough.","The TV experiment violates the smoothness assumptions yet works well, suggesting the error bound and convergence theory may extend to non-smooth regularizers under weaker conditions; a direct test on a non-smooth problem with a known hypergradient would clarify whether the residual terms still control the error.","The convergence guarantee holds for deterministic upper-level optimization; combining the a-posteriori error control with variance-reduced or stochastic hypergradient estimates could make the method scalable to large data sets, a direction the paper lists as future work."],"forward_implications":["The error bound enables adaptive stopping rules: tolerances for the lower-level and adjoint solves can be set from residuals, reducing computational cost while keeping the hypergradient accurate enough for descent.","The adaptive method, Algorithm 3 with the inexact sufficient-decrease condition of Lemma 5, guarantees convergence of the upper-level iterates: lim_{t→∞} ||∇L(K_t)|| = 0 under the stated assumptions.","In learning the discretization of total variation, the adaptive choice of step size yields smoother decrease of the upper-level loss and better reconstructions than fixed-step, fixed-tolerance piggyback, especially under a limited computational budget.","When training input-convex neural network regularizers for sparse-view CT, the bilevel-learned ICNN outperforms the adversarially trained ICNN with the same architecture, while the simpler Fields of Experts regularizer also gives strong results.","The framework is stated to extend directly to other linear inverse problems with data-driven, potentially non-smooth regularizers."],"supporting_citations":[{"why":"Supplies the piggyback-style differentiation algorithm and the linear convergence result for the exact hypergradient that this paper extends to the inexact, adaptive setting.","marker":"[28]"},{"why":"Provides the adaptive backtracking line-search scheme (MAID), including Lemma 5 and Theorem 3, which the paper uses to turn its error bound into an adaptive bilevel method with a convergence guarantee.","marker":"[39]"},{"why":"The PDHG algorithm used to solve both the primal and adjoint saddle-point problems, defining the iterates and step-size conditions on which the error analysis depends.","marker":"[42]"},{"why":"Gives the Fenchel duality relation between strong convexity and Lipschitz continuous gradients, used in Lemma 4 and Theorem 2 to bound Hessian differences.","marker":"[43]"},{"why":"Supplies the strong-convexity optimality-gap bound (Lemma 1), the basis for the residual-to-distance estimates in Lemmas 2 and 3.","marker":"[45]"},{"why":"Introduces the learning-consistent-discretization framework for total variation that Section 4.1 uses as the TV learning experiment.","marker":"[29]"},{"why":"Defines the learned convex regularizer (ICNN/ACR) architecture and adversarial training baseline that Section 4.2 compares against in CT reconstruction.","marker":"[12]"}],"fun_headline_variants":["Error bound certifies inexact gradients in bilevel learning","A-posteriori bound set tolerances for bilevel optimization","Adaptive step-size for bilevel learning with inexact gradients","Computable error estimate for primal-dual bilevel differentiation","New stopping criterion for bilevel learning via piggyback"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The lower-level functions must be strongly convex with locally $C^{{2,1}}$ conjugates (Assumptions 1 and 3), and the smoothing-free TV experiment violates these, so the error bound and convergence result do not strictly apply there.","fun_headline_variants_meta":{"raw":{"variants":["Error bound certifies inexact gradients in bilevel learning","A-posteriori bound set tolerances for bilevel optimization","Adaptive step-size for bilevel learning with inexact gradients","Computable error estimate for primal-dual bilevel differentiation","New stopping criterion for bilevel learning via piggyback"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000116,"raw_usage":{"total_tokens":1043,"prompt_tokens":879,"completion_tokens":164,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":495,"completion_tokens_details":{"reasoning_tokens":81}},"tokens_in":495,"tokens_out":164,"duration_ms":2313,"temperature":1.0,"reasoning_tokens":81,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-11T19:38:42.533222+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Take a finite-dimensional quadratic lower-level problem where the saddle point and hypergradient have closed forms, compute the bound (17) with the true constants at several tolerance combinations, and verify it holds; a single violation would refute the theorem. Alternatively, on the ICNN-CT setup, compute the bound's right-hand side at the final iterate and compare with the actual gradient error estimated by a high-accuracy solve.","supporting_citations":[{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Supplies the piggyback-style differentiation algorithm and the linear convergence result for the exact hypergradient that this paper extends to the inexact, adaptive setting."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Provides the adaptive backtracking line-search scheme (MAID), including Lemma 5 and Theorem 3, which the paper uses to turn its error bound into an adaptive bilevel method with a convergence guarantee."},{"cited_title":"Journal of math- ematical imaging and vision40, 120–145 (2011)","cited_arxiv_id":null,"evidence_quote":"The PDHG algorithm used to solve both the primal and adjoint saddle-point problems, defining the iterates and step-size conditions on which the error analysis depends."},{"cited_title":"Journal of mathematical imaging and vision63(5), 580–600 (2021)","cited_arxiv_id":null,"evidence_quote":"Supplies the strong-convexity optimality-gap bound (Lemma 1), the basis for the residual-to-distance estimates in Lemmas 2 and 3."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Introduces the learning-consistent-discretization framework for total variation that Section 4.1 uses as the TV learning experiment."}],"review_version":1}