Asymptotically Robust Learning-Augmented Algorithms for Preemptive FIFO Buffer Management

• URL: http://arxiv.org/abs/2604.26349v1
• Date: Wed, 29 Apr 2026 07:00:07 GMT
• Title: Asymptotically Robust Learning-Augmented Algorithms for Preemptive FIFO Buffer Management
• Abstract summary: We present a learning-augmented online algorithm for the FIFO buffer management problem.<n>Our algorithm simultaneously achieves an optimal competitive ratio of 1 under perfect predictions, degrades smoothly as the prediction error increases, and maintains an competitive ratio of sqrt3 under arbitrarily inaccurate predictions.
• Score: 0.6875312133832078
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We present a learning-augmented online algorithm for the preemptive FIFO buffer management problem, where packets arrive online to a finite-capacity buffer, must be transmitted in FIFO order, and the algorithm may preemptively discard buffered packets to accommodate future arrivals. Our algorithm simultaneously achieves 1-consistency, η-smoothness, and asymptotic \sqrt{3}-robustness, where ηdenotes the prediction error. Specifically, it attains an optimal competitive ratio of 1 under perfect predictions, degrades smoothly as the prediction error increases, and maintains an asymptotic competitive ratio of \sqrt{3} under arbitrarily inaccurate predictions, matching the best-known worst-case guarantee for the classical online problem, established by Englert and Westermann in 2009 [Algorithmica 53(4): 523-548]. A key technical contribution of our work is the introduction of an \emph{output-based prediction error metric}. Because capacity constraints dictate that only a strictly bounded subset of arriving packets is ultimately transmitted, our metric assesses prediction quality over the resulting optimal schedules rather than the raw input sequences, avoiding artificial error penalties. To guarantee robustness, our algorithm dynamically monitors predictions and executes a \emph{buffer-clearing strategy} upon transitioning to a worst-case fallback mechanism. We prove that the competitive loss incurred by this clearing operation is bounded by an additive capacity constant that vanishes asymptotically. Finally, we show that our algorithm provides a generalized framework for learning-augmented buffer management: substituting the fallback module with any β-competitive online algorithm immediately yields asymptotic β-robustness.

Related papers

• Simultaneous Coverage and Efficiency Guarantee in Online Conformal Prediction [5.533296779866529]
  Adaptive conformal inference (ACI) of Gibbs and Cands and its variants are the standard approach to online conformal prediction under distribution shift.<n>Existing guarantees say nothing about prediction-set size, so validity can be achieved trivially at the cost of unduly wide prediction sets.<n>We consider a unified online learning framework that simultaneously controls absolute, non-optimal coverage violation and prediction-set efficiency.
  arXiv  Detail & Related papers  (2026-07-29T07:56:59Z)
• Constrained Online Convex Optimization with Memory and Predictions [9.387819018679325]
  We study Constrained Online Convex Optimization with Memory (COCO-M), where both the loss and the constraints depend on a finite window of past decisions made by the learner.<n>This setting extends the previously studied unconstrained online optimization with memory framework and captures practical problems such as the control of constrained dynamical systems and scheduling with reconfiguration budgets.
  arXiv  Detail & Related papers  (2026-03-22T19:27:28Z)
• A Switching Framework for Online Interval Scheduling with Predictions [4.352962539265558]
  We study online interval scheduling in the irrevocable setting, where each interval must be immediately accepted or rejected upon arrival.<n>We consider this problem in a learning-augmented setting, where the algorithm has access to (machine-learned) predictions.<n>Our main contribution is the SemiTrust-and-Switch framework, which provides a unified approach for combining prediction-based and classical interval scheduling algorithms.
  arXiv  Detail & Related papers  (2025-11-20T10:01:09Z)
• The Coverage Principle: How Pre-Training Enables Post-Training [70.25788947586297]
  We study how pre-training shapes the success of the final model.<n>We uncover a mechanism that explains the power of coverage in predicting downstream performance.
  arXiv  Detail & Related papers  (2025-10-16T17:53:50Z)
• A Universal Error Measure for Input Predictions Applied to Online Graph Problems [57.58926849872494]
  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.
  arXiv  Detail & Related papers  (2022-05-25T15:24:03Z)
• Efficient and Differentiable Conformal Prediction with General Function Classes [96.74055810115456]
  We propose a generalization of conformal prediction to multiple learnable parameters. We show that it achieves approximate valid population coverage and near-optimal efficiency within class. Experiments show that our algorithm is able to learn valid prediction sets and improve the efficiency significantly.
  arXiv  Detail & Related papers  (2022-02-22T18:37:23Z)
• 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)
• An Asymptotically Optimal Primal-Dual Incremental Algorithm for Contextual Linear Bandits [129.1029690825929]
  We introduce a novel algorithm improving over the state-of-the-art along multiple dimensions. We establish minimax optimality for any learning horizon in the special case of non-contextual linear bandits.
  arXiv  Detail & Related papers  (2020-10-23T09:12:47Z)
• Learning Optimal Power Flow: Worst-Case Guarantees for Neural Networks [1.8352113484137629]
  We formulate mixed-integer linear programs to obtain worst-case guarantees for neural network predictions. We show that the worst-case guarantees can be up to one order of magnitude larger than the empirical lower bounds calculated with conventional methods.
  arXiv  Detail & Related papers  (2020-06-19T09:19:14Z)

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.