# On the Lower Bound of Minimizing Polyak-Lojasiewicz Functions

arXiv: https://arxiv.org/abs/2212.13551 · HTML: https://mlsanity.com/paper/2212.13551/

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 27 Dec 2022.

## Built on by (most cited first, 3 of 3)

- [Polyak's Heavy Ball Method Achieves Accelerated Local Rate of Convergence under Polyak-Lojasiewicz Inequality](https://mlsanity.com/paper/2410.16849/) (2024)
- [On the Relevance of Byzantine Robust Optimization Against Data Poisoning](https://mlsanity.com/paper/2405.00491/) (2024)
- [Gradient Descent with Provably Tuned Learning-rate Schedules](https://mlsanity.com/paper/2512.05084/) (2025)

## Abstract (arXiv)

Polyak-Lojasiewicz (PL) [Polyak, 1963] condition is a weaker condition than the strong convexity but suffices to ensure a global convergence for the Gradient Descent algorithm. In this paper, we study the lower bound of algorithms using first-order oracles to find an approximate optimal solution. We show that any first-order algorithm requires at least Omegaleft(fracLμlogfrac1varepsilonright) gradient costs to find an varepsilon-approximate optimal solution for a general L-smooth function that has an μ-PL constant. This result demonstrates the optimality of the Gradient Descent algorithm to minimize smooth PL functions in the sense that there exists a ``hard'' PL function such that no first-order algorithm can be faster than Gradient Descent when ignoring a numerical constant. In contrast, it is well-known that the momentum technique, e.g. [Nesterov, 2003, chap. 2] can provably accelerate Gradient Descent to Oleft(√fracLhatμlogfrac1varepsilonright) gradient costs for functions that are L-smooth and hatμ-strongly convex. Therefore, our result distinguishes the hardness of minimizing a smooth PL function and a smooth strongly convex function as the complexity of the former cannot be improved by any polynomial order in general.