{"id":"d531ad89-0a06-4158-aa87-243c683017f7","arxiv_id":"2607.24520","paper_version":3,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"AINE achieves the optimal oracle complexity for convex minimization with δ-inexact Hessians, matching new lower bounds for both Hessian-Lipschitz and third-derivative-Lipschitz functions.","lead":"This paper designs a new accelerated Newton-type algorithm, AINE, that works with approximate Hessians and proves it needs the minimum possible number of oracle calls to solve smooth convex optimization problems. If correct, it settles the optimal complexity for inexact second-order methods and makes cheap curvature estimates theoretically lossless.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Lemma 4.2 is false for ξ>2, and its Appendix E proof contains an invalid equality; the p=3 oracle implementation and O((δ/ε)^{1/2}+(L3/ε)^{1/5}) claim rest on it.","rationale":"The reader's weakest assumption points to Lemma 4.2 and the algebraic inconsistencies in Appendix E; my analysis sharpens this into an explicit counterexample showing the lemma is false for ξ>2. This is the most load-bearing concern because the p=3 complexity result O((δ/ε)^{1/2}+(L3/ε)^{1/5}) depends on the BDGM subroutine terminating in polylog iterations, which in turn relies on the relative-smoothness constants of Lemma 4.2. The p=2 result is supported by a more self-contained analysis and is not implicated. Since the defect is local and may be fixable by restricting ξ to the valid range (likely ξ=2) and providing a corrected proof, the appropriate disposition is unchanged from the reader's conditional acceptance: the paper should not be accepted in its current form, but rejection is not warranted. I agree with the reader's identification of the concern, and I would word the required revision as 'state the allowable range for ξ and repair the proof of Lemma 4.2 before the p=3 claim is accepted.'","tokens_in":19079,"tokens_out":12867,"duration_ms":115283,"concrete_test":"Evaluate Lemma 4.2 at y=z_t with d=2, f≡0, H(z_t)=0, δ=1, L3=0, ξ=3. Then ∇²f_t=((ξ²−1)/ξ)I=(8/3)I and ∇²ρ_t=I, so the claimed upper bound (1+1/ξ)∇²ρ_t=(4/3)I fails to dominate ∇²f_t. This single instantiation settles that the lemma as stated is false for ξ>2. If the intended parameter is ξ=2, re-check the full matrix inequality for ξ=2 and correct Appendix E by computing the Hessians of the quartic terms explicitly, including the hhᵀ terms.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The p=3 branch of the central claim rests on Lemma 4.2, which asserts that f_t is (1±1/ξ)-relatively smooth with respect to ρ_t. The proof in Appendix E is not merely incomplete: the displayed equality is algebraically false, and the lemma as stated is actually false for ξ>2. Consider f≡0, H(z_t)=0, δ=1, L3=0, and y=z_t. Then ∇²f_t(y) = ((ξ²−1)/ξ)I from the quadratic term in Eq. (10), while ∇²ρ_t(y) = I from Eq. (11). Lemma 4.2's upper bound then requires ((ξ²−1)/ξ)I ⪯ (1+1/ξ)I, which is equivalent to ξ≤2. For ξ=3 this fails: (8/3)I ≰ (4/3)I. In the general proof, the appendix writes (1+1/ξ)(H+ξδI+(ξ+ξ²)L3‖h‖²I) = (1+1/ξ)∇²ρ_t(y), but the true ∇²ρ_t has coefficient (ξ+ξ²)L3/3 on ‖h‖²I plus an additional (2/3)(ξ+ξ²)L3hhᵀ term; these are not equal, and in directions orthogonal to h the claimed majorization is not implied. Since Algorithm 3's BDGM termination in Theorem 4.1 uses Lemma 4.1's linear rate with condition number derived from Lemma 4.2, the polylog-iteration bound is unsupported as written. The p=2 claim (Corollary 3.1) is unaffected.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper introduces an accelerated inexact Newton extragradient (AINE) method for convex optimization with δ-inexact Hessian oracles. The main claims are: (i) for convex functions with L₂-Lipschitz Hessians, AINE achieves an inexact second-order oracle (ISO) complexity of O((δ/ε)^{1/2} + (L₂/ε)^{2/7}); (ii) when the third derivative is L₃-Lipschitz, it achieves O((δ/ε)^{1/2} + (L₃/ε)^{1/5}) by implementing a third-order MS oracle with a Bregman-distance gradient method using only inexact Hessians; (iii) matching oracle lower bounds are provided for both regimes; and (iv) each iteration is claimed to run in nearly matrix-multiplication time. The proof of the general convergence rate is given in Theorem 3.1, the p=2 oracle implementation in Lemma 3.1/Corollary 3.1, the p=3 implementation in Lemma 4.2/Theorem 4.1/Corollary 4.1, and the lower bounds in Proposition 5.1.","tokens_in":19499,"tokens_out":12272,"duration_ms":116668,"significance":"The p=2 result, if correct, would match the exact-setting optimal rate while retaining the (δ/ε)^{1/2} noise dependence, improving on prior inexact second-order methods. The per-iteration near-matrix-multiplication cost and the extension of lower bounds to all deterministic algorithms are also valuable. However, the p=3 branch rests on Lemma 4.2, which is false as stated; this currently invalidates the O((δ/ε)^{1/2}+(L₃/ε)^{1/5}) claim. The Eq. (21) exponent error in the proof of Theorem 3.1 is repairable and the final rate appears salvageable, but both issues must be addressed before the claims are established.","major_comments":[{"comment":"The displayed derivation before Eq. (21) gives ∥y_t−z_t∥ ≥ const·(λ'_t)^{1/(p−1)}, so λ'_t∥y_t−z_t∥² ≥ const·(λ'_t)^{1+2/(p−1)} = (λ'_t)^{(p+1)/(p−1)}. Eq. (21) instead writes (λ'_t)^{2p/(p−1)}, which is not implied. Consequently, the epoch-length bound in Eq. (22) has the wrong power in the third term. Note that choosing λ' by Eq. (6) is actually the minimizer for the correct exponent (p+1)/(p−1), not for the exponent 2p/(p−1) displayed in Eq. (21); with the displayed exponent the algebra in Eq. (22) and the claimed final rate do not follow. This is a load-bearing step for Theorem 3.1 and Corollary 3.1, although the exponent appears fixable.","section":"Appendix C, Eq. (21)-(22)"},{"comment":"Lemma 4.2 is false as stated. Take f≡0, H(z_t)=0, δ=1, L₃=0, and y=z_t. Then ∇²f_t(y) = ((ξ²−1)/ξ) I from Eq. (10), while ∇²ρ_t(y) = I from Eq. (11). The claimed upper bound (1+1/ξ)∇²ρ_t(y) is equivalent to ξ≤2; for ξ=3 it already fails. The proof in Appendix E confirms this: it replaces ∇²ρ_t by (H+ξδI+(ξ+ξ²)L₃∥h∥²I), but the actual Hessian of ρ_t in Eq. (11) has coefficients (ξ+ξ²)L₃/3 on ∥h∥²I and an additional (2/3)(ξ+ξ²)L₃ hh^T. Thus the displayed equalities are not equalities. Moreover, Assumption 2.3 does not prevent H(z_t)+δI from being singular or indefinite, in which case ρ_t is not non-degenerate and no constants (1±1/ξ) can hold. Since this lemma is the basis for the BDGM subroutine's linear-rate termination used in Theorem 4.1, the p=3 claim is currently unsupported.","section":"Lemma 4.2 / Appendix E / Eq. (10)-(11)"}],"minor_comments":[{"comment":"There are several small typos: 'generaliza ons' in Section 3.1, the caption of Table 2 refers to 'Figure 2' but the experiment is in Figure 2 (the tabular figure itself is unnumbered), and Eq. (24) uses z0 in βρ(z0,y*_t) where z_t is meant.","section":"General"},{"comment":"The parameter ξ is described only as 'a numerical constant' and no value is ever chosen. Since Lemma 4.2 is false for ξ>2, the statement should either fix ξ explicitly (and prove the lemma for that value) or impose the necessary restrictions.","section":"Section 4.2 / Eq. (9)"},{"comment":"The definition of a δ-Hessian estimator does not require H(x)+δI to be positive definite. The p=3 BDGM analysis seems to need a stronger assumption (or a different scaling/proximal function); this should be stated explicitly.","section":"Assumption 2.3 / Lemma 4.2"},{"comment":"In the proof of Lemma 3.1, the term '2L₃∥y−x∥(y−x)' should be 'L₂∥y−x∥(y−x)' since λ=2δ+L₂∥y−x∥. The typo is cosmetic but should be corrected.","section":"Appendix D"}],"recommendation":"major_revision","confidential_remarks":"The paper has two headline results. The p=2 result appears to be salvageable by fixing the exponent error in Appendix C, but the p=3 result as currently written is not correct: Lemma 4.2 has a simple counterexample for ξ>2, and the Appendix E proof contains algebraic equalities that are false. The authors should be given the opportunity to repair the p=3 branch, but the current version cannot be accepted. I would not reject outright because the framework is plausible and the p=2 contribution may stand after revision."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Rough take: the p=2 half of this paper is a genuine contribution and probably right; the p=3 half rests on a lemma that is false as stated, so that half is not currently supported.\n\nWhat's actually new: the epoch separation trick that splits the 'large λ' iterations by whether δ or L_p r^{p-1} dominates, and the idea of implementing a third-order MS oracle with only inexact second-order queries via BDGM. The p=2 result, O((δ/ε)^{1/2}+(L2/ε)^{2/7}), closes the gap left by AINCR and matches lower bounds. The lower-bound generalization to all deterministic algorithms and all p is also useful.\n\nI checked the p=2 proof. There are typos in the appendix—e.g., Eq. (21) has λ^{2p/(p-1)} where the algebra gives λ^{(p+1)/(p-1)}, and the displayed inequality for |S↓| has the λ' on the wrong side. But the proof sketch in the main text has the right form, and once the arithmetic is corrected the final rate works. Nothing fitted here; the constants come from prior work.\n\nThe soft spot is real. Lemma 4.2, the relative-smoothness claim that makes BDGM terminate in polylog iterations, is false for ξ>2. Take f≡0, H(z_t)=0, δ=1, L3=0, and y=z_t: the lemma reduces to ((ξ²−1)/ξ)I ≤ (1+1/ξ)I, which forces ξ≤2. The appendix proof also writes an equality between a multiple of (H+δI+... ) and ∇²ρ_t that omits the 1/3 and the h h^T cross term. Since the condition number in Lemma 4.1 and the termination argument in Theorem 4.1 both rely on Lemma 4.2, the O((δ/ε)^{1/2}+(L3/ε)^{1/5}) claim is unsupported as written. Maybe the lemma holds for a carefully chosen ξ≤2 and a corrected proof, but that needs to be shown. The lower-bound section likewise says two lower bounds imply a sum, but doesn't construct the single hard instance; that's a gap, probably fixable.\n\nBottom line: the p=2 contribution deserves publication if the typos get cleaned up. The p=3 section needs real work—rewrite the proof of Lemma 4.2 or restrict the constant, and detail the lower-bound combination. This is not a desk reject; an editor should send it to referees who know the A-NPE and relative-smoothness literature. I'd tell the authors to submit a revision with the p=3 claim deferred if they can't repair Lemma 4.2.","headline":"The p=2 result is a real step forward and likely correct; the p=3 claim rests on a false relative-smoothness lemma and is not supported as written.","tokens_in":20033,"tokens_out":21230,"would_cite":true,"duration_ms":176809,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["90C25","90C60","65K05"],"pacs":[],"model":"deepseek-v4-flash","headline":"AINE achieves optimal convergence rates for convex optimization with approximate Hessians, matching proven lower bounds.","keywords":["inexact Hessian","convex optimization","second-order oracle complexity","accelerated Newton methods","Monteiro-Svaiter acceleration","tensor methods","oracle lower bounds","cubic regularization"],"falsifier":"Take a simple convex function with L3-Lipschitz third derivative, fix a query point z_t, numerically compute the smallest and largest eigenvalues of ∇²f_t(y) and ∇²ρ_t(y) over y within radius R_t, and check whether (1−1/ξ)∇²ρ_t ⪯ ∇²f_t ⪯ (1+1/ξ)∇²ρ_t holds for the paper's ξ. If it fails for any such function satisfying Assumptions 2.1–2.3, then Lemma 4.2 is false and the BDGM termination bound, and hence the claimed p=3 complexity, collapses.","tokens_in":18988,"feed_emoji":"🎯","tokens_out":4872,"duration_ms":42106,"temperature":0.7,"pith_summary":"Accelerated Inexact Newton Extragradient (AINE) brings the optimal convergence rates of second-order methods into the setting where Hessians are only known approximately. The paper establishes that, with δ-inexact Hessians, AINE finds an ε-solution in O((δ/ε)^{1/2} + (L2/ε)^{2/7}) inexact-Hessian queries when the true Hessian is L2-Lipschitz, and in O((δ/ε)^{1/2} + (L3/ε)^{1/5}) when the third derivative is L3-Lipschitz. The same rates are proven to be the best possible, so the method is optimal in both settings. Each iteration costs about the same as a matrix multiplication, up to logarithmic factors, making the theoretical optimum potentially practical.","feed_headline":"Optimal rates proven for optimization with approximate Hessians","feed_subtitle":"New algorithm matches the best possible Hessian-query counts and runs near matrix-multiplication time per step.","key_machinery":"AINE extends the accelerated Newton proximal extragradient (A-NPE) framework, which solves a proximal subproblem with a regularization parameter λ_t balancing Hessian inexactness and high-order smoothness. The key machinery is an epoch-wise guessing strategy for λ′_t: iterations are partitioned into epochs where the guess is fixed, and the guess is updated only when the cumulative progress A_t doubles. For inexactness, the analysis separates iterations where δ dominates (λ_t ≈ δ) from those where p-th order terms dominate; the new 'separation trick' bounds the number of each type of iteration separately. For p=3, the third-order MS oracle is implemented by a BDGM subroutine whose convergence","core_discovery":"For convex functions whose Hessian is L2-Lipschitz, the paper proves AINE achieves an inexact second-order oracle complexity of O((δ/ε)^{1/2} + (L2/ε)^{2/7}), and under L3-smoothness it achieves O((δ/ε)^{1/2} + (L3/ε)^{1/5}); it then proves matching lower bounds, demonstrating these rates cannot be improved. The second rate is obtained without ever querying a third-order derivative: the required third-order tensor step is implemented by a Bregman-distance gradient subroutine that only calls the inexact Hessian oracle, and terminates in polylogarithmically many iterations.","pith_inferences":["If the p=3 relative-smoothness constants in Lemma 4.2 fail, the BDGM subroutine could require more than polylog iterations; the O((L3/ε)^{1/5}) claim would then need an additional logarithmic factor or a modified scaling function, so verifying Lemma 4.2 is the first check before building on the p=3 result.","The separation trick (dividing damped iterations by whether δ or p-th order progress dominates) may transfer to other inexact higher-order or nonconvex settings where the regularization coefficient is ambiguous.","The formal lower bound matching for all p suggests a general principle: any method with δ-inexact Hessians must pay an unavoidable (δ/ε)^{1/2} term, independent of smoothness order.","Because each iteration is nearly as cheap as a Newton step, AINE narrows the gap between optimal theoretical oracle counts and what is implementable in large-scale machine learning, where exact Hessians are rarely available."],"forward_implications":["Practical solvers can use approximate Hessians (e.g., mini-batch estimates) and still achieve the optimal iteration count without exact curvature.","The p=3 rate improves the previously best inexact method's dependence on the third-order term from (L3/ε)^{1/4} to (L3/ε)^{1/5}, matching exact-tensor lower bounds while needing only Hessian queries.","The lower bounds certify that no deterministic algorithm using δ-inexact Hessians can do better, so the two-term complexity is tight for both Lipschitz classes.","Each iteration's near matrix-multiplication cost means the optimal oracle complexity translates into comparable runtime, making the method a candidate for large-scale problems."],"fun_headline_variants":["Optimal rates proven for inexact-Hessian convex optimization","Proof of optimal Hessian-query rates with inexact oracles","Matching lower bounds confirm optimality for inexact Hessians","Achieving provably optimal rates with approximate Hessians"],"cache_read_input_tokens":2304,"weakest_assumption_plain":"For the third-order rate to hold, the proximal function f_t must be non-degenerate with respect to the chosen scaling function ρ_t with constants (1±1/ξ); the paper's proof of this inequality in Appendix E contains algebraic equalities that are not equalities as written, and if the constants fail, the inner BDGM subroutine may not terminate in polylogarithmically many iterations, leaving the O((δ/ε)^{1/2} + (L3/ε)^{1/5}) guarantee unsupported.","fun_headline_variants_meta":{"raw":{"variants":["Optimal rates proven for inexact-Hessian convex optimization","Proof of optimal Hessian-query rates with inexact oracles","Matching lower bounds confirm optimality for inexact Hessians","Achieving provably optimal rates with approximate Hessians"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000592,"raw_usage":{"total_tokens":2589,"prompt_tokens":700,"completion_tokens":1889,"prompt_tokens_details":{"cached_tokens":256},"prompt_cache_hit_tokens":256,"prompt_cache_miss_tokens":444,"completion_tokens_details":{"reasoning_tokens":1819}},"tokens_in":444,"tokens_out":1889,"duration_ms":13195,"temperature":1.0,"reasoning_tokens":1819,"cache_read_input_tokens":256,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-03T01:45:53.165159+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Take a simple convex function with L3-Lipschitz third derivative, fix a query point z_t, numerically compute the smallest and largest eigenvalues of ∇²f_t(y) and ∇²ρ_t(y) over y within radius R_t, and check whether (1−1/ξ)∇²ρ_t ⪯ ∇²f_t ⪯ (1+1/ξ)∇²ρ_t holds for the paper's ξ. If it fails for any such function satisfying Assumptions 2.1–2.3, then Lemma 4.2 is false and the BDGM termination bound, and hence the claimed p=3 complexity, collapses.","supporting_citations":[],"review_version":2}