mlsanityData to 14 Oct 2026

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

arXiv 2505.02281 ↗First posted 4 May 2025math.OC cs.AI cs.LGcited by 3

Not on the map. Why?

Abstract (arXiv)

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.

Key facts. Cited by 3 papers in the map (data through 14 Oct 2026). Builds on 23 of its 40 references that are in the map. First posted on arXiv 4 May 2025.

Builds on

23 of 40 references.

References · 23

  1. 2014Explaining and Harnessing Adversarial Examplescited by 7,364
  2. 2016Linear Convergence of Gradient and Proximal-Gradient Methods Under the Polyak-Lojasiewicz Conditioncited by 539
  3. 2016The CMA Evolution Strategy: A Tutorialcited by 377
  4. 2020On the Global Convergence Rates of Softmax Policy Gradient Methodscited by 264
  5. 2020Fast Global Convergence of Natural Policy Gradient Methods with Entropy Regularizationcited by 176
  6. 2013Mini-batch Stochastic Approximation Methods for Nonconvex Stochastic Composite Optimizationcited by 143
  7. 2018Zeroth-Order Stochastic Variance Reduction for Nonconvex Optimizationcited by 111
  8. 2016Identity Matters in Deep Learningcited by 109
  9. 2016Gradient Descent Learns Linear Dynamical Systemscited by 79
  10. 2023DeepZero: Scaling up Zeroth-Order Optimization for Deep Model Trainingcited by 76
  11. 2019An ADMM Based Framework for AutoML Pipeline Configurationcited by 47
  12. 2020Accelerated Zeroth-Order and First-Order Momentum Methods from Mini to Minimax Optimizationcited by 40
11 more
  1. 2019SGD Converges to Global Minimum in Deep Learning via Star-convex Pathcited by 39
  2. 2019Near-Optimal Methods for Minimizing Star-Convex Functions and Beyondcited by 36
  3. 2024Exploring Neural Network Landscapes: Star-Shaped and Geodesic Connectivitycited by 9
  4. 2020On The Convergence of First Order Methods for Quasar-Convex Optimizationcited by 8
  5. 2021Direct-Search for a Class of Stochastic Min-Max Problemscited by 7
  6. 2023Continuized Acceleration for Quasar Convex Functions in Non-Convex Optimizationcited by 6
  7. 2023Accelerated Stochastic Optimization Methods under Quasar-convexitycited by 6
  8. 2022A Zeroth-order Proximal Stochastic Gradient Method for Weakly Convex Stochastic Optimizationcited by 5
  9. 2025Min-Max Optimisation for Nonconvex-Nonconcave Functions Using a Random Zeroth-Order Extragradient Algorithmcited by 5
  10. 2024Minimisation of Polyak-Lojasewicz Functions Using Random Zeroth-Order Oraclescited by 4
  11. 2024Study of the behaviour of Nesterov Accelerated Gradient in a non convex setting: the strongly quasar convex casecited by 3

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2025: 1; 2026: 2.

3 papers.

  1. 2025Minimisation of Submodular Functions Using Gaussian Zeroth-Order Random Oraclescited by 2
  2. 2026Solving the Offline and Online Min-Max Problem of Non-smooth Submodular-Concave Functions: A Zeroth-Order Approachcited by 2
  3. 2026From Cursed to Competitive: Closing the ZO-FO Gap via Input-to-State Stabilitycited by 0