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
on a real Hilbert
space . Its gradient is -Lipschitz, and satisfies the Polyak–Łojasiewicz
inequality with parameter . A global minimizer exists, and a given starting point satisfies , where . The oracle returns at . For , the goal is an output
satisfying
almost surely under , the law of
the algorithm’s randomness.
The optimization problem is The norm is induced by the inner product
on . The algorithm receives only
, , and ; the parameters , , and may enter the oracle-call
budget but are not algorithm inputs.
Our assumptions:
Assumption 1 (Smoothness). The function is Fréchet differentiable everywhere on
, and
Assumption 2 (Polyak–Łojasiewicz inequality and
initial gap). There exists such that
Queries may be made at any point of . After the allotted oracle calls, the
output must satisfy The minimizer is fixed independently of the
algorithm’s randomness; any global minimizer gives the same objective
value.
Proved result
OracleTemplate.Convergence LongTails.Setups.SmoothPL.spec OracleTemplate.PLGradient.budget
Relevant previous results
- B. T. Polyak. Gradient
methods for minimizing functionals. 1963 (Russian original).
Complexity: exact-gradient oracle
calls for , and zero
calls when ;
fixed-step gradient descent gives with a fixed
budget.