← All setups

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 f:Rd→R, where d≥1. Its gradient is L-Lipschitz, and it satisfies the Polyak–Łojasiewicz inequality with constant 0<μ≤L. A given point x0 has objective gap at most Δ≥0 from a global minimizer x⋆. The oracle returns function values corrupted by arbitrary affine drift within blocks of d+2 calls and deterministic errors bounded by ν≥0. For ε>0 with 4dLν≤με, the goal is an output x¯ satisfying f(x¯)−f(x⋆)≤ε almost surely under P, the law of the algorithm’s randomness.

The optimization problem is minx∈Rdf(x), where d is an integer and ∥⋅∥ denotes the Euclidean norm. The algorithm receives only d,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 differentiable everywhere, and ∥∇f(x)−∇f(y)∥≤L∥x−y∥,x,y∈Rd.

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

Assumption 3 (Blockwise affine oracle drift). There are fixed real sequences (aj)j≥0 and (bj)j≥0 and fixed functions ek:Rd→R satisfying |ek(x)|≤ν,k≥0,x∈Rd. Index oracle calls from zero. On call k, a query at any x∈Rd returns the scalar yk(x)=f(x)+aj+bjr+ek(x),j=⌊kd+2⌋,r=k−j(d+2)∈{0,…,d+1}. The intercepts aj and slopes bj are arbitrary and may differ between blocks.

After the allotted oracle calls, the output x¯∈Rd must satisfy f(x¯)−f(x⋆)≤εP-a.s.

Proved result

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

OracleTemplate.Convergence LongTails.Setups.AffineDriftPL.spec OracleTemplate.AffineDriftPL.budget

Relevant previous results

No qualifying prior reference verified; this is not a proof of novelty.