Towards Gradient Free and Projection Free Stochastic Optimization
This work addresses optimization problems where gradients are unavailable or projections are costly, offering a novel algorithm with improved theoretical guarantees, though it is incremental in advancing zeroth-order methods.
The paper tackles constrained stochastic optimization by proposing a zeroth-order Frank-Wolfe algorithm that is both gradient-free and projection-free, achieving convergence rates of O(1/T^{1/3}) for convex functions and O(d^{1/3}T^{-1/4}) for non-convex functions, with a dimension dependence of O(d^{1/3}) that is the best known among such methods.
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.