← All setups

PL Minimization with Relative Discrepancy

Descriptions may be stale. Consult the linked Lean sources.

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.

Results

On a real Hilbert space, f is differentiable with L-Lipschitz gradient, attains its minimum at x⋆, and satisfies 2μ(f(x)−f(x⋆))≤∥∇f(x)∥2 for every x. Assume 0<μ≤L, D,Δ≥0, ε>0, and f(x0)−f(x⋆)≤Δ. Deterministic replies satisfy ∥∑i=0n−1(gs+i(x)−∇f(x))∥≤D∥∇f(x)∥ for all s,n,x. Target: f(xout)−f(x⋆)≤ε almost surely under any execution law; (1) attains it for every seed.

Relative temporal discrepancy under the PL condition: RelativeDiscrepancyPL.
Result Oracle complexity Novelty Limitations
(1) DiscrepancyBatchedGD (Ours) (review) O((1+D)[1+κlog⁡(1+Δ/ε)]) replies.
(2) Derived bound: fixed-step GD (Puchinin and Stonyakin 2023), §3, (9)–(11) O((1+D)[1+κlog⁡(1+Δ/ε)]) replies; batches max{1,⌈3D⌉}, relative error ≤1/3. (1): Matches known rate; Lean formalization on Hilbert spaces. The inner-product argument of (2) extends from Rd and permits time-varying replies.
(3) Exact GD (Karimi et al. 2020), Thm. 2.1; D=0, E=Rd O(1+κlog⁡(1+Δ/ε)) exact-gradient calls. (1): Matches known rate at D=0. (1): Larger leading iteration constant at D=0.
(4) Derived bound: RE-AGM (Vasin et al. 2025), Thm. 4; strongly convex, E=Rd O((κ+Dκ)log⁡(1+κΔ/ε)) replies, 0<ε<Δ. Batches max{1,⌈D/α⌉}, α=c/κ, 0<c<(2−1)/(182); assumes batch averages define a fixed relative-error oracle. (1): Scope: PL without strong convexity. On (4)'s restriction, D≥1: matches Dκ dependence, with log⁡(1+Δ/ε) instead of log⁡(1+κΔ/ε). Updates need no μ; stopping still does. On (4)'s restriction, D≤κ−1/2: (1) costs O(κlog⁡(1+Δ/ε)), versus O(κlog⁡(1+κΔ/ε)).

Abbr: κ=L/μ; Δ bounds the initial objective gap; D is the relative window-discrepancy bound; ε is the target objective gap; α is relative gradient error. Costs count individual replies, including all batch members. A fixed batch-average oracle returns the same averaged vector at a point across batches.

Karimi, Hamed, Julie Nutini, and Mark Schmidt. 2020. Linear Convergence of Gradient and Proximal-Gradient Methods Under the Polyak-Łojasiewicz Condition. arXiv:1608.04636v4. https://doi.org/10.48550/arXiv.1608.04636.
Puchinin, Sergei M., and Fedor S. Stonyakin. 2023. Gradient-Type Method for Optimization Problems with Polyak-Lojasiewicz Condition: Relative Inexactness in Gradient and Adaptive Parameters Setting. arXiv:2307.14101v3. https://doi.org/10.48550/arXiv.2307.14101.
Vasin, Artem, Valery Krivchenko, Dmitry Kovalev, et al. 2025. On Solving Minimization and Min-Max Problems by First-Order Methods with Relative Error in Gradients. arXiv:2503.06628v3. https://doi.org/10.48550/arXiv.2503.06628.

Lean setup