We consider the problem of unconstrained minimization of a smooth objective function in R d in setting where only function evaluations are possible. We propose and analyze stochastic zeroth-order method with heavy ball momentum. In particular, we propose, SMTP, a momentum version of the stochastic three-point method (STP) Bergou et al. (2019). We show new complexity results for non-convex, convex and strongly convex functions. We test our method on a collection of learning to continuous control tasks on several MuJoCo Todorov et al. (2012)  environments with varying difficulty and compare against STP, other state-of-the-art derivative-free optimization algorithms and against policy gradient methods. SMTP significantly outperforms STP and all other methods that we considered in our numerical experiments. Our second contribution is SMTP with importance sampling which we call SMTP_IS. We provide convergence analysis of this method for non-convex, convex and strongly convex objectives.
The authors extend recent the recent stochastic three-point (STP) method to allow for Polyak-style momentum, as well as momentum with importance sampling. They provide a range of analysis that mostly extends existing STP results to the STP+momentum case. Most of these results are similar in spirit to stochastic gradient or subgradient results, as in the methods converge up to a ball around the solution, with radius depending on step-size, so you can get an epsilon solution by choosing a suitably small stepsize. The analysis covers non-convex cases (bounds are on the norm of the gradient) and the importance sampling case as well.
Overall, I think this is a strong paper, and a very interesting topic, and hence I support a "Weak accept". The numerical results look good, as the new method outperforms most of the compared methods, at least for the easier problems (SMTP beats competitor ARS in 3/5 trials; both methods are generally very similar, though SMTP does better on the easy Swimmer problem; the SMTP_IS results are more complicated).  The analysis is mostly good (non-trivial), and shows a broad understanding.
That said, I have some concerns. 
(1) The analysis is nice in that it shows the methods work, but doesn't demonstrate benefit of their method over other methods
(2) Given that there are no results showing this method has better worst-case rates than other methods, we rely on experiments to see the actual benefit. In this case, more experiments is always better.
(3) I am quite skeptical of the importance sampling scheme. It's nice to include it, but I don't think it strengthens the paper too much. Empirically, the performance seems to help sometimes but not other times. Finding the individual Lipschitz constants seems tricky; this paper re-uses a scheme that iterates for a while, fits a function, and uses that to estimate the constants (it wasn't clear if this pre-processing was counted in the iteration count for experimental results). It's not clear how well that works to get an accurate estimate. Furthermore, to exploit the importance sampling, the directions must be sampled from a pre-determined basis, which seems restrictive.  This criticism is not just of the current paper but of other papers that use this approach.
-- The manuscript needs more proof reading, as there are mistakes in most paragraphs. There are a lot of problems with missing articles.  Phrases like "results for STP are shorts and clear" ("shorts" --> "short"), "which updates rule" [?? which-->with?? ], "hints [at] the update rule", "is far more superior" [-->"is far superior", since you can't be more superior], etc.
-- There is a confusion over how to use \cite, \citet and \citep in latex. Given the bibtex citation style, this makes it very hard to read in places
-- Literature review seems good and pretty thorough (mentions most key references through 2015, and a good selection of references since then).
-- Assumption 3.1 part 2 is stated in a funny way (it says, "there is a constant mu_D and a norm || ||_D such that ...").  You are free to choose the norm, and then find the constant (since all norms in finite dimensions are equivalent). That way, you can choose the norm that gives the tightest inequality.  I think you are aware of this, and it's just a wording issue.
-- Theorem 3.5 (Thm D.2) requires the mu_D^2 to be less than the condition number, which is weird. The easier the problem is, the tighter your assumptions are.  I suspect that this is because you use an inequality somewhere that simplifies things by bounding a term by the condition number. But as stated, this is a weak theorem.  It is also confusing because you have a mu_D which is not the strong convexity constant, but the actual strong convexity constant (mu) *does* depend on the norm D (cf eq 19; and this must be so, otherwise you can cheat and then the value of mu_D is meaningless). So both mu's are functions of the norm D. However, the Lipschitz constant L is *not* a function of D. So notation is confusing and makes interpreting the results harder.
-- sentences like "We achieve the state-of-the-art performance compared to *all* DFO based and policy gradient methods" are in appropriate (*italics* are mine). You mean to say that on the few examples you ran, based on a few DFO and policy gradient methods you tested, that the best of your two methods was better than the competitor methods on 4/5 problems.
-- I think a common-sense algorithm to compare to would be gradient descent (or heavy-ball) using finite differences to estimate the gradient.  In small dimensions this isn't such a bad idea.  I don't actually know what the dimensions of your test problems are (I looked in section 5 but didn't see it mentioned, other than reference to Ant-v1 and Humanoid-v1 being "high dimensional"; I think this is extremely relevant information. In small dimensions, traditional DFO and Bayesian optimization methods are competitive).
-- p 26/27, "Causchy-Schwartz" is spelled wrong, and usually this is called "Holder's inequality" when it's not the Euclidean norm.
-- Table 3, there is no space between the caption and the main text, so it's confusing
-- Eq (76) in appendix, the sum should go to d not n.
-- I think s^k may need to be independent of z^k for their tower property thing to work, otherwise it's not clear what's happening with the inequality prior to overset (30) on that last line of pg17. For example, if s^k were z^k measurable then that whole thing in the inner expectation would be a constant. This isn't a problem, it's fairly natural to assume that s^k is independent of z^k, I just didn't see the assumption anywhere.
-- Overall, comparing importance sampling results is hard, due to the different norms (this is mentioned in the paper, and there are inequalities between norms, but it's still hard to get a good result that shows importance sampling has better worst-case rates).
== AFTER READING REBUTTAL ==
I read the authors' response, and I am still slightly positive about the paper, though my major points were not addressed, but mostly deflected, e.g., referring to other papers that claim to show benefits of importance sampling. I think all the reviewers were curious how Bayesian optimization (BO) would perform. We understand numerical experiments are time consuming, but it's disappointing that you're not curious yourself whether your method outperforms BO. Your basic deflection seems to be that BO doesn't have provable guarantees, so because you do have guarantees, you don't need to compare with it.  Having one of the fastest methods among all methods with provable guarantees, but not necessarily the fastest method in general, sounds like a consolation prize to me.
The revision did not address some of the minor issues I mentioned, such as confusing "cite"/"cited"/"citep" issues in latex (which makes it hard to read).  My comment about Holder's inequality (vs Cauchy-Schwarz) applies not just to the $\|\cdot\|_1 \le \sqrt{d}\|\cdot\|_2$ bound, but also to the  $\|\cdot\|_2 \le \sqrt{d}\|\cdot\|_\infty$ bound in the next paragraph.
But despite a few items I'm being cranky about, I think it's still a solid paper, and it's still a weak accept.