← All setups

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 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.

Results

Differentiable f:Rd→R, d≥1, has an L-Lipschitz gradient and a global minimizer x⋆, with 0<μ≤L, 2μ(f(x)−f(x⋆))≤∥∇f(x)∥2, and f(x0)−f(x⋆)≤Δ. Query k returns f(x)+at+btj+ek(x), where t=⌊k/(d+2)⌋, j=kmod(d+2), at,bt are arbitrary, and |ek(x)|≤ν. Assume Δ,ν≥0, ε>0, and 4dLν≤με. Target: f(xK)−f(x⋆)≤ε almost surely under the oracle law; the constructed deterministic method satisfies it for every outcome.

Value-oracle optimization with aligned affine drift: AffineDriftPL.
Result Oracle complexity Novelty Limitations
(1) DriftCorrectedGD (Ours) (review) O(d[1+Lμlog⁡(1+Δε)]) value calls.
(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 O(d[1+Lμlog⁡(1+Δε)]) value calls. Special case: at=bt=0; 4dLν≤με. (1): Matches known rate; formalizes the PL guarantee. Scope: permits arbitrary affine drift within exactly aligned (d+2)-query blocks. (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 f(x)+βk+ek(x); full-rank augmented interpolation matrix. No objective-gap budget. (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 ∥∇f(x)∥≤τ for τ≥Cκegmax{δhi,σ/δlo}. Assumes probabilistically fully-linear models, bounded sample radii, controlled acceptance bias, sub-Gaussian innovations, and regularization confinement. Rates not comparable. (1): Deterministic objective-gap guarantee under PL, instead of expected stationarity; no identical-output speedup asserted. (1): Needs PL and 4dLν≤με; no coverage of general nonconvex objectives or C2 nonlinear drift with controlled residual bias.

Abbr: PL: Polyak–Łojasiewicz inequality; d: dimension; L: gradient Lipschitz constant; μ: PL constant; Δ: initial objective-gap bound; ν: value-error bound; ε: objective accuracy; K: iteration count; τ: gradient-norm tolerance; β: global drift slope. Costs count individual value queries. In (4), δlo,δhi bound sample radii, σ is the noise scale, κeg is the model-error constant, and C is universal.

Berahas, Albert S., Liyuan Cao, Krzysztof Choromanski, and Katya Scheinberg. 2022. “A Theoretical and Empirical Comparison of Gradient Approximations in Derivative-Free Optimization.” Foundations of Computational Mathematics 22 (2): 507–60. https://doi.org/10.1007/s10208-021-09513-z.
Friedlander, Michael P., and Mark Schmidt. 2012. “Hybrid Deterministic-Stochastic Methods for Data Fitting.” SIAM Journal on Scientific Computing 34 (3): A1380–405. https://doi.org/10.1137/110830629.
Yao, Haoyu, and Pengcheng Xie. 2026. TOBYQA: A Time-Augmented Model-Based Method for Derivative-Free Optimization Under Noise and Temporal Drift. https://doi.org/10.48550/arXiv.2608.18124.

Lean setup