A Simple Learning-Augmented Algorithm for Online Packing with Concave Objectives

• URL: http://arxiv.org/abs/2406.03574v1
• Date: Wed, 5 Jun 2024 18:39:28 GMT
• Title: A Simple Learning-Augmented Algorithm for Online Packing with Concave Objectives
• Authors: Elena Grigorescu, Young-San Lin, Maoyuan Song,
• Abstract summary: We introduce and analyze a simple learning-augmented algorithm for online packing problems with linear constraints and concave objectives. We further raise the problem of understanding necessary and sufficient conditions for when such simple black-box solutions may be optimal.
• Score: 4.9826534303287335
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Learning-augmented algorithms has been extensively studied recently in the computer-science community, due to the potential of using machine learning predictions in order to improve the performance of algorithms. Predictions are especially useful for online algorithms making irrevocable decisions without knowledge of the future. Such learning-augmented algorithms aim to overcome the limitations of classical online algorithms when the predictions are accurate, and still perform comparably when the predictions are inaccurate. A common approach is to adapt existing online algorithms to the particular advice notion employed, which often involves understanding previous sophisticated algorithms and their analyses. However, ideally, one would simply use previous online solutions in a black-box fashion, without much loss in the approximation guarantees. Such clean solutions that avoid opening up black-boxes are often rare, and may be even missed the first time around. For example, Grigorescu et al. (NeurIPS 22) proposed a learning-augmented algorithms for online covering linear programs, but it later turned out that their results can be subsumed by a natural approach that switches between the advice and an online algorithm given as a black-box, as noted in their paper. In this work, we introduce and analyze a simple learning-augmented algorithm for online packing problems with linear constraints and concave objectives. We exhibit several direct applications of our framework including online packing linear programming, knapsack, resource management benefit, throughput maximization, and network utility maximization. We further raise the problem of understanding necessary and sufficient conditions for when such simple black-box solutions may be optimal. We believe this is an important direction of research that would unify many ad-hoc approaches from the literature.

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 Algorithms with Uncertainty-Quantified Predictions [11.951228732915936]
  We investigate the problem of optimally utilizing uncertainty-quantified predictions in the design of online algorithms. In particular, we study two classic online problems, ski rental and online search, where the decision-maker is provided predictions augmented with UQ. We demonstrate that non-trivial modifications to algorithm design are needed to fully leverage the UQ predictions.
  arXiv  Detail & Related papers  (2023-10-17T20:09:41Z)
• 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 Algorithms with Multiple Predictions [17.803569868141647]
  This paper studies online algorithms augmented with multiple machine-learned predictions. Our algorithm incorporates the use of predictions in the classic potential-based analysis of online algorithms.
  arXiv  Detail & Related papers  (2022-05-08T17:33:01Z)
• 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)
• 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)
• 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)
• The Primal-Dual method for Learning Augmented Algorithms [10.2730668356857]
  We extend the primal-dual method for online algorithms to incorporate predictions that advise the online algorithm about the next action to take. We show that our algorithms outperform any online algorithm when the prediction is accurate while maintaining good guarantees when the prediction is misleading.
  arXiv  Detail & Related papers  (2020-10-22T11:58:47Z)
• 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)

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.