PL Minimization with Affine Drift
Descriptions may be stale. Consult the linked Lean sources.
PL Minimization with Affine Drift
We consider minimizing a differentiable, possibly nonconvex function
The optimization problem is
Our assumptions:
Assumption 1 (Smoothness). The function
Assumption 2 (Polyak–Łojasiewicz inequality and
initial gap). There exists
Assumption 3 (Blockwise affine oracle drift). There
are fixed real sequences
After the allotted oracle calls, the output
Results
Differentiable
| Result | Oracle complexity | Novelty | Limitations |
|---|---|---|---|
| (1) DriftCorrectedGD (Ours) (review) | |||
| (2) Forward-difference GD, derived bound (Berahas et al. 2022; Friedlander and Schmidt 2012); Thm. 2.1 and the PL form of Lemma 2.1 | (1): Matches known rate;
formalizes the PL guarantee. Scope: permits arbitrary affine drift
within exactly aligned |
(1): One extra value query per iteration, including on the drift-free restriction. | |
| (3) TOBYQA (Yao and Xie 2026), v2, §3.2, affine-drift invariance | Gradient-recovery guarantee for |
(1): Scope extends global affine drift to arbitrary jumps between aligned blocks; affine-drift cancellation itself is already known. | |
| (4) TOBYQA (Yao and Xie 2026), v2, §4.4, expected stationarity | Expected hitting time for |
(1): Deterministic objective-gap guarantee under PL, instead of expected stationarity; no identical-output speedup asserted. | (1): Needs PL and |
Abbr: PL: Polyak–Łojasiewicz inequality;