← All setups

Discrepancy Batched GD — PL Minimization with Relative Discrepancy

Descriptions may be stale. Consult the linked Lean sources.

PL Minimization with Relative Discrepancy · Lean proof

PL Minimization with Relative Discrepancy

We consider minimizing a differentiable, possibly nonconvex function f:E→R on a real Hilbert space E. Its gradient is L-Lipschitz, with L>0, and it satisfies the Polyak–Łojasiewicz condition with parameter μ∈(0,L]. A given point x0∈E has objective gap at most Δ≥0 above a global minimizer x⋆. At call k≥0, the oracle returns a deterministic vector gk(x)∈E at x; accumulated errors over every consecutive block at a fixed point have norm at most D∥∇f(x)∥, with D≥0. 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, D, 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 its gradient satisfies ∥∇f(x)−∇f(y)∥≤L∥x−y∥,x,y∈E.

Assumption 2 (Polyak–Łojasiewicz condition 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.

Assumption 3 (Relative discrepancy). The oracle is specified by a fixed sequence of maps gk:E→E, indexed by k=0,1,…. For every x∈E and all nonnegative integers s,n, ‖∑i=0n−1(gs+i(x)−∇f(x))‖≤D∥∇f(x)∥. The sum is zero when n=0. Each block in this condition is evaluated at the same point x.

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.

Proved result

⌈4⋅L3⋅μ⋅log⁡(1+Δε)⌉+⋅max{1,⌈2⋅D⌉+}

OracleTemplate.Convergence LongTails.Setups.RelativeDiscrepancyPL.spec OracleTemplate.RelativeDiscrepancyPL.budget

Relevant previous results

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