of size $l$ overall all possible choices of task when a best subset of size $k-l$ is added to that. In fact, if we define $f_i'({S_{\rm{tr}}}):=\max_{S_i\in V, |S_i|\leq k-l} f_i({S_{\rm{tr}}}\cup S_i)$, then we can rewrite the problem in as $$\max_{{S_{\rm{tr}}}\in V, |{S_{\rm{tr}}}|\leq l} \ \mathbb{E}_{i \sim p}\;  \left[ f_i'({S_{\rm{tr}}}) \right].$$

As described previously, we often do not have access to the underlying probability distribution $p$ of the tasks, and we instead have access to a large number of sampled tasked that are drawn independently according to $p$. Hence, instead of solving , we solve its sample average approximation given by $$\label{eq:ML_submodular_sample_avg}
    \max_{{S_{\rm{tr}}}\in V, |{S_{\rm{tr}}}|\leq l} \ \frac{1}{m}\sum_{i=1}^m\;  \left[\max_{S_i\in V, |S_i|\leq k-l} f_i({S_{\rm{tr}}}\cup S_i)\right]\ = \ \max_{{S_{\rm{tr}}}\in V, |{S_{\rm{tr}}}|\leq l} \ \frac{1}{m}\sum_{i=1}^m\;  \left[ f_i'({S_{\rm{tr}}}) \right],$$ where $m$ is the number of tasks in the training set which are sampled according to $p$. Even though the functions $f_i$ are submodular, $f'_i$ *is not submodular* or $k$-submodular [@ohsaka2015monotone] (see Appendix \[sec:counter\_example\] for specific counter examples). Hence, Problem  is not a submodular maximization problem. In the next section, we present algorithms for solving Problem  with provable guarantees.

We finally note that Problem  will be solved at *training* time to find the solution ${S_{\rm{tr}}}$ of 