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
on a real Hilbert
space . Its gradient is -Lipschitz, with , and it satisfies the
Polyak–Łojasiewicz condition with parameter . A given point has objective gap at most above a global minimizer
. At call , the oracle returns a
deterministic vector at
; accumulated errors over every
consecutive block at a fixed point have norm at most , with . 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 its gradient satisfies
Assumption 2 (Polyak–Łojasiewicz condition and
initial gap). There exists such that
Assumption 3 (Relative discrepancy). The oracle is
specified by a fixed sequence of maps , indexed by . For every and all nonnegative integers , The sum is zero when . Each block in this condition is
evaluated at the same point .
Queries may be made at any point of . After the allotted oracle calls, the
output must satisfy
Proved result
OracleTemplate.Convergence LongTails.Setups.RelativeDiscrepancyPL.spec OracleTemplate.RelativeDiscrepancyPL.budget
Relevant previous results
No qualifying prior reference verified; this is not a proof of novelty.