size $l$. This solution is then *completed at test time*, by, e.g., running $k-l$ further rounds of greedy on the new task, to obtain a task-specific solution of size $k$.

Submodular Cross-Learning
-------------------------

\[pr: cross-learning submodular\] Let $f_i:2^{\mathcal{X}}\xrightarrow{}{\mathbb{R}}_+$ for $i\in [m-1]$, be a monotone submodular function over ground set ${\mathcal{X}}$. We want to find $S_m$ with size at most $l$ whose subests with average size of at most $k$ maximize the sum of $f_i$ for $i\in [m-1]$, more formally:

$$\max_{S_m\subseteq {\mathcal{X}}, \mid S_m \mid\leq l}\;\sum_{i=1}^{m-1}\; \max_{S_i\subseteq S_m,\; \frac{1}{m-1}\sum\limits_{i=1}^{m-1} \mid S_i\mid \leq k}\; f_i(S_i)$$

\[eq:cross-learning submodular\] $$\begin{aligned}
{2}
    &\operatorname*{maximize}&&\sum_{i=1}^{m-1}\; \; f_i(S_i) \\
    &\operatorname*{subject\,\, to \quad}&& {S_m\subseteq {\mathcal{X}}, \mid S_m \mid\leq l}    \\
    & && {S_i\subseteq S_m,\; \frac{1}{m-1}\sum\limits_{i=1}^{m-1} \mid S_i\mid \leq k}\end{aligned}$$ \[eq:basic-formulation\]

Algorithms for Discrete Submodular Meta-Learning {#sec:algorithms_ML}
================================================

Solving Problem requires finding a set ${S_{\rm{tr}}}$ for the outer maximization and sets $\{S_i\}_{i=1}^m$ for the inner maximization. In this section, we describe our proposed greedy-type algorithms to select the elements ${S_{\rm{tr}}}$ and $\{S_i\}_{i=1}^m$. As we deal with $m+1$ sets, the order in which the sets ${S_{\rm{tr}}}$ and $\{S_i\}_{i=1}^m$ are updated becomes crucial, i.e., it is not clear which of the sets ${S_{\rm{tr}}}$ or $S_i$’s should be preferably updated in each round 