論文の概要: Online Dynamic Acknowledgement with Learned Predictions
- arxiv url: http://arxiv.org/abs/2305.18227v1
- Date: Thu, 25 May 2023 20:05:47 GMT
- ステータス: 処理完了
- システム内更新日: 2023-05-30 14:02:33.127384
- Title: Online Dynamic Acknowledgement with Learned Predictions
- Title（参考訳）: 学習予測を用いたオンライン動的認識
- Authors: Sungjin Im, Benjamin Moseley, Chenyang Xu, Ruilong Zhang
- Abstract要約: オンラインの動的認知問題を再考する。
問題の目標は、総要求遅延と承認コストを最小化することです。
このエレガントなモデルは、承認コストとリクエストで経験した待ち時間のトレードオフを研究します。
- 参考スコア（独自算出の注目度）: 13.821981661594844
- License: http://creativecommons.org/licenses/by-nc-nd/4.0/
- Abstract: We revisit the online dynamic acknowledgment problem. In the problem, a
sequence of requests arrive over time to be acknowledged, and all outstanding
requests can be satisfied simultaneously by one acknowledgement. The goal of
the problem is to minimize the total request delay plus acknowledgement cost.
This elegant model studies the trade-off between acknowledgement cost and
waiting experienced by requests. The problem has been well studied and the
tight competitive ratios have been determined. For this well-studied problem,
we focus on how to effectively use machine-learned predictions to have better
performance.
We develop algorithms that perform arbitrarily close to the optimum with
accurate predictions while concurrently having the guarantees arbitrarily close
to what the best online algorithms can offer without access to predictions,
thereby achieving simultaneous optimum consistency and robustness. This new
result is enabled by our novel prediction error measure. No error measure was
defined for the problem prior to our work, and natural measures failed due to
the challenge that requests with different arrival times have different effects
on the objective. We hope our ideas can be used for other online problems with
temporal aspects that have been resisting proper error measures.
- Abstract（参考訳）: オンラインの動的認識問題を再検討する。
問題では、リクエストのシーケンスが時間とともに到着して認識され、すべての優れたリクエストが1つの承認によって同時に満たされる。
問題の目標は、要求の総遅延と承認コストを最小化することである。
このエレガントなモデルは、承認コストと要求によって経験される待ちの間のトレードオフを研究する。
この問題はよく研究され、厳しい競争比率が決定されている。
このよく研究された問題に対して、より優れた性能を得るために機械学習による予測を効果的に活用する方法に焦点をあてる。
精度の高い予測で最適に任意に接近するアルゴリズムを開発し、予測にアクセスせずに最良のオンラインアルゴリズムが提供できるものに近い保証を同時に有し、同時に最適な一貫性と堅牢性を達成する。
この新たな結果は,新しい予測誤差尺度によって実現される。
作業前に問題に対するエラー対策は定義されておらず,到達時間の異なる要求が目的に対して異なる影響を持つという課題により,自然な対策は失敗に終わった。
当社のアイデアが,適切なエラー対策に抵抗する時間的側面を持つ,他のオンライン問題にも活用できることを願っています。
関連論文リスト
- Improved Online Conformal Prediction via Strongly Adaptive Online
Learning [86.4346936885507]
我々は、強い適応的後悔を最小限に抑える新しいオンライン共形予測手法を開発した。
提案手法は,すべての区間において,ほぼ最適に適応的な後悔を同時に達成できることを実証する。
実験により,本手法は実世界のタスクにおける既存の手法よりも,より優れたカバレッジと予測セットが得られることがわかった。
論文 参考訳（メタデータ） (2023-02-15T18:59:30Z) - A Universal Error Measure for Input Predictions Applied to Online Graph
Problems [57.58926849872494]
本稿では,入力予測における誤差の定量化のための新しい尺度を提案する。
この尺度は、予測されていない要求と予測されていない実際の要求によるエラーをキャプチャする。
論文 参考訳（メタデータ） (2022-05-25T15:24:03Z) - 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) - Online Search With Best-Price and Query-Based Predictions [2.3204178451683264]
本稿では,入力に関する誤予測が存在する可能性のある学習増強アルゴリズムについて検討する。
株式市場から得られたデータに関する実験結果を提供する。
論文 参考訳（メタデータ） (2021-12-02T20:18:37Z) - Double Coverage with Machine-Learned Advice [100.23487145400833]
オンラインの基本的な$k$-serverの問題を学習強化環境で研究する。
我々のアルゴリズムは任意の k に対してほぼ最適の一貫性-破壊性トレードオフを達成することを示す。
論文 参考訳（メタデータ） (2021-03-02T11:04:33Z) - Learnable and Instance-Robust Predictions for Online Matching, Flows and
Load Balancing [12.961453245099044]
本稿では,アルゴリズムが形式的に学習可能で,例えば頑健であることを要求して,予測を伴うアルゴリズムの拡張モデルを提案する。
ネットワークフロー割当問題と制限された割当ミスパン最小化の予測を含むオンラインアルゴリズムを設計する。
論文 参考訳（メタデータ） (2020-11-23T21:38:57Z) - Optimal Robustness-Consistency Trade-offs for Learning-Augmented Online
Algorithms [85.97516436641533]
機械学習予測を取り入れたオンラインアルゴリズムの性能向上の課題について検討する。
目標は、一貫性と堅牢性の両方を備えたアルゴリズムを設計することだ。
機械学習予測を用いた競合解析のための非自明な下界の最初のセットを提供する。
論文 参考訳（メタデータ） (2020-10-22T04:51:01Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。