Title: A STOCHASTIC DERIVATIVE FREE OPTIMIZATION METHOD WITH MOMENTUM

Abstract: We consider the problem of unconstrained minimization of a smooth objective function in 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.

1. INTRODUCTION:

In this paper, we consider the following minimization problem

EQUATION

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. In Stich (2014a; b) authors also consider acceleration of ZO methods and, in particular, 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 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:

x k+1 = arg min{f (x k ), f (x k + α k s k ), f (x k -α k s k )}.

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.

Momentum. Heavy ball momentum1 is a 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 L /µ log 1 /ε rate for twice continuously differentiable µ-strongly 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, L-smooth and µ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 et. 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 stochastic gradient based methods Zhao & Zhang (2015) or in coordinate based methods Richtárik & Takáč (2016) . Only very recently, Bibi et al. (2019) proposed, STP_IS, 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 to 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 Algorithm 1 SMTP: Stochastic Momentum Three Points Require: learning rates {γ k } k≥0 , starting point

x 0 ∈ R d , D -distribution on R d , 0 ≤ β < 1 - momentum parameter 1: Set v -1 = 0 and z 0 = x 0 2: for k = 0, 1, . . . do 3: Sample s k ∼ D 4: Let v k + = βv k-1 + s k and v k -= βv k-1 -s k 5: Let x k+1 + = x k -γ k v k + and x k+1 - = x k -γ k v k - 6: Let z k+1 + = x k+1 + -γ k β 1-β v k + and z k+1 - = x k+1 - -γ k β 1-β v k - 7: Set z k+1 = arg min f (z k ), f (z k+1 + ), f (z k+1 -) 8: Set x k+1 =    x k+1 + , if z k+1 = z k+1 + x k+1 -, if z k+1 = z k+1 - x k , if z k+1 = z k and v k+1 =    v k+1 + , if z k+1 = z k+1 + v k+1 -, if z k+1 = z k+1 - v k , if z k+1 = z k 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 a 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 method with heavy ball momentum, i.e. 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 to get more gain from momentum in the case when the sampling directions are coordinate directions and the objective function is coordinate-wise 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_IS) 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 E. • Practicality. We conduct extensive experiments on continuous control tasks from the MuJoCo suite Todorov et al. (2012) following recent success of DFO compared to modelfree reinforcement learning Mania et al. (2018) ; Salimans et al. (2017) . We achieve with SMTP_IS the state-of-the-art results on across all tested environments on the continuous control outperforming DFO Mania et al. (2018) and policy gradient methods Schulman et al. (2015) ; Rajeswaran et al. (2017) .

We provide more detailed comparison of SMTP and SMTP_IS in Section E.4 of the Appendix.

2. NOTATION AND DEFINITIONS:

We use x i e i . We use • * to define the conjugate norm for the norm • :

• p to define p -norm of the vector x ∈ R d : x p def = d i=1 |x i | p 1 /p for p ≥ 1 and x ∞ def = max i∈[d] |x i | where x i is the i-th component of vector x, [d] = {1,

x * def = max a, x | a ∈ R d , a ≤ 1 .

As we mention in the introduction we assume throughout the paper2 that the objective function f is L-smooth.

Assumptions on f SMTP Complexity Theorem Importance Sampling

SMTP_IS:



Complexity Theorem:

None 

2r 0 Lγ D µ 2 D ε 2 3.1 pi = L i d i=1 L i 2r 0 d d i=1 L i ε 2 E.1 Convex, R0 < ∞ 1 ε Lγ D R 2 0 µ 2 D ln 2r 0 ε 3.2 pi = L i d i=1 L i R 2 0 d d i=1 L i ε ln 2r 0 ε E.2 µ-strongly convex L µµ 2 D ln 2r 0 ε 3.5 pi = L i d i=1 L i d i=1 L i µ ln 2r 0 ε E.5

• D = • 2 in the strongly convex case. Assumption 2.1. (L-smoothness) We say that f is L-smooth if ∇f (x) -∇f (y) 2 ≤ L x -y 2 ∀x, y ∈ R d .

(2)

From this definition one can obtain

EQUATION

and if additionally f is convex, i.e. f (y) ≥ f (x) + ∇f (x), y -x , we have

EQUATION

)

3 STOCHASTIC MOMENTUM THREE POINTS (SMTP)

Our analysis of SMTP is based on the following key assumption. Assumption 3.1. The probability distribution D on R d satisfies the following properties:

1. The quantity γ D def = E s∼D s 2 2 is finite. 2. There is a constant µ D > 0 for a norm • D in R d such that for all g ∈ R d E s∼D | g, s | ≥ µ D g D .

(

EQUATION

Some examples of distributions that meet above assumption are described in Lemma 3.4 from Bergou et al. (2019) . For convenience we provide the statement of the lemma in the Appendix (see Lemma F.1).

Recall that one possible view on STP Bergou et al. ( 2019) is as following. If we substitute gradient ∇f (x k ) in the update rule for the gradient descent x k+1 = x k -γ k ∇f (x k ) by ±s k where s k is sampled from distribution D satisfied Assumption 3.1 and then select x k+1 as the best point in terms of functional value among x k , x k -γ k s k , x k + γ k s k 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 try to perform the same substitution-trick with more efficient first-order methods than gradient descent.

We put our attention on Polyak's heavy ball method where the update rule could be written in the following form:

v k = βv k-1 + ∇f (x k ), x k+1 = x k -γ k v k .

(6) As in STP, we substitute ∇f (x k ) by ±s k and consider new sequences {v k + } k≥0 and {v k -} k≥0 defined in the Algorithm 1. However, it is not straightforward how to choose next x k+1 and v k and the virtual iterates analysis Yang et al. (2016) hints the update rule. We consider new iterates z k+1

+ = x k+1 + -γ k β 1-β v k + and z k+1 - = x k+1 --γ k β 1-β v k

-and define z k+1 as arg min f (z k ), f (z k+1 + ), f (z k+1 -) . Next we update x k+1 and v k in order to have the same relationship between z k+1 , x k+1 and v k as between z k+1 + , x k+1 + and v k + and z k+1 -, x k+1 -and v k -. 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 z k+1 , we get that the sequence {f (z k )} k≥0 is monotone:

EQUATION

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:

f (z k+1 ) ≤ f (z k ) - γ k 1 -β | ∇f (z k ), s k | + L(γ k ) 2 2(1 -β) 2 s k 2 2 (8)

and

E s k ∼D f (z k+1 ) ≤ f (z k ) - γ k µ D 1 -β ∇f (z k ) D + L(γ k ) 2 γ D 2(1 -β) 2 . (9) 3.1 NON-CONVEX CASE

In this section, we show our complexity results for Algorithm 1 in the case when f is allowed to be non-convex. In particular, we show that SMTP in Algorithm 1 guarantees complexity bounds with the same order as classical bounds, i.e. 1/ √ K 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. Theorem 3.1. Let Assumptions 2.1 and 3.1 be satisfied. Let SMTP with γ k ≡ γ > 0 produce points {z 0 , z 1 , . . . , z K-1 } and z K is chosen uniformly at random among them. Then

EQUATION

Moreover, if we choose γ = γ0 √ K the complexity (10) reduces to

EQUATION

)

Then γ 0 = 2(1-β) 2 (f (x 0 )-f (x * ))

Lγ D minimizes the right-hand side of (11) and for this choice we have

EQUATION

)

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 we also show that theoretical convergence guarantees for SMTP are not worse than for STP for convex and strongly convex problems. However, in 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, we present our complexity results for Algorithm 1 when f is convex. In particular, we show that this method guarantees complexity bounds with the same order as classical bounds, i.e. 1/K, in the literature. We will need the following additional assumption in the sequel.

Assumption 3.2. We assume that f is convex, has a minimizer x * and has bounded level set at x 0 :

EQUATION

where

ξ * D def = max { ξ, x | x D ≤ 1} defines the dual norm to • D .

From the above assumption and Cauchy-Schwartz inequality we get the following implication:

EQUATION

)

Theorem 3.2 (Constant stepsize). Let Assumptions 2.1, 3.1 and 3.2 be satisfied. If we set

γ k ≡ γ < (1-β)R0 µ D

, then for the iterates of SMTP method the following inequality holds:

EQUATION

)

If we choose γ = ε(1-β)µ D Lγ D R0 for some 0 < ε ≤ Lγ D R 2 0 µ 2 D

and run SMTP for k = K iterations where

EQUATION

then we will get E f (z K ) -f (x * ) ≤ ε.

In order to get rid of factor ln 2(f (x 0 )-f (x * ))

ε in the complexity we consider decreasing stepsizes.

Theorem 3.3 (Decreasing stepsizes). Let Assumptions 2.1, 3.1 and 3.2 be satisfied. If we set γ k = 2 αk+θ , where α = µ D (1-β)R0 and θ ≥ 2 α , then for the iterates of SMTP method the following inequality holds:

EQUATION

)

where

η def = α θ . Then, if we choose γ k = 2α α 2 k+2 where α = µ D

(1-β)R0 and run SMTP for k = K iterations where

EQUATION

we get

E f (z K ) -f (x * ) ≤ ε.

We notice that if we choose β sufficiently close to 1, we will obtain from the formula (18

) that K ≈ 2R 2 0 Lγ D εµ 2 D .

3.3. STRONGLY CONVEX CASE:

In this section we present our complexity results for Algorithm 1 when f is µ-strongly convex.

Assumption 3.3. We assume that f is µ-strongly convex with respect to the norm • * D :

EQUATION

)

It is well known that strong convexity implies

EQUATION

)

Theorem 3.4 (Solution-dependent stepsizes). Let Assumptions 2.1, 3.1 and 3.3 be satisfied. If we set

γ k = (1-β)θ k µ D L 2µ(f (z k ) -f (x * )) for some θ k ∈ (0, 2) such that θ = inf k≥0 {2θ k -γ D θ 2 k } ∈ (0, L /(µ 2 D µ))

, then for the iterates of SMTP, the following inequality holds:

EQUATION

Then, If we run SMTP for k = K iterations where

EQUATION

)

where κ def = L µ is the condition number of the objective, we will get

E f (z K ) -f (x * ) ≤ ε.

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 s ∼ D we have s 2 = 1.

Theorem 3.5 (Solution-free stepsizes). Let Assumptions 2.1, 3.1, 3.3 and 3.4 be satisfied. If additionally we compute

f (z k + ts k ), set γ k = (1-β)|f (z k +ts k )-f (z k )| /(Lt)

for t > 0 and assume that D is such that µ 2 D ≤ L /µ, then for the iterates of SMTP the following inequality holds:

EQUATION

Moreover, for any ε > 0 if we set t such that

EQUATION

)

and run SMTP for k = K iterations where

EQUATION

where

κ def = L µ is the condition number of f , we will have E f (z K ) -f (x * ) ≤ ε.

4. STOCHASTIC MOMENTUM THREE POINTS WITH IMPORTANCE SAMPLING (SMTP_IS):

In this section we consider another assumption, in a similar spirit to Bibi et al. (2019) , on the objective. Assumption 4.1 (Coordinate-wise L-smoothness). We assume that the objective f has coordinatewise Lipschitz gradient, with Lipschitz constants L 1 , . . . , L d > 0, i.e.

EQUATION

where

∇ i f (x) is i-th partial derivative of f at the point x.

For this kind of problems we modify SMTP and present STMP_IS method in Algorithm 2. In general, the idea behind methods with importance sampling and, in particular, behind SMTP_IS is to adjust probabilities of sampling in such a way that gives better convergence guarantees. In the case when f satisfies coordinate-wise L-smoothness and Lipschitz constants L i are known it is natural to sample direction s k = e i with probability depending on L i (e.g. proportional to L i ). One can find more detailed discussion of the importance sampling in Zhao & Zhang (2015) and Richtárik & Takáč (2016) . Now, we establish the key result which will be used to prove the main complexity results of STMP_IS.

Algorithm 2 SMTP_IS: Stochastic Momentum Three Points with Importance Sampling Require: stepsize parameters w 1 , . . . , w n > 0, probabilities p 1 , . . . , p n > 0 summing to 1, starting point

x 0 ∈ R d , 0 ≤ β < 1 -momentum parameter 1: Set v -1 = 0 and z 0 = x 0 2: for k = 0, 1, . . . do 3: Select i k = i with probability p i > 0 4: Choose stepsize γ k i proportional to 1 wi k 5: Let v k + = βv k-1 + e i k and v k -= βv k-1 -e i k 6: Let x k+1 + = x k -γ k i v k + and x k+1 - = x k -γ k i v k - 7: Let z k+1 + = x k+1 + - γ k i β 1-β v k + and z k+1 - = x k+1 - - γ k i β 1-β v k - 8: Set z k+1 = arg min f (z k ), f (z k+1 + ), f (z k+1 -) 9: Set x k+1 =    x k+1 + , if z k+1 = z k+1 + x k+1 -, if z k+1 = z k+1 - x k , if z k+1 = z k and v k+1 =    v k+1 + , if z k+1 = z k+1 + v k+1 -, if z k+1 = z k+1 - v k , if z k+1 = z k 10: end for Lemma 4.1.

Assume that f satisfies Assumption 4.1. Then for the iterates of SMTP_IS the following inequalities hold:

f (z k+1 ) ≤ f (z k ) - γ k i 1 -β |∇ i k f (z k )| + L i k (γ k i ) 2 2(1 -β) 2 (27)

and

E s k ∼D f (z k+1 ) ≤ f (z k ) - 1 1 -β E γ k i |∇ i k f (z k )| | z k + 1 2(1 -β) 2 E L i k (γ k i ) 2 | z k . (28)

Due to the page limitation, we provide the complexity results of SMTP_IS in the Appendix.

5. EXPERIMENTS:

Experimental Setup. We conduct extensive experiments3 on challenging non-convex problems on the continuous control task from the MuJoCO 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 to learn how to control a 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 on several environments with varying difficulty Swimmer-v1, Hopper-v1, HalfCheetah-v1, Ant-v1, and Humanoid-v1.

Note that due to the stochastic nature of problem where f is stochastic, we use the mean of the function values of f (x k ), f (x k + ) and f (x k -), see Algorithm 1, over K observations. Similar to the work in Bibi et al. (2019) , we use K = 2 for Swimmer-v1, K = 4 for both Hopper-v1 and HalfCheetah-v1, K = 40 for Ant-v1 and Humanoid-v1. Similar to Bibi et al. (2019) , these values were chosen based on the validation performance over the grid that is K ∈ {1, 2, 4, 8, 16} for the smaller dimensional problems Swimmer-v1, Hopper-v1, HalfCheetah-v1 and K ∈ {20, 40, 80, 120} for larger dimensional problems Ant-v1, and Humanoid-v1. As for the momentum term, for SMTP we set β = 0.5. For SMTP_IS, as the smoothness constants are not available for continuous control, we use the coordinate smoothness constants of a θ parameterized smooth function fθ (multi-layer perceptron) that estimates f . In particular, consider running any DFO for n steps; with the queried sampled {x i , f (x i )} n i=1 , we estimate f by solving Bibi et al. (2019) for further implementation details 2 to demonstrate complexity of each method. as we follow the same experimental procedure. In contrast to STP_IS, 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_IS, we follow a similar procedure as Bibi et al. (2019) and sample from columns of a random matrix B.

θ n+1 = argmin θ i (f (x i ) -f (x i ; θ)) 2 . See

Similar to the standard practice, we perform all experiments with 5 different initialization and measure the average reward, in continuous control we are maximizing the reward function f , and best and worst run per iteration. We compare algorithms in terms of reward vs. sample complexity.

Comparison Against STP. Our method improves sample complexity of STP and STP_IS significantly. Especially for high dimensional problems like Ant-v1 and Humanoid-v1, sample efficiency of SMTP is at least as twice as 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.

Comparison Against State-of-The-Art.

We compare our method with state-of-the-art DFO and policy gradient algorithms. For the environments, Swimmer-v1, Hopper-v1, HalfCheetah-v1 and Ant-v1, our method outperforms the state-of-the-art results. Whereas for Humanoid-v1, our methods results in a comparable sample complexity.

6. CONCLUSION:

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.

A Stochastic Derivative Free Optimization Method with Momentum (Supplementary Material):

A PRELIMINARIES

We first list the main assumptions.

EQUATION

)

Assumption A.2. The probability distribution D on R d satisfies the following properties:

1. The quantity γ D def = E s∼D s 2 2 is positive and finite.

2. There is a constant µ D > 0 and norm

EQUATION

)

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:

f (z k+1 ) ≤ f (z k ) - γ k 1 -β | ∇f (z k ), s k | + L(γ k ) 2 2(1 -β) 2 s k 2 2 (31)

and

EQUATION

)

Proof. By induction one can show that

EQUATION

)

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

z k+1 + = x k+1 + - γ k β 1 -β v k + = x k -γ k v k + - γ k β 1 -β v k + = x k - γ k 1 -β v k + = x k - γ k β 1 -β v k-1 - γ k 1 -β s k (33) = z k - γ k 1 -β s k .

Similarly,

z k+1 - = x k+1 - - γ k β 1 -β v k -= x k -γ k v k -- γ k β 1 -β v k - = x k - γ k 1 -β v k -= x k - γ k β 1 -β v k-1 + γ k 1 -β s k (33) = z k + γ k 1 -β s k . It implies that f (z k+1 + ) (3) ≤ f (z k ) + ∇f (z k ), z k+1 + -z k + L 2 z k+1 + -z k 2 2 = f (z k ) - γ k 1 -β ∇f (z k ), s k + L(γ k ) 2 2(1 -β) 2 s k 2 2 and f (z k+1 -) ≤ f (z k ) + γ k 1 -β ∇f (z k ), s k + L(γ k ) 2 2(1 -β) 2 s k 2 2 .

Unifying these two inequalities we get

f (z k+1 ) ≤ min{f (z k+1 + ), f (z k+1 -)} = f (z k ) - γ k 1 -β | ∇f (z k ), s k | + L(γ k ) 2 2(1 -β) 2 s k 2 2 ,

which proves (31). Finally, taking the expectation E s k ∼D of both sides of the previous inequality and invoking Assumption A.2, we obtain

E s k ∼D f (z k+1 ) ≤ f (z k ) - γ k µ D 1 -β ∇f (z k ) D + L(γ k ) 2 γ D 2(1 -β) 2 .

B NON-CONVEX CASE:

Theorem B.1. Let Assumptions A.1 and A.2 be satisfied. Let SMTP with γ k ≡ γ > 0 produce points {z 0 , z 1 , . . . , z K-1 } and z K is chosen uniformly at random among them. Then

EQUATION

)

Moreover, if we choose γ = γ0 √ K the complexity (34) reduces to

EQUATION

)

Then γ 0 = 2(1-β) 2 (f (x 0 )-f (x * ))

Lγ D minimizes the right-hand side of (35) and for this choice we have

EQUATION

)

Proof. Taking full expectation from both sides of inequality (32) we get

E ∇f (z k ) D ≤ (1 -β)E f (z k ) -f (z k+1 ) γµ D + Lγγ D 2µ D (1 -β) .

Further, summing up the results for k = 0, 1, . . . , K -1, dividing both sides of the obtained inequality by K and using tower property of the mathematical expectation we get

E ∇f (z K ) D = 1 K K-1 k=0 E ∇f (z k ) D ≤ (1 -β)(f (z 0 ) -f (x * )) Kγµ D + Lγγ D 2µ D (1 -β) .

The last part where γ = γ0 √ K is straightforward.

Published as a conference paper at ICLR 2020

C CONVEX CASE:

Assumption C.1. We assume that f is convex, has a minimizer x * and has bounded level set at x 0 : , then for the iterates of SMTP method the following inequality holds:

EQUATION

EQUATION

)

If we choose γ = ε(1-β)µ D Lγ D R0 for some 0 < ε ≤ Lγ D R 2 0 µ 2 D

and run SMTP for k = K iterations where

EQUATION

)

then we will get E f (z K ) -f (x * ) ≤ ε.

Proof. From the (32) and monotonicity of {f (z k )} k≥0 we have

E s ∼ D f (z k+1 ) ≤ f (z k ) - γµ D 1 -β ∇f (z k ) D + Lγ 2 γ D 2(1 -β) 2 (14) ≤ f (z k ) - γµ D (1 -β)R 0 (f (z k ) -f (x * )) + Lγ 2 γ D 2(1 -β) 2 .

Taking full expectation, subtracting f (x * ) from the both sides of the previous inequality and using the tower property of mathematical expectation we get

EQUATION

) Since γ < (1-β)R0 µ D the term 1 -γµ D (1-β)R0

is positive and we can unroll the recurrence (40):

E f (z k ) -f (x * ) ≤ 1 - γµ D (1 -β)R 0 k f (z 0 ) -f (x * ) + Lγ 2 γ D 2(1 -β) 2 k-1 l=0 1 - γµ D (1 -β)R 0 l ≤ 1 - γµ D (1 -β)R 0 k f (x 0 ) -f (x * ) + Lγ 2 γ D 2(1 -β) 2 ∞ l=0 1 - γµ D (1 -β)R 0 l ≤ 1 - γµ D (1 -β)R 0 k f (x 0 ) -f (x * ) + Lγ 2 γ D 2(1 -β) 2 • (1 -β)R 0 γµ D = 1 - γµ D (1 -β)R 0 k f (x 0 ) -f (x * ) + Lγγ D R 0 2(1 -β)µ D .

Lastly, putting γ = ε(1-β)µ D Lγ D R0 and k = K from (39) in (38) we have

E[f (z K )] -f (x * ) = 1 - εµ 2 D Lγ D R 2 0 K f (x 0 ) -f (x * ) + ε 2 ≤ exp -K • εµ 2 D Lγ D R 2 0 f (x 0 ) -f (x * ) + ε 2 (39) = ε 2 + ε 2 = ε.

Next we use technical lemma from Mishchenko et al. (2019) . We provide the original proof for completeness.

Lemma C.1 (Lemma 6 from Mishchenko et al. (2019) ). Let a sequence {a k } k≥0 satisfy inequality a k+1 ≤ (1 -γ k α)a k + (γ k ) 2 N for any positive γ k ≤ γ 0 with some constants α > 0, N > 0, γ 0 > 0.

Further, let θ ≥ 2 γ0 and take C such that N ≤ αθ 4 C and a 0 ≤ C. Then, it holds

a k ≤ C α θ k + 1 if we set γ k = 2 αk+θ .

Proof. We will show the inequality for a k by induction. Since inequality a 0 ≤ C is one of our assumptions, we have the initial step of the induction. To prove the inductive step, consider

a k+1 ≤ (1 -γ k α)a k + (γ k ) 2 N ≤ 1 - 2α αk + θ θC αk + θ + θα C (αk + θ) 2 .

To show that the right-hand side is upper bounded by θC α(k+1)+θ , one needs to have, after multiplying both sides by (αk + θ)(αk

+ α + θ)(θC) -1 , 1 - 2α αk + θ (αk + α + θ) + α αk + α + θ αk + θ ≤ αk + θ, which is equivalent to α -α αk + α + θ αk + θ ≤ 0.

The last inequality is trivially satisfied for all k ≥ 0.

Theorem C.2 (Decreasing stepsizes). Let Assumptions A.1, A.2 and C.1 be satisfied. If we set γ k = 2 αk+θ , where α = µ D (1-β)R0 and θ ≥ 2 α , then for the iterates of SMTP method the following inequality holds:

EQUATION

)

where

η def = α θ . Then, if we choose γ k = 2α α 2 k+2 where α = µ D

(1-β)R0 and run SMTP for k = K iterations where

EQUATION

)

we get E f (z K ) -f (x * ) ≤ ε.

Proof. In (40) we proved that

E f (z k+1 ) -f (x * ) ≤ 1 - γµ D (1 -β)R 0 E f (z k ) -f (x * ) + Lγ 2 γ D 2(1 -β) 2 .

Having that, we can apply Lemma C.1 to the sequence E f (z k ) -f (x * ) . The constants for the lemma are:

N = Lγ D 2(1-β) 2 , α = µ D (1-β)R0 and C = max f (x 0 ) -f (x * ), 2Lγ D αθ(1-β) 2 . Lastly, choosing γ k = 2α α 2 k+2 is equivalent to the choice θ = 2 α . In this case, we have αθ = 2, C = max f (x 0 ) -f (x * ), Lγ D (1-β) 2 and η = α θ = α 2 2 = µ 2 D 2(1-β) 2 R 2 0

. Putting these parameters and K from (42) in the (41) we get the result.

D STRONGLY CONVEX CASE:

Assumption D.1. We assume that f is µ-strongly convex with respect to the norm

EQUATION

)

It is well known that strong convexity implies

EQUATION

)

Theorem D.1 (Solution-dependent stepsizes). Let Assumptions A.1, A.2 and D.1 be satisfied. If we set

γ k = (1-β)θ k µ D L 2µ(f (z k ) -f (x * )) for some θ k ∈ (0, 2) such that θ = inf k≥0 {2θ k -γ D θ 2 k } ∈ 0, L µ 2 D µ

, then for the iterates of SMTP the following inequality holds:

EQUATION

)

If we run SMTP for k = K iterations where

EQUATION

)

where κ def = L µ is the condition number of the objective, we will get

E f (z K ) -f (x * ) ≤ ε.

Proof. From ( 32) and

γ k = θ k µ D L 2µ(f (x k ) -f (x * )) we have E s k ∼D f (z k+1 ) -f (x * ) ≤ f (z k ) -f (x * ) - γ k µ D 1 -β ∇f (z k ) D + L(γ k ) 2 γ D 2(1 -β) 2 (44) ≤ f (z k ) -f (x * ) - γ k µ D 1 -β 2µ(f (z k ) -f (x * )) + γ D θ 2 k µ 2 D µ L (f (z k ) -f (x * )) ≤ f (z k ) -f (x * ) - 2θ k µ 2 D µ L (f (z k ) -f (x * )) + γ D θ 2 k µ 2 D µ L (f (z k ) -f (x * )) ≤ 1 -(2θ k -γ D θ 2 k ) µ 2 D µ L (f (z k ) -f (x * )). Using θ = inf k≥0 {2θ k -γ D θ 2 k } ∈ 0, L µ 2

D µ and taking the full expectation from the previous inequality we get

E f (z k+1 ) -f (x * ) ≤ 1 - θµ 2 D µ L E f (z k ) -f (x * ) ≤ 1 - θµ 2 D µ L k+1 f (x 0 ) -f (x * ) .

Lastly, from (45) we have

E f (z K ) -f (x * ) ≤ 1 - θµ 2 D µ L K f (x 0 ) -f (x * ) ≤ exp -K θµ 2 D µ L f (x 0 ) -f (x * ) (46) ≤ ε.

Assumption D.2. We assume that for all s ∼ D we have s 2 = 1. Theorem D.2 (Solution-free stepsizes). Let Assumptions A.1, A.2, D.1 and D.2 be satisfied. If additionally we compute

f (z k + ts k ), set γ k = (1-β)|f (z k +ts k )-f (z k )|

Lt:

for t > 0 and assume that D is such that µ 2 D ≤ L µ , then for the iterates of SMTP the following inequality holds:

EQUATION

)

Moreover, for any ε > 0 if we set t such that

EQUATION

)

and run SMTP for k = K iterations where

EQUATION

)

where

κ def = L µ is the condition number of f , we will have E f (z K ) -f (x * ) ≤ ε.

Proof. Recall that from (31) we have

f (z k+1 ) ≤ f (z k ) - γ k 1 -β | ∇f (z k ), s k | + L(γ k ) 2 2(1 -β) 2 .

If we minimize the right hand side of the previous inequality as a function of γ k , we will get that the optimal choice in this sense is

γ k opt = (1-β)| ∇f (z k ),s k | L .

However, this stepsize is impractical for derivative-free optimization, since it requires to know ∇f (z k ). The natural way to handle this is to approximate directional derivative ∇f

(z k ), s k by finite difference f (z k +ts k )-f (z k ) t

and that is what we do. We choose

γ k = (1-β)|f (z k +ts k )-f (z k )| Lt = (1-β)| ∇f (z k ),s k | L + (1-β)|f (z k +ts k )-f (z k )| Lt - (1-β)| ∇f (z k ),s k | L def = γ k opt + δ k . From this we get f (z k+1 ) ≤ f (z k ) - | ∇f (z k ), s k | 2 2L + L 2(1 -β) 2 (δ k ) 2 .

Next we estimate |δ k |:

|δ k | = (1 -β) Lt |f (z k + ts k ) -f (z k )| -| ∇f (z k ), ts k | ≤ (1 -β) Lt f (z k + ts k ) -f (z k ) -∇f (z k ), ts k (3) ≤ (1 -β) Lt • L 2 ts k 2 2 = (1 -β)t 2 .

It implies that

f (z k+1 ) ≤ f (z k ) - | ∇f (z k ), s k | 2 2L + L 2(1 -β) 2 • (1 -β) 2 t 2 4 = f (z k ) - | ∇f (z k ), s k | 2 2L +

Lt 2 8 and after taking full expectation from the both sides of the obtained inequality we get

E f (z k+1 ) -f (x * ) ≤ E f (z k ) -f (x * ) - 1 2L E | ∇f (z k ), s k | 2 + Lt 2 8 .

Note that from the tower property of mathematical expectation and Jensen's inequality we have

E | ∇f (z k ), s k | 2 = E E s k ∼D | ∇f (z k ), s k | 2 | z k ≥ E E s k ∼D | ∇f (z k ), s k | | z k 2 (30) ≥ E µ 2 D ∇f (z k ) 2 D (44) ≥ 2µ 2 D µE f (z k ) -f (x * ) .

Putting all together we get

E f (z k+1 ) -f (x * ) ≤ 1 - µ 2 D µ L E f (z k ) -f (x * ) + Lt 2 8 . Due to µ 2 D ≤ L µ we have E f (z k ) -f (x * ) ≤ 1 - µ 2 D µ L k f (x 0 ) -f (x * ) + Lt 2 8 k-1 l=0 1 - µ 2 D µ L l ≤ 1 - µ 2 D µ L k f (x 0 ) -f (x * ) + Lt 2 8 ∞ l=0 1 - µ 2 D µ L l = 1 - µ 2 D µ L k f (x 0 ) -f (x * ) + L 2 t 2 8µ 2 D µ .

Lastly, from (47) we have

E f (z K ) -f (x * ) ≤ 1 - µ 2 D µ L K f (x 0 ) -f (x * ) + L 2 t 2 8µ 2 D µ (48) ≤ exp -K µ 2 D µ L f (x 0 ) -f (x * ) + ε 2 (49) ≤ ε 2 + ε 2 = ε.

E SMTP_IS: STOCHASTIC MOMENTUM THREE POINTS WITH IMPORTANCE SAMPLING:

Again by definition of z k+1 we get that the sequence {f (z k )} k≥0 is monotone:

EQUATION

Lemma E.1. Assume that f satisfies Assumption 4.1. Then for the iterates of SMTP_IS the following inequalities hold:

EQUATION

and

EQUATION

)

Proof. In the similar way as in Lemma A.1 one can show that

EQUATION

and

z k+1 + = z k - γ k i 1 -β e i k , z k+1 - = z k + γ k i 1 -β e i k .

It implies that

f (z k+1 + ) (26) ≤ f (z k ) - γ k i 1 -β ∇ i f (z k ) + L i k (γ k i ) 2 2(1 -β) 2 and f (z k+1 -) ≤ f (z k ) + γ k i 1 -β ∇ i f (z k ) + L i k (γ k i ) 2 2(1 -β) 2 .

Unifying these two inequalities we get

f (z k+1 ) ≤ min{f (z k+1 + ), f (z k+1 -)} = f (z k ) - γ k i 1 -β |∇ i f (z k )| + L i k (γ k i ) 2 2(1 -β) 2 ,

which proves (51). Finally, taking the expectation E[• | z k ] conditioned on z k from the both sides of the previous inequality we obtain

E f (z k+1 ) | z k ≤ f (z k ) - 1 1 -β E γ k i |∇ i k f (z k )| | z k + 1 2(1 -β) 2 E L i k (γ k i ) 2 | z k . E.1 NON-CONVEX CASE Theorem E.1. Assume that f satisfies Assumption 4.1. Let SMTP_IS with γ k i = γ wi k

for some γ > 0 produce points {z 0 , z 1 , . . . , z K-1 } and z K is chosen uniformly at random among them. Then

EQUATION

) Moreover, if we choose γ = γ0 √ K , then E ∇f (z K ) 1 ≤ 1 √ K min i=1,...,d pi wi (1 -β)(f (x 0 ) -f (x * )) γ 0 + γ 0 2(1 -β) d i=1 L i p i w 2 i . (55) Note that if we choose γ 0 = 2(1-β) 2 (f (x 0 )-f (x * )) d i=1 L i p i w 2 i

in order to minimize right-hand side of (55), we will get

EQUATION

)

Note that for p i = Li / d i Li with w i = L i we have that the rates improves to

EQUATION

Proof. Recall that from (52) we have

E f (z k+1 ) | z k ≤ f (z k ) - 1 1 -β E γ k i |∇ i k f (z k )| | z k + 1 2(1 -β) 2 E L i k (γ k i ) 2 | z k . (58) Using our choice γ k i = γ wi k we derive E γ k i |∇ i k f (z k )| | z k = γ d i=1 p i w i |∇ i f (z k )| ≥ γ ∇f (z k ) 1 min i=1,...,d p i w i

and

E L i k (γ k i ) 2 | z k = γ 2 d i=1 L i p i w 2 i .

Putting it in (58) and taking full expectation from the both sides of obtained inequality we get

E f (z k+1 ) ≤ E f (z k ) - γ min i=1,...,d pi wi 1 -β E ∇f (z k ) 1 + γ 2 2(1 -β) 2 d i=1 L i p i w 2 i , whence ∇f (z k ) 1 ≤ (1 -β) E f (z k ) -E f (z k+1 ) γ min i=1,...,d pi wi + γ 2(1 -β) min i=1,...,d pi wi d i=1 L i p i w 2 i .

Summing up previous inequality for k = 0, 1, . . . , K -1 and dividing both sides of the result by K, we get

1 K K-1 k=0 E ∇f (z k ) 1 ≤ (1 -β)(f (z 0 ) -f (x * )) Kγ min i=1,...,d pi wi + γ 2(1 -β) min i=1,...,d pi wi d i=1 L i p i w 2 i . It remains to notice that 1 K K-1 k=0 E ∇f (z k ) 1 = E ∇f (z K ) 1 . The last part where γ = γ0 √ K is straightforward.

E.2 CONVEX CASE:

As for SMTP to tackle convex problems by SMTP_IS we use Assumption 3.2 with , then for the iterates of SMTP_IS method the following inequality holds:

• D = • 1 . Note that in this case R 0 = max x -x * ∞ | f (x) ≤ f (x 0 ) .

E f (z k ) -f (x * ) ≤   1 - γ min i=1,...,d pi wi (1 -β)R 0   k f (z 0 ) -f (x * ) + γR 0 2(1 -β) min i=1,...,d pi wi d i=1 L i p i w 2 i . (59) Moreover, if we choose γ = ε(1-β) min i=1,...,d p i w i R0 d i=1 L i p i w 2 i for some 0 < ε ≤ R 2 0 d i=1 L i p i w 2 i min i=1,...,d p 2 i w 2 i

and run SMTP_IS for k = K iterations where

EQUATION

)

EQUATION

Proof. Recall that from (52) we have

E f (z k+1 ) | z k ≤ f (z k ) - 1 1 -β E γ k i |∇ i k f (z k )| | z k + 1 2(1 -β) 2 E L i k (γ k i ) 2 | z k . (62) Using our choice γ k i = γ wi k we derive E γ k i ∇ i k f (z k ) | z k = γ d i=1 p i w i |∇ i f (z k )| ≥ γ ∇f (z k ) 1 min i=1,...,d p i w i (14) ≥ γ R 0 min i=1,...,d p i w i f (z k ) -f (x * )

and

E L i k (γ k i ) 2 | z k = γ 2 d i=1 L i p i w 2 i .

Putting it in (62) and taking full expectation from the both sides of obtained inequality we get 

EQUATION

E f (z k ) -f (x * ) ≤ 1 - γ (1 -β)R 0 min i=1,...,d p i w i k f (z 0 ) -f (x * ) + γ 2 2(1 -β) 2 d i=1 L i p i w 2 i k-1 l=0 1 - γ (1 -β)R 0 min i=1,...,d p i w i l ≤ 1 - γ (1 -β)R 0 min i=1,...,d p i w i k f (z 0 ) -f (x * ) + γ 2 2(1 -β) 2 d i=1 L i p i w 2 i ∞ l=0 1 - γ (1 -β)R 0 min i=1,...,d p i w i l ≤   1 - γ min i=1,...,d pi wi (1 -β)R 0   k f (z 0 ) -f (x * ) + γR 0 2(1 -β) min i=1,...,d pi wi d i=1 L i p i w 2 i . Then, putting γ = ε(1-β) min i=1,...,d p i w i R0 d i=1 L i p i w 2 i

and k = K from ( 60) in ( 59) we have (1-β)R0 and θ ≥ 2 α , then for the iterates of SMTP_IS method the following inequality holds:

E[f (z K )] -f (x * ) =      1 - ε min i=1,...,d p 2 i w 2 i R 2 0 d i=1 Lipi w 2 i      K f (z 0 ) -f (x * ) + ε 2 ≤ exp          -K • ε min i=1,...,d p 2 i w 2 i R 2 0 d i=1 Lipi w 2 i          f (z 0 ) -f (x * ) + ε 2 (60) = ε 2 + ε 2 = ε.

EQUATION

where

η def = α θ . Moreover, if we choose γ k = 2α α 2 k+2 where α = min i=1,...,d p i w i

(1-β)R0 and run SMTP_IS for k = K iterations where

K = 1 ε • 2R 2 0 min i=1,...,d p 2 i w 2 i max (1 -β) 2 (f (x 0 ) -f (x * )), d i=1 L i p i w 2 i - 2(1 -β) 2 R 2 0 min i=1,...,d p 2 i w 2 i , ε > 0, (65) we will get E f (z K ) -f (x * ) ≤ ε.

Proof. In (63) we proved that

E f (z k+1 ) -f (x * ) ≤   1 - γ min i=1,...,d pi wi (1 -β)R 0   E f (z k ) -f (x * ) + γ 2 2(1 -β) 2 d l=1 L i p i w 2 i .

Having that, we can apply Lemma C.1 to the sequence E f (z k ) -f (x * ) . The constants for the lemma are: N = 

k i = (1-β)θ k min i=1,...,d p i w i wi k d i=1 L i p i w 2 i 2µ(f (z k ) -f (x * )) for some θ k ∈ (0, 2) such that θ = inf k≥0 {2θ k -θ 2 k } ∈   0, d i=1 L i p i w 2 i µ min i=1,...,d p 2 i w 2 i  

, then for the iterates of SMTP_IS method the following inequality holds:

EQUATION

If we run SMTP_IS for k = K iterations where

EQUATION

we will get E f (z K ) -f (x * ) ≤ ε.

Proof. Recall that from (52) we have

E f (z k+1 ) | z k ≤ f (z k ) - 1 1 -β E γ k i |∇ i k f (z k )| | z k + 1 2(1 -β) 2 E L i k (γ k i ) 2 | z k . (68) Using our choice γ k i = (1-β)θ k min i=1,...,d p i w i wi k d i=1 L i p i w 2 i 2µ(f (z k ) -f (x * )) we derive E γ k i ∇ i k f (z k ) | z k = (1 -β)θ k min i=1,...,d pi wi d i=1 Lipi w 2 i 2µ(f (z k ) -f (x * )) d i=1 p i w i |∇ i f (z k )| ≥ (1 -β)θ k min i=1,...,d pi wi 2 d i=1 Lipi w 2 i 2µ(f (z k ) -f (x * )) ∇f (z k ) 1 (20) ≥ 2(1 -β)θ k min i=1,...,d p 2 i w 2 i d i=1 Lipi w 2 i µ(f (z k ) -f (x * ))

and

E L i k (γ k i ) 2 | z k = 2(1 -β) 2 θ 2 k min i=1,...,d p 2 i w 2 i d i=1 Lipi w 2 i 2 µ(f (z k ) -f (x * )) d i=1 L i p i w 2 i = 2(1 -β) 2 θ 2 k min i=1,...,d p 2 i w 2 i d i=1 Lipi w 2 i µ(f (z k ) -f (x * )).

Putting it in (68) and taking full expectation from the both sides of obtained inequality we get

E f (z k+1 ) -f (x * ) ≤      1 -(2θ -θ 2 ) µ min i=1,...,d p 2 i w 2 i d i=1 Lipi w 2 i      E f (z k ) -f (x * ) . Using θ = inf k≥0 {2θ k -θ 2 k } ∈   0, d i=1 L i p i w 2 i µ min i=1,...,d p 2 i w 2 i   we obtain E f (z k+1 ) -f (x * ) ≤      1 - θµ min i=1,...,d p 2 i w 2 i d i=1 Lipi w 2 i      E f (z k ) -f (x * ) ≤      1 - θµ min i=1,...,d p 2 i w 2 i d i=1 Lipi w 2 i      k+1 f (x 0 ) -f (x * ) .

Lasrtly, from (66) we have

EQUATION

≤ ε.

The previous result based on the choice of γ k which depends on the f (z k ) -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 • D = • 2 ) and 4.1 be satisfied.

If additionally we compute:

f (z k + te i k ), set γ k i = (1-β)|f (z k +tei k )-f (z k )| Li k t

for t > 0, then for the iterates of SMTP_IS method the following inequality holds:

E f (z k ) -f (x * ) ≤ 1 -µ min i=1,...,d p i L i k f (x 0 ) -f (x * ) + t 2 8µ min i=1,...,d pi Li d i=1 p i L i . (69)

Moreover, for any ε > 0 if we set t such that

EQUATION

and run SMTP_IS for k = K iterations where

EQUATION

we will get E f (z K ) -f (x * ) ≤ ε. Moreover, note that for p i = Li / d i Li with w i = L i , the rate improves to

EQUATION

Proof. Recall that from (51) we have

f (z k+1 ) ≤ f (z k ) - γ k i 1 -β |∇ i k f (z k )| + L i k (γ k i ) 2 2(1 -β) 2 .

If we minimize the right hand side of the previous inequality as a function of γ k i , we will get that the optimal choice in this sense is γ

k opt = (1-β)|∇i k f (z k )| Li k

. However, this stepsize is impractical for derivative-free optimization, since it requires to know ∇ i k f (z k ). The natural way to handle this is to

approximate directional derivative ∇ i k f (z k ) by finite difference f (z k +tei k )-f (z k ) t

and that is what we do. We choose

γ k i = (1-β)|f (z k +tei k )-f (z k )| Li k t = (1-β)|∇i k f (z k )| Li k + (1-β)|f (z k +tei k )-f (z k )| Li k t - (1-β)|∇i k f (z k )| Li k def = γ k opt + δ k i . From this we get f (z k+1 ) ≤ f (z k ) - |∇ i k f (z k )| 2 2L i k + L i k 2(1 -β) 2 (δ k i ) 2 .

Next we estimate |δ k i |:

EQUATION

and after taking expectation E • | z k conditioned on z k from the both sides of the obtained inequality we get

E f (z k+1 ) | z k ≤ f (z k ) - 1 2 E |∇ i k f (z k )| 2 L i k | z k + t 2 8 E L i k | z k .

Note that 

E |∇ i k f (z k )| 2 L i k | z k = d i=1 p i L i |∇ i f (z k )| 2 ≥ ∇f (z k

E L i k | z k = d i=1 p i L i .

Putting all together we get

E f (z k+1 ) | z k ≤ f (z k ) -µ min i=1,...,d p i L i f (z k ) -f (x * ) + t 2 8 d i=1 p i L i .

Taking full expectation from the previous inequality we get

E f (z k+1 ) -f (x * ) ≤ 1 -µ min i=1,...,d p i L i E f (z k ) -f (x * ) + t 2 8 d i=1 p i L i .

Since µ ≤ L i for all i = 1, . . . , d we have 

E f (z k ) -f (x * ) ≤ 1 -µ min

p i L i f (x 0 ) -f (x * ) + ε 2 (71) ≤ ε 2 + ε 2 = ε.

E.4 COMPARISON OF SMTP AND SMTP_IS:

Here we compare SMTP when D is normal distribution with zero mean and I d covariance matrix with SMTP_IS with probabilities p i = Li / d i=1 Li. We choose such a distribution for SMTP since it shows the best dimension dependence among other distributions considered in Lemma F.1. Note that if f satisfies Assumption 4.1, it is L-smooth with L = max i=1,...,d L i . So, we always have that d i=1 L i ≤ dL. Table 3 summarizes complexities in this case. We notice that for SMTP we have • D = • 2 . That is why one needs to compare SMTP with SMTP_IS accurately. At the first glance, Table 3 says that for non-convex and convex cases we get an extra d factor in the complexity of SMTP_IS when L 1 = . . . = L d = L. However, it is natural since we use different norms for SMTP and SMTP_IS. In the non-convex case for SMTP we give number of iterations in order to guarantee E ∇f (z K ) 2 ≤ ε while for SMTP_IS we provide number of iterations in order to guarantee E ∇f (z K ) 1 ≤ ε. From Holder's inequality That is, in all cases SMTP_IS shows better complexity than SMTP up to some constant factor. 

F AUXILIARY RESULTS:



Lemma:



:

We will refer to this as momentum.

We will use thinner assumption in Section 4.

The code will be made available online upon acceptance of this work.

Figures and Tables:

2, . . . , d}. Operator E[•] denotes mathematical expectation with respect to all randomness and E s∼D [•] denotes conditional expectation w.r.t. randomness coming from random vector s which is sampled from probability distribution D on R d . To denote standard inner product of two vectors x, y ∈ R d we use x, y def = d i=1 x i y i , e i denotes i-th coordinate vector from standard basis in R d , i.e. x = d i=1

Figure 1: SMTP is far superior to STP on all 5 different MuJoCo tasks particularly on the high dimensional Humanoid-v1 problem. The horizontal dashed lines are the thresholds used in Table2to demonstrate complexity of each method.

ξ, x | x D ≤ 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 γ k ≡ γ < (1-β)R0 µ D

Constant stepsize). Let Assumptions 3.2 and 4.1 be satisfied. If we set γ k i

Decreasing stepsizes). Let Assumptions 3.2 and 4.1 be satisfied. If we set γ k i = γ k wi k and γ k = 2 αk+θ , where α =

note that choosing γ k = 2α α 2 k+2 is equivalent to choice θ = 2 α . In this case we have αθ = 2 and C = max f (x 0 ) -f (x * ), Putting these parameters and K from (65) in the (64) we get the result.E.3 STRONGLY CONVEX CASETheorem E.4 (Solution-dependent stepsizes). Let Assumptions 3.3 (with • D = • 1 ) and 4.1 be satisfied. If we set γ

2µ f (z k ) -f (x * ) min i=1,...,d p i L i , since • D = • 2 , and

i .Lastly, from (69) we haveE f (z K ) -f (x * ) ≤ 1 -

Comparison of SMTP with D = N 0, I d and SMTP_IS with p i = Li / d i=1 Li.Herer 0 = f (x 0 ) -f (x * ), R 0, 2 corresponds to the R 0 from Assumption C.1 with • D = • 2 and R 0, ∞ corresponds to the R 0 from Assumption C.1 with • D = • 1 . • 1 ≤ √ d • 2 and, therefore, in order to have E ∇f (z K ) 1 ≤ ε for SMTP we need to ensure that E ∇f (z K ) 2 ≤ ε √ d . That is, to guarantee E ∇f (z K ) 1 ≤ ε SMTP for aforementioned distribution needs to perform πr0d 2 L ε 2 iterations.Analogously, in the convex case using Cauchy-Schwartz inequality• 2 ≤ √ d • ∞ we have that R 0, 2 ≤ √ dR 0, ∞ .Typically this inequality is tight and if we assume that R 0, ∞ ≥ C R 0, 2 √ d , we will get that SMTP_IS complexity is

F.1 (Lemma 3.4 from Bergou et al. (2019)). Let g ∈ R d . 1. If D is the uniform distribution on the unit sphere in R d , then γ D = 1 and E s∼D | g, s | satisfies Assumption 3.1 with γ D = 1, • D = • 2 and µ D ∼ 1 √ 2πd . 2. If D is the normal distribution with zero mean and identity over d as covariance matrix (i.e. s ∼ N (0, I d )) then γ D = 1 and E s∼D | g, s | = satisfies Assumption 3.1 with γ D = 1, • D = • 2 and µ D = √ 2 √ dπ . 3. If D is the uniform distribution on {e 1 , . . . , e d }, then γ D = 1 and E s∼D | g, s | satisfies Assumption 3.1 with γ D = 1, • D = • 1 and µ D = 1 d . 4. If D is an arbitrary distribution on {e 1 , . . . , e d } given by P {s = e i } = p i > 0, then γ D = 1 and E s∼D | g, s | = g D def = d i=1 p i |g i |. (76) Hence, D satisfies Assumption 3.1 with γ D = 1 and µ D = 1. 5. If D is a distribution on D = {u 1 , . . . , u d } where u 1 , . . . , u d form an orthonormal basis of R d and P {s = d i } = p i , then γ D = 1 and E s∼D | g, s | = g D def = d i=1 p i |g i |. (77)

Summary of the new derived complexity results of SMTP and SMTP_IS. The complexities for SMTP are under a generic sampling distribution D satisfying Assumption 3.1 while for SMTP_IS are under an arbitrary discrete sampling from a set of coordinate directions followingBibi et al. (2019) where we propose an importance sampling that improves the leading constant marked in red. Note that r 0 = f (x 0 ) -f (x * ) and that all assumptions listed are in addition to Assumption 2.1. Complexity means number of iterations in order to guarantee E ∇f (z K ) D ≤ ε for the non-convex case, E f (z K ) -f (x * ) ≤ ε for convex and strongly convex cases. R 0 < ∞ is the radius in • * D -norm of a bounded level set where the exact definition is given in Assumption 3.2. We notice that for SMTP_IS • D = • 1 and • * D = • ∞ in non-convex and convex cases and

Table content: <table/>



Table content: <table><tr><td/><td>Threshold</td><td>STP</td><td>STP IS</td><td colspan="6">SMTP SMTP IS ARS(V1-t) ARS(V2-t) NG-lin TRPO-nn</td></tr><tr><td>Swimmer-v1</td><td>325</td><td>320</td><td>110</td><td>80</td><td>100</td><td>100</td><td>427</td><td>1450</td><td>N/A</td></tr><tr><td>Hopper-v1</td><td>3120</td><td>3970</td><td>2400</td><td>1264</td><td>1408</td><td>51840</td><td>1973</td><td>13920</td><td>10000</td></tr><tr><td>HalfCheetah-v1</td><td>3430</td><td>13760</td><td>4420</td><td>1872</td><td>1624</td><td>8106</td><td>1707</td><td>11250</td><td>4250</td></tr><tr><td>Ant-v1</td><td>3580</td><td colspan="2">107220 43860</td><td>19890</td><td>14420</td><td>58133</td><td>20800</td><td>39240</td><td>73500</td></tr><tr><td>Humanoid-v1</td><td>6000</td><td>N/A</td><td colspan="3">530200 161230 207160</td><td>N/A</td><td>142600</td><td>130000</td><td>UNK</td></tr></table>

Peer review (iclr2020):
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. Overall, 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. That said, I have some concerns. (1) The analysis is nice in that it shows the methods work, but doesn*t demonstrate benefit of their method over other methods (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. (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. -- 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. -- 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 -- Literature review seems good and pretty thorough (mentions most key references through 2015, and a good selection of references since then). -- 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. -- 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. -- 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. -- 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). -- p 26/27, *Causchy-Schwartz* is spelled wrong, and usually this is called *Holder*s inequality* when it*s not the Euclidean norm. -- Table 3, there is no space between the caption and the main text, so it*s confusing -- Eq (76) in appendix, the sum should go to d not 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. -- 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). == AFTER READING REBUTTAL == I 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. The 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 bound, but also to the bound in the next paragraph. But despite a few items I*m being cranky about, I think it*s still a solid paper, and it*s still a weak accept.