論文の概要: Pareto-Optimal Anytime Algorithms via Bayesian Racing

• arxiv url: http://arxiv.org/abs/2603.08493v1
• Date: Mon, 09 Mar 2026 15:28:39 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-03-10 15:13:16.29985
• Title: Pareto-Optimal Anytime Algorithms via Bayesian Racing
• Title（参考訳）: ベイジアン・レーシングによるパレート最適随時アルゴリズム
• Authors: Jonathan Wurth, Helena Stegherr, Neele Kemper, Michael Heider, Jörg Hähner,
• Abstract要約: 我々は,任意のアルゴリズム比較のためのフレームワークであるPolarBear(ベイジアンレースによるパレート最適アルゴリズム)を紹介する。 このアプローチでは、任意のインスタンス分布に対して、既知のオプティマを必要とせず、バウンダリを必要とせず、正規化も必要とせず、コヒーレントに集約する。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Selecting an optimization algorithm requires comparing candidates across problem instances, but the computational budget for deployment is often unknown at benchmarking time. Current methods either collapse anytime performance into a scalar, require manual interpretation of plots, or produce conclusions that change when algorithms are added or removed. Moreover, methods based on raw objective values require normalization, which needs bounds or optima that are often unavailable and breaks coherent aggregation across instances. We propose a framework that formulates anytime algorithm comparison as Pareto optimization over time: an algorithm is non-dominated if no competitor beats it at every timepoint. By using rankings rather than objective values, our approach requires no bounds, no normalization, and aggregates coherently across arbitrary instance distributions without requiring known optima. We introduce PolarBear (Pareto-optimal anytime algorithms via Bayesian racing), a procedure that identifies the anytime Pareto set through adaptive sampling with calibrated uncertainty. Bayesian inference over a temporal Plackett-Luce ranking model provides posterior beliefs about pairwise dominance, enabling early elimination of confidently dominated algorithms. The output Pareto set together with the posterior supports downstream algorithm selection under arbitrary time preferences and risk profiles without additional experiments.
• Abstract（参考訳）: 最適化アルゴリズムを選択するには、問題インスタンス間の候補を比較する必要があるが、ベンチマーク時に、デプロイの計算予算が不明な場合が多い。 現在の手法では、任意のパフォーマンスをスカラーに分解するか、プロットを手動で解釈するか、アルゴリズムの追加や削除によって変化する結論を生成する。 さらに、生の目的値に基づいたメソッドには正規化が必要であり、多くの場合は利用できない境界や最適化が必要であり、インスタンス間で一貫性のあるアグリゲーションを損なう。 本稿では,アルゴリズムが時間とともにパレート最適化としてアルゴリズム比較を定式化するフレームワークを提案する。 客観的な値ではなくランク付けを使用することで、我々のアプローチは、既知の最適化を必要とせずに、境界、正規化、任意のインスタンス分布を一貫性を持って集約する必要がない。 そこで我々はPolaBear(ベイジアン・レースによる最適最適アルゴリズム)を導入し,アダプティブ・サンプリングによるアダプティブ・サンプリングにより任意のパレートを識別する手法を提案する。 時間的プラケット・リュックランキングモデルに対するベイズ的推論は、ペアの優位性に関する後続の信念を与え、自信ある支配的なアルゴリズムの早期排除を可能にする。 出力パレートと後続のパレートは、任意の時間優先条件下での下流アルゴリズムの選択と、追加実験なしでリスクプロファイルをサポートする。

関連論文リスト

• Semi-Bandit Learning for Monotone Stochastic Optimization [16.921694787482213]
  一般的なオンライン学習アルゴリズムは「モノトーン」問題のクラスのために開発されている。 当社のフレームワークは,預言不平等やPandoraのボックス,単一リソースの収益管理,ポスト価格など,いくつかの基本的な問題に適用しています。
  論文  参考訳（メタデータ） (2023-12-24T07:46:37Z)
• Accelerated First-Order Optimization under Nonlinear Constraints [61.98523595657983]
  我々は、制約付き最適化のための一階アルゴリズムと非滑らかなシステムの間で、新しい一階アルゴリズムのクラスを設計する。 これらのアルゴリズムの重要な性質は、制約がスパース変数の代わりに速度で表されることである。
  論文  参考訳（メタデータ） (2023-02-01T08:50:48Z)
• Formalizing Preferences Over Runtime Distributions [25.899669128438322]
  アルゴリズムよりも好みを記述したスコアリング関数を特徴付けるために,ユーティリティ理論のアプローチを用いる。 本稿では,不特定容量分布のモデル化における最大エントロピー手法の活用法を示す。
  論文  参考訳（メタデータ） (2022-05-25T19:43:48Z)
• Machine Learning for Online Algorithm Selection under Censored Feedback [71.6879432974126]
  オンラインアルゴリズム選択(OAS)では、アルゴリズム問題クラスのインスタンスがエージェントに次々に提示され、エージェントは、固定された候補アルゴリズムセットから、おそらく最高のアルゴリズムを迅速に選択する必要がある。 SAT(Satisfiability)のような決定問題に対して、品質は一般的にアルゴリズムのランタイムを指す。 本研究では,OASのマルチアームバンディットアルゴリズムを再検討し,この問題に対処する能力について議論する。 ランタイム指向の損失に適応し、時間的地平線に依存しない空間的・時間的複雑さを維持しながら、部分的に検閲されたデータを可能にする。
  論文  参考訳（メタデータ） (2021-09-13T18:10:52Z)
• Run2Survive: A Decision-theoretic Approach to Algorithm Selection based on Survival Analysis [75.64261155172856]
  生存分析(SA)は、自然に検閲されたデータをサポートし、アルゴリズムランタイムの分散モデルを学習するためにそのようなデータを使用する適切な方法を提供する。 我々は、アルゴリズム選択に対する洗練された決定論的アプローチの基礎として、そのようなモデルを活用し、Run2Surviveを疑う。 標準ベンチマークASlibによる広範な実験では、我々のアプローチは競争力が高く、多くの場合、最先端のASアプローチよりも優れていることが示されている。
  論文  参考訳（メタデータ） (2020-07-06T15:20:17Z)
• Private Stochastic Convex Optimization: Optimal Rates in Linear Time [74.47681868973598]
  本研究では,凸損失関数の分布から得られた個体群損失を最小化する問題について検討する。 Bassilyらによる最近の研究は、$n$のサンプルを与えられた過剰な人口損失の最適境界を確立している。 本稿では,余剰損失に対する最適境界を達成するとともに,$O(minn, n2/d)$グラデーション計算を用いて凸最適化アルゴリズムを導出する2つの新しい手法について述べる。
  論文  参考訳（メタデータ） (2020-05-10T19:52:03Z)

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

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