論文の概要: AlgoSelect: Universal Algorithm Selection via the Comb Operator

• arxiv url: http://arxiv.org/abs/2506.17304v1
• Date: Tue, 17 Jun 2025 23:38:53 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-06-24 19:06:36.32848
• Title: AlgoSelect: Universal Algorithm Selection via the Comb Operator
• Title（参考訳）: AlgoSelect:Combオペレータによるユニバーサルアルゴリズムの選択
• Authors: Jasper Yao,
• Abstract要約: 本稿では,データから最適なアルゴリズム選択を学習するためのフレームワークであるAlgoSelectを紹介する。 アルゴリズムのペアについては、Comb Operatorのインスタンスである単純なシグモイドゲートセレクタがこれを促進している。 このフレームワークは普遍的であり(任意のアルゴリズムセレクタを近似できる)、学習性において情報理論的に最適であることを示す。
• 参考スコア（独自算出の注目度）: 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.
• Abstract（参考訳）: 本稿では,新しいComb Operatorを中心に,データから最適なアルゴリズム選択を学習するための原則的フレームワークであるAlgoSelectを紹介する。 アルゴリズムのセットと問題の特徴表現が与えられたAlgoSelectは、多様な計算アプローチの相互補完を学ぶ。 アルゴリズムのペアに対して、単純なシグモノイドゲートセレクタ(Comb Operatorのインスタンス)は、この補間を促進する。 我々はこれを複数のアルゴリズムのためにN-Path Combに拡張する。 このフレームワークは普遍的であり(任意のアルゴリズムセレクタを近似することができる)、学習性において情報理論が最適であること(選択のための閾値はほぼ確実に収束し、ボレル・カンテッリの議論によって実証される)、計算効率が良く、堅牢であることを証明する。 主な理論的貢献は,(1)コムベースのセレクタが任意の精度を達成できることを示す普遍近似定理,(2)選択しきい値に対する情報理論的学習性,(3)線形作用素理論におけるコム作用素の形式化,(4)多重アルゴリズム選択のためのN-Path Comb一般化,(5)コム演算子を導く適応的シード関数の実践的学習フレームワークである。 包括的20$\times$20問題アルゴリズムに関する実証的検証は、非常に少ないサンプルと迅速な収束を伴うほぼ完全な選択(99.9\%以上の精度)を示し、構造化ドメインにおける$H(\text{Algorithm}|\text{Problem}) \approx 0$が明らかになった。 AlgoSelectは、AIと適応システムに重要な意味を持つ、証明可能な最適性と学習可能性を保証する自動アルゴリズム選択に対する理論的に基礎付けられた、実用的なデプロイ可能なソリューションを提供する。

関連論文リスト

• Sample Complexity of Algorithm Selection Using Neural Networks and Its Applications to Branch-and-Cut [1.4624458429745086]
  本研究は,最適な性能を持つ1つのアルゴリズムを選択するのではなく,インスタンスに基づいてアルゴリズムを選択することが可能となるような設定を考慮し,最近の研究を基礎にしている。 特に、代表的なインスタンスのサンプルが与えられた場合、問題のインスタンスをそのインスタンスの最も適切なアルゴリズムにマッピングするニューラルネットワークを学習する。 言い換えれば、ニューラルネットワークは混合整数最適化インスタンスを入力として取り、そのインスタンスの小さな分岐とカットツリーをもたらす決定を出力する。
  論文  参考訳（メタデータ） (2024-02-04T03:03:27Z)
• Large Language Model-Enhanced Algorithm Selection: Towards Comprehensive Algorithm Representation [27.378185644892984]
  本稿では,Large Language Models (LLM) をアルゴリズム選択に導入する。 LLMはアルゴリズムの構造的・意味的な側面を捉えるだけでなく、文脈的認識とライブラリ機能理解も示している。 選択されたアルゴリズムは、与えられた問題と異なるアルゴリズムの一致度によって決定される。
  論文  参考訳（メタデータ） (2023-11-22T06:23:18Z)
• Efficient Convex Algorithms for Universal Kernel Learning [46.573275307034336]
  カーネルの理想的な集合: 線形パラメータ化(トラクタビリティ)を認める; すべてのカーネルの集合に密着する(正確性)。 従来のカーネル最適化アルゴリズムは分類に限られており、計算に複雑なセミデフィニティプログラミング(SDP)アルゴリズムに依存していた。 本稿では,従来のSDP手法と比較して計算量を大幅に削減するSVD-QCQPQPアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2023-04-15T04:57:37Z)
• Algorithm Selection on a Meta Level [58.720142291102135]
  本稿では,与えられたアルゴリズムセレクタの組み合わせに最適な方法を求めるメタアルゴリズム選択の問題を紹介する。 本稿では,メタアルゴリズム選択のための一般的な方法論フレームワークと,このフレームワークのインスタンス化として具体的な学習手法を提案する。
  論文  参考訳（メタデータ） (2021-07-20T11:23:21Z)
• Towards Optimally Efficient Tree Search with Deep Learning [76.64632985696237]
  本稿では,線形モデルから信号整数を推定する古典整数最小二乗問題について検討する。 問題はNPハードであり、信号処理、バイオインフォマティクス、通信、機械学習といった様々な応用でしばしば発生する。 本稿では, 深いニューラルネットワークを用いて, 単純化されたメモリバウンドA*アルゴリズムの最適推定を推定し, HATSアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2021-01-07T08:00:02Z)
• Generalization in portfolio-based algorithm selection [97.74604695303285]
  ポートフォリオベースのアルゴリズム選択に関する最初の証明可能な保証を提供する。 ポートフォリオが大きければ、非常に単純なアルゴリズムセレクタであっても、過剰適合は避けられないことを示す。
  論文  参考訳（メタデータ） (2020-12-24T16:33:17Z)
• Extreme Algorithm Selection With Dyadic Feature Representation [78.13985819417974]
  我々は,数千の候補アルゴリズムの固定セットを考慮に入れた,極端なアルゴリズム選択(XAS)の設定を提案する。 我々は、XAS設定に対する最先端のAS技術の適用性を評価し、Dyadic特徴表現を利用したアプローチを提案する。
  論文  参考訳（メタデータ） (2020-01-29T09:40:58Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。