Zeroth Order Optimization by a Mixture of Evolution Strategies
Authors: Jun-Kun Wang
Xiaoyun Li
Ping Li
Venue:  (2020)

Abstract: Evolution strategies or zeroth-order optimization algorithms have become popular in some areas of optimization and machine learning where only the oracle of function value evaluations is available. The central idea in the design of the algorithms is by querying function values of some perturbed points in the neighborhood of the current update and constructing a pseudo-gradient using the function values. In recent years, there is a growing interest in developing new ways of perturbation. Though the new perturbation methods are well motivating, most of them are criticized for lack of convergence guarantees even when the underlying function is convex. Perhaps the only methods that enjoy convergence guarantees are the ones that sample the perturbed points uniformly from a unit sphere or from a multivariate Gaussian distribution with an isotropic covariance. In this work, we tackle the non-convergence issue and propose sampling perturbed points from a mixture of distributions. Experiments show that our proposed method can identify the best perturbation scheme for the convergence and might also help to leverage the complementariness of different perturbation schemes.


Under review as a conference paper at ICLR 2020
ZEROTH ORDER OPTIMIZATION BY A MIXTURE OF EVOLUTION STRATEGIES
Anonymous authors Paper under double-blind review
ABSTRACT
Evolution strategies or zeroth-order optimization algorithms have become popular in some areas optimization and machine learning where only the oracle of func- tion value evaluations is available. The central idea in the design of the algorithms is by querying function values of some perturbed points in the neighborhood of the current update and constructing a gheudo-gradien using the function values. In recent years, there is a growing interest in developing new ways of perturba- tion. Though the new perturbation methods well motivating, most of them are criticized for lack of convergence guarantees even when the underlying func- tion is convex. Perhaps the only methods that enjoy convergence guarantees are the ones that sample the perturbed points uniformly from a unit sphere or from a multivariate Gaussian distribution with an isotropic covariance. In this work, we tackle the non-convergence issue and propose sampling perturbed points from a mixture of distributions. Experiments show that our proposed method can identify the best perturbation scheme for the convergence and might also help to leverage the complementariness of different perturbation schemes.
INTRODUCTION
We consider optimizing a function f(-) RR +
IR in the setting that only querying function values allowed and there is no access to gradients of the function. Alternatively, we aim at minimizing a blxck-box function in which only the oracle of function value evaluations is available,
min f(w).
(1)
There are growing interest in studying "gradient-free" optimization due to its applications in hyper- parameter search (e.g.. |Bergstra et al. (20TT); Koch et al.] (2018)). reinforcement learning (e.g., Sehnke et al. (2100); Mania et al. (201(2018 8); Salimans al. (2017 7); Choromanski et al. (201 8); Vemula |l.
et al. 2019 ) or black-box adversarial attacks on deep neural nets (e.g., Chen et al. (2017): Ilyas et al. 2018); Papernot et al. (2017)). In hyper-paramette search, the goal is to find the best values of a set of hyper-pauee parameters for machine learning model (c.g.. a neural net). One can model the task of hyper-parameter search as optimizing an unknown/black box function as (1. Specifically, in the way that each element of w represents the value of specific hyper-parameter and different points w in the hyper-parameter space correspond to different realizations of the hyper-parameters. The mapping (i.c., f(-)) from hyper-parameter values a performance metric (e.g., classification error) of using those hyper-parameter values is unknown. Therefore, the gradient of the mapping/function is not available. One can only query the function value (i.e., obtaining f (w)) by training a model with the hyper-parameter values indicated by w. Obtaining the arg min of (T) in this case corresponds to finding the best values of the hyper- parameters (and consequently getting the best trained model). Because of the broad applicability of zeroth order optimization algorithms, recently there has been spate of research in improving them from different respects.
one can let w be in the space of
Standard zeroth order algorithms construct pseudo-gradients by sampling some perturbed points from a Gaussian distribution with an isotropic covariance (e.g.. Nesterov & Spokoiny (2017):Duchh
et al. (2012) or uniformly from unit sphere (e.g., Flaxman (e.gg,,Faxxxan et al. x Duchi et al. (2012); (hhami
(2017)) )). Algorithm describes a popular technique called ".. "Gaussian smoothing" first samples
some K perturbed vectors oy from Gaussian distribution, then a pseudo-gradient gi is constructed

---

Under review as a conference paper at ICLR 2020
Algorithm 1 Gaussian smoothing.
1: Require: hyper-parameters o, K and
2: Init: we E R
3: for t 0 to T do
4: Sample K perturbed vectors vt ~ (0, Is) for each E [K].
5: Construct pseudo-gradient g: Σ (S(w, + out) f(w.))o.
6: Obtain the next update W1+1 W² ng..
7: end for
by taking a weighted average of these perturbed points. The pseudo gradient is subsequently used to obtain the next update 1.+11 Very recently, there has been trend of studies in proposing sampling the perturbed vectors from some non con-isotropic Gaussian distributions (e.g. Maheswaranathan et al. (2019); Choromanski
al. ( Ye al. (2019)). They consider sampling perturbed vectors by 2f [0, 2 such that the covariance Σ may not be scale of the identity matrix. Maah to reflect the local geometry. Choromanski et al.] (2019a) propose updating Σ in the sense to tracking the low-dimensional manifold of the gradient space. Ye et al. (2019) propose letting be the in- verse of a diagonal matrix in way that the update rule of each diagonal element is in the fashion of updating the second moment quantity in "Adam" optimization algorithm of Kingma & Ba (2015). Nevertheless, these sampling methods have not really been shown to lead to the convergence to a global minimum even when the underlying function f(-) is convex, albeit some motivating toy examples some analysis (but not related to the convergence) are provided.
eswaranathan et al. 2019) propose letting be related with the span of latest
In this paper, we tackle the issue by proposing sampling from a mixture of distributions in which one of them is the standard Gaussian distribution with isotropic covariance. Our method leverages a bandit algorithm for adaptively selecting which distribution the perturbed vectors are sampled from. By building the theoretical guarantee of the bandit algorithm and the convergence guarantee of the algorithm which always sampling from an isotropic Gaussian distribution (i.e., Algorithm|] I) we can show that our method converges with high probability when the underlying function convex. We conduct experiments to show that our algorithm works well in practice. Our proposed algorithm is competitive with any algorithms that always sample perturbed vectors from a fixed component (distribution) of the mixture which our algorithm considers. This shows the effectiveness of the proposed method, as one would not know which perturbation scheme is the best beforehand. Furthermore, the proposed algorithm might outperform any of them when the complementariness of different perturbation schemes are exploited.
2 RELATED WORKS
Zeroth order optimization is studied in different areas, from optimization, online learning, to bioin- formatics. In optimization community, the setting that an algorithm can only query function values might date back to Nemirovski & Yudin (1983) (Chapter 9.3). [emirovski & Yudin (1983) develop sampling perturbed vectors on a 2-norm sphere for constructing the pseudo gradients. Furthermore, they also develop different family of zeroth order optimization algorithms that uses binary search (see also |Spal| (2003); Agarwal et al. (201 Jamieson al. (2012)) On the other hand, some lower bound results regarding the iteration complexity are obtained in recent years (c.g.. Duchi et al.) (Shamir (2013); Jamieson Jamisson al. 2012)) For online learning, Flaxman al. (005) introduce online convex optimization with "bandit" feedback. It considers that, in each round, the learner first plays a point in convex set and then it suffers loss which is the function value at the point that the leamner plays. The learner only knows the function value at the point it plays. The goal of the learner to minimize a quantity called "regret". Flaxman et al.) (2005) make the minimal assumption that the loss function in each round is convex while allow the loss functions be adversarially different in different rounds. Many follow-up papers consider different variants of the setting (see e.g. e.g..(aaarwal et al.) (2010): Shamir 2001 2017)) Zeroth order optimization also has connection with some biological evolution (see Rechenberg (1989) and Section 2 of Salimans et al. (2017)) As the re- sult, there are many zeroth order algorithms named as evolution strategies (c.g., Glasmachers et al. (2010): Hansen & Ostermeier (2001): WWerstra et al. (2014)). We also notice that many evolution strategies consider sampling from full covariance Gaussian distributions.
2

---

Under review as a conference paper at ICLR 2020
Substantial progress has been made in zeroth order optimization. Ghadimi & Lan (2013): Lian al. (2016): Liu et al. 20188); Ji et al. (2019) propose some zeroth order algorithms for non-convex optimization. On the other hand, there are some efforts in integrating the "gradient-free" technique into some first-order algorithms. For example, there are a zeroth order counterpart of Alternative Di- rection method of Multipliers (Liu al. (2018a)) zeroth order version of the Frank- Wolfe method Balasubramanian & Ghadimi (2018). ) and a zeroth order version of Adam (Chen et al.] (2019). The design principle basically replacing the step of computing gradient with that constructing the pseudo one. Another direction is by reducing or removing the dependency of convergence rate on the dimension. Since without further assumptions, the convergence rate of any zeroth order opti- mization algorithms depends on the dimension (see e.g.. Nestero & Spokoiny 2017); Duchi et al.) 2012 2015); [Shamir (2013, 2017) ) zeroth order algorithm can suffer from high dimensionality. To deal with the issue, Wang et al. (20T8) assume statistical model for an optimization problem and exploit the assumption to design some algorithms whose convergence rates do not depend on the dimension. Other directions in zeroth order optimization include designing a new estimator of the aseudo-gradient (Choromanski et al.] :0: Rowland et al. (2018), ), which can lead to a smaller variance of the estimator compared to the standard Monte-Care approach.
In this paper, we consider combining different ways of sampling perturbed vectors, which to our direction. As mentioned in the introduction, some recent works propose con-
knowledge is structing pseudo gradients by sampling from a non-isotropic Gaussian distributions whose covari- ance reflects local geometry around the current update (e.g. Maheswaranathan al. (2019) Choro- manski et al. (2019a); Ye et al. (2019)). Though the methods are interesting and well motivating, it unclear if they can guarantee the convergence. We tackle the issue by proposing sampling from mixture of distributions. Our method builds on a technique in bandit literature called EXP3.P (Auer al.) (2002)), which is used for adaptively selecting a sampling scheme during the optimization process.
PRELIMINARIES
Notation:
For a vector u E Idd, we denote u² as the element-wise square and denote diag(w (u) as the d diagonal matrix whose diagonal elements are the elements of u. We use um denotes its ma element of u, which should be distinguished from that stands for the vector u in iteration t.
Many zeroth order optimization algorithms construct a "pseudo" gradient in the following ways. First, the so called Gaussian smoothing is applied to the underlying function f()) to get a new function fo).)
fo (w)) == (. + rv)].
The new function f.(-) is differentiable and the gradient of fo (-) can be shown to be (see c.g., Nesterov & Spokoiny (017))
1 - E [f( touuu
(w))
(3)
Eor [[w σvju ((w)))
where the second equality is due to that v E Idd is zero mean vector. The pseudo gradient fo (w) can be viewed the expectation of the perturbed vectors weighted by the corresponding function values at the near-by points of w. Since it involves the expectation, in practice one uses a mmini-batch
of perturbed vectors to estimate f. (w) (like Algorithm I does). The parameter a controls trade-
off. The larger a, the larger bias of (-) larger [ f(.)). but large might help faster
convergence (to the optimum of (-)) (Nesterov & Spokoiny (2017 Duchi et al. (2012) Since
the algorithms actually optimize (-) instead of the original function f(-). one should not choose too large o, as the difference between fo (w) and f(w) increases as a increases.
Several algorithms in the literature can be written generic scheme equipped with different kinds of perturbation. Specifically, many existing algorithms can be generated from Algorithm 2 by using different sampling oracles. For example,
that Algorithm iis instance of Algorithm with sampling oracle on step 5 being Algorithm 3 Moreover, the recently proposed methods Mah- eswaranathan et al. (2019) Choromanski et al. (2019a) : Ye et al. (2019) can all be viewed some
3

---

Under review as a conference paper at ICLR 2020
instances of Algorithm 2 As illustration, an algorithm in Ye et al. (2019) is instance of Al- gorithm 2 with the sampling oracle on step being Algorithm 4 Ye et al. (2019) argue that the covariance matrix Σ should be the inverse of the Hessian. However, only the function value oracle available in zeroth order optimization, let alone the second-order information is provided. Ye et al. (2019) propose
the second moment quantity of Adam optimization algorithm (Kingma & Ba 2015 to construct a surrogate of the Hessian. However, when the perturbed vectors are sampled from non-isotropic Gaussian distribution, may not lead the convergence optimal point even when the function is convex.
Algorithm A template of zeroth order algorithms.
Require: sampling oracle.
2: Require: hyper-parameters a, K, and
3: Init: Wa E R.".
4: for t = to do
5: Update E, +- SAMPLINGORACLE
6: Sample K perturbed vectors ny ~ (0, Σ.) for each E [K].
7: Construct gecudo-gradiens go Lim1 (f(w, + ov.) f(wi))
8: Update parameter uP++1 = Wt 79t-
9: end for
Algorithm SAMPLINGORACLE ISOTROPIC COVARIANCE
Output: Ia.
Algorithm 4 SAMPLINGORACLE ADAM-STYLE HESSIAN Ye et al. (2019).
1: Require: ppper-prrmmeter a and c.
2: Input: pscudo gradient
3: Init: Do cId.
4: D aD: de)iaag(.)??
5: Output: Σ, inverse (D.).
4 PROPOSED METHOD
Consider that there are M different sampling oracles available. Each oracle (indexed by E [M) maintains its covariance matrix E and one them always outputs the isotropic covariance (c.g., Algorithm 3). So each oracle is actually associated with Gaussian distribution which the perturbed vectors can be sampled from.
We propose Algorithm 5 The idea is sampling the perturbed vectors oa from mixture of Gaussian distributions which are individually updated by their corresponding sampling oracles,
(0,, D E Rdd, AK
[K]
where we should have the weight each mixture component Pm satisfy
Pmm E [0, 1] and ΣM Pm = 1.
e [0, M adapts over time.
To sample ot from the mixture, Algorithm first samples an index m. [M] with each m E [M] following the categorical distribution indicated by p. After that, it samples ei from the Gaussian distribution indexed by m, The pseudo gradient is then constructed and is used to obtain the next update 11+1- At the end of an iteration, the covariance of the Gaussian distribution in which the vectors are sampled from is updated before continuing the next iteration. Notice that only one per- turbation scheme (one sampling oracle) is used in each iteration of Algorithm the computational complexity is basically the same as that of an algorithm which always uses a fixed sampling oracle (except the overhead for possibly updating the mixture weight p).
4

---

in which each element e(m²) represents the loss in iteration if the algorithm chooses to sample the Under review as a conference paper at ICLR 2020
Algorithm 5 A mixture of evolution strategies.
1: Require: M sampling oracles with one oracle being Algorithm 3
2: Require: hyper-parameters a, K, and 7/..
3: Init: wog E RR and vector p Am (Am stands for the M-dimensional simplex). do
4: for f = 0
5: Select an index my E [M]] with each m E [M] following the categorical distribution m ~ Pm.
6: Sample K perturbed vectors vf (0, 2, for each [K].
7: Construct pecudo-gradient g: Ka > (f(w: ovt) f(w:)) vi.
8: Update parameter W+++1 w, ThGh-
9: Update E <- SAMPLINGORACLE m..
10: end for
Algorithm 6 EXP3.P algorithm (Auer et al. (2002)).
1: Require:
1/erp3, M.
2: Init: A vector p A (AM stands for the M r-dimensional simplex).
3: for t = 0 to 1 do
4: Select an index m, E [M] with each m E [M] following the categorical distribution m ~ Pm-
5: Observe the loss e(ml) for picking my-
6: Compute the estimated loss for each Zm)) (m))
(ys =m
and update estimated cumulative
Pm
loss L,")) Σ.
(tm) 7(m)
expl Mespp (mn)
7: Update the weight of each component Pmu (1 7)
2mm expl nespa m1) 78
8:
end for
Natural questions regarding to the algorithm (1) which oracle should be called for sampling the perturbed vectors of in each iteration, and (2) how to update over time. Intuitively, one should add more weight to the perturbation scheme that works well and decrease the weight of other perturbation schemes. A concern is that if one chooses a perturbation scheme for the update in round, then one would not know the outcomes (i.e., the progress of optimization) of choosing other schemes in that round. Therefore, we propose to use EXP3.P algorithm in Auer et al. (2002) (see Algorithm 6) for adaptively selecting a perturbation scheme (i.e., step 5 of Algorithm S and updating the mixture weight p accordingly. To use EXP3. algorithm, we define the loss of choosing
m. [M] as el f(w:-1) ))- f(w:) LLLG, where L and G are constants defined in the later subsection. One can see that it is small when the function value at the next update W;+1 due to choosing my smaller than f(w;) (which suggests progress). On the other hand, the loss is large when choosing m, does not lead to decrease of the function value. As the next update W
(m74) depends on the choice of the sampling oracle my, in the following we also denote w explicitly state w,-13 i dependency on the selected sampling oracle m4. One can view that EXP3. P runs synchronously with Algorithm in the way that step of EXP3.P implements step of Algorithm and that step 5 and the subsequent steps of EXP3.P are conducted after step 8 of Algorithm 5 1S finished (so that EXP3.P can get p(mme) for updating its mixture weight p).
4.1 INTUITION IN THE DESIGN OF THE PROPOSED ALGORITHM
In this section, we explain the idea behind the design of the proposed algorithm. Let us begin by introducing some notations. We denote the M dimensional loss vector E, (e(2)) (2) ..... e(
perturbed vectors from the oracle So ((,)) stands for the loss of EXP3.P for choosing m,, We will make the assumptions that the function f(-) is non-negative, L-Lipschitz convex and the pseudo gradient ge satisfies [[9,1] I G, Vt for constant G.
Our proposed method requires a distribution the mixture to be an isotropic Gaussian distribution. So in the following, w.l.o.g. assume that m refers to the corresponding oracle. The following a convergence guarantee regarding to the algorithm that always samples the perturbed vectors from the distribution.
5

---

Under review as a conference paper at ICLR 2020
Theorem 1. (Theorem 6 of Nesterov & Spokoiny (2017)) Algorithm 2Ld-7Z K 1, and T
1 guarantees E[f(wrr)
f E when T 46d+-4) arg angminlf(ww) w E (wo, W2..... WT},, R being the bound of wo w S R, and w represents one of the optimal solutions.
[d+ (() where uT :=
Now let us replicate the theoretical statement of EXP3.P.
Theorem 2. (Theorem 3.3 in Sebastien Bubeck 20022:see also Auer et al. (2022) Assume that each element of the loss vector & is [., If the parameters of EXP3.P are chosen so that log M8-1)
then with probability at least log and y 1.05 M Texp3 0.95 1 Regred (m) = Σt mmm))
=
TM
V
TM
T
Σt Am)) I c/TM log(Mō-1) for any fixed m [M],
where the constant e is independent from T, M,
Notice that the theorem guarantees a strong result; the regret bound holds for any fixed benchmark
m E [M.]. To use the theorem, let us verify the non-negativeness of the 4. By the Lipschitz
assumption of the algorithm, the loss in any round is guaranteed to be in the range of [o, c'] with
ux + w LG 2 0, where the first inequality is by the I. T-Lipschitzeess of the function f(-) and the second one is by
= 21, L.G This because e(m := f (=r ( I. -I. (m..)
the update rule and the assumption that Ir satisfies || S G. Similarly, one can also show that l S 2n, LG. So one can apply the theoretical guarantee of EXP3.P.
Let us denote the best sampling oracle as m² E [M], which the best choice commits to a fixed perturbation scheme during optimization. That is, m² achieves the smallest optimality gap, f(w,, (m )) min fw). after sufficiently large 2 T iterations, among the fixed perturbation schemes. Let us also denote Ti 2 ' as the number of iterations for the algorithm which always chooses m (the isotropic Gaussian) to achieve the optimal gap being less than e. Now observe
Regret
that the average regret, T approaches 0 as the number of iterations T + co. So it implies that after sufficient number of iterations, say To, the majority of the choice should converge to the optimal m. with a high probability. By conducting the proposed algorithm with number of iterations max To) with some c, 2 1, it will make the proposed algorithm eventually behaves as convergent algorithm which uses fixed sampling oracle. Therefore, one might show that the proposed algorithm converges with a high probability.
4.2 TWO AUGMENTATIONS
In this section, propose two augmentations of the proposed method. The first augmentation is about changing the definition of the loss e(m))) We now allow the loss to be negative and consider defining g(().)
f(mr:) instead. The change leads to more aggressive update of the
mixture weight. Specifically, if the function value the next update w w((m)) smaller than f(w;), then e(m))) is negative (assume that f(() is non-negative) and consequently the weight Pm, is much more likely to increase or increases more using the new loss.
For the other augmentation, it is due to observation that the variance of the loss e ((m)) can be large, since the algorithm only uses K samples to estimate the pseudo gradient f. (-) (recall that exactly computing (-) involves expectation). As result, it might be the case that the selected sampling oracle m, is actually the right choice for decreasing the function value if (.((.) can
be computed exactly, but somehow the realization of e(me) is large due the high variance and consequently the weight of the oracle Pm, is severely penalized instead. To deal with this issue, consider only calling EXP3.P algorithm for selecting sampling oracle every 7 iterations. This means that sampling oracle is chosen for a consecutive т iterations before the possible switch.
Combining the first augmentation, we define the loss p(ma- .) p!me v) [(w (mny ( [-((w.rr) for (t mod 7) = 0. Algorithm (MIXTURE) in Appendix shows the proposed algorithm equipped with the two augmentations.
[w,),)

---

Under review as a conference paper at ICLR 2020
standard Adam-style Hessian
objective valuve
objective value
Adam-style Hessian
objective value
Adam-style Hessian
mixture
mixture
mixture
iteration
iberattion
iteaaioo
(a) hcart_scale.
(b) german www.ersscllee....
(c) a9a.
weighh each componentt
standard Adam-style Hessian
weiggtt each component
standard
standard Adam-style Hessian
Adam-style Hessian
6359
5329
63
0393
0473
6459
6425
20
12e
22
159
6483
25
159
iteration
iteration
iteration
(d) scart_scalc.
(c) german german.numer.ccm ncaer.
(f) a9a.
Figure I: Convex optimization min f(w) = min 1
Ei= max (0, ye(w xz)))
EXPERIMENTS
We compare our algorithm (MIXTURE) with two baselines: (1) Algorithm 2 with line 5 implemented by ((ooriimm((TTNDARD)) and (2) Algorithm with line 5 implemented by Algorithm[4(ADa STYLE HESSIAN), The mixture of our algorithm consists of two Gaussian distributions which are updated by Algorithm 3 and Algorithm respectively. So if always chooses specific oracle, then it would be equivalent to one of the two baselines.
Convex optimization: We consider empirical risk minimization with squared of hinge loss f(w) = Σ.= max (0, ye(w xz))) where each (Ii; yy) a feature/label pair. compare the algorithms on heart_scale, german wawtmnnummerseeeee scale, and a9a datasets which are all with binary labels y; [11]. All the algorithms only access to the oracle of function value evaluations. We use the same set of hyper-parameters for different datasets and repeated runs in the experiments. They are
(Same for all the algorithms) step size // 0.01, number of perturbed vectors K 4, and perturbation parameter a 0.001.
(ADAM-STYLE HESSIAN) mixing parameter = 0.9 and = 1.0.
(Algorithm 7 duration 5, step size 'eexp3 0.1, 0. and 0.
For each dataset, repeat the experiment 5 times and report the average and the standard deviation. Figure shous
shows the results. The top row on Figure plots the objective value versus iteration while the bottom plots the weight of each component in the mixture throughout iterations. We see that our algorithm MIXTURE is competitive to any of its mixture components. On heart_scale dataset, ADAM-STYLE HESSIAN makes a larger improvement in the early stage, but it suffers from fluctu- ation when the update close to an optimum, while the proposed MIXTURE is stable and converges to optimum. On german.nume numer scale, MIXTURE and ADAM-STYLL HESSIAN decreases func- tion values more than STANDARD does in the first few iterations, but have some fluctuations of the function values later. Yet, interesting observation that the weight of component STANDARD in
All are available online datasets/
csi edu. tttphttw///lll// in/1 ibsvttools

---

Under review as a conference paper at ICLR 2020
standard Adam-style Hessian
0.2
3
Adam-style Hessian
Adam-style Hessian
mixture
mixture
mixture
8:34
0.34
002
0.99
Iteration
lberation
Iteration
(a) hcart_scale.
(b) german numeerscall...
(c) a9a.
weight of each component
weight each coingooent
weight of each componentt
standard Adam-style Hessian
standard
standard
1.14
Adam-style Hessian
Adam-style Hessian
5.2
0.22
637
0:30
2:39
3.45
teeration
iteration
Iteration
(d) scalt.scale.
(c) german.numer.seo
(f) a9a.
Figure 2: Non-convex optimization minw f(w) == min EE= ii=1 1+exp(v.u
MIXTURE increases in the later iterations, which suggests that MIXTURE might rely on the oracle STANDARD reach an e-optimal point in this case, as solely using ADAM-STYLE HESSIAN may not be guaranteed the convergence. The observation also suggests that the proposed algorithm can adaptively choose a sampling oracle in effective way.
Non-convex optimization: We also consider a non-convex optimization problem with sigmoid loss function fww) := Σ T 2,)" which was also considered in Daneshmand et al. (2018). We use the same set datasets as the convex optimization experiments but we relabel those data with y/ 1 yı = (namely y/ (0, 1} here). The same hyper-parameter values used, this part of the experiments. Figure 2 shows the
except that we set = 1 for all the algorithms results. We that always sampling from the inverse of ADAM-STYLE HESSIAN performs the best. On the other hand, MIXTURE learns a larger weight of ADAM-STYLE HESSIAN (compared to that of the sampling oracle STANDARD) the first few iterations, which implies that identifies the component that works best in the early stage of optimization and consequently converges faster than STANDARD.
CONCLUSION
In this work, we propose sampling from mixture of distributions for zeroth order optimization. The propose method is modular and is complementary to existing works. It allows any proposals of sampling oracle and is an easy-to-use "meta" algorithm that provides reliable way to combine different perturbation schemes and different heuristics. We believe that the proposed method helps in the applications of hyper-parameter search, reinforcement learning, or black-box adversarial at- tacks where zeroth order optimization has been used as building block as sub-module of the algorithms. An interesting future work is designing a life-long zeroth order optimization algorithm. Consider the setting that series of similar optimization problems needed to be solved by one over time. Is possible to extend the idea of sampling from a mixture to the life-long optimization setup by assuming that the best mixture weight p for each optimization problem similar?
8

---

Under review as a conference paper at ICLR 2020
REFERENCES
Alckh Agarwal, Ofer Dekel, and Lin Xiao. Optimal algorithms for online convex optimization with multi-point bandit feedback. COLT, 2010.
Alckh Agarwal, Dean P. Foster, Daniel Hsu, Sham M. Kakade, and Alexander Rakhlin. Stochastic convex optimization with bandit feedback. NIPS, 2011.
Peter Auer, Nicolo Cesa-Bianchi, Yoav Freund, and Robert E Schapire. The nonstochastic multi- armed bandit problem. SIAM Journal Computing, 2002.
Krishnakumar Balasubramanian and Saeed Ghadimi. Zeroth-order nonconvex stochastic optimiza- tion: Handling constraints, high-dimensionality and saddle-points. NewrIPS, 2018.
James Bergstra, R. Bardenet, Yoshua Bengio, and Balazs Kegl. Algorithms for haram-er optimization. NIPS, 2011.
Pin-Yu Chen, Huan Zhang, Yash Sharma, Jinfeng Yi, and Cho-Jui Hsich. Zoo: Zeroth order op- timization based black-box attacks deep neural networks without training substitute models. Proceedings of the 10th ACM Workshop on Artificial Intelligence and Security, 2017.
Xiangyi Chen, Sijia Liu, Kaidi Xu, Xingguo Li, Xue Lin, Mingyi Hong, and David Cox. Zo- adamm::: Zeroth-order adaptive momentum method for black-box optimization. NuerIPS, 2019.
Krzysztof Choromanski, Mark Rowland, Vikas Sindhwani, Richard E. Turner, and Adrian Weller. Structured evolution with compact architectures for scalable policy optimization. ICML, 2018.
Krzysztof Choromanski, Aldo Pacchiano, Jack Parker-Holder, Yunhao Tang, and Vikas Sindhwani. From complexity simplicity: Adaptive es-active subspaces for blackbox optimization. NeurIPS, 2019a.
Krzysztof Choromanski, Mark Rowland, Wenyu Chen, and Adrian Weller. Unifying orthogonal monte carlo methods. ICML., 2019b.
Hadi Daneshmand, Jonas Kohler, Aurelien Lucchi, and Thomas Hofmann. Escaping saddles with stochastic gradients. ICMI,, 2018
John C. Duchi, Peter L. Bartlett, and Martin J. Wainwright. Randomized smoothing for stochastic optimization. SIAM Journal Optimization (SIOPT), 2012.
John C. Duchi, Michael I. Jordan, Martin J. Wainwright, and Andre Wibisono. Optimal rates for zero-order convex optimization: the power of two function evaluations. IEEE Transactions Information Theory, 2015.
Abraham D. Flaxman, Adam Tauman Kalai, and H. Brendan McMahan. Online convex optimization in the bandit setting: gradient descent without a gradient. SODA, 2005.
Saeed Ghadimi and Guanghui Lan. Stochastic first-and zeroth-order methods for nonconvex stochas- tic programming. SIAM Journal Optimization (SIOPT), 2013.
Tobias Glasmachers, Tom Schaul, Sun Yi, Daan Wierstra, and Jurgen Schmidhuber. Exponential natural evolution strategies. Annual conference Genetic and evolutionary computation, 2010.
Nikolaus Hansen and Andreas Ostermeier. Completely derandomized self-adaptation in evolution strategies. Evolutionary computation, 2001.
Andrew Ilyas, Logan Engstrom, Anish Athalye, and Jessy Lin. Black-box adversarial attacks with limited queries and information. ICML, 2018.
Kevin G. Jamieson, Robert D. Nowak. and Benjamin Recht. Query complexity of derivative-free optimization. NIPS, 2012.
Kaiyi Ji, Zhe Wang. Yi Zhou, and Yingbin Liang. Improved zeroth- order variance reduced algo- rithms and analysis for nonconvex optimization. ICMI., 2019.

---

Under review as a conference paper at ICLR 2020
Diederik P. Kingma and Jimmy Ba. Adam: A method for stochastic optimization. ICLR, 2015.
Patrick Koch, Oleg Golovidov, Steven Gardner, Brett Wujek, Joshua Griffin, and Yan Xu. Autotune: A derivative-free optimization framework for hyperparameter tuning. KDD, 2018.
Xiangru Lian, Huan Zhang, Cho-Jui Hsieh, Yijun Huang, and Ji Liu. A comprehensive linear speedup analysis for asynchronous stochastic parallel optimization from zeroth-order to first- order. NIPS, 2016.
Sijia Liu, Jie Chen, Pin-Yu Chen, and Alfred O. Hero. Zeroth-order online alternating direction method multipliers: Convergence analysis and applications. AISTAT, 2018a.
Sijia Liu, Bhavya Kailkhura, Pu Chen, Paishun Ting, Shiyu Chang, and Lisa Amini Zeroth- order stochastic variance reduction for nonconvex optimization. NeurIPS, 2018b.
Niru Maheswaranathan, Luke Metz, George Tucker, Dami Choi, and Jaseha Sohl-Dickstein. Guided evolutionary strategies: escaping the curse of dimensionality in random search. ICML, 2019.
Horia Mania, Aurelia Guy, and Benjamin Recht. Simple random search of static linear policies is competitive for reinforcement learning. NeurlPS, 2018.
Arkadi Nemirovski and D. Yudin. Problem complexity and method efficiency in optimization. Wiley- Interscience, 1983.
Yurii Nesterov and Vladimir Spokoiny. Random gradient- free minimization of convex functions. Foundations of Computational Mathematics, 2017.
Nicolas Papernot, Patrick McDaniel, Ian Goodfellow, Somesh Jha, Z. Berkay Celik, and Ananthram Swami. Practical black-box attacks against machine learning. ACM on Asia Conference on Computer and Communications Security, 2017.
Ingo Rechenberg. Evolution strategy: Natures way of optimization. Optimization: Methods and Applications, Possibilities and Limitations, Springer, 1989.
Mark Rowland, Krzysztof M Choromanski, François Chalus, Aldo Pacchiano, Tamas Sarlos, Richard E Turner, and Adrian Weller. Geometrically coupled monte carlo sampling. NeurIPS, 2018.
Tim Salimans, Jonathan Ho, Xi Chen, Szymon Sidor, and Ilya Sutskever. Evolution strategies as scalable alternative reinforcement learning. a7Xiv:1703.03864, 2017.
Nicolo
Sebastien Bubeck. Regret analysis of stochastic and nonstochastic multi-armed bandit problems. Foundations and Trends in Machine Learning, 2012.
Frank Sehnke, Christian Osendorfer, Thomas Ruckstie, Alex Graves, Jan Peters, and Jurgen Schmid- huber. Purameter-cxploring policy gradients. Neural Networks, 2010.
Ohad Shamir. On the complexity of bandit and derivative-free stochastic convex optimization. COLT, 2013.
Ohad Shamir. An optimal algorithm for bandit and zero-order convex optimization with two-point feedback. JMLR, 2017.
James Spall. Introduction to stochastic search and optimization: Estimation, simulation, and control. Wiley, 2003.
Anirudh Vemula, Wen Sun, and J. Andrew Bagnell. Contrasting exploration parameter and action space: A zeroth order optimization perspective. AISTATS, 2019.
Yining Wang, Simon Du, Sivaraman Balakrishnan, and Aarti Singh. Stochastic zeroth-order opti- mization in high dimensions. AISTAT, 2018
Daan Wierstra, Tom Schaul, Tobias Glasmachers, Yi Sun, Jan Peters, and Jurgen Schmidhuber. Natural evolution strategies. JMLR, 2014.
Haishan Ye, Zhichao Huang. Cong Fang, Chris Junchi Li, and Tong Zhang. Hessian- aware zeroth- order optimization for black-box adversarial attack. arXiv: 1377, 2019.
10

---

Under review as a conference paper at ICLR 2020
A AUGMENTED MIXTURE OF EVOLUTION STRATEGIES.
Algorithm MIXTURE
1: Require: M sampling oracles with one oracle heing Algorithm 3
2: Require: hyper-parameters a, K, 7) Mexpa, V; y and
3: Init: wo E _R . 177, M ..... M m 1.
4: for f = to 7 do
5: if mod
0 then
6: Select index m, E [M] with each m E [M] Pm-
7:
> then
(
f(w, (my +) f(
8:
each as ((m) ml Jon +2
9:
Compute the estimated
and update estimated
Pm
cumulative loss L!"") == E.= p(m)
10:
Update the weight of each component Pm (1 (1) IM expl Neayd (mm) 38
exp(
- d
11:
end
12:
end if
Sample K perturbed vectors v/ ~ (0, ) for each E [K].
15:
Construct pseudo-gradient gi: ΣK (f(w, out) f(wi))
Update parameter W141 wi 1I9t.
17:
Update 1 +- SAMPLINGORACLE m.
18:
end for


Reviews:
[{"review_id": "SyggtDwptr", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 1, "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 is motivated to improve the performance of zeroth order stochastic search by incorporating a gaussian mixture as the candidate solution sampler. It is (almost) not possible to improve the state of the art zeroth order optimizer in all aspects, hence I expect a description in which situation the authors try to improve the performance by the proposed technique. However, it is not mentioned in the paper. \n\nThe experiments are far away from convincing. The authors pick only two very simple functions, convex one and non-convex but very simple one. The experimental results are compared only with the two baselines of the proposed algorithm. I have to say that the experimental design of this paper must be reconsidered to conclude and derive the goodness of the proposed algorithm.\n\nFirst of all, the effect of introducing non-identity covariance matrix is usually to tackle the ill-conditioning of the objective function, as is well discussed in papers addressing the covariance matrix adaptation in evolution strategies (CMA-ES) by Hansen and his co-authors. However, the objective function doesn't seem to be so. Therefore, this effect can not be tested from this experiments. It is not at all clear what the authors want to claim from these experiments. \n\nIf the non-isotropic part is not important but the scaling factor of the covariance matrix matters (for the step-size adaptation effect), one must compare algorithms using isotropic covariance matrix but with step-size adaptation mechanisms. For example, random pursuit (Stich, SIOPT 2013) is a hill-climbing algorithm with randomly sampled direction with a line search. It also has a convergence results on convex functions. (1+1)-evolution strategy is another random direction hill-climbing algorithm with a step-size control mechanism. (Morinaga and Akimoto, FOGA 2019) has shown its linear convergence of this algorithm on strongly convex functions and beyond. These algorithms works reasonably well without tuning the hyper-parameters. In the proposed approach, there are several hyper-parameters that needs to be tuned to guarantee the convergence and perform reasonably. What is then the goodness of the proposed algorithm compared with above mentioned algorithms?\n\nTheorems provided in the paper doesn't show the goodness of the proposed algorithm, but it tells that the idea of having a mixture model is not a bad idea. I do not see from these arguments the reason why a mixture model leads to a better performance than the baseline. Nonetheless, the theoretical analysis of this work is not rigorous, and if I understand correctly, the convergence (and its rate) of the algorithm is not formally proved. ", "extra_scores": {"experience_assessment": "I have published in this field for several years.", "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": {}}, {"review_id": "H1gVIxe6KS", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 1, "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 proposes to change the sampling scheme of evolutionary strategies to sample from a mixture of distributions (instead of the standard way of sampling from one Gaussian).\nAlthough this seems to provide slightly better performance, the contribution is incremental and more importantly the paper lacks clarity, especially regarding the theory part. The experiments are also not on par with what’s typically expected in the literature. Overall, this paper is not ready for acceptance at a venue such as ICLR.\n\nEXP3.P algorithm\nThis is one of the key components of the algorithm presented by the authors but it is not properly explained in the paper. In fact, the algorithm implemented by the authors is very unclear to me. Below I quote the description given by the authors:\n“One can view that EXP3.P runs synchronously with Algorithm 5 in the way that step 4 of EXP3.P implements step 5 of Algorithm 5 and that step 5 and the subsequent steps of EXP3.P are conducted after step 8 of Algorithm 5 is finished“\nThis is a very poor description of the algorithm. The authors should give a clear pseudo-code to explain the algorithm.\n\nTheoretical guarantees\n1) Again, the paper is very unclear on what algorithm is being implemented. The authors claim they can directly use the guarantees provided by Bubeck et al but this is unclear to me given that the algorithm is never fully stated. This needs to be clarified.\n2) The authors claim asymptotic convergence, specifically they claim “Therefore, one might show that the proposed algorithm converges with a high probability.“. This proof should be provided in the paper, not left as an exercise to the reader...\n3) Does Theorem 2 (Theorem 3.3 from Bubeck) require convexity of the function? Can you comment on guarantees for non-convex functions?\n\nPrior work\nThe authors do not give a clear description of prior work. There is a large literature on proving convergence guarantees under weaker assumptions than discussed in the paper, see e.g.\nY. Diouane, S. Gratton, and L. N. Vicente. Globally convergent evolution strategies. Math.\nProgram., 152:467–490, 2015.\nY. Diouane, S. Gratton, and L. N. Vicente. Globally convergent evolution strategies for\nconstrained optimization. Comput. Optim. Appl., 62:323–346, 2015.\nVincente. Worst case complexity of direct search\n\nExperiments\nThis is also a weak part of the paper.\n1) The authors only run experiments on very small datasets. Regarding the non-convex task, it would be much more interesting to consider a reinforcement learning task where evolutionary methods typically perform well.\n2) You should include stronger baselines too, e.g. https://arxiv.org/abs/1806.10230.\n3) An interesting question to look at would be to analyze the behavior of the algorithm as a function of the number of mixture components. Also, what is the computational increase in terms of the number of components? Consider giving plots in terms of computation time.\n", "extra_scores": {"experience_assessment": "I have read many papers in this area.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper thoroughly.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I carefully checked the derivations and theory."}, "extra_text": {}}, {"review_id": "BylC0IXsYr", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 3, "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 submission is proposing an adaptive derivative-free optimization method. In this method, the sampling covariances are adapted between different covariance adaptation heuristics. The main intuition is seeing each algorithm as an arm in multi-armed bandit (MAB) setting. Moreover, authors use EXP3.P as an online learning mechanism.\n\nThe idea and intuition is definitely interesting. Although the idea of adapting DFO using MAB has been already explored, using MAB for choosing covariance adaptation scheme is definitely novel and interesting. However, the submission has various issues which need to be fixed.\n\nThe claim that the existing adaptation mechanisms have no guarantees is not correct. (Ye et al, 2019) provides convergence guarantees. Moreover, most of the existing adaptive optimization method convergence guarantees can be extended to DFO in a straightforward manner.\n\nThe main claim (\"we can show that our method converges with a high probability when the underlying function is convex\") is not completely substantiated. The high-probability no-regret guarantee (Theorem 2) the authors state is using the iterates (w_t) as an input. It shows that given adversarially chosen iterates (w_t), the Exp3.p has no regret. However, this says nothing about the convergence of these iterates (w_1,...,w_t). I think it is not hard to prove the main claim; however, the reasoning provided in the paper is incomplete. More importantly, both Thm.1 and Thm.2 are specifying the sample complexity of the methods. Whereas, authors only give rather asymptotic argument. Authors should 1) rigorously prove the convergence guarantee as an additional theorem. And, 2) give sample complexity of the proposed method.\n\nAnother issue is the empirical validation. It is clear from the results that the adam-style Hessian method outperforms the proposed method. This is counter-intuitive and no explanation (theoretical or empirical) is given for this discrepancy. \n\nAs a minor question: Why do you only update one method after each gradient update in Line 9 of Alg5? It is an unbiased estimate of the gradient, hence all sampling oracles can update itself using this estimate?", "extra_scores": {"experience_assessment": "I have published one or two papers in this area.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I carefully checked the derivations and theory.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper thoroughly."}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper proposes an adaptive sampling mechanism for zeroth order optimization that samples perturbed points from a mixture distribution with asymptotic convergence guarantees. The reviewers raised issues regarding the clarity of presentation, potential problems with the proofs, and simplicity of the experimental setup. The authors did not provide a response. Overall, the reviewers agree that the quality of the paper is not sufficient for publishing, and therefore I recommend rejection.
Decision: Reject