DiBB: Distributing Black-Box Optimization
Authors: Giuseppe Cuccu
Luca Sven Rolshoven
Fabien Vorpe
Philippe Cudre-Mauroux
Tobias Glasmachers
Venue: ICLR 2022 Submitted (2022)
Keywords: Black Box Optimization
Distributed Computing
Evolutionary Computation

Abstract: We present a novel framework for Distributing Black-Box Optimization (DiBB). DiBB can encapsulate any Black Box Optimization (BBO) method, making it of particular interest for scaling and distributing modern Evolution Strategies (ES), such as CMA-ES and its variants, which maintain a sampling covariance matrix throughout the run. Due to high algorithmic complexity however, such methods are unsuitable alone to address high-dimensional problems, e.g. for sophisticated Reinforcement Learning (RL) control. This limits the applicable methods to simpler ES, which trade off faster updates for lowered sample efficiency. DiBB overcomes this limitation by means of problem decomposition, leveraging expert knowledge in the problem structure such as a known topology for a neural network controller. This allows to distribute the workload across an arbitrary number of nodes in a cluster, while maintaining the feasibility of second order (covariance) learning on high-dimensional problems. The computational complexity per node is bounded by the (arbitrary) size of blocks of variables, which is independent of the problem size.

Under review as a conference paper at ICLR 2022
DIBB: DISTRIBUTING BLACK-BOX OPTIMIZATION
Anonymous authors
Paper under double-blind review
ABSTRACT
We present novel framework for Distributing Black-Box Optimization (DiBB). DiBB can encapsulate any Black Box Optimization (BBO) method, making it of particular interest for scaling and distributing modern Evolution Strategies (ES), such as CMA-ES and its variants, which maintain a sampling covariance matrix throughout the run. Due to high algorithmic complexity however, such methods are unsuitable alone to address high-dimensional problems, e.g. for sophisticated Reinforcement Learning (RL) control. This limits the applicable methods to simpler ES, which trade off faster updates for lowered sample efficiency. DiBB overcomes this limitation by means of problem decomposition, leveraging expert knowledge in the problem structure such known topology for neural network controller. This allows to distribute the workload across an arbitrary number of nodes in a cluster, while maintaining the feasibility of second order (covariance) learning on high-dimensional problems. The computational complexity per node is bounded by the (arbitrary) size of blocks of variables, which independent of the problem size.
INTRODUCTION
Black Box Optimization (BBO) can be applied, by definition, any problem independent of the specific application (Audet & Hare 2017). In principle, this provides a method that is applicable to problems yet unsolved by the current state of the art. The most obvious catch lies in their compu- tational requirements, which usually takes one of two forms: (i) simple black-box -bxx solvers suffers from high sample complexity (i.... they are data hungry), in exchange for smaller computational requirements (both in memory and CPU time). On the other hand, (ii) sophisticated solvers such as modern Evolution Strategies (ES: Hansen Ostermeier 2001; Wierstra et al. (0044) have a high internal computational cost per sample, in exchange for wide set of properties (see Section 2 that
make for significantly improved sample efficiency.
In the first case (simpler ES), the requirement for more samples can be mitigated-to some extent- through the embarrassingly parallel evaluation of a large population of candidate solutions. This approach however has its own limitations, traversing more complex fitness landscape often requires a disproportionate growth in the number of required samples as the dimensionality rises. In the second case however (complex ES), algorithms relying covariance matrix adaptation (CMA; e.g. CMA-ES by Hansen 1996) have a quadratic complexity in the number of variables for processing sample. This strictly limits their application (within a sensible time frame) problems within the tens of thousands variables. This limit has restricted the applicability of these methods to rather simple scenarios and applications so far. As a result, most successful applications of ES to high-dimensional problems (e.g. training larger neural networks) rely on simpler ES, such as the type (i) described above.
Most of the per-sample complexity of type (ii) algorithms can be traced to the algorithm maintaining and updating the covariance information among the set of variables, which helps the sample efficiency of these algorithms (as in convergence speed) at the cost of longer run times (as in wall-clock speed), eventually becoming intractable as the number of variables grows. Several algorithms (Ros & Hansen 2008 Schaul et al., 2011) thereby implement
assumption of separability between the variables, relinquishing covariance information altogether for greatly enhanced wall-clock speed per sample. Unsurprisingly. this comes at cost in terms of convergence speed: these algorithms can require several orders of magnitude more samples to find comparable solutions, depending on the problem structure (Hansen & Ostermeier 2001

---

Under review as a conference paper at ICLR 2022
Worker node A
Worker mode 6
node
EGC Da
CQO IESRUnC
SINEES Pou
CHALLATOOR
communattor ana
PARk Wilter
Cherue ASCDPT
Conkery PT
Figure I: Architecture of the DiBB framework. This example shows an instantiation on a cluster with 3 nodes, one head and two workers.
The approach taken in this paper takes instead into account the fact that the correlation among variables is not uniform for most complex problems. Rather, certain groups of variables will display higher correlation between each other, with variables having lower correlation belonging instead into different groups. This induces two different assumptions on the variable set: groups having high intra-corred corra-correlation support an assumption of partial correlation, while the low inter-group correlation displays the parallel argument of partial separability. We can represent this using block-diagonal covariance matrix, which at the same time maintains full-covariance information within the variables belonging to one such group, and discarding the less useful (and often negligible) inter- -nter-group correlation altogether (Cuccu & Gomez, 2012). Such an approach allows leveraging covariance information where it is most efficient, while at the same time significantly reducing the memory footprint of the algorithm (based on the number and size of the groups), and even offering additional opportunities for parallelization and distributed computing. We will use the term blocks to refer to the groups of variable with high intra-correlation in the rest of the paper.
BBO algorithms are designed to ignore blocks, since they need to work in any unknowable (black- be useful to
box) environment. Even in a gray-box setting, black-box algorithm engineering ensure that no illegitimate assumptions are made in their design. On the other hand, we aim to profit from the added information. Real applications often have a gray-box character, exposing certain level of expert knowledge about the correlation between variables. Let us take for example the common application of Neuroevolution (Stanley et al., 2019), where evolutionary algorithms (such as ES) are applied to learn the weights of neural network. We know from the network's 's equation that the weights of the connections entering the same neuron (as opposed to entering different neurons) are by necessity highly correlated, as they are composed in a linear fashion inside the neuron prior to activation. The same reasoning can be made for the weights of connections entering neurons belonging to the same layer, versus neurons in different layers, because outputs of layer are linearly combined in the next layer. This principle remains true as the network expands: in complex applications such those requiring deep networks, the correlation between weights of connections in the early versus late layers will be by design much more limited than in the neuron or layer examples above
Based on the above insights, this paper proposes a new framework for Distributed Black Box optimization, named DiBB, see Figure [ We leverage the assumption of partial correlation by partitioning the variables set into highly intra-correlated blocks; then, switching the assumption to partial separability, we search each block with a different instance of the reference BBO algorithm, independently. This makes DiBB particularly suited for neuroevolution applications requiring larger/deep networks. In Section we provide rigorous theoretical arguments for the sample efficiency of this approach.
From a practical perspective, this allows to search blocks asynchronously and even to distribute each BBO instance on different nodes in cluster. Varying the partition of the variables enables the user to arbitrarily trade-off between wall-clock speed (smaller blocks) and sample efficiency (larger blocks), while distributing the BBO instances decouples the complexity from the number of variables, as long
'The fundamental assumption of partial separability across network layers however does not seem to be very well studied in the literature, despite considerable body of work on neural network loss landscapes (Fort & Jastrzebski 2019 (Soltanolkotaii et al. 2018). This can be partially tracked to the limited availability of algorithms making use of partial correlation information.
2

---

Under review as a conference paper at ICLR 2022
enough machines available the BBO instances. A major challenge comes with solution evaluation, as the variables constituting a sample are practically scattered across a network. This is addressed in Section 3] by establishing rather sparse communication scheme.
is important to notice at this point that no assumption or claim has yet been made on the underlying BBO algorithm of choice nor will be made. While this paper explores the applicability of DiBB in the context of modern, sophisticated ESs, DiBB can be applied to any BBO algorithm with minimal interfaces.
We analyze the performance of our framework on the classic COCO benchmark, both on the BBOB and BBOB large-scale suites, using the industry-standard CMA-ES as reference, and as a block- level optimizer within DiBB. The sample complexity of our approach typically (and as expected) sits in between the full-covariance and the diagonal-covarian exceptions where maintaining extra covariance information is actually deceptivemmisladding due to separability. Notably, on parallel hardward, DiBB considerably faster in terms of wall clock time. To demonstrate the scalability of our algorithms, we present results on training 20-layer neural network using 20 blocks on 20 machines, the largest neural network trained with neuroevolution to date, to the best of our knowledge.
versions of CMA-ES, with few notable
1.1 CONTRIBUTIONS
Our key contributions are as follows:
We provide a novel way of parallelizing an ES, going beyond the parallel evaluation of candidate solutions forming population, by optimizing blocks of variables with multiple ES instances.
We exploit the block structure to add covariance matrix information at low cost where matters most, namely inside blocks of potentially highly correlated variables.
The resulting DiBB framework is particularly well-suited for neuroevolution. However, it can be applied to any BBO method.
We demonstrate that also large and deep networks can be trained efficiently with neuroevo- lution on highly parallel hardware.
2 A PRIMER ON EVOLUTION STRATEGIES
ES are direct search methods, which optimize black-box objective function f Rd + R by sampling candidate points from an adaptive Gaussian distribution. We briefly review the types of ES most relevant for our discussion. The classic variant is the (1+1)-ES (Rechenberg) 1973). Its central algorithmic mechanism is step size adaptation, i.e., its ability to actively adapt the standard deviation > 0 of its Gaussian sampling distribution (m,, o² f)) to the current needs. For about 20 years, CMA-ES (Hansen & Ostermeier 2001) is the gold standard in ES research. Many variants exist, such as Natural Evolution Strategies (NES; Wierstra al. 2014). Its most important mechanism going beyond "simple" step-size adaptive ES is covariance matrix adaptation (CMA), which means that not only the global step size a, but also the full covariance matrix C of the Gaussian N o2C) is adapted to the problem at hand.
CMA-ES is powerful optimizer; however, it not designed for sigh-dimensional applications with hundreds of thousands of variables. Its internal parameters are not tuned with such regime in mind, and learning full covariance matrix with d(d++1) 2 parameters is inherently slow, Such problems are best addressed by restricting C to a diagonal matrix (Ros & Hansen] 2008), to a diagonal plus a low-rank matrix (Loshchioov) 2014 Akimoto et al. Loshchilo 2018). or to a block- diagonal matrix (Cuccu & Gomez 2012). The number of parameters of the covariance matrix can hence be chosen rather flexibly in the range d to d(d+1)
2.1 ES FOR NEURORVOLUTION
The application ES to machine learning problems and to RL in particular has a long history (ggel 2003 [Heidrich-Meiser & Igel 2009). In 2017, the work Sf et al. (207)) sparked renewed
3

---

Under review as a conference paper at ICLR 2022
interest in ES by showcasing how to successfully exploit the embarrassing parallel nature of objective algorithms, considerably speeding-upg -up the learning process. This triggered large body of work on neuroevolution based on ES, see e.g. Plappert et al. (2017); Ha & Schmidhuher (2018); Chrabaszez et al. (2018); Stanley et al. 2019) and references therein.
function evaluations in populations-
2.2 CONVERGENCE RATES AND COMPUTATIONAL. COMPLEXITY
Due to Taylor's ' theorem, local optima of C² functions in d-dimensional space are well approximated (up O( x=1 ( by convex quadratic functions [(x:) = { )² ((x x²)) The computa- tional complexity of solving this problem with an ES to fixed target precision > is of the form Old x(f)) log [L/e),, where x(H)) denotes the condition number of the Hessian H/ (Jägersküpper
2006 Hansen et al. 2015). Hence, step-size adaptive ES achieves linear convergence with rate
()))
The linear dependency on d is optimal for comparison-base optimization (Fournier & Teytaud 2011 but the dependeney on H is sub-optimal. The advantage of maintaining covariance information is that the factor k(H) is improved to x [C*),, where C* denotes the optimal covariance matrix available to the ES. When approaching C H-1 methods maintaining full covariance achieve the optimal value k(HC*) = 1. In effect, as expected from pseudo second order method, the convergence rate is independent of H. A diagonal covariance matrix C* acts as a diagonal pre-conditioner, with varying effectiveness depending on the problem. Obviously, the block-diagonal and the low-rank cases are in-between.
The OpenAI-ES (Salimans et al. 2017 features neither step size adaptation nor covariance adaptation. Based on the NES framework of Wierstra et al. (2014), it leverages the ability of ES to estimate the natural gradient of from samples, and then applies the ADAM optimizer on top. In effect, this is roughly comparable to using diagonal C.
CMA has price in terms of algorithm internal complexity, and in addition the adaptation process slow in terms of sample complexity. The above convergence rates measure time in terms of objective function evaluations (sample complexity). When scaling up CMA to high dimensions, need to take the following concepts into consideration. Algorithm internal complexity refers to the required (amortized) number of operations needed for creating a sample and for updating the internal state-the the covariance matrix in particular. Regarding sample complexity, we distinguish between the number of samples needed to learn the covariance matrix, and the number of samples needed to solve the problem.
Learning C with up O(d²) parameters is sample-inefficient. For example, (small) network with d = 10 weights results in d(d+1) x 5 10 parameters of the covariance matrix. Learning these takes hundreds of millions of samples, each of which can be a full RL episode. This is too slow for being useful. For larger d, even the storage of the full covariance matrix C' becomes prohibitive. Furthermore, performing computations with scales at least linear with the number of its parameters, which amounts to an internal complexity of (2) for full CMA. Since network evaluation scales linearly with the number of weights d, CMA quickly becomes the computational bottleneck. Therefore, different trade-off between fast convergence and internal complexity is needed, which can be realized for example with block Bocck-diagonal and low-rank structures, and combinations thereof.
2.3 IMPLICATIONS FOR NEURAL NETWORK TRAINING
Diagonal, block-diagonal, and low-rank schemes successfully lower both internal and sample costs of CMA significantly. Therefore, they are key to the application of modern ES with CMA to RL.
In neural network training, weight spaces are often extremely high-dimensional. However, they also come with canonical structure, induced by the network topology. We can expect weights belonging to different layers (and even weights belonging to different neurons within the same layer) to be less correlated than weights within layer. Hence, a black-diagonal covariance structure with one block per layer (or per neuron) is natural choice. It should be noted that there exist approaches for identifying a problem decomposition automatically (Omidvar al. 2013), if needed.
4

---

Under review as a conference paper at ICLR 2022
If H has a block structure (f is separable), then sequentially optimizing all blocks in isolation is as fast as optimizing the full problem. This is a direct consequence of the ((d) scaling of the sample complexity discussed above, and lead to the following insight:
Solving independent sub prob-rrssemss with k = d/b variables each in parallel results in a b-fold speed-up over solving the full problem with d variables.
is understood that this comes a cost the separability assumption is violated. However, the block structure offers further benefit:
Solving b independent sub-problems with = d/b variables each with an ES featuring CMA results in ok²) sample and internal complexity for covariance learning, in contrast to (dd) for full CMA. If the number of blocks scales linearly with the problem size d, or E (1), then CMA becomes feasible for arbitrarily large problems.
These two insights offers a novel route towards highly parallel and at the same time more sample- efficient neuroevolution strategies. In addition to the embarrassingly parallel evaluation of popula- tion of candidate points, multiple blocks can be optimized parallel. Given enough cores, higher parallelism results in a b-fold speed-up. As an additional benefit, CMA can be applied within each block of variables. Provided that the problem has an (approximately) separable structure, CMA results in improved sample efficiency, yielding a further speed-up.
METHOD
The DiBB framework is originally inspired by Block-Diagonal Natural Evolution Strategies (BD- (uccuu & Gomez(2012) but extending the original design to be applicable to any BBO algorithm without restrictions, providing the same time parallel and distributed implementation with limited overhead. Here is a short summary of how to use DiBB:
1. The user defines a partition of the parameters, typically based expert knowledge of the application, e.g. for neuroevolution consider one block per (weights of connections entering a) layer or one block per neuron.
2. Launching the method on a head node spawns the run control routine plus the object store that maintains shared data. This follows typical best practices distributed processing (Dean & Ghemawat, 2008).
3. The control then launches one Block Worker (BW) for each parameter block on the avail- able machines. The BW encapsulates the actual BBO algorithm. Each BW runs fully asynchronously from the others, though contemporary. The BWs exchange information by uploading to the head node the state of their search after each update (i.e. generation in ES).
4. In our implementation, each BW can spawn a pool of Fitness Evaluators (FE) the same machine. These are used to manage limited computational resources, such as available CPUs, which becomes critical when nontrivial objective function needs access significant portion of the available resources, such as the case with external software (c.g. physics simulations of control tasks).
5. Alternatively, the user can request to evaluate trivial optimization fuucciions on the BW directly (either sequentially or with multi-threading. which is useful when the overhead of maintaining a discrete pool of evaluators would be significant.
The Block Workers communicate with the head node in each generation, while generation cycles are defined asynchronously by each BW. Consider problem with d variables 21..... Ld, and a BW optimizing b variables Ta. ... Ta 1-1, denoted as the vector x for short. The head node maintains reference solution ž E _dd, which fulfills two-fold purpose: it serves as anytime estimate of the state of the search (optimum), and it provides a unifying context to the BWs and the FEs.
Intuitively, each BW is only aware of the variables in one block, and can only generate samples for the corresponding variables. These incomplete samples need to be scored on the task to obtain the gradient for solution improvement. The problem here is that the task expects complete solution to be evaluated: in our recurring example of neuroevolution, the sample could correspond to the weights for neuron, or layer, while only full networks can be evaluated on the task.
5

---

measurable advantage or disadvantage on either approach from Under review as a conference paper at ICLR 2022
We address this issue by leveraging once again our assumption of partial separability. After hypothesis of the correlation across blocks being negligible, we can evaluate each block in isolation by inserting it in the context of the reference solution, obtained from the head node. Hypothesize for a moment that there is no correlation inter-block-we address below the validity of this statement. In this case, each layer can be scored fairly by constructing full reference network, then swapping the corresponding weights in the target layer for the block sample, and finally evaluating the resulting complete network on the task. Different independent samples from same block would receive fair evaluation in this fashion as long as they are evaluated on the same reference network. This is in fact constructed by assembling the per-block, partial reference solutions of each of the BBO instances running on each block, and is updated in the head node by each block instance after each generation.
More formally: at the start of each generation, the BW receives the current reference solution Tr. .i..... Fa from the head nodee] The block-level ES samples a population of candidate solutions y² ....... y RR. If is small, then sampling from a Gaussian with full covariance matrix ((m, C is feasible. The b-dimensions points are injected into the reference solution by constructing the d-dimensional vectors x², r'.....'* Rd according to the following rule:
v/La if sissaa a + T
x/ =
otherwise
The vectors x² ...... _d passed to the (thread or node) pool of Fimees Evaluators. Once all objective function values are computed, the ES updates its internal state, which contains its sampling mean m and optionally further parameters like step size, evolution paths, and covariance matrix. Finally, it sends the updated mean mn back to the head node, which incorporates it into its reference solution by overwriting 2 with m.
The last issue remaining is that of course we cannot expect the weights entering different neurons or layers be entirely separable; after all, they belong to the same network and they are thereby all contributing to the final output in its equation. This results in a problem of moving target, where the score of a block sample depends on the global state of the search (in the form of the current complete reference solution), which changes constantly as every BBO instance asynchronously sends an update to the global reference state. Empirically we verify that the impact on the algorithm only marginal: after all, our hypothesis is relatively much stricter than in fully-separable implementations. This further mitigated when comparing with full-covariance algorithms by the fact that the latter will still need to learn the lower covariance between lowly-correlated variables, which in turn effectively lowers the sample efficiency of the theoretically superior algorithm in most complex real-world scenario. In practice, we have this perspective.
The proposed setup directly reflects the added level of parallelism, compared to standard ES. Traditional implementations usually restrict parallelism to maintaining a pool of evaluators to speed up the evaluation of independent samples using multiple cores. In our setup, second level of parallelism is established in terms of the Block Workers, which operate independently but for sparse communication with the head node.
4 EXPERIMENTS
This section describes the setup used to empirically assess the performance of DiBB. With our experiments, we aim to address the following research questions:
QI: How well does the block-diagonal approach work, compared to diagonal and full CMA? Q2: How does DiBB scale to large number of machines and cores?
Q3: Is DiBB well-suited for neurocvolution applications?
We assess the first two questions on the standard COmparing Continuous Optimizers (COCO) Black Box Optimization Benchmark (BBOB), using both the standard and the large-scale benchmark suites. For answering the third question, we showcase neuroevolution application in the challenging OpenAl Gym 2D Walker environment.
It would suffice send T1,..., Fa 1a Fath. ... Fe the BW, but the difference is usually negligible.

---

Under review as a conference paper at ICLR 2022
Cluster setup. We tested DiBB variety of hardware solutions. The COCO-BBOB experiments were run on a cluster of 24 low-perfone ww-performaace machines, each sporting an Intel Core i7-2600 CPU @ 3.40GHz (4 cores/8 threads each), and 32 GB of RAM. As one expect, these old machines are far from state-of-the-ar performance, which leaves a significant margin of improvement for the timings presented in results.
Reference implementation. Our experiments use our implementation of DiBB written in Python and leveraging the Ray distributed computation library The code is released open source on Gud and available through Pypr for ease of adoption and extension. The cluster setup simplified by the included managing scripts. Rumning a single machine with single block and no Fitness Evaluators roughly corresponds to running the underlying BBO algorithm alone (plus overhead). Spawning multiple BWs and FEs automatically scales to the available resources. Defining set of IPs the managing script allows to easily distribute the computation.
4.1 COCO BBOB
COCO provides multiple suites covering a broad range of test cases. The experiments presented in this work are based on the BBOB and the BBOB large-scale suites.
The BBOB suite comes with 24 noise-free real- pala-memeeter single-objective benchmark functions in dimensions d E 3,5, 10, 20, 40} (Hansen et al. (009). The functions are divided into five groups: separable functions (f1-f5), moderately conditioned functions (f6-19), ill-conditioned functions (f10-f14), multi-modal functions (f15-f19), and weakly structured multi-modal functions (f20-124). We expect the performance of DiBB to vary accordingly our assumption of partial separability.
BBOB.
BBOB large-scale suite. The BBOB large-scale suite contains the same 24 same functions which are found in the BBOB suite, but scaling the available number of dimensions to E {20, 40, 80, 160, 320, 6403. This suite however introduces heuristics to decrease the computational cost of a selection of functions in a large-scale setting. We refer the interested reader to Elhara et al. (2019) for further details.
The BBOB suite provides broad range of problems representative of many use-cases in the spectrum of Black-Box Optimization. Particularly, and by design, several edge cases are present that are unlikely to be encountered in real applications but provide compelling insights on the performance and applicability of the tested algorithm. Particularly, BBOB problems are designed to be solved to high precision to test for scale invariance; therefore d is not in the thousands. Scalability of d, and the distinction between separable and non-separable problem classes, allows us to systematically evaluate the effect of DiBB's 's block structure on its performance. COCO greatly facilitates this process by providing publicly available performance data for many SOTA algorithms 6
We test the scaling of DiBB's performance the opposing perspectives sample efficiency (i.c. convergence speed) and run time (i.c. wall-clock speed). To this end, ran the following experiments:
vary the problem dimensions and block size, from
1. Constant number of blocks, increasing and block size, on the BBOB suite (bbob_ _nbb
2. Constant block size, increasing d and number of blocks the BBOB suite (bbob fbs)
3. Constant number of blocks, increasing and block size on the large-scale suite
(bbob_ls s_fnb)
4. Constant block size, increasing d and number of blocks on the large-scale suite (bbob_1s (ooob_ls_fb)
Details of the experimental setup are found in Appendix A.
"Link anonymized. a Python framework for distributed computing
LLink anonymized.
https: / htttp::/numbbo..rete httpp/////mmbb..tttbiiooo//////e wrchive/bbbhbb.b..
7

---

Under review as a conference paper at ICLR 2022
D0MA
(OM
300000
k:3t/a TeNos SwN00011
by33 Tewss/oeenssen
bxd Texiby SrMeso0)
kx02 www.e/ (inersle
Figure 2: ECDF plots of the performance of DiBB, separable and full CMA-ES in dimenion 320. From left to right: f1-f5 with Exp 1/Exp 3, Exp 2/Exp 4, then f10-f14 with Exp 1/Exp 3, Exp 2/Exp 4.
We chose to focus on the group of separable (f1-f5) and ill-conditioned functions (f10-f14). The first group contains problems that can solved easily by DiBB, while the second group extremely hard since it strongly violates the separability assumption.
Prototypical results of the COCO/BBOB experiments are found in figure 2 (full results in the ap- pendix). The ECDF plots show the fraction of reached (precision) targets over dimension dimension-normalizee normalized time on a log-scale, so "higher better".
Sample Efficiency On fully separable problems f1-15, all algorithms perform roughly the same in terms of sample complexity. In other words, covariance terms can be dropped at no cost, and blocks can be optimized independently. This confirms the theoretical predictions from Section 2 Interestingly, in some cases DiBB (slightly) outperforms full CMA-ES, since off-diagonal covariance terms can be detrimental when not needed.
For the ill-conditioned non-separable problems f10-f14, the performance of DiBB close CMA-ES with diagonal covariance matrix and far worse than full CMA-ES, since the unmodeled terms with (unrealistically high) correlations extremely close to 11 dominate performance. Yet, unsurprisingly, larger blocks result in better sample complexity. This finding confirms the theoretical prediction that the assumption of separability is crucial.
Taken together, the two results imply that DiBB applied to a problem with block structure greatly outperforms an ES with diagonal covariance matrix by being more sample-efficient within each block, while full CMA offers no further advantage. This answers question Q1.
Timings Most of the experiments were run on the oow-performance cluster described above. For 3 of the experiments however we tested the flexibility of DiBB by switching to new cluster of nodes with Intel(R) Xeon(R) CPU E5-2620 v4 @ 2. 2.10GHz processors (32 cores total) and 128 GB RAM. These were the BBOB suite with one block (thus running on a single machine), the 40d BBOB suite with 2 blocks (running on 3 machines: head and 2 for the Block Workers), and the 40d BBOB large-scale suite with one block (again single-machine run).
Number of Number dimensions of blocks
Block size
Number of Number dimensions of blocks
Block size
Duration
Duration
40
1
40
25h 133m 47s
80
16
02h 47m 53s
80
2
40
43h 26m 57s
160
16
10
04h 11m 15s
160
4
40
40h 2mm 0ls
320
16
20
07h 01m 38s
320
8
40
44h 53m 29s
640
16
12h 16m
640
16
61h 20m 1
Table 1: Timing data for experiment 3 on the BBOB large-scale suite with a fixed number of blocks (left) and experiment 4 with a fixed block size (right, 5x larger budget).
Table the runtimes of DiBB with different numbers of blocks, block sizes, and dimensions on the BBOB large-scale suite. Several effects come together: in larger dimensions, function evaluation time and communication overhead grow linearly. Due to the fixed budget multiplier used in COCO, the overall function evaluation budget also grows linearly. On the other hand, CMA's computational effort grows quadratically in the block size. We clearly observe that the runtime grows far more benign when using fixed block size, which indicates that CMA overhead indeed quickly
8

---

Under review as a conference paper at ICLR 2022
becomes the dominating term. Hence, the block size should be kept tightly under control. This answers question Q2.
4.2
PYBULLET WALKER 2D
Although this paper introduces DiBB as generie BBO framework, the original motivation behind its design is rooted in scaling neuroevolution to large network models. Therefore we present our results on com- plex reinforcement learning control task: the Walker 2D gym environment from PyBullet (Coumans Bai 2016-2021).
This task, running on the PyBullet physics engine, is about low-level control of a fairly basic 2D robot (see Figure 3) The goal of the task is to learn a gait that allows the robot to reach the farthest possible distance in limited time and without toppling. The 22 dimen- sions of the observations correspond to a broad array of sensors including positional and angular speed of the joints, height above the ground, speed along the axes (plus roll, pitch and yaw), and more. The action space is composed of 6 (normalized) torque control signals, which sent the motors in each joint.
Figure 3: The Walker 2D robot from the Walker2DBullets LenDBuleeeEEvv environ- ment in OpenAl Gym. The goal is to make the robot walk as far as possible without falling. This sophisticated control task pro- vides a significant challenge in reinforce- ment learning control, especially in its Py- Bullet implementation. We tackle using DiBB wrapping LM-MA-ES evolve neural network policy controller totaling 198 neurons and 11590 weights in direct encoding.
The policy network is ferd-forward and fully con- nected, including 2 hidden layers of sizes [128, 64), and using ReLU activation on all neurons. The output layer composed of 6 neurons with tanh activation to match the normalized range of motor commands.
The network is trained with DiBB wrapping LM-MA-ES (Loshchilov al. 2018), and reaches score of 1126 (average score over 100 rums, maximal episode length 1000) in 25 hours running cluster of 4 machines (3 of which have Intel(R) Core(TM) i7-3770 CPU @ 3.40GHz processors, the fourth one having 32 Intel(R) Xeon(R) CPU ES-2620 v4 @ 2.10GHz processors). As a comparison we used Random Weight Guessing, generating 1000 individuals, which reached a score of 42. TheTh are the first results on this benchmark using heuroevolution to the authors' knowledge, due to the limited availability of sophisticated evolutionary methods scaling to that many dimensions. This answers question Q3.
CONCLUSIONS
We present framework that wraps any Black-Box Optimization (BBO) algorithm into partially-separanl variant. The variable set is partitioned into blocks with high intra-correlation but low inter-correlation, based expert knowledge on the problem structure that is commonly available in real-world applications, Each block is searched independently by separate instance of the wrapped BBO algorithm, which allows parallelize and distribute its computation across any number of available machines. We name it DiBB for Distributing Black Box optimization.
Its main advantage lies in bounding the overall computational complexity not in the total number of variables, but in the (arbitrary, user-defined) size of the largest block. The algorithm complexity scales constantly with the number of blocks as long as more machines are available, but for a limited communication overhead. Varying the number and size of the blocks allows the user to trade off convergence speed (larger blocks giving more awareness of the relationship between variables) and wall-clock speed (smaller blocks make for faster updates). DiBB is particularly well suite for the purpose of scaling neuroevolution to larger network models, with (weights of connections entering) neurons and layers being prime candidate for block grouping. Future work includes exploring the dynamics of different BBO algorithms, and scaling to larger models models-pottenially non di-ddfffrenttbblee smoothness is not requirement.

---

Under review as a conference paper at ICLR 2022
REFERENCES
Youhei Akimoto, Anne Auger, and Nikolaus Hansen. Comparison-basee natural gradient optimization in high dimension. In Genetic and Evolutionary Computation Conference, pp. 373-380. ACM, 2014.
Charles Audet and Warren Hare. Derivative-free and blackbox optimization. Springer, 2017.
Patryk Chrabaszez, llya Loshchilov, and Frank Hutter. Back to basics: Benchmarking canonical evolution strategies for playing ATARI. Technical Report 1802.08842, arXiv.org, 2018.
Erwin Coumans and Yunfei Bai. Pybullet, a python module for physics simulation for games, robotics and machine learning. http://oybuliee org 2016-20211
Giuseppe Cuccu and Faustino Gomez. Block diagonal natural evolution strategies. In International Conference on Parallel Problem Solving from Nature, pp. 488 497. Springer, 2012.
Jeffrey Dean and Sanjay Ghemawat. Mapreduce: simplified data processing on large clusters.
Commun. ACM, 51(1) 2008. doi: 00.1145/1327452.1374999
acm. http.o/gg....115//3375522222222
Ouassim Ait Elhara, Konstantinos Varelas, Duc Manh Nguyen, Tea Tušar, Dimo Brockhoff, Nikolaus Hansen, and Anne Auger. COCO: The Large Scale Black-Box Optimization Benchmarking (bbob-largescale) Test Suite. arXiv preprint arXiv: (etp::9900033000 2019.
Stanislav Fort and Stanislaw Jastrzebski. Large scale structure of neural network loss landscapes. Advances in Neural Information Processing Systems, 32:6709-67113 2019.
Hervé Fournier and Olivier Teytaud. Lower bounds for comparison based evolution strategies using ve-dimension and sign patterns, Algorithmica, 59(3):387 00874448811 2011.
David Ha and Jürgen Schmidhuber. Recurrent world models facilitate policy evolution. Technical Report 1809.01999, Xrv.ooorg, 2018.
Nikolaus Hansen. Adapting Arbitrary Normal Mutation Distributions in Evolution Strategies: The Covariance Matrix Adaptation. In IEEE International Conference on Evolutionary Compulation, 1996, pp. 312-317, 1996.
Nikolaus Hansen. A global surrogate assisted CMA-ES. In Proceedings of the Genetic and Evolu- fionary Computation Conference, pp. 664-672, Prague Czech Republic, July 2019, ACM. ISBN 978-1 978-144003-611-88 doi: 10.1145/3221077.332)
CRL/ttts:://Ll acm. org/ 2o1/10
1145/3321707, 3321842
Nikolaus Hansen and Andreas Ostermeier. Completely derandomized self-adaptation in evolution strategies. Evolutionary Computation, 9(2):159-1))) 1955999-95--01 2001.
Nikolaus Hansen, Steffen Finck, Raymond Ros, and Anne Auger. Peal-Parrmeter Black-Box Optimization Benchmarking 2009: Noiseless Functions Definitions. Technical Report RR-6869, INRIA, 2009.
Nikolaus Hansen, Dirk V Amold, and Anne Auger. Evolution strategies. In Springer handbook of computational intelligence, pp. 871-898. Springer, 2015.
Verena Heidrich-Meisner and Christian Igel. Neuroevolution strategies for episodic reinforcement learning. Journal of Algorithms, 64(4):152-166) 2009.
Christian Igel. Neuroevolution for reinforcement learning using evolution strategies. In The 2003 Congress on Evolutionary Computation (CEC'03), volume 4, pp. 2588-2595. IEEE, 2003.
Jens Jägersküpper. How the (1+1)-ES using isotropic mutations minimizes positive definite quadratic forms. Theoretical Computer Science, (1)(1))38-55) 2006.
Ilya Loshchilov. Computationally Efficient Limited Memory CMA-ES for Large Scale Optimiza- tion. In Genetic and Evolutionary Computation Conference, pp. 397-404. ACM, 2014.
10

---

Under review as a conference paper at ICLR 2022
Ily Loshchilov, Tobias Glasmachers, and Hans Hans-Georg Beyer. Large scale black-box optimization by limited limited-memory memory matrix adaptation. IEEE Transactions on Evolutionary Computation, 99, 2018.
Mohammad Nabi Omidvar, Xiaodong Li, Yi Mei, and Xin Yao. Cooperative co-evolution with differential grouping for large scale optimization. IEEE Transactions on Evolutionary Computation, 18(3):378-393, 2013.
Matthias Plappert, Rein Houthooft, Prafulla Dhariwal, Szymon Sidor, Richard Y Chen, Xi Chen, Tamim Asfour, Pieter Abbeel, and Marcin Andrychowicz. Parameter space noise for exploration. Technical Report 1706.01905, arXiv.org, 2017.
Ingo Rechenberg. Exolutionsstrategi::
Optimierung technischer Systeme nach Prinzipien der biologischen Evolution. Frommann Frommann-Holzboog. 1973.
Raymond Ros and Nikolaus Hansen. A Simple Modification in CMA-ES Achieving Linear Time and Space Complexity. In Günter Rudolph, Thomas Jansen, Nicola Beume. Simon Lucas, and Carlo Poloni (eds.), Parallel Problem Solving from Nature PPSN X, pp. 296-305, Berlin, Heidelberg, 2008. Springer Berlin Heidelberg. ISBN 978-3-540-87700--1
Tim Salimans, Jonathan Ho, Xi. Chen, and Ilya Sutskever. Evolution strategies as a scalable alternative to reinforcement learning. Technical Report ttXiv:1703.000 arxiv.org, 2017.
Tom Schaul, Tobias Glasmachers, and Jürgen Schmidhuber. High dimensions and heavy tails for natural evolution strategies. In Proceedings of the 13th annual conference on Genetic and Evolutionary Computation (GECCO), pp. 845-852, 2011.
Mahdi Soltanolkotabi, Adel Javanmard, and Jason D Lee. Theoretical insights into the optimization landscape of werr-aaammeterzee shallow neural networks. IEEE Transactions on Information Theory, 65(2):742-769 2018.
Kenneth Stanley, Jeff Clune, Joel Lehman, and Risto Mikkkulainen. Designing neural networks through neuroevolution. Nature Machine Intelligence, 1(1):24335, 2019.
Konstantinos Varelas. Benchmarking Large Scale Variants of CMA-ES and L-BFGS-B the Bbob- Largescale Testbed. In Proceedings of the Genetic and Evolutionary Computation Conference Companion, GECCO '19, pp. 1937-1945, New York, NY, USA, 2019. Association for Computing Machinery, ISBN 4-78--4450- doi: 10. 10.1145/331661933326999 URL BoLLhttp::/// //doi Oxc/10.1145/33196199
D. Wierstra, T. Schaul, T. Glasmachers, Y. Sun, J. Peters, and J. Schmidhuber. Natural evolution strategies, Journal of Machine Learning Research, 15:949-980, 2014.
A APPENDIX
A.1 DETAILS OF THE COCO/BBOB EXPERIMENTS
For experiments and 2, budget multiplier of 10 was chosen and the IPOP restart mechanism was used in accordance with Hansen (2019). To compare not only against CMA-ES but also the separable version, we also ran sep-CMA-ES ES on the bbob suite with budget multiplier of 10*.
To compare with CMA-ES and sep-CMA-ES, we ran experiments 3 and 4 without IPOP and we sampled the initial candidate solutions uniformly at random from [-4, 4] the same way Varelas (2019). Experiment uses budget multiplier of 10f, and experiment 4 uses a budget multiplier of 1 The initial step size sigma0 was set in all of the experiments.
The data for CMA-ES and sep-CMA-ES can be downloaded via cocopp or us- ing the following links respectively: CMA /ttps//aaaaaaaooooooo/aaaaaaaaar
http::///mmbboogitttuu www.ooree//ggogggeeooooooo
and
Varelas seppo
11

---

Under review as a conference paper at ICLR 2022
JOWNG
X413 no
0080 110
5433 785
(1er 2079
aeroond DIGI
op201 SauEl
eg20
<0482 180)
1000
JOWNS
00000 Touhh Jabrnnde
kxt Teadh (sbrende
by22 "ook pavemast
20400 F1
J0W44
(аpр
JCMNCS
20MA
Low
Soees PM
85g
CM6
bp20/e Sierrbni
log Saak
Iagio Sevali
loga2 Heabi
VHEPON:
00159 PB5
ka3 Teaath Jenonsae
1xg1 Foaah
Nag Touah (Vhrensir))
kup0 hoodh//ooesse devenseed
20422
14
20
1OW4
2048 9M
Opee
044 PRX
kx302
1e Loch
1x Touch (1hremarr)
k4022 Leade/ Aiseende
Figure 4: BBOB COCO results of DiBB. separable and full CMA-ES. Rows correspond to dimen- sions 5, 10, 20, 40, 80, 160, 320, and 640. Columns correspond to Exp 1/Exp 2 on separable functions, ill-conditioned functions, as well as Exp 3/Exp 4 separable and ill-conditioned functions.
12

---

Under review as a conference paper at ICLR 2022
BBОB
d= 5
d d= 10
d = 20
d = 40
Exp. 1 Exp. 2
2/2 / 250K 1/ 500K
2/5 500K 2/5/ 500K
10/ 1M 4/ 5/ 500K
2/ / 2M
8/ 5 500K
large-scale
d 80
d= 160
d= 320
d = 640
Exp. 3 Exp. 4
16/ / 5 250K
16/ 1 500K
16/ / 1M
16 40/ 2M
2 40 400K
4 40 400K
/ 400K
16 40 400K
Table 2: Experimental setup the BBOB and the BBOB large-scale suites, in the format "number of blocks block size / # objective function evaluations per machine". Experiments and 3 scale the block size (and correspondingly, the evaluation budget per compute node), while experiments 2 and scale the number of blocks.
13


Reviews:
[{"review_id": "xxklRpVhpRW", "reviewer": "Reviewer_CxhD", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 4, "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": "Strengths:\n* Paper is clearly written and I was able to understand the technical concepts behind it. \n* Method is highly parallelizable and is scalable across multiple different machines.\n* Comprehensive results over BBOB functions show the speed scaling as well as which types of functions DiBB shines.\n\n\nWeaknesses:\n* Motivation for the Mujoco (actually, only Walker2d) benchmark. Applying LM-MA-ES on Walker2D (with a relatively huge policy network) is a bit artificial, since it's already solvable by a significantly smaller (even linear) policy with purely ARS/ES (see [1]). Figure 4 in [2] also showed that LM-MA-ES performs significantly worse than ES, so it's even more unclear why we need a Hessian-based method here. I would suggest to the authors to use a benchmark where CMA/Hessian methods are actually needed, over ES/ARS. Outside of the specific paper, it is generally a standard to also try methods on all standard Mujoco benchmarks (e.g. HalfCheetah, Hopper, Swimmer, etc.) and not just Walker2d.\n\n* Theoretical foundations are still quite lacking, even though the paper discusses convergence rates (ex: 2.2, 2.3). In Section 2.3, the paper discusses that \"weights belonging to different layers (and even weights belonging to different neurons within the same layer) to be less correlated than weights within a layer.\" This is somewhat of a controversial statement and needs to be quantified carefully. Can you provide any form of justifications for this claim? A simple and cheap way for instance, is to measure this correlation matrix explicitly (see ex: Figure 1 in [2]) for an example problem. \n\n* The method requires the user to know in advance which parameters have \"high correlations\" between each other rather than potentially learning this separation. This makes it fairly impractical for many scenarios and fairly difficult for widespread adoption. I would suggest to the authors to propose a mechanism to automate this process, as it seems like it may be a huge issue.\n\n[1] Simple random search of static linear policies is competitive for reinforcement learning (NeurIPS 2018)\n\n[2] From Complexity to Simplicity: Adaptive ES-Active Subspaces for Blackbox Optimization (NeurIPS 2019)", "summary_of_the_paper": "This paper proposes Distributed Black Box optimization (DiBB), which involves using disjoint distributed pipelines to perform CMA/Hessian-based updates, over functions with assumed separability in terms of parameters. The method is explained in detail, and experiments are performed on BBOB functions (with varying dimensions), along with Mujoco Walker2d with a relatively large policy architecture (10K+ parameters). Other ablations such as wall-clock time and varying block sizes are also experimentally presented.", "summary_of_the_review": "The paper seems like it has promise in terms of the core idea (i.e. throw out low correlations between certain parameters), but does not execute properly on showing where or why this modified CMA-ES variant is needed (outside of just BBOB benchmarking). I would suggest that the authors think strongly about this question, and strengthen the motivation more.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "m0yWP67MiKz", "reviewer": "Reviewer_6N3W", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 3, "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": "**Concerns on the main \"block\"-able assumptions**\n\nDiBB built on the assumptions that the optimization variables (e.g., the weight and bias of neural networks in the context of neural network training problems) can be separated, and the authors assume the blocks can be constructed when it comes to the neural network (most likely feed-forward style only) each weight parameters of layers can well serve as the blocks.\n\nHowever, it usually is not true when we consider the gigantic, deep, modern NNs — e.g., residual connections are designed to allow the gradient flow from the beginning of the network to the end of it. This, I think, highly violates the assumption that the authors made. In this view, I think the (proper) use of DiBB can be restricted to the quite conventional Feed forward typed neural network.\n\nFrom the reported experimental results, I can conclude that DiBB works well only when the underlying objective functions are separable. It is quite natural due to the design of DiBB.\n\n\nComments about the experiments\n- **COCO/BOBO experiments**: It seems like more experiments are required to understand the behavior or performance of the proposed DiBB fully.\n    - DiBB shows comparable results to the CMA-ES for f1-f4 on COCO/BOBO. I think this outcome should be actual by the design of DiBB and the functions (f1-f5).\n    - **Timings** sections highlight the computational times of the DiBB algorithm but do not explain the attained quality of objective values. It might be more comprehendible if it reports the objective values and computational time altogether.\n- **PyBullet WALKER 2D experiments:** Similar to the COCO/BOBO experiments, the conducted experiments do not fully explain the strength or weakness of DiBB.\n    - The network architecture (2 layered MLP) that has been tested may be too small to showcase the proposed algorithm. Furthermore, the reported performance of trained policy is far from the state-of-the-art or even okayish ones. One of the \"classic\" RL algorithms, TRPO [1] reports better performance with a shorter number of computational times.\n- Minor comments:\n    - Some parts of the paper use notations that are not introduced in the text. (e.g., the variable $a$ is not explained but used to explain a part of DiBB)\n    - The baseline algorithms of Figure 2 are not explained.\n    - Maybe some contents of table 1 are missing. However, the related contents can be found from the main text — The 2nd paragraph of **Timings**\n\n[1] Schulman, John, et al. \"Trust region policy optimization.\" *International conference on machine learning*. PMLR, 2015.", "summary_of_the_paper": "This paper suggests Distributing Black-Box Optimization (DiBB) framework that enables the running of black-box optimization techniques in a distributed manner. Under the assumption that some optimization variables are correlated in a negligible manner to the optimization objective values, the authors partition the variables into the chunk of variables dubbed \"Box.\" The core idea of DiBB is to perform black-box optimizations for each block and update the optimization results in an asynchronous manner. From the numerical experiments on the black box optimization benchmark (BBOB), the proposed DiBB shows marginally better performance when the underlying black box function matches the assumption that the optimization variables can form blocks. Additionally, the authors apply DiBB to perform a canonical example of RL tasks.", "summary_of_the_review": "The proposed method is not techincally novel enought and the experiment result does not fully support the effectiveness of the proposed method.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "dk0wT7cZJR4", "reviewer": "Reviewer_mpL3", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 4, "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": "First of all, the paper is not very well written or sufficiently detailed to warrant a publication in such a reputed conference as this one. In addition, I think the content of the paper is more meaningful to the narrower domains focussing on evolutionary computing, such as the GECCO community. Coming to the technical side of the paper, please consider the following comments:\n\n1) Although the abstract starts with a very ambitious note that the distributed computing framework can encapsulate \"any\" black-box optimizer, I do not see many provisions for simpler and very often better-performing algorithms like the Differential Evolution (DE).\n\n2) The main framework of DiBB is quite overlapping to that of the Block-Diagonal Natural Evolution Strategies (in the paper, referred to as: Cuccu & Gomez 2012). The tweakings introduced in the paper seem minor and hence, the major novel algorithmic contributions seem limited.\n\n3) When it comes to testing on BBOB test suite and neural architecture search problems, why the method was not compared to several other and recent distributed/parallel evolutionary algorithms where the core optimizer is not from the ES family? For example, see the following papers:\n\nNoor Awad, Neeratyoy Mallik, and Frank Hutter, Differential Evolution for Neural Architecture Search, NAS@ICLR 2020\n\nZ. Yang et al., \"CARS: Continuous Evolution for Efficient Neural Architecture Search,\" 2020 IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR), 2020, pp. 1826-1835, doi: 10.1109/CVPR42600.2020.00190.\n\nAlso, for NAS, the proposal was not compared against the most representative non-evolutionary approaches. The current results, on a first look, does not appear sufficiently competitive. \n\n4) The paper, except for citing a reference to Omidvar et al's IEEE  TEVC paper, does not elaborate on how the linkage between different variables could be explored more thoroughly.\n\n5) The speed-up with the proposed parallelization scheme has not been explicitly compared to other similar schemes for evolutionary/swarm intelligence-based algorithms.  \n\n6) The results were not explicitly validated on the basis of powerful, non-parametric hypothesis testing. \n", "summary_of_the_paper": "The paper presents an alternative method of parallelizing a particular flavor of Evolutionary Algorithms, more specifically the Evolution Strategies (ESs) and particularly the CMA-ES. The authors propose to use a block structure to add covariance matrix information inside the blocks of potentially highly correlated variables with a low computational cost.", "summary_of_the_review": "Considering the lack of originality, inadequate match to the theme of this conference and lack of rigorousness in experimental procedures, I will have to recommend a rejection for this paper. ", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "Y1msP8BRWL", "reviewer": "Reviewer_wFNK", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "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": "The idea of clustering variables into blocks is novel and neat. My main concern is that the empirical results are not as good as expected. However, I would still lean towards acceptance given the novelty of the idea. See detailed comments as follows.\n\nStrengths: \n1) The DiBB problem is a fundamental problem. The methodology and the ideas proposed in this paper could potentially be used in a wide range of problems of this nature, especially the neuroevolution problems.\n\n2) The idea of clustering variables into blocks is novel and neat. Moreover, the authors have done a great job illustrating the complexities of the previous methods, including the two extremes of CMA-ES (full covariance matrix update) and sepCMA (diagonal covariance matrix update). I like the discussion of \"sample complexity\" and \"internal complexity\".\n\n3) The line of existing works are well discussed.\n\n4) The neuroevolution example is a good motivation.\n\n5) In the specific method proposed, the reference solution seems to be a reasonable trick.\n\n\nWeaknesses: My main concern, as state above, is that the experimental results are not as good as expected. Also, there are some clarity issues that may need to addressed.\n\n1) In Figures 2 and 4, from the caption of the figures, it seems each figure shows results for two experiments? It is a bit hard to interpret what exactly each figure is about. For example, what do the lines ooutside the box mean? \n\n2) In Figure 4, for the f1-f5 functions, sometimes DiBB is worse than sepCMA. This is somehow expected, but it also shows (together with the other results such as the CMA-ES results) that DiBB does not have much advantage compared with the two extremes when there is no prior knowledge about the variable dependencies. This is a major limitation of DiBB. \n\n3) It is not clear to me how the different blocks are generated in the BBOB and BBOB large-scale suite experiments. Is it random, or by some rule?\n\n4) In the Walker 2D example, it is not clear to me, is DiBB used in each policy update step of the RL algorithm? -- so basically, you replaced the gradient step with the DiBB update -- is that correct? If this is correct, I am wondering why don't you run a simpler task, e.g., a supervised learning task where you need to do architecture/hyperparameter search. \n\n5) Another concern about the Walker 2D example is that, DiBB is not compared with sepCMA or CMA-ES. Theoretically, DiBB should show a large advantage in the neuroevolution task, but the baseline here is a rather weak one (Random weight guessing). This poses questions on the practical usefulness of the proposed method. ", "summary_of_the_paper": "This paper addresses the distributed black-box optimization problem. The key contribution is an in-depth understanding of the weaknesses of the current ES literature in sample complexity and per-sample complexity, and points out a direction to mitigate the weakness -- i.e., to exploit the prior knowledge of the dependency of the variables, and cluster them into blocks, where each block is solved separately with the designed distributed solution framework.", "summary_of_the_review": "Overall, the idea is novel and neat, and the discussion of the complexity/challenge and motivation are well presented. My main concern is about the experimental results, as they are not as good as expected, especially the Walker 2D example. \n\nIt might be because of the implementation details or other reasons, but the idea seems promising. \n\nTherefore, my overall recommendation is towards accept. ", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}]

Author rebuttal:

Meta-review: The authors propose a novel framework for Distributing Black-Box Optimization (DiBB) which can encapsulate any Black Box Optimization (BBO) method. DiBB overcomes some of the limitations of existing methods by leveraging expert knowledge in the problem. The reviewers raised a variety of important technical concerns. The authors seem to agree that they need to substantially rewrite the paper. Therefore I recommend a rejection.
Decision: Reject