Minimisation of Quasar-Convex Functions Using Random Zeroth-Order Oracles

[Submitted on 4 May 2025 (v1), last revised 22 Jun 2026 (this version, v3)]

View PDF HTML (experimental)

Abstract:This paper explores the performance of a random Gaussian smoothing zeroth-order (ZO) scheme for minimising quasar-convex (QC) and strongly quasar-convex (SQC) functions in both unconstrained and constrained settings. For the unconstrained problem, we establish the ZO algorithm’s convergence to a global minimum along with its complexity when applied to both QC and SQC functions. For the constrained problem, we introduce the new notion of proximal-quasar-convexity and prove analogous results to the unconstrained case. Specifically, we derive complexity bounds and prove convergence of the algorithm to a neighbourhood of a global minimum whose size can be controlled under a variance reduction scheme. Beyond the theoretical guarantees, we demonstrate the practical implications of our results on several machine learning problems where quasar-convexity naturally arises, including linear dynamical system identification and generalised linear models.

Submission history

From: Amir Ali Farzin Mr. [view email]
[v1] Sun, 4 May 2025 22:43:57 UTC (9,757 KB)
[v2] Fri, 30 Jan 2026 23:23:07 UTC (15,852 KB)
[v3] Mon, 22 Jun 2026 23:48:14 UTC (16,079 KB)