Hessian-Aided Random Perturbation (HARP) Using Noisy Zeroth-Order Queries

Jingyi Zhu
Proceedings of the 2nd Mathematical and Scientific Machine Learning Conference, PMLR 145:1137-1160, 2022.

Abstract

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

Cite this Paper

BibTeX
@InProceedings{pmlr-v145-zhu22b, title = {Hessian-Aided Random Perturbation (HARP) Using Noisy Zeroth-Order Queries}, author = {Zhu, Jingyi}, booktitle = {Proceedings of the 2nd Mathematical and Scientific Machine Learning Conference}, pages = {1137--1160}, year = {2022}, editor = {Bruna, Joan and Hesthaven, Jan and Zdeborova, Lenka}, volume = {145}, series = {Proceedings of Machine Learning Research}, month = {16--19 Aug}, publisher = {PMLR}, pdf = {https://proceedings.mlr.press/v145/zhu22b/zhu22b.pdf}, url = {https://proceedings.mlr.press/v145/zhu22b.html}, abstract = {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 } }
Endnote
%0 Conference Paper %T Hessian-Aided Random Perturbation (HARP) Using Noisy Zeroth-Order Queries %A Jingyi Zhu %B Proceedings of the 2nd Mathematical and Scientific Machine Learning Conference %C Proceedings of Machine Learning Research %D 2022 %E Joan Bruna %E Jan Hesthaven %E Lenka Zdeborova %F pmlr-v145-zhu22b %I PMLR %P 1137--1160 %U https://proceedings.mlr.press/v145/zhu22b.html %V 145 %X 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
APA
Zhu, J.. (2022). Hessian-Aided Random Perturbation (HARP) Using Noisy Zeroth-Order Queries. Proceedings of the 2nd Mathematical and Scientific Machine Learning Conference, in Proceedings of Machine Learning Research 145:1137-1160 Available from https://proceedings.mlr.press/v145/zhu22b.html.

Related Material