← All setups

High-Dimensional Strong Quasar Minimization

Descriptions may be stale. Consult the linked Lean sources.

High-Dimensional Strong Quasar Minimization

We consider minimizing a differentiable, possibly nonconvex function f:Rd→R with an L-Lipschitz gradient, where d is the dimension and L>0. The function is strongly quasar-convex toward a global minimizer x⋆, with parameters μ>0 and 0<γ≤1/256. A given starting point x0∈Rd satisfies f(x0)−f(x⋆)≤Δ, where Δ≥0. The oracle returns ∇f(x) at x. For ε>0, the goal is an output x¯∈Rd with integrable objective gap satisfying EP[f(x¯)−f(x⋆)]≤ε, where P is the law of the algorithm’s randomness.

The optimization problem is minx∈Rdf(x). We use the Euclidean inner product ⟨⋅,⋅⟩ and its induced norm ∥⋅∥. The algorithm receives d, L, x0, μ, γ, Δ, and ε.

Our assumptions:

Assumption 1 (Parameter and dimension regime). The dimension d is a nonnegative integer. In addition to the parameter ranges above, define κ=L/μ and require 870400μ≤L,4μ≤γ2L,1000γκε≤Δ,(κγ)5(Δ1000γκε)3≤d.

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

Assumption 3 (Strong quasar convexity and initial gap). There exists a global minimizer x⋆∈Rd satisfying the stated initial objective-gap bound such that, for every x∈Rd, f(x)−f(x⋆)≤1γ⟨∇f(x),x−x⋆⟩−μ2∥x−x⋆∥2.

Queries may be made at any point of Rd. After the allotted oracle calls, the output must have an integrable objective gap under P and satisfy EP[f(x¯)−f(x⋆)]≤ε.

Results

Differentiable f:Rd→R has L-Lipschitz gradient and a global minimizer x⋆ satisfying f(x⋆)≥f(x)+γ−1⟨∇f(x),x⋆−x⟩+μ2∥x−x⋆∥2 for every x, with f(x0)−f(x⋆)≤Δ. Parameters satisfy L,μ,ε>0, 0<γ≤1/256, κ≥870400, γ2κ≥4, Δ≥1000γκε, and d≥(κ/γ)5[Δ/(1000γκε)]3. The oracle returns exact gradients. The target is integrable expected gap ∫[f(xout(ω))−f(x⋆)]dP(ω)≤ε, with P the algorithm’s seed law. Under this same model, (1) and (2) match up to constants when ε≤Δ/(106γκ); for q≥2 otherwise, their ratio is at most O(log⁡κ).

Necessary and sufficient exact-gradient budgets for HighDimensionalStrongQuasar.
Result Oracle complexity Novelty Limitations
Lower bound (necessary)
(1) HighDimensionalStrongQuasarLowerBound (Ours) (⋆⋆⋆) (review)
Ω(κγlog⁡Δ1000γκε) gradient calls, q≥2. Arbitrary randomized algorithms and outputs.
Upper bound (sufficient)
(2) HighDimensionalStrongQuasarUpperBound (Ours) (review)
O(κγlog(1+Δγε)) gradient calls; fixed-call expected gap.
Prior lower bound (necessary)
(3) (Hinder et al. 2023), Remark 4 proof, App. E.3
Ω(max{κγ,κγlog⁡Δε}) gradient calls; deterministic algorithms. The proof gives this bound; the remark states a stronger product. (1): randomized hardness; necessary budget gains Θ(min{γ−1/2,log⁡(Δ/(γε))}) when ε≤Δ/(106γκ). For γ=κ−1/4, ε=Δκ−c, c≥2, gain Θ(min{κ1/8,clog⁡κ}). (1) needs the stated small-γ, large-κ, high-dimension regime; constants about 106 looser.

Abbr: κ=L/μ; Δ is the initial-gap bound; ε is target accuracy; q=Δ/(1000γκε); P is the seed probability measure. In (7), c0>1 is a confidence parameter and the corollary uses c=1/2. In (6), Tk is the kth unit-rate Poisson jump time and V=f(x0)−f(x⋆)+μ∥x0−x⋆∥2/2≤(1+γ−1)Δ.

HighDimensionalStrongQuasar (continued).
Result Oracle complexity Novelty Limitations
Prior upper bounds (sufficient)
(4) (LongTails, n.d.), δ=0
O(κγlog(1+Δγε)) gradient calls on the common setup; identical algorithm and budget. (2): Matches known rate. (2) restricts the earlier finite-dimensional, relative-error result to exact gradients and the stated parameter/dimension regime.
(5) (Hinder et al. 2023), Theorem 1 O(κγlog⁡κγlog(1+Δγε)) total function and gradient evaluations; deterministic gap ≤ε. (2) removes log⁡(κ/γ) in cost for the shared expected-gap target and needs no function values; already achieved by (4). (2) gives only expected accuracy, needs L and exact γ rather than a lower bound, and imposes the stated regime.
(6) (Wang and Wibisono 2023), Theorem 2 O(κγlog(1+Δγε)) gradient-call scale; time-weighted guarantee E[eγTk/κ(f(xk)−f(x⋆))]≤V. (2) matches the rate scale; fixed-call expected gap already appears in (4). (2) has larger constants and the stated parameter/dimension restrictions.
(7) (Wang and Wibisono 2023), Corollary 2 O(κγlog(1+c0Δγε)) gradient calls; gap ≤ε with probability at least 1−4/k−1/c0, for c0>1 and k calls. (2) matches the rate scale at fixed confidence, with fixed-call expected accuracy. (2) does not supply this explicit probability guarantee; its parameter/dimension regime is narrower.

Abbr: κ=L/μ; Δ is the initial-gap bound; ε is target accuracy; q=Δ/(1000γκε); P is the seed probability measure. In (7), c0>1 is a confidence parameter and the corollary uses c=1/2. In (6), Tk is the kth unit-rate Poisson jump time and V=f(x0)−f(x⋆)+μ∥x0−x⋆∥2/2≤(1+γ−1)Δ.

Hinder, Oliver, Aaron Sidford, and Nimit S. Sohoni. 2023. Near-Optimal Methods for Minimizing Star-Convex Functions and Beyond. https://doi.org/10.48550/arXiv.1906.11985.
LongTails: AcceleratedRelativeQuasar. n.d. Repository convergence theorem and oracle budget. https://github.com/k3nfalt/longtails/blob/main/LongTails/Theorems/AcceleratedRelativeQuasar.lean.
Wang, Jun-Kun, and Andre Wibisono. 2023. “Continuized Acceleration for Quasar Convex Functions in Non-Convex Optimization.” International Conference on Learning Representations. https://doi.org/10.48550/arXiv.2302.07851.

Lean setup