Venue: ICLR 2020 Conference

Reviews:

final_score: rating: 6: Weak Accept
review_content: 
Update after rebuttal: I found the rebuttal convincing and I liked the fact that concerns regarding empirical justification were addressed. Consequently, I increase my score from "Weak Reject" to "Weak Accept".
--------------------------
This paper focuses on derivative-free, or zero-th order, optimization. That is the setting where a function may be continuous and/or smooth and/or (quasi)-convex, however, we do not have access to the gradients. As such, it is not possible to apply standard gradient descent methods. The paper proposes an algorithm for "gradientless" descend. The basic intuition is that by careful randomly sampling it is quite probable that a lower objective value will be attained. Doing so recursively can then lead to the optimum with high probability. Clearly, in such a setting it is quite important to clarify what is "careful random sampling". To this end the paper casts this as sampling from a Gaussian ball of specific radius, chosen such that the samples are with high probality below the current level set (the hyperplance of equivalent solutions f(x) as our current solution f(x_t)). The paper derives and proves various theorems on how to select the optimal radius and how to perform the sampling. Specifically, the case of strongly convex and smooth functions is analyzed, however, the paper also shows how this generalizes to functions after a monotone transformation (thus leading to quasi-convex functions) and with extra error perturbations. The proposed algorithm is compared on a synthetic experiment, and a selection of MuJoCo benchmarks.

Strengths:
+ The derivations and the theorems are non-trivial. There is some serious analysis regarding the selection of radius of Gaussian balls. I would like to congratulate the authors for this. I particularly like the extension to having a perturbing function h(x), leading to a more realistic setup.
+ I also particularly like that the algorithm is able to recover subspaces automatically. This definitely makes the algorithm much more practical and more efficient.
+ The writing and the presentation are rather clear and well taken care of. Although there are several theorems, it was not too hard to follow the flow of the paper. The algorithm boxes are also concise and clear, helping with understanding the final result.

Weaknesses:
+ Although the contributions of the work are mostly on the theoretical side, I have a hard time grasping how useful is the algorithm in practice. For one, there is the assumption of strongly convex and smooth function. Granted, there is the relaxed case of having the perturbing function h(x), howevrer, in that case it seems that the algorithm becomes a slower by an order of 60 δ k Q_g(A). How fast or slow is this in practice? Even with applying the monotone function, the algorithm becomes more practical by being applicable to quasi-convex setups. However, how realistic is that a function will in practice be strictly monotone? While most of this may be hard to be theoretically proven, they can be experimentally tested.

+ Also, given that the paper is interested in black box functions, we cannot have much information regarding the function. So, what happens when the function is not strongly convex or not always smooth? Furthermore, how realistic is to know the condition number, that is the maximum derivative (or an upper bound of it) since we do not have access to the gradients in the first place?

+ I would say that the paper could benefit from a more extensive experimental section. Currently only a single synthetic function is analyzed, also under a single monotone exponential transformation. From a more practical point of view, MuJoCo environments are also examined. However, there exist no comparisons with other methods in the literature, including ARS. Another relevant algorithm to compare with would be the stochastic tree points (Bergou et al., 2019), if not experimentally at least theoretically. In the end, it quite unclear whether the algorithm work well in practice. Some experiments that could shed light would relate to how sensitive the algorithm is to the convexity/smoothness assumptions, how sensitive the algorithm is to the perturbing function h(x), how sensitive is the algorithm to the present of a lower-dimensional subspace that needs to be discovered. And for the MuJoCo experiments, the algorithm can compare at least with ARS.

+ In the experiments it seems the paper is particularly good in high dimensions. Can this be more precisely connected to the derived theory in the discussion of the experiments? Does this relate to the better subspaces k that are discovered automatically by the algorithm?

+ It is unclear how many evaluations are needed per step, that is what is the K value in the algorithm box? Also, there are at least two balls to sample from, so twice as many evaluations, correct?

+ It is unclear why Bayesian Optimization is not considered for at least comparing experimentally. Currently, the paper discards them on the grounds that they do not provide strong theoretically guarantees. However, it would be interesting to examine at least in practice how good/bad are these algorithms in comparison to the proposed one. Two recent bayesian optimization papers that can be considered for continuous and discrete inputs are

[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

+ The paper does not have a conclusion. That shows great sloppiness. Also, i/n the abstract, do you mean to say k>=n or k<=n?

To conclude, I recommend weak rejection only because I am not completely convinced by the experiments and do not know if the proposed algorithm is competitive against reasonable baselines and in more complex setups. I am more than happy to upgrade my score if experiments become more clear.
review_title: Official Blind Review #1

final_score: rating: 8: Accept
review_content: ** Summary
The paper proposes a novel zeroth-order algorithm for high-dimensional optimization. In particular, the algorithm as an instance of direct search algorithms where no attempt is made to estimate the gradient of the function during the optimization process. The authors study the optimization of monotone transformations of strongly-convex and smooth functions and they prove complexity bounds as a function of the condition number, the dimensionality and the desired accuracy. These results are also extended to the case where the function actually depends on a lower-dimensional input. Without any knowledge of the actual subspace of interest, the algorithm is able to adapt to the (lower) dimensionality of the problem. The proposed algorithms are tested on synthetic optimization problems and in a few Mujoco environments for policy optimization.

** Overall evaluation
The paper is a solid theoretical and algorithmic contribution to the zeroth-gradient optimization literature. The positive aspects of the paper are:
- Novel algorithm with strong theoretical guarantees improving or generalizing previous state-of-the-art methods.
- Ability to adapt to low-dimensional problems and more in general to monotone transformations of convex functions.
- Efficient version.

Negative aspects of the paper that the authors may address are:
- The empirical validation is rather weak at the moment. It provides some evidence of the effectiveness of the proposed method but it uses only one baseline and a very few type of optimization problems. Although in my opinion the main contribution is on the theoretical side, a more thorough empirical validation would be welcome.
- Some theorem statements can be made clearer and some comparisons should be more explicit (see detailed comments later).

Detailed comments:
1- The authors explicitly mentioned in the introduction that they do not compare/discuss alternative approaches such as Bayesian optimization (BO). Although I agree the approaches may be different, BO is probably the most popular type of black-box optimization. Furthermore, many methods (e.g., GP-UCB https://arxiv.org/abs/0912.3995) come with strong theoretical guarantees on the regret and so optimization performance both under the Bayesian assumption (i.e., the function is generated from a prior) and the "frequentist" case (i.e., the function is an arbitrary element of a bounded RKHS). Furthermore, there are also adaptive BO methods that adapt to the actual dimensionality of the problem, in a similar spirit as the low-dimensional case studied in this paper. See e.g., https://arxiv.org/abs/1903.05594 and http://papers.nips.cc/paper/8115-efficient-high-dimensional-bayesian-optimization-with-additivity-and-quadrature-fourier-features. I would appreciate if the authors would at least provide a high-level discussion on similarities and differences between these type of approaches.
2- Thm7: r = 2^k1 C_1 and r = 2^-k2 C_2 are the only two possible radii? Is the statement valid for any choice in the range?
3- Thm13: Unlike the statements in Sect.3.2 and 3.3, here the result is reported in terms of x_T (instead of f(x_T)). This is perfectly fine, but the guarantee you obtain is not an epsilon accuracy, but Q^{3/2}epsilon. If we want to obtain an epsilon accuracy, how much is the number of evaluation going to change? It seems like it would just make an additional Q appear in the log, but I would like the authors to confirm.
4- Thm13: "High-probability": could you make this more explicit? Can I make the probability arbitrarily close to 1? How would it appear in the number of iterations? As just a log(1/delta) term?
5- Thm14 is reported for "suitable parameters". Although this choice of parameter actually appears in Alg.2, it would be more complete to report it in the statement as well.
6- Fig1 bottom line, first two charts display a weird behavior for GLD-Fast, where the error seems to plateau and spot decreasing. Can you explain why this is happening? Is it due to wrong parameters \hat alpha and \hat beta?

Minor comments:
- In the proof of Lem.8, it would be helpful to have a graphical representation of the spheres and the hyperspherial caps.
- In the proof of Lem.15, you mention "strong smoothness assumption", it should be just smoothness.
- It would be helpful to have more intuition on the why the algorithm is able to adapt to the actual dimensionality of the problem. My understanding is that the probability to pick a point of lower value is increased and since the algorithm is testing different radii and pick the best point, it successfully adapt to this better situation.
review_title: Official Blind Review #3

final_score: rating: 6: Weak Accept
review_content: This paper proposes stable GradientLess Descent (GLD) algorithms that do not rely on gradient estimate. Based on the low-rank assumption on P_A, the iteration complexity is poly-logarithmically dependent on dimensionality. The theoretical analysis of the main results is based on a geometric perspective, which is interesting. The experimental results on synthetic and MuJoCo datasets validate the effectiveness of the proposed algorithms.

The theoretical contribution of this paper is nice and valuable. My main concern is the structure f(x) = g(P_A x) + h(x) looks somewhat limited. A more natural form is moving the perturbation into g, i.e, f(x) = g(P_A x + h(x)). 

The experiments on Mujoco do not satisfy the assumption previous. Is there any real-world application which matches the theoretical analysis?

In summary, I think this is a good paper and tend to accept it.

review_title: Official Blind Review #2

Meta-review: The paper considers an interesting algorithm on zeorth-order optimization and contains strong theory. All the reviewers agree to accept.
Decision: Accept (Spotlight)