Towards Gradient Free and Projection Free Stochastic Optimization
[edit]
Proceedings of Machine Learning Research, PMLR 89:34683477, 2019.
Abstract
This paper focuses on the problem of \emph{constrained} \emph{stochastic} optimization. A zeroth order FrankWolfe algorithm is proposed, which in addition to the projectionfree nature of the vanilla FrankWolfe 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 suboptimality 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 nonconvex functions, we obtain the \emph{FrankWolfe} gap to be $O\left(d^{1/3}T^{1/4}\right)$. Experiments on blackbox optimization setups demonstrate the efficacy of the proposed algorithm.
Related Material


