This paper focuses on the problem of \emph{constrained} \emph{stochastic}
optimization. A zeroth order Frank-Wolfe algorithm is proposed, which in
addition to the projection-free nature of the vanilla Frank-Wolfe algorithm
makes it gradient free. Under convexity and smoothness assumption, we show that
the proposed algorithm converges to the optimal objective function at a rate
$O\left(1/T^{1/3}\right)$, where $T$ denotes the iteration count. In
particular, the primal sub-optimality gap is shown to have a dimension
dependence of $O\left(d^{1/3}\right)$, which is the best known dimension
dependence among all zeroth order optimization algorithms with one directional
derivative per iteration. For non-convex functions, we obtain the
\emph{Frank-Wolfe} gap to be $O\left(d^{1/3}T^{-1/4}\right)$. Experiments on
black-box optimization setups demonstrate the efficacy of the proposed
algorithm.

本文介绍了一种零阶 Frank-Wolfe 算法，用于解决约束随机优化问题，该算法与基本 Frank-Wolfe 算法同样无需投影，且不需要计算梯度，可收敛于凸平滑约束下的优化目标函数。同时，本算法在具有每次迭代一个方向导数的所有零阶优化算法中具有最优维度依赖性。对于非凸函数，本算法的 Frank-Wolfe gap 为 O (d^{1/3} T^{-1/4})，并在黑盒优化设置上进行实验，证明了其效果。