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

Abstract

We study first-order oracle complexity under the $\alpha$-Polyak-Lojasiewicz condition $f(x)-f_{\star }\le \tau \Vert \nabla f(x){\Vert }^{\alpha }$ for $\alpha \in [1,2]$. For $\alpha <2$, we first show that global $L$-smoothness together with a global $\alpha$-Polyak-Lojasiewicz inequality forces the objective to be constant. This motivates a nontrivial model in which smoothness remains global but the inequality is required only on the initial sublevel set. On this class, we establish sharp minimax lower bounds for every $\alpha \in [1,2)$. Deterministic first-order methods require $\Omega (L{\tau }^{2/\alpha }{\epsilon }^{-(2-\alpha )/\alpha })$ oracle calls, matching gradient descent. With unbiased stochastic gradients of conditional variance at most ${\sigma }^2$, randomized first-order methods require $\Omega (L{\tau }^{2/\alpha }{\epsilon }^{-(2-\alpha )/\alpha }+L{\sigma }^2{\tau }^{4/\alpha }{\epsilon }^{-(4-\alpha )/\alpha })$ calls, matching the corresponding SGD dependence when the inequality holds along the stochastic trajectory. At the classical endpoint $\alpha =2$, a separate construction yields the variance-dependent lower bound $\Omega (L{\tau }^2{\sigma }^2/\epsilon )$ even for globally smooth objectives satisfying the Polyak-Lojasiewicz inequality globally. In contrast, the sharp variance-dependent complexity for smooth $\mu$-strongly convex objectives is $\Theta ({\sigma }^2/(\mu \epsilon ))$; with $\tau =(2\mu {)}^{-1}$, the worst-case global Polyak-Lojasiewicz class exhibits an additional factor $L\tau =L/(2\mu )$.