task arrives. This discussion also applies to any other greedy method (e.g., lazy or stochastic greedy). We now formally state this problem.

[0.21]{} ![image](train_tasks.pdf){width="1.0\linewidth" height="1\linewidth"}

[0.21]{} ![image](ERM.pdf){width="1.0\linewidth" height="1\linewidth"}

[0.21]{} ![image](new_task.pdf){width="1.0\linewidth" height="1\linewidth"}

[0.21]{} ![image](Str_1.pdf){width="1.0\linewidth" height="1\linewidth"}

**Discrete Meta-Learning.** As we discussed so far, when computational power is limited at test time, it makes sense to divide the process of choosing the best decision between training and test phases. To be more specific, in the training phase, we choose a subset of elements from the ground set that would perform over the training tasks, and then select (or optimize) the remaining elements at the test time *specifically* with respect to the task at hand. To state this problem, consider ${S_{\rm{tr}}}\subseteq V$ with cardinality $|{S_{\rm{tr}}}|=l$, where $l<k$, as the initial set that we aim to find at the training phase, and the set $S_i$ that we add to the initial set ${S_{\rm{tr}}}$ at test time (See Figure \[fig:toy\] for an illustration). Hence, the problem of interest can be written as $$\label{eq:ML_submodular}
    \max_{{S_{\rm{tr}}}\in V, |{S_{\rm{tr}}}|\leq l} \ \mathbb{E}_{i \sim p}  \Big[\max_{S_i\in V, |S_i|\leq k-l} f_i({S_{\rm{tr}}}\cup S_i)\Big],$$

Note that the critical decision variable that we need to find is ${S_{\rm{tr}}}$ which is the best initial subset 