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

arXiv:2505.02281 · math.OC, cs.AI, cs.LG, cs.NA, math.NA · Submitted 2025-05-04 · Read on arXiv

math.OC, cs.AI, cs.LG, cs.NA, math.NA

Submitted: 2025-05-04

Updated: 2026-06-22

Journal ref: Transactions on Machine Learning Research, 2026

License: http://creativecommons.org/licenses/by-sa/4.0/

The gist: 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

Terminology

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.

Sources

Related papers