Evolutionary Strategies (ES) are known to be an effective black-box optimization technique for deep neural networks when the true gradients cannot be computed, such as in Reinforcement Learning. We continue a recent line of research that uses surrogate gradients to improve the gradient estimation of ES. We propose a novel method to optimally incorporate surrogate gradient information. Our approach, unlike previous work, needs no information about the quality of the surrogate gradients and is always guaranteed to find a descent direction that is better than the surrogate gradient. This allows to iteratively use the previous gradient estimate as surrogate gradient for the current search point. We theoretically prove that this yields fast convergence to the true gradient for linear functions and show under simplifying assumptions that it significantly improves gradient estimates for general functions. Finally, we evaluate our approach empirically on MNIST and reinforcement learning tasks and show that it considerably improves the gradient estimation of ES at no extra computational cost.
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).