Selecting an optimization algorithm requires comparing candidates across problem instances, but the computational budget for deployment is often unknown at benchmarking time. Current methods either collapse anytime performance into a scalar, require manual interpretation of plots, or produce conclusions that change when algorithms are added or removed. Moreover, methods based on raw objective values require normalization, which needs bounds or optima that are often unavailable and breaks coherent aggregation across instances. We propose a framework that formulates anytime algorithm comparison as Pareto optimization over time: an algorithm is non-dominated if no competitor beats it at every timepoint. By using rankings rather than objective values, our approach requires no bounds, no normalization, and aggregates coherently across arbitrary instance distributions without requiring known optima. We introduce PolarBear (Pareto-optimal anytime algorithms via Bayesian racing), a procedure that identifies the anytime Pareto set through adaptive sampling with calibrated uncertainty. Bayesian inference over a temporal Plackett-Luce ranking model provides posterior beliefs about pairwise dominance, enabling early elimination of confidently dominated algorithms. The output Pareto set together with the posterior supports downstream algorithm selection under arbitrary time preferences and risk profiles without additional experiments.
Figures & tables
Model
Prior structure
Space
Temporal
Complexity in T
Independent Dirichlet
θ(t)∼Dir(α)
Simplex
Independent
O(T)
Hierarchical Dirichlet
θ(t)∼Dir(κ/n) , shared κ
Simplex
Independent
O(T)
Gaussian Process (GP)
ηq∼GP(0,k)
Log
Smooth
O(T3) / O(T2M)
Hilbert Space GP
ηq≈∑jβjϕj
Log
Smooth
O(Tm)
Random Walk
ηq(ti+1)∼N(ηq(ti),σ2Δt)
Log
Markov
O(T)
B-spline
ηq=∑jβjBj
Log
Smooth
O(TK)
Table 1. Temporal Plackett-Luce model variants for anytime performance analysis.
Figure 1. Mean execution time in seconds (5 repetitions) for selected models and approximation methods.
Figure 2. A synthetic example with 5 algorithms. Figures (b) to (e) show the mean and 95% credible interval of the rating posterior (y-axis) over time (x-axis), with ground truth ratings from (a) as dotted lines. Figure (f) shows the resulting posterior over preference values for a uniform budget preference. Note that ratings at a specific t always sum to 1.
Figure 3. Dominance posterior probabilities over rounds. Points show maxA∈AP(A≻TB) for each algorithm B at each round (left y-axis). Note that the left y-axis changes to a log-scale for p>0.9 . A cross marks elimination, i.e., when the dominance probability climbs above the decision threshold α . A diamond marks that the algorithm is fully resolved and a Pareto set member. The black line shows the proportion of resolved algorithm pairs (right y-axis).
Figure 4. A synthetic example with 10 algorithms. Conventions as in Figure 2 .
Figure 5. A synthetic example with 10 algorithms. Conventions as in Figure 2 . A resolved algorithm has all pairwise relationships determined; for non-eliminated algorithms, this confirms Pareto set membership.
Figure 6. ECDF (a) and AOCC (b) for the MA-BBOB case study, using 1000 instances. The ECDF shows the mean attained fraction of the interval [10−8,102] , scaled logarithmically. The shaded region is the 95% confidence interval of the mean, constructed by bootstrapping. The mean AOCC (dashes) is the area under the ECDF, using a linear x-axis. Points are the full AOCC distribution over instances.
Figure 7. EAF difference of selected algorithm pairs of the MA-BBOB case study on 1000 instances. In the EAF, color encodes the proportion of runs that attained at least the objective target z−fopt (y-axis) at a specific number of function evaluations (x-axis). Here, the difference of two such EAF surfaces is shown, with color encoding the difference in run proportions (red means first algorithm better, blue means second better, gray means no difference). The dashed line shows the median EAF contour (i.e., for each t , the z−fopt which 50% of runs have attained) of the first algorithm; dotted line shows the same of the second algorithm.
Figure 8. Key PolarBear rounds for the MA-BBOB case study. The figures show the mean and 95% credible interval of the rating posterior (y-axis) over function evaluations (x-axis). A resolved algorithm has all pairwise relationships determined; for non-eliminated algorithms, this confirms Pareto set membership.
Figure 9. Figure (a) and (b) show the mean and 95% credible interval of the final rating posterior of the anytime Pareto set for the MA-BBOB case study over function evaluations on a log and linear x-axis, respectively. Figure (c) and (d) show the resulting posterior over preference values for a uniform and log-uniform (i.e., w(t)=1/t ) budget preference, being the area under the curve of (a) and (b), respectively. Algorithms in the Pareto set are optimal under different time preferences; selection among them requires specifying such a preference at deployment.
Figure 10. Allocation of function evaluations and instances per algorithm by PolarBear for the MA-BBOB case study. Color shows the number of instances that saw the respective amount of function evaluations. Pointwise elimination allows reducing sample costs even for non-dominated algorithms by evaluating algorithms only up to their largest unresolved budget. This adaptive allocation achieves 59% fewer total function evaluations compared to the standard practice of running all algorithms to completion on 1000 instances.
Variant
Adaptation mechanism
Complexity
COV
Full covariance with eigendecomposition
O(d3)
SEP
Diagonal only
O(d)
MAT
Direct transformation matrix (rank-one + rank- μ )
O(d2)
CHO
Cholesky factor with rank updates
O(d2)
CMSA
Exponential moving average + Cholesky recomputation
O(d2)
NAT
Matrix exponential of natural gradient
O(d3)
Table 2. Modular CMA-ES variants compared in the GP-BBOB case study, differing in covariance matrix adaptation mechanism. Complexity is per-generation cost in dimension d .
Figure 11. Key PolarBear rounds and posteriors for the GP-BBOB case study. Figures (a) to (e) show the mean and 95% credible interval of the rating posterior (y-axis) over wall-clock time in seconds (x-axis). Figure (f) shows the resulting posterior over preference values for a uniform budget preference.
Figure 12. Dominance posterior probabilities over rounds for the GP-BBOB case study. Conventions as in Figure 3 . The drop in dominance posterior probability of CHO in round 6 can be attributed to high uncertainty whether it might cross NONE and SEP at 0.1s and 30s, respectively, given current observations (cf. Figure 11(b) ).
Appendix figures & tables2 assets
Supplementary material from the paper’s appendix.
Appendix
Parameter
Prior
Notes / support
d (dimension)
Trunc(N(240,30);[2,320])
integer cast
y0 (offset)
1000⋅Cauchy(0,1)
scalar
i (instances)
UnifInt{1,…,999}24
i.i.d. per base function
T (logits temperature)
LN(−0.5,0.5)
T>0
m (RFF features for logits GP)
DU{32,…,128}
integer cast
ℓ (logits GP lengthscale)
LN(2.0,1.0)
ℓ>0
Appendix
Table 3. Priors used for GP-BBOB in the third case study. Here LN(μ,σ) denotes a LogNormal distribution with underlying normal parameters, DU{a,…,b} a discrete uniform distribution on integers, and Trunc(⋅;[a,b]) truncation (not clipping) to the interval [a,b] .
Figure 13. A GP-BBOB instance with d=2 . Figure (a) shows w(x) for all instances with any w(x)>0.001 . Figure (b) shows the sparsity level k(x) , and (c) shows the resulting landscape f(x) with minimal observed value fmin (from the plotting grid, not necessarily the global optimum) subtracted, then log-scaled.
Identifying Pareto optimal solutions is critical to support multi-objective decision-making. We introduce the first anytime Multi-Objective Multi-Armed Bandit algorithm for the Pareto Set Identification problem, taking a Bayesian approach: Top-Two Pareto Front Thompson Sampling (TTPFTS). We benchmark TTPFTS against state-of-the-art fixed-budget Pareto Set Identification algorithms on synthetic environments. Next, we demonstrate its practical utility in a challenging multi-objective molecular discovery setting by efficiently exploring an ultra-large synthesis-on-demand molecular library. Furthermore, we introduce a novel uncertainty quantification metric that estimates our algorithm's confidence in the predicted Pareto set. We demonstrate that this metric effectively proxies true performance, yielding a robust methodology for monitoring learning progress in complex settings. Finally, we complement these empirical findings with a theoretical proof of the algorithm's asymptotic correctness.
Lennert Saerens, Bram Silue, Eleni Litsa +2
Artificial Intelligence Lab, Departement of Computer Science, Vrije Universiteit Brussel, Brussels, Belgium · imec, Leuven, Belgium
Bayesian optimization (BO) is typically used only for problems where the underlying function is deemed "expensive" (e.g. in time or money), with the speed of the BO algorithm being of little importance. In the real world, however, problems span a continuous range of values, going from cheap to expensive. In this paper, we present BO algorithms through the lens of a speed-performance Pareto frontier: we compare BO against faster algorithms like CMA-ES, and highlight how certain regions of the Pareto frontier are currently empty. As a solution, we propose a new set of fast BO methods that exploit the linear structure in existing BO algorithms, for both continuous and combinatorial inputs (from ~10 to 6000+ dimensions). Our methods achieve performance similar to state-of-the-art BO, while being more than 102× to 103× faster, opening the field of BO to an entirely new class of problems.
Colin Doumont, Henry Moss, Philipp Hennig
University of Tübingen, Tübingen AI Center · Lancaster University
The Strength Pareto Evolutionary Algorithm 2 (SPEA2) is a popular and prominent evolutionary algorithm for solving multi-objective optimisation problems. Despite its popularity, theoretical analyses of SPEA2 have only appeared recently. Moreover, these analyses focus exclusively on how SPEA2 handles non-dominated solutions and disregard the algorithmic components responsible for handling dominated solutions. We conduct a first runtime analysis of SPEA2 for which these components are analysed. We prove that, unlike other prominent algorithms, including NSGA-II, NSGA-III and SMS-EMOA under the same setting of constant population size and duplicate elimination, SPEA2 is unable to cover the Pareto front of the OneTrapZeroTrap benchmark efficiently. Our results indicate that using k-th nearest-neighbour distance in the fitness assignment provides an insufficient signal to maintain diversity among dominated individuals. To address this issue, we propose an improved variant, SPEA2+, that considers all pairwise distances. The new algorithm achieves the same performance guarantees as the other prominent algorithms on OneTrapZeroTrap, while matching the performance of the original SPEA2 on simpler problems. Experimental results complement our theoretical findings.