{"id":"57b8bf47-8eb4-4ab8-b5b2-8da2bd18d6ab","arxiv_id":"2505.06805","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":4,"one_line_summary":"The TSG method is the first stochastic gradient algorithm for trilevel optimization, with a convergence rate of O(J/√I) under strong-convexity assumptions on the two lower levels.","lead":"This paper presents a stochastic gradient descent method for trilevel optimization problems, which involve three nested optimization levels, together with a convergence analysis. It targets machine learning tasks such as hyperparameter tuning combined with adversarial training, where such hierarchical formulations arise.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Assumption 3.6, on which Theorem 3.1 rests, is not satisfied by the practical TSG-AD/TSG-N-FD estimators as implemented; fixed Neumann truncation or FD/CG settings leave inverse-Hessian bias independent of the required O(theta) rate.","rationale":"The reader's weakest_assumption identifies exactly the gap that is most load-bearing for the paper's central claim. The theorem is internally coherent as a conditional statement: if estimators satisfying Assumption 3.6 exist and are used in Algorithm 3, the proof plausibly yields the stated O(J/sqrt(I)) rate. But the two practical algorithms presented as the paper's main implementations, TSG-N-FD and TSG-AD, are not shown to satisfy Assumption 3.6, and in the form described they do not: fixed Neumann truncation, fixed FD step, and fixed CG tolerances produce inverse-Hessian bias that is constant in theta. Thus the advertised convergence theory does not cover the methods whose numerical performance is reported. This does not invalidate the theorem or the synthetic demonstrations of the abstract algorithm, but it materially narrows the contribution and supports the existing CONDITIONAL verdict. I did not choose the strong-convexity violation in the quartic experiments as the primary concern because the theorem's assumptions are stated explicitly and the limitations paragraph acknowledges them; the Assumption 3.6 gap is more directly connected to the core convergence claim and is not acknowledged in the limitations. The novelty dispute with existing federated trilevel works is a scope claim, not a correctness risk, so it is secondary. A targeted bias measurement or analytic tail-norm computation would settle whether Assumption 3.6 can be satisfied by the practical estimators, and therefore whether the current manuscript should move from conditional to a more definite position.","tokens_in":59049,"tokens_out":8353,"duration_ms":85261,"concrete_test":"Fix a small quadratic TLO instance with a computable B = nabla^2_yy fbar and run TSG-AD with the paper's fixed truncation Q, and TSG-N-FD with epsilon = 0.1 and its default CG stopping rule, under the Theorem 3.1 step sizes for increasing I, J, K. Measure ||B^{-1} - E[ Bhat^{-1} ]|| at a fixed point for theta = 1/(I^{3/2} J sqrt(K)) spanning several orders of magnitude. If the bias does not decrease proportionally to theta and instead saturates at a value independent of theta, Assumption 3.6 is violated for the practical estimators. Equivalently, an analytical check settles it directly: for fixed Q, ||B^{-1} - sum_{h=0}^Q (I-B)^h B^{-1}|| = ||(I-B)^{Q+1} B^{-1}|| is a constant depending only on B, so no choice of alpha, beta, gamma makes it O(theta) unless Q is iterated to infinity.","verdict_should_be":"UNCHANGED","load_bearing_attack":"Assumption 3.6 requires the estimators [nabla^2_zz f3^xi]^{-1} and [nabla^2_yy fbar^xi]^{-1} to have bias O(theta), with theta = alpha*beta*gamma. Theorem 3.1's O(J/sqrt(I)) guarantee is proved under this assumption, and the bias lemmas (D.1, D.3, D.5) all inherit it. The paper's practical methods do not provide such estimators. TSG-AD approximates inverse Hessians by a truncated Neumann series with a fixed accuracy level Q (Appendix F.3, eqs. F.9 and F.11); for fixed Q the truncation error is ||(I-B)^{Q+1} B^{-1}||, a constant independent of theta, so it cannot be O(theta) along the theorem's schedule unless Q grows unboundedly with I, J, K, which Algorithm 7 does not specify. TSG-N-FD solves adjoint systems by CG with finite-difference Hessian-vector products and a fixed epsilon = 0.1 (Appendix F.2, eq. F.5); neither the CG stopping tolerance nor the FD error is tied to theta, so the implied inverse-Hessian bias is not O(theta). Consequently the convergence theorem covers neither of the algorithms whose performance is reported. The paper's cited mechanisms for satisfying Assumption 3.6, truncated Neumann series and increasing sample sizes, are not instantiated: no Q, no CG tolerance, and no sample-size schedule is shown to drive the bias at rate theta. This is not an objection to the internal logic of Theorem 3.1, but to the claimed scope: the advertised convergence guarantee does not transfer to the implemented TSG variants.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper proposes TSG, a stochastic gradient method for unconstrained trilevel optimization, together with a convergence analysis. The algorithm updates the lower-level variables by stochastic gradient steps, the middle-level variables by an inexact bilevel stochastic gradient, and the upper-level variables by a noisy trilevel adjoint gradient. The main result, Theorem 3.1, states that under Assumptions 3.1–3.6 and with step sizes α_i=1/√I, β_i=(1/√J)α_i, γ_i=(1/(√J√K))α_i, the average squared gradient norm satisfies (1/I)ΣE[‖∇f(x_i)‖²]=O(J/√I), provided the iteration counts obey ς≤J, ϖ≤I, and Ξ(I,J)=O(J³I)≤K. The paper also presents two practical implementations, TSG-N-FD and TSG-AD, and reports numerical experiments on synthetic trilevel problems and on a trilevel adversarial hyperparameter tuning formulation.","tokens_in":59411,"tokens_out":4359,"duration_ms":45064,"significance":"If correct, Theorem 3.1 would provide the first convergence guarantee for a stochastic trilevel optimization method, extending the bilevel stochastic approximation framework. The main proof is detailed and appears internally consistent under the stated assumptions, and the paper supplies reproducible code. However, the advertised scope is currently wider than what the theorem actually covers: the practical algorithms used in the experiments are not shown to satisfy Assumption 3.6, and one of the synthetic test problems violates the strong convexity assumption. The result is therefore significant but needs substantial tightening before the main claims are fully supported.","major_comments":[{"comment":"Assumption 3.6 requires the inverted stochastic Hessian estimators [∇²_zz f_3^ξ]^{-1} and [∇²_yy f̄^ξ]^{-1} to have bias of order O(θ), with θ=αβγ. This assumption is load-bearing for Theorem 3.1, since Lemmas D.1, D.3, and D.5 all inherit it. However, the two implemented methods do not provide such estimators. TSG-AD approximates the inverse Hessians by a truncated Neumann series with a fixed accuracy level Q (Algorithms 5–6 and equations F.9, F.11); for fixed Q the truncation error is a constant independent of θ, and no schedule forcing Q to grow with I,J,K is specified. TSG-N-FD solves adjoint systems by CG with finite-difference Hessian-vector products and a fixed epsilon=0.1 (equation F.5), and neither the CG stopping tolerance nor the FD error is tied to θ. Consequently Theorem 3.1 does not cover the algorithms whose numerical performance is reported. The authors should either verify Assumption 3.6 for these implementations with explicit accuracy schedules, or state and prove a convergence theorem for the actually implemented estimators.","section":"Assumption 3.6, Appendix F.2–F.3"},{"comment":"Remark 3.1 claims a stronger O(1/√I) rate under more problem-dependent step sizes, referring to Theorem B.2.5 in the PhD thesis [26], which is listed as 'in preparation'. This result is advertised as part of the paper's convergence theory, but no proof is included or available for verification. Either provide the proof in the appendix or clearly mark the O(1/√I) rate as a conjecture/result to appear elsewhere.","section":"Section 3.2, Remark 3.1"},{"comment":"Propositions E.1 and E.2 state Lipschitz continuity properties of z(x,y), y(x), ∇_y f̄, ∇²_xy f̄, ∇²_yy f̄, ∇f, and related Jacobians, but the proofs are deferred to Appendix B.5 of the PhD thesis [26]. These properties are used throughout the proof of Theorem 3.1 (e.g., equations E.1–E.13 in Lemmas B.2–B.4 and in the main proof). Since [26] is an in-preparation self-citation, the current manuscript is not self-contained on a load-bearing component of the central convergence result. The authors should include the proofs or cite a publicly available source.","section":"Appendix E"},{"comment":"The quartic synthetic problem uses f_3(x,y,z)=0.5‖zᵀH_zz z−zᵀH_zx x−zᵀH_zy y‖². The paper itself notes in Appendix F.4 that this lower-level problem has two optimal solutions, z=0 and z=H_zx x+H_zy y, and therefore f_3 is not μ_z-strongly convex in z. This directly violates Assumption 3.2, which is used in the convergence analysis. The statement that the initial points ensure convergence to one of the two solutions does not restore strong convexity. The quartic experiments should either use a strongly convex lower-level problem or include a separate local strong-convexity analysis for the relevant solution branch.","section":"Appendix F.4, equation (F.16)"}],"minor_comments":[{"comment":"The numerical experiments use decaying step sizes α_i=ᾱ/i, β_j=β̄/j, γ_k=γ̄/k, whereas Theorem 3.1 is proved for constant step sizes α_i=1/√I, β_i=(1/√J)α_i, γ_i=(1/(√J√K))α_i. The paper should state explicitly that the experiments are illustrative and are not a direct verification of the theorem's step-size schedule.","section":"Table 2, Section 4.2"},{"comment":"There is a typo in Assumption 3.4: 'idententically' should be 'identically'.","section":"Assumption 3.4"},{"comment":"In Figure 3 the left-hand y-axis labels appear to contain overlapping tick values ('2, 0, 2'); the plot would be clearer with standard tick formatting. Similar minor formatting issues appear in other figures.","section":"Figures 3–4"},{"comment":"The comparison with the trilevel formulation of [38] is only briefly reported in Appendix F.5.1; since this comparison is used to motivate the authors' formulation, a short statement in the main text summarizing the outcome would improve readability.","section":"Section 4.3, Appendix F.5.1"}],"recommendation":"major_revision","confidential_remarks":"The main proof of Theorem 3.1 appears sound given the assumptions, but the paper's advertised convergence guarantee does not currently transfer to the implemented TSG-N-FD and TSG-AD variants, and two load-bearing results (Remark 3.1 and Propositions E.1–E.2) are deferred to the authors' own in-preparation PhD thesis. The quartic numerical example also violates the strong convexity assumption. These issues are substantial but fixable within the manuscript's scope, so I recommend major revision rather than rejection."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Quick take: this is the first stochastic gradient method for trilevel optimization, and the main convergence theorem is a genuine contribution. The trilevel adjoint gradient derivation and the inexactness analysis are substantial and mostly self-contained. But the paper's advertised scope is broader than what is proven: Assumption 3.6, on which Theorem 3.1 rests, is never verified for the two practical algorithms whose numbers are reported. That gap matters, and it is load-bearing for the numerical claims.\n\nWhat is new and good: extending the bilevel stochastic adjoint framework to trilevel problems is not trivial; the nested implicit differentiation requires third-order tensors and the paper handles them carefully. The convergence analysis covers multiple sources of inexactness (inexact ML and LL solves, noisy gradients/Hessians/Jacobians, biased inverse Hessian estimators) under an explicit assumption. The experiments, especially the adversarial hyperparameter tuning formulation, are a reasonable sanity check and the code is available.\n\nWhere the soft spots are: (1) Assumption 3.6 requires the biases of the inverted stochastic Hessians to be O(theta), with theta = alpha*beta*gamma. TSG-AD uses a fixed truncation level Q in the Neumann series; TSG-N-FD uses fixed FD epsilon and no CG tolerance tied to theta. As written, neither algorithm satisfies the assumption along the theorem's step-size schedule, so Theorem 3.1 does not govern the reported experiments. The paper mentions truncated Neumann series and increasing sample sizes as mechanisms, but no concrete schedule is given. (2) The stronger O(1/sqrt(I)) rate is deferred to one author's PhD thesis, and the Lipschitz properties in Propositions E.1-E.2 have proofs in the same thesis. That is acceptable for a preprint but should be fixed before publication. (3) The synthetic quartic LL problem is not strongly convex, and the authors acknowledge the strong convexity limitation only in the conclusion; the theorem's assumptions are not met by that test problem. (4) Numerical comparisons are only against the authors' own ablations and a deterministic baseline, so the empirical superiority claim is modest.\n\nI do not see circularity in the main theorem; the proof is long but looks internally consistent. The core contribution is real. The paper deserves peer review, but the revision should either tune the practical algorithms to satisfy Assumption 3.6 (e.g., make Q or CG tolerance functions of theta), or restate the convergence theorem as covering an idealized estimator and leave the practical convergence as an open question. The reader's conditional verdict is fair; the stress-test note lands.\n\nRecommendation: send it to a serious referee, with the expectation of major revision.","headline":"First stochastic trilevel method with a real convergence theorem, but the theory does not cover the implemented variants; worth refereeing with major revision.","tokens_in":59982,"tokens_out":1951,"would_cite":true,"duration_ms":20204,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["90C26","90C30","90C15"],"pacs":[],"model":"deepseek-v4-flash","headline":"This paper proposes TSG, presented as the first stochastic gradient method for unconstrained trilevel optimization, and proves that, under smoothness, strong convexity of the two inner problems, and a bias condition on inverted stochastic…","keywords":["trilevel optimization","stochastic gradient descent","adjoint gradient","implicit differentiation","nonconvex optimization","hyperparameter tuning","adversarial learning","bilevel optimization"],"falsifier":"Measure, on a problem satisfying Assumptions 3.1–3.5, the actual bias $\\| [\\nabla^2_{zz} f_3]^{-1} - \\mathbb{E}[[\\nabla^2_{zz} f_3^{\\xi}]^{-1} | \\mathcal{F}_\\xi] \\|$ during TSG-N-FD or TSG-AD runs: if it does not decay as $O(\\alpha_i \\beta_i \\gamma_i)$, Assumption 3.6 fails and Theorem 3.1 does not apply to the tested algorithms.","tokens_in":58748,"feed_emoji":"📉","tokens_out":7829,"duration_ms":72269,"temperature":0.7,"pith_summary":"Trilevel optimization nests three optimization problems; until now its stochastic variants had no convergence theory. This paper proposes TSG, a three-loop stochastic gradient method that alternates lower-, middle-, and upper-level updates, and proves that the expected squared gradient norm of the upper objective converges to zero at rate O(J/√I) for nonconvex upper problems when the two lower levels are strongly convex. The theorem is designed to absorb every practical source of error: inexact solves of the middle and lower problems, an inexactly computed adjoint gradient, and noisy estimates of gradients, Hessians, Jacobians, and third-order tensors. The authors also give two practical implementations, one using finite-difference Hessian-vector products and one using truncated Neumann series with automatic differentiation, and demonstrate the method on synthetic trilevel problems and on trilevel adversarial hyperparameter tuning. If the convergence proof holds, stochastic trilevel learning, such as hyperparameter tuning combined with adversarial robustness, becomes a problem class with guarantees rather than a heuristic exercise.","feed_headline":"Stochastic trilevel optimization gets its first convergence theorem","feed_subtitle":"The TSG method tolerates noise and inexact inner solves, with a provable convergence rate.","key_machinery":"The load-bearing object is the trilevel adjoint gradient, $$\\nabla f = (\\nabla_x f_1 - \\$nabla^{2}$_{xz} f_3 (\\$nabla^{2}$_{zz} f_3)^{-1} \\nabla_z f_1) - \\$nabla^{2}$_{xy} \\bar{f} (\\$nabla^{2}$_{yy} \\bar{f})^{-1}(\\nabla_y f_1 - \\$nabla^{2}$_{yz} f_3 (\\$nabla^{2}$_{zz} f_3)^{-1} \\nabla_z f_1),$$ which reduces the nested problem to a single-level objective by implicit differentiation of the two optimality conditions. The method never computes this quantity exactly; each stochastic estimate carries bias from the approximate middle and lower solutions and from noisy or approximated second- and third-order derivatives. The proof controls that bias with a Lyapunov function $V_i = f(x_i) + \\|y_i - y(x_i)\\|^2 + \\|z_i - z(x_i)\\|^2 + \\|z_i - z(x_i,y_i)\\|^2$, whose expected decrease telescopes over the three loops into the $O(J/\\sqrt{I})$ bound. The practical variants replace Hessian inverses either by conjugate-gradient solves with finite-difference Hessian-vector products (TSG-N-FD) or by truncated Neumann series evaluated through automatic differentiation (TSG-AD).","core_discovery":"The central claim is that the trilevel optimization problem can be solved by a stochastic gradient method with a convergence guarantee: under Assumptions 3.1–3.6, with step sizes $\\alpha_i = 1/\\sqrt{I}$, $\\beta_i = (1/\\sqrt{J})\\alpha_i$, $\\gamma_i = (1/(\\sqrt{J}\\sqrt{K}))\\alpha_i$, and with iteration counts satisfying $\\varsigma \\le J$, $\\varpi \\le I$, and $K \\ge \\Xi(I,J) = O(J^3 I)$, the iterates satisfy $\\frac{1}{I}\\sum_{i=0}^{I-1} \\mathbb{E}[\\|\\nabla f(x_i)\\|^2] = O(J/\\sqrt{I})$. A companion result improves this to $O(1/\\sqrt{I})$ when step sizes are chosen using more problem-specific constants, at the price of requiring $K \\ge O(J^4 I)$. The convergence statement is built around the inexact trilevel adjoint gradient, so bias from approximate inner solutions, approximate adjoint computation, and stochastic derivative estimation is covered by the same analysis. The paper also shows the method working on quadratic and quartic synthetic trilevel problems and on a trilevel formulation of adversarial hyperparameter tuning, where the full trilevel formulation is reported to be the most consistent performer across three tabular datasets compared with two bilevel ablations.","pith_inferences":["If Assumption 3.6 were verified for the two practical implementations by choosing the Neumann truncation length and the finite-difference parameter as explicit functions of $\\theta=\\alpha\\beta\\gamma$, Theorem 3.1 would directly certify the algorithms whose numerical results are reported; as written, the guarantee covers an idealized estimator of the same type.","The requirement $K \\ge O(J^3 I)$ suggests a scaling law for multi-level methods: adding upper levels multiplies the inner-level iteration budget polynomially, so in four-level problems the lowest-level cost would likely grow even faster. A four-level experiment could separate the paper's specific result from a general hierarchical principle.","The comparison between the trilevel formulation and its two bilevel ablations suggests a practical decision rule: include the third level only when both hyperparameter tuning and adversarial robustness matter, since the bilevel variants save runtime but were more dataset-sensitive. This rule is an inference from the reported data pattern, and image-classification tasks remain untested.","A testable extension is to replace the strong-convexity requirements on the middle and lower problems with penalty or regularization techniques, following recent bilevel practice; if the Lyapunov argument could be preserved without strong convexity, the method would cover nonconvex inner problems."],"forward_implications":["Stochastic trilevel learning problems, such as joint hyperparameter and adversarial tuning, now have an algorithm with a formal convergence rate rather than only heuristic support.","The step-size recipe $\\alpha_i=1/\\sqrt{I}$, $\\beta_i=(1/\\sqrt{J})\\alpha_i$, $\\gamma_i=(1/(\\sqrt{J}\\sqrt{K}))\\alpha_i$ is directly implementable, with the lower level needing $K \\ge O(J^3 I)$ inner iterations to keep the overall rate.","Because the analysis covers biased and inexact gradients, mini-batch sampling of Hessians and third-order tensors is theoretically permissible, not just sampling of gradients.","The tighter $O(1/\\sqrt{I})$ rate shows the $O(J/\\sqrt{I})$ bound is an artifact of simple step sizes, not a limitation intrinsic to trilevel problems.","On the three tabular datasets tested, keeping all three levels produced more consistent test error than removing either the upper or lower level, suggesting the full trilevel formulation is useful when both hyperparameter tuning and adversarial robustness matter."],"supporting_citations":[{"why":"Supplies the alternating bilevel analysis and the tighter-rate technology that the trilevel proof adapts to the three-loop setting.","marker":"[11]"},{"why":"Provides the truncated-Neumann-series estimator and the O(theta) bias framework that Assumption 3.6 borrows.","marker":"[17]"},{"why":"Supplies the increasing-accuracy schedule used in the experiments to set the middle- and lower-level iteration counts J and K.","marker":"[18]"},{"why":"Underlies the StocBiO-style Neumann-series Hessian-inverse approximation on which TSG-AD is built.","marker":"[22]"},{"why":"Defines the deterministic multilevel gradient framework and the adversarial-hyperparameter TLO formulation that the paper swaps and reports as outperformed.","marker":"[38]"},{"why":"Contains the formal statement of the tighter O(1/sqrt(I)) rate quoted in Remark 3.1.","marker":"[26]"},{"why":"Supplies the strong-convexity inequality used to turn inner-level descent into the contraction estimates in Lemmas B.2 through B.4.","marker":"[33]"}],"fun_headline_variants":["First stochastic gradient method for trilevel optimization with proof","Trilevel optimization: first stochastic method with convergence guarantee","TSG method: provably convergent stochastic trilevel optimization","Stochastic trilevel solver handles noise, inexactness, and converges","New stochastic trilevel method: convergence proven, noise tolerated"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The proof assumes that the inverses of the noisy Hessian estimates are biased by at most $O(\\theta)$ with $\\theta=\\alpha\\beta\\gamma$, but the two practical algorithms whose experiments are reported never verify this bias bound.","fun_headline_variants_meta":{"raw":{"variants":["First stochastic gradient method for trilevel optimization with proof","Trilevel optimization: first stochastic method with convergence guarantee","TSG method: provably convergent stochastic trilevel optimization","Stochastic trilevel solver handles noise, inexactness, and converges","New stochastic trilevel method: convergence proven, noise tolerated"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000324,"raw_usage":{"total_tokens":1836,"prompt_tokens":981,"completion_tokens":855,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":597,"completion_tokens_details":{"reasoning_tokens":773}},"tokens_in":597,"tokens_out":855,"duration_ms":7674,"temperature":1.0,"reasoning_tokens":773,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-15T22:33:07.074127+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Measure, on a problem satisfying Assumptions 3.1–3.5, the actual bias $\\| [\\nabla^2_{zz} f_3]^{-1} - \\mathbb{E}[[\\nabla^2_{zz} f_3^{\\xi}]^{-1} | \\mathcal{F}_\\xi] \\|$ during TSG-N-FD or TSG-AD runs: if it does not decay as $O(\\alpha_i \\beta_i \\gamma_i)$, Assumption 3.6 fails and Theorem 3.1 does not apply to the tested algorithms.","supporting_citations":[{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Supplies the alternating bilevel analysis and the tighter-rate technology that the trilevel proof adapts to the three-loop setting."},{"cited_title":"Giovannelli, G","cited_arxiv_id":null,"evidence_quote":"Supplies the increasing-accuracy schedule used in the experiments to set the middle- and lower-level iteration counts J and K."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Defines the deterministic multilevel gradient framework and the adversarial-hyperparameter TLO formulation that the paper swaps and reports as outperformed."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Contains the formal statement of the tighter O(1/sqrt(I)) rate quoted in Remark 3.1."},{"cited_title":"Nesterov.Lectures on Convex Optimization","cited_arxiv_id":null,"evidence_quote":"Supplies the strong-convexity inequality used to turn inner-level descent into the contraction estimates in Lemmas B.2 through B.4."}],"review_version":1}