When Switching Algorithms Helps: A Theoretical Study of Online Algorithm Selection

2026-04-08 · Denis Antipov, Carola Doerr arxiv

Online algorithm selection (OAS) aims to adapt the optimization process to changes in the fitness landscape and is expected to outperform any single algorithm from a given portfolio. Although this expectation is supported by numerous empirical studies, there are currently no theoretical results proving that OAS can yield asymptotic speedups (apart from some artificial examples for hyper-heuristics). Moreover, theory-based guidelines for when and how to switch between algorithms are largely missing. In this paper, we present the first theoretical example in which switching between two algorithms -- the $(1+λ)$ EA and the $(1+(λ,λ))$ GA -- solves the OneMax problem asymptotically faster than either algorithm used in isolation. We show that an appropriate choice of population sizes for the two algorithms allows the optimum to be reached in $O(n\log\log n)$ expected time, faster than the $Θ(n\sqrt{\frac{\log n \log\log\log n}{\log\log n}})$ runtime of the best of these two algorithms with optimally tuned parameters. We first establish this bound under an idealized switching rule that changes from the $(1+λ)$ to the $(1+(λ,λ))$ GA at the optimal time. We then propose a realistic switching strategy that achieves the same performance. Our analysis combines fixed-start and fixed-target perspectives, illustrating how different algorithms dominate at different stages of the optimization process. This approach offers a promising path toward a deeper theoretical understanding of OAS.

📄 PDF Abstract BibTeX arXiv:2604.07473

Code (0)

등록된 구현이 없습니다.

The Challenger: When Do New Data Sources Justify Switching Machine Learning Models?

2025-12-20 · Vassilis Digalakis, Christophe Pérignon, Sébastien Saurin, Flore Sentenac arxiv

Organizations often have an incumbent predictive model in production when new data sources become available. Because historical training data lack the new features, a challenger model must be trained on a small but growi…

Switching between Numerical Black-box Optimization Algorithms with Warm-starting Policies

2022-04-13 · Dominik Schröder, Diederick Vermetten, Hao Wang, Carola Doerr 외

When solving optimization problems with black-box approaches, the algorithms gather valuable information about the problem instance during the optimization process. This information is used to adjust the distributions fr…

Online learning with feedback graphs and switching costs

2018-10-23 · Anshuka Rangi, Massimo Franceschetti

We study online learning when partial feedback information is provided following every action of the learning process, and the learner incurs switching costs for changing his actions. In this setting, the feedback inform…

Multi-Armed Bandits

A Benchmark for Low-Switching-Cost Reinforcement Learning

2021-12-13 · Shusheng Xu, Yancheng Liang, Yunfei Li, Simon Shaolei Du 외

A ubiquitous requirement in many practical reinforcement learning (RL) applications, including medical treatment, recommendation system, education and robotics, is that the deployed policy that actually interacts with th…

Atari Games reinforcement-learning Reinforcement Learning Reinforcement Learning (RL)

Sample-Efficient Reinforcement Learning with loglog(T) Switching Cost

2022-02-13 · Dan Qiao, Ming Yin, Ming Min, Yu-Xiang Wang

We study the problem of reinforcement learning (RL) with low (policy) switching cost - a problem well-motivated by real-life RL applications in which deployments of new policies are costly and the number of policy update…

reinforcement-learning Reinforcement Learning Reinforcement Learning (RL)