論文の概要: Formalizing Preferences Over Runtime Distributions
- arxiv url: http://arxiv.org/abs/2205.13028v2
- Date: Fri, 2 Jun 2023 22:51:09 GMT
- ステータス: 処理完了
- システム内更新日: 2023-06-07 05:23:21.293394
- Title: Formalizing Preferences Over Runtime Distributions
- Title（参考訳）: ランタイムディストリビューションに対するフォーマルな優先順位付け
- Authors: Devon R. Graham, Kevin Leyton-Brown, Tim Roughgarden
- Abstract要約: アルゴリズムよりも好みを記述したスコアリング関数を特徴付けるために,ユーティリティ理論のアプローチを用いる。
本稿では,不特定容量分布のモデル化における最大エントロピー手法の活用法を示す。
- 参考スコア（独自算出の注目度）: 25.899669128438322
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: When trying to solve a computational problem, we are often faced with a
choice between algorithms that are guaranteed to return the right answer but
differ in their runtime distributions (e.g., SAT solvers, sorting algorithms).
This paper aims to lay theoretical foundations for such choices by formalizing
preferences over runtime distributions. It might seem that we should simply
prefer the algorithm that minimizes expected runtime. However, such preferences
would be driven by exactly how slow our algorithm is on bad inputs, whereas in
practice we are typically willing to cut off occasional, sufficiently long runs
before they finish. We propose a principled alternative, taking a
utility-theoretic approach to characterize the scoring functions that describe
preferences over algorithms. These functions depend on the way our value for
solving our problem decreases with time and on the distribution from which
captimes are drawn. We describe examples of realistic utility functions and
show how to leverage a maximum-entropy approach for modeling underspecified
captime distributions. Finally, we show how to efficiently estimate an
algorithm's expected utility from runtime samples.
- Abstract（参考訳）: 計算問題を解こうとすると、正しい答えを返すことが保証されているが、実行時分布が異なるアルゴリズム(例えば、satソルバ、ソートアルゴリズム)の間で選択されることが多い。
本稿では,実行時分布に対する選好を形式化し,そのような選択の理論的基盤を構築することを目的とする。
期待するランタイムを最小限にするアルゴリズムを、単に好むべきだと思います。
しかし、そのような選好は、アルゴリズムが悪い入力でどれだけ遅くなっているかによって引き起こされる。
提案手法は,アルゴリズムよりも選好を記述したスコアリング関数を特徴付けるためのユーティリティ理論的手法である。
これらの関数は、問題を解くための価値が時間とともに減少し、キャップタイムが引き出される分布に依存する。
本稿では,現実的なユーティリティ関数の例を説明し,不特定容量分布をモデル化するための最大エントロピー手法の活用方法を示す。
最後に,実行時サンプルからアルゴリズムの予測ユーティリティを効率的に推定する方法を示す。
関連論文リスト
- Semi-Bandit Learning for Monotone Stochastic Optimization [20.776114616154242]
モノトーン」問題のクラスに対して汎用的なオンライン学習アルゴリズムを提供する。
我々のフレームワークは、預言者、Pandoraのボックスナップサック、不等式マッチング、部分モジュラー最適化など、いくつかの基本的な最適化問題に適用できる。
論文 参考訳（メタデータ） (2023-12-24T07:46:37Z) - Efficient distributed representations beyond negative sampling [4.5687771576879594]
本稿では,分散表現を効率よく学習する手法について述べる。
我々は,sotfmax正規化定数を線形時間で推定でき,効率的な最適化戦略を設計できることを示した。
論文 参考訳（メタデータ） (2023-03-30T15:48:26Z) - Trajectory-based Algorithm Selection with Warm-starting [2.3823600586675724]
本研究では,アルゴリズムの性能予測シナリオにおいて,性能回帰モデルとアルゴリズム選択モデルの品質と精度について検討する。
ウォームスタートを用いたトラジェクトリベースラン毎のアルゴリズム選択の有望な性能を示す。
論文 参考訳（メタデータ） (2022-04-13T14:00:55Z) - Machine Learning for Online Algorithm Selection under Censored Feedback [71.6879432974126]
オンラインアルゴリズム選択(OAS)では、アルゴリズム問題クラスのインスタンスがエージェントに次々に提示され、エージェントは、固定された候補アルゴリズムセットから、おそらく最高のアルゴリズムを迅速に選択する必要がある。
SAT(Satisfiability)のような決定問題に対して、品質は一般的にアルゴリズムのランタイムを指す。
本研究では,OASのマルチアームバンディットアルゴリズムを再検討し,この問題に対処する能力について議論する。
ランタイム指向の損失に適応し、時間的地平線に依存しない空間的・時間的複雑さを維持しながら、部分的に検閲されたデータを可能にする。
論文 参考訳（メタデータ） (2021-09-13T18:10:52Z) - 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) - Efficient Computation of Expectations under Spanning Tree Distributions [67.71280539312536]
本稿では,エッジファクター,非プロジェクティブ・スパンニングツリーモデルにおいて,一階期待と二階期待の重要なケースに対する統一アルゴリズムを提案する。
我々のアルゴリズムは勾配と期待の基本的な関係を利用しており、効率的なアルゴリズムを導出することができる。
論文 参考訳（メタデータ） (2020-08-29T14:58:26Z) - 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) - Time-varying Gaussian Process Bandit Optimization with Non-constant
Evaluation Time [93.6788993843846]
非定常評価時間を効果的に処理できる新しい時間変化ベイズ最適化アルゴリズムを提案する。
我々の限界は、評価時間列のパターンが問題の難易度に大きな影響を与えることを決定づける。
論文 参考訳（メタデータ） (2020-03-10T13:28:33Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。