論文の概要: Beyond the Worst-Case Analysis of Algorithms (Introduction)
- arxiv url: http://arxiv.org/abs/2007.13241v1
- Date: Sun, 26 Jul 2020 23:18:19 GMT
- ステータス: 処理完了
- システム内更新日: 2022-11-06 20:12:23.226721
- Title: Beyond the Worst-Case Analysis of Algorithms (Introduction)
- Title（参考訳）: アルゴリズムの最悪のケース解析を越えて (序論)
- Authors: Tim Roughgarden
- Abstract要約: 最悪のケース分析では、与えられたサイズの入力に対して、アルゴリズムのパフォーマンスプロファイルを最悪のパフォーマンスで要約する。
この章では、本書の後半で詳細に議論されている最悪のケース分析のいくつかの選択肢について調査する。
- 参考スコア（独自算出の注目度）: 13.965228845332865
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: One of the primary goals of the mathematical analysis of algorithms is to
provide guidance about which algorithm is the "best" for solving a given
computational problem. Worst-case analysis summarizes the performance profile
of an algorithm by its worst performance on any input of a given size,
implicitly advocating for the algorithm with the best-possible worst-case
performance. Strong worst-case guarantees are the holy grail of algorithm
design, providing an application-agnostic certification of an algorithm's
robustly good performance. However, for many fundamental problems and
performance measures, such guarantees are impossible and a more nuanced
analysis approach is called for. This chapter surveys several alternatives to
worst-case analysis that are discussed in detail later in the book.
- Abstract（参考訳）: アルゴリズムの数学的解析の主要な目的の1つは、与えられた計算問題を解決するための「最良の」アルゴリズムについてガイダンスを提供することである。
最悪のケース分析は、与えられたサイズの入力に対して最悪のパフォーマンスによってアルゴリズムのパフォーマンスプロファイルを要約し、最も考えられる最悪のケースパフォーマンスのアルゴリズムを暗黙的に提唱する。
強力な最悪のケース保証はアルゴリズム設計の聖杯であり、アルゴリズムの堅牢な性能のアプリケーションに依存しない認証を提供する。
しかし、多くの基本的な問題や性能尺度では、そのような保証は不可能であり、より微妙な分析アプローチが求められている。
本章では,本書で詳述した最悪の事例分析の代替案について検討する。
関連論文リスト
- Absolute Ranking: An Essential Normalization for Benchmarking Optimization Algorithms [0.0]
多くの問題における最適化アルゴリズムの性能評価は,数値スケールの多様性が原因で複雑な問題となる。
本稿では,この問題を広範囲に検討し,根本原因の根本原因を徹底的に解析する上で説得力のある事例を提示する。
本研究では,「絶対ランク付け」と呼ばれる新しい数学的モデルとサンプリングに基づく計算手法を提案する。
論文 参考訳（メタデータ） (2024-09-06T00:55:03Z) - A General Online Algorithm for Optimizing Complex Performance Metrics [5.726378955570775]
我々は,バイナリ,マルチクラス,マルチラベルの分類問題において,様々な複雑なパフォーマンス指標を用いて,直接的に使用可能な汎用オンラインアルゴリズムを導入,分析する。
アルゴリズムの更新と予測のルールは、過去のデータを保存することなく、非常にシンプルで計算的に効率的である。
論文 参考訳（メタデータ） (2024-06-20T21:24:47Z) - Equitable and Fair Performance Evaluation of Whale Optimization
Algorithm [4.0814527055582746]
すべてのアルゴリズムは、徹底的に、幾分、知的に評価されることが不可欠である。
最適化アルゴリズムの有効性を等しく、公平に評価することは、様々な理由から簡単なプロセスではない。
論文 参考訳（メタデータ） (2023-09-04T06:32:02Z) - Accelerating Cutting-Plane Algorithms via Reinforcement Learning
Surrogates [49.84541884653309]
凸離散最適化問題に対する現在の標準的なアプローチは、カットプレーンアルゴリズムを使うことである。
多くの汎用カット生成アルゴリズムが存在するにもかかわらず、大規模な離散最適化問題は、難易度に悩まされ続けている。
そこで本研究では,強化学習による切削平面アルゴリズムの高速化手法を提案する。
論文 参考訳（メタデータ） (2023-07-17T20:11:56Z) - Regret Bounds for Expected Improvement Algorithms in Gaussian Process
Bandit Optimization [63.8557841188626]
期待されている改善(EI)アルゴリズムは、不確実性の下で最適化するための最も一般的な戦略の1つである。
本稿では,GP予測平均を通した標準既存値を持つEIの変種を提案する。
我々のアルゴリズムは収束し、$mathcal O(gamma_TsqrtT)$の累積後悔境界を達成することを示す。
論文 参考訳（メタデータ） (2022-03-15T13:17:53Z) - Outlier-Robust Sparse Estimation via Non-Convex Optimization [73.18654719887205]
空間的制約が存在する場合の高次元統計量と非破壊的最適化の関連について検討する。
これらの問題に対する新規で簡単な最適化法を開発した。
結論として、効率よくステーションに収束する一階法は、これらのタスクに対して効率的なアルゴリズムを導出する。
論文 参考訳（メタデータ） (2021-09-23T17:38:24Z) - Benchmarking Simulation-Based Inference [5.3898004059026325]
確率的モデリングの最近の進歩は、確率の数値的評価を必要としないシミュレーションに基づく推論アルゴリズムを多数もたらした。
推論タスクと適切なパフォーマンス指標を備えたベンチマークを,アルゴリズムの初期選択とともに提供する。
性能指標の選択は重要であり、最先端のアルゴリズムでさえ改善の余地があり、逐次推定によりサンプリング効率が向上することがわかった。
論文 参考訳（メタデータ） (2021-01-12T18:31:22Z) - Recent Theoretical Advances in Non-Convex Optimization [56.88981258425256]
近年、深層ネットワークにおける非最適化アルゴリズムの解析やデータ問題への関心が高まっており、非最適化のための理論的最適化アルゴリズムの最近の結果の概要を概説する。
論文 参考訳（メタデータ） (2020-12-11T08:28:51Z) - Data-driven Algorithm Design [21.39493074700162]
データ駆動型アルゴリズム設計は、現代のデータ科学とアルゴリズム設計の重要な側面である。
パラメータの小さな微調整は、アルゴリズムの振る舞いのカスケードを引き起こす可能性がある。
バッチおよびオンラインシナリオに対して、強力な計算および統計的パフォーマンス保証を提供する。
論文 参考訳（メタデータ） (2020-11-14T00:51:57Z) - Run2Survive: A Decision-theoretic Approach to Algorithm Selection based
on Survival Analysis [75.64261155172856]
生存分析(SA)は、自然に検閲されたデータをサポートし、アルゴリズムランタイムの分散モデルを学習するためにそのようなデータを使用する適切な方法を提供する。
我々は、アルゴリズム選択に対する洗練された決定論的アプローチの基礎として、そのようなモデルを活用し、Run2Surviveを疑う。
標準ベンチマークASlibによる広範な実験では、我々のアプローチは競争力が高く、多くの場合、最先端のASアプローチよりも優れていることが示されている。
論文 参考訳（メタデータ） (2020-07-06T15:20:17Z) - Extreme Algorithm Selection With Dyadic Feature Representation [78.13985819417974]
我々は,数千の候補アルゴリズムの固定セットを考慮に入れた,極端なアルゴリズム選択(XAS)の設定を提案する。
我々は、XAS設定に対する最先端のAS技術の適用性を評価し、Dyadic特徴表現を利用したアプローチを提案する。
論文 参考訳（メタデータ） (2020-01-29T09:40:58Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。