Online Weighted Paging with Unknown Weights

• URL: http://arxiv.org/abs/2410.21266v1
• Date: Mon, 28 Oct 2024 17:57:40 GMT
• Title: Online Weighted Paging with Unknown Weights
• Authors: Orin Levy, Noam Touitou, Aviv Rosenberg,
• Abstract summary: We present the first algorithm for online weighted paging that does not know page weights in advance, but rather learns from weight samples. We believe that our work can inspire online algorithms to other problems that involve cost sampling.
• Score: 15.525560291268219
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• 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.

Related papers

• Toward a Lightweight and Robust Design for Caching [16.71673148088561]
  Guard is a lightweight robustification framework that enhances the robustness of a class of learning-augmented caching algorithms to $2H_k + 2$.<n> Guard achieves the current best-known trade-off between consistency and robustness, with only $O(1)$ additional per-request overhead.
  arXiv  Detail & Related papers  (2025-07-22T05:26:28Z)
• MaskPro: Linear-Space Probabilistic Learning for Strict (N:M)-Sparsity on Large Language Models [53.36415620647177]
  Semi-structured sparsity offers a promising solution by strategically retaining $N$ elements out of every $M$ weights.<n>Existing (N:M)-compatible approaches typically fall into two categories: rule-based layerwise greedy search, which suffers from considerable errors, and gradient-driven learning, which incurs prohibitive training costs.<n>We propose a novel linear-space probabilistic framework named MaskPro, which aims to learn a prior categorical distribution for every $M$ consecutive weights and subsequently leverages this distribution to generate the (N:M)-sparsity throughout an $N$-way sampling
  arXiv  Detail & Related papers  (2025-06-15T15:02:59Z)
• An Efficient Rehearsal Scheme for Catastrophic Forgetting Mitigation during Multi-stage Fine-tuning [55.467047686093025]
  A common approach to alleviate such forgetting is to rehearse samples from prior tasks during fine-tuning. We propose a sampling scheme, textttbf mix-cd, that prioritizes rehearsal of collateral damage'' samples. Our approach is computationally efficient, easy to implement, and outperforms several leading continual learning methods in compute-constrained settings.
  arXiv  Detail & Related papers  (2024-02-12T22:32:12Z)
• Learning to Compose SuperWeights for Neural Parameter Allocation Search [61.078949532440724]
  We show that our approach can generate parameters for many network using the same set of weights. This enables us to support tasks like efficient ensembling and anytime prediction.
  arXiv  Detail & Related papers  (2023-12-03T04:20:02Z)
• Provably Efficient High-Dimensional Bandit Learning with Batched Feedbacks [93.00280593719513]
  We study high-dimensional multi-armed contextual bandits with batched feedback where the $T$ steps of online interactions are divided into $L$ batches. In specific, each batch collects data according to a policy that depends on previous batches and the rewards are revealed only at the end of the batch. Our algorithm achieves regret bounds comparable to those in fully sequential setting with only $mathcalO( log T)$ batches.
  arXiv  Detail & Related papers  (2023-11-22T06:06:54Z)
• On Optimal Caching and Model Multiplexing for Large Model Inference [66.50550915522551]
  Large Language Models (LLMs) and other large foundation models have achieved noteworthy success, but their size exacerbates existing resource consumption and latency challenges. We study two approaches for mitigating these challenges: employing a cache to store previous queries and learning a model multiplexer to choose from an ensemble of models for query processing.
  arXiv  Detail & Related papers  (2023-06-03T05:01:51Z)
• MUSTACHE: Multi-Step-Ahead Predictions for Cache Eviction [0.709016563801433]
  MUSTACHE is a new page cache replacement whose logic is learned from observed memory access requests rather than fixed like existing policies. We formulate the page request prediction problem as a categorical time series forecasting task. Our method queries the learned page request forecaster to obtain the next $k$ predicted page memory references to better approximate the optimal B'el'ady's replacement algorithm.
  arXiv  Detail & Related papers  (2022-11-03T23:10:21Z)
• Sublinear Time Algorithm for Online Weighted Bipartite Matching [16.48305467237292]
  Online bipartite matching is a fundamental problem in online algorithms. Weights are decided by the inner product between the deep representation of a user and the deep representation of an item. We show that, with our proposed randomized data structures, the weights can be computed in sublinear time while still preserving the competitive ratio of the matching algorithm.
  arXiv  Detail & Related papers  (2022-08-05T19:22:30Z)
• Online Lewis Weight Sampling [62.38157566916501]
  Cohen and Peng introduced Lewis weight sampling to the theoretical computer science community. Several works have extended this important primitive to other settings, including the online coreset, sliding window, and adversarial streaming models. We design the first nearly optimal $ell_p$ subspace embeddings for all $pin(0,infty)$ in the online coreset, sliding window, and the adversarial streaming models.
  arXiv  Detail & Related papers  (2022-07-17T19:40:51Z)
• Memory Bounds for the Experts Problem [53.67419690563877]
  Online learning with expert advice is a fundamental problem of sequential prediction. The goal is to process predictions, and make a prediction with the minimum cost. An algorithm is judged by how well it does compared to the best expert in the set.
  arXiv  Detail & Related papers  (2022-04-21T01:22:18Z)
• Online Sub-Sampling for Reinforcement Learning with General Function Approximation [111.01990889581243]
  In this paper, we establish an efficient online sub-sampling framework that measures the information gain of data points collected by an RL algorithm. For a value-based method with complexity-bounded function class, we show that the policy only needs to be updated for $proptooperatornamepolylog(K)$ times. In contrast to existing approaches that update the policy for at least $Omega(K)$ times, our approach drastically reduces the number of optimization calls in solving for a policy.
  arXiv  Detail & Related papers  (2021-06-14T07:36:25Z)
• Online Learning for Stochastic Shortest Path Model via Posterior Sampling [29.289190242826688]
  PSRL-SSP is a posterior sampling-based reinforcement learning algorithm for the Shortest Path (SSP) problem. It is the first such posterior sampling algorithm and outperforms numerically previously proposed optimism-based algorithms.
  arXiv  Detail & Related papers  (2021-06-09T18:46:39Z)
• Metrical Task Systems with Online Machine Learned Advice [0.0]
  We show that augmenting online algorithms with a machine learned predictor can provably decrease the competitive ratio under as long as the predictor is suitably accurate. We focus on the specific class of uniform task systems on $n$ tasks, for which the best deterministic algorithm is $O(n)$ competitive and the best randomized algorithm is $O(log n)$ competitive.
  arXiv  Detail & Related papers  (2020-12-17T04:56:51Z)
• Online Algorithms for Estimating Change Rates of Web Pages [2.4923006485141284]
  finite bandwidth availability and server restrictions limit how frequently different pages can be crawled. These either assume the knowledge of exact page change rates or use inefficient methods such as MLE for estimating the same. We provide three novel schemes for online estimation of page change rates, all of which have extremely low running times per frequencies.
  arXiv  Detail & Related papers  (2020-09-17T08:25:02Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.