{"id":"89951678-9f4b-4858-9efd-d8ff33fc1dde","arxiv_id":"2607.24120","paper_version":1,"verdict":"ACCEPT","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"low","formal_verification":"none","parameter_count":0,"one_line_summary":"No deterministic zero-respecting second-order algorithm can compute Goldstein approximate second-order stationary points of C^{1,1} functions within finitely many oracle calls; general deterministic algorithms need at least n−3 calls.","lead":"This paper proves that deterministic algorithms that use gradients and Hessians cannot reliably find approximate second-order stationary points of functions with Lipschitz gradients, no matter how many steps they take (or, in high dimension, more than n−3 steps). It matters because it reveals a fundamental limit on a broad class of nonsmooth optimization methods used in machine learning.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Corollary 3.2 proof does not handle algorithms with duplicate projected iterates, leaving the general deterministic lower bound incomplete.","rationale":"The reader identified the Goldstein chain rule (Lemma 2.8 / Corollary 2.9) as the weakest assumption. I find that lemma to be true and adequately supported: the orthonormal-column case follows from the orthogonal case by extending U to an orthogonal matrix, and the second-order version follows via scalarization. So that is not the limiting step. The actual soft spot is in the proof of Corollary 3.2: it imports the 2D hard function of Theorem 3.1, whose definition requires positive separation between centers (ζ>0). For arbitrary deterministic algorithms, the projected iterates (e1^T xk,0) are not guaranteed to be distinct; an algorithm may repeat queries or vary only in coordinates orthogonal to e1. The proof does not state the necessary compression/removal of duplicate projected points. This is a genuine gap in the proof as written, though likely repairable. I recommend CONDITIONAL acceptance pending a demonstration that the compression argument works, because the general deterministic lower bound is the paper's headline contribution and should rest on a complete proof.","tokens_in":26160,"tokens_out":42655,"duration_ms":329065,"concrete_test":"Take n=4, m=1, and let A be the deterministic algorithm that always queries the origin (x0=x1=0). Run the proof of Corollary 3.2: the projected iterates are (0,0),(0,0), so ζ=0 and (3) is undefined. Determine whether the proof can be repaired by compressing the distinct projected points, i.e., applying the 2D construction to the single center (0,0) and defining f(x)=f2(U^T x) with U=[e1,v], v⊥span{e1,x0,x1}. If the compressed f is compatible with the resisting oracle at x0=x1 and refutes Goldstein SOSP at both iterates, the gap is a minor exposition issue; if not, the general lower bound fails for repeat-query algorithms.","verdict_should_be":"CONDITIONAL","load_bearing_attack":"The proof of Corollary 3.2 takes the iterates x0,...,xm generated by A on the constant resisting oracle and constructs f2 using (e1^T x0,0),...,(e1^T xm,0) as centers of the 2D hard function (3). The construction of f2 in Section 4.1 requires these centers to be pairwise distinct: it defines ζ=min{|xi−xj|,1}>0, and if two projected iterates coincide then ζ=0 and the piecewise function (3) is undefined. The WLOG 'assume xi≠xj' in Section 4.1 is applied to zero-respecting algorithms whose iterates are confined to the x-axis; it is not repeated in Corollary 3.2. For an arbitrary deterministic algorithm in A^n_det(m), the iterates under the constant oracle may contain repeated points or points with equal first coordinate (e.g., an algorithm that always queries the origin). The proof gives no compression argument to reduce to the distinct case. Thus, as written, Corollary 3.2 only covers algorithms whose projected query sequence is distinct; the claimed 'no more than n−3 calls' lower bound for all deterministic algorithms is not fully proven.","agreement_with_reader":"disagree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper establishes deterministic oracle complexity lower bounds for computing Goldstein approximate second-order stationary points of functions with Lipschitz-continuous gradients (C^{1,1} functions). Theorem 3.1 shows that no deterministic zero-respecting second-order algorithm can compute such a point in finitely many iterations; Corollary 3.2 shows that no general deterministic second-order algorithm can do so in at most n−3 iterations, where n is the dimension. The proofs construct a resisting oracle with Hessian −e1e1^T, forcing zero-respecting iterates onto the x-axis, then build a hard 2D C^{1,1} function with local patches matching the oracle and an infinite band in which every point refutes Goldstein second-order stationarity. The general case is obtained by an orthogonal embedding using the Goldstein subdifferential chain rule. The appendix provides a detailed, largely self-contained proof with explicit constants: Lipschitz constant 4.086, initial gap 17/256, and stationarity refutation 0.0092714.","tokens_in":26509,"tokens_out":7367,"duration_ms":70312,"significance":"If the results are correct, they are significant: they show a sharp failure of deterministic second-order methods for weakly convex nonsmooth optimization, complementing existing first-order lower bounds and clarifying the limits of oracle-based deterministic algorithms. The paper also introduces the Goldstein second-order δ-subdifferential and proves scalarization and chain-rule tools that are likely to be useful beyond this work. The main theorems are accompanied by explicit constants and a detailed appendix, which makes the central claims verifiable and reproducible in outline. The construction is original and the paper is honest about its reliance on a previously published chain rule.","major_comments":[{"comment":"The proof as written does not handle algorithms whose projected iterates e1^T x0, ..., e1^T xm are not pairwise distinct. The function f2 constructed in Section 4.1 is defined only when ζ = min{|xi−xj|, 1} > 0, i.e., when the centers are distinct. For an arbitrary deterministic algorithm in A^n_det(m), the transcript under the constant resisting oracle may contain repeated points or equal first coordinates (e.g., an algorithm that always queries the origin). The proof gives no merging/compression argument in Corollary 3.2. As written, the lower bound covers only algorithms with distinct projected query sequences. This is load-bearing for the claimed general deterministic lower bound, and the gap needs to be repaired, for instance by constructing f2 on the set of distinct projected points and observing that oracle compatibility and badness extend to the repeated queries.","section":"§4.2, Corollary 3.2"},{"comment":"The same distinctness issue appears in the proof of Theorem 3.1. The text says 'Without loss of generality, we may assume that xi ≠ xj for all i ≠ j' after establishing that zero-respecting iterates lie on the x-axis. This is not justified in the manuscript: a zero-respecting algorithm may query the same point more than once. A repair is possible by taking the set of distinct iterates as the centers of the hard function, but the WLOG must be argued explicitly. Since this is the foundation for Theorem 3.1, the proof should be amended even if the final statement is likely salvageable.","section":"§4.1, WLOG assumption"},{"comment":"The chain rule Lemma 2.8 is central to Corollary 3.2 and is stated for matrices U with orthonormal columns, which the authors note is a strengthening of the result cited from [Tian and So, 2024]. The proof in the manuscript relies on the assertion 'It follows from the proof of [Tian and So, 2024, Theorem 1]' for the orthogonal case. This is an external dependency at a load-bearing step. Please state the precise lemma from [Tian and So, 2024] that is being invoked, or provide a self-contained proof of the orthogonal case. This would also let the reader verify the strengthening to non-square U with orthonormal columns.","section":"Lemma 2.8 / Corollary 2.9"}],"minor_comments":[{"comment":"The abstract phrase 'no more than n−3 calls' should be aligned with the theorem statement: Corollary 3.2 requires n ≥ m+3, so the claimed lower bound for general deterministic algorithms applies up to m ≤ n−3 iterations. This is clear in the body, but a brief qualifier in the abstract would prevent misreading.","section":"Abstract / Corollary 3.2"},{"comment":"After sorting the iterates, the paper says 'x0 may no longer be 0 anymore'. This is fine because the hard function construction only needs the set of queried points, but the reader should be reminded that the algorithm's initial point is still the original x0 when verifying membership in F^n_C1(L,G;A). A short clarifying sentence would help.","section":"§4.1, relabeling"},{"comment":"Appendix B is explicitly labeled a conjecture with numerical evidence. This is acceptable, but it is somewhat unusual to include a conjecture in the appendix of a paper whose main claims are theorems. Since the conjecture is not used, consider moving this discussion to 'Concluding remarks' or restricting it to one paragraph, to avoid implying that the local-oracle extension is proven.","section":"Appendix B"}],"recommendation":"major_revision","confidential_remarks":"The central construction and constant verification appear sound, and the paper is clearly written. However, the proof of Corollary 3.2 (and the WLOG in Theorem 3.1) omits the duplicate-iterate case, which is essential for the general deterministic lower bound. The issue is fixable by merging duplicate projected centers, but the authors must actually make that argument. I would be willing to accept after the gap is repaired and the chain-rule invocation is made precise."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"The two things to know up front. First, this is the first deterministic lower bound for Goldstein-type approximate second-order stationarity in C^{1,1} optimization, and the construction is explicit, with concrete numbers (Lipschitz 4.086, gap 17/256, refutation 0.0092714). That is a real step forward. Second, the proof of Corollary 3.2 has a genuine gap: the hard function f2 requires pairwise distinct centers, but an arbitrary deterministic algorithm can generate duplicate projected iterates on the resisting oracle. As written, ζ can be zero and the piecewise definition (3) is undefined. The stress-test note is right. This is fixable—compress the iterates to the distinct subsequence and argue duplicates also fail—but the argument needs to be written down.\n\nWhat is good: the Goldstein second-order δ-subdifferential is a natural definition, and the scalarization formulas (Corollary 2.7) and the second-order chain rule (Corollary 2.9) are useful tools. The hard function is carefully engineered, and the appendix gives explicit calculus bounds for the local surgery. The band refutation lemma (Corollary A.13) is clean. Theorem 3.1 for zero-respecting algorithms is essentially self-contained, modulo a WLOG distinctness statement that is not justified but is likely easy to fix.\n\nSoft spots. The WLOG \"assume xi≠xj\" in Section 4.1 is stated without argument; that needs to be made rigorous. Corollary 3.2 does not even state it, so the proof is incomplete as written. Lemma 2.8 imports and slightly strengthens a chain rule from the authors' own previous paper; the proof sketch is okay but should be fleshed out or cited with the strengthening shown. Appendix B honestly labels the local-oracle extension as a conjecture, so the results are specifically for second-order oracles.\n\nBottom line: this is a paper worth engaging with. For people in oracle complexity or nonsmooth nonconvex optimization, it advances a known open direction. It deserves a serious referee, but the referee should insist on a careful handling of duplicate iterates in both theorems. I'd send it.","headline":"Strong lower-bound paper with a real proof gap in Corollary 3.2: duplicate iterates are not handled, and that needs to be fixed before the general deterministic result stands.","tokens_in":26927,"tokens_out":6733,"would_cite":true,"duration_ms":57799,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["90C26","49J52","90C60"],"pacs":[],"model":"deepseek-v4-flash","headline":"This paper proves that deterministic second-order optimization of functions with Lipschitz gradients is intractable: zero-respecting algorithms cannot reach Goldstein approximate second-order stationarity in finite queries, and general dete","keywords":["C^{1,1} functions","weak convexity","second-order stationarity","Goldstein subdifferential","oracle complexity","lower bounds","nonsmooth optimization","deterministic algorithms"],"falsifier":"Run any deterministic zero-respecting algorithm on the paper's explicit two-dimensional hard function f(x,y;ζ) for m iterations and test each iterate against the Goldstein second-order stationarity condition with δ=1/8 and η=0.0092714; if any iterate satisfies it, Theorem 3.1 is false. A simpler check: compute max⟨z,w⟩ over the entire band R×(−1/4,1/4) for w=(10,11)/√221; if this maximum exceeds −0.0092714, the band-refutation bound in Corollary 4.4 fails.","tokens_in":26095,"feed_emoji":"📉","tokens_out":6698,"duration_ms":59267,"temperature":0.7,"pith_summary":"The paper proves that no deterministic algorithm can reliably find an approximate second-order stationary point of a C^{1,1} function — a differentiable function with Lipschitz-continuous gradients, whose Hessian may be nonsmooth — within a predetermined finite number of second-order oracle queries. For zero-respecting algorithms, which only update coordinates that previous gradients or Hessians have exposed, the obstacle is absolute: no finite number of queries suffices in any dimension n≥2. For general deterministic algorithms, the obstacle is dimension-sensitive: at most n−3 queries are insufficient. Because C^{1,1} functions are automatically weakly convex, this establishes deterministic second-order weakly convex optimization as intractable. The hard example matches a benign-looking oracle at every queried point, yet hides a direction along which every generalized second-order derivative is strongly negative, so no queried point can pass the Goldstein stationarity test.","feed_headline":"No deterministic method finds second-order stationarity in finite calls","feed_subtitle":"Even with exact Hessians, zero-respecting methods cannot escape; general deterministic methods need more than n−3 queries.","key_machinery":"The central object is the Goldstein second-order δ-subdifferential, the convex hull of Clarke generalized Hessians sampled within a radius δ of the current point; because it is a set of matrices rather than a single matrix, stationarity is certified through a min-max condition over directions w. The engine of the proof is the scalarization identity ∂²_δ f(x)(w)=∂_δ⟨w,∇f⟩(x), which converts the second-order condition into a first-order Goldstein subdifferential of the directional derivative, together with a chain rule (Corollary 2.9) that lets the two-dimensional counterexample be pulled back along an isometric embedding into any higher dimension without weakening the stationarity refutation.","core_discovery":"For any m≥1 and n≥2, there exists a C^{1,1} function f with gradient Lipschitz constant 4.086 and initial optimality gap 17/256 such that any deterministic zero-respecting second-order algorithm, run for m iterations, produces only iterates x_0,...,x_m that all fail the (ε,η,δ)-Goldstein approximate second-order stationarity test: for each iterate, min_{||w||=1} max_{z∈∂²_{1/8}f(x_k)(w)} ⟨z,w⟩ ≤ −0.0092714. Corollary 3.2 extends the failure to every deterministic algorithm, with dimension n≥m+3. The proof uses a resisting oracle that always returns (0,0,−e₁e₁ᵀ); the hard function matches this oracle at all queried points while elsewhere containing a horizontal band in which every second-orde","pith_inferences":["If randomization can bypass these lower bounds, as it does for analogous first-order Goldstein stationarity problems, then stochastic Hessian sampling may be the only route to dimension-independent second-order guarantees.","The paper's appendix conjectures that the same impossibility extends to local oracles, which return all derivatives in a neighborhood; verifying that conjecture would rule out any deterministic oracle-based rescue.","A natural stress test of the construction: replace the fixed refuting direction w=(10,11)/√221 with adaptive directions; if the negative band persists for all directions, the hard function is a much stronger obstruction than the proof alone requires."],"forward_implications":["Any standard deterministic second-order method, including Newton-type, cubic-regularized, and trust-region variants, can be forced to fail the Goldstein second-order stationarity test forever when no additional structure is assumed.","The dimension n enters the lower bound for general deterministic algorithms: fewer than n−3 queries are provably insufficient, so dimension-independent deterministic guarantees are impossible.","Weak convexity — an automatic property of C^{1,1} functions — is not by itself enough to make second-order deterministic optimization tractable.","The negative curvature toward which an algorithm must move cannot be reliably detected at queried points, because the constructed function is C² at those points and matches a Hessian with a zero direction.","The Goldstein second-order stationarity concept, which was introduced as a natural target for complexity guarantees, is shown not to admit deterministic tractability in general."],"fun_headline_variants":["No deterministic second-order method finds stationarity in finite calls","Deterministic second-order stationarity: impossible in finite time","Finite calls won't get deterministic second-order methods to stationarity","Second-order stationarity: deterministic methods can't guarantee it in finite steps"],"cache_read_input_tokens":2304,"weakest_assumption_plain":"The proof that the two-dimensional example can be lifted to any higher dimension uses a chain rule for the Goldstein subdifferential under an isometric embedding, a rule imported from an earlier result and slightly strengthened; if that strengthening fails for matrices with orthonormal columns, the dimension-free lower bound for all deterministic algorithms would collapse.","fun_headline_variants_meta":{"raw":{"variants":["No deterministic second-order method finds stationarity in finite calls","Deterministic second-order stationarity: impossible in finite time","Finite calls won't get deterministic second-order methods to stationarity","Second-order stationarity: deterministic methods can't guarantee it in finite steps"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.001292,"raw_usage":{"total_tokens":5060,"prompt_tokens":637,"completion_tokens":4423,"prompt_tokens_details":{"cached_tokens":256},"prompt_cache_hit_tokens":256,"prompt_cache_miss_tokens":381,"completion_tokens_details":{"reasoning_tokens":4350}},"tokens_in":381,"tokens_out":4423,"duration_ms":25107,"temperature":1.0,"reasoning_tokens":4350,"cache_read_input_tokens":256,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-07-31T22:58:11.532146+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Run any deterministic zero-respecting algorithm on the paper's explicit two-dimensional hard function f(x,y;ζ) for m iterations and test each iterate against the Goldstein second-order stationarity condition with δ=1/8 and η=0.0092714; if any iterate satisfies it, Theorem 3.1 is false. A simpler check: compute max⟨z,w⟩ over the entire band R×(−1/4,1/4) for w=(10,11)/√221; if this maximum exceeds −0.0092714, the band-refutation bound in Corollary 4.4 fails.","supporting_citations":[],"review_version":1}