\subseteq V$ the following inequality holds $f_i(A) + f_i(B) \geq f_i(A \cup B) + f_i(A \cap B)$. Furthermore, $f_i$ is called monotone if for any $A \subseteq B$ we have $f_i(A) \leq f_i(B)$.

**Training and test tasks.** We assume access to a collection of *training* tasks $\{\mathcal{T}_i\}_{i=1}^m$. These are the tasks that we have already experienced, i.e., they correspond to the users that we have already seen. Formally, this means that for each training task $\mathcal{T}_i$, we assume knowledge of the corresponding function $f_i$. In our formulation, each of the training tasks is assumed to be generated i.i.d. according to the distribution $p$. Indeed, eventually we aim to optimize performance at *test* time, i.e., obtain the best performance for new and unseen tasks generated independently from the distribution $p$. For instance, in our recommendation setting, test tasks correspond to new users that will arrive in the future. Our goal is to use the training tasks to reduce the computation load at test time.

**Two extremes of computation.** Let us use $\mathcal{T}_{\rm test}$ (and $f_{\rm{test}}$) to denote the task (and its corresponding set function) that we aim to learn at test time. Ideally, if we have sufficient computational power, then we 