A Novel Prediction Setup for Online Speed-Scaling
- URL: http://arxiv.org/abs/2112.03082v1
- Date: Mon, 6 Dec 2021 14:46:20 GMT
- Title: A Novel Prediction Setup for Online Speed-Scaling
- Authors: Antonios Antoniadis, Peyman Jabbarzade Ganje, Golnoosh Shahkarami
- Abstract summary: It is fundamental to incorporate energy considerations when designing (scheduling) algorithms.
This paper attempts to obtain the best of both worlds for the classical, deadline based, online speed-scaling problem.
- Score: 3.3440413258080577
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Given the rapid rise in energy demand by data centers and computing systems
in general, it is fundamental to incorporate energy considerations when
designing (scheduling) algorithms. Machine learning can be a useful approach in
practice by predicting the future load of the system based on, for example,
historical data. However, the effectiveness of such an approach highly depends
on the quality of the predictions and can be quite far from optimal when
predictions are sub-par. On the other hand, while providing a worst-case
guarantee, classical online algorithms can be pessimistic for large classes of
inputs arising in practice.
This paper, in the spirit of the new area of machine learning augmented
algorithms, attempts to obtain the best of both worlds for the classical,
deadline based, online speed-scaling problem: Based on the introduction of a
novel prediction setup, we develop algorithms that (i) obtain provably low
energy-consumption in the presence of adequate predictions, and (ii) are robust
against inadequate predictions, and (iii) are smooth, i.e., their performance
gradually degrades as the prediction error increases.
Related papers
- 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) - Online TSP with Predictions [3.8411077568039866]
We study the classical online traveling salesman problem (OLTSP)
Unlike the prediction models in other previous studies, each actual request in the OLTSP, associated with its arrival time and position, may not coincide with the predicted ones.
Our main result is to study different prediction models and design algorithms to improve the best-known results in the different settings.
arXiv Detail & Related papers (2022-06-30T15:35:53Z) - Scalable computation of prediction intervals for neural networks via
matrix sketching [79.44177623781043]
Existing algorithms for uncertainty estimation require modifying the model architecture and training procedure.
This work proposes a new algorithm that can be applied to a given trained neural network and produces approximate prediction intervals.
arXiv Detail & Related papers (2022-05-06T13:18:31Z) - Efficient and Differentiable Conformal Prediction with General Function
Classes [96.74055810115456]
We propose a generalization of conformal prediction to multiple learnable parameters.
We show that it achieves approximate valid population coverage and near-optimal efficiency within class.
Experiments show that our algorithm is able to learn valid prediction sets and improve the efficiency significantly.
arXiv Detail & Related papers (2022-02-22T18:37:23Z) - 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) - Parsimonious Learning-Augmented Caching [29.975391787684966]
We introduce and study the setting in which the learning-augmented algorithm can utilize the predictions parsimoniously.
We show that one can achieve quantitatively similar results but only using a sublinear number of predictions.
arXiv Detail & Related papers (2022-02-09T03:40:11Z) - 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) - Robust Learning-Augmented Caching: An Experimental Study [8.962235853317996]
Key optimization problem arising in caching cannot be optimally solved without knowing the future.
New field of learning-augmented algorithms proposes solutions that leverage classical online caching algorithms.
We show that a straightforward method has only a low overhead over a well-performing predictor.
arXiv Detail & Related papers (2021-06-28T13:15:07Z) - Learning Augmented Energy Minimization via Speed Scaling [11.47280189685449]
We study a variant of the classic online speed scaling problem, in which machine learning predictions about the future can be integrated naturally.
Inspired by recent work on learning-augmented online algorithms, we propose an algorithm which incorporates predictions in a black-box manner and outperforms any online algorithm if the accuracy is high.
arXiv Detail & Related papers (2020-10-22T11:58:01Z)
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.