A Stochastic Derivative Free Optimization Method with Momentum
Authors: Eduard Gorbunov
Adel Bibi
Ozan Sener
El Houcine Bergou
Peter Richtarik
Venue:  (2020)
Keywords: derivative-free optimization
stochastic optimization
heavy ball momentum
importance sampling

Abstract: 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.

Published as a conference paper at ICLR 2020
A STOCHASTIC DERIVATIVE FREE OPTIMIZATION METHOD WITH MOMENTUM
Eduard Gorbunov*
Adel Bibi
MIPT, Russia and IITP RAS, Russia and RANEPA, Russia edua rd. www....obb.oo.wppysseeeeee edu
KAUST, Saudi Arabia
adel bibi (obi@kann @kaust edu.
Ozan Sener
EI Houcine Bergou
Intel Labs
KAUST, Saudi Arabia and MalAGE, INRA, France elhoucine beeroouiina. fr
ozan.senerelntel.com
Peter Richtárik
KAUST, Saudi Arabia and MIPT, Russia peter. richtarik@kaust sa
ABSTRACT
We consider the problem of unconstrained minimization smooth objective function in Rd in setting where only function evaluations are possible. We propose and analyze stochastic zeroth-order method with heavy ball momentum. partieu- lar, propose, SMTP, 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 learning to continuous control tasks on several MuJoCo Todorov et al. (2012) envi- ronments with varying difficulty and compare against STP, other state-of tfee-----teerr art derivative-free optimization algorithms and against policy gradient methods. SMTP significantly outperforms STP and all other methods that considered in numerical experiments. Our second contribution is SMTP with importance sam- pling which we call SMTP We provide convergence analysis of this method for non-convex, convex and strongly convex objectives.
collection of
INTRODUCTION
In this paper, we consider the following minimization problem
min #ER4
f(x).
where f: Rd + R is "smooth" but not necessarily convex function in a Derivative-Free Opti- mization (DFO) setting where only function evaluations are possible. The function f is bounded from below by f(z*) where x is a minimizer. Lastly and throughout the paper, we assume that is L-smooth.
DFO. In DFO setting Conn et al. (2009); Kolda et al. (2003). the derivatives of the objective function are not accessible. That is they are either impractical to evaluate, noisy (function f noisy) (Chen 2015) or they are simply not available at all. In standard applications of DFO, evaluations of are only accessible through simulations of black-box engine or software as in reinforcement learning and continuous control environments Todorov et (2012). This setting of optimization problems appears also in applications from computational medicine Marsden et al. (2008) and fluid dynamics Allaire (200T): Haslinger & Mäckinen (2033): ; Mohammadi & Pironneaul (2001) localization Marsden et al. (007) and continuous control Mania et al. (2018) Salimans et al. (2017) to name a few.
The literature DFO for solving (T) is long and rich. The first approaches were based on deterministic
direct search (DDS) and they span half a century work Hooke & Jeeves [161]] Su (1979) Torezon
'The research of Eduard Gorbunov supported by RFBR, project number 18-31-20005 mol ved

---

Published as a conference paper at ICLR 2020
(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 (013) showed the first complexity results 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) ; Karmannvv (1974a b): [aba [98[]; Dorea (9 Sarma (1990). Only very recently, complexity bounds have al. (2008); (Stich et al. (20TT); Ghadimi & Lan 22133) Ghadimi et al. 2016); Gratton et al. (2015). For instance, the work of Diniz-Erhrraadd al.
also been derived for randomized methods Diniz-Ehrhanee
2008); Gratton et al. (015) imposes a decrease condition on whether accept or reject a
step of 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 (7O) 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- -on-Euclidean proximal setup was proposed by Gorbunov et al. (2018) for the smooth stochastic convex optimization with inexact oracle. In |ttchh (2014a b) authors also consider acceleration of ZO methods and, in partieular, develop the method called SARP, proved that its convergence rate is not worse than for non-accelerated ZO methods and
showed that in some cases it works even better.
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 sy according to a certain probability law and compares the objective function at three points: current iterate zg. a point in the direction of s and a point in the direction of -sk with certain step size Otj. The method then chooses the best of these three points as the new iterate:
Tk+1 arg min (xx), fax + aksk),, fxx a4ss))3
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 lot of strategies of choosing decent direction and even some of first-order methods fit the STP scheme which makes it very flexible in comparison with other zeroth-order methods (e.g. two-point evaluations methods like in Nesterov & Spokoiny (007)), 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.
Momentum. Heavy ball momentun is special technique introduced by Polyak in 1964 Polyak (1964) to get faster convergence to the optimum for the first-order methods. In the original paper, Polyak proved that his method converges locally with O (v log 1/e) rate for twice continuously differentiable y-sooongly convex and L-smooth functions. Despite the long history of this approach, there is still an open question whether heavy ball method converges to the optimum globally with accelerated rate when the objective function is twice continuous differentiable, T-smooth and ju- strongly convex. For this class of functions, only non-accelerated global convergence was proved Ghadimi et al. (2015) and for the special case of quadratic strongly convex and L-smooth functions Lessard ct. al. Lessard et al. (2016) recently proved asymptotic accelerated global convergence. However, heavy ball method performs well in practice and, therefore, is widely used. One can find more detailed survey of the literature about heavy ball momentum in Loizou & Richtárik (2017).
Importance Sampling. Importance sampling has been celebrated and extensively studied in stochas- tic gradient based methods IZhao & Zhang (2015) or in coordinate based methods Richtárik & Takáe (2016). Only very recently, [Bibi et al. (2019) proposed, STP_TS, the first DFO algorithm with importance sampling. In particular, under coordinate-wise smooth function, they show that sampling coordinate directions, can be generalized to arbitrary directions, with probabilities proportional the function coordinate smoothness constants, improves the leading constant by the same factor typically gained in gradient based methods.
Contributions. Our contributions can be summarized into three folds.
First ZO method with heavy ball momentum. Motivated by practical effectiveness of first-order momentum heavy ball method, we introduce momentum into STP method and
We will refer to this as momentum.
2

---

Published as a conference paper at ICLR 2020
Algorithm 1 SMTP: Stochastic Momentum Three Points
Require: learning rates {7 J220. starting point x E R D ー distribution on RR. 8/<88 <1 momentum parameter
1: Set v = 0 and 2 = x="
2: for k= 0, 1.... do
3: Sample 8 ~ D
4: Let vf = 10*==1 + s and ot Brk-1 zt
5:
Let # k++ = x² - -h and ghtt =x² - gk
6:
Let #4
k+1 k+1 3
I-8 of and 2et1 k+2
3* ck
I-p
Set 2h11 arg min {f(=*), f( / [) [==
7:
k+1
if x+1 =24 -t11
k+1 if 2 = 2 R+1
8:
Set x k+1
if =+1 -kt1
and wh+
k+l
if 2 2ht1
xt if 2 zh
o if ght1 2
9:
end for
propose new DFO algorithm with heavy ball momentum (SMTP). We summarized the method in Algorithm 1 with theoretical guarantees for non-convex, convex and strongly convex functions under generic sampling directions D. We emphasize that the SMTP with momentum is not straightforward generalization of STP and Polyak's method and requires insights from virtual iterates analysis from Yang et al. (2016).
To the best of our knowledge it is the first analysis of derivative-free free method with heavy ball momentum, i.c. we show that the same momentum trick that works for the first order method could be applied for zeroth-order methods as well.
First ZO method with both heavy ball momentum and importance sampling. In order get more gain from momentum in the when the sampling directions are coordinate directions and the objective function is coordinate-wiss L-smooth (see Assumption 4.1). we consider importance sampling to the above method. In fact, we propose the first zeroth-order momentum method with importance sampling (SMTP_ [_)) summarized in Algorithm 2 with theoretical guarantees for non-convex, convex and strongly convex functions. The details and proofs are left for Section 4 and Appendix
Practicality. We conduct extensive experiments on continuous control tasks from the MuJoCo suite Todorov et al. (2012) following recent success of DFO compared model- free reinforcement learning Mania et al. (2018); Salimans et al. (2017). We achieve with SMTP_1 IS the state-of-the-an results on across tested environments on the continuous control outperforming DFO Mania et al. (2018) and policy gradient methods Schulman et al. (201)); Rajeswaran et al. (2017).
We provide more detailed comparison of SMTP and SMTP_IS in Section E.4 of the Appendix.
NOTATION AND DEFINITIONS
We use || lpp to define fn-norm of the vector x E IR:: ||>|| def [I l2:1") 1/8
for p 2 and 22....dd,
||0|| def mmxxcej]] |x;] where x; the i-th component of vector x, [d] = {1, (1,2....,de d). Operator E[-] denotes mathematical expectation with respect to all randomness and EysDl [-] denotes conditional expectation w.r.t. randomness coming from random vector which is sampled from probability
distribution D on Rd. To denote standard inner product of two vectors x, E IRd we use (x, def TzAli e; denotes i-th coordinate vector from standard basis in Rd i.c. Ei 2ze,. We use
d
||- II define the conjugate norm for the norm ||: ||=||* def max ((a, x)) a Rd ||a|| 1].
As mention in the introduction assume throughout the pape that the objective function is L-smooth.
We will thinner assumption in Section
3

---

Published as a conference paper at ICLR 2020
SMTP Complexity
Importance Sampling
SMTP_ Complexity
Assumptions on f
Theorem
Theorem
None
2ra "Sp"" Ri
3.1
P
fiy
2ngid 2r
E.
KR 2i In
Convex, Ro < oo
In
3.2
P;
E.2
p-strongly
In
3.5
P L,
L
In
Bro
E.S
/
Table 1: Summary of the new derived complexity results of SMTP and SMTP IS. The complexities for SMTP are under generic sampling distribution 'D satisfying Assumption 3.1 while for SMTP _ under arbitrary discrete sampling from set of coordinate directions following Bibi al. (2019) where we propose an importance sampling that improves the leading constant marked in red. Note that vo [(x0) f(x.) and that all assumptions listed in addition to Assumption 2.1
Complexity means number of iterations in order guarantee E V f= D S for the non-convex case, E [f [x*)] < & for convex and strongly convex cases. Ro 3o is the radius in || Il norm of bounded level set where the exact definition is given in Assumption 3.2 We notice that for SMTP_IS || IlD = || and |l = || Ilso in non-convex and convex cases and
|| || ||2 in the strongly convex case.
Assumption 2.1. (L-smoothness) We say that L-smooth if L||x vll2
[V V/(w)l
Va,y Rd.
From this definition one can obtain
If(v) f(z) (Vf(x), 2)1 2 - =122 Yx,y Rd and if additionally f convex, i.e. f(v) f(x) (V)()), 2). have |VS( < 21((x) <2((())))))))))))))))))))))))))) f(x)), Vo Rdd
(3)
(4)
STOCHASTIC MOMENTUM THREE POINTS (SMTP)
Our analysis of SMTP is based on the following key assumption.
Assumption 3.1. The probability distribution DD on I&d satisfies the following properties:
1. The quantity YD def EE-DDI>l1B is fnite.
2. There is a constant > for norm || -1l in R such that for all E Rd
En-Dl s) 2 pDllgl|D.
(5)
Some examples of distributions that meet above assumption are described in Lemma 3.4 from Bergou et al. (2019). For convenience provide the statement of the lemma in the Appendix (see
Lemma F.I)
Recall that one possible view on STP Bergou et (2019) Vf(=*) in the update rule for the gradient descent x F+1 I² /f((*" by t where s is sampled from distribution satisfied Assumption 3.1 and then select k as the best point in terms of functional value among =² _ R + s we will get exactly STP method. However, gradient descent is not the best algorithm to solve unconstrained smooth minimization problems and the natural idea is to to perform the same substitution-trick with more efficient first-order methods than gradient descent.
following. we substitute gradient
We put our attention on Polyak's heavy ball method where the update rule could be written in the following form:
(6) As in STP, we substitute (*(*t) by t and consider new sequences {uf Jez0 and {u Ja20 defined in the Algorithm 1 However, it is not straightforward how choose next x+1 and x and
B-- + V)(**), ++1 - * k
4

---

Published as a conference paper at ICLR 2020
A+1 the virtual iterates analysis Yang al. (2016) hints the update rule. We consider new iterates 24 #4 af+1 7/8
D vt and define g as arg min (f(=*), [(=++1), (( (2=+t)) I-B of and = = k++
I-g
Next we update xh+1 and v in order to have the same relationship between =*+1, _ and E as between 24 -ff and of and 2++1 -hhر and v Such scheme allows easily apply virtual iterates analysis and and generalize Key Lemma from Bergou et al. (2019) which is the main tool in the analysis of STP.
By definition of * get that the sequence (f(2")) is monotone:
f(z S f(2²)
4k 2 0.
Now, we establish the key result which will be used to prove the main complexity results and remaining theorems in this section.
Lemma 3.1. Assume that f is L-smooth and D satisfies Assumption 3.1
Then for the iterates of
SMTP the following inequalities hold:
7k
L(>,})
f(z S x((2))
1- (Vf(z*)
s*),+
2(1 B)2 ||
(8)
and
ENAND [f( S {((h))
HD
Vf
\>(>>><<
L(7")>2D 2(1 -3
(9)
1
3.1 NON-CONVEX CASE
In this section, show complexity results for Algorithm in the when is allowed to be non-convex. In particular, we show that SMTP in Algorithm | the same order as classical bounds, i.e. 1/vK where K is the number of iterations, in the literature. We notice that query complexity (i.e. number of oracle calls) of SMTP coincides with its iteration complexity up to numerical constant factor. For clarity and completeness, proofs are left for the appendix.
guarantees complexity bounds with
Theorem 3.1. Let Assumptions 2.1 |
3.1 be satisfied. Let SMTP with 7* ア 0 produce points {2 21 ,,..,,.,,, =K-1 -13 and z is chosen uniformly at random among them. Then
((((==))((xz)) 2u 1
LAYD
[IV)(*>>)))) Mlll
(10)
KTHD
Moreover, if we choose
the complexity (10) reduces to V
((1
(1-B)){(=))) f(x)))
IAAND 2pd(1 -3)
E [[] [|l]] s VK
(11)
7OHD
2(1 (0=-))([22)) LnD
Then 7o
minimizes the right-hand side of
11 and this choice we have
E [IVS< [bb] < /2(l(z0) f(x LTD
(12)
PDVK
In other words, the above theorem states that SMTP converges no worse than STP for non-convex problems to the stationary point. In the next sections also show that theoretical convergence guarantees for SMTP are not worse than for STP for convex and strongly convex problems. However, practice SMTP significantly outperforms STP. So, the relationship between SMTP and STP correlates with the known in the literature relationship between Polyak's heavy ball method and gradient descent.
3.2 CONVEX CASE
In this section, present complexity results for A when is convex. In particular, show that this method guarantees complexity bounds with the same order as classical bounds, i.. 1/ K, in the literature. We will need the following additional assumption in the sequel.
5

---

Published as a conference paper at ICLR 2020
Assumption 3.2. We assume that is convex, has minimizer x² and has bounded level set at x!:
Ro def max (1|x-x")) 1()))
f(x) ( S
f(x9) < +00,
(13)
where || def max ((5.2) ) ||>|| 2 1} defines the dual norm to || -II
From the above assumption and Souchy-Schwarte inequality we get the following implication:
((x) S f(x)) - [(x.) S (VI(x), x²) < [V/[(>)l=ll> - x'11 S (o)lV/(>)ll,,
which implies
[Vf())l 2 f(x)= - f(x))
Væ f(x) S f(2o).
(14)
Ro
Theorem 3.2 (Constant stepsize). Let Assumptions
2.1
3. and 3.2 be satisfied. we set 7t =7 <
Ro then for the iterates of SMTP method the following inequality holds:
(1 (1-(1-90)
(1
7DD
(
+ Lo
(15)
R)
2(1 - B)DD
we choose 7 <(1-0)pp for some 0 E Ro
LyD Ri and run SMTP for ls = K iterations where n
K = RyDR
(2f((x)) f(xx))
In
(16)
then we will get E [f(=*)] - f(x²)= SE.
In order to get rid of factor In ( in the complexity consider decreasing stepsizes.
Theorem 3.3 (Decreasing stepsizes). Let Assumptions 2.7 3.1 and 3.2 be satisfied. If set
7th 2 ak40. where a (1-B)Ro
up and 2 2, then for the iterates of SMIP method the following
inequality holds:
1 max ((x9)- f(x"),
2L
E [f((2)] - f(x))
(17)
w/ +1
a0(1 B)3
where 1) def a. Then, if we choose nht iterations where
a2k42 where
2a
= (1-B) and run SMTP for k = K
1 2R max ((
2(1 - -3
K =
e> 0,
(18)
we get E [f(2*]] SE. S..
We notice that if we choose 3 sufficiently close to 1, we will obtain from the formula Lym
18 that
K
3.3 STRONGLY CONVEX CASE
In this section we present our complexity results for Algorithm Twhen is p-strongly convex. Assumption 3.3. We assume that f j-strongly convex with respect to the norm || I
f(v) 2 (Vf(z) + 1 (1ly- - x11b)) YoHERR
(19)
It is well known that strong convexity implies
[V 2p ( -(x)))
(20)

---

Published as a conference paper at ICLR 2020
Theorem 3.4 ioolution-deeendern stepsizes). Let Assumptions 2.7 3.1 and
3.3 be satisfied. If we
set 7 (1-9)6-u2 (2 f(x*)) for some 02 (0, 2) such that inf {20g 7D0%)
R20
(0, 4/wrbn), then for the iserates of SMTP, the following inequality holds:
E [ S(x²) (1-0)))11100))) 1--122)) (J(=9) s(x)))
(21)
Then, If we run SMTP for k = K iterations where
f(a9))((11))
K In
E> 0,
(22)
0p
where k def La is the condition number of the objective, we will get E [f(z*)] - f(x)) Se.
Note that the previous result uses stepsizes that depends on the optimal solution f(x") which is often not known in practice. The next theorem removes this drawback without spoiling the convergence rate. However, we need an additional assumption on the distribution D and one extra function evaluation.
Assumption 3.4. We assume that for all
we have ||s 2
Theorem 3.5 (Solution-free stepsizes). Let Assumptions
2.7
3.
3.3 and 3.4 be satisfied. If addi-
tionally we compute f(z + t,*), set 7 = (1-81)f(=* (===)
(L)) for t >> and assume that D such that p2 S 1/p, then for the iterates of SMIP the following inequality holds:
(LL)
(1-1)))) 1
(1- p-6u
12222
E [[(=a)] 1(x²)
(((a)-1(33)) + 8p351
(23)
Moreover, for any e > 0 if we set such that
4s
OC1S
(24)
I
and run SMTP for K iterations where
K
2(f(x0)-
-=f(=)))((x))) ff(x)))
K =
In
(25)
2
PDD
where K. def L the condition number of J. we will have E [](**)] - [xx)
Se. Sa.
4 STOCHASTIC MOMENTUM THREE POINTS WITH IMPORTANCE SAMPLING (SMTP_IS
In this section consider another assumption, in similar spirit Bibi et al. (2019), the objective. Assumption 4.1 (Coordinate-wird wise L-smoothness). We assume that the objective f has coordinate- wise Lipschitz gradient, with Lipschitz constants Li...., La > 0, i.e.
f(x he,) s f(x) Vef(x)h Tip n22
Yx BRER
(26)
where (x)(x) is i-th partial derivative of J at the point x.
For this kind of problems we modify SMTP and present STMP_ method in Algorithm 2 general, the idea behind methods with importance sampling and, in particular, behind SMTP IS is to adjust probabilities sampling in such a way that gives better convergence guarantees. In the case when f satisfies coordinate- wise L-smoothness and Lipschitz constants L; known it is natural to sample direction s = e; with probability depending on L, (e.g. proportional to L,). One can find more detailed discussion of the importance sampling in Zhao & Zhang (2015) and Richtárik & Takáč (2016).
Now, establish the key result which will be used prove the main complexity results of STMP_TS.
7

---

end for Published as a conference paper at ICLR 2020
Algorithm 2 SIMTP_IS, Stochastic Momentum Three Points with Importance Sampling
Require: stepsize parameters w1..... Wy >> probabilities PI,....PP > 0 summing 1, starting < 3
point x" E _R_ 0
momentum parameter
Set e- 0 and 00 x
2: for k = 0, 1.... do
3: Select iι = with probability p;
4: Choose stepsize y, proportional to BB
wiy
5: Let wf Bu + eie and vf
Cik
6:
Let 22 x² - u and x++1 r² - -
Let 24 kt1
I-g of and 2tt1 xxtt1 2 o
7:
I-p
8:
Set k+1 arg min {f(2²), ((2 {(=
k+1
if gk1 =24- =+11
04 k+1
if zht11 = 24 k+1
9: Set x
k+1
if 2 = _tt1
and ukt1
k+l
if if = k+1
if if = zh
ok if 2 =
10:
Lemma 4.1. Assume that f satisfies Assumption 4.1 inequalities hold:
Then for the iterates of SMTP IS the following
z
V. s(2h)) + Li, (
J( S f(z²)
(27)
2(1 - B)
and
EgtnD [f(] S f(((t)
1
E
V,
f(z
1
E [L (741) | (28)
1-3
2(1 B)²
Due to the page limitation, we provide the complexity results of SMTP IS in the Appendix.
5 EXPERIMENTS
Experimental Setup. We conduct extensive experiments on challenging non-convex problems on the continuous control task from the MuloCO suit Todorov et al. (2012). In particular, we address the problem of model-free control of a dynamical system. Policy gradient methods for model-free reinforcement learning algorithms provide an off-the-shelf model-free approach learn how to control dynamical system and are often benchmarked in a simulator. We compare our proposed momentum stochastic three points method SMTP and the momentum with importance sampling version SMTP IS against state-of-art DFO based methods as STP IS Bibi et al. (2019) and ARS Mania et al. 2018)). Moreover, we also compare against classical policy gradient methods as TRPO Schulman et al. (2015) and NG Rajeswaran et al. (2017). We conduct experiments several environments with varying difficulty Swimmer-vi, Hopper-vl, Hww.HHeaaaaaaaaaaaee Ant-vi. and Humanoid-vi.
Note that due to the stochastic nature of problem where f is stochastic, we use the mean of the function values of f (a**), f(+tt and f (a:h.)
Algorithm 1 over K observations. Similar to the work in Bibi et al. (2019). we use K = for Swimmer---..... - vI, Hal @elffheetah--ee v1,
= 4 for both Hopper-vi and 40 for Ant-vl and Humanoide d-v1. Similar to Bibi al. (2019). these values were chosen based on the validation performance over the grid that is K E 2, 8,8, 16) for the smaller dimensional problems Swimmer-vl. Hopper-vl, aa and K E {20, 40, 80, 120) for larger dimensional problems Ant-vi. and Humanoid-vl. As for the momentum term, for SMTP we set 3 0.5. For SMTP _N,, as the smoothness constants are not available for continuous control, we use the coordinate smoothness constants of 0 pa- rameterized smooth function fe (multi-layer perceptron) that estimates f. In particular, consider running any DFO for n steps; with the queried sampled {z,, f(x:)) we estimate f by solving 0n+1 = argming (z,)),) - f(x,; 2) See Bibi et al. (201)) for further implementation details
"The code will be made available online upon acceptance of this work.
8

---

Published as a conference paper at ICLR 2020
Swimmee-v1
Hopper-vi
HalfCheetahvvl
Avurage Rawwudd
Rowwrr
Avungg Rowned
5230
0330
200
2000
3330
2239
2320
4008
$200
19590
1200 16206
Number of Episodes
Number of Episodes
Number of Episodes
Ant-v1
Homanold-v1
Averago Reward
3000
Avurage
STP
2000
SMTP
100000
200000
350000
429038
Number of Egilodes
Number of Episodes
Figure 1: SMTP is far superior to STP on all 5 different MuJoCo tasks particularly on the high dimensional numanoid-vi problem. The horizontal dashed lines are the thresholds used in Table demonstrate complexity each method.
Table 2: For each MuJoCo task, we report the average number of episodes required to achieve predefined reward threshold. Results for our method averaged over five random seeds, the rest is copied from (Mania et al. 2018) (N/A means the method failed to reach the threshold. UNK means the results unknown since they are not reported in the literature.)
Threshold
STP
STP
SMTP
SMT
ARS(V1-1)
ARS(V2-1)
NG-lin
TRPO-nn
Swimmer-yy
325
320
100
100
427
1450
N/A
Hopper-vl
3120
3970
2400
1264
1408
51840
1973
13920
10000
Hal ahhe
3430
13760
4420
1872
1624
8106
1707
11250
4250
Ant-vi
3580
107220
43860
19890
14420
58133
20800
39240
73500
Humanoid-vl 6000
N/A
530200
161230
207160
N/A
142600
130000
UNK
as we follow the same experimental procedure. contrast _IP, our method (SMTP) does not
required sampling from directions in the canonical basis; hence, we use directions from standard Normal distribution in each iteration. For SMTP SMTP_IS, we follow similar procedure Bibi al.) (2019) and sample from columns of random matrix B.
Similar to standard practice, we perform experiments with 5 different initialization and measure the average reward, in continuous control we are maximizing the reward function J, and best and worst run per iteration. We compare algorithms terms of reward vs. sample complexity.
Comparison Against STP. Our method improves sample complexity of STP and STP_IS sig- nificantly. Especially for high dimensional problems like Ant Ant-vl and Humanoid-va ivvii, sample efficiency of SMIP is at least twice the STP. Moreover, SMTP IS helps in some experiments by improving over SMTP. However, this is not consistent in all environments. We believe this is largely due to the fact that SMTP IS can only handle sampling from canonical basis similar to STP_ _IS.
We compare our method with state-of-the-an DFO and policy gradient algorithms. For the environments, Swi momerrr,v,, Hopper-vi, Hal WalfCheetah-u and Ant-v1, our method outperforms the state-of-the-art results. Whereas for Humanoid vl, our methods results comparable sample complexity.
Comparison Against State-of-The-Art.
CONCLUSION
We have proposed, SMIP, 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 momentum and importance sampling version SMP T_ITSIS with new convergence rates for non-convex, convex and strongly convex functions too. We conduct large number of experiments the task of

---

Published as a conference paper at ICLR 2020
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.
REFERENCES
G. Allaire. Shape Optimization by the Homogenization Method. Springer, New York, USA, 2001.
N. Baba. Convergence of random optimization method for constrained optimization problems. Journal of Optimization Theory and Applications, 33:1-11, 1981.
El Houcine Bergou, Eduard Gorbunov, and Peter Richtárik. Stochastic three points method unconstrained smooth minimization. arXiv preprint 190.vv1902.0355 2019.
Adel Bibi, EI Houcine Bergou, Ozan Sener, Bernard Chanem, and Peter Richtárik. Stochastic derivative-fiee optimization method with importance sampling. arXiv preprint arXiv: 190p::/222.22.... 2019.
Ruobing Chen. Stochastic derivative-free optimization of noisy functions. PhD thesis at Lehigh University. 2015.
A. R. Conn, K. Scheinberg, and L. N. Vicente. Introduction to Derivative-Free Optimization. SIAM, Philadelphia. PA, USA, 2009.
M. A. Diniz-Ehrhardt, unconstrained optimization. Journal of Optimization Theory and Applications, 219:383-39 3977, 2008 Martinez, and M. Raydan. A derivative-free nommonotone linc-search technique for
Mahdi Dodangeh and Lufs N Vicente. Worst case complexity of direct search under convexity, Mathematical Programming. 155(1 (3((12)):5 20:307)3330330 -32,, 2016.
C. Dorca. Expected number of steps of a random optimization method. Journal of Optimization Theory and Applications, 39: 171, 1983.
Pavel Dvurechensky, Alexander Gasnikov, and Alexander Tiurin. Randomized similar triangles method: unifying framework for accelerated randomized optimization methods (coordinate descent, directional search, derivative-free method). arXiv preprint arXiv: (00::70070888 2017.
Euhanna Ghadimi, Hamid Reza Feyzmahdavian, and Mikael Johansson. Global convergence of the heavy-ball method for convex optimization. In 2015 European Control Conference (ECC), pp. 310-315. IEEE, 2015.
Saeed Ghadimi and Guanghui Lan. Stochastic first-and zeroth methods for nonconvex stochastic program- ming. SIAM Journal on Optimization, 23(4):2341-2366 2013.
Saced Ghadimi, Guanghui Lan, and Hongchao Zhang. Mini-batch stochastic approximation methods for nonconvex stochastic compositc optimization. Mathematical Programming, 155(1-2):277335, 2016.
Gorbunov, Dvurechensky, and Gasnikov, accelerated method for derivative-fre free smooth stochastic convex optimization. arXiv preprint 102.00000000002 2018
Gratton, C. Royer, L. Vicente, and Z. Zhang. Direct search based on probabilistic descent. SIAM Journal on Optimization, 25(3):1515-1541, 2015.
J. Haslinger and R.A.E. Mäckinen. Introduction to Shape Optimization: Theory, Approximation, and Computa- tion. SIAM, Philadelphia, PA, USA, 2003.
R. Hooke and T.A. Jeeves. Direct search solution of numerical and statistical problems. J. Assoc. Comput. Mach, 8:212-229, 1961.
G. Karmanov. Convergence estimates for iterative minimization methods, USSR Computational Mathematics and Mathematical Physics, 14:1-13, 1974a.
G. Karmanov. convergence of a random search method in convex minimization problems. Theory of Probability and its applications, 19:788-794, 1974b.
T. G. Kolda, R. M. Lewis, and J. Torezon. Optimization by direct search: New perspectives on some classical and modern methods. SIAM Review, 45:385-482, 2003.
Laurent Lessard, Benjamin Recht, and Andrew Packard. Analysis and design of optimization algorithms via integral quadratic constraints. SIAM Journal Optimization, 26(1):57-95, 2016.
10

---

Published as a conference paper at ICLR 2020
Nicolas Loizou and Peter Richtárik. Momentum and stochastic momentum for stochastic gradient, newton. proximal point and subspace descent methods. arXiv preprint 17X1v:1712.09677, 2017.
Horia Mania, Aurelia Guy, and Benjamin Recht. Simple random search provides competitive approach reinforcement learning. arXiv preprint arXiv: /a00:07005 2018.
A. L. Marsden, M. Wang. J. E. Dennis, and P. Moin. Optimal acroacustic shape design using the surrogate management framework. Optimization and Engineering, 5:235-262, 2004.
A. L. Marsden, M. Wang. J. E. Dennis, and P. Moin. Trailing-edge noise reduction using derivative-free optimization and large-eddy simulation, Journal of Fluid Mechanics, 5:235-262, 2007.
A. L. Marsden, J. A. Feinstein, and C. A. Taylor. A computational framework for Serivative--ree optimization of cardiovascular geometries. Computer Methods Applied Mechanics and Engineering, 197: 197:1890-1905. 2008.
J. Matyas. Random optimization. Automation and Remote Control, 26:246-253, 1965.
Konstantin Mishchenko, Eduard Gorbunov. Martin Takáč, and Peter Richtárik. Distributed learning with compressed gradient differences. arXiv preprint urXiv:1901.0922 09269, 2019.
B. Mohammadi and O. Pironneau. Applied Shape Optinization for Fluids. Clarendon Press, Oxford, 2001.
Y. Nesterov and Spokoiny. Random gradient-free minimization convex functions. Foundations of Computational Mathematics, 17:527-566, 2017.
Boris Polyak. Some methods of speeding up the convergence of iteration methods. USSR Computational Mathematics and Mathematical Physics, 4(5):1-17, 1964.
Aravind Rajeswaran, Kendall Lowrey, Emanuel Todorov, Sham M Kakade. Towards generalization and simplicity in continuous control. In Advances in Neural Information Processing Systems, pp. 6550-6561, 2017.
Peter Richtárik and Martin Takáč. On optimal probabilities in stochastic coordinate descent methods. Optimiza- tion Letters, 10(6): 2016.
Tim Salimans, Jonathan Ho, Xi Chen, Szymon Sidor, and Ilya Sutskever. Evolution strategies as scalable alternative to reinforeement learning. arXiv preprint arXiv: 038664 2017.
M. Sarma. On the convergence the Baba and Dorea random optimization methods. Journal of Optimization Theory and Applications, 66:337-343, 1990.
John Schulman, Sergey Levine, Picter Abbeel, Michael Jordan, and Philipp Moritz. Trust region policy optimization. In International Conference on Machine Learning, pp. 1889-1897 1897, 2015.
U. Stich, L., Muller, and B. Gartner. Optimization convex functions with random pursuit. arXiv preprint orXiv:/111 111.0144, 2011.
Sebastian Stich. Convex optimization with random pursuit. PhD thesis, ETH Zurich, 2014a.
Sehastian Urban Stich. On low complexity acceleration techniques for randomized optimization. International Conference on Parallel Problem Solving from Nature, pp. 130-140. Springer, 2014b.
Yu Wen Su. Positive basis and class of direct search techniques. Scientia Sinica (in Chinese), 9S11:533-77 1979.
Emanuel Todorov, Tom Erez, and Yuval Tassa. Mujoco: A physics engine for model-based control. In Intelligent Robots Syxtems (IROS), 2012 JEEE/RSJ International Conference on, pp. 5026-5033. IEEE, 2012.
Virginia Torezon. On the convergence of pattern search algorithms. SIAM Journal optimization, 7(1):1225 1997.
Luis Nunes Vicente. Worst case complexity of direct search. EURO Jourmal Computational Optimization, 1 (1-2):143 2013.
Tianbao Yang, Qihang Lin, and Zhe Li. Unified convergence analysis of stochastic momentum methods for convex and non-convex optimization. arXiv preprint 1rX1v:1604.03257 2016.
Peilin Zhao and Tong Zhang. Stochastic optimization with importance sampling for regularized loss minimization. In international conference machine learning, pp. 1-9, 2015.
11

---

Published as a conference paper at ICLR 2020
A Stochastic Derivative Free Optimization Method with Momentum
(Supplementary Material)
A PRELIMINARIES
We first list the main assumptions.
Assumption A.1. (I-smoothnesss) We say that is T-smooth if:
-Vf))ll & L|| - yll2 Va, R
(29)
Assumption A.2. The probability distribution DD on IRd satisfies the following properties:
1. The quantity TDD def E.-Dl|s|lä positive finite.
2. There is a constant pip and norm || |/D on IR such that for all g E Rdd
EgeDl (g, 8)1 2 PD vDllg//D
(30)
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 SMTP the following inequalities hold:
Then for the iterates of
nk
_(?,1)2
1( S s(=h) 1-
(0((1))**)11
|1
(31)
2(1 B32
and
[s(* + -(
BAND [5(*ht|)| S S((
(32)
1
2(1 -3)2
Proof. By induction one can show that
* k-1
x
(33)
1
That is, for & this recurrence holds and update rules for 2t xx and k-1 do not brake it. From this we get
*
x - n g
k+1
k+1
U
*
BB b
x
3
3
k
Similarly,
*k B
2/3
k+1
x
x+1
11
x
* ck
3 b
1
3
*B 3
7k
b
k-
+
1 B
3
12

---

Published as a conference paper at ICLR 2020
It implies that
L
f(x+t)) f(z²) + (V --1 - 26) +
2 =| x+1 2²12
7* - (>((t) st)
L(>²)²
s(
2(1 3)2 11
and
f* f( I f(z + 1- (Vf(2*), s*) + L(>*²² }²
1
2(1 3)2
Unifying these two inequalities we get
7* T VV ,,
=(>*)²
f(skt1) < min[ s(=)t)))) 5(x)) (,
2(1 B)2 ||
which proves (31 Finally, taking the expectation ESAAD of both sides of the previous inequality and invoking Assumption A.2 we obtain
"n 1
Vf(* Il + I(>*)> 2(1 B)2
ESAND [
B NON-CONVEX CASE
Theorem B.1. Let Assumptions A.I and A.2 be satisfied. Let SMTP with 7t m > 0 produce points
(2 --11) and z is chosen uniformly at random among them. Then
[IVf( [all s (1- (=-) ((x))
LYTD 2u - 3)
(34)
KYHD
Moreover, if we choose q
the complexity (34) reduces
v
1 ((1 (1- (-=))((=---((a -
LAOND
E [ [|l]]
(35)
VK
YolD
2p 3)
Then 7o / /20-0)((())==((")) lnp
minimizes the right-hand side of 35 and for this choice we have
E [IVf(E>>)l> [|o] < v2(f(z)) f(x²) LND
(36)
PDVK
Proof. Taking full expectation from both sides of inequality
32
we get
E [[>}}>] < (1- B)E [f(2)]
f(= k1))
LYTD
7/D
2μd
Further, summing up the results for k = 0, 1.... 1, dividing both sides of the obtained inequality by K and using tower property of the mathematical expectation get
K-1 Σ E
(1 -1- -=)(((=²)) - f(x"))
LYYD
E [IV
[al]
[IVf(>>))
<
KuHD
2 (1 B)
K=
The last part where 7
is straightforward
VK
13

---

Published as a conference paper at ICLR 2020
C CONVEX CASE
Assumption C.I. We assume that f is convex, has a minimizer x² and has bounded level set at x.:
Ro def max {11x - 2nIl f(x) - fxx0) < +00,
(37)
where |Ell def
max ((5, ||:|| S 1) defines the dual norm to
||D-
Theorem C.1 (Constant stepsize). Let Assumptions A.1 A.2 and C.1 be satisfied. If we set xf
(1 then for the iterates of SMTP method the following inequality holds:
y < AD
E f(x))
(1 1
7/1
(1(69)-((x)) [(x))) + Ro
(f(x9)
(38)
-1- R-
2(1 3)pD
If we choose y= E(1-8)wD for some LnD
L and run SMTP for k K iterations where E
K IIDDRi Rg
(([(x²) [(x)))
(39)
1
8
then will get E [[(= f(x") S.
Proof. From the 32) and monotonicity of (f(2*))k0 we have
LD2PD
E [f(
< f(*²) 7D [ )1
1-
2(1 33
14
f(a²)
(1 (1-3)Ro (f(=*) - f((x))) +
7PD
I 1^27D
2(1 - 3)
Taking full expectation, subtracting f(x)) from the both sides of the previous inequality and using the tower property of mathematical expectation we get
L
E [f( -(=-1)--(()))
f(x')] s (1
7ID
E[5(2*)-
(40)
Ry
2(1 3)2
Since (1-8)Ro the term PD
1-
3/4 (1-9)R,
is positive and we can unroll the recurrence
440)
LT2DD k-1
E [|(**) [(x*)] <
1
7HD
((==)-((x²)) +
TDD
(1
2(1 B)²
(1 3R)
1=0
711DD
(S(x9) 5(x)))
1T27D0
Σ
71D
(1-B)a -B
2(1 -3)2 1=0
(1 -3)Ro
1
714D
(f(29) f(x))) +
1722700
(1 - Ro
(1 Ro
2(1 -3)2
YPD
7/1D
k
(f(x9) - -0(=)))))))))))))))))))))))))- 2(1 B)
LAND Ro
(1 -3
Lastly, putting 7
=(1- 9ype and Lovo
K from 39 in
38
we have
K (((9))((x²)) +
E[S(=K) (ack)--((e f(x*)
EKD
RrDRy
E 1
exp
K
(1(69) f(x'))
Lyp Rg
E.
2
2
14

---

Published as a conference paper at ICLR 2020
Next technical lemma from Mishchenko al. (2019) We provide the original proof for completeness.
Lemma C.1 (Lemma 6 from Mishchenko et al. (2019). ) Let a sequence {a² J2z0 satisfy inequality
al+1 S (1 - 10--aaaaaa x*aa + ( N for any positive 7 S "o with some constants > 0, N > 0, 70 >
Further, let 2 and take such that S ad and du S C. Then, it holds
g +1
if we set 7h= ak+00
Proof. We will show the inequality for a by induction. Since inequality ao S C' is one of our assumptions, we have the initial step of the induction. To prove the inductive step, consider
r+1 S (1 <1-~>a)aa + (G (1
2a
OC
C
0ox (ack + 0)2
ak +
ok +
To show that the right-hand side is upper bounded by a(k+1)+6 one needs have, after multiplying both sides by (ak + (ak + ()(C))
#C
(1-aa) ak + ) ) +ak++++)) at + +
2a
ak + I ak - 0,
which is equivalent to
ak +
S 0.
ak +
The last inequality is trivially satisfied for all h: #20 0.
Theorem C.2 (Decreasing stepsizes). Let Assumptions A. A.2 and C.1 be satisfied. If we set
ght "k40 where (1-B)Re and > 2, then for the iterates of SMTP method the following
inequality holds:
2L
E [s(**)] - {(x))
n/ +1 max ((())-(xx),,
(41)
a0(1 - B)2
where 1) def 9. Then, if we choose gh iterations where
2n where a = (1-8)Ro and run SMTP for = K
pD
a²k+2
K = - 2R max (11-3(((2))
2(1 -3)
$ s> 0,
(42)
we get E [f(2 f(x") S..
Proof.
In 44 we proved that
E
<
7HD
E -
L
Ro
2(1 B3
Having that, we can apply Lemma C.1 to the sequence E [f( - f(x*)]. The constants for
the lemma are: N 2x is equivalent to the choice 0 2. In this case, have al C choosing nh a4442
Li
3y and C max f(x))- f(x*), at B }. Lastly,
2L7g
2(1
max f(x)) - f(x*), (T-B)=
Lon and =
Putting these parameters and K
21-38-R
from 42) in the 41 get the result.
15

---

Published as a conference paper at ICLR 2020
D STRONGLY CONVEX CASE
Assumption D.1. We assume that f is p-strongly convex with respect to the norm || 11.llb lb::
f(v) 2 f(x) + (VI(x), x) + 22(1lx 1oy--Ilig =lIb), Vx,y E RR.
(43)
It is well known that strong convexity implies
- [V 2 2p (
(44)
Theorem D.1 (Solution-dependent stepsizes). Let Assumptions A. A.2 and D. be satisfied. If we
R (1-9)6upm (=+ - f(x*)) for some f% E (0,2) such that inf (28, - 700%) E
set
L
k20
(0. m then for the iterates of SMTP the following inequality holds:
(1- -- (((=))((x"))
E [ f(x')
(45)
L
If we run SMTP for ks K iterations where
[[(²) (((0)-((0)))
== K In 0PD
E 8>0, 0,
(46)
E
where & def L is the condition number of the objective, we will get E [f(=*)] - f(xx)) Se. e.
Proof. From 32 and 7h = 1412
/2u(f(x*)) - f(x*)) we have
L
E EghaD [(tht))]] -(xx) S 1(zh) - -(x') 7 PD
(VS(s>))l + [(
1- B
2(1 - B)
f(²²) - f(x²) 1 3 V -
10RRN20 L
(f(x*) - -(xx))
20t 1131 (f(z*)-
f(z f(x))
- ff(x))
ro m0RR1b1
L (5(2"))((())
< 1 - (20) - 706
18/11) (bbl)) (f(=*)- - f(x)))
L
Using 0 inf (20g 70DR E (0, p3pu) and taking the full expectation from the previous inequality
k20
we get
0p
E [ - -(x=))
E [ - [(x'))
L
OpTO
k+1
(f(29) - f(x*))
Lastly, from 45 we have
(1
0p204
E [[(=)]] - f(x²)
L
01201 L
exp
- K
(5(x9) f(x"))
16

---

Published as a conference paper at ICLR 2020
Assumption D.2. We assume that for all ~ D we have ||
1.
Theorem D.2 (Solution-free stepsizes). Let Assumptions
A.7
A.2
D.1 and D.2 be satisfied. If
additionally compute f(* + ), set Th (1-8)1f(=* -ss"
for t > O and assume that 'D
such that p& S t.. then for the iterates of SMTP the following inequality holds:
11-244) )
L24²
E [[(( -(x²)
(((2))1(63)) + 8p331
(47)
Moreover, for any E if we set such that
4spba
0<15 V
(48)
1,2
and run SMTP for K iterations where
2(f(x=)
K
K
In
(49)
2
P
where K def La is the condition number of f. we will have E [f(**)] - f(x*) Sa.
Proof. Recall that from
31p we have
f( s(=t) - (VI(=)), L(7
7
2(1 - 3)2
If minimize the right hand side of the previous inequality function of a we will get that the optimal choice in this sense is Yopt derivative-free optimization, since requires to know Vf(=*). The natural way to handle this is to
& [V ((a" However, this stepsize is impractical for
approximate directional derivative (V]((*), s*) by finite difference [(* - and that is what
do. We choose 7ht +2.") f(="") (V (1 (1-B) 4ts*) f((")) (1-9)[V/LL ((2 ) def n Topi + Sth From this we get
Lt
[(aht)) S [(=*) (Vf(2*),
2(1 3)2 (8h)2
L
2T. +
Next we estimate 18/1:
= (1- B)
|6+1
|15(** + - f(=*)| (V )
L1
(1 (3
|5(8* + + ( -
Lt
(1 - B)
L
(1 8)t
|ts 1 =
Lt
2
2
It implies that
(VS(2 )
T
(1
2)
f(shtl) 1 5(zb)
2L
2(1
B)² 4
f(²²) [V 11
Lt²
2L
8
and after taking full expectation from the both sides of the obtained inequality we get
1 - [((Ts((*))
Lt
E [f( - f(x')] s (f(sh)
* | [r
2L
g
Note that from the tower property of mathematical expectation and Jensen's inequality we have
E [=V
E ES [I(V)(=*), y² |*1
E (EAro [[] +1| )}]
E [ ( MB 2433 [S(=t) ((()))((x']]
17

---

Published as a conference paper at ICLR 2020
Putting all together we get
E [ - [xx)]] - $11- w
E (((()) =(1-(h")
Lt2
L
+
Due to p/ - #
L we have
Lt
k-1 1
E -
1
1
+
Σ
L
8
L
1=0
1
(S(69) - -s(x') + L1
20
11
1
L
8
L
1=0
L2
(J(x")- - -)xx)) +
I,
81351
Lastly, from 47 we have
1zW K
L2212
E [[( - 1(x*)
+ 8/13/1
48
k 16111
L S (1(29) - -s(x)) + +2 2
exp
8
+ E.
2
2
18

---

Published as a conference paper at ICLR 2020
E SMTP_IS STOCHASTIC MOMENTUM THREE POINTS WITH IMPORTANCE SAMPLING
Again by definition of **+1 we get that the sequence {f(2*)) }x20 is monotone:
1( S f(=h)
4k: 0.
(50)
Lemma E.I. Assume that f satisfies Assumption 4.1 inequalities hold:
Then for the iterates of SMTP the following
7
V.. f(2h)) + Ls. (1/)2
f(zh+1) S f(z²)
(51)
1
3
2(1 - B)
and
EgtN [f(xkt]]] S f((tt)
1
E
V
x*
+
E Lig (744)
|2 (52)
2(1 B)²
Proof. In the similar way as in Lemma A.
one can show that
kk B
(53)
and
x
cip.
1 -
B
k+1
?
Cia.
1 B
implics that
k f(x²)
+ Lig (2
5(#4t1)
vif(E
1 B
2(1 B3)
and
((= < s(**) + 1 x
+ Lix
v.((=*)
2(1 18)2
Unifying these two inequalities we get
V.f(=>>) Ti, (2 1 3
1( < (in(f((+t)),(e+t)))
f(())
2(1 3)2
which proves 51) Finally, taking the expectation E|- ] conditioned on = from the both sides of the previous inequality obtain
E [[( < $(
1
E
2 +
1 E [L (T/)) |
1-
2(1 3)2
E. NON-CONVEX CASE
Theorem E.1. Assume that f satisfies Assumption 4.1
Let SMTP IS with 7: y 0 produce points {20, 21 ...,,.,,--1, and 2k is chosen uniformly random among them. Then
م for some
why
E [[]][(>*)I]] < (1 (1- (-B)(((x)) f(x)))
Lip:
(54)
Ky min
2(1
3) min
w
1=..... Wy
1=
1=1
19

---

Published as a conference paper at ICLR 2020
Moreover, if we choose
then
vk
(1 - ()((() - {(x)))
LiDi w
E ( [b1]
(55)
VK
min
Pt
70
2(1 3)
i'm p..dd
i=1
201 (12-))(f1=9)--1) -[(=)) in order to minimize right-hand side of
Note that if we choose "No
55 we
4.
will get
d 2 21((x9) - f(x((())) )) Σ
Lops mf
E [IVf((*))l 111]
(56)
VR
min
PL
Note that for Pt 1u/21 L, with wi Li have that the rates improves
/2(((09) - -((")) La
(57)
VK
Proof. Recall that from 52 have
[f(2 | S f(=²) I-
E
(( [
1
[Lix (75) 1 12 (58)
2(1 3)2
Using our choice 7M-
2 derive wiz
E V 21 =
Pt Wi
[.f((=)) \V
min Ps
I......d wi
and
d
L.ps wf
E [Li [1i,
1
Σ
Putting
58 and taking full expectation from the both sides of obtained inequality we get
min
Pe
L;P:
E [f(ttt1]] < E
[f(*)]]
I1
2(1
3)2
i=1
whence
[V (1- 3) (E [f(xt)] - E [f(*+t])]
7
Lip:
min
P
2(1 - 3) min
Pi
w?
d
Summing up previous inequality for h: = 0,1,..., K 1 and dividing both sides of the result by K, we get
[IV < (1- (=)) f(x)))
LiP: w²
E
Ky min Ps.
2(1 (9) min
Ps
i=1....dd
K
remains to notice that * straightforward.
[||] = E [IV]]<"" [11]. The last part where 7
20
VK
20

---

Published as a conference paper at ICLR 2020
E.2 CONVEX CASE
As for SMTP to tackle convex problems by SMTP IS we use Assumption 3.2 with || 11D = Il1. Note that in this case Rg max {|| x=" loc f(x) S f(
Theorem E.2 (Constant stepsize). Let Assumptions 3.2 and 4.1 be satisfied. If set y ب such
Wi
that 0 < y <
R1-9)Ro.
then for the iterates of SMTP IS method the following inequality holds:
min
min
P1
E -ff(=))f(x*))
1
i= il.....
wi
+
RRo
Lip:
(1
B) Ro
2(1 - 3)
min
im
(59)
6(1-8) min i-
Rg Σ
Moreover, we choose 7
for some 0 <eS
1=1 and run SMTP IS for
min
x
k = K iterations where
RD
Σ
Laps
2(f(x²)) - -1(x"))
K
In
(60)
8
min
P
will get E [][=*]] f(x*) Moreover, for p: L./Et with w; Lis the rate improves
to
2(f(x0)) - -f(x²))
K
Ryd
Lg In
(61)
8
Proof. Recall that from
52 we have
E [f(2 M S f(²²)
E
V
1
+
Lix (7+))2 1 2 (62)
2(1 8)2
Using our choice
7t 2 derive wiy
E
V f(*)) 1
12
Pi V.f(z*) 2 +11l=>/
min Pr
Wi
i=I....
W
pi - f(x'))
R i= i=l....
min
Wl
-
and
L.ps w
E Li, (Tt))
|
Putting it in 62 and taking full expectation from the both sides of obtained inequality get
min i=l....d
Pi
72 d
Lips
E [f(2**1) fxx²)] 5
E e[f(=h)-((<>>) - f(xx)] +
(63)
(1
Ro
2(1 - 33
w
21

---

Published as a conference paper at ICLR 2020
(1- (1-1-77)7
Due to our choice of y S negative and, therefore,
min or we have that the factor 1- I...... "/
Rg
(1-3)To
min Ri
is non-
i=l....d
E [f(=*) [(x))] 5
min
Pi
((=))-((²²))
(1
Ro
il.... Wi
72
d
LiPi
k-1
7
min Pi
+
2(1 - -332 1=1
w
(1 Ro i=..... We
1=0
s
(1 Ro i= wi)
7
min
Pi
(f(z")-f(()) -f(x"))
+
72
Σ
d
L,Pi
Σ 1=0
1
7 min
Pi
2(1 - 3)3 i=l
wi
(1 (1- Ro i= i= d W2
7 min
im I.....d
Wt
Pi
k
(f(2)-
-
+
Roo
d
L,ps
(1 - Ro
2(1 - 3) min
Pr
w
=(1-8) min
P1 and
Then, putting 7
1=
K from 60 in 59 we have
Luns
K
min I.....d
E[f(2*)] (f(1-(((-))
+
Lipe
min
exp
K
L....,d
(f(=")-((z*)
d
R2
Lipe
2
2
Theorem E.3 (Decreasing stepsizes). Let Assumptions 3.2 and 4.1 be satisfied. we set v
2i
and nh "k-4g. where a following inequality holds:
and 0 3, then for the iterates of SMTP_I IS method the [I B)
d
E [ - s nnk +1 max ((09)- - ((x)) a0(1 - 3)
2
pp
(64)
2
Ps.
where 17 def g. Moreover, if we choose 7t ath+2 K iterations where
where a
mi
and run SMTP SMTP_IS for
(1- 3ynl
K
2R3
2 max (1 (1- f(x))),
Σ
Lip: w
2(1 - 3)
2
E> 0,
8 min
min
im I....dd
I....d
(65)
we will get E [[[=>]] SE.
Proof. In (63 we proved that
7 min
Pi
E [[ - f(x*)] S
1-
:=......
E -
+
722
L,P:
(1 - B)
2(1
B)
w
1=1
22

---

Published as a conference paper at ICLR 2020
Having that, we apply Lemma C.1 to the sequence E [f(
f(xx)]
The con-
stants for the lemma are:
N
L.p. a
min
Rr
"
and C
2(1-A) B)a
(1 Ro
max (5(00) f(x"), a0l1 8)
Lips w
Lastly, note that choosing 7t
2a
is equivalent
a²k+2
to choice 2. In this case we have al and C max {
- {(a0)) I(x"), 3y
La
and 7)
2 Putting these parameters and K from 65 in the (64 get the
result.
E.3 STRONGLY CONVEX CASE
Theorem E.4 (Solution-dependent stepsizes). Let Assumptions 3.3 (with ||
1-1lp || || and 4.1
(1-9)0s min
2i
be satisfied. we set
y
/2p(f(za) ff(x)) for some O% (0, 2) such that
miik
0= in in0e k20
02)
0,
then for the iterates of SMTP_IS method the following
min
inequality holds:
Oμ min 1......d af
E [f(x))] - f(x))
(f(x9)
(66)
Lips
If we run SMTP IS for K iterations where
L.P.
W
[(x0) - f(x*)
K
8> 0,
(67)
8jl min
p
E
i=
will get E [f[=*]]
f(x")
Proof. Recall that from
52 we have
[]( # < f(=
{(=)) |
[Lig (Tt)) 1 (68)
2(1 B)2
(1-8)0& min
Using our choice 7
2p(f(2²)) - ff(=)) we derive
Lite m
(1 - 3)02
min
P
d Σ
E 7 fi
|
i=l.....d
-
Pi
V (=*)
Laps m
wi
(1 - 3)0x
min
2 -(x)))
Σ
Lyps w
2(1
8)0,
min
P
w(f(=t) f(x²))
Σ
Lips
w
i=
23

---

Published as a conference paper at ICLR 2020
and
2(1 - 3)
min
z u(f(zt) - f(x)))
d
E Lip (7/)2 1
Σ
Lipi w
Σ Li
1=1
2(1 8) min
-
Lip
Putting it in 68 and taking full expectation from the both sides of obtained inequality we get
11
min
E [[( [(xx)]] s
1 - 12 - 02)
E [ - {(x*))
Lips
Laps of
Using = inf (20k - 0% E
0,
we obtain
k20
ii......d
0p min
E [f(: - f(x1)]
1
E -((t))f((''))
>
wf
1=1
h-1
0p min
1= i=1.....d
(1(99-((="))
Σ
L,p: W
Lasrtly, from (66) we have
Uμ min
E [](=*)] - -((x))
5
((xx))((x)))
Lips wi
Op
min
i= i=!....d
cxp
Lips
w
67
E.
The previous result based the choice of x which depends the f(=*) f(x") which is often unknown in practice. The next theorem does not have this drawback and makes it possible to obtain the same rate of convergence as in the previous theorem using one extra function evaluation.
Theorem E,5 (Solution-free stepsizes). Let Assumptions 3.3 with || II = || (12) and 4. be satisfied.
If additionally we compute f(z + te set 7/ (1 1--)) (3e..) f(2")
for > 0, then for the
iterates of SMTP_IS IS method the following inequality holds:
[[(=*)] }] [(x") S (1
(1 (1- = )
) (S(x9) [(x")) + 81l min
12
d Σ
min
Prls- (69)
(=l..dd
t=1
24

---

Published as a conference paper at ICLR 2020
Moreover. for any 0 if we set t such that
4ep min P I=I....d
Octs
(70)
d
Σ Prl.
and run SMTP_TS for k = K iterations where
2(f(x f((x'))
K
(71)
H min i=..... L
Pi
will get E [f(=*)] f(x²) Moreover, note that for pt Tn/E! b, with wy I,, the rate improves to
Ei -= Ls In
(2([(x9) -
K
(72)
1
Proof. Recall that from 51 we have
Li, (7,))
f(a s f(**)
I-3 [z+(())))
2(1 - -)2
If minimize the right hand side of the previous inequality function of 7 will get that the optimal choice in this sense is d (I, s(=") However, this stepsize is impractical for derivative-free optimization, since requires to know (=*)(= The natural way to handle this is to
Iig
approximate directional derivative f=* by finite difference + and that is what we do. We choose
7/ (1-0)15(s" (te0)))(++++_))[(( +terg)-((=")) (L- + (1-9)1 ) --((=") Lige
Lige
Lit
(1-9)IV., f(s/)l Lis
def Topt + 5th From this get
Li,
1(x s S(=
2(1 3)2 (0t)2
2
Next estimate 18%1:
= (1- 3)
18,1
|1f(2 + +tesz) - f((x-)) (e
Ligt t
(1 3)
|1(2 k + +tei)) - -((x)) {z.f(==)
Ligt 1
26
(1 3)
Lint? 1 (1-B)t
L t
2
It implies that
f(chtl) s f(z²) [1,
Li
(1 33
+
2Li
2(1
2)1-83)²
4
L
= f(zh)
2Lix
8
and after taking expectation E [- **]
conditioned on * from the both sides of the obtained inequality
we get
Vi, (2
E
[[(
| < [(**)
E
E
[Ti,
Iri
Note that
V i ((
E
1
Σ
Pi (e
Lip
L
[2 ||3
min
:=,,... Li
2μ (f(et) {(x)))
min
: Lg"
25

---

Published as a conference paper at ICLR 2020
since || I|D = || ll2, and
E
[Ti 2x
Σ D.T4-
Putting all together we get
Pi (f(=))(((=)) + t² Σ
E [f(2 |>0]
S f(²")
1
min pro
f(x))(
PiL.
Li
i=1
Taking full expectation from the previous inequality we get
12 d
E [[ - f(x*)] - 1 (1-
Pi i= i...... Li
min
E
+ Σ
P.Li
1=1
Since S L; for all i i= I,...,d we have
E [(<=)))((x")) s
11
Pi i=.....
min
Li
12
k-1
Pi i=....,d Lip
+
Pilu
1 1- 1 min
8
1=1
1=0
k
s
min
Pi
(f(x*) - -(xx))
i=l,... d Li)
2
+
Σ
PiL:
- min
Pi
8 iml
i=
id.... Ls
1=0
(1
t²
min
(f(29) -f(x"))
+
prbi.
I......
Li
8p min
i=1
Lastly, from 69
we have
E [[(=*)]
-(x")
<
11-M min 2.) (S(x9)-((x))
- -1(x)) +
Σ
peLs
8y1 min
i=...... i=1
Pi 1 i Li (f(x9) - f(xx)) + 2
exp - KK
min
8 E
+ = E.
2 2
E.4 COMPARISON OF SMTP AND SMTP_IS
Here we compare SMTP when D is normal distribution with zero mean and / with SMTP IS with probabilities shows the best dimension dependence among other distributions considered Lemma F. Note that if ʃ satisfies Assumption 4. it is L-smooth with I. = max Lt. So, we always have that :=1....dd
d covariance matrix 1n/Ei 4, We choose such a distribution for SMTP since
EL, L, S dL. Table summarizes complexities in this case.
We notice that for SMTP we have ||- ||D = || 122. That is why one needs to compare SMTP with SMTP_ IS accurately. At the first glance, Table says that for non-convex and convex cases we get an extra d factor in the complexity of SMTP IS when L1 natural since we use different norms for SMTP and SMIP IS.
La L. However, it is SWTP_IS. In the non-convex case for SMTP we give number of iterations in order to guarantee E [[V [2] < while for SMTP_ we
provide number of iterations in order to guarantee E V [h] I From Holder's inequality
26

---

Published as a conference paper at ICLR 2020
SMTP Compleixty
Importance Sampling
SMIP _ Complexity
Assumptions on f
Theorem
Theorem
None
srndl
3.1
Pt
Tig
2ng 3
E.
Convex, Ro
R
In 2n1
3.2
L Px
Ro E le
In 2na
E.2
Lis
j-strongly convex
adl 2nu
2p
3.5
Pi
Lizt
D In
2no
E.5
Table 3: Comparison SMTP with D - N (0, 2) and SMTP_IC with pi I./EI=1 L.
Here
To = f(x") - f(="). Ro.e, corresponds to the Rg from Assumption C.1 with ||D
-|- and
& corresponds to the Rg from Assumption C.1 with || 1111
||
Il S Vdll 12 and, therefore, in order to have E
[| f [1]
S for SMTP we need to ensure
that E ||V S va That is, guarantee E | f S SMTP for aforementioned
distribution needs to perform #rad iterations.
Analogously, in the convex case using Sauchy-Schwarte inequality || lla S vdl 1loo we have that
Ra S Vd Typically this inequality tight and we assume that Ro 2 C R2, we will Re. Di
vi
get that SMTP_ TS complexity is
L:
In
220
up to constant factor.
That is, in all cases SMTP_IP IS shows better complexity than SMTP up some constant factor.
F AUXILIARY RESULTS
Lemma F.1 (Lemma 3.4 from Bergou et al. (2019). Let E TRd
1. If is the uniform distribution the unit sphere in Idd, then
YD =1 and EgED (gg 8) ~ 22rd |1l1|2
(73)
Hence, D satisfies Assumption 3.1 with TD = 1, || Ill = ||
ll2 and μD
V2nd'
2. If DD is the normal distribution with zero mean and identity over as covariance matrix (i.e. (0, 2)) then
v2
YD = and Ea-D () vdn
||glla.
(74)
Hence, 'D satisfies Assumption 3.1 with TD = 1, 1| = || 1.112 and μr
/22
<da
3. DfD is the uniform distribution on (ei,.... eaj. then
TDD and EgwD (g, 8) |1g|l
(75)
Hence, 'D satisfies Assumption 3.1 with TD = 1, || = ||. and μtD d'
4. Df is an arbitrary distribution on {ei...., ed) given by P {s ei} = > 0, then
DD = and EA-D (g. 8) = ||g|| def pilail
(76)
Hence, D satisfies Assumption 3.1 with 7D = 1 and = 1.
5. D is a distribution on D = {uI..... un} where ui...., form an orthonormal basis of IRd and {s d Ps, then
def d
YD = and ENE (g. s) |l
p-lg-l
p
(77)
27

---

Published as a conference paper at ICLR 2020
Hence, D satisfies Assumption 3.7 with "/D = 1 and pp 1.
28


Reviews:
[{"review_id": "rJxwjjnhYr", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The paper proposes a stochastic derivative free optimization algorithm. The contribution is two-fold: first, the paper introduces the heavy ball momentum into the STP framework; second, the paper fulfills both the importance sampling and heavy ball momentum in the STP framework. For both methods, the paper provides the convergence guarantees and rates. The experiments on reinforcement learning data-sets, as compared with the original STP, shows improvement. \n\nThe idea seems straightforward --- just combining a classical momentum strategy with the an existing derivative free optimization framework. But the author claim that they are the first to exploit this strategy. The analysis part, for strongly convex, convex and nonconvex problems, however, is solid to me. I am not the expert in this direction. Here are a few questions, from the answers of which I want to learn more about the meaning of this work. \n\n(1) As compared with other derivative free optimization algorithm, such as Bayesian optimization/genetic algorithms/simulated annealing, what is the advantage of the proposed method and also the STP framework? \n(2) The experiments seem weak to me. Why does the paper only compare with STP? Are there any other baselines, such as stochastic two points, BO and GA? Is it possible to conduct evaluation on other applications? For example, some general optimization tasks but not allowing gradient calculation?", "extra_scores": {"experience_assessment": "I do not know much about this area.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I did not assess the derivations or theory."}, "extra_text": {}}, {"review_id": "Hye_vaCb5B", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The authors extend recent the recent stochastic three-point (STP) method to allow for Polyak-style momentum, as well as momentum with importance sampling. They provide a range of analysis that mostly extends existing STP results to the STP+momentum case. Most of these results are similar in spirit to stochastic gradient or subgradient results, as in the methods converge up to a ball around the solution, with radius depending on step-size, so you can get an epsilon solution by choosing a suitably small stepsize. The analysis covers non-convex cases (bounds are on the norm of the gradient) and the importance sampling case as well.\n\nOverall, I think this is a strong paper, and a very interesting topic, and hence I support a \"Weak accept\". The numerical results look good, as the new method outperforms most of the compared methods, at least for the easier problems (SMTP beats competitor ARS in 3/5 trials; both methods are generally very similar, though SMTP does better on the easy Swimmer problem; the SMTP_IS results are more complicated).  The analysis is mostly good (non-trivial), and shows a broad understanding.\n\nThat said, I have some concerns. \n\n(1) The analysis is nice in that it shows the methods work, but doesn't demonstrate benefit of their method over other methods\n\n(2) Given that there are no results showing this method has better worst-case rates than other methods, we rely on experiments to see the actual benefit. In this case, more experiments is always better.\n\n(3) I am quite skeptical of the importance sampling scheme. It's nice to include it, but I don't think it strengthens the paper too much. Empirically, the performance seems to help sometimes but not other times. Finding the individual Lipschitz constants seems tricky; this paper re-uses a scheme that iterates for a while, fits a function, and uses that to estimate the constants (it wasn't clear if this pre-processing was counted in the iteration count for experimental results). It's not clear how well that works to get an accurate estimate. Furthermore, to exploit the importance sampling, the directions must be sampled from a pre-determined basis, which seems restrictive.  This criticism is not just of the current paper but of other papers that use this approach.\n\n\n-- The manuscript needs more proof reading, as there are mistakes in most paragraphs. There are a lot of problems with missing articles.  Phrases like \"results for STP are shorts and clear\" (\"shorts\" --> \"short\"), \"which updates rule\" [?? which-->with?? ], \"hints [at] the update rule\", \"is far more superior\" [-->\"is far superior\", since you can't be more superior], etc.\n\n-- There is a confusion over how to use \\cite, \\citet and \\citep in latex. Given the bibtex citation style, this makes it very hard to read in places\n\n-- Literature review seems good and pretty thorough (mentions most key references through 2015, and a good selection of references since then).\n\n-- Assumption 3.1 part 2 is stated in a funny way (it says, \"there is a constant mu_D and a norm || ||_D such that ...\").  You are free to choose the norm, and then find the constant (since all norms in finite dimensions are equivalent). That way, you can choose the norm that gives the tightest inequality.  I think you are aware of this, and it's just a wording issue.\n\n-- Theorem 3.5 (Thm D.2) requires the mu_D^2 to be less than the condition number, which is weird. The easier the problem is, the tighter your assumptions are.  I suspect that this is because you use an inequality somewhere that simplifies things by bounding a term by the condition number. But as stated, this is a weak theorem.  It is also confusing because you have a mu_D which is not the strong convexity constant, but the actual strong convexity constant (mu) *does* depend on the norm D (cf eq 19; and this must be so, otherwise you can cheat and then the value of mu_D is meaningless). So both mu's are functions of the norm D. However, the Lipschitz constant L is *not* a function of D. So notation is confusing and makes interpreting the results harder.\n\n-- sentences like \"We achieve the state-of-the-art performance compared to *all* DFO based and policy gradient methods\" are in appropriate (*italics* are mine). You mean to say that on the few examples you ran, based on a few DFO and policy gradient methods you tested, that the best of your two methods was better than the competitor methods on 4/5 problems.\n\n-- I think a common-sense algorithm to compare to would be gradient descent (or heavy-ball) using finite differences to estimate the gradient.  In small dimensions this isn't such a bad idea.  I don't actually know what the dimensions of your test problems are (I looked in section 5 but didn't see it mentioned, other than reference to Ant-v1 and Humanoid-v1 being \"high dimensional\"; I think this is extremely relevant information. In small dimensions, traditional DFO and Bayesian optimization methods are competitive).\n\n-- p 26/27, \"Causchy-Schwartz\" is spelled wrong, and usually this is called \"Holder's inequality\" when it's not the Euclidean norm.\n\n-- Table 3, there is no space between the caption and the main text, so it's confusing\n\n-- Eq (76) in appendix, the sum should go to d not n.\n\n-- I think s^k may need to be independent of z^k for their tower property thing to work, otherwise it's not clear what's happening with the inequality prior to overset (30) on that last line of pg17. For example, if s^k were z^k measurable then that whole thing in the inner expectation would be a constant. This isn't a problem, it's fairly natural to assume that s^k is independent of z^k, I just didn't see the assumption anywhere.\n\n-- Overall, comparing importance sampling results is hard, due to the different norms (this is mentioned in the paper, and there are inequalities between norms, but it's still hard to get a good result that shows importance sampling has better worst-case rates).\n\n\n== AFTER READING REBUTTAL ==\nI read the authors' response, and I am still slightly positive about the paper, though my major points were not addressed, but mostly deflected, e.g., referring to other papers that claim to show benefits of importance sampling. I think all the reviewers were curious how Bayesian optimization (BO) would perform. We understand numerical experiments are time consuming, but it's disappointing that you're not curious yourself whether your method outperforms BO. Your basic deflection seems to be that BO doesn't have provable guarantees, so because you do have guarantees, you don't need to compare with it.  Having one of the fastest methods among all methods with provable guarantees, but not necessarily the fastest method in general, sounds like a consolation prize to me.\n\nThe revision did not address some of the minor issues I mentioned, such as confusing \"cite\"/\"cited\"/\"citep\" issues in latex (which makes it hard to read).  My comment about Holder's inequality (vs Cauchy-Schwarz) applies not just to the $\\|\\cdot\\|_1 \\le \\sqrt{d}\\|\\cdot\\|_2$ bound, but also to the  $\\|\\cdot\\|_2 \\le \\sqrt{d}\\|\\cdot\\|_\\infty$ bound in the next paragraph.\n\nBut despite a few items I'm being cranky about, I think it's still a solid paper, and it's still a weak accept.", "extra_scores": {"experience_assessment": "I have published one or two papers in this area.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper thoroughly.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}, {"review_id": "Hye-lZhE5B", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper studies the so called problem of derivative-free optimization, which is relevant for cases when the evaluation function is continuous but access to gradients is not possible. The paper improves on top of the stochastic three points method (STP), an existing work (published in arXiv), by proposing adding momentum (SMTP). The intuition behind both STP and SMTP is rather straighforward: you sample a random direction s, then given your current position x you check x+as and x-as. You then move to the best position from (x, x+as, x_as). In a way, this is like computing the numerical derivatives (instead of the gradient) given a random location and its mirror, and then applying gradient descent given the best numerical derivative. However, take this analogy with a large grain of salt, as there are many differences with GD. The proposed algorithm adds momentum and importance sampling. Momentum helps speed up convergence, as the paper shows for non-convex, convex and strongly convex functions. All three cases are individually examined and bounds are derived regarding the speed of convergence. For the non-convex case the speed of convergence is 1/\\sqrt{K}, K being the number of iterations. For the convex case it is 1/K. For the strongly convex case the (unrealistic) assumption of knowing the optimal value is removed while maintaining the same speed of convergence.  Importance sampling helps computing the derivatives focusing on those coordinate dimensions that are more critical to the objective function f(x), improving the speed of convergence further. The importance sampling is proportional to the coordinate-wise Lipschitz constants, assuming that the objective function is coordinate-wise Lipschitz smooth. The methods are validated on five different cases of MuJoCo. Results seem good when compared to the STP ones. Compared to policy gradient methods, the results seem much better.\n\nStrengths:\n+ The paper presents a small but interesting and well-motivated addition to the original algorithm STP. I particularly liked how straightforward the final algorithm is: applying momentum and sampling according to the Lipschitz constants.\n\n+ At least at a first glance the results look good. Compared to STP in figure 1 there is a clear improvement not only in the final optimum but also in the speed of attaining the said optimum.\n\n+ I liked a lot the presentation and clarity of writing. While quite mathematically dense, it was easy to follow the big story and understand that underlying points. \n\nWeaknesses:\n+ While interesting and useful, I am not completely convinced whether the added novelty over (Bergou et al, 2019) is significant enough. At the end of the day, the final algorithm is the conglomeration of two existing algorithms, that is STP and momentum. STP is very similar to the final algorithm, after all it is the basis for it. The authors argue that it is not trivial to select the next points under the momentum term. To this end, they propose to rely on yet another existing approach, that is the virtual iterates analysis from (Yang et al. 2016). However, it is not clear why these points are \"optimal\", what is so \"non-trivial\" about selecting them? This is basically skimmed over in two lines.\n\n+ In the strongly convex case one assumption (knowing the f(x*) ) is replaced with another assumption, that all points lie on a hypersphere (|s|_2=1). I suppose this would assume a spherical normalization of the input space. While this is not an unrealistic assumption, it does place a constraint which could be problematic in the case of high dimensions for s? In that case the high dimensionality would render distances rather unreliable and in turn could hurt convergence? This is also perhaps the reason that only the MuJoCo enviroments were tested? In general, I would say that the strongly convex case was discussed less clearly and it is not exactly clear the final result. In the end, eq (25) does contain f(x*), whereas in the convex case K does not (K \\approx 2 R_0^2 L γ_D/(εμ_D^2).\n\n+ Some statements are unclear.\n  ++ In p. 2 some symbols are not explained, e.g., ε. While it is quite clear for peopled versed in the field, in my opinion it is bad practice to leave notation not explained.\n  ++ In assumption 3.1 seems rather trivial? Wouldn't γ_D by definition be always positive, since is the expectation of a squared norm (always positive)? Does this need to be an assumption?\n  ++ Between eq. (11) and (12) there is reference to (35)? What is (35)?\n  ++ It is not clear in practice how the importance sampling is performed. In Algorithm 2 the probabilities p_i are defined as function inputs and then never updated. Is that true? If yes, how is p_i decided in the first place? What is the connection to the Lipschitz constants L_i?\n\n+ A highly relevant field appears to be Bayesian Optimization, where also one cannot compute gradients and must optimize a black-box function. Some relevant recent works are [1] and [2] for continuous and discrete inputs. It would be interesting to discuss what are the distinct differences with bayesian optimization methods in [1] and [2].\n\n+ I would say that the paper is rather on the light side regarding experiments. Only MuJoCo is used as an experimental setup. It would be nice to also report results on synthetic experiments with known functions to better understand the limitations of the algorithm. Synthetic and realistic setups can be found in [1] and [2].\n\nWhat is more, the experimental choices are not entirely clear. What is the \"predefined reward threshold\" and why was that chosen? For instance, the leaderboard for \"Swimmer\" is in: https://www.endtoend.ai/envs/gym/mujoco/swimmer/. How does the proposed algorithm fair compared to these works? Also, *maybe* it would be interesting to compare even against [1] or [2] (I guess [2] is harder as it is for discete inputs), assuming that a relatively low number of iterations is performed.\n\n[1] BOCK: Bayesian Optimization with Cylindrical Kernels, C. Oh, E. Gavves, M. Welling, ICML 2018\n[2] BOCS: Bayesian Optimization of Combinatorial Structures, R. Baptista, M. Poloczek, ICML 2018\n", "extra_scores": {"experience_assessment": "I have published one or two papers in this area.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_experiments": "I carefully checked the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}]

Author rebuttal:

Meta-review: A new method for derivative free optimization including momentum and importance sampling is proposed.

All reviewers agreed that the paper deserves acceptance.

Acceptance is recommended.
Decision: Accept (Poster)