# Pareto-Optimal Anytime Algorithms via Bayesian Racing

arXiv: https://arxiv.org/abs/2603.08493 · HTML: https://mlsanity.com/paper/2603.08493/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 15 of its 40 references that are in the map.
- First posted on arXiv 9 Mar 2026.

## Builds on (most cited first, 15 of 15)

- [Hyperband: A Novel Bandit-Based Approach to Hyperparameter Optimization](https://mlsanity.com/paper/1603.06560/) (2016)
- [The CMA Evolution Strategy: A Tutorial](https://mlsanity.com/paper/1604.00772/) (2016)
- [Automatic Differentiation Variational Inference](https://mlsanity.com/paper/1603.00788/) (2016)
- [Automated Algorithm Selection: Survey and Perspectives](https://mlsanity.com/paper/1811.11597/) (2018)
- [Rank-normalization, folding, and localization: An improved widehatR for assessing convergence of MCMC](https://mlsanity.com/paper/1903.08008/) (2019)
- [Practical Hilbert space approximate Bayesian Gaussian processes for probabilistic programming](https://mlsanity.com/paper/2004.11408/) (2020)
- [Pathfinder: Parallel quasi-Newton variational inference](https://mlsanity.com/paper/2108.03782/) (2021)
- [Tuning as a Means of Assessing the Benefits of New Ideas in Interplay with Existing Algorithmic Modules](https://mlsanity.com/paper/2102.12905/) (2021)
- [Explainable Benchmarking for Iterative Optimization Heuristics](https://mlsanity.com/paper/2401.17842/) (2024)
- [Automated Configuration of Genetic Algorithms by Tuning for Anytime Performance](https://mlsanity.com/paper/2106.06304/) (2021)
- [MA-BBOB: Many-Affine Combinations of BBOB Functions for Evaluating AutoML Approaches in Noiseless Numerical Black-Box Optimization Contexts](https://mlsanity.com/paper/2306.10627/) (2023)
- [Sample size calculations for the experimental comparison of multiple algorithms on multiple problem instances](https://mlsanity.com/paper/1908.01720/) (2019)
- [Analyzing the Impact of Undersampling on the Benchmarking and Configuration of Evolutionary Algorithms](https://mlsanity.com/paper/2204.09353/) (2022)
- [Adaptive Estimation of the Number of Algorithm Runs in Stochastic Optimization](https://mlsanity.com/paper/2507.01629/) (2025)
- [Competitions in AI -- Robustly Ranking Solvers Using Statistical Resampling](https://mlsanity.com/paper/2308.05062/) (2023)

## Abstract (arXiv)

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.