論文の概要: The Predicted-Updates Dynamic Model: Offline, Incremental, and
Decremental to Fully Dynamic Transformations
- arxiv url: http://arxiv.org/abs/2307.08890v2
- Date: Mon, 27 Nov 2023 23:12:08 GMT
- ステータス: 処理完了
- システム内更新日: 2023-11-30 15:20:40.740201
- Title: The Predicted-Updates Dynamic Model: Offline, Incremental, and
Decremental to Fully Dynamic Transformations
- Title（参考訳）: 予測更新動的モデル:オフライン、インクリメンタル、デクリメントから完全な動的変換
- Authors: Quanquan C. Liu and Vaidehi Srinivas
- Abstract要約: 予測更新された動的モデルについて定式化する。
オフラインのパーティション・アンド・コンカレントアルゴリズムを、完全にダイナミックな設定に“リフト”する新しいフレームワークを提供します。
- 参考スコア（独自算出の注目度）: 1.8130068086063336
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We formulate the predicted-updates dynamic model, one of the first
beyond-worst-case models for dynamic algorithms, which generalizes a large set
of well-studied dynamic models including the offline dynamic, incremental, and
decremental models to the fully dynamic setting when given predictions about
the update times of the elements. In the most basic form of our model, we
receive a set of predicted update times for all of the updates that occur over
the event horizon. We give a novel framework that "lifts" offline
divide-and-conquer algorithms into the fully dynamic setting with little
overhead. Using this, we are able to interpolate between the offline and fully
dynamic settings; when the $\ell_1$ error of the prediction is linear in the
number of updates, we achieve the offline runtime of the algorithm (up to
$\mathrm{poly} \log n$ factors). Provided a fully dynamic backstop algorithm,
our algorithm will never do worse than the backstop algorithm regardless of the
prediction error. Furthermore, our framework achieves a smooth linear trade-off
between $\ell_1$ error in the predictions and runtime. These correspond to the
desiderata of consistency, robustness, and graceful degradation of the
algorithms-with-predictions literature. We further extend our techniques to
incremental and decremental settings, transforming algorithms in these settings
when given predictions of only the deletion and insertion times, respectively.
Our framework is general, and we apply it to obtain improved efficiency bounds
over the state-of-the-art dynamic algorithms for a variety of problems
including triconnectivity, planar digraph all pairs shortest paths, $k$-edge
connectivity, and others, for prediction error of reasonable magnitude.
- Abstract（参考訳）: 本稿では, 動的アルゴリズムにおける最初期の超越モデルである予測更新動的モデルを定式化し, オフライン動的, インクリメンタル, デクリメンタルモデルを含む, 多数のよく研究された動的モデルを, 要素の更新時間に関する予測が与えられたときに完全に動的設定に一般化する。
最も基本的なモデルでは、イベントの地平線上で発生するすべてのアップデートに対して、予測されるアップデートタイムのセットを受け取ります。
オフラインの分割・結合アルゴリズムを、オーバーヘッドの少ない完全にダイナミックな設定に"リフト"する、新しいフレームワークを提供する。
予測の$\ell_1$エラーが更新数で線形である場合、アルゴリズムのオフラインランタイム(最大$\mathrm{poly} \log n$ factor)を達成する。
完全にダイナミックなバックストップアルゴリズムが提供されると、予測誤差にかかわらず、我々のアルゴリズムはバックストップアルゴリズムよりも悪くならない。
さらに、我々のフレームワークは予測と実行時の$\ell_1$エラー間のスムーズな線形トレードオフを実現する。
これらは、一貫性、堅牢性、および予測付きアルゴリズムの優雅な劣化のデシラタに対応する。
削除時間と挿入時間のみの予測が与えられた場合に、これらの設定でアルゴリズムを変換し、インクリメンタル設定とデクリメント設定に技術をさらに拡張します。
私たちのフレームワークは一般的であり、三連結性、平面ダイアグラムの全ペア最短経路、$k$-edge接続など様々な問題に対して最先端の動的アルゴリズムよりも効率性が向上し、妥当な大きさの予測誤差が得られるように適用しています。
関連論文リスト
- 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。