Contract Scheduling With Predictions

• URL: http://arxiv.org/abs/2011.12439v1
• Date: Tue, 24 Nov 2020 23:00:04 GMT
• Title: Contract Scheduling With Predictions
• Authors: Spyros Angelopoulos and Shahin Kamali
• Abstract summary: We study the setting in which there is a potentially erroneous prediction concerning the interruption. For both settings, we investigate tradeoffs between the robustness (i.e., the worst-case performance assuming adversarial prediction) and the consistency (i.e., the performance assuming that the prediction is error-free)
• Score: 12.335698325757491
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Contract scheduling is a general technique that allows to design a system with interruptible capabilities, given an algorithm that is not necessarily interruptible. Previous work on this topic has largely assumed that the interruption is a worst-case deadline that is unknown to the scheduler. In this work, we study the setting in which there is a potentially erroneous prediction concerning the interruption. Specifically, we consider the setting in which the prediction describes the time that the interruption occurs, as well as the setting in which the prediction is obtained as a response to a single or multiple binary queries. For both settings, we investigate tradeoffs between the robustness (i.e., the worst-case performance assuming adversarial prediction) and the consistency (i.e, the performance assuming that the prediction is error-free), both from the side of positive and negative results.

Related papers

• Contract Scheduling with Distributional and Multiple Advice [37.64065953072774]
  Previous work has showed that a prediction on the interruption time can help improve the performance of contract-based systems. We introduce and study more general and realistic learning-augmented settings in which the prediction is in the form of a probability distribution. We show that the resulting system is robust to prediction errors in the distributional setting.
  arXiv  Detail & Related papers  (2024-04-18T19:58:11Z)
• Post-selection Inference for Conformal Prediction: Trading off Coverage for Precision [0.0]
  Traditionally, conformal prediction inference requires a data-independent specification of miscoverage level. We develop simultaneous conformal inference to account for data-dependent miscoverage levels.
  arXiv  Detail & Related papers  (2023-04-12T20:56:43Z)
• 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)
• Comparing Sequential Forecasters [35.38264087676121]
  Consider two forecasters, each making a single prediction for a sequence of events over time. How might we compare these forecasters, either online or post-hoc, while avoiding unverifiable assumptions on how the forecasts and outcomes were generated? We present novel sequential inference procedures for estimating the time-varying difference in forecast scores. We empirically validate our approaches by comparing real-world baseball and weather forecasters.
  arXiv  Detail & Related papers  (2021-09-30T22:54:46Z)
• 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)
• Novel Techniques to Assess Predictive Systems and Reduce Their Alarm Burden [0.0]
  We introduce an improved performance assessment technique ("u-metrics") using utility functions to score each prediction. Compared to traditional performance measures, u-metrics more accurately reflect the real-world benefits and costs of a predictor operating in a workflow context. We also describe the use of "snoozing," a method whereby predictions are suppressed for a period of time, commonly improving predictor performance.
  arXiv  Detail & Related papers  (2021-02-10T19:05:06Z)
• Distribution-Free, Risk-Controlling Prediction Sets [112.9186453405701]
  We show how to generate set-valued predictions from a black-box predictor that control the expected loss on future test points at a user-specified level. Our approach provides explicit finite-sample guarantees for any dataset by using a holdout set to calibrate the size of the prediction sets.
  arXiv  Detail & Related papers  (2021-01-07T18:59:33Z)
• Counterfactual Predictions under Runtime Confounding [74.90756694584839]
  We study the counterfactual prediction task in the setting where all relevant factors are captured in the historical data. We propose a doubly-robust procedure for learning counterfactual prediction models in this setting.
  arXiv  Detail & Related papers  (2020-06-30T15:49:05Z)
• 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)
• Predictive Business Process Monitoring via Generative Adversarial Nets: The Case of Next Event Prediction [0.026249027950824504]
  This paper proposes a novel adversarial training framework to address the problem of next event prediction. It works by putting one neural network against the other in a two-player game which leads to predictions that are indistinguishable from the ground truth. It systematically outperforms all baselines both in terms of accuracy and earliness of the prediction, despite using a simple network architecture and a naive feature encoding.
  arXiv  Detail & Related papers  (2020-03-25T08:31:28Z)
• Ambiguity in Sequential Data: Predicting Uncertain Futures with Recurrent Models [110.82452096672182]
  We propose an extension of the Multiple Hypothesis Prediction (MHP) model to handle ambiguous predictions with sequential data. We also introduce a novel metric for ambiguous problems, which is better suited to account for uncertainties.
  arXiv  Detail & Related papers  (2020-03-10T09:15:42Z)

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.