Minimisation of Quasar-Convex Functions Using Random Zeroth-Order Oracles
Fuente:
arXiv
Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866917235739590656 |
|---|---|
| author | Farzin, Amir Ali Pun, Yuen-Man Braun, Philipp Shames, Iman |
| author_facet | Farzin, Amir Ali Pun, Yuen-Man Braun, Philipp Shames, Iman |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2505_02281 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Minimisation of Quasar-Convex Functions Using Random Zeroth-Order Oracles Farzin, Amir Ali Pun, Yuen-Man Braun, Philipp Shames, Iman Optimization and Control Artificial Intelligence Machine Learning Numerical Analysis 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. |
| title | Minimisation of Quasar-Convex Functions Using Random Zeroth-Order Oracles |
| topic | Optimization and Control Artificial Intelligence Machine Learning Numerical Analysis |
| url | https://arxiv.org/abs/2505.02281 |