# SASHA: Hyperparameter Optimization by Simulated Annealing and Successive Halving

Ron Triepels

► To cite this version:

Ron Triepels. SASHA: Hyperparameter Optimization by Simulated Annealing and Successive Halving. 19th IFIP International Conference on Artificial Intelligence Applications and Innovations (AIAI), Jun 2023, León, Spain. pp.491-502, 10.1007/978-3-031-34107-6_39. hal-05498098

HAL Id: hal-05498098

https://inria.hal.science/hal-05498098v1

Submitted on 6 Feb 2026

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons CC BY 4.0 - Attribution - International License
<figure><img src="image_2.png" /></figure>

ifip

International Federation for Information Processing

This document is the original author manuscript of a paper submitted to an IFIP
conference proceedings or other IFIP publication by Springer Nature. As such, there
may be some differences in the official published version of the paper. Such
differences, if any, are usually due to reformatting during preparation for publication or
minor corrections made by the author(s) during final proofreading of the publication
manuscript.
# SASHA: Hyperparameter Optimization by Simulated Annealing and Successive Halving

Ron Triepels(✉)

Maastricht University, Tongersestraat 53, 6211 LM Maastricht, the Netherlands

r.triepels@maastrichtuniversity.nl

**Abstract.** Successive halving (SHA) has become popular for hyperparameter optimization since it often yields good results while consuming a considerably lower training budget than traditional brute-force algorithms. Nevertheless, SHA is known to suffer from the crossing curves problem. A configuration that performs poorly at the start may perform very well with more budget in later rounds, causing its loss curve to cross that of competing configurations. When this happens, there is a risk that promising configurations are discarded prematurely. In this paper, we propose a new variant of SHA which we name SASHA, that combines Simulated Annealing (SA) with SHA. SASHA discards configurations stochastically based on their performance relative to the best-performing configuration. This property allows the algorithm to make more informed decisions about the configurations to be discarded each round. We study the behavior of SASHA when optimizing a simple test function and a logistic regression model. Our results indicate that SASHA can effectively deal with the crossing curves problem.

**Keywords:** Hyperparameter Optimization · Simulated Annealing · Successive Halving · Machine Learning · Artificial Intelligence

## 1 Introduction

Hyperparameter optimization has become a critical part of the machine learning workflow. Modern machine learning models come with an array of hyperparameters that must be carefully tuned to the problem at hand. For example, when constructing a neural network, one has to make many decisions regarding the network architecture (e.g., the number of layers and activation functions), regularization (e.g., the use of weight decay or dropout), and optimization (e.g., the optimizer and learning rate). Inadequate optimization of these parameters may result in a model that does not generalize well to new and unseen data.

Many algorithms have been proposed to aid machine learning practitioners in this task. Recently, multi-armed bandit algorithms have become popular with the introduction of Successive Halving (SHA) [6]. In SHA, multiple instances of a model with different hyperparameter configurations are iteratively fitted for
some budget (e.g., number of epochs) over a series of rounds. In each round, a fixed ratio of the worst-performing configurations is discarded until the best configuration remains. The advantage of SHA over a traditional grid search or random search [1], in which all configurations are fitted with the same budget, is that it avoids spending much budget on unpromising configurations.

Nevertheless, SHA is known to suffer from the crossing curves problem. Configurations are discarded under the assumption that they will not outperform competing configurations with more budget. In practice, however, a configuration that performs poorly at the start may perform very well in later rounds, causing its loss curve to cross that of competing configurations. This behavior occurs, for example, when optimizing the learning rate of a neural network. A high learning rate causes the loss to decrease fast initially but diverge later on, whereas a low learning rate causes the loss to decrease slowly initially but converge to a low loss in the end. When this happens, there is a risk that SHA discards promising configurations prematurely.

Several extensions of SHA have been proposed to mitigate this risk. Hyperband [9] performs multiple runs of SHA, whereby each run optimizes over a smaller set of randomly sampled configurations. The motivation for this strategy is that if the overall budget is fixed, the budget spent on exploring promising configurations depends on the number of configurations under consideration. By performing a grid search over this number, the explorative nature of SHA can be adapted to the problem at hand. BOHB [3] applies a similar strategy. However, instead of randomly sampling configurations, BOHB uses Bayesian optimization to sample promising configurations for each run.

In this paper, we propose a new algorithm for hyperparameter optimization that combines Simulated Annealing (SA) [7] with SHA. We name the algorithm SASHA. The main innovation of SASHA is that it does not discard configurations based on a fixed ratio each round. Instead, configurations are discarded according to a stochastic process based on how much their performance deviates from the best-performing configuration. We study the behavior of SASHA when optimizing the hyperparameters of a simple test function and a logistic regression model. Our experimental results show that SASHA requires a considerably lower overall budget than SHA to obtain similar performance when hyperparameter optimization is subject to the crossing curves problem.

# 2 Hyperparameter Optimization

## 2.1 Problem Definition

We study hyperparameter optimization in a traditional framework with a single training and validation set [4]. Let $\mathcal{D}$ be a dataset split into a training set $\mathcal{D}_{\text{train}}$ and validation set $\mathcal{D}_{\text{val}}$. Moreover, let $f_{\theta}$ be a model parameterized by a set of hyperparameters $\theta$, where $\theta$ is an element of hyperparameter space $\Theta$. Without loss of generability, we assume that $\Theta$ is a discrete space (i.e., a grid of hyperparameters). The performance of $f_{\theta}$ is measured by loss function $\mathcal{L}$. Typically, $\mathcal{L}$ is the error rate in classification tasks or the mean squared error in regressions
tasks. The goal of hyperparameter optimization is to find the optimal $\theta$ after fitting $f_{\theta}$ on $\mathcal{D}_{\text{train}}$ such that $\mathcal{L}$ on $\mathcal{D}_{\text{val}}$ is minimized. Solving this optimization task is challenging because $f_{\theta}$ has to be fitted on $\mathcal{D}_{\text{train}}$ before $\mathcal{L}$ can be estimated on $\mathcal{D}_{\text{val}}$, and this fitting procedure is generally expensive. It is, therefore, desirable to solve the optimization problem with the least possible budget (e.g., training time or the number of epochs).

Early stopping is a strategy to solve hyperparameter optimization tasks with a minimal budget. In early stopping, it is assumed that $f_{\theta}$ can be fitted iteratively on $\mathcal{D}_{\text{train}}$ and $\mathcal{L}$ on $\mathcal{D}_{\text{val}}$ can be monitored between iterations. Configurations that perform poorly are terminated prematurely under the assumption that they will not outperform competing configurations. This allows more budget to be allocated to promising configurations. In the remainder of this section, we discuss hyperparameter optimization algorithms that are based on such a strategy.

## 2.2 Successive Halving

Successive Halving (SHA) solves hyperparameter optimization as a best-arm identification problem in a multi-armed bandit setting [6]. In this setting, an arm corresponds to a model with a particular hyperparameter configuration. Pulling an arm corresponds to fitting a model on the training set for some additional budget and measuring its loss on the validation set. SHA aims to find the best arm that yields the lowest loss when there is only a fixed overall budget to pull arms. This is done by repeatedly pulling arms and discarding a fraction of the worst-performing ones until the best arm remains.

Let $\mathcal{A}$ be a set of arms and $\mathcal{B}$ the overall budget. Initially, $\mathcal{A}$ contains an arm corresponding to $f_{\theta}$ for each $\theta \in \Theta$ or a (random) subset of $\Theta$. SHA proceeds over several rounds. We denote the number of arms at round $i$ by $k_i$. At round $i$, all arms in $\mathcal{A}$ are pulled with additional budget $b_i$, and the worst-performing arms are discarded according to discard rate $r \in (0, 1)$. This means that there are $k_1$ arms in round 1, $k_2 = \lfloor rk_1 \rfloor$ arms in round 2, $k_3 = \lfloor rk_2 \rfloor$ arms in round 3, and so on. If follows that the total number of rounds after which $\mathcal{A}$ contains less than $1/r$ arms is:

$$n = \lfloor \log_{1/r}(k_1) \rfloor \quad (1)$$

After $n$ rounds, the algorithm terminates and the arm in $\mathcal{A}$ with the lowest loss is returned. Algorithm 1 summarizes the SHA algorithm.

**Input:** Initial arms $\mathcal{A}$, total budget $\mathcal{B}$, discard rate $r$
**for** $i = 1$ **to** $n$ **by** 1 **do**
> Pull each arm in $\mathcal{A}$ with additional budget $b_i$;
> Discard worst performing arms based on rate $r$;
**end**
**Output:** Best arm in $\mathcal{A}$

<caption>**Algorithm 1:** SHA [6].</caption>
There are many ways to distribute $B$ across the arms and rounds. A common strategy is to fix the total budget per round. This means that the budget per arm at round $i$ is:

$$b_i = \left\lfloor \frac{B}{k_i n} \right\rfloor \qquad (2)$$

We will refer to this budget scheme as a geometric budget because $b_i$ follows a geometric series. A nice property of this budget scheme is that it assigns few budget to bad performing arms that are discarded early on and much budget to promising arms that survive many rounds.

However, a disadvantage of a geometric budget is that it requires a relatively high minimum budget for SHA to work properly. If there is an insufficient budget, arms are not fitted and discarded based on how well they perform by their initial (random) parameters. Given Eq. 1 and 2, we have that $b_1 \ge 1$ when:

$$B \ge k_1 \log_{1/r}(k_1) \qquad (3)$$

The minimum budget is a linearithmic function of $k_1$. Furthermore, this budget scheme is prone to the crossing curves problem because a relatively small portion of the overall budget is allocated to early rounds. Promising arms that require more budget to perform well are discarded prematurely. This risk can be mitigated by increasing $r$ at the expense of a higher minimum budget (Eq. 3) such that more budget is spent on the exploration of good arms in early rounds.

An alternative strategy is to fix the budget per arm at each round:

$$b_i = \left\lfloor \frac{B(1-r)}{k_1(1-r^n)} \right\rfloor \qquad (4)$$

We will refer to this budget scheme as a constant budget as $b_i$ is constant across rounds. A constant budget scheme has a lower minimum budget requirement. It follows from Eq. 1 and 4 that $b_1 \ge 1$ when:

$$B \ge \frac{1 - k_1}{r - 1} \qquad (5)$$

The minimum budget is a linear function of $k_1$. Moreover, this budget scheme is less prone to the crossing curves problem because a larger portion of the overall budget is allocated to early rounds. Table 1 provides an example of how the same overall budget is distributed according to a geometric and constant budget. In the remainder of this paper, we will refer to SHA with a geometric and constant budget as SHA-G and SHA-C, respectively.

A drawback of SHA is that the budget, budget scheme, and discard rate must be properly chosen to obtain good results. Finding optimal values for these parameters is challenging as this depends on many factors, including the type of model to be optimized, the nature of hyperparameters considered during the optimization, and the budget available for exploring promising arms. SHA can run for a long time on complex models with many initial arms, often leaving only a small budget for tuning these parameters. Furthermore, there may be better
<table><caption>**Table 1.** The distribution of budget to arms across rounds according to a geometric and constant budget. Note that the overall budget of the constant budget is slightly lower than the overall budget of the geometric budget due to rounding.</caption><thead><tr><th rowspan="3">Round</th><th rowspan="3">Arms</th><th colspan="2">Geometric Budget</th><th colspan="2">Constant Budget</th></tr><tr><th>Budget</th><th>Budget</th><th>Budget</th><th>Budget</th></tr><tr><th>Per Arm</th><th>Per Round</th><th>Per Arm</th><th>Per Round</th></tr><tr><th><i>i</i></th><th><i>k</i><sub><i>i</i></sub></th><th><i>b</i><sub><i>i</i></sub></th><th><i>k</i><sub><i>i</i></sub> &middot; <i>b</i><sub><i>i</i></sub></th><th><i>b</i><sub><i>i</i></sub></th><th><i>k</i><sub><i>i</i></sub> &middot; <i>b</i><sub><i>i</i></sub></th></tr></thead><tbody><tr><td>1</td><td>64</td><td>1</td><td>64</td><td>3</td><td>192</td></tr><tr><td>2</td><td>32</td><td>2</td><td>64</td><td>3</td><td>96</td></tr><tr><td>3</td><td>16</td><td>4</td><td>64</td><td>3</td><td>48</td></tr><tr><td>4</td><td>8</td><td>8</td><td>64</td><td>3</td><td>24</td></tr><tr><td>5</td><td>4</td><td>16</td><td>64</td><td>3</td><td>12</td></tr><tr><td>6</td><td>2</td><td>32</td><td>64</td><td>3</td><td>6</td></tr></tbody></table>

strategies than discarding arms based on a fixed discard rate. If the loss of all arms is very close, we should pull arms for a few more rounds to see whether a clear winner emerges with more budget. Likewise, if there is a large discrepancy in the loss of the arms, we should discard bad-performing arms prematurely to avoid wasting budget on these arms later on. It is unlikely that this should always be done based on the same discard rate across rounds. In the next section, we discuss how these issues can be addressed.

## 2.3 SASHA

SASHA is a combination of Simulated Annealing (SA) and SHA. In contrast to SHA, it does not use a pre-determined budget and fixed discard rate. Instead, arms are pulled for a fixed budget per arm *b* each round and discarded according to a stochastic process until only a single arm remains.

The probability of an arm being accepted to the next round depends on its performance and the current temperature. The gap in loss of arm *a* relative to the best-performing arm at round *i* is:

$$ \Delta_a^{(i)} = \mathcal{L}_a^{(i)} - \mathcal{L}_{\min}^{(i)} \qquad (6) $$

where $\mathcal{L}_{\min}^{(i)}$ is the lowest loss observed across all arms at round *i*. The probability of *a* being accepted to the next round is:

$$ p_a^{(i)} = \exp \left( - \frac{\Delta_a^{(i)}}{t^{(i)}} \right) \qquad (7) $$

where $t^{(i)}$ is the temperature at round *i*. The larger the gap $\Delta_a^{(i)}$, the less likely it is that *a* is accepted to the next round. Whether *a* is discarded is determined by random chance according to probability $p_a^{(i)}$. This can be implemented by
generating a random number between zero and one. If the number is larger than $p_a^{(i)}$, then $a$ is discarded. It follows from Eq. 6 and 7 that the best-performing arm has zero gap and, hence, is never discarded.

The temperature is annealed over the rounds to ensure the algorithm converges to a single arm. Initially, the temperature will be high, and arms are unlikely to be discarded, even when they perform relatively poorly. However, the temperature will decrease as the optimization progresses, and unpromising arms are more likely to be discarded. The algorithm keeps iterating until the temperature becomes so low that all arms except the best-performing arm are discarded. Algorithm 2 summarizes the proposed algorithm.

**Input:** Initial arms $\mathcal{A}$, initial temperature $t^{(0)}$, budget per arm $b$
$i = 1$;
**while** $|\mathcal{A}| > 1$ **do**
    Update temperature $t^{(i)}$;
    Pull all arms in $\mathcal{A}$ with additional budget $b$;
    **foreach** $a \in \mathcal{A}$ **do**
        Calculate acceptance probability $p_a^{(i)}$;
        **if** $\text{RAND}(0, 1) > p_a^{(i)}$ **then**
            Discard arm $\mathcal{A} = \mathcal{A} \setminus a$;
        **end**
    **end**
    $i = i + 1$;
**end**
**Output:** Best arm in $\mathcal{A}$

<caption>**Algorithm 2: SASHA.**</caption>

There are many ways to anneal the temperature. Ideally, we want the temperature to decrease fast to avoid spending much budget on unpromising arms, but not too fast to avoid promising arms being discarded prematurely. We use the fast annealing schedule proposed by [10]. The schedule can be defined as:

$$t^{(i)} = \frac{t^{(0)}}{i} \quad \text{for } i \ge 1 \qquad (8)$$

where $t^{(0)}$ is the initial temperature. Our experimental results show that this schedule works well for hyperparameter optimization.

Two parameters control the behavior of SASHA: $t^{(0)}$ and $b$. $t^{(0)}$ controls the explorative nature of the algorithm. If $t^{(0)}$ is close to zero, the algorithm quickly converges by immediately discarding arms when they fall behind the best-performing arm. In contrast, if $t^{(0)}$ is high, the algorithm converges more slowly by pulling bad-performing arms for more rounds to see whether they recover in the long run. $b$ is the fixed budget for which each arm is additionally pulled each round. It controls how often the optimization progress is checked and
changes to the current set of arms are made. In many applications, measuring the loss of an arm is expensive. Hence, b should not be too low to avoid the algorithm spending a large portion of its run-time on progress checks. It is recommended to fix b to a reasonable value and only tune t(0). In this way, the algorithm effectively has only a single parameter that requires fine-tuning.

An advantage of SASHA over SHA is that it can make more informed decisions about the arms to be discarded. It can discard arms early when a clear winner emerges or keep pulling arms when there is strong competition. Our results show that this property reduces the overall budget required to solve optimization problems subject to the crossing curves problem. Furthermore, the behavior of SASHA can be controlled more easily by effectively only a single parameter (the initial temperature) compared to three parameters (the overall budget, budget scheme, and discard rate) in SHA. It is, therefore, more likely SASHA is better tuned to the problem at hand.

However, a limitation of SASHA is that it is not known in advance how much overall budget the algorithm is going to consume. This can be problematic in applications where a model must be optimized under a strict budget. In such a case, an additional stopping criterion can be implemented that terminates the algorithm when a given overall budget is consumed.

# 3 Experiments

## 3.1 Test Function

We conducted an experiment to study the behavior of SASHA on a simple test function. The function simulates the loss of a model fitted by an iterative fitting procedure (like gradient descent). It is defined as:

$$ \mathcal{L} = -\beta \log(x/\gamma) \quad \text{for } \beta > 0, \gamma > 0 \qquad (9) $$

where, x can be interpreted as the total number of epochs for which the model has been fitted, β is a hyperparameter to be optimized, and γ is a parameter that controls the difficulty of the optimization. In the experiment, we optimized β over a space of 100 values $\beta \in \{0.01, 0.02, \dots, 1.00\}$ and fixed $\gamma = 100$. The motivation for this setup is that $\mathcal{L}$ can be evaluated cheaply and the behavior of SHA on this function can be studied analytically. Moreover, $\mathcal{L}$ is of interest because it simulates the crossing curves problem. $\mathcal{L}$ is a monotonic decreasing function whose rate of decrease depends on β and always crosses the point $(\gamma, 0)$, see Fig. 1. If $x < \gamma$, $\mathcal{L}$ is minimized when β is as small as possible, whereas, if $x > \gamma$, $\mathcal{L}$ is minimized when β is as large as possible.

The optimal β found by SHA depends on the round at which the cumulative budget spend on each arm crosses the critical value γ. The cumulative budget spend on each arm after n rounds is:

$$ c_n = \sum_{i=1}^{n} b_i \qquad (10) $$
<figure><img src="image_3.png" /><figcaption>Fig. 1. Plot of $\mathcal{L}$ for different values of $\beta$. (Color figure online)</figcaption></figure>

Let $\beta_1 = 0.01$, $\beta_2 = 0.02$, and so on. The optimal $\beta$ found by SHA when using a discard rate of $r = 0.5$ can be defined as:

$$ \hat{\beta} = \begin{cases} \beta_{100}, & \text{if } c_1 \ge \gamma \\ \beta_{50}, & \text{if } c_2 \ge \gamma \\ \beta_{25}, & \text{if } c_3 \ge \gamma \\ \beta_{12}, & \text{if } c_4 \ge \gamma \\ \beta_6, & \text{if } c_5 \ge \gamma \\ \beta_3, & \text{if } c_6 \ge \gamma \\ \beta_1, & \text{otherwise} \end{cases} \quad (11) $$

$\mathcal{L}$ is problematic for SHA to optimize properly. SHA keeps discarding the highest $\beta$ values each round until the cumulative budget spent on each arm exceeds $\gamma$, after which the lowest $\beta$ values are discarded each round. If the overall budget is too small, such that arms are pulled for a budget less than $\gamma$ in the first round, promising arms will be discarded prematurely. Moreover, it follows from Eq. 11 that $\gamma$ controls the difficulty of the optimization. Increasing $\gamma$ requires a higher overall budget to find the best solution $\beta_{100}$.

The goal of the experiment is to determine whether SASHA is less susceptible to the crossing curves problem than SHA when optimizing $\mathcal{L}$. We did this by optimizing $\mathcal{L}$ using SASHA based on 100 different values for the initial temperature $t^{(0)} \in \{100, 200, \dots, 10000\}$. We ran the algorithm ten times for each temperature, yielding a total of 1000 runs. Accordingly, we compared the optimal $\beta$ found by SASHA in each run to the solutions found by SHA-G and SHA-C when consuming the same overall budget.

Figure 2 shows the results of the experiment. The figure reveals that SASHA requires a considerable lower overall budget to find the best solution than SHA-G and SHA-C. SASHA finds the best solution when using a budget of approximately 10000 epochs. In contrast, SHA-G and SHA-C require an overall budget of at least 60000 and 19688 epochs respectively to find the same solution.
<figure><img src="image_4.png" /><figcaption>**Fig. 2.** The results of the experiment on the test function. Each circle corresponds to a value of $\beta$ found by SASHA in a run. The red and blue lines depict the $\beta$ found by SHA-G and SHA-C respectively according to Eq. 11. (Color figure online)</figcaption></figure>

## 3.2 MNIST

We also conducted an experiment to study how well SASHA optimizes the learning rate of a logistic regression model fitted on MNIST [8]. A standard logistic regression model optimized by stochastic gradient descent [2] with mini-batches of 128 images was used in the experiment. The weights of the model were initialized by the heuristic of [5], and its bias term was initially set to zero. The learning rate was optimized over a space of 16 possible rates (0.10, 0.12, ..., 0.40).

The goal of the experiment is to compare the efficiency of SASHA and SHA at different performance levels. This was done by randomly partitioning the MNIST training set into a training and validation set based on a 80%-20% split, respectively. Accordingly, we performed 100 runs of SASHA with different initial temperatures $t^{(0)} \in \{0.02, 0.04, ..., 2.00\}$. For each run, a logistic regression model was fitted on the entire original MNIST training set based on the optimal learning rate found in the run, and the error rate of the model was measured on the MNIST test set. In a similar way, 100 runs of SHA-G and SHA-C were performed while making sure the algorithms consumed the same overall budgets as SASHA in each run. Finally, we compared the overall budget required by the algorithms to achieve different error rates.

Figure 3 shows the results of the experiment. The figure shows that SASHA requires a considerably lower overall budget than SHA-G and SHA-C to achieve the same level of performance. SASHA achieves an average error rate of 7.76% with an overall budget of approximately 500 epochs. To obtain the same error rate, we need an overall budget of at least 1200 epochs for SHA-G and 800 epochs for SHA-C. Figure 4 reveals that this inefficiency of SHA-G and SHA-C is due to the crossing curves problem. Lower error rates are obtained by lowering the learning rate. However, arms corresponding to low learning rates require more
<figure><img src="image_5.png" /><figcaption>**Fig. 3.** Average error rate of the logistic regression model fitted on MNIST as a function of the overall budget consumed by SHA-G, SHA-C, and SASHA. Note that the overall budget is grouped by bins of 200 epochs for readability. The dashed line corresponds to an average error rate of 7.76%. (Color figure online)</figcaption></figure>

<figure><img src="image_6.png" /><figcaption>**Fig. 4.** Average learning rate found by SHA-G, SHA-C, and SASHA as a function of the overall budget consumed. (Color figure online)</figcaption></figure>
epochs to outperform arms with high learning rates and are, therefore, likely to be discarded prematurely by SHA. A higher overall budget is required to ensure these arms perform better in early rounds. SASHA is less susceptible to this problem because of the way the temperature is annealed over the rounds, which allows the algorithm to keep sub-optimal arms in early rounds.

# 4 Conclusion

We conclude that SASHA can be a good alternative to SHA for hyperparameter optimization problems that are subject to the crossing curves problem. The main innovation of SASHA is that arms are discarded by a stochastic process based on how well they perform relative to the best-performing arm. This property enables the algorithm to make more informed decisions about the arms to be discarded than SHA and better adapt to the problem at hand.

Our work can be improved in several ways. We only experimentally studied the behavior of SHA when optimizing a simple test function and a logistic regression model. Future research could focus on the theoretical properties of the algorithm or study its behavior on more complex models with many hyperparameters. Moreover, we only compared the performance of SASHA to SHA under different budget schemes. An interesting experiment would be to test whether SASHA also performs favorably against variants of SHA including Hyperband and MOHB. We leave this open to future research.

# References

1. Bergstra, J., Bengio, Y.: Random search for hyper-parameter optimization. J. Mach. Learn. Res. 13(2) (2012)

2. Bottou, L.: Stochastic gradient descent tricks. In: Montavon, G., Orr, G.B., Müller, K.-R. (eds.) Neural Networks: Tricks of the Trade. LNCS, vol. 7700, pp. 421–436. Springer, Heidelberg (2012). https://doi.org/10.1007/978-3-642-35289-8_25

3. Falkner, S., Klein, A., Hutter, F.: BOHB: robust and efficient hyperparameter optimization at scale. In: International Conference on Machine Learning, pp. 1437–1446. PMLR (2018)

4. Feurer, M., Hutter, F.: Hyperparameter optimization. Autom. Mach. Learn.: Methods, Syst. Challenges, 3–33 (2019)

5. Glorot, X., Bengio, Y.: Understanding the difficulty of training deep feedforward neural networks. In: Proceedings of the Thirteenth International Conference on Artificial Intelligence and Statistics, pp. 249–256 (2010)

6. Jamieson, K., Talwalkar, A.: Non-stochastic best arm identification and hyperparameter optimization. In: Artificial Intelligence and Statistics, pp. 240–248. PMLR (2016)

7. Kirkpatrick, S., Gelatt Jr, C.D., Vecchi, M.P.: Optimization by simulated annealing. Science 220(4598), 671–680 (1983)
8. LeCun, Y., Cortes, C., Burges, C. J.: MNIST handwritten digit database (2010)

9. Li, L., Jamieson, K., DeSalvo, G., Rostamizadeh, A., Talwalkar, A.: Hyperband: a novel bandit-based approach to hyperparameter optimization. J. Mach. Learn. Res. 18(1), 6765–6816 (2017)

10. Szu, H., Hartley, R.: Fast simulated annealing. Phys. Lett. A 122(3–4), 157–162 (1987)