To Be Greedy, or Not to Be – That Is the Question for Population Based Training Variants
Authors: Alexander Chebykin
Tanja Alderliesten
Peter Bosman
Venue: Accepted by TMLR ()

Abstract: Achieving excellent results with neural networks requires careful hyperparameter tuning, which can be automated via hyperparameter optimization algorithms such as Population Based Training (PBT). PBT stands out for its capability to efficiently optimize hyperparameter schedules in parallel and within the wall-clock time of training a single network. Several PBT variants have been proposed that improve performance in the experimental settings considered in the associated publications. However, the experimental settings and tasks vary across publications, while the best previous PBT variant is not always included in the comparisons, thus making the relative performance of PBT variants unclear. In this work, we empirically evaluate five single-objective PBT variants on a set of image classification and reinforcement learning tasks with different setups (such as increasingly large search spaces). We find that the Bayesian Optimization (BO) variants of PBT tend to behave greedier than the non-BO ones, which is beneficial when aggressively pursuing short-term gains improves long-term performance and harmful otherwise. This is a previously overlooked caveat to the reported improvements of the BO PBT variants. Examining their theoretical properties, we find that the returns of BO PBT variants are guaranteed to asymptotically approach the returns of the greedy hyperparameter schedule (rather than the optimal one, as claimed in prior work). Together with our empirical results, this leads us to conclude that there is currently no single best PBT variant capable of outperforming others both when pursuing short-term gains is helpful in the long term, and when it is harmful.

Published in Transactions on Machine Learning Research (05/2025)
To Be Greedy, or Not to Be - That Is the Question for Population Based Training Variants
Alexander Chebykin
a. a.chebykin@cwi.nl
Centrum Wiskunde & Informatica Amsterdam, the Netherlonds
Tanja Alderliesten
Calderticstennhhmmc..oo
Leiden University Medical Center Leiden, the Netherlands
Peter A. N. Bosman Centrum Wiskunde & Informatico Amsterdam, the Netherlonds Delft University of Technology Delft, the Netherlands
peler.bosman@cui.w
Reviewed on OpenReview: https: openreview. net/ forum? id= 3qmmmysN
Abstract
Achieving excellent results with neural networks requires careful hyperparameter tuning, which can be automated via. hyperparameter optimization algorithms such as Population Based Training (PBT). PBT stands out for its capability to efficiently optimize hyperparam- eter schedules in parallel and within the wall-clock time of training single net work. Several PBT variants have been proposed that improve performance in the experimental settings considered in the associated publications. However, the experimental scttings and tasks vary across publications, while the best previous PBT variant not always included the comparisons, thus making the relative performance PBT variants unclear. In this work, we empirically evaluate five single-objective PBT variants on set of image classification and reinforcement learning tasks with different setups (such increasingly large search spaces). We find that the Bayesian Optimization (BO) variants of PBT tend to behave greedier than the non-BO ones, which is beneficial when aggressively pursuing short-term gains improves long-term performance and harmful otherwise. This is previously overlooked caveat to the reported improvements of the BO PBT variants. Examining their theoretical properties, we find that the returns of BO PBT variants are guaranteed asymptotically approach the returns of the greedy hyperparameter schedule (rather than the optimal one, as claimed in prior work). Together with our empirical results, this leads us to conclude that there is currently no single best PBT variant capable of outperforming others both when pursuing short-term gains is helpful in the long term, and when it is harmful.
1 Introduction
Neural network training requires setting values of many hyperparameters, process that is both crucial for good performance and time-consuming, Hyperparameter Optimization (HPO) algorithms aim to automate Hyperparameter (HP) tuning (Bergstra et al., 2011; Feurer & Hutter, 2019).
The Population Based Training (PBT) algorithm (Jaderberg et al., 2017) and its variants (Parker-Holder et al., 2020; 2021; Wan et al., 2022; Dalibard & Jaderberg, 2021) stand out for several reasons. Firstly, they are designed to efficiently optimize a schedule of HPs (rather than one set of fixed values), which improves performance (Toshchilov & Hutter, 2017; Tan & Le, 2021). Unlike other dynamic HPO algorithms (Baydin

---

Published in Transactions on Machine Learning Research (05/2025)
et al., 2018; Badia et al., 2020; Li et al., 2022), PBT is general, i.e. not restricted to a specific HP such learning rate, or to specific setting such as Reinforcement Learning (RI.). Secondly, PBT runs within the wall-clock time of single training of a network, which is desirable in practice. Thirdly, PET is convenient to scale: adding parallel workers improves results without strongly inffuencing the wall-clock time of the algorithm. Finally, PBT can directly optimize non-differentiable objectives of interest, such as accuracy of a classifier, or score of an RL agent.
PBT was built upon in Population Based Bandits (PB2, Parker-Holder et al. (2020)) where Bayesian Optimization (BO) was introduced for sampling new HP values, PB2-Mix (Parker- Holder et al., 2021) where the BO setup of PB2 was extended to include discrete HPs, Bayesian Generational PBT (BG-PBT, Wan et al. (2022)) where a more advanced BO approach was used, and Faster Improvement Rate PBT (FIRE-PBT, Dalibard & Jaderberg (2021)) where the greedy nature PBT was addressed. In each publication, the proposed variant outperformed previous variants included in the experiments, which unfortunately did not always include the best previous variant. Additionally, cach subsequent publication performed evaluations different lasks and in different setups (e.g,, different implementations of RL lasks, different computation budgets).
These issues make it difficult to say if one of the PBT variants is substantially better than all others, and should therefore be preferred in practice. The question of whether there is one superior algorithm is the key question we aim to answer in this work. Towards that goal, we conduct an impartial empirical evaluation of the PBT variants in image classification and RL settings, using the FashiouMNIST (Xiao et al., 2017), CIFAR-10/100 (Krizhevsky & Hinton, 2009), and TinylmageNet (Stanford CS231N, 2017) datasets for the former, and subset of Brax tasks (Freeman et al., 2021) for the latter. Furthermore, look into the theoretical foundations of the BO variants of PBT to better understand the proved guarantees and how they correspond to the behaviour of the algorithms in practice.
Although there exist extensions of PBT for multi-objective optimization (Dushatskiy et al., 2023) and architecture search (Franke et al., 2020; Wan et al., 2022; Chebykin et al., 2023), the focus of this article is on single-objective optimization of HPs only. Furthermore, we do not aim to compare PBT variants (which we also refer to as PBTS) to other НPО algorithms.
The main contributions of our paper threefold:
We investigate whether the more recently introduced PBT variants are always superior to the earlier ones on a set of image classification and RL tasks.
We study how the performance and runtime of the PBT variants change when the task setup varied.
Theoretical and mechanistic causes for the observed differences in performance are explored.
2 Dynamic HPO
2.1 Problem statement
We formalize the problem setting by building upon the notation of Jaderberg et al. (2017). In the single- objective setting, the goal is maximize the final performance of a neural network by optimizing schedule of HPs. Let us denote the HP scarch space H, the HPs used during training between times and t+ 1 h E H, the maximum time T 1, the weight space as W, the weights as 0₂ E W, the objective function Q W - IR, and the training procedure as train W x HT + W. The dynamic HPO optimization problem can be written as:
(h))== = arg max ((train(01((bb)))) (h.)..
(1)
Note that while Eq. formalizes dynamic HPO in that varies over time, the optimization is written as static or non-sequential (arg max is applied to the entire schedule) to correspond to the informal problem
2

---

Published in Transactions on Machine Learning Research (05/2025)
hg mrr
by.
Weights (innel steps)
Suggest HPs (for all outer steps)
Train model (from 1 to 7)
Suggest HPs (for the next outer step)
Train model (from to (+1)
Oett
.+
ht
hge2
Objective Q at time T
Objective or proxy 9t+1 at time 1+1, updated weights 6p-f
HPs (outer steps)
(a) Kon-sequential optimization
(b) Sequential optimization (Eq. 2)
(c) Inner and outer optimization steps
(Eq. 1)
Figure 1: Illustration of concepts relevant to the problem statement (see Section 2.1).
statement of maximizing the final performance. Drawing the distinction between optimizing a schedule statically (non-sequentially) or dynamically (sequentially) is important for explaining our theoretical results in Section 4. In Figure 1, panels (a) and (b) illustrate the nou-sequential and sequential optimization loops.
For sequential optimization, consider step x + W, a logical (outer) step of PBT algo- rithm that corresponds to multiple inner steps (in which the weights are updated via, e.g., gradient descent). The hyperparameters are updated after each outer step. We can expand train(f:|(h,]]] 1T step(step(... step(0) [/r)). hr-1)(ftr). If we denote the objective or its proxy after steps as 9: H + IR dynamic sequential HPO can be written as a sequence of problems:
T = {arg max 91 (h1), arg max [h
arg max gr or (h... h1-1)).
(2)
h1
h2
hr
The sequential nature of optimization entails that previous choices cannot be altered. Consequently, directly optimizing Q at each step would make the optimization greedy, while optimizing an alternative de could lead to better long-term outcomes (as showcased by FIRE-PBT, see Section 3.1).
Let us further denote by steptnner the number of inner optimization steps taken within each outer step. Since step is applied T times, the total number of inner optimization steps is total = T step Figure Ic shows an example where each outer step corresponds to stePinner = 3 inner steps. For the visualized two outer steps, the total number of inner optimization steps total is equal to 6.
2.2 Dynamic HPO algorithms
In this section, provide overview of dynamic HPO algorithms that not PBT variants. While there are many HPO algorithms that tune static values of HPs (Bergstra et al., 2011; Li et al., 2018; Falkner et al., 2018; Awad et al., 2021; Tan et al., 2024), few can efficiently tune schedules of HPs (although any HPO algorithm can learn an HP schedule by introducing separate variables, one for each HP at each time step, this is unlikely to be efficient). One approach to dynamic HPO is to adjust the HPs via hypergradient descent (Baydin et al., 2018; Li al., 2022). While using hypergradients can be efficient, is also restrictive of HPs that can be tuned this way: e.g., only learning rate (in (Baydin et al., 2018)) or HPs that are both continuous and differentiable (in (Zahavy et al., 2020; Li et al., 2022)). Additionally, hypergradient algorithms introduce HPs of their own that require tuning (Paul et al., 2019; Jin et al., 2021).
Another research direction focuses on dynamic HPO specifically for RL, which can be performed via bandit optimization (Badia et al., 2020), evolutionary methods (Tang & Choromanski, 2020), hypergradients (Zahavy et al., 2020), or by estimating HP quality via weighted importance sampling (Paul et al., 2019).
Biedenkapp et al. (2020) use RL for dynamic optimization in the general setting of dynamic algorithm configuration. While promising, the approach relies on RI. that requires large number of roll-outs to learn,
3

---

Published in Transactions on Machine Learning Research (05/2025)
thus making it too inefficient for dynamic HPO on time-consuming tasks such neural network training (e.g., it required 40,000 training runs in the practical setting of tuning CMA-ES (Adriaensen et al., 2022)).
Unlike the approaches discussed above, the PBT variants are general algorithms that were empirically shown to be capable of tuning arbitrary HPs on challenging tasks. We further discuss them in Section
3 PBT variants
3.1 Exploration via perturbation ("Perturbation PBTs")
PBT Jaderberg et al. (2017) introduced the first PBT algorithm for dynamic HPO. In PBT, the training of N models interleaved with HPO. solution pt at (logical) time & is a tuple of model weights and HPs: (0i, ht). A population P= = { encompasses all solutions. At each time = ..... T, all models are trained in parallel for step inner steps corresponding to one outer step: 0/ step(f?(h)), and evaluated: 4:+1 Q(+++1).
After evaluation has been performed at time t, the exploit procedure is applied. Jaderberg et al. (2017) experimented with several exploit procedures and found truncation selection to perform best which was then used in all the PBT variants we describe. In truncation selection, each the X% worst-performing models is replaced with a copy of one of the X% best-performing ones (chosen randomly).
Finally, the explore procedure applied the copies created by the exploit procedure. In PBT, real-valued HPs are explored via perturbation: each HP is multiplied by randomly chosen factor from a predefined set (e.g., 20.5,2.0)) categorical HPs are randomly resampled. After the exploit step, the interleaved training and HPO continues with the updated population (as described above).
FIRE-PBT Dalibard & Jaderberg (2021) observed that PBT can behave too greedily, polentially harming its long-tene tong-term performance. This is addressed by splitting the population into hierarchical subpopulations PI..J and a subpopulation of "cvaluators". All subpopulations PI... execute the standard PBT algorithm (in parallel) but optimize different objective functions. P1 directly optimizes the target objective Q. Each subsequent subpopulation P3 optimizes Improvement Rate (TR) objective defined relative to P3-1- Omitting details, for (50), 2ht) E Pj. IR measures how fast Q improves when the weights '0} are trained with the currently best HPs from Pj-1: i-',;. The "evaluators" " enable the computation of IR by performing this training. Additionally, the weights trained by an evaluator can replace the weights associated with h- thus allowing the weights from P3 to propagate to Py-1. Using IR instead of Q in the subpopulations P2... makes optimization less greedy, see Dalibard & Jaderberg (2021) for further details.
3.2 Exploration via Bayesian optimization ("Bayesian PBTs")
PB2 Parker- Holder et al. (2020) replace the random perturbation explore procedure of PBT with BO approach based on Time- Time-Varying Gaussian Process Bandits (TV-GPB) (Bogunovic et al., 2016). At each time f, changes in performance relative to the previous step are computed: yi = qी - -gi-1- and collected in a dataset: D, = D.-1 U { (vi. 1, 1 Afterwards, a Gaussian Process (GP) model is fit to the dataset. and new HPs are selected by optimizing an acquisition function that extends TV-GPB to a parallel setting. The thcoretical guarantces for PB2 (and other Bayesian PBTs) are based on the TV-GPB formalism that is further discussed in Section 4.
The BO model in PB2 is defined only for real-valued hyperparamoters, while the categorical HPs are randomly resampled. To include categorical variables into the BO setup of PB2, Parker-Holder et al. (2021) introduce the TV. EXP3. M multi-armed bandit algorithm for the time-varying setting. TV. M is used to sample the categorical variables, after which a time-varying GP model relying on joint categorical-comiinuuus kornel is learned and used to sample the contimuuus variables.
PB2-Mix
1 Note that we describe synchronous version of PBT.
4

---

Published in Transactions on Machine Learning Research (05/2025)
BG-PBT BG-PBT (Wan et al., 2022) builds upon the previous Bayesian PBT variants by explicitly considering ordinal variables in its extended version of the CASMOPOLITAN algorithm (Wan et al., 2021) ) This algorithm was chosen for its suitability to high-dimensional and mixed-input problems thanks to adaptations such as trust regions. BG-PBT places focus on enabling neural architecture search, which is out of scope for our article, we therefore omit the related adaptations from our analysis and experiments (which therefore apply to a variant of BG-PBT without architecture search).
4
Analysis
4.1
The returns of the Bayesian PBTs asymptotically approach the returns of the greediest schedule
et al. (2020) formalize the problem of dynamic HPO as optimizing time-varying objective lunction (.(h)). In notation, it is equivalent to Q(train(O) [h,, (h. (h+))=)): evaluating the weights trained with schedule where the HPs before time are fixed, while the HPs at can be varied. The stated goal is to optimize the final performance (r(hr) with respect to a hyperparameter schodule {he)2m The optimization is sequential: the best choice at each step is defined as h2 = arg maxh, Se(hy), where Se is the improvement in F, after one outer step of an algorithm: fe(h,) = (ha)) Ft-1(h--1)- This corresponds to the dynamic sequential HPO setup in Eq. 2 with 9r = ft. The regret defined as (ht)) = fe(h.) - fi()).. Let us reproduce Lemma 1 of Parker-Holle
et al. (2020):
Lemma 1 HParker-Holder et al. (2020)). Mazinizing the final performance Fr of a model with respect to a given hyperparameter schedule {hr] is equivalent to mazimizing the time-varying black- box function ft (he) and minimizing the corresponding cumulative regret (h,):
max (r max Σ fe(h.) min Σ (h.).
We find two issucs with this lemma. The first is minor tochnicality unrolated to our main argument: max and min should be argmax and argmin. This due to the proof (Eq. 3) using Fr - Fi in place of (hrr). Subtracting a constant (as (h,) is assumed be) affects max but not argmax.
Secondly, find that the lemma is proved in the setting of non-sequential optimization (Eq. 1) rather than the sequential optimization actually performed by PBTs (Eq. 2). We show that F, the regret relative to the schedule {hr) lacks meaning in the non-sequential setting, rendering any conclusions about it moot. Finally, we show that the lemma does not hold in the sequential setting. Let us start with the original proof:
T
max (Fr(hr)) - (i.)) = max
(h.(h))) - P max s(hh)) = min En(
(3)
Let us replace max with argmax, specify the arguments, replace Fi with Fo to correct the indexing of the telescoping sum, and expand the last transition (in accordance to Parker-Holder et al. (2020)):
T
arg max (Fr(hr) Fo(h))) (h. )
= arg max (h, J
[Fh(h)) F(-1(h+-1)
T
T
T
= arg max (A.)
fe(hs)
(4.3)
arg max (h.) 1=1
[f((h) - s((ba)] = arg min
Σ (ha).
(h1)2
t=1
(4)
Observe that due to the dependencies between the summands, the argument of argmax must be the entire schodule for the transitions the original proof (Eq. 3) to hold as written. Thus, the lemma proved in the non-sequential setting. Let us next consider transition (4.3) in Eq. 4: it holds because for each time t, fo (h) is constant (so these values do not influence argmax). However, this holds not just for (he) but for any
5

---

Published in Transactions on Machine Learning Research (05/2025)
schedule (he H": for each time t, f(( is constant, and therefore transition (4.3) will hold also with fi( in place of (h,, on the right side. Therefore, maximizing Jt is equivalent to minimizing the cunulative regret relative to this arbitrary schedule, (ha)) = fc - f((h))
Thus, we can use the proof of the lemma to conclude that the regret relative to all possible schedules is minimized, making the original result about the specific regret lack meaning. The notion of minimizing regret relative a schedule is problematic if the final performance is optimized con-sequentially: the optimal schedule will maximize Fr regardless of the schedule used to define the regret, seen in the transition (4.3). The lemma ignores the sequential nature of optimization that is fundamental to the design of PBT's and that is required for meaningful notion of regret relative to a schedule.
Next, we give a high-level argument that the lemma does not hold in the sequential selting, with details provided in Appendix A. fe(hs) is defined as F((he)) - Fi-1(hi-1)) which reduces to F(:h)) during sequential optimization because (1t-)) is constant at time t. With fr(h,) = (he)), performance the current step is maximized rather than the final performance. Due to potential dependencies on the past choices, greedily optimizing F, leads to worse final results (unless no dependencies are present, which would make the greedy solution optimal). Thus, contrary to the statement of Lemma 1, sequentially maximizing ft is not equivalent to maximizing the final performance Fr.
In the theory underlying all Bayesian PBTs, Lemma connects minimizing regret to achieving optimal final performance. The associated regret bounds still hold, and it is true that the returns of the schedules discovered by Bayesian PBTs asymptotically approach those of {he To as shown by Parker-Holder al. (2020). Our contribution lies in reinterpreting these results: the returns achieved by the Bayesian PBTs asymptotically approach the returns of the greedy solution (which we find (hr)== to be) that will only be optimal if previous hyperparameter choices do not restrict achievable future results (which cannot be generally expected).
4.2 Limitations of the current theoretical approach
The theoretical asymptotic behavior, while informative, does not completely describe algorithm's behaviour in practice. Since Bayesian PBTs work with a population, a solution that does not lead to the best performance at the current step may still survive until the next step, where it may actually perform the best. Together with the search space exploration performed by BO, this enables Bayesian PBTs to discover schodules different from the greediest one (note that the exploit procedure can also influence the (asymptotic) behavior despite not being included in the theory of Bayesian PBTs, see Appendix B).
Nonetheless, Bayesian PBTs are solving an optimization problem that is fundamentally not aligned with the stated goal of optimizing the final performance. The TV-GPB formalization is well-suited for time-vayying problems where previous choices do not affect future results, such as adjusting a thermostat (Bogunovic et al., 2016). However, dynamic HPO typically does not fit this criterion, as is a timo-linked problem (Bosman, 2005), meaning that previous choices can strongly influence downstream results: e.g., reducing the learning rate too fast may improve performance in the short term, but the end leads to premature convergence and a suboptimal final result.
Note that the standard PBT optimizes the same greedy objective function Bayesian PBTss but it does less effectively due to its simple exploration via random perturbation (in contrast to BO). However, since the greedy objective function being optimized does not completely align with the true objective function (the final performance), the less effective optimization of PBT can lead to better final results.
FIRE-PBT stands out bocause its higher-order subpopulations greedily optimize not the current performance but the improvement rate, which encourages better long- term results. Changing the optimization problem is one way of aligning an online algorithm with the target objective, see Section 6 for further discussion.
4.3 Step size as mechanistic cause for the greediness of the PBT variants
All PBT variants operate on two levels. As discussed in Sections 2.1 and 3, on the upper level, a PBT performs T outer steps of HPO, while the lower level, within each outer step, the underlying models are
6

---

Published in Transactions on Machine Learning Research (05/2025)
trained for stepinner gradient descent (GD) steps, to the total of totaliuner = T stepinner steps over the entire run. While the intel budget is fixed, the number of outer steps T is a hyperparameter of PBT that can be set freely by appropriately adjusting stePinner' e.g., if the training budget is 100 epochs, they can be split into 100 outer steps of 1 epoch, or 10 outer steps of 10 epochs, etc.
PBT variants optimize the objective function after one outer step, which can correspond to an arbitrary number of inner steps. PBTs are blind to how long the inner optimization is: no matter if the weights are trained for single GD step or for many epochs, it is still single outer step for a PBT. What happens if we increase the number of outer steps T? Holding totaluuer constant, this requires decreasing step A PBT will still optimize one outer step ahead but fewer inner steps ahcad. In terms of inner steps, the optimization becomes greedier, as shorter-term improvements are pursued.
Thus, one mechanistic cause for how greedy a specific PBT variant behaves is the number of outer steps T (or, oquivalently, stePinner). It is not clear how should be set, as none of the PBT publications discuss it, while effectively using different values: 200 in PBT, 20 in PB2, 50 in PB2-Mix, 150 in BG-PBT.
Decreasing T' could decrease greediness, as it is equivalent to increasing stePineers i.e, how many inner steps ahcad the optimization is done. However, this would also make the schedule less granular and reduce the amount of exploration an algorithm can do, which could degrade performance in challenging search spaces.
The optimal amount of greediness and thus the optimal value of T'' (or stepimuer) is likely to be task-specific, and may even vary during the optimization: Wan et al. (2022) empirically observe that their chosen stepinner leads to excessively greedy behavior on some tasks, and add linear annealing of stePimner for these tasks. We argue that step is an important hyperparameter which could influence the behavior of PBTs in any task. We empirically demonstrate in Section 5.4 that varying the nunber of outer steps can change not only the final performance but also which PBT variant performs best.
5
Experiments & Results
5.1 General setup
We compare the PBT variants on image classification, RL, and toy problems. In our main classification experiments, the PBTs optimize hyperparameters of ResNet-12 (He et al., 2016) on Fashion-MNIST (Xiao et al., 2017) and CIFAR-10 (Krizhevsky & Hinton, 2009) datasets (see Appendix C for further details).
In main RL experiments, Proximal Policy Optimization (PPO) (Schulman et al., 2017) agent is trained on the Hopper and Humanoid tasks from the Brax library (Freeman et al., 2021). These tasks were selected because Wan et al. (2022) reported that PBTs tended to get stuck in local optima if the step size was small and we wanted to see if Perturbation PBTs could avoid local optima better than Bayesian PBTs.
By default, only the Learning Rate (LR) is tuned in the classification experiments, i.c., the small search space is used (see Appendix E for the description of search spaces) but we found that for the Humanoid task this leads to minimal performance differences between PBTs (sec Section 5.5) which motivated using the large search space in the RL experiments. For classification, the large search space is used in the scaling experiments (Sections 5.6 and 5.7) so that the scaling of PB2-Mix could be observed. PB2-Mix is equivalent to PB2 in contimuous search spaces and so is excluded from the experiments in the small space.
Unless specified otherwise, the PBTs are run with a population of size 22, see Appendix D for the explanation, as well as other implementation details of PBTs. Five random seeds were used for the classification and toy experiments, while seven seeds were used for RL (known to have high variability). We typically plot Interquartile Mean (IQM) and Interquartile Range (IQR) in order to focus on average tendencies rather than outliers, similar to previous work (Parker-Holder et al., 2020). Statistical testing is described in Appendix F.
5.2 Toy problems: plain and time-linked
In this section, we describe two toy problems: one where effective greedy optimization leads to better results, and another where the less greedy optimization is preferable.
7

---

Published in Transactions on Machine Learning Research (05/2025)
PBT PB2
BG-P6T FIRE-POT
BG-PBT FIRE-PAT
BG-PBT
BG-PET
PA2
P92
FIRE-P8T
P62
FIRE-PST
1.00
1.2
Objectivet
objective
1.1
0.8
0.50
1.0
0.5
0.6
0.00
0.0
500
1000
0
500
1000
500
1000
500
1000
SGD steps
SGD steps
5GD steps
SGD steps
(a) PlainToy
(b) TimeLinkedToy
Figure 2: The performance PBTs on the toy problems. For each problem, on the left, the IQM of the objective is shown (with TQR shaded), and on the right, the average value of the hyperparameter (with the standard deviation shaded).
The problems are created based on the toy problem from Jaderberg et al. (2017), where a quadratic function Q(0) 1.2 (0g + 0f) is maximized without knowing its formula. Instead, a differentiable surrogate function is provided ((0) = 1.2 - (hoff + h2ff), with h = [ho, h1] as the hyperparameters to be optimized. The gradient is V -2h0, therefore h should be greedily maximized to reach the optimum faster. We slightly adjust this problem and refer to it as PlainToy. Namely, we make 0 one-dimensional, and replace h with 2- to prevent h from going to infinity (while allowing it to increase up to 2). The objective is ()) = 1.2 8², the surrogate is 91 (0) = 1.2 (2 - h)6², the gradient is Vğ = 2(2 - 4)0. The initial values are uniformly randomly sampled from [0.9, 1.1]. This problem is designed so that the greody behavior of roducing to fast as possible is also the optimal behavior that leads to the best final result. On this problem, the greedier algorithms are expected to outperform the less- gre-dyr ones.
Our second problem, TimeLinkedToy, is designed so that the greodiest solution is optimal in the short-term but suboptimal in the long-term. It is an extension of the PlainToy with an additional penalty that is incurred by deviating from a linear decay schedule. As such, 2 is replaced with max(2 - c P:-1, 0), where Pt-1 = Eizo 1 - - (hr denotes the historical value of l at time i) and c 0.2 (a constant to control the impact of the penalty). The "max" " function is added to prevent the surrogate gradient from degrading the objective when the penalty grows large (making the gradient incorrect). The objective is g2(() = 1.2 02, the surrogate is (0()) 1.2 max(2 h c- Pt-1. 0) 82, the gradient is Vg2 -2 max(2 c Pt 0) 8. With e < 1, rapidly reducing h gives the best results in the first steps but the penalty gradually adds up, eventually stopping all progress.
5.3 Bayesian PBTs underperform Perturbation PBTs when greedy choices are harmful in the long term
Based on our theoretical analysis in Section 4, Bayesian PBTs should perform worse than Perturbation PBTs when short-term improvement is detrimental to long-term success (and they should perform better if not). The goal of the experiments in this section is to empirically validate these claims.
Toy problems We start with the PlainToy problem, where the greediest solution is optimal. Figure 2a shows that all PBT variants successfully solve PlainToy by roducing the hyperparameter h zero. Bayesian PBTs find the optimum faster than PBT, achieving better intermediate results. The less greedy FIRE-PBT reduces l the slowest, which leads to the slowest improvement (see the inset in Figure 2a (left)).
The results are different for the TimeLinkedToy problem (Figure 2b), where the greediest solution is optimal in the short but not the long term. Bayesian PBTs again quickly reduce h to zero, which leads to large penalties downstream due to deviating from the target linear decay schedule. Cumulative penalties eventually stop all progress of Bayesian PBTS, leading to poor final performance. Standard PBT, which cannot reduce the LR as quickly, performs better than the Bayesian PBTs, while FIRE-PET achieves the best result by successfully addressing time linkage.
8

---

Published in Transactions on Machine Learning Research (05/2025)
PBT
BG PBT
BG-PBT FIRE-PBT
PBT
BG-PBT FIRE-PBT
BG-PBT FIRE-PST
PB2
PB2
PB2
95.0
95
10-1
Learning rate
10-1
Accuratyy
Accuracyt
92.5
94
Learning
10--
10
90.0
93
10-1
87.5
10
20000
40000
20000 40000
0
20000
40000
0
20000 40000
steps
SGD steps
SGD steps
steps
(a) Fashion-MNIST
(b) CIFAR-10
Figure 3: The performance of PBTs on the classification tasks. For each datasct, on the left, the IQM of the accuracy is shown, and on the right, the median LR of the best solution. The IQRs are shaded.
Classification Figure 3 shows the results of optimizing the LR of an image classifier. For both datasets, Perturbation PBTs on average outperform Bayesian PBTs in terms of final accuracy. This is due to Bayesian PBTs decaying the LR too aggressively. It is interesting to see in Figure 3a that the latest PBT variant, BG-PBT, reduces LR the fastest and on average performs better at the start of the training - only to be later overtaken by less recent. PR2 that reduces the LR somewhat slower. PB2, in its turn, is overtaken by PBT that reduces the LR even more gradually. However, by that point, the eventual winner, FIRE-PBT, already outperforms others despite starting off as the worst. Figure 3b shows similar behaviour.
These results are consistent with our analysis in Section 4. They clearly demonstrate in a practical setting that more effective Baycsian optimization can, in fact, be greedier optimization, ultimately leading to worse results. Note, however, that depending on the budget, different algorithms should be considered best: for Fashion-MNNSTT, BG-PBT performs best after s 5, 000 steps, whereas PB2 the best after z 10, 000 steps. This implies that the properties of the task as well as the budget influence which PBT should be used for obtaining the best results.
Reinforcement learning Figure 4 shows the scores of the PBTs RI. tasks when either 30 100 outer steps are used. In the latter case, the algorithm with the highest final score on both tasks is Bayesian PBT (BG-PBT for Hopper, PB2-Mix for Humanoid), performing well throughout the training. Although pattern of rapid improvement followed by stagnation is visible in Figure 4b (similar to the classification tasks), Perturbation PBTs generally fail to overtake the Bayesian ones like they did the classification tasks. When 30 outer steps are used (Figure 4a), Bayesian PBTs again tend be better, although PBT marginally outperforms BG-PBT on Hopper (while continuing to perform poorly on Humanoid). We can conclude that in complex RL tasks and search spaces, the greedier but more effective optimization of Bayesian PBTs can lead to better results than the less greedy and less effective optimization of Perturbation PBTs.
PBT -BB--Mx FIRE PBT
-PST -P82-Mix PBT -G--PUT
-PBT -P82 Mix FIRE
-PBT PB2 -FIRE-PTT
2500
P02
-DG-PTT
-G-PPTT
P02 DDG-POT
2000
2000
8000
8000
Scoret
Scoret
Score1
1500
1500
6000
6000
1000
1000
500
2000
500
2000
0.0
1.0
1.5
0.0
0.5
1.0
1.5
0.5
1.0
1.5
0.0
1.0
1.5
Environment steps
1eB
Environment steps
leB
Environment steps
1e6
Environment steps
1e8
Hopper
Humanoid
Hopper
Humanoid
(a) 30 outer steps
(b) 100 outer steps
Figure 4: The performance (IQM, with IQR shaded) of PBTs on the RL tasks with 30 or 100 outer steps.
9

---

Published in Transactions on Machine Learning Research (05/2025)
PBT
BG-PBT FIRE-PBT
PBT PB2
BG PBT FIRE-PBT
$ PBT P82
1 P82-Mix BG-PBT
$ FIRE-P6T
PPT
PB2/MiX BG-PBT
FIRE-PET
PB2
2420
95.5
10000
94
Accuracy
Accuracyt
Scoret
1830
Score
95.0
92
0000
1230
94.5
90
3 10
30
100
10
30
100
10
30
100
10
30 100
Number of
Number steps
Number of steps
Number of steps (d) Humanoid
(a) Pashion-MNTST
(b) CIFAR-10
(c) Hopper
Figure 5: The performance (IQM and IQR) of the PBT variants as the number of outer steps is varied, while the number of inner steps (Stochastic Gradient Descent (SGD) steps for classification, environment steps for RL) is kept constant.
5.4 The number of outer steps impacts the greediness and the relative performance of PBT variants
In Section 4.3, we reasoned that increasing the number of outer steps (while keeping the number of inner steps constant) should make a PBT variant greedier. Let us first examine the results for the classification tasks Figure (a, b). Bayesian PBTs perform well when the number of outer steps very low (3) as they are able effectively find good LR values despite having few exploration opportunities, unlike the less-effective Perturbation PBTs (which consequently perform worse in this setting). However, as the number of outer steps increases, the performance of Bayesian PBTs tends to worsen, since they start to effectively optimize the increasingly shorter-term objective.
On the other hand, Perturbation PBTs strongly improve when the nunber of outer steps goes from 3 to 10, as they have more opportunities to explore the search space but not enough to arrive at the greedy solution that optimizes short-term performance improvement. However, as the number of outer steps is further increased, the Perturbation PBTs become capable of effective greedy optimization, and their performance deteriorates (at 30 steps for PBT, 100 steps for FIRE-PBT).
The impact of the number of outer steps on RL scores (Figure 5 (c, d)) does not follow clear pattern. PBT peaks at different number of outer steps in different tasks while FIRE-PBT show consistently poor performance. BG-PBT tends to outperform PB2 and PB2-Mix but as the number of outer steps is increased, its performance improves on Hopper and deteriorates on Humanoid. As discussed in Section 5.3, greedy optimization does not appear as detrimental for these tasks as for the classification tasks, explaining absence of similar interpretable pattern. Nonetheless, the number of outer steps affects both the absolute and the relative performance of the PBT variants (in most cases), highlighting the importance of this HP also in tasks without strong time linkage.
5.5 As the search space size is increased, performance of PBTs tends to improve
We investigated how the relative and absolute performance of PBT variants change when the size of the search space is varied. Figure 6 shows the performance of PBTs in search spaces of different sizes (note that search spaces differ between the classification and RI. tasks, see Appendix E...
As can be seen in Figure 6 (a, b), for classification, FIRE-PBT tends to perform best in all search spaces, with performance increasing in larger search spaces (which shows that optimizing additional hyperparameters is beneficial). The performance of PBT improves when going from the small to the medium search space but deteriorates in the large space. The latter observation is likely due to inability of PBT to optimize the increased number of variables. The performance of Bayesian PBTs tends to increase with the search space size, although without reaching the level of performance of FIRE-PBT.
Figure 6 (c, d) shows that the performance of all PBT variants improves on the RL tasks as more HPs are optimized in larger search spaces. The relative performance of PBTs varies strongly, with algorithm
10

---

Published in Transactions on Machine Learning Research (05/2025)
f PBT
PB2-Mix
f FIRE-PST
$ PBT P82-Mix $ FIRE-PBT
# PBT
P82-Mix $ FIRE-P6T BG--BT
PBT
PB2/ BG-PBT
& FIRE-PET
PB2
f PB2
BG-PBT
2400
Accuracyt
93.4
Accuracyt
92.5
Score
Score
94.8
800
6000
small
medium large
small
medium
large
small
medium
large
small
medium
large
Search space
Search space
Search space size
Search space size
(a) Mashion-MNIST
(b) CIFAR-10
(c) Hopper
(d) Humanoid
Figure 6: The performance (IQM and IQR) of the PBT variants as the search space size is increased. Some IQR marks are invisible due to the IQR being too narrow.
significantly outperforming others or even consistently achieving higher average rank (see Appendix F)- Interestingly, the difference in performance of the same PBT variant across search spaces can be larger than the differences between PBTs in the same search spacc. The disappointing relative performance of FIRE-PBT in most RL search spaces despite its excellent performance across classification search spaces serves as evidence that FIRE-PBT is not generally superior to the other PBT variants.
5.6 As the population size is increased, performance of PBTs tends to improve
We investigated the effect of inercasing the population size on the performance the PBT variants. Bayesian PBTs were designed to work well with a small population (lypically 8, although scaling larger populations was shown to be beneficial) while Perturbation PBTs tend to use population size of least 20.
Consequently, even for the time-linked classification tasks, PBT and FIRE-PBT do not outperform the Bayesian PBTs if the population size is 8 (see Figure 7 (a, b)). However, as the population size increases, FIRE-PBT strongly outperforms all the other variants on the classification tasks, with PBT tending to be second-best as the population size reaches 50.
Figure 7 (c, d) shows that on RL tasks, Perturbation PBTs again perform poorly with a population size of 8. While they tend to improve with an increasing population size, they typically still underperform Bayesian PBTs, except for PBT on Hopper. PBT performs well not only with a population size of 22 (as previously seen in Section 5.3), but with population size of 50 well. Which properties of the task lead to these results is open question. In general, performance of all PBTs tends to improve as the population size is increased, consistently with their nature as population-ban based algorithms. At the same time, the relative positions of the PBT variants changes across population sizes and lasks, with no algorithm significantly outperforming others, except for FIRE-PBT on classification tasks with population sizes of 22 and 50 (see Appendix F).
PBT $ PBZ-Mix FIRE-PET
$ PBT
PBZ-Mix $ FIRE-PBT BG-PBT
# PBT PB2-Mix F FIRE-PET BG-PBT
$ PBT
PB2 Mix
F PIRE-PUT
PB2
BG.PBT
$ P82
8G-PBT
2400
10000
Accuracyt
95
Accuracy
92.5
Scare ?
Score
1600
8000
90.0
6000
22
50
8
Population size
Population size
Population size
Population size
(a) Fashion-MNIST
(b) CIFAR-10
(c)
Hopper
(d) Humanoid
Figure 7: The performance (IQM and IQR) of the PBT variants as the population size is increased.
11

---

Published in Transactions on Machine Learning Research (05/2025)
Time (hours)4
PBT
Time (minutes)
80
PAT
(minutes)
PRT
P62
P82
PB2 BG-PBT
10
PBZ-Mix
P82 Mix
BG-PET
BG-PET
FIRE-PBT
20
FIRE-PET
FIRE-PST
5
10
small
medium
large
22
Number of steps
Search space
Population size
(a) Training and evaluation time as number of steps is varied
(b) Exploration time as
(c) Exploration time (per population member) as population size is varied
search space is varied
Figure 8: Wall-clock time (mean + st. dev.) taken by the PBTs on the Hopper task in various sctups.
5.7 PBTs scale differently in terms of wall-clock time
An attractive property of PBT variants is their ability to optimize hyperparameters within the wall-clock time of single training rum, if all N networks in the population are trained in parallel. We would like add muance by considering how much extra time the advanced PBT variants spend, and what they spend it on.
The first source of extra time spending is intermediate evaluations. At the end of each outer step, all networks need to be evaluated, with more outer steps requiring more evaluations and longer wall-clock time.
All PBT variants except for FIRE-PBT use the same number of evaluations. FIRE-PBT requires an order of magnitude more intermediate evaluations to compule the IR objective used in the higher-order subpopulations. As result, FIRE-PBT tends to take the longest wall-clock time, which is noticeable for RL tasks where evaluations interrupt efficient Brax-enabled training. Figure (a) shows that increasing the number of steps increases the total time spent on training and evaluation by all the algorithms but especially by FIRE-PBT.
The second source of extra time spending comes from selecting new hyperparamcters in the explore step. The Bayesian PBTs optimize the hyperparameters of the GP and the acquisition function, while the random perturbation of PBT is iea-tnnstatt FIRE-PET fits several GPs when computing the IR objective. The cost of these additional operations could be influenced by the search space and the population size.
As can be seen in Figure 8 (b), increasing the search space size strongly affects only BG-PBT and PB2-Mix. BG-PBT slows down considerably when going from contimuous search space (small) to mixed search space (medium), but does not meaningfully slow down when the number of variables is further increased in large. PB2-Mix, on the other hand, is slower in the large scarch space than in the medium scarch space. This is consistent with BG-PBT relying on a more efficient. BO algorithm. Figure 8 (c) shows that increasing the population size does not affect per-population-meee creates more data for the fitting of a GP, which appears to slow down more than lincarly (which would correspond to horizontal line). The exploration of FIRE-PBT incurs negligible costs, as does the exploration of PBT.
update times, except for PB2-Mix: a larger population
5.8 Do our observations generalize to similar settings?
Our computation budget is limited (since each PBT run entails training multiple neural networks, the total computational cost of the main experiments reach se 900 GPU-days) but we would still like to know whether changes in the experimental setup would substantially alter the results. For this purpose, we run additional experiments in selected settings.
Classification CIFAR-100 (Krizhevsky & Hinton, 2009) is a step-up in complexity from CIFAR-10 in number of classes. Tiny ImageNet (Stanford CS231N, 2017) is larger still in number of classes, number of samples, and resolution (which we upsample to 224²). This motivates training a larger architecture (ConvNeXi-T (Liu et al., 2022)) for 3 times more steps. We use the large search space, and 100 outer steps, further details are provided in Appendix C.
Figure 9a shows that FIRE-PBTT performs best on CIFAR-100, as expected. The standard PBT does not outperform the Bayesian PBTs, likely due to the search space being large, which is consistent with our
12

---

Published in Transactions on Machine Learning Research (05/2025)
75
-98T
50
-180
-PST
-P8T
70
P82 Hix 40
-822
Accuracy
P62 Mix
-240
PS2--85
1200
PP7
P82 MX
9G PST
8G-P8T
BG-FET
PBT
65
FIRE-PBT
FIRE PST
-300
-FRRT-POT
1000
40030
0.5 Environment steps
0.0
0.5
SGD steps
SGD steps
1e8
Environment steps
1e8
(a) CIFAR-100
(b) Tiny ImageNet
(c) Pusher
(d) Walker
Figure 9: The performance (IQM, with IQR shaded) of PBTs on additional tasks.
findings presented in Section 5.5. On Tiny ImageNet, however, FIRE-PET manages only to catch up to other PBTs but is not able to overtake them. The combination of increased difficulty of the underlying task and the large search space may strain the simple exploration procedure of FIRE-PBT that nonetheless performs best. in the small space, expected (see Appendix G). These results highlight the difficulty in choosing the PBT variant that would perform best for a specific lask, search space, and budgel, as discussed in Section 5.3.
Reinforcement learning We chose to evaluate on Brax Pusher and Walker tasks because they were not previously optimized by any PBT variant. Figure 9 shows that the algorithı that achieves the best final result, PB2-Mix, tends to perform well throughout optimization, with no issues caused by greediness (similarly to what observed on Hopper and Humanoid). PB2-Mix outperforming BG-PBT on both tasks is consistent with our previous results, where PB2-Mix was also found to be better than BG-PBT in some settings. On the other hand, in some previously considered settings, BG-PBT tended to perform better, preventing the conclusion that one of the two algorithms is superior.
6 Discussion & Conclusion
In this work, we compared five single-objective PBT variants on image classification and RL tasks, and found no single best algorithm that is capable of outperforming others in all (or even most) considered settings. This is partially explained by different PBT variants exhibiting (and different tasks requiring) different degrees of greediness. Tf good long-term results are achieved by optimizing short-term performance gains, then effective optimization of Bayesian PBTs is beneficial. If, however, effectively optimizing short-term gains compromises long term results, then even the slandard PBT can oulperform Bayesian PBTs, with FIRE-PBT performing even better. In our experiments, optimizing RL hyperparameters fell into the first category, while optimizing the LR of an image classifier typically fell into the second onc.
From a theoretical perspective (as discussed in Sections 4.1 and 4.2), the underwhelming results of BO in linkel settings stem from effectively solving an optimization problem that is not fully aligned with the desired goal of maximizing final performance. Is there an alternative to formalizing dynamic HPO optimization of time-varying function? In Eq. we defined optimmm the schedule optimized over all steps simultaneously, which is incompatible with the efficiency brought by the sequential optimization of PBTSs Nonetheless, greedy optimization could be improved upon, e.g., by using an estimate of the future performance as the objective (Bosman, 2005), or, as in FIRE-PBT, by letting a subset of the population optimize an alternative objective directed at long-term performance.
The objective of all PBT variants except FIRE-PBT is optimize performance after one outer step of the algorithm. We observe that by changing how much inner optimization (e.g., via gradient descent) is performed within outer step, we influence how greedily algorithm behaves time-linked tasks (although it is not the only effect, as discussed in Section 4.3). Varying the step size can substantially affect both the absolute and the relative performance of the PBT variants in all settings, with no single best value across algorithms and settings. Potentially having to try several values reduces the benefits of PBTs:: efficiency and running within the wall-clock time of a single training. In order for a more complete picture of the upsides and downsides of different approaches to dynamic HPO to emerge, alternative dynamic HPO algorithms should be studied and compared both to PBTs and to each other.
13

---

Published in Transactions on Machine Learning Research (05/2025)
PBT variants typically do not add much wall-clock time to the training of the underlying model (if it is large enough); with the exception of FIRE-PBT. Its success in optimizing time-linked problems comes al a cost of an order of magnitude higher number of evaluations, which can be ignored if the evaluations are fast but adds up they are not (as in our RL experiments). Future work could investigate the possibility of performing lewer intermediate evaluations or formulating a more efficient alternative to the improvement rate objective.
While we separately varied the number of steps of PBTS, their population sizes, and the search-space sizes, did not tune them jointly, nor have we fully explored all PBT hyperparameters (e.g., varied À of the truncation selection only in a few settings, reported in Appendix I; the perturbation factor of FIRE-PBT was also varied in limited number of settings, see Appendix J). Arguably, efficient HPO algorithms should perform well without requiring tuming of their HPs, as this only shifts the HPO problem to a higher level. While the untuned hyperparameters is a limitation of our work, we believe that our conclusions on the interplay of the greediness and performance of the PBT variants time-linked settings are general, given their theoretical underpinnings that align with empirical results. Deeper investigation of the interaction between the hyperparameters, the performance, and the behaviour of PBTs potentially interesting subject for future work.
Although our theoretical and empirical results can explain behaviour of PBT variants optimizing the LR of a classifier, they are far from a complete explanation of behaviour of PBTs on arbitrary tasks. Further understanding why a PBT variant performs poorly or well on a specific underlying task is an intriguing avenue of future research.
Acknowledgments
We thank the anonymous reviewers for their helpful feedback. This work is part of the research project DAEDALUS which is funded via the Open Technology Programme of the Dutch Research Council (NWO), project number 18373; part of the funding provided by Elekta and ORTEC LogiqCare.
References
Steven Adriaensen, André Biedenkapp, Gresa Shala, Noor Awad, Theresa Eimer, Marius Lindauer, and Frank Hutter. Automated Dynamic Algorithm Configuration. Journal of Artificial Intelligence Research, 75: 1633-1699, December 2022. ISSN 1076-9757. doi: 10.1613/jair.1.1 1.1.922....... URL https: http:://wwwwjjaa jjrg/.rrg////////o//ooooo
index. hidee.ppp//aaatrraiiil////eeeee 11191///..i...ee//2/2.2... 13922.
Noor Awad, Neeratyoy Malii,, and Frank Hutter. DEHB: Evolutionary Hyberband for Scalable, Robust and Efficient Hyperparameter Optimization. In Proceedings of the Twenty-Ninth International Joint Conference
on Artificial Intelligence, volume 3, pp. 2147-2153, August 2021. doi: 10.24963 1224633/jccai.2/ /jccai.222///2.... /296. URL
https: http://ww..jj..o wwweaaa.rrgppoceeeeeeee http://rrceednns//2/////2/
ISSN: 1045-0823.
Adrià Puigdomenech Badia, Bilal Piot, Steven Kapturowski, Pablo Sprechmaun, Alex Vitvitskyi, Zhao- han Daniel Guo, and Charles Blundell. Agent57: Outperforming the Atari Human Benchmark. In Proceedings of the 37th International Conference on Machine Learning, pp. 507 517. PMLR, November 2020. URL https: sctps://prooeeee http///roeeeess.eeee// mlr https///11b//aaaaaaaaaa html. ISSN: 2640-3498.
Atilim Gunes Baydin, Robert Cornish, David Martinez-Rubio, Mark Schmidt, and Frank Wood. Online Learning Rate Adaptation with Hypergradient Descent. In Sizth International Conference Learning Rep- resentations, ICLR 2018. OpenReview.nec 2018. URL /ttps://opeerrviiie http://ppnrrrrieo.oeeeeer/rorraa net/forummiiiiiie -irnnidd---rAlle
James Bergstra, Rémi Bardenet, Yoshua Bengio, and Balázs Kégl. Algorithms for Hyper-Parameee Optimization. In Advances in Newral Information Processing Systems, volume 24, pp. 2546 2554. Curran Associates, Inc., 2011. URL https://proceeddie wwwpeeeddnnnnn.uuiss..... nwwrips.r.... wwwrips.cc/paaappeppee cctp:/ccpppppp////ea//// B6Gf77 Absroocttbttt........ html.
Andre Biedenkapp, H. Furkan Bozkurt, Theresa Eimer, Frank Hutter, and Marius Lindauer. Dynamic Algorithm Configuration: Foundation of a New Meta-Algoii Framework. In ECAI 2020, pp. 427- 434. IOS Press, 2020. doi: 10.3233 10.3233/FAIA2000 FA1220012.
URL https://ebooks. wwwpooee..n///o///......ooooooee
FAIA200122.
14

---

Published in Transactions on Machine Learning Research (05/2025)
Iija Bogunovic, Jonathan Scarlett, and Volkan Cevher. Time-Varyine Varying Gaussian Process Bandit Optimization.
In Proceedings of the 19th International Conference on Artificial Intelligence and Statisties, pp. 314-323. PMLR, May 2016. URL
wwwphngg.mm.......m. wwt.mmrr...ep.e... /ttp:////////oogoorcci..... htmll.l....mm..... ISSN: 1938-7228.
Peter A. N. Bosman. Learning, anticipation and time-doception in evolutionary online dynamic optimization. Proceedings of the 7th annual workshop on Genelic und evolulionary compulation, GECCO '05, pp. 39-47, New York, NY, USA, June 2005. Association for Computing Machinery. ISBN 978-1-0508-7800--. doi: 00.144/1102256.11000
URL https://doi: wwweei.org//... htrg/10.114//// 1145/11022511666 1102264.
Alexander Chebykin, Arkadiy Dushatskiy, Tanja Alderlicsten, and Peter Bosman. Shrink-Porturb Improves Architecture Mixing During Population Based Training for Neural Architecture Search. ECAI 2023 26th European Conference on Artificial Intelligence, 372, 2023. ISSN 0922- 6389. doi: 10.3233 (12244d288-b123--1 4184-4414-88888 5694448349.77
(152233/FAAA2300 /FAA2302944
URL attps://reposiee tudelft.uuul...... www.eettte/iillaaaateeet htt//iilannor/////ee//eau
Ekin Dogus Cubuk, Barrel Zoph, Jon Shlens, and Quoc Le. Ragnent: Practical Automated Data Augmentation with a Reduced Search Space. In H. Larochelle, M. Ranzato, R. Hadsell, M. F. Balcan, and H. Lin (cds.), Advances in Neural Information Processing Systems, volume 33, pp. 18613-18624. Cur- ran Associales, Inc., 2020. URL https://proceee:: http://ooeeee..eeeeeeee neuripa. Paper. .dff.
Valentin Dalibard and Max Jaderberg. Faster Improvement Rate Population Based Training, September 2021. URL http://arxiz: wttgg////////.g/////////// 1180//.019..1.......1
13800. MxXi:22109113800 [cs, stat].
Arkadiy Dushatskiy, Alexander Chebykin, Tanja Alderliesten, and Peter Bosman. Multi-Objective Population Based Training. In Proceedings of the 40th International Conference on Machine Learning, pp. 8969 8989. PMLR, July 2023. URL https://prooceeding. mml. htt.rpees///222/uaaatttttt
html. ISSN: 2640-3498.
Theresa Eimer, Marius Lindauer, and Roberta Raileanu. Hyperparameters in Reinforcement Learning and How To Tune Them. In Proceedings of the 40th International Conference Machine Learning, pp. 9104-9149. PMLR, July 2023. URL https://proceedingg mlr, .rress//////eeee hesss//222//ees 2000/eim html. ISSN: 2640-3498.
Stefan Falkner, Aaron Klein, and Frank Hutter. BOHB: Robust and Efficient Hyperparameter Optimization at Scale. In Proceedings of the 35th International Conference on Machine Learning, pp. 1437 1446. PMLR, July 2018. URL stttp::/proccee http:///pocceegs.../// .ml...ssml............... hwt.pppe///////lleeeereeee html. ISSN: 2640-3498.
Matthias Feurer and Frank Hutter. Hyperparameter optimization. Automated machine learning: Methods, systems, challenges, pp. 3 33, 2019. Publisher: Springer International Publishing.
Jörg K. H. Franke, Gregor Kochler, André Biedenkapp, and Frank Hutter. Sample-Efficient Automated Decp Reinforcement Learning. October 2020. URL
C. Daniel Freeman, Erik Frey, Anton Raichuk, Sertan Girgin, Igor Mordatch, and Olivier Bachem. Brax - A Differentiable Physics Engine for Large Scale Rigid Body Simulation. In Proceedings of the Thirty-fifth Conference on Neural Information Processing Systems, June 2021. URL /ttpps://pperrveeee wwwprrrwwwii.neeefooneeeeee net/forum? id=VävDInnjzIN.
Milton Friedman. The Use of Ranks to Avoid the Assumption of Normality Implicit in the Analysis of Variance. Journal of the American Statistical Association, 32(200):675 701, 1937. ISSN 0162-1459. doi: 10.2307/2279372. URL attps://www.1 wsstoooogg/taalee//250//////// Association, Taylor & Francis, Ltd.].
Publisher: [American Statistical
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep Residual Learning for Image Recogni- tion. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition 2016, pp. 770-778, 2016. URL Learning BearninggcVPR__000 CVPR_2016 2016 20____2001__________1__1______ html.
thecvf. http://oooent_cpre1111///////
15

---

Published in Transactions on Machine Learning Research (05/2025)
Sture Holm. A Simple Sequentially Rejective Multiple Test Procedure. Scandinavian Journal of Statistics, 6 (2):65-70, 70, 1979. ISSN 0303-6898. URL attpps://ww... the Foundation of the Scandinavian Journal of Statistics, Wiley].
org/stablee4661773. Publisher: [Board of
Max Jaderberg, Valentin Dalibard, Simon Osindero, Wojeiech M. Czarnecki, Jeff Donahue, Ali Razavi, Oriol Vinyals, Tim Green, lain Dunning, Karen Simonyan, Chrisantha Fernando, and Koray Kavukeuoglu. Population Based Training of Neural Networks. (XXi::7111.08846 [es). November 2017. URL http: arXiv: 1711.09846.
Yuchen Jin, Tianyi Zhou, Liangyu Zhao, Yibo Zhu, Chuanxiong Guo, Marco Canini, and Arvind Krishna- murthy. AutoL.RS: Automatic Learning-Rate Schedule by Bayesian Optimization on the Fly. In Proceedings of the 9th International Conference on Learning Representations, ICLR 2021. OpenReview.net, 2021. URL https://openret wtw.rrrrrrreeo.eeooouuttoeeeoo.e forum?iddSSrqMM __jju.
net/
Alex Krizhevsky and Geoffrey Hinton. Learning Multiple Layers of Features from Tiny Images. Master's thesis, University of Toronto, 2009. URL https://www. cs. toronto. htlu//Kriz/eearae feettrffttttteeeee 2009-000099-000 TR. pdf. Publisher: Toronto, ON, Canada.
Junyi Li, Bin Gu, and Heng Huang, A Fully Single Loop Algorithm for Bilevel Optimization without Hessian Inverse. Proceedings of the AAAI Conference on Artificial Intelligence, 36:7420-7434, June 2022.
ISSN 2374-3468. doi: 10.1609/ (0.1609/aaai.vo v3617. URL https://oja aaai. htw.dee..pp/MMt/rrrtiiieee view/20706.
Lisha Li, Kevin Jamieson, Giulia DeSalvo, Afshin Rostamizadeh, and Ameet Talwalkar. Hyperband: A Novel Bandit-Based Approach to Hyperparameter Optimization. Journal of Machine Learning Research, 18(185):
1 52, 2018, ISSN 1533-7928. URL http://jmlr org/ httg/apprss/v1//16 1atper/vvv1166650 1-1166555...0 $558.tml..
Zhuang Liu, Hanzi Mao, Chao- Yuan Wu, Christoph Feichtenhofer, Trevor Darrell, and Saining Xie. A convnet for the 2020s. In Proceedings of the IEEE/CVF conference on computer vision and pattern recognition, pp. 11976-11986, 2022.
Nya Loshchilov and Frank Hutter. SGDR: Stochastic Gradient Descent with Warm Restarts. In 5th Interna- lional Conference on Learning Representations, ICLR 2017, Toulon, France, April 24-26, 2017, Conference Track Proceedings. OpenReview.ned net, 2017. URL
net/forum 1d-mmmmdd-s-kksxx.....
Jack Parker-Holder, Vu Nguyen, and Stephen J Roberts. Provably Efficient Online Hyperparameter Opti- mization with Population-Base Bandits. In H. Larochelle, M. Ranzato, R. Hadsell, M. F. Balcan, and H. Lin (eds.), Advances in Neural Information Processing Systems, volume 33, pp. 17200 17211. Cur- ran Associates, Inc., 2020. URL https: ptttp::/pproceednss..eues neurips... httpeeeccppppppeeeeeeeeeee 77 Pat.oo---ppppppp...
Jack Parker-Holder Vu Nguyen, Shaan Desai, and Stephen J Roberts. Tuning Mixed Input Hyperparameters on the Fly for Efficient Population Based AutoRL. In Advances in Neural Information Processing Systems, volume 34, pp. 15513 15528. Curran Associates, Inc., 2021. URL https://proceedin ieariiiinnnnnnuuss.n...m neurips. cc/ 1ar.laaaa...1004000----aaa...... html.
Supratik Paul, Vitaly Kurin, and Shimon Whiteson. Fast Efficient Hyperparameter Tuning for Policy Gradient Methods. In Advances in Newral Information Processing Systems, vol- ume 32. Curran Associates, Inc., 2019. URL https://proceeddie http httpscppppp/p/////aaaaa (B544a8221155044rrf4--BBBBBBBB
bibstract.htam
John Schulman, Filip Wolski, Prafulla Dhariwal, Alec Radford, and Oleg Klimov. Proximal Policy Optimization Algorithms, August. 2017. URL
06347. arXiv:1707.06347 [cs).
Stanford CS231N. Tiny ImageNet, 2017. URL http:://ss3t...stamfff stanfoord wtt.:/ttaaat....tttttraaaeeeeeea Sealyy-mmmmeeettte zip.
Jia Mian Tan, Haoran Liao, Wei Liu, Changjun Fan, Jincai Huang, Zhong Liu, Junchi Yan, Jia Mian Tan, Haoran Liao, Wei Liu, Changjun Fan, Jincai Huang, Zhong Liu, and Junchi Yan. Hyperparameter Optimization: Classics, Acceleration, Online, Multi-Objective, and Tools. Mathematical Biosciences
16

---

Published in Transactions on Machine Learning Research (05/2025)
and Engineering, 21(6):6289 6335, 2024. ISSN 1551-0018. 2024275.
doi: 10.3944mmbe.02242/ URL http:
//www. www.aimspress... com
Mingxing Tan and Quoe Le. EfficientNeet2: Smaller Models and Faster Training, In Proceedings of the 38th International Conference on Machine Learning, pp. 10096-10106. PMLR, July 2021. URL https: bttps:s//proceednng.coou /ttpe//ddngg........ee////////// 1t///////n22a.... html. ISSN: 2640-3498.
Yunhao Tang and Krzysztof Choromanski. Online Hyper-parameter Tuning in Off-policy Learning via Evolutionary Strategies, June 2020. URL stat].
arXiv:2006.0755 00.200006.7544 [cs,
Xingchen Wan, Vu Nguyen, Huong Ha, Binxin Ru, Cong Lu, and Michael A. Osborne. Think Global and Act Local: Bayesian Optimisation over High- High-Diienssonal Categorical and Mixed Search Spaces. In Proceedings of the 38th International Conference on Machine Learning, pp. 10663-10674. PMLR, July 2021. URL https://proceedee
mlr wal..preate pttppp//ev///aanllllll html. ISSN: 2640-3498.
Xingchen Wan, Cong Lu, Jack Parker-Holder, Philip Ball, Vu Nguyen, Binxin Ru, and Michael Osborne. Bayesian Generational Population-Bass Basod Training. In Proceedings of the First International Conference Aulomaled Machine Learning, pp. 14/1 27. PMLR, September 2022. URL https:///ppt htap::://proceedigg..oo mmr. press/v188/want wwt.///wn2aaa.aaa html. ISSN; 2640-3498.
Frank Wilcoxon. Individual Comparisons by Ranking Methods. In Samuel Kotz and Norman L. Johnson (eds.), Breakthroughs in Statistics: Methodology and Distribution, pp. 196-202. Springer, New York, NY, 1992. ISBN 978-1-4612-4380-01 doi: 10. 1e.1107//900 097-79997-441-43300 978-1-4612-4880-9 9_16.
16. URL http::::///oiooo////////
Han Xiao, Kashif Rasul, and Roland Vollgraf. Fashion-MNIST: a Novel Image Datasct for Benchmarking Ma- chine Learning Algorithnus, September 2017. URL http::/aarxv..or//aaaaaaa
07747. arXiv:1708.07741
[cs, stat].
Tom Zahavy, Zhongwen Xu, Vivek Veeriah, Matteo Hessel, Junhyuk Oh, Hado P van Hasselt, David Silver, and Satinder Singh. A Self-Tuning Actor-Critie Algorithm. In Advances in Newral Information Processing
Systems, volume 33, pp. 20913 20924. Curran Associates, Inc., 2020. URL https: https::/ neurips. http:///w.....ooo/////////////tt
A Detailed reasoning on Lemma 1 in sequential setting
Here we show that Lemna 1 does not hold in the sequential setting: specifically, that sequential maximization of fe does not generally result in optimal Fr. Parker- Holder et al. (2020) consider as optimal the schedule (hr)T-1 = farg max,, fi (h1), arg max,, f2(h2),.... arg max hy frrr))) Recall that fe.)) is defined as ((h - F(-(h)))) For sequential optimization, (h,1( is constant at time Therefore, it does not influence the optimization of fe()), allowing us to replace arg max,, fe(h,) with arg max,, (ha),, revealing that [ is simply the greedy schedule (arg maxn, Fi (hi), arg maxh, F2(h2)...,, arg maxky (hrr)). Consequently, sequentially maximizing fi is equivalent to greedily maximizing F; at each t (in other words, optimizing proxy ft (rather than the objective itself, F,) makes no difference in the outcome).
Such greedy maximization does not, in general, maximize the final performance. Although we and Parker- Holder et al. (2020) write F, as function of only he, this is not correct in the context of dynamic HPO. Previous hyperparameter choices can influence future results via the weights inherited from the previous step (e.g,, too high a learning rate can lead to divergence that cannot be recovered from). Thus, performance at step is not generally independent. of the previous steps, which can be made explicit: Fr .......))) = ((train(0:[(hh)]]]))
Due to potential dependencies on the past choices, greedily optimizing F, leads to worse results (unless no dependencies present, which would make the greedy solution optimal):
17

---

Published in Transactions on Machine Learning Research (05/2025)
Fr(hr/h Pr(hrrlt)...br11) 11-1)
max ( where {helt=1 farg max Fi (h1),, arg max F2 (2(hg)h1), arg max Fr (h)))) hr
A1
h2
To sum up, in the sequential setting, contrary to the statement of Lemma 1, maximizing Js is not equivalent. to maximizing the final performance Pr (even though it is equivalent to minimizing regret it).
B Theoretical consequences of the exploit procedure: an example
One can imagine a variant of the truncation selection where only the best solution in the population survives, and all others are replaced, with the weights copied from this solution, and hyperparameters explored via BO. Asympootically as population size goes to infinity, the best greedy solution maximizing current performance will be discovered at each step t. Only the weights from this solution will be present in the population of the next step, thus making sure that all schedules discovered in the future have the "greedy" hyperparameters at the time t. The final schedule will have the "greedy" hyperparameters at each step, i.e., it will be the greediest schedule.
On the other hand, if truncation selection with A < 50% is used, the population size going to infinity allows for many suboptimal-in- seetimmal----th---liee wwwe-short-teee weights to be preserved at each step, likely preventing the dominance of the greediest solution.
This is only an illustrative example of the potential influence of the exploit procedure on the results that can occur despite the BO component remaining constant. We hope to encourage a deeper theoretical treatment of the exploit procodure in future research.
C Task implementation details
Classification The default training hyperparameters are: 50, 000 SGD steps with a batch size of 128, a learning rate of 0.1, weight decay set to 0.0005, and the use of RandAugment (Cubuk al., 2020) with augmentation of magnitude 10.
The CIFAR-10/100 (Krizhevsky & Hinton, 2009) datasets contain 50,000 training and 10,000 testing samples each, we further separate 10,000 images from the training set to use as the validation set. The Fashion- MNIST (Xiao et al., 2017) contains 60,000 training and 10,000 testing samples, we further separate 10,000 images from the training set to use as the validation set. The Tiny ImageNett (Stanford CS231N, 2017) dataset contains 100,000 training, 10,000 validation, and 10,000 test samples. The labels for the test set are not available, therefore treat. the original validation set as the test set and separate 10,000 images from the training set to
the validation set.
For each dataset, the validation set is used during the search to estimate the quality of solution. The results in the main text are reported on the validation set so that the algorithms would be compared in terms of the objective they were optimizing. It also allows us to compare the intermodiate performanco. The final models are also evaluated on the lest. set. We observe that the results are similar to those on the validation set, see Figures 12-14 (Appendix H).
RL For the RL tasks, we follow the setup of Wan et al. (2022) where hyperparameters of a PPO (Schulman et al,, 2017) agent are tuned for 150 million environment interactions on the tasks from the Brax library (Free- man et al., 2021). To avoid overfitting to a single sced, different random seed is set in each outer step of a PBT. The lest performance is evaluated on a previously unseen seed. Both the validation and the test. rewards are averages over 256 parallel rollouts. The test results are presented in Figures 12-14 (Appendix H). We would like highlight that the validation and test performance on the RL. tasks is almost identical. The common RL issue of the train-test performance gap (Eimer et al., 2023) was avoided by using a different. random seed in each outer step of PBT algorithm.
18

---

Published in Transactions on Machine Learning Research (05/2025)
For further implementation details, see codebase: codebase includes configuration files for all experiments, as well as code for plotting and statistical testing.
htt.a///..ooomeeeeeooeeee/////// The
D PBT variants implementation details
Population sizes are set based on the requirements of FIRE-PBT: while the other PBTS have a single population, use FIRE-PBT with two hierarchical subpopulations and evaluator subpopulation. To avoid the evaluators staying idle, their number should be equal to (100 X1% of the second subpopulation, where À is the hyperparameter of the truncation selection (25% by default). We follow Dalibard & Jaderberg (2021) in using population sizes of 22 (two subpopulations of size 8, and 6 evaluators) and 50 (two subpopulations of size 18, and 14 evaluators). We additionally consider the smaller population size of 8, which is typically used by the Bayesian PBTs. In this setting, FIRE-PBT has two subpopulations of size 3, and evaluators. The À for FIRE-PBT appropriately increasod to 34% from the default 25%.
In Perturbation PBTs, use {0.5, as factors for perturbation. For some hyperparameters with narrow ranges, a perturbation can only flip between the maximum and minimum values, preventing reasonable exploration. To address this, in our implementation, we check if the variable range is narrow like this, and if so, normalize the range to [0.0, 1.0], perform random perturbation in the normalized range, and renormalize the resulting value back to the original range.
We implemented FIRE-PBT from scratch, as no implementation was available. PBT was also implemented from scratch. As to PB2, PB2-Mix, and BG-PBT, built upon the official implementations and adapted implementations of PB2-Mix and BG-PBT to be task-agnostic. Furthermore, we have fixed several issues with the gradients of PB2 and PB2-Mix that were present in these implementations (the issues were confirmed by the original authors in private communication). Specifically:
PB2: The gradient of variance should not square the length scale, as it is not squared in the forward path the kernel (https://githu) 47). Alternatively, the length scale could be squared both places.
py, lines 31,
PB2: The gradient of variance should be multiplied by the value of the time kernel, which is independent of it and is multiplied by it in the forward path (nttpa://github. ctm.ttthhbooooo//..ooooeeeeeeeet htrp::///gttuub..omo/prrrrttte /parkerholder/ pB2/blob/master//eeeee/e/ perrterrreeeel.... py, lines 33, 47).
PB2: The gradient of the length scale has an erroneous additional factor of "-2", which can be confirmed by taking the gradient of the kernel with respect to the length scale (attps://github. py, line 48).
han//pparkerhhllde//pp22 http:////..obbbmmtttte/eeee/eeee
PB2-Mix: The gradient of the length scale has erroncous minus sign, which is absent in the gradient formula in the PB2-Mix publication itself bettps://gitan com ppr.eerhholdderr/roeee.. bttoor//blobmmai//paa htpp:/p2puuttttl utils. py, line 248).
Based on our preliminary experiments, these changes did not impact the final results achieved by the algorithms but substantially improved their exploration speed. This happened because the errors led to some gradients having signs opposite to the correct ones, which deteriorated the performance L-BFGS that relied on these analytical gradients optimize the hyperparameters of the kernel.
E
Search spaces
In classification tasks, the small search space corresponds to searching just the learning rate. In the medium space, the number of augmentations in Rand RandAuggent and the augmentation si rength are additionally considered. The large space also includes weight decay and momentum. See Table 1.
In RL tasks, our search space is based on that of Wan et al. (2022), with architecture-relatedd hyperparameters omitted. We also narrow the ranges of the "batch size" and "number updates per epoch" hyperparameters in
19

---

Published in Transactions on Machine Learning Research (05/2025)
Hyperparameter
Type Exponent base
Range
learning rate number of augmentations
real 10
[-6, 0]
integer
[1,
augmentation strength integer
[L. 30]
weight decay momentum
real 10
[-8, -2]
real x
[0.5, 0.999]
Table 1: Hyperparameter tuning ranges for the classification tasks. All variables above the first and the second dashed lines are included in the small and medium search spaces accordingly, while the full table corresponds to the large search space.
order reduce the computational burden the experiments. We refer to the resulting search space as large. The medium space is its subset that contains only "learning rate", "entropy coefficient", and "batch size". The small space contains "learning rate" only. See Table 2.
Hyperparameter
Type
Exponent base Range
learning rate
real
10
[4, -3
entropy coefficient
real
10
6, -1
batch size
integer
2
8, 10
discount factor
real
X
[..9, 0.9999]
unroll length
integer
X
[5, 15]
reward scaling
real
[0.05, 20]
number of updates per epoch
integer
[2, 16]
GAE parameter
real
0.9, 1]
clipping parameter
real
00.1, 0.4]
Table 2: Hyperparameter tuning ranges for the RT tasks. All variables above the first and the second dashed lines are included in the small and medium search spaces accordingly, while the full table corresponds to the large search space.
F Statistical analysis
Due to high computational costs and the large number of settings considered in this article, we were able to run each algorithm with only a few random seeds in each setting: seeds for the classification tasks, 7 seeds for the RI. tasks. To partially counteract the lack of data, the results of the classification tasks were pulled together (so that each of the algorithm had 10 data points), and the results of the RL tasks were pulled logether (so that each algorithm had 14 data points).
The tests were performed independently in each setting, with the target p-value of 0.05. Firstly, a Friedman test (Friedman, 1937) was performed to determine if any algorithm achieved results statistically different to those of the others. If so, pairwise signed Wilcoxon rank Lests (Wilcoxon, 1992) with Holm correction (Holm, 1979) were performed. The results are presented in Figure 10 and referenced in the main text. We would like additionally speculate that repeating experiments more times could lead to more significant differences found in some cases with large differences in average ranks (e.g., between PB2 and FIRE-PBT in Figure 10 (a) with 3 steps).
G Additional results on Tiny ImageNet
In Scction 5.8, we unexpectedly found that FIRE-PBT does not outperform other PBTs on Tiny ImageNot in the setting where it did so for all other datasets (Fashion-MNIST,, CIFAR-10/100) large search space, 100 outer steps. We hypothesized that this could be due to the increased difficulty of the underlying task
20

---

Published in Transactions on Machine Learning Research (05/2025)
Rank
Rank
2
2
3
4
PBT
PBT
10
10
PH2
Steps
PB2
Steps
PB2-Mix
30
BG-PBT
BG-PBT
FIRE-PTT
FIRE-PIT
100
100
(a) Classification tasks: vary number of steps
(b) RL tasks: vary number of steps
Rank
Rank
2
3
5
3
5
small
small
PBT
PBT
Search spare
Search space
PB2
medium
PB2 Mix
medlum
PB2-Mix
BG-PBT PBT
DG-PBT
large
FIRE-PET
large
FIRE-PET
(c) Classification tasks: vary search space
(d) RL tasks: vary search space
Rank
Rank
3
8
Population size
PBT
Population size
PBT
PB2
PB2
22
O
22
A
PB2-Mix
PB2-Mix
BG-PBT
BG-PBT
50
FIRE-PET
50
FIRE-PET
(e) Classification lasks: vary population size
(I) RL lasks: vary population size
Figure 10: Critical difference diagrams for PBTs. Algorithms within bracket were not found to be statistically significantly different from each other. Each row in each subfigure corresponds to one experimental setting that was analyzed independently of all others.
in combination with the large search space. To test the impact of the search space, we ran an additional experiment in the small scarch space. Figure shows that in this setting FIRE-PBT outperforms other variants, as expectod.
40
PBT
Accuracyt
PB2
30
BG-PBT FIRE.BBT
20
SGD steps
x10
Figure 11: The performance (IQM, with IQR shaded) of PBTs Tiny ImageNet in the small search space.
21

---

Published in Transactions on Machine Learning Research (05/2025)
H Results on the test split
PBT P62
BG-PBT FIRE-PBT
PB2
PBT
PBT FIRE-PBT
P92
BG-PET
PB2
BG-PBT
10000
Accuracyt
94.5
92
Scoret
Score
94.0
90
88
6000
100
Number of steps
Number of steps
Number of steps
Number of steps
(a) Pashion-MNIST
(b) CIFAR-10
(c) Hopper
(d) Humanoid
Figure 12: Test performance (IQM and IQR) of the PBT variants as the number of outer steps varied,
while the number of inner steps (SGD steps for classification, environment steps for RL) kept constant.
I PBT
} PB2-Mix
& PIRE-PBT
PBT
PB2-MIX I FIRE-PBT BG-PST
$ PBT
P82-Mix RG-PBT
I FIRE-PBT
PBT 1 P82-Mix FIRE.PBT BG-PET
PB2
BG-P8T
2400
95.2
5000
Accuracy1
Acturacy
92.5
Scoret
Scoret
7500
90.0
93.6
800
0000
small
medium
large
small
medium
large
small
medium
large
small
medium
large
Search space
Search space
Search space
Search size
(a) Fashion-MNISTT
(b) CIFAR-10
(c) Hopper
(d) Humanoid
Figure 13: Test performance (IQM and IQR) of the PBT variants the search space size is increased. Some
IQR marks are invisible due to IQRs being too narrow.
PET
$ PBT } PB2
$
FIRE
PB2
BG.PBT
PB2
BG-P8T
AG-PBT
P82
BG-PET
2400
Tccuracyt
Accuracyt
92.5
Scoret
Scoret f
1600
93.6
800
6000
Population size
Population size
Population size
Population size
(a) Fashion-MNIST
(b) CIFAR-10
(c) Hopper
(d) Humanoid
Figure 14: Test performance (IQM and IQR) of the PBT variants as the population size is increased.
22

---

Published in Transactions on Machine Learning Research (05/2025)
P0T
-0.49
-0.38
-0.58
0.33
PRT
-863
1151
1684
2000
FINE-WIT aC--eIT Miz PR2
521
-1.955
304
427
P12
Algeritim
Difference
Alcorithm
Difference
FIRE-POT DiG UG--PT
-545
465
-100
-0.06
-0.74
-0.24
1.90
-2000
100
10
30
100
Number of scegs
Number of steps
(a) CIFAR-10
(b) Humanoid
Figure 15: Differences in IQMs of the performance of the PBT variants when changing the value of À of truncation selection from 25% to 12.5%.
Impact of X on performance of the PBT variants
To evaluate the impact of the truncation selection parameter on the performance of PBTs, we repeat a subset of experiments from Figure (specifically, those with CIFAR-10 and Humanoid) with the value of truncation selection changed from the default 25% 12.5%.
Figure 15 shows the difference in IQM that arise from such change of X. It can be generally observed that decreasing lambda improves results for combinations of (algorithm, number of steps) but leads to worse results in others. Therefore, we cannot conclude that one of the considered values of lambda should be generally preferred.
Interestingly, all algorithms seem to benefit from the decreased lambda when the number of steps is 100. Since smaller corresponds lower selection pressure and slower evolution, reducing could be espocially helpful in reducing short-term focus of optimization in this setting of many steps. We leave further investigation of the interaction between the hyperparameters and the performance of PBTs for future research.
J Impact of the perturbation factor on performance of FIRE-PBT in challenging search spaces
In order to evaluate the potential impact of the perturbation factor hyperparameter of FIRE-PBT on its performance in larger and more challenging search spaces, we have run FIRE-PET with the perturbation factor of 1.25 instead of 2.0 the large search space on two RL tasks, Hopper and Humanoid. in Figure 16, the smaller perturbation factor leads decreased score on Hopper and an increased score Humanoid. This indicates that the perturbation-based search procedure sensitive to the perturbation factor, which may need to be tuned per task to achieve optimal performance.
can seen
1250
7500
2.0
1.25
2.0
1.25
Perturbation factor
Perturbation factor
(a) Hopper
(b) Humanoid
Figure 16: The performance (IQM and IQR) of FIRE-PBT when the perturbation factor is reduced from 2.0 to 1.25. The large search space is used.
23


Reviews:
[{"review_id": "lBAjoKcYUT", "reviewer": "Reviewer_2tGy", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "- The analysis clarifying the assumptions of cumulative regret analysis from PB2 is a good sound contribution and put forths a hypothesis that Bayesian PBTs work by optimizing greedily. \n\n- The related work coverage in the paper is excellent which makes it clear to understand the landscape of PBT methods.\n\n- I like the extended discussion about step size which is typically missing in existing work and one big source of inconsistencies in comparisons of different PBT algorithms.\n\n- The paper clarifies that other Bayesian PBTs (like BG-PBT Wan et al) are out of scope of the paper but it does seem to weaken the theoretical analysis in 4.1 since it focuses on one very specific paper within this class. \n\n- I am most concerned about the experimental analysis in the paper which is inconsistent and doesn't seem to follow nicely with the hypotheses made in the theoretical analysis section. For example, in Figure 4, Bayesian PBTs perform better than perturbation ones for reinforcement learning tasks which is attributed to greedy optimization working better for these tasks. This is counterintuitive since RL tasks have a larger search space than image classification one and one would expect to larger spaces to be less amenable to greedy optimization. \n\n- The results in section 5.7 show that there is no clear method that performs clearly better. It is not clear how can we leverage the greedy optimization hypothesis to explain the performance difference here. Again, it is slightly unclear whether the theoretical analysis helps in understanding the results. \n\n- In the light of the results, I think the paper should consider either studying or adding a recommendation for future work regarding studying other class of algorithms (for example, RL based or hypergradient methods) for dynamic HPO going beyond PBT. In fact, based on this paper, all issues mentioned with these approaches in the related work section (like meta-hyperparameters of their own or inefficiency) seem to arise with PBT methods as well.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "No", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The paper studies Population based training (PBT) methods which is one class of algorithms for dynamic hyper-parameter optimization (HPO) in neural networks. First, the paper studies and analyzes the assumptions behind the theoretical analysis of a particular algorithm in this class (PB2 Parker-holder et al). Second, the paper empirically analyzes the performance of multiple algorithm variants in the broader PBT class on a series of image classification and reinforcement learning HPO setting.", "claims_and_evidence_yn": "No", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "Please see strengths and weaknesses section.", "broader_impact_concerns": "I do not see any ethical concern.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "UaJk9e50uU", "reviewer": "Reviewer_Tn4y", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "*Strengths*\n\nThis paper evaluates the performance of different PBT variants for hyperparameter autotuning in multiple tasks. The authors made multiple claims about the properties of different methods and the experiments are well designed to support their claims. The authors also tried to interprete their observations from a theoretical perspective.\n\n*Weaknesses*\n\n* I have some questions about the analysis section, see the requested changes below.\n* I should mention that I am not an expert in AutoML. According to my background knowledge (I am from convex optimization and inverse RL), I can not really evaluate wheather the PBT variants compared in this paper are representative or thorough. I think this should be evaluated by the other reviewers.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The authors compared the performance of some variants of PBTs on a set of image classification and reinforcement learning tasks for hyperparameter autotuning. Theoretical analysis and discussion are introduced to explain the observed differences in the performance of different approaches.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "* In the paragraph after (6), the authors mentioned that the transition (6.3) holds for any schedule that $f_t(h_t^A)$ is constant for all $t$. Maybe the authors could include an specific example for such a schedule? It would me much helpful for the readers to understand.\n* In the last paragraph of section 4.1, the authors mentioned that the schedules discoverd by Bayesian PBTs  asymptotically approach {$\\tilde{h}_1, \\ldots, \\tilde{h}_T$}. This is not quite clear to me according to the analysis in the text. Is this discussed in the paper from Parker-Holder et al., or did I missed something? It would be good if the authors could explain this point in more detail.\n* The authors discussed the limitations of the current theoretical approach in section 4.2, but it is not quite clear to me what is the author's motivation of writing this section. Is it just for some discussion, or related to the subsequent experiments? Could the authors make their claim in this section more clear?\n* Not all equations in display mode are properly punctuated. As far as I noticed, except for (3), a period is missing for all other display mode equations.\n\nMinor:\n* It is a bit weird for me to put the toy examples in the analysis section. The authors could restruct the sections about this part such that the structure of the whole paper is more clear.\n* All equations in this paper are numbered but not all of them are referred to somewhere else. Particularly, the equations (5) and (6) should be understood as the same equation but are numbered twice. The authors could consider only numbering those equations that are used, and remove duplicate numbering.", "broader_impact_concerns": "No.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "yDsuwY1log", "reviewer": "Reviewer_rR61", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "**Strengths**\n\n- the authors define a common set of tasks to evaluate PBT algorithms fairly, thereby defining a standard experimental setup that other works can adopt in the future\n- an extensive empirical evaluation is conducted, showing that although recent works on PBT claim to achieve new state-of-the-art results, no clear winner can be identified among those methods\n- a theoretical analysis is provided, showing that the optimization dynamics of PBT algorithms have to be properly accounted for in future theoretical analysis\n- overall, the paper is well-structured and written clearly\n\n**Weaknesses and Questions**\n\n- Sec. 4.1 can be shortened significantly to improve readability (see Requested Changes)\n- the work does not propose an extended theoretical framework that can be used to analyze the optimization properties of PBT algorithms\n- the PlainToy problem introduced to support the theoretical findings is too simplistic, in my opinion: It is quadratic in $\\theta$ (thus convex) and linear in $h$. Another more complex problem would significantly strengthen the work.\n- Fig. 3(a): it is unclear to me, why PB2 is so much worse compared to PBT although both show similar behavior in decreasing the learning rate\n- Fig. 4: Why is the standard deviation of BO-based PBT algorithms increasing towards the end (see BG-PBT in (a) and PB2 in (b))?\n- Fig. 6(c, d): It seems that the results in Fig. 6(c) and (d) contradict the results in Fig. 4: In Fig. 4, BG-PBT was best on Hopper and PB2 was best on Humanoid. However, in Fig. 6, none of them is best for any search space size. Could the authors explain this?\n- I would have expected FIRE-PBT to shine on RL tasks as it focuses on optimization on long-term gains. However, the greedier BO-PBT variants seem to perform better on RL tasks. Do the authors have an explanation for this?", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The authors empirically evaluate five recent Population Based Training (PBT) algorithms on classification and reinforcement learning tasks to provide a fair comparison of PBT algorithms on a unified set of tasks. It is shown that, although there is no clear winner, perturbation-based PBT variants perform better on classification tasks, while PBT algorithms leveraging Bayesian Optimization for candidate selection perform better on RL tasks. Besides the empirical results, the authors provide theoretical insights that partially explain their observations.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "**Shorten Sec. 4.1 and fix minor flaws**\n\n- after Eq. 6, the authors write: `Observe that the argument of argmax must be the entire schedule for the transitions in the original proof (Eq. 4) to hold as written. Thus, the lemma is proved in the non-sequential setting.` I agree that the Lemma is shown for the non-sequential setting. However, this is not because the entire schedule is the argument of argmax. Rather, it is due to the dependencies among the terms in the summation (as correctly described below). This should be changed. \n- Sec. 4.1 can be significantly shortened. In my opinion, the authors could discuss the dependencies among the terms in the sum of Eq. 6 briefly below the equation, saying that greedy optimization does not guarantee to find the maximum of Eq. 6. After that, the authors could briefly state that PBT is not a purely greedy optimization algorithm (3-5 lines should be enough on that). This would increase clarity and readability.\n\n**Other Changes**\n\n- Sec. 4.4 should be moved to Sec. 5. Also, the authors should discuss the design of the toy functions a bit more and provide justification for their design. Additionally, I believe a slightly more complex PlainToy problem is required to validate the theoretical findings (as described in \"Weaknesses and Questions\").\n- if computationally feasible, a senstivity analysis of the hyperparameters of (at least some) PBT algorithms would be beneficial to see the influence of these parameters on the overall performance.", "broader_impact_concerns": "n.a.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper provides both a theoretical and empirical analysis of population-based training (PBT) to dynamically optimize the hyperparameters of supervised training for deep neural networks and deep reinforcement learning agents. It compares multiple methods from the literature, showing that none of the methods performs consistently better across all benchmarks.
Results indicate that Bayesian optimization-based methods behave more greedily than random search-based counterparts, such as vanilla PBT, which performs better on certain benchmarks that favor short-term gains.

The reviewers unanimously recommend acceptance of the paper, appreciating its insights into the behavior of the different methods. They did, however, point out some discrepancies between the theoretical and empirical results. These discrepancies are explicitly acknowledged and discussed in the paper. While the paper does not fully explain all empirical findings in detail, it nonetheless offers valuable insights for the TMLR community.
Decision: Accept (poster)