← All setups

Smooth Polyak–Łojasiewicz Minimization

Descriptions may be stale. Consult the linked Lean sources.

Smooth Polyak–Łojasiewicz Minimization

We consider minimizing a differentiable, possibly nonconvex function f:E→R on a real Hilbert space E. Its gradient is L-Lipschitz, and f satisfies the Polyak–Łojasiewicz inequality with parameter 0<μ≤L. A global minimizer x⋆∈E exists, and a given starting point x0∈E satisfies f(x0)−f(x⋆)≤Δ, where Δ≥0. The oracle returns ∇f(x) at x. For ε>0, the goal is an output x¯∈E satisfying f(x¯)−f(x⋆)≤ε almost surely under P, the law of the algorithm’s randomness.

The optimization problem is minx∈Ef(x). The norm ∥⋅∥ is induced by the inner product on E. The algorithm receives only E, L, and x0; the parameters μ, Δ, and ε may enter the oracle-call budget but are not algorithm inputs.

Our assumptions:

Assumption 1 (Smoothness). The function f is Fréchet differentiable everywhere on E, and ∥∇f(x)−∇f(y)∥≤L∥x−y∥,x,y∈E.

Assumption 2 (Polyak–Łojasiewicz inequality and initial gap). There exists x⋆∈E such that f(x⋆)≤f(x)for every x∈E,f(x0)−f(x⋆)≤Δ,2μ(f(x)−f(x⋆))≤∥∇f(x)∥2for every x∈E.

Queries may be made at any point of E. After the allotted oracle calls, the output must satisfy f(x¯)−f(x⋆)≤εP-a.s. The minimizer is fixed independently of the algorithm’s randomness; any global minimizer gives the same objective value.

Results

On a real Hilbert space, f has an L-Lipschitz gradient and a global minimizer x⋆, with f(x0)−f(x⋆)≤Δ and 2μ(f(x)−f(x⋆))≤∥∇f(x)∥2 for all x. Here 0<μ≤L, Δ≥0, and ε>0; convexity is not required. The oracle returns exact gradients. Target: f(xK)−f(x⋆)≤ε deterministically. The setup does not restrict the algorithm; (1) constructs GD with step 1/L.

Smooth PL optimization: SmoothPL.
Result Oracle complexity Novelty Limitations
(1) GdPL (Ours) (review) O(1+Lμlog⁡(1+Δε)) gradient calls
(2) GD (Karimi et al. 2016, Theorem 1, arXiv v4) O(1+Lμlog+⁡Δε) gradient calls; stated on Rd (1): Matches known rate for ε≤Δ/2. Lean formalization on Hilbert spaces; the dimension-independent classical proof extends unchanged. (1): Explicit stopping budget needs a known Δ; (2) states convergence in the actual initial gap.
(3) Lower bound (Yue et al. 2023, Theorems 2–3, arXiv v2) Ω(Lμlog⁡Δε) gradient calls; deterministic first-order methods, L/μ>C, 0<ε≤Δ/16 (1): Matches (3) up to constants in this regime. A problem-class lower bound, not a competing algorithm; randomized methods are not covered.

Abbr: GD: gradient descent; PL: Polyak–Łojasiewicz; L: gradient Lipschitz constant; μ: PL constant; Δ: initial objective-gap bound; ε: target gap; K: gradient-call count; log+⁡t=max{0,log⁡t} for t>0, with log+⁡0=0; C: universal positive constant.

Karimi, Hamed, Julie Nutini, and Mark Schmidt. 2016. “Linear Convergence of Gradient and Proximal-Gradient Methods Under the Polyak–Łojasiewicz Condition.” Machine Learning and Knowledge Discovery in Databases (ECML PKDD 2016), Lecture notes in computer science, vol. 9851: 795–811. https://doi.org/10.1007/978-3-319-46128-1_50.
Yue, Pengyun, Cong Fang, and Zhouchen Lin. 2023. “On the Lower Bound of Minimizing Polyak–Łojasiewicz Functions.” In Proceedings of Thirty Sixth Conference on Learning Theory, edited by Gergely Neu and Lorenzo Rosasco, vol. 195. Proceedings of Machine Learning Research. PMLR. https://proceedings.mlr.press/v195/yue23a.html.

Lean setup