Paging with Succinct Predictions

• URL: http://arxiv.org/abs/2210.02775v1
• Date: Thu, 6 Oct 2022 09:26:34 GMT
• Title: Paging with Succinct Predictions
• Authors: Antonios Antoniadis, Joan Boyar, Marek Eli\'a\v{s}, Lene M. Favrholdt, Ruben Hoeksma, Kim S. Larsen, Adam Polak, Bertrand Simon
• Abstract summary: We study learning-augmented paging from the new perspective of requiring the least possible amount of predicted information. We develop algorithms for each of two setups that satisfy all three desirable properties of learning-augmented algorithms.
• Score: 25.959849403994202
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Paging is a prototypical problem in the area of online algorithms. It has also played a central role in the development of learning-augmented algorithms -- a recent line of research that aims to ameliorate the shortcomings of classical worst-case analysis by giving algorithms access to predictions. Such predictions can typically be generated using a machine learning approach, but they are inherently imperfect. Previous work on learning-augmented paging has investigated predictions on (i) when the current page will be requested again (reoccurrence predictions), (ii) the current state of the cache in an optimal algorithm (state predictions), (iii) all requests until the current page gets requested again, and (iv) the relative order in which pages are requested. We study learning-augmented paging from the new perspective of requiring the least possible amount of predicted information. More specifically, the predictions obtained alongside each page request are limited to one bit only. We consider two natural such setups: (i) discard predictions, in which the predicted bit denotes whether or not it is ``safe'' to evict this page, and (ii) phase predictions, where the bit denotes whether the current page will be requested in the next phase (for an appropriate partitioning of the input into phases). We develop algorithms for each of the two setups that satisfy all three desirable properties of learning-augmented algorithms -- that is, they are consistent, robust and smooth -- despite being limited to a one-bit prediction per request. We also present lower bounds establishing that our algorithms are essentially best possible.

Related papers

• Non-clairvoyant Scheduling with Partial Predictions [17.387787159892287]
  We present a learning-augmented algorithm satisfying the robustness, consistency, and smoothness criteria. We also present a novel tradeoff between consistency and smoothness inherent in the scenario with a restricted number of predictions.
  arXiv  Detail & Related papers  (2024-05-02T05:29:22Z)
• Learning-Augmented Algorithms with Explicit Predictors [67.02156211760415]
  Recent advances in algorithmic design show how to utilize predictions obtained by machine learning models from past and present data. Prior research in this context was focused on a paradigm where the predictor is pre-trained on past data and then used as a black box. In this work, we unpack the predictor and integrate the learning problem it gives rise for within the algorithmic challenge.
  arXiv  Detail & Related papers  (2024-03-12T08:40:21Z)
• Best of Many in Both Worlds: Online Resource Allocation with Predictions under Unknown Arrival Model [16.466711636334587]
  Online decision-makers often obtain predictions on future variables, such as arrivals, demands, and so on. Prediction accuracy is unknown to decision-makers a priori, hence blindly following the predictions can be harmful. We develop algorithms that utilize predictions in a manner that is robust to the unknown prediction accuracy.
  arXiv  Detail & Related papers  (2024-02-21T04:57:32Z)
• Minimalistic Predictions to Schedule Jobs with Online Precedence Constraints [117.8317521974783]
  We consider non-clairvoyant scheduling with online precedence constraints. An algorithm is oblivious to any job dependencies and learns about a job only if all of its predecessors have been completed.
  arXiv  Detail & Related papers  (2023-01-30T13:17:15Z)
• Algorithms with Prediction Portfolios [23.703372221079306]
  We study the use of multiple predictors for a number of fundamental problems, including matching, load balancing, and non-clairvoyant scheduling. For each of these problems we introduce new algorithms that take advantage of multiple predictors, and prove bounds on the resulting performance.
  arXiv  Detail & Related papers  (2022-10-22T12:58:07Z)
• A Universal Error Measure for Input Predictions Applied to Online Graph Problems [57.58926849872494]
  We introduce a novel measure for quantifying the error in input predictions. The measure captures errors due to absent predicted requests as well as unpredicted actual requests.
  arXiv  Detail & Related papers  (2022-05-25T15:24:03Z)
• Non-Clairvoyant Scheduling with Predictions Revisited [77.86290991564829]
  In non-clairvoyant scheduling, the task is to find an online strategy for scheduling jobs with a priori unknown processing requirements. We revisit this well-studied problem in a recently popular learning-augmented setting that integrates (untrusted) predictions in algorithm design. We show that these predictions have desired properties, admit a natural error measure as well as algorithms with strong performance guarantees.
  arXiv  Detail & Related papers  (2022-02-21T13:18:11Z)
• Learning Predictions for Algorithms with Predictions [49.341241064279714]
  We introduce a general design approach for algorithms that learn predictors. We apply techniques from online learning to learn against adversarial instances, tune robustness-consistency trade-offs, and obtain new statistical guarantees. We demonstrate the effectiveness of our approach at deriving learning algorithms by analyzing methods for bipartite matching, page migration, ski-rental, and job scheduling.
  arXiv  Detail & Related papers  (2022-02-18T17:25:43Z)
• Robustification of Online Graph Exploration Methods [59.50307752165016]
  We study a learning-augmented variant of the classical, notoriously hard online graph exploration problem. We propose an algorithm that naturally integrates predictions into the well-known Nearest Neighbor (NN) algorithm.
  arXiv  Detail & Related papers  (2021-12-10T10:02:31Z)
• Online Paging with a Vanishing Regret [6.520803851931362]
  This paper considers a variant of the online paging problem, where the online algorithm has access to multiple predictors, each producing a sequence of predictions for the page arrival times. The predictors may have occasional prediction errors and it is assumed that at least one of them makes a sublinear number of prediction errors in total. Our main result states that this assumption suffices for the design of a randomized online algorithm whose time-average regret with respect to the optimal offline algorithm tends to zero as the time tends to infinity.
  arXiv  Detail & Related papers  (2020-11-18T18:17:49Z)

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.