Lower Bounds for $(L_0,L_1)$-Smooth Optimization

We establish the deterministic first-order oracle complexity of finding an $\varepsilon$-stationary point of a lower-bounded nonconvex function satisfying $\||\nabla^2 f(x)\|| \leq L_0 + L_1\||\nabla f(x)\||$ and $f(0)-\inf_x f(x)\leq\Delta$. Normalized gradient methods achieve an upper bound of $O(L_0\Delta/\varepsilon^2 + L_1\Delta/\varepsilon)$ oracle queries, whereas standard smooth nonconvex lower bounds capture only the first term. We close this gap by proving that every deterministic first-order method requires $\Omega(L_0\Delta/\varepsilon^2 + L_1\Delta/\varepsilon)$ queries in a dimension proportional to the query budget. Our construction modifies the zero-chain of Carmon et al. (2020) by replacing its Gaussian tail with a logistic tail. The bounded logarithmic derivative of the logistic density provides simultaneous absolute and gradient-relative curvature control, yielding both the $L_0$- and $L_1$-dependent terms after scaling. We further establish the same complexity for a Hessian-free $C^1$ function class defined through a one-sided exponential upper model, with a matching upper bound that does not require twice differentiability. Equivalently, after $N$ oracle queries, the minimax gradient norm is $\Theta(\sqrt{L_0\Delta/N}+L_1\Delta/N)$.