pipette
ESEspañol

Spherical-Design Oracles for Zeroth-Order Optimisation: Deterministic, Variance-Free Gradient Estimation

Amir Ali Farzin, Yuen-Man Pun, Philipp Braun, Iman Shames

Preprint

In the authors' words

In this work, we develop a zeroth-order (ZO) method that estimates the gradient with minimal bias and variance. Instead of the random directions often used in the ZO literature, we consider central differences with directions given by a fixed spherical -design, a finite point set that integrates every polynomial of degree at most exactly. The oracle is deterministic and thus does not induce any variance.We also propose a general finite difference method in the higher-order-smoothness regime and show the bias of both finite difference methods. We then show the convergence of the proposed ZO method via the input-to-state stability concept. Numerical experiments show the superiority of our proposed method over the existing random ZO methods.

Main resultThe abstract does not state a limitation.

Appeared: Tuesday, October 20. arXiv. Preprint, not yet peer-reviewed.