The Differentiable Cross-Entropy Method

T HE D IFFERENTIABLEC ROSS-E NTROPYM ETHOD Brandon Amos 1 Denis Y arats 12 1 Facebook AI Research 2 New Y ork University A BSTRACT We study the Cross-Entropy Method (CEM) for the non-convex optimization of a continuous and parameterized objective function and introduce a differentiable variant (DCEM) that enables us to differentiate the output of CEM with respect to the objective function's parameters. In the machine learning setting this brings CEM inside of the end-to-end learning pipeline where this has otherwise been impossible. We show applications in a synthetic energy-based structured prediction task and in non-convex continuous control. In this paper we focus on the setting of optimizing an unconstrained, non-convex, and continuous objective function f θ(x): R n Θ R as ˆ x arg min x f θ(x), where f is parameterized by θ Θ and has inputs x R n . If it exists, some (sub-)derivative θˆ x is useful in the machine learning setting to make the output of the optimization procedure end-to-end learnable. For example, θ could parameterize a predictive model that is generating potential outcomes conditional on x happening that you want to optimize over. End-to-end learning in these settings can be done by defining a loss function L on top of ˆ x and taking gradient steps θL . If f θ were convex this gradient is easy to analyze and compute when it exists and is unique (Gould et al., 2016; Johnson et al., 2016; Amos et al., 2017; Amos & Kolter, 2017). Unfortunately analyzing and computing a "derivative" through the non-convex arg min here is not as easy and is challenging in theory and practice. No such derivative may exist in theory, it might not be unique, and even if it uniquely exists, the numerical solver being used to compute the solution may not find a global or even local optimum of f . One promising direction to sidestep these issues is to approximate the arg min operation with an explicit optimization procedure that is interpreted as just another compute graph and unrolled through.