Online Capacity Scaling Augmented With Unreliable Machine Learning Predictions

• URL: http://arxiv.org/abs/2101.12160v2
• Date: Wed, 20 Apr 2022 13:58:41 GMT
• Title: Online Capacity Scaling Augmented With Unreliable Machine Learning Predictions
• Authors: Daan Rutten, Debankur Mukherjee
• Abstract summary: We propose a novel algorithm, called Adaptive Balanced Capacity Scaling (ABCS), that has access to black-box machine learning predictions. ABCS aims to adapt to the predictions and is also robust against unpredictable surges in the workload. In particular, we prove that ABCS is $(varepsilon)$-competitive if the predictions are accurate, and yet, it has a uniformly bounded competitive ratio even if the predictions are completely inaccurate.
• Score: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Modern data centers suffer from immense power consumption. As a result, data center operators have heavily invested in capacity scaling solutions, which dynamically deactivate servers if the demand is low and activate them again when the workload increases. We analyze a continuous-time model for capacity scaling, where the goal is to minimize the weighted sum of flow-time, switching cost, and power consumption in an online fashion. We propose a novel algorithm, called Adaptive Balanced Capacity Scaling (ABCS), that has access to black-box machine learning predictions. ABCS aims to adapt to the predictions and is also robust against unpredictable surges in the workload. In particular, we prove that ABCS is $(1+\varepsilon)$-competitive if the predictions are accurate, and yet, it has a uniformly bounded competitive ratio even if the predictions are completely inaccurate. Finally, we investigate the performance of this algorithm on a real-world dataset and carry out extensive numerical experiments, which positively support the theoretical results.

Related papers

• A Dynamical Model of Neural Scaling Laws [79.59705237659547]
  We analyze a random feature model trained with gradient descent as a solvable model of network training and generalization. Our theory shows how the gap between training and test loss can gradually build up over time due to repeated reuse of data.
  arXiv  Detail & Related papers  (2024-02-02T01:41:38Z)
• PePNet: A Periodicity-Perceived Workload Prediction Network Supporting Rare Occurrence of Heavy Workload [11.93843096959306]
  workload of cloud servers is highly variable, with occasional heavy workload bursts. There are two categories of workload prediction methods: statistical methods and neural-network-based ones. We propose PePNet to improve overall especially heavy workload prediction accuracy.
  arXiv  Detail & Related papers  (2023-07-11T07:56:27Z)
• Boosted Dynamic Neural Networks [53.559833501288146]
  A typical EDNN has multiple prediction heads at different layers of the network backbone. To optimize the model, these prediction heads together with the network backbone are trained on every batch of training data. Treating training and testing inputs differently at the two phases will cause the mismatch between training and testing data distributions. We formulate an EDNN as an additive model inspired by gradient boosting, and propose multiple training techniques to optimize the model effectively.
  arXiv  Detail & Related papers  (2022-11-30T04:23:12Z)
• 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)
• A Novel Prediction Setup for Online Speed-Scaling [3.3440413258080577]
  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.
  arXiv  Detail & Related papers  (2021-12-06T14:46:20Z)
• Learning to Predict Trustworthiness with Steep Slope Loss [69.40817968905495]
  We study the problem of predicting trustworthiness on real-world large-scale datasets. We observe that the trustworthiness predictors trained with prior-art loss functions are prone to view both correct predictions and incorrect predictions to be trustworthy. We propose a novel steep slope loss to separate the features w.r.t. correct predictions from the ones w.r.t. incorrect predictions by two slide-like curves that oppose each other.
  arXiv  Detail & Related papers  (2021-09-30T19:19:09Z)
• Online Bin Packing with Predictions [11.306212771477645]
  We study the online variant of the problem, in which a sequence of items of various sizes must be placed into a minimum number of bins of uniform capacity. We design and analyze online algorithms with efficient tradeoffs between the consistency (i.e., the competitive ratio assuming no prediction error) and the robustness (i.e., the competitive ratio under adversarial error) This is the first theoretical and experimental study of online bin packing under competitive analysis, in the realistic setting of learnable predictions.
  arXiv  Detail & Related papers  (2021-02-05T17:32:52Z)
• 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)
• Optimal Robustness-Consistency Trade-offs for Learning-Augmented Online Algorithms [85.97516436641533]
  We study the problem of improving the performance of online algorithms by incorporating machine-learned predictions. The goal is to design algorithms that are both consistent and robust. We provide the first set of non-trivial lower bounds for competitive analysis using machine-learned predictions.
  arXiv  Detail & Related papers  (2020-10-22T04:51:01Z)
• A Predictive Autoscaler for Elastic Batch Jobs [8.354712625979776]
  Large batch jobs such as Deep Learning, HPC and Spark require far more computational resources and higher cost than conventional online service. We propose a predictive autoscaler to provide an elastic interface for the customers and overprovision instances.
  arXiv  Detail & Related papers  (2020-10-10T17:35:55Z)
• Diversity inducing Information Bottleneck in Model Ensembles [73.80615604822435]
  In this paper, we target the problem of generating effective ensembles of neural networks by encouraging diversity in prediction. We explicitly optimize a diversity inducing adversarial loss for learning latent variables and thereby obtain diversity in the output predictions necessary for modeling multi-modal data. Compared to the most competitive baselines, we show significant improvements in classification accuracy, under a shift in the data distribution.
  arXiv  Detail & Related papers  (2020-03-10T03:10:41Z)

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.