We consider the problem of unconstrained minimization of a smooth objective
 function in $\mathbb{R}^d$ in setting where only function evaluations are possible. We propose and analyze stochastic zeroth-order method with heavy ball momentum. In particular, we propose, SMTP, a momentum version of the stochastic three-point method (STP) Bergou et al. (2019). We show new complexity results for non-convex, convex and strongly convex functions. We test our method on a collection of learning to continuous control tasks on several MuJoCo Todorov et al. (2012) environments with varying difficulty and compare against STP, other state-of-the-art derivative-free optimization algorithms and against policy gradient methods. SMTP significantly outperforms STP and all other methods that we considered in our numerical experiments. Our second contribution is SMTP with importance sampling which we call SMTP_IS. We provide convergence analysis of this method for non-convex, convex and strongly convex objectives. In this paper, we consider the following minimization problem where f : R d → R is "smooth" but not necessarily a convex function in a Derivative-Free Optimization (DFO) setting where only function evaluations are possible. The function f is bounded from below by f (x * ) where x * is a minimizer. Lastly and throughout the paper, we assume that f is L-smooth. DFO. In DFO setting Conn et al. (2009); Kolda et al. (2003) , the derivatives of the objective function f are not accessible. That is they are either impractical to evaluate, noisy (function f is noisy) (Chen, 2015) or they are simply not available at all. In standard applications of DFO, evaluations of f are only accessible through simulations of black-box engine or software as in reinforcement learning and continuous control environments Todorov et al. (2012) . This setting of optimization problems appears also in applications from computational medicine Marsden et al. (2008) and fluid dynamics Allaire (2001) ; Haslinger & Mäckinen (2003) ; Mohammadi & Pironneau (2001) to localization Marsden et al. (2004; 2007) and continuous control Mania et al. (2018) ; Salimans et al. (2017) to name a few. The literature on DFO for solving (1) is long and rich. The first approaches were based on deterministic direct search (DDS) and they span half a century of work Hooke & Jeeves (1961) ; Su (1979); Torczon (1997) . However, for DDS methods complexity bounds have only been established recently by the work of Vicente and coauthors Vicente (2013); Dodangeh & Vicente (2016) . In particular, the work of Vicente Vicente (2013) showed the first complexity results on non-convex f and the results were extended to better complexities when f is convex Dodangeh & Vicente (2016) . However, there have been several variants of DDS, including randomized approaches Matyas (1965) ; Karmanov (1974a; b) ; Baba (1981) ; Dorea (1983) ; Sarma (1990) . Only very recently, complexity bounds have also been derived for randomized methods Diniz-Ehrhardt et al. (2008) ; Stich et al. (2011); Ghadimi & Lan (2013) ; Ghadimi et al. (2016) ; Gratton et al. (2015) . For instance, the work of Diniz-Ehrhardt et al. (2008) ; Gratton et al. (2015) imposes a decrease condition on whether to accept or reject a step of a set of random directions. Moreover, Nesterov & Spokoiny (2017) derived new complexity bounds when the random directions are normally distributed vectors for both smooth and non-smooth f . They proposed both accelerated and non-accelerated zero-order (ZO) methods. Accelerated derivative-free methods in the case of inexact oracle information was proposed in Dvurechensky et al. (2017) . An extension of Nesterov & Spokoiny (2017) for non-Euclidean proximal setup was proposed by Gorbunov et al. (2018) for the smooth stochastic convex optimization with inexact oracle. More recently and closely related to our work, Bergou et al. (2019) proposed a new randomized direct search method called Stochastic Three Points (STP). At each iteration k STP generates a random search direction s k according to a certain probability law and compares the objective function at three points: current iterate x k , a point in the direction of s k and a point in the direction of −s k with a certain step size α k . The method then chooses the best of these three points as the new iterate: The key properties of STP are its simplicity, generality and practicality. Indeed, the update rule for STP makes it extremely simple to implement, the proofs of convergence results for STP are short and clear and assumptions on random search directions cover a lot of strategies of choosing decent direction and even some of first-order methods fit the STP scheme which makes it a very flexible in comparison with other zeroth-order methods (e.g. two-point evaluations methods like in Nesterov & Spokoiny (2017) , Ghadimi & Lan (2013) , Ghadimi et al. (2016) , Gorbunov et al. (2018) that try to approximate directional derivatives along random direction at each iteration). Motivated by these properties of STP we focus on further developing of this method. We have proposed, SMTP, the first heavy ball momentum DFO based algorithm with convergence rates for non-convex, convex and strongly convex functions under generic sampling direction. We specialize the sampling to the set of coordinate bases and further improve rates by proposing a momentum and importance sampling version SMPT_IS with new convergence rates for non-convex, convex and strongly convex functions too. We conduct large number of experiments on the task of controlling dynamical systems. We outperform two different policy gradient methods and achieve comparable or better performance to the best DFO algorithm (ARS) on the respective environments. Assumption A.2. The probability distribution D on R d satisfies the following properties: 2 is positive and finite. 2. There is a constant µ D > 0 and norm We establish the key lemma which will be used to prove the theorems stated in the paper. Lemma A.1. Assume that f is L-smooth and D satisfies Assumption A.2. Then for the iterates of SMTP the following inequalities hold: and Proof. By induction one can show that That is, for k = 0 this recurrence holds and update rules for z k , x k and v k−1 do not brake it. From this we get Similarly,
We develop and analyze a new derivative free optimization algorithm with momentum and importance sampling with applications to continuous control.
{"src": "scitldr-AIC_train", "paper_id": "HylAoJSKvH"}