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

• URL: http://arxiv.org/abs/2604.07473v1
• Date: Wed, 08 Apr 2026 18:11:36 GMT
• Title: When Switching Algorithms Helps: A Theoretical Study of Online Algorithm Selection
• Abstract summary: Online 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.<n>There are currently no theoretical results proving that OAS can yield speedups.<n>We present the first theoretical example in which switching between two algorithms solves the One problemally faster than either algorithm used in isolation.
• Score: 0.15469452301122175
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: 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.

Related papers

• Approximation Algorithms for Preference Aggregation Using CP-Nets [3.337244446073836]
  This paper studies the design and analysis of approximation algorithms for aggregating preferences over Conditional Preference Networks (CP-nets) Its focus is on aggregating preferences over so-called emphswaps, for which optimal solutions in general are already known to be of exponential size.
  arXiv  Detail & Related papers  (2023-12-14T17:31:38Z)
• Fast Computation of Optimal Transport via Entropy-Regularized Extragradient Methods [75.34939761152587]
  Efficient computation of the optimal transport distance between two distributions serves as an algorithm that empowers various applications. This paper develops a scalable first-order optimization-based method that computes optimal transport to within $varepsilon$ additive accuracy.
  arXiv  Detail & Related papers  (2023-01-30T15:46:39Z)
• Improved Rate of First Order Algorithms for Entropic Optimal Transport [2.1485350418225244]
  This paper improves the state-of-the-art rate of a first-order algorithm for solving entropy regularized optimal transport. We propose an accelerated primal-dual mirror descent algorithm with variance reduction. Our algorithm may inspire more research to develop accelerated primal-dual algorithms that have rate $widetildeO(n2/epsilon)$ for solving OT.
  arXiv  Detail & Related papers  (2023-01-23T19:13:25Z)
• An Accelerated Stochastic Algorithm for Solving the Optimal Transport Problem [2.1485350418225244]
  A primal-dual accelerated gradient descent with variance reduction algorithm (PDASGD) is proposed to solve linear-constrained optimization problems. PDASGD enjoys the best-known computational complexity -- $widetildemathcalO(n2/epsilon)$, where $n$ is the number of atoms, and $epsilon>0$ is the accuracy.
  arXiv  Detail & Related papers  (2022-03-02T01:16:10Z)
• Choosing the Right Algorithm With Hints From Complexity Theory [16.33500498939925]
  We show that the Metropolis algorithm is clearly the best of all algorithms regarded for reasonable problem sizes. An artificial algorithm of this type having an $O(n log n)$ runtime leads to the result that the significance-based compact genetic algorithm (sig-cGA) can solve the DLB problem in time $O(n log n)$ with high probability.
  arXiv  Detail & Related papers  (2021-09-14T11:12:32Z)
• Provably Faster Algorithms for Bilevel Optimization [54.83583213812667]
  Bilevel optimization has been widely applied in many important machine learning applications. We propose two new algorithms for bilevel optimization. We show that both algorithms achieve the complexity of $mathcalO(epsilon-1.5)$, which outperforms all existing algorithms by the order of magnitude.
  arXiv  Detail & Related papers  (2021-06-08T21:05:30Z)
• Lower Bounds and Optimal Algorithms for Smooth and Strongly Convex Decentralized Optimization Over Time-Varying Networks [79.16773494166644]
  We consider the task of minimizing the sum of smooth and strongly convex functions stored in a decentralized manner across the nodes of a communication network. We design two optimal algorithms that attain these lower bounds. We corroborate the theoretical efficiency of these algorithms by performing an experimental comparison with existing state-of-the-art methods.
  arXiv  Detail & Related papers  (2021-06-08T15:54:44Z)
• Towards Optimally Efficient Tree Search with Deep Learning [76.64632985696237]
  This paper investigates the classical integer least-squares problem which estimates signals integer from linear models. The problem is NP-hard and often arises in diverse applications such as signal processing, bioinformatics, communications and machine learning. We propose a general hyper-accelerated tree search (HATS) algorithm by employing a deep neural network to estimate the optimal estimation for the underlying simplified memory-bounded A* algorithm.
  arXiv  Detail & Related papers  (2021-01-07T08:00:02Z)
• Single-Timescale Stochastic Nonconvex-Concave Optimization for Smooth Nonlinear TD Learning [145.54544979467872]
  We propose two single-timescale single-loop algorithms that require only one data point each step. Our results are expressed in a form of simultaneous primal and dual side convergence.
  arXiv  Detail & Related papers  (2020-08-23T20:36:49Z)
• Private Stochastic Convex Optimization: Optimal Rates in Linear Time [74.47681868973598]
  We study the problem of minimizing the population loss given i.i.d. samples from a distribution over convex loss functions. A recent work of Bassily et al. has established the optimal bound on the excess population loss achievable given $n$ samples. We describe two new techniques for deriving convex optimization algorithms both achieving the optimal bound on excess loss and using $O(minn, n2/d)$ gradient computations.
  arXiv  Detail & Related papers  (2020-05-10T19:52:03Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.