Data-Driven Solution Portfolios

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 $\mathrm{\Theta }(1)$-approximation of the optimal portfolio.

We give a high-level description of our techniques in Section 3 and present a simpler algorithm for the case of uniform matroids in Section 4. In the full version of the paper we show how this algorithm can be extended to work for all matroids.

The related work can be broadly categorized into three main directions. The first is the study of Segmentation Problems, initially introduced by Kleinberg, Papadimitriou and Raghavan [9]. This work, inspired by data mining techniques for market segmentation, defines a new class of optimization problems named Segmentation Problems. For any combinatorial optimization problem and a set $S$ of different cost vectors for this problem, the corresponding segmentation problem asks to partition the set $S$ into several segments and pick a separate solution for each segment, so that the total cost is minimized. The Portfolio Optimization problem can be seen as a stochastic variant of the aforementioned family of problems, where instead of a fixed set of cost vectors, one has access to a distribution over cost vectors and aims to optimize the expected value of the constructed portfolio. In fact, the two formulations are effectively equivalent when the distribution over cost vectors has a polynomial-sized support. This new, stochastic, viewpoint can accommodate a wider variety of applications where randomness is inherent in the problem at hand (e.g., sports betting, as introduced earlier). Besides that, it also enables the formulation of elegant and technically challenging theoretical questions, like the case where every element of a groundset takes a value independently of the other elements. Another adaptation of the family of “Segmentation Problems” is due to Gupta, Moondra and Singh [8] who examined a “robust” version of the problem. In this variant, the objective is to identify a small set of solutions that guarantees a good approximation for each one of the cost vectors of interest. This approach was motivated by fairness concerns, aiming to guarantee a good approximation across various cost vectors that may arise due to different fairness constraints.

On the technical side, Kleinberg et al. [9] study the Catalogue Segmentation problem, i.e. constructing portfolios for linear maximization with cardinality constraints. For the case where elements take values in $\{0,1\}$, they design an algorithm that runs in time $O(n^{k\log k}/\delta )$ and produces a portfolio that is a $(1-\delta )$-approximation, under the assumption that on every instance a large fraction of the items have value $1$. Our result is a $O(1)$ approximation with a running time that is polynomial in both $n$ and $k$, without the need of a density assumption, but for the case where the value of each element is independent of the values of other elements. Furthermore, our results extend to more general settings, accommodating any matroid constraints on the ground set.

The second related line of work is the area of Data-Driven Algorithm Design and specifically speeding up an algorithms’ execution by utilizing data. Some of these attempts include speeding up: the Greedy algorithm for submodular maximization [2, 15], the Hungarian algorithm for calculating maximum matchings [7], primal-dual algorithms for various graph problems [3], algorithms for flow problems [4, 5] and the Bellman-Ford algorithm [11]. The key distinction of our work lies in defining a new set of problems and providing general techniques for solving them.

A third relevant area of research is stochastic probing and online decision-making (for a detailed survey, see [14]). These problems typically involve a ground set of elements, each with an unknown stochastic weight sampled from a known distribution. The algorithm can probe certain elements – often incurring a cost – in order to reveal their weights. Based on these observations, it then selects a feasible subset and is rewarded with the weight of the selected items. A key distinction between this area and the Portfolio Optimization problem is that, in our setting, the solutions are chosen entirely offline, without observing any weights, and remain fixed across all possible realizations.

Our problem is more closely aligned with a non-adaptive strategy for stochastic probing. However, the variants of non-adaptive strategies studied in the literature typically impose only partial restrictions on the algorithm’s flexibility – for instance, requiring the algorithm to preselect which elements to probe but still allowing it to form its solution after observing the probed weights. In contrast, in the Portfolio Optimization problem, the selection is entirely offline, with no adjustments allowed after weights are realized. For this reasons, the benchmarks of the two problems are also different: non-adaptive strategies are evaluated against the optimal value achievable in hindsight, whereas our benchmark is the best offline strategy with the same constraints as the algorithm.

In this section we define the Portfolio Optimization problem in its general form, for any classical combinatorial problem. In the next section, we define the Matroid Portfolio Optimization problem, which is the portfolio problem for a special case of maximization with matroid constraints.

We present the maximization variant of our problem, with the minimization version defined in a similar manner. For any combinatorial problem $\mathrm{\Pi }$, the Portfolio Optimization problem is described by a tuple $𝒥=(ℐ,𝒱,𝒟,k)$ where $ℐ$ is the set of feasible solutions of problem $\mathrm{\Pi }$, $𝒱$ is a set of value functions from $ℐ$ to ${ℝ}_{\ge 0}$, $𝒟$ is a distribution over $𝒱$ and $k$ is a natural number that describes the desired size of the portfolio.

Our goal is to select $k$ solutions from $ℐ$ so as to maximize the expected value of the best of those solutions. That is, for a collection of $k$ sets $𝒮=\{S_1,\mathrm{\dots },S_k\}$ such that $S_i\in ℐ,\forall i\in \{1,\mathrm{\dots },k\}$ we define its value as:

Formally, we want to solve the following optimization problem.

We remark that the solutions $S_1,\mathrm{\dots },S_k$ are chosen offline, without observing the realized value function, but rather only by using our knowledge about the distribution $𝒟$.

For any input tuple $𝒥$, we denote by $𝒪(𝒥)=\{O_1(𝒥),\mathrm{\dots },O_k(𝒥)\}$ the optimal portfolio, that is the maximizer of the above optimization problem. To ease notation, whenever the input and the algorithm are clear from the context we use $𝒪=\{O_1,\mathrm{\dots },O_k\}$ and OPT to denote the optimum solution and its value respectively.

For an algorithm ALG we denote by ${𝒮}_{\text{ALG}(𝒥)}$ its output on input $𝒥$. We say that ALG is a $c$-approximation if it always outputs a collection of feasible solutions and:

where the expectation is taken over the internal randomness of ALG.

In the maximization variant of the problem, the value of a set of solutions, defined as the expected maximum of their values, is a monotone submodular function, as demonstrated by Kleinberg and Raghu [10]. Consequently, the celebrated Greedy algorithm of [13] is a $(1-1/e)$ approximation that runs in polynomial time in the size of the solution set $ℐ$. Without imposing any further restrictions to the problem, this is the best approximation ratio one can achieve, as the Max-$k$-Cover problem can be reduced to the Portfolio Optimization problem. The details of the reduction are deferred to the full version of the paper.

Although Greedy achieves the optimal approximation ratio for this problem, its running time is impractical for most interesting applications like max-$k$-cover, knapsack, shortest paths, spanning trees, etc. In all of the aforementioned applications, the set of feasible solutions is given implicitly and is exponentially large in the size of the input. Therefore, one needs to have a running time that is polynomial in the description of the solution set, rather than its size. 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 description of the solution set $ℐ$.

In this work, we focus on the fundamental case of optimization over matroid contraints and answer the latter question affirmatively for a natural distribution over value functions. We formulate this problem in the following section.

The Matroid Portfolio Optimization problem is a special case of the Portfolio Optimization problem, where the set of feasible solutions, $ℐ$, is the family of independent sets of an underlying matroid $M=(E,ℐ)$ (see Definition 1). The set $𝒱$ of value functions is the set of all additive set functions that map the elements of $E$ to $\{0,1\}$. Formally, for any value function $u\in 𝒱$, element $e\in E$ and subset $S\subseteq E$ we have: $u(\{e\})\in \{0,1\}$ and $u(S)={\sum }_{e^{\prime }\in S}u(\{e^{\prime }\})$. Throughout the paper we use the term “active” to denote an element $e\in E$ that takes value one, under a specific value function, and the term “inactive” to describe an element with value zero.

We assume that $𝒟$ is such that each element $e\in E$ is active with probability $p_e$, independently of the values of the rest of the elements of $E$. Formally,

To simplify the notation we define an equivalent distribution ${𝒟}^{\prime }$ over subsets of $E$, that represent the set of active elements, such that

and

In other words, instead of sampling a value function that assigns $\{0,1\}$ values to the elements, we can equivalently sample the set of active elements and, thus, switch to distributions over subsets of $E$. Also, the value of any set $S\subseteq E$ will now be equal to the random variable $|S\cap A|$, where $A$ is the random set denoting the active elements.

For the remainder of the paper, the input to the Matroid Portfolio Optimization problem will be described by a triplet $𝒥=(M,k,𝒟)$, where $M=(E,ℐ)$ is a matroid over the ground set $E$, $k$ a natural number describing the desired size of the portfolio and $𝒟$ is a distribution over subsets of $E$ such that each element $e\in E$ is included in a sample, independently, with probability $p_e$. For a collection $𝒮=\{S_1,\mathrm{\dots },S_k\}$ such that $S_i\in ℐ,\forall i\in \{1,\mathrm{\dots },k\}$, we define its value as

In this subsection we introduce notation and give some preliminary definitions. First, for any positive integer $\mathrm{\ell }$ we use the shorthand $[\mathrm{\ell }]$ to denote the set $\{1,\mathrm{\dots },\mathrm{\ell }\}$. In addition, we give the definition of matroids below.

For a matroid $M=(E,ℐ)$ the elements of $ℐ$ are called the independent sets of $M$. The rank function of a matroid $M$, $r_M:2^E\to \mathbb{N}$, maps each set $U\subseteq E$ to the size of the largest independent set contained in $U$. We use the term “rank of a matroid $M$” to denote the rank $r$ of the ground set, i.e. $r=r_M(E)$. A set $B\subseteq E$ is called a base if and only if it’s a maximum size independent set. In addition, the span of a set $S\subseteq E$ is defined as ${\text{span}}_M(S)=\{e\in E:\text{rank}(S\cup \{e\})=\text{rank}(S)\}$.

The matroid polytope $𝒫(M)$, of a matroid $M$, is a subset of ${ℝ}^{|E|}$ that is defined by the following sets of inequalities, where $r_M$ is the rank function of $M$.

It is well known that one can check whether some $x\in {ℝ}^{|E|}$ lies in the matroid polytope, that is $x\in 𝒫(M)$, in polynomial time in the size of $E$.

The first approach for this problem is simply to pick the $k$ independent sets with the highest expected value. Of course, it makes sense to enforce that these independent sets are disjoint, since we want them to “complement” each other. If these sets had large pairwise intersections, we would observe no benefit from selecting $k$ of them instead of one. In other words, a natural strategy is to pick the highest expectation subset, remove it from the ground set, continue by picking the highest expectation subset of the remaining elements and so on. However, this approach will fail to construct a good portfolio.

Intuitively, in some cases it is better to restrict ourselves to considerably less disjoint subsets and complete our portfolio by combining those subsets in a clever way, instead of using new subsets that might have lower expectation. For example, consider the instance where we need to pick $k$ subsets of size $r=k$ and we have $n=r^2$ elements available. Let the first $k\log k$ elements have activation probability $1/k$, and the rest to have activation probability $1/k^2$. The approach described above will form $k$ disjoint subsets, out of which $\log k$ will behave as independent binomials with expectation $1$ and the rest will be independent binomials with expectation $1/k$. The value of this portfolio will be dominated by the expectation of the maximum of the first $\log k$ binomials, which is $O(\log \log k)$. Surprisingly, instead of using the lower probability elements, one can pick $k$ solutions by uniformly combining parts of the first $\log k$ subsets and construct a portfolio that has value $\mathrm{\Theta }(\log k/\log \log k)$, which is asymptotically optimal (we describe this construction in the full version of the paper). This example showcases the power of having a clever “mixing” strategy as this can boost the portfolio to achieve an exponentially better value than a portfolio that only uses disjoint solutions. In fact, in this example, a strategy that picks only disjoint solutions would need $k$ disjoint subsets of expectation $1$ in order to achieve the same value as the one achieved by uniformly mixing $\log k$ subsets of expectation $1$.