{"id":"arxiv/2607.24120","url":"https://arxiv.org/abs/2607.24120","tags":["math.OC"],"score":0,"title":"On the hardness of deterministic second-order optimization of functions with Lipschitz gradients","domain":"math.OC","source":"arxiv","authors":["Jiewen Guan","Anthony Man-Cho So"],"reviews":0,"subject":"math.OC","summary":"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.","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-07-27","reactions":{}}