Accelerated Stochastic Gradient-free and Projection-free Methods

arXiv2007.12625MaRDI QIDQ6345783

Author name not available (Why is that?)

Publication date: 16 July 2020

Abstract: 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(dsqrtnepsilo{n}^{-2})$ for finding an $epsilon$-stationary point in the finite-sum problem, which improves the exiting best result by a factor of $O(sqrtnepsilo{n}^{-2})$, and has the function query complexity of $O(depsilo{n}^{-3})$ in the stochastic problem, which improves the exiting best result by a factor of $O(epsilo{n}^{-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(depsilo{n}^{-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.

Has companion code repository: https://github.com/TLMichael/Acc-SZOFW

This page was built for publication: Accelerated Stochastic Gradient-free and Projection-free Methods

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6345783)