論文の概要: Online Weighted Paging with Unknown Weights
- arxiv url: http://arxiv.org/abs/2410.21266v1
- Date: Mon, 28 Oct 2024 17:57:40 GMT
- ステータス: 翻訳完了
- システム内更新日: 2024-10-29 12:20:40.636287
- Title: Online Weighted Paging with Unknown Weights
- Title（参考訳）: 未知の重みを持つオンライン重み付きページング
- Authors: Orin Levy, Noam Touitou, Aviv Rosenberg,
- Abstract要約: ページの重みを事前に知るのではなく、むしろ重みサンプルから学習するオンライン重み付きページングのアルゴリズムを提示する。
私たちの仕事は、コストサンプリングを含む他の問題に対して、オンラインアルゴリズムに刺激を与えることができると信じています。
- 参考スコア（独自算出の注目度）: 15.525560291268219
- License:
- Abstract: Online paging is a fundamental problem in the field of online algorithms, in which one maintains a cache of $k$ slots as requests for fetching pages arrive online. In the weighted variant of this problem, each page has its own fetching cost; a substantial line of work on this problem culminated in an (optimal) $O(\log k)$-competitive randomized algorithm, due to Bansal, Buchbinder and Naor (FOCS'07). Existing work for weighted paging assumes that page weights are known in advance, which is not always the case in practice. For example, in multi-level caching architectures, the expected cost of fetching a memory block is a function of its probability of being in a mid-level cache rather than the main memory. This complex property cannot be predicted in advance; over time, however, one may glean information about page weights through sampling their fetching cost multiple times. We present the first algorithm for online weighted paging that does not know page weights in advance, but rather learns from weight samples. In terms of techniques, this requires providing (integral) samples to a fractional solver, requiring a delicate interface between this solver and the randomized rounding scheme; we believe that our work can inspire online algorithms to other problems that involve cost sampling.
- Abstract（参考訳）: オンラインページのフェッチ要求がオンラインに届くと、$k$スロットのキャッシュを維持するオンラインアルゴリズムの分野において、オンラインページングは基本的な問題である。
この問題の重み付け版では、各ページは独自のフェッチングコストを持ち、Bansal, Buchbinder and Naor (FOCS'07) による(最適)$O(\log k)$-competitive randomized algorithm において、この問題に関するかなりの作業が完了した。
ページの重み付けに関する既存の研究は、ページの重み付けが事前に知られていることを前提としているが、実際にはそうとは限らない。
例えば、マルチレベルのキャッシュアーキテクチャでは、メモリブロックをフェッチするコストは、メインメモリではなく中レベルのキャッシュに入る確率の関数である。
この複雑な性質は事前に予測することはできないが、時間が経つにつれて、ページの重みに関する情報は、フェッチングコストを何回もサンプリングすることで収集することができる。
ページの重みを事前に知るのではなく、むしろ重みサンプルから学習するオンライン重み付きページングのアルゴリズムを提示する。
技術面では、この手法では(積分的な)サンプルを分数分解器に提供し、この解法とランダム化ラウンドリングスキームの微妙なインターフェースを必要とする。
関連論文リスト
- Learning to Compose SuperWeights for Neural Parameter Allocation Search [61.078949532440724]
提案手法は,同じ重み集合を用いて多くのネットワークに対してパラメータを生成することができることを示す。
これにより、効率的なアンサンブルや、いつでも予測できるようなタスクをサポートできます。
論文 参考訳（メタデータ） (2023-12-03T04:20:02Z) - Provably Efficient High-Dimensional Bandit Learning with Batched
Feedbacks [93.00280593719513]
本稿では,オンラインインタラクションのT$ステップをバッチに分割したバッチフィードバックによる高次元マルチアームコンテキストバンドレットについて検討する。
具体的には、各バッチは以前のバッチに依存するポリシーに従ってデータを収集し、その報酬はバッチの最後にのみ明らかにする。
我々のアルゴリズムは,$mathcalO( log T)$ バッチで完全に逐次的に設定されたものに匹敵する後悔の限界を達成している。
論文 参考訳（メタデータ） (2023-11-22T06:06:54Z) - On Optimal Caching and Model Multiplexing for Large Model Inference [66.50550915522551]
大きな言語モデル(LLM)や他の大きな基盤モデルは注目すべき成功を収めているが、そのサイズは既存のリソース消費とレイテンシーの問題を悪化させている。
キャッシュを用いて以前のクエリを格納し、モデルの多重化を学習し、クエリ処理のためのモデルの集合から選択する。
論文 参考訳（メタデータ） (2023-06-03T05:01:51Z) - MUSTACHE: Multi-Step-Ahead Predictions for Cache Eviction [0.709016563801433]
MUSTACHEは、既存のポリシーのように修正されるのではなく、観測されたメモリアクセス要求からロジックを学ぶ新しいページキャッシュ置換である。
本稿では,ページ要求予測問題をカテゴリー時系列予測タスクとして定式化する。
提案手法では,学習したページ要求予測器に次の$k$のページメモリ参照を問い合わせ,最適なB'el'adyの置換アルゴリズムをよりよく近似する。
論文 参考訳（メタデータ） (2022-11-03T23:10:21Z) - Sublinear Time Algorithm for Online Weighted Bipartite Matching [16.48305467237292]
オンラインバイパーティイトマッチングは、オンラインアルゴリズムの基本的な問題である。
ウェイトは、ユーザのディープ表現とアイテムのディープ表現との間の内部積によって決定される。
提案したランダム化データ構造では,マッチングアルゴリズムの競合比を保ちながら,重みをサブ線形時間で計算できることが示されている。
論文 参考訳（メタデータ） (2022-08-05T19:22:30Z) - Online Lewis Weight Sampling [62.38157566916501]
コーエンとペンはルイスの重量サンプリングを理論計算機科学コミュニティに導入した。
この重要なプリミティブを、オンラインコアセット、スライディングウィンドウ、対向ストリーミングモデルなど、他の設定に拡張した作品もいくつかある。
オンラインコアセット,スライディングウィンドウ,および逆ストリーミングモデルにおいて,すべての$pin(0,infty)$に対して,ほぼ最適に近い$ell_p$サブスペース埋め込みを設計する。
論文 参考訳（メタデータ） (2022-07-17T19:40:51Z) - Memory Bounds for the Experts Problem [53.67419690563877]
専門家のアドバイスによるオンライン学習は、逐次予測の根本的な問題である。
目標は、予測を処理し、最小コストで予測を行うことです。
アルゴリズムは、そのセットでもっとも優れた専門家と比較してどれだけうまく機能するかによって判断される。
論文 参考訳（メタデータ） (2022-04-21T01:22:18Z) - Online Sub-Sampling for Reinforcement Learning with General Function
Approximation [111.01990889581243]
本稿では,RLアルゴリズムによって収集されたデータポイントの情報取得量を測定する,効率的なオンラインサブサンプリングフレームワークを確立する。
複雑性バウンド関数クラスを持つ値ベースのメソッドの場合、$proptooperatornamepolylog(K)$ timesに対してのみポリシーを更新する必要がある。
少なくとも$Omega(K)$倍のポリシーを更新する既存のアプローチとは対照的に、当社のアプローチはポリシーの解決における最適化コールの数を劇的に削減します。
論文 参考訳（メタデータ） (2021-06-14T07:36:25Z) - Online Learning for Stochastic Shortest Path Model via Posterior
Sampling [29.289190242826688]
PSRL-SSPは、最短経路(SSP)問題に対する後方サンプリングに基づく強化学習アルゴリズムである。
これはそのような後方サンプリングアルゴリズムとしては初めてであり、これまで提案されていた楽観主義に基づくアルゴリズムよりも優れている。
論文 参考訳（メタデータ） (2021-06-09T18:46:39Z) - Metrical Task Systems with Online Machine Learned Advice [0.0]
機械学習予測器によるオンラインアルゴリズムの強化は,予測器の精度が適切であれば,競争比を確実に低下させることができることを示す。
我々は、$n$タスク上の一様タスクシステムの特定のクラスに焦点を当て、最良の決定論的アルゴリズムは$O(n)$競争であり、最良のランダム化アルゴリズムは$O(log n)$競争である。
論文 参考訳（メタデータ） (2020-12-17T04:56:51Z) - Online Algorithms for Estimating Change Rates of Web Pages [2.4923006485141284]
有限帯域の可用性とサーバの制限により、異なるページをクロールする頻度が制限される。
これらは、正確なページ変更率の知識を前提とするか、MLEのような非効率な手法を使って同じことを推定する。
ページ変更率をオンラインで推定するための3つの新しいスキームを提供する。
論文 参考訳（メタデータ） (2020-09-17T08:25:02Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。