A Universal Error Measure for Input Predictions Applied to Online Graph Problems

• URL: http://arxiv.org/abs/2205.12850v1
• Date: Wed, 25 May 2022 15:24:03 GMT
• Title: A Universal Error Measure for Input Predictions Applied to Online Graph Problems
• Authors: Giulia Bernardini, Alexander Lindermayr, Alberto Marchetti-Spaccamela, Nicole Megow, Leen Stougie, Michelle Sweering
• Abstract summary: We introduce a novel measure for quantifying the error in input predictions. The measure captures errors due to absent predicted requests as well as unpredicted actual requests.
• Score: 57.58926849872494
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We introduce a novel measure for quantifying the error in input predictions. The error is based on a minimum-cost hyperedge cover in a suitably defined hypergraph and provides a general template which we apply to online graph problems. The measure captures errors due to absent predicted requests as well as unpredicted actual requests; hence, predicted and actual inputs can be of arbitrary size. We achieve refined performance guarantees for previously studied network design problems in the online-list model, such as Steiner tree and facility location. Further, we initiate the study of learning-augmented algorithms for online routing problems, such as the traveling salesperson problem and dial-a-ride problem, where (transportation) requests arrive over time (online-time model). We provide a general algorithmic framework and we give error-dependent performance bounds that improve upon known worst-case barriers, when given accurate predictions, at the cost of slightly increased worst-case bounds when given predictions of arbitrary quality.

Related papers

• Error Feedback under $(L_0,L_1)$-Smoothness: Normalization and Momentum [56.37522020675243]
  We provide the first proof of convergence for normalized error feedback algorithms across a wide range of machine learning problems. We show that due to their larger allowable stepsizes, our new normalized error feedback algorithms outperform their non-normalized counterparts on various tasks.
  arXiv  Detail & Related papers  (2024-10-22T10:19:27Z)
• Online Dynamic Acknowledgement with Learned Predictions [13.821981661594844]
  We revisit the online dynamic acknowledgment problem. The goal of the problem is to minimize the total request delay plus acknowledgement cost. This elegant model studies the trade-off between acknowledgement cost and waiting experienced by requests.
  arXiv  Detail & Related papers  (2023-05-25T20:05:47Z)
• Improved Online Conformal Prediction via Strongly Adaptive Online Learning [86.4346936885507]
  We develop new online conformal prediction methods that minimize the strongly adaptive regret. We prove that our methods achieve near-optimal strongly adaptive regret for all interval lengths simultaneously. Experiments show that our methods consistently obtain better coverage and smaller prediction sets than existing methods on real-world tasks.
  arXiv  Detail & Related papers  (2023-02-15T18:59:30Z)
• 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)
• 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)
• Backward-Compatible Prediction Updates: A Probabilistic Approach [12.049279991559091]
  We formalize the Prediction Update Problem and present an efficient probabilistic approach as answer to the above questions. In extensive experiments on standard classification benchmark data sets, we show that our method outperforms alternative strategies for backward-compatible prediction updates.
  arXiv  Detail & Related papers  (2021-07-02T13:05:31Z)
• Learnable and Instance-Robust Predictions for Online Matching, Flows and Load Balancing [12.961453245099044]
  We propose a new model for augmenting algorithms with predictions by requiring that they are formally learnable and instance robust. We design online algorithms with predictions for a network flow allocation problem and restricted assignment makespan minimization.
  arXiv  Detail & Related papers  (2020-11-23T21:38:57Z)

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.