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

Saeed Masiha, Negar Kiyavash, Patrick Thiran

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$-sm…