SkipPredict: When to Invest in Predictions for Scheduling
- URL: http://arxiv.org/abs/2402.03564v1
- Date: Mon, 5 Feb 2024 22:24:19 GMT
- Title: SkipPredict: When to Invest in Predictions for Scheduling
- Authors: Rana Shahout, Michael Mitzenmacher
- Abstract summary: We introduce a novel approach to utilizing predictions, SkipPredict, designed to address their inherent cost.
To achieve this, we employ one-bit "cheap predictions" to classify jobs as either short or long.
We examine the effect of this cost for two distinct models.
- Score: 10.895221249490984
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: In light of recent work on scheduling with predicted job sizes, we consider
the effect of the cost of predictions in queueing systems, removing the
assumption in prior research that predictions are external to the system's
resources and/or cost-free. In particular, we introduce a novel approach to
utilizing predictions, SkipPredict, designed to address their inherent cost.
Rather than uniformly applying predictions to all jobs, we propose a tailored
approach that categorizes jobs based on their prediction requirements. To
achieve this, we employ one-bit "cheap predictions" to classify jobs as either
short or long. SkipPredict prioritizes predicted short jobs over long jobs, and
for the latter, SkipPredict applies a second round of more detailed "expensive
predictions" to approximate Shortest Remaining Processing Time for these jobs.
Our analysis takes into account the cost of prediction. We examine the effect
of this cost for two distinct models. In the external cost model, predictions
are generated by some external method without impacting job service times but
incur a cost. In the server time cost model, predictions themselves require
server processing time, and are scheduled on the same server as the jobs.
Related papers
- Performative Prediction on Games and Mechanism Design [69.7933059664256]
We study a collective risk dilemma where agents decide whether to trust predictions based on past accuracy.
As predictions shape collective outcomes, social welfare arises naturally as a metric of concern.
We show how to achieve better trade-offs and use them for mechanism design.
arXiv Detail & Related papers (2024-08-09T16:03:44Z) - 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) - Conformal Prediction Regions for Time Series using Linear
Complementarity Programming [25.094249285804224]
We propose an optimization-based method for reducing conservatism to enable long horizon planning and verification.
We show that this problem can be cast as a mixed integer linear complementarity program (MILCP), which we then relax into a linear complementarity program (LCP)
arXiv Detail & Related papers (2023-04-03T15:32:38Z) - Acela: Predictable Datacenter-level Maintenance Job Scheduling [27.990173338574138]
We present Acela, a machine learning system for predicting maintenance job duration.
We show that Acela reduces the number of servers that are taken offline by 1.87-4.28X, and reduces the server offline time by 1.40-2.80X.
arXiv Detail & Related papers (2022-12-10T00:22:49Z) - What Should I Know? Using Meta-gradient Descent for Predictive Feature
Discovery in a Single Stream of Experience [63.75363908696257]
computational reinforcement learning seeks to construct an agent's perception of the world through predictions of future sensations.
An open challenge in this line of work is determining from the infinitely many predictions that the agent could possibly make which predictions might best support decision-making.
We introduce a meta-gradient descent process by which an agent learns what predictions to make, 2) the estimates for its chosen predictions, and 3) how to use those estimates to generate policies that maximize future reward.
arXiv Detail & Related papers (2022-06-13T21:31:06Z) - 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) - Private Prediction Sets [72.75711776601973]
Machine learning systems need reliable uncertainty quantification and protection of individuals' privacy.
We present a framework that treats these two desiderata jointly.
We evaluate the method on large-scale computer vision datasets.
arXiv Detail & Related papers (2021-02-11T18:59:11Z) - Improving Event Duration Prediction via Time-aware Pre-training [90.74988936678723]
We introduce two effective models for duration prediction.
One model predicts the range/unit where the duration value falls in (R-pred); and the other predicts the exact duration value E-pred.
Our best model -- E-pred, substantially outperforms previous work, and captures duration information more accurately than R-pred.
arXiv Detail & Related papers (2020-11-05T01:52:11Z) - AutoCP: Automated Pipelines for Accurate Prediction Intervals [84.16181066107984]
This paper proposes an AutoML framework called Automatic Machine Learning for Conformal Prediction (AutoCP)
Unlike the familiar AutoML frameworks that attempt to select the best prediction model, AutoCP constructs prediction intervals that achieve the user-specified target coverage rate.
We tested AutoCP on a variety of datasets and found that it significantly outperforms benchmark algorithms.
arXiv Detail & Related papers (2020-06-24T23:13:11Z)
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.