Abstract: We study how to utilize (possibly machine-learned) predictions in a model for computing under uncertainty in which an algorithm can query unknown data. The goal is to minimize the number of queries needed to solve the problem. We consider fundamental problems such as finding the minima of intersecting sets of elements or sorting them (these problems can also be phrased as (hyper)graph orientation problems), as well as the minimum spanning tree problem. We discuss different measures for the prediction accuracy and design algorithms with performance guarantees that improve with the accuracy of predictions and that are robust with respect to very poor prediction quality. These measures are intuitive and might be of general interest for inputs involving uncertainty intervals. We show that our predictions are PAC learnable. We also provide new structural insights for the minimum spanning tree problem that might be useful in the context of explorable uncertainty regardless of predictions. Our results prove that untrusted predictions can circumvent known lower bounds in the model of explorable uncertainty. We complement our results by experiments that empirically confirm the performance of our algorithms.
Introduction
In the paradigm of explorable uncertainty, algorithms operate on inputs where exact values are initially unknown. Instead, each element is represented by an uncertainty interval (e.g., "this edge weight is between 5 and 10"). To reveal the true value, the algorithm must perform a "query," which incurs a cost. The objective is to minimize the total number of queries required to solve a specific problem, such as finding a Minimum Spanning Tree (MST) or sorting elements.
Traditionally, query policies are evaluated by their competitive ratio: the number of queries made compared to an optimal offline algorithm that knows the true values beforehand. For many fundamental problems, the best possible deterministic algorithm has a competitive ratio of 2. This research explores whether machine learning (ML) predictions can be used to bypass this theoretical limit while maintaining a safety net against inaccurate predictions.
The Learning-Augmented Framework
The proposed framework introduces a two-stage approach to utilize untrusted predictions:
- The Trust Phase: The algorithm identifies "prediction mandatory" elements—items that would be necessary to query if the ML predictions were perfectly accurate. To ensure robustness, the algorithm does not query blindly; it identifies "witness sets" (groups of elements where at least one must be queried in any valid solution) and queries them in a structured order.
- The Verification Phase: Once the predicted queries are completed, the algorithm transitions to a structural approach. For problems like finding the minimum element, this involves solving a Minimum Vertex Cover on a dependency graph of the remaining uncertain elements to complete the task optimally.
Quantifying Prediction Error
To evaluate the impact of prediction quality, the authors introduce two novel error measures: Mandatory Query Distance ($k_M$) and Hop Distance ($k_h$). The Hop Distance $k_h$ is particularly intuitive for interval-based uncertainty, as it counts how many interval boundaries a prediction "jumps" over relative to the true value.
These metrics allow for a formal definition of performance guarantees:
- $\alpha$-consistency: The competitive ratio achieved when predictions are perfect.
- $\beta$-robustness: The competitive ratio achieved when predictions are arbitrarily poor.
Performance and Results
The research proves that untrusted predictions allow algorithms to break the standard "2-competitive" barrier. Specifically, the authors achieve 1.5-consistency while maintaining 2-robustness, which represents the theoretical limit for this trade-off.
Experimental results on SATLIB interval sets and TSPLIB graphs confirm these theoretical findings. In simulations involving over 230,000 instances, the learning-augmented algorithms consistently outperformed traditional state-of-the-art "witness set" algorithms as long as the relative prediction error remained within reasonable bounds. Furthermore, the performance degrades gracefully as error increases, eventually matching the baseline performance rather than failing catastrophically.
Conclusion
By integrating ML predictions into query policies, this work demonstrates that it is possible to circumvent long-standing lower bounds in explorable uncertainty. The resulting algorithms are not only faster when predictions are accurate but also remain as safe as traditional methods when predictions fail. Future work may extend these concepts to stochastic settings or approximate solutions, further bridging the gap between theoretical query complexity and practical machine learning applications.
Summary updated