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

2026/07/27 by Jiewen Guan, Anthony Man-Cho So · 1 citation
#math.OC

paper · pdf

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 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.

Citations

• An Algorithm with Optimal Dimension-Dependence for Zero-Order Nonsmooth Nonconvex Stochastic Optimization
• Deterministic Nonsmooth Nonconvex Optimization
• No Dimension-Free Deterministic Algorithm Computes Approximate Stationarities of Lipschitzians
• Gradient-Free Methods for Deterministic and Stochastic Nonsmooth Nonconvex Optimization
• On the Finite-Time Complexity and Practical Computation of Approximate Stationarity Concepts of Lipschitz Functions
• A gradient sampling method with complexity guarantees for Lipschitz functions in high and low dimensions
• Oracle Complexity in Nonsmooth Nonconvex Optimization
• Generalized Damped Newton Algorithms in Nonsmooth Optimization via Second-Order Subdifferentials
• Understanding Notions of Stationarity in Non-Smooth Optimization
• Generalized Newton Algorithms for Tilt-Stable Minimizers in Nonsmooth Optimization
• Perturbed Iterate SGD for Lipschitz Continuous Loss Functions
• Pathological subgradient dynamics
• Nonconvex Robust Low-rank Matrix Recovery
• Stochastic model-based minimization of weakly convex functions
• Lower Bounds for Finding Stationary Points I
• Lower bounds for finding stationary points I
• Fast and Accurate Deep Network Learning by Exponential Linear Units (ELUs)
• A Differential Equation for Modeling Nesterov's Accelerated Gradient Method: Theory and Insights
• Generalized Newton's Method based on Graphical Derivatives

Cited by

• On computing Goldstein approximate second-order stationary points of structured nonsmooth nonconvex programs

Related

• Oracle Complexity of Second-Order Methods for Smooth Convex Optimization
• On computing Goldstein approximate second-order stationary points of structured nonsmooth nonconvex programs
• Convergence to Second-Order Stationarity for Constrained Non-Convex Optimization
• Lower Bounds for Finding Stationary Points II: First-Order Methods
• Second-Order Information in Non-Convex Stochastic Optimization: Power and Limitations