Abstract
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.
Abstract (translated)
这项研究探讨了随机高斯平滑零阶(ZO)方案在无约束和有约束条件下最小化类夸克凸(QC)和强类夸克凸(SQC)函数时的性能。对于无约束问题，我们建立了ZO算法应用于QC和SQC函数时收敛于全局最优解及其复杂度的理论基础。对于有约束问题，我们引入了新的近似-类夸克凸性概念，并证明了与无约束情况类似的结果。具体来说，我们展示了算法在方差减少方案下的复杂度界线以及该算法收敛到一个可以控制大小的全局最优点邻域。 通过研究ZO方法应用于机器学习和优化问题中的性能表现，本文理论发现得到了验证。特别是，在一些场景中，ZO方法的表现优于梯度下降法。对此现象，我们提供了一种可能的解释。
URL
https://arxiv.org/abs/2505.02281
