{"id":"76677f80-3d5f-4b7e-a02f-65152d66f8bf","arxiv_id":"2607.19647","paper_version":1,"verdict":"ACCEPT","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"Classical and modified-ratio trust-region methods reach the optimal O(ε^{-1/(1+ν)}) convex and O(ε^{-(2+ν)/(1+ν)}) nonconvex complexity for any Hölder ν∈[0,1] without knowing ν.","lead":"This paper proves that simple quadratic trust-region methods automatically adapt to the smoothness of the objective: regardless of the Hölder exponent ν of the Hessian, they achieve the theoretically optimal convergence rates in convex, nonconvex, and local regimes without tuning. The key new tool is a function-gap model-decrease estimate that turns the current distance to the optimum into guaranteed progress.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Lemma 12's βτ constant is wrong: with Eq. (49), the bound |1−ρk|≤1−η2 only holds for τ≥1, leaving Theorem 13's proof invalid for τ<1.","rationale":"The reader's weakest assumption identified the strong subproblem-solve condition (11) as the main fragility. That is a genuine practical limitation, but it is fully disclosed and does not invalidate the theoretical claims. My stress-test found a more concrete, load-bearing issue: Lemma 12, a linchpin of the convex analysis for Variant I, contains an incorrect constant in the definition of βτ (Eq. (49)). The proof's final inequality only works for τ≥1, contradicting the stated range τ∈[0,¯τ). Since Theorem 13 depends directly on Lemma 12, the universal convex complexity claim for the basic method is not rigorously established as written. However, the error is localized and appears easily fixable by changing the denominator from (1+τ)^2 to 2(1+τ). I verified the other main components: Lemma 7's function-gap estimate, Lemma 9's induction, Lemma 10's potential-function argument, Lemma 16/17/18 for UniCAT's nonconvex complexity, and Lemma 19's small-radius implication all appear mathematically correct. Thus the central claims are likely true after a minor correction, but the current manuscript should not be unconditionally accepted without fixing Lemma 12 and re-verifying the proof of Theorem 13. Hence CONDITIONAL rather than REJECT or UNCHANGED.","tokens_in":28482,"tokens_out":21573,"duration_ms":170999,"concrete_test":"Re-derive Lemma 12 with explicit numerical parameters: choose ν=0, τ=0, η2=0.1, C_f=D=1, F0=F_k=1, Δ=βτ. With the paper's βτ from Eq. (49), βτ=0.9, and the final inequality gives |1−ρ|≤1.8, which does not imply ρ≥η2. Replace Eq. (49) by βτ := min{ D/F0^α, ((1−η2)/(2(1+τ)C_fD))^α }, giving βτ=0.45 and |1−ρ|≤0.9. Verify that with the corrected constant, Lemma 12's implication (Δ≤βτ F_k^α ⟹ ρ≥η2) holds, and subsequently Theorem 13's complexity bound follows intact. This single-parameter check settles whether the proof gap is merely typographical.","verdict_should_be":"CONDITIONAL","load_bearing_attack":"The convex universal result for Variant I (Theorem 13) relies on Lemma 12 to establish condition (ii) of Theorem 8, namely that sufficiently small radii yield very successful steps. In Lemma 12, the proof derives |1−ρk| ≤ 2(1+τ)C_fD Δ^{1+ν}/F_k. To conclude |1−ρk| ≤ 1−η2, one needs 2(1+τ)C_fD βτ^{1+ν} ≤ 1−η2, i.e. βτ ≤ ((1−η2)/(2(1+τ)C_fD))^α. However, Eq. (49) defines βτ := min{ D/F0^α, ((1−η2)/((1+τ)^2 C_fD))^α }. With this definition, 2(1+τ)C_fD βτ^{1+ν} = 2(1−η2)/(1+τ), which exceeds 1−η2 whenever τ<1. For example, τ=0 (exact solves), η2=0.1, C_f=D=1 gives 1.8 > 0.9. The proof as written therefore fails for τ∈[0,1), a range explicitly allowed by the algorithm (τ_k∈[0,¯τ)). This is likely a typographical slip—replacing (1+τ)^2 by 2(1+τ) in Eq. (49) repairs the argument—but the manuscript as submitted does not rigorously prove the claimed universal convex complexity for the basic inexact trust-region method. The rest of the convex proof (Lemma 7, Lemma 9, Lemma 10) appears sound, and the UniCAT (Variant II) analysis, including Lemma 19, checks out, so the overall theory is probably salvageable with a corrected constant.","agreement_with_reader":"disagree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies two quadratic trust-region variants: the classical ratio-test method with inexact subproblem solves (Variant I) and an exact-solve variant with a modified acceptance ratio (UniCAT, Variant II). Under ν-Hölder-continuous Hessians and without knowledge of ν or the Hölder constant, it claims the following: Variant I achieves O(ε^{-1/(1+ν)}) for convex ε-approximate minimization, retains the classical O(ε^{-2}) nonconvex first-order bound, and recovers local Newton-type rates; Variant II achieves the Hölder-adaptive nonconvex first-order bound O(ε^{-(2+ν)/(1+ν)}), the universal convex bound O(ε^{-1/(1+ν)}), and local Q-superlinear/order-(1+ν) convergence. The convex analysis is organized around a function-gap model-decrease property (MD_α) that is isolated as the key new mechanism.","tokens_in":28825,"tokens_out":8244,"duration_ms":71384,"significance":"If the results are correct, this is a valuable contribution: it shows that the classical trust-region mechanism is automatically adaptive to unknown Hölder smoothness across convex, nonconvex, and local regimes, without gradient/cubic regularization or gradient-dependent radii. The function-gap model-decrease estimate in Lemma 7 is a clean and reusable abstraction, and the paper is generally self-contained, carefully separating assumptions from conclusions and explicitly disclosing limitations (exact subproblem solves for Variant II, the strong inexactness condition for Variant I, and the use of ψ_k rather than ‖∇f(x_k)‖ in the nonconvex UniCAT bound). The abstract theorem framework in Section 4 is well designed. The main reservation is a localized but load-bearing proof error in Lemma 12 that affects the first main convex claim as submitted.","major_comments":[{"comment":"The definition of βτ in Eq. (49) does not imply the claimed conclusion for τ<1. The proof derives |1−ρ_k| ≤ 2(1+τ)C_fD βτ^{1+ν}. With βτ as defined, this is at most 2(1−η2)/(1+τ), which exceeds 1−η2 whenever τ<1. For example, τ=0, η2=0.1, C_f=D=1 gives 1.8 > 0.9. Thus Lemma 12 is not established for the allowed range τ_k∈[0,\\barτ) when \\barτ<1, including the exact-solve case τ=0, and Theorem 13's universal convex claim for Variant I is therefore unproved as submitted. The likely fix is to replace (1+τ)^2 in (49) by 2(1+τ) (or equivalently to define βτ with the factor 2(1+τ) in the denominator); the rest of the convex proof appears sound. This is load-bearing for the paper's first main theorem and must be corrected or the theorem restated with a restricted inexactness range.","section":"§6.1, Theorem 18 and Remark 8"},{"comment":"The nonconvex UniCAT guarantee is stated for ψ_k = min{‖∇f(x_k)‖, ‖∇f(x_k+s_k)‖}, not for the gradient at the accepted iterate. Remark 8 discloses this, but the abstract and introduction phrase the result as a bound on 'computing an ε-first-order stationary point.' This is a weaker output convention than the standard one, since the certificate may be at a rejected trial point and no explicit output-selection rule is given. The paper should state this convention prominently in the abstract/introduction, or add a simple rule such as returning the best of the iterates and trial points, so that the claimed nonconvex complexity is not overstated.","section":null}],"minor_comments":[{"comment":"The global parameters are stated as 0<η1≤η2<1, but for Variant II the analysis later requires η2<1/(1+ϑ) or η2<1/(1+ϑ/2). State these restrictions near Algorithm 1 to avoid an apparent inconsistency.","section":"§3.4, Lemma 6"},{"comment":"In the proof, the denominator |log(γ2)| is written inconsistently (once as logγ2 and once as |logγ2|). This is cosmetic but should be cleaned up.","section":null},{"comment":"After fixing the constant in Lemma 12, please re-check the related constants in Theorems 8 and 13 so that the dependencies on \\barτ are consistent throughout.","section":null},{"comment":"The local convergence proof is standard but somewhat long; it could be streamlined by citing the classical Newton analysis more explicitly and moving some estimates to an appendix.","section":null},{"comment":"The phrase 'function-gap model-decrease estimate that appears to be new' is useful, but the relationship to the related estimate in [CGT12] should be spelled out more precisely in the introduction or in Remark 3.","section":null}],"recommendation":"major_revision","confidential_remarks":"The paper is well-structured and the main framework is convincing, but the proof error in Lemma 12 is load-bearing: it invalidates the universal convex complexity claim for the inexact basic trust-region method for an explicitly allowed parameter range, including exact subproblem solves. The error appears localized and easily repairable, so I recommend major revision rather than rejection. I would be willing to accept once the constant is fixed and the output convention for the UniCAT nonconvex result is clarified."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Here's my take. The core idea is real: Lemma 7's function-gap model-decrease estimate is the right lever to get Hölder-adaptive convex complexity for trust-region methods, and the abstract Theorem 8 cleanly isolates what you need. I checked the main chain for the UniCAT variant and it looks coherent — Lemma 19 works, and the nonconvex bound with the ψ_k measure is plausible and clearly disclosed. The paper is also honest about its limitations: Variant I needs near-exact subproblem solves, Variant II exact solves, and only first-order stationarity is treated. Those are disclosed and don't by themselves undermine the claims.\n\nThe problem is Lemma 12. The claim is that small radii are very successful for the basic method, and the proof needs 2(1+τ)C_fD β_τ^{1+ν} ≤ 1−η_2. But Eq. (49) defines β_τ with a square in the denominator: ((1−η_2)/((1+τ)^2 C_fD))^α. Plugging that in gives exactly 2(1−η_2)/(1+τ), which is larger than 1−η_2 whenever τ<1. So the inequality asserted at the end of the lemma doesn't follow. For τ=0 and η_2=0.1, it's 1.8 vs 0.9. This is exactly the range the algorithm allows. The rest of the proof structure is right, and replacing (1+τ)^2 in Eq. (49) by 2(1+τ) repairs the argument — but the submitted manuscript does not rigorously prove Theorem 13 as stated.\n\nThat's load-bearing because Theorem 13 is one of the two advertised headline results. It doesn't sink the paper's overall thesis — the same mechanism works for UniCAT, and the basic-method result is almost certainly true with a corrected constant — but it needs to be fixed before the result can be taken as established.\n\nWorth a serious referee? Yes. The idea is good, the writing is careful, and the flaw looks like a genuine typo rather than a structural gap. A referee should push for the corrected constant and re-verification of the τ<1 range. I'd bring it to the reading group, and I'd cite it once the corrected version is out.","headline":"Sharp idea, one bad constant: Lemma 12's beta_tau invalidates the convex proof for the basic method as written, but the UniCAT analysis and the core mechanism look sound.","tokens_in":29422,"tokens_out":4485,"would_cite":true,"duration_ms":38401,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["90C30","90C25","90C60"],"pacs":[],"model":"deepseek-v4-flash","headline":"The classical quadratic trust-region method, given no information about the smoothness of the objective, provably attains the optimal iteration complexity in convex, nonconvex, and local regimes under Hölder-continuous Hessians.","keywords":["trust-region methods","universal complexity","Hölder-continuous Hessian","convex optimization","nonconvex optimization","Newton method","iteration complexity"],"falsifier":"Implement the basic ratio-test trust-region method with a near-exact subproblem solver on convex functions with known Hölder exponent ν (for example f(x) = |x|^{2+ν} on ℝ) and check whether the number of iterations to reach f(x)-f* ≤ ε scales as ε^{-1/(1+ν)} without any ν-dependent tuning. An observed exponent different from 1/(1+ν), or a need to know ν to achieve it, would refute the universality claim.","tokens_in":28255,"feed_emoji":"🎯","tokens_out":9064,"duration_ms":67165,"temperature":0.7,"pith_summary":"The paper claims that the classical trust-region mechanism is inherently adaptive. For the basic ratio-test method with inexact subproblem solves, it proves the universal convex complexity bound O(ε^{-1/(1+ν)}) under a ν-Hölder-continuous Hessian, with no knowledge of ν or the Hölder constant. For a variant with a modified acceptance ratio and exact solves (UniCAT), it proves the same convex bound together with the optimal nonconvex first-order complexity O(ε^{-(2+ν)/(1+ν)}) and local Newton rates. The key new ingredient is a function-gap model-decrease estimate that links the model decrease to the function gap rather than the gradient norm. If correct, this shows that trust-region methods automatically adapt to unknown smoothness across all three regimes, without cubic, gradient, or tensor regularization.","feed_headline":"Trust-region algorithm hits optimal rates with no tuning","feed_subtitle":"A single classical algorithm provably matches each Hölder-exponent bound across convex, nonconvex, and local regimes.","key_machinery":"The central mechanism is the function-gap model-decrease estimate (Lemma 7, property (MD_α)): for a convex objective with Hölder-continuous Hessian, the optimal trust-region model decrease at x_k is bounded below by (1+η_2)F_k/(2D) min{βF_k^α, Δ}, where F_k = f(x_k)-f* is the function gap, α = 1/(1+ν), and β, D are constants. This replaces the classical Cauchy-decrease (gradient-norm) estimate with one in terms of the function gap, and it supplies one of the two hypotheses of an abstract convex complexity theorem (Theorem 8); the other is that sufficiently small trust-region radii are automatically very successful. Together they yield the universal rate O(ε^{-1/(1+ν)}).","core_discovery":"The paper proves that the classical quadratic trust-region method is universal under convexity: for every ν∈[0,1], under a ν-Hölder-continuous Hessian, the basic ratio-test method with inexact solves attains the global complexity O(ε^{-1/(1+ν)}) for an ε-approximate minimizer, with no knowledge of ν or its Hölder constant; the UniCAT variant—same quadratic model, slightly modified acceptance ratio, exact subproblem solves—attains the same convex bound, the optimal nonconvex first-order complexity O(ε^{-(2+ν)/(1+ν)}), and local Newton rates in one algorithm. The central new estimate is a function-gap model-decrease inequality that bounds the model decrease by the scaled function gap, and the","pith_inferences":["If the universal bound holds, the practical bottleneck shifts to subproblem solvers: making the guarantee effective at scale requires inexact solvers satisfying condition (11), which standard truncated-CG does not; designing such solvers for large-scale problems is a natural next step.","The abstract convex theorem suggests that the radius-update rule, not the specific model, is what drives adaptation to unknown smoothness; this may transfer to quasi-Newton, stochastic, or proximal trust-region variants.","The function-gap mechanism might also explain empirically observed fast convergence of trust-region methods on ill-conditioned machine-learning problems, though the exact-solve assumption limits direct transfer.","A testable extension is whether the UniCAT modification retains its three-regime universality under a more permissive inexactness condition than exact solves; the paper notes this as an open direction."],"forward_implications":["The basic ratio-test trust-region method, with near-exact subproblem solves, achieves the universal convex rate O(ε^{-1/(1+ν)}) for every ν∈[0,1], improving on the standard O(ε^{-1}) bound whenever ν>0.","The UniCAT variant attains the optimal nonconvex first-order complexity O(ε^{-(2+ν)/(1+ν)}) while preserving the convex rate and local Newton rates—the first simple trust-region method universal across all three regimes.","Under vanishing inexactness, both variants recover Q-superlinear convergence (ν=0) and order 1+ν (ν∈(0,1]) near nondegenerate minimizers, matching classical Newton behavior adaptively.","Any trust-region variant that satisfies the two abstract hypotheses—function-gap model decrease and small-radii success—inherits the universal convex rate (Theorem 8), giving a template for further designs.","The nonconvex O(ε^{-2}) guarantee for the basic method is retained under bounded Hessians, so the new convex results do not weaken the classical first-order bound."],"fun_headline_variants":["Trust-region hits every optimal bound","Universal complexity: trust-region simple","No tuning: trust-region adapts to all","Optimal for every smoothness: trust-region","Simple trust-region is universally optimal"],"cache_read_input_tokens":2304,"weakest_assumption_plain":"The load-bearing premise is that the method can compute, at every iteration, a trust-region step that captures a fixed fraction of the optimal model decrease (for the basic variant) or the exact optimal step (for the faster variant); if only the weaker standard Cauchy-decrease condition is available, the universal convex analysis does not go through.","fun_headline_variants_meta":{"raw":{"variants":["Trust-region hits every optimal bound","Universal complexity: trust-region simple","No tuning: trust-region adapts to all","Optimal for every smoothness: trust-region","Simple trust-region is universally optimal"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000342,"raw_usage":{"total_tokens":1800,"prompt_tokens":908,"completion_tokens":892,"prompt_tokens_details":{"cached_tokens":256},"prompt_cache_hit_tokens":256,"prompt_cache_miss_tokens":652,"completion_tokens_details":{"reasoning_tokens":825}},"tokens_in":652,"tokens_out":892,"duration_ms":8105,"temperature":1.0,"reasoning_tokens":825,"cache_read_input_tokens":256,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-01T12:10:35.651467+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Implement the basic ratio-test trust-region method with a near-exact subproblem solver on convex functions with known Hölder exponent ν (for example f(x) = |x|^{2+ν} on ℝ) and check whether the number of iterations to reach f(x)-f* ≤ ε scales as ε^{-1/(1+ν)} without any ν-dependent tuning. An observed exponent different from 1/(1+ν), or a need to know ν to achieve it, would refute the universality claim.","supporting_citations":[],"review_version":1}