Hessian Estimation via Stein’s Identity in Black-Box Problems

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

Abstract

When only the noisy zeroth-order (ZO) oracle is available, stochastic approximation algorithms are popular for estimating the root of the multivariate gradient equation. Inspired by Stein’s identity, this work establishes a novel Hessian approximation scheme. We compare it with second-order si- multaneous perturbation stochastic approximation (2SPSA) algorithm (Spall, 2000). On the basis of the almost sure convergence guarantee with the same convergence rate, 2SPSA requires four ZO queries, while ours requires three instead. Moreover, 2SPSA requires two statistically independent perturbations and two differencing stepsizes, while ours requires generating one perturbation vec- tor and tuning one differencing stepsize only. Besides, the weighting mechanism for the Hessian estimate is generalized and the smoothness restriction on the loss function is relaxed compared to 2SPSA. Finally, we present numerical support for the reduced per-iteration ZO query complexity.

Cite this Paper

BibTeX
@InProceedings{pmlr-v145-zhu22c, title = {Hessian Estimation via Stein’s Identity in Black-Box Problems}, author = {Zhu, Jingyi}, booktitle = {Proceedings of the 2nd Mathematical and Scientific Machine Learning Conference}, pages = {1161--1178}, 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/zhu22c/zhu22c.pdf}, url = {https://proceedings.mlr.press/v145/zhu22c.html}, abstract = { When only the noisy zeroth-order (ZO) oracle is available, stochastic approximation algorithms are popular for estimating the root of the multivariate gradient equation. Inspired by Stein’s identity, this work establishes a novel Hessian approximation scheme. We compare it with second-order si- multaneous perturbation stochastic approximation (2SPSA) algorithm (Spall, 2000). On the basis of the almost sure convergence guarantee with the same convergence rate, 2SPSA requires four ZO queries, while ours requires three instead. Moreover, 2SPSA requires two statistically independent perturbations and two differencing stepsizes, while ours requires generating one perturbation vec- tor and tuning one differencing stepsize only. Besides, the weighting mechanism for the Hessian estimate is generalized and the smoothness restriction on the loss function is relaxed compared to 2SPSA. Finally, we present numerical support for the reduced per-iteration ZO query complexity. } }
Endnote
%0 Conference Paper %T Hessian Estimation via Stein’s Identity in Black-Box Problems %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-zhu22c %I PMLR %P 1161--1178 %U https://proceedings.mlr.press/v145/zhu22c.html %V 145 %X When only the noisy zeroth-order (ZO) oracle is available, stochastic approximation algorithms are popular for estimating the root of the multivariate gradient equation. Inspired by Stein’s identity, this work establishes a novel Hessian approximation scheme. We compare it with second-order si- multaneous perturbation stochastic approximation (2SPSA) algorithm (Spall, 2000). On the basis of the almost sure convergence guarantee with the same convergence rate, 2SPSA requires four ZO queries, while ours requires three instead. Moreover, 2SPSA requires two statistically independent perturbations and two differencing stepsizes, while ours requires generating one perturbation vec- tor and tuning one differencing stepsize only. Besides, the weighting mechanism for the Hessian estimate is generalized and the smoothness restriction on the loss function is relaxed compared to 2SPSA. Finally, we present numerical support for the reduced per-iteration ZO query complexity.
APA
Zhu, J.. (2022). Hessian Estimation via Stein’s Identity in Black-Box Problems. Proceedings of the 2nd Mathematical and Scientific Machine Learning Conference, in Proceedings of Machine Learning Research 145:1161-1178 Available from https://proceedings.mlr.press/v145/zhu22c.html.

Related Material