论文标题
加速随机无梯度和无投影方法
Accelerated Stochastic Gradient-free and Projection-free Methods
论文作者
论文摘要
在本文中，我们提出了一类加速的随机梯度无梯度和无投影（又称零级弗兰克 - 沃尔夫）方法，以解决约束的随机和有限的和有限的非凸优化。具体而言，我们提出了一种基于蜘蛛/蜘蛛杆的方差减少技术和一种新颖的动量加速技术的加速随机零阶（ACC-SZOFW）方法。此外，在某些温和条件下，我们证明ACC-SZOFW具有$ O（D \ sqrt {n}ε^{ - 2}）$的功能查询复杂性，用于在有限的sum问题中找到$ε$ - 稳定点，从而提高了$ o（\ sqrt and的最佳结果），并提高了$ o的最佳结果。随机问题中的$ O（dε^{ - 3}）$的$（将出口的最佳结果提高了$ O（ε^{ - 1}）$。为了放松ACC-SZOFW中所需的大批量，我们进一步提出了一种基于新方差的风暴技术，在不依赖任何大型批准的情况下，在不依赖机构问题的情况下，它仍然达到$ O（Dε^{-3}）$的功能查询的复杂性（Dε^{-3}）$，它仍然达到$ O（Dε^{-3}）的功能复杂性。特别是，我们根据提议的动量加速技术提出了弗兰克 - 沃尔夫方法的加速框架。黑盒对抗攻击和强大的黑盒分类的广泛实验结果证明了我们算法的效率。
In the paper, we propose a class of accelerated stochastic gradient-free and projection-free (a.k.a., zeroth-order Frank-Wolfe) methods to solve the constrained stochastic and finite-sum nonconvex optimization. Specifically, we propose an accelerated stochastic zeroth-order Frank-Wolfe (Acc-SZOFW) method based on the variance reduced technique of SPIDER/SpiderBoost and a novel momentum accelerated technique. Moreover, under some mild conditions, we prove that the Acc-SZOFW has the function query complexity of $O(d\sqrt{n}ε^{-2})$ for finding an $ε$-stationary point in the finite-sum problem, which improves the exiting best result by a factor of $O(\sqrt{n}ε^{-2})$, and has the function query complexity of $O(dε^{-3})$ in the stochastic problem, which improves the exiting best result by a factor of $O(ε^{-1})$. To relax the large batches required in the Acc-SZOFW, we further propose a novel accelerated stochastic zeroth-order Frank-Wolfe (Acc-SZOFW*) based on a new variance reduced technique of STORM, which still reaches the function query complexity of $O(dε^{-3})$ in the stochastic problem without relying on any large batches. In particular, we present an accelerated framework of the Frank-Wolfe methods based on the proposed momentum accelerated technique. The extensive experimental results on black-box adversarial attack and robust black-box classification demonstrate the efficiency of our algorithms.
