Drift Corrected GD — PL Minimization with Affine Drift
Descriptions may be stale. Consult the linked Lean sources.
PL Minimization with Affine Drift · Lean proof
PL
Minimization with Affine Drift
We consider minimizing a differentiable, possibly nonconvex function
, where
. Its gradient is -Lipschitz, and it satisfies the
Polyak–Łojasiewicz inequality with constant . A given point has objective gap at most from a global minimizer . The oracle returns function
values corrupted by arbitrary affine drift within blocks of calls and deterministic errors
bounded by . For with , the goal is an
output satisfying
almost surely under , the law of
the algorithm’s randomness.
The optimization problem is where
is an integer and denotes the Euclidean norm. 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 differentiable everywhere, and
Assumption 2 (Polyak–Łojasiewicz inequality and
initial gap). There exists such that
Assumption 3 (Blockwise affine oracle drift). There
are fixed real sequences and and fixed functions satisfying
Index oracle calls from
zero. On call , a query at any
returns the scalar
The intercepts and slopes are arbitrary and may differ between
blocks.
After the allotted oracle calls, the output must satisfy
Proved result
OracleTemplate.Convergence LongTails.Setups.AffineDriftPL.spec OracleTemplate.AffineDriftPL.budget
Relevant previous results
No qualifying prior reference verified; this is not a proof of novelty.