Minimisation of Quasar-Convex Functions Using Random Zeroth-Order Oracles
This work addresses optimization problems for functions with specific convexity properties, offering incremental improvements in zeroth-order methods for scenarios where gradients are unavailable.
This study tackles the minimization of quasar-convex and strongly quasar-convex functions using a random zeroth-order algorithm, establishing convergence and complexity bounds for both unconstrained and constrained settings, with theoretical results illustrated through machine learning problems where the method sometimes outperforms gradient descent.
This study 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 show the complexity bounds and the convergence of the algorithm to a neighbourhood of a global minimum whose size can be controlled under a variance reduction scheme. Theoretical findings are illustrated through investigating the performance of the algorithm applied to a range of problems in machine learning and optimisation. Specifically, we observe scenarios where the ZO method outperforms gradient descent. We provide a possible explanation for this phenomenon.