Lower Bounds for Feasibility and Stationarity in First-Order Nonconvex Constrained Optimization

We study oracle-complexity lower bounds for first-order methods applied to smooth equality-constrained nonconvex optimization, separating two components of approximate KKT accuracy: feasibility and stationarity. Under iteration-wise Jacobian regularity, we prove a lower bound of order \(\Omega(\frac{L_c\Delta_c}{\sigma^2}+\log\log(\frac{\sigma^2}{L_c\epsilon}))\) to achieve \(\epsilon\)-feasibility. For stationarity, we construct a nonlinear equality-constrained hard instance whose multiplier-minimized stationarity residual reduces exactly to the gradient of a scalar function, yielding the lower bound \(\Omega((L_f+\frac{GL_c}{\sigma})(\Delta_f+\frac{G\Delta_c}{\sigma})\epsilon^{-2})\) to reach \(\epsilon\)-stationarity. A reduction using disjoint supports {transfers zero-chain lower bounds} to any deterministic first-order methods and, for the stationarity construction, preserves the \(\ell_\infty\)-norm objective gradient bound. We also verify tightness of the lower bound regarding feasibility via a damped Newton method and regarding the stationarity, up to the stated dimension dependence, via a prox-linear method. Finally, we establish the union lower bound for smooth equality-constrained nonconvex problems and show its tightness through a two-stage method.

Article

Download

View PDF