Parsimonious Learning-Augmented Online Metric Matching

• URL: http://arxiv.org/abs/2605.26886v1
• Date: Tue, 26 May 2026 11:47:58 GMT
• Title: Parsimonious Learning-Augmented Online Metric Matching
• Abstract summary: A growing line of work studies the tradeoff between performance guarantees and the number of predictions used in learning-augmented algorithms.<n>We develop parsimonious learning-augmented algorithms and establish lower bounds on their performance.<n>Our approach extends the Follow-the-Prediction framework to the parsimonious setting by filling in a virtual prediction in the absence of an actual prediction.
• Score: 1.5755923640031846
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Learning-augmented algorithms have received significant attention in recent years, particularly in the context of online optimization. Motivated by the high computational cost of generating predictions, a growing line of work studies the tradeoff between performance guarantees and the number of predictions used in learning-augmented algorithms for problems such as caching and metrical task systems. In this paper, we extend this line of research to online metric matching by developing parsimonious learning-augmented algorithms and establishing lower bounds on their performance. Our approach extends the Follow-the-Prediction framework to the parsimonious setting by filling in a virtual prediction in the absence of an actual prediction, using an online metric matching algorithm that maintains good intermediate matchings throughout its execution. We complement our theoretical results with an empirical evaluation, demonstrating the practical effectiveness of our approach.

Related papers

• Prediction-Specific Design of Learning-Augmented Algorithms [10.918779264590297]
  We show that prediction-specific performance criteria can enable significant performance improvements over coarser notions of consistency and robustness.<n>We develop a general bi-level optimization framework that enables systematically designing strongly-optimal algorithms.<n>Our results demonstrate that prediction-specific, strongly-optimal algorithms can significantly improve performance across a variety of online decision-making settings.
  arXiv  Detail & Related papers  (2025-10-16T17:06:53Z)
• Algorithms with Calibrated Machine Learning Predictions [9.18151868060576]
  A field of algorithms with predictions incorporates machine learning advice in the design of online algorithms to improve real-world performance.<n>A central consideration is the extent to which predictions can be trusted -- while existing approaches often require users to specify an aggregate trust level, modern machine learning models can provide estimates of prediction-level uncertainty.<n>We propose calibration as a principled and practical tool to bridge this gap, demonstrating the benefits of calibrated advice through two case studies.
  arXiv  Detail & Related papers  (2025-02-05T03:41:18Z)
• 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 Network Source Optimization with Graph-Kernel MAB [62.6067511147939]
  We propose Grab-UCB, a graph- kernel multi-arms bandit algorithm to learn online the optimal source placement in large scale networks. We describe the network processes with an adaptive graph dictionary model, which typically leads to sparse spectral representations. We derive the performance guarantees that depend on network parameters, which further influence the learning curve of the sequential decision strategy.
  arXiv  Detail & Related papers  (2023-07-07T15:03:42Z)
• Scalable computation of prediction intervals for neural networks via matrix sketching [79.44177623781043]
  Existing algorithms for uncertainty estimation require modifying the model architecture and training procedure. This work proposes a new algorithm that can be applied to a given trained neural network and produces approximate prediction intervals.
  arXiv  Detail & Related papers  (2022-05-06T13:18:31Z)
• 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)
• 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)
• 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)

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.