and we obtain the best possible guarantee for the new task, but at the cost of performing computationally expensive operations (e.g., full greedy) at the test time. In the second approach, by solving in the training phase, we obtain a solution that possibly performs reasonably without any computation at the test phase, but the quality of the solution may not be as good as the first option. In summary, there exists a trade-off between the required computational cost at the test time and the performance guarantee on the unseen task. Hence, a fundamental question that arises is what would be the best scheme at the training phase assuming that at test time we have some limited computational power. For instance, in the monotone submodular case, assume that instead of running the greedy algorithm for $k$ rounds, which has a complexity of $\mathcal{O}(kn)$, we can only afford to run $\alpha k$ rounds of greedy at test time, which has a complexity of $\mathcal{O}(\alpha nk)$, where $\alpha\in(0,1)$ is small. In this case, a natural solution would be to find an appropriate set of $(1-\alpha)k$ elements in the training phase, and add the remaining $\alpha k$ elements at test time when a new 