Data-Driven Solution Portfolios
Marina Drygala, Silvio Lattanzi, Andreas Maggiori, Miltiadis Stouras, Ola Svensson, Sergei Vassilvitskii · 2024
Read Data-Driven Solution Portfolios by Marina Drygala, Silvio Lattanzi, Andreas Maggiori, Miltiadis Stouras, Ola Svensson, Sergei Vassilvitskii (2024) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2412-00717.txt.
Introduction
Marina Drygala and five co-authors study how to pick a small set of candidate solutions under uncertainty in a 2024 paper. Many planning tasks hide key values until after choices are made. A planner can hedge by keeping several options and using the best one once facts arrive.
The formal task asks for a fixed number of solutions that maximize the expected value of the best among them. A knapsack example shows the idea, with item weights drawn from a known distribution. The authors extend the problem to a broad class of set systems called matroids. Good portfolios must be diverse and work against each other. The paper develops methods to build such sets with provable quality.
Catalog record
| CREATOR | Marina Drygala, Silvio Lattanzi, Andreas Maggiori, Miltiadis Stouras, Ola Svensson, Sergei Vassilvitskii |
|---|---|
| YEAR | 2024 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 137 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2412-00717
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Data-Driven Solution Portfolios Marina Drygala, Silvio Lattanzi, Andreas Maggiori, Miltiadis Stouras, Ola Svensson, Sergei Vassilvitskii Abstract 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 k potential solutions, with the goal of optimizing the value of the best solution. More formally, given a combinatorial problem Π \Pi , a set of value functions 𝒱 \mathcal{V} over the solutions of Π \Pi , and a distribution 𝒟 \mathcal{D} over 𝒱 \mathcal{V} , our goal is to select k k solutions of Π \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 r elements maximizing the total value. Now suppose that each element’s weight comes from a (known) distribution. How should we select k 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. 1 Introduction Worst-case analysis has long been the prevailing standard for assessing an algorithm’s performance. However, this approach often falls short in capturing the real-world performance of algorithms, as instances encountered in practice often differ significantly from those that define worst-case scenarios. To address this discrepancy, the field of Data-Driven Algorithm Design has sought to create algorithms that utilize past data about a problem, either implicitly or explicitly, and provably achieve superior performance on the typical instances that arise in practical applications. For surveys of this area see [ MV22 , Bal20 ] . Building on this line of research, we study the portfolio optimization problem as a simple framework for speeding up algorithms using historical data; a method with potential applications across various combinatorial problems. Specifically, given a combinatorial problem \Pi , a solution set \mathcal{I} , and a distribution \mathcal{D} over value functions (which map solutions to values, with each function representing a different scenario), our objective is to compute a portfolio of k solutions that maximizes (or minimizes) the expected value (or cost) of the best among the k solutions. Starting from a different perspective, Kleinberg, Papadimitriou and Raghavan [ KPR04 ] have defined a very similar family of optimization problems, called “Segmentation Problems”. The Portfolio Optimization problem can be seen as a stochastic version of the aforementioned family of problems; actually the two definitions are effectively equivalent when the distribution over value functions has a polynomial-sized support (for more details see Related Work, Section 1.2 ). The Portfolio Optimization problem captures many natural questions. The problem mentioned in the abstract–how to select k bundles of r items each so that the expected value of the best bundle is maximized–is only one of them. Another practical application is finding the shortest path between two points (e.g., home and work) in a city, under varying daily traffic conditions. Here, the solution set consists of all possible source-destination paths and the value functions assign weights to each path based on specific traffic scenarios. The distribution over value functions models the stochastic nature of traffic. Rather than rerunning a shortest-path algorithm for each new instance, one could leverage the statistical knowledge about traffic patterns to precompute a few paths that cover different likely scenarios (e.g., peak morning traffic, light nighttime traffic, etc.). This approach, then, allows us to quickly evaluate the precomputed paths under new traffic conditions and select the best option without the need to resolve the problem from scratch each time. Interestingly, this stochastic formulation also captures problems outside the area of speeding up algorithms. In particular, our objective captures any stochastic problem where one needs to select a set of dependent objects with the goal of maximizing the expectation of their maximum. A practical example of this is sports betting pools, which was recently explored in [ DBC+24 ] . The authors examine the scenario of participating in a betting pool for a basketball tournament, where individuals can pay a fee to submit a prediction for the outcome of all tournament matches, with the potential to win a substantial monetary prize if their predictions are accurate. Given a budget constraint on the number of entries that a person can submit, the technical problem essentially reduces to computing a portfolio of entries that maximizes the probability that one of the selected entries succeeds. From a technical standpoint, in the maximization variant of our problem, the value of a portfolio is a submodular function. Therefore, one can find an approximately optimal portfolio by running the Greedy algorithm, with a running time that is polynomial in the size of the solution set \mathcal{I} . However, for most interesting problems, e.g., spanning trees, entries in betting pools, etc., the solution set is given implicitly and is usually exponentially large in the size of the input, making Greedy inefficient. This raises the natural question of whether one can compute approximately optimal portfolios, for interesting problems, with a running time that is polynomial in the size of the input. 1.1 Our contributions The first important contribution of our paper is conceptual: we formulate the Portfolio Optimization problem from a new, stochastic, viewpoint and show that it captures many interesting scenarios. On the technical side, we focus on constructing solution portfolios for the fundamental problem of optimization under matroid contraints. We examine the simplified case where each element of the matroid’s ground set takes a 0-1 value, independently, with some known probability, and the value of a set is the sum of the values of its elements. Despite its simplicity, this case captures many core challenges of constructing solution portfolios and proves to be technically challenging. As we discuss in Section 3 , this problem differs fundamentally from classical problems in the area of randomized algorithms, because constructing effective portfolios requires leveraging the “anti-concentration” properties of various solutions. Additionally, employing standard tools from the literature, such as contention resolution schemes, presents challenges due to the nature of our objective function. In particular, the value of a portfolio depends heavily on “abnormal” events, such as significant deviations from the expected value, occurring in one of its k solutions. However, contention resolution schemes do not offer per-instance guarantees but rather only work on expectation. Therefore, we need to take extra care to apply these results while conditioning on those events. The main technical contribution of our work is to design an algorithm with polynomial running time in the size of the matroid’s ground set which constructs a portfolio that is a \Theta(1) -approximation of the optimal portfolio. We give a high-level description of our techniques in Section 3 , present a simpler algorithm for the case of uniform matroids in Section 4 and present our general algorithm in