论文标题
懒惰查询可以减少零订单优化的方差
Lazy Queries Can Reduce Variance in Zeroth-order Optimization
论文作者
论文摘要
应用零订单（ZO）方法的主要挑战是高查询复杂性，尤其是当查询昂贵时。我们提出了一种基于我们称为lazo的自适应懒惰查询的ZO方法的新型梯度估计技术。与经典的单点或两点梯度估计方法不同，Lazo开发了两种替代方法来检查以前迭代中旧查询的有用性，然后自适应地重新恢复它们以构建低变义梯度估计。我们严格地确定，通过明智地重用旧查询，Lazo可以减少随机梯度估计的差异，从而使它不仅节省了每次迭代的查询，而且还为对称的两点方法带来了遗憾。我们评估了Lazo的数值性能，并证明了相对于几种现有的ZO方法的遗憾和查询复杂性，Lazo的低变义属性以及Lazo的性能增长。 Lazo的想法是一般的，可以应用于ZO方法的其他变体。
A major challenge of applying zeroth-order (ZO) methods is the high query complexity, especially when queries are costly. We propose a novel gradient estimation technique for ZO methods based on adaptive lazy queries that we term as LAZO. Different from the classic one-point or two-point gradient estimation methods, LAZO develops two alternative ways to check the usefulness of old queries from previous iterations, and then adaptively reuses them to construct the low-variance gradient estimates. We rigorously establish that through judiciously reusing the old queries, LAZO can reduce the variance of stochastic gradient estimates so that it not only saves queries per iteration but also achieves the regret bound for the symmetric two-point method. We evaluate the numerical performance of LAZO, and demonstrate the low-variance property and the performance gain of LAZO in both regret and query complexity relative to several existing ZO methods. The idea of LAZO is general, and can be applied to other variants of ZO methods.
