- Rating
- 2
- Confidence
- 3
- Informativeness
- 2
- Presentation
- 2
- Soundness
- 2
Read review
Paper summary
The paper studies the complexity of finding Goldstein approximate second-order stationary points of functions using deterministic second-order algorithms. The authors establish two lower bounds. Theorem 3.1 shows that deterministic zero respecting algorithms cannot guarantee finding such points in finitely many oracle calls, while Corollary 3.2 establishes an lower bound for general deterministic algorithms, where is the problem dimension.
The analysis relies on a resisting-oracle construction and a carefully designed function that preserves the oracle responses at queried points while maintaining negative curvature in a common direction. The paper also develops scalarization identities and a chain rule for generalized second order subdifferentials.
Critical strengths
The lower bounds hold with fixed smoothness constants, initial optimality gap, and stationarity tolerances. In particular, the impossibility result for zero respecting methods is an interesting theoretical observation.
The extension to general deterministic algorithms considers access to full Hessian information, which strengthens the oracle model relative to some existing lower bounds based on Hessian-vector products.
Critical weaknesses
1. The central claim of intractability is stronger than what is proved. The abstract and conclusion state that the results show “deterministic second-order weakly convex optimization is intractable.” The finite-time impossibility (Theorem 3.1) holds only for zero-respecting algorithms. For general deterministic algorithms, Corollary 3.2 gives a lower bound of oracle calls. The authors themselves describe this in Section 3.2 as a reduction “from finite-time intractability to dimension-free intractability.” A linear-in- lower bound rules out dimension-free guarantees, but it does not rule out deterministic algorithms with polynomial dependence on . In the usual sense of the word, that is not intractability. Likewise, the hardness concerns one particular stationarity notion, Goldstein approximate second-order stationarity. It does not concern weakly convex optimization in general. Since the headline claim is the main way the paper presents its significance, this gap materially affects my assessment.
2. Limited scope relative to existing deterministic lower bounds. The proof combines a resisting oracle with an orthogonal embedding, an approach already used in Nemirovsky & Yudin and in Tian & So (2024). Corollary 3.2 is closely related to the deterministic lower bound of Dragomir et al. (2026). The added value is full-Hessian access and the setting, which is genuine but incremental. In addition, the results hold only for pointwise second-order oracles. The first-order counterpart of Tian & So (2024) covers local oracles, while here that extension is left as a conjecture (Appendix D). For nonsmooth lower bounds, robustness to local information is important. A hard instance that defeats only pointwise queries says less about the intrinsic difficulty of the problem. Finally, the paper does not isolate which feature of the hard instance drives the hardness: the nonsmoothness of the Hessian specifically, or merely the absence of Hessian Lipschitz continuity. That makes it hard to judge what the separation from smooth saddle-escape results really means.
Questions for authors
- In what precise sense does Corollary 3.2 establish intractability? Would the authors revise the abstract and conclusion to say “no dimension-free deterministic algorithm” or similar? A clear revision here would address my main concern.
- Can the authors give any partial result toward Conjecture D.1, for instance for local oracles of a fixed small radius? Absent that, why should the pointwise-oracle lower bound be viewed as reflecting the intrinsic hardness of the problem?
- Does the hardness persist for functions whose Hessians are continuous but not Lipschitz? The answer would clarify whether the separation is due to nonsmooth second-order information or simply to the absence of Hessian regularity.
- Beyond the scalarization formula and chain rule (Corollaries 2.7 and 2.9), which technical components are new relative to Tian & So (2024) and Jordan et al. (2023)?