Lab2.ipynb

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "64641a49",
   "metadata": {},
   "outputs": [],
   "source": [
    "import sys\n",
    "print(sys.version)\n",
    "if sys.version[:3] not in [\"3.8\", \"3.9\"]:\n",
    "    print(\"You need to use a conda environment or upgrade your Python version to at least 3.8\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "9284b56b",
   "metadata": {},
   "outputs": [],
   "source": [
    "import warnings\n",
    "warnings.filterwarnings('ignore')\n",
    "\n",
    "import math\n",
    "\n",
    "import cloudpickle\n",
    "import numpy as np\n",
    "import skopt"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "31aad544",
   "metadata": {},
   "source": [
    "In Lab 1, you gained intuition for how to optimize the parameters for expensive-to-evaluate functions using Bayesian optimization. Bayesian optimiation is a powerful tool, and there are lots of open-source Bayesian optimization libraries, so you will rarely need to implement the low-level details of Bayesian optimization yourself. However, as you will see during this lab, applying Bayesian optimization to real-world problems is rarely as simple as making a single call to a library function.\n",
    "\n",
    "In this lab, imagine that you are in charge of administering a multi-tenant cloud machine that is storing data from ten different customers (let's call them customer 1 through customer 10). Each customer stores 1 GB of data, so the cloud machine stores 10 GB of total data on its disk. Each customer runs queries over their own data, which requires reading the relevant data from disk into memory for processing. As a concrete example, imagine that customer 1 is MIT, and MIT is storing data about all undergraduate students on the cloud machine's disk, and MIT runs queries such as \"what is the average GPA of course 6 undergrads?\", which requires reading a portion of the data (only the portion regarding course 6 undergrads) into memory for processing.\n",
    "\n",
    "The cloud machine has enough memory to cache a total of 1 GB of data. Cached data is pinned in memory and is therefore much faster to process than data that must be read from disk. Ideally, we want all data to be cached in memory, but in this case there's only enough cache space to store 10% of the total data in cache.\n",
    "\n",
    "To preserve customer privacy, you are not allowed to share the cache among the ten customers. Therefore, you must decide how to allocate the 1 GB cache budget among the 10 customers. More concretely, you must define a vector $x = [x_1, x_2, \\ldots, x_{10}]$, where $x_i$ is the amount of cache given to customer $i$'s data, measured in bytes.\n",
    "\n",
    "How do you find the best setting for $x$? First, you need a way to evaluate the performance of a given setting for $x$. For privacy reasons, you are not allowed to directly observe each customer's query workload. All you can do is set $x$, wait for a while, and measure the resulting performance. Therefore, evaluating the performance for a given $x$ is expensive.  This seems like a perfect fit for Bayesian optimization."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "e8bcec15",
   "metadata": {},
   "source": [
    "# Assignment 0: Setup"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "2e8b3957",
   "metadata": {},
   "source": [
    "Let's say we want to measure performance in terms of the average time it takes to process a query. (In the real world, depending on customer expectations and business requirements, you might measure performance a different way, e.g., in terms of tail latencies or cache hits.)\n",
    "\n",
    "For this lab, we will provide you with a Python function, `measure_average_query_time`. It takes a single argument, which is the vector $x$ (represented as a Python list), and outputs the time in seconds that it takes to run an average query across all customers. In reality, this function would take a while to run (because we need to wait for customer queries to actually run), but for the sake of this lab, the provided function will run very quickly."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "f42f3f45",
   "metadata": {},
   "outputs": [],
   "source": [
    "# Load the Python function\n",
    "with open(\"measure_average_query_time.bin\", \"rb\") as f:\n",
    "    measure_average_query_time = cloudpickle.loads(f.read())"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "157064ee",
   "metadata": {},
   "source": [
    "For example, if we allocate 100 MB to each customer's cache, the average query time would be:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "66385c2a",
   "metadata": {},
   "outputs": [],
   "source": [
    "measure_average_query_time([int(1e8)] * 10)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "42aafbe7",
   "metadata": {},
   "source": [
    "In this lab, we will be using the scikit-optimize library, which implements Bayesian optimization. You can find documentation and examples [here](https://scikit-optimize.github.io/stable/index.html).\n",
    "\n",
    "Let's try using scikit-optimize to find the best setting for $x$. (This may run for about half a minute.)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "b5f79147",
   "metadata": {},
   "outputs": [],
   "source": [
    "# An objective function which returns the average query time achieved with a certain\n",
    "# setting of cache sizes\n",
    "def objective(cache_sizes):\n",
    "    return measure_average_query_time(cache_sizes)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "c4de8e4a",
   "metadata": {},
   "outputs": [],
   "source": [
    "res = skopt.gp_minimize(         # Bayesian optimization using Gaussian processes\n",
    "    objective,                   # The function to minimize\n",
    "    [(0, int(1e9))] * 10,        # The bounds on each dimension of x (we should not allocate more than 1 GB to any customer's cache)\n",
    "    n_calls=50,                  # Maximum number of calls to the objective function\n",
    ")  "
   ]
  },
  {
   "cell_type": "markdown",
   "id": "847a3c31",
   "metadata": {},
   "source": [
    "The best setting for $x$ that the optimizer found can be accessed through `res.x`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "ac92e301",
   "metadata": {},
   "outputs": [],
   "source": [
    "res.x"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "e7c983e6",
   "metadata": {},
   "source": [
    "For most customers, the optimizer allocated 1 GB of cache. Obviously, this would minimize average query time, but it's not a valid setting, because we only have 1 GB of total cache, so this result is useless. This brings us to the first challenge: how do we incorporate the constraint that the total cache size cannot be more than 1 GB into the optimization?"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "006d19a7",
   "metadata": {},
   "source": [
    "# Assignment 1: Incorporating constraints"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "33ed120e",
   "metadata": {},
   "source": [
    "The total size of all caches must be no more than 1 GB. There are many possible ways to incorporate this constraint into the optimization problem. Here, we explore two of those ways.\n",
    "\n",
    "#### Assignment 1a\n",
    "\n",
    "The first way is to incorporate the constraint into the objective function directly. Think of a way to modify the objective function by penalizing any setting of $x$ that sums to more than 1 GB."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "faee8dbc",
   "metadata": {},
   "outputs": [],
   "source": [
    "max_total_cache_size = 1e9"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "5ed3ebd2",
   "metadata": {},
   "outputs": [],
   "source": [
    "def objective_v1(cache_sizes):\n",
    "    # Insert code here that penalizes settings where the total size of all caches is more than 1 GB.\n",
    "    # Hint: you may need to scale the penalty based on the amount by which the maximum size is exceeded."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "292dc16e",
   "metadata": {},
   "source": [
    "Now if we run the Bayesian optimization, the sum of $x$ should be no more than 1 GB."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "d0bc6a9a",
   "metadata": {},
   "outputs": [],
   "source": [
    "res = skopt.gp_minimize(\n",
    "    objective_v1,\n",
    "    [(0, int(1e9))] * 10,\n",
    "    n_calls=50,\n",
    ")\n",
    "print(f\"Total cache size: {sum(res.x)}, avg query time achieved: {res.fun}\")\n",
    "if int(sum(res.x)) > max_total_cache_size:\n",
    "    print(\"Oh no! Total cache size constraint violated. Something went wrong.\")"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "d28f1732",
   "metadata": {},
   "source": [
    "#### Assignment 1b\n",
    "\n",
    "The second way is to reinterpret $x$. Instead of interpreting it as the exact cache sizes per customer in bytes, think of them as relative cache sizes. Can you scale $x$ so that the total cache size is no more than 1GB?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "dd77a146",
   "metadata": {},
   "outputs": [],
   "source": [
    "def compute_scaled_cache_sizes(cache_sizes):\n",
    "    # Insert code here that scales `cache_sizes` so that it sums to no more than 1 GB,\n",
    "    # and returns the scaled version."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "27ed79ed",
   "metadata": {},
   "outputs": [],
   "source": [
    "def objective_v2(cache_sizes):\n",
    "    scaled_cache_sizes = compute_scaled_cache_sizes(cache_sizes)\n",
    "    return measure_average_query_time(scaled_cache_sizes)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "978f479c",
   "metadata": {},
   "source": [
    "Now if we run the Bayesian optimization, the sum of scaled $x$ should be no more than 1 GB."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "812db9d8",
   "metadata": {},
   "outputs": [],
   "source": [
    "res = skopt.gp_minimize(\n",
    "    objective_v2,\n",
    "    [(0, int(1e9))] * 10,\n",
    "    n_calls=50,\n",
    ")\n",
    "best_cache_sizes = compute_scaled_cache_sizes(res.x)\n",
    "print(f\"Total cache size: {sum(best_cache_sizes)}, avg query time achieved: {objective_v2(best_cache_sizes)}\")\n",
    "if int(sum(best_cache_sizes)) > max_total_cache_size:\n",
    "    print(\"Oh no! Total cache size constraint violated. Something went wrong.\")"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "f60420e3",
   "metadata": {},
   "source": [
    "#### Assignment 1c\n",
    "\n",
    "For each of these two methods, describe one advantage that it has over the other method.\n",
    "\n",
    "Your text here:"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "9974d8ca",
   "metadata": {},
   "source": [
    "For the remainder of this lab, we will continue to use the second method above."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "6d937072",
   "metadata": {},
   "outputs": [],
   "source": [
    "def objective(cache_sizes):\n",
    "    return objective_v2(cache_sizes)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "73b427c7",
   "metadata": {},
   "source": [
    "# Assignment 2: Multi-objective optimization"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "b2b07ae5",
   "metadata": {},
   "source": [
    "So far we have set $x$ in a way that minimizes average query time across all customers. But what if customer 1 is a very important customer, and they make a request that their own average query time does not fall below a certain value $T$? Therefore, we want to minimize the average query runtime across all customers while guaranteeing that average runtime for customer 1 is no more than $T$. For this assignment, we will set $T$ to 7.4:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "9e898145",
   "metadata": {},
   "outputs": [],
   "source": [
    "desired_cust1_avg_time = 7.4"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "ded59f77",
   "metadata": {},
   "source": [
    "Now how do we find the best $x$? Again, there are multiple viable methods. One method is to do something similar to Assignment 1a, where we incorporated the constraint into the optimization objective. Here, we explore a different method.\n",
    "\n",
    "First, we provide you with a Python function `measure_average_query_time_customer1`, which takes a single value as input (the cache size for customer 1, in bytes) and returns customer 1's average query time."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "0f4932fb",
   "metadata": {},
   "outputs": [],
   "source": [
    "with open(\"measure_average_query_time_customer1.bin\", \"rb\") as f:\n",
    "    measure_average_query_time_customer1 = cloudpickle.loads(f.read())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "aa2c2d48",
   "metadata": {},
   "outputs": [],
   "source": [
    "measure_average_query_time_customer1(1e8)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "7e1dc256",
   "metadata": {},
   "source": [
    "#### Assignment 2a"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "8cc1647c",
   "metadata": {},
   "source": [
    "We now have two objective functions: `measure_average_query_time`, which is the average query time across all customers, and `measure_average_query_time_customer1`, which is the average query time for customer 1 only. How do we trade off between these two objectives? One way is to create one global objective function that is the weighted sum of these two individual objectives. Essentially, given a weight $w$, our global objective function is `measure_average_query_time + w * measure_average_query_time_customer1`. Implement this weighted objective below, while keeping in mind the total cache size constraint."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "d9862db6",
   "metadata": {},
   "outputs": [],
   "source": [
    "### Assignment 2a ###\n",
    "def create_weighted_objective_function(weight):\n",
    "    def weighted_objective(cache_sizes):\n",
    "        # Insert code here that returns a weighted global objective\n",
    "    \n",
    "    return weighted_objective"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "43111f1f",
   "metadata": {},
   "source": [
    "Intuitively, as the weight $w$ increases, the optimizer places increasing importance on minimizing customer 1's average query time, and the setting of $x$ found by the optimizer should result in a lower average query time for customer 1, although at the expense of having a higher overall average query time. Conceptually, there should be an optimal weight $w^*$ that is just large enough to induce the optimizer to satisfy customer 1's constraint, while still maintaining a low overall average query time.\n",
    "\n",
    "We can set this up as a two-level Bayesian optimization problem. In the outer level, we will optimize the weight $w$. In the inner level, we will create a weighted objective using the given $w$ and optimize the cache sizes $x$.\n",
    "\n",
    "Now, implement the outer objective. You will need to think closely about the value you want to return from the outer objective. Conceptually, you want to return low values for desirable settings of $w$ and high values for undesirable settings of $w$. Here, \"desirability\" is measured both by the average overall query time and by the constraint that customer 1's query time constraint must be met.\n",
    "\n",
    "Hint: for the best results, the output of the outer objective should be smooth as the input $w$ varies."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "91c0df04",
   "metadata": {},
   "outputs": [],
   "source": [
    "memo = {}  # Store the result of the inner-level BO for every iteration of the outer BO\n",
    "\n",
    "def outer_objective(weight):\n",
    "    weight = weight[0]  # the weight argument is a length-1 list, so we unwrap it\n",
    "    weighted_objective = create_weighted_objective_function(weight)\n",
    "    res = skopt.gp_minimize(\n",
    "        weighted_objective,\n",
    "        [(0, int(1e9))] * 10,\n",
    "        n_calls=10,  # You can vary this if you want\n",
    "    )\n",
    "    memo[weight] = res.x\n",
    "    # Insert code here that returns an objective value that induces the optimizer to\n",
    "    # find weights that satisfy customer 1's constraint while minimizing overall\n",
    "    # average query time"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "822b4ccf",
   "metadata": {},
   "source": [
    "Note that there is some randomness in Bayesian optimization so if you don't satisfy the constraint the first time you run, try running again (or increasing the number of calls `n_calls`) to see if you were just unlucky the first time. However, you should rarely violate the constraint two runs in a row."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "b19a6f96",
   "metadata": {},
   "outputs": [],
   "source": [
    "memo = {}  # Store the result of the inner-level BO for every iteration of the outer BO\n",
    "\n",
    "res = skopt.gp_minimize(\n",
    "    outer_objective,\n",
    "    [(0.1, 10.)],\n",
    "    n_calls=10,  # You can vary this if you want\n",
    ")\n",
    "\n",
    "best_cache_sizes = compute_scaled_cache_sizes(memo[res.x[0]])\n",
    "print(f\"Best weight: {res.x}, avg query time achieved: {measure_average_query_time(best_cache_sizes)}\")\n",
    "if int(sum(best_cache_sizes)) > 1e9:\n",
    "    print(\"Oh no! Total cache size constraint violated. Something went wrong.\")\n",
    "if measure_average_query_time_customer1(best_cache_sizes[0]) > desired_cust1_avg_time:\n",
    "    print(\"Oh no! Customer 1 average query time constraint violated. Something went wrong.\")"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "145e5039",
   "metadata": {},
   "source": [
    "#### Assignment 2b\n",
    "\n",
    "Let's say that you know that the relationship between average query time and cache size for any individual customer is a monotonic function: as you increase cache size, average query time is non-increasing. Given this extra assumption, can you think of an even simpler way to minimize overall average query time while satisfying customer 1's query time constraint? You don't need to code anything here. Just describe the more efficient method:\n",
    "\n",
    "Your text here"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "2176ec71",
   "metadata": {},
   "source": [
    "# Assignment 3: Time-based budgets"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "d03c737f",
   "metadata": {},
   "source": [
    "So far, we've set up the Bayesian optimizer by giving it a budget for the number of calls to the objective function that it's allowed to make (using the `n_calls` parameter). However, in practice what we really want is to give the Bayesian optimizer a time budget, e.g., \"I'll give you 1 hour to find the best setting of $x$\". If each call to the objective function takes the same amount of time, then a time budget is more or less equivalent to a function call budget. But in practice, calls to the objective function can take different amounts of time.\n",
    "\n",
    "In our scenario, the objective function sets $x$, waits for a while, and measures the average query time over the queries that have been run so far. How long should we wait? If we wait for a short period of time, the measurement might be noisy, but we also don't want to wait for too long because that time might be better spent measuring a different setting of $x$.\n",
    "\n",
    "For this assignment, we provide you with a function `create_cache_configuration`. It takes a single argument, which is the vector $x$ (represented as a Python list), and outputs a `CacheConfiguration` object which has a method `measure_average_query_time`. Every call to this method will wait for one additional unit of time and measure the average query time observed so far for that cache configuration. As a result, every successive call to `measure_average_query_time` returns decreasingly noisy measurements. If you execute the code below, you will notice that as we spend more time units, the measurement becomes more and more stable."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "40aee86d",
   "metadata": {},
   "outputs": [],
   "source": [
    "with open(\"create_cache_configuration.bin\", \"rb\") as f:\n",
    "    create_cache_configuration = cloudpickle.loads(f.read())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "98342c95",
   "metadata": {},
   "outputs": [],
   "source": [
    "cache_config = create_cache_configuration([1e8] * 10)\n",
    "for i in range(10):\n",
    "    print(f\"Time {i + 1} measurement: {cache_config.measure_average_query_time()}\")"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "08ddf8d2",
   "metadata": {},
   "source": [
    "Suppose that you are given a time budget of 500 to find the best setting for $x$."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "704a59e7",
   "metadata": {},
   "outputs": [],
   "source": [
    "time_budget = 500"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "804f6530",
   "metadata": {},
   "source": [
    "How do you decide how many time units to spend when measuring each setting for $x$? One very simple strategy is to always measure for 10 time units. Here's an example for how to do that."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "7a25743e",
   "metadata": {},
   "outputs": [],
   "source": [
    "# In practice, global variables should be avoided, but for simplicity we're going to have\n",
    "# a global variable that measures the total time used. This must be reset before each trial\n",
    "# of the Bayesian optimizer.\n",
    "total_time_used = 0\n",
    "\n",
    "# Simple strategy: always measure for 10 time units.\n",
    "def simple_time_aware_objective(cache_sizes):\n",
    "    global total_time_used\n",
    "    cache_config = create_cache_configuration(compute_scaled_cache_sizes(cache_sizes))\n",
    "    for _ in range(10):\n",
    "        avg_query_time = cache_config.measure_average_query_time()\n",
    "        total_time_used += 1\n",
    "    return avg_query_time"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "64c94478",
   "metadata": {},
   "outputs": [],
   "source": [
    "# We use this callback function with scikit-optimize to force the Bayesian optimizer to\n",
    "# stop when the time budget is exceeded.\n",
    "def callback(res):\n",
    "    if total_time_used > time_budget:\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "929aa549",
   "metadata": {},
   "outputs": [],
   "source": [
    "total_time_used = 0\n",
    "res = skopt.gp_minimize(\n",
    "    simple_time_aware_objective,\n",
    "    [(0, int(1e9))] * 10,\n",
    "    n_calls=500,  # The callback should stop the optimization before reaching 500 calls\n",
    "    callback=callback,\n",
    ")\n",
    "best_cache_sizes = compute_scaled_cache_sizes(res.x)\n",
    "print(f\"Total cache size: {sum(best_cache_sizes)}, avg query time achieved: {measure_average_query_time(best_cache_sizes)}\")"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "698dd49c",
   "metadata": {},
   "source": [
    "However, there should be much smarter strategies for how to use our time budget. Your task is to create a smarter time-aware objective function. You can be as creative as you want. This assignment is meant to be more open-ended, and there isn't really any wrong solution."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "bbacb28b",
   "metadata": {},
   "outputs": [],
   "source": [
    "def time_aware_objective(cache_sizes):\n",
    "    global total_time_used\n",
    "    cache_config = create_cache_configuration(compute_scaled_cache_sizes(cache_sizes))\n",
    "    # Insert your code here"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "981dbedb",
   "metadata": {},
   "source": [
    "Explain in text why you believe your time-aware objective function is better than the simple strategy of always measuring for 10 time units:\n",
    "\n",
    "Your text here"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "655d3177",
   "metadata": {},
   "source": [
    "Aim for the average query time achieved by your time-aware objective to be better (i.e., lower) than that achieved by the simple strategy above, although it's not required as long as you gave a reason for your approach in the text above."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "e1fc48f0",
   "metadata": {},
   "outputs": [],
   "source": [
    "total_time_used = 0\n",
    "res = skopt.gp_minimize(\n",
    "    time_aware_objective,\n",
    "    [(0, int(1e9))] * 10,\n",
    "    n_calls=500,\n",
    "    callback=callback,\n",
    ")\n",
    "best_cache_sizes = compute_scaled_cache_sizes(res.x)\n",
    "print(f\"Total cache size: {sum(best_cache_sizes)}, avg query time achieved: {measure_average_query_time(best_cache_sizes)}\")"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "f69549f4",
   "metadata": {},
   "source": [
    "# A Note on Scalability\n",
    "\n",
    "(This part is not an assignment, simply a note to supplement your understanding.)\n",
    "\n",
    "In this lab, we assumed there are ten customers. What if you are given another multi-tenant cloud machine, but this time there are five customers, or twenty customers? Intuitively, you would expect that it's harder to find an optimal setting of $x$ as the number of customers increases, because the search space is much larger.\n",
    "\n",
    "To give you a visual for this intuition, below we show you three different plots. In the first plot, we assume that there are only two customers, and we are allocating a total cache space of 200 MB amongst these two customers. In the second plot, we assume 500 MB of cache for five customers, and in the third plot, we assume 1 GB of cache for ten customers. On the x-axis, we vary the number of calls to the objective function (`measure_average_query_time`) that we allow the Bayesian optimizer. On the y-axis we show the minimum objective function value found by the optimizer. We run multiple trials, and show variation between trials by the shaded area.\n",
    "\n",
    "The main takeaway from these plots is that when the number of customers is low (more generally, when the number of parameters to optimize is low), the Bayesian optimizer requires a low number of function calls to find the optimal setting. For example, with two customers, the optimizer finds the optimal setting after only around 8 function calls; we know this is the optimal because the minimum value found does not decrease further as the number of function calls increases. As the number of parameters increases, the Bayesian optimizer requires more function calls. This matches our intuition.\n",
    "\n",
    "In general, increasing the number of parameters is a common issue across many situations and is known as the [\"curse of dimensionality\"](https://en.wikipedia.org/wiki/Curse_of_dimensionality)."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "d9b056f8",
   "metadata": {},
   "source": [
    "![2caches](2caches.png)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "2cf595f8",
   "metadata": {},
   "source": [
    "![5caches](5caches.png)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "e0f5f6f4",
   "metadata": {},
   "source": [
    "![10caches](10caches.png)"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.8.8"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}