AlgoSelect: Universal Algorithm Selection via the Comb Operator

• URL: http://arxiv.org/abs/2506.17304v1
• Date: Tue, 17 Jun 2025 23:38:53 GMT
• Title: AlgoSelect: Universal Algorithm Selection via the Comb Operator
• Authors: Jasper Yao,
• Abstract summary: We introduce AlgoSelect, a principled framework for learning optimal algorithm selection from data.<n>For pairs of algorithms, a simple sigmoid-gated selector, an instance of the Comb Operator, facilitates this.<n>We prove that this framework is universal (can approximate any algorithm selector), information-theoretically optimal in its learnability.
• Score: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We introduce AlgoSelect, a principled framework for learning optimal algorithm selection from data, centered around the novel Comb Operator. Given a set of algorithms and a feature representation of problems, AlgoSelect learns to interpolate between diverse computational approaches. For pairs of algorithms, a simple sigmoid-gated selector, an instance of the Comb Operator, facilitates this interpolation. We extend this to an N-Path Comb for multiple algorithms. We prove that this framework is universal (can approximate any algorithm selector), information-theoretically optimal in its learnability (thresholds for selection converge almost surely, demonstrated via Borel-Cantelli arguments), computationally efficient, and robust. Key theoretical contributions include: (1) a universal approximation theorem demonstrating that Comb-based selectors can achieve arbitrary accuracy; (2) information-theoretic learnability for selection thresholds; (3) formalization of the Comb Operator within linear operator theory, detailing its boundedness and spectral properties; (4) an N-Path Comb generalization for multi-algorithm selection; and (5) a practical learning framework for the adaptive seeding functions that guide the Comb Operator. Empirical validation on a comprehensive 20$\times$20 problem-algorithm study demonstrates near-perfect selection (99.9\%+ accuracy) with remarkably few samples and rapid convergence, revealing that $H(\text{Algorithm}|\text{Problem}) \approx 0$ in structured domains. AlgoSelect provides a theoretically grounded, practically deployable solution to automated algorithm selection with provable optimality and learnability guarantees, with significant implications for AI and adaptive systems.

Related papers

• Sample Complexity of Algorithm Selection Using Neural Networks and Its Applications to Branch-and-Cut [1.4624458429745086]
  We build upon recent work in this line of research by considering the setup where, instead of selecting a single algorithm that has the best performance, we allow the possibility of selecting an algorithm based on the instance to be solved. In particular, given a representative sample of instances, we learn a neural network that maps an instance of the problem to the most appropriate algorithm for that instance. In other words, the neural network will take as input a mixed-integer optimization instance and output a decision that will result in a small branch-and-cut tree for that instance.
  arXiv  Detail & Related papers  (2024-02-04T03:03:27Z)
• Large Language Model-Enhanced Algorithm Selection: Towards Comprehensive Algorithm Representation [27.378185644892984]
  This paper introduces Large Language Models (LLMs) into algorithm selection for the first time. LLMs not only captures the structural and semantic aspects of the algorithm, but also demonstrates contextual awareness and library function understanding. The selected algorithm is determined by the matching degree between a given problem and different algorithms.
  arXiv  Detail & Related papers  (2023-11-22T06:23:18Z)
• Efficient Convex Algorithms for Universal Kernel Learning [46.573275307034336]
  An ideal set of kernels should: admit a linear parameterization (for tractability); dense in the set of all kernels (for accuracy) Previous algorithms for optimization of kernels were limited to classification and relied on computationally complex Semidefinite Programming (SDP) algorithms. We propose a SVD-QCQPQP algorithm which dramatically reduces the computational complexity as compared with previous SDP-based approaches.
  arXiv  Detail & Related papers  (2023-04-15T04:57:37Z)
• Algorithm Selection on a Meta Level [58.720142291102135]
  We introduce the problem of meta algorithm selection, which essentially asks for the best way to combine a given set of algorithm selectors. We present a general methodological framework for meta algorithm selection as well as several concrete learning methods as instantiations of this framework.
  arXiv  Detail & Related papers  (2021-07-20T11:23:21Z)
• Leveraging Benchmarking Data for Informed One-Shot Dynamic Algorithm Selection [0.9281671380673306]
  A key challenge in the application of evolutionary algorithms is the selection of an algorithm instance that best suits the problem at hand. We analyze in this work how such prior performance data can be used to infer informed dynamic algorithm selection schemes for the solution of pseudo-Boolean optimization problems.
  arXiv  Detail & Related papers  (2021-02-12T12:27:02Z)
• 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)
• Generalization in portfolio-based algorithm selection [97.74604695303285]
  We provide the first provable guarantees for portfolio-based algorithm selection. We show that if the portfolio is large, overfitting is inevitable, even with an extremely simple algorithm selector.
  arXiv  Detail & Related papers  (2020-12-24T16:33:17Z)
• Online Model Selection for Reinforcement Learning with Function Approximation [50.008542459050155]
  We present a meta-algorithm that adapts to the optimal complexity with $tildeO(L5/6 T2/3)$ regret. We also show that the meta-algorithm automatically admits significantly improved instance-dependent regret bounds.
  arXiv  Detail & Related papers  (2020-11-19T10:00:54Z)
• Towards Meta-Algorithm Selection [78.13985819417974]
  Instance-specific algorithm selection (AS) deals with the automatic selection of an algorithm from a fixed set of candidates. We show that meta-algorithm-selection can indeed prove beneficial in some cases.
  arXiv  Detail & Related papers  (2020-11-17T17:27:33Z)
• Extreme Algorithm Selection With Dyadic Feature Representation [78.13985819417974]
  We propose the setting of extreme algorithm selection (XAS) where we consider fixed sets of thousands of candidate algorithms. We assess the applicability of state-of-the-art AS techniques to the XAS setting and propose approaches leveraging a dyadic feature representation.
  arXiv  Detail & Related papers  (2020-01-29T09:40:58Z)

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.