論文の概要: Utilitarian Algorithm Configuration

• arxiv url: http://arxiv.org/abs/2310.20401v1
• Date: Tue, 31 Oct 2023 12:23:24 GMT
• ステータス: 処理完了
• システム内更新日: 2023-11-01 15:20:33.901078
• Title: Utilitarian Algorithm Configuration
• Title（参考訳）: 実用的アルゴリズム構成
• Authors: Devon R. Graham, Kevin Leyton-Brown and Tim Roughgarden
• Abstract要約: エンドユーザーに提供されるユーティリティを最大化するためにアルゴリズムを設定するための最初の非自明な手順を示す。 また, 実用目的は, アルゴリズム的メリットも有意であることを示す。
• 参考スコア（独自算出の注目度）: 19.018182447704977
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We present the first nontrivial procedure for configuring heuristic algorithms to maximize the utility provided to their end users while also offering theoretical guarantees about performance. Existing procedures seek configurations that minimize expected runtime. However, very recent theoretical work argues that expected runtime minimization fails to capture algorithm designers' preferences. Here we show that the utilitarian objective also confers significant algorithmic benefits. Intuitively, this is because mean runtime is dominated by extremely long runs even when they are incredibly rare; indeed, even when an algorithm never gives rise to such long runs, configuration procedures that provably minimize mean runtime must perform a huge number of experiments to demonstrate this fact. In contrast, utility is bounded and monotonically decreasing in runtime, allowing for meaningful empirical bounds on a configuration's performance. This paper builds on this idea to describe effective and theoretically sound configuration procedures. We prove upper bounds on the runtime of these procedures that are similar to theoretical lower bounds, while also demonstrating their performance empirically.
• Abstract（参考訳）: 提案手法は,エンドユーザに提供されるユーティリティを最大化するためにヒューリスティックアルゴリズムを構成するための最初の非自明な手順であり,性能に関する理論的保証を提供する。 既存のプロシージャは、期待されるランタイムを最小限にする設定を求める。 しかし、非常に最近の理論的研究は、期待されるランタイムの最小化はアルゴリズム設計者の好みを捉えないと主張している。 ここでは、実用目的も重要なアルゴリズム上の利点をもたらすことを示す。 実際、アルゴリズムがそのような長い実行を決して起こさない場合でも、平均ランタイムを確実に最小化する構成手順は、この事実を実証するために、膨大な数の実験を実行しなければなりません。 対照的に、ユーティリティはバウンダリであり、実行時に単調に減少し、構成のパフォーマンスに有意義な経験的境界が与えられる。 本稿では,この概念に基づいて,有効かつ理論的に健全な構成手順を記述する。 我々は、理論上の下限に類似した手順の実行時の上限を証明し、その性能を実証的に証明する。

関連論文リスト

• Parsimonious Optimal Dynamic Partial Order Reduction [1.5029560229270196]
  本稿では,Parsimonious-Optimal DPOR(POP)を提案する。 POPは、(i)同じ人種の複数の逆転を避ける擬似的な人種反転戦略を含む、いくつかの新しいアルゴリズム技術を組み合わせている。 我々のNidhuggの実装は、これらの手法が並列プログラムの解析を著しく高速化し、メモリ消費を抑えられることを示している。
  論文  参考訳（メタデータ） (2024-05-18T00:07:26Z)
• FuzzyFlow: Leveraging Dataflow To Find and Squash Program Optimization Bugs [92.47146416628965]
  FuzzyFlowはプログラム最適化をテストするために設計されたフォールトローカライゼーションとテストケース抽出フレームワークである。 我々は、データフロープログラム表現を活用して、完全に再現可能なシステム状態と最適化のエリア・オブ・エフェクトをキャプチャする。 テスト時間を削減するため,テスト入力を最小限に抑えるアルゴリズムを設計し,再計算のためのメモリ交換を行う。
  論文  参考訳（メタデータ） (2023-06-28T13:00:17Z)
• Formalizing Preferences Over Runtime Distributions [25.899669128438322]
  アルゴリズムよりも好みを記述したスコアリング関数を特徴付けるために,ユーティリティ理論のアプローチを用いる。 本稿では,不特定容量分布のモデル化における最大エントロピー手法の活用法を示す。
  論文  参考訳（メタデータ） (2022-05-25T19:43:48Z)
• A Fast PC Algorithm with Reversed-order Pruning and A Parallelization Strategy [22.31288740171446]
  PCアルゴリズムは観測データに基づく因果構造発見のための最先端のアルゴリズムである。 条件付き独立テストが実行された場合、最悪の場合、計算コストがかかる可能性がある。 これにより、タスクが数百から数千のノードを含む場合、アルゴリズムは計算的に難解になる。 本稿では、2つのノードを独立にレンダリングする条件セットが非特異であり、特定の冗長ノードを含む場合、結果の精度を犠牲にしない、という批判的な観察を提案する。
  論文  参考訳（メタデータ） (2021-09-10T02:22:10Z)
• Minimax Optimization with Smooth Algorithmic Adversaries [59.47122537182611]
  対戦相手が展開するスムーズなアルゴリズムに対して,Min-playerの新しいアルゴリズムを提案する。 本アルゴリズムは,制限周期のない単調進行を保証し,適切な勾配上昇数を求める。
  論文  参考訳（メタデータ） (2021-06-02T22:03:36Z)
• Provably Efficient Reward-Agnostic Navigation with Linear Value Iteration [143.43658264904863]
  我々は、最小二乗値スタイルのアルゴリズムで一般的に使用される、より標準的なベルマン誤差の概念の下での反復が、ほぼ最適値関数の学習において強力なPAC保証を提供することを示す。 そこで本稿では,任意の(線形な)報酬関数に対して,最適に近いポリシーを学習するためにどのように使用できるかを示す。
  論文  参考訳（メタデータ） (2020-08-18T04:34:21Z)
• Approximation Algorithms for Sparse Principal Component Analysis [57.5357874512594]
  主成分分析(PCA)は、機械学習と統計学において広く使われている次元削減手法である。 スパース主成分分析(Sparse principal Component Analysis)と呼ばれる,スパース主成分負荷を求める様々な手法が提案されている。 本研究では,SPCA問題に対するしきい値の精度,時間,近似アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2020-06-23T04:25:36Z)
• Refined bounds for algorithm configuration: The knife-edge of dual class approximability [94.83809668933021]
  トレーニングセットが、トレーニングセット上でのパラメータの平均メトリックのパフォーマンスが、予想される将来的なパフォーマンスに最も近いことを保証するために、どの程度の規模が必要かを調査する。 この近似が L-無限ノルムの下で成り立つなら、強いサンプル複雑性境界を与えることができる。 我々は、コンピュータ科学において最も強力なツールの一つである整数プログラミングの文脈において、我々の限界を実証的に評価する。
  論文  参考訳（メタデータ） (2020-06-21T15:32:21Z)
• Time-varying Gaussian Process Bandit Optimization with Non-constant Evaluation Time [93.6788993843846]
  非定常評価時間を効果的に処理できる新しい時間変化ベイズ最適化アルゴリズムを提案する。 我々の限界は、評価時間列のパターンが問題の難易度に大きな影響を与えることを決定づける。
  論文  参考訳（メタデータ） (2020-03-10T13:28:33Z)

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

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