2025/05/04 by Amir Ali Farzin, Yuen-Man Pun, Farzin, Amir Ali +3 · 3 citations
Computer Science · Engineering · #Advanced Numerical Analysis Techniques #Artificial Intelligence (cs.AI) #Data Management and Algorithms #Digital Image Processing Techniques #FOS: Computer and information sciences #FOS: Mathematics #Machine Learning (cs.LG) #Numerical Analysis (math.NA) #Optimization and Control (math.OC)
paper · pdf · doi:10.48550/arxiv.2505.02281
openalex publication_date 2025/05/04 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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.