Venue: ICLR 2020 Conference

Reviews:

final_score: rating: 6: Weak Accept
review_content: This paper studies the so called problem of derivative-free optimization, which is relevant for cases when the evaluation function is continuous but access to gradients is not possible. The paper improves on top of the stochastic three points method (STP), an existing work (published in arXiv), by proposing adding momentum (SMTP). The intuition behind both STP and SMTP is rather straighforward: you sample a random direction s, then given your current position x you check x+as and x-as. You then move to the best position from (x, x+as, x_as). In a way, this is like computing the numerical derivatives (instead of the gradient) given a random location and its mirror, and then applying gradient descent given the best numerical derivative. However, take this analogy with a large grain of salt, as there are many differences with GD. The proposed algorithm adds momentum and importance sampling. Momentum helps speed up convergence, as the paper shows for non-convex, convex and strongly convex functions. All three cases are individually examined and bounds are derived regarding the speed of convergence. For the non-convex case the speed of convergence is 1/\sqrt{K}, K being the number of iterations. For the convex case it is 1/K. For the strongly convex case the (unrealistic) assumption of knowing the optimal value is removed while maintaining the same speed of convergence.  Importance sampling helps computing the derivatives focusing on those coordinate dimensions that are more critical to the objective function f(x), improving the speed of convergence further. The importance sampling is proportional to the coordinate-wise Lipschitz constants, assuming that the objective function is coordinate-wise Lipschitz smooth. The methods are validated on five different cases of MuJoCo. Results seem good when compared to the STP ones. Compared to policy gradient methods, the results seem much better.

Strengths:
+ The paper presents a small but interesting and well-motivated addition to the original algorithm STP. I particularly liked how straightforward the final algorithm is: applying momentum and sampling according to the Lipschitz constants.

+ At least at a first glance the results look good. Compared to STP in figure 1 there is a clear improvement not only in the final optimum but also in the speed of attaining the said optimum.

+ I liked a lot the presentation and clarity of writing. While quite mathematically dense, it was easy to follow the big story and understand that underlying points. 

Weaknesses:
+ While interesting and useful, I am not completely convinced whether the added novelty over (Bergou et al, 2019) is significant enough. At the end of the day, the final algorithm is the conglomeration of two existing algorithms, that is STP and momentum. STP is very similar to the final algorithm, after all it is the basis for it. The authors argue that it is not trivial to select the next points under the momentum term. To this end, they propose to rely on yet another existing approach, that is the virtual iterates analysis from (Yang et al. 2016). However, it is not clear why these points are "optimal", what is so "non-trivial" about selecting them? This is basically skimmed over in two lines.

+ In the strongly convex case one assumption (knowing the f(x*) ) is replaced with another assumption, that all points lie on a hypersphere (|s|_2=1). I suppose this would assume a spherical normalization of the input space. While this is not an unrealistic assumption, it does place a constraint which could be problematic in the case of high dimensions for s? In that case the high dimensionality would render distances rather unreliable and in turn could hurt convergence? This is also perhaps the reason that only the MuJoCo enviroments were tested? In general, I would say that the strongly convex case was discussed less clearly and it is not exactly clear the final result. In the end, eq (25) does contain f(x*), whereas in the convex case K does not (K \approx 2 R_0^2 L γ_D/(εμ_D^2).

+ Some statements are unclear.
  ++ In p. 2 some symbols are not explained, e.g., ε. While it is quite clear for peopled versed in the field, in my opinion it is bad practice to leave notation not explained.
  ++ In assumption 3.1 seems rather trivial? Wouldn't γ_D by definition be always positive, since is the expectation of a squared norm (always positive)? Does this need to be an assumption?
  ++ Between eq. (11) and (12) there is reference to (35)? What is (35)?
  ++ It is not clear in practice how the importance sampling is performed. In Algorithm 2 the probabilities p_i are defined as function inputs and then never updated. Is that true? If yes, how is p_i decided in the first place? What is the connection to the Lipschitz constants L_i?

+ A highly relevant field appears to be Bayesian Optimization, where also one cannot compute gradients and must optimize a black-box function. Some relevant recent works are [1] and [2] for continuous and discrete inputs. It would be interesting to discuss what are the distinct differences with bayesian optimization methods in [1] and [2].

+ I would say that the paper is rather on the light side regarding experiments. Only MuJoCo is used as an experimental setup. It would be nice to also report results on synthetic experiments with known functions to better understand the limitations of the algorithm. Synthetic and realistic setups can be found in [1] and [2].

What is more, the experimental choices are not entirely clear. What is the "predefined reward threshold" and why was that chosen? For instance, the leaderboard for "Swimmer" is in: https://www.endtoend.ai/envs/gym/mujoco/swimmer/. How does the proposed algorithm fair compared to these works? Also, *maybe* it would be interesting to compare even against [1] or [2] (I guess [2] is harder as it is for discete inputs), assuming that a relatively low number of iterations is performed.

[1] BOCK: Bayesian Optimization with Cylindrical Kernels, C. Oh, E. Gavves, M. Welling, ICML 2018
[2] BOCS: Bayesian Optimization of Combinatorial Structures, R. Baptista, M. Poloczek, ICML 2018

review_title: Official Blind Review #2

final_score: rating: 6: Weak Accept
review_content: 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.
review_title: Official Blind Review #3

final_score: rating: 6: Weak Accept
review_content: The paper proposes a stochastic derivative free optimization algorithm. The contribution is two-fold: first, the paper introduces the heavy ball momentum into the STP framework; second, the paper fulfills both the importance sampling and heavy ball momentum in the STP framework. For both methods, the paper provides the convergence guarantees and rates. The experiments on reinforcement learning data-sets, as compared with the original STP, shows improvement. 

The idea seems straightforward --- just combining a classical momentum strategy with the an existing derivative free optimization framework. But the author claim that they are the first to exploit this strategy. The analysis part, for strongly convex, convex and nonconvex problems, however, is solid to me. I am not the expert in this direction. Here are a few questions, from the answers of which I want to learn more about the meaning of this work. 

(1) As compared with other derivative free optimization algorithm, such as Bayesian optimization/genetic algorithms/simulated annealing, what is the advantage of the proposed method and also the STP framework? 
(2) The experiments seem weak to me. Why does the paper only compare with STP? Are there any other baselines, such as stochastic two points, BO and GA? Is it possible to conduct evaluation on other applications? For example, some general optimization tasks but not allowing gradient calculation?
review_title: Official Blind Review #1

Meta-review: A new method for derivative free optimization including momentum and importance sampling is proposed.

All reviewers agreed that the paper deserves acceptance.

Acceptance is recommended.
Decision: Accept (Poster)