Many applications in machine learning require optimizing a function whose true gradient is unknown, but where surrogate gradient information (directions that may be correlated with, but not necessarily identical to, the true gradient) is available instead. This arises when an approximate gradient is easier to compute than the full gradient (e.g. in meta-learning or unrolled optimization), or when a true gradient is intractable and is replaced with a surrogate (e.g. in certain reinforcement learning applications or training networks with discrete variables). We propose Guided Evolutionary Strategies, a method for optimally using surrogate gradient directions along with random search. We define a search distribution for evolutionary strategies that is elongated along a subspace spanned by the surrogate gradients. This allows us to estimate a descent direction which can then be passed to a first-order optimizer. We analytically and numerically characterize the tradeoffs that result from tuning how strongly the search distribution is stretched along the guiding subspace, and use this to derive a setting of the hyperparameters that works well across problems. Finally, we apply our method to example problems including truncated unrolled optimization and training neural networks with discrete variables, demonstrating improvement over both standard evolutionary strategies and first-order methods (that directly follow the surrogate gradient). We provide a demo of Guided ES at: redacted URL Optimization in machine learning often involves minimizing a cost function where the gradient of the cost with respect to model parameters is known. When gradient information is available, firstorder methods such as gradient descent are popular due to their ease of implementation, memory efficiency, and convergence guarantees (Sra et al., 2012) . When gradient information is not available, however, we turn to zeroth-order optimization methods, including random search methods such as evolutionary strategies (Rechenberg, 1973; Nesterov & Spokoiny, 2011; Salimans et al., 2017) .However , what if only partial gradient information is available? That is , what if one has access to surrogate gradients that are correlated with the true gradient, but may be biased in some unknown fashion? Naïvely , there are two extremal approaches to optimization with surrogate gradients. On one hand, you could ignore the surrogate gradient information entirely and perform zeroth-order optimization, using methods such as evolutionary strategies to estimate a descent direction. These methods exhibit poor convergence properties when the parameter dimension is large BID5 . On the other hand, you could directly feed the surrogate gradients to a first-order optimization algorithm. However , bias in the surrogate gradients will interfere with optimizing the target problem (Tucker et al., 2017) . Ideally , we would like a method that combines the complementary strengths of these two approaches: we would like to combine the unbiased descent direction estimated with evolutionary strategies with the low-variance estimate given by the surrogate gradient. In this work, we propose a method for doing this called guided evolutionary strategies (Guided ES).The critical assumption underlying Guided ES is that we have access to surrogate gradient information, but not the true gradient. This scenario arises in a wide variety of machine learning problems, which typically fall into two categories: cases where the true gradient is unknown or not defined, and cases where the true gradient is hard or expensive to compute. Examples of the former include: models with discrete stochastic variables (where straight through estimators (Bengio et al., Figure 1: (a) Schematic of guided evolutionary strategies. We perform a random search using a distribution (white contours) elongated along a subspace (white arrow) which we are given instead of the true gradient (blue arrow). (b) Comparison of different algorithms on a quadratic loss, where a bias is explicitly added to the gradient to mimic situations where the true gradient is unknown. The loss (left) and correlation between surrogate and true gradient (right) are shown during optimization. See §4.1 for experimental details.2013 ; van den Oord et al., 2017) or Concrete/Gumble-Softmax methods (Maddison et al., 2016; BID12 are commonly used) and learned models in reinforcement learning (e.g. for Q functions (Watkins & Dayan, 1992; Mnih et al., 2013; or value estimation (Mnih et al., 2016) ). For the latter, examples include optimization using truncated backprop through time (Rumelhart et al., 1985; Williams & Peng, 1990; Wu et al., 2018) . Surrogate gradients also arise in situations where the gradients are explicitly modified during training, as in feedback alignment BID17 and related methods (Nøkland, 2016; BID6 .The key idea in Guided ES is to keep track of a low-dimensional subspace, defined by the recent history of surrogate gradients during optimization, which we call the guiding subspace. We then perform a finite difference random search (as in evolutionary strategies) preferentially within this subspace. By concentrating our search samples in a low-dimensional subspace where the true gradient has non-negative support, we dramatically reduce the variance of the search direction.Our contributions in this work are:• a new method for combining surrogate gradient information with random search,• an analysis of the bias-variance tradeoff underlying the technique ( §3.3),• a scheme for choosing optimal hyperparameters for the method ( §3.4), and• applications to example problems ( §4). We have introduced guided evolutionary strategies (Guided ES), an optimization algorithm which combines the benefits of first-order methods and random search, when we have access to surrogate gradients that are correlated with the true gradient. We analyzed the bias-variance tradeoff inherent in our method analytically, and demonstrated the generality of the technique by applying it to unrolled optimization, synthetic gradients, and training neural networks with discrete variables.
We propose an optimization method for when only biased gradients are available--we define a new gradient estimator for this scenario, derive the bias and variance of this estimator, and apply it to example problems. The authors propose an approach that combines random search with the surrogate gradient information and give a discussion on variance-bias trade-off as well as a discussion on hyperparameter optimization.  The paper proposes a method to improve random search by building a subspace of the previous k surrogate gradients. This paper attempts accelerating the OpenAI type evolution by introducing a non-isotrophic distribution with a covariance matrix in the form I + UU^t and external information such as a surrogate gradient to determine U