Deterministic gradient estimation improves zeroth-order optimization efficiency
Spherical-Design Oracles for Zeroth-Order Optimisation: Deterministic, Variance-Free Gradient Estimation
Computer Science and Game Theory
Summary
Optimizing functions without knowing their internal details is often done by guessing the direction to improve. Usually, these guesses rely on random directions, which adds noise and slows down progress. The authors propose a method that uses a special set of fixed directions, called spherical t-designs, that perfectly average certain polynomial behaviors. This deterministic approach removes randomness from the gradient estimates and reduces errors, leading to better and faster optimization in practice.
What this means in practice
- •For machine learning engineers: Improve black-box model tuning by reliably estimating gradients without random noise for more stable training.
- •For control system developers: Use deterministic gradient estimates in controller optimization where measurement noise hinders random-direction methods.
Authors
Amir Ali Farzin, Yuen-Man Pun, Philipp Braun, Iman Shames
Abstract
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 $t$-design, a finite point set that integrates every polynomial of degree at most $t$ 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.