← All setups

Gd PL — Smooth Polyak–Łojasiewicz Minimization

Descriptions may be stale. Consult the linked Lean sources.

Smooth Polyak–Łojasiewicz Minimization · Lean proof

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.

Proved result

⌈Lμ⋅log⁡(1+Δε)⌉+

OracleTemplate.Convergence LongTails.Setups.SmoothPL.spec OracleTemplate.PLGradient.budget

Relevant previous results

  • B. T. Polyak. Gradient methods for minimizing functionals. 1963 (Russian original). Complexity: O(⌈(L/μ)log⁡(Δ/ε)⌉) exact-gradient oracle calls for 0<ε<Δ, and zero calls when Δ≤ε; fixed-step gradient descent gives f(xK)−f∗≤ε with a fixed budget.