Learning-Augmented Algorithms for Online Concave Packing and Convex Covering Problems

• URL: http://arxiv.org/abs/2411.08332v1
• Date: Wed, 13 Nov 2024 04:27:25 GMT
• Title: Learning-Augmented Algorithms for Online Concave Packing and Convex Covering Problems
• Authors: Elena Grigorescu, Young-San Lin, Maoyuan Song,
• Abstract summary: We present learning-augmented algorithmic frameworks for two fundamental optimizations settings. For online packing with concave objectives, we present a simple but overarching strategy that switches between the advice and the state-of-the-art online algorithm. We show that our algorithms break impossibility results when the advice is accurate, while maintaining comparable performance with state-of-the-art classical online algorithms even when the advice is erroneous.
• Score: 4.9826534303287335
• License:
• Abstract: Learning-augmented algorithms have been extensively studied across the computer science community in the recent years, driven by advances in machine learning predictors, which can provide additional information to augment classical algorithms. Such predictions are especially powerful in the context of online problems, where decisions have to be made without knowledge of the future, and which traditionally exhibits impossibility results bounding the performance of any online algorithm. The study of learning-augmented algorithms thus aims to use external advice prudently, to overcome classical impossibility results when the advice is accurate, and still perform comparably to the state-of-the-art online algorithms even when the advice is inaccurate. In this paper, we present learning-augmented algorithmic frameworks for two fundamental optimizations settings, extending and generalizing prior works. For online packing with concave objectives, we present a simple but overarching strategy that switches between the advice and the state-of-the-art online algorithm. For online covering with convex objectives, we greatly extend primal-dual methods for online convex covering programs by Azar et al. (FOCS 2016) and previous learning-augmented framework for online covering linear programs from the literature, to many new applications. We show that our algorithms break impossibility results when the advice is accurate, while maintaining comparable performance with state-of-the-art classical online algorithms even when the advice is erroneous.

Related papers

• A Simple Learning-Augmented Algorithm for Online Packing with Concave Objectives [4.9826534303287335]
  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.
  arXiv  Detail & Related papers  (2024-06-05T18:39:28Z)
• 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)
• 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)
• Optimistically Tempered Online Learning [19.12634663761194]
  Optimistic Online Learning algorithms exploit expert advices assumed optimistically to be always useful. We develop the emphoptimistically tempered (OT) online learning framework as well as OT adaptations of online algorithms. Our algorithms come with sound theoretical guarantees in the form of dynamic regret bounds.
  arXiv  Detail & Related papers  (2023-01-18T13:48:20Z)
• Learning-Augmented Algorithms for Online Linear and Semidefinite Programming [9.849604820019394]
  Semidefinite programming (SDP) is a unifying framework that generalizes both linear and quadratically-constrained programming. There exist known impossibility results for approxing the optimal solution when constraints for covering SDPs arrive in an online fashion. We show that if the predictor is accurate, we can efficiently bypass these impossibility results and achieve a constant-factor approximation to the optimal solution.
  arXiv  Detail & Related papers  (2022-09-21T19:16:29Z)
• Tree-Based Adaptive Model Learning [62.997667081978825]
  We extend the Kearns-Vazirani learning algorithm to handle systems that change over time. We present a new learning algorithm that can reuse and update previously learned behavior, implement it in the LearnLib library, and evaluate it on large examples.
  arXiv  Detail & Related papers  (2022-08-31T21:24:22Z)
• 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)
• 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)
• Evolving Reinforcement Learning Algorithms [186.62294652057062]
  We propose a method for meta-learning reinforcement learning algorithms. The learned algorithms are domain-agnostic and can generalize to new environments not seen during training. We highlight two learned algorithms which obtain good generalization performance over other classical control tasks, gridworld type tasks, and Atari games.
  arXiv  Detail & Related papers  (2021-01-08T18:55:07Z)
• 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.