論文の概要: On the Influence of the Feature Computation Budget on Per-Instance Algorithm Selection for Black-Box Optimization
- arxiv url: http://arxiv.org/abs/2605.04954v1
- Date: Wed, 06 May 2026 14:15:34 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-05-07 18:41:07.867576
- Title: On the Influence of the Feature Computation Budget on Per-Instance Algorithm Selection for Black-Box Optimization
- Title（参考訳）: ブラックボックス最適化のためのインスタンスごとのアルゴリズム選択における特徴計算予算の影響について
- Abstract要約: Per-Instance Algorithm selection (PIAS) は、あるインスタンス上でどのアルゴリズムを実行するかを決定することで、アルゴリズムの集合間の相補性を利用する。
これは、(a)機能計算に費やした予算のどれがPIASに価値があるかという問題と、(b)機能精度とPIASのパフォーマンスのトレードオフを最適化する予算のどの部分かという2つの疑問を提起する。
PIASは、機能計算に費やされた予算の4分の1の場合でも、ほとんどのテストシナリオで有効であることが分かりました。
- 参考スコア（独自算出の注目度）: 0.42970700836450487
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Per-instance algorithm selection (PIAS) takes advantage of complementarity between a set of algorithms by deciding which algorithm to run on a given instance. This decision is based on features of the instances, which, in the context of black-box optimization (BBO), require a part of the optimization budget to be computed. This raises two questions: (a) from which fraction of the budget spent on feature computation does PIAS become worth it for BBO, and (b) which fraction of the budget optimizes the tradeoff between feature accuracy and PIAS performance. To this end, we perform a broad study where PIAS with varying sampling budgets for feature computation is compared to the single best algorithm on a broad range of algorithm selection scenarios. These scenarios consist of two portfolio sizes, three problem sets, 4 dimensionalities, and 10 target budgets. We find that PIAS is viable for the majority of tested scenarios, even when as much as a quarter of the total budget is spent on feature computation. The tradeoff for the fraction of the budget spent on feature computation to maximize the benefit of PIAS is highly dependent on the specific AS scenario. Further, on average 20 percent of PIAS loss to the virtual best solver is explained by the budget spent on feature computation, highlighting the importance of properly accounting for the feature budget.
- Abstract（参考訳）: Per-Instance Algorithm selection (PIAS) は、あるインスタンス上でどのアルゴリズムを実行するかを決定することで、アルゴリズムの集合間の相補性を利用する。
この決定は、ブラックボックス最適化(BBO)の文脈で計算される最適化予算の一部を必要とするインスタンスの特徴に基づいている。
これは2つの疑問を提起する。
(a)機能計算に費やした予算のどの部分からPIASがBBOにとって価値のあるものとなるか
b) 予算のどの部分が特徴精度とPIAS性能のトレードオフを最適化するか。
そこで本研究では,多種多様なサンプリング予算を持つPIASを,多種多様なアルゴリズム選択シナリオにおいて,最も優れたアルゴリズムと比較した。
これらのシナリオは、2つのポートフォリオサイズ、3つの問題セット、4次元、10の目標予算で構成される。
PIASは、機能計算に費やされた予算の4分の1の場合でも、ほとんどのテストシナリオで有効であることが分かりました。
PIASのメリットを最大化するために、機能計算に費やされた予算のごく一部に対するトレードオフは、特定のASシナリオに大きく依存しています。
さらに,仮想最適解法に対するPIAS損失の約20%は,特徴計算に費やされた予算によって説明され,機能予算を適切に考慮することの重要性が強調された。
関連論文リスト
- Cost-Aware Learning [72.31444819326795]
本稿では,異なるコンポーネント関数をサンプリングするコスト認識学習の問題点について考察する。
凸関数に対するコスト・アウェア・Descentアルゴリズムを提案し、そのコスト複雑性を導出し誤差を$$$とする。
本稿では,性能を保ちつつポリシー最適化のコストを削減するアルゴリズムであるCost-Aware GRPOを紹介する。
論文 参考訳（メタデータ） (2026-04-30T15:39:09Z) - Principled Algorithms for Optimizing Generalized Metrics in Binary Classification [53.604375124674796]
一般化されたメトリクスを最適化するアルゴリズムを導入し、$H$-consistency と finite-sample generalization bounds をサポートする。
提案手法は,メトリクス最適化を一般化したコスト依存学習問題として再検討する。
我々は,理論性能を保証する新しいアルゴリズムMETROを開発した。
論文 参考訳（メタデータ） (2025-12-29T01:33:42Z) - Computational Budget Should Be Considered in Data Selection [21.598075666695483]
データ選択戦略には計算予算が不可欠であるべきだと我々は主張する。
本稿では,新しい計算予算対応データ選択法を提案する。
本手法は,視覚および言語ベンチマークのベースラインを最大14.42%上回る性能向上を実現する。
論文 参考訳（メタデータ） (2025-10-19T12:16:43Z) - Optimizing Anytime Reasoning via Budget Relative Policy Optimization [70.32755424260336]
我々は,任意の推論性能を最適化する新しいフレームワークであるAnytimeReasonerを提案する。
従来の分布からサンプルトークンの予算に適合するように、完全な思考プロセスを切り離します。
次に、累積報酬を最大化するために、分割された方法で思考と要約ポリシーを最適化する。
論文 参考訳（メタデータ） (2025-05-19T17:58:44Z) - PIPA: Preference Alignment as Prior-Informed Statistical Estimation [57.24096291517857]
本稿では、RLフリーな統一確率的フレームワークであるPIPA(Pior-Informed Preference Alignment)を紹介する。
PIPAはペアデータとアンペアデータの両方に対応し、回答とステップレベルのアノテーションを提供する。
異なる種類の事前情報を統合することにより,PIPA-MとPIPA-Nの2種類のPIPAを開発した。
論文 参考訳（メタデータ） (2025-02-09T04:31:30Z) - Achieving PAC Guarantees in Mechanism Design through Multi-Armed Bandits [8.013444110633223]
自動機構設計のための線形プログラム(LP)に最適解のクラスを解析的に導出する。
これらの解は、元の定式化における変数の総数よりも指数関数的に小さい基本変数の集合を用いて表すことができる。
本稿では,この用語の評価をマルチアーム・バンディット(MAB)問題に翻訳することでこの問題に対処する。
論文 参考訳（メタデータ） (2024-11-30T03:59:36Z) - On Constructing Algorithm Portfolios in Algorithm Selection for Computationally Expensive Black-box Optimization in the Fixed-budget Setting [0.0]
本稿では,アルゴリズムポートフォリオ構築におけるサンプリングフェーズにおける関数評価の回数を考慮することの重要性を論じる。
その結果,提案手法により構築されたアルゴリズムのポートフォリオは,従来の手法よりも大幅に向上していることがわかった。
論文 参考訳（メタデータ） (2024-05-13T03:31:13Z) - Stochastic Multi-round Submodular Optimization with Budget [7.902059578326225]
我々は、アイテムの部分集合上で定義された単調部分モジュラー目的関数の和を、複数のラウンドで適応的に最大化することを目指している。
目的関数はイベントの実現にも依存しており、全てのラウンドで選択できるアイテムの総数は、限られた予算で制限されている。
論文 参考訳（メタデータ） (2024-04-21T18:24:43Z) - Welfare Maximization Algorithm for Solving Budget-Constrained
Multi-Component POMDPs [2.007262412327553]
本稿では,多成分予算制約POMDPの最適ポリシを求めるアルゴリズムを提案する。
提案アルゴリズムは,現在実施中であるポリシーを大幅に上回っていることを示す。
論文 参考訳（メタデータ） (2023-03-18T01:43:47Z) - Best Arm Identification for Stochastic Rising Bandits [84.55453174601826]
SRB(Rising Bandits)は、選択される度に選択肢の期待される報酬が増加する、シーケンシャルな意思決定の問題をモデル化する。
本稿では,SRBの固定予算ベストアーム識別(BAI)問題に焦点をあてる。
R-UCBE と R-SR の2つのアルゴリズムを提案する。
論文 参考訳（メタデータ） (2023-02-15T08:01:37Z) - Bayesian Algorithm Execution: Estimating Computable Properties of
Black-box Functions Using Mutual Information [78.78486761923855]
多くの現実世界では、T関数の評価の予算を考えると、高価なブラックボックス関数 f の性質を推測したい。
本稿では,アルゴリズムの出力に対して相互情報を最大化するクエリを逐次選択する手法InfoBAXを提案する。
これらの問題に対してInfoBAXは、元のアルゴリズムで要求されるより500倍少ないクエリをfに使用する。
論文 参考訳（メタデータ） (2021-04-19T17:22:11Z) - Provably Efficient Exploration in Policy Optimization [117.09887790160406]
本稿では,最適化アルゴリズム(OPPO)の最適変種を提案する。
OPPO は $tildeO(sqrtd2 H3 T )$ regret を達成する。
我々の知る限りでは、OPPOは、探索する最初の証明可能な効率的なポリシー最適化アルゴリズムである。
論文 参考訳（メタデータ） (2019-12-12T08:40:02Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。