Venue: ICLR 2020 Conference

Reviews:

final_score: rating: 6: Weak Accept
review_content: This paper provides a new type of gradient estimator that combines an Evolutionary Strategies (ES) style estimate (using function evaluations at perturbed parameters) along with surrogate gradient estimates (gradient estimates that may be biased and/or high variance). The estimator involves computing antithetic ES estimates in two subspaces: along the set of (normalized) surrogate gradients, and along a set of randomly chosen vectors in the orthogonal complement of the span of the surrogate gradients. The paper provides a proof of the optimality of the estimate, that is, the proposed gradient estimate maximizes the cosine of the angle with the true gradient over the vectors in the subspace defined by the set of surrogate gradients and sampled directions. The paper proposes an additional mechanism for generating surrogate gradients by simply using previous gradient estimates as surrogate gradients, and derives a convergence rate for when this iterative estimator will approximate a fixed, true gradient (e.g. for linear functions). Finally, the paper applies the estimate to two tasks: MNIST classification and robotic control via reinforcement learning, demonstrating improvements on both compared to standard ES.

I think this is a nice contribution, and I enjoyed reading this paper, with one major caveat regarding some of the experiments. The paper is clearly written.

Major concerns:
- The paper is missing critical comparisons to existing work. In particular, the paper cites Ref. 14 as another method for using surrogate gradients in optimization. For both examples (MNIST and RL), it is crucial to add the algorithm from that paper as a baseline.
- In addition, it would also be nice to see one of the diagonal approximations of CMA-ES as a baseline.

Other questions/comments:
- For the MNIST example, you mentioned that the function is deterministic--how many examples are used for each function/gradient evaluation (the full dataset, or some fixed subset)?
- It would be nice to see how the performance gap between the proposed estimate and ES varies with the number of parameters (size of the network).
- It would be nice to compare the orthogonal epsilon to the N(0,I) epsilon case. As mentioned in the paper, the N(0,I) will be nearly orthogonal to the surrogate gradients in high dimensions. For a practical problem (e.g. MNIST), is the orthogonalization strictly necessary?

Minor comments/typos:
- Fig 2: Add label for the x- and y-axes, and a legend.
- Use a more semantically meaningful subscript than `our` for the proposed gradient estimate. Perhaps `orth`, since you utilize orthogonal subspaces?
- Typo in eq. (6) (issue with the subscript on f)

review_title: Official Blind Review #2

final_score: rating: 3: Weak Reject
review_content: This paper is about improving the quality of surrogate gradients. Their proposal in guaranteed to find a descent direction. In addition to two results, the authors also provide experimental results.

This paper is presenting a research on a recent topic. Using random search methods or evolutionary strategies in machine learning problems is attracting quite an interest in the last years. However, this particular paper misses several important points and hence, lacks sufficient contribution. 

Here are my major comments:

- The technical results are somewhat superficial: The first one is with the big assumption of linearity. This assumption does not hold almost for all problems where random search strategies would be of use. The second result, on the other hand, assumes orthogonality, which almost surely never happens. I must add that the authors also acknowledge the severity of these assumptions.

- It is important to note that the theory here assumes that the gradient does exist but cannot be computed or too expensive to compute.

- I would have expected an experimental study that would properly support the proposed approach. Such a study would have shed light on the computation time and efficiency. The authors solve MNIST problem, which can be quite efficiently solved with a variant of (accelerated) gradient method. Solving it with ES and then improving the result with the proposed approach is not satisfactory. Reinforcement learning experiments could have been noteworthy but the authors have solved quite small problems and did not compare their results extensively against contender approaches like augmented random search. It would have been also nice to see the computation times on large problems since the extensive computation time is a big obstacle for training in reinforcement learning.

review_title: Official Blind Review #3

final_score: rating: 3: Weak Reject
review_content: This paper addresses the issue of noisy gradient estimation in a type of evolution strategies popularized by the open AI's reinforcement learning paper. It is a follow-up paper of reference [14], and try to analyze the optimality of the gradient estimation. The goal of the paper is well stated and well motivated. The paper itself is well-organized. However, the novelty of this work is not sufficiently high and its usefulness is questionable. 

Theorem 1 is trivial under the assumption stated above the theorem---the numerical approximation of the directional derivative admits the true directional derivative. In other words, the assumption is too strong to claim the goodness of the proposed scheme. 

Let's just sample k+P random normal vectors and orthogonalize and normalize them. Let them denoted by the same symbols hat zeta and hat epsilon. The theorem statements holds for this case. Therefore I failed to understand the essential claim of Theorem 1. 

About Theorem 2 and 3, again, the assumption that he numerical approximation of the directional derivative matches the true directional derivative is too strong to make the claim relevant. Moreover, the effect of P somehow disappear from the analysis. 

All the analysis is done assuming the above mentioned strong assumption. However, in one of the experiments and the existing works, ranking based fitness shaping has been applied to make the algorithm robust. This replaces the function value differences in the gradient estimator with some predefined values depending on the ranking of f-values of each trial vector. This definitely violates the assumption, and it may result in some vector far away from the true gradient, yet the algorithm still works well. Therefore, the hypothesis underlying in this paper---better estimation of the gradient will lead to a better performance---may not be true. At least the numerical experiments provided in this paper do justify this hypothesis.

The numerical experiments have been conducted to compare the proposed algorithm with the baseline ES algorithm. In a sense it is reasonable to evaluate the effect of the proposed modification in the baseline ES. However, since the baseline ES algorithm is not really efficient on tasks such as the one conducted in Figure 2, the usefulness of the proposed approach is not tested. At least one should compare with the "canonical" ES, where the learning rate fixed and sigma is adapted. See https://arxiv.org/pdf/1802.08842.pdf. 

Use of the search history proposed in this paper is not really new in ES community. A sort of momentum terms appears in the standard CMA-ES [18] even in two parts of the algorithm and its effectiveness is well-studied empirically. This paper addresses the theoretical aspect of the momentum and this may be new. However, as mentioned above, the assumption is too strong to describe the reality.

"Linear time approximations of CMA-ES like diagonal approximations of the covariance matrix (19) often do not work well." Please specify in what sense the linear time version of the CMA-ES do not work well and provide the evidence (references). 
review_title: Official Blind Review #1

Meta-review: The authors propose a novel approach to using surrogate gradient information in ES. Unlike previous approaches, their method always finds a descent direction that is better than the surrogate gradient. This allows them to use previous gradient estimates as the surrogate gradient. They prove results for the linear case and under simplifying assumptions that it extends beyond the linear case. Finally, they evaluate on MNIST and RL tasks and show improvements over ES.

After the revisions, reviewers were concerned about: 
* The strong (and potentially unrealistic) assumptions for the theorems. They felt that these assumptions trivialized the theorems.
* Limited experiments demonstrating advantages in situations where other more effective methods could be used. The performance on the RL tasks shows small gains compared to a vanilla ES approach. Thus, the usefulness of the approach is not clearly demonstrated. 

I think that the paper has the potential to be a strong submission if the authors can extend their experiments to more complex problems and demonstrate gains. At this time however, I recommend rejection.
Decision: Reject