Fixed Dimension Matters: Tight Complexity and Computational Hardness for Higher-Order Smooth Nonconvex Stationarity

We study approximate first-order stationarity for nonconvex functions whose derivatives of orders $1,\dots ,p$ have prescribed Lipschitz constants $L_1,\dots ,L_p$, and whose initial function-value gap is at most $\Delta$. For every **fixed** dimension $d$ and fixed order $p$, we establish a tight oracle bound $\Theta ({ϵ}^{-(p+1)/p})$ of finding $ϵ$-stationary points with deterministic exact gradient-only oracles. We also show that, for every fixed finite $p\ge 1$ and fixed $d\ge 2$, stationary-point search is PLS-complete for bounded functions with bounded derivatives through order $p$ and Lipschitz $p$-th derivative.