论文标题
黑森逆近似作为黑盒问题中随机扰动的协方差
Hessian Inverse Approximation as Covariance for Random Perturbation in Black-Box Problems
论文作者
论文摘要
在仅使用嘈杂的零阶（ZO）orac的随机优化问题中，Kiefer-Wolfowitz-type方法的随机对应物被广泛用于估计梯度。现有算法从零均值和单位协方差分布产生随机扰动。相比之下，这项工作考虑了扰动具有从ZO查询历史构建的可能非身份协方差的概括。我们建议将二阶近似值送入随机扰动的协方差矩阵中，因此将其称为Hessian-Aid随机扰动（HARP）。 HARP每次迭代收集四个零订单查询，以形成梯度和Hessian的近似值。我们显示了（几乎肯定是肯定的）收敛性，并在轻度假设下得出了竖琴的收敛速率。我们通过理论保证和数值实验证明，与其他随机扰动具有身份协方差的梯度近似方案相比，HAR对不良条件和查询效率更高的敏感性不那么敏感。
In stochastic optimization problems using noisy zeroth-order (ZO) oracles only, the randomized counterpart of the Kiefer-Wolfowitz-type method is widely used to estimate the gradient. Existing algorithms generate randomized perturbation from a zero-mean and unit-covariance distribution. In contrast, this work considers the generalization where the perturbations have a possibly non-identity covariance constructed from the history of the ZO queries. We propose to feed the second-order approximation into the covariance matrix of the random perturbation, so it is dubbed as Hessian-aided random perturbation (HARP). HARP collects four zeroth-order queries per iteration to form approximations for both the gradient and the Hessian. We show the convergence (in an almost surely sense) and derive the convergence rate for HARP under mild assumptions. We demonstrate, with theoretical guarantees and numerical experiments, that HARP is less sensitive to ill-conditioning and more query-efficient than other gradient approximation schemes whose random perturbation has an identity covariance.
