Hessian-Aided Random Perturbation (HARP) Using Noisy Zeroth-Order Queries
Proceedings of the 2nd Mathematical and Scientific Machine Learning Conference, PMLR 145:1137-1160, 2022.
In stochastic optimization problems using noisy zeroth-order (ZO) oracles only, the randomized counterpart of Kiefer-Wolfowitz-type method is widely used to estimate the gradient. Existing al- gorithms generate the randomized perturbation from a zero-mean unit-covariance distribution. In contrast, this work considers the generalization where the perturbations may have non-isotropic covariance matrix constructed from the ZO queries. We propose to feed the Hessian-inverse ap- proximation into the covariance of the random perturbation, so it is dubbed as Hessian-Aided Ran- dom Perturbation (HARP). HARP collects two or more (depending on the specific estimator form) zeroth-order queries per iteration to form approximations for both the gradient and the Hessian. We show the almost surely convergence and derive the convergence rate for HARP under stan- dard assumptions. We demonstrate, with theoretical guarantees and numerical experiments, that HARP is less sensitive to ill-conditioning and more query-efficient than other gradient approxima- tion schemes with isotropic-covariance random perturbation