論文の概要: Pareto-Optimal Learning-Augmented Algorithms for Online Conversion Problems

• arxiv url: http://arxiv.org/abs/2109.01556v1
• Date: Fri, 3 Sep 2021 14:27:33 GMT
• ステータス: 処理完了
• システム内更新日: 2021-09-06 13:48:35.959671
• Title: Pareto-Optimal Learning-Augmented Algorithms for Online Conversion Problems
• Title（参考訳）: オンライン変換問題に対するPareto-Optimal Learning-Augmented Algorithms
• Authors: Bo Sun, Russell Lee, Mohammad Hajiesmaili, Adam Wierman, Danny H.K. Tsang
• Abstract要約: 我々は,予測が正確である場合に競争率を改善することを目的として,オンライン変換問題の競合アルゴリズムを設計する。 また、予測品質に関わらず、最悪の競合比率を保証します。 ビットコイン変換に関する数値実験により,OTAの性能を実証した。
• 参考スコア（独自算出の注目度）: 13.593621603504847
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: This paper leverages machine-learned predictions to design competitive algorithms for online conversion problems with the goal of improving the competitive ratio when predictions are accurate (i.e., consistency), while also guaranteeing a worst-case competitive ratio regardless of the prediction quality (i.e., robustness). We unify the algorithmic design of both integral and fractional conversion problems, which are also known as the 1-max-search and one-way trading problems, into a class of online threshold-based algorithms (OTA). By incorporating predictions into design of OTA, we achieve the Pareto-optimal trade-off of consistency and robustness, i.e., no online algorithm can achieve a better consistency guarantee given for a robustness guarantee. We demonstrate the performance of OTA using numerical experiments on Bitcoin conversion.
• Abstract（参考訳）: 本稿では,予測精度(一貫性)の向上と,予測品質(堅牢性)に関わらず最悪の競合率を保証することを目的とした,オンライン変換問題の競合アルゴリズムの設計に,機械学習による予測を活用している。 1-max-search および one-way trading problem とも呼ばれる積分および分数変換問題のアルゴリズム設計を、オンラインしきい値ベースアルゴリズム (ota) のクラスに統合する。 OTAの設計に予測を組み込むことで、一貫性と堅牢性のパレート最適トレードオフを達成する。 ビットコイン変換における数値実験を用いてOTAの性能を示す。

関連論文リスト

• Overcoming Brittleness in Pareto-Optimal Learning-Augmented Algorithms [6.131022957085439]
  本稿では,ユーザ特定プロファイルを用いて,アルゴリズムの性能のスムーズさを強制する新しいフレームワークを提案する。 我々は、この新しいアプローチを、よく研究されたオンライン問題、すなわち片道取引問題に適用する。
  論文  参考訳（メタデータ） (2024-08-07T23:15:21Z)
• Learning Predictions for Algorithms with Predictions [49.341241064279714]
  予測器を学習するアルゴリズムに対して,一般的な設計手法を導入する。 オンライン学習の手法を応用して、敵のインスタンスに対して学習し、堅牢性と一貫性のあるトレードオフを調整し、新しい統計的保証を得る。 両部マッチング,ページマイグレーション,スキーレンタル,ジョブスケジューリングの手法を解析することにより,学習アルゴリズムの導出におけるアプローチの有効性を実証する。
  論文  参考訳（メタデータ） (2022-02-18T17:25:43Z)
• Robustification of Online Graph Exploration Methods [59.50307752165016]
  我々は、古典的で有名なオンライングラフ探索問題の学習強化版について研究する。 本稿では,予測をよく知られたNearest Neighbor(NN)アルゴリズムに自然に統合するアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2021-12-10T10:02:31Z)
• Adversarial Deep Learning for Online Resource Allocation [12.118811903399951]
  私たちはディープニューラルネットワークを使って、リソース割り当てと価格の問題に対するオンラインアルゴリズムをゼロから学習しています。 私たちの研究は、最悪のパフォーマンス保証の観点から、ディープニューラルネットワークを使用してオンラインアルゴリズムを設計した初めてのものです。
  論文  参考訳（メタデータ） (2021-11-19T15:48:43Z)
• Instantaneous Grammatical Error Correction with Shallow Aggressive Decoding [57.08875260900373]
  即時文法的誤り訂正(GEC)のためのトランスフォーマーのオンライン推論効率を改善するために,Shallow Aggressive Decoding (SAD)を提案する。 SADは、計算並列性を改善するために、各ステップで1つのトークンだけを復号するのではなく、可能な限り多くのトークンを並列に復号する。 英語と中国語のGECベンチマークでの実験では、アグレッシブな復号化がオンライン推論の大幅なスピードアップをもたらす可能性がある。
  論文  参考訳（メタデータ） (2021-06-09T10:30:59Z)
• 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)
• Triple Wins: Boosting Accuracy, Robustness and Efficiency Together by Enabling Input-Adaptive Inference [119.19779637025444]
  深層ネットワークは、(クリーンな自然画像の場合)正確さと(敵対的な摂動画像の場合)頑健さの相違に直面することを最近提案された。 本稿では,入力適応推論に関連するマルチエグジットネットワークについて検討し,モデル精度,ロバスト性,効率の最適化において「スイートポイント」を達成する上での強い期待を示す。
  論文  参考訳（メタデータ） (2020-02-24T00:40:22Z)

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

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