Learned Predictions for Data Structures and Running Time

We initiate a systematic study of utilizing predictions to improve over approximation guarantees of classic algorithms, without increasing the running time. We propose a systematic method for a wide class of optimization problems that ask to select a feasible subset of input items of minimal (or maximal) total weight. This gives simple (near-)linear time algorithms for, e.g., Vertex Cover, Steiner Tree, Min-Weight Perfect Matching, Knapsack, and Clique. Our algorithms produce optimal solutions when provided with perfect predictions and their approximation ratios smoothly degrade with increasing prediction error. With small enough prediction error we achieve approximation guarantees that are beyond reach without predictions in the given time bounds, as exemplified by the NP-hardness and APX-hardness of many of the above problems. Although we show our approach to be optimal for this class of problems as a whole, there is a potential for exploiting specific structural properties of individual problems to obtain improved bounds; we demonstrate this on the Steiner Tree problem. We conclude with an empirical evaluation of our approach.

The talk discusses two of the most fundamental problems in algorithms and data structures through the lens of algorithms-with-predictions: sorting and priority queues. We consider different types of predictions and show how these can be used to improve running time and comparison complexity of algorithms. In one setting, the algorithm is given predictions about the rank of items, and in another setting, the algorithm has access to quick-and-dirty comparisons to complement much slower exact comparisons. We obtain simple algorithms with optimal guarantees and favorable experimental performance in sorting tasks as well as when applied to Dijkstra’s shortest path algorithm.

Ski rental was one of the first problems to be considered in the algorithms with predictions literature. We revisit this problem from the perspective of distributional predictions. We give an algorithm with optimal additive loss as a function of the earth mover’s distance between the predicted distribution and the true distribution, and show both analytically and experimentally that in many natural settings distributional predictions allow for significantly better performance than traditional point predictions.

We initiate the study of tree structures in the context of scenario-based robust optimization. Specifically, we study Binary Search Trees (BSTs) and Huffman coding, two fundamental tech- niques for efficiently managing and encoding data based on a known set of frequencies of keys. Given k different scenarios, each defined by a distinct frequency distribution over the keys, our objective is to compute a single tree of best-possible performance, relative to any scenario. We consider, as performance metrics, the competitive ratio, which compares multiplicatively the cost of the solution to the tree of least cost among all scenarios, as well as the regret, which induces a similar, but additive comparison. For BSTs, we show that the problem is NP-hard across both metrics. We also show how to obtain a tree of competitive ratio $\lceil {\log }_2(k+1)\rceil$, and we prove that this ratio is optimal. For Huffman Trees, we show that the problem is, likewise, NP-hard across both metrics; we also give an algorithm of regret $\lceil {\log }_{2}k\rceil$, which we show is near-optimal, by proving a lower bound of $\lfloor {\log }_{2}k\rfloor$. Last, we give a polynomial-time algorithm for computing Pareto-optimal BSTs with respect to their regret, assuming scenarios defined by uniform distributions over the keys. This setting captures, in particular, the first study of fairness in the context of data structures. We provide an experimental evaluation of all algorithms. To this end, we also provide mixed integer linear program formulation for computing optimal trees.

Key-value stores and search engines are posing a continuously growing need to efficiently store, retrieve and analyze massive sets of keys under the many and different requirements posed by users, devices, and applications. Such a new level of complexity could not be properly handled by known data structures, so that academic and industrial researchers started recently to devise new approaches that integrate classic data structures with various kinds of advanced techniques drawn from data compression, computational geometry and machine learning, hence originating what are currently called “Learned Data Structures”. In this talk, I’ll survey the evolution of these kinds of data structures, discuss their theoretical and experimental performance, highlight their limits, and point out new challenges worth of future research.

The list-labeling problem is a fundamental data structural primitive which captures the basic task of storing a dynamically changing set of up to $N$ elements in sorted order in an array of size $M=\mathrm{\Theta }(N)$. The goal is to support online insertions and deletions while moving elements around in the array as little as possible. Despite over four decades of study, there has until recently been a longstanding gap between the upper and lower bounds for list labeling $(O({\log }^2(N))$ and $\mathrm{\Omega }(\log (N))$ element moves per operation, respectively). This gap was narrowed in 2022 by Bender et al. with a randomized history-independent algorithm with $O({\log }^{1.5}(N))$ cost, and they showed a matching lower bound for history-independent list-labeling algorithms. In recent work, we nearly close the gap by providing an $\tilde{O}(\log (N))$ algorithm which leverages the workload’s history of operations. We do this by building a randomized predictor of future operations that performs well on all inputs in expectation. Combining this with a prediction-augmented algorithm, we achieve an improved worst-case upper bound.

This talk will survey a recent trend through which history independence – a widely-studied privacy property in the data-structures literature – has been used as an algorithmic tool, not just for privacy, but for building faster and better data structures.

In this paper, we consider a new problem of portfolio optimization using stochastic information. In a setting where there is some uncertainty, we ask how to best select $k$ potential solutions, with the goal of optimizing the value of the best solution. More formally, given a combinatorial problem $\mathrm{\Pi }$, a set of value functions $V$ over the solutions of $\mathrm{\Pi }$, and a distribution $D$ over $V$, our goal is to select $k$ solutions of $\mathrm{\Pi }$ that maximize or minimize the expected value of the best of those solutions. For a simple example, consider the classic knapsack problem: given a universe of elements each with unit weight and a positive value, the task is to select $r$ elements maximizing the total value. Now suppose that each element’s weight comes from a (known) distribution. How should we select $k$ different solutions so that one of them is likely to yield a high value?

In this work, we tackle this basic problem, and generalize it to the setting where the underlying set system forms a matroid. On the technical side, it is clear that the candidate solutions we select must be diverse and anti-correlated; however, it is not clear how to do so efficiently. Our main result is a polynomial-time algorithm that constructs a portfolio within a constant factor of the optimal.

The main bottleneck in designing efficient dynamic algorithms is the unknown nature of the update sequence. In particular, there are some problems, like triconnectivity, planar digraph all pairs shortest paths, k-edge connectivity, and others, where the separation in runtime between the best offline or partially dynamic solutions and the best fully dynamic solutions is polynomial, sometimes even exponential. In this talk, we introduce the predicted-updates dynamic model, one of the first beyond-worst-case models for dynamic algorithms, which generalizes a large set of well-studied dynamic models including the offline dynamic, incremental, and decremental models to the fully dynamic setting when given predictions about the update times of the elements. In the most basic form of our model, we receive a set of predicted update times for all of the updates that occur over the event horizon. We give a novel framework that “lifts” offline divide-and-conquer algorithms into the fully dynamic setting with little overhead. Using this, we are able to interpolate between the offline and fully dynamic settings; when the ${\mathrm{\ell }}_1$ error of the prediction is linear in the number of updates, we achieve the offline runtime of the algorithm (up to poly log n factors). The second part of the talk will feature experimental results on how feasible it is to obtain these predictions in real-world graphs. We discuss new results that learn deletion times in dynamic networks using a very simple linear regression framework based on a set of features we find for our testing datasets.

This talk is about recent results for how predictions can improve online algorithms for list labelling, online cycle detection, and incremental shortest paths. In each case, the main idea of the technique is to use predictions to decompose the input into smaller pieces which can be solved more efficiently. I will discuss how this technique works, as well as how to use it in the future: both the potential to apply it to new problems, and common challenges that may arise.

This talk explores the emerging area of algorithms with predictions, also known as learning-augmented algorithms. These methods incorporate machine-learned predictions into algorithmic design, allowing the algorithms to adapt to input distributions and achieve improved performance in runtime, space, or solution quality. The presentation will highlight recent advances in leveraging predictions to enhance the efficiency of discrete algorithms. The goal is to overview the breadth of the uses of the model in numerous areas, showcasing prior work and examples.

This will be a talk about the travelling salesperson problem. I will show how to improve upon the approximation guarantees of the classic Christofides algorithm by using per-edge predictions as to whether the edge is part of the optimal TSP tour. Our algorithm can be seen as a tool for turning a probabilistic heatmap, produced by a deep neural network, into a discrete solution – which is a crucial step in pipelines of modern neural network solvers for TSP and other combinatorial optimization problems. I will present preliminary empirical results comparing our algorithm to other typical solutions for that step.

In the strategic facility location problem, a set of agents report their locations in a metric space and the goal is to use these reports to open a new facility, minimizing an aggregate distance measure from the agents to the facility. However, agents are strategic and may misreport their locations to influence the facility’s placement in their favor. The aim is to design truthful mechanisms, ensuring agents cannot gain by misreporting. This problem was recently revisited through the learning-augmented framework, aiming to move beyond worst-case analysis and design truthful mechanisms that are augmented with (machine-learned) predictions. The focus of this prior work was on mechanisms that are deterministic and augmented with a prediction regarding the optimal facility location. In this paper, we provide a deeper understanding of this problem by exploring the power of randomization as well as the impact of different types of predictions on the performance of truthful learning-augmented mechanisms. We study both the single-dimensional and the Euclidean case and provide upper and lower bounds regarding the achievable approximation of the optimal egalitarian social cost.

In this talk, I’ll provide an overview of streaming algorithms with predictions. I’ll begin with results for vector-based problems (e.g., frequency estimation, norm estimation, low-rank approximation), and then focus on the use of recent epsilon-accurate predictions in graph streaming settings, specifically for the Max-Cut problem.

Dynamic algebraic algorithms are data structures that maintain properties of matrices and vector spaces, such as matrix inverse, determinant, rank, etc. They are the main subroutine behind the best algorithms for many dynamic graph problems, such as maintaining reachability, maximum matching size, triangle detection, and many more.

In this talk, we will see techniques that accelerate dynamic algebraic algorithms when predictions about future updates are available. Via reductions, this allows to maintain fully dynamic triangle detection, maximum matching, single-source reachability, in $O(n^{\omega -1}+n{\eta }_i)$ worst-case update time. Here ${\eta }_i$ denotes how much earlier the $i$-th update occurs than predicted, and $\omega \tilde{2}.372$ is the matrix multiplication exponent. For comparison, there are conditional lower bounds that prove no non-trivial data structures are possible without predictions.

When designing algorithms for computational problems in practice, there is often ample data about the application domains in which these algorithms will operate. This data presents a valuable opportunity: it can be leveraged via machine learning (ML) to improve the performance of existing optimization algorithms, help practitioners select among different algorithms, and guide the discovery of entirely new algorithms. However, this promise hinges on several core challenges, including: How to align deep learning architectures with algorithmic tasks, Whether to integrate ML into existing algorithms or train them end-to-end for combinatorial tasks, How to supervise ML models on (NP-hard) algorithmic problems, where ground-truth labels are computationally expensive to obtain, and Whether we can provide robust theoretical guarantees for the resulting algorithms. This talk will showcase solutions through two case studies. The first uses graph neural networks to learn near-optimal online matching policies that generalize beyond their training regime. The second shows how large language models can configure integer programming solvers with only a handful of training instances.

Lazy search trees [1] are a comparison-based sorted dictionary that smoothly interpolates between binary search trees and efficient priority queues automatically, depending on use. In particular they support faster insertions if many elements are not queried. Lazy B-trees bring this trade-off to external memory. Lazy search trees (of either kind) achieve this interpolation by a beyond-worst-case view of operations on sorted dictionaries, in particular by taking the ranks of queries into account and avoiding insertions to be always preceded by a query. The talk also suggested considering predictions of upcoming queries towards further improvements.

Panelists: Sergei Vassilvitskii (Google – New Yor, US), Rob Johnson (Broadcom – San Jose, US) and Cindy Phillips (Sandia National Labs – Albuquerque, US)

During the coffee and cake break on Tuesday, we held an informal panel discussion on industry research. Participants asked our panelists questions about their experiences working in their current roles. The discussion was meant to mentor students and junior academics and to offer practical advice for those considering or engaging careers outside academia.

During the coffee break on Thursday, we held an informal gathering for all self-identifying women and non-binary participants at the workshop. The goal was to provide mentorship and networking opportunity for the junior members. The topics of discussion included teaching and advising challenges as well as career trajectories in academia and industry.