論文の概要: On Tradeoffs in Learning-Augmented Algorithms
- arxiv url: http://arxiv.org/abs/2501.12770v1
- Date: Wed, 22 Jan 2025 10:12:18 GMT
- ステータス: 翻訳完了
- システム内更新日: 2025-01-23 16:53:03.939387
- Title: On Tradeoffs in Learning-Augmented Algorithms
- Title（参考訳）: 学習強化アルゴリズムにおけるトレードオフについて
- Authors: Ziyad Benomar, Vianney Perchet,
- Abstract要約: 学習強化アルゴリズムは、一貫性、堅牢性、滑らか性という3つの重要な特性を示さなければならない。
本稿では, 一貫性, 堅牢性, 滑らか性, 平均性能の相違点が複数存在することを実証する。
- 参考スコア（独自算出の注目度）: 17.387787159892287
- License:
- Abstract: The field of learning-augmented algorithms has gained significant attention in recent years. These algorithms, using potentially inaccurate predictions, must exhibit three key properties: consistency, robustness, and smoothness. In scenarios where distributional information about predictions is available, a strong expected performance is required. Typically, the design of these algorithms involves a natural tradeoff between consistency and robustness, and previous works aimed to achieve Pareto-optimal tradeoffs for specific problems. However, in some settings, this comes at the expense of smoothness. This paper demonstrates that certain problems involve multiple tradeoffs between consistency, robustness, smoothness, and average performance.
- Abstract（参考訳）: 近年,学習強化アルゴリズムの分野に注目が集まっている。
これらのアルゴリズムは、潜在的に不正確な予測を用い、一貫性、堅牢性、滑らか性という3つの重要な特性を示さなければならない。
予測に関する分散情報が利用できるシナリオでは、高い期待性能が要求される。
通常、これらのアルゴリズムの設計には、一貫性と堅牢性の間の自然なトレードオフと、特定の問題に対するパレート最適トレードオフを達成することを目的とした以前の作業が含まれる。
しかし、いくつかの設定では、これは滑らかさを犠牲にしている。
本稿では, 一貫性, 堅牢性, 滑らか性, 平均性能の相違点が複数存在することを実証する。
関連論文リスト
- Overcoming Brittleness in Pareto-Optimal Learning-Augmented Algorithms [6.131022957085439]
本稿では,ユーザ特定プロファイルを用いて,アルゴリズムの性能のスムーズさを強制する新しいフレームワークを提案する。
我々は、この新しいアプローチを、よく研究されたオンライン問題、すなわち片道取引問題に適用する。
論文 参考訳（メタデータ） (2024-08-07T23:15:21Z) - Learning-Augmented Algorithms with Explicit Predictors [67.02156211760415]
アルゴリズム設計の最近の進歩は、過去のデータと現在のデータから得られた機械学習モデルによる予測の活用方法を示している。
この文脈における以前の研究は、予測器が過去のデータに基づいて事前訓練され、ブラックボックスとして使用されるパラダイムに焦点を当てていた。
本研究では,予測器を解き,アルゴリズムの課題の中で生じる学習問題を統合する。
論文 参考訳（メタデータ） (2024-03-12T08:40:21Z) - It's All in the Mix: Wasserstein Machine Learning with Mixed Features [5.739657897440173]
混合機能問題の解法として,実用的なアルゴリズムを提案する。
提案手法は, 個々の特徴が存在する場合の既存手法を著しく上回りうることを示す。
論文 参考訳（メタデータ） (2023-12-19T15:15:52Z) - Minimalistic Predictions to Schedule Jobs with Online Precedence
Constraints [117.8317521974783]
オンライン優先制約による非サーボ的スケジューリングについて検討する。
アルゴリズムは、任意のジョブ依存に偏りがなく、前任者がすべて完了した場合に限り、ジョブについて学習する。
論文 参考訳（メタデータ） (2023-01-30T13:17:15Z) - Non-Clairvoyant Scheduling with Predictions Revisited [77.86290991564829]
非論理的スケジューリングでは、優先度不明な処理条件でジョブをスケジューリングするためのオンライン戦略を見つけることが課題である。
我々はこのよく研究された問題を、アルゴリズム設計に(信頼できない)予測を統合する、最近人気の高い学習強化された設定で再検討する。
これらの予測には所望の特性があり, 高い性能保証を有するアルゴリズムと同様に, 自然な誤差測定が可能であることを示す。
論文 参考訳（メタデータ） (2022-02-21T13:18:11Z) - Robustification of Online Graph Exploration Methods [59.50307752165016]
我々は、古典的で有名なオンライングラフ探索問題の学習強化版について研究する。
本稿では,予測をよく知られたNearest Neighbor(NN)アルゴリズムに自然に統合するアルゴリズムを提案する。
論文 参考訳（メタデータ） (2021-12-10T10:02:31Z) - Double Coverage with Machine-Learned Advice [100.23487145400833]
オンラインの基本的な$k$-serverの問題を学習強化環境で研究する。
我々のアルゴリズムは任意の k に対してほぼ最適の一貫性-破壊性トレードオフを達成することを示す。
論文 参考訳（メタデータ） (2021-03-02T11:04:33Z) - Optimal Robustness-Consistency Trade-offs for Learning-Augmented Online
Algorithms [85.97516436641533]
機械学習予測を取り入れたオンラインアルゴリズムの性能向上の課題について検討する。
目標は、一貫性と堅牢性の両方を備えたアルゴリズムを設計することだ。
機械学習予測を用いた競合解析のための非自明な下界の最初のセットを提供する。
論文 参考訳（メタデータ） (2020-10-22T04:51:01Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。