Nonconvex complexity and stationarity certificates

For a differentiable unconstrained objective, an epsilon-first-order stationary point has gradient norm at most epsilon in a specified norm. This condition rules out large first-order descent but can hold at a saddle or maximum. A common approximate second-order certificate also bounds the smallest Hessian eigenvalue below by minus a tolerance. It excludes sufficiently strong negative curvature, yet weak or higher-order saddles can remain. Neither certificate is a global objective-value guarantee without extra structural assumptions such as convexity or an appropriate error bound.

The tolerances carry scale. Multiplying an objective by a constant multiplies both gradient and Hessian, so the same numeric epsilon can represent a different demand after rescaling. In constrained problems, replace these unconstrained tests with feasibility, complementarity, and an appropriate Lagrangian or projected residual. A certificate computed using inaccurate derivatives should include that uncertainty. A solver stopping because it exhausted a wall-clock budget has supplied a budget outcome, not necessarily the promised mathematical certificate.

Assume the objective is differentiable on all Euclidean space, bounded below by a finite f_low, and has a globally L-Lipschitz gradient for some positive L. Exact gradient descent with step 1/L satisfies the descent lemma. Each update reduces the objective by at least the squared gradient norm divided by 2L. Summing over N updates telescopes the function values, leaving a finite initial objective budget that must pay for every large-gradient iteration. Convexity is not needed for this calculation.

The smallest squared gradient among the N starting iterates is at most their average. Consequently it is bounded by 2L times the initial objective gap divided by N. Taking N at least that numerator divided by epsilon squared ensures that one tested iterate meets the first-order target. This is an upper bound on updates and exact gradient evaluations in the stated model. If f_low or L is unknown, the theorem remains a valid analysis but does not by itself supply a computable stopping counter.

Second-order methods can exploit negative curvature and regularized quadratic models. With a Lipschitz Hessian and bounded-below objective, suitably solved cubic-regularization methods admit an $O(\varepsilon^{-3/2})$ evaluation bound for a first-order gradient target. A representative simultaneous second-order target scales the allowable negative curvature with the square root of the gradient tolerance, with constants depending on Hessian regularity. Such results require specified subproblem accuracy and oracle assumptions; they are not a blanket rate for every Newton method.

Comparing exponents alone hides costs. Forming a dense Hessian, solving a cubic subproblem, or estimating an extreme eigenvalue may be far more expensive than one gradient. Direct search uses objective calls and dimension-dependent directional coverage, while stochastic methods must account for variance and failure probability. State dimension, derivative access, smoothness class, target tolerances, and the operation being counted before comparing algorithms. The most honest final report combines a measured certificate with measured cost and separately lists any unverified global or feasibility claims.