Optimal Robustness-Consistency Trade-offs for Learning-Augmented Online Algorithms

• URL: http://arxiv.org/abs/2010.11443v1
• Date: Thu, 22 Oct 2020 04:51:01 GMT
• Title: Optimal Robustness-Consistency Trade-offs for Learning-Augmented Online Algorithms
• Authors: Alexander Wei and Fred Zhang
• Abstract summary: 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.
• Score: 85.97516436641533
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: 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, meaning that the algorithm performs well when predictions are accurate and maintains worst-case guarantees. Such algorithms have been studied in a recent line of works due to Lykouris and Vassilvitskii (ICML '18) and Purohit et al (NeurIPS '18). They provide robustness-consistency trade-offs for a variety of online problems. However, they leave open the question of whether these trade-offs are tight, i.e., to what extent to such trade-offs are necessary. In this paper, we provide the first set of non-trivial lower bounds for competitive analysis using machine-learned predictions. We focus on the classic problems of ski-rental and non-clairvoyant scheduling and provide optimal trade-offs in various settings.

Related papers

• Overcoming Brittleness in Pareto-Optimal Learning-Augmented Algorithms [6.131022957085439]
  We propose a new framework in which the smoothness in the performance of the algorithm is enforced by means of a user-specified profile. We apply this new approach to a well-studied online problem, namely the one-way trading problem.
  arXiv  Detail & Related papers  (2024-08-07T23:15:21Z)
• Improving Online Algorithms via ML Predictions [19.03466073202238]
  We consider two classical problems, ski rental and non-clairvoyant job scheduling, and obtain new online algorithms that use predictions to make their decisions. These algorithms are oblivious to the performance of the predictor, improve with better predictions, but do not degrade much if the predictions are poor.
  arXiv  Detail & Related papers  (2024-07-25T02:17:53Z)
• 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)
• Improved Learning-Augmented Algorithms for the Multi-Option Ski Rental Problem via Best-Possible Competitive Analysis [0.1529342790344802]
  We present improved learning-augmented algorithms for the multi-option ski rental problem. Our algorithm is based on a new, provably best-possible randomized competitive algorithm for the problem.
  arXiv  Detail & Related papers  (2023-02-14T05:05:03Z)
• 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)
• Online Search with Predictions: Pareto-optimal Algorithm and its Applications in Energy Markets [32.50099216716867]
  This paper develops learning-augmented algorithms for energy trading in volatile electricity markets. We incorporate machine-learned predictions to design competitive algorithms for online search problems.
  arXiv  Detail & Related papers  (2022-11-12T04:12:10Z)
• 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)
• 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)
• Double Coverage with Machine-Learned Advice [100.23487145400833]
  We study the fundamental online $k$-server problem in a learning-augmented setting. We show that our algorithm achieves for any k an almost optimal consistency-robustness tradeoff.
  arXiv  Detail & Related papers  (2021-03-02T11:04:33Z)

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.