Zeroth-order (Non)-Convex Stochastic Optimization via Conditional Gradient and Gradient Updates
In this paper, we propose and analyze zeroth-order stochastic approximation algorithms for nonconvex and convex optimization. Specifically, we propose generalizations of the conditional gradient algorithm achieving rates similar to the standard stochastic gradient algorithm using only zeroth-order information. Furthermore, under a structural sparsity assumption, we first illustrate an implicit regularization phenomenon where the standard stochastic gradient algorithm with zeroth-order information adapts to the sparsity of the problem at hand by just varying the stepsize. Next, we propose a truncated stochastic gradient algorithm with zeroth-order information, whose rate depends only poly-logarithmically on the dimensionality.
The paper considers the problem of extending the Frank-Wolfe method to scenarios that only an unbiased estimate of the function value is available, i.e.  we don't have access to any (stochastic) gradient o higher order information and only (an unbiased version of) the function values can be obtained from the oracle. The authors use Nestrov's smoothing method to find a (stochastic) proxy of the gradient and use such a proxy to design their algorithms.  I have carefully read the paper and I have two major issues with this paper. While I find the problem and the solutions interesting and somehow novel, I believe the following two issues have to be resolved before I can give a higher mark for accepting the paper.   1) Related work and giving credit to previous work: Algorithm 1 in the paper is exactly the algorithm SFW proposed in [12,24] with the difference that the stochastic gradients are replaced by unbiased estimators of the smoothed function (from equation (1.3)). While I find the smoothing step crucial and novel due to having only zero-order information, I believe that the authors should have given credit to [12] or [24] by specifying what steps Algorithm 1 has different with respect to those algorithms.    Furthermore, the problem of stochastic FW (with first order information) has been studied recently in various papers and the authors have failed to review recent progress and related work on this topic. For example, the following paper by Mokhtari et al proposes a stochastic Frank-Wolfe method for both convex and structured non-convex problems with O(1/eps^3) samples (potentially dimension-independent): https://arxiv.org/abs/1804.09554  I expect that in the revised version the authors highlight the differences of their algorithms with the recent results (perhaps the authors can add a section called related work). I understand that the authors consider zero-order information, but in principle by using the smoothing trick one can come up with (unbiased estimates of) first order information of a sufficiently close function (as done in equation 1.3 in the paper).  2) To get the O(d/eps^2) bound the authors add a proximal step (equation 2.15) and solve this step by using the FW method (Algorithm 2). Well, I can not really call the whole algorithm (Algorithm 3) a stochastic and projection-free conditional gradient method. The authors are just solving an expensive quadratic optimization problem by the FW method and claim that the overall algorithm is a FW-type method.  Indeed, one can solve any quadratic projection problem with FW. For example, consider projected gradient descent. We can solve the projection step with FW and claim that we have a projection-free method with rate O(1/eps^2). Can the authors comment on this?