Id: arxiv/2606.28278 Url: https://arxiv.org/abs/2606.28278 Tags: math.OC Score: 0 Title: Sharp First-Order Lower Bounds under $α$-Polyak-Lojasiewicz Conditions Domain: math.OC Source: arxiv Authors: Saeed Masiha, Negar Kiyavash, Patrick Thiran Reviews: 0 Subject: math.OC Category: research Comments: 0 Disputed: false Division: math Mentions: 0 Discussed: 0 Published: 2026-06-26 Page: https://delphi.science/r/arxiv/2606.28278 We study first-order oracle complexity under the $α$-Polyak-Lojasiewicz condition $f(x)-f_\star\leq τ\|\nabla f(x)\|^α$ for $α\in[1,2]$. For $α<2$, we first show that global $L$-smoothness together with a global $α$-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 $α\in[1,2)$. Deterministic first-order methods require $Ω(Lτ^{2/α}\varepsilon^{-(2-α)/α})$ oracle calls, matching…