acceptodds
Under review as a conference paper at ICLR 2027

On the hardness of deterministic second-order optimization of functions with Lipschitz gradients

Abstract

We show that no deterministic zero-respecting algorithm (resp., (general) deterministic algorithm) can compute Goldstein approximate second-order stationary points of functions with Lipschitz continuous gradients within a finite number of (resp., no more than with being the input dimension) second-order oracle calls. This, among other consequences, shows that deterministic second-order weakly convex optimization is intractable.

Primary area:
optimization
Keywords:
Variational analysis, second-order theory, lower bounds, oracle complexity, nonconvex nonsmooth optimization, $C^{1, 1}$-functions, weak convexity, second-order stationarity

Reviews

Among:
Shape:
1234this paper, Bottom 10%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 1.67 over 3 reviews, above 10% of the others.
Reviewer_7qHqOpenReview ↗
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 C1,1C^{1,1} 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 Ω(n)\Omega(n) lower bound for general deterministic algorithms, where nn 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 n−3n-3 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-nn lower bound rules out dimension-free guarantees, but it does not rule out deterministic algorithms with polynomial dependence on nn. 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 Ω(n)\Omega(n) deterministic lower bound of Dragomir et al. (2026). The added value is full-Hessian access and the C1,1C^{1,1} 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 C2C^2 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)?
Reviewer_v4nZOpenReview ↗
Rating
1
Confidence
3
Informativeness
1
Presentation
1
Soundness
1
Read review
Paper summary

The paper studies the deterministic oracle complexity of finding approximate second-order stationary points of lower-bounded C1,1C^{1,1} functions. It works with a second-order Goldstein δ\delta-subdifferential, the convex hull of the Clarke generalized Hessians over a δ\delta-ball, and calls a point (ε,η,δ)(\varepsilon,\eta,\delta)-Goldstein approximately second-order stationary if it satisfies the first-order Goldstein condition and, for every unit vector ww, some generalized Hessian HH in this set satisfies w⊤Hw≥−ηw^\top H w\ge-\eta. The main result is a resisting-oracle lower bound. For every deterministic second-order zero-respecting algorithm, every number of oracle calls mm and every dimension n≥2n\ge2, there is a lower-bounded C1,1C^{1,1} function with fixed gradient-Lipschitz constant and initial gap on which none of the iterates x0,…,xmx_0,\dots,x_m is approximately stationary in this sense.

Critical strengths

None

Critical weaknesses
  1. The main results are stated in a form that is very hard to read. Theorem 3.1 and Corollary 3.2 are written as five nested extrema, with the outer max and min taken over infinite sets of algorithms and functions. Constants in Theorem 3.1 need not appear in the main statements at all. The function class depends on the algorithm, since ff must be C2C^2 around the iterates that A\mathcal A generates on ff itself, and the statement carries four construction-specific constants.

  2. The paper is better suited to a journal.

Questions for authors

Can the authors restate Theorem 3.1 and Corollary 3.2?

Reviewer_M5mpOpenReview ↗
Rating
2
Confidence
4
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

This paper examines the oracle complexity of finding approximate second-order stationary points of functions with Lipschitz gradients but possibly discontinuous Hessians. The authors work with a Goldstein-type notion of second-order stationarity and some element of the convexified union of Clarke generalized Hessians. The main results are two lower bounds for deterministic methods with second-order point-query oracles.

Critical strengths
  • The question is a natural one. The first-order Goldstein hardness story is well known, and a second-order analogue was missing. The deterministic/randomized separation fits nicely with the two recent randomized upper-bound papers.

  • The construction is clean and, as far as I can tell, looks sound.

  • The hard instance is piecewise polynomial rather than some exotic pathological function. That makes it more convincing than a purely existential construction, and it connects to the motivating examples (squared hinge, Huber, ELU).

  • The algorithm-class discussion in Section 2.3.2 is useful. It makes clear which classical methods are covered by the zero-respecting restriction.

  • The chain rule (Lemma 2.8 / Cor. 2.9) with merely orthonormal columns is a small but real technical contribution, and the proof via orthogonal extension is neat.

Critical weaknesses
  • The core insight is less surprising than the framing suggests. The “separation between smooth and nonsmooth regimes” (Section 3.3.2) is really the well-known statement that second-order methods need Hessian-Lipschitzness (cubic Newton etc.). The paper never says this clearly. It also overstates its novelty by calling Prop. 2.4/Cor. 2.7 “new machinery”. They are nearly immediate from Rockafellar–Wets and Cui–Pang as far as I know.

  • All queries land in regions where f is C³, so the oracle returns a single Hessian. A more natural stronger model, such as a local oracle or one returning Hessians in a neighborhood, is not covered. The authors acknowledge this in Appendix D, but the appendix only offers a conjecture.

  • The paper says (after Def. 2.6) that the Goldstein notions in Lei et al. and Guan & So are identical to theirs, and that those works give polynomial randomized algorithms. The concluding remarks then pose as an “intriguing question” whether randomization can bypass the lower bounds, and remark that Guan & So “does not bypass” them. A randomized upper bound for the same stationarity notion plainly shows randomization helps, unless the oracle models differ (those algorithms use zeroth/first-order oracles). The paper should compare oracle models explicitly, and say what exactly the open question is.

Questions for authors
  1. The abstract says “no more than n−3 oracle calls”, but Corollary 3.2 needs n≥m+3n \ge m+3 with iterates x0,…,xmx_0, \ldots, x_m, which is m+1m+1 queried points, i.e. up to n−2n−2 calls. Is this an off-by-one, or are you counting iterations rather than oracle calls?

  2. I was left wondering if there is any deterministic algorithm with a finite (e.g. poly(n)poly(n)) upper bound for this problem, even under a stronger oracle? If not, can you justify “intractable” as opposed to “no dimension-free algorithm”?

  3. The intro states that Lei et al. and Guan & So give polynomial randomized algorithms for the same stationarity notion, yet the conclusion poses randomization as an open question. What exactly is open, and how do the oracle models differ (second-order point queries vs. zeroth/first-order sampling)?

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.