论文标题
零订单随机子空间牛顿方法
Zeroth-Order Randomized Subspace Newton Methods
论文作者
论文摘要
零阶方法已成为解决我们仅访问功能评估的问题的重要工具。但是，仅使用梯度近似值的零级方法比解决n维问题的经典一阶方法慢$ n $倍。为了加速收敛速率，本文提出了零订单随机子空间牛顿（ZO-RSN）方法，该方法通过随机素描和有限的差异来估计梯度和黑森的投影。这使我们能够以较小的计算成本计算牛顿的步骤。我们证明，ZO-RSN比现有的零序订购方法可以达到较低的迭代复杂性，以实现强烈凸出问题。我们的数值实验表明，ZO-RSN可以比最先进的Hessian-Hessian-Awawawawawawawawawawawaweawawaweawaweawawawawaweawawaweawawawawaweawawawaweawawawawawawawawawawawawawawawawawawawawaweawawawawawawe box攻击。
Zeroth-order methods have become important tools for solving problems where we have access only to function evaluations. However, the zeroth-order methods only using gradient approximations are $n$ times slower than classical first-order methods for solving n-dimensional problems. To accelerate the convergence rate, this paper proposes the zeroth order randomized subspace Newton (ZO-RSN) method, which estimates projections of the gradient and Hessian by random sketching and finite differences. This allows us to compute the Newton step in a lower dimensional subspace, with small computational costs. We prove that ZO-RSN can attain lower iteration complexity than existing zeroth order methods for strongly convex problems. Our numerical experiments show that ZO-RSN can perform black-box attacks under a more restrictive limit on the number of function queries than the state-of-the-art Hessian-aware zeroth-order method.
