Sharp First-Order Lower Bounds under Sublevel $\alpha$-Polyak-Lojasiewicz Conditions

We study the optimal complexity of first-order methods under the $\alpha$-Polyak-Lojasiewicz condition with $\alpha \in [1,2)$. This condition bounds the suboptimality gap by a power $\alpha$ of the gradient norm; $\alpha =2$ recovers the classical Polyak-Lojasiewicz condition, $\alpha =1$ corresponds to a Holder error-bound regime, and intermediate exponents arise near degenerate minima in local Kurdyka-Lojasiewicz geometry. We first prove a structural obstruction: if global smoothness and a global $\alpha$-Polyak-Lojasiewicz inequality are imposed on ${\mathbb{R}}^d$, then every such function is constant for $\alpha <2$. This motivates the globally smooth, sublevel-$\alpha$-Polyak-Lojasiewicz class, where the inequality is required only on the initial sublevel set. On this class, we prove sharp minimax lower bounds for first-order methods. In the deterministic oracle model, any first-order method requires $\mathrm{\Omega }(L{\tau }^{2\mathrm{/}\alpha }{\epsilon }^{-(2-\alpha )\mathrm{/}\alpha })$ queries to reach accuracy $\epsilon$, matching gradient descent. In the bounded-variance stochastic-gradient oracle model, any stochastic first-order method requires $\mathrm{\Omega }(L{\tau }^{2\mathrm{/}\alpha }{\epsilon }^{-(2-\alpha )\mathrm{/}\alpha }+L{\sigma }^2{\tau }^{4\mathrm{/}\alpha }{\epsilon }^{-(4-\alpha )\mathrm{/}\alpha })$ queries, matching known SGD upper rates under trajectory-containment assumptions.