← All setups

Strong Quasar Minimization with Relative Errors

Descriptions may be stale. Consult the linked Lean sources.

Strong Quasar Minimization with Relative Errors

We consider minimizing a differentiable function f:E→R on a finite-dimensional real Hilbert space E. The function has an L-Lipschitz gradient, with L>0, and is strongly quasar-convex with parameters μ>0 and γ∈(0,1] relative to a global minimizer x⋆. A given point x0∈E satisfies f(x0)−f(x⋆)≤Δ, where Δ≥0. The oracle returns a fixed measurable vector g(x) satisfying ∥g(x)−∇f(x)∥≤δ∥∇f(x)∥, with δ∈[0,1). For ε>0, the goal is an output x¯∈E with integrable objective gap and EP[f(x¯)−f(x⋆)]≤ε, where P is 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 E, L, x0, μ, γ, δ, Δ, and ε.

Our assumptions:

Assumption 1 (Smoothness). The function f is Fréchet differentiable everywhere on E, and ∥∇f(x)−∇f(y)∥≤L∥x−y∥,x,y∈E.

Assumption 2 (Strong quasar-convexity and initial gap). There exists x⋆∈E such that f(x⋆)≤f(x),x∈E,f(x0)−f(x⋆)≤Δ. Relative to this same minimizer, strong quasar-convexity means that, for every x∈E, f(x⋆)≥f(x)+1γ⟨∇f(x),x⋆−x⟩+μ2∥x−x⋆∥2.

Assumption 3 (Relative gradient error). The oracle returns g(x) at any query point x∈E, where g:E→E is a fixed Borel-measurable map satisfying ∥g(x)−∇f(x)∥≤δ∥∇f(x)∥,x∈E.

After the allotted oracle calls, the output must have an integrable objective gap under P and satisfy EP[f(x¯)−f(x⋆)]≤ε.

Results

On a finite-dimensional real Hilbert space with its Borel measurable structure, f has an L-Lipschitz gradient and a minimizer x⋆ satisfying f(x0)−f(x⋆)≤Δ and f(x⋆)≥f(x)+γ−1⟨∇f(x),x⋆−x⟩+μ2∥x−x⋆∥2 for all x. Here L,μ,ε>0, 0<γ≤1, Δ≥0, and 0≤δ<1. Each oracle call returns the same measurable g(x), with ∥g(x)−∇f(x)∥≤δ∥∇f(x)∥. Target: ∫(f(xK(ω))−f(x⋆))dP(ω)≤ε, with integrable gap and P the algorithm’s randomization law. The setup does not restrict the algorithm; (1) constructs a randomized continuized method.

Relative-gradient acceleration under RelativeGradientStrongQuasar.
Result Oracle complexity Novelty Limitations
(1) AcceleratedRelativeQuasar (Ours) (⋆⋆) (review) O([1+κ/(1−δ)γ+δ2κγ2(1−δ)]ℓ) calls; deterministic budget.
(2) Continuized acceleration (Wang and Wibisono 2023), Thm. 2; δ=0. O((1+κ/γ)ℓ) expected gradient calls at fixed continuous time; expected gap ≤ε. (1): Scope extends to fixed relative bias. Retains O((1+κ/γ)ℓ) when δ≤12, δ2≲γ/κ; matches δ=0 rate with fixed-call expected accuracy. (1): Roughly fourfold larger leading constants in the exact-gradient comparison.
(3) Continuized acceleration (Wang and Wibisono 2023), Cor. 2; δ=0. O((1+κ/γ)ℓ) gradient calls for gap ≤ε with fixed success probability 3/4. (1): Extends to δ<1; matches the exact-gradient complexity order for the expected-accuracy target. (1): Expected accuracy instead of the stated probability guarantee.
(4) Restarted CG (Kuruzov and Stonyakin 2026), Thm. 3.3; additionally f(x)−f⋆≥μ2∥x−x⋆∥2. O((1+κ/γ)[1+log⁡(1+Δ/ε)]) calls and exact two-dimensional solves (gradient cost unspecified). Requires ∥g−∇f∥≤δ1, δ12≲γ2με, and ∥g(x^k)∥≥2δ1 at every inner query. (1): On the common exact-gradient, quadratic-growth restriction, removes subspace solves. For nonzero errors, absolute versus relative models make rates noncomparable. (1): Expected instead of deterministic accuracy.
(5) Inexact acceleration (AcceleratedInexactStronglyConvex, n.d.); μ-strong convexity, γ=1, purely relative error.

O([1+κ1−δ+δ2κ1−δ]

⋅[1+log⁡(1+κΔ/ε)]) calls, using R2=2Δ/μ.

(1): Scope extends to nonconvex strongly quasar-convex objectives; matches polynomial dependence on the strongly convex overlap. (1): Requires fixed errors rather than call-dependent errors; expected rather than deterministic accuracy.

Abbr: κ=L/μ; ℓ=1+log⁡(1+Δ/(γε)); f⋆=f(x⋆); R is an initial-distance bound; δ1 is an absolute gradient-error bound; x^k are the inner query points of (4); CG denotes conjugate gradient. The symbol ≲ hides a universal constant, chosen sufficiently small in admissibility conditions.

AcceleratedInexactStronglyConvex: Convergence Theorem in LongTails. n.d. Lean source in the LongTails repository. https://github.com/k3nfalt/longtails/blob/main/LongTails/Theorems/AcceleratedInexactStronglyConvex.lean.
Kuruzov, Ilya, and Fedor Stonyakin. 2026. On Some Versions of Subspace Optimization Methods with Inexact Gradient Information. https://doi.org/10.48550/arXiv.2407.01051.
Wang, Jun-Kun, and Andre Wibisono. 2023. “Continuized Acceleration for Quasar Convex Functions in Non-Convex Optimization.” International Conference on Learning Representations. https://openreview.net/forum?id=yYbhKqdi7Hz.

Lean setup