What can multi-cloud configuration learn from AutoML?
Authors: Malgorzata Lazuka
Thomas Parnell
Andreea Anghel
Haralampos Pozidis
Venue: ICLR 2022 Submitted (2022)
Keywords: Cloud
AutoML
Multi-armed bandit
Black box optimizers

Abstract: Multi-cloud computing has become increasingly popular with enterprises looking to avoid vendor lock-in. While most cloud providers offer similar functionality, they may differ significantly in terms of performance and/or cost. A customer looking to benefit from such differences will naturally want to solve the multi-cloud configuration problem: given a workload, which cloud provider should be chosen and how should its nodes be configured in order to minimize runtime or cost? In this work, we consider this multi-cloud optimization problem and publish a new offline benchmark dataset, MOCCA, comprising 60 different multi-cloud configuration tasks across 3 public cloud providers, to enable further research in this area. Furthermore, we identify an analogy between multi-cloud configuration and the selection-configuration problems that are commonly studied in the automated machine learning (AutoML) field. Inspired by this connection, we propose an algorithm for solving multi-cloud configuration, CloudBandit (CB). It treats the outer problem of cloud provider selection as a best-arm identification problem, in which each arm pull corresponds to running an arbitrary black-box optimizer on the inner problem of node configuration. Extensive experiments on MOCCA indicate that CB achieves (a) significantly lower regret relative to its component black-box optimizers and (b) competitive or lower regret relative to state-of-the-art AutoML methods, whilst also being cheaper and faster.

Under review as a conference paper at ICLR 2022
WHAT CAN MULTI-CLOUD CONFIGURATION LEARN FROM AUTOML?
Anonymous authors Paper under double-blind review
ABSTRACT
Multi-cloud computing has become increasingly popular with enterprises looking to avoid vendor lock-in. While most cloud providers offer similar functionality, they may differ significantly in terms of performance and/or cost. A customer looking to benefit from such differences will naturally want to solve the multi- cloud configuration problem: given a workload, which cloud provider should be chosen and how should its nodes be configured in order to minimize runtime or cost? In this work, consider this multi-cloud optimization problem and publish a new offline benchmark dataset, MOCCA, comprising 60 different multi-cloud configuration tasks across 3 public cloud providers, to enable further research in this area. Furthermore, we identify an analogy between multi-cloud configuration and the selection-configuratin problems that are commonly studied in the automated machine learning (AutoML. field. Inspired by this connection, we propose an algorithm for solving multi-cloud configuration, CloudBandit (CB). It treats the outer problem of cloud provider selection as a best-arm identification problem, in which each arm pull corresponds to running an arbitrary black-box optimizer on the inner problem of node configuration. Extensive experiments on MOCCA indicate that CB achieves (a) significantly lower regret relative to its component black-box optimizers and (b) competitive lower regret relative to state-of-the-art AutoML and multi-cloud methods, whilst also being cheaper and faster.
INTRODUCTION
We are currently living in the era of cloud computing, in which cloud providers compete to offer computing resources, including servers, storage and managed software, to businesses and consumers via the internet. Cloud a high growth segment: according to Gartner (2021), worldwide end-user spending public cloud services is forecast grow 23.1% in 2021 to total $332.3 billion. From an enterprise perspective, there are many benefits to utilizing cloud services including, but not limited to: increased flexibility, reduced costs, improved security and rapid scaling.
Coupled to the rise cloud is the growing popularity of containers and container orchestration platforms. A container image (e.g., Docker) is executable package of software that includes everything needed to run an application: code, runtime, system tools, system libraries and settings (Soltesz et al., 2007: Merkel, 2014). At runtime, container images become containers and can be deployed quickly and reliably from one computing environment to another, making them well-suited the world of cloud computing. Many of today's workloads, such as machine learning (ML) training, are distributed in nature and require the deployment and management of multiple containers, all working together in parallel. Container orchestration platforms such as Kubernetes (Brewer, 2014) enable running such systems resiliently, providing features like auto-scaling and failure management.
Most cloud providers now offer Kubernetes service, meaning that they require only a few commands to create a Kubernetes cluster, and the user can specify the desired number of nodes and how each node should be configured (how many CPUs, memory, etc.). Given a Kubernetes cluster, one can easily run a complex distributed workload, whilst remaining agnostic to which cloud provider is providing the resources in the backend. This level of abstraction presents the savvy business or consumer with new optimization opportunity, which will refer to the multi-clone configuration problem. Namely, given a workload, which cloud provider should be selected, and how should the nodes in the cluster be configured, in order minimize runtime cost?

---

Under review as a conference paper at ICLR 2022
In practice, this optimization problem is of particular interest to businesses with complex, distributed workloads that must be run repeatedly. For instance, consider a business with a ML-based recom- mendation engine that must be trained, in distributed fashion, multi-cloud configuration problem, the business will be able to exploit price/performanee differences that may exist between cloud providers improve their bottom-line However, any optimization algorithm will involve making a certain number of evaluations (c.g., running the workload on particular cloud provider, with particular node configuration), and these evaluations will themselves incur certain dollar cost. For this reason, effective algorithms with fast convergence are of particular interest in this domain, and are the primary focus of this paper.
every hour. By solving the
The main contributions of our work are as follows:
We formally introduce the multi-cloud configuration problem and draw an interesting connection with the selection-configuratioo problems that are commonly studied in the automated machine learning (AutoML) field.
Inspired by AutoML approaches, we propose a best-arm identification algorithm, Cloud- Bandit, for solving the multi-cloud configuration problem.
We present a new dataset, MOCCA, for offline benchmarking of optimization algorithms applied to 60 multi-cloud configuration tasks, across 3 public cloud providers.
Extensive experiments on MOCCA show that CloudBandit outperforms many generic black-box optimizers and state-of-the-art selection-configuration algorithms.
2 PROBLEM STATEMENT AND BACKGROUND
2.1 MULTI-CLOUD CONFIGURATION AS OPTIMIZATION
The runtime/cost of workload in the cloud depends on many factors, such as the number of nodes used, the vCPU count, the amount of memory allocated to each node, the manufacturcr/generatti of the backend CPU, the network on which the nodes communicate and the region in which the nodes are deployed. While some of these parameters (c.g., vCPU count and amount of memory) are, on the surface, common across different cloud providers, most providers do not give the option to set these parameters freely. Instead, one must select from set of available VM categories (often parameterized into sub-categories like family, lype or size) that define which CPU will be used, how many vCPUs and how much memory will be assigned to the node, well as what network interfaces are used. These subb))categorie are significantly different across cloud providers, making it difficult to construct multi-cloud optimization problem over parameters that are common across all cloud providers (e.g., vCPU count) without introducing complex constraints.
Instead, is much easier to view the multi-cloud configuration problem as an optimization over a hierarchical domain, where the domain for each cloud provider comprises unique set of categorical parameters. Let {Ci, C2 ..., C.) denote the set of available cloud providers and P. the set of all possible node configurations for the i-th cloud provider for i 1, 1,2...,74 n. We can then define the functions [p) : P/ + IR, which, for the i-th cloud provider with node configuration p, may measure either workload runtime, monetary cost or some other optimization target. We can then formally define the multi-cloud configuration problem as follows:
= arg min vE[L.x] [min peP, f((p]
(1)
We note that this is joint optimization problem comprising the outer selection problem, i.e., which cloud provider to use, as well the inner configuration problem, i.e., how to configure the nodes.
2.2 RELATED WORK CLOUD LITERATURE
Configuration subproblem. There is significant body of work studying the configuration subprob- lem: i.e., given a cloud environment C₁ how to find the number and types of computing instances that would maximize the performance minimize the cost of workload deployment. Chen et al. (2021) present a cloud configuration framework that builds prediction models from small-scale experiments to estimate the performance of experiments large-scale clusters. Mahgoub et al. (2020) introduce
2

---

Under review as a conference paper at ICLR 2022
an online system that adjusts the database and VM configurations the behavior of the workload changes. Mariani et al. (2017) define a method to estimate the cloud performance of a workload by employing hardware-agnostie application profiles and cirtoo--frrst-bbiie prediction models. Other prior art from the cloud literature considered employing black-box optimizers (BBOs), such as Bayesian Optimization (BO), to optimize the cloud instance type, cluster size, or both (Yadwadkar et al., 201 7a; Alipourfard et al., 2017: Bilal et al., 2020; Hsu et al., 201 8b). Additionally, a number of works have looked at improving the performance of BO by augmenting it with low-level performance metrics captured from the workload Hsu et al. (2018 2008);c).
Selection subproblem. None of the approaches mentioned so far have addressed the cloud configu- ration problem in the multi-cloud setting. However, there has been work in the direction of cloud provider selection (without configuration). Chen et al. (2020) introduce a provider selection optimizer (FrugalML) for specific workload, namely ML inference. Given input data, FrugalML. suggests which cloud providers (cloud APIs) should optimally be used for running an inference task so that the user budget is met and the prediction accuracy is increased. Moreover, the selection problem has been widely addressed in the context of multi-cloud service composition (MCSC). Pang et al. (2020) propose method based on formal concept analysis and skyline hierarchical computation to obtain an optimal MCSC in a mobile edge computing environment. To solve MCSC under uncertain QoS attributes, Haytamy& & Omara (2020) describe method based on Particle Swarm Optimization. Souri et al. (2020) use formal verification to prove the correctness of MCSC approach that finds the service composition with the minimum number of cloud providers under given QoS user requirements.
Joint calectin-cooffiuuratin problem. To the best of our knowledge, the joint cloud selection- configuration problem has been less studied. Yadwadkar et al. (2017b) consider the problem of finding the best VM for single-node workload across multiple cloud providers. The problem is framed as a prediction task and a random forest model is trained on dataset comprising low- level performance metrics from pre-existing workloads. The trained model can then be used to effectively predict the performance of each VM for unseen workloads. An orthogonal direction, with which our paper is aligned, treats the multi-cloud configuration problem as an optimization task and aims to develop algorithms that do not require information collected from pre-existing workloads. Ramamurthy et al. (2020) propose a search-based method that ranks cloud providers for given workload. The VM configuration for each cloud provider is optimized independently, using an arbitrary optimization algorithm that may take into account memory and/or disk space constraints. Shi et al. (2020) describe Genetic Algorithm that finds multi-cloud deployment configuration for multi-service applications. To decrease the complexity of the search, the authors design a clustering algorithm that groups dependent services, so that services in the same cluster are deployed to the same location (provider or region). Challenges arise with this approach when mutations occur that cross cloud providers, since the of VMs offered by each provider differ significantly.
Figure 1: Relationship between multi-cloud configuration and AutoMI..
AutoML
Multi-cloud
RF
XGBoost
NN
Cloud A
Cloud B
Cloud C
trtress
eta max depth
n_ _.aaerrs aaer size
Autamily
type
Clclass
max_depth
A 5.0
B. memory
C_cou
activation
nodos
nodes
nodes
2.3 RELATION TO AUTOML
In Bilal et al. (2020) the authors make an analogy between cloud configuration and hyperparameter tuning in machine learning. They point out important differences between these two problems. Firstly, cloud configurations consist mostly of integer or categorical variables, whereas hyperparameters in machine learning are often continuous. Secondly, cloud configurations are typically complex and expensive to evaluate (involving spinning up a cluster of nodes), whereas hyperparameter configurations may be easily evaluated on single node. Despite these differences, the authors found
3

---

Under review as a conference paper at ICLR 2022
that methods that work well for hyperparameter tuning (such BO with random forests or gradient boosted trees) are also extremely effective for solving the cloud configuration problem.
The key insight of this paper is to go one step further and notice that, due to its hierarchical nature, the selection-configuratin configuration problem defined in (1) bears a striking resemblance to the joint optimization selection
problem at the heart of AutoML. Namely, in AutoML. neural networks vs. gradient-booste decision trees), and decide how to configure each model (e.g.. how each hyperparameter should be chosen). Figure illustrates this analogy.
must select which ML model to use (e.g..
2.4 RELATED WORK IN AUTOML
Having established this analogy, it makes sense ask the question: can existing methods from AutoML be applied to the multi-cloud configuration problem (1)? We now proceed to review the state-of-the-ar with this question in mind.
Two early, ground fround-breaken breaking AutoML solutions were auto-sklearn (Feurer et al., 2019) and Auto- WEKA (Thornton al., 2013). Both of these frameworks remain highly active GitHub projects, and both use sequential model-based algorithm configuration (SMAC) for solving the model selection- configuration problem. SMAC, introduced in Hutter al. (2011) and recently extended in Lindauer et al. (2021), implements form of BO that takes into account the natural hierarchy present in selection-confiiuration problems. SMAC is itself an actively maintained GitHub project, and provides APIs that can be used to solve arbitrary to AutoML). Accordingly, SMAC can be easily applied to multi-cloud configuration.
problems (rather than being specific
More recent works have proposed splitting the model dntection-configuraaioon problem into simpler subproblems and solving them in an alternating fashion. In principle, all of these approaches can be readily applied to the analogous problem of (1). Firstly, an approach based on the alternating direction method of multipliers (ADMM) was proposed in Liu et al. (2020). Secondly, in Rakotoarison et al. (2019), it was proposed use Monte-Carlo tree search to solve the selection problem, and BO to solve the configuration problem. Finally, Li et al. (2020) proposed Rising Bandits (RB), an algorithm that treats the model selection problem as a best-arm identification problem, in which each arm corresponds to ML model and each arm pull corresponds to running BO with a fixed budget to optimize the corresponding model configuration. These methods, in particular RB, served as main inspiration for the algorithmic approach described in the next section.
On the other hand, there exist AutoML solutions which cannot be applied to multi-cloud configuration in straightffrward manner. For example, frameworks like H2O's AutoML (LeDell & Poirier, 2020) and AutoGluon (Erickson et al., 2020) do not perform selection, but rather form ensembles of different, configured ML models. While ensembling has proven very successful in the AutoML context, achieving better accuracy than a single model, it does not have a natural analogy in the context of optimization problem (1). Other AutoML frameworks, such as TPOT (Olson & Moore, 2016), focus more on the problem of feature engineering to achieve high accuracy, rather than selection-configuration and thus do not relate directly to problem of minimizing runtime and/or cost of cloud workloads. Another popular direction in AutoML are multi-fidelity approaches like Hyperband (Li et al., 2017) or BOHB (Falkner et al., 2018) that try eliminate bad configurations very quickly by evaluating them using small resource (for instance, small subset of the training examples). Such methods cannot be applied to multi-cloud configuration the general setting since we may not know the specifics about the workload that is to be optimized, and even if we did, it may not admit any sensible notion of resource. Finally, there exist numerous commercial offerings AltoMI. space such as Google Cloud Platform A Tables, IBM AutoAI, H2O Driverless AI, and many more. These proprietary offerings typically provide ML-specific interfaces and the details of how they solve the problem internally remains unknown.
the
CLOUDBANDIT A MULTI-CLOUD CONFIGURATION SOLUTION
3.1 ALGORITHM DESCRIPTION
We propose treating the multi-cloud configuration problem non-stochastic best-arm identification problem, as defined in Jamieson & Talwalkar (2016). Specifically, we have n arms, each arm corresponding different cloud provider. Pulling corresponds to running iteration of
4

---

Under review as a conference paper at ICLR 2022
an arbitrary BBO algorithm find the best configuration for the corresponding cloud provider. Let reward ri,k denote the best runtime or cost obtained by pulling the i-th arm k times. Assuming that the reward for the i-th arm eventually converges to 14, lim Tü, min pEr, fe(p), then the multi-cloud configuration problem (1) is equivalent to the problem of identifying arg min, Hi- To have efficient algorithm, we would like achieve this whilst minimizing the total number of arm pulls, henceforth referred to as the total budget.
We now describe Clnddtandit (CB), simple algorithm for solving the best-arm identification problem defined above. The algorithm maintains an active set of arms A, which is initially equal the complete set of all arms (i.e., all cloud providers). The algorithm then performs number of rounds equal to the number of providers. The k-th round (for k = L..., n) arms the active set by times. Next, the arm in the active set with the worst reward is identified and eliminated from the active set. Before proceeding to the next round, the budget is increased by
begins by pulling all
multiplicative factor: 1 = 7 At the end of the n-th round, the best identified configuration returned, for the sole remaining provider.
The CB algorithm defined in full in Algorithm 1. The algorithm has two hyperparameters: the initial budget by and the growth factor The total budget of CB can be expressed in terms of these two hyperparancters: B = Σ (n 1 1 By using relatively small by and setting 17 > 1, is hoped that the algorithm can eliminate slow (or expensive) cloud providers very quickly, whilst exploring the more promising cloud providers exponentially more than those that are eliminated.
Algorithm CloudBandit
1: Initialize set of arms (cloud providers): A {1, ............ n) and 8
2: Set initial budget bı and budget growth factor 1).
3: for k == 1......,14 do
4: for A do
5:
Run by iterations of component BBO for provider 6: Receive best configuration Pi, and corresponding reward: ri,ttb. fi(Pebtbo)
7:
end for
8:
Identify the best arm: i* = arg min "bb+bb
9: Eliminate the worst arm: A A farg max Teb+b,,
10: Increment = b + by and set budget for next round: ba-1 77 bN.
11: end for
12: Output best provider i* and its configuration Ps-.b-
We note that, after each round of CloudBandit, is actually possible to utilize all previously-evaluate configurations by passing them on the component optimizers in following rounds. However, due to the way most BBO software tools are implemented, this presents quite some technical challenges. We discuss how these challenges can be overcome and the effect of passing this information forward in Appendix B. However, all results in the main manuscript use the vastly simpler approach, where each component optimizer instance is independent.
3.2 CLOSELY RELATED ALGORITHMS
Successive Halving. A popular method for solving best-arm identification problems is successive halving (SH). It was first proposed in Karnin et al. (2013) for the stochastic setting, in which each arm pull corresponds to sampling from a probability distribution, and later generalized to the non-stochastic setting in Jamieson & Talwalkar (2016). SH is similar to CloudBandit, in that it maintains an active set of arms which are progressively eliminated, and arms that survive are explored exponentially more than arms that don't. The key difference is that SH eliminates constant fraction (1 (1/1) of the arms in each round. While this approach may also be effective the multi-cloud configuration setting when the number of providers is fairly large, when this number is relatively small (c.g., = 3), it is hard to define a reasonable climination schedule due to rounding issues.
Rising Bandits. In Li et al. (2020), the authors treat the model dalection-confiuurain problem from AutoMI. best-arm identification problem, and propose new algorithm: Rising Bandits
5

---

Under review as a conference paper at ICLR 2022
(RB). In RB, each arm corresponds to different ML model, and each arm pull corresponds to running a fixed number of iterations of BO to tune the hyperparameters of the corresponding model. The reward is given by the best validation loss found by the optimizer. This algorithm is different to CloudBandit in three important respects. Firstly, each arm pull in RB corresponds to running a number of iterations of BO (rather than an arbitrary BBO). Secondly, in RB, the arms are pulled fixed number of times in each round (i.e., by is constant). Finally, RB does not eliminate arms by simply discarding the arm with the worst reward. Instead, RB makes a theoretical assumption about the way the validation loss converges as a function of BO iterations. Specifically, RB assumes that after a certain number of pulls all arms will reach a point of diminishing returns. The authors derive a theoretical criteria for when this point is reached, at which point an arm is eliminated.
4 MOCCA: AN OFFLINE MULTI-CLOUD BENCHMARK DATASET
Multi-cloud configuration is an exciting new optimization problem, and we feel that the ML. com- munity would be interested in developing new algorithms for this emerging application. However, running online experiments can be time-consuming and costly, making this area of research inacces- sible to many our community. For this reason, offine benchmark datasets that allow researchers to compare different optimization algorithms without performing all the necessary cloud experimenta- tion are highly desirable. While Hsu et al. (2018c) provided an offline dataset regarding configuration of cloud workloads for single-provider, to the best of our knowledge there are no datasets relating to the multi-cloud scenario. Thus, in order to accelerate our own experimentation, as well as to open this problem up others, we have constructed MOCCA (Dataset for Multi-Cloud Configuration A Algorithms) - a multi- cllud benchmark dataset, which will be made publicly available. In this section we will describe some important details regarding how this dataset constructed.
Cloud provider and configuration space. Our experimental data was collected by running workloads on top of Kubernetes clusters, deployed three different cloud providers. The process of deploying Kubernetes cluster on each of the providers follows the same general pattern but differs in the details such as provider-specific tooling and authentication. The number of nodes in the cluster treated as an integer parameter that is common across all providers, and for each provider, we introduce a number of provider-specifi categorical variables corresponding the various options f.g..ff.iily size, type) that are available for configuring the nodes. Throughout the paper, as well as in the dataset itself, the names of the cloud providers (as well as their configuration options) have been anonymized. The total dimensionality of the resulting hierarchical configuration space is 88.
Workloads. We consider various ML training and data pre-processing workloads from the da dask-ml package, a library for scalable ML that runs on top of the Dask framework (Dask Development Team, 2016). For our purposes, Dask workloads were attractive for two main reasons. Firstly, Dask is a distributed framework and workloads can be seamlessly scaled out across nodes. Some workloads may benefit greatly from such scaling, others may suffer in terms of performance as more nodes are added. For this reason, it is typically more difficult to find the optimal configuration of distributed workload, compared to the single-node case, leading to a more interesting optimization problem for our benchmark. Secondly, Dask has a clean integration with Kubernetes: it is simple to deploy a Dask cluster (using Helm charts) on top of a set of Kubernetes pods. Furthermore, this process is agnostic to where the Kubernetes pods are located, resulting in straightforward scripting even in the multi-cloud setting.
Optimization tasks. our benchmark an optimization task comprises: (a) a workload defined as a (Dask task, input dataset) pair, and (b) an optimization target which can be either runtime or cost. We collected data for 30 different workloads (10 Dask tasks running on input datasets) and 2 different optimization targets, leading to a total of 60 different optimization tasks. Details regarding all Dask tasks and datasets can be found in Appendix A. For the runtime target, we recorded the total time taken by given workload for each cloud provider and configuration, including all data transfer overheads. To generate data for the cost target, we estimate the cost by multiplying the runtime by the listed price-per-hie per-hour for each node, as well as factor equal to the number of nodes. While this is an imperfect estimate, and will not take into account additional data transfer costs, more precise estimates are difficult to obtain since cloud billing typically occurs monthly in an aggregate manner.

---

Under review as a conference paper at ICLR 2022
5 EXPERIMENTAL RESULTS
5.1 CHOOSING THE COMPONENT BBO
To begin our experimental evaluation, we will investigate the effect of using different BBOs as components inside CB. The goal of this experiment is twofold. Firstly, we would like to determine which BBO provides the best performance. Secondly, we would like to verify that the performance of given BBO is consistently improved when used inside CB relative to being naively applied to the flattened parameter space. In our experiment we consider four different BBOs: random search (RS), BO with Gaussian processes (GP), BO with random forests (RF) and RBFOpt. While RS is perhaps the simplest baseline, in Li Talwalkar (2020) was found to be a surprisingly strong baseline in AutoML context. BO with GP surrogate model was proposed in Snock et al. (2012) for hyperparameter tuning tasks, whereas Bilal et al. (2020) found BO with RF to perform better for the cloud configuration task. In both cases, we use the BO implementation provided by scikit-optimize (Louppe, 2017). RBFOpt is a relatively new BBO and has been shown in Costa & Nannicini (2018) to outperform wide range of BBOs function method, originally proposed in Gutmann (2001), and was recently improved in Nannicini (2020) to provide better support for categorical variables.
variety of optimization tasks. It is based on the radial basis
For each BBO, we evaluated its performance both when used as a standalone optimizer, and when used component within CB. Experiments were performed for all 30 workloads in the MOCCA dataset, for both time and cost optimization targets. When used inside CB, we used a default growth factor of 1 = 2 and varied the value of initial budget b = 1. ........ 8, which for the n providers in the dataset, results in total budget of B = 36, + 2b1 r + b1n a fair comparison terms of number of evaluations, when used as a standalone optimizer, each BBO was run by varying the budget between B = 11, 22, .... 88 evaluations. Default hyperparameters were used for BBOs, both when used inside CB and when used as a standalone optimizer, with the exception of BO with RF, where the hyperparameters from Bilal et al. (2020) were used. For each workload, optimization target and optimization algorithm, we performed 50 experiments using different random seeds. As evaluation metric we used the regret: the relative distance the true minimum, averaged over all seeds.
11b; evaluations. In order to ensure
Figure 2: Probability distribution functions (PDF) for a representative workload.
(a) Cost target
(b) Time target
O Cloud A Cloud B
Cloud A
Cloud Cloud
0.75
0.75
PDF
0.25
0,250
06
00
0.2
0.4
0.6
0.8
0
0.2
0.4
0.6
0.8
Normalized Cost
Normalized Time
In Table we present the average percentage regret, across all workloads in the MOCCA dataset, as function of the total number of evaluations. Results are provided for the cost optimization target in Table la and for the time optimization target in Table lb. For each pair of columns corresponding to given BBO, the lowest regret is highlighted in bold. From these results, we can make number of observations. Firstly, for all BBOs we observe significantly lower regret when the BBO is used as part of CB, relative to when it used by 20 percentage points (p.p.) for the cost target and by 7 p.p. for time. Secondly, we notice that RBFOpt appears to the best choice of component BBO for CB, consistently achieving the lowest regret across all budgets. Finally, the best algorithm (CB with RBFOpt) seems to converge to the true minimum faster for the cost target, relative to the time target. We believe this last observation is related to the fact that for the cost target, we typically see one provider that is significantly cheaper that the others, whereas for time the distributions for each provider have more overlap. Statistics are provided in Figure 2, for representative workload, to illustrate this characteristic. The sensitivity of CB to the overlap between distributions, as well as to the number of cloud providers, has been further investigated using a synthetic dataset in Appendix C.
standalone optimizer. On average, the regret is reduced
7

---

Under review as a conference paper at ICLR 2022
Table Average percentage regret of CB and component BBOs across all workloads in MOCCA.
(a) Optimization for cost
RS
BO with GP
BO with RF
RBFOpt
budget
alone
in CB
alone
in CB
alone
in CB
alone
in CB
11
87.85
48.01
120.83
54.33
93.75
53.60
66.66
48.01
22
47.91
30.76
38.90
33.56
70.14
27.74
32.93
18.11
33
33.33
18.65
25.79
18.07
62.29
18.27
17.78
6.99
44
24.49
13.56
20.65
12.43
56.54
12.17
12.99
0.53
55
18.71
7.48
18.26
9.94
51.04
9.11
9.29
0.18
66
14.36
4.75
16.40
8.58
46.04
6.42
5.65
0.05
77
11.59
2.61
15.90
7.53
43.06
4.72
4.28
0.00
8.11
2.51
15.58
7.19
40.82
3.81
2.28
0.00
(b) Optimization for time
RS
BO with GP
BO with RF
RBFOpt
budget
alone
in CB
alone
in CB
alone
in CB
alone
in CB
11
38.67
35.05
52.58
38.79
38.60
36.08
38.13
35.05
24.04
21.91
40.05
26.26
22.39
21.90
20.21
19.00
33
16.79
15.49
36.83
18.97
17.99
15.36
15.69
12.83
12.94
11.44
34.36
14.74
16.64
12.19
13.47
10.12
55
10.48
8.62
32.63
11.91
16.19
10.26
11.54
5.57
66
8.87
7.10
30.90
9.48
15.77
8.88
9.70
4.69
77
7.48
5.89
29.80
8.72
15.57
7.98
8.86
3.93
88
6.13
4.64
28.55
7.90
15.48
7.40
8.19
3.43
5.2
COMPARISON TO EXISTING AUTOML AND MULTI-CLOUD METHODS
While there have been a number of attempts to solve the multi-cloud configuration problem in the cloud literature, to the best of our knowledge, there is no publicly available code implementing the solutions from either Ramamurthy et al. (2020) Shi et al. (2020). On the AutoMI. side, SMAC is a highly active GitHub project, and can readily applied our problem and compared with CB. While in principle all of the solutions from Liu et al. (2020); Rakotoarison et al. (2019); ) Li et al. (2020) could also be used as baselines, none of the papers refer to publicly available implementations. Despite this, we have re-implemented the solutions from Li et al. (2020) (RB) and Ramamurthy et al. (2020) (RM) and included them as baselines.
We thus performed experiment to compare CB (with RBFOpt the component BBO) against SMAC, RB and R.M. As in the previous experiment, for CB we used default growth rate of 7 = and varied the initial budget bj 2, 8, leading range of total budgets For SMAC and RB we used default hyperparameters. For RM, which allows an arbitrary model to be used solve the inner configuration task, that the total number of evaluations coincided with the budget that was used for CB, We ran each algorithm with 50 different random seeds, for every workload and target from the MOCCA dataset. For each workload and target, we then computed the average regret across all random seeds.
11, 22, ... 88.
RBFOpt. The budget for all baselines was varied so
The percentage regret, averaged over all workloads, is presented in Table Additionally, for each algorithm we present the total accumulated cost (or time) incurred, averaged over all workloads. The cost/time normalized by the cost/time required for performing an exhaustive search. The winning results are highlighted in bold. From these results we can draw few interesting conclusions. Firstly, for the cost optimization target, CB out-performs SMAC, RB and RM in terms regret on average by 5 p.p., 16 p.p. and p.p. respectively. For larger budgets, SMAC and RM approach the performance CB in terms of regret, but incur respectively 57% and 56% higher cost on average. In fact, for budget 88, SMAC is equivalent to exhaustive search, since it does not try any configuration more than once. On the other hand, RB is around 45% cheaper than CB on average, but performs significantly worse in terms of regret, suggesting that the theoretical assumptions made by RB may
8

---

Under review as a conference paper at ICLR 2022
Table Average regret and normalized accumulated cost/time of CB and baselines.
(a) Optimization for cost
budget
regret
accumulated cost
CB
SMAC
RB
RM
CB
SMAC
RB
R.M
11
48.0
72.1
66.7
69.0
7.8
12.5
12.0
19.1
22
18.1
23.0
23.1
26.4
14.7
32.5
13.8
26.5
33
7.0
11.8
20.1
11.9
20.4
48.7
15.3
37.9
44
0.5
3.1
19.3
3.1
27.1
64.7
16.7
62.8
55
0.2
1.8
19.1
0.5
30.6
76.6
18.0
83.8
66
0.0
0.2
19.1
0.1
33.7
86.8
19.4
85.6
77
0.0
0.1
19.1
0.0
36.2
94.5
20.8
88.1
88
0.0
0.0
18.8
0.0
39.1
100.0
22.1
89.2
Optimization for time
budget
regret
accumulated time
CB
SMAC
RB
RM
CB
SMAC
RB
RM
11
35.0
38.1
41.9
37.9
11.9
13.0
12.9
15.0
22
19.0
18.7
28.4
18.5
22.8
28.5
20.2
26.6
33
12.8
14.7
26.1
14.3
32.7
42.7
25.5
39.4
44
10.1
8.0
25.1
12.2
43.0
56.2
30.5
56.4
55
5.6
4.5
24.0
7.1
51.9
68.5
35.3
68.2
66
4.7
2.3
23.5
4.4
61.0
80.1
40.0
73.7
77
3.9
1.1
23.0
4.3
67.3
90.3
44.6
79.7
88
3.4
0.0
22.5
3.5
74.2
100.0
49.2
82.5
not apply in this new application domain. Secondly, for the time optimization target, the average regret of CB comparable that RM (1 p.p. better on average) but at the same time CB is 18% faster. CB also performs similarly to SMAC in terms of regret for all but the highest budgets (1 p.p. worse on average), whilst being 22% faster. Equivalently the cost target, RB is 35% faster than CB on average, but in terms of regret, it is 15 p.p. worse on average.
5.3 FURTHER EXPERIMENTS
So far, the baseline models Section 5.2 were run using default hyperparameters. However, the HPs of SMAC and Rising Bandits were set to work well in a different domain. Therefore, we perform a further study of the algorithms' hyperparameters scenario in which the user wishes to receive more than one cloud provider recommendation at a time. We analyze and discuss CB's performance in this scenario, as well as a possible modification to the algorithm, in Appendix E. Finally, consider the dynamic nature of cloud's performance, i.c. dependence on the data center's load. We run experiments on selected workloads repeated multiple times, optimizing various statistical metries. We present the experimental results in Appendix F.
Furthermore, we consider Appendix
CONCLUSION
In this paper, we have presented a key connection between the model selection-configuee problem extensively studied the AutoMI. field and the multi-cloud configuration optimization task. Inspired by recent trends in AutoML, we have introduced CB, an algorithm for best-arm identification, that has been specifically designed with the multi-cloud configuration task mind. To evaluate the performance of CB, we have built and will open to the community first-of-a-kind benchmark dataset, MOCCA, comprising 60 multi-cloud configuration tasks across 3 public cloud providers. Our experimental results show that CB achieves lower regret MOCCA relative to variety of BBOs, and comparable or lower regret relative to sfte--ofthhe-a AutoML and multi-cloud solutions, whilst at the same time being either cheaper faster.

---

Under review as a conference paper at ICLR 2022
ETHICS STATEMENT
The algorithms described in this paper enable consumers and businesses to deploy large-scale workloads in multi-cloud setting in workloads, we acknowledge that societal concerns exist regarding safety, privacy, fairness and more. These concerns are often valid, and we acknowledge that helping scale ML workloads further and further may have an indirect, potentially negative, impact on the way ML models are used in society, On the positive side, we feel that helping people optimize their computing workloads across multiple cloud providers can have positive economic impact: helping to prevent the emergence of a large, all all-powerful monopoly in the ever-growing cloud industry.
cost-efficient way. In the particular case of ML-based
REPRODUCIBILITY STATEMENT
The MOCCA dataset and code to reproduce the tables from the paper have been prepared and ready to be shared publicly. We feel strongly about sharing these materials, so that others in the community can reproduce and improve upon our results. Unfortunately, our institution does not permit us to share code publicly (e.g. on OpenReview or GitHub) without clear indication of authorship. the paper is accepted, we will upload both the dataset and code, repository on public GitHub.
REFERENCES
Omid Alipourfard, Hongqiang Harry Liu, Jianshu Chen, Shivaram Venkataraman, Minlan Yu, and Ming Zhang. Cherrypick: Adaptively unearthing the best cloud configurations for big data analytics. In 14th USENIX Symposium on Networked Systems Design and Implementa- tion (NSDI 17), pp. 469-482, Boston, MA, March 2017. USENIX Association. ISBN 978-1- 931971-37-9. URL https: www..usente xx http://oooeeeeeeeen/n//////eeeee cal sessions sessions/
Alessio Benavoli, Giorgio Corani, and Francesca Mangili. Should we really use post-hoc tests based mean-ranks? Journal of Machine Learning Research, 17(5)1-10, 2016. URL http: //jmlr.... org/ http://pppsssss///////ss http://///eavlllleeeeee 6a html.
Muhammad Bilal, Marco Serafini, Marco Canini, and Rodrigo Rodrigues. Do the best cloud configurations grow trees? An experimental evaluation of black box algorithms for optimizing cloud workloads. Proc. VLDB Endow., 13(1)):2563-22 2575, July 2020. ISSN 2150-8097, doi:
10.14778/34079903407755 URL https: / doi org/ 10
3407790 3407845.
Eric Brewer. An update container support google cloud platform, 2014. https:
//cloudpaatfoommmopeeo/. wttp://rww.ooooooooooooooooooooe wttp:////////////// http//////nuuaaeeee ottp://nn-upaat-----oootaaaaaaaa -o--oontainne- auppott-oor-poogle--ooo---p-ppae
html, accessed: 5.10.2021.
Lingjiao Chen, Matei Zaharia, and James Zou. Frugalml: How use ml prediction apis more accurately and cheaply, 06 2020.
Yanjiao Chen, Long Lin, Baochun Li, Qian Wang. and Qian Zhang. Silhouette: Efficient cloud
configuration exploration for large-scale analytics. IEEE Transactions Parallel and Distributed Systems, 32(8):2049-206 2021. doi: 10. 109/TPDS 2021 1.3058165..
Alberto Costa and Giacomo Nannicini. Rbfopt: an open-source library for black-box optimization with costly function evaluations. Mathematical Programming Computation, 10(4):597-629, 2018.
Dask Development Team. Dask: Library dynamic task scheduling, 2016. URL https: dask. org.
Janez Demšar. Statistical comparisons of classifiers over multiple data sets. Journal of Machine learning research, 70Jan):1-30, 2006.
Nick Erickson, Jonas Mueller, Alexander Shirkov, Hang Zhang, Pedro Larroy, Mu Li, and Alexander Smola. Autogluon Autogluon-tabular: tabular: Robust and accurate automl for structured data. arXiv preprint arXiv:2003. 00650500..005 2020.
10

---

Under review as a conference paper at ICLR 2022
Stefan Falkner, Aaron Klein, and Frank Hutter. Bohb: Robust and efficient hyperparameter opti- mization at scale. In International Conference on Machine Learning. pp. 1437-1446. PMLR, 2018.
Matthias Feurer, Aaron Klein, Katharina Eggensperger, Jost Tobias Springenberg, Manuel Blum, and Frank Hutter. Auto-skleam: efficient and robust automated machine learning. In Automated Machine Learning, pp. 113-134. Springer, Cham, 2019.
Gartner. Gartner forecasts worldwide public cloud end-user spending grow 23% in 2021, 2021.
wtw.aaatteerreeeeeeeaeeeooaoeeee www//e///////cc /ewss/nwwoommmmm wwtps/rrwoo/peeo/eeeeeeeeeeeeeee eaweleeaee//eeee wawsse/222--aae 21 21-gartner- forecasts wor www.ww...wwwwwuwwwdwweeee-e pesee-puliic-e oud oud-end-user--pendde to 2o-grow-22 2w----2e--eeeee---eee in- 2021, accessed: 27.05.2021.
http://wwwwwwwatte.ecoco
H-M Gutmann. A radial basis function method for global optimization. Journal of global optimization,
1933)2011227,
Samar Haytamy and Fatma Omara. Enhanced qos-based service composition approach in multi-cloud environment. In 2020 International Conference on Innovative Trends in Communication and Computer Engineering (ITCE), pp. 33-38, 2020. doi: (TL.:///TTTEAA000000000000000
Chin-Jung Hsu, Vivek Nair, Vincent W. Frech, and Tim Menzies. Arrow: Low-level augmented bayesian optimization for finding the best cloud vm. In 2018 IEEE 38th International Conference on Distributed Computing Systems (ICDCS), pp. 660-670, 201 8a. doi: 10. 10.1109// 2012200008000 8.00070.
Chin-Jung Hsu, Vivek Nair, Tim Menzies, and Vincent Frech. Micky; cheaper alternative for selecting cloud instances. In 2018 IEEE I 11th International Conference on Cloud Computing (CLOUD), pp. 409-416, 2018b. doi: 10. 109/CLOUD. 20018.0005..
Chin-Jung Hsu, Vivek Nair, Tim Menzies, and Vincent W Freeh. Scout: An experienced guide to find the best cloud configuration. arXiv preprint Att.:/800302299 2018c.
Frank Hutter, Holger H. Hoos, and Kevin Leyton-Brown Sequential model-based optimization for the 5th International Conference on Learning and Intelligent Optimization, LION'05, pp. 507-523, Berlin, Heidelberg, 2011. Springer- Verlag.. ISBN 9783642255656. doi: 1007 9000/978--00 642 -2-422-5555555 20122225566222 40.
general algorithm configuration. Proceedings the
URL https: /ooi http//ooo.oogg/././////// org/10.
Ronald L Iman and James M Davenport. Approximations of the critical region of the friedman statistic. Communications in Statistics-Theory and Methods, (6):571-555, 1980.
Kevin Jamieson and Ameet Talwalkar. Non-stochastic best arm identification and hyperparameter optimization. In Artificial Intelligence and Statistics, pp. 240-248. PMLR, 2016.
Kaggle. Credit card fraud detection, 2018. https: /ttp:///wwwww... http://wwwwllll..cm/llllee//e/ee creditcardfraud.
Kaggle. Santander customer transaction prediction, 2019.
Zohar Karnin, Tomer Koren, and Oren Somekh. Almost optimal exploration in multi-armed bandits. In International Conference on Machine Learning, pp. 1238-1246 PMLR, 2013.
Kawala, A. DouzaalChouakria, E. Gaussier, and E. Dimert. Prédictions d' d'activité dans les réseaux sociaux ligne. In Actes de la Conférence sur les Modèles et l l'Analyse des Réseaux Approches Mathématiques et Informatique (MARAMI), pp. 16, 2013. setp://archhe ics uci edu/ml / Raaitt//uuzzzz
Buzz+ Puzztintsost +medi at.
Erin LeDell and Sebastien Poirier. H2o automl: Scalable automatic machine learning. In Proceedings of the AutoMI. Workshop at ICML., volume 2020, 2020.
Jianjun David Li. A two-step rejection procedure for testing multiple hypotheses. Journal of Statistical Planning and Inference, 1521)175 2008
11

---

Under review as a conference paper at ICLR 2022
Liam Li and Ameet Talwalkar. Random search and reproducibility for neural architecture search. In Uncertainty in Artificial Intelligence, pp. 367-377. 367-377.PMLR, 2020.
Lisha Li, Kevin Jamieson, Giulia DeSalvo, Afshin Rostamizadeh, and Ameet Talwalkar. Hyperband: A novel bandit-based approach to hyperparameter optimization. J. Mach. Learn. Res., 18(1): 6765-6816, 16, January 2017. ISSN 1532-4435.
Yang Li, Jiawei Jiang, Jinyang Gao, Yingxia Shao, Ce Zhang, and Bin Cui. Efficient automatic cash via rising bandits. Proceedings of the AAAI Conference on Artificial Intelligence, 34(04): 4763-4771, Apr. 2020. doi: 111609/aaii.334444.... index. paddex.ppp/// AAAIAAAAAAAA http///rriieeeviiiiee 5910.
URL https: wwwpjj.aaaiioooo.oo..o.ooo
Marius Lindaner, Katharina Eggensperger, Matthias Feurer, André Biedenkapp, Difan Deng, Carolin Benjamins, René Sass, and Frank Hutter. Smac3: A versatile bayesian optimization package for hyperparameter optimization. arXiv preprint arXiv:2109.0985 09831, 2021.
Sijia Liu, Parikshit Ram, Deepak Vijaykeerthy. Djallel Bouneffouf, Gregory Bramble, Horst Samu- lowitz, Dakuo Wang, Andrew Conn, and Alexander G. Gray. An ADMM based framework Artificial Intelli-
for automl pipeline configuration. In The Thirly-Fourte AAAI Conference gence, AAAI 2020, The Thirty-Second Innovative Applications of Artificial Intelligence Conference, IAAI 2020, The Tenth AAAI Symposium on Educational Adyances in Artificial Intelligence, EAAI 2020, New York, NY, USA, February 7-12, 2020, pp. 4892-4899, AAAI Press, 2020. URL https: / aaaaaaaa..........aa.aaaaa...... org/ o jss// index. phtp /AA.AAAAAAAAAA// wtAa///atiee//veeeeaa.
Gilles Louppe. Bayesian optimisation with scikit-optimize. 2017.
Ashraf Mahgoub, Alexander Michaelson Medoff, Rakesh Kumar, Subrata Mitra, Ana Klimovic, Somali Chaterji, and Saurabh Bagchi. OPTIMUSCLOUD: Heterogeneous configuration opti- mization for distributed databases in the cloud. In 2020 USENIX Annuul Technical Conference (USENIX ATC 20), pp. 189-203. USENIX Association, July 2020. ISBN 978-1-939133-144 URL wwwph:tpp//.... / www. usenix x. org/ http://oooeeeeeeatccccoo http://tttt2epppeeetttttte itwpeetateettteeeeee on mahgoub.
Giovanni Mariani, Andreea Anghel, Rik Jongerius, and Gero Dittmann. Predicting cloud performance for hpe applications: A user-oriented approach. In 2017 17th IEEE/ACM International Symposium Cluster, Cloud and Grid Computing (CCGRID), pp. 524-533, 2017. doi: 10.1 109/CCGRID. 2017.11.
Dirk Merkel. Docker: Lightweight linux containers for consistent development and deployment. Linux J., 2014(239), March 2014. ISSN 1075-3583.
Giacomo Nannicini. On the implementation of a global optimization method for mixed-variable problems. arXiv preprint urXiv:2009.02183, 2020.
Randal Olson and Jason H Moore. Tpot: A tree-based pipeline optimization tool for automating
machine learning. In Workshop on automatic machine learning, pp. 66-74. PMLR, 2016.
Beibei Pang, Fei Hao, Doo-Soon Park, and Carmen De Maio. A multi-criteria multi-cloud service composition in mobile edge computing. Sustainabiliry, 12(18), 2020. ISSN 2051-1050. doi: 223390/su12187660 URL https: / www. . mddpi...... com 100011115001211//1711
Herilalaina Rakotoarison, Mare Schoenauer, and Michèle Sebag. Automated machine learning with monte-carlo tree search. In Proceedings of the Tienty-Eighth International Joint Conference on Artificial Intelligence, IJCAI-19, pp. 3296-3303. International Joint Conferences on Artificial Intelligence Organization, 2019. doi: 10. 10.24963/ijeai.2019/4457 URL https::/doi. org/ 10. 24962496334 / wwi.aiic22.11 /477
Arun Ramamurthy, Saket Saurabh, Mangesh Gharote, and Sachin Lodha. Selection of cloud service providers for hosting web applications in multi-cloud environment. In 2020 IEEE International Conference on Services Computing (SCC), pp. 202-209, 2020. doi: 10.1 1 109/SCC49933..0020, 00034.
Tao Shi, Hui Ma, Gang Chen, and Sven Hartmann. Location- and budget- conttrreed service deployment for composite applications in multi-cloud environment. IEEE Transactions on Parallel and Distributed Systems,
2020. doi: 10. 2920..2S..02002911111
12

---

Under review as a conference paper at ICLR 2022
Jasper Snoek, Hugo Larochelle, and Ryan P Adams. Practical bayesian optimization of machine learning algorithms. arXiv preprint arXiv:1206. 2944, 2012.
Stephen Soltesz, Herbert Pötzl, Mare E. Fiuczynski, Andy Bavier, and Larry Peterson. Container- based operating system virtualization: A scalable, high-performance alternative to hypervisors. SIGOPS Oper. Syst. Rev, (1(3)2775-287, March 2007. ISSN 0163-5980. doi: 10.1145/1272998. 1273025. URL https: /wwi www//0..........o...ooo.o.. 11151........... 1145/12722221
1273025.
Alireza Souri, Amir Masoud Rahmani, Nima Jafari Navimipour, and Reza Rezaei. hybrid formal verification approach for qos-aware multi-cloud service composition. Clust. Comput., 23(4): 2453 2470, 2020. doi: 10.1007/100886-099400 s10586-
URL https: http:///d..ooo/..100000o
Chris Thornton, Frank Hutter, Holger H Hoos, and Kevin Leyton-Brown. Auto-weka: Combined selection and hyperparameter optimization of classification algorithms. In Proceedings of the 19th ACM SIGKDD international conference on Knowledge discovery and data mining, pp. 847-855, 2013.
Neeraja J. Yadwadkar, Bharath Hariharan, Joseph Gonzalez, Burton Smith, and Randy H. Katz. Selecting the best across multiple public clouds: A data-driven performance modeling approach. In Proceedings of the 2017 Symposium on Cloud Computing, SoCC '17, pp. 452-465, New York, NY, USA, 2017a. Association for Computing Machinery. ISBN 9781450350280, doi: 10.1145/3127479.313666 URL https:: htt/ddii.rgg/////
Neeraja J Yadwadkar, Bharath Hariharan, Joseph E Gonzalez, Burton Smith, and Randy H Katz. Selecting the best vm across multiple public clouds: data-driven performance modeling approach. In Proceedings of the 2017 Symposium on Cloud Computing, pp. 452-465, 2017b.
A DETAILS OF THE MOCCA DATASET
In Table we present the details of Dask tasks, input datasets and optimization targets included the MOCCA dataset.
Table Details of the optimization tasks used in the dataset.
Optimization targets
Dask tasks
Datasets
kmeans
polynomial features santander (Kaggle, 2019)
cost
linear regression
quantile transformer
credit card (Kaggle, 2018)
runtime
logistic regression
spectral clustering
buzz in social media
naive bayes
standard scaler
(Kawala et al., 2013)
poisson regression
xgboost
B CONTINUOUS CLOUDBANDIT
In Section 3 we have described the CloudBandit algorithm which may come in two variants: continu- (in each round, CloudBandit utilizes all previously-evaluated configurations by passing them on to the component BBO) or intermittent (the component optimizer is independent in each round and does not utilize any of the previously-evaluated configurations). In Section we have presented the experimental results for the latter variant. In this section we will present the results for the continuous variant too.
B. IMPLEMENTATION CHALLENGES
It is necessary note that depending the BBO used, sometimes implementing the continuous variant of CloudBandit may be difficult or impossible. Some BBOs, e.g. Random Search, are conceptually unable to utilize any information about past configuration evaluations at all. In other
13

---

Under review as a conference paper at ICLR 2022
cases, using continuous CB can be impossible due to the optimizer's incompatible API, which e.g. does not allow the user to pass previous evaluations or to extract evaluations from the current round.
In cases when the BBO's API is incompatible, may be possible to find a workaround. An example of such case is RBFOpt, which does not allow the user to extract all the configurations evaluated by the optimizer. They can only be extracted an encoded form used internally by the optimizer. In order adjust RBFOpt to be used with the continuous CloudBandit scheme, one use an additional wrapper that was developed for the NeurlPS 2020 BBO Challenge The wrapper utilizes synchronization primitives in order to pause and resume the optimization process, feeding one evaluation at a time. This way, all configurations can be collected and passed to the optimizer in later CB rounds.
B.2
COMPARISON AGAINST INTERMITTENT CLOUDBANDIT
Table 4: Average ranks of continuous and intermittent CloudBandit.
(a) Optimization for cost
CB BO with GP
CB BO with RF
CB RBFOpt
budget
intermittent
continuous
intermittent
continuous
intermittent
continuous
11
3.23
3.13
4.13
4.67
3.33
1.60
22
4.13
4.13
3.70
4.83
2.20
1.00
33
4.00
3.03
4.97
5.70
1,83
1.00
44
3.50
2.67
4.90
5.80
1.27
1.00
55
3.33
2.80
4.87
5.67
1.13
1.00
66
3.37
2,50
4.63
5.73
1.07
1.10
77
3.03
2.53
4.83
5.53
1.10
1.10
88
3.03
2.47
4.90
5.23
1.10
1.13
(b) Optimization for time
CB BO with GP
CB BO with RF
CB RBFOpt
budget
intermittent
continuous
intermittent
continuous
intermittent
continuous
11
4.00
4.00
3.30
3.07
2.73
3.03
22
4.40
4.33
3.77
3.77
2.10
1.77
33
4.87
4.50
3.73
4.17
2.23
1.50
44
4.67
3,83
3.97
5.00
1.87
1.53
55
4.30
3.73
4.17
5.13
1.70
1.73
66
3.73
3.83
4.20
5,53
1.77
1.57
77
3.73
3.37
4.30
5.57
1.50
1.53
88
3.37
3.10
4.43
5.57
1.47
1.40
In Tables 4a and 4b present the average ranks of the continuous CloudBandit scheme compared against the corresponding intermittent scheme for different component BBOs. The ranks were determined based all algorithmss' results averaged over 50 random seeds and all workloads in the MOCCA dataset. Random Search was excluded as a component BBO in this study, since intermittent and continuous CloudBandit are identical by construction. Best results within each pair of continuous and intermittent CloudBandit with the same BBO are highlighted in bold.
When comparing a number of optimization algorithms across large collection of tasks, rather than applying parametric statistical tests (such as Student's t-test) on a per-task basis, Demšar (2006)
argues that it is preferable to perform non non-paramen parameeri
across the collection.
In this case, we have family of 6 optimization algorithms ranked across 60 different multi-clo cooii--cood con- figuration tasks (30 workloads with cost optimization target and 30 workloads with time optimization target), for 8 different budgets. In order to verify that statistical differences exist within the family,
hhaps//tboochalleng.ccom/
14

---

Under review as a conference paper at ICLR 2022
Table Pairwise p-values comparing continuous vs, intermittent CB. (a) Optimization for cost
Intermittent vs. Continuous CB
Budget
BO with GP
BO with RF
RBFOpt
11
2.20c-01
6.02e-02
1.09c-03
22
5.00e-01
1.38e-03
1.73e-06
33
5,18e-04
1.02e-03
1.24e-05
44
9,90e-05
4.87e-05
4.49e-02
55
2.95e-02
1.94e-03
1.85e-01
66
2.31e-03
2.59e-04
4.96e-01
77
1.87e-02
8.65c-03
5,00e-01
88
2.35e-02
2.26c-01
4.96c-01
(b) Optimization for time
Intermittent vs. Continuous CB
Budget
BO with GP
BO with RF
RBFOpt
11
5.00e-01
2.62e-01
4.26e-01
22
3.11e-01
3.83e-01
1.66e-01
33
8.53e-02
6,93e-02
1,63e-02
44
2.40e-03
1.55e-03
2.23e-01
55
1.98e-02
1.85e-03
4.24e-01
66
3.37e-01
1.21e-04
1.86e-01
77
1.18e-01
1.57e-05
4.79e-01
88
2.24e-01
1.85e-05
3.87e-01
we first apply the correction of the Friedman omnibus test proposed in Iman & Davenport (1980). We were able to firmly reject the family-wise null hypothesis (via the omnibus test) with p < 0.004 for all budgets, and both time and cost optimization targets. Secondly, we perform pairwise testing using the Wilcoxon signed-rank test (Benavoli et al., 2016) (correcting for multiple hypotheses via the procedure defined in (2008)) to verify differences exist between the optimization algorithms themselves. The pairwise p-values are presented in Table 5a and Table 5b. The cases for which the null hypothesis can't rejected (p < 0.05) are highlighted in red.
When using BO with GP the component BBO, find that the continuous variant improves the average rank in a majority of cases. For the cost-based target, the p-values suggest that this improvement is statistically significant, whereas for the time-based target the null hypothesis cannot be rejected most of the time. For BO with RF, we find that the continuous variant results worse performance relative to the intermittent variant. Furthermore, the p-values suggest this worsening statistically significant. One explanation for this could be that for BO with RF the number of initial random evaluations in the component BBO was to following the best hyperparameters identified in Bilal et al. (2020), whereas for BO with GP the number of initial random evaluations is set to 10. may be that using fewer random evaluations results in less exploration and more exploitation, leading to convergence to local minima, and the continuous variant amplifies this effect. Finally, for RBFOpt with a time-based target, while we see the average rank improve in many cases, the p-values suggest these differences not statistically significant. However, for the cost-based target we do see a statistically significant improvement the average rank for lower budgets.
In conclusion, while we do see an improvement from the continuous variant in some scenarios, there are others where it clearly makes things worse, and others still where statistical differences do not seem be present. Since significant technical work may be needed to get the continuous variant working for some component BBOs (as described Section B. we opted to present the simpler intermittent scheme in the main manuscript.
15

---

Under review as a conference paper at ICLR 2022
C SENSITIVITY ANALYSIS
We performed an analysis of how sensitive CloudBandit's results are, both to the search space distribution, as well the number of providers. In those experiments, we compared ranks of standalone Random Search and CloudBandit using Random Search as the component BBO, calculated by averaging results over multiple random seeds. To be able to simulate various scenarios, the sensitivity experiments were conducted using a synthetic dataset. Each provider was assumed to produce random results drawn from a normal distribution (U4,,")
Table 6: Average ranks of RS and CB with RS for various scenarios run on synthetic dataset.
(a) Varying standard deviation ø
(b) Varying number of providers n
Random Search
Random Search
0
71
alone
in CB
alone
in CB
1000
1.34
1.33
12
1.84
1.08
100
1.34
1.33
10
1.81
1.10
10
1.38
1.33
8
1.78
1.11
5
1.41
1.31
6
1.71
1.14
2
1.49
1.24
5
1.68
1.15
1
1.54
1.18
4
1.62
1.17
0.1
1,56
1.16
3
1.54
1.18
2
1.39
1.18
C.I SEARCH SPACE DISTRIBUTION
In this experiment, we assume n = 3 providers and the means of the providers' distributions were fixed as μ4 = i for i = 0, ..... 1. We were then able to manipulate the overlap between providers' distributions by changing the standard deviation o of the distributions. In Table 6a we present the average ranks of CB with RS and standalone RS for various standard deviations a. As expected, for small values of a, i.e., when the distributions have almost no overlap. CloudBandit gives clearly better results than standalone Random Search. For big values of a, where the distributions significantly overlap, we can observe that CloudBandit still wins over standalone RS. However, the difference between average ranks of the two methods is less significant than for small values of a.
The results presented in Table 6a allow us to explain why CloudBandit gives better results on the MOCCA dataset when optimizing for cost than case of optimizing for time, as presented in Tables la and 1b. As presented in Figures 2a and 2b, in practice the providers' distributions show bigger overlap for runtime measurements than in terms of cost.
C.2 NUMBER OF PROVIDERS
We further evaluated CloudBandit's results for various numbers of providers n. In this experiment, each case has a radically different search space size because of the varying number of providers. Therefore, instead of using the same total budget for each test case, fix the initial budget of CloudBandit to bj = 8. The average ranks of CloudBandit with RS and standalone RS are presented in Table 6b. In cases where many providers were available, CloudBandit has a significant advantage over standalone Random Search. The difference between the methods decreases with the decline in the number of providers, as each arm rejection in CloudBandit carries ever higher risk. However, for only 2 providers, CloudBandit gives better results than Random Search.
should be noted that CloudBandit's complexity grows rapidly with the growing number of providers. A possible solution to this issue could be to reject more than one provider at the end of each round in order to reduce the number of rounds needed. This possible modification could motivate future work on CloudBandit.
16

---

Under review as a conference paper at ICLR 2022
D HYPERPARAMETER TUNING
In the previous experiment, default hyperparameters (HPs) were used for both AutoMI. baselines: SMAC and RB, and a default growth rate of was used for CB, alongside default HPs for the component RBFOpt. Since the defaults for SMAC and RB were determined for a different application, it is necessary to check whether their performance, well as that of CB, can be improved by HP tuning.
To achieve this, made 67%/33% validation/test split of the workloads from MOCCA. For each of the three algorithms, we defined a HP grid of equal size. The budget for all algorithms was fixed to 33. We then performed grid search optimize the HPs: identifying the HP configuration that achieved the lowest average regret on the validation set. For each algorithm, the best configuration was then evaluated on the test set.
Table 7: Average regret using default and tuned hyperparameters.
optimization
CB
SMAC
RB
HP setting
target
val
test
val
test
val
test
best default
1.20
0.19
5.14
25.05
10.02
30.95
cost
3.50
13.96
5.14
25.05
10.77
38.74
best default
11.69
11.52
12.64
11.75
20.23
22.13
time
13.48
11.53
14.60
14.84
26.04
26.23
Table 8: Detailed test results for CloudBandit and AutoML algorithms.
Optimization for cost
Optimization for time
workload
CB
SMAC
RB
CB
SMAC
RB
buzz-polynomial_feee features
1.88
0.47
1.49
0.35
1.48
6.11
buzz-spectral classterinn
0.00
0.49
1.92
7.91
2.54
17.70
buzz-xgboost
0.00
0.00
0.39
88.97
86.86
138.81
creditcard-naive bayes
0.00
4.28
22.04
6.18
5.41
9.77
crediccard-standard_saall
0.00
24.79
20.80
0.92
2.89
4.71
contander-mmeann
0.00
3,23
3.19
1.57
3.90
7.46
santander-linee waaperliicaarrereeeeeeeeeeee regression
0.00
1.44
8.41
1.28
2.17
4.77
contander-poisoor reegressinnnesnonnnnno
0.00
195.28
239.53
1.71
1.94
4.34
santander-quantile transformer
0.00
20.53
11.31
0.68
2.44
3.57
santander-xgboost
0.00
0.00
0.39
5.59
7.90
24.01
Table 9: Hyperparameter search space for each of the compared algorithms.
best setting
best setting for time
algorithm
parameter
values
for cost
bj rbf
1, 2, 3, 4, cubic, linear, gaussian Gutmann, MSRSM
CB
linear Gutmann
gaussian Gutmann
algorithm
mode oot__challengers
SMAC4HPO, SMAC4AC 50, 500, 5000 0.1, 0.3, 0.5, 0.7,
SMAC4HPO
SMAC4AC
SMAC
acq acq_opttchee rand_prof
500
500
0.5
0.5
estimator n_init acq_func
RF. GP
GP
RF
RB
2, 10, 12, 15
15
15
LCB, Pl, EI
P[
El
The results are presented Table 7 which shows the average regret, on both the validation set and test set, for each of the three algorithms, using both the default and tuned HPs. We see that, in most cases,
17

---

Under review as a conference paper at ICLR 2022
HPP tuning helped to improve the average regret the test set, relative to the default HPs. However, there is no change in the relative order of the algorithms, both for the cost, as well as for the time optimization target. Additionally, in Table 8 we list the average test scores of best HP configurations of all 3 3 algorithms, individually for each test workload. The winning results for each workload and optimization target were highlighted in bold. Finally, Table 9 lists all hyperparameters tuned for each algorithm, together with value ranges and best configurations selected for both optimization targets.
E BEST-k ARMS SELECTION
Another extension of CloudBandit is a scenario which the user wishes to receive more than one cloud recommendation at time and choose themself which provider they wish to use. Specifically, we focus on a case which & = 2 best providers (and their best configurations) are to be identified. This can be achieved by running the traditional 1-best-arm identification CloudBandit scheme as presented in Section 3. and suggesting 2 best providers found throughout the optimization process (the arms that survived up to round 1). However, this approach treats the suggested arms unfairly, as one of the arms receives a significant additional evaluation budget in the final round. To solve this issue, simple and effective modification of CloudBandit for this scenario can be the 2-best-arms scheme, which stops the algorithm when the size of the set of active arms A is down to k = 2 arms, so that both candidates are treated equally budget-wise.
In order to evaluate CloudBandit's performance in this scenario, we run both schemes described above on the MOCCA dataset, this time expecting 2 arm candidates each time. We ensure fair comparison by setting equal total evaluation budgets (identical starting budgest by and different growth factors " = 2, 1) = for 1-best-arm and 2-best-arms schemes, respectively). Table 10 presents the average regrets of both the traditional 1-best-arm CB scheme and the 2-best-arms scheme. The regrets of the first (better) candidates (denoted as option in Table 10) were calculated with respect to the true minimum of the MOCCA dataset, similarly to Section 5. The regrets of the second (worse) candidates (denoted as option 2) were calculated with respect to the minimum over all providers except for the one which gives the true minimum. The better result across CB schemes for each candidate is highlighted in bold. The results for both optimization targets were averaged over 50 random seeds and all 30 workloads. As the component BBO, we use RBFOpt both cases.
Table 10: Average regrets of 2 best provider candidates for 1 1-best-arm and 2-best-arms CB schemes.
Optimization for cost
Optimization for time
budget
2-best-arms
1-best-arm
2-best-arms
1-best-arm
option
option
option
option 2
option
option 2
option
option 2
11
58.74
96.33
48.01
128.77
34.79
46.56
35.05
63.29
22
21.70
21.21
18.11
72.61
18.59
24.17
19.00
38.27
33
9.03
15.06
6.99
32.94
13.59
16.91
12.83
26.33
44
0.64
11.50
0.53
17.05
9.82
13.84
10.12
19.41
55
0.18
6.20
0.18
11.33
5.34
11.10
5.57
15.00
66
0.00
2.39
0.05
9.22
4.18
8.20
4.69
11.40
77 0.00
0.88
0.00
8.18
3.41
6.48
3.93
8.89
88
0.00
0.41
0.00
7.21
2.51
4.73
3.43
7.07
The 2-best-arms scheme gives much better second candidates for both optimization targets, which was expected, as this scheme devotes a bigger budget to the second best arm. For the cost optimization target, the 1-best-arm scheme produces comparable or better first candidates than the 2-best-arms scheme for most budgets. However, for the runtime optimization target, the 2-best-arms scheme produces better first candidates than the 1-best-arm scheme, although it gives a smaller evaluation budget to the winning arm. As was shown in Figure 2b, there significant overlap between providers' distributions for the runtime optimization target. Better results of the 2-best-arms scheme for this optimization target may indicate that when there too much overlap between providers' distributions, the regular 1-best-arm CloudBandit scheme sometimes reject providers too aggres- sively. In such cases, CloudBandit may therefore benefit from keeping more than one provider the final optimization round.
18

---

Under review as a conference paper at ICLR 2022
F DYNAMIC EFFECTS
One of important issues the cloud is the dynamic nature of performance, which may differ depending the load on the data center any given instant. The tail effects (worst scenario results) are of special interest from the users' perspective, so that their workloads are guaranteed not exceed some acceptable limits.
To analyze CloudBandit's performance in the dynamic environment, we re-run some of the workloads from MOCCA multiple times. For this experiment, chose the 5 fastest workloads, they should be the most susceptible to tail effects. We consider various statistical metrics that can be used by CloudBandit the optimization metric: the mean, median and 90th percentile of results used by Yadwadkar et al. (2017b) (b)). The experiments were run for the time optimization target and repeated over multiple random seeds.
Table 11 compares the average regrets of CloudBandit with RBFOpt and standalone RBFOpt for the analyzed statistical metries. Additionally, Figures 3a-3c present the probability distribution functions (PDFs) of the analyzed metrics of all 3 cloud providers for representative workload. We can see that despite differences between the PDFs of the analyzed statistical metrics, CloudBandit's results comparable for all of them. This confirms that CloudBandit can be used universally, regardless of the metric interest.
Figure 3: PDFs of various statistical metrics for a representative workload.
Provider
(h) Provider B
0.5
0.5
- Meeni
Meen
Medien
Median
0.3
0.3
0.1
0.1
6
10
14
10
14
Runtime (s)
Runtime (5)
(c) Provider C
Median
0.4
BD- th Percentie
0.2
0.1
10
Runtime (8)
Table 11: Average regrets CloudBandit using various statistical metrics the data.
budget
mean
median
90th percentile
RBFOpt
CB
RBFOpt
CB
RBFOpt
CB
11
21.45
17.25
19.98
16.54
23.53
19.59
12.72
8.03
11.25
8.51
14.18
8.81
33
8.79
6.24
8.42
5.97
10.64
6.74
7.04
4.20
6.97
4.66
8.57
4.83
55
6.06
3.81
5.39
3.80
7.25
4.21
5.29
2.69
4,45
3,01
5.99
3.23
77
4.23
2.11
3,88
2.01
5.17
1.98
3.86
1.67
3.33
1.42
4.41
1.45
19


Reviews:
[{"review_id": "yZUHitx76h", "reviewer": "Reviewer_mcUn", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 5, "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": "Overall, the motivation and idea presented in the paper is clear. However, it is significantly missing in details wrt to datasets, experiments and cloud provider configuration space. \n\nI would implore authors to think about following limitations of the work that should be addressed (and possibly their future work):\n\n1. Taskset: Tasks in the current work only consist of ML-workloads which are algorithmically fixed, i.e., there is little to no control flow/branching. \n\n2. Dynamic environment: How will the results change across the cloud providers if the cloud itself is heavily loaded. Tail latency is a big issue in the cloud environment. See \"Selecting the Best VM across Multiple Public Clouds: A Data-Driven Performance Modeling Approach\" published in SOCC 17.\n\n3. Moving away from black-box assumption: There is no requirement in this task to be workload agnostic, i.e., the users of the CloudBandit should have access to the workload and should be able to leverage insights from workload details (such as memory required, code complexity, processor, etc). One can obtain such details by profiling and tracing of the code and execution environment. Roofline models (see https://en.wikipedia.org/wiki/Roofline_model) should also help model aspects of the code and execution environment to significant reduce the accumulated cost while providing great performance. ", "summary_of_the_paper": "This pager presents CloudBandit to solve the multi-cloud selection-configuration problem. While the problem is heavily explored in several domains, this paper leverages the hierarchical aspect of the selection-configuration problem. The main novelty of the paper lies in creating the dataset for the above problem. Such dataset can be immensely useful for academic research as \"executing code\" in cloud can be prohibitively expensive in academic settings; thereby, hindering the academic research.", "summary_of_the_review": "Overall, the paper is well written. However, several aspects of the problem were ignored (see main review). The dataset presented could be meaningful but currently it lacks the rigor in generating the dataset or providing meaningful motivation for selecting \"dask\" tasks. This paper has the seed for significant contribution but the current quality of work is not sufficient for publication in a conference.", "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": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "wkuXpqwLxo", "reviewer": "Reviewer_bhwc", "summary": "", "questions": "", "limitations": "", "rating": 5, "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": "Strengths\n=========\n1. The paper discusses a direction of research which will become more and more relevant in the years to come. As such this paper may inspire future researchers to work on the problem of multi-cloud configuration which will enable customers to minimize runtime and cost while running workloads on clouds provided by multiple vendors, without explicitly having to choose one vendor over another. \n2. The paper draws an analogy to AutoML and uses some of the concepts to come up with a novel approach based on best-arm identification problem. This is one of the key contributions of the paper.\n3.  Another major contribution of the paper is the release of the multi-cloud configuration dataset which will be made publicly available. In line with my comment above this will further enable researchers to work on this area and make further inroads.\n4. The experimental section appears very detailed. The authors have compared the use of different BBOs (black box optimizers) inside CB. The comparison has been done for both cost and runtime targets. However the 2nd part of the experimental section has some weakness as described under “weaknesses”.\n\nWeaknesses\n===========\n1. The main algorithm for optimisation viz. CloudBandit appears to be a simple extension of existing approaches and does not seem to have enough novelty (considering the exclusiveness of ICLR)\n2. Although there are multiple similar approaches the authors have run experiments against only 2 baselines viz. SMAC and RB. The authors argue that other approaches cannot be compared against as there is no public implementations available.Thus it not clear how this method compares against the SOTA approaches. \n\n", "summary_of_the_paper": "he paper  provides a solution for multi-cloud configuration problem. Specifically, the paper tries to provide cloud customers with an optimal configuration to minimise runtime and cost. The paper also presents a dataset, for offline benchmarking, comprising of 60 different multi-cloud configuration tasks across 3 cloud service providers. ", "summary_of_the_review": "The authors have done a commendable job in a very relevant research area which will become more prominent in the coming years. The key contributions are: 1) CloudBandit a best-arm identification problem for multi-cloud configuration optimization. and 2) the public release of a multi-cloud configuration dataset. \nHowever the novelty does not seem to be adequate keeping in mind the standards of the conference. Also there are some weaknesses in the evaluation results and the comparision with SOTA is not clear.", "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": "eCiQble3fDb", "reviewer": "Reviewer_FdKV", "summary": "", "questions": "", "limitations": "", "rating": 5, "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": "The pros: 1) The authors firstly build a benchmark for the multi-cloud configuration task. 2) they evaluate the proposed methods comprehensively, compared to BBOs and other AutoML methods. \nThe cons and questions：1) Can you justify the dataset is correct? Because it is an imperfect estimate, and the more precise estimates are difficult to obtain for the cost target. Does the dataset consider the different prices/costs from different providers? It seems to matter and impact the correctness of the proposed dataset for the cost target. \n2）Does the CB algorithm output only one best arm/provider? In practice, the users might choose multi-cloud to avoid vendor lock-in. Does it seem the goal of the algorithm should output top-n best arms/providers? \n3）The situation for AutoML and Multi-cloud configuration seems to be different in Fig. 1. In the Multi-cloud configuration case, each provider provides the same type of parameters, e.g., CPU number/type，memory size，VM/container type. But for AutoML，the parameter types are totally different for different models.  Is the special character in the multi-cloud configuration case helpful to solve the multi-cloud configuration problem? ", "summary_of_the_paper": "In this paper, the authors analyze the similarity between the multi-cloud configuration optimization task and the model selection-configuration problem, and try to solve the multi-cloud configuration optimization task inspired by an algorithm for best-arm identification from the AutoML domain.  They built a benchmark for the multi-cloud configuration task including  60 multi-cloud configuration tasks across 3 public cloud providers. The experimental results show the proposed method can find best cloud provider with best instances and other parameters more cheaper or faster, compared to BBOs.", "summary_of_the_review": "In this paper, the authors try to solve the multi-cloud configuration problem with an algorithm from the AutoML domain. It looks good, but it requires more explanation and clarification why it is a good/best way by the proposed method, why it is better than other methods, why it works. And it also requires more justification of the correctness of the evaluation data.", "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": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "63acrVE5jjj", "reviewer": "Reviewer_5pqw", "summary": "", "questions": "", "limitations": "", "rating": 5, "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": "The main contributions of the paper are: 1) A method to choose the best cloud provider in a multi cloud scenario to avoid vendor lock in given a task. The method provides an objective metric and helps narrow down the choice based on runtime or cost. 2) A dataset for benchmarking and comparisons (although this has to be released publicly yet). and 3) A comprehensive study against other Black box optimizers is provided. The optimization is studied firstly to choose which BBO is better for the search internally in CB and then it is evaluated against SMAC, RB to compare the overall algo.  Main concerns are the following 1) CB is evaluated over runtime and cost currently. However, in practice there are many variables in play such as region availability, SLA requirements, number of instance availability, networking requirements etc., Without actually looking at the current 60 multi cloud configurations that it has been evaluated on, it is hard to comment on the how the tasks were setup and how generally applicable this is or add more configurations. 2) Given that cloud providers provide custom rates for long term usage under corporate deals, in practice the cost estimation can vary quite a lot and passing these custom configurations to CloudBandit seems to be unknown.", "summary_of_the_paper": "The paper proposes a method to find the best cloud provider for multi cloud compute selection (time, cost) to avoid vendor lock in. They achieve this using a best-arm identification algorithm where each arm runs an BBO on each provider and eventually choosing the best arm. They test this approach on 60 different configuration across 3 providers using a proposed dataset and show that the algorithm provides cheaper, faster config. given a set of parameters.", "summary_of_the_review": "The authors study the problem of multi-cloud configuration in this paper, where the problem can be defined as how to choose the best cloud provider based on runtime or cost for a given workload. They propose an algorithm (CB) to help solve this and compare the algorithm for its effectiveness against SMAC, RB and show that it performs well at solving the optimization problem. More work needs to be done to show how complex workloads can be translated into configs that CB can solve and also account for more parameters when optimizing for runtime or cost as discussed above. ", "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": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper studies the problem of choosing the best cloud provider for a task. The problem is formulated as a bandit and solved using algorithm CloudBandit. The algorithm is compared to several baselines, such as SMAC, and performs well. The evaluation is done on 60 different multi-cloud configuration tasks across 3 public cloud providers, which the authors want to share with the public.

This paper has four borderline reject reviews. All reviewers agree that it studies an important problem and that the promised multi-cloud optimization dataset could spark more research in the area of cloud optimization. The weaknesses of the paper are that it is not technically strong and that the quality of the new dataset is not clear from its description. At the end, the scores of this paper are not good enough for acceptance. Therefore, it is rejected.
Decision: Reject