← All setups

Gradient-Only Generalized Quasar Minimization

Descriptions may be stale. Consult the linked Lean sources.

Gradient-Only Generalized Quasar Minimization

We consider minimizing a continuously differentiable function f:E→R on a finite-dimensional real Hilbert space E. The function f is (L0,L1)-smooth, with L0>0 and L1≥0, and is γ-quasar-convex relative to a global minimizer x⋆, meaning γ(f(x)−f(x⋆))≤⟨∇f(x),x−x⋆⟩ for every x∈E, where 0<γ≤1. A given starting point x0∈E has bounded distance and objective gap to this minimizer. The oracle returns ∇f(x) at x. For ε>0 and δ∈(0,1), the goal is an output x¯∈E with P{f(x¯)−f(x⋆)>ε}≤δ, where P is the law of the algorithm’s randomness.

The optimization problem is minx∈Ef(x). Write ⟨⋅,⋅⟩ for the inner product on E and ∥⋅∥ for its induced norm. Let R>0 and Δ>0 denote the initial distance and objective-gap bounds. The algorithm receives E, L0, L1, R, Δ, x0, γ, ε, and δ.

Our assumptions:

Assumption 1 (Generalized smoothness). The function f is Fréchet differentiable everywhere, and ∇f:E→E is continuous. For every x,y∈E and M∈R, the segment bound ∥∇f(x+θ(y−x))∥≤Mfor every θ∈[0,1] implies ∥∇f(x)−∇f(y)∥≤(L0+L1M)∥x−y∥.

Assumption 2 (Quasar convexity and initialization). There exists x⋆∈E such that f(x⋆)≤f(x)for every x∈E,∥x0−x⋆∥≤R,f(x0)−f(x⋆)≤Δ. Relative to this same minimizer, the quasar-convexity condition is γ(f(x)−f(x⋆))≤⟨∇f(x),x−x⋆⟩for every x∈E.

Queries may be made at any point of E. After the allotted gradient calls, the output must satisfy the failure-probability bound P{f(x¯)−f(x⋆)>ε}≤δ.

Results

A finite-dimensional real Hilbert space; continuously differentiable f with ∥∇f(x)−∇f(y)∥≤(L0+L1supz∈[x,y]∥∇f(z)∥)∥x−y∥. An attained minimizer x⋆ satisfies ∥x0−x⋆∥≤R, f(x0)−f(x⋆)≤Δ, and γ(f(x)−f(x⋆))≤⟨∇f(x),x−x⋆⟩ for all x. Here L0,R,Δ,ε>0, L1≥0, 0<γ≤1, 0<δ<1. Exact gradients are available; all parameters are public. Target: P{f(yK)−f(x⋆)>ε}≤δ, with P the algorithm’s randomization law.

Gradient-only quasar optimization: GradientOnlyGeneralizedQuasar.
Result Oracle complexity Novelty Limitations
(1) GradientOnlyQuasarHighProbability (Ours) (⋆⋆⋆) (review) O(hγ[1+T+L1Rℓ]) gradients
(2) (Wang and Wibisono 2023), Cor. 1 O(γ−1T/δ+δ−1) gradients; L1=0. (1): at T≥1, confidence saving at least order δ−1/2/h against this proved bound. Scope: allows L1>0. (1): substantially larger numerical constant.
(3) (Hinder et al. 2020), Thm. 2 O(1+γ−1Tlog+⁡(T/γ)) value and gradient calls; deterministic, L1=0. (1): no values or search; fewer calls when T≥1 and h≪log+⁡(T/γ). Scope: allows L1>0. (1): probabilistic instead of deterministic; more calls when h≫log+⁡(T/γ), T≥1.
(4) GD, (Jin 2020), derived from (12) O(1+T/γ) gradients; deterministic, L1=0, step 1/(2L0). (1): saving T/h when T≥1, h≪T. Scope: allows L1>0. (1): randomized; loses deterministic accuracy; more calls when h≫T, T≥1.
(5) (Kovalev 2026), Thm. 11; derived bound O((L1R)4γ6a+[(L1R)3γ2+L02R2γ2L12ε2δ2]b) gradients after Markov; L1R≳1. (1): logarithmic confidence instead of δ−2; ε−1/2 instead of ε−2 for fixed other parameters. (1): requires smoothness and exact gradients; (5) also covers nonsmooth stochastic objectives.
(6) (LongTails, n.d.), GeneralizedAcceleratedConvex O(1+T+[1+(L1R)2/3]ℓ) gradients; convex, differentiable gradient, γ=1; almost-sure accuracy. (1): scope extends to nonconvex quasar objectives and merely continuous gradients. (1): confidence factor h; L1R versus (L1R)2/3 for L1R≥1; loses almost-sure accuracy.

Abbr: T=L0R2/ε, h=1+log⁡(1/δ), ℓ=1+log⁡(1+Δ/ε), log+⁡u=max{1,log⁡u}. In (5), a=1+log⁡(1+γΔL12/L0) and b=1+log⁡(1+L0/(γL12εδ)); the gradient-growth parameters are G0≍L0/L1, G1≍L1.

Hinder, Oliver, Aaron Sidford, and Nimit Sohoni. 2020. “Near-Optimal Methods for Minimizing Star-Convex Functions and Beyond.” Proceedings of Thirty Third Conference on Learning Theory, Proceedings of machine learning research, vol. 125: 1894–938. https://proceedings.mlr.press/v125/hinder20a.html.
Jin, Jikai. 2020. On the Convergence of First Order Methods for Quasar-Convex Optimization. https://doi.org/10.48550/arXiv.2010.04937.
Kovalev, Dmitry. 2026. Stochastic Non-Smooth Convex Optimization with Unbounded Gradients. https://doi.org/10.48550/arXiv.2605.15522.
LongTails: GeneralizedAcceleratedConvex. n.d. Repository theorem. https://github.com/k3nfalt/longtails/blob/main/LongTails/Theorems/GeneralizedAcceleratedConvex.lean.
Wang, Jun-Kun, and Andre Wibisono. 2023. Continuized Acceleration for Quasar Convex Functions in Non-Convex Optimization. https://doi.org/10.48550/arXiv.2302.07851.

Lean setup