Year: 2021

Abstract:
Bayesian optimization (BO) has become an established framework and popular tool for hyperparameter optimization (HPO) of machine learning (ML) algorithms. While known for its sample-efficiency, vanilla BO can not utilize readily available prior beliefs the practitioner has on the potential location of the optimum. Thus, BO disregards a valuable source of information, reducing its appeal to ML practitioners. To address this issue, we propose πBO, an acquisition function generalization which incorporates prior beliefs about the location of the optimum in the form of a probability distribution, provided by the user. In contrast to previous approaches, πBO is conceptually simple and can easily be integrated with existing libraries and many acquisition functions. We provide regret bounds when πBO is applied to the common Expected Improvement acquisition function and prove convergence at regular rates independently of the prior. Further, our experiments show that πBO outperforms competing approaches across a wide suite of benchmarks and prior characteristics. We also demonstrate that πBO improves on the state-of-theart performance for a popular deep learning task, with a 12.5× time-to-accuracy speedup over prominent BO approaches.

heading: 1 INTRODUCTION
text: The optimization of expensive black-box functions is a prominent task, arising across a wide range of applications. Bayesian optimization (BO) is a sample-efficient approach to cope with this task, and has been successfully applied to various problem settings, including hyperparameter optimization (HPO) (Snoek et al., 2012), neural architecture search (NAS) (Ru et al., 2021), joint NAS and HPO (Zimmer et al., 2021), algorithm configuration (Hutter et al., 2011), hardware design (Nardi et al., 2019), robotics Calandra et al. (2014), and the game of Go (Chen et al., 2018).
Despite the demonstrated effectiveness of BO for HPO (Bergstra et al., 2011; Turner et al., 2021), its adoption among practitioners remains limited. In a survey covering NeurIPS 2019 and ICLR 2020 (Bouthillier & Varoquaux, 2020), manual search was shown to be the most prevalent tuning method, with BO accounting for less than 7% of all tuning efforts. As the understanding of hyperparameter settings in deep learning (DL) models increase (Smith, 2018), so too does the tuning proficiency of practitioners (Anand et al., 2020). As previously displayed (Smith, 2018; Anand et al., 2020; Souza et al., 2021; Wang et al., 2019), this knowledge manifests in choosing single configurations or regions of hyperparameters that presumably yield good results, demonstrating a belief over the location of the optimum. BO’s deficit to properly incorporate said beliefs is a reason why practitioners prefer manual search to BO (Wang et al., 2019), despite its documented shortcomings (Bergstra & Bengio, 2012). To improve the usefulness of automated HPO approaches for ML practictioners, the ability to incorporate such knowledge is pivotal.
Well-established BO frameworks (Snoek et al., 2012; Hutter et al., 2011; The GPyOpt authors, 2016; Kandasamy et al., 2020; Balandat et al., 2020) support user input to a limited extent, such as by biasing the initial design, or by narrowing the search space; however, this type of hard prior can lead to poor performance by missing important regions. BO also supports a prior over functions p(f) via the Gaussian Process kernel. However, this option for injecting knowledge is not aligned with the knowledge that experts possess: they often know which ranges of hyperparameter values tend to work best (Perrone et al., 2019; Smith, 2018; Wang et al., 2019), and are able to specify a probability distribution to quantify these priors. For example, many users of the Adam optimizer (Kingma & Ba,
2015) know that its best learning rate is often in the vicinity of 1× 10−3. In practice, DL experiments are typically conducted in a low-budget setting of less than 50 full model trainings (Bouthillier & Varoquaux, 2020). As such, practitioners want to exploit their knowledge efficiently without wasting early model trainings on configurations they expect to likely perform poorly. Unfortunately, this suits standard BO poorly, as BO requires a moderate number of function evaluations to learn about the response surface and make informed decisions that outperform random search.
While there is a demand to increase knowledge injection possibilities to further the adoption of BO, the concept of encoding prior beliefs over the location of an optimum is still rather novel: while there are some initial works (Ramachandran et al., 2020; Li et al., 2020; Souza et al., 2021), no approach exists so far that allows the integration of arbitrary priors and offers flexibility in the choice of acquisition function; theory is also lacking. We close this gap by introducing a novel, remarkably simple, approach for injecting arbitrary prior beliefs into BO that is easy to implement, agnostic to the surrogate model used and converges at standard BO rates for any choice of prior.
Our contributions After discussing our problem setting, related work, and background (Section 2), we make the following contributions:
1. We introduce πBO, a novel generalization of myopic acquisition functions that accounts for user-specified prior distributions over possible optima, is demonstrably simple-to-implement, and can be easily combined with arbitrary surrogate models (Section 3.1 & 3.2);
2. We formally prove that πBO inherits the theoretical properties of the well-established Expected Improvement acquisition function (Section 3.3);
3. We demonstrate on a broad range of established benchmarks and in DL case studies that πBO can yield 12.5× time-to-accuracy speedup over vanilla BO (Section 4).

heading: 2 BACKGROUND AND RELATED WORK

heading: 2.1 BLACK-BOX OPTIMIZATION
text: We consider the problem of optimizing a black-box function f across a set of feasible inputs X ⊂ Rd:
x∗ ∈ arg min x∈X f(x). (1)
We assume that f(x) is expensive to evaluate, and can potentially only be observed through a noisy estimate, y. In this setting, we wish to minimize f in an efficient manner, typically adhering to a budget which sets a cap on the number of points that can be evaluated.
Black-Box Optimization with Probabilistic User Beliefs In our work, we consider an augmented version of the optimization problem in Eq. (1), where we have access to user beliefs in the form of a probability distribution on the location of the optimum. Formally, we define the problem of black-box optimization with probabilistic user beliefs as solving Eq. (1), given a user-specified prior probability on the location of the optimum defined as
π(x) = P ( f(x) = min
x′∈X f(x′)
) , (2)
where regions that the user expects to likely to contain an optimum will have a high value. We note that, without loss of generality, we require π to be strictly positive on all of X , i.e., any point in the search space might be an optimum. Since the user belief π(x) can be inaccurate or even misleading, optimizing Eq. (1) given (2) is a challenging problem.

heading: 2.2 BAYESIAN OPTIMIZATION
text: We outline Bayesian optimization (Mockus et al., 1978; Brochu et al., 2010; Shahriari et al., 2016b).
Model BO aims to globally minimize f by an initial experimental design D0 = {(xi, yi)}Mi=1 and thereafter sequentially deciding on new points xn to form the data Dn = Dn−1 ∪ {(xn, yn)} for the n-th iteration with n ∈ {1 . . . N}. After each new observation, BO constructs a probabilistic surrogate
model of f and uses that surrogate to evaluate an acquisition function α(x,Dn). The combination of surrogate model and acquisition function encodes the policy for selecting the next point xn+1. When constructing the surrogate, the most common choice is Gaussian processes (Rasmussen & Williams, 2006), which model f as p(f |Dn) = GP(m, k), with prior mean m (which is typically 0) and positive semi-definite covariance kernel k. The posterior mean mn and the variance s2n are
mn(x) = kn(x) >(Kn + σ 2 nI)y, s 2 n(x) = k(x,x)− kn(x)>(Kn + σ2nI)kn(x), (3)
where (Kn)ij = k(xi,xj), kn(x) = [k(x,x1), . . . , k(x,xn)]> and σ2n is the estimation of the observation noise variance σ2. Alternative surrogate models include Random forests (Hutter et al., 2011) and Bayesian neural networks (Springenberg et al., 2016).
Acquisition Functions To obtain new candidates to evaluate, BO employs a criterion, called an acquisition function, that encapsulates an explore-exploit trade-off. By maximizing this criterion at each iteration, one or more candidate point are obtained and added to observed data. Several acquisition functions are used in BO; the most common of these is Expected Improvement (EI) (Jones et al., 1998). For a noiseless function, EI selects the next point xn+1, where f∗n is the minimal objective function value observed by iteration n, as
xn+1 ∈ arg max x∈X
E [ [(f∗n − f(x)]+ ] = arg max
x∈X Zsn(x)Φ(Z) + sn(x)φ(Z), (4)
where Z = (f∗n −mn(x))/sn(x). Thus, EI provides a myopic strategy for determining promising points; it also comes with convergence guarantees (Bull, 2011). Similar myopic acquisition functions are Upper Confidence Bound (UCB) (Srinivas et al., 2012), Probability of Improvement (PI) (Jones, 2001; Kushner, 1964) and Thompson Sampling (TS) (Thompson, 1933). A different class of acquisition functions is based on non-myopic criteria, such as Entropy Search (Hennig & Schuler, 2012), Predictive Entropy Search (Hernández-Lobato et al., 2014) and Max-value Entropy Search (Wang & Jegelka, 2017), which select points to minimize the uncertainty about the optimum, and the Knowledge Gradient (Frazier et al., 2008), which aims to minimize the posterior mean of the surrogate at the subsequent iteration. Our work applies to all acquisition functions in the first class, and we leave its extension to those in the second class for future work.

heading: 2.3 RELATED WORK
text: There are two main categories of approaches that exploit prior knowledge in BO: approaches that use records of previous experiments, and approaches that incorporate assumptions on the black-box function provided either directly or indirectly by the user. As πBO exploits prior knowledge from users, we briefly discuss approaches which utilize previous experiments, and then comprehensively discuss the literature on exploiting expert knowledge.
Learning from Previous Experiments Transfer learning for BO aims to automatically extract and use knowledge from prior executions of BO. These executions can come, for example, from learning and optimizing the hyperparameters of a machine learning algorithm on different datasets (van Rijn & Hutter, 2018; Swersky et al., 2013; Wistuba et al., 2015; Perrone et al., 2019; Feurer et al., 2015; 2018), or from optimizing the hyperparameters at different development stages (Stoll et al., 2020). For a comprehensive overview of meta learning for hyperparameter optimization, please see the survey from Vanschoren (2018). In contrast to these transfer learning approaches, πBO and the related work discussed below does not hinge on the existence of previous experiments, and can therefore be applied more generally.
Incorporating Expert Priors over Function Structure BO can leverage structural priors on how the objective function is expected to behave. Traditionally, this is done via the surrogate model’s prior over functions, e.g., the kernel of the GP. However, there are lines of work that explore additional structural priors for BO to leverage. For instance, both SMAC (Hutter et al., 2011) and iRace (LópezIbáñez et al., 2016) support structural priors in the form of log-transformations, Li et al. (2018) propose to use knowledge about the monotonicity of the objective function as a prior for BO, and Snoek et al. (2014) model non-stationary covariance between inputs by warping said inputs.
Oh et al. (2018) and Siivola et al. (2018) both propose structural priors tailored to high-dimensional problems, addressing the issue of over-exploring the boundary described by Swersky (2017). Oh et al. (2018) propose a cylindrical kernel that expands the center of the search space and shrinks the
edges, while Siivola et al. (2018) propose adding derivative signs to the edges of the search space to steer BO towards the center. Lastly, Shahriari et al. (2016a) propose a BO algorithm for unbounded search spaces which uses a regularizer to penalize points based on their distance to the center of the user-defined search space. All of these approaches incorporate prior information on specific properties of the function or search space, and are thus not always applicable. Moreover, they do not generally direct the search to desired regions of the search space, offering the user little control over the selection of points to evaluate.
Incorporating Expert Priors over Function Optimum Few previous works have proposed to inject explicit prior distributions over the location of an optimum into BO. In these cases, users explicitly define a prior that encodes their beliefs on where the optimum is more likely to be located. Bergstra et al. (2011) suggest an approach that supports prior beliefs from a fixed set of distributions. However, this approach cannot be combined with standard acquisition functions. BOPrO (Souza et al., 2021) employs a similar structure that combines the user-provided prior distribution with a data-driven model into a pseudo-posterior. From the pseudo-posterior, configurations are selected using the EI acquisition function, using the formulation in Bergstra et al. (2011). While BOPrO is able to recover from misleading priors, its design restricts it to only use EI. Moreover, it does not provide the convergence guarantees of πBO.
Li et al. (2020) propose to infer a posterior conditioned on both the observed data and the user prior through repeated Thompson sampling and maximization under the prior. This method displays robustness against misleading priors but lacks in empirical performance. Additionally, it is restricted to only one specific acquisition function. Ramachandran et al. (2020) use the probability integral transform to warp the search space, stretching high-probability regions and shrinking others. While the approach is model- and acquisition function agnostic, it requires invertible priors, and does not empirically display the ability to recover from misleading priors. In Section 4, we demonstrate that πBO compares favorably for priors over the function optimum, and shows improved empirical performance. Additionally, we do a complete comparison of all approaches in Appendix C.
In summary, πBO sets itself apart from the methods above by being simpler (and thus easier to implement in different frameworks), flexible with regard to different acquisition functions and different surrogate models, the availability of theoretical guarantees, and, as we demonstrate in Section 4, better empirical results.

heading: 3 METHODOLOGY
text: We now present πBO, which allows users to specify their belief about the location of the optimum through any probability distribution. A conceptually simple approach, πBO can be easily implemented in existing BO frameworks and can be combined directly with the myopic acquisition functions listed above. πBO augments an acquisition function to emphasize promising regions under the prior, ensuring such regions are to be explored frequently. As optimization progresses, the πBO strategy increasingly resembles that of vanilla BO, retaining its standard convergence rates (see Section 3.3).

heading: 3.1 PRIOR-WEIGHTED ACQUISITION FUNCTION
text: In πBO, we consider π(x) in Eq. (2) to be a weighting scheme on points in X . The heuristic provided by an acquisition function α(x,Dn), such as EI in Eq. (2.2), can then be combined with said weighting scheme to form a prior-weighted version of the acquisition function. The resulting strategy then becomes:
xn ∈ arg max x∈X α(x,Dn)π(x). (5)
This emphasizes good points under π(x) throughout the optimization. While this property is suitable for well-located priors π, it risks incurring a substantial slowdown for poorly-chosen priors; we will now show how to counter this by decaying the prior over time.

heading: 3.2 DECAYING PRIOR-WEIGHTED ACQUISITION FUNCTION
text: As the optimization progresses, we should increasingly trust the surrogate model over the prior; the model improves with data while the user prior remains fixed. This cannot be achieved with the
formulation in Eq. (5), as poorly-chosen priors would permanently slow down the optimization. Rather, to accomplish this desired behaviour, the influence of the prior needs to decay over time. Building on the approaches of Lee et al. (2020) and Souza et al. (2021), we accomplish this by raising the prior to a power γn ∈ R+, which decays towards zero with growing n. Thus, the resulting prior πn(x) = π(x)γn reflects a belief on the location of an optimum that gets weaker with time, converging towards a uniform distribution. We set γn = β/n, where β ∈ R+ is a hyperparameter set by the user, reflecting their confidence in π(x). We provide a sensitivity study on β in Appendix A. For a given acquisition function α(x,Dn) and user-specified prior π(x), we define the decaying prior-weighted acquisition function at iteration n as
απ,n(x,Dn) ∆ = α(x,Dn)πn(x) ∆ = α(x,Dn)π(x)β/n (6)
and its accompanying strategy as the maximizer of απ,n. With the acquisition function in Eq. (6), the prior will assume large importance initially, promoting the selection of points close to the prior mode. With time, the exponent on the prior will tend to zero, making the prior tend to uniform. Thus, with increasing n, the point selection of απ,n becomes increasingly similar to that of α. Algorithm 1 displays the simplicity of the new strategy, highlighting the required one-line change (Line 6) in the main BO loop. In Line 3, the mode of the prior is used as a first initial sample if available. Otherwise, only sampling is used for initialization.
Algorithm 1 πBO Algorithm 1: Input: Input space X , prior distribution over optimum π(x), prior confidence parameter β, size M of the initial design, max number of optimization iterations N .
2: Output: Optimized design x∗. 3: {xi}Mi=1 ∼ π(x), {yi ← f(xi) + i}Mi=1, i ∼ N(0, σ2) 4: D0 ← {(xi, yi)}Mi=1 5: for {n = 1, 2, . . . , N} do 6: xnew ← arg maxx∈X α(x,Dn−1)π(x)β/n 7: ynew ← f(xnew) + i 8: Dn ← Dn−1 ∪ {(xnew, ynew)} 9: end for
10: return x∗ ← arg min(xi,yi)∈DN yi
To illustrate the behaviour of πBO, we consider a toy problem with Gaussian priors on three different locations of the 1D space (center, left and right) as displayed in Figure 1. We define a 1D-Log-Branin toy problem by setting the second dimension of the 2D Branin function to the global optimum x2 = 2.275 and optimizing for the first dimension. Initially (iteration 4 in the top row), πBO amplifies the acquisition function α in high-probability regions, putting a lot of trust in the prior. As the prior decays (iteration 6 and 8 in the middle and bottom rows, respectively), the influence of the prior on the point selection decreases. By later iterations, πBO has searched substantially around the prior mode, and moves gradually towards other parts of the search space. This is of particular importance for the scenarios in the right column, where πBO recovers from a misleading prior. In Appendix B, we show that πBO is applicable to different surrogate models and acquisition functions.

heading: 3.3 THEORETICAL ANALYSIS
text: We now study the πBO method from a theoretical standpoint when paired with the EI acquisition function. For the full proof, we refer the reader to Appendix E. To provide convergence rates, we rely on the set of assumptions introduced by Bull (2011). These assumptions are satisfied for popular kernels like the Matérn (1960) class and the Gaussian kernel, which is obtained in the limit ν →∞, where the rate ν controls the smoothness of functions from the GP prior. Our theoretical results apply when both length scales ` and the global scale of variation σ are fixed; these results can then be extended to the case where the kernel hyperparameters are learned using Maximum Likelihood Estimation (MLE) following the same procedure as in Bull (2011) (Theorem 5). We define the loss over the ball BR for a function f of norm ||f ||H`(X ) ≤ R in the reproducing kernel Hilbert space (RKHS)H`(X ) given a symmetric positive-definite kernel K` as
Ln(u,Dn,H`(X ), R) ∆ = sup ||f ||H`(X)≤R Euf [f(x∗n)−min f ], (7)
where n is the optimization iteration and u a strategy. We focus on the strategy that maximizes EIπ , the prior-weighted EI, and show that the loss in Equation (7) can, at any iteration n, be bounded by the vanilla EI loss function. We refer to EIπ,n and EIn when we want to emphasize the iteration n for the acquisition functions EIπ and EI, respectively.
Theorem 1. Given Dn, K`, π, β, σ, `, R and the compact set X ⊂ Rd as defined above, the loss Ln incurred at iteration n by EIπ,n can be bounded from above as
Ln(EIπ,n,Dn,H`(X ), R) ≤ Cπ,nLn(EIn,Dn,H`(X ), R), Cπ,n = ( maxx∈X π(x)
minx∈X π(x)
)β/n .
(8)
Using Theorem 1, we obtain the convergence rate of EIπ . This trivially follows when considering the fraction of the losses in the limit and inserting the original convergence rate on EI as in Bull (2011):
Corollary 1. The loss of a decaying prior-weighted Expected Improvement strategy, EIπ, is asymptotically equal to the loss of an Expected Improvement strategy, EI:
Ln(EIπ,n,Dn,H`(X ), R) ∼ Ln(EIn,Dn,H`(X ), R), (9)
so we obtain a convergence rate for EIπ of Ln(EIπ,n,Dn,H`(X ), R) = O(n−(ν∧1)/d(log n)γ).
Thus, we determine that the weighting introduced by EIπ does not negatively impact the worst-case convergence rate. The short-term performance is controlled by the user in their choice of π(x) and β. This result is coherent with intuition, as a weaker prior or quicker decay will yield a short-term performance closer to that of EI. In contrast, a stronger prior or slower decay does not guarantee the same short-term performance, but can produce better empirical results, as shown in Section 4.

heading: 4 RESULTS
text: We empirically demonstrate the efficiency of πBO in three different settings. As πBO is a general method to augment acquisition functions, it can be implemented in different parent BO packages, and the implementation in any given package inherits the pros and cons of that package. To minimize confounding factors concerning this choice of parent package, we keep comparisons within the methods in one package where possible and provide results in the other packages in Appendix C. In
Sec. 4.2, using Spearmint as a parent package, we evaluate πBO against three intuitive baselines to assess its performance and robustness on priors with different qualities, ranging from very accurate to purposefully detrimental. To this end, we use toy functions and cheap surrogates, where priors of known quality can be obtained. Next, in Sec. 4.3, we compare πBO against two competitive approaches (BOPrO and BOWS) that integrate priors over the optimum similarly to πBO, using Hypermapper (Nardi et al., 2019) as a parent framework, in which the most competitive baseline BOPrO is implemented. For these experiments we adopt a Multilayer Perceptron (MLP) benchmark on various datasets, using the interface provided by HPOBench (Eggensperger et al., 2021), with priors constructed around the defaults provided by the library. Lastly, in Sec. 4.4, we apply πBO and other approaches to two deep learning tasks, also using priors derived from publicly available defaults. Further, we demonstrate the flexibility of πBO in Appendix B, where we evaluate πBO in SMAC (Hutter et al., 2011; Lindauer et al., 2021) with random forests, as another framework with another surrogate model, and adapt it to use the UCB, TS and PI acquisition functions instead of EI.

heading: 4.1 EXPERIMENTAL SETUP
text: We summarize important aspects of our experimental setup and provide further details in Appendix F.
Priors For our surrogate and toy function tasks, we follow the prior construction methodology in BOPrO (Souza et al., 2021) and create three main types of prior qualities, all Gaussian: strong, weak and wrong. The strong and weak priors are located to have a high and moderate density on the optimum, respectively. The wrong prior is a narrow distribution located in the worst region of the search space. For the OpenML MLP tuning benchmark, we utilize the defaults and search spaces provided in HPOBench (Eggensperger et al., 2021), and construct Gaussian priors for each hyperparameter with their mean on the default value, and a standard deviation of 25% of the hyperparameter’s domain. For the DL case studies, we utilize defaults from each task’s repository and, for numerical hyperparameters, once again set the standard deviation to 25% of the hyperparameter’s domain. For categorical hyperparameters, we place a higher probability on the default. As such, the quality of the prior is ultimately unknown, but serves as a proxy for what a practitioner may choose and has shown to be a reasonable choice (Anastacio & Hoos, 2020). For all experiments, we run πBO with β = N/10, where N is the total number of iterations, in order to make the prior influence approximately equal in all experiments, regardless of the number of allowed BO iterations. We investigate the sensitivity to β in Appendix A, and the sensitivity to prior quality in Appendix G.
Baselines We empirically evaluate πBO against the most competitive approaches for priors over the optimum described in Section 2.3: BOPrO (Souza et al., 2021) and BO in Warped Space (BOWS) (Ramachandran et al., 2020). To contextualize the performance of πBO, we provide additional, simpler baselines: random sampling, sampling from the prior and BO with prior-based initial design. The latter is initialized with the mode of the prior in addition to its regular initial design. In our main results, we choose Spearmint (with EI) (Snoek et al., 2012) for this mode-initialized baseline, simply referring to it as Spearmint. See Appendix F for complete details on the experiments.
4.2 ROBUSTNESS OF πBO
First, we study the robustness of πBO. To this end, we show that πBO benefits from informative priors and can recover from wrong priors, being consistent with our theoretical results in Section 3.3. To this end, we consider a well-known black-box optimization function, Branin (2D), as well as two surrogate HPO tasks from the Profet suite (Klein et al., 2019): FC-Net (6D) and XGBoost (8D). For these tasks, we exemplarily show results for πBO implemented in the Spearmint framework. As Figure 2 shows, πBO is able to quickly improve over sampling from the prior. Moreover, it improves substantially over Spearmint (with mode initialization) for all informative priors, staying up to an order of magnitude ahead throughout the optimization for both strong and weak priors. For wrong priors, πBO displays desired robustness by recovering to approximately equal regret as Spearmint. In contrast, Spearmint frequently fails to substantially improve from its initial design on the strong and weak prior, which demonstrates the importance of considering the prior throughout the optimization procedure. This effect is even more pronounced on the higher-dimensional tasks FCNet and XGBoost, where BO typically spends many iterations at the boundary (Swersky, 2017). Here, πBO rapidly improves multiple orders of magnitude over the initial design, displaying its ability to efficiently exploit the information provided by the prior.
4.3 COMPARISON OF πBO AGAINST OTHER PRIOR-GUIDED APPROACHES
Next, we study the performance of πBO against other state-of-the-art prior-guided approaches. To this end, we consider optimizing 5 hyperparameters of an MLP for classification (Eggensperger et al., 2021) on 6 different OpenML datasets (Vanschoren et al., 2014) and compare against BOPrO (Souza et al., 2021) and BOWS (Ramachandran et al., 2020). For minimizing confounding factors, we implement πBO and BOWS in HyperMapper (Nardi et al., 2019), the same framework that BOPrO runs on. Moreover, we let all approaches share πBO’s initialization procedure. We consider a budget of 50 iterations as it is common with ML practitioners (Bouthillier & Varoquaux, 2020). In Figure 3, we see that πBO offers the best performance on four out of six tasks, and displays the most consistent performance across tasks. In contrast to them BOWS and BOPrO, πBO also comes with theoretical guarantees and is flexible in the choice of framework and acquisition function.

heading: 4.4 CASE STUDIES ON DEEP LEARNING PIPELINES
text: Last, we study the impact of πBO on deep learning applications, which are often fairly expensive, making efficiency even more important than in HPO for traditional machine learning. To this
end, we consider two deep learning case studies: segmentation of neuronal processes in electron microscopy images with a U-Net(6D) (Ronneberger et al., 2015), with code provided from the NVIDIA deep learning examples repository (Przemek et al.), and image classification on ImageNette128 (6D) (Howard, 2019), a light-weight adaptation of ImageNet (Deng et al., 2009), with code from the repository of the popular FastAI library (Howard et al., 2018). We mimic the setup from Section 4.3 by using the HyperMapper framework and identical initialization procedures across approaches. Gaussian priors are set around the publicly available default values, which are results of previous tuning efforts of the original authors. We again optimize for a practical budget of 50 iterations (Bouthillier & Varoquaux, 2020). As test splits for both tasks were not available to us, we report validation scores.
As shown in Figure 4, πBO achieves a 2.5× time-to-accuracy speedup over Vanilla BO. For ImageNette, the performance of πBO at iteration 4 already surpasses the performance of Vanilla BO at Iteration 50, demonstrating a 12.5× time-to-accuracy speedup. Ultimately, πBO’s final performance establishes a new state-of-the-art validation performance on ImageNette with the provided pipeline, with a final accuracy of 94.14% (vs. the previous state of the art with 93.55%1).

heading: 5 CONCLUSION AND FUTURE WORK
text: We presented πBO, a conceptually very simple Bayesian optimization approach for leveraging user beliefs about the location of an optimum, which relies on a generalization of myopic acquisition functions. πBO modifies the selection of design points through a decaying weighting scheme, promoting high-probability regions under the prior. Contrary to previous approaches, πBO imposes only minor restrictions on the type of priors, surrogates or frameworks that can be used. πBO provably converges at regular rates, displays state-of-the art performance across tasks, and effectively recovers from poorly specified priors. Moreover, we have demonstrated that πBO can yield substantial performance gains for practical low-budget settings, improving on the state-of-the-art for a real-world CNN tuning tasks even with trivial choices for the prior. For practitioners who have historically relied on manual or grid search for HPO, we hope that πBO will serve as an intuitive and effective tool for bridging the gap between traditional tuning methods and BO.
πBO sets the stage for several follow-up studies. Amongst others, we will examine the extension of πBO to non-myopic acquisition functions, such as entropy-based methods. Non-myopic acquisition functions do not fit well in the current πBO framework, as they do not necessarily benefit from evaluating inputs expected to perform well. We will also combine πBO with multi-fidelity optimization methods to yield even higher speedups, and with multi-objective optimization to jointly optimize performance and secondary objective functions, such as interpretability or fairness of models.
1https://github.com/fastai/imagenette#imagenette-leaderboard, 80 Epochs, 128 Resolution

heading: 6 ETHICS STATEMENT
text: Our work proposes an acquisition function generalization which incorporates prior beliefs about the location of the optimum into optimization. The approach is foundational and thus will not bring direct societal or ethical consequences. However, πBO will likely be used in the development of applications for a wide range of areas and thus indirectly contribute to their impacts on society. In particular, we envision that πBO will impact a multitude of fields by allowing ML experts to inject their knowledge about the location of the optimum into Bayesian Optimization.
We also note that we intend for πBO to be a tool that allows users to assist Bayesian Optimization by providing reasonable prior knowledge and beliefs. This process induces user bias into the optimization, as πBO will inevitably start by optimizing around this prior. As some users may only be interested in optimizing in the direct neighborhood of their prior, πBO could allow them to do so if provided with a high β value in relation to the number of iterations. Thus, if improperly specified, πBO could serve to reinforce user’s beliefs by providing improved solutions only for the user’s region of interest. However, if used properly, πBO will reduce the computational resources required to find strong hyperparameter settings, contributing to the sustainability of machine learning.

heading: 7 REPRODUCIBILITY
text: In order to make the experiments run in πBO as reproducible as possible, we have included links to repositories of our implementations in both Spearmint and Hypermapper, with instructions on how to run our experiments. Moreover, we have included in said repositories all of the exact priors that we have used for our runs, which run out of the box. The priors we used were, in our opinion, well motivated as to avoid subjectivity, which we hope serves as a good frame of reference for similar works in the future. Specifically, Appendix 4.4 describes how we ran our DL experiments, Appendix ?? goes into the implementation in further detail, and Appendix D displays the exact priors for all our experiments and prior strengths. Our Spearmint implementation of both πBO and BOWS is available at https://github.com/piboauthors/PiBO-Spearmint, and our HyperMapper implementation is available at https://github.com/piboauthors/ PiBO-Hypermapper. For our results on the convergence of πBO, we have provided a complete proof in Appendix E.

heading: A BETA ABLATION STUDY
text: We consider the effect of the β hyperparameter of πBO introduced in Section 3.2, controlling the speed of the prior decay. To show the effect of this hyperparameter, we display the performance of πBO for the toy and surrogate-based benchmarks across all prior qualities. We emphasize the trade-off between high-end performance on good priors and robustness to bad priors. In general, a higher value of β yields better performance for good priors, but makes πBO slower to recover from bad priors. This behaviour follows intuition and the results provided in Section 3.3.
In Figure 5, we display how πBO performs for different choices of β, and once again provide sampling from the prior and Spearmint as baselines. Following the prior decay parameter baseline by (Souza et al., 2021), we show that the choice of β = 10 onsistently gives one of the best performances for strong priors, while retaining good overall robustness. Nearly all choices of β give a final performance better than that of Spearmint for good priors. Additionally, there is a clear relationship between final performance and β on all good priors. This is best visualized in the weak XGBoost experiment, where the final performances are distinctly sorted by increasing β. Similar patterns are not as apparent in the final performance on wrong priors. This behaviour highlights the benefits of slowly decaying the prior. Overall, πBO is competitive for a wide range of β, but suffers slightly worse final performance on good priors for low values of β.
B πBO VERSATILITY
We show the versatility of πBO by implementing it in numerous variants of SMAC Hutter et al. (2011), a well-established HPO framework which supports both GP and RF surrogates, and a majority of the myopic acquisition functions mentioned in Section 2. We showcase the performance of πBO-EI, πBO-PI, πBO-UCB and πBO-TS on the general formulation of πBO with a GP surrogate, as well as πBO-EI with an RF surrogate, which requires a minor adaptation.
B.1 GENERAL FORMULATION OF πBO
To allow for the universality of πBO across several acquisition function, we must consider the various magnitudes of acquisition functions. As UCB and TS typically output values in the same order of magnitude and sign as the objective function, we do not want the behaviour of πBO to be affected by such variations.
The solution to the problem referenced above is to add a simple affine transformation to the observations, {yi}ni=1, by subtracting by the incumbent, y∗n. As such, we consider at each time step not the original dataset, Dn = {(xi, yi)}ni=1, but the augmented dataset D̂n = {(xi, yi − y∗n)}ni=1. With this formulation, we get the desired scale- and sign-invariance in the UCB and TS acquisition functions, without changing the original strategy of any of the acquisition function. Notably, this change leaves prior-weighted EI and PI unaffected.
B.2 RANDOM FOREST SURROGATE
We now demonstrate πBO with a RF surrogate model. In the SMAC implementation of the RF surrogate, the model forms piece-wise constant mean and covariance functions. Naturally, this leads to the EI, PI or UCB acquisition function surface being piece-wise constant as well. Consequently, an acquisition function with a RF surrogate will typically have a region of global optima. The choice of the next design point is then selected uniformly at random among the candidate optima. We wish to retain this randomness when applying πBO. As such, we require the prior to be piece-wise constant, too. To do so, we employ a binning approach, that linearly rounds prior values after applying the decay term. The granularity of the binning decreases at the same rate as the prior, allowing the piece-wise constant regions of the prior grow in size as optimization progresses. In Figure 9, we demonstrate the importance of the piece-wise constant acquisition function by showing the point selection when applying a πBO with a continuous prior to an RF surrogate (left) and when applying the binning approach (right). Notably, the smooth prior on the left repeatedly proposes design points very close to previous points, as the prior forces the selection of points near the boundary of a promising region. Thus, the surrogate model rarely improves, and the optimization gets stuck at said boundary for multiple iterations at a time. This is best visualized at iteration 5 and 10, where similar points have been selected for all iterations in the time span. With the binned prior on the right, the selection of design points occurs randomly within a region, avoiding the static point selection and updating of non-modified approach. In Figure 8, we report the performance of πBO with a RF surrogate and the binning approach. This approach is competitive, as it provides substantial improvement over SMAC, improves over sampling from the prior, and quickly recovers from misleading priors. Notably, the binning is not required for discrete parameters, as the piece-wise constant property holds by default. Thus, this adaptation is only necessary for continuous parameters.

heading: C OTHER PRIOR-BASED APPROACHES
text: We now demonstrate the performance of πBO for five different functions and HPO Surrogates: Branin, Hartmann-6, as well as three tasks from the Profet suite - SVM, FCNet and XGBoost. We compare all frameworks for priors over the optimum - namely BOPrO Souza et al. (2021), BOWS Ramachandran et al. (2020), TPE Bergstra et al. (2011), PS-G Li et al. (2020). The performance of πBO is shown on two different frameworks - Spearmint and Hypermapper - to allow for fair comparison and display cross-framework consistency. As BOWS is implemented in Spearmint and BOPrO in Hypermapper, they appear in the plots retaining to their framework. We display each approach with vanilla Spearmint/Hypermapper, with normal initialization, as an additional baseline. Moreover, we display the performance of πBO implemented in Spearmint, as well as Mode + Spearmint, on the MLP tuning tasks.

heading: D PRIOR CONSTRUCTION
text: We now present the method by which we construct our priors. For the synthetic benchmarks, we mimic (Souza et al., 2021) by offsetting a Gaussian distribution from the optima. For our case studies, we choose a Gaussian prior with zero correlation between dimensions. This was required in order to have a simple, streamlined approach that was compatible with all frameworks. We constructed the priors once before conducting the experiments, and kept them fixed throughout.
Synthetic and Surrogate-based HPO Benchmarks For these benchmarks, the approximate optima of all included functions could be obtained in advance, either analytically or empirically through extensive sampling. Thus, the correctness of the prior is ultimately known in advance. For a function of dimensionality d with optimum at x∗, the strong and weak prior qualities were constructed by using a quality-specific noise term = { i}di=1 and quality-specific standard deviation as a fraction of the search space. For the strong prior πs(x), we use a small standard deviation σs = 1% and construct the prior as
πs(x) ∼ N (x∗ + , σs), i ∼ N (0, σs). (10) We construct the weak priors analogously by using a larger standard deviation σw = 10%. For our 20 runs of the strong and weak prior, this procedure yielded us 20 unique priors per quality type, with varying offsets from the true optimum. Additionally, the density on the optimum is substantially
larger for the strong prior than the weak prior. No priors with a mean outside the search space were allowed, such priors were simply replaced. For Branin, we only considered one of the three Branin optima for this procedure, since not all included frameworks support multi-modal distributions. For the wrong prior, we construct it similarly to the strong prior, but around the empirical maximum, x∗̄, of the objective function in the search space. Since this point was far away from the optimum for all benchmarks, we did not add additional noise. So, the wrong prior πm is constructed as πm(x) ∼ N (x∗̄, σs), (11) which means that the wrong prior is identical across runs for a given benchmark.

heading: E PROOFS
text: Here, we provide the complete proofs for the Theorem and Corollary introduced in 3.3. In addition, we provide insight into the interplay between β, the prior π, and the value of the derived bound Cπ,n.
Theorem 1. Given Dn, K`, π, σ, `, R and the compact set X ⊂ Rd as defined above, the loss Ln incurred at iteration n by EIπ,n can be bounded from above as
Ln(EIπ,n,Dn,H`(X ), R) ≤ Cπ,nLn(EIn,Dn,H`(X ), R), Cπ,n = ( maxx∈X π(x)
minx∈X π(x)
)β/n .
(12)
Proof. To bound the performance of EIπ to that of EI, we primarily need to consider Lemma 7 and Lemma 8 by Bull Bull (2011). In Lemma 7, it is stated that for any sequence of points {xi}ni=1, dimensionality d, kernel length scales `, and p ∈ N, the posterior variance s2n on xn+1 will, for a large value C, satisfy the following inequality at most p times,
sn(xn+1; `) ≥ Cp−(ν∧1)/d(log p)γ , γ = { α, ν ≤ 1 0, ν > 1 . (13)
Thus, we can bound the posterior variance by assuming a point in time np where Eq. 13 has held p times. We now consider Lemma 8 where, through a number of inequalities, EI is bounded by the actual improvement In
max ( In −Rs,
τ(−R/σ) τ(R/σ) In
) ≤ EIn(x) ≤ In + (R+ σ)s, (14)
where In = (f(x∗n)−f(x))+, τ(z) = zΦ(z) +φ(z) and s = sn(xn; `). Since πBO re-weights EIn by πn, these bounds need adjustment to hold for EIπ,n. For the upper bound provided in Lemma 8, we make use of maxx∈X πn(x) to bound EIπ,n(x) for any point x ∈ X :
EIπ,n(x) maxx∈X πn(x) = EIn(x)πn(x) maxx∈X πn(x) ≤ EIn(x) ≤ In + (R+ σ)s. (15)
For the lower bounds, we instead rely on minx∈X πn(x) in a similar manner:
max ( In −Rs,
τ(−R/σ) τ(R/σ) In
) ≤ EIn(x) ≤
EIn(x)πn(x) minx∈X πn(x) = EIπ,n(x) minx∈X πn(x) . (16)
Consequently, EIπ can be bounded by the actual improvement as
min x∈X πn(x) max
( In −Rs,
τ(−R/σ) τ(R/σ) In
) ≤ EIπ,n(x) ≤ max
x∈X πn(x)(In + (R+ σ)s). (17)
With these bounds in place, we consider the setting as in the proof for Theorem 2 in Bull Bull (2011), which proves an upper bound for the EI strategy in the fixed kernel parameters setting. At an iteration np, p ≤ np ≤ 3p, the posterior variance will be bounded by Cp−(ν∧1)/d(log p)γ . Furthermore, since In ≥ 0 and ||f ||H`(X )) ≤ R, we can bound the total improvement as∑
i Ii ≤ ∑ i f(x∗i )− f(x∗i+1) ≤ f(x∗1)−min f ≤ 2||f ||∞ ≤ 2R, (18)
leaving us a maximum of p times that In ≥ 2Rp−1. Consequently, both the posterior variance s2np and the improvement Inp are bounded at np. For a future iteration n, 3p ≤ n ≤ 3(p+ 1), we use the bounds on EIπ , snp and Inp to obtain the bounds on the EIπ loss:
Ln(EIπ,Dn,H`(X ), R) = f(x∗n)−min f ≤ f(x∗np)−min f
≤ EIπ,np(x
∗)
minx∈X πn(x)
τ(R/σ)
τ(−R/σ)
≤ EIπ,np(xn+1) minx∈X πn(x) τ(R/σ) τ(−R/σ)
≤ maxx∈X πn(x) minx∈X πn(x) τ(R/σ) τ(−R/σ) ( Inp + (R+ σ)snp ) ≤ ( maxx∈X π(x)
minx∈X π(x)
)β/n τ(R/σ)
τ(−R/σ) (2Rp−1 + (R+ σ)Cp−(ν∧1)/d(log p)γ),
where the last inequality is a factor Cπ,n = (
maxx∈X π(x) minx∈X π(x)
)β/n larger than the bound on
Ln(EI,Dn,H`(X ), R).
Corollary 1. The loss of a decaying prior-weighted Expected Improvement strategy, EIπ, is asymptotically equal to the loss of an Expected Improvement strategy, EI:
Ln(EIπ,n,Dn,H`(X ), R) ∼ Ln(EIn,Dn,H`(X ), R), (19)
so we obtain a convergence rate for EIπ of Ln(EIπ,n,Dn,H`(X ), R) = O(n−(ν∧1)/d(log n)γ).
Proof. We simply compute the fraction of the losses in the limit,
lim n→∞ Ln(EIπ,Dn,H`(X ), R) Ln(EI,Dn,H`(X ), R) ≤ lim n→∞
( maxx∈X π(x)
minx∈X π(x)
)β/n = 1. (20)
E.1 SENSITIVITY ANALYSIS ON Cπ,n
We now provide additional insight into how Cπ,n depends on the choices of prior and β made by the user. To do so, we consider a typical low-budget setting and display values of Cπ,n at iteration 50. We consider a one-dimensional search space where with a Gaussian prior located in the center of the search space. In the plot below, we display how the choice of σ, given as a percentage of the search space, and β, the prior confidence parameter, yield different values of Cπ,n. We see that, for approximately half of the space, the upper bound on the loss is at least 80% (bright green or yellow) of the upper bound of EI, and only a small region of very narrow priors (dark blue) give a low guaranteed convergence rate.

heading: F EXPERIMENT DETAILS
text: F.1 FRAMEWORKS
Our implementations of πBO require little change in the supporting frameworks, Spearmint and HyperMapper, and we stay as close to the default settings as possible for each framework. For both Spearmint and HyperMapper, we consider a Matérn 5/2 Kernel. For particularly strong priors, rounding errors can cause the prior to be zero in parts of the search space, potentially affecting πBO’s convergence properties. To avoid these rounding errors and ensure a strictly positive prior, we add a small constant, = 10−12, to the prior throughout the search space for all prior qualities. For the initial sampling from the prior, we truncate the distribution by disallowing sampled points from outside the search space, instead re-sampling such points. During optimization, we do not to explicitly truncate the prior, as points outside the search space are never considered during acquisition function maximization. Thus, the prior is effectively truncated to fit the search space without requiring additional consideration.
To the best of our knowledge, there is no publicly available implementation of BOWS, so we reimplemented it in Spearmint. For the Spearmint implementation of BOWS, we provide warped versions of each benchmark, obtaining 20 unique warpings per prior quality and benchmark. We truncate the prior by restricting the warped search space to only include the region which maps back to the original search space through the inverted warping function. For all other approaches, we use the original, publicly available implementations. Notably, the available implementation of Hyperopt TPE does not support bounded search spaces under our priors; as a compromise, when asked to evaluate outside the search space we return an empirically obtained maximum on the objective function inside the search space.
We use the search spaces, prior locations and descriptions used by (Souza et al., 2021) for the toy and surrogate HPO problems. We now provide additional details about the benchmarks and case study tasks used, their associated search spaces and priors, and the resources used to run these studies.
F.2 BENCHMARKS AND CASE STUDIES
Branin The Branin function is a well-known synthetic benchmark for optimization problems. The Branin function has two input dimensions and three global minima.
Hartmann-6 The Hartmann-6 function is a well-known synthetic benchmark for optimization problems, which has one global optimum and six dimensions.
SVM A hyperparameter-optimization benchmark in 2D based on Profet (Klein et al., 2019). This benchmark is generated by a generative meta-model built using a set of SVM classification models trained on 16 OpenML tasks. The benchmark has two input parameters, corresponding to SVM hyperparameters.
FCNet A hyperparameter and architecture optimization benchmark in 6D based on Profet. The FC-Net benchmark is generated by a generative meta-model built using a set of feed-forward neural networks trained on the same 16 OpenML tasks as the SVM benchmark. The benchmark has six input parameters corresponding to network hyperparameters.
XGBoost A hyperparameter-optimization benchmark in 8D based on Profet. The XGBoost benchmark is generated by a generative meta-model built using a set of XGBoost regression models in 11 UCI datasets. The benchmark has eight input parameters, corresponding to XGBoost hyperparameters.
OpenML MLP The OpenML MLP tuning tasks are provided through HPOBenchEggensperger et al. (2021), and train binary classifiers on real-world datasets. The 5D parameter space consists of four continous parameters and one integer parameter.
U-Net Medical The U-Net (Ronneberger et al., 2015) is a popular convolutional neural network architecture for image segmentation. We use the implementation and evaluation setting from the popular NVIDIA deep learning examples repository (Przemek et al.) to build a case study for optimizing hyperparameters for U-Net. The NVIDIA repository is aimed towards the segmentation of neuronal processes in electron microscopy images for the 2D EM segmentation challenge dataset
(Arganda-Carreras et al., 2015; Cardona et al., 2010). We optimize 6 hyperparameters of the U-Net pipeline.
ImageNette ImageNette (Howard, 2019) is a subset of 10 classes of ImageNet (Deng et al., 2009) and is primarily used for algorithm development for the popular FastAI library (Howard et al., 2018). The FastAI library contains a convolutional neural network pipeline for ImageNette, that is used by all competitors on the ImageNette leaderboard. We base our case study on the 80 epoch, 128 resolution setting of this leaderboard and optimize 6 of the hyperparameters of the FastAI ImageNette pipeline.
F.3 SEARCH SPACES AND PRIORS
The search spaces for each benchmark are summarized in Table 1 (Branin and Profet), Table 2 (OpenML MLP), and Table 3 (ImageNette and U-Net). For the Profet benchmarks, we report the original ranges and whether or not a log scale was used. However, in practice, Profet’s generative model transforms the range of all hyperparameters to a linear [0, 1] range. We use Emukit’s public implementation for these benchmarks (Paleyes et al., 2019).
F.4 CASE STUDY DETAILS
Training details deep learning case studies Both case studies are based on existing deep learning code, whose hyperparameters we vary according to the HPO. In both case studies, we enabled mixed precision training, and for ImageNette-128 to work in conjunction with Spearmint, we had to enable the MKL_SERVICE_FORCE_INTEL environment flag. For all further details, we refer to the supplementary material containing our code.
Resources used for deep learning case studies For U-Net Medical we used one GeForce RTX 2080 Ti GPU, whereas for ImageNette-128 we used two GeForce RTX 2080 Ti GPU’s. Also, we used 4 cores and 8 cores respectively, of an AMD EPYC 7502 32-Core Processor. In Table 4 we list the GPU hours needed for running the deep learning case studies as well as the emitted CO2 equivalents.
Assets deep learning case studies In addition to the assets we list in the main paper, the U-Net Medical code base we used employs the 2D EM segmentation challenge dataset (Arganda-Carreras et al., 2015; Cardona et al., 2010), which is available for for the purpose of generating or testing non-commercial image segmentation software. We include licenses of all existing code assets we used in the supplementary material containing our code.

heading: G SENSITIVITY TO PRIOR STRENGTH
text: We investigate the performance of πBO when providing priors over the optimum of various qualities. To show the effect of decreasing the prior strength, a grid of prior qualities, with varying widths and
offsets from the optimum, are provided. Thus, priors range from the strong prior in the results, to weak, correct priors and sharp, misplaced priors.
From Figures 14- 18, it is shown that πBO provides substantial performance across most prior qualities for all benchmarks but Branin, and recoups its early losses on the worst priors in the bottom left corner. πBO demonstrates sensitivity to the width of the prior, as the optimization does not progress as quickly for well-located priors with a larger width. Additionally, πBO’s improvement over the Spearmint + Mode baseline is further emphasized, as this baseline often fails to meaningfully improve over the mode in early iterations.

Review summaries:
In this article the authors propose to incorporate domain knowledge on where good configurations are located in Bayesian optimization (BO). They do so by weighting the acquisition function by a prior that decays and reverts to uniform as iterations go. The asymptotic rate of convergence is shown to be of the same order as the non-prior version. Empirical tests are provided on various synthetic and  hyperparameter tuning tasks, with diverse baseline methods and ablation studies.

The paper proposes a method to incorporate prior information about the optimum in the standard Bayesian optimisation (BO) setting. The prior is specified as a smooth function over the range having high values where the experimenter think the optimum may exist with high probability and low values otherwise. This prior function is incorporated in the BO workflow through multiplication with the EI acquisition function. The authors show that when the prior function is decayed then this BO achieves the usual sublinear regret rate of a standard BO asymptotically. The synthetic experiments are extensive and convincing. The real case studies are limited, but sufficient.

## Summary:  PiBO is a very straightforward paper that seeks to incorporate prior knowledge about the optimum to accelerate Bayesian optimization.   They achieve this by simply multiplying the acquisition function (Expected Improvement, in the paper) by the prior distribution, and then maximizing that. They then decay the prior in order to deal with mis-specified priors. The authors also provide some theory that this weighted acquisition function performs (for some particular definition of performance) no worse than EI times a constant that depends on the decay rate. It’s a reasonable idea; honestly I’m surprised no paper has tried this before.   Synthetic and real-world experiments indicate that: -With a well-specified prior, PiBO demonstrates superior performance over it’s basic EI counterpart.  -With a poorly-specified prior, PiBO performs poorly worse than it’s EI counterpart but is usually able to recover given enough iterations.