論文の概要: The Predicted-Deletion Dynamic Model: Taking Advantage of ML Predictions, for Free

• arxiv url: http://arxiv.org/abs/2307.08890v1
• Date: Mon, 17 Jul 2023 23:22:57 GMT
• ステータス: 処理完了
• システム内更新日: 2023-07-19 16:59:37.779000
• Title: The Predicted-Deletion Dynamic Model: Taking Advantage of ML Predictions, for Free
• Title（参考訳）: 予測削除動的モデル:ML予測の利点を無償で活用する
• Authors: Quanquan C. Liu and Vaidehi Srinivas
• Abstract要約: 効率的な動的アルゴリズムを設計する際のボトルネックは、更新シーケンスの未知の性質である。 動的グラフのエッジ更新を予測することによって,予測削除動的モデルを定式化する。 一部動的アルゴリズムを、オーバーヘッドの少ない完全に動的な設定に“リフト”する、このモデルのための新しいフレームワークを提供する。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: The main bottleneck in designing efficient dynamic algorithms is the unknown nature of the update sequence. In particular, there are some problems, like 3-vertex connectivity, planar digraph all pairs shortest paths, and others, where the separation in runtime between the best partially dynamic solutions and the best fully dynamic solutions is polynomial, sometimes even exponential. In this paper, we formulate the predicted-deletion dynamic model, motivated by a recent line of empirical work about predicting edge updates in dynamic graphs. In this model, edges are inserted and deleted online, and when an edge is inserted, it is accompanied by a "prediction" of its deletion time. This models real world settings where services may have access to historical data or other information about an input and can subsequently use such information make predictions about user behavior. The model is also of theoretical interest, as it interpolates between the partially dynamic and fully dynamic settings, and provides a natural extension of the algorithms with predictions paradigm to the dynamic setting. We give a novel framework for this model that "lifts" partially dynamic algorithms into the fully dynamic setting with little overhead. We use our framework to obtain improved efficiency bounds over the state-of-the-art dynamic algorithms for a variety of problems. In particular, we design algorithms that have amortized update time that scales with a partially dynamic algorithm, with high probability, when the predictions are of high quality. On the flip side, our algorithms do no worse than existing fully-dynamic algorithms when the predictions are of low quality. Furthermore, our algorithms exhibit a graceful trade-off between the two cases. Thus, we are able to take advantage of ML predictions asymptotically "for free.''
• Abstract（参考訳）: 効率的な動的アルゴリズムを設計する際のボトルネックは、更新シーケンスの未知の性質である。 特に、3頂点接続、すべてのペアの最短経路を平面ディグラフで表すといった問題があり、最高の部分動的解と最高の完全動的解の間の実行時の分離は多項式であり、時には指数関数である。 本稿では,動的グラフにおけるエッジ更新の予測に関する最近の経験的作業に動機づけられた予測削除動的モデルを定式化する。 このモデルでは、エッジをオンラインに挿入して削除し、エッジを挿入すると、その削除時間の"予測"が伴う。 このモデルは、サービスが入力に関する履歴データや他の情報にアクセスし、その情報を使用してユーザーの振る舞いを予測できる現実世界の設定をモデル化する。 このモデルは、部分動的設定と完全動的設定の間を補間し、動的設定への予測パラダイムを伴うアルゴリズムの自然な拡張を提供するので、理論的にも興味深い。 我々は、部分動的アルゴリズムをオーバーヘッドの少ない完全な動的設定に"リフト"する、このモデルのための新しいフレームワークを提供する。 我々はこのフレームワークを用いて、様々な問題に対して最先端の動的アルゴリズムの効率バウンダリを改善する。 特に、予測が高品質である場合に高い確率で部分的に動的アルゴリズムでスケールするアモータイズされた更新時間を持つアルゴリズムを設計する。 逆に、予測が低品質である場合、我々のアルゴリズムは既存のフルダイナミックアルゴリズムよりも悪くはない。 さらに,本アルゴリズムは両事例間に優雅なトレードオフを示す。 したがって、私たちは"無償で"漸近的に"ML予測を活用できます。 ''

関連論文リスト

• Efficient and Effective Implicit Dynamic Graph Neural Network [42.49148111696576]
  Indicit Dynamic Graph Neural Network (IDGNN) は動的グラフのための新しい暗黙的ニューラルネットワークである。 IDGNNの鍵となる特徴は、それが実証的に良好である、すなわち、固定点表現を持つことが理論的に保証されていることである。
  論文  参考訳（メタデータ） (2024-06-25T19:07:21Z)
• Model Ensembling for Constrained Optimization [7.4351710906830375]
  下流最適化に使用される多次元出力予測のためのモデルを組み立てたいという設定について検討する。 より正確には、状態空間を多次元実数値予測にマッピングする多くのモデルが与えられていると想像する。 これらの予測は、指定された制約の下で最適化したい線形対象の係数を形成する。 証明可能かつ収束性の高い2つのアルゴリズムに導かれる多重校正手法を適用した。
  論文  参考訳（メタデータ） (2024-05-27T01:48:07Z)
• OneNet: Enhancing Time Series Forecasting Models under Concept Drift by Online Ensembling [65.93805881841119]
  ドリフト問題に対処するため,textbfOnline textbfensembling textbfNetwork (OneNet)を提案する。 OneNet は State-Of-The-Art (SOTA) 法と比較してオンライン予測エラーを $mathbf50%$ 以上削減する。
  論文  参考訳（メタデータ） (2023-09-22T06:59:14Z)
• Improving Dual-Encoder Training through Dynamic Indexes for Negative Mining [61.09807522366773]
  本稿では,ソフトマックスを証明可能な境界で近似し,木を動的に維持するアルゴリズムを提案する。 我々は,2000万以上のターゲットを持つデータセットについて検討し,オラクル・ブルート力負の鉱業に関して,誤差を半分に削減した。
  論文  参考訳（メタデータ） (2023-03-27T15:18:32Z)
• Accelerated First-Order Optimization under Nonlinear Constraints [73.2273449996098]
  我々は、制約付き最適化のための一階アルゴリズムと非滑らかなシステムの間で、新しい一階アルゴリズムのクラスを設計する。 これらのアルゴリズムの重要な性質は、制約がスパース変数の代わりに速度で表されることである。
  論文  参考訳（メタデータ） (2023-02-01T08:50:48Z)
• ANACONDA: An Improved Dynamic Regret Algorithm for Adaptive Non-Stationary Dueling Bandits [20.128001589147512]
  本研究では,非定常デュエル帯域の問題について検討し,この問題に対する適応的動的後悔アルゴリズムを提案する。 ほぼ最適の $tildeO(sqrtStexttCW T)$ dynamic regret bound を示します。
  論文  参考訳（メタデータ） (2022-10-25T20:26:02Z)
• Robust Value Iteration for Continuous Control Tasks [99.00362538261972]
  シミュレーションから物理システムへ制御ポリシを転送する場合、そのポリシは、動作の変動に対して堅牢でなければならない。 本稿では、動的プログラミングを用いて、コンパクトな状態領域上での最適値関数を計算するRobust Fitted Value Iterationを提案する。 より深い強化学習アルゴリズムや非ロバストなアルゴリズムと比較して、ロバストな値の方が頑健であることを示す。
  論文  参考訳（メタデータ） (2021-05-25T19:48:35Z)
• Dynamic Graph Convolutional Recurrent Network for Traffic Prediction: Benchmark and Solution [18.309299822858243]
  DGCRN(Dynamic Graph Contemporal Recurrent Network)と呼ばれる新しい交通予測フレームワークを提案する。 DGCRNでは、ハイパーネットワークはノード属性から動的特性を活用して抽出するように設計されている。 我々は、各時間ステップで動的グラフの細かい反復をモデル化する生成法を最初に採用した。
  論文  参考訳（メタデータ） (2021-04-30T11:25:43Z)
• Autoregressive Dynamics Models for Offline Policy Evaluation and Optimization [60.73540999409032]
  表現的自己回帰ダイナミクスモデルが次の状態の異なる次元を生成し、以前の次元で順次条件付きで報酬を得ることを示す。 また,リプレイバッファを充実させる手段として,自己回帰的ダイナミクスモデルがオフラインポリシー最適化に有用であることを示す。
  論文  参考訳（メタデータ） (2021-04-28T16:48:44Z)
• Reinforcement Learning based dynamic weighing of Ensemble Models for Time Series Forecasting [0.8399688944263843]
  データモデリングのために選択されたモデルが(線形/非線形、静的/動的)異なるモデルと独立(最小相関)モデルである場合、予測の精度が向上することが知られている。 アンサンブルモデルを重み付けするために文献で提案された様々なアプローチは、静的な重みセットを使用する。 この問題に対処するため、Reinforcement Learning (RL)アプローチでは、各モデルの重み付けを異なるタイミングで動的に割り当て、更新する。
  論文  参考訳（メタデータ） (2020-08-20T10:40:42Z)
• Predicting Temporal Sets with Deep Neural Networks [50.53727580527024]
  本稿では,時間集合予測のためのディープニューラルネットワークに基づく統合解を提案する。 ユニークな視点は、セットレベルの共起グラフを構築することで要素関係を学ぶことである。 我々は,要素や集合の時間依存性を適応的に学習するアテンションベースのモジュールを設計する。
  論文  参考訳（メタデータ） (2020-06-20T03:29:02Z)

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

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