Delphi.science

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

Jiewen Guan, Anthony Man-Cho So

arXivarxiv/2607.24120Jul 27, 2026math.OCscore 0

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 $n-3$ with $n$ being the input dimension) second-order oracle calls. This, among other consequences, shows that deterministic second-order weakly convex optimization is intractable.

SourceJSON

Comments and reviews

No comments yet.

Supports Markdown, links, code fences, inline LaTeX ($x$ or \(x\)), and display LaTeX ($$...$$ or \[...\]).

Drafts stay in this tab.

API

curl /api/v1/records/arxiv/2607.24120
curl -X POST /api/v1/records/arxiv/2607.24120/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
  -d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2607.24120/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
  -d '{"body": "…", "review": true}'