acceptodds
Under review as a conference paper at ICLR 2027

Learning-Augmented Online Acknowledgment with Worst-Case Latency Guarantees

Abstract

We study the online acknowledgment problem under a maximum-latency objective, which captures tail latency and min–max fairness in systems where delayed responses may block downstream progress. An online algorithm observes packet arrivals over time and must decide when to issue acknowledgments, trading off acknowledgment overhead against the maximum delay among the packets covered by each acknowledgment. We consider this problem in a learning-augmented setting, where the algorithm receives incremental (possibly erroneous) predictions of the next arrival time. We introduce a deterministic, parameterized algorithm, AugmentedAlarm, whose performance depends explicitly on the prediction error and a trust parameter . We give a tight, error-dependent characterization of its competitive ratio: it is -competitive when predictions are perfect (consistency), -competitive under arbitrary error (robustness), and exhibits smooth, graceful degradation as prediction accuracy deteriorates. We prove matching upper and lower bounds, showing that this consistency–robustness tradeoff is Pareto-optimal: no deterministic online algorithm can simultaneously achieve better consistency and robustness. We further show that weaker prediction mechanisms, such as statistical information, are insufficient to achieve near-optimal performance, even when they are error-free. Finally, we complement our theoretical results with experiments on synthetic and real-world packet traces, confirming the predicted smooth dependence on prediction error and the practical benefits of learning-augmented strategies.

Primary area:
optimization
Keywords:
Learning-augmented algorithms, Online algorithms, Competitive analysis, Acknowledgement problem, Maximum latency, Worst-case guarantees, Robustness to prediction error

Reviews

Among:
Shape:
1234this paper, Bottom 27%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.00 over 3 reviews, above 27% of the others.
Reviewer_f5yQOpenReview ↗
Rating
1
Confidence
3
Informativeness
2
Presentation
2
Soundness
1
Read review
Paper summary

The paper studies online acknowledgment with an objective combining ACK costs and the sum of batch-wise maximum delays. Each arrival reveals a prediction of the next arrival time. The proposed learning-augmented Alarm algorithm has an error-dependent competitive-ratio upper bound, with consistency 1+λ1+\lambda and robustness 1+1/λ1+1/\lambda. The paper additionally claims a universal deterministic lower bound establishing Pareto optimality and evaluates the algorithm on synthetic and real packet traces.

Critical strengths

The paper considers a meaningful prediction interface for a classical acknowledgment objective. The proposed timer-based algorithm is simple, and its explicit error-dependent upper bound provides a concrete characterization of its behavior under imperfect next-arrival predictions.

Critical weaknesses

Theorem 5.4 is false under the stated model, invalidating the claimed universal Pareto optimality.

First, Appendix A.3, lines 690–695, omits the fixed ACK cost from the offline solution and does not account for the algorithm's subsequent ACK. Consequently, the displayed ratio does not establish the claimed lower bound.

More importantly, the following deterministic algorithm contradicts the theorem. Normalize the ACK cost and the critical interarrival gap ρ/(1−ρ)\rho/(1-\rho) to 11. Initially, operate in a trusting mode:

  • If the predicted next gap exceeds 11, acknowledge immediately.
  • Otherwise, wait for the next arrival, but acknowledge after a timeout of 11 if no arrival occurs.
  • Upon the first detected gap-classification error, switch permanently to Classic, which waits 11 after the most recent arrival and resets its timer on each arrival.

A classification error is detectable online: either a predicted short gap times out, or a predicted long gap is followed by an arrival within 11.

For a nonempty finite input with consecutive gaps Δ1,…,Δn−1\Delta_1,\ldots,\Delta_{n-1}, the offline optimum is

OPT=1+∑j=1n−1min⁡�0�.\mathrm{OPT}=1+\sum_{j=1}^{n-1}\min �0�.

Each gap can independently be covered by waiting across it or separated by an additional ACK. Under perfect predictions, the proposed fallback algorithm makes exactly these optimal choices, including an immediate final ACK, so it is 11-consistent.

For arbitrary predictions, use the paper's gap-wise cost decomposition. Correct classifications before the switch incur the corresponding optimal gap cost. A short prediction followed by a long gap incurs cost 22, twice its optimal gap cost. A long prediction followed by a short gap incurs cost 11, exceeding twice its optimal gap cost by at most 11. After the switch, Classic incurs at most twice the corresponding optimal gap costs, including a terminal cost of at most 22. Thus,

ALG≤2OPT+1≤3OPT,\mathrm{ALG}\le 2\mathrm{OPT}+1\le 3\mathrm{OPT},

since OPT≥1\mathrm{OPT}\ge1.

This gives a 11-consistent, 33-robust deterministic algorithm. Taking λ=1/4\lambda=1/4 contradicts Theorem 5.4, which requires robustness at least 55 whenever consistency does not exceed 1.251.25. The construction requires neither future information nor knowledge of the input length or prediction error.

This counterexample does not claim the same smoothness guarantee as Augmented Alarm. However, Theorem 5.4 quantifies over all deterministic algorithms without imposing such an additional requirement.

Questions for authors
  1. Does the stated model exclude the fallback algorithm above? If so, please identify the precise restriction. Otherwise, how should Theorem 5.4 and the associated Pareto-optimality claims be revised?

  2. After removing the universal optimality claim, what substantive optimality result remains beyond the analysis of the proposed timer family? Please distinguish algorithm-specific tightness from lower bounds applying to all deterministic algorithms.

2 comments
AuthorsOpenReview ↗

Revised Theorem 5.4 and the universal lower bound

Thank you for carefully reading the paper and for providing the counterexample.

The original Theorem 5.4. Yes, your fallback is valid in our model and has consistency 11 and robustness at most 33. Section 5.2 of the revised manuscript describes it, and Appendix A.2 proves the bound. In normalized units, OPT=1+∑gmin⁡(g,1)\mathrm{OPT}=1+\sum_g\min(g,1), where the sum runs over consecutive gaps and the leading 11 pays for the final ACK. The fallback matches the offline cost on every gap before the first misclassification. If a predicted short gap times out, the fallback pays 22 against an offline cost of 11. If a predicted long gap turns out to be short, it pays 11, which is at most one unit above twice the offline gap cost. The remaining gaps and the final ACK cost at most twice their offline contributions, so ALG≤2OPT+1≤3OPT\mathrm{ALG}\leq 2\mathrm{OPT}+1\leq 3\mathrm{OPT}.

This disproves the original Theorem 5.4, whose two-packet argument also omitted mandatory ACK costs.

BudgetAlarm and the revised Theorem 5.4. For each target consistency κ∈[1,2]\kappa\in[1,2], the revised Theorem 5.4 gives the smallest possible robustness among deterministic algorithms with consistency at most κ\kappa. Our new algorithm, BudgetAlarm, attains this value, R⋆(κ)=1+1+1+4κ2κR_\star(\kappa)=1+\frac{1+\sqrt{1+4\kappa}}{2\kappa}. The optimal robustness is about 2.6182.618 at perfect consistency and 2.3802.380 at consistency 1.251.25.

For a candidate robustness R=1+sR=1+s, the lower bound in Appendix A.3 tracks DD, the cost of completed gaps minus RR times their offline cost. Fixing every prediction to +∞+\infty gives the prediction-free lower bound s≥1s\geq 1. If the input ends at the current arrival and the algorithm waits tt before the final ACK, robustness requires D+1+t≤RD+1+t\leq R, so t≤s−Dt\leq s-D.

Let b=s−1/sb=s-1/s. Suppose D=b+uD=b+u for some u>0u>0. If D>sD>s, ending the input already violates robustness. Otherwise the ACK delay satisfies t≤1/s−ut\leq 1/s-u. The adversary can then release the next packet just after that ACK, at a gap of t+ε<1t+\varepsilon<1. The new value of DD is D+1−st−Rε≥b+(1+s)u−RεD+1-st-R\varepsilon\geq b+(1+s)u-R\varepsilon. By choosing ε\varepsilon sufficiently small at each step, the adversary makes the excess above bb grow geometrically until D>sD>s. Thus any algorithm with robustness RR must have D≤bD\leq b at every arrival.

Now consider a first packet with a prediction of +∞+\infty. If it is the only packet, the prediction is correct, so consistency forces the first ACK delay to be at most κ−1\kappa-1. For κ<2\kappa<2, the adversary can release a second packet just after that ACK. Applying D≤bD\leq b to this gap and taking ε\varepsilon to zero gives 1−s(κ−1)≤b1-s(\kappa-1)\leq b, or κs2≥s+1\kappa s^2\geq s+1. Solving this inequality yields R≥R⋆(κ)R\geq R_\star(\kappa). At κ=2\kappa=2, the prediction-free lower bound already gives R≥2R\geq 2.

To attain the bound, BudgetAlarm sets R=R⋆(κ)R=R_\star(\kappa) and uses the forecasts when D≤0D\leq 0. It sets a timeout of κ−1\kappa-1 for a predicted long gap and ss for a predicted short gap. Either timer can increase DD by at most bb on one gap, so DD stays at most bb. When D>0D>0, BudgetAlarm uses a timeout of 1/s1/s, which prevents DD from increasing and limits the final ACK cost to R−bR-b. When D≤0D\leq 0, the final ACK costs at most RR. In both cases, the total cost is at most ROPTR\mathrm{OPT}. With perfect predictions, each gap costs at most κ\kappa times its offline cost. Since R≥κR\geq\kappa, this keeps D≤0D\leq 0, and the final ACK costs κ\kappa.

Theorems 5.1 and 5.2 give AugmentedAlarm’s exact, continuous error-dependent ratio. Corollary 5.3 gives its consistency 1+λ1+\lambda and robustness 1+1/λ1+1/\lambda. Theorem 5.4 establishes BudgetAlarm’s Pareto optimality among all deterministic algorithms, including those with continuous or discontinuous error curves. At matched consistency κ=1.25\kappa=1.25, BudgetAlarm’s ratio jumps to about 2.3802.380 just above normalized error 0.3800.380. AugmentedAlarm gives a tighter guarantee just above that threshold and has robustness 55 under arbitrary errors. Appendix A.4 and Figure 3 compare the guarantees across error levels.

Dear Reviewer,

As the discussion period is approaching its end, we wanted to kindly follow up regarding our response and revised manuscript.

We sincerely appreciate your identification of the counterexample to the original Theorem 5.4. As explained in our rebuttal, we have corrected the error and replaced the theorem with a new universal lower bound, together with a matching algorithm, BudgetAlarm, establishing the exact deterministic consistency–robustness frontier.

We hope that this new result addresses your central concern regarding Pareto optimality and the substantive theoretical contribution of the paper.

We would greatly appreciate your reassessment in light of these revisions and would be happy to address any further concerns.

Thank you again for your time and careful consideration.

Reviewer_SZcPOpenReview ↗
Rating
3
Confidence
2
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

This paper studies the online acknowledgment problem under a maximum-latency objective, balancing acknowledgment overhead against packet delay. In a learning-augmented setting with potentially erroneous arrival predictions, the authors propose a deterministic, parameterized algorithm. Theoretical analysis shows the algorithm achieves high consistency with perfect predictions, strong robustness against arbitrary errors, and smooth degradation as prediction accuracy declines. By proving matching upper and lower bounds, the authors establish that this consistency-robustness trade-off is Pareto-optimal. They further show that weaker statistical predictions are insufficient even when error-free. Experiments on synthetic and real-world packet traces validate the theoretical findings.

Critical strengths

The theoretical problem is clearly formulated, the algorithm design is concise, and interpretable worst-case guarantees are provided. Furthermore, the theoretical analysis encompasses error-dependent bounds and the inherent trade-offs among algorithms.

Critical weaknesses

(-) There is a technical concern regarding the universal optimality conclusion in Theorem 5.4. The two-packet construction in Appendix A.3 omits the mandatory acknowledgment cost when calculating OPT. More importantly, the current model allows an algorithm to permanently switch to Classic after first detecting a prediction error, but the theorem does not rule out this strategy. Therefore, the authors need to re-examine this lower bound and its scope of applicability, as it directly supports the paper's Pareto-optimality claim.

(-) The representativeness of the experimental baselines and real-world data remains limited. The main baselines are extreme strategies or simple heuristics such as Trust, Classic, immediate acknowledgment, and fixed waiting time. Although related work mentions existing learning-augmented acknowledgment methods, the paper does not sufficiently explain why the closest methods cannot be adapted to the maximum-latency objective for comparison.

(-) The connection between the application motivation and the objective function is insufficiently specific. The paper mentions TCP acknowledgments, distributed computing, and online control, but does not use a complete example to explain how a practical system obtains predictions of the next arrival time, how it uses these predictions to determine the acknowledgment timing, and how the sum of maximum batch delays corresponds to the actual system performance objective. This makes the practical scope and applicability of the paper insufficiently clear.

(-) The validation of the actual prediction mechanism and parameter selection is still lacking. The experiments mainly control prediction error by adding uniform random noise to the true arrival times, without evaluating the error patterns generated by real predictors. The parameter \lambda is also primarily swept as a fixed design parameter, lacking a clear principle for practical calibration. Therefore, the experiments do not yet sufficiently demonstrate the potential gains of the algorithm under realistic prediction settings.

Questions for authors

See the 4 weaknesses for more details.

1 comment
AuthorsOpenReview ↗

Theorem 5.4 correction and experimental updates

Thank you for the detailed feedback on the theorem, baselines, and application.

Theorem 5.4. We agree that the original claim of Pareto optimality for AugmentedAlarm was incorrect. In the revision, we introduce BudgetAlarm, a new history-dependent algorithm that adapts its timers using the costs incurred on completed gaps. The revised Theorem 5.4 shows that for each target consistency κ∈[1,2]\kappa \in [1,2], BudgetAlarm achieves robustness R⋆(κ)=1+1+1+4κ2κR_\star(\kappa) = 1 + \frac{1 + \sqrt{1 + 4\kappa}}{2\kappa}. The matching lower bound in Appendix A.3 accounts for the mandatory final ACK and applies to all deterministic algorithms with consistency at most κ\kappa, including those that switch permanently to Classic after detecting an error. Thus BudgetAlarm is Pareto optimal.

Baselines and trace coverage. Figure 5 (Appendix C) compares AugmentedAlarm and BudgetAlarm at the same consistency (1.251.25), using identical arrivals and forecasts. Classic serves as the prediction-free baseline. For MAWI, we regenerated 1,000 windows from the first 54.86 seconds of one capture. Each window contains 1,000 distinct arrival timestamps, and the windows can overlap (Section 7). The new results follow the same pattern as in the submitted paper. On MAWI at low noise (η≈0.245\eta \approx 0.245), both algorithms average about 1.0351.035 times OPT\mathrm{OPT}, compared with 1.1051.105 for Classic.

Section 2 discusses the closest learning-augmented acknowledgment methods. They optimize sum delay and assume forecasts that describe traffic beyond the next arrival, such as an entire ACK schedule or future arrival intensities. A direct comparison would therefore give these methods access to forecasts beyond the incremental next-arrival estimates available to our algorithms.

Application and use of forecasts. Section 1 gives the example of a stream processor that sends cumulative ACKs so the upstream producer can release a batch’s state. Each ACK has a fixed overhead. The producer also pays a holding cost proportional to how long the batch stays open, measured by the age of its oldest item when the ACK is sent.

The processor could forecast the next gap using the median of recent completed gaps. AugmentedAlarm sets a timeout of λτ\lambda\tau if the forecast is above the break-even gap τ\tau, and τ/λ\tau/\lambda otherwise. If another item arrives by the deadline, the algorithm resets the timer using the new forecast. Otherwise, it sends an acknowledgment.

Forecast validation and calibration. In our experiments, we tested several values of λ\lambda at different levels of prediction noise. In practice, one way to choose λ\lambda is to start with the largest worst-case ratio the application can tolerate. If that ratio is B≥2B \geq 2, Corollary 5.3 requires λ≥1/(B−1)\lambda \geq 1/(B-1). The smallest allowed value gives AugmentedAlarm its best guarantee when predictions are correct. Purohit et al. (2018, §4.1) used this approach in their deterministic ski-rental experiments, choosing λ=0.5\lambda=0.5 to guarantee a worst-case ratio of 33.

The value that minimizes average cost depends on the forecaster and the workload. To find it, one could train the forecaster on earlier traffic, choose the allowed value of λ\lambda with the lowest ACK-plus-delay cost on a separate validation window, and test that choice on later traffic.

Reviewer_Xnx7OpenReview ↗
Rating
2(+1)
Confidence
3
Informativeness
1
Presentation
3
Soundness
1
Read review
Paper summary

The paper studies online acknowledgment with a cost combining acknowledgment overhead and the maximum packet delay within each batch. It considers predictions of the next arrival time and proposes an alarm-based algorithm with a parameter λ\lambda controlling trust in those predictions. The authors derive tight error-dependent bounds for this algorithm, giving (1+λ)(1+\lambda)-consistency and (1+1/λ)(1+1/\lambda)-robustness, and claim that this tradeoff is optimal among deterministic algorithms. They also establish lower bounds for limited advice and evaluate the algorithm on synthetic arrivals and real packet traces.

Critical strengths

The paper studies a fundamental online decision problem and gives a simple, intuitive algorithm whose performance degrades smoothly with prediction error. The matching upper and lower bounds for the proposed algorithm make its guarantees precise and clarify how the trust parameter affects performance. The advice-complexity lower bound complements this analysis by showing that sublinear advice cannot guarantee a competitive ratio arbitrarily close to 11, even when the advice is correct. Together, these results provide useful guarantees for the proposed algorithm and a limitation on what compact predictions can achieve.

Critical weaknesses
  1. Each inter-arrival gap admits a ski-rental interpretation: waiting incurs latency cost, while acknowledging incurs a fixed cost. The short/long alarm rule closely follows the deterministic learning-augmented ski-rental algorithm of Kumar, Purohit and Svitkina (2018). The consistency and robustness guarantees follow by summing the corresponding local bounds, and the error-dependent analysis and matching examples appear to require relatively straightforward adaptations. Although that work is cited, the manuscript does not explain this direct connection or clearly identify the additional technical challenges. The advice-complexity result is a separate contribution, but the novelty of the main algorithm and its analysis seems limited.

  2. My more important concern is that Theorem 5.4 appears false under the stated model. This is the main reason for my strong reject recommendation for the current manuscript. In Appendix A.3, the two-packet construction assigns OPT the cost (1−ρ)(t+ε)(1-\rho)(t+\varepsilon), omitting the acknowledgment cost. OPT actually pays ρ+(1−ρ)(t+ε)\rho+(1-\rho)(t+\varepsilon). The online algorithm must also acknowledge the second packet, so the claimed ratio does not follow.

    Beyond this proof error, consider the following deterministic counteralgorithm. Normalize time and cost so that an acknowledgment costs 11 and waiting incurs cost at rate 11. Initially follow Trust: acknowledge immediately when the predicted next gap exceeds 11; otherwise wait for the predicted arrival. At the first detected prediction error, permanently switch to Classic. An error is detected when an arrival occurs earlier than predicted or a predicted arrival fails to occur. In the latter case, acknowledge any pending packets immediately before switching.

    With perfect predictions, this algorithm follows the optimal schedule, so it is 1-consistent. It also appears to be at most 3-robust. Writing dj=aj+1−ajd_j=a_{j+1}-a_j, the offline optimum satisfies OPT=1+∑j=1n−1min⁡(dj,1).OPT=1+\sum_{j=1}^{n-1}\min(d_j,1). Before the first erroneous prediction, the algorithm's gap contributions equal OPT's. On the first erroneous gap, its contribution exceeds OPT's by at most 1: it either acknowledges immediately for cost 1, waits until an early arrival at no excess cost, or acknowledges at a missed predicted gap h≤1h\le1 for cost 1+h1+h, while OPT's contribution is at least hh. Afterward, Classic's contributions are at most twice OPT's, including the terminal acknowledgment. Consequently, ALG≤2OPT+1≤3OPT.ALG \le 2OPT+1 \le 3OPT. Taking λ=1/4\lambda=1/4, Theorem 5.4 requires any algorithm with consistency at most 1.25 to have robustness at least 5, contradicting these guarantees. Thus, this appears to invalidate the claimed Pareto optimality, rather than merely leave its proof incomplete.

Questions for authors

Is my understanding correct that Theorem 5.4 applies to all deterministic algorithms, including algorithms that remember prediction errors and permanently stop using predictions? Does the algorithm above achieve 1-consistency and robustness at most 3 under your model? If not, please identify the step that fails or the assumption that excludes it.

3 comments
AuthorsOpenReview ↗

Theorem 5.4 correction and the ski-rental connection

Thank you for identifying the problem with Theorem 5.4 and giving a counterexample.

The original Theorem 5.4. Yes, your fallback algorithm is valid in our model and disproves the original claim. We note that, in the proposed algorithm, a single small timestamp error can trigger a permanent switch to Classic. Even if all subsequent gaps are long and predicted exactly, the fallback still waits a full break-even period before each ACK, and its competitive ratio on such inputs can approach 22.

The revised theorem. Theorem 5.4 now gives the exact minimum robustness R⋆(κ)=1+1+1+4κ2κR_\star(\kappa) = 1 + \frac{1 + \sqrt{1 + 4\kappa}}{2\kappa} for deterministic algorithms with consistency at most κ\kappa, for 1≤κ≤21 \leq \kappa \leq 2. Our new algorithm, BudgetAlarm, attains it. The optimal robustness is about 2.6182.618 at perfect consistency and 2.3802.380 at consistency 1.251.25. The matching lower bound in Appendix A.3 allows arbitrary history-dependent policies. At matched consistency 1.251.25 and low noise on MAWI (η≈0.245\eta \approx 0.245), both AugmentedAlarm and BudgetAlarm average about 1.0351.035 times OPT\mathrm{OPT}, compared with 1.1051.105 for Classic (Appendix C).

Connection to ski rental. Section 2 now explicitly credits AugmentedAlarm’s timers as a direct adaptation of the deterministic ski-rental construction of Purohit, Svitkina, and Kumar (2018). As you point out, each gap is a rent-or-buy decision, and summing the local bounds gives AugmentedAlarm’s consistency and robustness guarantees. Theorems 5.1 and 5.2 use the timestamp error to give its exact, continuous curve. The matching examples repeat gaps that make the timer expire before the next arrival, so the final ACK contributes a vanishing fraction of the total cost.

The deterministic ski-rental frontier gives robustness 1+1κ−11 + \frac{1}{\kappa - 1} for 1<κ≤21 < \kappa \leq 2. The optimal frontier for acknowledgment is different because decisions interact across gaps. BudgetAlarm tracks the excess of its cost on completed gaps over R⋆R_\star times their offline cost. It uses a safe timer when the excess is positive and returns to prediction-based timers when the excess falls back to zero or below. At matched consistency κ=1.25\kappa = 1.25 and normalized error 0.400.40, AugmentedAlarm’s worst-case ratio is about 2.0832.083 and BudgetAlarm’s is about 2.3802.380. Appendix A.4 and Figure 3 give the comparison across error levels.

Dear Reviewer,

As the discussion period is approaching its end, we wanted to kindly follow up and ask whether you have had an opportunity to examine our rebuttal and revised manuscript.

We are grateful for your identification of the error in the original Theorem 5.4. In response, we have replaced the incorrect claim with a new result establishing the exact consistency–robustness frontier for deterministic algorithms, attained by our new history-dependent algorithm, BudgetAlarm. We have also clarified the connection between AugmentedAlarm and learning-augmented ski rental.

We would greatly appreciate your assessment of these revisions, particularly whether they address your principal concerns regarding soundness and novelty. We would be happy to clarify any remaining questions.

Thank you again for your careful review and constructive feedback.

Thank you for the detailed response and for revising the paper. The new BudgetAlarm algorithm and the proof of the revised Theorem 5.4 appear sound to me, and they address my main correctness concern. I also appreciate the added discussion of the ski-rental connection.

I am raising my score to weak reject. I still find the overall contribution moderate, although the new algorithm and frontier analysis make the paper stronger. In fact, I consider these among the most substantial contributions of the revised paper. Since they were introduced during rebuttal, I leave it to the AC to decide whether this degree of revision should be taken into account in the final decision.

Comments on the paper

2 comments
AuthorsOpenReview ↗

Correction to Theorem 5.4 and the new Pareto-optimality result

We thank the reviewers for identifying the error in the submitted Theorem 5.4. We agree that the claim of Pareto optimality for AugmentedAlarm was incorrect, and we have replaced the theorem accordingly. The revised manuscript, including the new experiments, is now available on OpenReview.

The correction is confined to the old Theorem 5.4, namely the Pareto-optimality claim. Our other theoretical results hold as stated, including AugmentedAlarm’s exact error-dependent competitive ratio (Theorems 5.1 and 5.2), its consistency and robustness guarantees (Corollary 5.3), and the impossibility result for algorithms with sublinear advice (Theorem 6.1). In particular, AugmentedAlarm’s guarantee degrades continuously as predictions become less accurate.

The revised Theorem 5.4 determines the best worst-case guarantee any deterministic algorithm can achieve for each target competitive ratio between 1 and 2 under perfect predictions. In particular, we introduce a new history-dependent algorithm, named BudgetAlarm, which attains Pareto optimality with respect to consistency and robustness. For example, if we require a ratio of at most 1.25 with perfect predictions, BudgetAlarm achieves the optimal worst-case ratio of about 2.38 under arbitrary prediction errors. Section 5.2 presents the algorithm, and Appendix A.3 gives the proof.

AugmentedAlarm is particularly useful when performance needs to degrade gradually as forecasts become less accurate. At the same consistency, it can also give a tighter guarantee at intermediate prediction errors (Figure 3). In the new paired experiments at matched consistency (Appendix C), the two algorithms have similar mean costs overall, with AugmentedAlarm achieving a slightly lower mean cost than BudgetAlarm on all three workloads at the highest noise level tested.

Dear authors, dear reviewers,

thank you for engaging in the discussion on this paper.

@reviewers: please acknowledge the rebuttal by the authors. Decide whether their rebuttal affects your assessment and your score.

AC

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.